Selection of the set S and the properties that it holds are heavily dependent on the contouring propagation algorithm applied, thus we will introduce propagation first.
The central idea is that, given an initial cell (a seed cell) which contains the surface of interest, the remainder of the surface can be efficiently traced by performing a breadth-first search in the graph of cell adjacencies, as illustrated for a 2D contour extraction in Figure 2. Use of a breadth-first search keeps the memory requirements minimal, as only the ``advancing front'' of the surface needs to be stored at any one time. One advantage to using a propagation approach over other techniques is that surfaces are easily transformed into a triangle strip representation for more efficient rendering [6]. Also of importance is the fact that shared vertices between cells are more efficiently located, as we are considering only a single closed contour at any given time. In our implementation, carefully hashed indexing of the advancing front allows us to efficiently eliminate recomputing intersections when the advancing front closes on itself, completing the extraction of a connected component. Similar to related caching techniques [1] [7], the cache is made efficient by discarding entries which are known to not be referenced again, based on the maximum number of cells which share a given edge.
Figure 2: Illustration of contour
propagation