libopenvdb-doc 2.1.0-1ubuntu1 / usr / share / doc / openvdb / html / overview.html

This file is indexed.

/usr/share/doc/openvdb/html/overview.html is in libopenvdb-doc 2.1.0-1ubuntu1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below. 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.6"/>
<title>OpenVDB: OpenVDB Overview</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td style="padding-left: 0.5em;">
   <div id="projectname">OpenVDB
   &#160;<span id="projectnumber">2.1.0</span>
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.6 -->
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li class="current"><a href="pages.html"><span>Related&#160;Pages</span></a></li>
      <li><a href="namespaces.html"><span>Namespaces</span></a></li>
      <li><a href="annotated.html"><span>Classes</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
    </ul>
  </div>
<div id="nav-path" class="navpath">
  <ul>
<li class="navelem"><a class="el" href="index.html">OpenVDB</a></li>  </ul>
</div>
</div><!-- top -->
<div class="header">
  <div class="headertitle">
<div class="title">OpenVDB Overview </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><h1><a class="anchor" id="Contents"></a>
Contents</h1>
<ul>
<li><a class="el" href="overview.html#secOverview">Introduction</a></li>
<li><a class="el" href="overview.html#secTree">The Tree</a><ul>
<li><a class="el" href="overview.html#subsecTreeConfig">Tree Configuration</a></li>
</ul>
</li>
<li><a class="el" href="overview.html#secSparsity">Sparse Values and Voxels</a><ul>
<li><a class="el" href="overview.html#subsecValues">Tile, Voxel, and Background Values</a></li>
<li><a class="el" href="overview.html#subsecInactive">Active and Inactive Voxels</a></li>
</ul>
</li>
<li><a class="el" href="overview.html#secSpaceAndTrans">Coordinate Systems and Transforms</a><ul>
<li><a class="el" href="overview.html#subsecVoxSpace">Index Space</a></li>
<li><a class="el" href="overview.html#subsecWorSpace">World Space</a></li>
<li><a class="el" href="overview.html#subsecTrans">Transforms and Maps</a></li>
</ul>
</li>
<li><a class="el" href="overview.html#secToolUtils">Utilities and Tools</a></li>
<li><a class="el" href="overview.html#secIterator">Iterators</a><ul>
<li><a class="el" href="overview.html#subsecTreeIter">Tree Iterators</a></li>
<li><a class="el" href="overview.html#subsecNodeIter">Node Iterators</a></li>
<li><a class="el" href="overview.html#subsecValueAccessor">Value Accessor</a></li>
<li><a class="el" href="overview.html#subsecTraversal">Tree Traversal</a></li>
</ul>
</li>
</ul>
<h1><a class="anchor" id="secOverview"></a>
Introduction</h1>
<p>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.</p>
<p>When manipulating data in OpenVDB, the three essential objects are (1) the <a class="el" href="classopenvdb_1_1v2__1__0_1_1tree_1_1Tree.html">Tree</a>, a B-tree-like three-dimensional data structure; (2) the <a class="el" href="classopenvdb_1_1v2__1__0_1_1math_1_1Transform.html">Transform</a>, which relates voxel indices <img class="formulaInl" alt="$(i,j,k)$" src="form_51.png"/> to physical locations <img class="formulaInl" alt="$(x,y,z)$" src="form_54.png"/> in <a class="el" href="overview.html#subsecWorSpace">world</a> space; and (3) the <a class="el" href="classopenvdb_1_1v2__1__0_1_1Grid.html">Grid</a>, a container that associates a <code>Tree</code> with a <code>Transform</code> 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 <code>Grid</code>s, each having a unique transform.</p>
<p>We now proceed to discuss the <code>Tree</code> 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.</p>
<h1><a class="anchor" id="secTree"></a>
The Tree</h1>
<p>In OpenVDB the <code>Tree</code> data structure exists to answer the question <em>What value is stored at location <img class="formulaInl" alt="$(i,j,k)$" src="form_51.png"/> in three-dimensional index space?</em> Here <em>i</em>, <em>j</em> and <em>k</em> are arbitrary signed 32-bit integers, and the data type of the associated value (<code>float</code>, <code>bool</code>, vector, etc.) is the same for all <img class="formulaInl" alt="$(i,j,k)$" src="form_51.png"/>. While the <code>Tree</code> 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 <a class="el" href="classopenvdb_1_1v2__1__0_1_1tree_1_1RootNode.html">RootNode</a>, <a class="el" href="classopenvdb_1_1v2__1__0_1_1tree_1_1LeafNode.html">LeafNodes</a> and usually one or more levels of <a class="el" href="classopenvdb_1_1v2__1__0_1_1tree_1_1InternalNode.html">InternalNodes</a> with prescribed branching factors.</p>
<h2><a class="anchor" id="subsecTreeConfig"></a>
Tree Configuration</h2>
<p>The tree-based acceleration structure can be configured in various ways, but with the restriction that for a given tree all the <code>LeafNode</code>s are at the same depth. Conceptually, the <code>RootNode</code> and <code>InternalNodes</code> increasingly subdivide the three-dimensional index space, and the <code>LeafNode</code>s hold the actual unique voxels.</p>
<p>The type of a <code>Tree</code> encodes both the type of the data to be stored in the tree (<code>float</code>, <code>bool</code>, 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 <a class="el" href="openvdb_8h.html">openvdb.h</a>. For example, </p>
<div class="fragment"><div class="line"><span class="keyword">typedef</span> tree::Tree4&lt;float, 5, 4, 3&gt;::Type <a class="code" href="namespaceopenvdb_1_1v2__1__0.html#a6b41620b1f0b01f83684d2e024728562">FloatTree</a>;</div>
<div class="line"><span class="keyword">typedef</span> tree::Tree4&lt;bool, 5, 4, 3&gt;::Type  <a class="code" href="namespaceopenvdb_1_1v2__1__0.html#a155dad3305a25615b4eb7640dff865e3">BoolTree</a>;</div>
</div><!-- fragment --><p> 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.</p>
<p>In the default tree configuration, each <code>LeafNode</code> holds a three-dimensional grid of 2<sup>3</sup> voxels on a side (i.e., an <img class="formulaInl" alt="$8\times8\times8$" src="form_55.png"/> voxel grid). Internally, the <code>LeafNode</code> is said to be at "level 0" of the tree. At "level 1" of this tree is the first <code>InternalNode</code>, and it indexes a <img class="formulaInl" alt="$2^4\times2^4\times2^4 = 16\times16\times16$" src="form_56.png"/> grid, each entry of which is either a <code>LeafNode</code> or a constant value that represents an <img class="formulaInl" alt="$8\times8\times8$" src="form_55.png"/> block of voxels. At "level 2" is the second <code>InternalNode</code> in this configuration; it in turn indexes a <img class="formulaInl" alt="$2^5\times2^5\times2^5 = 32\times32\times32$" src="form_57.png"/> grid of level-1 <code>InternalNode</code>s and/or values, and so the <code>InternalNode</code> at level 2 subsumes a three-dimensional block of voxels of size <img class="formulaInl" alt="$32\times16\times8 = 4096$" src="form_58.png"/> on a side. Unlike the <code>InternalNode</code>s and <code>LeafNode</code>s, the <code>RootNode</code> ("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.</p>
<h1><a class="anchor" id="secSparsity"></a>
Sparse Values and Voxels</h1>
<p>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).</p>
<h2><a class="anchor" id="subsecValues"></a>
Tile, Voxel, and Background Values</h2>
<p>Although the data in a tree is accessed and set on a per-voxel level (i.e., the value at <img class="formulaInl" alt="$(i,j,k)$" src="form_51.png"/>) 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: <b>voxel values</b>, <b>tile values</b>, and a <b>background value</b>. A voxel value is a unique value indexed by the location of a voxel and is stored in the <code>LeafNode</code> 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 <code>InternalNode</code> at level 1 is equivalent to a constant-value cube of voxels of the same size, <img class="formulaInl" alt="$8\times8\times8$" src="form_55.png"/>, as a <code>LeafNode</code>.) The tile value is returned when a request is made for the data associated with any <img class="formulaInl" alt="$(i,j,k)$" src="form_51.png"/> location within the uniform tile. The background value is a unique value (stored at the root level) that is returned when accessing any <img class="formulaInl" alt="$(i,j,k)$" src="form_51.png"/> location that does not resolve to either a tile or a <code>LeafNode</code>.</p>
<h2><a class="anchor" id="subsecInactive"></a>
Active and Inactive Voxels</h2>
<p>Any voxel or tile can be classified as either <b>active</b> or <b>inactive</b>. 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 <a class="el" href="overview.html#secIterator">iterators</a> 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).</p>
<p>The <a class="el" href="classopenvdb_1_1v2__1__0_1_1tree_1_1Tree.html#a462c7056adc55d8da2cc5828934ff859">prune()</a> 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.</p>
<h1><a class="anchor" id="secSpaceAndTrans"></a>
Coordinate Systems and Transforms</h1>
<p>The sampled data in the tree is accessed using signed <b>index coordinates</b> <img class="formulaInl" alt="$(i,j,k)$" src="form_51.png"/>, but associating each indicial coordinate with a specific physical location is a job for a <code>Transform</code>. A simple linear transform assumes a lattice-like structure with a fixed physical distance <img class="formulaInl" alt="$\Delta$" src="form_59.png"/> between indices, so that <img class="formulaInl" alt="$(x,y,z) = (\Delta i, \Delta j, \Delta k)$" src="form_60.png"/>.</p>
<h2><a class="anchor" id="subsecVoxSpace"></a>
Index Space</h2>
<p>To simplify transformations between physical space and lattice index coordinates, a continuous generalization of the index lattice points called <b>index space</b> 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.</p>
<h2><a class="anchor" id="subsecWorSpace"></a>
World Space</h2>
<p>The interpretation of the data in a tree takes place in <b>world space</b>. For example, the tree might hold data sampled at discrete physical locations in world space. <code>Transform</code> methods such as <a class="el" href="classopenvdb_1_1v2__1__0_1_1math_1_1Transform.html#a9b0e6d022b2571d4b0551704406ac4ba">indexToWorld() </a> and its inverse <a class="el" href="classopenvdb_1_1v2__1__0_1_1math_1_1Transform.html#a917d728a21347bc8528cfdcd0cbada38">worldToIndex() </a> may be used to relate coordinates in the two continuous spaces. In addition, methods such as <a class="el" href="classopenvdb_1_1v2__1__0_1_1math_1_1Transform.html#a63423207db89c360676357577e25175d">worldToIndexCellCentered()</a> actually return lattice points.</p>
<h2><a class="anchor" id="subsecTrans"></a>
Transforms and Maps</h2>
<p>A <code>Grid</code> contains smart pointers to both a <code>Tree</code> object and a <a class="el" href="classopenvdb_1_1v2__1__0_1_1math_1_1Transform.html">Transform </a> object. The transform provides a context for interpreting the information held in the tree by associating a location in world space with each entry in the tree. The actual implementation of the <code>Transform</code> is managed by a <a class="el" href="classopenvdb_1_1v2__1__0_1_1math_1_1MapBase.html">Map</a> object, which is an encapsulation of a continuous, mostly invertible function of three variables. A <code>Map</code> is required to provide <a class="el" href="classopenvdb_1_1v2__1__0_1_1math_1_1MapBase.html#a25df8ee7780261985003d37baf6f014d">applyMap()</a> and <a class="el" href="classopenvdb_1_1v2__1__0_1_1math_1_1MapBase.html#a047af417cb22eb286a02bf3d51148eb3">applyInverseMap()</a> methods to relate locations in its domain to its range and vice versa. A <code>Map</code> is also required to provide information about its local derivatives. For more on these classes, see the <a class="el" href="transformsAndMaps.html">Transforms and Maps</a> page.</p>
<h1><a class="anchor" id="secToolUtils"></a>
Utilities and Tools</h1>
<p>OpenVDB provides utility functions and classes for the manipulation of grids and the data they hold. Tools such as those found in <a class="el" href="GridOperators_8h.html" title="Applies an operator on an input grid to produce an output grid with the same topology but potentially...">GridOperators.h</a> compute vector quantities from scalar data or vice-versa. Other tools perform filtering (<a class="el" href="Filter_8h.html" title="Filtering of VDB volumes. Note that only the values in the grid are changed, not its topology! All op...">Filter.h</a> and <a class="el" href="LevelSetFilter_8h.html" title="Performs various types of level set deformations with interface tracking. These unrestricted deformat...">LevelSetFilter.h</a>) and interpolation (<a class="el" href="Interpolation_8h.html">Interpolation.h</a>) as well as sampling (<a class="el" href="GridTransformer_8h.html">GridTransformer.h</a>), compositing and constructive solid geometry (<a class="el" href="Composite_8h.html" title="Functions to efficiently perform various compositing operations on grids. ">Composite.h</a>), and other transformations (<a class="el" href="ValueTransformer_8h.html">ValueTransformer.h</a>). OpenVDB also supports advanced finite difference computations through a variety of local support stencils (<a class="el" href="Stencils_8h.html">Stencils.h</a>).</p>
<h1><a class="anchor" id="secIterator"></a>
Iterators</h1>
<p>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 <code>Tree</code>. These take several forms: iterator classes of various types, functor-based <b>visitor</b> methods, and the <a class="el" href="classopenvdb_1_1v2__1__0_1_1tree_1_1ValueAccessor.html">ValueAccessor</a>, an accelerator for indexed <img class="formulaInl" alt="$(i,j,k)$" src="form_51.png"/> voxel lookups.</p>
<p>Iterator classes follow a fairly consistent naming scheme. First, the <b>CIter</b> and <b>Iter</b> suffixes denote <code>const</code> and non-<code>const</code> 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 <b>On</b>, <b>Off</b> or <b>All</b>, indicating that they visit only active values, only inactive values, or both active and inactive values. So, for example, <code>Tree::ValueOnCIter</code> is a read-only iterator over all active values (both tile and voxel) of a tree, whereas <code>LeafNode::ValueAllIter</code> is a read/write iterator over all values, both active and inactive, of a single leaf node.</p>
<p>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 <code>test()</code> method that returns <code>true</code> as long as the iterator is not exhausted and <code>false</code> as soon as it is. Typical usage is as follows: </p>
<div class="fragment"><div class="line"><span class="keyword">typedef</span> <a class="code" href="classopenvdb_1_1v2__1__0_1_1Grid.html">openvdb::FloatGrid</a> GridType;</div>
<div class="line">GridType grid = ...;</div>
<div class="line"><span class="keywordflow">for</span> (GridType::ValueOnCIter iter = grid.cbeginValueOn(); iter.test(); ++iter) ...</div>
</div><!-- fragment --><p> or more compactly </p>
<div class="fragment"><div class="line"><span class="keywordflow">for</span> (GridType::ValueOnCIter iter = grid.cbeginValueOn(); iter; ++iter) ...</div>
</div><!-- fragment --><p> Note that the naming scheme for methods that return "begin" iterators closely mirrors that of the iterators themselves. That is, <code>Grid::cbeginValueOn()</code> returns a <code>const</code> iterator to the first of a grid's active values, whereas <code>LeafNode::beginValueAll()</code> returns a non-<code>const</code> iterator to the first of a leaf node's values, both active and inactive. (Const overloads of <code>begin*</code>() methods are usually provided, so that if the <code>Grid</code> is itself <code>const</code>, <code>Grid::begin*</code>() will actually return a <code>const</code> iterator. This makes it more convenient to use these methods in templated code.)</p>
<p>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).</p>
<h2><a class="anchor" id="subsecTreeIter"></a>
Tree Iterators</h2>
<p><a class="anchor" id="treeValueIterRef"></a></p>
<dl class="section user"><dt>Tree::ValueIter</dt><dd>Tree-level value iterators traverse an entire tree, visiting each value (tile or voxel) exactly once. (It is also possible to restrict the traversal to minimum and maximum levels of the tree.) In addition to the methods common to all OpenVDB iterators, such as <code>test()</code> and <code>next()</code>, a <code>Tree::ValueIter</code> provides methods that return the depth in the tree of the node within which the iterator is pointing (the root node has depth 0) and the <img class="formulaInl" alt="$(i,j,k)$" src="form_51.png"/> axis-aligned bounding box of the tile or voxel to which it is pointing, and methods to get and set both the value and the active state of the tile or voxel. See the <a class="el" href="classopenvdb_1_1v2__1__0_1_1tree_1_1TreeValueIteratorBase.html">TreeValueIteratorBase </a> class for the complete list.</dd></dl>
<p><a class="anchor" id="treeLeafIterRef"></a></p>
<dl class="section user"><dt>Tree::LeafIter</dt><dd>Narrow-band level sets are represented by three distinct regions of voxels: a thin band of active voxels whose values are signed distances; an <b>outside</b> (or background) region of inactive voxels having a constant, positive distance; and an <b>inside</b> region of inactive voxels having a constant, negative distance. By convention in OpenVDB, narrow-band voxels are stored only at the leaf level of a tree, so to facilitate the implementation of level set algorithms that operate on narrow-band voxels, OpenVDB provides an iterator that visits each <code>LeafNode</code> in a tree exactly once. See the <a class="el" href="classopenvdb_1_1v2__1__0_1_1tree_1_1LeafIteratorBase.html">LeafIteratorBase </a> class for details.</dd></dl>
<p><a class="anchor" id="treeNodeIterRef"></a></p>
<dl class="section user"><dt>Tree::NodeIter</dt><dd>A node iterator traverses a tree in depth-first order, starting from its root, and visits each node exactly once. (It is also possible to restrict the traversal to minimum and maximum node depths&mdash;see the <a class="el" href="classopenvdb_1_1v2__1__0_1_1tree_1_1NodeIteratorBase.html">NodeIteratorBase </a> class for details.) Like the tree-level value iterator, the node iterator provides methods that return the depth in the tree of the node to which the iterator is pointing (the root node has depth 0) and the <img class="formulaInl" alt="$(i,j,k)$" src="form_51.png"/> axis-aligned bounding box of the voxels subsumed by the node and all of its children. </dd></dl>
<dl class="section user"><dt></dt><dd>Naturally, a node iterator also provides access to the node to which it is pointing, but this is complicated somewhat by the fact that nodes of the various types (<code>RootNode</code>, <code>InternalNode</code> and <code>LeafNode</code>) do not inherit from a common base class. For efficiency, OpenVDB generally avoids class inheritance and virtual functions in favor of templates, allowing the compiler to optimize away function calls. In particular, each node type is templated on the type of its children, so even two <code>InternalNode</code>s at different levels of a tree have distinct types. As a result, it is necessary to know the type of the node to which a node iterator is pointing in order to request access to that node. See the <a class="el" href="codeExamples.html#sNodeIterator">Cookbook</a> for an example of how to do this.</dd></dl>
<h2><a class="anchor" id="subsecNodeIter"></a>
Node Iterators</h2>
<p>Less commonly used than tree-level iterators (but found in the implementations of some of the narrow-band level set algorithms referred to <a class="el" href="overview.html#treeLeafIterRef">above</a>) are node-level iterators. A node <b>value iterator</b> visits the values (active, inactive or both) stored in a single <code>RootNode</code>, <code>InternalNode</code> or <code>LeafNode</code>, whereas a node <b>child iterator</b> 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.)</p>
<h2><a class="anchor" id="subsecValueAccessor"></a>
Value Accessor</h2>
<p>When traversing a grid by <img class="formulaInl" alt="$(i,j,k)$" src="form_51.png"/> index in a spatially coherent pattern, such as when iterating over neighboring voxels, request a <a class="el" href="classopenvdb_1_1v2__1__0_1_1tree_1_1ValueAccessor.html">ValueAccessor</a> from the grid (with <a class="el" href="classopenvdb_1_1v2__1__0_1_1Grid.html#afd9327e5a015e2e860017765f0eb372c">Grid::getAccessor()</a>) and use the accessor's <a class="el" href="classopenvdb_1_1v2__1__0_1_1tree_1_1ValueAccessor.html#aa0cec1da633233009e933bb56b1ec345">getValue()</a> and <a class="el" href="classopenvdb_1_1v2__1__0_1_1tree_1_1ValueAccessor.html#a83302a39df403b0b10ffcadac5856916">setValue()</a> 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.</p>
<p>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 <a class="el" href="structopenvdb_1_1v2__1__0_1_1tree_1_1ValueAccessorRW.html">ValueAccessorRW</a>), 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.</p>
<p>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 <a class="el" href="classopenvdb_1_1v2__1__0_1_1tree_1_1Tree.html#a24a9fa1c5dbac50f2d5f406f8842e368">Tree::clearAllAccessors()</a> whenever deleting nodes directly.</p>
<h2><a class="anchor" id="subsecTraversal"></a>
Tree Traversal</h2>
<p><em>To be written</em> </p>
</div></div><!-- contents -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated on Fri Feb 7 2014 01:56:45 for OpenVDB by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.8.6
</small></address>
</body>
</html>

APT Browse - Built by Thomas Orozco.