I have a 3d landscape created from a heightmap. I'd like to "carve" some holes in that terrain. That will allow me to create bridges, caverns and tunnels inside it.

That operation will be done in the game editor so it doesn't need to be realtime. In the end, rendering is done using traditional polygons.

What would be the best/easiest way to do that ? I already think about several solutions :

Solution 1

1) Create voxels from the heightmap (very easy). In other words, fill a 3D array like this : voxels[32][32][32] from the heightmap values.

2) Carve holes in the voxels as i want (easy too).

3) Convert voxels to polygons using some iso-surface extraction technique (like marching cubes).

4) Reduce (decimate) polygons created in 3).

This technique seems to be the most promising for giving good results (untested). However the problem with marching cubes is that they tends to produce lots of polygons thus reducing them is mandatory. Implementing 4) also seems not trivial, i have read several papers on the web and it seems pretty complex. I was also unable to find an example, code snippet or something to start writing an algorithm for triangle mesh decimation. Maybe there is a special decimation algorithm (simpler) for meshes created from marching cubes ?

Solution 2

1) Create some triangle mesh from the heighmap (easy).

2) Apply severals 3D boolean operation (eg: subtraction with a sphere) to carve the mesh.

3) apply some procedure to reduce polygons (optional).

Operation 2) seems to be very complex and to be honest i have no idea how to do that. Also applying many boolean operation seems to be slow and will maybe degrade the triangle mesh every time a boolean operation is applied.