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

51–60 of 73 posts

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

#51

Post by uecker »

chrisjj wrote: post #43
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.

I really hope nobody computes the volume by rendering in 3D and counting pixels.

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

#52

Post by Joker_vD »

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?

    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.

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

#53

Post by lern_too_spel »

lern_too_spel wrote: post #37

You might be interested in the shoelace formula and its generalization to n dimensions. https://en.wikipedia.org/wiki/Shoelace_formula

For this particular case of 3 dimensions, I found

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

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

#54

Post by diabllicseagull »

MarkusQ wrote: post #45
diabllicseagull wrote: post #26

Earlier quoted context omitted.

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.

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.

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

#56

Post by 12_throw_away »

diabllicseagull wrote: post #54
MarkusQ wrote: post #45

Earlier quoted context omitted.

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.

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.

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.

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

#58

Post by PiXeL161616 »

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…

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.

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

#59

Post by nyeah »

diabllicseagull wrote: post #54
MarkusQ wrote: post #45

Earlier quoted context omitted.

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.

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.

The article relates that this isn't about the state of the art. It's about insight gained while taking a calculus class.

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

#60

Post by ted_dunning »

amluto wrote: post #49
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 wa…

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.

Post reply on HN