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

Абстракт

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

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

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

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

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

Читать далее