PDA

View Full Version : how to compute volume of a set of points in space



blue5teel
06-12-2006, 05:30 PM
Hello.
I am new to Opengl and graphical/geometric algorithms.
How can i compute the volume of a given set of points in space.

Do i have to do a triangulation, compute the volumes of the single tetraeders and unify the results to one big volume ?
Or is there a better approach ?

THX

06-12-2006, 07:22 PM
Your problem statement is underconstrained. What do you me by "a set of points in space?"

For convex polyhedrons, summing tetrahedrons is just fine.

What does this have to do with OpenGL?

blue5teel
06-13-2006, 12:29 AM
Ok, its not opengl-specific.
But where else should i post it ? I need it in my OpenGL-application....

Ok again( Is it so hard to understand ?):

1) You have a set of points
2) You connect them all to an object
3) How can i compute the volume now ?


:|

thx

ZbuffeR
06-13-2006, 01:39 AM
You know, there is a math and algos section here (http://www.opengl.org/discussion_boards/ubb/ultimatebb.php?ubb=forum;f=6) .

Step 2 is non trivial, different valid solutions can exist for the same set of points.

s03 already gave you a good answer. For non convex, split your volume into multiple convex parts.

Flavious
06-14-2006, 02:41 PM
Assuming you can form convex polyhedrons from your points in space, you can calculate the volume of those polyhedrons by selecting a single vertex from the polyhedron as the apex, then forming tetrahedrons with the triangles in the other polygons, one at a time, summing the volumes as you go.

The volume of a single tetrahedron is V = 1/3 * area of triangle * height, which can also be written as V = 1/6 * dot(H, cross(V2,V1)), where H is the vector from polygon point P0 to the apex, apex - P0, and V1, V2 are the vectors Pi+1 - P0, Pi+2 - P0, respectively, with i in [0, n-2) (Pi are the points of the current polygon and n is the total number of points).

Keep in mind volumes can produce some very large numbers so double precision may be advisable depending on the scale of things. You could also simply scale all volumes by a small number to avoid overflow, while still maintaining equivalent relative proportions.

As Zbuffer pointed out, tesselation of the space is probably going to be the hard part of this assignment.