qweqweqe123123

Булевские операторы

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

Если же система твердотельного моделирования использует структуру B-Rep, ситуация оказывается принципиально иной. В этом случае структуру B-Rep исходного тела приходится вычислять по структурам B-Rep исходных тел, к которым применяется булевская операция. Этот процесс называется вычислением границ (boundary evaluation).

Алгоритм вычисления границ был впервые предложен Реквичей и Велкером [132] под названием процесс вычисления и слияния границ (boundary evaluation and merging process) и впоследствии был усовершенствован Миллером [115]. Предлагаемый метод реализуется в три этапа. Для удобства иллюстрирования мы решили воспользоваться плоским рисунком (рис. 5.42), но тот же подход применим и к трехмерным телам. Сначала обозначим две грани (два тела в трехмерном случае), к которым должна быть применена булевская операция, буквами А и Б, а результат операции назовем буквой В (рис. 5.42, а). На первом этапе все ребра А и Б, а также ребра, получаемые пересечением этих граней, помещаются в единый пул ребер. Подмножеством пула ребер, очевидно, являются все ребра грани В. На втором этапе все ребра пула классифицируются по их положению относительно граней А и Б. Любое ребро может находиться, во-первых, внутри, на границе или снаружи грани и, во-вторых, внутри, на границе или снаружи грани Б (рис. 5.42, б). На третьем этапе ребра группируются по их относительному положению в соответствии с применяемой булевской операцией. Заметьте, что для операции «А объединить с Б» нужно отбросить все ребра, находящиеся «внутри А» и «внутри Б» (см. рис. 5.42, б). Аналогичным образом для операции «А пересечь с Б» отбрасываются ребра, лежащие «вне А» и «вне Б». Собранные ребра формируют грань. Для этого в структуру заносятся все необходимые сведения о вершинах, ребрах, кольцах и прочих элементах. Для объемных тел такой подход требует серьезных геометрических вычислений, поскольку требуется опре- делять, где именно находятся ребра, а конструирование структуры B-Rep полу- чившегося тела по собранным ребрам представляет сложную топологическую задачу.

 

Булевские операторы

Чтобы избежать указанных трудностей, Мянтюля [105] предложил алгоритм под названием классификатор окрестностей вершин (vertex neighborhood classifier). Алгоритм Мянтюля работает с отдельными гранями, в отличие от алгоритма Ревичи и Велкера. Гофман, Хопкрофт и Карасик [69] и Чийокура [35] также пред- ложили свои алгоритмы определения границ, основанные на рассмотрении гра- ней. В приложении Г мы предлагаем алгоритм, используемый в SNUMOD, который также основан на подходе к отдельным граням.

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