Главная > Математика > Геометрическое моделирование
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.6. Булевы операции над телами

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

Булевыми операциями называют операции объединения, пересечения и вычитания тел, так как они выполняют одноименные операции над внутренними объемами тел (над множествами точек пространства, находящимися внутри тел). Булеву операцию объединения тел будем обозначать формулой , где — исходные тела, S — результирующее тело. Булеву операцию пересечения тел будем обозначать формулой . Булеву операцию вычитания тел будем обозначать формулой . В порядке следования тел-операндов будем называть их первым телом и вторым телом.

Рис. 6.6.1. Два исходных тела

Рис. 6.6.2. Объединение тел

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

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

На рис. 6.6.1 приведены исходные для булевой операции тела. На рис. 6.6.2 приведен результат операции объединения тел, на рис. 6.6.3 приведен результат операции пересечения, на рис. 6.6.4 и 6.6.5 приведены результаты операции вычитания тел.

Операцию вычитания тел можно свести к операции пересечения тел; для этого нужно вывернуть второе тело наизнанку и найти точки его объема, одновременно принадлежащие и объему первого тела. Вывернутое наизнанку тело S будем обозначать

Рис. 6.6.3. Пересечение тел

Рис. 6.6.4. Разность тел

Рис. 6.6.5. Разность тел

При выворачивании тела наизнанку внутренние стороны граней становятся наружными сторонами, а наружные — внутренними и изменяются направления циклов на противоположные, в результате чего внутренним объемом тела становится та часть пространства, которая до этого находилась снаружи тела. Математически операция вычитания сводится к операции пересечения тел Конструктор при проектировании использует операции объединения и вычитания (они могут называться по-другому, например, операции сварки и сверления), а математический аппарат выполняет соответственно операции объединения и пересечения. Все булевы операции содержат много общего и выполняются по единому алгоритму.

Объединение тел.

Рассмотрим булеву операцию объединения тел. Кратко суть операции можно описать следующим образом: нужно найти линии пересечения граней тел, удалить ту часть первого тела, которая попала внутрь второго тела и ту часть второго тела, которая попала внутрь первого тела, а из всего остального построить новое тело. Операцию условно разобьем на три этапа. На первом этапе построим линии пересечения поверхностей граней и на их базе — новые ребра. Построенные новые ребра будем называть ребрами пересечения, а ребра тел будем называть старыми ребрами. На втором этапе определим точки пересечения новых ребер со старыми ребрами и в этих точках разрежем старые ребра на несколько ребер. На третьем этапе операции перестроим циклы пересекшихся граней. После этого добавим к пересекшимся граням тел грани, топологически связанные ними. Рассмотрим этапы построения тела более подробно.

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

Пусть грани первого тела описываются поверхностями

(6.6.1)

а грани второго тела описываются поверхностями

(6.6.2)

На базе линий пересечения граней первого и второго тел

(6.6.3)

построим ребра пересечения. При этом ребрам пересечения дадим направление векторного произведения нормали грани первого тела с нормалью грани второго тела: Направление ребра определяется признаком совпадения направления производной линии пересечения с требуемым направлением ребра. За положительное направление нормали грани примем направление наружу тела. Нормаль грани может совпадать с нормалью ее поверхности или иметь противоположное направление в зависимости от признака их совпадения. На рис. 6.6.6 показаны направления ребер пересечения грани первого тела с двумя гранями второго тела.

Рис. 6.6.6. Направление ребер пересечения граней тел

Ребра пересечения должны быть построены так, чтобы они полностью лежали внутри циклов граней исходных тел. Ребра пересечения могут подходить к границам грани только своими концами. В точках А, В и С (рис. 6.6.6) старые ребра граней должны быть разбиты каждое на два ребра, так как в результирующее тело войдет только часть исходной грани.

