“Far voxels: a multiresolution framework for interactive rendering of huge complex 3D models on commodity graphics platforms” by Gobbetti and Marton

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.

1. Aliaga, D., Cohen, J., Wilson, A., Baker, E., Zhang, H., Erikson, C., Hoff, K., Hudson, T., Stürzlinger, W., Bastos, R., Whitton, M., Brooks, F., and Manocha, D. 1999. MMR: An interactive massive model rendering system using geometric and image-based acceleration. In 1999 Symposium on Interactive 3D Graphics, 199–206. Google ScholarDigital Library
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.Google ScholarCross Ref
3. Andujar, C., Brunet, P., and Ayala, D. 2002. Topology-reducing surface simplification using a discrete solid representation. ACM Trans. Graph, 21, 2, 88–105. Google ScholarDigital Library
4. Arenberg, J., 1988. Re: Ray/triangle intersection with barycentric coordinates. Ray Tracing News. 1.Google Scholar
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.Google ScholarCross Ref
6. Chen, B., and Nguyen, M. X. 2001. Pop: a hybrid point and polygon system for large data. In Proc. IEEE Visualization, 45–52. Google ScholarDigital Library
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.Google Scholar
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.Google ScholarCross Ref
9. Cignoni, R., Ganovelli, F., Gobbetti, E., Marton, F., Ponchio, F., and Scopigno, R. 2004. Adaptive TetraPuzzles — efficient out-of-core construction and visualization of gigantic polygonal models. ACM Transactions on Graphics 23, 3 (August), 796–803. Proc. SIGGRAPH 2004. Google ScholarDigital Library
10. Cohen, J. D., Aliaga, D. G., and Zhang, W. 2001. Hybrid simplification: combining multi-resolution polygon and point rendering. In VIS ’01: Proceedings of the conference on Visualization ’01, IEEE Computer Society, 37–44. Google ScholarDigital Library
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. Google ScholarDigital Library
12. Corréa, W. T., Klosowski, J. T., and Silva, C. T. 2003. Visibility-based prefetching for interactive out-of-core rendering. In IEEE Symposium on Parallel and Large-Data Visualization and Graphics, 1–8. Google ScholarDigital Library
13. Decaudin, P., and Neyret, F. 2004. Rendering forest scenes in real time. In Proc. Rendering Techniques, 93–102. Google ScholarDigital Library
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. Google ScholarDigital Library
15. El-Sana, J., Sokolovsky, N., and Silva, C. T. 2001. Integrating occlusion culling with view-dependent rendering. In VIS ’01: Proceedings of the conference on Visualization ’01, IEEE Computer Society, 371–378. Google ScholarDigital Library
16. Erikson, C., Manocha, D., and Baxter, W. 2001. HLODs for faster display of large static and dynamic environments. In Proc. ACM Symposium on Interactive 3D Graphics, 111–120. Google ScholarDigital Library
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). Google ScholarDigital Library
18. Govindaraju, N. K., Sud, A., Yoon, S.-E., and Manocha, D. 2003. Interactive visibility culling in complex environments using occlusion-switches. In SI3D ’03: Proceedings of the 2003 symposium on Interactive 3D graphics, 103–112. Google ScholarDigital Library
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. Google ScholarDigital Library
20. Havran, V. 1999. Analysis of cache sensitive representations for binary space partitioning trees. Informatica 29, 3, 203–210.Google Scholar
21. Klosowski, J. T., and Silva, C. T. 2001. Efficient conservative visibility culling using the prioritized-layered projection algorithm. IEEE Transactions on Visualization and Computer Graphics 7, 4, 365–379. Google ScholarDigital Library
22. Levenberg, J. 2002. Fast view-dependent level-of-detail rendering using cached geometry. In Proceedings IEEE Visualization ’02, IEEE, 259–266. Google ScholarDigital Library
23. Lindstrom, P. 2003. Out-of-core construction and visualization of multiresolution surfaces. In ACM 2003 Symposium on Interactive 3D Graphics, 93–102,239. Google ScholarDigital Library
24. Livnat, Y., and Tricoche, X. 2004. Interactive point based isosurface extraction. In Proc. IEEE Visualization, 457–464. Google ScholarDigital Library
25. MacDonald, J. D., and Booth, K. S. 1990. Heuristics for ray tracing using space subdivision. The Visual Computer 6, 6, 153–165. Google ScholarDigital Library
26. Pharr, M., Kolb, C., Gershbein, R., and Hanrahan, P. 1997. Rendering complex scenes with memory coherent ray tracing. In Proc. SIGGRAPH, 101–108. Google ScholarDigital Library
27. Rusinkiewicz, S., and Levoy, M. 2000. QSplat: A multiresolution point rendering system for large meshes. In Comp. Graph. Proc., Annual Conf. Series (SIGGRAPH 00). ACM Press, 343–352. Google ScholarDigital Library
28. Rusinkiewicz, S., and Levoy, M. 2001. Streaming QSplat: A viewer for networked visualization of large, dense models. In Symposium for Interactive 3D Graphics Proceedings, 63–68. Google ScholarDigital Library
29. Stamminger, M., and Drettakis, G. 2001. Interactive sampling and rendering for complex and procedural geometry. In Proceedings of the 12th Eurographics Workshop on Rendering Techniques, Springer-Verlag, 151–162. Google ScholarDigital Library
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. Google ScholarDigital Library
31. Wand, M., Fischer, M., Peter, I., auf der Heide, F. M., and Strasser, W. 2001. The randomized z-buffer algorithm: Interactive rendering of highly complex scenes. In SIGGRAPH 2001 Proceedings, 361–370. Google ScholarDigital Library
32. Wimmer, M., Wonka, P., and Sillion, F. 2001. Point-based impostors for real-time visualization. In Proc. Rendering Techniques, 163–176. Google ScholarDigital Library
33. Wood, D. N., Azuma, D. I., Aldinger, K., Curless, B., Duchamp, T., Salesin, D. H., and Stuetzlinger, W. 2000. Surface light fields for 3d photography. In Proc. SIGGRAPH, 287–296. Google ScholarDigital Library
34. Yoon, S.-E., Salomon, B., Gayle, R., and Manocha, D. 2004. Quick-vdr: Interactive view-dependent rendering of massive models. In VIS ’04: Proceedings of the IEEE Visualization 2004 (VIS’04), IEEE Computer Society, 131–138. Google ScholarDigital Library
35. Zhang, E., and Turk, G. 2002. Visibility-guided simplification. In Proc. IEEE Visualization, 267–274. Google ScholarDigital Library
36. Zhang, H., Manocha, D., Hudson, T., and Hoff III, K. 1997. Visibility culling using hierarchical occlusion maps. In Proc. SIGGRAPH, 77–88. Google ScholarDigital Library