СОДЕРЖАНИЕОбщая характеристика Актуальность темы. Бесспорно,
геометрическое моделирование является одним из наиболее важных областей
человеческой деятельности, поскольку оно часто используется при
проектировании. Например, при проектировании архитектурных строений,
механических узлов, нового дизайна изделий бытового назначения и
других предметов. Основой точного геометрического моделирования
является прикладная геометрия. Однако в силу возрастающей мощности
компьютерных систем эта область пополнилась новыми технологиями,
такими как твердотельное моделирование, В-сплайны, лофтинг, скиннинг
и др. Они успешно применяются на практике. Однако не смотря на большие
успехи в этом направлении, вопросы синтеза моделей геометрических
объектов все еще остаются актулаьными. Основные из них это: Цели и задачи исследования. Целью магистерской работы является исследование способов представления моделей геометрических объектов и алгоритмов их синтеза. Научная новизна состоит в разработке метода построения моделей геометрических объектов по произвольному параметрическому описанию образующих их частей (кривых или поверхностей). Практическая ценность состоит в разработке библиотеки функций, обслуживающих основные этапы построения моделей геометрических объектов по их произвольному параметрическому описанию. Реализация результатов работы.
Результат работы составляет библиотека функций, построенной по COM
технологии. Библиотека включает: 1 Способы представления моделей геометрических объектов В общем случае в любой геометрической модели можно выделить две составляющие ее части (уровни):
Структурный элемент как геометрический объект, вообще говоря, можно
представить одним из способов:
2) неявно
где
Как видно неявное задание геометрического объекта более компактное.
Тем не менее, параметрическому заданию отдается предпочтение в силу
его удобства для решения задач нахождения: Таблица 1 Классификация элементов геометрических объектов
Из таблицы видно, что m <= n. Будем ссылаться на данные элементы
обозначением (m\n)-элемент. Например, (2\1) – это линия на плоскости. Рассмотрим распространенную классификацию существующих способов
представления трехмерных геометрических объектов (моделей) [1]: К простейшим способы задания трехмерных объектов относятся точечное
и проволочное (каркасное) представления. Поверхностное (граничное) задание моделей. Поверхностное представление объекта подразумевает точное математическое описание. Исходя из вышеприведенной классификации существует два основных способа описания поверхности: явное параметрическое и виде неявных функций. Общий вид параметрической поверхности следующий:
где, для параметров u и v, как правило, определяют область определения либо прямоугольного (ua < u < ub, va < v < vb) либо треугольного (ua < u < ub, va < u + v < vb) вида. Можно выделить два основных типа поверхностных параметрических
моделей: Поверхностное задание трехмерных объектов является наиболее распространенным и для него сформировались следующие разновидности топологий:
"Крылатое" представление является наиболее удобным для
реализации важнейших алгоритмов над геометрическими объектами: Кроме того, не более, чем за линейное время можно восстановить любую другую топологию, следуя по цепочкам связей между элементами. В объемном представлении базовыми являются (3\2)-элементы или неявно
представленные примитивы. Наиболее известны:
Воксельное представление является очень удобным для реализации
пространственных алгоритмов и теоретико-множественных операций над
объектами (объединение, вычитание, пересечение), но обладает рядом
недостатков, которые ограничивают область его применения: Метаболы [2] – это шары различного радиуса (r), которые могут взаимодействовать в зависимости от близости и радиуса взаимодействия (R): Сфера = (координаты, радиус, вещество). Взаимодействие выражается через появление дополнительной «материи» между ними (см. рис 1.1). Топология как таковая здесь отсутствует.
Рисунок 1.1 Взаимодействие двух метаболов При представлении объекта в виде сплошных конструктивов используют
два набора: Например, если мы имеем три примитива A, B, C и формулу (A + T(B)) * C, то это означает, что мы объединяем объект А с трансформацией объекта В и пересекаем его с объектом С. Преимущество данного способа представления заключается в том, что таким образом можно относительно легко моделировать достаточно сложные объекты. 2 Синтез моделей геометрических объектов Под синтезом модели геометрического объекта будем понимать преобразование модели одного и того же геометрического объекта в другую модель.
Рисунок 2.1 Синтез как процесс преобразования одной модели в другую В настоящее время методы синтеза достигли такого многообразия благодаря современным мощным системам геометрического моделирования (3DStudioMAX, Autodesk AutoCAD, Autodesk Inventor, Rhino, Lightwave, Maya, “СПРУТ”, комплекс программ фирмы IDEA и др.), что выполнить обобщенную классификацию достаточно сложно. Поэтому составим ее по отдельным признакам. Исходя из принятого выше разделения модели на два уровня можно выполнить поуровневую классификацию методов синтеза:
В отдельный и наиболее широкий класс выделяют процедурные методы
синтеза. Они составляются из комбинации предварительно определенных
кривых, поверхностей, функциональных компонент и процедур, которые
соотносят их для получения новой кривой или поверхности. Сюда относятся: Эти методы являются математически точными и универсальными. А кинематические методы используются для формирования базовых элементов твердотельного моделирования (AutoCAD). Одним из мощных средств синтеза являются пространственные искажения (3D Studio MAX [2]), которые могут быть выражены как: p’ = M(p)*p где 3 Параметрическое заданние геометрических объектов Как упоминалось ранее, параметрическое задание подразумевает функциональную зависимость координат точек объекта от некоторых параметров. Для линий используются функция одной переменной: p = F(u) = (Fx(u), Fy(u), Fz(u)), а для поверхности – функция двух переменных: p = F(u, v) = (Fx(u, v), Fy(u, v), Fz(u, v)). Вообще говоря, вид функции F может произвольным. Но на практике ограничивают набор функций, которые представляют наиболее часто встречающиеся геометрические объекты, из которых затем составляют более сложные. К ним относятся [3]: 1) плоские линии: прямые, окружности, эллипсы, и их отрезки, спирали
Архимеда, эквидистанты; Как видно их перечень невелик. А потому для моделирования кривых и поверхностей, которые не вписываются в этот набор, используется сплайны и патчи. Наиболее употребляемые виды сплайнов: сплайны Безье, B-сплайны (NURBS). Среди патчей можно выделить: патчи NURBS, Безье-патчи, N-патчи, билинейные патчи, патчи Кунса. Тем не менее, большинство пакетов использует эти инструменты для аппроксимации вышеперечисленных кривых и поверхностей и не имеют автоматических средств для аппроксимации пользовательский кривых (параболы, гиперболы, синусоиды) и поверхностей (параболоиды, конусы с образующей заданного вида и др.) с помощью перечисленных сплайнов и патчей. Данная работа как раз и посвящается изучению и разрешению данной проблемы. Сформулируем основные задачи, которые должны быть при этом решены: 1) гибкость и универсальность определения пользовательских функций
(расширяет область применения); В последующих разделах будут описаны пути решения поставленных задач. 4 Библиотека произвольных символьных функций Для построения любой сложной системы необходимы: Для построения пользовательских функций будем использовать математический аппарат. В качестве базовых элементов будут выступать элементарные функции: синус, косинус, тангенс, функций возведения в степень, экспонента и др. По аналогии с языками программирования в качестве построения новых функций целесообразно использовать привычные для человека арифметические выражения, включающие:
Теперь определим тело произвольной функции, используюя формализм Бекуса-Нура: <имя> ::= <буква> {<буква> | <цифра>} Определим также общепринятый приоритет операций по убыванию: Таблица 4.1
Для обеспечения преемственности объявлений функций введем понятие библиотеки функций: <библиотека функций> = {(<имя функции>, <тело функции>)} Определим для нее следующие операции, которые можно выразить тривиальными
операциями над множествами: Таким образом мы обеспечили решение первой поставленной задачи. 4.1 Синтаксический разбор и оптимизация Приведенный выше синтаксис описания функции позволяет строить структуры вычисления реализующий их арифметических выражений. Другими словами для данного описания требуется механизм синтаксического разбора. При этом известны два вида структур:
Рисунок 4.1 Дерево, представляющее арифметическое выражение Первая структура удобна для реализации чистых арифметических выражений. Дерево – это более сложная структура, но она универсальнее по представимости выражений, удобна для проведения их оптимизации и проведению символьных вычислений. Поэтому целесообразно применять комбинацию этих структур, и определим ее следующим образом:
При этом следует отметить, что элемент <ПОЛИЗ> - это польская инверсная запись бесскобочного арифметического выражения. Арифметическое выражение в скобках соответствует узлу, содержащему элемент <ПОЛИЗ>. Теперь обратим внимание на один важный факт. Поскольку в определение тела функции входят константы, то может оказаться, что функция содержит ветви, все операнды которых прямо или косвенно зависят от констант и могут быть предрасчитаны заранее. Например, для выражения x + 5 * (3 + sqrt(4)) возможно следующее упрощение (sqrt – функция вычисления квадратного корня): x + 25. Поэтому имеет смысл после построения дерева проводить проверку на выявления и замену таких ветвей с целью оптимизации. 4.2 Вычисление функции и компиляция Имея структуру, представляющую тело функции можно вычислять ее значение по заданным значениям аргументов. Рекурсивный алгоритм 4.1 вычисления следует из определений (4.1), ( 4.2). Причем: <корневой узел>::= <имя функции>({<ПОЛИЗ>} {,<ПОЛИЗ>}) Алгоритм 4.1. ВЫЧИСЛИТЬ_УЗЕЛ (<узел>) = Данный алгоритм реализует интерпретатор. Однако интерпретатор выполняет множество лишних манипуляций данными (копирование во вспомогательные переменные, дополнительные проверки условий), которых можно избежать при вычислении конкретной функции. Этого можно добиться путем генерации (компиляции) ее исполнимого кода. Компиляция решает вторую из поставленных задачу – высокая скорость вычислений. Компиляции состоит в формировании кода их базовых наборов команд:
5 Аппроксимация произвольных функций с помощью B-сплайнов Как упоминалось ранее для параметрического описания геометрических объектов в пространстве используются функции одной (линии) и двух (поверхности) переменных. В виду некоторых принципиальных отличий их аппроксимации рассмотрим каждый из этих видов функций по отдельности. Выбор B-сплайнов (NURBS) в качестве аппроксимирующих функций обусловлен следующими причинами:
5.1 Кривые и поверхности NURBS Начнем с рассмотрения NURBS-кривых, поскольку это дает базовое понимание В-сплайнов, а затем обобщим их на поверхности. В общем случае В-сплайн состоит из нескольких сплайновых сегментов, каждый из которых определен как набор управляющих точек. Поэтому коэффициенты многочлена будут зависеть только от управляющих точек на рассматриваемом сегменте кривой. Этот эффект называется локальным управлением, поскольку перемещение управляющей точки будет влиять не на все сегменты кривой. Рисунок 5.1 показывает, как управляющие точки влияют на форму кривой.
Рисунок 5.1 В-сплайн с управляющей точкой Р4 в нескольких положениях. Рассмотрим различные виды В-сплайнов [4]. В-сплайн интерполирует набор из р+1 управляющей точки: Для каждого i >= n существует узел между Теперь предположим, что координаты (x, y, z) точки кривой представлены в виде рациональной дроби. В этом случае говорят, что В-сплайн рациональный, иначе – нерациональный
Подводя итог, можно указать на существование 4 типов В-сплайнов: Последний тип и представляет собой NURBS как наиболее общий случай В-сплайнов. Теперь рассмотрим математическое описание NURBS. NURBS кривая и поверхность соответственно выражаются следующими двумя параметрическими уравнениями:
где, Pi - управляющая точка, wi - ассоциированный с ней вес и
Из формул видно, что точка кривой (поверхности) является средневзвешенных управляющих точек, причем удельный вес каждой точки зависит от одного (двух – для поверхности) параметра. Как видно NURBS имеют явные преимущества по сравнению со всеми описанными выше сплайнами. Следует также обратить внимание, что сплайны Безье – это NURBS, у которого веса всех управляющих точек равны 1 и который состоит из 1-го сплайнового сегмента. Таким образом, NURBS имеет все преимущества Безье-сплайнов, а также
следующие: Единственный недостаток – это несколько более сложное математическое описание NURBS по сравнению с Безье сплайнами, однако порядок этого усложнения не высок. Итак, NURBS предоставляет точность, гибкость и совместимость с другими системами. 5.2 Аппроксимация функции одной переменной В общем виде аппроксимацию функции F(t) можно представить следующим образом:
где Для простоты будем полагать, что параметр t лежит в пределах от
0 до 1. Для NURB сплайнов ситуация усложняется тем, что они имеют множество неизвестных величин, которые можно менять в широких пределах. К ним относятся: 1) количество управляющих точек p + 1 (p – порядок); Однако первые три величины связаны соотношением:
Из (5.1) видно, что управляющие точки Pi являются определяющими, поскольку только с помощью этих значений независимо от весовых коэффициентов можно получить любое значение функции Q(t). Кроме того, использование весов создает иррациональность при составлении системы алгебраических уравнений, а также создает зависимость систем уравнений для отдельных координат управляющих точек плоских и пространственных кривых NURBS (для всех координат веса одинаковые). Эти проблемы легко устраняются, если задать значения весов равными 1. Тогда NURBS-приближение для функции одной переменной примет вид:
аналогичный (5.4). В целях определенности в качестве ограничений будем использовать ограничения на значения функции при заданных, а не ее производные, параметрах со следующими оговорками для замкнутых кривых (F(0) = F(1)): 1) Q'(0) = Q'(1), если F'(0) = F'(1) Первое условие необходимо для сохранения непрерывности соединения кривой, а второе только для обеспечения недостающего (n+1)-го ограничения. Ограничения на значения функции примут вид:
Выбор и распределение ti должно определяться поведение функции. Очевидно, что для уменьшения числа ti необходимо их расставить прежде всего в точках резкого изменения функции F (экстремумах и точках перегибов), т.е. для исходного набора ti имеем: K = {ti} = {t: F'(t) = 0 v F''(t) = 0} Задачи нахождения экстремумов и точек перегиба можно решить следующими способами: 1) использование соответствующих численных методов непосредственно (методы дихотомии, "золотого" сечения, наискорейшего спуска и т.д.); 2) поэтапное вычисление:
Второй способ является более приемлемым, поскольку:
Пусть f(x), g(x) – функции с известными экстремумами; Тогда:
Еще один момент, на который следует обратить внимание – это область определения функции f (D(f)). D(f) необходимо учитывать в целях надежности и контроля ошибок, которые может допустить пользователь при составлении новых функций и использовании их для построения геометрических объектов. В этом случае для аргумента функции f должно выполняться: [0,1] Є D(f). Нахождение D(f) может производится при составлении функции, исходя из следующих очевидных утверждений:
Узлы knoti NURB сплайнов играют роль точек соединения его сегментов и как видно из (5.3) влияют на точность вычисления значений функций между узлами: чем больше knot[[i+1]]-knot[[i]], тем точнее результат вычисления на интервале [ knot[[i]], knot[[i+1]] ]. Поэтому узлы можно распределить пропорционально расстоянию между точками (ti, f(ti)) и (t[[i+1]], f(t[[i+1]])) графика функции f. Поскольку возможен случай линейности функции f, то целесообразно начинать процесс аппроксимации с NURB сплайна первой степени (n = 1). Отсюда количество управляющих точек p+1 можно найти из (5.5): p + 1 = n + q = n + |K| Т.о. мы определили все неизвестные величины NURB. Далее, имея некоторую допустимую погрешность error, для которой должно выполняться условие аппроксимации |f(t) – Q(t)| < error, можно найти неизвестные Pi и степень n для функции Q(t) по алгоритму 2: Алгоритма 4.2.
На шаге 3 алгоритма можно применить один из методов поиска максимума
функций. 5.3 Аппроксимация функции двух переменных По аналогии рассмотренной задачи аппроксимации в предыдущем пункте сформулируем и рассмотрим пути ее решения для двумерного случая (F(u,v)). NURB сплайн будет иметь вид:
Неизвестные величины: Область определения для функции нескольких переменных можно находить аналогично с той разницей, что она должна определятся для каждой переменной в отдельности. Что касается нахождения экстремумов для определения узлов knotij, то в общем случае эта задача может не иметь единственного решения, поскольку количество экстремумов может оказаться бесконечно большим (в случае линий экстремумов). Поэтому нужно определить критерий оптимальности выбора количества и расположения точек графика функции, соответствующих узлам knotij. Простейшим критерием количества может быть выбор узлов только в точках, которые являются единственными в сколь угодно малой их окрестности (на рис. 5.2 это точки 1 и 2).
Рисунок 5.2 Точки и линии экстремумов функции При аппроксимации по алгоритму, приведенном в предыдущем пункте
на шаге 3 потребуется использовать алгоритм поиска максимума функции
двух переменных. С увеличением узлов трудоемкость алгоритма будет
нелинейно возрастать, поскольку узлы появляются по обоим параметрам. 6 Синтез твердотельных моделей Данный раздел не вносит никакой научной новизны в принципы построения гранично заданных твердотельных моделей, однако он необходим для выявления особенностей элементов, составляющих эти модели, поскольку элементы синтезируются как аппроксимации произвольно заданных символьных функций. Вначале рассмотрим составляющие элементы и структуру твердотельной модели, затем перейдем собственно к синтезу моделей по различным наиболее распространенным их процедурным описаниям. 6.1 Структура твердотельной модели Выбор структуры, или топологии, твердотельной модели определяется способом дальнейшего использования синтезируемой модели. Для внешнего использования (при экспорте в таких форматах обмена данными, как dxf, iges, step и т.д.) топология определяется форматом файла, но как правило это одна из реберных поверхностных модели. Для внутреннего использования (приложениями, использующими данную библиотеку) наиболее удобна топология "крылатого" представления (winged-edge representation). Как упоминалось в разделе 1 структурными элементами гранично заданные модели являются вершины v, ребра e и грани f. Поскольку для представления поверхности мы будем использовать NURBS поверхности, то, как показывает практика [5] целесообразно использовать обрезанные патчи как показано на рисунке 6.1.
Рисунок 6.1 Усеченный патч Усекаемая часть патча задается цепочкой плоских кривых (c0-c7), заданный в его области определения (по параметрам s, t). Эти цепочки образуют циклы, направление обхода (по или против часовой стрелки) которых определяет какая часть патча остается, а какая отсекается. В некоторых системах [5] указанные плоские кривые хранятся в двух видах: как алгебраическая и как параметрическая сплайновая кривая. Алгебраическая кривая определяет точное ее уравнение (прямая, дуга), а параметрическая – определяет аппроксимацию этой кривой для единообразия при выполнении операций с моделью. В данной работе аналогом алгебраической кривой является произвольная символьная функция библиотеки. Поэтому двойственность представления будет иметь смысл только для внутреннего использования. Во многих системах кривые являются линиями пересечения патчей, а вершины – точками пересечения кривых. Так, например, на рисунке 6.2 изображена твердотельная модель цилиндра. Патчи боковой его грани являются полными (без усечения), а верхняя и нижняя грани усеченны цепочками c8-c7-c6-c5 и c1-c2-c3-c4 соответственно.
Рисунок 6.2 Граничное представление твердотельной модели цилиндра В таблицах 4.1 и 4.2 для данной модели цилиндра приведены вершинное и "крылатое" представления. Таблица 6.1. Тверотельная модель цилиндра в вершинном представлении
Таблица 6.2. Твердотельная модель цилиндра в "крылатом" представлении
6.2 Синтез твердого тела по процедурному описанию В современных системах геометрического моделирования сформировались следующие способы синтеза твердотельных моделей:
В данной работе имеет смысл использовать только последний способ. Наиболее распространенными процедурными методами синтеза являются:
Рассмотрим принципы синтез твердотельных моделей на примере двух первых, наиболее простых методах. В каждом случае на кривые, участвующие в синтезе, налагаются определенные ограничения во избежание получения топологически некорректных многосложных моделей. Тело выдавливания, как видно из рисунка 6.3, образуется из двух усеченных плоских патчей (f1 и f2) и неусеченных патчей, составляющих боковую поверхность тела. Отсюда очевидны два необходимых условия:
Рисунок 6.3 Тело выдавливания Тело вращения можно построить двумя способами: путем полного обращения образующей вокруг оси (рисунок 6.4а) и неполного обращения (рисунок 6.4б). В первом случае боковая поверхность может быть представлена с помощью одного полного (неусеченного) патча и двух (верхний и нижний) усеченных патчей. Во втором случае добавляется еще два усеченных патча f3 и f4.
Рисунок 6.4 Тела вращения: а – полный оборот, б – неполный оборот Поскольку при построении будут получены конические кривые (с1) и поверхности (f2), то в целях точности целесообразно их построения осуществлять по специальным алгоритмам с использованием весов NURBS [6]. Для соблюдения правильности топологии должны выполняться следующие
условия: Пример использования произвольной параметрической поверхности для построения твердотельной модели проиллюстрирован на рисунке 6.5.
Рисунок 6.5 Твердое тело как параллелепипед, ограниченный параметрической поверхностью Здесь твердотельная модель состоит из:
В данной работе пранализированы и классифицированы используемые в настоящее время модели геометрических моделей. Классификация методов синтеза была проведена очень поверхностно, поскольку число существующих систем, которые используют свои собственные методы достаточно много, и они требуют отдельного изучения. Подробно рассмотрены принципы реализации наращиваемой библиотеки символьных функций и ее использование для аппроксимации функции одной переменной. Проблема аппроксимация функции двух переменных была рассмотрена неподробно и требует дополнительных исследований. Освещены принципы синтеза твердотельных моделей объектов по их процедурным описаниям с помощью кривых. Определены основные условия возможности построения таких моделей. СПИСОК ЛИТЕРАТУРЫ
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
- m-мерная вектор-функция,
определяющая форму параметрического элемента;
- m-мерная вектор-функция,
задающая пределы изменения параметров ui;
- m-мерная вектор-функция,
определяющая неявное уравнение геометрического элемента;
- m-мерный нулевой вектор.
,
и состоит из р-(n-1) сегментов кривой: 
.
Кроме того, мы можем определить общий параметр t, нежели отдельный
для каждого сегмента в интервале от 0 до 1. Таким образом, для каждого
сегмента кривой 
t будет
принадлежать интервалу 
.
Более того, на каждый сегмент 
до 
.
для значения ti параметра
t. Для В-сплайна существует p-n-2 узлов. Отсюда исходит понятие
однородности: если узлы равномерно распределены на интервале от
0 до 1, т.е. 
, то говорят,
что В-сплайн равномерный. В противном случае – неравномерный. Стоит
также обратить внимание на факт, что эти определения касаются узлов,
возрастающих по значению, т.е. 
.
- базовая функция, определенная рекурсивно следующим образом:
