Sign in to follow this  
frean

Heightmap tesselation

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
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

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

Sign in to follow this