Smooth Voxel Terrain, Part 2 (2012)

Isosurface extraction is a fascinating rabbit hole to go down (speaking as someone that's deep underground).

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

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.

[1] https://github.com/regl-project/regl

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.

worth mentioning: Eric Lengyel's improved Cube Marching Look-up Tables:

http://transvoxel.org/

weblgl demo using them:

http://art.muth.org/microcosm.html#TorusBox

http://art.muth.org/microcosm.html#SimpleKaleidoscope

code: https://github.com/robertmuth/Microcosm

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.

[0] https://play.sunfall.co/

The author writes:

  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

Here a some results (some meshed noise):

https://i.imgur.com/utCcKYx.mp4

If you want to have your mind blown, take a look at what the 1992 DOS game "Comanche" was doing: https://www.youtube.com/watch?v=MLcxgYEBAXA

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.

Lin has some interesting work in isosurface extraction https://github.com/Lin20/BinaryMeshFitting

I found OpenVDB to be quite a good library for isosurface extraction. It has a very efficient, parallelized implementation.

offtopic: at the bottom of the article he claims he has a WordPress theme that "constantly crashes chrome"? Get on the bounty son!

That demo is oddly satisfying