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

71–73 of 73 posts

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

#71

Post by uecker »

chrisjj wrote: post #62
uecker wrote: post #51

Earlier quoted context omitted.

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.

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.

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

#72

Post by Sharlin »

calf wrote: post #70
Sharlin wrote: post #12

Earlier quoted context omitted.

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

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