Join the discussion
Write your take first — we'll ask for email only when you're ready to publish.
- Hacker News
- I'll accept any kind of jocularity in the current climate!by N_Lens
- > 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.
by bob1029 - 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
- 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].by gurkwart
- Did they also work on the graphics stack for the Asahi project?by gigatexal
- Sadly, there is no way to find out, f.ex. by a quick Google search.by unkeen
- Yup!by StilesCrisis
- I used to watch their vtuber videos on YouTube!by gigatexal
- 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 (???).
by meindnoch - 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.by nyeah
- I love these kinds of posts. Simple, fast, AI-free, and I learn something new.by arn3n
- (2018)by alex_suzuki
- 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.
by ahaferburg - Closed is clearly important. Why does it have to be simple? It looks like it should handle disjoint components, interior holes, etc. just fine?by MarkusQ
- >> 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.
by phkahler - 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".
by elikoga - 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.by PiXeL161616
- 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.by chrisjj
- > My belly says the naive formula is summing the triangle pyramid volumes to the origin with sign in orientation.
Yeah, that would also work but it's a slightly slower formula, sum(det(v1,v2,v3))/6. This one is summing sort of prism+pyramid shapes made by projecting each triangle to the yz plane.
by less_less - 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
This is Pick's theoremA = I + B/2 - 1https://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
That's the beauty of signed areas and volumes, determinants and exterior algebra.V_∆ = 1/6 Va ^ Vb ^ Vc.To understand why this is so there's this beautiful short video
by srean - From a computational standpoint, Pick's theorem seems more useful to find the number of interior points via
Where area would be calculated using the sum of signed areas of triangles.I = 2 (A - B + 1) - 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.by eterevsky
- reminds me of that 1994 paper that reinvented the trapezoidal rule
- Yes, the algorithm and its derivations are elementary and rather obvious for anyone decent at undergraduate level mathematics. But still, I am glad to see more people enjoying math!by gloveone
- Yes I remember doing something like that in 90s for a survey/map engineering cad application. After delaunay triangulation, calculating approximate voulume is easy. But this probably is a more general solutionby aaa_aaa
- Better still, you calculate the signed volume of the the tetrahedron formed by the triangle and the origin (4th vertex).by phkahler
- I wonder if this could be reversed to give an intuitive “proof” of the divergence theorem.by xigoi
- > 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.
by joelthelion - Yep. Using the same kind of calculus ideas, I can also think about a vector field that has a Dirac mass of divergence at some point and zero divergence everywhere else. Then you get an expression that you can sum over faces to determine if a polyhedron contains some point. Again, for the right vector field there is a simple geometric interpretation, namely the solid angle that a face makes with respect to the point.by cgadski
- 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 of the left-to-right trapezoids (or in the case of edges below the x-axis, add precisely the "missing" area).by Sharlin