## Fast volume computing algorithm of arbitrary polyhedron in 3D space

### 6 responses

1. Vicente Cuellar
13.11.2012

It would be great to discuss practical aspects of the implementation in different architetures, like GPUs for example...

Vicente's comment from LinkedIn: "very nice article, great explanation...it woud be interesting to discuss practical impementation in gpus for example.
Although new nvidia devices allow sort of recursive algorithms, most deveices require a more explicit approach."

• Simmakers
15.11.2012

Hello Vicente!

We intend to apply this algorithm on multi-core processors either on GPUs. Moreover for GPGPU application we usually use Nvidia adapters. Currently we actively test this algorithm; GPU architecture consideration will be later.

2. Carlos Carbonera
18.11.2012

Computing the volume of a polyhedron is a trivial task assuming you have a solid: create a tessellation of the boundary, calculate the volume of the tetrahedron defined by each triangle on the boundary and a fix point in space, add all the volumes, and you are done. This method is very efficient even when you have millions of triangles. I do that all the time. I don't see a need for anything more complicated. If you are concerned about errors there are techniques to improve the accuracy of the summation of the volumes of each tetrahedron.

• Simmakers
19.11.2012

The algorithm that you have already described is post factum "classic" algorithm of calculating the volume of a polyhedron, which is true only for a single object (polyhedron).
Comparison between the proposed "Fast volume computing algorithm "and "classic volume computing algorithm" is the following:
The proposed Fast volume computing algorithm can compute the volume, occupied by a number of intersected polyhedra with the inaccuracy only in those cells in which there is contact of polyhedra faces.
The Opportunities for parallelization of the algorithm is not worse the opportunities of the classic algorithm that you have already described.

Due to the fact that the algorithm was written for solving a particular objective (in our objective it is necessary to operate with the resulting mesh and the volumes occupied by the objects in the cell), then many researchers may be interested in the following: 1) the method of calculating the volume of the cell, not inferior to the "classic" method either in speed or in accuracy, and 2) a considerable amount of "related" information obtained in the course of the algorithm (eg, mesh, triangles cut off by grid cell, etc.).

3. Carlos Carbonera
23.11.2012

With all due respect, this article loosely describes a method to approximate the volume of a polyhedron using voxels; there is no mention on how the technique works on intersecting polyhedra. (If the polyhedra are mutually disjoint what you call classic volume calculation is still valid, and will be much faster than the method proposed here.)

There are no error estimates associated to the error induced by the volume calculation of the cells near the boundary. If the error estimate is simply the sum of the volumes of the cells that intersect the boundary, we are considering a relatively large error.
I cannot think of any application where the volume of intersecting polyhedra need to be calculated without actually calculating the actual intersection or union of the polyhedra. Is there a specific application for the method being proposed?

• Simmakers
10.12.2012

The method described in this article, is used to compute the volume of body intersection in dynamics. You can build three-dimensional cell representations of the simulated objects and then intersect them (deform). Of course, you will get the error, but the error depends on the cells size. This algorithm provides accuracy-speed tradoff with the help of regulation of only one parameter - the cells size. The presence of the "real" amount of cell body allows to use such representation in modeling systems.

mobile desktop