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

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

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

· топология, т.е. собственно структура, определяющая способ взаимосвязи элементов.

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

2 ) неявно:

где m – размерность пространства (1 – одномерное, 2 – двумерное, 3 – трехмерное);

n – размерность элемента (0 – нульмерный, определяет точку; 1 – одномерный, определяет линию; 2 – определяет поверхность);

- m-мерная вектор-функция, определяющая форму параметрического элемента;

- m-мерная вектор-функция, задающая пределы изменения параметров;

- m-мерная вектор-функция, определяющая неявное уравнение геометрического элемента;

- m-мерный нулевой вектор.

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

- точки, принадлежащей объекту;

- нормали к кривой или поверхности;

- осуществления мэппинга поверхности.

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

Таблица 1

 

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

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

Из таблицы видно, что 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, то это означает, что мы объединяем объект А с трансформацией объекта В и пересекаем его с объектом С. Преимущество данного способа представления заключается в том, что таким образом можно относительно легко моделировать достаточно сложные объекты.