2015-05-30
1046
Алгоритмы удаления невидимых граней могут быть условно поделены на два класса в зависимости от принципов, заложенных для их реализации. Первый класс – это алгоритмы работающие в пространстве объекта. Это означает, что для определения видимости данной грани сравнивается ее взаимное расположение со всеми остальными гранями в трехмерной сцене.
Пусть N – количество граней в трехмерной сцене. Для построения трехмерной сцены в этом случае необходимо сравнить положение каждой грани с оставшимися, что требует порядка 2 N операций. Например, пусть количество граней в трехмерной сцене 1000 = N, тогда время работы алгоритмов этого класса порядка 1,000,000 операций.
Другой класс алгоритмов - работающих в пространстве изображения, основан на нахождении точки ближайшей грани которую пересекает луч зрения, проходящий через заданную точку на растре. Поскольку число точек на растровом экране фиксировано, то алгоритмы этого класса менее чувствительны к увеличению количества объектов в трехмерной сцене. Пусть n - число точек на растровом экране. Тогда количество операций, необходимых для построения трехмерной сцены будет порядка N n ×.
Например, для экранного разрешения 320´200 точек, = n 64000, тогда количество операций для = N 1000 граней будет порядка 64,000,000. Выбор класса алгоритма может зависеть от особенностей конкретной задачи, а также от способов реализации алгоритма.
Рассмотрим алгоритм удаления невидимых граней методом сортировки по глубине (авторы: Ньюэлл, Ньюэлл, Санча). Часть этого метода работает в пространстве объекта, а часть в пространстве изображения. Он также работает для параллельной проекции, то есть с учетом того что произведено перспективное преобразование. Введем определение
пространственной оболочки.
Пространственной оболочкой трехмерного объекта называется минимальный прямоугольный параллелепипед, целиком содержащий внутри себя данный объект. Аналогично можно определить двумерную и одномерную пространственные оболочки.
Метод состоит из трех основных шагов:
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, которая ближе к точке зрения. Этот тест дает положительный ответ как показано на рис. 36 b).
5. Проекции многоугольников на плоскости xOy, то есть на экране, не перекрываются (это определяется сравнением ребер одного многоугольника с ребрами другого).
Если во всех пяти тестах получен отрицательный ответ, то P – действительно закрывает Q. Тогда меняем P и Q в списке местами. Для избежания зацикливания вводится ограничение: многоугольник, перемещенный в конец списка (т.е. помеченный), не может быть повторно перемещен. Вместо этого многоугольник P или Q разделяется плоскостью другого на два новых многоугольника. Эти два новых многоугольника включаются в соответствующие места упорядоченного списка, и алгоритм продолжает работу.
