# 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 density field and so you can carve your hole. Examples for this are marching cubes, or dual contouring. 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. 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. Nov 29 '12 at 23:27

If you have a heightmap that is, say, 512x512 and reinterpret it as a volume of 512x512x512, with every voxel set to a value of 0 that would be in the terrain, marching cubes should give you a similar result on this than what you would get when building a regular heightmap terrain. In order to get closer to the proper heightmap, you can use a more accurate representation. So instead of just setting everything to 0, you have to set it to values that represent the actual height for this voxel, as otherwise, you only have 512 different height positions which would look bad.

This means that all you have to implement is marching cubes, as well as the heightmap => voxel transfer. These are all fairly simple things, just marching cubes is like one huge collection of if/else or switch. One problem you will get is of course the resolution. You can however likely have a much smaller vertical resolution (I'd try to get square voxels) because your terrain is probably much wider than it is high, which should alleviate the problem. Otherwise you have to tile the terrain into multiple chunks and only keep the chunk in memory during editing that you are working on.

At runtime you then just have a mesh. And if you chunked the volume texture, you also have something to work with for larger scenes. You could also compute a LOD hierarchy from this by downsampling the volume and running marching cubes again.

Honestly, the HARD part is writing the tools that actually allow you to carve in a usable way. All you have to do is set voxels to 1 instead of 0, but developing a good user interface for this isn't trivial. Also, running marching cubes on the whole volume every time something is edited is probably kinda slow and could be improved somehow.