Geometry engine optimization: cache friendly compressed representation of geometry

ABSTRACT

Recent advances in graphics architecture focus on improving texture performance and pixel processing. These have paralleled advances in rich pixel shading algorithms for realistic images. However, applications that require significantly more geometry processing than pixel processing suffer due to limited resource being devoted to the geometry processing part of the graphics pipeline. We present an algorithm to improve the effective geometry processing performance without adding significant hardware. This algorithm computes a representation for geometry that reduces the bandwidth required to transmit it to the graphics subsystem. It also reduces the total geometry processing requirement by increasing the effectiveness of the vertex cache. A goal of this algorithm is to keep the primitive assembly simple for easy hardware implementation.

REFERENCES

• 1: Pierre Alliez , Mathieu Desbrun, Progressive compression for lossless transmission of triangle meshes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.195-202, August 2001 [doi>10.1145/383259.383281]
• 2: Reuven Bar-Yehuda , Craig Gotsman, Time/space tradeoffs for polygon mesh rendering, ACM Transactions on Graphics (TOG), v.15 n.2, p.141-152, April 1996 [doi>10.1145/234972.234976]
• 3: Alexander Bogomjakov , Craig Gotsman, Universal rendering sequences for transparent vertex caching of progressive meshes, No description on Graphics interface 2001, p.81-90, June 07-09, 2001, Ottawa, Ontario, Canada
• 4: Mike M. Chow, Optimized geometry compression for real-time rendering, Proceedings of the 8th conference on Visualization '97, p.347-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 5: Cover, T. M., and Joy, A. T. 1991. Elements of Information. John Wiley and Sons.
• 6: Michael Deering, Geometry compression, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.13-20, September 1995 [doi>10.1145/218380.218391]
• 7: Pablo Diaz-Gutierrez , Anusheel Bhushan , M. Gopi , Renato Pajarola, Single-strips for fast interactive rendering, The Visual Computer: International Journal of Computer Graphics, v.22 n.6, p.372-386, June 2006 [doi>10.1007/s00371-006-0018-2]
• 8: Regina Estkowski , Joseph S. B. Mitchell , Xinyu Xiang, Optimal decomposition of polygonal models into triangle strips, Proceedings of the eighteenth annual symposium on Computational geometry, p.254-263, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513431]
• 9: Francine Evans , Steven Skiena , Amitabh Varshney, Optimizing triangle strips for fast rendering, Proceedings of the 7th conference on Visualization '96, p.319-326, October 28-29, 1996, San Francisco, California, United States
• 10: Pierre-Marie Gandoin , Olivier Devillers, Progressive lossless compression of arbitrary simplicial complexes, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 11: André Guéziec , Frank Bossen , Gabriel Taubin , Claudio Silva, Efficient compression of non-manifold polygonal meshes, Proceedings of the conference on Visualization '99: celebrating ten years, p.73-80, October 1999, San Francisco, California, United States
• 12: Stefan Gumhold , Wolfgang Straßer, Real time compression of triangle mesh connectivity, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.133-140, July 1998 [doi>10.1145/280814.280836]
• 13: Hugues Hoppe, Optimization of mesh locality for transparent vertex caching, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.269-276, July 1999 [doi>10.1145/311535.311565]
• 14: IdSoftware, 2005. http://www.idsoftware.com.
• 15: Isenburg, M. 2001. Triangle strip compression. Computer Graphics Forum 20, 2, 91--101.
• 16: Kronrod, B., and Gotsman, C. 2002. Optimized compression of triangle mesh geometry using prediction trees. In Proceedings of 1st International Symposium on 3D Data Processing Visualization and Transmission (3DPVT-02), IEEE, 602--608.
• 17: Gang Lin , Thomas P. -Y. Yu, An Improved Vertex Caching Scheme for 3D Mesh Rendering, IEEE Transactions on Visualization and Computer Graphics, v.12 n.4, p.640-648, July 2006 [doi>10.1109/TVCG.2006.59]
• 18: Nvidia, 2001. D3d optimization: http://developer.nvidia.com/attach/6523.
• 19: Nvidia, 2004. Triangle strip library:developer.nvidia.com/object/nvtristrip_library.html.
• 20: Budirijanto Purnomo , Jonathan Bilodeau , Jonathan D. Cohen , Subodh Kumar, Hardware-compatible vertex compression using quantization and simplification, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 30-31, 2005, Los Angeles, California [doi>10.1145/1071866.1071876]
• 21: Jarek Rossignac, Edgebreaker: Connectivity Compression for Triangle Meshes, IEEE Transactions on Visualization and Computer Graphics, v.5 n.1, p.47-61, January 1999 [doi>10.1109/2945.764870 ]
• 22: Andrzej Szymczak , Davis King , Jarek Rossignac, An edgebreaker-based efficient compression scheme for regular meshes, Computational Geometry: Theory and Applications, v.20 n.1-2, p.53-68, October 2001 [doi>10.1016/S0925-7721(01)00035-9 ]
• 23: Gabriel Taubin , Jarek Rossignac, Geometric compression through topological surgery, ACM Transactions on Graphics (TOG), v.17 n.2, p.84-115, April 1998 [doi>10.1145/274363.274365]
• 24: Touma, C., and Gotsman, C. 1998. Triangle mesh compression. In Proc. Graphics Interface, ACM, 26--34.
• 25: Xinyu Xiang , Martin Held , Joseph S. B. Mitchell, Fast and effective stripification of polygonal surface models, Proceedings of the 1999 symposium on Interactive 3D graphics, p.71-78, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300531]
• 26: Sung-Eui Yoon , Peter Lindstrom, Mesh Layouts for Block-Based Caches, IEEE Transactions on Visualization and Computer Graphics, v.12 n.5, p.1213-1220, September 2006 [doi>10.1109/TVCG.2006.162]
• 27: Sung-Eui Yoon , Peter Lindstrom , Valerio Pascucci , Dinesh Manocha, Cache-oblivious mesh layouts, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Graphics processors

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Keywords:
data compression, graphics hardware cache, interactive navigation