Приложение Г. Пошаговый алгоритм реализации булевской операции

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

1. Вычисляются кривые пересечения всех граней объема А и всех граней объема В; объемы А и В показаны на рис. Г.1. Затем находятся фрагменты каждой из кривых пересечения, лежащие внутри двух граней, которые пересекаются по данной кривой (рис. Г.2). Далее такие фрагменты будут называться ксег- ментами (xegments). Вычисление кривой пересечения между двумя гранями — сложная задача. Однако оно является важным аспектом определения эффективности и устойчивости булевской операции.

Приложение Г. Пошаговый алгоритм реализации булевской операции
 
 
 

Приложение Г. Пошаговый алгоритм реализации булевской операции

 

В зависимости от типов уравнений, используемых для представления каждой поверхности, можно использовать различные методы вычисления кривых пересечения, как описано в главе 7. Кроме того, конечные точки ксегмента находятся по точкам пересечения кривой пересечения с ребрами граней, как описано в главе 6.

2. Ксегменты, полученные на шаге 1, наносятся на соответствующие грани объемов А и В (рис. Г.З). Каждый ксегмент добавляется как новое ребро соответствующей грани каждого объема с помощью операторов Эйлера, так что разделение граней учитывается автоматически. Операторы Эйлера выбираются в зависимости от расположения ксегмента относительно грани, на которую он должен быть нанесен. Есть пять возможных вариантов расположения (рис. Г.4). На рис. Г.4, а изображена ситуация, в которой новое ребро совпадает с существующим; здесь никаких действий не требуется. На рис. Г.4, б два конца нового ребра совпадают с существующими вершинами, но само ребро не совпадает с существующими ребрами; в этом случае необходимо применить оператор MEL На рис. Г.4, в один конец нового ребра совпадает с существующей вершиной, а другой расположен внутри грани; в этом случае применяется оператор MEV. На рис. Г.4, г оба конца нового ребра находятся внутри грани; в этой ситуации мы действуем операторами MEWLS и КРМН. Здесь оператор КРМН преобразует кольцо, созданное оператором MEWLS, в кольцо отверстия, принадлежащее внешнему кольцу грани. Одновременно он устраняет избыточную оболочку, если кольцо, которое преобразовывается в кольцо отверстия, было связано с отдельной оболочкой. На рис. Г.4, д два конца нового ребра связаны с разными кольцами на грани; в этом случае применяется оператор МЕКН. Из этих объяснений мы можем заключить, что каждый ксегмент можно нанести на соответствующую грань каждого из объемов автоматически, если можно автоматически определить его положение по отношению к этой грани. Для этого необходимо проверить, где лежат конечные точки нового ребра: внутри, снаружи или на границе грани. Такая проверка называется тестом на вхождение (in/out test).

Приложение Г. Пошаговый алгоритм реализации булевской операции
 
Приложение Г. Пошаговый алгоритм реализации булевской операции
 

3. Грани объема А классифицируются по их расположению относительно объема В. Иными словами, для каждой грани определяется, расположена ли она внутри, снаружи или на граничной поверхности объема В. Грани объема В классифицируются таким же образом по отношению к объему А.

Классификация требует большого объема вычислений, поэтому мы будем избегать ее, если результат можно вывести из результата для соседних граней. К счастью, группы граней одного обьема могут иметь одинаковое положение по отношению к другому объему. На рис. Г.5 грани, принадлежащие к каждой из групп, имеют одно и то же положение относительно другого объема (то есть грани в группе А1 находятся вне объема В, грани в группе В, находятся внутри объема Л). Эти группы также разделены новыми ребрами, полученными из ксегментов.

Приложение Г. Пошаговый алгоритм реализации булевской операции

Таким образом, грани, принадлежащие группе, можно определить путем обхода соседних граней, начиная с любой грани в группе, без пересечения ксре- бер (xedges) — новых ребер, полученных из ксегментов. Будем искать грани, принадлежащие одной группе, начав обход с грани, которая заштрихована на рис. Г.5. Сначала из всей совокупности соседних граней отбираются только те, которые не имеют общих ксребер с заштрихованной гранью. Затем процедура повторяется: каждая из отобранных ранее граней используется в качестве вторичной начальной грани, и обнаруженные на данной итерации грани добавляются к отобранному множеству. Процесс останавливается, когда каждая грань из отобранного множества побывает в роли вторичной исходной грани. В данном примере будут отобраны грани из группы А1. После этого в качестве вторичной исходной грани будет выбрана любая из граней, не принадлежащих к группе А1; тот же самый процесс будет повторен для нахождения граней, принадлежащих к группе А2. Если какая-либо грань не принадлежит ни к А1, ни к А2, то далее находятся грани группы А3 (которые не  существуют в данном примере). Такой же процесс применяется к объему В, в результате чего получаются группы граней В1 и В2 (рис. Г.5).

