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

Введение

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

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

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


Геометрическая фигура, помещенная в прямоугольную сетку

Рисунок 1 – Геометрическая фигура, помещенная в прямоугольную сетку

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

Схематическое изображение объёма ячейки (в срезе),который необходимо определить

Рисунок 2 – Схематическое изображение объёма ячейки (в срезе), который необходимо определить

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

Алгоритм определения объёма в ячейке:

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

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

Пример вычисления объёма многогранника как суммы объёмов трёх образующих его пирамид

Рисунок 3 – Вычисление объёма многогранника как суммы объёмов трёх образующих его пирамид

Шаг 3. В зависимости от ориентации нормали частные объёмы входят в сумму с разным знаком (знак скалярного произведения нормали полигона и плоскости проекции рис. 4).

Пример расстановки знаков при вычислении объёма под треугольником

Рисунок 4 – Расстановка знаков при вычислении объёма под треугольником

Шаг 4. Вычислить площадь сечения, образованного верхней плоскостью бокса (параллельной плоскости проекции) и меша (рис. 5).

Пример сечения, образованного верхней гранью бокса и мешем.

Рисунок 5 – Сечение, образованное верхней гранью бокса и мешем

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

Вычисляем площадь сечения (рис. 6) с описанной ниже модификацией.

Алгоритм вычисления площади двумерного полигона.

Рисунок 6 – Вычисление площади двухмерного полигона

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

Пример незамкнутого полигона.

Рисунок 7 – Пример незамкнутого полигона

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

Ребро А

Рисунок 8 – Ребро а

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

На рисунке 9 схематично изображён алгоритм вычисления замыкания на верхнем ребре.

Схема вычисления замыкания и соответственно общей площади.

Рисунок 9 – Схема вычисления замыкания и соответственно общей площади

Ребро разбивается на отрезки и каждому отрезку в соответствие ставится число нормалей. Под числом нормалей отрезка будем понимать число нормалей, направленных от данного отрезка, минус число нормалей, направленных к данному отрезку, причём учитываются только нормали тех треугольников меша, которые имеют ровно одно пересечение с ребром.
Изначально всё ребро образует один исходный отрезок с числом нормалей 0.

В зависимости от чётности числа пересекающих ребро треугольников, внутренние (относительно меша) отрезки ребра могут иметь число нормалей 0 или 1.

В зависимости от реализации предыдущих шагов алгоритма могут возникать некоторые граничные ситуации (рис. 10).

Пересечение треугольника и ребра на отрезке

Рисунок 10 – Пересечение треугольника и ребра на отрезке

Рассмотрим случай, когда треугольник пересекается с ребром на некотором отрезке АВ (больше одной точки пересечения). Необходимо «заблокировать» отрезок АВ от дальнейших вычислений числа нормалей на нём по двум причинам:

• площадь под данным отрезком учтена, т.к. этот отрезок присутствует в списке граней двухмерного полигона;

• невозможно спроецировать нормаль на ребро.

Завершение алгоритма.

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

Если сечение меша с ячейкой есть, то такие ячейки помечаются как занятые.

Далее необходимо промаркировать свободные ячейки как входящие в объём или не входящие. Например, пометить нулем не входящие в объём ячейки или пометить значением величины объёма ячейки, если в объём входит.

Для этого можно использовать один из двух алгоритмов или их комбинацию:

• алгоритм построчного сканирования;

• алгоритм рекурсивного заполнения объёма.

Оба алгоритма достаточно широко освещены в интернете. Суть первого алгоритма заключается в следующем: выбирается произвольное направление (например, вдоль оси OZ). Последовательно выбирается плоскость вдоль выбранного направления (например, плоскость XOY в случае оси OZ). На плоскости построчно сканируется каждая строчка, представляющая собой последовательный набор ячеек вдоль выбранного направления. Маркирование ячеек сводится к выделению пустых до тех пор, пока не встретилась заполненная ячейка. Данный алгоритм содержит много ограничений, которые необходимо рассматривать отдельно (если на строке только 1 ячейка заполнена; если заполнены 2 ячейки, но представляющие собой вершины геометрии и т.п.).

Суть второго алгоритма сводится к выборке любой свободной ячейки и рекурсивному анализу соседей с их последующим добавлением в очередь для выборки. Если соседом является заполненная ячейка, то эта ячейка не включается в очередь для выборки. Как только выбрать соседа уже невозможно, вся выбранная последовательность ячеек отмечается как находящаяся в неком объёме. Выбирается следующая случайная ячейка, и проводятся аналогичные действия. В результате все свободные ячейки маркируются как принадлежащие к определенному объёму. Далее необходимо определить, представляет ли выбранный объём пустоту или заполненность. В этом и состоит сложность алгоритма. Самый простой случай: в ходе рекурсии, как только попадается первая заполненная ячейка или граница объёма, выполняется анализ либо всего этого объём внутри, либо снаружи. Анализ выполняется на базе нормалей треугольников, которые составляют меш в занятой ячейке. Но эта операция трудоемкая и ресурсоемкая.

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

Заключение.

Таким образом, был представлен алгоритм быстрого вычисления объёма произвольной многосегментной геометрии в пространстве. Алгоритм можно использовать, например, для определения объема нефти или газа в месторождении.

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

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

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


*

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