Реферат: Трёхмерная компьютерная графика
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 .
2.4 Окружность в первом квадранте. 2.5 Выбор пикселов в первом квадранте
Алгоритм выбирает пиксел, для которого минимален квадрат расстояния между одним из этих пикселов и окружностью, т. е. минимум из
mH = | ( xi + 1 )2 + ( yi )2 – R2 |
mH = | ( xi + 1 )2 + ( yi - 1 )2 – R2 |
mH = | ( xi )2 + ( yi - 1 )2 – R2 |
Вычисления можно упростить, если заметить, что в окрестности точки ( xi , yi ) возможны только пять типов пересечений окружности и сетки растра, приведенных на рис.2.6.
Разность между квадратами расстояний от центра окружности до диагонального пиксела ( xi + 1, yi - 1) и от центра до точки на окружности R2 равна