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

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

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

Хотя подобный подход и работает в подавляющем большинстве случаев, однако возможны ситуации, когда просто сортировка по расстоянию до картинной плоскости не обеспечивает правильного упорядочения граней (рис. 2.15), -так, грань В будет ошибочно выведена раньше, чем грань А; поэтому после сортировки желательно проверить порядок, в котором грани будут выводиться.

Предлагается следующий алгоритм этой проверки. Для простоты будем считать, что рассматривается параллельное проектирование вдоль оси Ог Перед выводом очередной грани Р следует убедиться, что никакая другая грань Q, которая стоит в списке после Р и проекция которой на ось Ог пересекается с проекцией грани Р (если пересечения нет, то порядок вывода Р и Q определен однозначно), не может закрываться гранью Р. В этом случае грань Р действительно должна быть выведена раньше, чем грань Q.

Ниже приведены 4 теста в порядке возрастания сложности проверки.

1. Пересекаются ли проекции этих граней на ось Ох?

2. Пересекаются ли проекции этих граней на ось Оу ?

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

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


⇐ Предыдущая| |Следующая ⇒