Алгоритмы вывода прямой линии

 

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

Алгоритм ЦДА. Простейший алгоритм растрового преобразования линейного отрезка известен как алгоритм ЦДА [24]. Этот алгоритм "позаимствован" у специализированных вычислителей - цифровых дифференциальных анализаторов, которые использовались для численного решения систем дифференциальных уравнений. Поскольку прямая описывается дифференциальным уравнением вида dy/dx = m, где m — коэффициент наклона, формирование прямолинейного отрезка есть не что иное, как решение этого простейшего уравнения численным методом.

Пусть отрезок задан крайними точками (х1,у1) и (х2,у2) (рис. 9.1).

 

Рис. 9.1. Прямолинейный отрезок в системе координат

 

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

.

Будем считать, что 0 < т <; 1. При других вариантах значения т можно использовать симметричную модификацию алгоритма.

В основе алгоритма лежит запись кода цвета в ячейку буфера, представляющую определенный пиксел, по мере того как х изменяется от х1 до х2. Между элементарными приращениями δx и δy координат точки, которая перемещается от начала отрезка к его концу, существует связь: δy = m * δx.

Если на каждом шаге увеличивать значение х на 1, т.е. принять δx =1, то координату у отображающей точки нужно увеличить на величину δy=т. Хотя каждое очередное значение х представляет целое число, очередное значение у таковым не является, поскольку m в общем случае — дробь. Поэтому значение у нужно округлить и найти подходящий пиксел, представляющий текущее положение отображающей точки (рис. 9.2).

Рис.9.2. Формирование пикселей при использовании алгоритма ЦДА

 

Алгоритм Брезенхема рисования линии. Описанный алгоритм ЦЦА при всей его простоте и наглядности обладает одним недостатком – при формировании координат каждой отображающей точки необходимо выполнять сложение действительных чисел. Более простой целочисленный алгоритм предложил Брезенхэм в 1965 году [21, 24]. Как и в алгоритме ЦДА, будем считать, что конечные точки отрезка представлены целочисленными координатами (x1, y1) и (х2, у2), а коэффициент наклона удовлетворяет условию 0 < m < 1.

Это условие достаточно критично для работоспособности алгоритма. Суть алгоритма в том, что при построении растрового образа отрезка выбирается пиксел, ближайший по вертикали к соответствующей прямой. Рассмотрим промежуточный шаг растрового преобразования отрезка после того, как будет сформирован пиксел (i + 1/2, j + 1/2) (рис.9.3).

Рис.9.3. Алгоритм Брезенхема

 

Известно, что прямая описывается уравнением: y=тх + h.

При х = i + 1/2 прямая проходит от центра пиксела, точки с координатами (i, j+ 1/2), не далее, чем на 1/2 шага между пикселами. В противном случае образ прямой вследствие округления не прошел бы через этот пиксел. При переходе к следующей точке, для которой х = i + 3/2, учитывая ограничения, наложенные на значение коэффициента наклонa, образ отрезка должен пройти либо через пиксел с центром в (i+ 3/2, j+ 1/2), либо через пиксел с центром в (i +3/2, j+ 3/2).

Проблема выбора решается с помощью характеристической переменной d = b - a, где а и b расстояния между прямой в точке х=i +3/2 и верхним и нижним пикселами кандидатами (рис. 9.4).

Рис. 9.4. Характеристическая переменная алгоритма Брезенхема

 

Если d отрицательно, прямая проходит ближе к центру нижнего пиксела в качестве следующего пиксела образа отрезка выбирается (i+ 3/2, j+ 1/2).

В противном случае выбирается пиксел с центром в (i + 3/2, j + 3/2 ).

Можно было бы определить значение d, вычислив у = тх + b, но тогда теряется одно из заявленных достоинств алгоритма – использование только целочисленных операций, поскольку т является действительной дробью.

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

Изменим определение характеристической переменной. Будем использовать . Это изменение не влияет на выбор пикселов-кандидатов, поскольку для принятия решений используется только знак характеристической переменной, а он в новой формулировке будет таким же, как и в прежней.

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

Поэтому несколько изменим подход. Пусть d_k — значение d при х = k+ 1/2. Попробуем вычислить d_k+i в приращениях относительно d_k. Значение приращения будет зависеть от того, выполнялось ли на предыдущем шаге приращение координаты у пиксела. Возможные варианты представлены на рис 9.5.

 

 

Рис.9.5. Приращение значений параметров a и b

 

Для параметров а и b — расстояний между прямой и пиксе­лами-кандидатами — справедливы следующие соотношения: если на предыдущем шаге произошло приращение у, то . В противном случае .

Умножив полученные выражения на Δ х, получим, что при переходе к следующему значению х значение d изменяется либо на 2Δ у, либо на 2( Δ у- Δ х).

Этот результат можно записать в таком виде:

 

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