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

61–70 of 73 posts

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

#61

Post by ted_dunning »

joelthelion wrote: post #20
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.

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

More correctly, the insight is that this computation is trivial after you expand it.

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

#62

Post by chrisjj »

uecker wrote: post #51
chrisjj wrote: post #43

Earlier quoted context omitted.

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.

Rendering in 2D and summing per-pixel Z-spans. For a finely meshed shape and approx. result, it has by far the lowest cost.

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

#63

Post by diabllicseagull »

nyeah wrote: post #59
diabllicseagull wrote: post #54

Earlier quoted context omitted.

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.

"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?

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

#64

Post by phkahler »

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.

Better still, you calculate the signed volume of the the tetrahedron formed by the triangle and the origin (4th vertex).

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

#65

Post by phkahler »

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.

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

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

#66

Post by arjie »

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.

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.

https://wiki.roshangeorge.dev/w/Roshan%27s_Conjecture

I think this is quite entertaining.

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

#67

Post by georgeburdell »

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…

As an aside, this seems related to the Holographic Principle? It states that the content of a volume is encoded in its surface

https://en.wikipedia.org/wiki/Holographic_principle

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

#70

Post by calf »

Sharlin wrote: post #12
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.

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…

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"?
Post reply on HN