|
OpenVDB
9.0.1
|
The OpenVDB Tree is a sparse representation of a three-dimensional array of voxels, each element of which is addressed via discrete, three-dimensional index space coordinates, typically in the form of a Coord. For example, the following code retrieves the floating-point value of a voxel with index coordinates (1, 2, 3):
A Transform relates index space coordinates to world space coordinates that give a spatial context for the discretized data. Translation from index coordinates (i,  j,  k) to world space coordinates (x,  y,  z) is done with a call to the indexToWorld method, and from world space coordinates to index space coordinates with a call to worldToIndex:
In the above example, there are two things to notice. First, world space locations are specified as three-dimensional, double-precision, floating-point vectors, and second, worldToIndex does not return discrete coordinates, but rather a floating-point vector. This is a reflection of the fact that not every location in a continuous world space, i.e., not every (x,  y,  z), is the image of discrete integral coordinates (i,  j,  k).
Currently two different types of transforms are supported: linear and frustum transforms. A linear transform can be composed of scale, translation, rotation, and shear; essentially those things that can be mathematically represented by an invertible, constant-coefficient, 3×3 matrix and a translation (mathematically, an affine map). An essential feature of a linear transformation is that it treats all regions of index space equally: a small box in index space about origin (i,  j,  k)=(0,0,0) is mapped (sheared, scaled, rotated, etc.) in just the same way that a small box about any other index point is mapped.
The frustum transform is a nonlinear transform that treats different index points differently. And while the linear transform can be applied to any point in index or world space, the frustum transform is designed to operate on a subset of space. Specifically, it transforms a given box in index space to a tapered box in world space that is a frustum of a rectangular pyramid.
When partitioning world space with a regular grid, two popular configurations are cell-centered and vertex-centered grids. This is really a question of interpretation and transforms.
The cell-centered interpretation imagines world space as divided into discrete cells (e.g., cubes) centered on the image of the index-space lattice points. So the physical location (x,  y,  z) that is the image (result of indexToWorld) of a lattice point (i,  j,  k) is the center of a cube. In the vertex-centered approach, the images of the lattice points form the vertices of cells, so the location (x,  y,  z) would be a corner, not the center, of a cube.
The link between transforms and cell-centered or vertex-centered partitioning of world space is tenuous. It boils down to this: the “first” cell vertex often is aligned with the origin. In the cell-centered case, when the cells are cubes of length Δ on a side, the transform (x,  y,  z) = (Δi + Δ/2, Δj + Δ/2, Δk + Δ /2) will place the center of the first cube (i.e., the image of (0,0,0)) at the world space location of (Δ/2, Δ/2, Δ/2), and the cube will have walls coincident with the x=0, y=0 and z=0 planes. Using the OpenVDB transforms to create a so-called cell-centered transform could be done like this:
In contrast, for the vertex-centered partitions of space the first vertex is just the image of the first lattice point (i,  j,  k) = (0,0,0), and the transform would lack the offset used in the cell-centered case; so it would simply be (x,  y,  z) = (Δi, Δj, Δk).
A similar and often related concept to cell- and vertex-centered partitioning of world space is the idea of a voxel. A voxel historically refers to the volumetric equivalent of a pixel and as such implies a small region of world space. A voxel could, for instance, be the image under transform of a vertex-centered (or cell-centered) box in index space. In this way the voxel can be seen as a generalization of regular grid cells. The interpretation of data stored in a grid can be related to the concept of a voxel but need not be. An application might interpret the grid value indexed by (i,  j,  k) as the spatial average of a quantity in a defined world-space voxel centered on the image of that lattice point. But in other situations the value stored at (i,  j,  k) might be a discrete sample taken from a single point in world space.
The Transform class does include methods such as voxelSize and voxelVolume that suppose a particular interpretation of a voxel. They assume a voxel that is the image of a vertex-centered cube in index space, so the voxelSize methods return the lengths of line segments in world space that connect vertices:
In the case where the transform is linear, the result of voxelSize will be independent of the actual location (i,  j,  k), but the voxel size for a nonlinear transform such as a frustum will be spatially varying. The related voxelVolume can not in general be computed from the voxelSize, because there is no guarantee that a general transform will convert a cube-shaped voxel into another cube. As a result, voxelVolume actually returns the determinant of the transform, which will be a correct measure of volume even if the voxel is sheared into a general parallelepiped.
Staggered velocity data is often used in fluid simulations, and the relationship between data interpretation and transforms is somewhat peculiar when using a vector grid to hold staggered velocity data. In this case the lattice point (i,  j,  k) identifies a cell in world space by mapping to the cell’s center, but each element of the velocity vector is identified with a different face of the cell. The first element of the vector is identified with the image of the (i−1/2, j, k) face, the second element with (i, j−1/2, k), and the third element with (i, j, k−1/2).
The actual work of a Transform is performed by an implementation object called a Map. The Map in turn is a polymorphic object whose derived types are designed to optimally represent the most common transformations. Specifically, the Transform holds a MapBase pointer to a derived type that has been simplified to minimize calculations. When the transform is updated by prepending or appending a linear operation (e.g., with preRotate), the implementation map is recomputed and simplified if possible. For example, in many level-set-oriented applications the transform between index space and world space is simply a uniform scaling of the index points, i.e., (x,  y,  z) = (Δi, Δj, Δk), where Δ has some world space units. For transforms such as this, the implementation is a UniformScaleMap.
There are specialized maps for a variety of common linear transforms: pure translation (TranslationMap), uniform scale (UniformScaleMap), uniform scale and translation (UniformScaleTranslateMap), non-uniform scale (ScaleMap), and non-uniform scale and translation (ScaleTranslateMap). A general affine map (AffineMap) is used for all other cases (those that include non-degenerate rotation or shear).
The matrix representation used within OpenVDB adheres to the minority convention of right-multiplication of the matrix against a vector:
Any linear map can produce an equivalent AffineMap, which in turn can produce an equivalent 4×4 matrix. Starting with a linear transform one can produce a consistent matrix as follows:
This could be used as an intermediate form when constructing new linear transforms by combining old ones.
Notice that in the above example, the internal representation used by the transform will be simplified if possible to use one of the various map types.
Accessing a transform’s map through virtual function calls introduces some overhead and precludes compile-time optimizations such as inlining. For this reason, the more computationally intensive OpenVDB tools are templated to work directly with any underlying map. This allows the tools direct access to the map’s simplified representation and gives the compiler a free hand to inline.
Maps themselves know nothing of index space and world space, but are simply functions xrange = f(xdomain) that map 3-vectors from one space (the domain) to another (the range), or from the range back to the domain (xdomain = f−1(xrange)), by means of the methods applyMap and applyInverseMap.
In many tools, the actual map type is not known a priori and must be deduced at runtime prior to calling the appropriate map-specific or map-templated code. The type of map currently being used by a transform can be determined using the mapType method:
To simplify this process, the function processTypedMap has been provided. It accepts a transform and a functor templated on the map type.
In addition to supporting the mapping of a point from one space to another, maps also support mapping of local gradients. This results from use of the chain rule of calculus in computing the Jacobian of the map. Essentially, the gradient calculated in the domain of a map can be converted to the gradient in the range of the map, allowing one to compute a gradient in index space and then transform it to a gradient in world space.
1.8.11
