2

I´m searching for a method to calculate the volume of a three-dimensional irregular object in either python or R. I have a time series of files (around 50 per sequence), equally spaced in time. They consist of a triangular mesh representation of the object with a fixed number of triangles. The vertices have known x,y,z-coordinates. There is no need for regenerating the mesh. And no need for visualization. The triangles have indices, the points as well. The object is not necessarily completely convex. But there are no unnecessary points. All known points are part of the hull. Now, I would like to calculate the volume of the object at each time point.

Doc
  • 358
  • 1
  • 4
  • 24
  • The `cluster` pacakge in R has a `volume` function – James Sep 14 '12 at 10:55
  • Hmmm, not really what I´m looking for. The function is restricted to ellipsoids (as far as I can see). And it´s more a point cloud problem, than a statistical one. – Doc Sep 14 '12 at 11:05
  • 1
    Can't you immerse your computer into your bathtub and shout "Eureka!"? – Roman Luštrik Sep 14 '12 at 11:21
  • Kidding aside, this sounds like an interesting problem. What I would do is "slice" the object in one dimension, interpolate points and do a Monte Carlo integration to find the area under the "slice". Sum by all slices and you should get the (normalized?) volume. – Roman Luštrik Sep 14 '12 at 11:24
  • 4
    This sounds similar: http://stackoverflow.com/questions/1406029/how-to-calculate-the-volume-of-a-3d-mesh-object-the-surface-of-which-is-made-up – Bitwise Sep 14 '12 at 11:31
  • @RomanLuštrik I think your "projection" technique would fail if the object is not a convex hull. Think of two dimensions and the letter "C" - it would have the same area as the letter "O". – Hooked Sep 14 '12 at 13:37
  • @bitwise: indeed, it´s pretty much the same problem. Unfortunately, most of the links in that thread are expired. I found this paper, though: http://research.microsoft.com/en-us/um/people/chazhang/publications/icip01_chazhang.pdf – Doc Sep 14 '12 at 13:46
  • @RomanLuštrik: sounds like an interesting solution. I think theoretically You could slice up the object and determine the area of the slice. There are quite a lot hull / polygon algorithms around. But they have limitations even in 3D (like no folding, complex polygon i.e.). But then, the object I have in mind, tends to have molds, which would translate into several polygons within one slice. Therefore , slicing is not optimal. – Doc Sep 14 '12 at 14:36
  • A point cloud is a set of points *without* a triangular mesh associated with it. Since you have a triangular mesh (which is presumably also a closed, oriented surface), you have a *manifold* problem, not a point cloud problem. – comingstorm Sep 14 '12 at 18:31

1 Answers1

1

After some googling I found that this algorithm should do the trick for the closed mesh you are describing: iterate over all your triangles and sum up dot(v0, cross(v1, v2)) / 6 where v0, v1, and v2 are the coordinates of the triangle's vertices.

Source

Artyom
  • 1,599
  • 12
  • 22
  • 1
    I don´t quite get it... what is "cross()" and are v0,v1,v2 the vectors to three vertices of a triangle (like: v0(x0,y0,z0), v1(x1,y1,z1), ...) and what does dot()? – Doc Sep 14 '12 at 15:18
  • If your hull is a closed surface, then this should work as long as your triangles `(v0,v1,v2)` are oriented consistently (e.g., counterclockwise as seen from the outside of the surface). `cross()` is a vector cross product. The formula computes the signed volume of the tetrahedron `(origin,v0,v1,v2)`. Because it is signed, triangles facing toward the origin are subtracted from those facing away from it -- this is why consistent triangle orientation is essential. – comingstorm Sep 14 '12 at 18:28
  • so.. if the origin is inside the structure, the algorithm wouldn´t work, right? And about the boundary conditions: what if the origin is in the plane of the triangle (therefore the normal of the triangle neither facing to or from the origin)? Would the calculation work? – Doc Sep 15 '12 at 17:16
  • Hmmm, no more interest in this little question? I´m still confused about the dot(v,crossproduct) function. And I´m not sure, that the structure is strictly "oriented". Let´s think about something like a torus. Oriented or not? – Doc Sep 17 '12 at 16:03
  • @Doc Like comingstorm said, `cross()` is the vector cross-product. Likewise, `dot()` is the vector dot-product. You can find the definitions of both of these operations on Wikipedia. As far as I can tell, the location of the origin in regards to your mesh shouldn't matter, as it is the relationship between the vertices that matters. I'm not sure though why triangles have to be consistently oriented, since the normals are not used in the calculation, and the signs are determined automatically. If I were you I'd test it on a few simple shapes (that you can easily know the volume of) first. – Artyom Sep 18 '12 at 09:53