Метод сортировки по глубине (depth sort) реализует подход к решению проблемы удаления невидимых поверхностей, основанный на анализе пространства объектов. Мы рассмотрим этот метод применительно к сценам, состоящим из плоских многоугольников, но его можно распространить и на другие классы объектов. Метод сортировки по глубине является вариантом еще более простого алгоритма, получившего название алгоритма маляра (painter's algorithm).
Предположим, что имеется набор многоугольников, отсортированных по расстоянию от них до наблюдателя. В примере, показанном на рис. 7.32,а, имеются два многоугольника. С точки зрения наблюдателя они выглядят так, как показано на рис. 7.32,6, - один многоугольник частично закрывает от наблюдателя второй. Для корректного отображения такой сцены нужно определить, какая часть дальнего многоугольника перекрыта тем, что расположен ближе, "вырезать" ее, а оставшуюся часть подвергнуть растровому преобразованию и вывести на экран. Но можно поступить и по-другому - некоторые считают, что именно так делает маляр, нанося новый рисунок поверх старого. Образы объектов можно формировать в порядке от наиболее удаленного к менее удаленным. В результате образы объектов, расположенных ближе к наблюдателю, автоматически перекроют образы объектов, расположенных дальше, и необходимость в каком-либо "искусственном" анализе перекрытия полностью отпадет. Для такого метода придуман даже специальный термин - отображение многоугольников от дальнего к ближнему (back-to-front rendering)1Но реализация описанного подхода требует решения двух проблем: как рассортировать многоугольники в пространстве сцены и что делать, если многоугольники пересекаются. Обе эти проблемы решаются методом сортировки по глубине, хотя для некоторых ситуаций можно разработать и более эффективные методы (см. упр. 7.10).
Предположим, что для каждого многоугольника уже вычислены параметры прямоугольной оболочки. Следующая операция - отсортировать все многоугольники по степени
7.7.3. Сортировка по глубине