15.4. Алгоритм сортировки по глубине
В этом алгоритме, разработанном Ньюэлом, Ньюэлом и Санча [341], применяется простой подход, состоящий из трех шагов:
1. Упорядочение всех многоугольников в соответствии с их наибольшими z-координатами.
2. Разрешение всех неопределенностей, которые возникают при перекрытии z-оболочек.
3. Преобразование каждого из многоугольников в растровую форму, производимое в порядке уменьшения их наибольшей г-координаты.
Основная идея алгоритма заключается в упорядочении многоугольников в соответствии с их удаленностью от точки зрения, а также в размещении этих многоугольников в буфере регенерации в порядке убывания расстояния. Ближайшие многоугольники преобразуются в растровую форму последними и закрывают более отдаленные многоугольники, поскольку записываются в буфер регенерации поверх старых. При разложении каждого многоугольника в растр значения его пэлов вычисляются с использованием одного из правил тоновой или цветовой закраски, изложенных в гл. 16. Рассматриваемый алгоритм обладает свойствами алгоритмов, работающих в пространстве изображения и в пространстве объекта: некоторые его шаги выполняются в первом пространстве, а некоторые — во втором.
Этот алгоритм может легко работать с явным приоритетом, рассмотренным в разд. 11.9. Приоритет играет роль максимального значения z, причем неопределенностей, связанных с глубиной, в этом случае может не быть, поскольку считается, что каждому приоритету соответствует своя плоскость с постоянной координатой z. На рис. 15.6 показаны некоторые типы неопределенностей, необходимость в разрешении которых может возникнуть на шаге 2. Как же устраняются эти неопределенности? Обозначим многоугольник, находящийся в конце упорядоченного списка многоугольников, через Р. До отображения в буфер регенерации этот многоуголь
ник необходимо сравнить с каждой гранью Q, г-оболочка которой перекрывает z-оболочку многоугольника Р. Проверка складывается не более чем из пяти шагов (тестов), которые выполняются в порядке возрастания сложности. Как только на любом из шагов выдается утвердительный ответ, Р сразу преобразуется в растровую форму. Этими пятью тестами являются следующие:
1. х-оболочки многоугольников не перекрываются, поэтому сами многоугольники тоже не перекрываются;
2. у-оболочки многоугольников не перекрываются, поэтому сами многоугольники тоже не перекрываются. (Отметим, что в тестах 1 и 2, взятых в совокупности, оболочки рассматриваются в том виде, как были впервые введены в предыдущем разделе.)
3. Р целиком лежит с той стороны от плоскости Q, которая дальше от точки зрения (этот тест дает отрицательный ответ в случае а на рис. 15.6 и утвердительный ответ в ситуации, показанной на рис. 15.7).
4. Q целиком находится с той стороны от плоскости Р, которая ближе к точке зрения (этот тест дает отрицательный ответ в случае а на рис. 15.6 и утвердительный ответ в ситуации, показанной на рис. 15.8).
5. Проекции многоугольников на плоскость ху (экран) не перекрываются (это определяется путем сравнения ребер одного многоугольника с ребрами другого). В упражнении 15.7 предложен способ реализации тестов 3 и 4.
Если во всех пяти тестах получен отрицательный ответ, мы предполагаем, что Р действительно закрывает Q, поэтому поменяем Р и Q местами в списке, пометив при этом, что многоугольник Q был перемещен на новое место в конце списка. В случае а на рис. 15.6 так оно и есть: если мы сравним Q с Р, то обнаружим с помощью теста 3 (где Р и Q поменялись местами), что многоугольник Q должен преобразовываться в растровую форму первым. В случаях же б и в на рис. 15.6 (поскольку не существует плоскости, разделяющей многоугольники) многоугольник Q рано или поздно придется снова перемещать в списке, и алгоритм зациклится.
Чтобы избежать зацикливания, введем ограничение, в соответствии с которым многоугольник, перенесенный в конец списка (и, следовательно, помеченный), не может подвергаться повторному перемещению. Вместо этого многоугольник Р или Q рассекается на ! две части плоскостью другого многоугольника (разд. 11.6). Первоначальный многоугольник отбрасывается, а две его части включаются в соответствующие места упорядоченного списка, и алгоритм ; продолжает работать, как прежде.
С помощью такого алгоритма многоугольники, находящиеся с задней стороны объекта, изображаются первыми, но затем они могут быть закрыты. Это может помочь наблюдателю понять пространственную структуру объекта, однако отсюда следует, что некоторые многоугольники будут без необходимости преобразовываться в растровую форму. Алгоритм плохо приспособлен для использования на растровых фильмирующих устройствах, поскольку фильм, проэкспонированный под действием некоторого многоугольника, нельзя «разэкспонировать», если позднее на этот многоугольник наложится другой.
С помощью алгоритма сортировки по глубине можно стирать также и невидимые ребра. Вначале в буфер регенерации заносятся некоторые значения V0. При разложении многоугольника в растр его ребрам присваивается некоторое другое значение Vi, а все внутренние пэлы устанавливаются в V0. Если многоугольник перекрывает другой многоугольник, который ранее уже был преобразован в растровую форму, при установке внутренности нового многоугольника в уо будут стерты ребра предыдущего многоугольника. Подобный подход можно использовать и в других алгоритмах, рассмотренных в этой главе.
Упомянутые выше алгоритмы изображения однозначных функций двух переменных действуют так же, как и алгоритм сортировки по глубине, лишь обработка в этих случаях производится, начиная с переднего плана (минимальные значения г) по направлению к заднему. Сортировка, как таковая, отсутствует, поскольку функция однозначная. При изображении каждой новой грани поверхности, представляющей функцию, рисуется только та часть этой грани, которая попадает за пределы внешней границы фигуры, образован-ной ранее рассмотренными гранями. Внешняя граница затем соответствующим образом расширяется. В новом алгоритме Сечреста и Гринберга обработка производится снизу вверх, а не спереди назад 1416].
- 1. Векторные дисплеи.
- 2. Растровые дисплеи.
- Программистская модель интерактивной графики
- Лекция 2
- 640X480
- Лекция 4. Анимация
- Лекция 7. Алгоритмы растровой графики. Растровая графика.
- Лекция 9
- Перспективные проекции
- 15.1. Введение
- 15.2. Упрощение сравнений по глубине: перспективное преобразование
- 15.3. Исключение сравнений по глубине. Оболочки
- 15.4. Алгоритм сортировки по глубине
- 15.5. Алгоритм, использующий z-буфер
- 15.6. Алгоритмы построчного сканирования
- 15.7. Алгоритмы разбиения области
- 15.8. Эффективность алгоритма
- 15.9. Алгоритмы для криволинейных поверхностей
- Введение в OpenGl
- Void glVertex[2 3 4][s I f d] (type coords)
- Void glVertex[2 3 4][s I f d]V (type *coords)
- Gl_points каждая вершина задает координаты некоторой точки. Gl_lines каждая отдельная пара вершин определяет отрезок; ес-ли задано нечетное число вершин, то последняя вершина игнорируется.
- Gl_polygon последовательно задаются вершины выпуклог многоугольника.
- OpenGl в Delphi
- Событие. Сообщение. Контекст.