References on volume surface extraction algorithms

[Zylann]

Marching cubes

Simple, but flawed by ambiguous cases and cannot reproduce sharp features. Also, no specification of how to handle LOD across regions of different detail. Naive implementations often miss out vertex sharing and end up with flat normals, or do it slowly compared to Transvoxel. So later algorithms may be preferred.

Transvoxel

Extension of Marching Cubes with a solution for LOD across regions of different detail. Doesn't handle sharp features, but is a good entry-level candidate for large voxel terrain in a game. A part of this algorithm is implemented in the module already, but misses LOD and texturing. It is now fully implemented and is very fast (no octrees, no hashmaps, vertex sharing is built-in), although texturing uses a different technique than the one described in the paper. Seams handling is nice, but quite annoying to put up in Godot because it requires the ability to manipulate the index buffer very fast (not possible with current API), or multiply even more the amount of meshes (this might be a problem for any meshing algorithm relying on transition meshes).

Dual contouring

Different approach to marching cubes, which handles sharp features, but requires voxel data to also contain normals, or gradient (Hermite data), which is quite a high expectation. It requires more calculations to generate the data (getting derivatives analytically is a big challenge notably for graph generators), and a lot more space to occupy in memory for edited regions. It has inter-cell dependency (cells cannot be evaluated independently) and complexity lies in corner cases. Still need to see how stitching LODs would work there.

https://www.boristhebrave.com/2018/04/15/dual-contouring-tutorial/

Manifold dual contouring

Variant of Dual Contouring. According to @tinmanjuggernaut it would be the best DC variant to implement. https://www.youtube.com/watch?v=l3K-tD3TMqQ&feature=youtu.be&t=514

Cubical Marching Squares

Technique using 2D marching squares and wrapping it back in 3D, claiming to support sharp features by the use of Hermite data but also remove the inter-cell dependency found in Dual Contouring, making it easier to parallelize. Sounds to be a bit more complex. Implementations: https://github.com/mkeeter/kokopelli/blob/master/libfab/asdf/cms.c https://bitbucket.org/GRassovsky/cubical-marching-squares

Dual Marching Cubes

Adaptive extension to marching cubes. The original paper also claims to support sharp features, but implementation in this module only stores a distance field without QEF for speed, so gradients are computed on the fly. https://github.com/Zylann/godot_voxel/issues/15 Currently implemented in the module, but the adaptative part of the algorithm didn't work well, mostly due to use of 8-bit distance field. Remains to be investigated once the module supports 16-bit precision distance field. Texturing is not implemented and wasnt maintained since Transvoxel took over.

Surface nets

https://bonsairobo.medium.com/smooth-voxel-mapping-a-technical-deep-dive-on-real-time-surface-nets-and-texturing-ef06d0f8ca14

Elastic Surface Nets

https://www.youtube.com/watch?v=Rc1ztktWxJs

No Man's Sky

GDC talk from a dev: https://www.youtube.com/watch?v=sCRzxEEcO2Y They use a custom dual contouring with LOD, and they handle seams by simply polygonizing a small distance over neighboring blocks, but using a lower isolevel so they match up with very little artifacts. This seams technique could work with other algorithms, and I tried with Transvoxel, but it resulted very often in Z-fighting with the Godot renderer and a workaround has yet to be found.

[brylie]

The ESN video looks really nice, and would be useful for many types of games. Are you considering implementing any of these? What is the purpose of this issue?

[Zylann]

I make this issue just to list the techniques I've seen, because I'm considering going further and implement one for Godot completely. I've been half-way through Transvoxel 2 years ago but I'm still undecided on which one to take now, as my use case would be a large streamed terrain, and so many people mention they want to make infinite generated worlds^^"

[brylie]

Yeah, open world games are really nice. It would be cool to see more capabilities in Godot to build open world projects, similar to the Grit or Cryengine.

My personal interests are more in the realm of 3D city/transportation simulation (OpenTTD, Cities in Motion, Cities Skylines), where the map has clear boundaries.

What kind of game are you building? Is it open world?

[Zylann]

I don't really have a well defined game in mind, mostly ideas, some of which would involve such large worlds. Being able to generate one successfully would be inspiring, like a planet.

[brylie]

What would the player do, mainly explore, build, evolve life?

My son and I have been playing a bit of Minetest and recently Lego Worlds, which both have good game mechanics.

E.g. it might be cool to use the Stylized Planet Generator and/or Gravity Objects to create an open-source exploration game where you could land a spaceship on a procedural planet and explore.

The Lego Worlds is really cool, in that it provides tools for terrain manipulation and prefab structures to build, as well as vehicles. Minetest servers, like Illuna, have many layers of exploration including space and subterranean, as well as some basic terrain modification and building aspects that are part of the core Minetest game.

[TokisanGames]

Here are some other algorithms that are popular and worth consideration.

