Article “Fast Volume Computing Algorithm…”
Introduction
Computing of the volume of polyhedron in 3D space isn’t a trivial problem, but the following trivial method exists: dividing the volume into simple pyramids and counting the sum of these volumes. However, this methodology is difficult for implementation, as well as it is resource-intensive and slow. What is more, computing algorithm according to this methodology is difficult to parallelize. And taking into account trends in the field of parallel computing on GPU development, the ability to increase the rate of computing repeatedly is being lost.
In this article the algorithm for determining the volume of arbitrary geometry in 3D space in terms of fast computing is described.
Input data
Preparatory step. A rectangular grid (pos.1 on fig.1) around geometry (pos.2 on fig.1) is built using its minimum and maximum coordinates.
User chooses rectangular grid parameters. For example, the number of grid cells can be taken equal to the number of stream multi-processors on GPU. Therefore, our task turns into computing and subsequent summing of the volumes occupied by fragments of geometries in cells, as shown on Figure 2.