> I'd appreciate some help with contour generation -- i.e. given a height map,

> generate contour lines.

> Seems like this should be a well-known algorithm (many apps, including

> Photoshop, have some sort of contour generation capability), but I'm unable

> to find any info.

There are several "well-known" algorithms. One trap for the unwary is

that the algorithms often differ (and are considered "good" by different

people) because of the current technology (esp. memory size).

Suppose that your height map is relatively small, and is on a complete

rectangular grid. You can start by considering every square cell (with

a height sample at each corner) and try to figure out how the contour(s)

pass through the cell.

Alas, some cells will be ambiguous.

In the alternative, you can find (by any means) a cell which contains a

part of the contour, and follow the contour wherever it leads you.

Alas, in some cells, you won't know (for sure) where to go next.

Resolving these ambiguities accounts for lots and lots of papers, and

algorithm design.

I prefer to examine EDGES joining sample points (instead of cells) and

build small pieces of contour separating height samples above and below

the contour height.

Alas, when these are stitched together, the contours may be ambiguous.

Alas, often the ambiguity is inherent in the data. Then, no matter what

you do, you may end up being screwed.

In my opinion (warning - this opinion is not shared by many) it is

better to delay the resolution of any ambiguity as long as possible, so

that you may take maximum advantage of domain-specific knowledge. So,

I prefer a method which refuses to make a choice...and allowe me to

represent an ambiguious answer.

If you'd rather have an unambiguous (but perhaps wrong) answer right

away, a convenient way to proceed is to triangulate (arbitrarily) your

square mesh into a triangular mesh. Then you can either follow each

contour, or generate pieces of contour in all triangular cells in

parallel - and the answer will be unambiguous.

One way to think of this is to think of the triangulated height field as

a piecewise-planar surface in 3D. Extracting a contour is equivalent to

finding the intersection of this surface with a plane (at constant z).

--

Computer and Information Sciences (205) 934-2213

University of Alabama at Birmingham FAX (205) 934-5473

Birmingham, AL 35294-1170 http://www.cis.uab.edu/info/faculty/sloan/