As a generalist trying to develop a CAD system using SDF and functional representation, the details of isosurface extraction are interesting to me (if somewhat tedious at times). Researching the bigger picture, tying together the concepts of representation, rendering, analysis, manufacturing, etc. is my rabbit hole.
For those of you that don't know, mkeeter has developed Libfive--a well-regarded project which performs isosurface extraction of implicit functions to triangular meshes--so we can render them with OpenGL or print them on a 3D printer, for example. The implicit functions can be implemented at several language layers, including C, C++, and Scheme.
The author, Mikola Lysenko, is a remarkable engineer. He's wildly prolific, but my favorite project of his is regl[1], which is an unparalleled WebGL library. I think it might be the best-in-class example of all OpenGL libraries, though I have admittedly fallen behind on the state-of-the-art of desktop OpenGL.
Way, way back in university, I wrote “the most copy-pasted code of all time” —-according to the author. But, I’m not actually much of an expert in the subject beyond that :p So, whenever people ask about implementing Marching Cubes, I suggest they check out this article instead.
I implemented a variation on marching cubes for this demo [0] based partially on readings from this author. It mainly handles smoothing of corners so I can still apply textures adequately, not a perfect by-the-book implementation. Very performant in the browser across thousands of vertices. Was very grateful for this work!
(Note: I'm a SaaS company founder, not a game developer, so forgive the rough edges.)
Edit: If you notice lagging, it's actually synchronous Voxel / terrain generation, not the rendering! Never did offload it to a separate thread like I had planned. Built this during the start of the pandemic in a weekend or two.
The second issue is that solving an overdetermined linear least squares problem is much more expensive than taking a few floating point reciprocals, and is also more prone to blowing up unexpectedly when you run out of precision. There is some discussion in the paper about how to manage these issues, but it can become very tricky. As a result, I did not get around to implementng this method in javascript (maybe later, once I find a good linear least squares solver…)
While writing an (honestly probably not very good) implementation in Lua I was facing the same problem. If I understand it correctly the problem is to figure out where to put the vertices so that they end up close to the planes defined by the positions and normals of the neighbouring hermites. I found that I can get a good-enough-for-my-purposes approximation in about 20 lines:
initialize point at center
for i = 1, 8 do
project point onto each plane
point := average of projected points
constrain point to reasonable range
end
That level of detail was really rare at the time and I'm somewhat surprised voxel tech didn't really take off more. I suppose it might be that 3dfx launched a few years after that.
Suggestion: Arxiv and many blog archives encode the year in the URL; you could probably add a 3-line filter that suggests a year in case it’s arxiv or /yyyy/ in the URL when yyyy is in range 2005-$currentyear
Also: thanks for all your work making HN the pleasant awesome forum that it is.
There's a long list of properties that you want your algorithm to have:
- Meshes should be watertight
- Meshes should be manifold
- There should be no self-intersections
- Sharp features (edges and corners) should be reproduced accurately, rather than blurred or bevelled
- Thin features should be preserved (which makes it tricky to sample on a regular grid!)
- The mesh should be adaptive, i.e. having fewer triangles in flat areas
It's relatively easy to get ~3 of these properties, and (last time I checked) nigh impossible to get 5 or 6 in the general case.
If you'd like to read more, Doug Moen has a comprehensive overview of the literature: https://github.com/curv3d/curv/blob/master/ideas/v-rep/To_Me...
I've also written up a 2D study of Marching Cubes (Squares) vs Dual Contouring: https://www.mattkeeter.com/projects/contours/
And a deep dive into the math that lets you precisely position vertexes in dual contouring: https://www.mattkeeter.com/projects/qef