Первые две главы книги [8] являются хорошим дополнением к материалу настоящей лекции. Полезно ознакомиться также с главой 4 монографии [2].

Лекция 2. Геометрическое моделирование

Автоматизация черчения и геометрическое моделирование

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

Однако создание чертежей вручную - чрезвычайно дорогостоящая процедура, доступная только подготовленным специалистам и требующая использования специальной чертежной доски с линейкой - кульмана, а также разных вспомогательных средств (например, лекал для рисования кривых). Неудивительно, что первые системы автоматизации в этой области были предназначены именно для упрощения и ускорения создания чертежей (подобно другой эпохальной концепции автоматизации с помощью компьютера - текстовым процессорам, предназначенным для упрощения создания текстовых документов и легкого внесения изменений в них). Системы класса computer-aided drafting существуют и поныне, самый известных их представитель - AutoCAD. Типичная функциональность таких систем включает в себя средства, необходимые для создания и редактирования чертежей, а процесс работы концептуально не отличается от работы в графическом редакторе. (Основными понятиями графических моделей таких систем являются графические примитивы с атрибутами, отображаемые уровни, а также различные способы конструирования.) В нашем курсе мы не будем рассматривать системы этого класса, так как в настоящее время они стремительно уступают свои позиции системам трехмерного моделирования (даже Autodesk делает основную ставку не на AutoCAD, а на Inventor Series).

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

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

Виды геометрического моделирования

Хронологически различают следующие подходы к геометрическому моделированию:

- каркасное моделирование;

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

- твердотельное моделирование;

- немногообразное моделирование.

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

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

Рис. 2

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

Немногообразное (non-manifold) моделирование снимает ограничения, присущие классическому твердотельному моделированию - с его помощью можно описывать геометрические модели, которые локально могут быть не только многообразиями размерности три (объемными телами), но и размерности два (поверхностями), один (кривыми), нуль (точками), а также участками сопряжения многообразий разной размерности.

Функции твердотельного моделирования

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

- функции создания примитивов,

- перенос и поворот тела,

- булевы операции,

- функции заметания и скиннинга,

- конструктивные элементы,

- расчет объемных параметров тела (объема, массы, моментов инерции).

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

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

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

Рис. 3

Функции заметания создают объемное тело поступательным или вращательным движением замкнутого двумерного контура в трехмерном пространстве. Функция скиннинга «натягивает» трехмерное тело на его плоские срезы, заданные в виде замкнутых двумерных контуров.

Типичные конструктивные элементы включают в себя скругление, поднятие, проделывание отверстия. При создании конструктивного элемента задаются его размеры.

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

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

Декомпозиционные модели

Декомпозиционные модели являются простейшим подходом к твердотельному моделированию, представляя трехмерное тело композицией некоторых простых элементов. Различают следующие декомпозиционные модели:

- воксельное (voxel) представление;

- октантное дерево;

- ячеечное представление.

Воксельное представление - полный трехмерный аналог растрового одноцветного изображения. Тело представляется трехмерным булевым массивом, каждый элемент которого является пространственным кубиком одинакового размера со своими уникальными координатами. Такой кубик называется вокселом (voxel - от VOlume piXEL). Вокселы равномерно покрывают всю область (прямоугольный параллелепипед), в которой содержится моделируемое тело. Соответственно, те вокселы, которые имеют непустое пересечение с моделируемым телом, представляются в массиве значением ИСТИНА, прочие - значение ЛОЖЬ. Отметим удобство воксельного представления для реализации на его основе булевых операций твердотельного моделирования. Для этого необходимо построить согласованные воксельные представления двух тел и применить соответствующую операцию к булевым значениям ячеек массива. Отметим, что сложность такого алгоритма будет прямо зависеть от числа вокселов. На воксельном представлении несложно вычислять объемные параметры тела - достаточно лишь вычислить их аналитически для каждого воксела и просуммировать.

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

- полностью (с заданной точностью) принадлежащим описываемому телу;

- полностью непринадлежащим описываемому телу;

