[dead]
Hilariously fast volume computation with the divergence theorem (2018)
21–30 of 73 posts
Re: Hilariously fast volume computation with the divergence theorem (2018)
#22I love these kinds of posts. Simple, fast, AI-free, and I learn something new.
(2018)
Re: Hilariously fast volume computation with the divergence theorem (2018)
#23On 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
A = I + B/2 - 1
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
V_∆ = 1/6 Va ^ Vb ^ Vc.
To understand why this is so there's this beautiful short video
Re: Hilariously fast volume computation with the divergence theorem (2018)
#24Don'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. Visualization: https://jsfiddle.net/L7r1hwca/ I don't know what they could possibly mean by the naïve algorithms with rendering and sampling (???).
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.
Re: Hilariously fast volume computation with the divergence theorem (2018)
#25> 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.
Re: Hilariously fast volume computation with the divergence theorem (2018)
#26Isn'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
Re: Hilariously fast volume computation with the divergence theorem (2018)
#27On 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 A = I + B/2 - 1 This is Pick's theorem 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…
From a computational standpoint, Pick's theorem seems more useful to find the number of interior points via
I = 2 (A - B + 1)
Re: Hilariously fast volume computation with the divergence theorem (2018)
#28I'm sorry, English is my first language. What does "Hilariously" mean in this context? Or is there a maths specific meaning/interpretation?
Re: Hilariously fast volume computation with the divergence theorem (2018)
#29On 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 A = I + B/2 - 1 This is Pick's theorem 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…
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.
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.Re: Hilariously fast volume computation with the divergence theorem (2018)
#30I'm sorry, English is my first language. What does "Hilariously" mean in this context? Or is there a maths specific meaning/interpretation?
The author is just expressing amusement at the surprising simplicity of the resulting algorithm