Быстрый вывод треугольника

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

Отсортируем вершины так, чтобы вершина A была верхней, C - нижней, тогда у нас min_y = A.y, max_y = C.y, и нам надо пройтись по всем линиям от min_y до max_y. Рассмотрим какую-то линию sy, A.y = 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);
}
// ...

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

1.

84K

23 июня 2012 года

ezfalc0n

0 / / 23.06.2012

+0 / -1

23 июня 2012, 13:05:02

Если отрисовывать ребра, то вызываем 3 раза функцию Брезенхема для прямого отрезка.


Если задача стоит закрасить треугольник,
то, используя алгоритм Брезенхема, получаем координаты (адреса) начал и концов горизонтальных отрезков, далее чертим отрезки. Если это приемлемо, то просто заполняем память значением, для отрисовки отрезков. Такой метод можно оптимизировать 64бит, увеличив производительность.

Нахождение координат отрезков производится инкрементацией и декрементацией аргументов в цикле по алгоритму Брезенхема. Отрисовку каждого отрезка можно вынести в отдельный цикл, либо совместить с поиском.
В первом случае необходимо выделение памяти для хранения структуры X, Y, Length размером равным "высоте" треугольника на экране

2.

Аноним

10 августа 2005, 22:30:11

точно! Я реализовал брезенхемовский... однако, надеюсь, может есть какая хитрая хитрость? Неужто видеокарты так муторно рисуют???

3.

Аноним

+1 / -0

20 марта 2005, 21:11:04

Использование деления - это не "быстрый метод".
Быстрый метод - это расчет ограничивающих линий по методу Брезенхема.