Методы построения трехмерных моделей

Построение кривых и поверхностей

Способы построения кривой:

¾ интерполяция по точкам;

¾ деформация кривой (перемещение точки, изменение полинома);

¾ вычисление эквидистанты к заданной кривой;

¾ формирование кривой из отрезков и дуг;

¾ вычисление различных сечений;

¾ пересечение поверхностей.

Способы построения поверхности:

¾ интерполяция по точкам;

¾ деформация поверхности;

¾ перемещение образующей кривой по заданной траектории;

¾ вычисление эквидистантой поверхности на заданном расстоянии.

Эти способы построения часто используются для объектов сложной формы в автомобильной и авиационной промышленности, в судостроении (формы Эрмита, Безье, В-сплайны). В машиностроении же часто используются объекты, описание которых можно выполнить аналитически. Многие объекты можно представить плоскими гранями или аппроксимировать ими более сложные поверхности.

Задание гранями (кусочно-аналитическое описание)

Модель представляет собой пятиуровневую иерархическую структуру. Тело представляется множеством ограничивающих его граней: . Каждая грань задается множеством ограничивающих ее ребер: и нормалью , направленной из тела; каждое ребро — двумя точками: ; и каждая точка — тремя координатами: . Для реализации аналитических операций над гранями, для каждой грани задаются 4 коэффициента — A, B, C, D, однозначно определяющие уравнение плоскости.

Модель может быть реализована в виде графа:

Рис. 8.11

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

Координаты вершин — 24 слова.

Коэффициенты уравнений плоскостей граней — 24 слова.

Ссылки первого уровня — 6 слов.

Ссылки второго уровня — 24 слова.

Ссылки третьего уровня — 24 слова.

Ссылки пятого уровня — 24 слова.

Итого — 126 слов.

Кинематический принцип

Задание толщиной:

.

Контур С, помещенный в плоскости Р порождает тело S путем переноса по направлению D на расстояние L.

Рис. 8.12

Задание вращением

Тело получается путем вращения контура С вокруг оси А.

Рис. 8.13

Булевы операции

Модель представляет собой дерево, узлы которого — операции, листья — базовые элементы. Каждый базовый элемент имеет свою геометрию и топологию и представлен в виде геометрической модели (каркасной, поверхностной, объемной).

При вызове базового элемента для присоединения к объекту он должен в общем случае обладать следующими атрибутами:

где — координаты точки привязки ЛСК и ГСК; — углы поворота ЛСК относительно ГСК; — параметры элемента.

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

Чаще всего при конструировании объекта используются следующие операции над базовыми элементами:

¾ объединение;

¾ пересечение;

¾ разность.

В настоящее время существует два метода геометрического объединения:

1) метод контактного соединения;

2) метод соединения с проникновением.

Метод контактного соединенияприменяется при наличии у тел плоских поверхностей, по которым они могут быть соединены. Далее проводится анализ граничных контуров поверхностей, по которым соединяются тела. Существует много разных методик, но общими действиями обычно остаются:

¾ аналитическое описание граничных контуров двух тел;

¾ определение точек пересечения контуров и их сегментация;

¾ анализ вершин.

Метод контактного соединения прост в реализации. Затраты на программирование и время обработки программ невелики.

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

Обычно существует два пути:

1) когда поверхности заданы аналитически (но тогда есть ограничение — поверхности должны быть максимум второго порядка);

2) численное определение кривой пересечения.

Этапы метода соединения с проникновением.

Этап 1. Определение объемов V1 и V2 на основе математического представления поверхностей, образующих эти объемы.

Рис. 8.14

Этап 2. Определение пар потенциально пересекающихся поверхностей (F1 и F2).

Рис. 8.15

Этап 3. Аналитическое определение кривой пересечения для пары пересекающихся поверхностей и удаление тех сегментов кривой, которые не лежат внутри пересекающихся поверхностей.

Рис 8.16

Этап 4. Сегментация поверхности в соответствии с полученной кривой

.

Рис. 8.17

Этап 5. Удаление сегментов поверхностей.

Рассмотрев другую пару поверхностей, получим:

Рис. 8.18

5. Полигональные сетки

