Во многих областях приложений, таких как, например, системы автоматизированного проектирования машиностроительного направления, естественными графическими примитивами, кроме отрезков прямых и строк текстов, являются и конические сечения, т.е. окружности, эллипсы, параболы и гиперболы. Наиболее употребительным примитивом, естественно, является окружность. Один из наиболее простых и эффективных алгоритмов генерации окружности разработан Брезенхемом []. В переводной литературе он изложен, в частности, в [,].
Для простоты и без ограничения общности рассмотрим генерацию 1/8 окружности, центр которой лежит в начале координат. Остальные части окружности могут быть получены последовательными отражениями (использованием симметрии точек на окружности относительно центра и осей координат).
Окружность с центром в начале координат описывается уравнением:
|
Алгоритм Брезенхема пошагово генерирует очередные точки окружности, выбирая на каждом шаге для занесения пиксела точку растра Pi(Xi, Yi), ближайшую к истинной окружности, так чтобы ошибка:
|
была минимальной. Причем, как и в алгоритме Брезенхема для генерации отрезков, выбор ближайшей точки выполняется с помощью анализа значений управляющих переменных, для вычисления которых не требуется вещественной арифметики. Для выбора очередной точки достаточно проанализировать знаки.
Рассмотрим генерацию 1/8 окружности по часовой стрелке, начиная от точки X=0, Y=R.
Проанализируем возможные варианты занесения i+1-й точки, после занесения i-й.
При генерации окружности по часовой стрелке после занесения точки (Xi, Yi) следующая точка может быть (см. рис. 0.1а) либо Pg = (Xi+1, Yi) - перемещение по горизонтали, либо Pd = (Xi+1, Yi-1) - перемещение по диагонали, либо Pv = (Xi, Yi-1) - перемещение по вертикали.
Для этих возможных точек вычислим и сравним абсолютные значения разностей квадратов расстояний от центра окружности до точки и окружности:
| ||||||||||||||||||||||||||||||||||||||||||
Выбирается и заносится та точка, для которой это значение минимально.
Выбор способа расчета определяется по значению Dd. Если Dd < 0, то диагональная точка внутри окружности. Это варианты 1-3 (см. рис. 0.1б). Если Dd > 0, то диагональная точка вне окружности. Это варианты 5-7. И, наконец, если Dd = 0, то диагональная точка лежит точно на окружности. Это вариант 4. Рассмотрим случаи различных значений Dd в только что приведенной последовательности.
Здесь в качестве следующего пиксела могут быть выбраны или горизонтальный - Pg или диагональный - Pd.
Для определения того, какой пиксел выбрать Pg или Pd составим разность:
| |||||||||||||
И будем выбирать точку Pg при di Ј 0, в противном случае выберем Pd.
Рассмотрим вычисление di для разных вариантов.
Dg і 0 и Dd < 0, так как горизонтальный пиксел либо вне, либо на окружности, а диагональный внутри.
|
Добавив и вычтя (Y-1)2 получим:
|
В квадратных скобках стоит Dd, так что
|
Ясно, что должен быть выбран горизонтальный пиксел Pg. Проверка компонент di показывает, что Dg < 0 и Dd < 0, причем di < 0, так как диагональная точка больше удалена от окружности, т.е. по критерию di < 0 как и в предыдущих случаях следует выбрать горизонтальный пиксел Pg, что верно.
Здесь в качестве следующего пиксела могут быть выбраны или диагональный - Pd или вертикальный Pv.
Для определения того, какую пиксел выбрать Pd или Pv составим разность:
| |||||||||||||
Если si Ј 0, то расстояние до вертикальной точки больше и надо выбирать диагональный пиксел Pd, если же si > 0, то выбираем вертикальный пиксел Pv.
Рассмотрим вычисление si для разных вариантов.
Dd > 0 и Dv Ј 0, так как диагональный пиксел вне, а вертикальный либо вне либо на окружности.
|
Добавив и вычтя (X+1)2 получим:
|
В квадратных скобках стоит Dd, так что
|
Ясно, что должен быть выбран вертикальный пиксел Pv. Проверка компонент si показывает, что Dd > 0 и Dv > 0, причем si > 0, так как диагональная точка больше удалена от окружности, т.е. по критерию si > 0 как и в предыдущих случаях следует выбрать вертикальный пиксел Pv, что соответствует выбору для вариантов 5 и 6.
Для компонент di имеем: Dg > 0 и Dd = 0, следовательно по критерию di > 0 выбираем диагональный пиксел.
С другой стороны, для компонент si имеем: Dd = 0 и Dv < 0, так что по критерию si Ј 0 также выбираем диагональный пиксел.
Итак:
Dd < 0
di Ј 0 - выбор горизонтального пиксела Pg
di > 0 - выбор диагонального пиксела Pd
Dd > 0
si Ј 0 - выбор диагонального пиксела Pd
si > 0 - выбор вертикального пиксела Pv
Dd = 0
выбор диагонального пиксела Pd.
Выведем рекуррентные соотношения для вычисления Dd для (i+1)-го шага,
после выполнения i-го.
1. Для горизонтального шага к Xi+1, Yi
Xi+1 = Xi + 1
Yi+1 = Yi
Ddi+1 = (Xi+1+1)2 + (Yi+1-1)2 - R2 =
Xi+12 + 2·Xi+1 + 1 + (Yi+1-1)2 - R2 =
(Xi+1)2 + (Yi-1)2 - R2 + 2·Xi+1 + 1 =
Ddi + 2·Xi+1 + 1
2. Для диагонального шага к Xi+1, Yi-1
Xi+1 = Xi + 1
Yi+1 = Yi - 1
Ddi+1 = Ddi + 2 ·Xi+1 - 2 ·Yi+1 + 2
3. Для вертикального шага к Xi, Yi-1
Xi+1 = Xi
Yi+1 = Yi - 1
Ddi+1 = Ddi - 2 ·Yi+1 + 1
В Приложении 5 приведена подпрограмма V_circle, реализующая описанный выше алгоритм и строящая дугу окружности в первой четверти. Начальная инициализация должна быть:
X= 0
Y= R
Dd = (X+1)2 + (Y-1)2 - R2 = 1 + (R-1)2 - R2 = 2*(1 - R)
Пикселы в остальных четвертях можно получить отражением. Кроме того достаточно сформировать дугу только во втором октанте, а остальные пикселы сформировать из соображений симметрии, например, с помощью подпрограммы Pixel_circle, приведенной в Приложении 5 и заносящей симметричные пикселы по часовой стрелке от исходного.
В Приложении 6 приведены подпрограмма V_BRcirc, реализующая описанный выше алгоритм и строящая дугу окружности во втором октанте с последующим симметричным занесением пикселов. Эта процедура может строить и 1/4 окружности. Подробнее см. текст Приложения 6. Там же приведена более короткая подпрограмма, строящая 1/8 окружности методом Мичнера [], (том 1, стр. 152). Остальная часть окружности строится симметрично.
|
|
 |
