|
OpenVDB
11.0.0
|
This document is a high-level summary of the terminology and basic components of the OpenVDB library and is organized around two key motivating concepts. First, OpenVDB is designed specifically to work efficiently with sparse volumetric data locally sampled at a high spatial frequency, although it will function well for dense volumetric data. From this follows the need for a memory efficient representation of this sparsity and the need for fast iterators (and other tools) that respect sparsity. Second, data storage is separated from data interpretation. OpenVDB uses unit-less three-dimensional integer coordinates to address the sparse data, but introduces a unit-less continuous index space for interpolation, along with a transform to place the data in physical space.
When manipulating data in OpenVDB, the three essential objects are (1) the Tree, a B-tree-like three-dimensional data structure; (2) the Transform, which relates voxel indices (i,  j,  k) to physical locations (x,  y,  z) in World Space “world” space; and (3) the Grid, a container that associates a Tree with a Transform and additional metadata. For instancing purposes (i.e., placing copies of the same volume in multiple locations), the same tree may be referenced (via smart pointers) by several different Grids, each having a unique transform.
We now proceed to discuss the Tree and ideas of sparsity in some detail, followed by a briefer description of the different spaces and transforms as well as some of the tools that act on the sparse data.
In OpenVDB the Tree data structure exists to answer the question What value is stored at location (i,  j,  k) in three-dimensional index space? Here i, j and k are arbitrary signed 32-bit integers, and the data type of the associated value (float, bool, vector, etc.) is the same for all (i,  j,  k). While the Tree serves the same purpose as a large three-dimensional array, it is a specially designed data structure that, given sparse unique values, minimizes the overall memory footprint while retaining fast access times. This is accomplished, as the name suggests, via a tree-based acceleration structure comprising a RootNode, LeafNodes and usually one or more levels of InternalNodes with prescribed branching factors.
The tree-based acceleration structure can be configured in various ways, but with the restriction that for a given tree all the LeafNodes are at the same depth. Conceptually, the RootNode and InternalNodes increasingly subdivide the three-dimensional index space, and the LeafNodes hold the actual unique voxels.
The type of a Tree encodes both the type of the data to be stored in the tree (float, bool, etc.) and the tree’s node configuration. In practice a four-level (root, internal, internal, leaf) configuration is standard, and several common tree types are defined in openvdb.h. For example,
These predefined tree types share the same branching factors, which dictate the number of children of a given node. The branching factors (5, 4, 3) are specified as base two logarithms and should be read backwards from the leaf nodes up the tree.
In the default tree configuration, each LeafNode holds a three-dimensional grid of 23 voxels on a side (i.e., an 8×8×8 voxel grid). Internally, the LeafNode is said to be at “level 0” of the tree. At “level 1” of this tree is the first InternalNode, and it indexes a 24×24×24 = 16×16×16 grid, each entry of which is either a LeafNode or a constant value that represents an 8×8×8 block of voxels. At “level 2” is the second InternalNode in this configuration; it in turn indexes a 25×25×25 = 32×32×32 grid of level-1 InternalNodes and/or values, and so the InternalNode at level 2 subsumes a three-dimensional block of voxels of size 32×16×8 = 4096 on a side. Unlike the InternalNodes and LeafNodes, the RootNode (“level 3” for the default configuration) is not explicitly restricted in the number of children it may have, so the overall index space is limited only by the range of the integer indices, which are 32-bit by default.
Like a tree’s node configuration, the type of data held by a tree is determined at compile time. Conceptually the tree itself employs two different notions of data sparsity to reduce the memory footprint and at the same time accelerate access to its contents. The first is largely hidden from the user and concerns ways in which large regions of uniform values are compactly represented, and the second allows for fast sequential iteration, skipping user-specified “uninteresting” regions (that may or may not have uniform values).
Although the data in a tree is accessed and set on a per-voxel level (i.e., the value at (i,  j,  k)) it need not be internally stored in that way. To reduce the memory footprint and accelerate data access, data values are stored in three distinct forms internal to the tree: voxel values, tile values, and a background value. A voxel value is a unique value indexed by the location of a voxel and is stored in the LeafNode responsible for that voxel. A tile value is a uniform value assigned to all voxels subsumed by a given node. (For example, a tile Value belonging to an InternalNode at level 1 is equivalent to a constant-value cube of voxels of the same size, 8×8×8, as a LeafNode.) The tile value is returned when a request is made for the data associated with any (i,  j,  k) location within the uniform tile. The background value is a unique value (stored at the root level) that is returned when accessing any (i,  j,  k) location that does not resolve to either a tile or a LeafNode.
Any voxel or tile can be classified as either active or inactive. The interpretation of this state is application-specific, but generally active voxels are “interesting” and inactive somehow less so. The locations of active values may be sparse in the overall voxel topology, and OpenVDB provides iterators that access active values only (as well as iterators over inactive values, all values, and general topology). An example of active vs. inactive: the voxels used to store the distance values of a narrow-band level set (i.e., close to a given surface) will be marked as active while the other (“far”) voxel locations will be marked as inactive and will generally represent regions of space with constant distance values (e.g., two constant distance values of opposite sign to distinguish the enclosed inside region from the infinite outside or background embedding).
The prune method replaces with tile values any nodes that subsume voxels with the same values and active states. The resulting tree represents the same volume, but more sparsely.
The sampled data in the tree is accessed using signed index coordinates (i,  j,  k), but associating each indicial coordinate with a specific physical location is the job of a Transform. A simple linear transform assumes a lattice-like structure with a fixed physical distance Δ between indices, so that (x,  y,  z) = (Δi, Δj, Δk).
To simplify transformations between physical space and lattice index coordinates, a continuous generalization of the index lattice points called index space is used. For example, index space coordinate (1.0, 1.0, 1.0) corresponds to the same point as (1,1,1) in the index lattice, but (1.5,1.0,1.0) also has meaning as halfway between the index coordinates (1,1,1) and (2,1,1). Index space can be used in constructing interpolated data values: given an arbitrary location in physical space, one can use a transform to compute the point in index space (which need not fall on an exact integer index) that maps to that location and locally interpolate from values with neighboring index coordinates.
The interpretation of the data in a tree takes place in world space. For example, the tree might hold data sampled at discrete physical locations in world space. Transform methods such as indexToWorld and its inverse worldToIndex may be used to relate coordinates in the two continuous spaces. In addition, methods such as worldToIndexCellCentered actually return lattice points.
A Transform provides a context for interpreting the information held in a tree by associating a location in world space with each entry in the tree. The actual implementation of the Transform is managed by a Map object, which is an encapsulation of a continuous, mostly invertible function of three variables. A Map is required to provide applyMap and applyInverseMap methods to relate locations in its domain to its range and vice versa. A Map is also required to provide information about its local derivatives. For more on these classes, see the Transforms and Maps page.
For many applications, it might not be necessary ever to operate directly on trees, though there are often significant performance improvements to be gained by exploiting the tree structure. The Grid, however, is the preferred interface through which to manage voxel data, in part because a grid associates with a tree additional and often necessary information that is not accessible through the tree itself.
A Grid contains smart pointers to a Tree object and a Transform object, either or both of which might be shared with other grids. As mentioned above, the transform provides for the interpretation of voxel locations. Other grid metadata, notably the grid class, the vector type and the world space/local space toggle, affect the interpretation of voxel values.
OpenVDB is particularly well-suited (though by no means exclusively so) to the representation of narrow-band level sets and fog volumes. A narrow-band level set is represented by three distinct regions of voxels: an outside (or background) region of inactive voxels having a constant, positive distance from the level set surface; an inside region of inactive voxels having a constant, negative distance; and a thin band of active voxels (normally three voxels wide on either side of the surface) whose values are signed distances. Similarly, a fog volume is represented by an outside region of inactive voxels with value zero, an inside region of active voxels with value one, and a thin band of active voxels, with values typically varying linearly between zero and one, that separates the inside from the outside. Identifying a grid as a level set or a fog volume, by setting its grid class with setGridClass, allows tools to invoke alternative implementations that are better-suited or better-optimized for those classes. For example, resampling (in particular, scaling) a level set should normally not be done without updating its signed distance values. The resampleToMatch tool automatically recomputes signed distances for grids that are identified as level sets. (The lower-level GridResampler does not, but it is optimized for level set grids in that it transforms only voxels in the narrow band and relies on signed flood fill to reconstruct the inside and outside regions.) Other tools whose behavior is affected by the grid class include the divergence operator (which has an alternative implementation for staggered velocity grids), the volume to mesh converter, and the sphere packing tool. In addition, a number of level-set-specific tools, such as the level set tracker, throw exceptions when invoked on grids that are not identified as level sets. It is important, therefore, to set a grid’s class appropriately.
When a vector-valued grid is transformed or resampled, it is often necessary for the transform to be applied not just to voxel locations but also to voxel values. By default, grids are identified as “world-space”, meaning that if the grid is vector-valued, its voxel values should be transformed. Alternatively, voxel values of grids identified as “local-space”, via setIsInWorldSpace, do not undergo transformation. A world-space grid’s vector type, specified with setVectorType, may be invariant, covariant or contravariant, which determines how transforms are applied to the grid’s voxel values (for details see, for example, Covariance and contravariance of vectors [Wikipedia]). The transformVectors tool can be used to apply a transform to a grid’s voxel values, and it handles all of the supported vector types.
A grid can optionally be assigned name and creator strings. These are purely informational, though it might be desirable to name grids so as to easily select which ones to read from files that contain multiple grids. In the absence of grid names, or at least of unique names, OpenVDB’s file I/O routines recognize an ordinal suffix: “[0]” refers to the first unnamed grid, “[1]” refers to the second, and so on, and “density[0]” and “density[1]” refer to the first and second grids named “density”. Also of interest for file I/O is a grid’s “save float as half” setting, which allows it to be written more compactly using 16-bit floating point values rather than full-precision values. Finally, during file output certain statistics are computed and stored as per-grid metadata. These include the grid’s index-space active voxel bounding box, its active voxel count and its memory usage in bytes. This information can also be retrieved efficiently from a file.
OpenVDB provides utility functions and classes for the manipulation of grids and the data they hold. Tools such as those found in GridOperators.h compute vector quantities from scalar data or vice-versa. Other tools perform filtering (Filter.h and LevelSetFilter.h) and interpolation (Interpolation.h) as well as sampling (GridTransformer.h), compositing and constructive solid geometry (Composite.h), and other transformations (ValueTransformer.h). OpenVDB also supports advanced finite difference computations through a variety of local support stencils (Stencils.h).
OpenVDB provides efficient, often multithreaded, implementations of a large variety of morphological, filtering and other algorithms that address common data manipulation tasks on three-dimensional grids. For more specialized tasks, OpenVDB provides lower-level data accessors that enable fast iteration over all or selected voxels and over the elements of a Tree. These take several forms: iterator classes of various types, functor-based visitor methods, and the ValueAccessor, an accelerator for indexed (i,  j,  k) voxel lookups.
Iterator classes follow a fairly consistent naming scheme. First, the CIter and Iter suffixes denote const and non-const iterators, i.e., iterators that offer, respectively, read-only and read/write access to the underlying tree or node. Second, iterators over tile and voxel values are denoted either On, Off or All, indicating that they visit only active values, only inactive values, or both active and inactive values. So, for example, Tree::ValueOnCIter is a read-only iterator over all active values (both tile and voxel) of a tree, whereas LeafNode::ValueAllIter is a read/write iterator over all values, both active and inactive, of a single leaf node.
OpenVDB iterators are not STL-compatible in that one can always request an iterator that points to the beginning of a collection of elements (nodes, voxels, etc.), but one usually cannot request an iterator that points to the end of the collection. (This is because finding the end might require a full tree traversal.) Instead, all OpenVDB iterators implement a test method that returns true as long as the iterator is not exhausted and false as soon as it is. Typical usage is as follows:
or more compactly
Note that the naming scheme for methods that return “begin” iterators closely mirrors that of the iterators themselves. That is, Grid::cbeginValueOn returns a const iterator to the first of a grid’s active values, whereas LeafNode::beginValueAll returns a non-const iterator to the first of a leaf node’s values, both active and inactive. (const overloads of begin* methods are usually provided, so that if the Grid is itself const, Grid::begin* will actually return a const iterator. This makes it more convenient to use these methods in templated code.)
Finally, note that modifying the tree or node over which one is iterating typically does not invalidate the iterator, though it might first need to be incremented to point to the next existing element (for example, if one deletes a child node to which the iterator is currently pointing).
Less commonly used than tree-level iterators (but found in the implementations of some of the narrow-band level set algorithms referred to above) are node-level iterators. A node value iterator visits the values (active, inactive or both) stored in a single RootNode, InternalNode or LeafNode, whereas a node child iterator visits the children of a single root or internal node. (Recall that non-leaf nodes store either a tile value or a child node at each grid position.)
When traversing a grid by (i,  j,  k) index in a spatially coherent pattern, such as when iterating over neighboring voxels, request a ValueAccessor from the grid (with Grid::getAccessor) and use the accessor’s getValue and setValue methods, since these will usually be significantly faster (a factor of three is typical) than accessing voxels directly in the grid’s tree. The accessor records the sequence of nodes visited during the most recent access; on the next access, rather than traversing the tree from the root node down, it performs an inverted traversal from the deepest recorded node up. For neighboring voxels, the traversal need only proceed as far as the voxels’ common ancestor node, which more often than not is the first node in the sequence.
Multiple accessors may be associated with a single grid. In fact, for multithreaded, read-only access to a grid, it is recommended that each thread be assigned its own accessor. A thread-safe, mutex-locked accessor is provided (see ValueAccessorRW), but the locking negates much of the performance benefit of inverted traversal; and because it is the accessor object that is thread-safe, not the grid, concurrent reads and writes are not safe unless all threads share a single accessor.
All accessors associated with a grid must be cleared after any operation that removes nodes from the grid’s tree, such as pruning, CSG or compositing. For those and other built-in operations, this is done automatically via a callback mechanism, but developers must be careful to call Tree::clearAllAccessors whenever deleting nodes directly.
To be written
1.8.11
