Often, a velocity field (or other object that we want to triangulate) is defined on a regular Cartesian grid. One way to perform a triangulation in this case is to select a smaller subset of the initial grid points, using them as the input to a triangulation program. We need to select the points in a way that preserves the main features of the original image, while removing some unnecessary redundancy in the regular grid description.

Figure 10

Garland and Heckbert 1996 surveyed different approaches
to this problem and proposed a fast version of the incremental
*greedy insertion* algorithm. Their algorithm adds points
incrementally, selecting at each step the point with the maximum
interpolation error with respect to the current triangulation. Though
a straightforward implementation of this idea would lead to an
unacceptably slow algorithm, Garland and Heckbert have discovered
several sources for speeding it up. First, we can take advantage of
the fact that only a small area of the current triangulation gets
updated at each step. Therefore, it is sufficient to recompute the
interpolation error only inside this area. Second, the maximum
extraction procedure can be implemented very efficiently with a
priority queue data structure.

opengl
An image from the previous
example, as rendered by the OpenGL library. The shades on polygonal
(triangulated) sides are exaggerated by a simulation of the direct
light source.
Figure 11 |

Figure 10 illustrates this algorithm with a simple example. The original image (the left plot) contained 10,000 points, laid out on a regular rectangular grid. The algorithm selects a smaller number of points and immediately triangulates them (the middle plot). The image can be reconstructed by local plane interpolation (the right plot.) The reconstruction quality can be further improved by increasing the number of triangles. Figure 11 shows the same image as rendered by the OpenGL graphics library Woo et al. (1997).

Figure 12

Figure 12 shows an application of the height triangulation algorithm to the famous Marmousi model. The left plot shows a smoothed and windowed version of the Marmousi, plotted on a 501 by 376 computational grid. In the middle plot, 10,000 points from the original 188,376 were selected for triangulation and interpolated back to the rectangular grid. The right plot demonstates the small difference between the two images.

10/9/1997