Эффективный алгоритм учета коллизий нескольких геометрических фигур в ячейке гексаэдральной сетки при вычислении их объемов.

Абстракт

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

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

Считается, что такие операции необходимо выполнять в специализированных САПР, таких как Autodesk 3ds Max, AutoCAD, SolidWorks, T-FLEX и др., где применяются специальные приемы для ускорения выполнения булевых операций. Например, строятся деревья иерархий для геометрических объектов, наподобие CSG [1, 2, 3], где новые булевы операции над все более сложными объектами сводятся к системе решений для более простых составных объектов. Явным недостатком подобных подходов является их неприменимость для произвольных геометрий. Поэтому для общих случаев решение булевых операций над произвольными геометрическими объектами является более затратным по времени.

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

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


Булева разность геометрий

Рисунок 1 – Булева разность геометрий

Постановка задачи

Приведем более подробное описание задачи: задана ячейка, ограниченная точками и некоторые геометрические объекты (т.н. “геометрии”) , заданные набором треугольников и их нормалей. Объекты могут пересекаться с ячейкой и необязательно являются полными. Исходные геометрические объекты отсортированы в порядке убывания приоритета. Объекты с более высоким приоритетом “вырезают” пересекаемые ими части других объектов с более низким приоритетом. Необходимо посчитать объемы объектов, над которыми проведены операции булевой разности.

Входные данные: координаты точек , ограничивающие ячейку, и некоторые геометрические объекты , заданные набором треугольников и их нормалей.

Выходные данные: – объемы фигур с учетом булевых операций.

Описание алгоритма

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

Равномерное распыление точек внутри ячейки

Рисунок 2 – Равномерное распыление точек внутри ячейки

Идея алгоритма заключается в следующем: в заданной ячейке равномерно располагаются K точек (рис. 2). Для каждой точки определяются объекты, которым она принадлежит. Среди этих объектов определяется объект с наивысшим приоритетом, к которому данная точка будет отнесена. Далее предполагается, что весь объем, окружающий эту точку, принадлежит фигуре, и итоговый объем i-го объекта приближенно вычисляется , где – число точек, отнесённых к i-ому объекту с учетом приоритетов, V – объем ячейки, K – суммарное число точек.

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

1. Для каждой точки обходим все треугольники геометрии. Находим ближайший треугольник.

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

Время работы такого алгоритма будет , где n – число треугольников геометрии.

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

Алгоритм получения такой структуры данных следующий:

1. Через каждую вершину проводим параллельные плоскости, получив разбиение на слои. Для каждого слоя вычисляем треугольники, которые ему принадлежат.

Разбиение пространства на слои

Рисунок 3 – Разбиение пространства на слои

Введем понятие проецируемой плоскости – это плоскость ортогональная плоскостям, ограничивающим слой.

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

Выделение монотонных последовательностей в слое

Рисунок 4 – Выделение монотонных последовательностей в слое

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

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

Определение принадлежности точки к геометрии

Рисунок 5 – Определение принадлежности точки к геометрии

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

Для нахождения такого треугольника выполним следующие шаги:

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

Определение слоя, в котором лежит точка, двоичным поиском

Рисунок 6 – Определение слоя, в котором лежит точка, двоичным поиском

2. Затем, в полученном слое для каждой монотонной последовательности с помощью двоичного поиска находим треугольник, в проекции которого лежит точка в проецируемой плоскости.

Определение треугольника, в котором лежит точка, двоичным поиском

Рисунок 7 – Определение треугольника, в котором лежит точка, двоичным поиском

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

Получаем итоговую вычислительную сложность определения принадлежности одной точки . Так как на практике – невелико, можно сделать вывод, что данный алгоритм гораздо эффективнее, чем алгоритмы, решающие эту задачу за .

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

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

Преобразование плохого геометрического объекта

Рисунок 8 – Преобразование "плохого" геометрического объекта

Выводы

Таким образом, был представлен быстрый алгоритм вычисления объемов нескольких геометрических фигур в ячейке гексаэдральной сетки с учетом коллизий, возникающих между ними. Было показано, что итоговая сложность алгоритма составляет порядка , где – на практике незначительно, а – управляющий точностью параметр. Это значительно эффективнее, чем алгоритмы, решающие эту задачу за . Несмотря на то, что вычислительная сложность фазы препроцессинга составляет , а с модификацией добавляется ещё и , необходимо учитывать то, что это выполняется лишь один раз, а не для каждой ячейки расчетной сетки, число ячеек которой может составлять миллионы.

Литература

1. Constructive Solid Geometry..
2. Constructive Solid Geometry program. .
3. UnBBoolean. Author: Danilo Balby..

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *


*

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>