» » »

16. Алгоритм Брезенхема для генерации окружности

АЛГОРИТМ БРЕЗЕНХЕМА ДЛЯ ГЕНЕРАЦИИ ОКРУЖНОСТИ

В растр разлагаются не только линейные, но и другие, более сложные функции. Разложению конических сечений, т.е. окружностей, эллипсов, парабол, гипербол посвящено значительное число работ. Наибольшее внимание, разумеется, уделено окружности. Один из наиболее эффективных и простых для понимания алгоритмов генерации окружности принадлежит Брезенхему. Для начала заметим, что необходимо сгенерировать только одну восьмую часть окружности. Остальные ее части могут быть получены последовательными отражениями. Если сгенерировать первый октант (от 0 до 45º против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у=х, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой х=0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у=0 для завершения построения. Приведем матрицы соответствующих преобразований.

Для отражения первого октанта относительно оси 

src=16.1.JPG

Для отражения первого квадранта относительно оси 

src=16.2.JPG

Для отражения верхней полуокружности относительно оси 

src=16.3.JPG

Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат. Заметим. Что если работа алгоритма начинается в точке х=0 у= R, то при генерации окружности по часовой стрелке в первом квадранте у является  0, х= R, то при генерации окружности против часовой стрелки х будет монотонно убывающей функцией аргумента у. В нашем случае выбирается генерация по чаовой стрелке с началом в точке х=0, у=R. Предполагается, что центр окружности и начальная точка находятся точно в точках растра.

 Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. На следуем рисунке эти направления обозначены соответственно mH, mD,mv. Алгоритм

 src=16.4.JPG

Выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т.е.: минимум из

src=16.5.JPG

Вычисление можно упростить, если заметить, что в окрестности точки (хi,yi) возможны только пять типов пересечения окружности и сетки растра приведенных на следующем рисунке

src=16.6.JPG


Разность между квадратами расстояний от центра окружности до диагонального пиксела (xi-1,yi-1) и от центра до точки окружности R2 равна

src=16.7.JPG

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

При дельта < 0 диагональная точка (xi-1,yi-1) находится внутри реальной окружности, т.е это случаи 1 или 2 на нашем рисунке. Ясно, что в этой ситуации следует выбрать либо пиксел (xi+1, yi), т.е. mH, либо пиксел (xi+1,yi-1), т.е. mD. Для этого сначала рассмотрим случай 1 и проверим разность квадратов расстояний от окружности до пиксела в горизонтальном и диагональном направлениях:

src=16.8.JPG

При   б < 0 рассотяние от окружности до диагонального пиксела (mD) больше, чем до горизонтального (mH). Напротив, если б>0, расстояние до горизонтального пиксела (mH) больше. Таким образом,

    при б <= 0выбираем mH в (xi+1, yi)

    при  б>0 выбираем mD в (xi+1, yi-1)

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

Количество вычислений, необходимых для оценки величины б можно сократить, если заметить, что в случае 1

  (xi + 1) 2 + (yi)2 – R2 ≥ 0

   (xi + 1) 2 + (yi - 1)2 – R2 < 0

Так как диагональный пиксел (xi+1, yi-1) всегда лежит внутри окружности, а горизонтальный (xi+1, yi) вне ее. Таким образом, б можно вычислить по формуле

  (xi + 1) 2 + (yi)2 R2 +   (xi + 1) 2 + (yi - 1)2 R2

Дополнение до полного квадрата члена (yi)2 c помощью добавления и вычитания -2yi + 1  дает

src=16.9.JPG

В квадратных скобках стоит по определению дельта и его подстановка

         src=16.10.JPG

существенно упрощает выражение.

Рассмотрим случай 2 на нашем рисунке и заметим, что здесь должен быть выбран горизонтальный  пиксел (xi + 1, yi) так как у является монотонно убывающей функцией. Поверка компонент б показывает что,

(xi +1)2 + (yi)2R2 < 0

(xi +1)2+ (yi -1)2R2 < 0

Поскольку в случае 2 горизонтальный (xi + 1, yi)  и диагональный   (xi + 1, yi - 1) пикселы лежат внутри окружности. Следовательно, б < 0, и при использовании того же самого критерия, что и в случае 1, выбирается пиксел  (xi + 1, yi).

Если дельта >0 , то диагональная точка  (xi + 1, yi - 1) находится вне окружности, т. Е. это случаи 3 и 4 на нашем рисунке. В данной ситуации ясно, что должен быть выбран либо пиксел  (xi + 1, yi - 1), т.е. mD, либо  (xi, yi - 1), т.е. mV. Аналогично разбору предыдущего случая критерий выбора можно получить, рассматривая сначала случай 3 и проверяя разность между квадратами расстояний от окружности до диагонального mD и вертикального mV пикселов, т.е.

src=16.11.JPG

При б' < 0 расстояние от окружности до вертикального пиксела (xi, yi - 1) больше и следует выбрать диагональный шаг mD, к пикселу (xi + 1, yi - 1). Напротив, в случае б' >0 расстояние от окружности до диагонального пиксела больше и следует выбрать вертикальное движение к пикселу (xi, yi - 1),  

Здесь в случае  б '= 0, т.е когда расстояния равны выбран диагональный шаг.

Проверка компонент б' показывает что

(xi +1)2 + (yi - 1)2R2 >= 0

(xi )2 + (yi -1)2R2 < 0

Поскольку для случая 3 диагональный пиксел (xi + 1, yi - 1) находится вне окружности, тогда как вертикальный пиксел (xi, yi - 1) лежит внутри окружности. Это позволяет записать б' в виде

     б'= (xi +1)2 + (yi - 1)2R2 + (xi )2 + (yi -1)2R2

Дополнение до полного квадрата члена (xi )2 с помощью добавления и вычитания 2 xi +1 дает

2[(xi +1)2 + (yi - 1)2R2] – 2xi – 1

Использование определения дельта приводит выражение к виду

б'=2 (дельта - xi) – 1.

Теперь рассматривая случай 4, снова заметим, что следует выбрать вертикальный пиксел (xi, yi - 1), так как у является монотонно убывающей функцией при возрастании х.

Проверка компонент б 'для случая 4 показывает что

(xi +1)2 + (yi - 1)2 – R2 > 0

(xi )2 + (yi -1)2 – R2 > 0

Поскольку оба пиксела находятся вне окружности. Следовательно, б' > 0 и при использовании критерия, разработанного для случая 3, происходит верный выбор mD.

Осталось проверить только случай 5 на нашем рисунке, который встречается, когда диагональный пиксел(xi + 1, yi - 1) лежит на окружности, т.е. дельта = 0. Проверка компонент показывает, что

(xi +1)2 + (yi)2R2 > 0

(xi +1)2 + (yi - 1)2R = 0

Следовательно, б' > 0 и выбираем диагональный пиксел (xi + 1, yi - 1). Аналогичным образом оцениваем компоненты

(xi +1)2 + (yi - 1)2R2 = 0

(xi )2 + (yi -1)2R2 < 0

 И б'< 0, что является условием выбора правильного диагонального шага к (xi + 1, yi - 1). Таким образом, случай  дельта = 0 подчиняется тому же критерию, что и дельта < 0 или дельта > 0.

Подведем  итог полученных результатов

дельта< 0

src=16.12.JPG


Легко разработать простые рекуррентные соотношения для реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг mH к пикселу (xi+1,yi). Обозначим новое положение пиксела как (i+1). Тогда координаты нового пиксела и значение дельта  равны

     xi+1= xi +1

      yi+1 = yi

       дельта+1 = (xi+1 +1)2 +(yi+1 -1)2 –R2 =

        = (xi+1 +1)2 +2xi+1+1+(yi+1 -1)2 –R2 =

        = (xi+1 +1)2 +(yi+1 -1)2R2+2xi+1+1 =

       =дельта+2xi+1+1

Аналогично координаты нового пиксела и значение дельта для шага mD к пикселу (xi + 1, yi - 1) таковы

     xi+1= xi +1

      yi+1 = yi -1

       дельта+1 =дельта+2xi+1 - 2 yi+1 +2

То же самое для шага mv к  (xi, yi - 1)

  xi+1= xi +1

      yi+1 = yi -1

       дельта+1 =дельта - 2 yi+1 +1

Приведем реализацию алгоритма Брезенхема для окружности на псевдокоде.

Пошаговый алгоритм Брезенхема для генерации окружности в первом квадранте

все переменные целые

    инициализация переменных

   xi = 0

   yi = 0

   дельта = 2(1-R)

    Предел = 0

1 Plot (xi, yi)

   If y <= предел then 4

Выделение случая 1 или 2, 4 или 5, или 3

if дельта< 0 then 2

if дельта> 0 then 3

if дельта= 0 then 20

определение случая 1 или 2

2 б=2дельта+ 2yi -1

If  б <=0 Then 10

If б > 0 then 20

определение случая 4 или5

3 б'=2дельта+ 2xi – 1

If б' <=0 then 20

If  б'> 0 then 30

выполнение шагов

шаг mH

10  xi = xi +1

      дельта = дельта+2xi+1+1

       go to 1

шаг md

20 xi = xi +1

     yi = yi -1

     дельта = дельта+2xi+1 - 2 yi+1 +2

    go to 1

шаг mv

30     yi = yi -1

     дельта = дельта - 2 yi+1 +1

    go to 1

finish


Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.

Поделиться

Оплаченная реклама

Дисциплины