Hilariously fast volume computation with the divergence theorem (2018)

arn3n

I love these kinds of posts. Simple, fast, AI-free, and I learn something new.

N_Lens

I'll accept any kind of jocularity in the current climate!

eterevsky

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.

elikoga

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 this hard. No idea what the author means by "which are equivalent to rendering the mesh and then sampling the render".

gigatexal

Did they also work on the graphics stack for the Asahi project?

gurkwart

There's a really elegant solution using Geometric Algebra, that to this day is one of the most satisfying things I've ever learnt. Steven de Keninck outlines it in his 2019 Siggraph talk [1]. [1] https://youtu.be/tX4H_ctggYo?t=4795

meindnoch

Don'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 (???).

physicsguy

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, graphics, numerical integration Language: Fortran 66/77; Shar Index: Z; Gams: P File size: 19.1 KB; But Messner published it first in: A. M. Messner, "A surface Integral method for computer calculation of mass properties", Paper No. 852, 29TH ANNUAL CONF. OF THE SOCIETY OF AERONAUTICAL WEIGHT ENGINEERS, Washington, D.C., May 1970. I think

FartyMcFarter

> (No, there won’t be jokes.) I must be missing something here, inside joke or something in the title?

srean

On 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 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. That's the beauty of signed areas and volumes, determinants and exterior algebra. To understand why this is so there's this beautiful short video https://youtu.be/Sv7VseMsOQc

bob1029

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

Isofarro

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

ahaferburg

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.

lern_too_spel

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

OscarCunningham

It's also robust to errors in the mesh. Like if the triangles don't quite join up it still gives a reasonable answer. https://mathstodon.xyz/@keenancrane/109388206643166726

xbar

What a fun post! My vector calculus is rusty so it was a pleasant little derivation. I liked getting to the end an find A.R. as the author. It made me appreciate this part of the journey that eventually got us some Asahi Linux graphics.

hingler36

This appears to be a retelling of another well-known process for volume computation: sum together the signed volumes of the tetraheda formed by each face with the origin (or any other fixed point WLOG). Very cool derivation though!

bmenrigh

At first I was going to say this is just the tetrahedra trick dressed up in slightly different clothes, and some sense it is, but there is a nice cancellation in the y and z coordinates which leads to less calculation in practice.