Height Field Maps and Contouring

Is there anyone out there that can help me???

Heh, sorry, I know I need help. Anyways, to topic, can anyone help me out. I’m writing up a 3D modeling app and things are going well so far, but its now time to start optimizing things.

I’m working with 3D maps and converting them into internal models, and mapping them with colors (height fields). However, my first incarnation is pure triangle strips. I need an algorithm to reduce the triangle count without losing detail in the map (there are holes in it). I suppose for right now, we can disregard the holes though. Please note, the maps that I’m working with (vertex-wise) are upto 4kx4k. That means 3.2 million trianges per map with generic triangle strips. I’m shooting for at most half that.

On average, my maps are 512x512, and 1kx1k tops. I’m shooting for 500k triangles tops.

And secondly, I’d like to contour the map at given values. Anyone have an algorithm for that?

Any resources on this, let me know. I’ve checked the web and haven’t found anything real useful, or at least understandable.

Thanks in advance!

For the contours, there’s an example using projective textures in the OpenGL Red Book.

For triangle reduction, do a search for “binary triangle trees” on the Web, there’s a heap of resources on this subject.

Check out http://www.gamasutra.com/features/20000403/turner_01.htm for an article on the ROAM algorithm, a demo and some links.

Good luck,


You don’t need projective texturing for doing contours. You can use a simple 1D texture with texgen of OBJECT_LINEAR. The problem with this is that the contours are defined by the current LOD rather than the original geometry. If that is a problem, you might need to use a 2D texture instead.

For the terrain demo that I did ( http://www.r3.nu/~cass/thesis/ ), I started out using 1D textures for contours then switched to 2D in order to capture the land/sea boundary (coastline) correctly.

Thanks guys. I’ve taken a quick look at all of the solutions/suggestions posted so far, and things are looking promising right now.

As far as the contouring goes, I guess I should clairify quickly.

I’m looking to place contour lines on the map. The map itself is shaded with color, no problems, however, I want to denote boundry values (or even boundry values within a range, as I can guarantee that it is possible a boundy point has no immediate neighbor to connect with, but one or more intermidiate neighbors before the next pure boundry point occurs).

Any ideas? Or did I just translate what was posted wrong.

cass, I thought projective texturing WAS just texgen with GL_OBJECT_LINEAR… am I missing some distinction here?


Using texgen to assign texture coordinates is really just using texgen. The nomenclature may be a bit confusing since a dot4 (projection) is used to transform the full four-component spatial coordinate into a single component (scalar) of the texture coordinate.

What people are generally referring to when they talk about “projective textures” would probably be more accurately called “perspective projected textures”. That is, they’re referring to a specific type of projective transform in texture coordinates.

In my “simple projective texture” demo on http://www.r3.nu/ you can see a simple implementation of this concept. The key ideas are to use EYE_LINEAR texgen and to put the view and projection transforms into the texture matrix. You have to back out the camera view first since EYE_LINEAR provides eye-space coordinates.

Hope that makes sense.

Okay, here’s another quick question. I’m thinking I can get away with meshing and skinning, until I considered the following problem.

The height map dimensions are square, ie: 1kx1k. If I were to produce a bitmap from it, I could theoretically skin the mesh produced by the map with the bitmap from the map. However, the map is in Z Height format. This produces the problem that the bitmap triangles are 1x1 right triangles, but the mesh triangles become acute triangles when the z value is included.

Is there anyway to compensate for this and still be able to mash and skin?

Also, if there is, can anyone tell me how to skin the entire model with the texture rather than by poly? (Clairify, stretch the texture over the entire model rather than repeat the texture for each poly, my text doesn’t clearly specify how to do that.)

Thanks again.