New Tool: Dual Contouring voxels and terrain in Unity

I want to share a new asset I've been working on:
a Dual contouring package for Unity!



Demos
Play a test-bed, sand-box of it here!
and a fully deformable terrain world using Dual Contouring here.
Also a cubical, blocky world for all the Mine-craft fans.


Why would you want this?
Dual Contouring (D.C.) is one of a number of algorithms for extracting surfaces from scalar data sets. This makes it great for creating procedural objects or terrain where you want to modify them dynamically in generic ways (like blow a hole in a tank/wall/building/world/etc.) Marching Cubes (M.C.) is available in several packages for Unity currently (I would point you to my own package: Ruaumoko as an example). Despite "voxel" becoming synonymous with Mine-Craft like games it is in fact merely a data format and MC is actually really bad at making cubes (it loves to smooth them over). DC is much better, and the cubes don't need to be oriented along the primary axes of the world!
Here's an image that shows the difference in functionality between M.C. and D.C.:



The upper-right is what Cubes do and lower-right is what Contouring does. Basically it tries to honor sharp angles even if they fall into the center of a voxel.

My implementation is all in C# so it will run fine in Unity Indy! I'm planning on releasing it on the asset store once I've wrung the bugs out and worked on as much optimization as possible.

Below are a couple images of the same blocks rendered with Cubes and Contouring (from the demo).

Marching Cubes:

Dual Contouring:


The differences are subtle but distinctive. You can see how the DC likes to make flat sides in some places where MC chops them off (and the shader stretches badly on the flat walls).

 

this seems really cool, but ya know what could set it apart more - when chunks become separated, have gravity take effect, and drop it to the ground! I bet that's not easy with voxels defining these shapes... which is what probably causes that floating effect in tons of voxel engines I've seen. Anyway, nice project keep it up!

 

Updated the demos because I found a glaring bug. The "cube" cutting tool was leaving rounded edges, totally failing to show off the features of Dual Contouring. Doh!

MD_Reptile: agreed. The floating chunks should really fall but requires another algorithm to continually scan the voxel data for physical integrity. I might take a stab at it!

 

Second link doesn't load properly for me. The first demo is working fine though.

-Dane

 

remove the s from https://

 

Any chance that you share some source code? For example code of Dual Contouring?

 

mmm..... pyramids

