Основы компьютерной графики: Часть 1. Математический аппарат компьютерной графики. Казанцев А.В. - 40 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

ОСНОВЫ КОМПЬЮТЕРНОЙ ГРАФИКИ, часть 1 40
достаточно для всех целых
x
, принадлежащих отрезку, выводить на экран
точки с координатами
(
)()
yx Round,. Однако в этом методе присутствует
операция умножения kx . Хотелось бы иметь алгоритм без частого
использования операции умножения вещественных чисел. Избавиться от
операции умножения можно следующим образом. Поскольку
x
y
k
Δ
Δ
= , то
один шаг по целочисленной сетке на оси
x
будет соответствовать 1
=
Δ
x
.
Отсюда получаем, что y будет увеличиваться на величину
k
. Итерационная
последовательность выглядит следующим образом:
1
1
+
=
+ ii
xx , kyy
ii
+
=
+1
Когда 1>
k
, то шаг по
x
будет приводить к шагу по 1>y , поэтому
x
и
y следует поменять ролями, придавая y единичное приращение, а
x
будет
увеличиваться на
k
k
y
x
1
=
Δ
=Δ единиц. Этот алгоритм все же не свободен
от операций с вещественными числами. Наиболее изящное решение задачи
растровой развертки отрезков прямых было найдено Брезенхемом. В его
алгоритме вообще не используются операции с вещественными числами, в
том числе операции умножения и деления.
Для вывода формул алгоритма Брезенхема рассмотрим рис
. 29.
Рис. 29. Рисование отрезков прямых по методу Брезенхема.
Пусть начало отрезка имеет координаты
(
)
1,1 yx , а конец
(
)
2,2 yx .
Обозначим
()
12 xxdx −= ,
(
)
12 yydy
−
=
. Не нарушая общности, будем
считать, что начало отрезка совпадает с началом координат, и прямая имеет
вид
x
dy
dx
y = , где
[]
1,0∈
dy
dx
. Считаем что начальная точка находится слева. 
ОСНОВЫ КОМПЬЮТЕРНОЙ ГРАФИКИ, часть 1                                     40



достаточно для всех целых x , принадлежащих отрезку, выводить на экран
точки с координатами ( x, Round ( y )). Однако в этом методе присутствует
операция умножения kx . Хотелось бы иметь алгоритм без частого
использования операции умножения вещественных чисел. Избавиться от
операции умножения можно следующим образом. Поскольку k = Δy , то
                                                                   Δx
один шаг по целочисленной сетке на оси x будет соответствовать Δx = 1 .
Отсюда получаем, что y будет увеличиваться на величину k . Итерационная
последовательность выглядит следующим образом:
                            x i +1 = x i + 1, y i +1 = y i + k
      Когда k > 1 , то шаг по x будет приводить к шагу по y > 1 , поэтому x и
 y следует поменять ролями, придавая y единичное приращение, а x будет
увеличиваться на Δx = Δy = 1 единиц. Этот алгоритм все же не свободен
                           k    k
от операций с вещественными числами. Наиболее изящное решение задачи
растровой развертки отрезков прямых было найдено Брезенхемом. В его
алгоритме вообще не используются операции с вещественными числами, в
том числе операции умножения и деления.
      Для вывода формул алгоритма Брезенхема рассмотрим рис. 29.




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

     Пусть начало отрезка имеет координаты ( x1, y1) , а конец ( x 2, y 2 ) .
Обозначим dx = ( x 2 − x1) , dy = ( y 2 − y1) . Не нарушая общности, будем
считать, что начало отрезка совпадает с началом координат, и прямая имеет
         dx         dx
вид y =     x , где    ∈ [0,1]. Считаем что начальная точка находится слева.
         dy         dy

Страницы