2 State of the Art

Many works on constructing triangle strips were presented. Arkin et al. [4] show that testing whether a given triangulation of point set or polygon is Hamiltonian (i.e. the dual graph of triangulation contains a Hamilton cycle) can be done in linear time. They prove that related problem of computing a Hamilton triangulation is NP-complete for polygon with holes.

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.