книги / Основы САПР. CAD CAM CAE

на тело снаружи. Благодаря тому что ребра хранятся согласованно, вместе с каж­

дой гранью сохраняется информация о том, с какой стороны от нее находится

внутренний объем тела. Другими словами, имея сведения о гранях, вы можете

определить, где расположена конкретная точка: снаружи или внутри тела. Вер­

шины, ребра и грани, изображенные на рис. 5.25, нумеруются системой геомет­

рического моделирования в произвольном порядке в момент сохранения сведе­

ний из табл. 5.1.

Таблица 5.1. Три таблицы представления B-Rep

Vs

Fs

Рис. 5.25. Объемное тело, сохраняемое в табл. 5.1

В каждой строке таблицы ребер хранятся вершины, находящиеся на концах со­ ответствующего ребра, а в строках таблицы вершин хранятся координаты всех вершин. Эти координаты обычно определяются в модельной системе коорди}'{ат, связанной с данным телом. Если убрать отсюда таблицу граней, эту структуру данных можно будет использовать для хранения форм, созданных в систеl\iах

каркасного моделирования. Структура данных для каркасной модели может ис­

пользоваться в качестве базовой для систем автоматизированной разрабоrки

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

вывалось с направлением обхода границ грани: против часовой стрелки, если смотреть снаружи тела. В результате получаются двусвязные списки полуребер для граней F1 и F2 (рис. 5.30). Теперь никаких проблем, приводящих к разруше­

нию списка для ребра F1, не возникает.

Vs

Fs

Рис. 5.29. Полуребра рассматриваемого тела

С?- h4 ~ h11 ~ ht4 3)

Рис. 5.30. Двусвяэньtй список полуребер

Для описания граней с внутренними отверстиями без добавления избыточных

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

ним кольцом и может ограничиваться внутренними1, определяющими отвер­

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

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

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

На рис. 5.31 показано, как хранится в памяти грань с отверстиями при помощи

колец. Обычно в структуру грани включается указатель на внешнее кольцо,

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

ца есть список полуребер, направление которых противоположно направлению внешнего кольца. Другими словами, полуребра отверстия помещаются в список

1Внешнее кольцо и кольца отверстий называются также родительским (parent loop) и до­

черними кольцами (child loop) соответственно.

1.Если вершина Vt является начальной вершиной h1 (в нашем случае так и есть),

то выбирается полуребро, предшествующее h1 (prev_h1 ), а его родительское ребро оказывается одним из нужных нам ребер, соединенных с V1• Теперь ме­

сто ht занимает сопряженное полуребро prev_h1 (которое мы обозначаем new_h1)

и шаг 1 повторяется. Если V1 -конечная вершина h1, выбирается полуребро,

следующее за ht, а его родительское ребро считается одним из подходящих

к вершине. Затем вместо h1 берется полуребро, сопряженное со следовавшим

за ht, и шаг 1 повторяется с полуребром new_h1.

2.Процесс повторяется до тех пор, пока не будет достигнуто полуребро, сопря­ женное с исходным h1•

Рис. 5.32. Получение данных о смежности ребер и вершин

Реализация структуры данных полуребер представлена в приложении А. Струк­

туру данных, используемую в системе твердотельного моделирования GWB,

разработанной Мянтюля [106], демонстрирует листинг А.1. В книге [106] рас­

сказывается о некоторых дополнительных указателях. В некоторых случаях ока­

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

туры данных. Реализация процедуры поиска всех ребер, исходящих из конкрет­

ной вершины, на предлагаемой структуре данных, представлена в листинге А.2.

Структура крыльевых ребер

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

объемного тела отводится граням. В структуре крьUlьевыхребер (winged-edge data structure) главная роль, напротив, отводится ребрам. Для каждого ребра сохраня­ ется список граней, которым оно принадлежит, ребер, с которыми оно имеет об­ щие вершины, и вершин на его концах. Список ребер для каждой грани не сохра­ няется в структуре в явном виде, поскольку он может быть получен анализом любого ребра грани и соседних с ним ребер. Проблема неопределенности коли­

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

