Hilariously fast volume computation with the divergence theorem (2018)(alyssarosenzweig.ca) |
Hilariously fast volume computation with the divergence theorem (2018)(alyssarosenzweig.ca) |
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
https://en.wikipedia.org/wiki/Shoelace_formula#Generalizatio...
The 2-d version is from the 18th century. I'd expect the 3-d version was probably known in the 19th century, but I haven't searched for a reference.
If you have a scalar-valued function that you can conveniently express as the divergence of any closed-form function, you can integrate it like this. And you can generalize beyond scalar-valued functions and beyond Euclidean space using the generalized Stokes’ theorem.
You can even do this in real life: if you want to integrate the electric current density through a surface (that is, measure the total current crossing the surface), you can integrate its anti-curl (is that a word?) around the boundary of that surface, which is what a current transformer or a clamp-on current meter does.
I bet there’s a hydraulic or pneumatic analog as well, but a nontrivial example isn’t immediately coming to mind.
This looks like it requires a dot product with the normal vector for each triangle, but you can expand it into the same form as the article.
A = I + B/2 - 1
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.
To understand why this is so there's this beautiful short video
I = 2 (A - B + 1)
One of my off by one errors is a stupid hacky Monte Carlo intution for Picks theorem.
I count the number of points inside. Now about the boundary points I must assign some fractional weight because they are not fully inside. What's a stupid fraction I can use? Well, half seems about right. Voila,
A = I + B/2.No idea what the author means by "which are equivalent to rendering the mesh and then sampling the render".
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.
Similar formulas exist for moments, to compute the inertia matrix for a rigid body.
Fun fact. The inertia for any rigid body can be represented by 4 point masses forming a tetrahedron. If you diagonalize the inertia matrix, the coordinates of the 4 point masses can be (x, y, -z) (-x,-y,-z) (x, -y, z) (-x, y, z) where x,y,z are easy to calculate (I wrote this all down ages ago). You can also represent any point on the rigid body by its barycentric coordinates relative to those points. I believe an impulse can be applied, by finding the barycentric coordinates of the point its applied and using those coordinates to distribute the impulse to the 4 masses.
This is all really cool with one huge exception. The 4 points become coplanar for large flat objects, which means the z-height is really small for a piece of sheet metal for example.
Are they not reading the entire internet every morning, when they wake up???
Visualization: https://jsfiddle.net/L7r1hwca/
I don't know what they could possibly mean by the naïve algorithms with rendering and sampling (???).
If knowing the volume of a mesh is important, we could pre-calculate it (even using this exact technique) and store it as an attribute on the object. Lots of things in game dev that are modeled as an integral over three+ dimensions tend to work better as a baked setup rather than real time. We kickstarted an entire AI industry trying to chase real time lighting.
Adverb
hilariously (comparative more hilariously, superlative most hilariously)
1. In a hilarious manner; so as to amuse greatly.
Newson, H. B. “On the Volume of a Polyhedron.” Annals of Mathematics, vol. 1, no. 1/4, 1899, pp. 108–10. JSTOR, https://doi.org/10.2307/1967277
I liked getting to the end an find A.R. as the author. It made me appreciate this part of the journey that eventually got us some Asahi Linux graphics.
I must be missing something here, inside joke or something in the title?
b
a c
d
There is the key insight that you don't need to explicitly compute this projection.
The Surveyor’s Area Formula Bart Braden The College Mathematics Journal, September 1986, Volume 17, Number 4.
https://web.archive.org/web/20150406152731if_/http://www.maa...
OP's description vaguely triggered memories of the shoelace formula from a decade ago, but geometry was never my strong suit. All I remembered was positive/negative triangles (or was it trapezoids)? make magic happen for area calculation.
anyhoo, it's always a great skill to review the state-of-the-art BEFORE investing in a work/write-up/article - one of the very first things that a post-graduate program would teach you.
- we are presented something
"I would be (pleasantly) surprised if the algorithm is novel. Further research after posting reveals the paper Efficient Feature Extraction for 2D/3D Objects in Mesh Representation by Cha Zheng and Tsuhan Chen, which appears to describe the same algorithm, although the derivation is different. It was fun while it lasted!"
- there was an initial expectation, though slim, that it may be novel. then on the discovery that it wasn't, related fun time was insinuated to be over.
are we reading the same text?
See, when I was a kid I found something I thought was great and inventive only to find that it was not only long trodden mathematics it was famous long trodden mathematics. I named it after myself for humorous value, the distinction between others who dreamed of finding some novel structure and me being solely that I did not know the famous results and conjectures in the space.
https://wiki.roshangeorge.dev/w/Roshan%27s_Conjecture
I think this is quite entertaining.