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

Простой пошаговый алгоритм вычерчивания отрезков

Численная и компьютерная графика

Перспективные преобразования

Проецирование трехмерного пространства на плоскость

Аксонометрические проекции

Классификация общих аксонометрических проекций приведена в таблице:

Пример для изометрической проекции матрицы преобразований:

Проекция из трехмерного пространства XYZ может быть получена при помощи следующей операции:

Перспективная проекция получается путем преобразования и проецирования на некоторую двухмерную плоскость наблюдения.

Перспективная проекция на плоскость ось Z.

= * =

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

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

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

Приведем пример подобного алгоритма:

(начало)

шаг = приращение

1. if (позиция – конец) < точность then 4

if позиция > конец then 2

if позиция < конец then 3

2. позиция = позиция – шаг go to 1

3. позиция = позиция + шаг go to 1

4. (stop. END)

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

Алгоритм выбирает оптимальные растры из координат для построения отрезка. В процессе работы одна из координат либо X, либо Y, в зависимости от углового коэффициента изменяется на 1, изменение другой координаты равно нулю или единице. Это зависит от расстояния действий положения отрезков, ближайшим координатам сетки.

Алгоритм построен так, что требуется только проверить знак ошибки. Проиллюстрируем на рисунке для отрезка, лежащего в диапазоне от 0 до 1.

≤ ≤ 1

Ошибка = ошибка + .

На рисунке можно увидеть, что угловой коэффициент из точки (0.0) > 1/2.

Приведём алгоритм для первого октанта.

х, y, , Δу – целые

е – вещественное

1) инициализация переменных

х = х₁

у = у₁

Δх = х₂-х₁

Δу = у₂-у₁

е = Δу*Δх-1/2

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

for i:=1 to Δx

plot (x,y)

while (e>0)

y = y+1;

e = e-1;

and while

x = x+1

e = e+

end;

end;

Обобщённый целочисленный алгоритм

Предполагается, что концы отрезка не совпадают и все переменные считаются целыми. Функция sign возвращает -1, 0, 1 для отрицательного, нулевого и положительного аргумента соответственно.

Инициализация переменных:

х = х1

у = у1

Δх = abs (x₂-x₁)

Δy = abs (y₂-y₁)

S1 = sign (x₂-x₁)

S2 = sign (y₂-y₁)

Обмен значений Δх и Δу в зависимости от углового коэффициента наклона отрезка.

if Δy > Δx then

временная = Δx

Δх = Δу

Δу = временная

else

обмен = 0

end if

Инициализация с поправкой на половину пикселя

= 2* Δy – Δх

Основной цикл:

for i:= 1 to Δх

plot (x, y)

while () ≥ 0

if обмен = 1 then

x = x+S₁

else

y = y+S₂

end if

= - 2 * Δх

end while

if обмен = 1 then

y = y+S₂

else

x = x + S₁

else if

= + 2 * Δy

next i

finish