Каждая ветвь дерева состоит из кода и восьми указателей на восемь потомков, пронумерованных от 0 до 7. Если код = "черный", часть пространства, представляемая этой ветвью является заполненной и все указатели нулевые, т.е это лист. Аналогично, если код = "белый", часть пространства пустая и это опять лист. Код = "серый" соответствует случаю, когда область пространства частично пуста и частично заполнена. В этом случае 8 ссылок указывают на подразбиение данной области. Например, на рисунке объект (в) представляется деревом (с)
Примечание: Если рассматривается плоский случай (2D), то мы получаем квадро-деревья. В этом случае плоскость рекурсивно разбивается на занумерованные квадранты.

Очень важным достоинством октарных деревьев является то, что они хранят информацию в упорядоченном виде. Это дает нам возможность разработать простые алгоритмы рендеринга объектов, представляемых в таком виде. Например, если точка наблюдения расположена в октанте x, y, z>0, упорядочение дерева 4, 0, 5, 1, 6, 2, 7, 3 будет давать корректные результаты (при условии вывода back-to-front)

Напомним, что октанты дерева пронумерованы от 0 до 7. Эти числа могут быть использованы для конструирования адреса каждой ветви дерева, кроме корня. Адрес ветви уровня i есть последовательность i чисел от 0 до 7 – путь от корня к этой ветви. Также можно включить специальный символ X для обозначения того, что в последовательности чисел меньше, чем максимальное разрешение. При таком подходе линейная запись дерева есть просто сортированный массив адресов ветвей с кодом "черный". Например, дерево на рисунке кодируется следующей последовательностью: {03,1X,51,53}
Другой подход к линейному представлению дерева базируется на обходе дерева в фиксированном порядке, например, слева направо, сверху вниз. Кодирование использует трехсимвольный алгоритм "B","W" и "(" (обозначают соответственно "черную" ветвь, "белую" ветвь и нелистовую ветвь). Дерево на рисунке кодируется в этом случае следующей строкой:

((WWWBWWWWBWWW(WBWBWWWWWW

Как альтернатива октарному делению пространства также возможно бинарное деление. Это представление очень похоже на предыдущее. Но здесь производится деление пространства пополам, а не на восемь частей. Деление производится последовательно в направлении осей x,y и z.
По сравнению с октарными деревьями, бинарные требуют немного меньше памяти для хранения. Также возможна линейная запись таких деревьев по аналогии с октарными. Например, для дерева, изображенного на рисунке, линейная запись будет такой: ((W(W(W(WBW(((W((WB(WBBW



Рисунок 4 Бинарное дерево

Некоторые характеристики деревьев:

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

Поскольку глобальная параметризация поверхности объекта произвольной формы обычно является трудновыполнимой задачей, поверхность приближается набором граней (face). Обычно разбиение выполняется таким образом, чтобы каждая грань имела компактное математическое представление.
Границы граней представляется ребрами (edge). Так - же как и грани, ребра выбираются таким образом, чтобы иметь компактное математическое описание. Часть кривой, формирующей ребро, заканчивается вершинами (vertex).
Поверхностная модель, которая имеет только плоские грани, называется полигональной моделью. Рассмотрим возможные варианты задания полигональной модели.

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

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

Повторяемость координат вершин можно обойти путем выделения координат вершин в отдельную структуру. В этом случае с гранями ассоциируются не координаты вершин, как в предыдущем случае, а индексы в массиве координат вершин. В нашем примере (см. рисунок ) будем иметь:

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

В такой модели грань представляется набором ребер и вершины грани определяются через ребра.

Таким образом, для каждого ребра мы задаем направление. Например, ребро e1 направлено ( имеет положительное направление) от точки v1 к точке v2. Грани также ориентированы, т.е. ребра заданы по часовой стрелке, если смотреть на куб снаружи.

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



Рисунок 8 "Крылатое" представление

Так как каждое ребро e присутствует точно в двух гранях, ровно два других ребра e1 и e2 появляются после e в этих гранях. Более точно, поскольку направление обхода грани задано, e появляется один раз в положительной ориентации, а другой раз – в отрицательной.
"Крылатое представление" использует это путем ассоциации с каждым ребром двух "следующих" ребер. Они обозначаются как ncw и nccw ("next clockwise" и "next counterclockwise" ). В данном случае ncw обозначает следующее ребро в той грани, где данное ребро появляется в положительном направлении, а nccw – следующее ребро в другой грани.
Таким образом, начиная с ребра, прямо связанного с гранью, мы может получить все другие инцидентные данной вершине ребра, следуя ссылкам ncw и nccw.
В наиболее общем случае в нашу структуру включают также ссылки на предыдущие ребра в соседних гранях. Имеем следующую структуру (см. рис):

struct edge{
pEdge ncw, pcw, pccw, nccw;
pFace fcw, fccw;
pVertex vstart, vend;
};

Здесь ncw, pcw – ссылки соответственно на следующее и предыдущее ребро в грани, в которую данное ребро входит в положительном направлении.
Аналогично nccw, pccw – следующее и предыдущее ребро в грани, соответствующей отрицательному направлению ребра.

Рассмотрим операции, наиболее характерные для граничного представления:

Рассмотрим, например, алгоритм определения правильности задания объекта.

Известно соотношение, связывающее количество вершин, ребер и граней в объекте – формула Эйлера.

В наиболее простом виде, применимом для связных объектов без сквозных отверстий, она записывается так:
V – E + F = 2,
где
V – количество вершин
E – количество ребер
F – количество граней.

Для произвольного объекта она выглядит так:

V-E+F-H=2*(C-G),
где
H – количество отверстий (несквозных).
C – количество компонент
G – количество сквозных отверстий.

Например, для объекта на рисунке имеем следующее тождество:

24-36+15-3=2(1-1)

Рисунок 9 Пример

Формула Эйлера является необходимым условием правильности задания сплошного (solid) объекта.