Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Hilariously fast volume computation with the divergence theorem (2018)

alyssarosenzweig.ca

Post reply on HN
Print view View original

41–50 of 73 posts

Re: Hilariously fast volume computation with the divergence theorem (2018)

#41

Post by sigbottle »

srean wrote: post #33
aaa_aaa wrote: post #7

Earlier quoted context omitted.

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

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. https://web.archive.org/web/20150406152731if_/http://www.maa...

Oh, it is the shoelace formula, but for 3D?

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.

Re: Hilariously fast volume computation with the divergence theorem (2018)

#42

Post by jacobolus »

physicsguy wrote: post #15

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…

This is one variant of the 3-d analog of the "shoelace formula" for area:

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.

Re: Hilariously fast volume computation with the divergence theorem (2018)

#43

Post by chrisjj »

elikoga wrote: post #5

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 t…

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.

Re: Hilariously fast volume computation with the divergence theorem (2018)

#44

Post by MarkusQ »

meindnoch wrote: post #17
xigoi wrote: post #9

Earlier quoted context omitted.

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"

Minus whatever went away inside, unless you're implicitly allowing negative production.

Re: Hilariously fast volume computation with the divergence theorem (2018)

#45

Post by MarkusQ »

diabllicseagull wrote: post #26
eterevsky wrote: post #4

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.

reminds me of that 1994 paper that reinvented the trapezoidal rule

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.

Re: Hilariously fast volume computation with the divergence theorem (2018)

#46

Post by MarkusQ »

ahaferburg wrote: post #34

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.

Closed is clearly important. Why does it have to be simple? It looks like it should handle disjoint components, interior holes, etc. just fine?

Re: Hilariously fast volume computation with the divergence theorem (2018)

#47

Post by MarkusQ »

Isofarro wrote: post #28

I'm sorry, English is my first language. What does "Hilariously" mean in this context? Or is there a maths specific meaning/interpretation?

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.)

Re: Hilariously fast volume computation with the divergence theorem (2018)

#48

Post by seanhunter »

xigoi wrote: post #9
eterevsky wrote: post #4

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.

I wonder if this could be reversed to give an intuitive “proof” of the divergence theorem.

A very intuitive presentation of the divergence theorem is here https://youtu.be/TORt20_HjMY?is=uoJ8-2ToCSwW9rVF

Re: Hilariously fast volume computation with the divergence theorem (2018)

#49

Post by amluto »

physicsguy wrote: post #15

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…

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.

Re: Hilariously fast volume computation with the divergence theorem (2018)

#50

Post by meindnoch »

MarkusQ wrote: post #44
meindnoch wrote: post #17

Earlier quoted context omitted.

The divergence theorem can be intuitively summarized in one sentence: "what comes out is whatever went in, plus whatever was produced inside"

Minus whatever went away inside, unless you're implicitly allowing negative production.

Yes, both "production" and "comes out" are signed quantities.
Post reply on HN