После того как грани объемов А и В будут разделены на группы, необходимо определить положение каждой группы граней по отношению к противоположному объему. В качестве примера рассмотрим метод для группы А1. Остальные группы можно обрабатывать так же. Сначала произвольно выбирается одно из ксребер, образующих внешнюю границу группы А1, и обозначается как Xс. (рис. Г.6). Любая из граней группы А1, имеющая Хс. одним из своих ребер, обозначается Fa, а грань объема В, делящая ребро Хс с Fa, обозначается Fb. Затем находятся векторы Na и Nh внешних нормалей к граням Fa и Fb, а также тангенциальный вектор Т в любой точке Хс (рис. Г.6). Тангенциальный вектор Т имеет направление против часовой стрелки, чтобы он был согласован с направлением внешнего кольца La грани Fa при взгляде снаружи. Наконец, классификация группы Л, по отношению к объему В находится из значения (Na Т) ∙ Nb следующим образом. Группа Л, находится вне объема В, если это значение положительно, внутри — если значение отрицательно, и на поверхности объема, если это значение равно нулю. Если выясняется, что группа Л находится на поверхности объема В, она далее классифицируется как ON_ SAME (если Na и Nb имеют одно и то же направление) или ON_OPPOSITE (если Na и Nb направлены противоположно).

Приложение Г. Пошаговый алгоритм реализации булевской операции
4. Группы граней отбираются в соответствии с конкретной булевской операцией. Правила отбора групп определяет табл. Г.1. Мы объясним, как использовать эти правила для операции объединения, а для прочих операций они используются точно так же. Для операции объединения табл. Г. 1 показывает, что нам необходимо отобрать элементы О и О(Х) в столбце «Объединение». Это означает, что мы должны отобрать группы объема Л, находящиеся вне объема В, группы объема В, находящиеся вне объема Л, и группы объема Л, классифицированные как ON_SAME (или группы ON_SAME объема В). Символы О(Х) и Х(О) в табл. Г.1 подразумевают, что элемент объема Л соответствует элементу объема В, и что данный элемент должен быть отобран лишь единожды. Если мы применим это правило к группам граней на рис. Г.5, мы выясним, что для операции объединения будут отобраны группы А1 и В2. Правила для операций разности и пересечения вы можете проверить, применяя их к группам граней на рис. Г.5.
Приложение Г. Пошаговый алгоритм реализации булевской операции
 

5. По результатам, полученным на шаге 4, ненужные группы граней удаляются из каждого объема. Для примера с операцией объединения из объемов А и В удаляются соответственно группы А2 и В1. Форму объемов А и В после удаления ненужных групп граней илюстрирует рис. Г.7. Сложной топологической операции, необходимой для создания объема можно избежать, удалив ненужные группы граней из исходного объема, вместо того чтобы создавать новый объем из отобранных групп граней. Как упоминалось ранее, подходы, изложенные в работах [132, 115], требуют этой топологической операции.

Приложение Г. Пошаговый алгоритм реализации булевской операции
 
В качестве примера рассмотрим удаление группы граней А2 из объема А. Грани группы А2 можно удалить путем уничтожения ребер Е1 и Е2 (рис. Г.8). В общем случае грани, принадлежащие группе, удаляются путем уничтожения всех их ребер, кроме ксребер. Ксребра уничтожать не следует, поскольку они также являются граничными ребрами других групп граней, которые сохраняются. Ребро Е1 удаляется оператором Эйлера KEL, который также объединяет грани F1 и F2 (рис. Г.9, о). Аналогичным образом с помощью оператора KEL удаляется ребро Е2 (рис. Г.9, б). Теперь геометрическая информация, хранимая для грани F1, не имеет смысла, и на следующем шаге используется только информация о ее внешнем кольце.
Приложение Г. Пошаговый алгоритм реализации булевской операции
 
Приложение Г. Пошаговый алгоритм реализации булевской операции

6. Два объема, полученные на шаге 5, склеиваются по общей границе (рис. Г. 10). Ту же процедуру склеивания необходимо применить к другим группам граней при использовании операторов пересечения и разности.

Приложение Г. Пошаговый алгоритм реализации булевской операции
 
Для примера, изображенного на рис. Г. 10, процедура склеивания выполняется следующим образом. Во-первых, определяются восемь пар совпадающих вершин и восемь пар совпадающих ребер, и пара вершин соединяется операторами КРМН и МЕКН. Как объяснялось ранее, два объема будут объединены оператором КРМН и сохранены в одной оболочке. Более того, одно из двух общих граничных колец станет кольцом отверстия для другого в результате применения оператора КРМН. Оператор МЕКН соединяет пару совпадающих вершин путем присоединения кольца отверстия к внешнему кольцу. Оставшиеся семь пар вершин соединяются путем семикратного применения опера- тора MEL (рис. Г.11). Во-вторых, каждая пара вершин, соединенных ребром нулевой длины, удаляется оператором KZEV. Этот оператор применяется восемь раз, поскольку имеется восемь вершин, соединенных ребрами нулевой длины. Обратите внимание, что множественные ребра и вырожденное кольцо до сих пор существуют для каждого ребра, на что указывает жирная линия на рис. 7.11. Наконец, восьмикратным применением оператора KEL удаляются множественные ребра и вырожденные кольца.

Приложение Г. Пошаговый алгоритм реализации булевской операции

7. Далее определяется, имеет ли полученный объем множественные несвязанные оболочки. Этот шаг необходим, поскольку булевская операция может привести к появлению нескольких объемов, что демонстрирует рис. Г. 12.


Приложение Г. Пошаговый алгоритм реализации булевской операции