“Simplifying complex environments using incremental textured depth meshes” by Wilson and Manocha

  • ©Andrew Wilson and Dinesh Manocha




    Simplifying complex environments using incremental textured depth meshes



    We present an incremental algorithm to compute image-based simplifications of a large environment. We use an optimization-based approach to generate samples based on scene visibility, and from each viewpoint create textured depth meshes (TDMs) using sampled range panoramas of the environment. The optimization function minimizes artifacts such as skins and cracks in the reconstruction. We also present an encoding scheme for multiple TDMs that exploits spatial coherence among different viewpoints. The resulting simplifications, incremental textured depth meshes (ITDMs), reduce preprocessing, storage, rendering costs and visible artifacts. Our algorithm has been applied to large, complex synthetic environments comprising millions of primitives. It is able to render them at 20 — 40 frames a second on a PC with little loss in visual fidelity.


    1. ALIAGA, D., AND LASTRA, A. 1999. Automatic image placement to provide a guaranteed frame rate. In Proc. of ACM SIGGRAPH 1999. Google ScholarDigital Library
    2. ALIAGA, D., COHEN, J., WILSON, A., ZHANG, H., ERIKSON, C., HOFF, K., HUDSON, T., STÜRZLINGER, W., BAKER, E., BASTOS, R., WHITTON, M., BROOKS, F., AND MANOCHA, D. 1999. MMR: An integrated massive model rendering system using geometric and image-based acceleration. In Proc. of ACM Symposium on Interactive 3D Graphics 1999. Google Scholar
    3. ALIAGA, D., FUNKHOUSER, T., YANOVSKY, D., AND CARLBOM, I. 2002. Sea of images. In Proc. of IEEE Visualization 2002. Google ScholarDigital Library
    4. ALIAGA, D. G. 1996. Visualization of complex models using dynamic texture-based simplification. In Proc. of IEEE Visualization 1996, 101–106. Google ScholarDigital Library
    5. BANTA, J., ZHIEN, Y., WANG, X., ZHANG, G., SMITH, M., AND ABIDI, M. 1995. A best-next-view algorithm for three-dimensional scene reconstruction using range images. Proc. of SPIE 2588, 418–429.Google Scholar
    6. BAXTER, B., SUD, A., GOVINDARAJU, N., AND MANOCHA, D. 2002. Gigawalk: Interactive walkthrough of complex 3d environments. Proc. of Eurographics Workshop on Rendering 2002. Google Scholar
    7. CHANG, C., LI, Z., VARSHNEY, A., AND GE, Q. 2001. Hierarchical image-based and polygon-based rendering for large-scale visualization. In Scientific Visualization, Springer-Verlag.Google Scholar
    8. COHEN-OR, D., CHRYSANTHOU, Y., DURAND, F., GREENE, N., KOLTUN, V., AND SILVA, C. 2001. Visibility, problems, techniques and applications. ACM SIGGRAPH 2001 Course Notes # 30.Google Scholar
    9. CURLESS, B., AND LEVOY, M. 1996. A volumetric method for building complex models from range images. In ACM SIGGRAPH ’96 Conference Proceedings, 303–312. Google Scholar
    10. DARSA, L., COSTA, B., AND VARSHNEY, A. 1998. Walkthroughs of complex environments using image-based simplification. Computer and Graphics 22, 1, 55–69.Google ScholarCross Ref
    11. DEBEVEC, P., YU, Y., AND BORSHUKOV, G. 1998. Efficient view-dependent image-based rendering with projective textures. Proc. of Eurographics Workshop on Rendering 1998, 105–116.Google ScholarCross Ref
    12. DECORET, X., SCHAUFLER, G., SILLION, F., AND DORSEY, J. 1999. Multi-layered impostors for accelerated rendering. Computer Graphics Forum 18, 3.Google ScholarCross Ref
    13. EL-SANA, J., SOKOLOVSKY, N., AND SILVA, C. 2001. Integrating occlusion culling with view-dependent rendering. Proc. of IEEE Visualization 2001. Google ScholarDigital Library
    14. ERIKSON, C., AND MANOCHA, D. 1999. GAPS: General and Automatic Polygonal Simplification. In Proc. of ACM Symposium on Interactive 3D Graphics 1999. Google ScholarDigital Library
    15. FLEISHMAN, S., COHEN-OR, D., AND LISCHINSKI, D. 2000. Automatic Camera Placement for Image-Based Modeling. In Computer Graphics Forum 19(2), pp. 100–110, June 2000.Google ScholarCross Ref
    16. GARLAND, M., AND HECKBERT, P. 1997. Surface simplification using quadric error bounds. Proc. of ACM SIGGRAPH 1997, 209–216. Google Scholar
    17. GONZALEZ-BANOS, H., AND LATOMBE, J. 1998. Planning robot motions for range-image acquisition and automatic 3d model construction. In Proc. AAAI Fall Symp., AAAI Press.Google Scholar
    18. GONZALEZ-BANOS, H., AND LATOMBE, J. 2001. A randomized art-gallery algorithm for sensor placement. In Proc. ACM Symp. on Computational Geometry. Google Scholar
    19. GOVINDARAJU, N., SUD, A., YOON, S.-E., AND MANOCHA, D. 2003. Interactive visibility culling for complex environments using occlusion switches. To appear in ACM Symposium on Interactive 3D Graphics. Google Scholar
    20. GREENE, N., KASS, M., AND MILLER, G. 1993. Hierarchical z-buffer visibility. In Proc. of ACM SIGGRAPH 1993, 231–238. Google Scholar
    21. HOPPE, H. 1997. View dependent refinement of progressive meshes. In Proc. of ACM SIGGRAPH 1997, 189–198. Google Scholar
    22. JESCHKE, S., AND WIMMER, M. 2002. Textured depth mesh for real-time rendering of arbitrary scenes. In Proc. Eurographics Workshop on Rendering 2002. Google ScholarDigital Library
    23. LEVOY, M. 1995. Polygon-assisted JPEG and MPEG compression of synthetic images. In Proc. of ACM SIGGRAPH 1995, 21–28. Google Scholar
    24. LINDSTROM, P., AND TURK, G. 2000. Image-driven simplification. ACM Trans. on Graphics 19, 3, 204–241. Google ScholarDigital Library
    25. LUEBKE, D., AND ERIKSON, C. 1997. View-dependent simplification of arbitrary polygon environments. In Proc. of ACM SIGGRAPH 1997. Google Scholar
    26. LUEBKE, D., REDDY, M., COHEN, J., VARSHNEY, A., WATSON, B., AND HUEBNER, R. 2002. Level of Detail for 3D Graphics. Morgan-Kaufmann. Google Scholar
    27. MACIEL, P., AND SHIRLEY, P. 1995. Visual navigation of large environments using textured clusters. In ACM Symposium on Interactive 3D Graphics 1995, 95–102. Google Scholar
    28. MAVER, J., AND BAJCSY, R. 1993. Occlusions as a guide for planning the next view. IEEE PAMI 15, 5, 417–433. Google ScholarDigital Library
    29. MAX, N., AND OHSAKI, K. 1995. Rendering trees from precomputed Z-buffer views. In Proc. of Eurographics Rendering Workshop 1995.Google ScholarCross Ref
    30. MCMILLAN, L., AND BISHOP, G. 1995. Plenoptic modeling: An image-based rendering system. In Proc. of ACM SIGGRAPH 1995, 39–46. Google Scholar
    31. NYLAND, L., LASTRA, A., MCALLISTER, D., POPESCU, V., AND MCCUE, C. 2001. Capturing, processing and rendering real-world scences. In Videometrics and Optical Methods for 3D Shape Measurement, Electronic Imaging, vol. SPIE 4309.Google Scholar
    32. O’ROURKE, J. 1997. Visibility. In Handbook of Discrete and Computational Geometry, CRC Press LLC, J. E. Goodman and J. O’Rourke, Eds., 467–480. Google ScholarDigital Library
    33. PITO, R. 1999. A solution to the next best view problem for automated surface acquisition. IEEE Trans. Pattern Analysis and Machine Intelligence 21, 1016–1030. Google ScholarDigital Library
    34. POPESCU, V. AND LASTRA, A. 2001. The Vacuum Buffer. Proc. of ACM Symposium in Interactive 3D Graphics 2001. Google ScholarDigital Library
    35. REED, M., AND ALLEN, P. K. 1999. Constraint-based sensor planning for scene modeling. Computational Intelligence in Robotics and Automation.Google Scholar
    36. SCHAUFLER, G., AND STÜRZLINGER, W. 1996. A three dimensional image cache for virtual reality. Computer Graphics Forum 15, 3, C227–C235.Google ScholarCross Ref
    37. SHADE, J., LISCHINSKI, D., SALESIN, D., DEROSE, T., AND SNYDER, J. 1996. Hierarchical image caching for accelerated walkthroughs of complex environments. In Proc. of ACM SIGGRAPH 1996, 75–82. Google Scholar
    38. SHADE, J., GORTLER, S., WEI HE, L., AND SZELISKI, R. 1998. Layered depth images. Proc. of ACM SIGGRAPH 1998, 231–242. Google Scholar
    39. SILLION, F., DRETTAKIS, G., AND BODELET, B. 1997. Efficient impostor manipulation for real-time visualization of urban scenery. In Computer Graphics Forum, vol. 16.Google Scholar
    40. WILSON, A., MAYER-PATEL, K., AND MANOCHA, D. 2001. Spatially-encoded far-field representations for interactive walkthroughs. Proc. of ACM Multimedia 2001. Google ScholarCross Ref
    41. WILSON, A. 2002. Spatially encoded image-space simplifications for interactive walkthrough. Ph.D. dissertation, University of North Carolina at Chapel Hill. Google Scholar
    42. WOO, M., NEIDER, J., AND DAVIS, T. 1997. OpenGL Programming Guide, Second Edition. Addison Wesley.Google Scholar
    43. XIA, J., EL-SANA, J., AND VARSHNEY, A. 1997. Adaptive real-time level-of-detail-based rendering for polygonal models. IEEE Transactions on Visualization and Computer Graphics 3, 2 (June), 171–183. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: