Jump to content

Voxel Terrain Part 2 - Voxelization Methods


SpiderPig

1,028 views

 Share

Instead of settling for one way only to voxelize a terrain I decide to make it possible to select between a few of them depending on what was required.  They're are basically just two methods, forward or backward.

enum VoxelMethod {
	VOXEL_METHOD_FORWARD,
	VOXEL_METHOD_FORWARD_CONTOUR,
	VOXEL_METHOD_BACKWARD,
	VOXEL_METHOD_BACKWARD_CONTOUR
};

Forward starts with a parent node and checks each corner against some function that says if the corner is above or below some user defined surface.  If the node has been determined to represent some part of the surface it is subdivided into eight new nodes and the process repeated until the lowest subdivision level is achieved.

Backward creates a 3D grid of points that are iterated through in a three layer nested for loop.  The points are spaced at the lowest node size required (1m cubed in this case) and then tested with the same user defined function for forward voxelization.  The points and then looped through again to find which ones represent the surface and then the parent node is subdivided until it reaches the node that represents these points.  It starts from the end and works it's way back.

 

As shown here the forward method is fast but in most cases leaves a few holes in the mesh as stated in my previous entry.  I've left the method in there because it might be useful in some situations.

ForwardVoxelization.thumb.png.5c754c1e24c398a45bfb2add8d5e51d4.png

 

Here is the result from using the backward method.  Ignoring the bounds of the terrain you can see there are no more holes in the surface.  I haven't done any speed comparisons yet but for this small 128x128x128 terrain I can't tell a difference.  It also uses a bit less memory too than the forward method.  Most likely due the fact only the nodes that represent the surface are actually created.  This was a feature I removed from the forward method because it made more holes with it than without it, but it could be re-introduced later know that I know what the issue is.

BackwardVoxelization.thumb.png.29d8a39bb98c688f28cd6620bf8729f3.png

 

A view from inside looking out.

BackwardInside.thumb.png.8b2689b9130e162a8fc05565ed85afc4.png

 

This leads me to the small floating fragments caused by using 3D noise and the potential resolution by the contouring method.  I'm thinking in either the forward or backward case, when a surface is found it will start to follow the surface by calculating where it might be based on the surface it's already found.  This should mean that only a surface connected the previous nodes surface will actually be created.  It may even be faster due to it only having to sample the noise when it knows it's close to it.  The issue though is first determining which surface is the main surface, otherwise it could find the small fragment first (pictured) and class that as the main surface and therefore disregarding the larger main surface.  This requires more thought.

FloatingIslands.thumb.png.8c2a459eb34506d16c23e6c24248b343.png

 

Next though I am going to work on render methods.

enum RenderMethod {
	RENDER_METHOD_MARCHING_CUBES,
	RENDER_METHOD_TRANS_VOXEL,
	RENDER_METHOD_CUBOID,
	RENDER_METHOD_SURFACE_NETS,
	RENDER_METHOD_DUAL_CONTOURING
};

 

  • Upvote 1
 Share

5 Comments


Recommended Comments

I've also changed the class name from VoxelTerrain to VoxelObject.  There's no reason this can't be used for smaller destructible objects as well.  :D

Link to comment

In this 128^3 terrain there is 512 components and 488 of them are active (they have a mesh).  I want to make it that the size of a component can be dynamic when LOD is enabled otherwise for large terrains the component count could be excessive.  The component size here is only 16^3.

ActivevsInActiveComponents.thumb.png.b2688a2781c43b295dd6d9ef53429553.png

  • Like 2
Link to comment

Marching cubes are not the best for displaying geometry.  It's fine if you want a blocky look (let the vertex be created at the centre of every node edge) but if you interpolate to better match the object you want to represent, you end up with lots of different sized triangles.  Below is flat shading so it's more obvious, but you can see in wireframe the steps where triangles are squashed as it goes up to the next highest node.  SurfaceNets and DualContouring should be much better (and faster to generate) but there are aspects about both I don't really like.

SurfaceNets, once the vertices are created, needs to be looped over a few times to slowly morph the vertices toward one another to create a smooth shape.  This means the object will shrink a little at the edges.

DualContouring seems much better but does use some fancy math I can't wrap my head around (yet) to better represent sharp edges.  I think I am going to try and make something that is a combination of the two.

MarchingCubes:

MarchingCubesAstheticsSolid.thumb.png.0ed8e7adf4f37f56200ea714f8756903.png

WireFrame:

MarchingCubesAstheticsWireframe.thumb.png.008447220ac849e16f1b2d3d66b28260.png

Link to comment

Are you saying that marching cubes creates some "stair-stepping" due to the fact the minimum change in elevation is equal to the voxel size, so the minimum change in height is equal to the distance between terrain points?

Link to comment

Not really... because each node has a set amount of vertices and triangles, if you want to have a smooth shape you have to interpolate the vertices down or up the nodes edge toward the surface.  There's no visual stepping or anything, it just creates a lot of small triangles where the vertices have been moved really close to a nodes corner.  Mostly it is just wasted geometry because they are so small but I've found it does give a more non-uniform look in the geometry compared to the 2D terrain rendering method with set patch sizes.

In some cases the vertices could all be on top of one another and therefore the triangle is not visible at all, but it is still there.

This is marching cubes without interpolation.

MarchingCubesWithOutInterpolation.thumb.png.897dffdfbe6bb80619dc4c4d286cea47.png

  • Like 1
Link to comment
Guest
Add a comment...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...