What is the best way to “carve” a terrain created from a heightmap?

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.

-

3D carving can be done with Surface extraction of a 3D density field. Then you can reduce the values in the dinsity field and so dou can carve your hole. Examples for this is marching cubes, or dual conturing. The problem is, that heightmap polygons and polygons generated with surface extraction are not that easy to mix together. Either you only use surface extraction or you invent some technique that helps you to merge them together.

-

That operation will be done in the game editor

Did you just imply that you're expecting to make something better than world-class modelling application developers? Not that I don't consider all this doable, it's just time-consuming and will most likely require an artistic touch in the end anyway (which procedural generation tools simply cannot provide from that point in the pipeline). Especially since you haven't considered texcoord generation here at all.

So before I make my suggestion, let me point you to someone who struggled with a similar problem: Art Asset Overview #32 (from Wolfire Blog). They solved it by allowing to edit the procedurally generated terrain mesh. If you check their blog, they've done really impressive things like making crazy algorithms work (Delaunay triangulation is extremely crazy because of floating point number inexactness, for example).

So we've come full circle back to my suggestion. It's quite simple, actually.

1. Find yourself a good terrain generator for the base terrain.

2. Find or create something that would generate a mesh from a heightmap.

3. Find a good modelling application with sculpting tools that you like. If necessary, create converters between yours and whatever the modelling application can import/export.

4. Render the mesh in your game and use your editor for nothing more than selecting a mesh.

If you want, you can easily split the mesh into many smaller meshes for culling. As opposed to what you want to do up there, it's much easier.

-
Maybe i underestimated the amount of time/effort to do such a thing. For example, lot of games just store a heightmap as game data and then generate a mesh from that (because its quite trivial to do and make sometimes things easier, like implementing a LOD system). Based on that idea i wanted to know if carving would be feasible. – tigrou Nov 29 '12 at 21:18
Terrain LOD algorithms are obviously not an option after any such modifications. And I don't think it's good to look at lots of games. Pick two to five that describe your intentions best and you might have a more accurate list of possibilities. – snake5 Nov 29 '12 at 23:27