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.
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.
Figure 11 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 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 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.