Advertisement Jump to content

Organizing and simplifying a complicated terrain mesh data structure

This topic is 489 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a few key features that I want for my game's terrain mesh, but putting it all together into an terrain editor is becoming a headache. I need some advice from someone more experienced than myself. Perhaps there is some design pattern or object-oriented trickery to add some abstraction and turn this mess into something manageable.

I am creating my terrain mesh as a problem of dynamic constrained triangulation. I start with a regular triangulation of a 2D plane into equilateral triangles, and then as I draw the game's map the existing edges and vertices are automatically removed to make room for the edges and vertices I'm drawing, and naturally the reverse happens when I erase. There are fairly simple algorithms for inserting individual vertices and edges into a triangulated plane. Using a half-edge data structure to represent the triangulation makes it quite manageable.

Unfortunately there are a few additional important features. For one, a game map should be an infinite plane in all directions. The obvious solution to this is to break up the mesh into regular pieces, each one separately triangulated but sharing common points along their edges so that the multiple meshes fit together seamlessly in the game. The user should be able to draw map features across the boundaries of the map pieces seamlessly, without needing to care where one map piece begins and another one ends. An ordinary half-edge data structure doesn't have anything to deal with that and it would be nice if I could manage that complexity so it doesn't seriously affect my triangulation algorithms.

Perhaps I'm asking for trouble, but I also want the terrain mesh to be able to change while the game is playing. I'm not so greedy as to try to implement animated terrain, but I would at least like to be able to remove a designated region of the map and substitute an alternative map of the same shape. We might think of it as having a hole in the map that can be filled by any one of several appropriately shaped meshes. Once we've got these meshes it will be trivial to pop them in and out during the game, but again it's another complication of the editor. Keeping the boundaries of the designated regions aligned with the rest of the map and allowing new edges to be drawn across that boundary is making the editor too complicated for comfort.

What are the appropriate abstractions to use for this kind of situation? These seem like relatively simple features, but my design is turning into a tangled mess. What am I doing wrong? An ordinary half-edge structure doesn't seem to be the right tool for this job, but what would be the right tool?

Share this post

Link to post
Share on other sites

Why not just use a simple height map and render your terrain with a regular grid patch, like below? If you need holes in the terrain just create a normal mesh based on the same grid structure and drop it in where you have modifications. Edge connectivity is guaranteed.


Share this post

Link to post
Share on other sites
1 minute ago, Mk_ said:

Why not just use a simple height map and render your terrain with a regular grid patch, like below?

That's because of a few other features that I'm trying to implement. I'd really like to have sharp vertical cliffs in just the way that height maps do poorly. With a little extra fiddling, a regular grid would still work for cliffs, but they would need to be axis aligned. That's why I've been aiming for a data structure that allows me to insert arbitrary edges into my mesh, so I can have cliffs aligned to whatever angle I like.

Much like cliffs, I would also like to put roads into the mesh, with UV coordinates setup so I can render the road's texture aligned with the direction of the road. Again, I hope to achieve this by inserting arbitrary edges into the regular grid so I can give the roads dedicated triangles with custom UV coordinates.

Even so, my difficulty with this approach has lead me to seriously consider using Marching Cubes to generate my mesh. By carefully choosing the grid values, it should be possible to create cliffs at any angle, and it would be a regular grid so it eliminates my current problems. I still haven't figured out a way to make the roads work with Marching Cubes, but I imagine I could do it with some adjustment to the triangulation algorithm.

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!