I want to make game terrain using something like a heightmap, but I want vertical cliffs and none of the usual artifacts that go along with the limited resolution of a heightmap. So why not use marching squares to turn the heightmap into a contour map? Next we can triangulate the contour map to generate a 3D mesh with smooth lines at any angle and no difficulty with vertical cliffs.

Here is a youtube video summarizing an algorithm for triangulating contour maps:

Unfortunately it looks quite complicated and computationally intensive. Is there any hope of being able to recalculate that mesh frame-by-frame as the user draws the heightmap? Does anyone know of a way to simplify this problem?

Marching cubes rather than marching squares should do it. I've used it before, with great results! Not insanely easy but definitely doable. Or do a regular heightmap and simply check the bounding box of each polygon; if it's too big (you decide what that means), tesselate it. Just make sure adjacent polygons know each other (simple to do during heightmap generation), so that tesselation diffuses correctly.

16 hours ago, Embassy of Time said:

Marching cubes rather than marching squares should do it. I've used it before, with great results!

How would you use marching cubes for terrain design? The obvious approach would be a 3D grid of voxels where each voxel is either 0 or 1, but in that case marching cubes would produce mostly axis aligned polygons and a few diagonals across the voxels. It wouldn't have a smooth or natural look. Marching cubes applied to voxels always seems to have the lumpy look of plastic stretched over piles of dice.

On the other hand, marching cubes can produce amazing images. Metaballs are a great example of marching cubes producing smooth lines and curves, but in that case the cubes use a continuous field of values based on their distance from the center of each metaball, so it's not just 0 or 1.

It's not hard to imagine using metaballs for rolling hills. A hand-drawn curve could perhaps form a cliff by blocking the influence of metaballs on one side from affecting the other side, but it would have to do it in a way that reflects the shape of the curve rather than just creating another jagged 0 and 1 situation.

Does anyone have any tips or resources on this type of terrain mesh generation?

8 hours ago, Outliner said:

How would you use marching cubes for terrain design? The obvious approach would be a 3D grid of voxels where each voxel is either 0 or 1, but in that case marching cubes would produce mostly axis aligned polygons and a few diagonals across the voxels. It wouldn't have a smooth or natural look. Marching cubes applied to voxels always seems to have the lumpy look of plastic stretched over piles of dice.

On the other hand, marching cubes can produce amazing images. Metaballs are a great example of marching cubes producing smooth lines and curves, but in that case the cubes use a continuous field of values based on their distance from the center of each metaball, so it's not just 0 or 1.

It's not hard to imagine using metaballs for rolling hills. A hand-drawn curve could perhaps form a cliff by blocking the influence of metaballs on one side from affecting the other side, but it would have to do it in a way that reflects the shape of the curve rather than just creating another jagged 0 and 1 situation.

Does anyone have any tips or resources on this type of terrain mesh generation?

In essence, ditch the 0/1 approach and use floating point values, like in metaballs, except values are calculated according to some worl generation algorithm (you will need one of those algorithms no matter what, even if it's just a fixed set of values). I've done that for ages, although the actual algorithm still hasn't hit the spot for me. I found an ooooold set of images of me trying something like it, here. Don't mind the text, it's Danish, just see the pretty pictures for the essence of what the method can do. I've done weirder stuff, too, but the images seem to be hiding from me at the moment....