Основы построения 3-х мерных сцен с использованием библиотеки DirectX. Макушкина Л.А - 21 стр.

Различаются способы поиска и определения взаимного расположения объектов.
На этом этапе существует два общих подхода.
       1.Итерационный (приоритетный).
       Осуществляется последовательный просмотр всех объектов сцены и их
сортировка по т.п. глубине, т.е. их взаимному расположению.
       2.Рекурсивный (“разделяй и властвуй”).
       Вся сцена рекурсивно разбивается на части до тех пор, пока решение всей
задачи загораживания не сведется к решению простых более мелких задач.
       Существуют также алгоритмы, в которых задача загораживания решается с
помощью аппаратных особенностей системы или геометрических свойств
отображаемых объектов.
       Примером для 1-го подхода может служить простой метод перебора
(алгоритм Робертса).Этот метод лучше всего подходит для каркасных объектов.
Рассматривается каждое ребро каждого объекта со всеми гранями всех объектов.
Возможны варианты (рис. 6).




               Рис. 6. Взаимное расположение граней и ребер.

       Все ребра и грани сортируются, затем отображаются от дальних к
ближним. Ребро разбивается на части, к обеим применяются предыдущие
варианты.
       Время выполнения пропорционально произведению числа ребер на число
граней.
       Для уменьшения времени выполнения данного алгоритма применяется
метод кеширования по равномерной сетке. Этот метод исключает сравнение
неинцедентных ребер и граней. Ребро и грань считаются инцедентными, если их
проекции на плоскость проецирования имеют фактическое пересечение.
       Плоскость проецирования разбивается на прямоугольные ячейки. Если
ячейка пересекается с проекцией ребра на плоскость проецирования, то ячейка и
ребро являются инцедентными. То же понятие применяется к ячейке и грани. Для
каждой ячейки сетки вычисляются инцедентные с ней грани. По результатам этой
проверки составляется список. Затем при переборе ребер анализируются только
те грани, которые имеют с этими ребрами общие инцедентные ячейки. Время
выполнения прямо пропорционально количеству ребер. Однако требуется
дополнительная память. Отсюда название метода - «кэширование».
       Примером для 2-го подхода может служить метод двоичного разбиения
пространства. Из сцены произвольным образом выбирается некоторая грань,
которая в дальнейшем называется активной. Оставшиеся грани делятся на две
группы: 1-я –та, которая лежит в одном полупространсве с наблюдателем
относительно активной грани, 2-я – в другом. Грани 1-й группы не могут
                                             23