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

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

Рис. 5.37. Пример формирования октантного дерева

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

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

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

struct octreeroot

float float struct

octree

}:

struct octree

char struct

octree

}:

xmin, ymin. zrnin: xmax. ymax. zmax: *root:

/* гранииы пространства */ /* корень дерева */

code: /* цвет октанта: BtACK. WHITE. GREY */ *oct[8]: /* указатели на октанты */ /* отличны от нуля, если code==GREY */

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

make tree(p. t. depth)

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

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

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

J

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

int i: switch(classify(p. t)) {

case WHITE:

t->code - WHITE:

break: case BLACK:

t->code - BLACK;

break: case GREY:

if (depth-O)

{

t->code - BLACK:

}

else {

subdivide(t):

for (i-0: i<B: 1++)

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

}

break:

}

}

}

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

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

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

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

Рис. 5.38. Пример ячеечного представления

5.3.3. Операторы Эйлера

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

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

Попытка рассматривать топологический элемент отдельно от тех элементов, с которыми он связан, несет в себе внутреннее противоречие. К топологическим элементам применимо приведенное ниже равенство, которое называется формулой Эйлера-Пуанкаре [120, 23]:

v-e + f-h=2(s-p),(5.1)

где v - количество вершин, е - количество ребер, / - количество граней или внешних колец, h - количество колец отверстий, s - количество оболочек и р - количество сквозных проходов через отверстия в теле. Можно проверить это уравнение на фигуре, изображенной на рис. 5.39. Здесь v= 16,/= 10, h = 2, s= 1 и р = 1 (посчитайте самостоятельно). Подставив эти значения в уравнение (5.1), мы получим:

16-24 + 10-2=2(1-1).

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

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

Рис. 5.30. Пример объемного тела

Рис. 5.40. Добавление ребра приводит к изменению грани

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

элементов из этого уравнения необходимо пять операторов. Таким образом, нам нужно определить не более пяти операторов. Полезно было бы определить их так, чтобы они одновременно изменяли такие элементы, которые часто меняются вместе, когда конструктор варьирует форму тела. Предсказать, какая именно группа топологических элементов будет изменяться наиболее часто, не так-то просто. Однако операторы должны включать топологические элементы, которые по меньшей мере удовлетворяют уравнению Эйлера-Пуанкаре. Например, нам подошел бы оператор, создающий ребро и вершину, поскольку он позволяет увеличить количество ребер и вершин на единицу, сохраняя истинность уравнения (5.1). Благодаря этому объемное тело, изначально являвшееся корректным, гарантированно останется таковым после изменения его топологии. Операторы, удовлетворяющие перечисленным выше требованиям, называются операторами Эйлера (Euler operators). Существует много разных наборов операторов Эйлера, и в каждой системе твердотельного моделирования используется свой собственный набор. Изменение, показанное на рис. 5.41, - пример применения оператора Эйлера, который называется Создать Ребро и Кольцо (Make and Edge and a Loop - MEL). Этот оператор увеличивает число колец, соединяя две вершины одного кольца новым ребром. Легко представить себе использование этого оператора для деления грани на две части перед поднятием одной из этих частей. На рис. 5.44 перечислены операторы Эйлера, часто используемые в этой книге.

Рис. 5.41. Операторы Эйлера

тве?тпЛ°ЖеНИИ В МЫ ПеРечислили операторы Эйлера, используемые в системе ™ерДОхельного моделирования SINUMOD, „ описали реализацию типичных

функций моделирования. Список операторов практически совпадает с предложенным Чийокурой [35]. Подробное описание операторов Эйлера и их реализации можно найти в работах [106, 35].

5.3.4. Булевские операторы

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

Если же система твердотельного моделирования использует структуру B-Rep, ситуация оказывается принципиально иной. В этом случае структуру B-Rep исходного тела приходится вычислять по структурам B-Rep исходных тел, к которым применяется булевская операция. Этот процесс называется вычислением границ (boundary evaluation).

Алгоритм вычисления границ был впервые предложен Реквичей и Велкером [132] под названием процесс вычисления и слияния границ (boundary evaluation and merging process) и впоследствии был усовершенствован Миллером [115]. Предлагаемый метод реализуется в три этапа. Для удобства иллюстрирования мы решили воспользоваться плоским рисунком (рис. 5.42), но тот же подход применим и к трехмерным телам. Сначала обозначим две грани (два тела в трехмерном случае), к которым должна быть применена булевская операция, буквами А и Б, а результат операции назовем буквой В (рис. 5.42, а). На первом этапе все ребра А и Б, а также ребра, получаемые пересечением этих граней, помещаются в единый пул ребер. Подмножеством пула ребер, очевидно, являются все ребра грани В. На втором этапе все ребра пула классифицируются по их положению относительно граней А и Б. Любое ребро может находиться, во-первых, внутри, на границе или снаружи грани и, во-вторых, внутри, на границе или снаружи грани Б (рис. 5.42, б). На третьем этапе ребра группируются по их относительному положению в соответствии с применяемой булевской операцией. Заметьте, что для операции «А объединить с Б» нужно отбросить все ребра, находящиеся «внутри А» и «внутри Б» (см. рис. 5.42, б). Аналогичным образом для операции «А пересечь с Б» отбрасываются ребра, лежащие «вне А» и «вне Б». Собранные ребра формируют грань. Для этого в структуру заносятся все необходимые сведения о вершинах, ребрах, кольцах и прочих элементах. Для объемных тел такой под-