Far voxels: a multiresolution framework for interactive rendering of huge complex 3D models on commodity graphics platforms

ABSTRACT

We present an efficient approach for end-to-end out-of-core construction and interactive inspection of very large arbitrary surface models. The method tightly integrates visibility culling and out-of-core data management with a level-of-detail framework. At preprocessing time, we generate a coarse volume hierarchy by binary space partitioning the input triangle soup. Leaf nodes partition the original data into chunks of a fixed maximum number of triangles, while inner nodes are discretized into a fixed number of cubical voxels. Each voxel contains a compact direction dependent approximation of the appearance of the associated volumetric subpart of the model when viewed from a distance. The approximation is constructed by a visibility aware algorithm that fits parametric shaders to samples obtained by casting rays against the full resolution dataset. At rendering time, the volumetric structure, maintained off-core, is refined and rendered in front-to-back order, exploiting vertex programs for GPU evaluation of view-dependent voxel representations, hardware occlusion queries for culling occluded subtrees, and asynchronous I/O for detecting and avoiding data access latencies. Since the granularity of the multiresolution structure is coarse, data management, traversal and occlusion culling cost is amortized over many graphics primitives. The efficiency and generality of the approach is demonstrated with the interactive rendering of extremely complex heterogeneous surface models on current commodity graphics platforms.

REFERENCES

