Fast and Effective Stripification of Polygonal Surface Models

A fundamental algorithmic problem in computer graphics is that of computing a succinct encoding of a triangulation of a polygonal sur-face model in order to be able to transmit and render it efficiently. The goal is to take a given polygonal surface model, whose facets are given by (possibly multiply-connected) polygons, triangulate its facets, and then decompose the triangulation into a small number of "tristrips," each of which has its connectivity stored implicitly in the ordering of the data points. We develop methods that are effective in solving the stripification problem, both in theory (prov-ably good encodings) and in practice. Our methods are based on carefully constructed search trees in the dual graph, followed by al-gorithms to decompose dual trees into tristrips. One decomposition algorithm is provably optimal (based on dynamic programming), allowing us a sound basis of comparison among our other (heuris-tic) algorithms. We demonstrate the speed and effectiveness of our algorithms through a battery of experiments. In comparison with the recently released STRIPE system for stripification, we find that our stripifier, FTSG, produces comparable or better quality encod-ings, while requiring significantly less computing time on a large variety of datasets. Further, FTSG is carefully engineered and im-plemented to be robust, even in the face of highly degenerate and corrupted real-world data.