CSVO: Clustered Sparse Voxel Octrees—A Hierarchical Data Structure for Geometry Representation of Voxelized 3D Scenes
When representing the geometry of voxelized three-dimensional scenes (especially if they have been voxelized to high resolutions) in a naive—uncompressed—form, one may end up using vast amounts of data. These can easily attack the available memory capacity of the graphics card, the operating memory...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-10-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/14/10/2114 |
| _version_ | 1797469849108086784 |
|---|---|
| author | Branislav Madoš Eva Chovancová Martin Chovanec Norbert Ádám |
| author_facet | Branislav Madoš Eva Chovancová Martin Chovanec Norbert Ádám |
| author_sort | Branislav Madoš |
| collection | DOAJ |
| description | When representing the geometry of voxelized three-dimensional scenes (especially if they have been voxelized to high resolutions) in a naive—uncompressed—form, one may end up using vast amounts of data. These can easily attack the available memory capacity of the graphics card, the operating memory or even secondary storage of computer. A viable solution to this problem is to use domain-specific hierarchical data structures, based on octant trees or directed acyclic graphs, which, among other advantages, provide a compact binary representation that can thus be considered to be their compressed encoding. These data structures include—inter alia—sparse voxel octrees, sparse voxel directed acyclic graphs and symmetry-aware sparse voxel directed acyclic graphs. The paper deals with the proposal of a new domain-specific hierarchical data structure: the clustered sparse voxel octrees. It is designed to represent the geometry of voxelized three-dimensional scenes and can be constructed using the out-of-core algorithm proposed in the paper. The advantage of the presented data structure is in its compact binary representation, achieved by omitting a significant number of pointers to child nodes (82.55% in case of Angel Lucy model in 128<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mrow></mrow><mn>3</mn></msup></semantics></math></inline-formula> voxels resolution) and by using a wider range of child node pointer lengths, including 8b, 16b and 32b. We achieved from 6.57 to 6.82 times more compact encoding, compared to sparse voxel octrees, whose all node components were 32b aligned, and from 4.11 to 4.27 times more compact encoding, when not all node components were 32b aligned. |
| first_indexed | 2024-03-09T19:26:52Z |
| format | Article |
| id | doaj.art-770d734dfc9147f08efd73333a355f2b |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-03-09T19:26:52Z |
| publishDate | 2022-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-770d734dfc9147f08efd73333a355f2b2023-11-24T02:52:39ZengMDPI AGSymmetry2073-89942022-10-011410211410.3390/sym14102114CSVO: Clustered Sparse Voxel Octrees—A Hierarchical Data Structure for Geometry Representation of Voxelized 3D ScenesBranislav Madoš0Eva Chovancová1Martin Chovanec2Norbert Ádám3Department of Computers and Informatics, Faculty of Electrical Engineering and Informatics, Technical University of Košice, Letná 9/A, 042 00 Košice, SlovakiaDepartment of Computers and Informatics, Faculty of Electrical Engineering and Informatics, Technical University of Košice, Letná 9/A, 042 00 Košice, SlovakiaDepartment of Computers and Informatics, Faculty of Electrical Engineering and Informatics, Technical University of Košice, Letná 9/A, 042 00 Košice, SlovakiaDepartment of Computers and Informatics, Faculty of Electrical Engineering and Informatics, Technical University of Košice, Letná 9/A, 042 00 Košice, SlovakiaWhen representing the geometry of voxelized three-dimensional scenes (especially if they have been voxelized to high resolutions) in a naive—uncompressed—form, one may end up using vast amounts of data. These can easily attack the available memory capacity of the graphics card, the operating memory or even secondary storage of computer. A viable solution to this problem is to use domain-specific hierarchical data structures, based on octant trees or directed acyclic graphs, which, among other advantages, provide a compact binary representation that can thus be considered to be their compressed encoding. These data structures include—inter alia—sparse voxel octrees, sparse voxel directed acyclic graphs and symmetry-aware sparse voxel directed acyclic graphs. The paper deals with the proposal of a new domain-specific hierarchical data structure: the clustered sparse voxel octrees. It is designed to represent the geometry of voxelized three-dimensional scenes and can be constructed using the out-of-core algorithm proposed in the paper. The advantage of the presented data structure is in its compact binary representation, achieved by omitting a significant number of pointers to child nodes (82.55% in case of Angel Lucy model in 128<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mrow></mrow><mn>3</mn></msup></semantics></math></inline-formula> voxels resolution) and by using a wider range of child node pointer lengths, including 8b, 16b and 32b. We achieved from 6.57 to 6.82 times more compact encoding, compared to sparse voxel octrees, whose all node components were 32b aligned, and from 4.11 to 4.27 times more compact encoding, when not all node components were 32b aligned.https://www.mdpi.com/2073-8994/14/10/2114clustered sparse voxel octrees (CSVO)sparse voxel octrees (SVO)sparse voxel directed acyclic graphs (SVDAG)symmetry-aware sparse voxel directed acyclic graphs (SSVDAG)hierarchical data structuregeometry representation |
| spellingShingle | Branislav Madoš Eva Chovancová Martin Chovanec Norbert Ádám CSVO: Clustered Sparse Voxel Octrees—A Hierarchical Data Structure for Geometry Representation of Voxelized 3D Scenes Symmetry clustered sparse voxel octrees (CSVO) sparse voxel octrees (SVO) sparse voxel directed acyclic graphs (SVDAG) symmetry-aware sparse voxel directed acyclic graphs (SSVDAG) hierarchical data structure geometry representation |
| title | CSVO: Clustered Sparse Voxel Octrees—A Hierarchical Data Structure for Geometry Representation of Voxelized 3D Scenes |
| title_full | CSVO: Clustered Sparse Voxel Octrees—A Hierarchical Data Structure for Geometry Representation of Voxelized 3D Scenes |
| title_fullStr | CSVO: Clustered Sparse Voxel Octrees—A Hierarchical Data Structure for Geometry Representation of Voxelized 3D Scenes |
| title_full_unstemmed | CSVO: Clustered Sparse Voxel Octrees—A Hierarchical Data Structure for Geometry Representation of Voxelized 3D Scenes |
| title_short | CSVO: Clustered Sparse Voxel Octrees—A Hierarchical Data Structure for Geometry Representation of Voxelized 3D Scenes |
| title_sort | csvo clustered sparse voxel octrees a hierarchical data structure for geometry representation of voxelized 3d scenes |
| topic | clustered sparse voxel octrees (CSVO) sparse voxel octrees (SVO) sparse voxel directed acyclic graphs (SVDAG) symmetry-aware sparse voxel directed acyclic graphs (SSVDAG) hierarchical data structure geometry representation |
| url | https://www.mdpi.com/2073-8994/14/10/2114 |
| work_keys_str_mv | AT branislavmados csvoclusteredsparsevoxeloctreesahierarchicaldatastructureforgeometryrepresentationofvoxelized3dscenes AT evachovancova csvoclusteredsparsevoxeloctreesahierarchicaldatastructureforgeometryrepresentationofvoxelized3dscenes AT martinchovanec csvoclusteredsparsevoxeloctreesahierarchicaldatastructureforgeometryrepresentationofvoxelized3dscenes AT norbertadam csvoclusteredsparsevoxeloctreesahierarchicaldatastructureforgeometryrepresentationofvoxelized3dscenes |