|
Published Articles >> Table of Contents >> Abstract
January/February 2005 (Vol. 11, No. 1)
pp. 35-47
vLOD: High-Fidelity Walkthrough of Large Virtual Environments
Jatin Chhugani
Budirijanto Purnomo
Shankar Krishnan
Jonathan Cohen
Suresh Venkatasubramanian
David S. Johnson
Subodh Kumar, IEEE Computer Society
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TVCG.2005.17
Send link to a friend
| Abstract |
|
We present visibility computation and data organization algorithms that enable high-fidelity walkthroughs of large 3D geometric data sets. A novel feature of our walkthrough system is that it performs work proportional only to the required detail in visible geometry at the rendering time. To accomplish this, we use a precomputation phase that efficiently generates per cell vLOD: the geometry visible from a view-region at the right level of detail. We encode changes between neighboring cells' vLODs, which are not required to be memory resident. At the rendering time, we incrementally construct the vLOD for the current view-cell and render it. We have a small CPU and memory requirement for rendering and are able to display models with tens of millions of polygons at interactive frame rates with less than one pixel screen-space deviation and accurate visibility.
|
 References
|
[1] D. Aliaga, J. Cohen, A. Wilson, E. Baker, H. Zhang, C. Erikson, K. Hoff, T. Hudson, W. Stuerzlinger, R. Bastos, M. Whitton, F. Brooks, and D. Manocha, “MMR: An Integrated Massive Model Rendering System Using Geometric and Image-Based Acceleration,” Proc. Symp. Interactive 3D Graphics, pp. 101-106, 1999.
[2] F. Alizadeh, R.M. Karp, L.A. Newberg, and D.K. Weisser, “Physical Mapping of Chromosomes: A Combinatorial Problem in Molecular Biology,” Proc. ACM/SIAM Symp. Discrete Algorithms, pp. 371-381, 1993.
[3] C. Andújar, C. Saona-Vázquez, I. Navazo, and P. Brunet, “Integrating Occlusion Culling and Levels of Detail through Hardly-Visible Sets,” Computer Graphics Forum, vol. 19, no. 3, pp. C187-C194, Aug. 2000.
[4] W.V. Baxter, A. Sud, N. Govindaraju, and D. Manocha, “Gigawalk: Interactive Walkthrough of Complex Environments,” Technical Report TR02-013, Univ. of North Carolina at Chapel Hill, 2002.
[5] J.L. Bentley, “Multidimensional Binary Search Trees Used for Associative Searching,” Comm. ACM, vol. 18, no. 9, pp. 509-517, Sept., 1975.
[6] J. Chhugani, B. Purnomo, S. Krishnan, J. Cohen, and S. Kumar, “vLOD: A Scalable System for Interactive Walkthroughs of Very Large Virtual Environments,” Technical Report JHU-CS-GL03-3, http://www.cs.jhu.edu/graphics/html/TR.html, Computer Science Dept., Johns Hopkins Univ., 2003.
[7] Y. Chrysanthou, D. Cohen-Or, and E. Zadicario, “Viewspace Partitioning of Densely Occluded Scenes,” Proc. 14th ACM Symp. Computational Geometry (SCG '98), pp. 41-414, June 1998.
[8] E. Cohen, M. Datar, S. Fujiwara, A. Gionis, P. Indyk, R. Motwani, J.D. Ullman, and C. Yang, “Finding Interesting Associations without Support Pruning,” Proc. Int'l Conf. Data Eng., pp. 489-499, 2000.
[9] S. Coorg and S. Teller, “Real-time Occlusion Culling for Models with Large Occluders,” Proc. Symp. Interactive 3D Graphics, pp. 83-90, 1997.
[10] X. Décoret, G. Debunne, and F. Sillion, “Erosion Based Visibility Preprocessing,” Proc. Eurographics Symp. Rendering, 2003.
[11] F. Durand, G. Drettakis, and C. Puech, “The 3D Visibility Complex: A New Approach to the Problems of Accurate Visibility,” Proc. Eurographics Rendering Workshop 1996, X. Pueyo and P. Schröder, eds., pp. 24-256, Aug. 1996.
[12] F. Durand, G. Drettakis, and C. Puech, “The Visibility Skeleton: A Powerful and Efficient Multi-Purpose Global Visibility Tool,” Proc. ACM SIGGRAPH, Ann. Conf. Series (SIGGRAPH '97), T. Whitted, ed., pp. 89-100, Aug. 1997.
[13] F. Durand, G. Drettakis, J. Thollot, and C. Puech, “Conservative Visibility Preprocessing Using Extended Projections,” Computer Graphics Proc., Ann. Conf. Series (SIGGRAPH '00), pp. 239-248, 2000.
[14] J. El-Sana, N. Sokolovsky, and C. Silva, “Integrating Occlusion Culling with View-Dependent Rendering,” Proc. IEEE Visualization, pp. 371-378, Aug. 2001.
[15] L. De Floriani, P. Magillo, and E. Puppo, “Building And Traversing a Surface at Variable Resolution,” Proc. IEEE Visualization '97, Oct. 1997.
[16] T. Funkhouser, C. Séquin, and S. Teller, “Management of Large Amounts of Data in Interactive Walkthrough,” Proc. Symp. Interactive 3D Graphics, pp. 11-20, 1992.
[17] Z. Gigus, J. Canny, and R. Seidel, “Efficiently Computing and Representing Aspect Graphs of Polyhedral Objects,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, no. 6, pp. 542-551, June 1991.
[18] C. Gotsman, O. Sudarsky, and J. Fayman, “Optimized Occlusion Culling Using Five-Dimensional Subdivision,” Computers and Graphics, vol. 23, no. 5, pp. 645-654, 1999.
[19] N. Govindaraju, A. Sud, S. Yoon, and D. Manocha, “Parallel Occlusion Culling for Interactive Walkthroughs Using Multiple GPUs,” Technical Report TR02-027, Univ. of North Carolina at Chapel Hill, 2002.
[20] N. Greene, M. Kass, and G. Miller, “Hierarchical Z-Buffer Visibility,” Proc. ACM SIGGRAPH, pp. 231-238, 1993.
[21] H. Hoppe, “View Dependent Refinement of Progressive Meshes,” Proc. ACM SIGGRAPH, pages 189-198, 1997.
[22] T. Hudson, D. Manocha, J. Cohen, M. Lin, K. Hoff, and H. Zhang, “Accelerated Occlusion Culling Using Shadow Frusta,” Proc. Symp. Computational Geometry, 1997.
[23] D.S. Johnson, L.A. McGeoch, “The Traveling Salesman Problem: A Case Study in Local Optimization,” Local Search in Combinatorial Optimization, E.H.L. Aarts and J.K. Lenstra, eds., pp. 215-310. London: John Wiley and Sons, 1997.
[24] D.S. Johnson, S. Krishnan, J. Chhugani, S. Kumar, and S. Venkatasubramanian, “Compressing Large Boolean Matrices Using Reordering Techniques,” Technical Report TD-5X77W6, AT&T Technical Memorandum, March 2004.
[25] V. Koltun, Y. Chrysanthou, and D. Cohen-Or, “Hardware-Accelerated From-Region Visibility Using a Dual Ray Space,” Proc. 12th Eurographics Rendering Workshop, pp. 205-216, 2001.
[26] S. Kumar, D. Manocha, W. Garrett, and M. Lin, “Hierarchical Back-Face Culling,” Computers and Graphics, vol. 23, no. 5, pp. 681-692, 1999.
[27] F. Law and T. Tan, “Preprocessing Occlusion for Real-Time Selective Refinement,” Proc. Symp. Interactive 3D Graphics, pp. 47-54, 1999.
[28] T. Leyvand, O. Sorkine, and D. Cohen-Or, “Ray Space Factorization for From-Region Visibility,” ACM Trans. Graphics, vol. 22, no. 3, pp. 595-604, 2003.
[29] M.S. Lobo, “Robust and Convex Optimization with Application in Finance,” PhD thesis, Dept. of Electrical Eng., Stanford Univ., 2000.
[30] D. Luebke, M. Reddy, J. Cohen, A. Varshney, B. Watson, and R. Huebner, Level of Detail for 3D Graphics. San Francisco: Morgan Kaufmann, 2002.
[31] P. Maciel and P. Shirley, “Visual Navigation of Large Environments Using Textured Clusters,” Proc. Symp. Interactive 3D Graphics, pp. 95-102, 1995.
[32] D. Meneveaux, K. Bouatouch, and E. Maisel, “Memory Management Schemes for Radiosity Computation in Complex Environments,” Computer Graphics Int'l, pp. 706-715, 1998.
[33] S. Nirenstein, E. Blake, and J. Gain, “Exact From Region Visibility Culling,” Proc. 15th Eurographics Rendering Workshop, pp. 305-316, 2002.
[34] M.V. Panne and A.J. Stewart, “Efficient Compression Techniques for Precomputed Visibility,” Proc. 12th Eurographics Rendering Workshop, pp. 305-316, 1999.
[35] J.R. Rossignac and P. Borrel, “Multi-Resolution 3D Approximations for Rendering Complex Scenes,” Geometric Modeling in Computer Graphics, B. Falcidieno and T. Kunii, eds., pp. 455-465. Genova: Springer-Verlag, 1993.
[36] G. Schaufler, J. Dorsey, X. Decoret, and F. Sillion, “Conservative Volumetric Visibility with Occluder Fusion,” Computer Graphics Proc., Ann. Conf. Series (SIGGRAPH '00), Kurt Akeley, ed., pp. 229-238, 2000.
[37] T.W. Sederberg and R.J. Meyers, “Loop Detection in Surface Patch Intersections,” Computer Aided Geometric Design, vol 5., pp. 161-171, 1988.
[38] S. Teller, “Computing the Antipenumbra of an Area Light Source,” Computer Graphics Proc., Ann. Conf. Series (SIGGRAPH '92), pp. 139-48, 1992.
[39] S. Teller, C. Fowler, T. Funkhouser, and P. Hanrahan, “Partitioning and Ordering Large Radiosity Computations,” Proc. Ann. Conf. Series (SIGGRAPH '94), pp. 443-450, 1994.
[40] S. Teller and C. Sequin, “Visibility Preprocessing for Interactive Walkthroughs,” ACM Computer Graphics (SIGGRAPH '97 Proc.), vol. 25, no. 4, pp. 61-69, 1991.
[41] G. Varadhan and D. Manocha, “Out-Of-Core Rendering of Massive Geometric Environments,” Proc. IEEE Visualization, 2002.
[42] Y. Wang, H. Bao, and Q. Peng, “Accelerated Walkthrough of Virtual Environments Based on Visibility Preprocessing and Simplification,” Computer Graphics Forum, vol. 17, no. 3, pp. C187-C194, 1998.
[43] P. Wonka and D. Schmalstieg, “Occluder Shadows for Fast Walkthroughs of Urban Environments,” Computer Graphics Forum (Eurographics '99), P. Brunet and R. Scopigno, eds., vol. 18, no. 3, pp. 51-60, 1999.
[44] P. Wonka, M. Wimmer, and D. Schmalstieg, “Visibility Preprocessing with Occluder Fusion for Urban Walkthroughs,” Proc. 11th Eurographics Rendering Workshop, June 2000.
[45] P. Wonka, M. Wimmer, and F. X. Sillion, “Instant Visibility,” Proc. EG Computer Graphics Forum 2001, A. Chalmers and T.-M. Rhyne, eds., vol. 20, no. 3, pp. 411-421, 2001.
[46] J. Xia and A. Varshney, “A Dynamic View-Dependent Simplification for Polygonal Models,” Proc. IEEE Visualization, pp. 327-334, 1996.
[47] H. Zhang, D. Manocha, T. Hudson, and K. Hoff, “Visibility Culling Using Hierarchical Occlusion Maps,” Proc. ACM SIGGRAPH, pp. 77-88, 1997.
|
 Additional Information
|
Index Terms- Interactive walkthrough, levels of detail, visibility computation, compression.
Citation:
Jatin Chhugani, Budirijanto Purnomo, Shankar Krishnan, Jonathan Cohen, Suresh Venkatasubramanian, David S. Johnson, Subodh Kumar,
"vLOD: High-Fidelity Walkthrough of Large Virtual Environments,"
IEEE Transactions on Visualization and Computer Graphics,
vol. 11,
no. 1,
pp. 35-47,
Jan/Feb,
2005
|
|
RSS Feed