Ограничивающие тела можно строить и для проекций объектов, причем в случае параллельного проектирования вдоль оси Oz ограничивающим телом для проекции будет прямоугольник, получающийся из ограничивающего тела для самого объекта отбрасыванием z-компоненты.

Ограничивающие тела можно описывать не только вокруг отдельных граней, но и вокруг наборов граней и сложных составных объектов, что позволяет легко отбрасывать сразу целые группы граней и объектов. При этом могут возникать сложные иерархические структуры.

10.2.3. Разбиение пространства (плоскости) (Spatial Subdivision)

Еще одним, методом, позволяющим заметно облегчить сравнение объектов друг с другом и использовать когерентность как в пространстве, так и на картинной плоскости, является разбиение пространства (картинной плоскости). С этой целью разбиение пространства строится уже на этапе препроцессирования и для каждой клетки разбиения составляется список всех объектов (граней), которые ее пересекают.

Простейшим вариантом является равномерное разбиение пространства на набор равных прямоугольных клеток (рис. 10.16).

Очень эффективным является использование разбиения картинной плоскости, когда каждой клетке разбиения ставится в соответствие список тех объектов, проекции которых данную клетку пересекают. Для отыскания всех объектов, которые закрывают рассматриваемый объект при проектировании, определяются объекты, попадающие в те же клетки картинной плоскости, что и проекция данного объекта, и на закрывание проверяются только они.

Для сцен с неравномерным распределением объектов имеет смысл использовать неравномерное (адаптивное) разбиение пространства или плоскости (рис. 10.17).

Иерархические структуры (Hierarchies)

10.2.4. Иерархические структуры (Hierarchies)

При работе с большими объемами данных весьма полезными могут оказаться различные древовидные (иерархические) структуры. Стандартными формами таких структур являются восьмеричные, тетрарные и BSP-деревья, а также деревья ограничивающих тел.

Компьютерная графика. Полигональные модели Одной из сравнительно простых структур является иерархия ограничивающих тел (Bounding Volume Hierarchy). Сначала ограничивающее тело описывается вокруг всех объектов. На следующем шаге объекты разбиваются на несколько компактных групп и вокруг каждой из них описывается свое ограничивающее тело. Далее каждая из групп снова разбивается на подгруппы, вокруг каждой из них строится ограничивающее тело и т. д. В результате получается дерево, корнем которого является тело, описанное вокруг всей сцены. Тела, построенные вокруг первичных групп образуют первичных потомков, вокруг вторичных - вторичных и т. д.


⇐ Предыдущая| |Следующая ⇒