Article “Fast Volume Computing Algorithm…”

Sep 26, 2012


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.

Geometric figure placed into rectangular grid

Figure 1 – Geometric figure placed into rectangular grid

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.

Read more