Akeley et al. [1] have developed an algorithm, known
as *tomesh* or *SGI algorithm*, that converts a fully
triangulated mesh into triangle strips. The algorithm tries to
build triangle strips which do not divide the remaining
triangulation into too many small parts. The strip is starting in
the triangle with the least number of neighbors. Then a greedy
heuristic is adding neighboring triangles with the least number of
neighbors. If more triangles has the same number of neighbors, the
algorithm looks one step ahead. As this algorithm is one of the
most often used, we decided to pick it for implementation.
Therefore, more details are presented in Section 3.

Other method for stripification is STRIPE [6,7]. It is public free and it is used by many authors for comparison. We will also use it as one of method, to be able to compare our future algorithm to some other (indirectly). The main idea of this algorithm is base on a fact that there exists a lot of models that are not fully triangulized (i.e., contains quadrilateral faces). These faces are often arranged in large rectangular regions called "patches". In the first pass (called "Global algorithm") the algorithm analyze these patches and stripify them. For remaining triangles a "Local algorithm" is used. The local algorithm is based on the same idea as the SGI algorithm.

A method based on a spanning tree duality is presented in [12]. This algorithm constructs a spanning tree in the dual graph of the triangulation. Then it partitions the tree into a set of paths, corresponding to Hamiltonian triangulations, and greedily decomposes the corresponding Hamiltonian strips into sequential strips. Finally it concatenates short strips into longer strips using a set of postprocessing heuristics.

The tunneling algorithm [11] can be used for both static and continuous level-of-detail (CLOD) meshes. It uses the dual graph representation. There are two different edges in this representation - "strip edge" that is a part of strip and "non-strip edge". The tunnel in the dual graph is a sequence joining two ends of strips and alternating between strip and non-strip edges. By changing the strip edge for non-strip edge and vice versa, the number of strips is reduced by one.

Petr Vanecek, pet@students.zcu.cz, 2002-03-19