30697-1 (Трёхмерная компьютерная графика), страница 2

2.4 Окружность в первом квадранте. 2.5 Выбор пикселов в первом квадранте

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

m_H = | ( x_i + 1 )² + ( y_i )² – R² |

m_H = | ( x_i + 1 )² + ( y_i 1 )² – R² |

m_H = | ( x_i )² + ( y_i 1 )² – R² |

Вычисления можно упростить, если заметить, что в окрестности точки ( x_i, y_i ) возможны только пять типов пересечений окружности и сетки растра, приведенных на рис.2.6.

Разность между квадратами расстояний от центра окружности до диагонального пиксела ( x_i + 1, y_i 1 ) и от центра до точки на окружности R² равна

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

2.6 Пересечение окружности и сетки растра

При < 0 диагональная точка ( x_i + 1, y_i 1 ) находится внутри реальной окружности, т. е. это случаи 1 или 2 на рис.2.6. Ясно, что в этой ситуации следует выбрать либо пиксел ( x_i + 1, y_i ) т. е. m_H, либо пиксел ( x_i + 1, y_i 1 ), т. е. m_D. Для этого сначала рассмотрим случай 1 и проверим разность квадратов расстояний от окружности до пикселов в горизонтальном и диагональном направлениях:

При < 0 расстояние от окружности до диагонального пиксела

(m_D) больше, чем до горизонтального (m_H). Напротив, если > 0, расстояние до горизонтального пиксела (m_H) больше. Таким образом,

при < 0 выбираем m_H ( x_i + 1, у_i )

при > 0 выбираем m_D ( x_i + 1, у_i – 1 )

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

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

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

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

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

= 2(_i + y_i) – 1

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

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

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

Если _i > 0, то диагональная точка ( x_i + 1, у_i – 1 ) находится вне окружности, т. е. это случаи З и 4 на рис.2.6. В данной ситуации ясно, что должен быть выбран либо пиксел ( x_i + 1, у_i – 1 ), т. е. m_D, либо ( x_i, у_i – 1 ), т. е. m_V. Аналогично разбору предыдущего случая критерий выбора можно получить, рассматривая сначала случай З и проверяя разность между квадратами расстояний от окружности до диагонального m_D и вертикального m_V пикселов, т. е.

При ^\ < 0 расстояние от окружности до вертикального пиксела ( x_i, у_i – 1 ) больше и следует выбрать диагональный шаг m_D, к пикселу ( x_i + 1, у_i – 1 ). Напротив, в случае ^\ > 0 расстояние от окружности до диагонального пиксела больше и следует выбрать вертикальное движение к пикселу ( x_i, у_i – 1 ). Таким образом,

при 0 выбираем m_D в ( x_i + 1, у_i – 1 )

при < 0 выбираем m_V в ( x_i, у_i – 1 )

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

Проверка компонент ^\ показывает, что

поскольку для случая З диагональный пиксел ( x_i + 1, у_i – 1 ) находится вне окружности, тогда как вертикальный пиксел ( x_i, у_i – 1 ) лежит внутри ее. Это позволяет записать ^\ в виде

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

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

Теперь, рассматривая случай 4, снова заметим, что следует выбрать вертикальный пиксел ( x_i, у_i – 1 ), так как y является монотонно убывающей функцией при возрастании x. проверка компонент ^\ для случая 4 показывает, что

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

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

Следовательно, > 0 и выбирается диагональный пиксел ( x_i + 1, у_i – 1 ). Аналогичным образом оцениваем компоненты ^\:

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

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

_i < 0

0 выбираем пиксел ( х_i + 1, у_i ) m_H

> 0 выбираем пиксел ( х_i + 1, у_i – 1 ) m_D

_i > 0

^\ 0 выбираем пиксел ( х_i + 1, у_i – 1 ) m_D

^\ > 0 выбираем пиксел ( х_i , у_i – 1 ) m_V

_i = 0 выбираем пиксел ( х_i + 1, у_i – 1 ) m_D

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

Аналогично координаты нового пиксела и значения _i для шага m_D к пикселу ( х_i + 1, у_i – 1 ) таковы:

То же самое для шага m_V к ( х_i, у_i – 1 )

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

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

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

x_i = 0

y_i = R

_i = 2(1 – R)

Предел = 0

Plot ( x_i, y_i )

