Алгоритмы и математические выкладки построения воксельных сеток цилиндрической формы

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

Расчётная сетка, которая состоит из расположенных на листе и скрученных в цилиндр вокселов

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

ИСХОДНЫЕ ДАННЫЕ ДЛЯ ПОСТРОЕНИЯ ВОКСЕЛЬНОЙ СЕТКИ

Имеется лист, на поверхность которого нанесены вокселы (пузырьки, имеющие цилиндрическую форму). Далее предполагается, что вокселы располагаются на листе согласно шаблону, представленному на рисунке 1.

Расположение вокселов. Шаблон

Рисунок 1 – Шаблон расположения вокселов

Читать далее

Перенос граничных условий на ортогональную гексаэдрическую сетку

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

Рисунок 1 – Пример сложной поверхности, как части расчетной области

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

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

Приведем алгоритм, решающий выше поставленную задачу.

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

Читать далее

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

Абстракт

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

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

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

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

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

Читать далее

Методика построения трехмерной геологической модели на основании информации о скважинах

Введение

В настоящее время для планирования и выполнения работ по застройке территорий, проведения экологической экспертизы загрязнений почвогрунтовых сред, оценки залежей полезных ископаемых и др., актуальной является задача построения трехмерной геологической модели. Так, в современных программных комплексах, предназначенных для моделирования в геологии [1-3], существуют различные подходы к решению этой задачи. При этом наиболее часто применяется метод восстановления геологического объекта на основании информации об уровнях залегания геологических горизонтов, полученных в результате бурения [4-6]. Сама реализация этого метода может иметь некоторые особенности.

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

Методика построения

Предложенная методика состоит из 6 основных этапов, описанных ниже. В качестве исходных данных служит следующая информация по скважинам: 1) координаты скважины; 2) отметка устья; 3) мощность геологических горизонтов.

Читать далее

Разбиение отрезка с опциональным сгущением на концах

Предисловие:

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

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

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

Читать далее

Быстрый алгоритм вычисления объёма произвольного многогранника в 3D пространстве

Введение

Вычисление объёма произвольного многогранника в 3D пространстве достаточно нетривиальная задача. Существует тривиальный подход: разбить объём на простые пирамиды и посчитать сумму этих объёмов. Однако эта методика сложная как с точки зрения реализации, так и достаточно ресурсоемкая и медленная. Более того, алгоритм вычисления по данной методике тяжело распараллелить. А с учетом современных тенденций в развитии параллельных вычислительных систем на GPU — теряется возможность многократного увеличения скорости расчета.

Входные данные

Подготовительный шаг. Строится прямоугольная сетка (поз.1 рис.1) вокруг геометрии (поз.2 см. рис.1) используя ее минимальные и максимальные координаты.

Читать далее