3UZ

Приложение Д. Структура данных и топологические операторы

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

Модель

Регион

Оболочка [

Вхождение грвни

Вхождение кольца

Грань J

Кольцо

Вхождение ребра U-► Ребро

Вхождение вершины «-► Вершина \

Рис. Д.4. Топологические элементы в представлении радиальных ребер

Рисунок Д.4 показывает, что связи между базовыми топологическими сущностями задаются косвенно через четыре дополнительных топологических элемента: вхождение грани, вхождение кольца, вхождение ребра и вхождение вершины. Это аналогично введению полуребер для косвенного задания связей между кольцами, ребрами и вершинами (см. раздел 5.3.2). Вхождение грани (face-use) - это один из двух вариантов использования грани, или одна из двух ее сторон. Таким образом, оболочка, окружающая внешнюю или внутренню область объема, определяется набором связанных вхождений граней. Вхождение грани, или использование грани оболочкой, имеет определенную ориентацию по отношению к геометрии грани, и эта ориентация противоположна ориентации сопряженного ему вхождения данной грани. Каждое из двух вхождений грани становится элементом каждой из двух оболочек, обращенных к данной грани. В случае сотовой структуры без замкнутого объема, как на рис. Д.5, эти сопряженные вхождения грани принадлежат одной и той же оболочке. В данном примере список вхождений граней fiii- fu2- fu5- fu6- fu4- fu3 образует оболочку. Вхождение грани ограничено одним или несколькими вхождениями кольца, так как грань окружена кольцами. Вхождение кольца (loop-use) - это один из вариантов использования кольца, связанный с одним из двух вариантов использования грани, и оно имеет ориентацию по отношению к соответствующему вхождению грани, что определяет ее внутреннюю или внешнюю границу (см. рис. Д.5). Вхождение кольца определяется списком вхождений ребер. Вхождение ребра (edge-use) - это граничный сегмент кривой на вхождении кольца, принадлежащего вхождению грани, и оно представляет использование ребра данным вхождением кольца или, в случае

Д.1. Структура данных

5U3

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

Рис. Д.5. Использование дополнительных топологических элементов для указания

смежности

Некоторые вырожденные ситуации указаны пунктирными связями на рис. Д.4. Во-первых, прямое соединение оболочки и списка вхождений ребра допускает существование оболочки, представляющей собой каркас. Аналогичным образом, соединение оболочки и вхождения вершины допускает существование оболочки, состоящей из одной вершины. Изолированная точка в немногообразном представлении хранится как независимая оболочка. Кроме того, прямое соединение вхождения кольца и вхождения вершины позволяет хранить изолированную точку, находящуюся на грани, в виде кольца отверстия этой грани, что дает возможность представить свободное ребро, исходящее из некоторой точки на грани. Немногообразные модели смешанной размерности можно обрабатывать, интерпретируя элементы меньшей размерности как вырожденные вхождения граней и храня эти вхождения в списке вместе с другими вхождениями граней, принадлежащими той же оболочке.

Теперь поясним, как в структуре радиальных ребер представляются кольцевой и радиальный циклы. Прежде всего, кольцевой цикл задается просто списком вхождений ребер для каждого вхождения кольца. Например, вхождение кольца luj на рис. Д.5 несет в себе список вхождений ребер eut - eu7 - eu8 - eu9. Для задания радиального цикла каждое вхождение ребра имеет два указателя, указатель сопряженности и радиальный указатель (рис. Д.6). На рис. Д.6 изображен вид сотовой структуры, представленной на рис. Д.5, в поперечном сечении. По рис. Д.6 видно, что указатель сопряженности вхождения ребра - это указатель на вхождение ребра на обратной стороне грани, а радиальный указатель указывает на вхождение ребра, которое принадлежит вхождению грани, смежному в радиаль-

5U4

Приложение Д. Структура данных и топологические операторы

ном направлении с вхождением грани заданного вхождения ребра. Благодаря этим указателям можно полностью радиально упорядочить грани вокруг ребра, отслеживая указатели от любого вхождения ребра. Как упоминалось ранее, в представлении радиальных ребер дисковый цикл не хранится в явном виде. Однако цикл «вершина-ребро» хранится, как и в многообразном представлении, в виде списка вхождений вершин для каждой вершины. Хранение списка вхождений вершин эквивалентно хранению вхождений ребер, поскольку каждое вхождение вершины связано с вхождением ребра, и поэтому эквивалентно хранению цикла «вершина - ребро». Например, вершина VI на рис. Д.5 хранит список вхождений вершин vui - vu2 - vu3 - vu4 - vu5 - vu6. Обратите внимание, что вхождения вершин перечислены без значительного упорядочивания. Именно поэтому две различные модели, показанные на рис. Д.З, имеют одну и ту же структуру в представлении радиальных ребер.

По рис. Д.4 можно заметить, что такие базовые топологические элементы, как грань, кольцо, ребро и вершина, являются избыточными, поскольку вся необходимая информация о них хранится в элементах их вхождений. На самом деле не обязательно иметь прямое представление граней, колец, ребер и вершин как таковых - представления их вхождений достаточно, чтобы указать их положение в модели. Однако с точки зрения системной архитектуры удобнее, когда программисты, использующие операторы для манипуляции структурами данных, имеют дело с более интуитивными понятиями базовых топологических элементов, а не с топологическими вхождениями этих элементов. Это одно из нескольких оправданий для того, чтобы включать в представление такие избыточные элементы, как грани, кольца, ребра и вершины. Это рассмотрение структуры Данных радиальных ребер станет яснее, если вы познакомитесь с детальной реализацией этой структуры в [156].

д./. операторы для манипулирования топологией

Д.2. Операторы для манипулирования топологией

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

u e + (/ r) (V yA +Vc) = C-C„ +СС,(Д.1)

где:

v - количество вершин; е - количество ребер; / - количество граней;

г - количество колец, или отверстий, в гранях;

V - количество замкнутых объемов во всех комплексах, или просто несвязных объектах1;

Vh - количество отверстий, или проходов через объемы;

Vc - количество полостей, или пустот, в объемах;

С - количество комплексов, или несвязных объектов;

С/, - количество отверстий, или проходов через объекты;

Сс - количество полостей, или пустот, в объектах. Выражение (Д.1) можно проверить на модели, изображенной на рис. Д.1, а. В этой модели v = 6, е = 9,/= 5, г= 0, V= 1, Vh = 0, Ve = 0, С = 1, Ch = 0 и Сс = 0. Подстановка этих значений в выражение (Д.1) дает 6-9 +(5-0)- (1-0 + 0) = = 1-0 + 0, что удовлетворяет уравнению.

Мы можем также показать, что формула Эйлера-Пуанкаре, приведенная в уравнении (5.1), является просто частным случаем уравнения (Д.1). Поскольку любой несвязный объект имеет один объем в многообразной интерпретации, мы знаем, что V = С, Vh = Ch и Vc = Сс. Подставляя это в уравнение (Д.1), получаем

v-e + if-r) = 2(V-V„ +VC).(Д.2)

