| A fundamental algorithmic problem in computer graphics is that of computing a succinct encoding of a triangulation of a polygonal surface 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 (provably good encodings) and in practice. Our methods are based on carefully constructed search trees in the dual graph, followed by algorithms 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 (heuristic) 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 encodings, while requiring significantly less computing time on a large variety of datasets. Further, FTSG is carefully engineered and implemented to be robust, even in the face of highly degenerate and corrupted real-world data. In addition to fast and effective practical algorithms, we also develop optimization algorithms to extract a minimum number of tristrips from a given mesh, using both integer programming and branch-and-bound methods. We are able to find optimal solutions for models containing several tens of triangles in a few minutes. We also incorporate our optimization algorithms into FTSG to provide the user the option of spending more CPU time to obtain fewer tristrips. Furthermore, we study the effect of allowing a small on-board vertex cache on computing a succinct encoding of a triangulation. Methods of maximizing cache utility are developed in an attempt to minimize the encoding cost. |