So would this allow me to cut a rounded surface tunnel then halfway through the tunnel I could change settings begin to square off the corners of the tunnel ? ( I guess I should simply try the demo

Q. is it possible to sculpt an object and then detach that object from the terrain ? A bit like a sculpting a product from clay then placing it where he/she wished.

 

word up, y'all: I've posted the D.C. package to the asset store. It'll include all the code. Here's the latest demo.

Play with the "smoothness" Banksy, it should get what you want (or you can just switch between "sphere" and "cube" as the tool shape and sculpt your tunnel with/out edges!) The detaching is not included, unfortunately.

I'll post when I see the package is live!

 

Many of your webplayer links don't work (or possibly they only work for you?). The ones which don't work seems to be fixed by removing the 's' from 'https'. Also, after a couple of minutes the latest demo gave an error box saying "Fatal error in gc" and "Too many heap sections".

Apart from those issues it's interesting stuff. I've never worked with Dual Contouring but I have heard it has some interesting properties, so I'll be interested to see where this goes.

 

I'm interested in this. Any idea when this gets released and for what price?

 

hi that and your other one are both amazing

also i just tried the dc one which just got released on asset store and it crashed bigtime the webplayer. i had to logoff nothing else would work!

basically i put pointed right next to me and press build (not dig) and it was sort of stuck in the build and it went off with heap error and everytime i closed the dialog a new one would come up. task manager was of little use since when you brought it up that heap dialog was modal too on top of task manager! ouch

thankfully ctrl+alt+del worked with logoff!

also the demo has other issues with build/dig right next to player it mostly does not work. i wonder if its cause of the bug. its should since right now u have to be at a bit of a distance normally at least. sometimes it works like above but most it just ignores you.

still amazing.

also change from use of mouse only have a key to build and one to dig. the right mouse click keeps bringing up unity3d webplayer context menu for full screen, etc real pain.

 

I just got an error in the Web Player (in Chrome) and had to restart as well.

It said something like:

"Error in gc
Too many heap allocations."

 

Is the shader stretching in the flat areas in the DC version just an issue with bad UV's or some more substantial issue?

Looks good!

 

Just saw this while researching dual contouring. In your demo it's not too hard to find the edges where the granularity changes and this creates gaps in the triangles. I thought DC was guaranteed to be water tight. Other than that I have to say congrats. The implementation is non-trivial and you have a nice example. I'm very surprised it hasn't been more talked about. DC is like marching cubes on steroids.

no to mention your price is roughly 1/100th of a competing product.

edit**

your demos aren't doing the technique justice man. You've done the tough part, may consider spending a bit of time on the showcasing part.

 

Great package! Are you still updating this asset? or are you focusing on the full package? Btw, did you get my PM?

Thanks

 

Apologies thread, for the delay in response!

@jmatthews: thanks for checking it. I agree that the demos are weak–I spent so much time on the implementation I ran out on the demos. But I'll give it some thought. The current problems (where you can see the "leaks") result from normals being interpolated out of the voxel data in a way that can result in vertex mis-alignment when sharp edges occur between mesh objects. I believe a solution can be found to clean that up.

@sebbn: yes, it's still being updated. There just haven't been any changes to the core in a while! I'd like to think the lack of bug reports is a good sign...

 

Hi Bens,
I recently bought this asset and was wondering if you could help me figure out what format the desntiyMap should be when using the March(float[]....) signature (non-static).

Is it implied x,y,z,x,y,z,x,y,z. Or x,x,x,x,y,y,y,z,z,z? Or am I misunderstanding it?

I haven't tried with the float[][][] signature yet (I assume that is [x][y][z] from what I have read of the code).

I'm generating my own density maps and just need to stick it in somewhere. For quick results the "ref Mesh" suited me, but if you think it's better to just go the float[][][] route then I'll take a deeper look.

Also: Are you on twitter?

Cheers,
Martin

 

Ya know I was thinking of this and before I start lemme say I have only scratched the surface of using voxels and or point cloud data, but I thought wouldn't it save resources to only check for "physically seperate" chunks after something has effected the worlds geometry (player blast off one end of bridge, then the other end, two checks of a local area for seperations) and that way it doesn't constantly check for them universally (or even local to the player position) and instead only checks it in small chunks near wherever has been edited (blown up/digging whatever)

Anyway those are my thoughts haha, could be something already well thought out and I am wasting my brain energy

 

@bens1984
Further to this, I seem to get an out of bounds error when I use the no-arguments method like so:

Code (csharp):

1.  
2.         Mesh mesh = meshFilter.mesh;
3.         DualContour meshGen = DualContour.Singleton;
4.        
5.         // Empty Signature style
6.         meshGen.SetDensityMap(jaggedVoxels);
7.         meshGen.GutterSize = 0;
8.         meshGen.March();
9.         meshGen.UpdateMesh(mesh);
10.         TangentSolver.Solve(mesh);
11.         meshFilter.mesh = mesh;
12.  

Which errors on:

Code (csharp):

1.  
2. protected static int GetVertIDForEdge(Triplet[][][] vertIDs, int x, int y, int z, int edge) {
3. ...
4. Triplet output = vertIDs[x + MCTables.edge_start[edge]][y + MCTables.edge_start[edge+1]][z + MCTables.edge_start[edge+2]];
5. }
6.  

After rearranging the code a little I found it to be caused by the Y value going too high when the initial values are 0, 6, 30 edge=9; Giving vert lookup values of: 0, 7, 30.

The call previous to the failing one used the same initial XYZ but for edge 8, no error; It produced vert lookup values of 0, 6, 30 (matching the initial XYZ values).

Could this be because my voxel data is not cubed? The jagged array is float[21][7][34].
As you can see guttering is set to 0.

Rearranged code to get these values if it helps:

Code (csharp):

1.  
2. protected static int GetVertIDForEdge(Triplet[][][] vertIDs, int x, int y, int z, int edge) {
3.             //Debug.Log (x + "," + y + "," + z + "," + edge + "," + vertIDs.Length);
4.             Triplet output;
5.             edge *= 4;
6.             int xVal = x + MCTables.edge_start[edge];
7.             int yVal = y + MCTables.edge_start[edge+1];
8.             int zVal = z + MCTables.edge_start[edge+2];
9.             Debug.Log(
10.                 "Try to access "+(xVal)+" "+(yVal)+" "+(zVal)+
11.                 " vertIDs len"+vertIDs.Length +
12.                 " inital vals "+x+","+y+","+z+" edge: "+(edge/4)+" now "+edge);
13.  
14.             try {
15.                 output = vertIDs[xVal][yVal][zVal];
16.             } catch(Exception e) {
17.                 // Recreate so we know exactly which is erroring
18.                 Triplet[][] xVerts = vertIDs[xVal];
19.                 Triplet[] xyVerts = xVerts[yVal]; // Errors here
20.                 Triplet xyzVerts = xyVerts[zVal];
21.                 Debug.Log("OUT OF BOUNDS for "+x+","+y+","+z+" - "+edge);
22.                 throw e;
23.             }
24. ...
25.  

Also I had to make sure my "empty" densities were -1f not just 0f otherwise they all get picked up as 1 after being processed by CalcCubeCases().

Code (csharp):

1.  
2. bit4 = densityField[x+y+0] < surfaceThreshold ? 0 : 1;
3.  

Should that maybe be <= surfaceThreshold?

Any help is seriously appreciated, this is riffing off the Sculpting demo FWIW.

Thanks,
Martin

 

Okay: Quick experiment and I made my density map cubical, it works! Any ideas how to best make it work without being cubed?

 

MartinLyne,

I assume you've dug into the DCBlock.cs and DynamicSculptingDC.cs scripts? In particular the "BuildDensityMap" functions. It sounds like you've got it working with cubical chunks, at least!

I confess I haven't experimented much with irregular blocks, so I'll get on that and check it. Things I'm going to try (and you're welcome to experiment too) are even numbers (21x7 is certainly irregular! 22x8 may work...) and powers of 2. I suspect something in the code is making an erroneous assumption that should be easy to correct.

I'll change the surfaceThreshold check to <=, it mostly won't make a difference for others but will certainly help in your case (and wherever that happens to others!)

cheers - B

 

Thanks for your response Bens, I'll keep experimenting and putting results here. I suspect the cubical won't actually b such a problem, already pushing the vert limit for meshes in unity at my given resolution - so will have to chunk them up anyway.

I'll re-read those functions, thanks,

Martin

 

Hi again,
I thought I was being clever and reversed the triangle winding order in your files, it works fine apart from when I remove a voxel from the outer edge of an empty box - whereby it actually extends outwards - I guess the DC/MC code still thinks it's an "inside-out" system even though the triangles are "outside-in". So it extends the mesh "outwards" to represent a dent on the inside of the mesh.

Any idea if there is a way of altering the "direction" of the mesh from the offset? Hope that all makes sense. I'll knock up a diagram too, just in case.

Thanks,
M

Edit: image

 

@bens1984
I changed my voxel visualisation code and noticed that actually the above diagram was slightly off, in actual fact it was removing a voxel from the "inner" layer.

Now I'm left with my last problem: everything works fine if the camera is inside my oxel space, but if it is outside then the mesh is visibly single sided.

Here is the camera inside the voxel space:

And here from outside (notice the outer surfaces are not generated):


Is there any way to either invert the assumed direction (a partial fix at best) or preferably to get i to continue to create the isosurface around the rest of the shape?

The above images are a 2 and 3 voxel thick hollow cube, but I also see the same issue.

My end goal is to basically have boxes that people can shoot their way into, so inner and outer surfaces need to be rendered. Any ideas?

Thanks,
Martin