- частично пересекающимся с описываемым телом.

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

Рис. 4

Ячеечное представление соответствует разбиению моделируемого тела на произвольные непересекающиеся выпуклые многогранники, полностью (в соответствии с заданной погрешностью) заполняющие его объем.

Конструктивные модели

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

Рис. 5

CSG (constructive solid geometry)- модели реализуют конструктивный подход в терминах булевых операций над параметрическими твердотельными примитивами (прямоугольный параллелепипед, цилиндр и пр.). CSG-модели обычно представляются в виде дерева, у которого все листья являются примитивами с указанными размерами, а каждая нетерминальная вершина является либо аффинной трансформацией (переносом или вращением), либо булевым оператором. И трансформация, и оператор применяются к вершинам-потомкам. Пример CSG-дерева приведен на рис. 5.

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

Нетрудно составить алгоритм перевода CSG-дерева в октантное дерево, алгоритм трассировки луча (для отрисовки CSG-дерева на дисплее), а также алгоритм упрощения дерева (устранения из него лишних узлов).

Расчет объемных параметров выполняется простым обходом дерева. Для терминальных узлов (представляющих собой примитивные тела) расчет объемных параметров выполняется аналитически, для нетерминальных (трансформаций и булевых операций) требуется лишь выполнить арифметические действия над вычисленными параметрами дочерних узлов.

Граничные модели

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

- для вершины - ее координаты;

- для ребра - параметрическое уравнение кривой (прямой);

- для грани - параметрическое уравнение поверхности либо тип и набор параметров в случае канонической поверхности (плоскости, сферы, цилиндра, конуса, тора).

Топологические данные - это информация о смежности вершин и ребер, ребер и граней, а также о внутренних и внешних границах грани. Для удобного манипулирования топологической информацией было предложено несколько структур данных, называемых BRep:

- многогранные (фасетные) модели;

- вершинные модели;

- полуреберные модели;

- крыльевые реберные модели.

Разберем одну из самых популярных структур - полуреберную, основанную на том простом факте, что каждое ребро границы твердого тела принадлежит ровно двум граням (рис. 6).

Рис. 6

Структуры данного представления таковы:

- список тел (solid), каждое тело состоит из списка его граней (faces), ребер (edges) и вершин (vertices);

- грань состоит из колец (loop), представляющих собой внешнюю границу грани, а также ее опциональные внутренние границы;

- кольцо состоит из списка полуребер (halfedges);

- полуребро указывает на начальную вершину и следующее полуребро, а также на свое ребро;

- ребро хранит указатели на два своих полуребра.

Корректность граничных моделей

Подробную информацию (со ссылками на первоисточники) по различным видам геометрического моделирования можно получить из главы 5 книги [8] и главы 2 в [37].

Лекция 3. Базовые геометрические объекты

Аффинное пространство и соглашение о нотации

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

В дальнейшем будем придерживаться следующего соглашения о нотации: точки будем обозначать прописными жирными латинскими и греческими буквами: P,, векторы - строчными жирными буквами: e, скалярные величины - обычным шрифтом: x. Оставшийся способ обозначений - прописные нежирные буквы - будем использовать для обозначения матриц. Скалярное произведение векторов u и v обозначим (u, v), векторное - u^v. При работе с формулами, содержащими векторное произведение, часто бывает удобно представлять его в виде произведения 3x3-матрицы и вектора. Делается это путем определения операции: R3 R3x3, отображающей произвольный трехмерный вектор в матрицу, называемую его кососимметрическим тензором:

Нетрудно видеть, что u^v = u? v. Нормой вектора будем называть корень из его скалярного произведения с самим собой (которое всегда положительно): . При записи векторно-матричных операций будем пользоваться операцией транспонирования, обозначая ее RT.

Способы задания аналитических кривых и поверхностей

