“Optimization of mesh locality for transparent vertex caching” by Hoppe

Bus traffic between the graphics subsystem and memory can become a bottleneck when rendering geometrically complex meshes. In this paper, we investigate the use of vertex caching to transparently reduce geometry bandwidth. Use of an indexed triangle strip representation permits application programs to animate the meshes at video rates, and provides backward compatibility on legacy hardware. The efficiency of vertex caching is maximized by reordering the faces in the mesh during a preprocess. We present two reordering techniques, a fast greedy strip-growing algorithm and a local optimization algorithm. The strip-growing algorithm performs lookahead simulations of the cache to adapt strip lengths to the cache capacity. The local optimization algorithm improves this initial result by exploring a set of perturbations to the face ordering. The resulting cache miss rates are comparable to the efficiency of the earlier mesh buffer scheme described by Deering and Chow, even though the vertex cache is not actively managed.

1. Bar-Yehuda, R., and Gotsman, C. Time/space tradeoffs for polygon mesh rendering. ACM Transactions on Graphics 15, 2 (April 1996), 141-152.
2. Birdwell, K. Valve Corp. Personal communication, 1998.
3. Chow, M. Optimized geometry compression for real-time rendering. In Visualization ’97 Proceedings (1997), IEEE, pp. 347-354.
4. Deering, M. Geometry compression. Computer Graphics (SIG-GRAPH ’95 Proceedings) (1995), 13-20.
5. Evans, F., Skiena, S., and Varshney, A. Optimizing triangle strips for fast rendering. In Visualization ’96 Proceedings (1996), IEEE, pp. 319-326.
6. Gumhold, S., and Strasser, W. Real time compression of triangle mesh connectivity. Computer Graphics (SIGGRAPH ’98 Proceedings) (1998), 133-140.
7. Hakura, Z., and Gupta, A. The design and analysis of a cache architecture for texture mapping. In Proceedings of the 24th International Symposium on Computer Architecture (June 1997), pp. 108-120.
8. Hoppe, H. View-dependent refinement of progressive meshes. Computer Graphics (SIGGRAPH ’97 Proceedings) (1997), 189-198.
9. Hoppe, H. Efficient implementation of progressive meshes. Computers and Graphics 22, 1 (1998), 27-36.
10. Lengyel, J. Compression of time-dependent geometry. In Symposium on Interactive 3D Graphics (1999), ACM, pp. 89-96.
11. Li, J., Li, J., and Kuo, C. C. Progressive compression of 3D graphics models. In Multimedia Computing and Systems (April 1997), IEEE, pp. 135-142.
12. Neider, J., Davis, T., and Woo, M. OpenGL Programming Guide. Addison-Wesley, 1993.
13. Taubin, G., Gueziec, A., Horn, W., and Lazarus, F. Progressive forest split compression. Computer Graphics (SIGGRAPH ’98 Proceedings) (1998), 123-132.
14. Taubin, G., and Rossignac, J. Geometric compression through topological surgery. ACMTransactions on Graphics 17, 2 (April 1998), 84-115.
15. Touma, C., and Gotsman, C. Triangle mesh compression. In Proceedings of Graphics Interface ’98 (1998), pp. 26-34.
16. Xiang, X., Held, M., and Mitchell, J. Fast and effective stripification of polygonal surface models. In Symposium on Interactive 3D Graphics (1999), ACM, pp. 71-78.