Модифицированный алгоритм Брезенхема

Основная идея алгоритма состоит в том, чтобы для ребер многоугольника устанавливать яркость пиксела пропорционально площади пиксела, попавшей внутрь многоугольника.

При построении ребра многоугольника с тангенсом угла наклона t (0 £ t £ 1) могут захватываться либо один пиксел (пикселы (0,0), (2,1), (4,2), (6,8)) либо два пиксела (пикселы (1,0) и (1,1), (3,1) и (3,2), (5,2) и (5,3)). Если захватывается один пиксел, то часть его площади, попавшая внутрь многоугольника, равна dy + t/2 (рис. a).

Если же захватывается два пиксела, то часть площади нижнего пиксела, попавшая внутрь многоугольника равна 1 - [((1 - dy)²)/ 2t], а верхнего - [((dy - 1 + 2)²)/ 2t]. Суммарная площадь частей для двух пикселов, попавшая внутрь многоугольника, равна dy + t/2.

Если теперь в исходном алгоритме Брезенхема заменить отклонение E на E' = E + (1-t), то 0 £ E' £ 1) и значение E' будет давать значение той части площади пиксела, которая находится внутри многоугольника.

Выполняя преобразование над значением отклонения для первого шага получим, что начальное значение станет равным 1/2. Максимальное значение отклонения E'_max, при превышении которого производится увеличение Y-координаты занесения пикселов, станет равным (1 - t).

Для того, чтобы оперировать не дробной частью максимальной интенсивности, а непосредственно ее значениями достаточно домножить на полное число уровней интенсивности I тангенс угла наклона (t), начальное (E') и максимальное (E'_max) значения отклонения.

В результате получается следующий алгоритм, пригодный для случая 0 £ dY £ dX:

X= x1;

Y= y1;

Px= x2 - x1;

Py= y2 - y1;

t= I*Py / Px;

E'= I/2;

E'_max= I - I*Py / Px;

i= Px;

PutPixel(X, Y, t/2); /* Первая точка вектора */

while (i = i - 1 ³ 0) {

if (E' ³ E'_max) {

X= X + 1;

Y= Y + 1;

E' = E'- E'_max;

} else

X= X + 1;

E' = E'+ t;

PutPixel(X, Y, E'); /* Очередная точка вектора */}

Для избавления от вещественной арифметики при манипулировании с E' можно домножить уже упомянутые величины на 2*Px. Но в этом случае при занесении пикселов потребуется деление E' на 2*Px.

В Приложении 2 приведена процедура V_BreM, реализующая модифицированный алгоритм Брезенхема для генерации ребра заполненного многоугольника и пригодная для любого октанта.