Число оболочек s равняется сумме количества объемов Уи количества пустот Vc, поэтому (Д.2) можно переписать следующим образом:

v-e + (f-r) = 2(s-Vh).(Д.З)

Любой несвязный объект считается одним комплексом, и каждый комплекс может состоять из нескольких объемов и свободных ребер. Комплекс эквивалентен модели в представлении радиальных ребер.

Следовательно, уравнение (Д.З) - это то же самое, что и уравнение (5.1), поскольку г и V/, имеют такой же смысл, что hup в уравнении (5.1).

Когда связь между топологическими элементами в немногообразной модели установлена, как в уравнении (Д.1), мы можем определить минимальный набор операторов, необходимых для манипулирования ими. Поскольку формула (Д.1) определяет плоскость в 10-мерном пространстве с координатами (гл е, /, г, V, Vh, Vc, С, Ch, Сс), имеется 9 независимых базисных векторов. Таким образом, для описания любого объекта в немногообразной топологии достаточно иметь 9 операторов и соответствующих им обратных операторов. Один из возможных минимальных наборов, определенный в [109], иллюстрирует рис. Д.7. Хотя девяти операторов достаточно для создания любого объекта, на практике можно достичь большей эффективности, если добавить еще несколько операторов. Как вы помните, в разделе 5.3.3 мы ввели семь операторов Эйлера, хотя для создания многообразной модели достаточно пяти.

Рис. Д.7. Минимальный набор операторов

Точно так же, как команды моделирования высокого уровня реализованы в системах твердотельного моделирования с помощью операторов Эйлера, команды немногообразных систем моделирования реализуются путем последовательного выполнения соответствующих операторов. На рис. Д.8 показано, как с помощью предложенных операторов, перечисленных на рис. Д.7, создается примитивный параллелепипед. Все прочие команды моделирования реализованы аналогично. На самом деле команды, доступные в немногообразных системах моделирования, выглядят точно так же, как команды обычных системах твердотельного мо-

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

Рис. Д.8. Создание примитивного параллелепипеда с помощью операторов, предложенных Масудой и др.