Учебное пособие Воронеж 2005 А. С. Кольцов Е. Д. Федорков Геометрическое моделирование в сапр

Система координат, применяемая в методе обратной трассировки лучей

Сцена - совокупность изображаемых объектов, включая при необходимости поверхность основания.
Система координат сцены - правая прямоугольная система координат, общая для всей сцены X_c Y_c Z_c.
Объект - совокупность точек пространства, объединенных функциональной общностью с точки зрения конкретно-целевой задачи.
Соответственно для каждого объекта вводится своя правая прямоугольная система координат XYZ.
Экранная система координат - система координат X₁Y₁Z наблюдательной системы. Данная система координат выбирается левой.

По аналогии c физическими устройствами ось z соответствует главному лучу объектива, плоскость xy - задней фокальной плоскости, а центр проекции F располагается на оси OZ в точке (0,0,f) и сопоставляют с задней главной точкой объектива.


6.4. СПОСОБЫ ПРЕДСТАВЛЕНИЯ МОДЕЛЕЙ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ

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

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

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

2) неявно:

где m – размерность пространства (1 – одномерное, 2 – двумерное, 3 – трехмерное);
n – размерность элемента (0 – нульмерный, определяет точку; 1 – одномерный, определяет линию; 2 – определяет поверхность);
- m-мерная вектор-функция, определяющая форму параметрического элемента;
- m-мерная вектор-функция, задающая пределы изменения параметров;
- m-мерная вектор-функция, определяющая неявное уравнение геометрического элемента;
- m-мерный нулевой вектор.
Как видно, неявное задание геометрического объекта более компактное. Тем не менее параметрическому заданию отдается предпочтение в силу его удобства для решения задач нахождения:
- точки, принадлежащей объекту;
- нормали к кривой или поверхности;
- осуществления мэппинга поверхности.
В зависимости от значений m и n сведем геометрические объекты для параметрического их представления в следующую таблицу.
Таблица 1

Классификация элементов геометрических объектов

m\n	0	1	2
1	точка прямой	отрезок прямой	-
2	точка плоскости	линия на плоскости	область на плоскости
3	точка в пространстве	пространственная линия	область в пространстве

Из таблицы видно, что m <= n. Будем ссылаться на данные элементы обозначением (m\n)-элемент. Например, (2\1) – это линия на плоскости.
Имея данные структурные элементы, можем конструировать из них различную топологию, выражающую отношения между структурными элементами, например, с помощью таблиц или с использованием теории множеств. Так ломаную можно представить двумя множествами:
V – множество вершин ((2\0)-элементов);
Е = {vi, vj}– множество ребер.
Рассмотрим распространенную классификацию существующих способов представления трехмерных геометрических объектов (моделей):
- простейшие способы;
- граничное задание;
- объемное задание.
К простейшим способам задания трехмерных объектов относятся точечное и проволочное (каркасное) представления. В точечном представлении объект задан совокупностью вершин, принадлежащих поверхности объекта V = {V1,…,Vn}.
Проволочная модель является расширением предыдущего способа. Объекты задаются совокупностью вершин и соединяющих их ребер (отрезков прямой или кривой):
V = {v₁,…,v_n}, Е = {v_i, v_j [f_k(u)]},
где f_k(u) – это (3\1)-элемент, используемый, если ребро не является отрезком прямой, соединяющей вершины v_i, v_j. Как правило, для одной модели f_k является вектор-функцией одного и того же типа.
Основное преимущество этих способов - простота представления. Потому они применяются на промежуточных стадиях работы с геометрическим объектом: предварительная визуализация и как исходные модели для синтеза более сложных моделей.
Поверхностное (граничное) задание моделей. Поверхностное представление объекта подразумевает точное математическое описание. Исходя из вышеприведенной классификации существует два основных способа описания поверхности: явное параметрическое и в виде неявных функций. Общий вид параметрической поверхности следующий:
,
где для параметров u и v, как правило, определяют область определения либо прямоугольного (u_a < u < u_b, v_a < v < v_b), либо треугольного (u_a < u < u_b, v_a < u + v < v_b) вида.
Можно выделить два основных типа поверхностных параметрических моделей:
- полигональная модель, которая представлена набором плоских граней;
- патч-модель, или лоскутная модель. В данном случае гранями служат части поверхностей одного типа (билинейные, поверхности Кунса, бикубические поверхности, поверхности Безье, поверхности на основе B-сплайнов).
Поверхностное задание трехмерных объектов является наиболее распространенным, и для него сформировались следующие разновидности топологий:

