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.

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 |

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.

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.

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.

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.

Up to research page.