“High resolution sparse voxel DAGs” by Kampe, Sintorn and Assarsson
Conference:
Type(s):
Title:
- High resolution sparse voxel DAGs
Session/Category Title: Advanced Rendering
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We show that a binary voxel grid can be represented orders of magnitude more efficiently than using a sparse voxel octree (SVO) by generalising the tree to a directed acyclic graph (DAG). While the SVO allows for efficient encoding of empty regions of space, the DAG additionally allows for efficient encoding of identical regions of space, as nodes are allowed to share pointers to identical subtrees. We present an efficient bottom-up algorithm that reduces an SVO to a minimal DAG, which can be applied even in cases where the complete SVO would not fit in memory. In all tested scenes, even the highly irregular ones, the number of nodes is reduced by one to three orders of magnitude. While the DAG requires more pointers per node, the memory cost for these is quickly amortized and the memory consumption of the DAG is considerably smaller, even when compared to an ideal SVO without pointers. Meanwhile, our sparse voxel DAG requires no decompression and can be traversed very efficiently. We demonstrate this by ray tracing hard and soft shadows, ambient occlusion, and primary rays in extremely high resolution DAGs at speeds that are on par with, or even faster than, state-of-the-art voxel and triangle GPU ray tracing.
References:
1. Aila, T., and Laine, S. 2004. Alias-free shadow maps. In Proceedings of Eurographics Symposium on Rendering 2004, 161–166. Google ScholarDigital Library
2. Aila, T., Laine, S., and Karras, T. 2012. Understanding the efficiency of ray traversal on GPUs — Kepler and Fermi addendum. NVIDIA Technical Report NVR-2012-02, NVIDIA Corporation, June.Google Scholar
3. Akenine-Möller, T., Haines, E., and Hoffman, N. 2008. Real-Time Rendering, 3rd ed. A K Peters.Google Scholar
4. Annen, T., Mertens, T., Bekaert, P., Seidel, H.-P., and Kautz, J. 2007. Convolution shadow maps. In Proceedings of Eurographics Symposium on Rendering 2007, 51–60. Google ScholarDigital Library
5. Annen, T., Dong, Z., Mertens, T., Bekaert, P., Seidel, H.-P., and Kautz, J. 2008. Real-time, all-frequency shadows in dynamic scenes. ACM Transactions on Graphics 27, 3 (Proceedings of ACM SIGGRAPH 2008) (Aug.), 34:1–34:8. Google ScholarDigital Library
6. Assarsson, U., and Akenine-Möller, T. 2003. A geometry-based soft shadow volume algorithm using graphics hardware. ACM Transactions on Graphics 22, 3 (Proceedings of ACM SIGGRAPH 2003) (July), 511–520. Google ScholarDigital Library
7. Billeter, M., Olsson, O., and Assarsson, U. 2009. Efficient stream compaction on wide simd many-core architectures. In Proceedings of the Conference on High Performance Graphics 2009, ACM, New York, NY, USA, HPG ’09, 159–166. Google ScholarDigital Library
8. Crassin, C., and Green, S. 2012. Octree-based sparse voxelization using the gpu hardware rasterizer. In OpenGL Insights. CRC Press, Patrick Cozzi and Christophe Riccio.Google Scholar
9. Crassin, C., Neyret, F., Lefebvre, S., and Eisemann, E. 2009. Gigavoxels: Ray-guided streaming for efficient and detailed voxel rendering. In ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D). Google ScholarDigital Library
10. Crassin, C., Neyret, F., Sainz, M., Green, S., and Eisemann, E. 2011. Interactive indirect illumination using voxel cone tracing. Computer Graphics Forum (Proceedings of Pacific Graphics 2011) 30, 7 (sep).Google Scholar
11. Crow, F. C. 1977. Shadow algorithms for computer graphics. Computer Graphics 11, 2 (Proceedings of ACM SIGGRAPH 77) (Aug.), 242–248. Google ScholarDigital Library
12. Dong, Z., and Yang, B. 2010. Variance soft shadow mapping. In ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games 2010: Posters, 18:1. Google ScholarDigital Library
13. Donnelly, W., and Lauritzen, A. 2006. Variance shadow maps. In Proceedings of ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games 2006, 161–165. Google ScholarDigital Library
14. Egan, K., Hecht, F., Durand, F., and Ramamoorthi, R. 2011. Frequency analysis and sheared filtering for shadow light fields of complex occluders. ACM Transactions on Graphics 30, 2 (Apr.), 9:1–9:13. Google ScholarDigital Library
15. Eisemann, E., Schwarz, M., Assarsson, U., and Wimmer, M. 2011. Real-Time Shadows. A. K. Peters. Google ScholarDigital Library
16. Elseberg, J., Borrmann, D., and Nüchter, A. 2012. One billion points in the cloud — an octree for efficient processing of 3d laser scans. ISPRS Journal of Photogrammetry and Remote Sensing.Google Scholar
17. Fernando, R. 2005. Percentage-closer soft shadows. In ACM SIGGRAPH 2005 Sketches and Applications, 35. Google ScholarDigital Library
18. Gobbetti, E., and Marton, F. 2005. Far Voxels — a multiresolution framework for interactive rendering of huge complex 3d models on commodity graphics platforms. ACM Transactions on Graphics 24, 3 (August), 878–885. Proc. SIGGRAPH 2005. Google ScholarDigital Library
19. Hachisuka, T., Jarosz, W., Weistroffer, R. P., Dale, K., Humphreys, G., Zwicker, M., and Jensen, H. W. 2008. Multidimensional adaptive sampling and reconstruction for ray tracing. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2008) 27, 3 (Aug.), 33:1–33:10. Google ScholarDigital Library
20. Heidmann, T. 1991. Real shadows real time. IRIS Universe 18 (Nov.), 28–31.Google Scholar
21. Intel, 2013. Threading Building Blocks. Computer Software.Google Scholar
22. Johnson, G. S., Lee, J., Burns, C. A., and Mark, W. R. 2005. The irregular z-buffer: Hardware acceleration for irregular data structures. ACM Transactions on Graphics 24, 4, 1462–1482. Google ScholarDigital Library
23. Johnson, G. S., Hunt, W. A., Hux, A., Mark, W. R., Burns, C. A., and Junkins, S. 2009. Soft irregular shadow mapping: Fast, high-quality, and robust soft shadows. In Proceedings of ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games 2009, 57–66. Google ScholarDigital Library
24. Katajainen, J., and Mäkinen, E. 1990. Tree compression and optimization with applications. International Journal of Foundations of Computer Science 1, 4, 425–447.Google ScholarCross Ref
25. Kontkanen, J., and Laine, S. 2005. Ambient occlusion fields. In Proceedings of ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games 2005, 41–48. Google ScholarDigital Library
26. Laine, S., and Karras, T. 2010. Efficient sparse voxel octrees. In Proceedings of ACM SIGGRAPH 2010 Symposium on Interactive 3D Graphics and Games, ACM Press, 55–63. Google ScholarDigital Library
27. Laine, S., and Karras, T. 2010. Two methods for fast ray-cast ambient occlusion. Computer Graphics Forum (Proc. Eurographics Symposium on Rendering 2010) 29, 4. Google ScholarDigital Library
28. Laine, S., Aila, T., Assarsson, U., Lehtinen, J., and Akenine-Möller, T. 2005. Soft shadow volumes for ray tracing. ACM Transactions on Graphics 24, 3 (Proceedings of ACM SIGGRAPH 2005) (July), 1156–1165. Google ScholarDigital Library
29. Lehtinen, J., Aila, T., Chen, J., Laine, S., and Durand, F. 2011. Temporal light field reconstruction for rendering distribution effects. ACM Transactions on Graphics 30, 4. Google ScholarDigital Library
30. Malmer, M., Malmer, F., Assarsson, U., and Holzschuch, N. 2007. Fast precomputed ambient occlusion for proximity shadows. Journal of Graphics Tools 12, 2, 59–71.Google ScholarCross Ref
31. McGuire, M. 2010. Ambient occlusion volumes. In Proceedings of High Performance Graphics 2010, 47–56. Google ScholarDigital Library
32. Mehta, S. U., Wang, B., and Ramamoorthi, R. 2012. Axis-aligned filtering for interactive sampled soft shadows. ACM Transactions on Graphics 31, 6 (Nov.), 163:1–163:10. Google ScholarDigital Library
33. Méndez-Feliu, À., and Sbert, M. 2009. From obscurances to ambient occlusion: A survey. The Visual Computer 25, 2 (Feb.), 181–196. Google ScholarDigital Library
34. Parker, E., and Udeshi, T. 2003. Exploiting self-similarity in geometry for voxel based solid modeling. In Proceedings of the eighth ACM symposium on Solid modeling and applications, ACM, New York, NY, USA, SM ’03, 157–166. Google ScholarDigital Library
35. Parsons, M. S. 1986. Generating lines using quadgraph patterns. Computer Graphics Forum 5, 1, 33–39. Google ScholarDigital Library
36. Reeves, W. T., Salesin, D. H., and Cook, R. L. 1987. Rendering antialiased shadows with depth maps. Computer Graphics 21, 4 (Proceedings of ACM SIGGRAPH 87) (July), 283–291. Google ScholarDigital Library
37. Schnabel, R., and Klein, R. 2006. Octree-based point-cloud compression. In Symposium on Point-Based Graphics 2006, Eurographics. Google ScholarDigital Library
38. Sintorn, E., Eisemann, E., and Assarsson, U. 2008. Sample based visibility for soft shadows using alias-free shadow maps. Computer Graphics Forum 27, 4 (Proceedings of Eurographics Symposium on Rendering 2008) (June), 1285–1292. Google ScholarDigital Library
39. Sintorn, E., Olsson, O., and Assarsson, U. 2011. An efficient alias-free shadow algorithm for opaque and transparent objects using per-triangle shadow volumes. ACM Transactions on Graphics 30, 6 (Dec.), 153:1–153:10. Google ScholarDigital Library
40. Webber, R. E., and Dillencourt, M. B. 1989. Compressing quadtrees via common subtree merging. Pattern Recognition Letters 9, 3, 193–200.Google ScholarCross Ref
41. Williams, L. 1978. Casting curved shadows on curved surfaces. Computer Graphics 12, 3 (Proceedings of ACM SIGGRAPH 78) (Aug.), 270–274. Google ScholarDigital Library
