Основы САПР (CAD,CAM,CAE) - (Кунву Ли)(2004) (951262), страница 26
Текст из файла (страница 26)
Такие грани появляются, например, при моделировании вбъж-",-"'".;; ных тел со сквозными отверстиями. Простым решением этой проблемы яйдм.",,— ',;- ется добавление ребра, соединяющего внешнюю и внутреннюю,гранигщ:,:-,=':,,з (рис. 5.26, б). В этом случае два списка вершин могут быть объединены. Со-".',,-''-:"'.
единительное ребро называется мостиком или перемычкой (Ьп(йе ет(йв) и ЙтГ": ';, падает в список ребер в двух экземплярах. Рис. В.26. Поверхность с двумя границами и метод их обхода О Количество ребер у разных граней может быть различно (см. табл. 5.1). Вейж'-".:,'- того, невозможно определить заранее количество столбцов (по одному вй ка'. ждое ребро), которые потребуются для конкретной грани, поскольку это ксйличество может меняться в процессе моделирования.
Следовательно, колина- ~~г ство столбцов должно сохраняться в виде переменной в момент объявления таблицы граней. Работа с таблицей переменного размера создает некоторьтв неудобства. О Получать сведения о связности непосредственно из данных, сохраненных-.в трех таблицах, может быть довольно утомительно. Представьте себе поиск двух граней с общим ребром в случае граничного представления тела в тпехт!„"...' таблицах. Придется просмотреть всю таблицу граней, чтобы найти строки;:и" которых присутствует нужное ребро. Если нужно найти все ребра, соелиняюФ; щиеся в конкретной вершине, опять-таки придется просматривать всю табдй" '-'-';=",'; цу ребер. Легко видеть, что при больших размерах таблиц поиск в них стано'',:„:з вится крайне неэффективным.
,, '.1 хностей и кривых, а также координаты вершин называют геометриче'-:" огда как отногоення между гранямн, рсбрамн н вершинами лазы~:.,'-,;!!~! даннылзн. Данные в любой структуре В-Гтер могут быть классифнцнРо",::~-.'г;:;у~ метрические, либо как топологичесхие. бз Е5 Рис. 5.29. Попуребрв рассматриваемого тела 1'ис. 5.27. Двусвязный список грани Е, Рис.
5.50. Двусвязный список полуребер Рис. 5.25. Двусвязный список грани Ез ит)зт~,'~йййй( 5щю~хфффф$йзй . Зтййтуву(зй'4Фи((%%гав;:.."ги(ггтурЫФ":-'ззуйййдийгт"тйзйржзФВ ,ИЗйеэгИКЗЕИНЫЗХ,:щдЗ~ФИМ, При..ООХраНЕИГИГ-ГртПНЧНОГЗ.Прцхстдцзяигвц. ПбгЬЕГМИЗГИ =тпёд,эуо''бзй~уюищра-'типЗу)ззйр (йф-З4е Иаира жгиспгге) и сэтруятзууа вззььгвегзых р'ебер (ач щег(-етую гтага зьисятз) С"г(з)йКг$фи паляжбйр ;-' 'Ц'Кзгчестве средства для борьбы с таблицей граней переменного размера можно „' использовать двусвяэный список', в который помещаются сведения обо всех ,: вершинах данной грани (рис.
5.27). Для каждой грани сохраняется указатель на первое ребро списка, а не весь список, тогда как в структуре каждого ребра име' зпся указатели на предыдушее и последующее ребро того же списка. В результате в таблице граней будет фиксированное число столбцов. Список ребер при '.. этом всегда можно будет восстановить, переходя от одного ребра к другому по указателям (например, список ребер Еь Е, и Е, для грани Е,). Грань Е, может хра.
нить указатель на Ев или Еь но список ребер всегда будет один и тот же. -':.; Однако мы немедленно столкнемся с другой проблемой, когда перейдем к грани ""' Еь которая имеет обшее ребро Е, с гранью Е, (рнс. 5.25). Двусвязный список для грани Ез должен выглядеть так, как показано на рис. 5.28.
По этому рисунку видно, что для ребра Ев последующим является Ет, а предыдущим — Еь Сохранив соответствующие указатели, мы изменим заданные ранее значения указателей, обеспечивавшие ребру Ев место в списке ребер грани Ен то есть фактически разрушим список ребер грани Еи Чтобы решить эту проблему, нужно разделить каждое из ребер на две половинки и использовать каждую из них в списке ребер той грани, к которой она относится. Деление ребра осуществляется таким образом, что его половинки оказываются противоположно направленными (рнс. 5.29).
Для каждой грани сохраняется двусзязный список полуребер, а не обычных ребер. Полуребра каждой грани со,би , ираются в список таким образом, чтобы направление каждого из них согласо- 'Э Эту проблему можно решить н с односвязным списком. Мы выбрали двойной связный 1гбб). список, чтобы получить ту полуребсрную структуру, которую предложил Мянтюля выззлось.
е нзпрзхглепием обхода границ грзнвп.,против часовой.щувлииг,,''*4~фщ-"';,,':.ц';!*; смотреть,.снаружи тела. В результате получаются двусвязные списки полу()зйей::,'.::::-„:!::' для. граней Е, и Ез (рис. 5.30). Теперь никаких проблем, приводящии и рйзруцг5;.,:;.::: "",':.".";,:, нию списка для ребра Еь не возникает. и Для описания граней с внутренними отверстиями без добавления избыточных .;;.— ','. соединительных ребер используются кольца. Кольцо (1оор) — это список ребер, образуюших замкнутую цепочку, так что любая грань ограничивается одним внепг-'.;:,"'",!' ним кольцом и может ограничиваться внутренними', определяющими отве$~,' ';л,:, стия. Теперь каждая грань может ссылаться на список полуребер через кольцо, а не непосредственно.
Другими словами, для каждой грани хранится двусвязнмй, ',,":='! список колец, а для каждого кольца хранится список полуребер. Это поэволя5З' ",';. обрабатывать грани с любым количеством отверстий без добавления мостиков) т~," ' На рис. 5.31 показано, как хранится в памяти грань с отверстиями при помощи колец. Обычно в структуру грани включается указатель на внешнее кольцо, а оно становится первым элементом двусвяэного списка колец.
У каждого коль= па есть список полуребер, направление которых противоположно нэлравленигр внешнего кольца Другими словами, полуребра отверстия помещаются в список ':еу ' Внешнее кольцо и кольца отверстий называются также родительским (рагеят (оор) и до" черними кольцами (сйЫ моор) соответственно.
г П- Га~"~~' ~ГФФ~~Щ' .Ф~~ М'-'НФ$ ВВЛгиьуп' СОВП~~Е-,' 11адчуайЛВИИЕДГ ',бхай'ы „," ' ' "- й" РЕДКА'вс и Р ёФкгг евж На рис. 5;31 "ппвуреб й -кольца Х,; обходятся против часовой стрелки (это 'кольцо внешнее), а цолуребра колец Ет и Ез — по часовой стрелке (эти кольца внутренние). е 'ш шива .Ф'. является нэчвпвепай ввршиа11йб1 (п.иашеь~~Фча~~ ®в~7~)':;: ?я т 1 ыбирается полуребро, предп(ествующее ггг'(ргеч ь1)г а его Родггуед ребро оказывается одним из нужных нам ребер, соединенных с У~.
Теперь'меб: и шаг 1 повторяется. Если Р, — конечная вершина Аь выбирается полуребрц следующее за Ьи а его родительское ребро считается одним из падхбдящьцг к вершине. Затем вместо й! берется полуребро, сопряженное со следовавшим за Ьь и шаг 1 повторяется с полуребром пеуу П1. 2, Процесс повторяется до тех пор, пока не будет достигнуто полуребро, сопряженное с исходным Аь Рис. 3.31. Описание грани с отверстиями при помощи колец Последовательность обхода полуребер отверстий противоположна последовательности обхода палуребер внешнего кольца для того, чтобы сохранить информацию о внутренней и внешней сторонах грани.
Направления обхода выбраны таким образом, чтобы внутренняя часть грани всегда была по левую сторону при .обходе любого кольца в соответствующем направлении. Структура данных с полуребрами и кольцами имеет множество преимуществ перед структурой с таблицами вершин, ребер и граней. В структуре с полуребрами и кольцами можно сохранять данные о связности вершин, ребер и граней и по , . этим данным получать сведения о смежности. Мы уже показали, что получить такие данные по исходной простой таблице — задача непростая. Однако благодаря полуребрам и кольцам в структуре сохраняются сведения о связности вершин, ребер и граней, и тогда задача упрощается.
Вершины, ребра и грани указывают на соответствующие полуребра и кольца, для которых сохраняются сведения о смежности. Чтобы обеспечить связь между ребром и его полуребрами, для каждого ребра сохраняются указатели на соответствующие полуребра, а для полуребер — указатели на родительские ребра. Аналогичным образом, для каждой вершины сохраняется указатель на одна из полуребер, исходящих из нее, а для каждого полуребра сохраняется указатель на его начальную вершину'. Для грани сохраняется указатель на внешнее кольцо, а для кольца — указатель на родительскую грань (см. Рис, 5.31). Сведения о смежности колец и полуребер сохраняются естественным способом (каждое кольцо представляется в виде двусвязного списка полуребер).
Покажем, как можно получить информацию о смежности вершин и ребер из сохРаненной структуры данных, чтобы продемонстрировать наличие в структуре всей необходимой информации. Например, попробуем найти все ребра, исходящие на вершины Р1 (рис. 5.32). Поиск начинаегся с полуребра, указатель на которое сохранен в вершине. Это может быть любое полуребро из тех, что соединены с данной вершиной. Обозначим его Ь, (см. рис.
5.32). Процедура поиска будет выглядеть следующим образом. 1 Вершина полуребрв считается начальной илн конечной в соответствии с направлением этого полуребра, Рис. 3.32. Получение данных о смехпосги ребер и вершин Реализация структуры данных полуребер представлена в приложении А. Струк- данных, используемую в системе твердотелыюго д ро туру данн азработаннай Мянтюля 11061, демонстрирует листинг А.. .1.
В книге (1061 ас1 р разра т н " сказывается а некоторых дополнительных указателя . х. В некого ых случаях ока- Р зывается выгоднее сохранить избьпочные указател, тели, чем вычислять их заново, особенно если выполнять это при пришлось бы часто. Количество и назначение из- быточных указателей должны планироваться в процессе проектирования струк- . Р ция процедуры поиска всех ребер, исходягпих из конкретистинге А.2. ной вершины, на предлагаемой структуре данных, представлена в листинге Структура крыльееых ребер ребе редставляет собой список граней, каждой из которых со- Ст а полуребер предст ответствует двусвязный список ребер.
В этой структуре главная роль в описании объемного тела отводится граням. В структуре крьиьееых реб ( 'щ,' - д мгпсгиге) главная роль, напротив, отводится ребрам. Для каждого ребра сохраня- ется список гранеи, которым оно принадлежит, рнер, , рЖе, с которыми оно имеет об- щие вершины, и вершин на его концах. Список ребер д, д " гр ребе тя каж ой грани не сохра- няется в структуре в явном виде, поскольку он может уч быть пол ен анализом любого ребра грани и соседних с ним ребер.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
