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

Введение

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

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

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

Читать далее