1. 
   Список вершин. В этой топологии грань выражается через вершины:
   

V = {v_i } – вершины |V| = n;
F = {(v_j1, v_j2,…, v_jk [, f_j(u,v)]) } – грань (или патч f_j), состоящая из k вершин (k >= 3).

2. 
   Список ребер. Здесь грань выражена через ребра:
   

V = {v_i } – вершины |V| = n;
Е = {e_k = (v_i, v_j [f_k(u)])} – ребро. f_k – уравнение линии;
F = {(e_j1, e_j2,…,e_jk [f_j(u,v)])} – грань (или патч f_j), состоящая из k ребер (k >= 3).

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

V = {v_i } – вершины |V| = n;
E = { e_k = (v_start, v_end, n_cw, n_ccw, [f_k(u)])} – ребро, где v_start – начало ребра, v_end – конец ребра, n_cw – следующее (предыдущее) ребро в той грани, где e_k встречается в положительном направлении обхода вершин, n_ccw – следующее (предыдущее) ребро в другой грани (где e_k встречается в отрицательном направлении);
F = { (first_edge, sign [f_j(u,v)]) } – грань (или патч f_j), где first_edge – первое ребро в цепочке представления грани, sign – знак (+/-), определяющий, в каком направлении встречается ребро first_edge в данной грани.
«Крылатое» представление является наиболее удобным для реализации важнейших алгоритмов над геометрическими объектами:
- проверка правильности задания;
- алгоритмы для полигональных моделей, связанные с обходом ребер (выделение плоских контуров, упрощение модели путем удаления граней и другие).
Кроме того, не более чем за линейное время можно восстановить любую другую топологию, следуя по цепочкам связей между элементами.
В объемном представлении базовыми являются (3\2)-элементы или неявно представленные примитивы. Наиболее известны:
- воксели;
- метаболы;
- сплошные конструктивы.
Основой воксельного представления служит так называемый воксель (или ячейка), представляющий собой кубическую область пространства. Трехмерный объект определяется как массив вокселей. Можно выделить следующие топологии воксельного объекта:

1. 
   простейшая – набор одинаковых вокселей, аппроксимирующий область пространства, занимаемую объектом;
   
2. 
   V = { ({L} x {M} x {N}, {1,0}) } – элементу трехмерного массива вокселей размером L x M x N ставится в соответствие его заполненность (принадлежность объекту);
   
3. 
   октальное дерево – рекурсивное разбиение пространства на 8 частей. При этом устанавливается некоторый минимальный размер вокселя. Лист дерева помечается заполненным, если он полностью принадлежит объекту. Таким образом, топология представлена в виде дерева;
   
4. 
   PM-октальные деревья – это гибрид октального дерева и полигональной модели для уменьшения погрешности аппроксимации при достижении минимального размера вокселя в рекурсивном разбиении пространства.
   

Воксельное представление является очень удобным для реализации пространственных алгоритмов и теоретико-множественных операций над объектами (объединение, вычитание, пересечение), но обладает рядом недостатков, которые ограничивают область его применения:
- низкая точность для представления для большинства
объектов;
- большой объем занимаемой памяти.
Метаболы – это шары различного радиуса (r), которые могут взаимодействовать в зависимости от близости и радиуса взаимодействия (R): Сфера = (координаты, радиус, вещество). Взаимодействие выражается через появление дополнительной «материи» между ними (см. рис. 5). Топология, как таковая, здесь отсутствует.

Рис. 5. Взаимодействие двух метаболов
При представлении объекта в виде сплошных конструктивов используют два набора:
- базовый набор примитивов (параллелепипед, сфера, конус, цилиндр, тор, призма, пирамида и т.п.), являющихся структурными элементами объекта;
- базовый набор теоретико-множественных операций: унарного аффинного преобразования (T) и бинарных операций вычитания (-), пересечения (*), объединения (+). Данный набор определяет топологию модели, которая реализуется в виде формулы теории множеств.
Например, если мы имеем три примитива A, B, C и формулу (A + T(B)) * C, то это означает, что мы объединяем объект А с трансформацией объекта В и пересекаем его с объектом С. Преимущество данного способа представления заключается в том, что таким образом можно относительно легко моделировать достаточно сложные объекты.