граней сохраняются в структуре данных в явном виде. В структуре полуребер

связность неявно описывалась самими полуребрами. Мы уже отметили некото­

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

оно принадлежит, соседние ребра и конечные вершины.

Структура крыльевых ребер впервые была предложена Бомгартом [11]. Брейд

расширил ее, добавив поддержку тел со сквозными отверстиями посредством ис­ пользования колец [23].

Определим структуру крыльевых ребер для фигуры, изображенной на рис. 5~33. Ребро Е1 является смежным с четырьмя другими ребрами: Е2, Е3, Е4 и Е5, каждое из которых содержит одну из двух вершин ребра Е1• Если рассматривать ребро Е1 как фюзеляж самолета, четыре ребра Е2, Е3, Е4 и Е5 будут его крыльями. Эти че­

тыре смежных ребра называются крыльевыми ребрами Е1• Каждое из них долж­ но быть сохранено под отдельным именем с информацией о положении этого

ребра относительно Е1• Именуются крыльевые ребра так. Вначале Е1 назначается

определенное направление (рис. 5.33). Здесь ребро направлено от вершины V1 к

вершине V2• Затем следует представить себе, что вы лежите вдоль ребра Е1 так, что голова направлена к V2 (а тело, разумеется, находится снаружи объема). Вы­ тяните руки и ноги так, как если бы вы летели. Левая рука коснется ребра Е2,

правая рука - ребра Е3, левая нога - ребра Е4, правая нога - ребра Е5• Поэтому ребро Е2 называют ребром левой руки, Е3 - ребром правой руки, Е4 - ребром ле­ вой ноги, Е5 - ребром правой ноги. Если Е1 направить в противоположную сто­ рону, Е5 будет ребром левой руки, Е4 - ребром правой руки, Е3 - ребром левой ноги и Е2 - ребром правой ноги. Направление каждого ребра устанавливает­ ся произвольно в момент создания объемного тела и сохранения его структуры крыльевых ребер.

Помимо связности ребер в терминах крыльевых ребер необходимо также опи­

сать связность граней и ребер. Поэтому для каждого ребра сохраняются указате­ ли на две грани, которым оно принадлежит. Например, для ребра Е1 на рис. 5.33 сохраняются указатели на ребра F1 и F2 (левое и правое соответственно). Назва­

ния ребер определяются направлением Е1• Граням присваиваются разные назва­

ния по той же схеме, по которой они присnаиваются крыльевым ребрам. Брейд

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

отверстиями в структуре крыльевых ребер. Связь между гранью и ее ребрами за­

дается неявно при помощи колец. Каждое ребро хранит указатель на свое левое

и правое кольца, а не на левую и правую грань. Например, на рис. 5.33 ребро Е1

хранит указатель на L 1 как на левое кольцо и на L2 как на правое кол'ьцо. Если

направление Е1 изменить на противоположное, названия колец также изменятся. Кольца содержат указатели на все ребра, которые к ним относятся. Это дает воз­ можность получить список всех ребер одного кольца. Процедура аналогична по­

лучению списка полуребер начиная с любого произвольнаго полуребра, на кото­

рое имеется указатель в кольце.

Теперь рассмотрим описание связности ребер и вершин. Вспомните, что у каж­

дого ребра на концах находятся вершины. Эти вершины сохраняются под имена­

ми предыдущая вершина (previous vertex или tail vertex) и последующая вершина

(пехt ve1te.т или head vertex), поскольку все ребра имеют направления. На рис. 5.33 V1 является предыдущей вершиной для Е1, а V2 - последующей. Сохраняются не

только указатели на вершины в структурах ребер, но и указатели на ребра в

структурах вершин - по одному ребру для каждой вершины. Это позволяет вы­

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

