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

В разделе 5.3.2 мы представляли объем в виде трех таблиц — грани, ребра и вершины. Можно представить себе хранение списков топологических элементов немногообразной модели аналогичным способом. Такой подход, предложенный в [109], иллюстрирует рис. Д.1. Объект, в данном случае пирамида со слоистой гранью и свободным ребром, состоит из объема, соответствующего пирамиде, грани, соответствующей слоистой грани, и ребра, соответствующего свободному ребру. Объем определяется оболочкой, окружающей объект, а оболочка снова определяется списком поверхностей (см. таблицу граней в разделе 5.3.2). Далее, с каждой гранью связаны кольца, и каждое кольцо имеет список ребер (см. таблицу ребер в разделе 5.3.2). Аналогичным образом, каждое ребро имеет список вершин (см. таблицу вершин в разделе 5.3.2). Структура данных, представленная на рис. Д.1, а, представляется весьма компактной и четкой, поскольку она является простым расширением структуры данных на случай немногообразных моделей. Однако эта структура не дает достаточно информации для получения сведений о смежности топологических элементов. Например, при добавлении к модели новой грани (рис. Д.1, а) мы должны выяснить отношения смежности между гранями. Если добавленная грань создает новую оболочку с существующими гранями, необходимо определить эту оболочку и добавить ее, изменив оболочку S1 в структуре данных, показанной на рис. Д.1, б. Чтобы можно было определить оболочку, образуемую гранями, необходимо иметь информацию о смежности граней.

Разработано несколько подходов к описанию немногообразной топологии, в особенности информации о смежности. Наиболее значительная работа была проделана Вейлером, который ввел структуру радиальных ребер для представления немногообразных топологий [156]. В случае многообразных твердотельных моделей информация о смежности хранится в виде двух типов циклического упорядочивания (то есть цикл «грань — ребро» и цикл «вершина — ребро»). Цикл «грань — ребро» — это список ребер для каждой грани или кольца, а цикл «вершина — ребро» — список связанных ребер, сходящихся в заданной вершине. Посмотрев на структуру полуребер и структуру крыльевых ребер в разделе 5.3.2, можно убедиться, что эти сведения о циклах хранятся прямо или косвенно. Между тем, для представления нсмногобразной модели общего вида необходимо задать три типа циклов: кольцевой, радиальный и дисковый. Кольцевой цикл (рис. Д.2, а) соответствует циклу «грань — вершина» в многообразных твердотельных моделях. Радиальный цикл, показанный на рис. Д.2, б представляет собой цикл граней, соединенных с определенным ребром. Эта информация не является необходимой в многообразной модели, поскольку ребро всегда принадлежит двум граням. Однако в немногообразных моделях ребро может одновременно принадлежать более чем двум граням, и они должны быть заданы явно. Дисковый цикл, изображенный на рис. Д.2, в, напоминает цикл «вершина—ребро» в многообразных твердотельных моделях. Однако в немногообразных моделях вершина может иметь несколько дисковых циклов. Например, вершина V на рис. Д.З, а и б имеет три дисковых цикла, каждый из которых принадлежит своей оболочке.

 
 

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

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

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

Представление радиальных ребер, предложенное Вейлером [156], является первым полным немногообразным представлением для моделирования границ, в котором топологическая смежность представлена в явном виде. С ее помощью можно представить радиальный цикл и кольцевой цикл, но она не хранит в явном виде дисковый цикл вокруг вершины. Хотя информация о смежности у вершины в ограниченном числе случаев может быть получена из другой топологической информации, структура радиальных ребер не всегда позволяет получить правильную информацию такого рода из топологических данных. Более того, топологически различные модели, изображенные на рис. Д.З, представляются в структуре радиальных ребер одной и той же топологией. Чтобы обойти эту трудность, в [60] было предложено вершинное представление, с помощью которого можно выразить и дисковые, и радиальные, и кольцевые циклы. Здесь мы опишем только представление радиальных ребер, поскольку прочие представления можно рассматривать как его расширения. Описания других представлений можно найти в [161].

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

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

Теперь поясним, как в структуре радиальных ребер представляются кольцевой и радиальный циклы. Прежде всего, кольцевой цикл задается просто списком вхождений ребер для каждого вхождения кольца. Например, вхождение кольца lu1 на рис. Д.5 несет в себе список вхождении ребер eu1 — eu7 — eu8 — еи9. Для задания радиального цикла каждое вхождение ребра имеет два указателя, указатель сопряженности и радиальный указатель (рис. Д.б). На рис. Д.6 изображен вид сотовой структуры, представленной на рис. Д.5, в поперечном сечении. По рис. Д.6 видно, что указатель сопряженности вхождения ребра — это указатель на вхождение ребра на обратной стороне грани, а радиальный указатель указывает на вхождение ребра, которое принадлежит вхождению грани, смежному в радиальном направлении с вхождением грани заданного вхождения ребра Благодаря этим указателям можно полностью радиально упорядочить грани вокруг ребра, отслеживая указатели от любого вхождения ребра. Как упоминалось ранее, в представлении радиальных ребер дисковый цикл не хранится в явном виде. Однако цикл «вершина-ребро» хранится, как и в многообразном представлении, в виде списка вхождений вершин для каждой вершины. Хранение списка вхождений вершин эквивалентно хранению вхождений ребер, поскольку каждое вхождение вершины связано с вхождением ребра, и поэтому эквивалентно хранению цикла «вершина — ребро». Например, вершина V1 на рис. Д.5 хранит список вхождений вершин vu1 — vu2 — vu3 — vu4 — vu5 — vu6. Обратите внимание, что вхождения вершин перечислены без значительного упорядочивания. Именно поэтому две различные модели, показанные на рис. Д.З, имеют одну и ту же структуру в представлении радиальных ребер.

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

 

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