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.

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.

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.

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.