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