Computing Mesh Volume in O(n) with the Divergence Theorem
Hilariously Fast Volume Computation with the Divergence Theorem
This article presents a fast algorithm for computing the volume of a closed, triangulated 3D mesh using the divergence theorem. By choosing a vector field with divergence 1, the volume integral reduces to a sum over triangles, yielding a simple formula that requires only 11n floating-point operations for n triangles. The author benchmarks it against naive methods and notes that a Raspberry Pi could handle 30 million triangles per frame at 60 fps. A postscript acknowledges prior work by Cha Zheng and Tsuhan Chen.
Thus, for a mesh of $n$ triangles, the algorithm requires $8 n - 1$ additions and $3 n + 1$ multiplications, or $11 n$ floating point operations.
- physicsguy
This is one of those when you go "Huh, this is amazing!" or "Huh, I thought this trick was really well known!" depending on your background ;)
Here's a similar impl from 1980 written in Fortran that also computes other properties like centroid:
Algorithm 550: Solid Polyhedron Measures
A. M. Messner and G. Q. Taylor
ACM Trans. Math. Softw., 6(1), Mar 1980, pp.121--130
Keywords: polyhedron, graphics, numerical integration
Language: Fortran 66/77; Shar Index: Z; Gams: P
File size: 19.1 KB;
But Messner published it first in:
A. M. Messner, "A surface Integral method for computer
calculation of mass properties", Paper No. 852, 29TH ANNUAL
CONF. OF THE SOCIETY OF AERONAUTICAL WEIGHT ENGINEERS,
Washington, D.C., May 1970.
I think
- eterevsky
Isn't the same as just taking every triangle from the mesh, calculating the volume of a prism-like polytope between it and its projection on one the planes, and then taking it with a + sign if its projection is oriented in one direction, and with a - sign if it's oriented in another? This kind of formula works based on the basic geometry.
- srean
On the other hand, if you want to compute the area of a polygon that have vertices at lattice points, you can count the number of interior points I, the number of boundary points B. Then the area A is
A = I + B/2 - 1
This is Pick's theorem
https://en.wikipedia.org/wiki/Pick's_theorem
one of my favorite results. It does not generalize as nicely to higher dimensions unfortunately.
If like the post you want the volume of a polyhedron you can use the three dimensional analogue of the shoelace formula (essentially equivalent).
Let Va, Vb and Vc be the vertices of a triangle ∆ of a triangulation of the surface. You need to name the vertices in a consistent order/orientation wrt the origin.
Then the volume V is the sum over all such triangles of the signed volumes
V_∆ = 1/6 Va ^ Vb ^ Vc.
That's the beauty of signed areas and volumes, determinants and exterior algebra.
To understand why this is so there's this beautiful short video
- elikoga
My belly says the naive formula is summing the triangle pyramid volumes to the origin with sign in orientation. It looks like that's what they derived. Which is a generalization of 2d polygon area calculated by summing triangle areas for each edge, I was taught this in a math camp where we calculated map polygon areas on gis data. I remember math knowledge being hard to get pre AI era but I didn't remember it being this hard.
No idea what the author means by "which are equivalent to rendering the mesh and then sampling the render".
- ahaferburg
The emphasis here is on the mesh being simple and closed. Make sure to validate these preconditions before relying on the output.
Similar formulas exist for moments, to compute the inertia matrix for a rigid body.