Billboard clouds for extreme model simplification

ABSTRACT

We introduce billboard clouds -- a new approach for extreme simplification in the context of real-time rendering. 3D models are simplified onto a set of planes with texture and transparency maps. We present an optimization approach to build a billboard cloud given a geometric error threshold. After computing an appropriate density function in plane space, a greedy approach is used to select suitable representative planes. A good surface approximation is ensured by favoring planes that are "nearly tangent" to the model. This method does not require connectivity information, but instead avoids cracks by projecting primitives onto multiple planes when needed. For extreme simplification, our approach combines the strengths of mesh decimation and image-based impostors. We demonstrate our technique on a large class of models, including smooth manifolds and composite objects.

REFERENCES

• 1: ALIAGA, D., AND LASTRA, A. 1998. Smooth transitions in texture-based simplification. Computers & Graphics 22, 1, 71--81.
• 2: Daniel G. Aliaga , Anselmo Lastra, Automatic image placement to provide a guaranteed frame rate, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.307-316, July 1999 [doi>10.1145/311535.311574]
• 3: Daniel G. Aliaga, Visualization of complex models using dynamic texture-based simplification, Proceedings of the 7th conference on Visualization '96, p.101-ff., October 28-29, 1996, San Francisco, California, United States
• 4: CAZALS, F., DRETTAKIS, G., AND PUECH, C. 1995. Filtering, clustering and hierarchy construction: a new solution for raytracing complex scenes. Computer Graphics Forum (Eurographics '95).
• 5: CGAL library. http://www.cgal.org.
• 6: P. Cignoni , C. Montani , R. Scopigno , C. Rocchini, A general method for preserving attribute values on simplified meshes, Proceedings of the conference on Visualization '98, p.59-66, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 7: Jonathan Cohen , Marc Olano , Dinesh Manocha, Appearance-preserving simplification, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.115-122, July 1998 [doi>10.1145/280814.280832]
• 8: William J. Dally , Leonard McMillan , Gary Bishop , Henry Fuchs, The Delta Tree: An Object-Centered Approach to Image-Based Rendering, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 9: Lucia Darsa , Bruno Costa Silva , Amitabh Varshney, Navigating static environments using image-space simplification and morphing, Proceedings of the 1997 symposium on Interactive 3D graphics, p.25-ff., April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253298]
• 10: DÉCORET, X., SILLION, F., SCHAUFLER, G., AND DORSEY, J. 1999. Multi-layered impostors for accelerated rendering. Computer Graphics Forum (Eurographics '98) 18, 3.
• 11: E. G. Coffman, Jr. , M. R. Garey , D. S. Johnson, Approximation algorithms for bin packing: a survey, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 12: Carl Erikson , Dinesh Manocha, GAPS: general and automatic polygonal simplification, Proceedings of the 1999 symposium on Interactive 3D graphics, p.79-88, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300532]
• 13: FAUGERAS, O., HEBERT, M., AND PAUCHON, E. 1983. Segmentation of range data into planar and quadratic patches. In Proceedings of IEEE Conf. on Computer Vision and Pattern Recognition.
• 14: Michael Garland , Paul S. Heckbert, Surface simplification using quadric error metrics, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.209-216, August 1997 [doi>10.1145/258734.258849]
• 15: Michael Garland , Andrew Willmott , Paul S. Heckbert, Hierarchical face clustering on polygonal surfaces, Proceedings of the 2001 symposium on Interactive 3D graphics, p.49-58, March 2001 [doi>10.1145/364338.364345]
• 16: GROSSMAN, J. P., AND DALLY, W. 1998. Point sample rendering. In Eurographics Rendering Workshop.
• 17: HECKBERT, P., AND GARLAND, M. 1997. Survey of polygonal surface simplification algorithms. Tech. rep., Carnegie Mellon University.
• 18: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 19: HOUGH, P., 1962. Method and means for recognizing complex patterns. US Patent 3, 069, 654.
• 20: Alan D. Kalvin , Russell H. Taylor, Superfaces: Polygonal Mesh Simplification with Bounded Error, IEEE Computer Graphics and Applications, v.16 n.3, p.64-77, May 1996 [doi>10.1109/38.491187]
• 21: Martin Kraus , Thomas Ertl, Adaptive texture maps, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
• 22: Jerome Edward Lengyel, Real-Time Hair, Proceedings of the Eurographics Workshop on Rendering Techniques 2000, p.243-256, June 26-28, 2000
• 23: LEVOY, M., AND WHITTED, T. 1985. The use of points as a display primitive. Tech. Rep. 85-022, U. of North Carolina.
• 24: Peter Lindstrom , Greg Turk, Image-driven simplification, ACM Transactions on Graphics (TOG), v.19 n.3, p.204-241, July 2000 [doi>10.1145/353981.353995]
• 25: Kok-Lim Low , Tiow-Seng Tan, Model simplification using vertex-clustering, Proceedings of the 1997 symposium on Interactive 3D graphics, p.75-ff., April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253310]
• 26: David Luebke , Carl Erikson, View-dependent simplification of arbitrary polygonal environments, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.199-208, August 1997 [doi>10.1145/258734.258847]
• 27: David P. Luebke, A Developer's Survey of Polygonal Simplification Algorithms, IEEE Computer Graphics and Applications, v.21 n.3, p.24-35, May 2001
• 28: Paulo W. C. Maciel , Peter Shirley, Visual navigation of large environments using textured clusters, Proceedings of the 1995 symposium on Interactive 3D graphics, p.95-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199420]
• 29: MAX, N., DEUSSEN, O., AND KEATING, B. 1999. Hierarchical image-based rendering using texture mapping hardware. In Eurographics Rendering Workshop.
• 30: MEYER, A., AND NEYRET, F. 1998. Interactive volumetric textures. In Eurographics Rendering Workshop.
• 31: Manuel M. Oliveira , Gary Bishop , David McAllister, Relief texture mapping, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.359-368, July 2000 [doi>10.1145/344779.344947]
• 32: Hanspeter Pfister , Matthias Zwicker , Jeroen van Baar , Markus Gross, Surfels: surface elements as rendering primitives, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.335-342, July 2000 [doi>10.1145/344779.344936]
• 33: Voicu Popescu , Anselmo Lastra , Daniel Aliaga , Manuel de Oliveira Neto, Efficient warping for architectural walkthroughs using layered depth images, Proceedings of the conference on Visualization '98, p.211-215, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 34: Jovan Popović , Hugues Hoppe, Progressive simplicial complexes, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.217-224, August 1997 [doi>10.1145/258734.258852]
• 35: Thomas Porter , Tom Duff, Compositing digital images, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.253-259, January 1984
• 36: PUPPO, E., AND SCOPIGNO, R., 1997. Simplification, lod and multiresolution - principles and applications.
• 37: ROSSIGNAC, J., AND BORREL, P. 1993. Multi-resolution 3D approximation for rendering complex scenes. In 2nd Conf. on Geometric Modelling in Computer Graphics.
• 38: Szymon Rusinkiewicz , Marc Levoy, QSplat: a multiresolution point rendering system for large meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.343-352, July 2000 [doi>10.1145/344779.344940]
• 39: Pedro V. Sander , Xianfeng Gu , Steven J. Gortler , Hugues Hoppe , John Snyder, Silhouette clipping, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.327-334, July 2000 [doi>10.1145/344779.344935]
• 40: SCHAUFLER, G., AND STURZLINGER, W. 1996. A three-dimensional image cache for virtual reality. Computer Graphics Forum (Eurographics '96) 15, 3.
• 41: SCHAUFLER, G. 1998. Per-object image warping with layered impostors. In Eurographics Rendering Workshop.
• 42: Mark Segal , Carl Korobkin , Rolf van Widenfelt , Jim Foran , Paul Haeberli, Fast shadows and lighting effects using texture mapping, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.249-252, July 1992
• 43: Jonathan Shade , Dani Lischinski , David H. Salesin , Tony DeRose , John Snyder, Hierarchical image caching for accelerated walkthroughs of complex environments, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.75-82, August 1996 [doi>10.1145/237170.237209]
• 44: Jonathan Shade , Steven Gortler , Li-wei He , Richard Szeliski, Layered depth images, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.231-242, July 1998 [doi>10.1145/280814.280882]
• 45: SHEFFER, A. 2001. Model simplification for meshing using face clustering. Computer-Aided Design (CAD) 33, 925--934.
• 46: SILLION, F., DRETTAKIS, G., AND BODELET, B. 1997. Efficient impostor manipulation for real-time visualization of urban scenery. Computer Graphics Forum (Eurographics '97) 16, 3.
• 47: Jay Torborg , James T. Kajiya, Talisman: commodity realtime 3D graphics for the PC, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.353-363, August 1996 [doi>10.1145/237170.237274]
• 48: Andrew Thomas Wilson , Dinesh Manocha, Spatially encoded image-space simplifications for interactive walkthrough, 2002
• 49: WYNN, C. Implementing bump-mapping using register combiners. http://developer.nvidia.com/.
• 50: Eugene Zhang , Greg Turk, Visibility-guided simplification, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism

Keywords:
LOD, billboard, error-driven simplification, image-based rendering, model simplification, real-time rendering