2. Алгоритм Робертса
Алгоритм Робертса представляет собой первое известное решение задачи об удалении невидимых линий и поверхностей. Этот алгоритм работает в пространстве объекта. Алгоритм, прежде всего, удаляет из каждого тела те ребра или грани, которые экранируются самим телом. Затем каждое из видимых ребер каждого тела сравнивается с каждым из оставшихся тел для определения того, какая его часть экранируется этими телами. Вычислительная трудоемкость алгоритма Робертса растет теоретически как квадрат числа объектов. В настоящее время в связи с широким применением растровых устройств наиболее распространены алгоритмы, работающие в пространстве изображения, имеющие более низкую вычислительную трудоемкость, равную произведению числа объектов на разрешающую способность экрана визуализации. Это привело к снижению интереса к алгоритму Робертса. Но математические методы, используемые в алгоритме, применяются в большинстве современных приложений компьютерной графики. Наконец, более поздние реализации алгоритма, использующие предварительную сортировку по расстоянию от точки наблюдения, в сочетании с простыми габаритными (или минимаксными) тестами демонстрируют почти линейную зависимость вычислительной трудоемкости от числа объектов.
Более подробно данный алгоритм будет рассмотрен в третьей части учебного пособия, так как для его понимания необходимо предварительно рассмотреть некоторые основы компьютерной геометрии.
3. Алгоритм Варнока
Алгоритм основывается на гипотезе о способе обработки информации, содержащейся в сцене, глазом и мозгом человека [1]. Эта гипотеза заключается в том, что тратится очень мало времени и усилий на обработку тех областей, которые содержат мало информации. Большая часть времени и труда затрачивается на области с высоким информационным содержанием.
«Классический» пример: поверхность стола, на котором нет ничего, кроме вазы с предметами (рис. 3.1). Для восприятия цвета, фактуры и других характеристик всей поверхности стола много времени не нужно. Все внимание сосредотачивается на вазе. В каком месте стола она расположена, из какого материала сделана, какие предметы, какого они цвета и так далее?
Рис. 3.1. Алгоритм Варнока
В каждом случае, по мере сужения интересов, возрастает уровень требуемой детализации. Если на определенном уровне детализации на конкретный вопрос ответить нельзя, то он откладывается на время для последующего рассмотрения.
Алгоритм Варнока работает в пространстве изображения. В этом пространстве рассматривается окно и решается вопрос о том, пусто ли оно, или его содержимое достаточно просто для визуализации. Если это так, то окно изображается. Если нет, то оно разбивается на части до тех пор, пока содержимое подокна не станет достаточно простым для визуализации или пока размер подокна не достигнет предела разрешения экрана. В последнем случае информация, содержащаяся в окне, усредняется, и оно изображается.
С уществует множество реализаций алгоритма Варнока, в том числе, работающих попеременно в пространствах изображения и объекта. Конкретная реализация зависит от метода разбиения окна и от критерия, используемого для решения вопроса о «простоте» окна.
В оригинальной версии алгоритма окно, содержимое которого слишком сложно изображать, разбивается на 4 подокна. Окно, в котором что-то есть, разбивается далее до тех пор, пока не будет достигнут предел разрешения экрана. Для устранения лестничного эффекта возможно дальнейшее разбиение.
В качестве примера рассмотрим сцену, изображенную на рис. 3.2, а.
Окно слишком сложно для визуализации, следовательно, разбиваем его на 4 части (рис. 3.2, б) и рассматриваем левое нижнее подокно первого разбиения. Опять слишком сложно – разбиваем на 4 части (рис. 3.2, в). Левое нижнее подокно после второго разбиения пусто – изображаем его цветом фона. Возвращаемся к правому нижнему подокну второго разбиения – снова сложно, разбиваем его на 4 части (рис. 3.2, г) и так далее. В конце концов, при N-ном разбиении достигаем размеров пиксела (рис. 3.2, д).
Теперь необходимо «вспомнить» какой алгоритм мы применяем – удаления невидимых линий или поверхностей. В случае удаления невидимых линий – окрашиваем левое и правое нижние и верхнее левое подокна в цвет многоугольника, а правое верхнее – в цвет фона. Затем возвращаемся к предыдущим подокнам и так далее. Результат показан на рис. 3.3. В случае удаления невидимых поверхностей – окрашиваем все подокна в цвет ближайших к наблюдателю многоугольников (рис. 3.4).
В данном варианте используются очень простой метод разбиения и критерий определения простоты визуализации, что приводит к большому количеству подразбиений. Для получения более эффективного алгоритма необходимо использовать более сложные методы и критерии. В случае простых сцен можно использовать прямоугольную оболочку (рис. 3.5). При этом окна подразбиения необязательно квадратные.
Для более сложных сцен необходимо определить способы расположения многоугольников относительно окна. Многоугольник является:
внешним, если он находится вне окна (рис. 3.6, а);
внутренним, если он находится внутри окна (рис. 3.6, б);
пересекающим, если он пересекает окно (рис. 3.6, в);
охватывающим, если окно находится внутри него (рис. 3.6, г).
Рис. 3.2. Алгоритм отсечения Варнока
Рис. 3.3. Алгоритм отсечения Варнока. Удаление невидимых линий
Рис. 3.4. Алгоритм отсечения Варнока. Удаление невидимых поверхностей
Рис. 3.5. Вариант разбиения в алгоритме типа Варнока
Рис. 3.6. Типы многоугольников
И алгоритм удаления невидимых поверхностей будет заключаться в следующем:
если все многоугольники сцены являются внешними, то окно пусто и закрашивается цветом фона;
если внутри окна только один многоугольник, то он закрашивается своим цветом, остальное – фоном;
если только один многоугольник пересекает окно, то его часть, попадающая в окно, окрашивается цветом многоугольника, остальное – фоном;
если окно охвачено только одним многоугольником и в нем больше нет многоугольников, то окно окрашивается цветом этого многоугольника;
если окно охвачено несколькими многоугольниками, которые не протыкают друг друга, и в нем больше нет многоугольников, то окно окрашивается цветом ближайшего к наблюдателю многоугольника;
иначе – проводится разбиение окна.
Аналогичным образом можно разработать правила и для алгоритма удаления невидимых линий:
если все многоугольники сцены являются внешними, то окно пусто и закрашивается цветом фона;
если внутри окна только один многоугольник, то рисуется его внешняя граница, остальное закрашивается фоном;
если только один многоугольник пересекает окно, то рисуется часть его внешней границы, попадающая в окно, остальное окрашивается фоном;
если окно охвачено одним или несколькими многоугольниками и в нем больше нет многоугольников, то окно окрашивается фоном;
иначе – проводится разбиение окна.
Для реализации этих правил необходимы методы определения положения многоугольника относительно окна.
В случае прямоугольных окон можно воспользоваться минимаксными (габаритными) тестами (рис. 3.7). То есть, если Xl, Xr, Yu, Yd – четыре ребра окна, а Xmax, Xmin, Ymax, Ymin – ребра прямоугольной оболочки, то этот многоугольник будет:
внешним, если:
Xmin > Xr или Xmax < Xl или Ymin > Yu или Ymаx > Yd;
внутренними, если:
Xmin ≥ Xl & Xmax ≤ Xr & Ymin ≥ Yd & Ymаx ≤Yu.
Следующий способ – подстановка для проверки пересечения окна отсечения многоугольником. Координаты вершины окна подставляются в тестовую функцию, заданную уравнением прямой, несущей ребро многоугольника (Y = kX + b). Если знак этой тестовой функции не зависит от значений координат вершин окна, то все вершины многоугольника лежат по одну сторону от несущей прямой и на указанной прямой нет точек пересечения. Если эти значения различны, то многоугольник, возможно, пересекает окно. Если ни одно из ребер не пересекает окно, то этот многоугольник является либо внешним, либо охватывает окно.
Уравнение тестовой функции для прямой, проходящей через вершины P1 и P2, имеет вид:
Test Function = Y – kX - b,
где k = (Y2 - Y1)/(X2 - X1), при X2 ≠ X1,
b = Y1 - kX1
и Test Function = X - X1 при X2 = X1.
Простым габаритным тестом нельзя идентифицировать все виды многоугольников, например, внешние многоугольники (рис. 3.6, а) или охватывающие многоугольники (рис. 3.6, г). Следовательно, здесь необходимо применять более сложные тесты. В приведенных ниже тестах предполагается, что были идентифицированы внутренние и пересекающие многоугольники. Остается определить внешние и охватывающие многоугольники.
Рис. 3.7. Проверка с помощью прямоугольной оболочки
Тест с бесконечной прямой:
проводится луч из любой точки окна в бесконечность (обычно, используется одно из ребер окна) и подсчитывается число пересечений этого луча с заданным многоугольником (рис. 3.8, а), касание вершины равно 2, если вершина – локальный максимум или минимум, иначе - 1 (рис. 3.8, б). Касание стороны равно 2. Если сумма пересечений четная (или равна 0), то многоугольник внешний, иначе, он охватывает окно.
Тест с подсчетом угла:
совершается обход ребер многоугольника по или против часовой стрелке. Суммируются углы, образованные векторами, начинающимися в любой точке окна и проходящими через начало и конец проходимого в данный момент ребра многоугольника (рис. 3.9). Если сумма углов равна 0, то многоугольник внешний, если сумма углов равна ±360*n, то многоугольник охватывает окно.
На практике нет необходимости точно вычислять углы (да это и невозможно). Как и в случае алгоритма Коэна-Сазерленда, пространство изображения разбивается на 9 частей (рис. 3.10).
Внешние октанты нумеруются от 0 до 7. Число целых октантов, покрытых углом равно ∆α = (№ октанта со вторым концом ребра) – (№ октанта с первым концом ребра). Предлагается следующий алгоритм:
если ∆α > 4, то ∆α = ∆α – 8;
если ∆α < - 4, то ∆α = ∆α + 8.
Суммируя все ∆α, получаем:
если сумма ∆α равна 0, то многоугольник внешний по отношению к окну;
если сумма ∆α равна ±8*n, то многоугольник охватывает окно.
Используя иерархически все вышеизложенные методы (и еще более сложные), мы получим алгоритм. Простейшая реализация алгоритма Варнока изложена в [1].
Рис. 3.8. Тест с бесконечной прямой
Рис. 3.9. Тест с подсчетом угла
а)
Рис. 3.10. Модифицированный тест с подсчетом угла