Rendered at 15:39:32 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
physicsguy 1 days ago [-]
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:
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
jacobolus 1 days ago [-]
This is one variant of the 3-d analog of the "shoelace formula" for area:
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.
amluto 1 days ago [-]
This technique should be straightforwardly adaptable to compute arbitrary moments, not just the centroid.
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.
ted_dunning 21 hours ago [-]
The hydraulic analog is that you can weigh a volume of water (which is the same as computing its volume) by adding up the forces on the surface surrounding the water.
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.
georgeburdell 19 hours ago [-]
As an aside, this seems related to the Holographic Principle? It states that the content of a volume is encoded in its surface
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.
Sharlin 1 days ago [-]
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).
calf 16 hours ago [-]
I'm stupid, consider a quadrilateral with points
b
a c
d
Then the area needs to be the trapezoids projected to x axis is ab+bc-ad-dc. What is the correct way to keep track of the signs? I.e. what is the definition of "right-to-left"?
Sharlin 42 minutes ago [-]
Polygon edges are usually considered directed and forming a loop, the edges of said quad being either ab, bc, cd, da (clockwise winding) or ad, dc, cb, ba (counterclockwise winding). They give the same result up to sign, as long as you’re consistent. In the first case ab and bc are left-to-right and cd and da right-to-left, and vice versa in the second case. (Vertical edges of course contribute zero area.) The signed area of a right-to-left trapezoid is automatically negative (if above the x-axis) because the delta-x is negative (eg. a_x - d_x < 0 for the da edge), so there’s no need to worry about whether to add or subtract each individual term.
cgadski 1 days ago [-]
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.
joelthelion 1 days ago [-]
> 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.
ted_dunning 21 hours ago [-]
More correctly, the insight is that this computation is trivial after you expand it.
phkahler 20 hours ago [-]
Better still, you calculate the signed volume of the the tetrahedron formed by the triangle and the origin (4th vertex).
xigoi 1 days ago [-]
I wonder if this could be reversed to give an intuitive “proof” of the divergence theorem.
meindnoch 1 days ago [-]
The divergence theorem can be intuitively summarized in one sentence: "what comes out is whatever went in, plus whatever was produced inside"
MarkusQ 1 days ago [-]
Minus whatever went away inside, unless you're implicitly allowing negative production.
meindnoch 24 hours ago [-]
Yes, both "production" and "comes out" are signed quantities.
Yes, the algorithm and its derivations are elementary and rather obvious for anyone decent at undergraduate level mathematics. But still, I am glad to see more people enjoying math!
aaa_aaa 1 days ago [-]
Yes I remember doing something like that in 90s for a survey/map engineering cad application. After delaunay triangulation, calculating approximate voulume is easy. But this probably is a more general solution
srean 1 days ago [-]
Yes it goes by a couple of names. Surveyor's formula, shoelace formula.
The Surveyor’s Area Formula
Bart Braden
The College Mathematics Journal, September 1986, Volume 17, Number 4.
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.
diabllicseagull 1 days ago [-]
reminds me of that 1994 paper that reinvented the trapezoidal rule
MarkusQ 1 days ago [-]
Except this one 1) didn't try to name it after themselves, 2) explicitly told us it wasn't new, and linked to an example of prior work, and 3) isn't generally taught in high school.
diabllicseagull 23 hours ago [-]
see, when I say something reminds me of something else I don't mean a one-to-one equivalence at every aspect one can think of.
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.
12_throw_away 22 hours ago [-]
Nah. Being able to derive and prove easy results like this for yourself is both way faster and more reliable than trying to wade through the literature to find the equation you want.
nyeah 21 hours ago [-]
The article relates that this isn't about the state of the art. It's about insight gained while taking a calculus class.
diabllicseagull 20 hours ago [-]
"The following presents a fast algorithm for volume computation of a simple, closed, triangulated 3D mesh."
- 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?
arjie 19 hours ago [-]
It’s someone’s blog post before a calculus exam. I think it’s fun to do this stuff. On your own site you can write whatever you want.
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.
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
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
From a computational standpoint, Pick's theorem seems more useful to find the number of interior points via
I = 2 (A - B + 1)
Where area would be calculated using the sum of signed areas of triangles.
srean 1 days ago [-]
Indeed.
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.
elikoga 1 days ago [-]
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".
less_less 1 days ago [-]
> 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.
PiXeL161616 21 hours ago [-]
Voxelising, most likely. The naive way's to rasterise the mesh into a 3D grid and count the cells inside, which really is rendering and then sampling the result. It costs resolution cubed instead of triangle count, and the answer's only ever as good as the grid.
chrisjj 1 days ago [-]
I'd say what author means is the standard solution - which is equivalent to his on triangles but is on pixels ... except there's nothing naive about it and by using GPU parallelism and depth hardware it is lower cost on dense meshes.
uecker 24 hours ago [-]
I really hope nobody computes the volume by rendering in 3D and counting pixels.
chrisjj 20 hours ago [-]
Rendering in 2D and summing per-pixel Z-spans. For a finely meshed shape and approx. result, it has by far the lowest cost.
uecker 9 hours ago [-]
Yes, this makes more sense as you at least collapse the third dimensions, but I would assume this formula is still faster when implemented efficiently.
1 days ago [-]
ahaferburg 1 days ago [-]
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.
phkahler 20 hours ago [-]
>> 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.
MarkusQ 1 days ago [-]
Closed is clearly important. Why does it have to be simple? It looks like it should handle disjoint components, interior holes, etc. just fine?
arn3n 1 days ago [-]
I love these kinds of posts. Simple, fast, AI-free, and I learn something new.
alex_suzuki 1 days ago [-]
(2018)
IAmBroom 1 days ago [-]
OMG, that absolute dummy didn't know something that a human did in 2018!
Are they not reading the entire internet every morning, when they wake up???
alex_suzuki 1 days ago [-]
I was merely pointing out that the post was published in 2018 so AI-free is kind of implied.
meindnoch 1 days ago [-]
Don'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.
I don't know what they could possibly mean by the naïve algorithms with rendering and sampling (???).
nyeah 1 days ago [-]
Yeah, agreed. But words are cheap. It's one thing to say we don't need vector calculus, and another to develop that claim through the actual vector calculus, step by step.
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].
> For a ballpark number, if volume needs to be calculated every frame in a high-performance 60 frames per second application, without the aid of a GPU, only using the CPU capabilities of a $35 Raspberry Pi, around 30 million triangles could be measured every frame.
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.
Isofarro 1 days ago [-]
I'm sorry, English is my first language. What does "Hilariously" mean in this context? Or is there a maths specific meaning/interpretation?
MarkusQ 1 days ago [-]
It's an intensifier. As a native English speaker you should probably be aware that we eventually sand-blast the semantics off of words until they all becomes synonyms for "good", "bad", "very", or "um". (This is similar to what French does to phonemes, but unrelated.)
hallgrim 1 days ago [-]
The author is just expressing amusement at the surprising simplicity of the resulting algorithm
Joker_vD 23 hours ago [-]
Adverb
hilariously (comparative more hilariously, superlative most hilariously)
1. In a hilarious manner; so as to amuse greatly.
The author was greatly amused how quick the resulting algorithm works.
1 days ago [-]
bmenrigh 18 hours ago [-]
At first I was going to say this is just the tetrahedra trick dressed up in slightly different clothes, and some sense it is, but there is a nice cancellation in the y and z coordinates which leads to less calculation in practice.
hingler36 18 hours ago [-]
This appears to be a retelling of another well-known process for volume computation: sum together the signed volumes of the tetraheda formed by each face with the origin (or any other fixed point WLOG). Very cool derivation though!
N_Lens 1 days ago [-]
I'll accept any kind of jocularity in the current climate!
xbar 21 hours ago [-]
What a fun post! My vector calculus is rusty so it was a pleasant little derivation.
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.
gigatexal 1 days ago [-]
Did they also work on the graphics stack for the Asahi project?
StilesCrisis 1 days ago [-]
Yup!
gigatexal 1 days ago [-]
I used to watch their vtuber videos on YouTube!
unkeen 1 days ago [-]
Sadly, there is no way to find out, f.ex. by a quick Google search.
FartyMcFarter 1 days ago [-]
> (No, there won’t be jokes.)
I must be missing something here, inside joke or something in the title?
Agentlien 1 days ago [-]
I assume it's because the title contains "hilariously" and the author felt it necessary to state the content wasn't meant as humorous.
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.
https://en.wikipedia.org/wiki/Holographic_principle
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.
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
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
https://youtu.be/Sv7VseMsOQc
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,
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 (???).
[1] https://youtu.be/tX4H_ctggYo?t=4795
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.
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?
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