qweqweqe123123

Структура данных

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

Структуры данных, используемые для описания объемных тел, обычно делятся на три типа в зависимости от того, какие тела ими описываются. Первая структура представляет собой дерево, описывающее историю применения булевских операций к примитивам. Журнал операций называется конструктивным представлением объемной геометрии (Constructive Solid GeometryCSG representation). Дерево называется деревом CSG (GSG tree). Вторая структура содержит сведения о границах объема (вершинах, ребрах, гранях и их соединении друг с другом). Это представление называется граничным представлением (boundary representation - В-rep), а структура данных - структурой B-rep (B-rep data structure). Многие структуры B-rep строятся по-разному в зависимости от того, какой элемент считается основным при сохранении сведении о связности (см. далее). Третья структура представляет объем в виде комбинации элементарных объемов (например, кубов). Можно придумать множество моделей разложения, выбирая разные элементарные объемы, но ни одна из них не может точно описать объемное тело.

Дерево CSG

Вспомните, что дерево CSG содержит историю применения булевских операций к примитивам. Рассмотрим тело, изображенное на рис. 5.23, а. Его историю булевских операций можно представить в виде дерева так, как показано на рис. 5.23, б. Это дерево может быть представлено взаимосвязанными элементами данных (рис. 5.23, в). Элементы данных реализуются на языке С (листинг 5.1).

Структура данных

Листинг 5.1. Реализация структуры дерева CSG на языке С

struct operator {

int op_type. /* оператор обьединения. пересечения или разности */ L type. /* тип левого узла: 0 - оператор. 1 - примитив */ R_type:       /* тип правого узла: 0 - оператор. 1 - примитив */

void *L_ptr. /* левый узел */

*R_ptr.           /* правый узел */

*p_ptr:           /* родительский узел */

}

