Метод сортировки по глубине
Рассмотрим далее алгоритм удаления невидимых граней методом сортировки по глубине (авторы: Ньюэлл, Ньюэлл, Санча). Часть этого метода работает в пространстве объекта, а часть в пространстве изображения. Он также работает для параллельной проекции, то есть с учетом того что произведено перспективное преобразование. Введем определение пространственной оболочки.
Пространственной оболочкой трехмерного объекта называется минимальный прямоугольный параллелепипед, целиком содержащий внутри себя данный объект. Аналогично можно определить двумерную и одномерную пространственные оболочки.
Метод состоит из трех основных шагов:
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 разделяется плоскостью другого на два новых многоугольника. Эти два новых многоугольника включаются в соответствующие места упорядоченного списка, и алгоритм продолжает работу.