Основы компьютерной графики для программистов. Казанцев А.В. - 37 стр.

Основы компьютерной графики для программистов                                                                  37
____________________________________________________________________________________________________________________



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




                                  Рис. 30. Рисование отрезков прямых по методу Брезенхема.

Пусть начало отрезка имеет координаты                           (x1, y1) ,   а конец   (x2, y 2 ) .   Обозначим
dx = ( x 2 − x1) , dy = ( y 2 − y1) . Не нарушая общности, будем считать, что начало
                                                                      dx         dx
отрезка совпадает с началом координат, и прямая имеет вид y =            x , где    ∈ [0,1].
                                                                      dy         dy
Считаем что начальная точка находится слева. Пусть на (i − 1) -м шаге текущей точкой
отрезка является Pi −1 = (r , q ) . Выбор следующей точки S i или Ti зависит от знака
разности (s − t ) . Если (s − t ) < 0 , то Pi = Ti = (r + 1, q ) и тогда x i +1 = x i + 1,
 y i +1 = y i , если же (s − t ) ≥ 0 , то Pi = S i = (r + 1, q + 1) и тогда xi +1 = xi + 1 ,
 y i +1 = y i + 1 .
                                                dy
                                         s=        (r + 1) − q , t = q + 1 − dy (r + 1) , ⇒
                                                dx                           dx
                                                            dy
                                                  s−t =2       (r + 1) − 2q − 1 ⇒
                                                            dx
                                           dx(s − t ) = 2(r ⋅ dy − q ⋅ dx ) + 2dy − dx .
Поскольку знак dx(s − t ) совпадает со знаком разности (s − t ) , то будем проверять
знак     выражения     d i = dx(s − t ) . Так как r = x i −1 и q = y i −1 , то
d i +1 = d i + 2dy − 2dx( y i − y i −1 ) .
Пусть на предыдущем шаге d i < 0 , тогда ( y i − y i −1 ) = 0 и d i +1 = d i + 2dy . Если же
на предыдущем шаге d i ≥ 0 , то ( y i − y i −1 ) = 1 и d i +1 = d i + 2(dy − dx ) .

Осталось узнать, как вычислить d1 . Так как при i = 1 :

                                         (x0 , y 0 ) = (0,0 ), ⇒ d1 = 2dy − dx .
http://www.ksu.ru/persons/9134.ru.html