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

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