К разделу 'Компьютерная Графика' сайта AlgoList.







ОСНОВЫ 3D ГРАФИКИ
2.4. Рисование одноцветного треугольника

Без понимания того, как рисовать залитый одним цветом треугольник, дальше лезть в 3D графику явно не стоит. Поэтому вот объяснение.

Возьмем любой треугольник. Его изображение на экране - набор горизонтальных отрезков, причем из-за того, что треугольник - фигура выпуклая, каждой строке экрана соответствует не более одного отрезка. Поэтому достаточно пройтись по всем строкам экрана, с которыми пересекается треугольник (то есть, от минимального до максимального значения y для вершин треугольника), и нарисовать соответствующие горизонтальные отрезки.

рисунок (illu/illu24a.gif) рисунок (illu/illu24b.gif)

Отсортируем вершины так, чтобы вершина A была верхней, C - нижней, тогда у нас min_y = A.y, max_y = C.y, и нам надо пройтись по всем линиям от min_y до max_y. Рассмотрим какую-то линию sy, A.y <= sy <= C.y. Если sy < B.y, то она пересекает стороны AB и AC; если sy >= B.y - то стороны BC и AC. Мы знаем координаты всех вершин, поэтому мы можем написать уравнения сторон и найти пересечение нужной стороны с прямой y = sy. Получим два конца отрезка. Так как мы не знаем, какой из них левый, а какой правый, сравним их координаты по x и обменяем значения, если надо. Рисуем этот отрезок, повторяем процедуру для каждой строки - и вуаля, трегуольник нарисован.

Остановимся более подробно на нахождении пересечения прямой y = sy (текущей строки) и стороны треугольника, например AB. Напишем уравнение прямой AB в форме x = k*y+b:

x = A.x+(y-A.y)*(B.x-A.x)/(B.y-A.y)

Подставляем сюда известное для текущей прямой значение y = sy:

x = A.x+(sy-A.y)*(B.x-A.x)/(B.y-A.y)

Вот, в общем-то, и все. Для других сторон пересечение ищется совершенно точно так же. А вот и пример кода.

// ...
// здесь сортируем вершины (A,B,C)
// ...
for (sy = A.y; sy <= C.y; sy++) {
  x1 = A.x + (sy - A.y) * (C.x - A.x) / (C.y - A.y);
  if (sy < B.y)
    x2 = A.x + (sy - A.y) * (B.x - A.x) / (B.y - A.y);
  else
    x2 = B.x + (sy - B.y) * (C.x - B.x) / (C.y - B.y);
  if (x1 > x2) { tmp = x1; x1 = x2; x2 = tmp; }
  drawHorizontalLine(sy, x1, x2);
}
// ...

Надо, правда, защититься от случая, когда B.y = C.y - в этом (и только этом, потому как если C.y = A.y, то треугольник пустой и рисовать его не стоит, или можно рисовать горизонтальную линию; а если B.y = A.y, то sy >= A.y и до деления на B.y - A.y не дойдет) случае произойдет попытка деления на ноль. Код изменится совсем чуть-чуть:

// ...
// здесь сортируем вершины (A,B,C)
// ...
for (sy = A.y; sy <= C.y; sy++) {
  x1 = A.x + (sy - A.y) * (C.x - A.x) / (C.y - A.y);
  if (sy < B.y)
    x2 = A.x + (sy - A.y) * (B.x - A.x) / (B.y - A.y);
  else {
    if (C.y == B.y)
      x2 = B.x;
    else
      x2 = B.x + (sy - B.y) * (C.x - B.x) / (C.y - B.y);
  }
  if (x1 > x2) { tmp = x1; x1 = x2; x2 = tmp; }
  drawHorizontalLine(sy, x1, x2);
}
// ...

Вот и все. Ну, горизонтальную линию, надеюсь, нарисовать сумеют все желающие.



 в самое начало


demo.design
3D programming FAQ