loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Quick-VDR: Out-of-Core View-Dependent Rendering of Gigantic Models
July/August 2005 (vol. 11 no. 4)
pp. 369-382
We present a novel approach for interactive view-dependent rendering of massive models. Our algorithm combines view-dependent simplification, occlusion culling, and out-of-core rendering. We represent the model as a clustered hierarchy of progressive meshes (CHPM). We use the cluster hierarchy for coarse-grained selective refinement and progressive meshes for fine-grained local refinement. We present an out-of-core algorithm for computation of a CHPM that includes cluster decomposition, hierarchy generation, and simplification. We introduce novel cluster dependencies in the preprocess to generate crack-free, drastic simplifications at runtime. The clusters are used for LOD selection, occlusion culling, and out-of-core rendering. We add a frame of latency to the rendering pipeline to fetch newly visible clusters from the disk and avoid stalls. The CHPM reduces the refinement cost of view-dependent rendering by more than an order of magnitude as compared to a vertex hierarchy. We have implemented our algorithm on a desktop PC. We can render massive CAD, isosurface, and scanned models, consisting of tens or a few hundred million triangles at 15--35 frames per second with little loss in image quality.

[1] 369 H. Hoppe, “View Dependent Refinement of Progressive Meshes,” ACM SIGGRAPH Conf. Proc., pp. 189-198, 1997.[2] D. Luebke and C. Erikson, “View-Dependent Simplification of Arbitrary Polygon Environments,” Proc. ACM SIGGRAPH, 1997.[3] J. Xia, J. El-Sana, and A. Varshney, “Adaptive Real-Time Level-of-Detail-Based Rendering for Polygonal Models,” IEEE Trans. Visualization and Computer Graphics, vol. 3, no. 2, pp. 171-183, Apr.-June 1997.[4] S. Yoon, B. Salomon, R. Gayle, and D. Manocha, “Quick-VDR: Interactive View-Dependent Rendering of Massive Models,” Proc. IEEE Visualization, 2004.[5] H. Hoppe, “Progressive Meshes,” Proc. ACM SIGGRAPH, pp. 99-108, 1996.[6] E.P.L. De Floriani and P. Magillo, “Building and Traversing a Surface at Variable Resolution,” Proc. IEEE Visualization, 1997.[7] N. Williams, D. Luebke, J.D. Cohen, M. Kelley, and B. Schubert, “Perceptually Guided Simplification of Lit, Textured Meshes,” Proc. ACM Symp. Interactive 3D Graphics, 2003.[8] M. Duchaineau, M. Wolinsky, D.E. Sigeti, M.C. Miller, C. Aldrich, and M.B. Mineev-Weinstein, “ROAMing Terrain: Real-Time Optimally Adapting Meshes,” Proc. IEEE Visualization, pp. 81-88, 1997.[9] J. El-Sana and A. Varshney, “Generalized View-Dependent Simplification,” Computer Graphics Forum, pp. C83-C94, 1999.[10] J. El-Sana, E. Azanli, and A. Varshney, “Skip Strips: Maintaining Triangle Strips for View-Dependent Rendering,” Proc. IEEE Visualization, 1999.[11] R. Pajarola, “Fastmesh: Efficient View-Dependent Mesh,” Proc. Pacific Graphics, pp. 22-30, 2001.[12] A. Bogomjakov and C. Gotsman, “Universal Rendering Sequences for Transparent Vertex Caching of Progressive Meshes,” Computer Graphics Forum, 2002.[13] J. El-Sana and E. Bachmat, “Optimized View-Dependent Rendering for Large Polygonal Data Set,” Proc. IEEE Visualization, pp. 77-84, 2002.[14] P. Lindstrom and C. Silva, “A Memory Insensitive Technique for Large Model Simplification,” Proc. IEEE Visualization, pp. 121-126, 2001.[15] E. Shaffer and M. Garland, “Effient Adaptive Simplification of Massive Meshes,” Proc. IEEE Visualization, 2001.[16] P. Cignoni, C. Montani, C. Rocchini, and R. Scopigno, “External Memory Management and Simplification of Huge Meshes,” IEEE Trans. Visualization and Computer Graphics, 2003.[17] H. Hoppe, “Smooth View-Dependent Level-of-Detail Control and Its Application to Terrain Rendering,” IEEE Visualization Conf. Proc., pp. 35-42, 1998.[18] C. Prince, “Progressive Meshes for Large Models of Arbitrary Topology,” master's thesis, Univ. of Washington, 2000.[19] J. El-Sana and Y.-J. Chiang, “External Memory View-Dependent Simplification,” Computer Graphics Forum, vol. 19, no. 3, pp. 139-150, 2000.[20] C. DeCoro and R. Pajarola, “Xfastmesh: View-Dependent Meshing from External Memory,” Proc. IEEE Visualization, 2002.[21] P. Lindstrom, “Out-of-Core Construction and Visualization of Multiresolution Surfaces,” Proc. ACM Symp. Interactive 3D Graphics, 2003.[22] P. Lindstrom and V. Pascucci, “Terrain Simplification Simplified: A General Framework for View-Dependent Out-of-Core Visualization,” IEEE Trans. Visualization and Computer Graphics, vol. 8, pp. 239-254, 2002.[23] P. Cignoni, F. Ganovelli, E. Gobbetti, F. Marton, F. Ponchio, and R. Scopigno, “Adaptive TetraPuzzles— Efficient Out-of-Core Construction and Visualization of Gigantic Polygonal Models,” Computer Graphics Forum, vol. 23, no. 3, Aug. 2004.[24] D. Cohen-Or, Y. Chrysanthou, C. Silva, and F. Durand, “A Survey of Visibility for Walkthrough Applications,” IEEE Trans. Visualization and Computer Graphics, vol. 9, 2003.[25] S. Coorg and S. Teller, “Real-Time Occlusion Culling for Models with Large Occluders,” Proc. ACM Symp. Interactive 3D Graphics, 1997.[26] T. Hudson, D. Manocha, J. Cohen, M. Lin, K. Hoff, and H. Zhang, “Accelerated Occlusion Culling Using Shadow Frusta,” Proc. ACM Symp. Computational Geometry, pp. 1-10, 1997.[27] N. Greene, M. Kass, and G. Miller, “Hierarchical z-Buffer Visibility,” Proc. ACM SIGGRAPH, pp. 231-238, 1993.[28] H. Zhang, D. Manocha, T. Hudson, and K. Hoff, “Visibility Culling Using Hierarchical Occlusion Maps,” Proc. ACM SIGGRAPH, 1997.[29] J. Klosowski and C. Silva, “Efficient Conservative Visiblity Culling Using the Prioritized-Layered Projection Algorithm,” IEEE Trans. Visualization and Computer Graphics, vol. 7, no. 4, pp. 365-379, Oct.-Dec. 2001.[30] P. Wonka, M. Wimmer, and F. Sillion, “Instant Visibility,” Proc. Eurographics, 2001.[31] N. Govindaraju, A. Sud, S. Yoon, and D. Manocha, “Interactive Visibility Culling in Complex Environments with Occlusion-Switches,” Proc. ACM Symp. Interactive 3D Graphics, pp. 103-112, 2003.[32] T. Funkhouser, D. Khorramabadi, C. Sequin, and S. Teller, “The UCB System for Interactive Visualization of Large Architectural Models,” Presence, vol. 5, no. 1, pp. 13-44, 1996.[33] D. Aliaga, J. Cohen, A. Wilson, H. Zhang, C. Erikson, K. Hoff, T. Hudson, W. Stuerzlinger, E. Baker, R. Bastos, M. Whitton, F. Brooks, and D. Manocha, “MMR: An Integrated Massive Model Rendering System Using Geometric and Image-Based Acceleration,” Proc. ACM Symp. Interactive 3D Graphics, pp. 199-206, 1999.[34] B. Baxter, A. Sud, N. Govindaraju, and D. Manocha, “GigaWalk: Interactive Walkthrough of Complex 3D Environments,” Proc. Eurographics Workshop Rendering, pp. 203-214, 2002.[35] N. Govindaraju, B. Lloyd, S. Yoon, A. Sud, and D. Manocha, “Interactive Shadow Generation in Complex Environments,” Proc. ACM SIGGRAPH/ACM Trans. Graphics, vol. 22, no. 3, pp. 501-510, 2003.[36] C. Erikson, D. Manocha, and B. Baxter, “Hlods for Fast Display of Large Static and Dynamic Environments,” Proc. ACM Symp. Interactive 3D Graphics, 2001.[37] I. Wald, A. Dietrich, and P. Slusallek, “An Interactive Out-of-Core Rendering Framework for Visualizing Massively Complex Models,” Proc. Eurographics Symp. Rendering, 2004.[38] S. Yoon, B. Salomon, and D. Manocha, “Interactive View-Dependent Rendering with Conservative Occlusion Culling in Complex Environments,” Proc. IEEE Visualization, 2003.[39] J. El-Sana, N. Sokolovsky, and C. Silva, “Integrating Occlusion Culling with View-Dependent Rendering,” Proc. IEEE Visualization, 2001.[40] W.T. Correa, J.T. Klosowski, and C.T. Silva, “Visibility-Based Prefetching for Interactive Out-of-Core Rendering,” Proc. PVG 2003 (Sixth IEEE Symp. Parallel and Large-Data Visualization and Graphics), pp. 1-8, 2003.[41] W.T. Correa, “New Techniques for Out-of-Core Visualization of Large Datasets,” PhD dissertation, Princeton Univ., 2004.[42] S. Rusinkiewicz and M. Levoy, “Qsplat: A Multiresolution Point Rendering System for Large Meshes,” Proc. ACM SIGGRAPH, 2000.[43] C. Dachsbacher, C. Vogelgsang, and M. Stamminger, “Sequential Point Trees,” Proc. ACM SIGGRAPH, 2003.[44] M. Isenburg and S. Gumhold, “Out-of-Core Compression for Gigantic Polygon Meshes,” ACM Trans. Graphics (Proc. ACM SIGGRAPH), vol. 22, 2003.[45] S. Arya and D.M. Mount, “Approximate Nearest Neighbor Queries in Fixed Dimensions,” Proc. Fourth ACM-SIAM Symp. Discrete Algorithms, pp. 271-280, 1993.[46] B. Hendrickson and R. Leland, “A Multilevel Algorithm for Partitioning Graphs,” Proc. Super Computing, 1995.[47] G. Karypis and V. Kumar, “Multilevel k-Way Partitioning Scheme for Irregular Graphs,” J. Parallel and Distributed Computing, 1998.[48] M. Garland and P. Heckbert, “Surface Simplification Using Quadric Error Bounds,” Proc. ACM SIGGRAPH, pp. 209-216, 1997.[49] M. Cox and D. Ellsworth, “Application-Controlled Demand Paging for Out-of-Core Visualization,” Proc. IEEE Visualization, pp. 235-244, 1997.[50] W. Correa, J. Klosowski, and C. Silva, “iwalk: Interactive Out-of-Core Rendering of Large Models,” Technical Report TR-653-02, Princeton Univ., 2002.[51] S. Yoon, B. Salomon, M.C. Lin, and D. Manocha, “Fast Collision Detection between Massive Models Using Dynamic Simplification,” Proc. Eurographics Symp. Geometry Processing, 2004.

Index Terms:
Index Terms- Interactive display, view-dependent rendering, occlusion culling, external-memory algorithm, out-of-core algorithms, levels-of-detail.
Citation:
Sung-Eui Yoon, Brian Salomon, Russell Gayle, Dinesh Manocha, "Quick-VDR: Out-of-Core View-Dependent Rendering of Gigantic Models," IEEE Transactions on Visualization and Computer Graphics, vol. 11, no. 4, pp. 369-382, July/Aug. 2005, doi:10.1109/TVCG.2005.64
Usage of this product signifies your acceptance of the Terms of Use.