struct primitive {

int prim_ type:     /* тип примитива */

double pos_x. posj. pos_z; /‘положение экземпляра */ double ori_x. ori y. ori_z: /* ориентация экземпляра */ void ‘attribute:           /* значения размеров примитива */

 

Дерево CSG обладает следующими преимуществами:

□   структура данных проста, а их представление компактно, что облегчает обработку;

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

□   представление CSG всегда может быть преобразовано к соответствующему представлению B-Rep. Это позволяет взаимодействовать с программами, ориентированными на использование B-Rep;

□   параметрическое моделирование легко реализуется изменением параметров соответствующих примитивов (рис. 5.24).

 

Есть у этого дерева и недостатки:

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

□   для получения сведений о граничных поверхностях, их ребрах и связях между этими элементами из дерева CSG требуются сложные вычисления. К сожалению, сведения о границах нужны для множества приложений, в частности для отображения тел. Для того чтобы отобразить затушеванное изображение или чертеж объемного тела, нужно иметь информацию о гранях или вершинах этого тела (см. главу 3). Поэтому представление CSG является недостаточным для интерактивного отображения тел и манипулирования ими. Другой пример — расчет траектории движения фрезы с ЧПУ для обработки поверхностей тела. Для этой задачи нужны сведения о поверхностях, их ребрах и связности. Получить все эти сведения из дерева CSG очень непросто.

Структура данных

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

 

Структура данных B-Rep

Границы объемных тел состоят из элементарных геометрических объектов: вершин, ребер и граней1. В структуре данных B-Rep хранятся все эти элементы вместе со сведениями о том, как они соединены друг с другом. Одна из простейших структур данных, если не самая простая, приведена в табл. 5.1. Структура данных представляет объемное тело, изображенное на рис. 5.25. В таблице граней хранится список ограничивающих ребер для каждой грани. Последовательность ребер для каждой грани дается обходом против часовой стрелки, если смотреть на тело снаружи. Благодаря тому что ребра хранятся согласованно, вместе с каждой гранью сохраняется информация о том, с какой стороны от нее находится внутренний объем тела. Другими словами, имея сведения о гранях, вы можете определить, где расположена конкретная точка: снаружи или внутри тела. Вершины, ребра и грани, изображенные на рис. 5.25, нумеруются системой геометрического моделирования в произвольном порядке в момент сохранения сведений из табл. 5.1.

Структура данных

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

Структура данных

Структура данных В-Rep выглядит очень простой и компактной. Однако она не используется в развитых системах твердотельного моделирования из-за перечисленных ниже недостатков.

□   Структура данных B-Rep ориентирована на хранение плоских многогранников. Если потребуется сохранить данные о теле с криволинейными гранями и ребрами, строки таблиц граней и ребер придется изменять таким образом, чтобы в них можно было включить уравнения поверхности и кривой соответственно2. Уравнения для плоских граней сохранять не обязательно, поскольку плоские грани определяются находящимися на них вершинами.

□   Грань с внутренними и внешними границами (рис. 5.26, а) не может быть сохранена в таблице граней, поскольку для нее нужно два списка ребер вместо одного. Такие грани появляются, например, при моделировании объемных тел со сквозными отверстиями. Простым решением этой проблемы является добавление ребра, соединяющего внешнюю и внутреннюю границы (рис. 5.26, б). В этом случае два списка вершин могут быть объединены. Соединительное ребро называется мостиком или перемычкой (bridge edge) и попадает в список ребер в двух экземплярах.

Структура данных

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

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

Есть две распространенные структуры данных, которые позволяют избежать перечисленных проблем при сохранении граничного представления объемного тела. Это структура полуребер (half-edge data structure) и структура крыльевых ребер (winged-edge data structure).

 

Структура полуребер

В качестве средства для борьбы с таблицей граней переменного размера можно использовать двусвязный список3, в который помещаются сведения обо всех вершинах данной грани (рис. 5.27). Для каждой грани сохраняется указатель на первое ребро списка, а не весь список, тогда как в структуре каждого ребра имеются указатели на предыдущее и последующее ребро того же списка. В результате в таблице граней будет фиксированное число столбцов. Список ребер при этом всегда можно будет восстановить, переходя от одного ребра к другому по указателям (например, список ребер Е5, E6 и E7, для грани F1). Грань F1 может хранить указатель на E6 или Е1,но список ребер всегда будет один и тот же.

Структура данных

Однако мы немедленно столкнемся с другой проблемой, когда перейдем к грани F2, которая имеет общее ребро Е6 с граньюF1 (рис. 5.25). Двусвязный список для грани F2 должен выглядеть так, как показано на рис. 5.28. По этому рисунку видно, что для ребра Е6 последующим является E7, а предыдущим — E2. Сохранив соответствующие указатели, мы изменим заданные ранее значения указателей, обеспечивавшие ребру Е6 место в списке ребер грани F1, то есть фактически разрушим список ребер грани F1.

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

Структура данных

 

Структура данных

Для описания граней с внутренними отверстиями без добавления избыточных соединительных ребер используются кольца (loop) — это список ребер, образующих замкнутую цепочку, так что любая грань ограничивается одним внешним кольцом и может ограничиваться внутренними4, определяющими отверстия. Теперь каждая грань может ссылаться на список полуребер через кольцо, а не непосредственно. Другими словами, для каждой грани хранится двусвязный список колец, а для каждого кольца хранится список полуребер. Это позволяет обрабатывать грани с любым количеством отверстий без добавления мостиков.

На рис. 5.31 показано, как хранится в памяти грань с отверстиями при помощи колец. Обычно в структуру грани включается указатель на внешнее кольцо, а оно становится первым элементом двусвязного списка колец. У каждого кольца есть список полуребер, направление которых противоположно направлению внешнего кольца Другими словами, полуребра отверстия помешаются в список в таком порядке, что их направления совпадают с направлением обхода отверстий по часовой стрелке, если смотреть снаружи тела На рис. 5.31 полуребра кольца L1 обходятся против часовой стрелки (это кольцо внешнее), а полуребра колец L2 и L3 — по часовой стрелке (эти кольца внутренние).

Структура данных

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

 

Структура данных с полуребрами и кольцами имеет множество преимуществ перед структурой с таблицами вершин, ребер и граней. В структуре с полуребрами и кольцами можно сохранять данные о связности вершин, ребер и граней и по этим данным получать сведения о смежности. Мы уже показали, что получить такие данные по исходной простой таблице — задача непростая. Однако благодаря полуребрам и кольцам в структуре сохраняются сведения о связности вершин, ребер и граней, и тогда задача упрощается. Вершины, ребра и грани указывают на соответствующие полуребра и кольца, для которых сохраняются сведения о смежности. Чтобы обеспечить связь между ребром и его полуребрами, для каждого ребра сохраняются указатели на соответствующие полуребра, а для полуребер — указатели на родительские ребра. Аналогичным образом, для каждой вершины сохраняется указатель на одно из полуребер, исходящих из нее, а для каждого полуребра сохраняется указатель на его начальную вершину5. Для грани сохраняется указатель на внешнее кольцо, а для кольца — указатель на родительскую грань (см. рис. 5.31). Сведения о смежности колец и полуребер сохраняются естественным способом (каждое кольцо представляется в виде двусвязного списка полуребер).

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

1.  Если вершина V1 является начальной вершиной h1, (в нашем случае так и есть), то выбирается полуребро, предшествующее h1 (prev_h1), а его родительское ребро оказывается одним из нужных нам ребер, соединенных с V1. Теперь место h1 занимает сопряженное полуребро prev_h1 (которое мы обозначаем new_h1) и шаг 1 повторяется. Если Vx — конечная вершина h1, выбирается полуребро, следующее за h1, а его родительское ребро считается одним из подходящих к вершине. Затем вместо h1 берется полуребро, сопряженное со следовавшим за h1 и шаг 1 повторяется с полуребром new_h1.

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

Структура данных

Реализация структуры данных полуребер представлена в приложении А. Структуру данных, используемую в системе твердотельного моделирования GWB, разработанной Мянтюля [106], демонстрирует листинг А.1. В книге [106] рассказывается о некоторых дополнительных указателях. В некоторых случаях ока зывается выгоднее сохранить избыточные указатели, чем вычислять их заново, особенно если выполнять это пришлось бы часто. Количество и назначение избыточных указателей должны планироваться в процессе проектирования структуры данных. Реализация процедуры поиска всех ребер, исходящих из конкретной вершины, на предлагаемой структуре данных, представлена в листинге А2.

 

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

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

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

Определим структуру крыльевых ребер для фигуры, изображенной на рис. 5.33. Ребро E1 является смежным с четырьмя другими ребрами: Е2, E3, E4 и Es, каждое из которых содержит одну из двух вершин ребра E1. Если рассматривать ребро E1 как фюзеляж самолета, четыре ребраЕ2, E3, E4 и Es будут его крыльями. Эти четыре смежных ребра называются крыльевыми ребрами E1. Каждое из них должно быть сохранено под отдельным именем с информацией о положении этого ребра относительно E1. Именуются крыльевые ребра так. Вначале E1 назначается определенное направление (рис. 5.33). Здесь ребро направлено от вершины V1 к вершине V2. Затем следует представить себе, что вы лежите вдоль ребра E1 так, что голова направлена к V2 (а тело, разумеется, находится снаружи объема). Вытяните руки и ноги так, как если бы вы летели. Левая рука коснется ребра E2, правая рука — ребра E3, левая нога — ребра E4, правая нога - ребра E5. Поэтому ребро E2 называют ребром левой руки, E3 — ребром правой руки, E4 — ребром левой ноги, E5 — ребром правой ноги. Если E1 направить в противоположную сторону, E5 будет ребром левой руки, E4 — ребром правой руки, E3 — ребром левой ноги и E2 — ребром правой ноги. Направление каждого ребра устанавливается произвольно в момент создания объемного тела и сохранения его структуры крыльевых ребер.

Помимо связности ребер в терминах крыльевых ребер необходимо также описать связность граней и ребер. Поэтому для каждого ребра сохраняются указатели на две грани, которым оно принадлежит. Например, для ребра E1 на рис. 5.33 сохраняются указатели на ребра F1 и F2 (левое и правое соответственно). Названия ребер определяются направлением E1. Граням присваиваются разные названия по той же схеме, по которой они присваиваются крыльевым ребрам. Брейд предложил использовать кольца для сохранения сведений о телах со сквозными отверстиями в структуре крыльевых ребер. Связь между гранью и ее ребрами задается неявно при помощи колец. Каждое ребро хранит указатель на свое левое и правое кольца, а не на левую и правую грань. Например, на рис. 5.33 ребро E1 хранит указатель на L1 как на левое кольцо и на L2 как на правое кольцо. Если направление Et изменить на противоположное, названия колец также изменятся. Кольца содержат указатели на все ребра, которые к ним относятся. Это дает возможность получить список всех ребер одного кольца Процедура аналогична получению списка полуребер начиная с любого произвольного полуребра, на которое имеется указатель в кольце.

Теперь рассмотрим описание связности ребер и вершин. Вспомните, что у каждого ребра на концах находятся вершины. Эти вершины сохраняются под именами предыдущая вершина (previous vertex или tail vertex) и последующая вершина (next vertex или head vertex), поскольку все ребра имеют направления. На рис. 5.33 V1 является предыдущей вершиной для E1, a V2 ~ последующей. Сохраняются не только указатели на вершины в структурах ребер, но и указатели на ребра в структурах вершин — по одному ребру для каждой вершины. Это позволяет выделить ребро, начиная с которого перечисляются все ребра, сходящиеся в одной вершине. При реализации функций моделирования, в особенности содержащих

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

Описанные способы сохранения информации о связности вершин, ребер и граней иллюстрирует рис. 5.34.

Структура данных

Помимо описанных связей сохраняются также связи между гранями и их кольцами, как в структуре данных полуребер. А именно, для каждой грани сохраняется указатель на ее внешнее кольцо, а для внешнего кольца сохраняется указатель на кольцо отверстия, если в данной грани оно есть. Кольцо отверстия может указывать на другое кольцо отверстия, если в грани отверстий несколько; в противном случае оно указывает обратно на внешнее кольцо (рис. 5.35). Кроме того, для каждого кольца сохраняется указатель па его родительскую грань. Заметьте, что здесь используется односвязный список, а не двусвязный, как на рис. 5.30. Выбор односвязного или двусвязного списка определяется тем, что считается более важным — эффективность обращения к данным или компактность структуры.

Структура данных

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

Структура данных

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

 

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

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

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

Воксельное представление (voxel representation) объемного тела — это просто трехмерный аналог растрового представления плоской фигуры. Чтобы рассказать о воксельном представлении, нам придется вспомнить процедуру получения растрового представления или растрового изображения. Растровое изображение двумерного объекта формируется следующим образом. Сначала создается квадрат, размер которого соответствует интересующей нас области двумерного пространства. Затем квадрат делится на много маленьких квадратиков путем нанесения на него линий сетки. Расстояние между линиями сетки определяется желаемой точностью растрового представления. Другими словами, если это расстояние будет очень маленьким, то растровое изображение будет очень точно воспроизводить форму исходного двумерного объекта В противном случае получится лишь грубое приближение. Квадрат, содержащий много маленьких квадратиков, представляется в компьютере в виде двумерного массива, количество элементов в котором совпадает с количеством квадратиков. Наконец, большой квадрат накладывается на двумерный объект, и элементы массива, соответствующие квадратикам, находящимся над объектом, получают значение 1, а остальные элементы получают значение 0. Получившийся массив нулей и единиц становится растровым представлением двумерного объекта.

Воксельное представление объемного тела получается при помощи той же процедуры, что и растровое представление. Однако начинается она не с большого квадрата и маленьких квадратиков, а с большого куба и маленьких кубиков, называемых вокселами6. Деление на вокселы осуществляется сеткой плоскостей, расположенных на равном расстоянии друг от друга перпендикулярно осям x, у и z. Исходный куб представляется в виде трехмерного массива, количество элементов которого совпадает с количеством кубиков, и каждому элементу массива присваивается значение 0 или 1 в зависимости от положения элемента в теле.

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

Структура данных

Воксельное представление обладает следующими преимуществами.

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

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

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

 

Есть у вексельного представления и некоторые недостатки.

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

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

 

Представление октантного дерева

Представление октантного дерева (octree representation) аналогично воксельному в том плане, что тело рассматривается как совокупность шестигранников (куб — это правильный шестигранник). Однако это представление предъявляет значительно менее серьезные требования к памяти благодаря иной схеме деления пространства. В воксельном представлении исходный куб делится сеткой плоскостей, находящихся на равном расстоянии друг от друга по осям х, у и z. В представлении октантного дерева исходный куб делится каждый раз на восемь равных кубов поперечными плоскостями (рис. 5.37, о). Объем маленького куба в восемь раз меньше объема исходного, отсюда и название представления. Более того, если кубики представить в виде узлов дерева, то от каждого узла будет отходить восемь ветвей (рис. 5.37, б). Такое дерево и называется октантным (octree). Если бы каждый кубик всегда делился на восемь меньших вне зависимости от формы моделируемого тела, то результат был бы полностью аналогичен вексельному представлению с кубиками постоянного размера. Однако в представлении октантного дерева некоторые кубики делятся на восемь частей, тогда как другие кубики того же уровня остаются целыми. Определяется это положением кубиков по отношению к представляемому телу.

Структура данных

Процедура построения представления октантного дерева выглядит следующим образом. Сначала создается шестигранник, в который моделируемое тело помещается целиком. Этот шестигранник называется корневым октантом (root octant). Затем корневой октант делится на восемь октантов, после чего анализируется их положение в пространстве по отношению к моделируемому телу. Если октант находится полностью внутри тела, он считается «черным»; если снаружи — «белым». Если же октант частично лежит внутри тела, а частично — снаружи, то он считается «серым» и делится на восемь октантов меньшего размера. Черные и белые октанты дальше не делятся. Процедура повторяется до тех пор, пока не будет достигнут заданный минимальный размер октанта После этого октанты, окрашенные в черный цвет, считаются относящимися к исходному телу8.

На рис. 5.37, в показано октантное дерево для тела с рис. 5.37, б. Количество октантов, под которые приходится отводить память, мною меньше количества во- кселов для тела того же объема поскольку белые и черные октанты дальше не делятся. Октантное дерево с рис. 5.37, в хранится в компьютере в виде структуры данных. Реализация такой структуры на языке С показана в листинге 5.2, а процедура формирования октантного дерева на основе этой структуры данных приводится в листинге 5.3. Эта процедура представляет собой, по сути, запись на языке программирования описанных выше действий. Несмотря на относительно простой вид процедуры, подпрограмма classify(p.t) требует сложных геометрических вычислений, поскольку она определяет, где находится конкретный октант, внутри тела, снаружи его или на границе. Серые октанты преобразуются в черные после окончания процесса деления. Поэтому объем модели, полученной в результате применения этой процедуры, будет заведомо большим объема исходного тела.

 

Листинг 5.2. Структура данных для хранения октантного дерева

struct octreeroot

* float                                                 xmin. ymin. zmin:             /* границы пространства */

float                             xmax. ymax. zmax;

struct       octree *root:                                         /* корень дерева */

}:

