\section{Related Work}

\subsection{Building Good Strips in Static Meshes}

The problem of finding a minimum number of triangle strips that cover
a mesh is known to be NP--complete~\cite{Estkowski02,Arkin}.  Many
``stripification'' algorithms use heuristics to construct good sets of
triangle strips.  Best known are the classic SGI and {\sc STRIPE}
algorithms.

The SGI algorithm~\cite{SGI} greedily constructs a strip by extending
it incrementally to the next adjacent triangle of lowest valence,
where the valence of a triangle is the number of adjacent triangles
not already in a strip.  This tends to construct strips that follow
boundaries, and prevents the creation of isolated faces.

The widely used {\sc STRIPE} algorithm~\cite{stripe} finds large areas
of quadrilaterals, triangulates them and stripifies them, and greedily
adds the remaining triangles.  

Other methods take a graph--theoretic approach, and construct a
spanning tree of the dual graph and traverse it to form triangle
strips.  (In the dual graph, a node corresponds to a triangle and an
edge joins nodes that correspond to adjacent triangles.) Speckmann and
Snoeyink~\cite{Speckman} build an implicit spanning tree and produce
``close--to--sequential'' strips.  Xiang {\em et al}~\cite{Xiang}
build long strips by concatenating shorter strips in the spanning
tree.

An elegant recent result by Taubin~\cite{Taubin02} describes how to
construct a single, Hamiltonian strip in a triangulated quadrilateral mesh.
The algorithm takes a quadrilateral mesh (which must be a 2--manifold
without boundaries) and triangulates it by adding a diagonal edge to
each quadrilateral.  The diagonals are chosen, in time linear in the
number of quadrilaterals, to produce a Hamiltonian strip.

\subsection{Maintaining Good Strips in Multiresolution Meshes}

Multiresolution meshes come in different forms: {\em CLOD\/} meshes
permits topological changes to occur through individual edge collapses
and vertex splits, while {\em hierarchical\/} meshes have a
constrained structure which limits the types of transformation
allowed.

The Skip Strip algorithm~\cite{skipStrips} of El-Sana {\em et al\/}
builds a good initial stripification of a high resolution CLOD mesh
and stores it in a structure which is based upon the skip list
structure of Pugh~\cite{Pugh90}.  As the mesh is modified through the
removal and subsequent replacement of triangles, the Skip Strip
structure maintains the unbroken sections of the initial strips.

The DStrips algorithm~\cite{DStrips} of Shafae and Pajarola makes repairs
to the CLOD mesh as triangles are added and removed.  Upon each
topological change, the algorithm disassembles strips in the vicinity
of the change, and then creates new strips with a fast greedy
algorithm similar to the SGI algorithm.  It also opportunistically
joins strips with adjacent endpoints.

Belmonte {\em et al}~\cite{Belmonte01} consider the closely related
problem of progressive mesh transmission~\cite{HoppePM}, in which a
large mesh is transmitted progressively: An initial, very low
resolution mesh is followed by a sequence of vertex split operations
to produce higher and higher resolution versions of the mesh.
Progressive transmission is suitable on low--bandwidth connections,
and permits the client to see a low--resolution approximation of the
mesh early in the transmission.  Belmonte {\em et al\/} use a spanning
tree approach, from which strips are chosen so that they will not be
broken in the later stages of the transmission.

The ROAM renderer~\cite{roam} uses a fast incremental approach to
maintain small {\em sequential\/} strips in a hierarchical mesh.
Velho {\em et al\/}~\cite{velho} use recursive space filling curves to
define generalized triangle strips at all resolutions of a
hierarchical mesh.

\subsection{Building Strips to Maximize Cache Hits}

Deering introduced {\em generalized triangle meshes}~\cite{deering}
which use a vertex cache to decrease vertex transfers from the CPU to
the graphics card.  The idea is to exploit those vertices that are
currently in the cache in order to minimize the number of times a
given vertex is sent to the graphics card.  Chow~\cite{Chow97}
described methods to construct strips and compress the geometry detail
of these meshes.  Bar--Yehuda and Gotsman~\cite{barYehuda} showed that
a cache of size ${\cal O}(\sqrt{n}\ )$ is necessary to minimize vertex
transmission in a mesh of size $n$.  Hoppe~\cite{transparent} has
described heuristics to construct triangle strips that are optimized
for a given cache size.  Bogomjakov and Gotsman~\cite{bo-go-gi01}
showed how to generate strips that perform well for {\em all\/} cache
sizes.

\subsection{Comparison to the Tunneling Algorithm of this Paper}

The tunneling algorithm of this paper is a heuristic approach which
can build a stripification or can repair a stripification that is
broken due to a topological change in the mesh.  Cache coherence is
not considered by the tunneling algorithm.

The tunneling algorithm builds generalized triangle strips that are
much better than those of any algorithm to date (including an earlier
version of the tunneling algorithm~\cite{Stewart-gi01}).  However, the
algorithm is substantially slower than others.  The SGI and {\sc
stripe} algorithms, for example, compute stripifications of 705 and
917 strips for the 69,451--triangle Stanford bunny, as opposed to the
three strips computed by the tunneling algorithm.  But the SGI and
{\sc stripe} algorithms take only five seconds, as opposed to the ten
{\em minutes} of the tunneling algorithm.

Tunneling is an incremental operation that can be used to improve upon
a given stripification.  When strips are broken or very short strips
are created due to a topological change in a CLOD mesh, the tunneling
operation can be applied to ``repair'' the stripification.  This is
opposite to the Skip Strip method (which maintains subsequences of the
original strips) but is similar to the DStrips method (which makes
incremental repairs in the region of the change).  


