Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11]


Journal of Information Science and Engineering, Vol. 21 No. 6, pp. 1277-1288 (November 2005)

A Simple and Efficient Triangle Strip Filtering Algorithm

Byung-Uck Kim, Kyoung-Wha Kim, Woo-Chan Park, Sung-Bong Yang and Tack-Don Han
Department of Computer Science
Yonsei University
Seoul, 120-749 Korea

A triangle strip is one of the standard rendering primitives used to reduce the amount of data transmitted to the graphics pipeline. In order to exploit such efficient triangulation data in level-of-detail-based rendering applications, real-time updating of triangle strips is required, and it can be done by repeating vertices. However, the number of degenerate triangles increases in strips as the mesh degrades to a coarser level. Such triangles only add overhead to the rendering task. In this paper, we propose a simple and efficient triangle strip filtering algorithm to convert a strip into a more suitable one for display. The proposed algorithm eliminates the vertices of degenerate triangles from a strip and then reorders the remaining vertices in such a way that the two consecutive triangles share a common edge. In addition, the filtering process takes O(n) time units since it scans vertices only once and does so sequentially from the first vertex to the last one in a strip. Experimental results show that the proposed filtering algorithm not only reduces the amount of data transmitted to the graphics pipeline by 22.2% on average, but also slightly reduces the filtering time by 7.1% on average, compared with the previous method.

Keywords: 3D graphics, triangle mesh, triangle strip, level-of-detail, degenerate triangle

Full Text () Retrieve PDF document (200511_11.pdf)

Received May 29, 2003; revised May 18, 2004; accepted May 31, 2004.
Communicated by C. C. Jay Kuo.