SCom DAG: compact representation of spatial data for real-time rendering

摘要

We developed a new data structure for the efficient representation of spatial data, called SCom DAG — Similarity Compressed Directed Acyclic Graph. It subdivides space with an octree and utilizes local data similarities and topology for compact encoding. Our method exploits the fact that many surface and volume areas are similar to each other up to a transformation. We store spatial transformations on the edges of the graph and data transformations on terminal links pointing to data blocks. Compression is achieved mainly by reducing the number of graph nodes and data blocks while maintaining the same number of paths in the graph. Spatial transformations are compact due to the use of hyper-octahedral groups that are relatively small even in 4D space. SCom DAG works with data of different dimensionality, such as 2D textures, 3D meshes and 4D time-varying volumetric data. Thus, it is well suited for volumetric data visualization and rendering large scenes. The proposed algorithm performs lossy compression, creating a compact representation of various data with controlled quality, which is especially valuable for low-end devices and convenient browser use. It provides a balance of compression and quality comparable to state-of-the-art technologies in various domains, such as compact texture and geometry representation, volumetric data, radiance fields, and precomputed 4D volume animations. At the same time, our data structure enables fast sampling and real-time ray tracing, and its hierarchical nature allows for rendering with a continuous level of detail.