Stripification of Polyhedral Models

CAD/CAM and virtual environments applications often require that very complex datasets be visualized at real-time rates. Current 3D graphics rendering hardware often faces a memory bus bandwidth bottleneck in the processor-to-graphics pipeline. One naturally wants to avoid rendering unnecessary triangles (e.g., through visibility culling). Also, it is common to simplify and approximate complex models. But it is also important to minimize the time needed to transmit N triangles that are to be rendered, e.g., by compressing the geometric and topological information in a model, transmitting the compressed data, and decompressing at the rendering stage, hopefully using a very small on-chip cache.

A common encoding method is based on ``tristrips,'' which permit a minimal cache (two vertices): when vertex V[i+2] is transmitted, it, together with the two cache vertices V[i] and V[i+1], determines a triangle. A tristrip specifies a triangulation at a cost of one vertex per triangle, versus sending three vertices per triangle in a conventional encoding of a triangulation.

Obviously, a given triangulation need not allow for using only one tristrip. Then, the goal is to encode it with few tristrips, using a minimal number of vertices.

We designed and implemented a Fast Triangle Strip Generator, FTSG. In comparison with the STRIPE 2.0 system for stripification, we find that 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. FTSG cooperates closely with FIST, our Fast Industrial-Strength Triangulation system.

This project was joint work with Joe Mitchell and Xinyu Xiang. Most of the implementation of FTSG has been carried out by Xinyu Xiang at the Computational Geometry Lab of the State University of New York at Stony Brook, Stony Brook, USA. Financial support and hardware grants for this project have been provided by Sun Microsystems.

The following images show triangle strips computed by means of FTSG. (Click on an image icon in order to see the full-size image. The full-size images have about 600x600 pixels.) The models displayed were obtained from the web. In particular, we tested models ftp'ed from Geo-metricks and DIGIGRAPH.

Results of FTSG stripification of the cow. Left: Stripified cow, with different strips having different colors. Right: A zoomed view, with spanning tree edges highlighted on the cow's head.

Results of FTSG stripification of the shark. Left: Stripified shark, with different strips having different colors. Right: A zoomed view, with spanning tree edges highlighted on the shark's body.

Copyright © 2024 Martin Held, held@cs.sbg.ac.at. All rights reserved. Impressum and Disclaimer. file last modified: Thursday, 27-Feb-2020 07:29:07 CET