| Speaker: | Joseph S.B. Mitchell University at Stony Brook |
|---|---|
| Topic: | Algorithms for Stripification of Polygonal Surface Models |
| Date: | Wednesday, April 3, 2002 |
| Time: | 11:00 - 12:00pm |
| Place: | Physics-Atmospheric Sciences 224
Refreshments will be served. |
We consider algorithmic issues in a problem of importance in graphics and visualization: computing a succinct encoding of a triangulation of a polygonal surface model in order to be able to transmit and render it efficiently.
CAD/CAM and virtual environments applications often require that very complex datasets be visualized at real-time rates. Current 3D graphics rendering hardware, particularly in low- to mid-range machines, 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 memory.
A common encoding method is based on ``tristrips,'' which permit a minimal cache (two vertices). In some cases (e.g., Iris GL), a tristrip may have swaps, special marks (bits) within a vertex sequence to indicate an exchange of the two cache vertices; alternatively (e.g., OpenGL), a swap can be effected by sending a zero-area triangle (transmitting an extra vertex instead of a ``swap'' bit).
We study the Stripification Problem: The input is a general (manifold) polygonal surface model P: facets are polygons (possibly with holes), specified by lists of vertices; each edge is shared by at most two facets. The output is a list of k tristrips (sequential and/or fan), having m swaps, encoding the n triangles in a triangulation of P. Our objective is to determine a triangulation of P, together with a set of tristrips that encode it, in order to minimize an encoding cost (e.g., the total number of vertices to transmit).
We give very fast and simple stripification algorithms; we prove them effective in theory (via an approximation bound) and in practice (via experiments). We also propose two (much slower) methods for solving the problem to optimality, one based on an integer programming formulation, one based on a branch-and-bound scheme that relies on lower bounding techniques for its efficiency. We have implemented our algorithms within the FTSG (Fast Triangle Strip Generator) software package, which is available for research and commercial applications.
This is joint work with Xinyu Xiang, Regina Estkowski, and Martin Held.
About the speaker:
Joseph S. B. Mitchell received a BS (1981, Physics and Applied Mathematics), and an MS (1981, Mathematics) from Carnegie-Mellon University, and Ph.D. (1986, Operations Research) from Stanford University. Mitchell was with Hughes Research Labs (1981-86) and then on the faculty of Cornell University (1986-1991). He now serves as Professor of Applied Mathematics and Statistics and Research Professor of Computer Science at the University at Stony Brook. Mitchell has received various research awards (NSF Presidential Young Investigator, Fulbright Scholar) and numerous teaching awards. He serves as the current Chair of the Steering Committee for computational geometry.
His primary research area is computational geometry, applied to problems in computer graphics, visualization, air traffic management, manufacturing, and geographic information systems.