£ Dy/Dx < ½ (ошибка <0)
Окружность в первом квадранте. 2.5 Выбор пикселов в первом квадранте
Системы координаты строк сканирования
Необходимость удаления невидимых линий
Обработка нижней стороны поверхности
Эффект зазубренного ребра
Xребра = x
Не лицевые плоскости
Схема решения относительно a и t
Простая трассировка лучей
Пересечение прямоугольной области в преобразованной системе координат
Навигация
£ Dy/Dx < ½ (ошибка <0)
Трёхмерная компьютерная графика
103587
знаков
0
таблиц
24
изображения
0 £ Dy/Dx < ½ (ошибка <0)
Инициировать ошибку в – ½
ошибка = ошибка + Dy/Dx
2.1 Основная идея алгоритма Брезенхема
октанте, т. е. для отрезка с угловым коэффициентом, лежащим в диапазоне от нуля до единицы. Из рисунка можно заметить, что если угловой коэффициент отрезка из точки (0,0) больше чем 1/2, то его пересечение с прямой x = 1 будет расположено ближе к прямой у = 1, чем к прямой у = 0. Следовательно, точка растра (1,1) лучше аппроксимирует ход отрезка, чем точка (1,0). Если угловой коэффициент меньше 1/2, то верно обратное. Для углового коэффициента равного 1/2 нет какого-либо предпочтительного выбора. В данном случае алгоритм выбирает точку (1,1).
Быстродействие алгоритма можно существенно увеличить, если использовать только целочисленную арифметику и исключить деление. Т.к. важен лишь знак ошибки, то приняв
можно добиться хорошей скорости выполнения алгоритма.
2.2 Разбор случаев для обобщённого алгоритма Брезенхема.
Чтобы реализация алгоритма была полной необходимо обрабатывать отрезки во всех октантах. Когда абсолютная величина углового коэффициента больше 1, y постоянно изменяется на единицу, а критерий ошибки Брезенхема используется для принятия решения об изменении величены x. Выбор постоянно изменяющейся (на +1 или –1) координаты зависит от квадранта (рис. 2.2).
Алгоритм Брезенхема может быть оформлен в следующем виде.
Обобщённый целочисленный алгоритм Брезенхема квадрантов
предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают и все переменные - целые.
Функция Sign возвращает - 1, 0, 1 для отрицательного нулевого и положительного аргумента соответственно.
инициализация переменных
x = x1
y = y1
Dx = abs ( x2 - x1 )
Dy = abs ( y2 - y1 )
s1 = Sign ( x2 - x1 )
s2 = Sign ( y2 - y1 )
обмен значение Dx и Dy в зависимости от углового коэффициента наклона отрезка
if Dy > Dx then
Врем = Dx
Dx = Dy
Dy = Врем
Обмен = 1
else
Обмен = 0
end if
инициализация 
с поправкой на половину пиксела
= 2 * Dy - Dx
основной цикл
for i = 1 to Dx
Plot ( x ,y )
While ( ³ 0 )
If Обмен = 1 then
x = x + s1
else
y = y + s2
end if
= - 2 * Dx
end while
if Обмен = 1 then
y = y + s2
else
x = x + s1
end if
= + 2 * Dy
next i
finish
Этот алгоритм удовлетворяет самым строгим требованиям. Он имеет приемлемую скорость и может быть легко реализован на аппаратном или микропрограммном уровне.
Алгоритм Брезенхема для генерации окружностей
В растр нужно разлагать не только линейные, но и другие, более сложные функции. Разложению конических сечений, т. е. окружностей, эллипсов, парабол, гипербол посвящено значительное число работ. Наибольшее внимание, разумеется, уделено окружности. Один из наиболее эффективных и простых для понимания алгоритмов генерации окружности принадлежит
2.3 Генерация полной окружности из дуги в первом октанте
Брезенхему. Для начала заметим, что необходимо сгенерировать только одну восьмую часть окружности. Остальные её части могут быть получены последовательными отражениями, как это показано на рис. 2.3. Если сгенерирован первый октант (от 0° до 45° против часовой стрелки), то второй октант можно получить зеркальным отражением относительно прямой у = x, что дает в совокупности первый квадрант. Первый квадрант отражается относительно прямой x = 0 для получения соответствующей части окружности во втором квадранте. Верхняя полуокружность отражается относительно прямой у = 0 для завершения построения. На рис.2.3. приведены двумерные матрицы соответствующих преобразований.
Для вывода алгоритма рассмотрим первую четверть окружности с центром в начале координат. Заметим, что если работа алгоритма начинается в точке x = 0, у = R, то при генерации окружности по часовой стрелке в первом квадранте у является монотонно убывающей функцией аргумента x (рис. 2.4). Аналогично, если исходной точкой является y = 0, x = R, то при генерации окружности против часовой стрелки x будет монотонно убывающей функцией аргумента у. В нашем случае выбирается генерация по часовой стрелке с началом в точке x = 0, у = R. Предполагается, что центр окружности и начальная точка находятся точно в точках растра.
Для любой заданной точки на окружности при генерации по часовой стрелке существует только три возможности выбрать следующий пиксел, наилучшим образом приближающий окружность: горизонтально вправо, по диагонали вниз и вправо, вертикально вниз. На рис.2.5 эти направления обозначены соответственно mH, mD, mV.
Похожие работы
... Разновидности компьютерной графики Двумерная графика Двумерная компьютерная графика классифицируется по типу представления графической информации, и следующими из него алгоритмами обработки изображений. Обычно, компьютерную графику разделяют на: · векторную · растровую, · фрактальную Они отличаются принципами формирования изображения при отображении на экране монитора или при печати на ...
... в качестве реальной альтернативы системе Unix. _ 23.Платформа Intel ПК с процессором Intel продолжает оставаться наиболее распространённой платформой в сфере компьютерной графики и анимации. Главным событием, имеющим к ней непосредственное отноше- ние, стала демонстрация компанией Autodesk четвёртой версии программы 3D Studio - ...
... простыми. Большинство цветовых оттенков образуется смешением основных цветов. Способ разделения цветового оттенка на составляющие компоненты называется цветовой моделью. Существует много различных типов цветовых моделей, но в компьютерной графике, как правило, применяется не более трех. Эти модели известны под названиями: RGB, CMYK, НSB. Цветовая модель RGB Наиболее проста для понимания и ...
... прочие). В соответствии с принципами формирования изображения аддитивным или субтрактивным методами разработаны способы разделения цветового оттенка на составляющие компоненты, называемые цветовыми моделями. В компьютерной графике в основном применяют модели RGB и HSB (для создания и обработки аддитивных изображений) и CMYK (для печати копии изображения на полиграфическом оборудовании). Цветовые ...
0 комментариев