Методы приоритетов

Идея состоит в попытке упорядочить элементы сцены по некоторому признаку. Обычно в качестве критерия упорядочения выступает глубина элементов сцены. Тест глубины рассматривался ранее. Вывод проекций граней на картинную плоскость выполняется, начиная с самых дальних от точки наблюдения граней в порядке приближения к точке наблюдения. Возможны случаи, когда сортировка по расстоянию до картинной плоскости не обеспечивает правильного упорядочения граней из-за пересечения объектов. Перед выводом грани P следует убедиться, что никакая другая грань Q, проекция которой пересекается с проекцией грани Р, не закрывается гранью Р. Тогда грань Р выводится раньше Q. Требуются дополнительные проверки для установления порядка вывода граней. Рассмотрим эти проверки для наиболее простого случая параллельного проектирования вдоль оси Z. Тесты в порядке возрастания сложности проверки:

1. Накладываются ли друг на друга отрезки при проектировании проекций граней в плоскости XY на ось Х.

2. Накладываются ли друг на друга отрезки при проектировании проекций граней в плоскости XY на ось Y. y

3. Находится ли грань Р по отношению к плоскости, проходящей через грань Q,

по другую сторону, чем наблюдатель.

4. Находится ли грань Q по отношению к плоскости, проходящей через грань P,

по ту же сторону, что наблюдатель.

5. Пересекаются ли проекции граней P и Q на картинную плоскость. х

Если хотя бы на один из вопросов получен отрицательный ответ, считается, что грани P и Q упорядочены верно, грань P сравнивается со следующей гранью. В противном случае проверяется возможность поменять грани местами. Для этого выполняются следующие тесты:

3а. Находятся ли грань Q и наблюдатель по разные стороны плоскости, проходящей через грань Р.

4а. Находится ли грань P и наблюдатель по одну сторону плоскости, проходящей через грань Q.

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

Изложенный метод упорядочения - не единственный. Рассмотрим еще один, называемый МЕТОДОМ ДВОИЧНОГО РАЗБИЕНИЯ ПРОСТРАНСТВА. В основе - известный прием дихотомии (половинного деления). Пространство делится плоскостью на два полупространства. Далее используется исходная эвристика №2 (п. 6.5.1). Внутри каждого полупространства разбиение повторяется. Можно также секущую плоскость провести через произвольно выбранную грань (модификация алгоритма). Фактически строится двоичное дерево, узлами которого являются грани. Древовидные структуры достаточно легко программируются с помощью списков и объектно-ориентированного подхода. Объект - грань, методы -различные виды прохода по дереву (получить следующий выше/нижележащий элемент, получить следующий элемент на том же уровне соседней ветви и т.д.).

Как выбрать грани для разбиения? Существует два основных критерия:

· получить как можно более сбалансированное дерево;

· минимизировать количество разбиений.

Эти критерии обычно являются взаимно исключающими, требуется компромисс.

Алгоритм работает в объектном пространстве. Его сильная сторона - независимость от положения центра проектирования (точки наблюдения). Одну и ту же сцену можно перерисовывать для разных точек наблюдения.

К методам упорядочения относится также МЕТОД ПЛАВАЮЩЕГО ГОРИЗОНТА. В отличие от вышеизложенных, в этом методе сначала выводятся ближние к наблюдателю фрагменты. Пусть требуется получить каркасное изображение гладкой поверхности. Для изображения проекции ребра на картинную плоскость используется растровый алгоритм, например, алгоритм Брезенхейма. При выводе очередной точки проекции видимость анализируется с учетом нижней и верхней границ уже полученной части изображения. Эти границы называют соответственно нижним и верхним плавающим горизонтом, т.к. в процессе работы алгоритма их положение меняется. Горизонты можно представить как 2 целочисленных массива. В процессе работы изображение достраивается вне области, где оно уже построено. Пример - /hidden/surface1.cpp из [ 1 ]. Объяснение - на стр. 135 в [ 1 ], тема "Построение графика функции 2 переменных".

Дата добавления: 2014-01-11