Rapid k-d Tree Construction for Sparse Volume Data (Unknown language)

How to get this document?

Download
Commercial Copyright fee: €14.50 Basic fee: €4.00 Total price: €18.50
Academic Copyright fee: €4.50 Basic fee: €2.00 Total price: €6.50

While k-d trees are known to be effective for spatial indexing of sparse 3-D volume data, full reconstruction, e.g. due to changes to the alpha transfer function during rendering, is usually a costly operation with this hierarchical data structure. We pick a serial state of the art implementation that is based on summed-volume tables and propose a parallel version of the construction algorithm for multi-core CPUs. Our parallel k-d tree construction algorithm can be used to rapidly perform full hierarchy rebuilds for moderately sized to large volume data sets. We reformulate the original, highly serial construction algorithm by replacing the summed-volume table (SVT) that is used to perform fast occupancy queries with a list of partial summed-volume tables. This gives rise to parallelism at several stages of the algorithm. We show how to achieve high scalability with a carefully crafted parallelization scheme. As a side effect, our construction algorithm also relaxes the tremendous memory overhead imposed by full SVTs. For our scalability study, we have integrated the parallel k-d tree implementation into a ray casting volume rendering pipeline. We present comparisons for various sparse 3-D volumetric data sets where k-d trees are first built interactively and then later used to skip over empty space.

Table of contents conference proceedings

The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.

1
Direct Raytracing of Particle-based Fluid Surfaces Using Anisotropic Kernels
Biedert, Tim / Sohns, Jan-Tobias / Schröder, Simon / Amstutz, Jefferson / Wald, Ingo / Garth, Christoph | 2018
13
VisIt-OSPRay: Toward an Exascale Volume Visualization System
Wu, Qi / Usher, Will / Petruzza, Steve / Kumar, Sidharth / Wang, Feng / Wald, Ingo / Pascucci, Valerio / Hansen, Charles D. | 2018
25
Robust Iterative Find-Next-Hit Ray Traversal
Wald, Ingo / Amstutz, Jefferson / Benthin, Carsten | 2018
33
Hardware-Accelerated Multi-Tile Streaming for Realtime Remote Visualization
Biedert, Tim / Messmer, Peter / Fogal, Thomas / Garth, Christoph | 2018
45
Performance-Portable Particle Advection with VTK-m
Pugmire, David / Yenpure, Abhishek / Kim, Mark / Kress, James / Maynard, Robert / Childs, Hank / Hentschel, Bernd | 2018
57
Dense Texture Flow Visualization using Data-Parallel Primitives
Kim, Mark / Klasky, Scott / Pugmire, David | 2018
63
Revisiting the Evaluation of In Situ Lagrangian Analysis
Sane, Sudhanshu / Bujack, Roxana / Childs, Hank | 2018
69
Rapid k-d Tree Construction for Sparse Volume Data
Zellmann, Stefan / Schulze, Jürgen P. / Lang, Ulrich | 2018
79
Interactive Visual Analysis of Multi-dimensional Metamodels
Gebhardt, Sascha / Pick, Sebastian / Hentschel, Bernd / Kuhlen, Torsten Wolfgang | 2018
91
La VALSE: Scalable Log Visualization for Fault Characterization in Supercomputers
Guo, Hanqi / Di, Sheng / Gupta, Rinku / Peterka, Tom / Cappello, Franck | 2018