Dynamic Terrain Triangulation

Question

Is there someone who know/have an algorithm which can perform terrain triangulation like on the example image right under (there is a secondary image as well).

The reason I say "Dynamic" is because I want it to support Dynamic changes to the terrain, like if one was to dig into the ground or into the side of a mountain, then it should be capable of triangulating the new changes without destroying the old terrain which doesn't need changes.

Ignore the things like the trees, etc. This is only about the style of the terrain itself.

• Click here for fullscreen picture
• Secondary Image

I've tried using the Marching Cubes Algorithm, though it didn't give me that triangle'ish feeling, like in the image(s) above (While ignoring the normal rendering in my example).

Bottom Line

Does anybody know/have an algorithm, or any idea of how to...

• Triangulate terrain so it have that style like in the above example image(s).
• Support dynamic changes like Marching Cubes does, but with this triangle'ish style.

Note: All the "points" would be in an unsorted list, where the "points" of course is all the vertices, which should be used to generate all the triangles from.

---

Disclaimer: I usually answer and sometimes ask question on Stack Overflow, so if anything is wrong with my question here I apologize, though comment and I will fix whatever is wrong.

Answer 1

One (expensive) approach I've been playing with is Constructive Solid Geometry (CSG). csg.js, for example, is a nice clean short piece of code (if inefficient BSP approach) that can subtract and union meshes together. It'd be straightforward to port the approach literally to any other language. And there are more efficient CSG algorithms that can be googled once you know the terminology.

Using BSP splitting (as csg.js demonstrates) really fragments your meshes. You can tidy them up again using Hertel-Mehlhorn algorithm or you can tag the polygons before you BSP them so you can cheaply find all the split parts after and reassemble concave polygons in a tidy-up pass.

I've been playing with it to shoot holes in meshes for today's Ludum Dare competition: http://williamedwardscoder.tumblr.com/post/69968194211/last-week-i-discovered-csg-js-constructive-solid

And a fun video I just made: http://www.youtube.com/watch?v=7zjz-hpm8No

Answer 2

This is a super hard question, and you probably wont find your answer you want just like that. Most likely you will have to do some own research on how to achieve this.

there is also so many different ways doing this, and depending on your requirements you have to choose one that suits you.

The way i would do it would be that you take the direction that the player is digging in and with that you project that direction (or in any means find the triangels affected directly in a visinity ( basicly the size of the hole i guess. ) and from there then modify the vertexes so that you create an specialized gap towards that direction. this would also of course require to modify the amount of vertexs all the time so that you have to tessellate the digging.

You could also of course use voxelbased information and from there create vertexes that you could build your terrain with.

Answer 3

Take a look at the dual contouring algorithm. It can be used as a basis for the terrain stuff.

A useful idea is to combine it with polygon reduction methods, maybe even parameterized (so that steep hills have sharp corners but hills don't).

Answer 4

I didn't try anything, because it would take to long to set up a testing environment, but I would try to get rid of vertices that are too close to each other, combined with some randomness. Reconnect edges to adjacent vertices that were not removed. I really don't know what this is going to look like, but I think it can't be that bad.

When I see your attempt demo image, it looks like you are using some perlin noise. Great, but I think you should use some extra octaves to make the landscape a bit more nice.