PDA

View Full Version : Volume for a closed mesh ??



Mahdy
04-06-2001, 10:32 PM
How can i calculates the volume for a closed mesh ??
Also how can i determine if a point is inside or outside a closed mesh ???
Thanx in advance

Michail Bespalov
04-07-2001, 12:18 AM
Is your mesh convex ?

Mahdy
04-07-2001, 01:29 AM
No...it is irregular !!!
if it is convex, i there a solution ???

mmeyer
04-07-2001, 01:40 AM
Simply take the (signed) volume of each of the tetrahedra formed by the origin and a triangle in the mesh. Add up the volumes, and this will give the total volume.

For more info see our SIGGRAPH99 paper, "Implicit Fairing of Irregular Meshes Using Diffusion and Curvature Flow" at http://www.cs.caltech.edu/~mmeyer/Research/research.html

jwatte
04-07-2001, 07:00 AM
If your mesh is manifold ("regular") you can intersect a line through the interest point and through some other random point that you know is outside the mesh, with all triangles of the mesh. If it intersects an odd number of triangles, the point of interest is inside the mesh.

For the "point outside the mesh" you can use "(max(X)+1, max(Y)+1, max(Z)+1)" where X, Y and Z are the sets of all x, y and z coordinates for vertexes in the mesh.

The trick is figuring out what to do when a point grazes an edge between two triangles, or when it goes through the mesh at a vertex; you have to carefully construct your inequalities to achieve consistency.

[This message has been edited by jwatte (edited 04-07-2001).]

iss
04-07-2001, 06:58 PM
To elaborate on signed volumes, Ron Goldman has published an article in the Graphics Gems Series. You calculate the signed volume using the surface polygons. That is, assuming outward pointing normals (right handed curl) for ordered vertices a,b,c of a triangular surface patch, the signed volume is (1/6)(a x b . c) or a cross b dotted with c. That is, use the coordinate of a, cross product it with the coordinate of b and finally dot this temporary vector with the coordinate of c. As I said with the right handed curl, order counts. The sequence a then b then c should point outside the volume using the right handed rule. Note that the fourth point of the tetrahedral piece is the origin. Now SUM these signed mini-volumes for all the triangular patches of the closed and possibly nonconvex surface. The more general formula presented by Goldman can use surface polygons of more than three vertices. Since the summation of mini-volumes is signed, the origin doesn't have to be "inside" the volume http://www.opengl.org/discussion_boards/ubb/wink.gif

All this really is Gauss's theorem from vector calculus. You can calculate volume properties from surface properties. http://www.opengl.org/discussion_boards/ubb/cool.gif


[This message has been edited by iss (edited 04-10-2001).]

billy
04-09-2001, 05:44 AM
I also would like to know how to calculate a volume from a mesh of triangles. However, I think that the act of adding the volume tetrahedral elements formed by the triangle and the origin would work only for simple shapes.

iss
04-09-2001, 03:40 PM
Let go and use the Force, Luke. http://www.opengl.org/discussion_boards/ubb/smile.gif

The beauty is: It Works for Shapes that are Quite Complex and Non Convex. http://www.opengl.org/discussion_boards/ubb/biggrin.gif Moreover, I validated my implementation of the technique to objects that I imaged and then weighed (knowing their denisty, of course.)

The formulae are derived from physics: for example in calculating the electric field flux through an irregular object. For a simpler analogy, the area under the curve of an arbitrary function can be calculated using thin trapezoids or rectangles. As the rectangles become thinner, the estimated area approaches the true area. For your volume, as the triangles become smaller and more numerous, the volume approaches the true volume.


[This message has been edited by iss (edited 04-09-2001).]

chennes
04-10-2001, 04:59 AM
I can second iss's faith in the signed-volume method - I use it to calculate the volumes of helicopters, which probably don't fit the description of "simple shapes". http://www.opengl.org/discussion_boards/ubb/smile.gif

Chris

Hull
04-10-2001, 03:49 PM
I second it to.

Using calculus fundamentals you will find that iss beautiful solution works for ANY shapes whatsoever.

You can use the same principles for complex spaces like 4d too. http://www.opengl.org/discussion_boards/ubb/eek.gif


[This message has been edited by Hull (edited 04-10-2001).]

billy
04-15-2001, 11:09 PM
Thanks for the tip.

I was using a much more complicated approach to calculate the volume.