Surface Nets

Related to surface nets above, this page discusses surface nets and gives a javascript implementation with some optimizations to the algorithm. He compares the number of faces and speeds between marching cubes, marching tetrahedra and surface nets. The latter is far superior with fewer faces and 2x the speed of marching cubes at high complexity. Also discusses the development of these methods and the transition from primal (marching cubes) to dual methods.

https://0fps.net/2012/07/12/smooth-voxel-terrain-part-2/

Manifold Dual Contouring

According to this video, MDC is considerably faster and more accurate than normal DC, and provides manifold meshes. And Lin provides an implementation in code.

https://www.youtube.com/watch?v=l3K-tD3TMqQ http://faculty.cs.tamu.edu/schaefer/research/dualsimp_tvcg.pdf https://github.com/Lin20/isosurface

Isosurfaces Over Simplicial Partitions of Multiresolution Grids

Generates manifold, intersection-free surfaces. No code, paper only. http://faculty.cs.tamu.edu/schaefer/research/iso_simplicial.pdf

Multiresolution Isosurface Extraction with Adaptive Skeleton Climbing

Faster and fewer triangles than MC, with multiple levels of detail. With code. http://www.cse.cuhk.edu.hk/~ttwong/papers/asc/asc.html

[TokisanGames]

And not a surface extraction algorithm, but a related topic.

Levels Of Detail (LOD)

This link discusses seamless LOD transitions that doesn't use the common chunks, but instead uses a sort of geomorphing technique. https://dexyfex.com/2016/07/14/voxels-and-seamless-lod-transitions/

This guy is using dual contouring and had stitching problems. He found a solution and provided code. https://www.reddit.com/r/VoxelGameDev/comments/6kn8ph/dual_contouring_seam_stitching_problem/

[Zylann]

It should be noted that I currently can't use any technique relying on geometry or tessellation shaders, until Godot gets some support for them.

For stitches I currently use marching squares skirts like the Ogre implementation does, which is actually a good start at the moment. But I have notes to use simple overlaps like mentionned in this video from a No Man's Sky dev: https://www.youtube.com/watch?v=sCRzxEEcO2Y

[TokisanGames]

As I've been looking at porting John/Lin20's C# implementation of Manifold Dual Contouring to Godot, I've been looking at the work of Nick Gildea who was a resource for John doing MDC.

Nick's repositories contain a Dual Contouring with an Octree, Faster DC w/o an Octree, SSE2 QEF solver, Mesh Simplification Library, and a Voxel engine using DC and LOD in C++.

He also has a blog where he talks about his implementation of the above, stitching seams, and a rudimentary OpenCL DC implementation that combines with OpenGL.

[goatchurchprime]

My 2cents: In many of these examples the same structure which defines the surface is also being used to compute the surface.

For example, the description in #123 is of a scalar function f(x,y,z) -> lambda, where f() is defined on vertices of a cubic grid and then it's interpolated for the points in between. However, it uses the same grid to calculate and join (with a triangulated surface) points where f()=0. But there is no reason you have to use the same cubic grid, except that it looks easier to evaluate the f() when you're always starting with a point that you know is on a gridline. But actually, if the first grid was on a different resolution and regular, it would be no bother to find which cell to look up to use for the interpolation of f() at the cost of a floating point division.

Once you separate the two parts from one another, it is then easier to make the calculation grid more sophisticated, for example by allowing for fine or coarse subdivisions, because you don't having to carry the baggage for the evaluation of f() with it. And likewise, you may not need to use a definition of f() that is forced to be compatible with being a calculation grid, and it can take other forms. It's kind of like having a spork, which is not a very good spoon or a very good fork, but is probably the best that can be made if they have to be the same thing.

A while ago I experimented with non-rectilinear subdivisions, which I might have a look at again now. I did a lot of work on CNC machine tool simulation models, where you can think of the model (the f() above) as a massive CSG problem where you are subtracting thousands of swept volumes from a solid cube. This cannot be done using normal CAD methods. See here for example. However, in my book this tech is totally wasted on them, because all they're doing is make simulations of boring engineering parts. It would be far better to build one of these models into a games engine where some actual interesting shapes might get created.

Anyhow, in my opinion, this low level model implementation (transvoxels and whatnot) is just a minor detail. The amazing part is how this works in a games engine in a background thread spectacularly well. I would like to contribute something useful if I can.

[goatchurchprime]

There was a European Geological Modelling meeting in May 2019 where geologists around the continent showed off their hacks, as detailed in the PDF link at the bottom called "5th_EU_3D_WS_Final_Program_Abstracts_20190502.pdf".

Much of it refers to some software called GoCAD and using WebGL, but I did find that the British Geological Survey has made a whole map of Britain in Minecraft which you can download.

I'm going to ask them if they should do it in Godot instead.