Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Given a data layout of a large walkthrough scene, we present a novel and simple spatial hierarchy on the disk-pages of the layout that has notable advantages over a conventional spatial hierarchy on the scene geometry. Assume that each disk-page consists of a set of triangles whose bounding boxes are computed. A spatial hierarchy of the walkthrough space is constructed, not with the given scene, but with the bounding boxes of disk-pages. The leaf nodes of the spatial-hierarchy refer directly to the page numbers of the pages of the bounding box it contains. We call this hierarchy on the pages as the disk-page hierarchy. We also propose a self-contained disk-page format that would suit this data structure well. Further, we present a new cache-oblivious graph-based data layout algorithm called the 2-factor layout that would preserve the proximity and orientation properties of the primitives in the layout. Walkthrough experiments have been conducted on a city scene consisting of over 110M triangles. Our system renders this scene on a laptop within a one pixel projection error at over 20 fps with simple texture substitution based simplification of distant objects, and with no explicit data/cache management.

REFERENCES

• 1: Daniel G. Aliaga , Anselmo A. Lastra, Architectural walkthroughs using portal textures, Proceedings of the 8th conference on Visualization '97, p.355-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 2: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 3: Bittner, J., Wimmer, M., Piringer, H., and Purgathofer, W. 2004. Coherent hierarchical culling: Hardware occlusion queries made useful. Computer Graphics Forum (Eurographics) 23, 3, 615--624.
• 4: 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
• 5: 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]
• 6: Michael Deering, Geometry compression, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.13-20, September 1995 [doi>10.1145/218380.218391]
• 7: Diaz-Gutierrez, P., and Gopi, M. 2005. Quadrilateral and tetrahedral mesh stripification using 2-factor partitioning of the dual graph. The Visual Computer 21, 8--10, 689--697.
• 8: P. Diaz-Gutierrez , A. Bhushan , M. Gopi , R. Pajarola, Constrained strip generation and management for efficient interactive 3D rendering, Proceedings of the Computer Graphics International 2005, p.115-121, June 02-04, 2005
• 9: Diaz-Gutierrez, P., Gopi, M., and Pajarola, R. 2005. Hierarchiless simplification, stripification, and compression of triangulated two manifolds. In Proc. of EUROGRAPHICS.
• 10: Pablo Diaz-Gutierrez , Anusheel Bhushan , M. Gopi , Renato Pajarola, Single-strips for fast interactive rendering, The Visual Computer: International Journal of Computer Graphics, v.22 n.6, p.372-386, June 2006 [doi>10.1007/s00371-006-0018-2]
• 11: Mark Duchaineau , Murray Wolinsky , David E. Sigeti , Mark C. Miller , Charles Aldrich , Mark B. Mineev-Weinstein, ROAMing terrain: real-time optimally adapting meshes, Proceedings of the 8th conference on Visualization '97, p.81-88, October 18-24, 1997, Phoenix, Arizona, United States
• 12: Enrico Gobbetti , Fabio Marton, Far voxels: a multiresolution framework for interactive rendering of huge complex 3D models on commodity graphics platforms, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 13: Gopi, M., and Eppstein, D. 2004. Single strip triangulation of manifolds with arbitrary topology. Computer Graphics Forum (EUROGRAPHICS) 23, 3, 371--379.
• 14: Hugues Hoppe, Optimization of mesh locality for transparent vertex caching, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.269-276, July 1999 [doi>10.1145/311535.311565]
• 15: Isenburg, M., and Lindstrom, P. 2005. Streaming meshes. IEEE Visualization, 231--238.
• 16: Martin Isenburg , Peter Lindstrom , Stefan Gumhold , Jack Snoeyink, Large Mesh Simplification using Processing Sequences, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.61, October 22-24, 2003 [doi>10.1109/VISUAL.2003.1250408]
• 17: Lin, M., and Manocha, D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry.
• 18: Peter Lindstrom , Valerio Pascucci, Visualization of large terrains made easy, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 19: Frank Losasso , Hugues Hoppe, Geometry clipmaps: terrain rendering using nested regular grids, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 20: David Luebke , Carl Erikson, View-dependent simplification of arbitrary polygonal environments, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.199-208, August 1997 [doi>10.1145/258734.258847]
• 21: David Luebke , Benjamin Watson , Jonathan D. Cohen , Martin Reddy , Amitabh Varshney, Level of Detail for 3D Graphics, Elsevier Science Inc., New York, NY, 2002
• 22: Miguel A. Otaduy , Ming C. Lin, CLODs: dual hierarchies for multiresolution collision detection, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 23: Valerio Pascucci , Randall J. Frank, Global static indexing for real-time exploration of very large regular grids, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.2-2, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582036]
• 24: Sagan, H. 1994. Space-Filling Curves. Springer-Verlag.
• 25: Hanan Samet, Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 26: Pedro V. Sander , Diego Nehab , Joshua Barczak, Fast triangle reordering for vertex locality and reduced overdraw, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 27: Teschner, M., Kimmerle, S., Heidelberger, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M.-P., Faure, F., Magnenat-Thalmann, N., Strasser, W., and Volino, P. 2005. Collision detection for deformable objects. Computer Graphics Forum 19, 1, 61--81.
• 28: Gokul Varadhan , Dinesh Manocha, Out-of-core rendering of massive geometric environments, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 29: Luiz Velho , Jonas de Miranda Gomes, Digital halftoning with space filling curves, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.81-90, July 1991
• 30: Wald, I., and Havran, V. 2006. On building fast kd-trees for ray tracing, and on doing that in O(N log N). In Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing, 61--69.
• 31: Walter, B., Bala, K., Kulkarni, M., and Pingali, K. 2008. Fast agglomerative clustering for rendering. IEEE Symp. on Interactive Ray Tracing, 81--86.
• 32: Sung-Eui Yoon , Peter Lindstrom, Mesh Layouts for Block-Based Caches, IEEE Transactions on Visualization and Computer Graphics, v.12 n.5, p.1213-1220, September 2006 [doi>10.1109/TVCG.2006.162]
• 33: Sung-Eui Yoon , Peter Lindstrom , Valerio Pascucci , Dinesh Manocha, Cache-oblivious mesh layouts, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 34: Yoon, S., Gobbetti, E., Kasik, D., and Manocha, D. 2008. Real-Time Massive Model Rendering. Morgan & Claypool Publisher.

INDEX TERMS

Keywords:
data layouts, out-of-core algorithms, spatial data structures, walkthrough systems