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

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

26.09.2012

Введение

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

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

 

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

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

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

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

 

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

Читать далее