References on volume surface extraction algorithms about godot_voxel HOT 11 OPEN

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.

from godot_voxel.

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?

from godot_voxel.

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^^"

from godot_voxel.

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?

from godot_voxel.

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.

from godot_voxel.

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.

from godot_voxel.

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

from godot_voxel.

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/

from godot_voxel.

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

from godot_voxel.

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.

from godot_voxel.

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.

from godot_voxel.