операторы Эйлера (см. раздел 5.3.3), приходится часто просматривать списки ре­

бер, сходящихся в одной вершине.

Описанные способы сохранения информации о связности вершин, ребер и гра­

ней иллюстрирует рис. 5.34.

Предыдущая вершина

Рис. 5.34. Связность вершин, ребер и граней

Помимо описанных связей сохраняются также связи между гранями и их кош,­

цами, как n структуре данных полуребер. А именно, для каждой грани сохраняет­

ся указатель на ее внешнее кольцо, а для nнешнего кольца сохраняется указатель

на кольцо отверстия, если в данной грани оно есть. Кольцо отверстия может ука­

зьшать на другое кольцо отверстия, если в грани отверстий несколько; в против­

ном случае оно указывает обратно на nнешнее кольцо (рис. 5.35). Кроме того, для

каждого кольца сохраняется указатель на его родительскую грань. Заметьте, что здесь используется односвязный список, а не двусвязный, I<ак на рис. 5.30.

Выбор односвязного или дnусвязного списка определяется тем, что считается более важным - эффективность обращения к данным или комiJактносп, струк­

туры.

Грань

L / ~ ----------

Кольцо 1 - Кольцо2- ·• · -n ~

Рис. 5.35. Связи между гранью и ее кольцами

Пример реализации структуры д<шных крыльевых ребер на языке С Jtемонстрн­

рует листинг Б.1 в приложении Б. Эта структура данных испольэуется в систеl\lе

твердотельного моделирования SNUMOD, разработанной в Сеульском государ-

ственном университете в Корее. В листинге присутствует новый элемент - обо­ лочка (shell). Оболочка - это трехмерное расширение кольца, то есть список гра­

ней, образующих замкнутый объем. Обычно в объемном теле может быть только

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

кольца отверстия позволяет описывать грань с отверстиями.

Сrруктура декомпозиционной модели

Объемная модель может быть приближенно представлена в виде совокупности

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

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

ответствующими структурами данных относятся воксельное представление,

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

Ваксельное предсгавление

Боксельное представление (voxel representation) объемного тела - это просто трехмерный аналог растрового представления плоской фигуры. Чтобы расска­

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

ния растрового представления или растрового изображения. Растровое изобра­

жение двумерного объекта формируется следующим образом. Сначала создается

квадрат, размер которого соответствует интересующей нас области двумерного пространства. Затем квадрат делится на много маленьких квадратиков путем на­

несения на него линий сетки. Расстояние между линиями сетки определяется желаемой точностыо растрового представления. Другими словами, если это рас­

стояние будет очень маленьким, то растровое изображение будет очень точно

воспроизводить форму исходного двумерного объекта. В противном случае по­ лучится лишь грубое приближение. Квадрат, содержащий много маленьких

квадратиков, представляется в компьютере в виде двумерного массива, количе­

ство элементов в котором совпадает с количеством квадратиков. Наконец, боль­ шой квадрат накладывается на двумерный объект, и элементы массива, соответ­ ствующие квадратикам, находящимся над объектом, получают значение 1, а

остальные элементы получают значение О. Получившийся массив нулей и еди­

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

Боксельное представление объемного тела получается при помощи той же про­

цедуры, что и растровое представление. Однако начинается она не с большого

квадрата и маленьких квадратиков, а с большого куба и маленьких кубиков, на­

зываемых воксела.ми1• Деление на вокселы осуществляется сеткой плоскостей,

расналоженных на равном расстоянии друг от друга перпендикулярно осям х, у

и z. Исходный куб представляется в виде трехмерного массива, количество эле­

ментов которого совпадает с количеством кубиков, и каждому элементу массива

присваивается значение О или 1 в зависимости от положения элемента в теле.

1 Боксел - это трехмерный аналог пикссла. Последние четыре буквы названия взяты от

слова спиксел• (pixel), а первые две - от слова собъем• (volume).