Компьютерная графика - 7 Вариант

    Каждая  ветвь дерева состоит из кода и восьми указателей на восемь потомков, пронумерованных от 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 

    1.2.2 Бинарные деревья

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

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

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

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

    Объем памяти, требуемый для хранения деревьев, пропорционален площади поверхности  объекта. 

    2 Пространственная геометрия (CSG)

    В пространственной геометрии объект задается набором примитивов и операций над ними.

     
 
 
Рисунок 5 Дерево пространственной геометрии 

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

    3 Boundary representation (B-rep) (граничное, поверхностное представление)

     
В отличие от ранее описанных  моделей, поверхностное представление  определяет сплошное тело неявно путем  описание ограничивающей его поверхности.

     
 
 
Рисунок 6 Основные составляющие граничной  модели

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

    3.1 Явное представление.

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

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

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

    3.2 Список вершин

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

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

    3.3 Список ребер

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

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

    3.4 Winged-Edge Representation ("крылатое" представление)

    Эта модель является развитием модели, основанной на информации о ребрах. 
Отличие состоит в том, что в структуру, описывающую ребра, добавляется информация о взаимном расположении граней. 
 
 
 
Рисунок 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 – следующее и предыдущее ребро в грани, соответствующей отрицательному направлению ребра. 

    3.5 Операции над граничными представлениями.

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

• проверка правильности задания
• вычисление габаритного объема
• вычисление нормали в точке
• вычисление кривизны поверхности
• нахождение точки пересечения с лучом или кривой
• определение положения точки относительно поверхности

Описание  разработки тренажера со скриншотами, пояснениями, текстами программ и контрольными примерами