Jump to content
  • Advertisement
Sign in to follow this  
frean

Heightmap tesselation

This topic is 3134 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

Hi, Decade-long reader, first time poster. I'm trying to construct a threshold-based 2D mesh generator that feeds from a height map. For example, say we have a greyscale 8-bit heightmap (0-255) of some size. I'd like to construct a bunch of triangles covering this bitmap, where triangles are expanded as long as the bitmap values contained within a triangle is within the treshold. If the contrast becomes too large when expanding, a new triangle(s) will start to form with that value as base. The seems like a problem that must have solved many times before, but I can't seem to find any words for it. Somewhere between edge detection and mesh generation I guess. Any tips? Edit: Supplying screenshot of code that doesn't quite behave like I want, but kind of: http://www.stuffing.se/gl/edges.png [Edited by - frean on February 20, 2010 6:08:33 PM]

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by frean
Hi,

Decade-long reader, first time poster. I'm trying to construct a threshold-based 2D mesh generator that feeds from a height map. For example, say we have a greyscale 8-bit heightmap (0-255) of some size. I'd like to construct a bunch of triangles covering this bitmap, where triangles are expanded as long as the bitmap values contained within a triangle is within the treshold. If the contrast becomes too large when expanding, a new triangle(s) will start to form with that value as base.

The seems like a problem that must have solved many times before, but I can't seem to find any words for it. Somewhere between edge detection and mesh generation I guess.

Any tips?

Edit: Supplying screenshot of code that doesn't quite behave like I want, but kind of: http://www.stuffing.se/gl/edges.png
I could be completely off base here, but it seems like what you're wanting to do is somewhat similar to what the Recast navigation mesh generator does. If so, perhaps it would be a suitable solution (or could at least serve as a point of reference if you're looking for a strictly 2-d solution).

Share this post


Link to post
Share on other sites
My gut instinct tells me that this is essentially a bin packing problem, so you won't be finding an optimal solution in any reasonable amount of time. However what I would first do is run an edge detection filter over the image to find locations where the gradient is larger than the threshold, since these are boundaries which triangles cannot cross. For regions bounded by these edges, you can perform a flood-fill based on the gradients to form sub-regions that are within the threshold, and then triangulate them. Like I mentioned previously this probably won't generate the optimal solution, but it might be a start.

Share this post


Link to post
Share on other sites
Thanks so much for the suggestions. Recast looks fun, I like to think of terrains as "molds" as they do, will check it out. Bin packing with first-fit strategy pretty much describes exactly how I did the code so far, so that's a very accurate description of the problem!

Basically, initialize a bool[][] with the same dimensions as the bitmap. When you encounter a false entry, start expanding a rectangle from there while uhm... true:ing the area. Made it quite easy to apply constraints on the boxes as well (max size, ratios).


Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!