• 1: Daniel Aliaga , Jon Cohen , Andrew Wilson , Eric Baker , Hansong Zhang , Carl Erikson , Kenny Hoff , Tom Hudson , Wolfgang Stuerzlinger , Rui Bastos , Mary Whitton , Fred Brooks , Dinesh Manocha, MMR: an interactive massive model rendering system using geometric and image-based acceleration, Proceedings of the 1999 symposium on Interactive 3D graphics, p.199-206, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300554]
• 2: Andujar, C., Saona, C., Navazo, I., and Brunet, P. 2000. Integrating occlusion culling and levels of detail through hardly-visible sets. Computer Graphics Forum 19, 3, 499--506.
• 3: Carlos Andújar , Pere Brunet , Dolors Ayala, Topology-reducing surface simplification using a discrete solid representation, ACM Transactions on Graphics (TOG), v.21 n.2, p.88-105, April 2002 [doi>10.1145/508357.508359]
• 4: Arenberg, J., 1988. Re: Ray/triangle intersection with barycentric coordinates. Ray Tracing News. 1.
• 5: Bittner, J., Wimmer, M., Piringer, H., and Purgathofer, W. 2004. Coherent hierarchical culling: Hardware occlusion queries made useful. Computer Graphics Forum 23, 3, 615--624.
• 6: Baoquan Chen , Minh Xuan Nguyen, POP: a hybrid point and polygon rendering system for large data, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 7: Chiang, Y.-J., El-Sana, J., Lindstrom, P., Pajarola, R., and Silva, C. T. 2003. Out-of-core algorithms for scientific visualization and computer graphics. IEEE Visualization 2003, Tutorial 4 Course Notes.
• 8: Cignoni, P., Ganovelli, F., Gobbetti, E., Marton, F., Ponchio, F., and Scopigno, R. 2003. BDAM -- batched dynamic adaptive meshes for high performance terrain visualization. Computer Graphics Forum 22, 3, 505--514.
• 9: Paolo Cignoni , Fabio Ganovelli , Enrico Gobbetti , Fabio Marton , Federico Ponchio , Roberto Scopigno, Adaptive tetrapuzzles: efficient out-of-core construction and visualization of gigantic multiresolution polygonal models, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 10: Jonathan D. Cohen , Daniel G. Aliaga , Weiqiang Zhang, Hybrid simplification: combining multi-resolution polygon and point rendering, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 11: Cohen-Or, D., Chrysanthou, Y. L., and Silva, C. T. 2003. A survey of visibility for walkthrough applications. IEEE Transactions on Visualization and Computer Graphics 9, 3, 412--431.
• 12: Wagner T. Correa , James T. Klosowski , Claudio T. Silva, Visibility-Based Prefetching for Interactive Out-Of-Core Rendering, Proceedings of the 2003 IEEE Symposium on Parallel and Large-Data Visualization and Graphics, p.2, October 20-21, 2003 [doi>10.1109/PVG.2003.10002]
• 13: Decaudin, P., and Neyret, F. 2004. Rendering forest scenes in real time. In Proc. Rendering Techniques, 93--102.
• 14: DeMarle, D. E., Gribble, C., and Parker, S. 2004. Memory-savvy distributed interactive ray tracing. In Proc. Eurographics Symposium on Parallel Graphics and Visualization, 93--100.
• 15: Jihad El-Sana , Neta Sokolovsky , Cláudio T. Silva, Integrating occlusion culling with view-dependent rendering, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 16: Carl Erikson , Dinesh Manocha , William V. Baxter, III, HLODs for faster display of large static and dynamic environments, Proceedings of the 2001 symposium on Interactive 3D graphics, p.111-120, March 2001 [doi>10.1145/364338.364376]
• 17: Gobbetti, E., and Marton, F. 2004. Layered point clouds -- a simple and efficient multiresolution structure for distributing and rendering gigantic point-sampled models. Computers & Graphics 28, 6 (December).
• 18: Naga K. Govindaraju , Avneesh Sud , Sung-Eui Yoon , Dinesh Manocha, Interactive visibility culling in complex environments using occlusion-switches, Proceedings of the 2003 symposium on Interactive 3D graphics, April 27-30, 2003, Monterey, California [doi>10.1145/641480.641501]
• 19: Guthe, M., Borodin, P., Balázs. A., and Klein, R. 2004. Real-time appearance preserving out-of-core rendering with shadows. In Proc. Eurographics Symposium on Rendering, June, 69--79 + 409.
• 20: Havran, V. 1999. Analysis of cache sensitive representations for binary space partitioning trees. Informatica 29, 3, 203--210.
• 21: James T. Klosowski , Cláudio T. Silva, Efficient Conservative Visibility Culling Using the Prioritized-Layered Projection Algorithm, IEEE Transactions on Visualization and Computer Graphics, v.7 n.4, p.365-379, October 2001 [doi>10.1109/2945.965350]
• 22: Joshua Levenberg, Fast view-dependent level-of-detail rendering using cached geometry, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 23: Peter Lindstrom, Out-of-core construction and visualization of multiresolution surfaces, Proceedings of the 2003 symposium on Interactive 3D graphics, April 27-30, 2003, Monterey, California [doi>10.1145/641480.641500]
• 24: Yarden Livnat , Xavier Tricoche, Interactive Point-Based Isosurface Extraction, Proceedings of the conference on Visualization '04, p.457-464, October 10-15, 2004 [doi>10.1109/VIS.2004.52]
• 25: David J. MacDonald , Kellogg S. Booth, Heuristics for ray tracing using space subdivision, The Visual Computer: International Journal of Computer Graphics, v.6 n.3, p.153-166, 1990 [doi>10.1007/BF01911006]
• 26: Matt Pharr , Craig Kolb , Reid Gershbein , Pat Hanrahan, Rendering complex scenes with memory-coherent ray tracing, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.101-108, August 1997 [doi>10.1145/258734.258791]
• 27: Szymon Rusinkiewicz , Marc Levoy, QSplat: a multiresolution point rendering system for large meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.343-352, July 2000 [doi>10.1145/344779.344940]
• 28: Szymon Rusinkiewicz , Marc Levoy, Streaming QSplat: a viewer for networked visualization of large, dense models, Proceedings of the 2001 symposium on Interactive 3D graphics, p.63-68, March 2001 [doi>10.1145/364338.364350]
• 29: Marc Stamminger , George Drettakis, Interactive Sampling and Rendering for Complex and Procedural Geometry, Proceedings of the 12th Eurographics Workshop on Rendering Techniques, p.151-162, June 25-27, 2001
• 30: Wald, I., Dietrich, A., and Slusallek, P. 2004. An interactive out-of-core rendering framework for visualizing massively complex models. In Proc. Eurographics Symposium on Rendering, 81--92.
• 31: Michael Wand , Matthias Fischer , Ingmar Peter , Friedhelm Meyer auf der Heide , Wolfgang Straßer, The randomized z-buffer algorithm: interactive rendering of highly complex scenes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.361-370, August 2001 [doi>10.1145/383259.383299]
• 32: Michael Wimmer , Peter Wonka , François X. Sillion, Point-Based Impostors for Real-Time Visualization, Proceedings of the 12th Eurographics Workshop on Rendering Techniques, p.163-176, June 25-27, 2001
• 33: Daniel N. Wood , Daniel I. Azuma , Ken Aldinger , Brian Curless , Tom Duchamp , David H. Salesin , Werner Stuetzle, Surface light fields for 3D photography, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.287-296, July 2000 [doi>10.1145/344779.344925]
• 34: Sung-Eui Yoon , Brian Salomon , Russell Gayle , Dinesh Manocha, Quick-VDR: Interactive View-Dependent Rendering of Massive Models, Proceedings of the conference on Visualization '04, p.131-138, October 10-15, 2004 [doi>10.1109/VIS.2004.86]
• 35: Eugene Zhang , Greg Turk, Visibility-guided simplification, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 36: Hansong Zhang , Dinesh Manocha , Tom Hudson , Kenneth E. Hoff, III, Visibility culling using hierarchical occlusion maps, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.77-88, August 1997 [doi>10.1145/258734.258781]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism

Keywords:
level of detail, out-of-core algorithms