struct octree

{char             code:        /* цвет октанта: BLACK. WHITE. GREY */

struct       octree *oct[8]: /* указатели на октанты */

I* отличны от нуля, если code=GREY */

}:

Листинг 5.3. Процедура формирования октантного дерева

make_tree(p. t. depth)

primitive *p:                   /* p - моделируемый примитив */

octree *t:                       /* t - узел дерева, то есть исходное дерево с одним серым узлом /

int                         depth:       /* максимальная глубина рекурсии */

{

int i:

switch(classify(p t))

case WHITE:

t->code - WHITE: break: case BLACK:

t->code - BLACK; break: case GREY: if (depth—0)

{

t->code - BLACK:

}

else

              }

          }

     }

subdivide(t);

for (i=0: i

make_tree(p.t->oct[i].depth-1):

break.

/* функция определения цвета узла дерева */ classify(_);

/* функция деления узла на восемь октантов */ subdivided:

 

Ячеечное представление

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

Структура данных

 


1 Грань — часть граничной поверхности, граница которой состоит из криволинейных сегментов, при пересечении которых происходит существенное изменение вектора нормали к поверхности. Криволинейные сегменты, ограничивающие грань, называются ребрами. Точки, в которых встречаются соседние ребра, называются вершинами.

2 Уравнения поверхностей и кривых, а также координаты вершин называют геометрическими данными, тогда как отношения между гранями, ребрами и вершинами называют топологическими данными. Данные в любой структуре B-Rep могут быть классифицированы либо как геометрические, либо как топологические.

3 Эту проблему можно решить и с односвязным списком. Мы выбрали двойной связный список, чтобы получить ту полуреберную структуру, которую предложил Мянтюля [106].

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

5 Вершина полуребра считается начальной или конечной в соответствии с направлением этого полуребра.

6 Воксел — это трехмерный аналог пиксела. Последние четыре буквы названия взяты от слова "пиксел"(pixel), а первые две — от слова "объем" (volume).

7 Аналогичное представление можно построить и для двумерного объекта, но в этом случае дерево будет называться квадрантным (quadtree).

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

Смотрите также