На втором этапе разрежем старые ребра тела, к которым подходят ребра пересечения. Резка старого ребра осуществляется путем рассечения кривой, на которой базируется ребро. Из одной кривой получим две кривые, в совокупности заменяющие исходную кривую ребра. Одна из этих кривых останется геометрическим носителем разрезаемого ребра, а на базе второй построим новое ребро, которое получит от исходного ребра всю необходимую информацию. Как было сказано, каждое ребро строится на базе кривой пересечения поверхностей (6.1.1). Кривую пересечения поверхностей составляют две поверхности и две соответствующие им двухмерных кривые. Рассечению подлежат именно двухмерные кривые на двух разных поверхностях. Как до, так и после рассечения эти кривые должны иметь одинаковые области определения параметров и соответствие точек при всех значениях параметра.

Точки пересечения нового ребра со старым ребром грани ищутся как точки пересечения двухмерных кривых, заданных на общей для них плоскости параметров. От каждого ребра в формуле (4.8.6) точек пересечения линий участвует по одной двухмерной кривой, входящей в линию пересечения.

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

Если разрезаемое ребро базируется на кривой пересечения, заданной отдельными точками (двухмерные линии являются ломаными и точно совпадают в пространстве только в характеристических точках), то прежде чем разрезать такую кривую, нужно в обе линии вставить дополнительные точки, соответствующие точки пересечения трех поверхностей — двух поверхностей, лежащих по обе стороны разрезаемого ребра, и поверхности грани другого исходного тела. Например, если режется линия пересечения поверхностей поверхностью , то в линии нужно вставить дополнительные двухмерные характеристические точки, соответствующие пересечению поверхностей . Задача пересечения трех поверхностей сводится к решению системы шести скалярных уравнений (4.12.5) относительно шести параметров . Начальное приближение решения известно достаточно точно.

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

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

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

Рис. 6.6.7. Исходные грани тела

Рис. 6.6.8. Обрезанные грани

Стрелками показано направление перестроенных циклов граней тел. Каждый цикл представляет собой список ребер в порядке их следования и список флагов ориентации этих ребер в цикле.

Из рисунка видно, что при принятой ориентации ребер пересечения () в циклы граней первого тела они войдут с отрицательным флагом, а в циклы граней второго тела они войдут с положительным флагом.

Старые ребра исходных тел, которые сохранятся в результирующем теле, войдут в перестроенные циклы, сохранив свои флаги. При перестройке циклов пересекшихся граней будем использовать следующий алгоритм.

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

Процесс перестроения цикла грани будем продолжать до тех пор, пока цикл не замкнется. На этом построение очередного цикла заканчивается. Если у рассматриваемой грани при построении цикла использованы не все ребра пересечения, то с любого из оставшихся ребер пересечения начинаем строить еще один цикл грани. Циклы перестраиваем до тех пор, пока не используем все ребра пересечения. Таким способом мы построим в общем случае несколько новых циклов рассматриваемой грани первого тела.

Рис. 6.6.9

Поиск стыкующихся ребер и определение угла поворота в точке стыка удобно выполнять по двухмерным кривым ребер грани. При этом можно работать даже с такими ребрами, которые в пространстве стянуты в точку (например, ребро в вершине конуса или полюсе сферы). На рис. 6.6.9 показано, что с новым ребром В А в точке А стыкуются несколько ребер. В данном случае для продолжения цикла, начатого с ребра пересечения В А, следует выбрать ребро АС.

Вновь построенные циклы рассортируем по группам, каждая из которых состоит из внешнего цикла и входящих в него внутренних циклов. У рассматриваемой грани могут остаться нетронутыми один или несколько старых циклов. Нетронутыми мы будем называть старые циклы грани, ни одно ребро которых не вошло в перестроенные циклы. Среди старых нетронутых циклов отберем те, которые необходимо включить в состав описания перестроенной грани. Ими являются старые внутренние циклы грани, лежащие внутри новых внешних циклов. Еще нужно определить, не потребуется ли включить в результат старый внешний цикл грани, если он остался нетронутым. Это необходимо сделать, если для некоторых новых внутренних циклов не найден новый внешний цикл и они лежат внутри старого внешнего цикла. Сортировку циклов удобно выполнять с помощью двухмерных контуров, соответствующих каждому циклу.

Если в результате сортировки внешних циклов получилось больше одного, то это означает, что из исходной грани в результате операции образовалось несколько граней. На рис. 6.6.10 а - 6.6.13 а приведены варианты исходных граней первого тела.

