“Billboard clouds for extreme model simplification” by Décoret, Durand, Sillion and Dorsey

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.

1. ALIAGA, D., AND LASTRA, A. 1998. Smooth transitions in texture-based simplification. Computers & Graphics 22, 1, 71–81.Google ScholarCross Ref
2. ALIAGA, D., AND LASTRA, A. 1999. Automatic image placement to provide a guaranteed frame rate. In Proceedings of SIGGRAPH ’99. Google Scholar
3. ALIAGA, D. 1996. Visualization of complex models using dynamic texture-based simplification. In IEEE Visualization ’96. Google Scholar
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).Google Scholar
5. CGAL library. http://www.cgal.org.Google Scholar
6. CIGNONI, P., MONTANI, C., SCOPIGNO, R., AND ROCCHINI, C. 1998. A general method for preserving attribute values on simplified meshes. In IEEE Visualization ’98, 59–66. Google Scholar
7. COHEN, J., OLANO, M., AND MANOCHA, D. 1998. Appearance-preserving simplification. In Proceedings of SIGGRAPH ’98. Google Scholar
8. DALLY, W. J., MCMILLAN, L., BISHOP, G., AND FUCHS, H. 1996. The delta tree: An object-centered approach to image-based rendering. Tech. rep., MIT AI Lab #1604. Google Scholar
9. DARSA, L., SILVA, B. C., AND VARSHNEY, A. 1997. Navigating static environments using image-space simplification and morphing. In ACM Symp. Interactive 3D Graphics. Google Scholar
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.Google Scholar
11. E. G. COFFMAN, J., GAREY, M. R., AND JOHNSON, D. S. 1997. Approximation algorithms for bin packing: a survey. 46–93. Google Scholar
12. ERIKSON, C., AND MANOCHA, D. 1999. GAPS: General and automatic polygonal simplification. In ACM Symp. Interactive 3D Graphics. Google Scholar
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.Google Scholar
14. GARLAND, M., AND HECKBERT, P. 1997. Surface simplification using quadric error metrics. In Proceedings of SIGGRAPH ’97. Google Scholar
15. GARLAND, M., WILLMOTT, A., AND HECKBERT, P. 2001. Hierarchical face clustering on polygonal surfaces. In ACM Symp. Interactive 3D Graphics. Google Scholar
16. GROSSMAN, J. P., AND DALLY, W. 1998. Point sample rendering. In Eurographics Rendering Workshop.Google Scholar
17. HECKBERT, P., AND GARLAND, M. 1997. Survey of polygonal surface simplification algorithms. Tech. rep., Carnegie Mellon University.Google Scholar
18. HOCHBAUM, D., Ed. 1997. Approximation Problems for NP-hard Problems. PWS Publishing Company. Google Scholar
19. HOUGH, P., 1962. Method and means for recognizing complex patterns. US Patent 3, 069, 654.Google Scholar
20. KALVIN, A., AND TAYLOR, R. 1996. Superfaces: Polygonal mesh simplification with bounded error. IEEE CG&A 16, 3, 64–77. Google Scholar
21. KRAUS, M., AND ERTL, T. 2002. Adaptive Texture Maps. In Proc. SIGGRAPH/EG Graphics Hardware Workshop ’02, 7–15. Google Scholar
22. LENGYEL, J. 2000. Real-time hair. In Eurographics Rendering Workshop. Google Scholar
23. LEVOY, M., AND WHITTED, T. 1985. The use of points as a display primitive. Tech. Rep. 85-022, U. of North Carolina.Google Scholar
24. LINDSTROM, P., AND TURK, G. 2000. Image-driven simplification. In ACM Transactions on Graphics, vol. 19, 204–241. Google ScholarDigital Library
25. LOW, K., AND TAN, T. 1997. Model simplification using vertex-clustering. In ACM Symp. Interactive 3D Graphics. Google Scholar
26. LUEBKE, D., AND ERIKSON, C. 1997. View-dependent simplification of arbitrary polygonal environments. In Proceedings of SIGGRAPH ’97. Google Scholar
27. LUEBKE, D. 2001. A developer’s survey of polygonal simplification algorithms. IEEE CG&A 21, 3, 24–35. Google Scholar
28. MACIEL, P., AND SHIRLEY, P. 1995. Visual navigation of large environments using textured clusters. In ACM Symp. Interactive 3D Graphics. Google Scholar
29. MAX, N., DEUSSEN, O., AND KEATING, B. 1999. Hierarchical image-based rendering using texture mapping hardware. In Eurographics Rendering Workshop. Google Scholar
30. MEYER, A., AND NEYRET, F. 1998. Interactive volumetric textures. In Eurographics Rendering Workshop.Google Scholar
31. OLIVEIRA, M. M., BISHOP, G., AND MCALLISTER, D. 2000. Relief texture mapping. In Proceedings of SIGGRAPH 2000. Google ScholarDigital Library
32. PFISTER, H., ZWICKER, M., VAN BAAR, J., AND GROSS, M. 2000. Surfels: Surface elements as rendering primitives. In Proceedings of SIGGRAPH 2000. Google ScholarDigital Library
33. POPESCU, V., LASTRA, A., ALIAGA, D., AND DE OLIVEIRA NETO, M. 1998. Efficient warping for architectural walkthroughs using layered depth images. In IEEE Visualization ’98. Google Scholar
34. POPOVIC, J., AND HOPPE, H. 1997. Progressive simplicial complexes. In Proceedings of SIGGRAPH ’97. Google Scholar
35. PORTER, T., AND DUFF, T. 1984. Compositing digital images. Computer Graphics (Proceedings of SIGGRAPH ’84) 18, 3. Google Scholar
36. PUPPO, E., AND SCOPIGNO, R., 1997. Simplification, lod and multiresolution – principles and applications.Google Scholar
37. ROSSIGNAC, J., AND BORREL, P. 1993. Multi-resolution 3D approximation for rendering complex scenes. In 2nd Conf. on Geometric Modelling in Computer Graphics.Google Scholar
38. RUSINKIEWICZ, S., AND LEVOY, M. 2000. Qsplat: A multiresolution point rendering system for large meshes. In Proceedings of SIGGRAPH 2000. Google ScholarDigital Library
39. SANDER, P., GU, X., GORTLER, S., HOPPE, H., AND SNYDER, J. 2000. Silhouette clipping. In Proceedings of SIGGRAPH 2000. Google ScholarDigital Library
40. SCHAUFLER, G., AND STURZLINGER, W. 1996. A three-dimensional image cache for virtual reality. Computer Graphics Forum (Eurographics ’96) 15, 3.Google Scholar
41. SCHAUFLER, G. 1998. Per-object image warping with layered impostors. In Eurographics Rendering Workshop.Google Scholar
42. SEGAL, M., KOROBKIN, C., VAN WIDENFELT, R., FORAN, J., AND HAEBERLI, P. E. 1992. Fast shadows and lighting effects using texture mapping. Computer Graphics (Proceedings of SIGGRAPH ’92) 26, 2, 249–252. Google Scholar
43. SHADE, J., LISCHINSKI, D., SALESIN, D., DEROSE, T., AND SNYDER, J. 1996. Hierarchical image caching for accelerated walkthroughs of complex environments. In Proceedings of SIGGRAPH ’96. Google Scholar
44. SHADE, J., GORTLER, S., HE, L., AND SZELISKI, R. 1998. Layered depth images. In Proceedings of SIGGRAPH ’98. Google Scholar
45. SHEFFER, A. 2001. Model simplification for meshing using face clustering. Computer-Aided Design (CAD) 33, 925–934.Google ScholarCross Ref
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.Google Scholar
47. TORBORG, J., AND KAJIYA, J. 1996. Talisman: Commodity realtime 3d graphics for the pc. In Proceedings of SIGGRAPH ’96. Google Scholar
48. WILSON, A. 2002. Spatially Encoded Image-Space simplifications for Interactive Walkthrough. PhD thesis, University of North Carolina at Chapel Hill’s Dpt of Computer Science. Google Scholar
49. WYNN, C. Implementing bump-mapping using register combiners. http://developer.nvidia.com/.Google Scholar
50. ZHANG, E., AND TURK, G. 2002. Visibility-guided simplification. In IEEE Visualization ’02. Google Scholar