Рис. 8.19. еречное сечение криволинейного объекта и его полигональная аппроксимация

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

Для улучшения качества можно увеличить число многоугольников для аппроксимации, но это приведет к дополнительным затратам памяти и вычислительного времени.

Явное задание многоугольников

Каждый многоугольник можно задать в виде списка координат его вершин:

.

Вершины запоминаются в том порядке, в котором они встречаются при обходе вокруг многоугольника. При этом все последовательные вершины, а также первая и последняя соединяются ребрами. Для каждого отдельного многоугольника данный способ записи является эффективным, но для полигональной сетки дает большие потери памяти вследствие дублирования информации о координатах общих вершин (недостаток 1). Кроме того, нет явного описания общих ребер и вершин. Например, поиск всех многоугольников, имеющих общую вершину, требует сравнения троек координат одного многоугольника с тройками координат всех остальных многоугольников (недостаток 2). Наиболее эффективный способ выполнить такое сравнение — сортировка всех N троек координат: для этого потребуется в лучшем случае — сравнений. Но и при этом существует опасность, что одна и та же вершина вследствие ошибок округления может в разных многоугольниках иметь различные значения координат, поэтому правильное соответствие может быть никогда не найдено.

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

Задание многоугольников с помощью указателей на вершины

Каждый узел запоминается лишь один раз в списке вершин

.

Многоугольник определяется списком указателей на вершины. Например:

Рис. 8.20

,

.

Общие ребра рисуются дважды (недостаток).

Явное задание ребер

В этом представлении есть список вершин:

,

и список ребер, где каждое ребро указывает:

,

Рис. 8.21

на две вершины в списке вершин, определяющие это ребра, а также на один или два многоугольника, которым это ребро принадлежит. Если ребро принадлежит одному многоугольнику, то либо Р₁, либо Р₂ — пусто.

,

,

,

,

,

,

,

.

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

Октантные деревья

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

Модель строится из трехмерного массива элементов объема — вокселей (voxels). Все воксели имеют форму куба и одинаковый размер по трем координатным осям. Октантное дерево организует иерархическую структуру группировки вокселей. Весь объект хранится в боксе. Этот бокс делится на восемь подбоксов плоскостями, перпендикулярными осям координат. Эти подбоксы, в свою очередь снова делятся на подбоксы и т.д. (см. рис 8.22). Этот процесс заканчивается на уровне вокселей — элементарных неделимых единиц объема. При такой схеме кодирования воксельного пространства октантное дерево может представлять кубический объем пространства из (2^N)³ вокселей, где N — глубина дерева.

Каждый воксель внутри модели может быть либо прозрачным ("воздух"), либо принадлежать поверхности объекта ("кожа"). Воксели "воздуха" — это прозрачные области пространства, они не нужны для представления модели. Структура октантного дерева позволяет избегать хранения "воздушных" подбоксов на каждом уровне иерархии, в результате чего существенным образом уменьшается объем памяти, требуемый для хранения моделей.

Воксели "кожи" содержат информацию о свойствах поверхности в точке — цвет, внешняя нормаль, коэффициент отражения/преломления и т.д. для проведения необходимых вычислений во время построения изображения.

Такая модель данных не позволяет эффективно представлять трехмерные плотностные модели (3D density fields) в необработанном виде. Однако после предобработки (называемой также двоичной квантизацией [9]) визуализировать такие данные (компьютерная томография и магнитно-резонансное сканирование) не представляет большой сложности.

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

В сравнении с обычным однородным представлением трехмерного пространства, где каждый вексель содержит информацию, а для хранения всего пространства требуются гигантские объемы памяти, октантные деревья являются существенно менее требовательными. Например, для хранения объектов, состоящих из 256³ вокселей, требуется до 98 Мбайт: каждым вексель содержит 3 байта для хранения цвета поверхности + 3 байта для хранения нормали + 1/8 байта на тип вокселя ("воздух"—"кожа"), итого 6.125 байт/воксель. Прямое перемножение 256³ на 6.125 дает 98 Мбайт информации. Применение октантных деревьев позволяет сократить этот объем до 1-2.5 Мбайт.