Hi everyone,

This is perhaps not a typical post here. I'm an ecologist (previously an electrical engineer) working with the shapes of crowns of trees in tropical forests. I need to calculate the volumes of these crowns, for which I have points describing the surface. There are lots of tools for working with convex polyhedrons (i.e., like you wrap the points in plastic wrap). However, these tree crowns are not convex (e.g., the polyhedron can have inward cuts).

I figured that game programmers would be far more advanced that other communities when it comes to working with polyhedrons. Do you folks have any routines that would calculate the volumes (and perhaps other metrics) of polyhedrons like this? There are indeed algorithms to carry out the calcuations (see a discussion about the topic here: https://math.stackexchange.com/questions/803076/how-to-calculate-volume-of-non-convex-polyhedron/803429), but I'd like to avoid the weeks-long effort it would take to implement such a routine.

If you all have any suggestions, I would be very grateful, and I would surely acknowedge the contribution in any publication that results. If I've posted in the wrong area, my apologies, and I'll be happy to move the discussion to where it belongs.

Thanks very much,

Alex

Alvaro's method does require that your polyhedron is represented as a triangle mesh, but if I understand you correctly, you only have a set of points, which lie on the boundary. This means that before you can use it, you'd have to create a triangle mesh from those points, which is possible, but really quite difficult (search for surface reconstruction from point clouds). If you don't mind using third party libraries, you could use CGAL for this though (see http://doc.cgal.org/latest/Surface_reconstruction_points_3/).

Thanks for the replies. quasar3d is correct - i just have points describing verticies of the polyhedron. However, because of the way I take the points, it's easy for me to reconstruct the triangles (we take points clockwise around the perimeter of the crown, and then take the top and bottom point). I'll give the determinant method a go, and will report back!

So, I'm getting some very strange results. In the results below, "vol" comes from a convex hull algorithm, and poly_vol comes from constructing triangle faces, getting the determinant of each, summing them, and dividing by 6. I assume I should just take absolute value, but I would expect the results to be generally similar (the shapes aren't all that convex), and anyway, the volume of the non-convex shape (poly_vol) should always be less than the convex one (vol), which doesn't seem to be the case.

I'll keep looking into this, but, any initial thoughts? Do I have to make sure all my coordinates are positive, or anything like that?

thanks...

vol poly_vol
1 179.856656 -74.66895705
3 309.408934 -30.86378243
4 49.055692 58.50492336
5 137.396611 -1.22918695
6 104.583539 68.68539370
7 227.369522 65.11191354
8 290.735380 475.99441998
9 82.800011 73.55208137
10 47.755043 -11.14450305
11 133.034612 183.04390294
12 627.933679 -517.44746905
15 62.878588 42.39460754
16 386.673666 629.14455792
17 2.635686 7.17761069
18 281.262214 437.38127061
19 6.360490 22.77254820
20 222.333367 456.47448861

Thanks for the replies. quasar3d is correct - i just have points describing verticies of the polyhedron. However, because of the way I take the points, it's easy for me to reconstruct the triangles (we take points clockwise around the perimeter of the crown, and then take the top and bottom point). I'll give the determinant method a go, and will report back!

You should translate the model to the origin before doing the volume computation for higher accuracy -- if a model is far away skinny triangles with very long side lengths (on the tetrahedron) can mess the results up.

Also be aware that you're summing signed volumes, which means both positive and negative tetrahedrons.

Check out slides 10 and 11 here if you want to understand what's going on with this determinant summing (note that determinant of a 3x3 matrix would be the same as a scalar triple product with the columns): http://www.randygaul.net/wp-content/uploads/2014/02/RigidBodies_WaterSurface.pdf

Furthermore the triangle mesh has to satisfy a couple of criteria for the determinant method to work. It should have closed manifold(s) (e.g. no isolated triangles) and the triangles need consistent winding, i.e. all triangle face normals should point into or out of the volume. Can your mesh generator guarantee that ? Otherwise you need a validation/clean step.

PS: There's probably more which can go wrong topology-wise, I don't know.

I don't think it will work with intersecting triangles either (i.e. self-intersecting volume). In the worst case you can voxelize your mesh and use the total number of filled voxels as an approximation of the volume.