This page describes the structure of the FEAT VoxelMap file format, which is used to store voxel maps that can be created by using the voxel-map-gen tool and read in as FEAT::Geometry::VoxelMap objects. Voxel map files are binary files that store a (possibly zlib-compressed) 3D voxel map; 2D voxel maps are stored as voxel maps with Z-dimension equal to 0.

See also: FEAT::Geometry::VoxelMap

Basic Information about Voxel Maps

The entries in a 3D voxel map are stored in XYZ-order as byte arrays, i.e. the voxel map is stored as a sequence of XY-planes, where each plane has the same Z-coordinate, in order of ascending Z-coordinates. Each XY-plane is stored as a sequence of X-lines, where each line has the same YZ-coordinates, in order of ascending Y-coordinates. Each X-line is stores as a sequence of bytes, where each byte contains the bits of eight consecutive voxels, in order of ascending X-coordinates. 2D voxel maps consist only of a singe XY-plane.

Voxel Map Strides

The line stride specifies the length of a single X-line of voxels in bytes. By convention, the line stride must always be a multiple of 16, so typically an X-line of voxels has some padding attached at the end.

Let num_x denote the X-dimension of a voxel map, then the smallest legal line stride is given by the formula

stride_line := (((num_x + 7) / 8 + 15) / 16) * 16

where the division operator is assumed to be an integer division. The above formula consists basically of two steps: firstly, divide num_x by 8 and round up to the nearest integer and, secondly, round up to the nearest multiple of 16. The above formula can also be slightly rewritten by using bit-wise operators (yay!):

stride_line := (((num_x + 7) >> 3) + 15) & ~15)

The plane stride specifies the length of a single XY-plane of voxels in bytes. Let num_y denote the Y-dimension of a voxel map, then the smallest legal plane stride is given by

stride_plane := num_y * stride_line

The volume stide specifies the total size of the XYZ-volume of voxels in bytes. Let num_z denote the Z-dimension of a voxel map, then the smallest legal volume stride is given by

stride_volume := num_z * stride_plane

Voxel Map Indices

Let (i,j,k) denote the XYZ-indices of a voxel in a 3D voxel map with 0 <= i < num_x, 0 <= j < num_y, 0 <= k < num_z, then the bit of the corresponding voxel can be extracted by the following formula:

(voxel_map[k*plane_stride + j*line_stride + i/8] >> (i%8)) & 1

The above formula can also be slightly rewritten by using bit-wise operators (yay!):

(voxel_map[k*plane_stride + j*line_stride + (i>>3)] >> (i & 7)) & 1

Voxel Coordinates

To avoid storing floating point values in the voxel map file, the choice was made to convert the coordinates to signed integer values by first multiplying the floating point values by 1E+9 and then casting the resulting value to the signed 64-bit integer type.

Furthermore, the domain discretized by the voxel map with a given resolution is represented by the minimum and maximum X/Y/Z coordinates of the domain's bounding box stored as 64-bit signed integer values, so to obtain the floating point values one has to cast the integer values to the floating point format and then multiply these values by 1E-9.

Voxels are represented as point values, so if x_min and x_max are the minimum and maximum X-coordinates (in floating point format) of the bounding box and the voxel map has num_x voxels in X-dimension, then the X-coordinate of the i-th voxel is given by the formula

x_i := x_min + (x_max - x_min) * Real(i) / Real(num_x - 1)

where DT_ represents the floating point format, e.g. double. The Y- and Z-coordinates are computed analogously.

Voxel Map File Overview

A voxel map file consist of three sections:

136-byte file header
compression block size array (only if compressed)
(compressed) voxel map data

In the following, let u64 denote the 64-bit unsigned integer (i.e. std::uint64_t ) and let i64 denote the 64-bit signed integer (i.e. std::int64_t ) stored in little-endian (Intel) byte order.

Voxel Map File Header

The 136-byte file header is defined in FEAT::Geometry::VoxelMap::FileHeader and its entries look like follows:

Offset	Type	Name	Entry
0	u64	magic_number	must be equal to 0x70614D6C65786F56 = "VoxelMap"
8	u64	header_size	must be equal to 136
16	i64	min_x	minimum X-coordinate of bounding box
24	i64	max_x	maximum X-coordinate of bounding box
32	u64	num_x	number of points in X-dimension
40	u64	stride_line	X-line stride: see Voxel Map Strides
48	i64	min_y	minimum Y-coordinate of bounding box
56	i64	max_y	maximum Y-coordinate of bounding box
64	u64	num_y	number of points in Y-dimension
72	u64	stride_plane	XY-plane stride: see Voxel Map Strides
80	i64	min_z	minimum Z-coordinate of bounding box
88	i64	max_z	maximum Z-coordinate of bounding box
96	u64	num_z	number of points in Z-dimension (0 for a 2D voxel map)
104	u64	stride_volume	XYZ-volume stride: see Voxel Map Strides
112	u64	coverage	domain coverage multiplied by 1E+9
120	u64	planes_per_block	number of planes per compression block (0 if uncompressed)
128	u64	num_blocks	total number of compression blocks (0 if uncompressed)

Voxel Map File Compression Blocks

Voxel maps may (and actually should) be compressed by utilizing the ZLIB compression algorithms, which may easily reduce the overall file size of a voxel map file by over 95%. Since compression can be a quite resource-hungry task, the voxel map file format offers the possibility to compress the voxel map in disjoint plane blocks rather than requiring that the entire voxel map, which may be sereval GB in size, has to be compressed as a single block. The drawback is that the file has to contain an array of sizes of the indiviual compressed blocks, which is a small price to pay.

To reduce code complexity, a compression block can only contain entire XY-planes, i.e. a XY-plane must be contained in its entirety in a single compression block and so in consequence, the size of a compression block is given as the number of planes that it contains rather than the number of bytes, which can be computed by multiplying the number of planes in the block by the plane stride, see Voxel Map Strides. Note that 2D voxel maps can only be compressed into a single block.

If a voxel map file is compressed, then the planes_per_block entry of the file header stores the number of planes contained in a single compression block, however, the last compression block will typically contain less planes (unless the total number of planes is a multiple of planes_per_block, of course), i.e. the last compression block is not padded. The total number of compression blocks is stored in the num_blocks entry of the file header, which can be be computed by using the following formula:

num_blocks = (num_x * num_y + planes_per_block - 1) / planes_per_block

The sizes of the individual compression blocks are stored in an u64 array of length num_blocks directly after the file header, followed by the individual zlib-compressed voxel map block buffers without any sort of padding.

If the voxel map is not compressed, i.e. header.num_blocks is 0, then the raw voxel map is written directly after the file header without any sort of additional processing.

Author: Peter Zajac

Table of Contents