На рис. 6.6.10 б-6.6.13 б. приведены грани с добавлением ребер пересечения (ребра пересечения выделены). На рис. 6.6.10 в-6.6.13 в приведены грани, которые получились в результате операции.

Рис. 6.6.10. Исходная грань (а), грань с. добавлением ребер пересечения (б), результат операции (б)

Рис. 6.6.11. Исходная грань (а), грань с добавлением ребер пересечения (б), результат операции (в)

Рис. 6.6.12. Исходная грань (а), грань с добавлением ребер пересечения (б), результат операции (в)

Рис. 6.6.13. Исходная грань (а), грань с добавлением ребер пересечения (б), результат операции (в)

На рис. 6.6.10 грань с двумя циклами была разрезана и получилась одна грань с одним циклом. На рис. 6.6.11 грань с двумя циклами дала две грани. В примере, приведенном на рис. 6.6.12, потребовалось использовать старый внешний и внутренний циклы. На рис. 6.6.13 из одной грани получено две грани, причем для одной из них потребовалось использовать старый внешний цикл.

Описанное перестроение циклов выполняется для каждой пересекшейся грани первого тела.

С пересекшимися гранями второго тела поступим аналогично тому, как мы поступили с гранями первого тела, но с одной небольшой разницей. Ребра пересечения должны войти в перестроенные циклы граней второго тела с положительным флагом (в перестроенные циклы граней первого тела они вошли с отрицательным флагом). В этом состоит отличие перестроения циклов граней второго тела. Все остальные действия над гранями первого и второго объединяемых тел одинаковы.

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

Пересечение тел.

Коротко суть булевой операции пересечения тел можно описать следующим образом: нужно найти линии пересечения тел, удалить ту часть первого тела, которая не попала внутрь второго, и ту часть второго тела, которая не попала внутрь первого, а из всего остального построить новое тело.

Эта операция имеет много общего с операцией объединения тел. Вернемся к рис. 6.6.6. На нем приведены пересекающиеся грани: одна грань первого тела и две грани второго тела. Грани режут друг друга, так что в результирующую оболочку войдут только части этих граней.

В пересечение тел войдет часть грани первого тела, лежащая внутри второго тела, и часть грани второго тела, лежащая внутри первого тела (рис. 6.6.14) (в объединение тел вошла часть грани первого тела, лежащая вне второго тела, и часть грани второго тела, лежащая вне первого тела).

Рис. 6.6.14. Исходные грани

Рис. 6.6.15. Перестроенные грани пересечения тел

В этом и состоит основное отличие операций объединения и пересечения тел.

Операцию разобьем на три этапа. Первый и второй этапы операции пересечения тел полностью совпадают с соответствующими этапами операции объединения тел.

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

Разность тел.

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

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

Пересекающиеся ребра.

Наиболее трудоемким и требующим определенной точности в процессе выполнения булевых операций является построение ребер пересечения. Ребра пересечения не должны иметь выступающих за пределы грани частей, они должны обязательно стыковаться или друг с другом или со старыми ребрами граней. При корректном выполнении операции пересечения поверхностей эти условия обеспечиваются. Ребра пересечения не должны пересекать друг друга вне крайних точек.

В большинстве случаев новые ребра не пересекают друг друга, но в некоторых частных случаях это возможно. На рис. 6.6.16 показаны два цилиндрических тела одинакового диаметра, оси которых пересекаются — крест из цилиндров. При булевом объединении этих тел возможна ситуация, когда будут построены всего два замкнутых ребра пересечения. Такие ребра имеют две точки пересечения: А и В, по крайней мере, одна из которых не будет совпадать с вершинами ребер, а будет лежать где-то на ребре. Точки пересечения ребер лежат в точках касания цилиндров. Эти ребра должны быть разрезаны в точках А и В и у их частей должна быть уточнена ориентация, так как при прохождении точки касания поверхностей в данном случае векторное произведение нормалей к ним, по которому ориентируются новые ребра, меняет свое направление на противоположное. Обнаружить пересечение новых ребер можно по пересечению кривых на поверхностях, из которых состоит линия пересечения.

Рис. 6.6.16. В точках А и В нормали граней совпадают

Совпадающие ребра.

