Voxels
Internally, the mapping component uses an octree data structure to store and manage points. Adapters configured to ingest points will ingest them into an octree data structure. Octrees can be thought of as a cube with a particular size or bounds that things can be stored within. For 3D points to be stored within this cube they must fall within its bounds.
Octrees are a recursively subdivided data structure. Starting with the initial bounding box, each level of recursion divides its parent into 8 uniform children. This can be seen visualised in the following image. Each sub-cube is known as a node and nodes with no children are called leaf nodes.
An octree is defined with a maximum number of times that it can be subdivided, this is known as its maximum depth. The dimension of the leaf nodes at this maximum depth is known as the resolution of the octree. Both these values are used to compute overall bounds of the octree (represented by a cube at level 0).
Points are only stored if they fall within the bounds of the octree. The overall bounds of an octree is a function of its resolution and maximum depth.
When points are inserted, they traverse the octree until they find a leaf node at the octrees maximum depth. During the traversal, missing nodes will get constructed, and existing nodes will have their meta-information updated by the new points information (colour, intensity, etc). If two points fall within the same leaf node then the average of the meta-information of each point will be stored, however; the individual point locations will not.
Point locations are not stored after they have been used to find a corresponding leaf node. This is because the existence of the new leaf node itself is enough information to tell that something existed within that volume. Future points falling within this volume can be safely discarded, thus saving considerable amounts of memory.
More information on octrees can be found here.
There are four configuration parameters for the mapping component that relate to the internal octree data structure and how it is used. These are introduced in the following table and discussed in more detail in the following sections.
| Setting | Type | Description | Default |
|---|---|---|---|
octreeDepth | integer | The maximum depth that the octree will recurse to when adding nodes. | |
octreeResolution | float | The size of the smallest node within the octree. | |
voxelChunkSize | integer | The number of voxels that can be packed into a single telemetry message before a new one is constructed. | 20000 |
refreshOctree | bool | Whether or not the octree is cleared before each frame of points is inserted. | true |
Octree Depth
In general, the deeper the octree, the more performance is impacted. For each additional level of depth, the number of nodes in the octree can theoretically increase by a factor of 8; however, in reality, this is closer to a factor of 2 - 3. Each point inserted into the octree must also traverse the entire depth, and as a result, the deeper the octree the more computation also needs to be done.
The maximum depth supported by the map component is 16. However, care should be taken when using an octree this deep as the performance impact can be significant.
Octree Resolution
The smaller the octree resolution, the more detail can be captured. However, it comes at the expense of performance. The smaller the resolution, the more voxels are needed to represent the same object.
For large outdoor maps, we recommend a resolution of 0.1 m, for indoor maps 0.02 m - 0.05 m works well.
Octree Bounds
Points that fall outside of the octree bounds will not be captured. It is also important to note that octrees are centered around the origin. For example, an octree with a bound size of 100 m will extend from min=[-50, -50, -50] to max=[50, 50, 50].
To compute the size of the octree bounds the following equation can be used. Here b is the size of an edge of the resulting bounding box, d is the maximum depth of the octree, and r is the resolution.
For an octree of depth 12 and resolution 0.05 m the size of the bounds works out to be 204.8 m.
Voxel Chunk Size
When maps get relatively large they can be hard to send within one telemetry message. The voxelChunkSize is the number of voxels that the component will pack into a single message. Making this smaller will result in a larger number of smaller messages, and conversely, making it bigger will result in a smaller number of larger messages.
Refreshing the Octree
By default the component will clear the octree before each new frame of points is added. This is done to ensure the number of voxels that are then published remains manageable. This is the desired behaviour in most situations. However, there are times, such as when points are registered to a static coordinate frame, where it may be preferable to accumulate all points instead. To achieve this, the refreshOctree parameter can be set to false.
Any change to the map component settings within agent-settings.json will result in the map component being reset. Any accumulated points will be lost.