if y_i Предел then 4

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

if _i < 0 then 2

if _i > 0 then 3

if _i = 0 then 20

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

= 2_i + 2y_i – 1

if 0 then 10

if > 0 then 20

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

= 2_i + 2x_i – 1

if 0 then 20

if > 0 then 30

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

шаг m_H

x_i = x_i +1

_i = _i +2x_i + 1

goto 1

шаг m_D

x_i = x_i +1

y_i = y_i – 1

_i = _i +2x_i – 2y_i + 2

goto 1

шаг m_V

30y_i = y_i – 1

_i = _i – 2x_i + 1

goto 1

4finish

Растровая развёртка сплошных областей

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

В методах растровой развертки пытаются определить в порядке

сканирования строк, лежит ли точка внутри многоугольника или контура. Эти алгоритмы обычно иду от “верха” многоугольника или контура к “низу”.

В методах затравочного заполнения предполагается, что известна некоторая точка (затравка) внутри замкнутого контура. В алгоритмах ищут точки, соседние с затравочной и расположенные внутри контура. Если соседняя точка расположена не внутри, значит, обнаружена граница контура. Если же точка оказалась внутри контура, то она становится новой затравочной точкой и поиск продолжается рекурсивно.

Растровая развёртка многоугольников

Можно разработать эффективный метод растровой развёртки многоугольников, если воспользоваться тем фактом, что соседние пикселы, вероятно, имеют одинаковые характеристики (кроме пикселов граничных рёбер). Это свойство называется пространственной когерентностью.

2.7 Растровая развёртка сплошной области

Характеристики пикселов на данной строке изменяются только там, где ребро многоугольника пересекает строку. Эти пересечения делят сканирующую строку на области.

Для простого многоугольника на рис. 2.7 строка 2 пересекает многоугольник при x = 1 и x = 8.

Получаем три области:

x < 1вне многоугольника

1 x 8внутри многоугольника

x > 8вне многоугольника

Строка 4 делится на пять областей:

x < 1вне многоугольника

1 x 4внутри многоугольника

4 < x < бвне многоугольника

б x 8внутри многоугольника

x > 8вне многоугольника

Совсем необязательно, чтобы точки пересечения для строки 4 сразу определялись в фиксированном порядке (слева направо). Например, если многоугольник задаётся списком вершин P₁, P₂, P₃, P₄, а список рёбер последовательными парами вершин P₁P₂, P₂P₃, P₃P₄, P₄P₅, P₅P₁, то для строки 4 будут найдены следующие точки пересечения с рёбрами многоугольника: 8, 6, 4, 1. Эти точки надо отсортировать в возрастающем порядке по x, т. е. получить 1,4, 6, 8.

При определении интенсивности, цвета и оттенка пикселов на сканирующей строке рассматриваются пары отсортированных точек пересечений. Для каждого интервала, задаваемого парой пересечений, используется интенсивность или цвет заполняемого многоугольника. Для интервалов между парами пересечений и крайних (от начала строки до первой точки пересечения и от последней точки пересечения до конца строки) используется фоновая интенсивность или цвет.

2.8 Системы координаты строк сканирования.

Точное определение тех пикселов, которые должны активироваться, требует некоторой осторожности. Рассмотрим простой прямоугольник, изображенный на рис. 2.8. Прямоугольник имеет координаты (1,1), (5,1), (5,4), (1,4). Сканирующие строки с 1 по 4 имеют пересечения с ребрами многоугольника при x = 1 и 5. Пиксел адресуется координатами своего левого нижнего угла, значит, для каждой из этих сканирующих строк будут активированы пикселы с x-координатами 1, 2, 3, 4 и 5. На рис. 2.8 показан результат. Заметим, что площадь, покрываемая активированными пикселами, равна 20, в то время как настоящая площадь прямоугольника равна 12.

Модификация системы координат сканирующей строки и теста активации устраняет эту проблему, как это показано на рис. 2.8,b. Считается, что сканирующие строки проходят через центр строк пикселов, т. е. через середину интервала, как это показано на рис. 2.8,b. Тест активации модифицируется следующим образом: проверяется, лежит ли внутри интервала центр пиксела, расположенного справа от пересечения. Однако пикселы все еще адресуются координатами левого нижнего угла. Как показано на рис.2.8,b, результат данного метода корректен.