2. Boxm2 Data Structures

Chapter summary:
Data structures used by the Boxm2 library

2.1 Boxm2 Scene data structures

The data structures used in boxm2 are optimized to be used both by a CPU and GPU. A scene is composed of blocks, which are specified in the scene.xml file. Each block is a fixed grid of octrees, also referred to as sub_blocks in the code. The dimension of a sub_block and the number of sub_blocks in each block are specified in the scene.xml file.

The voxel structure of each block is encoded in its own file which is located in the directory specified by the scene.xml file. Each block has a unique boxm2_block_id, which consists of three integers. This block id is how blocks and their corresponding data are identified on disk.

2.1.1 Boxm2 Block: octree based voxel structure

A boxm2_block contains the following buffers:

• boxm2_array_3d<uchar16> trees_ : a three-d buffer of bit-encoded octrees. It's dimensions are indicated in the scene.xml file.
• boxm2_array_2d<int> tree_ptrs_ : a two-d buffer that mirrors the location of corresponding data cells.
• boxm2_array_1d<ushort> trees_in_buffers_ : a one-d buffer that indicates how many trees are in each row of tree_ptrs (as they may not be full).
• boxm2_array_1d<ushort2> mem_ptrs_ : a one-d buffer that indicates where data is stored in each row of data buffers.

2.1.2 bit_trees

The voxel structure of a block is encoded in the 3d array trees_, which contains bit-encoded octrees of maximum depth 4. A bit is reserved for each potential inner node (73 on a depth 4 octree), which indicates whether or not that node has children. This tree is full, meaning all nodes either have zero children or 8 children. The first 10 bytes (index 0-9) are reserved to encode the voxel structure. Bytes (10,11) and (12,13) encode two unsigned shorts that index into any data buffer with the same ID as the block. This index points to the data that corresponds with the root node of the tree. From there, a simple counting bits algorithm is performed to find the data of a particular cell, specified by it's bit_index.

These algorithms are implemented in both OpenCL and C++. The C++ object boct_bit_tree2 is our latest implementation of the bit encoded octree. It is located in src/contrib/brl/bseg/boct/.

The structure of the data buffer is described below.

2.1.3 Data structures.

The boxm2_data<T> object is a wrapper around a boxm2_array_1d<T> buffer. The template parameter is a boxm2_data_type as specified in the file boxm2_data_traits.h. Currently, we have the following data types implemented:

• BOXM2_ALPHA : data type is float
• BOXM2_MOG3_GREY : data type is uchar8 (a typedef of vnl_vector_fixed<unsigned char, 8>)
• BOXM2_NUM_OBS : data type is ushort4 (a typedef of vnl_vector_fixed<unsigned short, 4>)
• BOXM2_AUX : data type is int4 (a typedef of vnl_vector_fixed<int, 4>)
• BOXM2_UNKNOWN : whose data type is undefined

Each data buffer is split into a two dimensional array, whose size is determined by:

• number of buffers: determined by the maximum size of a block, as specified in the scene.xml file
• number cells in each buffer: currently hardcoded to 65536 (maximum value of an unsigned short).

The cell size for each data buffer can be statically called by using boxm2_data_traits<DATA_TYPE>::datasize().

For any empty scene, the data corresponding to each tree (for the root node) is randomly distributed among the buffers. This is to ensure that trees located at surfaces are uniformly distributed, allowing for efficient usage of space and maximum growth.

The unsigned short encoded in bytes (12,13) of a tree indicate which buffer its data is in. The unsigned short encoded in bytes (10,11) indicate the offset within the buffer that points to the root node's data. The tree's data is then stored in breadth first search order within the data buffer. Given the location of the tree cell (bit index in [0,585] for a depth 4 tree), and the location of its root data, it is a simple bit counting algorithm to find the specified cell's data. This algorithm runs in log time on the index of the tree, and is further accelerated by caching tree bit counts in the OpenCL implementation.

Furthermore, all data buffers with the same boxm2_block_id have the same structure. This means that any indexing any data buffer with the same (buffIndex, buffOffset) will give you the data that corresponds to the exact same voxel. This inherent structure is important, as it allows for data modularity accross different algorithms.

2.2 Boxm2 Basic

The sub-library boxm2_basic includes wrappers around buffers that make multi-dimensional indexing easy. We currently have boxm2_array_1d<T>, boxm2_array_2d<T>, and boxm2_array_3d<T> implemented. These arrays only allocate memory to assist multi-dimensional indexing, and will not destroy the original flat buffer upon destruction. These wrappers are designed to merely wrap memory, not manage it.

This document was generated on May, 1 2013 using texi2html 1.76.