Процедура рисования линии по алгоритму Брезенхэма

Процедура рисования линии по алгоритму Брезенхэма

Автор: Mikezt
Эта статья посвящается baze/3sc.

Одной из самых базовых графических процедур является рисование линии. Когда вы пробуете написать такую процедуру сами, задача может показаться довольно сложной. Не переживайте — вот один из способов её решения.

Алгоритмы Брезенхэма обладают преимуществом перед другими методами, так как работают исключительно с целыми числами. Благодаря этому их очень просто реализовать в машинном коде. Но прежде чем начать, приготовьтесь к математическим формулам. Нижние индексы я буду записывать в квадратных скобках [].

Отрезок задаётся двумя точками $(x_1, y_1)$ и $(x_2, y_2)$ и может быть описан уравнением:

$$y = k \cdot x + q$$

где $k$ — угловой коэффициент (направление), а $q$ — смещение по оси $Y$.

Коэффициент $k$ определяет наклон прямой и делит координатную сетку на восемь октантов (см. рис. 1). Рассмотрим случай, когда $k$ положителен и меньше 1 ($0 < k < 1$). Предположим, что точка $(x[i], y[i])$ уже нарисована. Для каждого следующего пикселя нам нужно вычислить отклонение от идеального хода отрезка (рис. 2).

Отклонения для двух возможных точек равны:

$$D_1 = y - y[i] = k \cdot (x[i] + 1) + q - y[i]$$
$$D_2 = y[i] + 1 - y = y[i] + 1 - k \cdot (x[i] + 1) - q$$

Разность этих двух величин равна:

$$D = D_1 - D_2 = 2 \cdot k \cdot (x[i] + 1) - 2 \cdot y[i] + 2 \cdot q - 1$$

По знаку этой разности мы и выбираем нужный пиксель. Очевидно, что решающим фактором является именно знак: отрицательное значение выберет точку $(x[i] + 1, y[i] + 1)$, а положительное — $(x[i] + 1, y[i])$. Недостаток заключается в том, что значения остаются вещественными. Мы можем избавиться от этого, умножив выражение разности на $(x_2 - x_1)$, получив так называемую решающую переменную (decision):

$$d[i] = D \cdot (x_2 - x_1) = 2 \cdot (y_2 - y_1) \cdot (x[i] + 1) - 2 \cdot y[i] \cdot (x_2 - x_1) + (2 \cdot q - 1) \cdot (x_2 - x_1)$$

и после небольшого преобразования:

$$d[i] = 2 \cdot (y_2 - y_1) \cdot x[i] - 2 \cdot y[i] \cdot (x_2 - x_1) + 2 \cdot (y_2 - y_1) + (2 \cdot q - 1) \cdot (x_2 - x_1)$$

Выражение $2 \cdot (y_2 - y_1) + (2 \cdot q - 1) \cdot (x_2 - x_1)$ является константой, обозначим её как $c$. Получаем:

$$d[i] = 2 \cdot (y_2 - y_1) \cdot x[i] - 2 \cdot y[i] \cdot (x_2 - x_1) + c$$

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

$$d[i+1] = 2 \cdot (y_2 - y_1) \cdot (x[i] + 1) - 2 \cdot y[i+1] \cdot (x_2 - x_1) + c$$

Вычтя одно из другого, мы выразим значение $d$ в рекурсивном виде:

$$d[i+1] = d[i] + 2 \cdot (y_2 - y_1) - 2 \cdot (x_2 - x_1) \cdot (y[i+1] - y[i])$$

Выражение $(y[i+1] - y[i])$ может принимать только значения 0 или 1, поэтому правила вычисления следующего значения упрощаются:

• если $d[i] < 0 \implies d[i+1] = d[i] + 2 \cdot (y_2 - y_1)$
• если $d[i] \ge 0 \implies d[i+1] = d[i] + 2 \cdot (y_2 - y_1) - 2 \cdot (x_2 - x_1)$

Последнее, что осталось узнать — начальное значение на первом шаге:

$$d[1] = 2 \cdot (y_2 - y_1) - (x_2 - x_1)$$

Таким образом, всё, что вам нужно делать в цикле: проверять знак решающей переменной; если он отрицательный — сдвигать координату $Y$, вычислять новое значение ошибки для следующего шага и проверять, не достигли ли вы конечной точки. Если нет — повторять цикл. Для направлений, отличных от $0 < k < 1$, формулы необходимо скорректировать путём аналогичного вывода, либо воспользовавшись иллюстрациями. Я использовал их для определения нужного направления в начальной точке своей процедуры.

Достаточно просто заменить выражение $(x_2 - x_1)$ на первое выражение из последнего сравнения, а $(y_2 - y_1)$ — на второе (думаю, идея понятна :-) ...

Несколько советов по оптимизации процедуры:

• Проверяйте условие $x_2 > x_1$ (или любое другое, выбирая соответствующую ветку алгоритма): если оно истинно, начальную и конечную точки не нужно менять местами.
• Уравнения решающей переменной можно разделить на 4 (два сдвига вправо) — тогда ошибку можно хранить в 8-битном регистре без потери точности!

Фух, на этом всё. Моя процедура доступна (надеюсь) на сайте проекта HighTech (http://hightech.da.ru). Надеюсь, суть написанного понятна. Если есть вопросы — пишите.

Пока!

mike/zt/ctl
jurica@sknet.sk