Алгоритмы генерации октодеревьев можно структурировать так, чтобы они принимали определения объектов в любой форме, например, многоугольной сетки, криволинейных участков поверхности или стереометрических конструкций. Октодерево одного объекта можно построить из ограждающего параллелепипеда, определяемого координатными границами объекта.
Объемный объект, представленный в форме октодерева, можно подвергать различным обработкам. Алгоритм выполнения операций над множествами можно применить к двум представлениям в форме октодерева для одной области пространства. При операции логического сложения новое октодерево строится с использованием узлов обоих входных октодеревьев. Чтобы для двух входных октодеревьев задать представление пересечения, строится новое дерево с использованием октантов, в которых два объекта перекрываются. Подобным образом, при вычитании исследуются области, занятые одним объектом и не занятые другим.
Разработано еще несколько алгоритмов обработки октодеревьев. Например, трехмерные вращения выполняются путем преобразования пространственных областей, представленных занятыми октантами. Чтобы определить на сцене видимые объекты, можно вначале выяснить, заняты ли передние октанты. Данный процесс продолжается до тех пор, пока все занятые октанты не будут определены по направлению наблюдения. Первый объект, обнаруженный по направлению наблюдения (через октанты пространства от переднего плана вглубь), является видимым, а информация относительно этого объекта может передаваться в представление в форме квадродерева с последующим отображением на экране.
BSP-ДЕРЕБЬЯ
Данная схема представления подобна кодированию в форме октодерева, только в этом случае пространство на каждом этапе делится не на восемь, а на два участка. С помощью дерева бинарного разделения пространства (binary space-partitioning - BSP) на каждом этапе сцена делится на два участка плоскостью, которая может проходить через любую точку и иметь любую ориентацию. В кодировании же с помощью октодерева сцена на каждом этапе делится тремя взаимно перпендикулярными плоскостями, параллельными декартовым координатным плоскостям.
Адаптивное деление пространства с помощью BSP-деревьев может быть более эффективным, поскольку разрезающие плоскости располагаются где угодно и ориентированы как угодно согласно пространственному расположению объектов. Это может уменьшить глубину дерева, предоставляющего сцену, по сравнению с октоде-ревом, а следовательно, сократить время, необходимое для поиска на дереве. Кроме того, BSP-деревья полезны для определения видимых поверхностей при разделении пространства в алгоритмах построения хода лучей.
МЕТОДЫ ФРАКТАЛЬНОЙ ГЕОМЕТРИИ
Во всех рассмотренных выше представлениях объектов используются методы евклидовой геометрии; т.е. формы объектов описываются уравнениями. Данных методов достаточно для описания объектов производства, которые имеют гладкие поверхности и правильные формы. Однако такие природные объекты, как горы и облака, имеют неправильные или фрагментированные особенности, и евклидовы методы не позволяют реалистично представить подобные объекты. Естественные объекты описываются методами фрактальной геометрии, где для моделирования объектов используются процедуры, а не уравнения. Как можно было ожидать, характеристики процедурно определенных объектов достаточно отличаются от характеристик объектов, описанных уравнениями. Представления объектов средствами фрактальной геометрии