Jump to content
  • Advertisement
Sign in to follow this  
timmaxw

Heightmap with varying degrees of density

This topic is 4074 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 wrote a basic heightmap terrain renderer for a game I'm working on. It worked great with small maps, but ran pathetically slow with big maps. I could optimize it, but I think there might be alternatives. 1. Most heightmaps have the same density of triangles throughout. What if there were a heightmap editor that let the user specify different densities for different parts of the heightmap? Flat plains could be rendered with only a few triangles, and trickier regions could be rendered with more. 2. Alternatively, there could be a "heightmap" that was deformable. Control points could be moved horizontally as well as vertically so that they would only be where they were needed. It would allow for more precision - steep cliffs could be done by moving two rows of points very close together - and it would take less faces than a "normal" heightmap. It would take about the same number of triangles to render as a mesh of the same shape. I've never heard of anybody trying this before. I've already coded most of solution #2, but I think it might be too complicated. Should I use it, or should I just throw it away and use a standard heightmap with optimizations? Comments, suggestions, ideas, and opinions welcome.

Share this post


Link to post
Share on other sites
Advertisement
If you are going to move vertexes around then you might be better off using a mesh rather than a heightmap. Also, look up "triangulated irregular network".

Share this post


Link to post
Share on other sites
Yes, a triangular irregular network is almost exactly what I'm doing. Thanks. I didn't know what to search for.

There are some performance benefits to a TIN because the triangles don't overlap in any way. Also, in my implementation the triangles are stored in order by coordinate so collision detection is faster. I'll think about just using one big mesh for the world, because that's a lot more expressive than the TIN + geometric primitive approach that I was planning.

Share this post


Link to post
Share on other sites
You can always start with a height field (defined on a rectangular grid) and keep only a subset of the vertices. The difficult part, of course, is choosing a "good" subset--one that captures the essential shape of the mesh.

By analogy, consider a curve X(t) for 0 <= t <= 1. Suppose you have a set of N+1 samples P = X(t), for t = i/N and 0 <= i <= N. The "mesh" in this case is a polyline that connects the consecutive points. The segments are <P,P[i+1]> for 0 <= i < N. You want to choose a subset of the P and have the resulting polyline still retain the essential shape of the original polyline.

Start with a single segment <P[0],P[N]>, which is parameterized by Y(t) = P[0] + t*(P[N] - P[0]) for 0 <= t <= 1. Locate the index j so that the length |P[j] - Y(t[j])| is maximum. Subdivide <P[0],P[N]> into two segments, <P[0],P[j]> and <P[j],P[N]>, and repeat this algorithm on the subsegments. If you have a "vertex budget" M < N, then stop the process once you have M vertices in the approximating polyline.

The idea extends to height fields X(t0,t1) for 0 <= t0 <= 1 and 0 <= t1 <= 1. You have an array of samples P[i0][i1] = X(t0,t1), t0 = i0/N0, t1 = i1/N1, 0 <= i0 <= N0 and 0 <= i1 <= N1. Start with a pair of triangles whose vertices are the four corners of the height field. Find the indices i0 and i1 for which the length of the vector from P[i0][i1] to the corresponding triangle point is maximum. Subdivide the rectangular domain into four rectangular subdomains and repeat the algorithm.

Share this post


Link to post
Share on other sites
When doing LOD on a heightmap, you render chunks at different 'densities'. There is absolutely no reason why you couldn't set it do different chunks have different densities as their most detailed level. In fact if you already had a LOD system this would be simple. I always planned to add that to my heightmap system but never got around to it.

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!