Methods for implementing contour plotting

Question

I need to implement a contour plotting algorithm (as opposed to just using one). The input is a (continuous) function f: R^2 - > R (the function is defined over the entire domain, not just for certain inputs). The output should be in vector form, i.e. a set of splines or line segments.

I'm looking for recommendations on how to implement this, preferably in the form of (scientific) papers.

I found some references to algorithms developed in the 80s ("Level Tracing Algorithm"). Have there been any development in this area in the past 30 years? What's the standard method(s) used to solve this problem?

The algorithm will be used for real-time visualization, so it needs to be fast while still producing decent results.

(Small, self-contained and well tested C/C++ implementations would be welcomed as well.)

Answer 1

I recall the TI-89 calculator used a very simple scheme like this:

• Make a grid, experiment with mesh size
• Compute your function at each vertex of the grid
• For each square, if there are two values of f with different signs, there is something interesting inside. Assume it is the case in the following:
  • For each "interesting" side of the square (f has different signs at endpoints), find the zero of f on the side by bisection (or by linear interpolation if you're on low budget). There may be two or four interesting sides.
  • If there are two interesting sides, draw a straight line between the zero points.
  • If there are four interesting sides, draw a cross.

Now, you may want to refine the interesting squares adaptatively. The TI-89 had a damn small screen (160x120) and this was not necessary. The exact same method can be used inside an interesting square.