Rapid k-d Tree Construction for Sparse Volume Data

Simple item page
dc.contributor.authorZellmann, Stefanen_US
dc.contributor.authorSchulze, Jürgen P.en_US
dc.contributor.authorLang, Ulrichen_US
dc.contributor.editorHank Childs and Fernando Cucchiettien_US
dc.date.accessioned2018-06-02T18:02:42Z
dc.date.available2018-06-02T18:02:42Z
dc.date.issued2018
dc.description.abstractWhile 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.en_US
dc.description.sectionheadersSession 3
dc.description.seriesinformationEurographics Symposium on Parallel Graphics and Visualization
dc.identifier.doi10.2312/pgv.20181097
dc.identifier.isbn978-3-03868-054-3
dc.identifier.issn1727-348X
dc.identifier.pages69-77
dc.identifier.urihttps://doi.org/10.2312/pgv.20181097
dc.identifier.urihttps://diglib.eg.org:443/handle/10.2312/pgv20181097
dc.publisherThe Eurographics Associationen_US
dc.subjectComputing methodologies
dc.subjectShared memory algorithms
dc.subjectRendering
dc.titleRapid k-d Tree Construction for Sparse Volume Dataen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
069-077.pdf
Size:
13.05 MB
Format:
Adobe Portable Document Format
Download
Collections
EGPGV18: Eurographics Symposium on Parallel Graphics and Visualization