1 Introduction

In various computer graphics applications such as CAD, digital cartography, medicine, etc., triangle models are often used to visualize surfaces and volumes. The speed of high performance rendering engines on triangular meshes is usually bounded by the rate at which triangulation data is sent into the machine. To draw independent triangles we need to transmit three vertices per triangle to the graphic system, but we can minimize the data by an ordering the triangles so that consecutive triangles share an edge. Using such an ordering, called triangle strip, the first triangle is defined by three vertices and the following triangles by only one additional vertex. This reduces the rendering time by avoiding redundant data transmission to engine and redundant lighting and transformation computations. As the datasets in practice are usually huge, substantial speedup and/or data compression [8] may be achieved in this way.

The triangle strip primitive is supported in many graphics libraries such as Irix-GL or OpenGL. In Fig. 1 a sequential triangle strip is shown. In this case each triangle is described by i th, (i + 1) st, and (i+2) nd vertices of the strip. Using the sequential strip, the transmit cost of n triangles can be reduced from 3n to n+2 vertices.

There also exists a situation where the triangle adjacency does not allow a sequential encoding. In Fig. 2 we have to break the strip, add an inverted edge 4',4 and continue with the rest of sequence. This inverting operation is called swap and strips using these swaps are called generalized strips.

   

Figure 1: The order of vertices to send is 1,2,3,4,5,6,7.	Figure 2: The order of vertices to send is 1,2,3,4,4',swap/4,5,6,7.

The swap had been implemented as a one-bit attribute in GL. For better portability it was decided to not support it in OpenGL and one more vertex is sent to the engine instead. This means that an empty triangle appears. Although the swap costs one vertex, it is still cheaper to use the swap instead of starting a new triangle strip that costs two vertices.

Due to importance of this topic, many algorithms already exist. Because the computing of an optimal set of triangle strips is NP-complete [5], some heuristic is necessary. This means that each method has its own advantages and disadvantages. In this paper we want to explore and compare some of the existing algorithms. Using this knowledge, we want to develop our own stripification algorithm in the future.

There exist several different criteria of strip quality, such as number of strips, number of vertices, locality of the strip etc. The locality criteria are mainly useful if level-of-detail clipping of geometric models in complicated scenes is expected. As, at present, we solve only static visualization of simple scenes, we concentrated on number of strips and number of vertices criteria.

In Section 2, some of existing methods for non-hierarchical meshes are shown. In section 3, we describe the SGI based algorithms into more details [1]. Another OpenGL speed-up technique that can be combined with strips is presented in section 4. Experimental results are published in section 5. Conclusion and future work are discussed in section 6.