Метод сортировки по глубине

Рассмотрим далее алгоритм удаления невидимых граней методом сортировки по глубине (авторы: Ньюэлл, Ньюэлл, Санча). Часть этого метода работает в пространстве объекта, а часть в пространстве изображения. Он также работает для параллельной проекции, то есть с учетом того что произведено перспективное преобразование. Введем определение пространственной оболочки.

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

Метод состоит из трех основных шагов:

1. Упорядочение всех многоугольников в соответствии с их наибольшими z-координатами.

2. Разрешение всех неопределенностей, которые возникают при перекрытии z-оболочек многоугольников.

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

Ближайшие многоугольники преобразуются в растровую форму последними и закрывают более отдаленные многоугольники, так как изображаются поверх предыдущих. Реализация пунктов 1 и 3 достаточно очевидна. Рассмотрим подробнее пункт 2.

Пусть многоугольник P после упорядочения находится в конце списка, то есть является наиболее удаленным. Все многоугольники Q чьи оболочки перекрываются с z-оболочкой P должны проходить проверку по пяти тестам (шагам). Если на некотором шаге получен утвердительный ответ, то P сразу преобразуется в растровую форму.

Пять тестов:

1. x-Оболочки многоугольников не перекрываются, поэтому сами многоугольники тоже не перекрываются.

2. y-Оболочки многоугольников не перекрываются, поэтому сами многоугольники тоже не перекрываются.

3. P полностью расположен с той стороны от плоскости Q, которая дальше от точки зрения (этот тест дает положительный ответ как показано на рис. 36.

4. Q полностью расположен с той стороны от плоскости P, которая ближе к точке зрения. Этот тест дает положительный ответ как показано на рис. 37.

5.
Проекции многоугольников на плоскости xOy, то есть на экране, не перекрываются (это определяется сравнением ребер одного многоугольника с ребрами другого).

Если во всех пяти тестах получен отрицательный ответ, то P – действительно закрывает Q. Тогда меняем P и Q в списке местами. В случае, как показано на рис. 38, алгоритм зацикливается.

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