Interactive Dynamic Volume Trees on the GPU.
Maik Keller, Nicolas Cuntz, Andreas Kolb · 2009
In many systems hierarchical data structures are used to accelerate the access to spatial data, whereas other applications use a hierarchical volumetric data structure to implicitly represent 3D objects. We introduce Dynamic Volume Trees (DVT), i.e. an adaptive hierarchical volume data structure which can be modified in real-time. The online capability is achieved by realizing both the hierarchical data structure and the manipulation of the structure solely on the Graphics Processing Unit (GPU). Even though we focus on the representation of highly-detailed volumetric scenes which may be gathered by sensors, e.g. in the fields of robotics and remote sensing applications, DVTs may easily be used to reference different data such as object references. The data is organized in a hierarchical kd-tree-like structure which provides a compact storage of multi-resolution volumes with no redundant memory consumption. Boolean operations are supported, i.e. sub-volumes can be efficiently merged (set union) and removed (set subtraction) with nearly arbitrary resolution. Additionally, a tree optimization is realized in order to improve the performance online. Furthermore, we present two approaches to render the data structure. The power and robustness of DVTs are demonstrated by a multi-resolution volume drawing example. 1