Описанный алгоритм выполнения булевых операций работает корректно, если ребра пересечения не совпадают с ребрами исходных тел. В противном случае он нуждается в уточнении. Рассмотрим примеры.

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

Правило для ребер пересечения.

При наличии ребер пересечения, совпадающих с ребрами граней исходных тел, и в некоторых других случаях будем выполнять следующую проверку. Построим в плоскости каждой из двух пересекаемых граней по два вектора, ортогональные ребру пересечения. На рис. 6.6.18 это векторы для грани с нормалью и векторы для грани с нормалью . Векторы поворачивают влево от ребра пересечения в соответствующих плоскостях, а векторы поворачивают вправо от ребра пересечения в соответствующих плоскостях.

Рис. 6.6.17. Совпадение ребер пересечения с ребрами меньшего тела

Рис. 6.6.18. Пересечение граней

Рис. 6.6.19. Пересечение граней по ребру

Если грань не имеет продолже ния за ребро пересечения (ребро пересечения частично или полностью совпадает с ребром тела), то соответствующий вектор положим равным нулю (рис. 6.6.19). Используя векторы и нормали мы можем определить, будет ли данное ребро пересечения использовано в операции или оно должно быть опущено. Обратим внимание на следующее обстоятельство.

В операции объединения тел грань первого тела мы сможем перестроить, еслиона имеет продолжение справа от ребра пересечения вне второго тела, а грань второго тела мы сможем перестроить, если она имеет продолжение слева от ребра пересечения вне первого тела.

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

(6.6.7)

В противном случае рассматриваемое ребро пересечения в булевой операции объединения тел строить не следует (если оно построено, то должно быть опущено).

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

(6.6.8)

В противном случае рассматриваемое ребро пересечения в булевой операции пересечения тел строить не следует (если оно построено, то должно быть опущено).

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

Так как булева операция вычитания тел сводится к операции пересечения тел, то для нее должно выполнятся правило (6.6.8) для вывернутой наизнанку оболочки тела.

Принадлежность точки пространству внутри тела.

Для ответа на вопрос, внутрь или вне тела продолжается от ребра пересечения грань другого тела, нужно уметь определять, принадлежит ли некоторая точка пространству внутри тела — классифицировать точку относительно тела. Нам известно, что нормаль каждой грани направлена вне объема тела. Для точки найдем ближайшую точку на ближайшей грани. Построим вектор из найденной точки в точку . Вычислим нормаль m тела в точке Если точка лежит на границе граней (является точкой ребра или вершины), то в качестве нормали m тела возьмем среднюю нормаль граничащих граней. Если то точка принадлежит внутреннему пространству тела. В противном случае — нет.

Перекрывающиеся грани.

В булевых операциях довольно часто можно встретить случаи частичного совпадения некоторых граней двух исходных тел. На рис. 6.6.20 приведены два тела, некоторые грани которых частично перекрывают друг друга.

Рис. 6.6.20. Совпадающие грани тел

Рис. 6.6.21. Объединение тел

В данном случае не все ребра пересечения граней войдут в булев результат; некоторые ребра должны быть опущены (или не должны строиться). Результат объединения тел приведен на рис. 6.6.21.

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

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

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

Тела с несколькими оболочками.

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

Дерево построения тел.

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

Рассмотренные в предыдущих параграфах тела будем называть простыми, в отличие от тел, полученных в результате операций, которые будем называть сложными. Структура данных простых тел содержит минимум информации, по которой могут быть построены все грани тела. В структуре данных тела, полученного в результате булевой операции, положим структуры данных исходных тел и тип булевой операции. Оболочки тела всегда могут быть построены по этой информации. Таким образом, структура данных тела, полученного в результате многократного выполнения булевых операций, будет содержать дерево построения. Результирующее тело находится в корне дерева, а его ветви начинаются в простых телах.

Пример дерева приведен на рис. 6.6.22. В узлах дерева находятся тела. Дерево имеет несколько ярусов. Операции между телами обозначены соответствующими знаками. Операции выполняются между телами одного яруса.

Рис. 6.6.22. Дерево построения тела

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

<< Предыдущий параграф Следующий параграф >>
Оглавление