There's a really elegant solution using Geometric Algebra, that to this day is one of the most satisfying things I've ever learnt.
Steven de Keninck outlines it in his 2019 Siggraph talk [1].
Hilariously fast volume computation with the divergence theorem (2018)
11–20 of 73 posts
Re: Hilariously fast volume computation with the divergence theorem (2018)
#12Isn'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.
Yes, this is essentially what the author derived (by means of calculus rather than geometric argument but the result is unsurprisingly the same). The 2D analog is easy to grok: to compute the area of a polygon, find the sum of the signed areas of each of the trapezoids formed by an edge and its projection on the x-axis. Turns out the negative areas of the right-to-left trapezoids cancel precisely out any excess area of the left-to-right trapezoids (or in the case of edges below the x-axis, add precisely the "missing" area).
Re: Hilariously fast volume computation with the divergence theorem (2018)
#13Isn'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.
Yep. Using the same kind of calculus ideas, I can also think about a vector field that has a Dirac mass of divergence at some point and zero divergence everywhere else. Then you get an expression that you can sum over faces to determine if a polyhedron contains some point. Again, for the right vector field there is a simple geometric interpretation, namely the solid angle that a face makes with respect to the point.
Re: Hilariously fast volume computation with the divergence theorem (2018)
#14Don't really need vector calculus for this. Geometric intuition is sufficient. It is simply the summation of signed volumes of triangular columns/prisms parallel to the X axis.
Visualization: https://jsfiddle.net/L7r1hwca/
I don't know what they could possibly mean by the naïve algorithms with rendering and sampling (???).
Re: Hilariously fast volume computation with the divergence theorem (2018)
#15This 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: https://calgo.acm.org/550.zip 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
Re: Hilariously fast volume computation with the divergence theorem (2018)
#16My 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 t…
> My belly says the naive formula is summing the triangle pyramid volumes to the origin with sign in orientation.
Yeah, that would also work but it's a slightly slower formula, sum(det(v1,v2,v3))/6. This one is summing sort of prism+pyramid shapes made by projecting each triangle to the yz plane.
Re: Hilariously fast volume computation with the divergence theorem (2018)
#17Isn'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.
I wonder if this could be reversed to give an intuitive “proof” of the divergence theorem.
The divergence theorem can be intuitively summarized in one sentence: "what comes out is whatever went in, plus whatever was produced inside"
Re: Hilariously fast volume computation with the divergence theorem (2018)
#18> (No, there won’t be jokes.)
I must be missing something here, inside joke or something in the title?
Re: Hilariously fast volume computation with the divergence theorem (2018)
#19> (No, there won’t be jokes.) I must be missing something here, inside joke or something in the title?
I assume it's because the title contains "hilariously" and the author felt it necessary to state the content wasn't meant as humorous.
Re: Hilariously fast volume computation with the divergence theorem (2018)
#20Isn'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.
> calculating the volume of a prism-like polytope between it and its projection
There is the key insight that you don't need to explicitly compute this projection.