Triangle Strip Tunneling Algorithm

Triangle Strips

Strips are more efficient because each successive triangle in the strip is defined by a single additional vertex; the triangle's other two vertices are already known from the preceding triangle in the strip. A strip of k triangles can be drawn with 2 + k vertices. Without a strip, the k triangles would require 3 k vertices. With CPU-to-graphics processor bandwidth a bottleneck, the use of triangle strips can greatly accelerate rendering.

This page describes a novel method of computing a small set of triangle strips that covers a mesh, using a technique dubbed ``tunnelling.'' A paper on the technique is available.

Tunnels

The dual graph of a mesh has a node corresponding to each face of the mesh and has an edge between two nodes whose corresponding faces are adjacent. Each edge of the dual graph is either a "strip edge" or a "nonstrip edge". Strip edges join nodes whose corresponding faces are adjacent in a triangle strip.

A mesh with three triangle strips	The dual graph with solid strip edges and dashed nonstrip edges

A tunnel in the dual graph is a sequence of edges that joins the ends of two strips. A tunnel starts and ends with a nonstrip edge. It alternates between strip and nonstrip edge.

The dual graph of part of a mesh, showing four strips	A tunnel joining the ends of two strips

The key observation is that the edges of a tunnel can be complemented to reduce the number of strips by one: Strip edges become nonstrip edges and vice versa.

The dual graph from above with the tunnel edges complemented, showing three strips

Tunneling in Static Meshes

For static meshes, tunneling can be repeated over and over until no more tunnels can be found. With each attempt, a strip end is selected and a tunnel is searched for (using breadth-first search (BFS) in the dual graph) starting from that strip end.

The depth of the BFS can be limited to accelerate the process. Experiments on the Stanford Bunny have shown that the depth can be limited to about 75 edges without substantially affecting the quality of the resulting stripification.

Results in Static Meshes

Here are some stripifications of static meshes produced by repeated tunneling. The stripification made by the classic SGI algorithm is shown for comparison.

The Stanford Bunny with 69,451 faces
SGI algorithm 705 strips	Tunneling algorithm 158 strips

The Stanford Dragon with 871,414 faces
SGI algorithm 17,653 strips	Tunneling algorithm 1,798 strips

Here are some results from other meshes, with execution times reported in seconds. The STRIPE 2.0 algorithm failed for the two largest meshes.

For static meshes, the tunneling algorithm produces much better stripifications, but takes substantially longer than the other methods.

Tunneling in CLOD (Dynamic) Meshes

In CLOD meshes, the mesh topology changes as the viewpoint moves. This is done in order to reduce the number of triangles in areas of low perceptual importance, and to increase the number of triangles in areas of high perceptual importances.

But topology changes cause triangle strips to become fragmented. For example, the edge collapse and vertex split operations used in progressive meshes can sometime increase the number of triangle strips, as follows:

An edge collapse which splits a strip into two

A vertex split which creates a new, short strip

Some splits and collapses don't cause any damage

Tunneling can repair the damage caused by such a topological change. Whenever strips are broken or created by such a topological change, a tunnel search should be performed starting from the strip ends in the vicinity of the topological change.

In addition, tunnel searches should be performed starting from some of the other strip ends in the mesh, since a topological change or even the changes caused by tunneling may allow other tunnels to be found where none existed before.

Results in CLOD Meshes

A sequence of 5,000 topology-changing operations was performed upon a 20,000-face version of the Stanford Bunny. Each operation was an edge collapse (EC) or vertex split (VS), randomly chosen with equal probability. Operations were performed at random locations of the mesh.

The graph below shows how the number of strips (vertical axis) changes as the number of operations (horizontal axis) increases.

In the experiment that produced the red line, each EC or VS was followed by an attempt to join triangle strips that both ended in one of the triangles involved in the EC or VS, or in an adjacent triangle. Such local repairs are not sufficient to maintain a good stripification.

The other three lines show that tunneling can maintain a relatively constant number of triangle strips. In each of those three experiments, each EC or VS was followed by:

• an attempt to find tunnels starting from the triangle strips that ended in one of the triangles involved in the EC or VS, and

• an attempt to find tunnels starting from the ends of some other triangles strips that were not involved in the EV or VS.

For the blue line, each tunnel was bounded in length to 10 edges and there were 5 tunnels attempted elsewhere in the mesh.

For the green line, each tunnel was bounded in length to 20 edges and there were 5 tunnels attempted elsewhere in the mesh.

For the purple line, each tunnel was bounded in length to 50 edges and there were 10 tunnels attempted elsewhere in the mesh.

The grey region shows the minimum number of strips achieved when tunneling is performed repeatedly with no restrictions after each EC or VS operation.

Tunneling clearly helps to maintain a good stripification. The additional time for tunneling can be adjusted with the two parameters above to trade execution speed for stripification quality. Tunneling is fast: The experiment with the blue line took only 104% the time of the "local-only" experiment with the red line.