Задавать множество точек в трехмерном аффинном пространстве можно несколькими способами. Первый - описать условия на координаты точек множества в алгебраическом виде. При этом речь может идти о явном (y = ax2, z = 0) или неявном (x2 + y2 + z2 = 1) задании. Другим способом спецификации множества точек является его параметрическое описание (например, уравнение спирали x(t) = sin t, y(t) = cos t, z(t) = a(t). Заметим, что 1-многообразия (кривые) параметризуются одной переменной, тогда как 2-многообразия (поверхности) требуют двух переменных при параметрическом описании. В силу ряда причин в CAD-системах удобно комбинировать неявное координатное и параметрическое задание многообразий (в частности, при нахождении пересечения двух множеств удобно подставить в координатное уравнение одного параметрическое описание другого). Ниже мы разберем, каким образом задаются простейшие многообразные формы в трехмерном пространстве, указывая оба способа задания.

Одним из способов задания прямой является спецификация какой-либо точки на ней, а также указание единичного вектора, задающего направление прямой:

L = (P, e) = {Q|(Q-P)^e = 0}

Параметрическое уравнение прямой в этом случае имеет вид

L(t) = P + te

Популярным способом представления плоскости является спецификация какой-либо точки на ней и указание единичного вектора нормали:

F = (P, e) = {Q|((Q-P),e) = 0}

Однако для параметрического задания плоскости приходится строить два дополнительных вектора, ортогональных нормали плоскости и неколлинеарных между собой. Проще всего это сделать с помощью следующей процедуры: взять три единичных координатных вектора (1,0,0)T, (0,1,0)T, (0,0,1)T и вычислить их векторные произведения с e. Нетрудно видеть, что среди трех полученных векторов всегда найдутся два неколлинеарных, обозначим их f и g. Тогда параметрическое уравнение плоскости выглядит как

F(u, v) = P + uf + vg.

Сфера задается центром и радиусом:

S = (P, r) = {Q|||Q-P|| = r}

и параметризуется сферическими координатами:

S(u, v) = P + (r cos u cos v, r sin u cos v, r sin v)

Цилиндр задается точкой на оси, направлением оси и радиусом:

C = (P, e, r) = {Q|||(Q-P)^e|| = r}

Окружность задается своим центром, направлением оси и радиусом:

O = (P, e, r) = {Q|((Q-P),e) = 0 и ((Q-P)^e) = r}

Ее параметризацию удобно выполнять для случая e = (0, 0, 1)T. Тогда

O(t) = P + (r cos t, r sin t, 0)

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

Изометрии аффинного пространства

Как известно, изометрия (от греч. isos и metron - равное измерение) - это трансформация метрического пространства, сохраняющая расстояния между любыми его точками. В аффинном пространстве изометрии сохраняют углы между векторами и расстояния между точками. Отметим, что множество всех изометрий образует группу. С каждой изометрией аффинного пространства связано соответствующее преобразование ассоциированного евклидова пространства, которое называется ортогональным. Ортогональные преобразования трехмерного евклидова пространства - это вращения (ортогональные преобразования, сохраняющие векторное произведение) и отражения (не сохраняющие знак векторного произведения) векторов. Изометрии аффинного пространства, сохраняющие знак векторного произведения, называются трансформациями; их можно исчерпывающим образом разделить на три класса:

- параллельный перенос вдоль заданного вектора;

- вращение вокруг заданной оси;

- винтовое движение (комбинация вращения вокруг заданной оси со смещением вдоль нее).

Таким образом, любую трехмерную трансформацию можно охарактеризовать следующими геометрическими параметрами:

- e - единичный вектор (задающий направление оси вращения

или направление параллельного переноса);

- точка опоры (вместе с вектором e она задает ось вращения);

- угол вращения (зависит от направления);

- величина смещения вдоль вектора e.

Свойства этих параметров в зависимости от класса трансформации определяются с помощью табл. 2.

Таблица 2

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

Матричное представление трансформации в аффинном пространстве

Кусочные кривые и их гладкость

Стандарты обмена геометрическими данными

Каждое геометрическое ядро по-своему реализует одни и те же функции твердотельного моделирования. К тому же набор этих функций от ядра к ядру различается. Поэтому важной становится проблема переноса геометрической модели, созданной с помощью одного геометрического ядра, в систему, основанную на другом ядре. Существует множество трансляторов данных из одного представления в другое, но реально независимым от третьих поставщиков способом обмена данными является поддержка каждой CAD-системой нейтральных форматов данных. В рамках системы такая поддержка состоит в реализации двух типов конверторов - преобразовать внутренние данные в нейтральный формат (такой конвертор называется препроцессором) и преобразовать данные в нейтральном формате во внутренние структуры конкретной системы (постпроцессор). Если каждая система реализует преи постпроцессинг своих данных в нейтральном формате, то никакие дополнительные конверторы не требуются. Исторически первыми нейтральными форматами геометрических данных стали IGES и DXF.

Формат IGES

Первая спецификация формата появилась в 1980 г. в результате усилий компаний Boeing и General Electric, а в 1981 он был принят в качестве стандарта ANSI. Первая версия была ориентирована в основном на обмен чертежами между системами автоматизации черчения. В версии 2.0 появилась поддержка данных для метода конечных элементов и специфических элементов печатных плат. В версии 3.0 были поддержаны пользовательские макрокоманды, в 4.0 - твердые тела в виде деревьев CSG, в 5.0 - структура BRep. В рамках стандарта поддерживаются три содержательно и структурно эквивалентных формата IGES-файлов - текстовый (ASCII) со строками фиксированной длины, сжатый ASCII и бинарный. Отметим богатую номенклатуру поддерживаемых форматом типов данных:

§ твердые тела (начиная с версии 4.0):

– параллелепипед;

– прямоугольный клин;

– прямой круглый цилиндр;

– прямой круглый конус;

– сфера;

– тор;

– тело вращения;

– тело линейного перехода;

– эллипсоид;

– булево дерево;

– объемный агрегат;

– экземпляр твердотельного объекта;

§ поверхности:

– плоскость;

– поверхность параметрического сплайна;

– линейчатая поверхность;

– поверхность вращения;

– табулированный цилиндр;

– поверхность рационального B-сплайна;

– поверхность смещения;

– усеченная параметрическая поверхность;

§ кривые:

– дуга окружности;

– составная кривая;

– коническая дуга;

– прямая линия;

– кривая параметрического сплайна;

– точка;

– кривая рационального B-сплайна;

– кривая смещения;

– кривая на параметрической поверхности;

§ прочие объекты:

– множественные данные;

– матрица преобразования;

– отражение;

– узел;

– конечный элемент;

– точка соединения;

– узловое отображение и вращение;

– узловые результаты;

– элементные результаты.

IGES-файл имеет следующую структуру:

– флаг (для идентификации сжатого ASCII и бинарного формата);

– начало (информация на английском языке о происхождении файла);

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

– запись в каталоге (перечисляются все объекты и их типы);

– параметрические данные (задаются координаты и размеры для перечисленных выше объектов);

– конец (контрольные числа - общее количество записей в каждой секции файла).

Формат DXF

Изначально родной формат системы автоматизации черчения AutoCAD стал де-факто стандартом для обмена чертежами. Этот формат поддерживается практически всеми современными CAD-системами. Текстовый файл в этом формате содержит пять основных разделов, содержимое которых изменяется с каждой новой версией AutoCAD:

– заголовок (номер версии AutoCAD, в которой был приготовлен файл DXF);

– таблица (типы линий и слоев, стили текста и виды чертежа);

– блок (список графических элементов, определенных как группа);

– элемент (главный раздел файла, в котором собственно и описываются все графические элементы - точки, линии, дуги, надписи и пр.);

– конец.

Формат STEP

Стандарт STEP (STandard for Exchange of Product model data) разрабатывается непосредственно международной организацией стандартов (ISO) c 1983 г. В основе его разработки лежат следующие принципы:

– ориентация на данные о продукте, включающие информацию обо всем жизненном цикле (проектирование, производство, контроль качества, испытания и поддержка);

– информация, специфичная для конкретного приложения, хранится в отдельной секции;