ВУЗ:
Составители:
Рубрика:
Схема алгоритма Брезенхема рассматривается на случай обхода лишь дуги окружности в 45° от
x
= 0 до
2Rx =
. Для
построения полной окружности используется восьмисторонняя симметрия (рис. 2.2).
Рис. 2.2. Восьмисторонняя симметрия и область работы алгоритма
Рис. 2.3. Контрольные точки для окружности Брезенхема
Работа алгоритма аналогична построению отрезков прямых. Пиксели окружности (дуги) высвечиваются в зависимости
от знака управляющей переменной
d
i
, где
i
– шаг работы алгоритма.
На каждом шаге построения окружности алгоритм Брезенхема выбирает точку
P
i
(
x
i
,
y
i
), которая является наиболее бли-
жайшей к истинной окружности, и поэтому ошибка
222
)()( RyxPD
iii
−+=
будет близкой к нулю; т.е. значение
)(
i
PD
ми-
нимизируется на каждом шаге.
Пусть на
i
– 1-ом шаге работы алгоритма точка
P
i
– 1
была выбрана как ближайшая к окружности при параметрах (
x
i
– 1
,
y
i
– 1
). Далее, определяется какая из двух точек
T
i
или
S
i
расположена ближе к окружности
x
i
– 1
+ 1:
а) если
d
i
< 0, то выбирается пиксель
S
i
(
X
i
– 1
+ 1,
Y
i
– 1
) и для следующего шага
d
i
+ 1
=
d
i
+ 4
x
i
– 1
+ 6;
б) если
d
i
≥ 0, то выбирается пиксель
T
i
(
X
i
– 1
+ 1,
Y
i
– 1
– 1)
и для следующего шага
d
i
+ 1
=
d
i
+ 4(
x
i
– 1
–
y
i
– 1
) + 10.
На первом шаге работы алгоритма значение управляющей переменной
d
1
определяется как
d
1
= 3 – 2
R
.
Как и в алгоритме Брезенхема для построения отрезков прямы, в данном отсутствуют вещественные числа, операция
округления.
3. АФФИННЫЕ ПРЕОБРАЗОВАНИЯ НАД ДВУМЕРНЫМИ ОБЪЕКТАМИ
В компьютерной графике часто применяются различные геометрические преобразования: вращение, сжатие, парал-
лельный перенос и др. С помощью них, однократно описав топологию объекта, мы можем получить много различных его
экземпляров. На практике подобные геометрические изменения (2
D
) объектов на плоскости описываются аффинными пре-
образованиями, описывающиеся следующими соотношениями [23]:
,
;
FEyDxy
CByAxx
++=
′
+
+
=
′
где
A
,
B
, …,
F
– константы;
x
,
y
– координаты до преобразования;
yx
′
′
,
– новые коорди-
наты точек 2
D
объектов.
Рассмотрим основные
2D
преобразования:
Перемещение (сдвиг) 2
D
объекта на
D
x
единиц по оси
x
и на
D
y
единиц по оси
y
(рис.
3.1) описывается следующими уравнениями:
+=
+=
′
.Dyy'
Dxx
y
x
;
Используя однородные координаты, операция перемещения в векторной форме имеет
вид
Y
X
R
(
x
,
y
)
(–
x
,
y
)
(–
y
,
x
)
(–
y
, –
x
)
(–
x
, –
y
)
(
x
, –
y
)
(
y
, –
x
)
(
y
,
x
)
45°
2
R
S
i
(
X
i
– 1
+ 1,
Y
i
– 1
)
Реальная
окружность
P
i
–1
(
X
i
– 1
,
Y
i
– 1
)
T
i
(
X
i
– 1
+ 1,
Y
i
– 1
– 1)
Dx
Рис. 3.1. Перемещение (сдвиг)
сдвиг
y
D
y
x
x
′
y
′
P
P
′
X
Y
Страницы
- « первая
- ‹ предыдущая
- …
- 21
- 22
- 23
- 24
- 25
- …
- следующая ›
- последняя »
