Implement Support for Dual Marching Cubes

zauberparacelsus commented 6 years ago

Dual Marching Cubes is an algorithm for meshing voxel data that uses an octree to optimize the mesh, resulting in a mesh that uses less geometry where less is needed. It also (as far as I can tell) supports both smooth and blocky geometry. This would potentially provide better rendering performance compared to transvoxel.

There are two implementations I know of which can be useful to study:

First is this one, which solves an issue with non-manifold geometry sometimes being generated: https://github.com/dominikwodniok/dualmc

The second is the VolumeComponent from Ogre3D, which is more game-oriented and additionally has a LOD mechanism: http://wiki.ogre3d.org/VolumeComponent

Document from volume-gfx.com - https://www.volume-gfx.com/volume-rendering/dual-marching-cubes/

Original paper: https://www.cs.rice.edu/~jwarren/papers/dmc.pdf

Zylann commented 6 years ago

I would tend to prefer a solution with LOD, but I have no dedicated time to work on this at the moment.

zauberparacelsus commented 6 years ago

Well, the implementation in Ogre3D's VolumeComponent does have a LOD mechanism, but yeah, can't work on stuff if you don't have the time for it :-/

Zylann commented 5 years ago

I started investigating this algorithm, but I have a questionning about the way it uses the octree in a top-down way to detect surface features. Let's say you have an empty volume, and the player places a small sphere in the middle:

The algorithm goes by checking the corners of the octree node, and if they differ by some policy, splits the node recursively. But in that situation I can see it won't detect anything, because it starts at the boundaries of the whole terrain, and that sphere is small in comparison. No voxels will be polygonized...

zauberparacelsus commented 5 years ago

Maybe the paper's explanation was vague? I think it's not checking the actual corners, but rather checking to see if there is any geometry within the volume of the cube, and then subdividing.

Though, that portion of the algorithm I think is for voxelizing an existing mesh. For terrain, that probably won't be needed except maybe when the player is digging or building. Generating the terrain from noise or existing data, you'd basically be able to just generate a chunk of terrain data as a 3D array, and build the octree in a "bottoms up" fashion.

Zylann commented 5 years ago

@zauberparacelsus I'm actually not using the paper much, I'm following the explanations from volume-gfx.com (which doesn't use QEF), in parallel with Ogre's implementation and so far that's what I realized from it. So I wonder if indeed a bottom-up construction would make more sense to catch this kind of situation.

zauberparacelsus commented 5 years ago

Yeah, I had been attempting to write a custom voxel algorithm a while back, not going off of references to anything else (so probably a lot of mistakes and way too many ifs). I was using an octree just for storage rather than using it to generate the mesh, though when I was generating the octree I did it purely by "bottoms up" from an input 3D array.

zauberparacelsus commented 5 years ago

One additional thought: I don't know if the algorithm is designed to handle volumes containing multiple materials. Like, if you have a large flat area with nothing but dirt except for one block of stone. Would the algorithm ensure that the single bit of stone was preserved, or would it get optimized out? If the latter, the algorithm might need to be coded to handle volumes with multiple materials.

Zylann commented 5 years ago

@zauberparacelsus my guess is, it will probably have two material IDs and a blend value, and the shader will use a texture array with triplanar sampling. But like heightmap rendering, and due to how Godot rendering works, having two actual materials will be quite hard without splitting the mesh.

Zylann commented 5 years ago

Another thing I'm not used to, is the use of Hermite data. So far my voxels only needed 8 quantified bytes per value, which worked OK with Transvoxel. Now, they need WAY more, like 64 bytes (if using 16-bit floats), for the value and the gradient's X, Y and Z, which appears to not even be a normalized vector. I can still quantify that in 8-bit channels but I'm unsure of the result. I could compute it on the fly, though.

Zylann commented 5 years ago

Ok, that doesn't look too bad for a sphere placed in a corner

zauberparacelsus commented 5 years ago

Oh, by material I hadn't meant in the sense of a 3D shader, but rather in a more conventional sense. Like, dirt, clay, stone, and wood are all different materials in the perspective of the player.

Zylann commented 5 years ago

Got to the stage of deriving the dual grid, using very similar code to Ogre. I have a hunch something isn't right... not sure if that's just the debug rendering or an actual grid problem I submitted my WIP on the dmc branch

Zylann commented 5 years ago

Might have been the debug draw, it wasn't making cubes properly

Zylann commented 5 years ago

Making good progress, finally got a mesh :) But it has holes in it, I don't understand why

Zylann commented 5 years ago

Also, turns out my fear really happens: I found a case where the sphere is larger than a voxel, but small enough to make nothing generate because it doesnt affect corners of the whole volume.

~~For holes, I found they appear in very specific grid locations, no matter where I put the sphere. DualCells don't generate there for some reason, causing 1-voxel size holes.~~ Edit: fixed :)

So here is the current status:

I've got it to "work", but there are several problems with it.

1) I use a constrained 8-bit distance field.

So far, to represent smooth voxel data, I used only 8 bits per voxel to store the isolevel. So in about 2 units of space among the surface normal, it goes from -1 (inside the object) to 1 (outside the object), where the intersection with 0 defines the surface. Any voxel beyond this area will either always be 1 or -1, regardless of how further away they are.

A slice of the volume looks like this: isolevel_4 gradient_4

Pros:

Most of the voxel data will happen to be either -1 or 1, which means it can be compressed very well with RLE
Editing the data can stay relatively local, since changing the isolevel to add a sphere on the terrain only requires to modify voxels around in a distance of 2 units.

Cons:

LOD is probably less straightforward than a true distance field

The problem is, it breaks part of the Dual Marching Cubes approach, which is assuming an actual distance field. For this reason I tried to reverse the way the octree is built. It succeeds at subdividing where the surface is, but it fails to simplify it further than 2 cells. For example, if I give the algorithm a flat plane, it will still generate plenty of quads (regardless of building top-down or bottom-up):

Something to do with the octree's split policy? At this point, having an octree and a dual grid before using marching cubes isn't very useful.

In the case simplification of dual marching cubes isn't good, I don't know how I could go about simplify meshes. I don't have much experience in this area, and if there is an algorithm fast enough for voxel surface extraction, it would need to spare chunk borders so that they can still connect seamlessly etc.

2) If I had to use a true distance field

Pros:

Dual Marching Cubes would work?
LOD becomes simpler

Cons:

I would have at least to double memory required, for example using 16-bit floats to store the isolevel
It would no longer compress well to RLE as the values change all the way to the end of the volume (because it's a distance)
Editing the volume would become much more expensive, because adding even a tiny sphere requires to update the distance to the surface in the whole volume rather than locally. Removing matter would be even worse, in fact I don't even know how to do it properly.

A sparse voxel octree could be used (currently I only have a "sparse voxel" structure), but I'm not sure which approach is best to handle real-time edits across LODs.

So I'm unsure at this point. Is a true distance field really the way to go? How would these concerns would be solved?

Now this mesher is pushed to the master branch, under the meshers/dmc folder. The main routine is found in VoxelMesherDMC::build(). I added several options to choose how adaptivity is done, including disabling it, which then provides regular marching cubes (faster to build, but more polygons).

Zylann commented 4 years ago

I'll close this, as I don't plan to work more on the DMC implementation for now (default got replaced with Transvoxel). More specific issues or PRs can still be opened later.

Zylann / godot_voxel