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

[11]

Основная идея свободного октарного дерева такая же, как и обычного дерева, за исключением того, что размер каждого прямоугольного параллелепипеда не фиксирован, т.е. значение длины параллелепипеда / можно заменить на kl, где к>\ (рис. 5.)

б

а

Рис. 5. Сравнение октарного дерева (а) со свободным октарным деревом (б).

Рассмотрим рисунок 5. Объект "звезда" пересекает разделяющую плоскость октарного дерева (а). Справа,. Объект "звезда" целиком расположен в левом верхнем узле (б) при использовании свободного октарного дерева, k=1.5.

Следует отметить, что центры ограничивающих объемов остаются на своих местах. Использование параллелепипедов большего размера позволяет сократить число объектов, пересекающих плоскости разбиения, и разместить такие объекты глубже в дереве. Объект всегда вставляется только в один лист дерева, что делает удаление объекта тривиальной задачей. Предположим, k = 2. Сложность вставки и удаления объектов в такое дерево равняется 0(1). Размеры объекта позволяют сразу определить, на каком уровне октарного дерева его возможно расположить целиком в одном параллелепипеде. Благодаря таким свойствам эта структура хорошо подходит для оперирования динамическими объектами. Однака при этом наблюдаются меньшая эффективность и потеря четкого порядка во время обхода структуры.

Граф сцены

В основе BVH, BSP и октарного дерева лежит структура данных - дерево. Различия этих подходов заключаются в способах разделения пространства сцены и механизмов хранения геометрических объектов. Однако для расчета и отображения трехмерной сцены необходимо больше, чем набор геометрических примитивов. Граф сцены представляет собой древовидную структуру более высокого уровня, чем рассмотренные раннее, и оперирует такими понятиями как текстура, трансформация, уровень детализации, свойства материала, источники освещения и, возможно, еще что-то, необходимое для расчета изображения. Обычно граф сцены представляется деревом, и расчет сцены происходит посредством его обхода. Например, источник освещения может быть помещен в один из внутренних узлов, при этом он будет действовать только на объекты, расположенные в его поддереве. Таким же примером служит текстура, накладывающаяся

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

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

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

При появлении у нескольких узлов общего "ребенка", древовидная структура называется направленным ациклическим графом (Directed Acyclic Graph) [1]. Ациклический - означает отсутствие петли, направленный - означает, четкую заданность направления соединения двух соединенных узлов, (т.е. кто "родитель", а кто "ребенок"). Направленный ациклический граф часто используется в качестве графа сцены, так как позволяет производить инстанцирование (instancing) - операции получения нескольких

копий объекта без репродукции геометрии объекта (рис. 6.).

узлах.

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

Следует отметить, что возможно использование более одного графа сцены в одной и той же сцене, т. е. для решения различных задач используются различные графы.

Заключение

Рассмотрены три типа структурирования пространственных данных: BVH, BSP-дерево, октарное дерево. Способ структурирования данных необходимо выбирать, основываясь на типе сцены, с которой придется работать, и задаче, которую придется решать.

Для решения задачи визуализации больших открытых пространств и определения столкновений на такой сцене использование структуры "октарное дерево" является

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

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

BVH целесообразно использовать если задача локализации объектов и групп объектов, ограничивающий объем которых необходимо найти, имеет простое решение. В случае представления виртуальной сцены одним набором примитивов (polygon soup) использование данного метода неэффективно.

Литература

1.Cormen, T.H., C.E. Leiserson, and R. Rivest, Introduction to Algorithms, MIT Press, Inc., Cambridge, Massachusetts, 1990.

2.Larsson, Thomas, and Tomas Akenine-Moller, "Collision Detection for Continuously Deforming Bodies", Eurographics 2001.

3.Ratcliff, John W., "Sphere Trees for Fast Visibility Culling, Ray Tracing and Range Searching", Game Programming Gems 2.

4.Samet, Hanan, The Design and Analysis of Spatial Data Structures, Adison-Wesley, Reading. Massachusetts, 1989.

5.Abrash, Michael, Michael Abrashs Graphics Programming Black Book, Special Edition, The Coriolis Group, Inc., Arizona, 1997.

6.Fuchs, H., Z.M. Kedem, and B.F. Naylor, "On Visible Surface Generation by A Priori Tree Structure", Computer Graphics, (Siggraph 80 Proceeding).

7.Fuchs, H., G.D. Abram, and E.D. Grant, "Near Real-Time Shader Display of Rigid Objects", Computer Graphics, (Siggraph 89 Proceeding).

8.Gordon, Dan, and Shuhong Chen, "Front-to-back display of BSP trees", IEEE computer Graphics and Applications.

9.James, Adam, Binary Space Partition for Accelerated Hidden Surface Removal and Rendering of Static Environments, Ph. D. Thesis, University of East Anglia, August

1999.

10.Samet, Hanan, Application of Spatial Data Structures: Computer Graphics, Image Processing and GIS, Addison-Wesley, Reading. Massachusetts, 1989.

11.Ulrich, Thatcher, "Loose Octrees", Game Programming Gems.