Системы автоматизированного проектирования САПР CAD/CAM/CAE

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

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

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

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

Теперь поясним, как в структуре радиальных ребер представляются кольцевой и радиальный циклы. Прежде всего, кольцевой цикл задается просто списком вхождений ребер для каждого вхождения кольца. Например, вхождение кольца lu₁ на рис. Д.5 несет в себе список вхождении ребер eu₁ — eu₇ — eu₈ — еи₉. Для задания радиального цикла каждое вхождение ребра имеет два указателя, указатель сопряженности и радиальный указатель (рис. Д.б). На рис. Д.6 изображен вид сотовой структуры, представленной на рис. Д.5, в поперечном сечении. По рис. Д.6 видно, что указатель сопряженности вхождения ребра — это указатель на вхождение ребра на обратной стороне грани, а радиальный указатель указывает на вхождение ребра, которое принадлежит вхождению грани, смежному в радиальном направлении с вхождением грани заданного вхождения ребра Благодаря этим указателям можно полностью радиально упорядочить грани вокруг ребра, отслеживая указатели от любого вхождения ребра. Как упоминалось ранее, в представлении радиальных ребер дисковый цикл не хранится в явном виде. Однако цикл «вершина-ребро» хранится, как и в многообразном представлении, в виде списка вхождений вершин для каждой вершины. Хранение списка вхождений вершин эквивалентно хранению вхождений ребер, поскольку каждое вхождение вершины связано с вхождением ребра, и поэтому эквивалентно хранению цикла «вершина — ребро». Например, вершина V1 на рис. Д.5 хранит список вхождений вершин vu₁ — vu₂ — vu₃ — vu₄ — vu₅ — vu₆. Обратите внимание, что вхождения вершин перечислены без значительного упорядочивания. Именно поэтому две различные модели, показанные на рис. Д.З, имеют одну и ту же структуру в представлении радиальных ребер.

Системы автоматизированного проектирования САПР CAD/CAM/CAE › Приложение Д. Структура данных и топологические операторы для немногообразных систем моделирования › Структура данных