Реферат: Трёхмерная компьютерная графика

Dx = ( x₂ -x₁ ) / Длина

Dy = ( y₂ -y₁ ) / Длина

округляем величины, а не отбрасываем дробную часть

использование знаковой функции делает алгоритм пригодным для всех квадрантов

x = x₁ + 0.5 * Sign ( Dx )

y = y₁ + 0.5 * Sign ( Dy )

начало основного цикла

i =1

while ( i £Длина)

Plot ( Integer ( x ), Integer ( y ) )

x = x + Dx

y = y + Dy

i = i + 1

end while

finish

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

Алгоритм Брезенхема

Алгоритм Брезенхема выбирает оптимальные растровые координаты для представления отрезка. В процессе работы одна из координат - либо x, либо у (в зависимости от углового коэффициента) - изменяется на единицу. Изменение другой координаты (либо на нуль, либо на единицу) зависит от расстояния между действительным положением отрезка и ближайшими координатами сетки. Такое расстояние называется ошибкой.

Алгоритм построен так, что требуется проверять лишь знак этой ошибки. На рис.2.1 это иллюстрируется для отрезка в первом

½ £Dy £ 1 (ошибка³ 0)

0 £Dy/Dx < ½ (ошибка <0)

Инициировать ошибку в – ½

ошибка = ошибка + Dy/Dx

2.1 Основная идея алгоритма Брезенхема

октанте, т. е. для отрезка с угловым коэффициентом, лежащим в диапазоне от нуля до единицы. Из рисунка можно заметить, что если угловой коэффициент отрезка из точки (0,0) больше чем 1/2, то его пересечение с прямой x = 1 будет расположено ближе к прямой у = 1 , чем к прямой у = 0 . Следовательно, точка растра (1,1) лучше аппроксимирует ход отрезка, чем точка (1,0). Если угловой коэффициент меньше 1/2, то верно обратное. Для углового коэффициента равного 1/2 нет какого-либо предпочтительного выбора. В данном случае алгоритм выбирает точку (1,1).

Быстродействие алгоритма можно существенно увеличить, если использовать только целочисленную арифметику и исключить деление. Т.к. важен лишь знак ошибки, то приняв

можно добиться хорошей скорости выполнения алгоритма.