Organizing and simplifying a complicated terrain mesh data structure

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.

terrain_patch.jpg?psid=1

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Forum Statistics

    • Total Topics
      628686
    • Total Posts
      2984234
  • Similar Content

    • By Big Impact Sound Composer for Media
      Big Impact Sound | Composer for Media
       
      provides royalty free music and sound design for media, games, television, film, trailers, commercials, documentaries, YouTube creators, exhibits, websites, slide shows, corporate projects, podcasts, wedding albums, presentations, audiobooks, radio, apps and so much more.
      Royalty free music
      Big Impact Sound allows you to distribute the royalty free music worldwide  and without any additional fees.
      Our music licensing system is transparent and easy:  once the music license is paid there are no copyright issues.
       
      Wide range of musical styles
      Our award winning team has more than two decades of experience in the creation and production of contemporary and classical music.
       
      Composition on demand
      Custom-made composition and sound design that will maximize the impact of your game, movie, commercial, trailer, documentary or presentation.
       
      Music productions ranging from single tracks to full orchestral scores
      We can provide single tracks or full scores and our team helps you with your project
      from start to finish according to your specific wishes.
       
      Stock Music (Library Music)
      Fast and easy music and sound design browsing in our huge music library. All our tracks are immediately available for any of your projects.
       
      Fast turnaround time
      We are used to work with tight deadlines and will help you meet them. We are passionate about our work and always aim for perfection.
       
      Contact us (by PM or by the website) to discuss how we can enhance your project with a distinctive sound identity.
      https://bigimpactsound.com/
       
       
       
    • By DavidMT
      A team has a position open for a 3D artist and/or modeler.
      Excellent opportunity to gain experience working with a team remotely. Great chance to extend your portfolio Candidates, if successful have the chance to join the team permanently with entry-level financial benefits. Revenue Share What they expect
      Excellent communication skills Portfolio of previous work If you are interested please attach a CV and/or relevant works to jobs@iamdavidmt.com
       
    • By ForgedInteractive
      Who We Are
      We are Forged Interactive, a small team of like-minded game developers with the sole purpose of making games we love! Currently, we're progressing very quickly with our first project and there are plenty of opportunities and work for new interested programmers. With this project, our development platform is Unity 5.5.2 and C# as our behavioral language. Since this project is our first release, the game itself is a smaller project though progress is moving quickly. We are looking to finalize the current project and get started on future projects in the near future and are expanding our team to do so.
       
      Who We Are Looking For:
      Programmer Level Designer  
      About the Game
      Ours is the tale of two siblings, thrown into a world of chaos. Living in the shadow of their parents' heroic deeds and their Uncle's colorful military career, Finn and Atia are about to become the next force to shape our world. How will you rise through the ranks of Hereilla and what will be your legacy? Once defeated your enemies turn coat and join you in your adventures. Players can enjoy a range of troops and abilities based on their gameplay style which become more important as maps introduce more challenging terrain, enemies and bosses. Strong orc knights, dangerous shamans, and even a dragon are out on the prowl. Knowing when to fight and when to run, and how to manage your army is essential. Your actions alone decide the fate of this world.
       
      Previous Work by Team
      Although we are working towards our first game as Forged Interactive, our team members themselves have worked on titles including and not limited to:
      Final Fantasy Kingsglaive FIFA 2017 Xcom 2 Civilization  
      What do we expect?
      Reference work or portfolio. Examples what have you already done and what projects you have worked on academic or otherwise. The ability to commit to the project on a regular basis. If you are going on a two-week trip, we don't mind, but it would be good if you could commit 10+ hours to the project each week. Willingness to work with a royalty based compensation model, you will be paid when the game launches. Openness to learning new tools and techniques
       
      What can we offer?
      Continuous support and availability from our side. You have the ability to give design input, and creative say in the development of the game. Shown in credits on websites, in-game and more. Insight and contacts from within the Industry.
       
      Contact
      If you are interested in knowing more or joining, please email or PM us on Skype. A member of our management team will reply to you within 48 hours.
       
      E-mail: Recruitment@ForgedInteractive.com
      Skype: ForgedInteractive
       
      Regards,
      David, Colin and Joseph
       
      Follow us on:
      Facebook: https://www.facebook.com/ForgedInteractive/
      Twitter: @ForgedInteract
      Youtube: https://www.youtube.com/channel/UCpK3zhq5ToOeDpdI0Eik-Ug?view_as=subscriber
      Reddit: www.reddit.com/user/Forged_Interactive

    • By Michael Pearson
      Hello all!   I'm currently in my third year on my 3D Animation & Games Development course, and I am in the process of doing some basic primary research for my dissertation project, which is to create a high quality 3D Environment for use in video games and potentially VR.   I have a questionnaire (targeting other artists in the field), and I would really appreciate it if you took some time to have a look and fill it out:   https://docs.google.com/forms/d/e/1FAIpQLScW12nFI8-fMlAUMNSQvOInxhnIfXpG91iRCm25TVlZufrvbQ/viewform?usp=sf_link   Thank you in advance!   Mike.
  • Popular Now