Перенос баз данных с одного SQL Server на другой Изменения в системе защиты SQL Server Новые средства разработки Новые элементы программирования на языке Visual Basic Редактирование и анализ данных с помощью запросов

Лекции по компьютерной графике начало

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

Брезенхем разработал алгоритм более эффективный, чем каждый рассмотренный выше. Здесь используется тот же принцип, что и для рисования линии.


рис. 2.6.1

Будем рассматривать сегмент окружности, соответствующий x=x0.. x0+R/sqrt(2). На каждом шаге выбираем точку, ближайшую к реальной окружности. В качестве ошибки возьмем величину D(Pi)=(x2i+ y2i) – R2.

Рассмотрим рис. 2.6.1 , на котором показаны различные возможные способы прохождения истинной окружности через сетку пискселов. Пусть пиксел Pi-1 уже найден как ближайший к реальной изображенной окружности, и теперь требуется определить, какой из пикселов должен быть установлен следующим: Ti или Si. Для этого определим точку, которой соответствует минимальная ошибка:


D(Si)=((q+1)2+ p2 ) – R2, D(Ti)=((q+1)2+ (p+1)2 ) – R2.

Если |D(Si)| < |D(Ti)|, то выбираем Si, иначе - Ti. Введем величину di = |D(Si)| - |D(Ti)|, тогда Si выбирается при di < 0, иначе выбирается Ti. Если рассматривать только часть окружности, дугу от 00 до 450, то D(Si) > 0 так как точкаSi лежит за пределами окружности, а D(Ti) < 0, так как Ti находится внутри окружности, поэтому
di = D(Si) + D(Ti).

Алгебраические вычисления, аналогичные тем, которые проводились для линии, приводят к результату:

d1=3-2R.

Если выбираем Si (когда di < 0 ),

Di=4xi-1+6;

если выбираем Ti (когда di >=0 ),

D i=4(xi-1 * yi-1) +10.

Блок-схема этого алгоритма (рис. 2.6.2).


рис. 2.6.2

Алгоритм хорош тем что отсутствуют операции с плавающей точкой, а также операции деления и извлечения корня.

Дизайн, инженерная и Web графика