|
Voxomap
A C++11 voxel container.
|
|
Voxomap
A C++11 voxel container.
|
Voxomap is a container of voxels, it's a C++11 header only library. It was build to be used like a std container, it's templated on user data and it's possible to browse it with iterators.
The container is based on an octree and uses a structure in leaves of the tree to improve performance and memory footprint.
The library is based on an octree, it's a tree data structure in which each internal node has exactly eight children. Octrees are used to partition a three-dimensional space by recursively subdividing it into eight octants/nodes. The bottom level of the octree consists of leaf nodes that contain the voxels (user data). Octrees are the three-dimensional analog of quadtrees.
The leaf nodes of the VoxelOctree, that have size of 8, contain voxel container. A voxel container is a structure that contains voxels, it can contain 8x8x8(512) voxels. The voxel container fills all its octants/nodes, so like its container, it is axis aligned. The library allows to implement different type of voxel container. There are two implementations, but it's easy to create a new one that will better suit your needs.
This structure exists for improved performance and memory. This mixture between octree and array allows to take advantage of both structure without taking their disadvantages. Indeed, an octree has advantage to be dynamic and to not store empty space but can take lot of memory to store all its nodes and it's heavy to go through. An array, meanwhile, has advantage to store only user information (no nodes) and it's fast to go through but stores the empty space and is difficult to grow.
This structure doesn't store empty space (when no voxels, no voxel containers and no nodes), uses less nodes (voxel container inside node of size 8), it's easy to grow (advantage of a tree) and the performance for going through are very good (not so far from an array).
This structure is based on a fixed size 3D array that contains the user data. It's a very simple structure that is useful for high density of voxels.
Warning: For use this structure, the user data structure must override the boolean operator to know if it's an empty voxel or not.
This structure is a mix between a fixed size 3D array (like in ArrayContainer) and a dynamic array. Useful for little density of voxels.
The container uses 3 containers:
This structure is a wrapper on other voxel containers. It adds neighbor information inside voxels to allow the user to know the neighborhood of the voxels. The values of SideEnum are used to map the vicinity.
Warning: Since it is only a wrapper, it have to be used with another voxel container (like ArrayContainer or SparseContainer)
In this example, the blue voxel has 4 neighbors (at position x + 1, x - 1, y + 1 and z - 1).
So the side values are:
Super containers are similar to voxel containers but instead of containing voxels they contain voxel containers or super containers. Like voxel containers, the super containers contains 8x8x8 other containers and they fill all its octants/nodes.
There is two implemented super containers, ArraySuperContainer and SparseSuperContainer. They have the same characteristics as their voxel container counterpart (ArrayContainer and SparseContainer).
Like Voxel Container, this structure exists for improved performance, it allows to approach the performances of an array while keeping the advantage of the octree structure.
| Size of voxel | Number of voxels | ArrayContainer | SparseContainer |
|---|---|---|---|
| 1 byte | X | ||
| >= 2 bytes | <= 255 | X | |
| > 255 | X |
This comparative table is just here to give you an idea of what to use.
It's just a simple calculation:
Protocol:
Protocol:
1.8.20