HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
RootNode.h
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (c) 2012-2017 DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
29 ///////////////////////////////////////////////////////////////////////////
30 ///
31 /// @file RootNode.h
32 ///
33 /// @brief The root node of an OpenVDB tree
34 
35 #ifndef OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
36 #define OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
37 
38 #include <map>
39 #include <set>
40 #include <sstream>
41 #include <deque>
42 #include <hboost/type_traits/remove_const.hpp>
43 #include <hboost/type_traits/remove_pointer.hpp>
44 #include <hboost/type_traits/is_pointer.hpp>
45 #include <hboost/type_traits/is_const.hpp>
46 #include <hboost/mpl/contains.hpp>
47 #include <hboost/mpl/if.hpp>
48 #include <hboost/mpl/vector.hpp>//for hboost::mpl::vector
49 #include <hboost/mpl/at.hpp>
50 #include <hboost/mpl/push_back.hpp>
51 #include <hboost/mpl/size.hpp>
52 #include <tbb/parallel_for.h>
53 #include <openvdb/Exceptions.h>
54 #include <openvdb/Types.h>
55 #include <openvdb/io/Compression.h> // for truncateRealToHalf()
56 #include <openvdb/math/Math.h> // for isZero(), isExactlyEqual(), etc.
57 #include <openvdb/math/BBox.h>
58 #include <openvdb/util/NodeMasks.h> // for backward compatibility only (see readTopology())
59 #include <openvdb/version.h>
60 
61 
62 namespace openvdb {
64 namespace OPENVDB_VERSION_NAME {
65 namespace tree {
66 
67 // Forward declarations
68 template<typename HeadType, int HeadLevel> struct NodeChain;
69 template<typename, typename> struct SameRootConfig;
70 template<typename, typename, bool> struct RootNodeCopyHelper;
71 template<typename, typename, typename, bool> struct RootNodeCombineHelper;
72 
73 
74 template<typename ChildType>
75 class RootNode
76 {
77 public:
78  typedef ChildType ChildNodeType;
79  typedef typename ChildType::LeafNodeType LeafNodeType;
80  typedef typename ChildType::ValueType ValueType;
81  typedef typename ChildType::BuildType BuildType;
82 
83  static const Index LEVEL = 1 + ChildType::LEVEL; // level 0 = leaf
84 
85  /// NodeChainType is a list of this tree's node types, from LeafNodeType to RootNode.
88 
89  /// @brief ValueConverter<T>::Type is the type of a RootNode having the same
90  /// child hierarchy as this node but a different value type, T.
91  template<typename OtherValueType>
92  struct ValueConverter {
94  };
95 
96  /// @brief SameConfiguration<OtherNodeType>::value is @c true if and only if
97  /// OtherNodeType is the type of a RootNode whose ChildNodeType has the same
98  /// configuration as this node's ChildNodeType.
99  template<typename OtherNodeType>
102  };
103 
104 
105  /// Construct a new tree with a background value of 0.
106  RootNode();
107 
108  /// Construct a new tree with the given background value.
109  explicit RootNode(const ValueType& background);
110 
111  RootNode(const RootNode& other) { *this = other; }
112 
113  /// @brief Construct a new tree that reproduces the topology and active states
114  /// of a tree of a different ValueType but the same configuration (levels,
115  /// node dimensions and branching factors). Cast the other tree's values to
116  /// this tree's ValueType.
117  /// @throw TypeError if the other tree's configuration doesn't match this tree's
118  /// or if this tree's ValueType is not constructible from the other tree's ValueType.
119  template<typename OtherChildType>
120  explicit RootNode(const RootNode<OtherChildType>& other) { *this = other; }
121 
122  /// @brief Construct a new tree that reproduces the topology and active states of
123  /// another tree (which may have a different ValueType), but not the other tree's values.
124  /// @details All tiles and voxels that are active in the other tree are set to
125  /// @a foreground in the new tree, and all inactive tiles and voxels are set to @a background.
126  /// @param other the root node of a tree having (possibly) a different ValueType
127  /// @param background the value to which inactive tiles and voxels are initialized
128  /// @param foreground the value to which active tiles and voxels are initialized
129  /// @throw TypeError if the other tree's configuration doesn't match this tree's.
130  template<typename OtherChildType>
131  RootNode(const RootNode<OtherChildType>& other,
132  const ValueType& background, const ValueType& foreground, TopologyCopy);
133 
134  /// @brief Construct a new tree that reproduces the topology and active states of
135  /// another tree (which may have a different ValueType), but not the other tree's values.
136  /// All tiles and voxels in the new tree are set to @a background regardless of
137  /// their active states in the other tree.
138  /// @param other the root node of a tree having (possibly) a different ValueType
139  /// @param background the value to which inactive tiles and voxels are initialized
140  /// @note This copy constructor is generally faster than the one that takes both
141  /// a foreground and a background value. Its main application is in multithreaded
142  /// operations where the topology of the output tree exactly matches the input tree.
143  /// @throw TypeError if the other tree's configuration doesn't match this tree's.
144  template<typename OtherChildType>
146 
147  /// @brief Copy a root node of the same type as this node.
148  RootNode& operator=(const RootNode& other);
149  /// @brief Copy a root node of the same tree configuration as this node
150  /// but a different ValueType.
151  /// @throw TypeError if the other tree's configuration doesn't match this tree's.
152  /// @note This node's ValueType must be constructible from the other node's ValueType.
153  /// For example, a root node with values of type float can be assigned to a root node
154  /// with values of type Vec3s, because a Vec3s can be constructed from a float.
155  /// But a Vec3s root node cannot be assigned to a float root node.
156  template<typename OtherChildType>
158 
159  ~RootNode() { this->clear(); }
160 
161 private:
162  struct Tile {
163  Tile(): value(zeroVal<ValueType>()), active(false) {}
164  Tile(const ValueType& v, bool b): value(v), active(b) {}
166  bool active;
167  };
168 
169  // This lightweight struct pairs child pointers and tiles.
170  struct NodeStruct {
171  ChildType* child;
172  Tile tile;
173 
174  NodeStruct(): child(nullptr) {}
175  NodeStruct(ChildType& c): child(&c) {}
176  NodeStruct(const Tile& t): child(nullptr), tile(t) {}
177  NodeStruct(const NodeStruct&) = default;
178  NodeStruct& operator=(const NodeStruct&) = default;
179  ~NodeStruct() {} ///< @note doesn't delete child
180 
181  bool isChild() const { return child != nullptr; }
182  bool isTile() const { return child == nullptr; }
183  bool isTileOff() const { return isTile() && !tile.active; }
184  bool isTileOn() const { return isTile() && tile.active; }
185 
186  void set(ChildType& c) { delete child; child = &c; }
187  void set(const Tile& t) { delete child; child = nullptr; tile = t; }
188  ChildType& steal(const Tile& t) { ChildType* c=child; child=nullptr; tile=t; return *c; }
189  };
190 
191  typedef std::map<Coord, NodeStruct> MapType;
192  typedef typename MapType::iterator MapIter;
193  typedef typename MapType::const_iterator MapCIter;
194 
195  typedef std::set<Coord> CoordSet;
196  typedef typename CoordSet::iterator CoordSetIter;
197  typedef typename CoordSet::const_iterator CoordSetCIter;
198 
199  static void setTile(const MapIter& i, const Tile& t) { i->second.set(t); }
200  static void setChild(const MapIter& i, ChildType& c) { i->second.set(c); }
201  static Tile& getTile(const MapIter& i) { return i->second.tile; }
202  static const Tile& getTile(const MapCIter& i) { return i->second.tile; }
203  static ChildType& getChild(const MapIter& i) { return *(i->second.child); }
204  static const ChildType& getChild(const MapCIter& i) { return *(i->second.child); }
205  static ChildType& stealChild(const MapIter& i, const Tile& t) {return i->second.steal(t);}
206  static const ChildType& stealChild(const MapCIter& i,const Tile& t) {return i->second.steal(t);}
207 
208  static bool isChild(const MapCIter& i) { return i->second.isChild(); }
209  static bool isChild(const MapIter& i) { return i->second.isChild(); }
210  static bool isTile(const MapCIter& i) { return i->second.isTile(); }
211  static bool isTile(const MapIter& i) { return i->second.isTile(); }
212  static bool isTileOff(const MapCIter& i) { return i->second.isTileOff(); }
213  static bool isTileOff(const MapIter& i) { return i->second.isTileOff(); }
214  static bool isTileOn(const MapCIter& i) { return i->second.isTileOn(); }
215  static bool isTileOn(const MapIter& i) { return i->second.isTileOn(); }
216 
217  struct NullPred {
218  static inline bool test(const MapIter&) { return true; }
219  static inline bool test(const MapCIter&) { return true; }
220  };
221  struct ValueOnPred {
222  static inline bool test(const MapIter& i) { return isTileOn(i); }
223  static inline bool test(const MapCIter& i) { return isTileOn(i); }
224  };
225  struct ValueOffPred {
226  static inline bool test(const MapIter& i) { return isTileOff(i); }
227  static inline bool test(const MapCIter& i) { return isTileOff(i); }
228  };
229  struct ValueAllPred {
230  static inline bool test(const MapIter& i) { return isTile(i); }
231  static inline bool test(const MapCIter& i) { return isTile(i); }
232  };
233  struct ChildOnPred {
234  static inline bool test(const MapIter& i) { return isChild(i); }
235  static inline bool test(const MapCIter& i) { return isChild(i); }
236  };
237  struct ChildOffPred {
238  static inline bool test(const MapIter& i) { return isTile(i); }
239  static inline bool test(const MapCIter& i) { return isTile(i); }
240  };
241 
242  template<typename _RootNodeT, typename _MapIterT, typename FilterPredT>
243  class BaseIter
244  {
245  public:
246  typedef _RootNodeT RootNodeT;
247  typedef _MapIterT MapIterT; // either MapIter or MapCIter
248 
249  bool operator==(const BaseIter& other) const
250  {
251  return (mParentNode == other.mParentNode) && (mIter == other.mIter);
252  }
253  bool operator!=(const BaseIter& other) const { return !(*this == other); }
254 
255  RootNodeT* getParentNode() const { return mParentNode; }
256  /// Return a reference to the node over which this iterator iterates.
257  RootNodeT& parent() const
258  {
259  if (!mParentNode) OPENVDB_THROW(ValueError, "iterator references a null parent node");
260  return *mParentNode;
261  }
262 
263  bool test() const { assert(mParentNode); return mIter != mParentNode->mTable.end(); }
264  operator bool() const { return this->test(); }
265 
266  void increment() { ++mIter; this->skip(); }
267  bool next() { this->increment(); return this->test(); }
268  void increment(Index n) { for (int i = 0; i < n && this->next(); ++i) {} }
269 
270  /// @brief Return this iterator's position as an offset from
271  /// the beginning of the parent node's map.
272  Index pos() const
273  {
274  return !mParentNode ? 0U : Index(std::distance(mParentNode->mTable.begin(), mIter));
275  }
276 
277  bool isValueOn() const { return RootNodeT::isTileOn(mIter); }
278  bool isValueOff() const { return RootNodeT::isTileOff(mIter); }
279  void setValueOn(bool on = true) const { mIter->second.tile.active = on; }
280  void setValueOff() const { mIter->second.tile.active = false; }
281 
282  /// Return the coordinates of the item to which this iterator is pointing.
283  Coord getCoord() const { return mIter->first; }
284  /// Return in @a xyz the coordinates of the item to which this iterator is pointing.
285  void getCoord(Coord& xyz) const { xyz = this->getCoord(); }
286 
287  protected:
288  BaseIter(): mParentNode(nullptr) {}
289  BaseIter(RootNodeT& parent, const MapIterT& iter): mParentNode(&parent), mIter(iter) {}
290 
291  void skip() { while (this->test() && !FilterPredT::test(mIter)) ++mIter; }
292 
293  RootNodeT* mParentNode;
294  MapIterT mIter;
295  }; // BaseIter
296 
297  template<typename RootNodeT, typename MapIterT, typename FilterPredT, typename ChildNodeT>
298  class ChildIter: public BaseIter<RootNodeT, MapIterT, FilterPredT>
299  {
300  public:
301  typedef BaseIter<RootNodeT, MapIterT, FilterPredT> BaseT;
302  typedef RootNodeT NodeType;
303  typedef NodeType ValueType;
304  typedef ChildNodeT ChildNodeType;
305  typedef typename hboost::remove_const<NodeType>::type NonConstNodeType;
306  typedef typename hboost::remove_const<ValueType>::type NonConstValueType;
307  typedef typename hboost::remove_const<ChildNodeType>::type NonConstChildNodeType;
308  using BaseT::mIter;
309 
310  ChildIter() {}
311  ChildIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
312 
313  ChildIter& operator++() { BaseT::increment(); return *this; }
314 
315  ChildNodeT& getValue() const { return getChild(mIter); }
316  ChildNodeT& operator*() const { return this->getValue(); }
317  ChildNodeT* operator->() const { return &this->getValue(); }
318  }; // ChildIter
319 
320  template<typename RootNodeT, typename MapIterT, typename FilterPredT, typename ValueT>
321  class ValueIter: public BaseIter<RootNodeT, MapIterT, FilterPredT>
322  {
323  public:
324  typedef BaseIter<RootNodeT, MapIterT, FilterPredT> BaseT;
325  typedef RootNodeT NodeType;
326  typedef ValueT ValueType;
327  typedef typename hboost::remove_const<NodeType>::type NonConstNodeType;
328  typedef typename hboost::remove_const<ValueT>::type NonConstValueType;
329  using BaseT::mIter;
330 
331  ValueIter() {}
332  ValueIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
333 
334  ValueIter& operator++() { BaseT::increment(); return *this; }
335 
336  ValueT& getValue() const { return getTile(mIter).value; }
337  ValueT& operator*() const { return this->getValue(); }
338  ValueT* operator->() const { return &(this->getValue()); }
339 
340  void setValue(const ValueT& v) const { assert(isTile(mIter)); getTile(mIter).value = v; }
341 
342  template<typename ModifyOp>
343  void modifyValue(const ModifyOp& op) const
344  {
345  assert(isTile(mIter));
346  op(getTile(mIter).value);
347  }
348  }; // ValueIter
349 
350  template<typename RootNodeT, typename MapIterT, typename ChildNodeT, typename ValueT>
351  class DenseIter: public BaseIter<RootNodeT, MapIterT, NullPred>
352  {
353  public:
354  typedef BaseIter<RootNodeT, MapIterT, NullPred> BaseT;
355  typedef RootNodeT NodeType;
356  typedef ValueT ValueType;
357  typedef ChildNodeT ChildNodeType;
358  typedef typename hboost::remove_const<NodeType>::type NonConstNodeType;
359  typedef typename hboost::remove_const<ValueT>::type NonConstValueType;
360  typedef typename hboost::remove_const<ChildNodeT>::type NonConstChildNodeType;
361  using BaseT::mIter;
362 
363  DenseIter() {}
364  DenseIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) {}
365 
366  DenseIter& operator++() { BaseT::increment(); return *this; }
367 
368  bool isChildNode() const { return isChild(mIter); }
369 
370  ChildNodeT* probeChild(NonConstValueType& value) const
371  {
372  if (isChild(mIter)) return &getChild(mIter);
373  value = getTile(mIter).value;
374  return nullptr;
375  }
376  bool probeChild(ChildNodeT*& child, NonConstValueType& value) const
377  {
378  child = this->probeChild(value);
379  return child != nullptr;
380  }
381  bool probeValue(NonConstValueType& value) const { return !this->probeChild(value); }
382 
383  void setChild(ChildNodeT& c) const { RootNodeT::setChild(mIter, c); }
384  void setChild(ChildNodeT* c) const { assert(c != nullptr); RootNodeT::setChild(mIter, *c); }
385  void setValue(const ValueT& v) const
386  {
387  if (isTile(mIter)) getTile(mIter).value = v;
388  /// @internal For consistency with iterators for other node types
389  /// (see, e.g., InternalNode::DenseIter::unsetItem()), we don't call
390  /// setTile() here, because that would also delete the child.
391  else stealChild(mIter, Tile(v, /*active=*/true));
392  }
393  }; // DenseIter
394 
395 public:
396  typedef ChildIter<RootNode, MapIter, ChildOnPred, ChildType> ChildOnIter;
397  typedef ChildIter<const RootNode, MapCIter, ChildOnPred, const ChildType> ChildOnCIter;
398  typedef ValueIter<RootNode, MapIter, ChildOffPred, const ValueType> ChildOffIter;
399  typedef ValueIter<const RootNode, MapCIter, ChildOffPred, ValueType> ChildOffCIter;
400  typedef DenseIter<RootNode, MapIter, ChildType, ValueType> ChildAllIter;
401  typedef DenseIter<const RootNode, MapCIter, const ChildType, const ValueType> ChildAllCIter;
402 
403  typedef ValueIter<RootNode, MapIter, ValueOnPred, ValueType> ValueOnIter;
404  typedef ValueIter<const RootNode, MapCIter, ValueOnPred, const ValueType> ValueOnCIter;
405  typedef ValueIter<RootNode, MapIter, ValueOffPred, ValueType> ValueOffIter;
406  typedef ValueIter<const RootNode, MapCIter, ValueOffPred, const ValueType> ValueOffCIter;
407  typedef ValueIter<RootNode, MapIter, ValueAllPred, ValueType> ValueAllIter;
408  typedef ValueIter<const RootNode, MapCIter, ValueAllPred, const ValueType> ValueAllCIter;
409 
410 
411  ChildOnCIter cbeginChildOn() const { return ChildOnCIter(*this, mTable.begin()); }
412  ChildOffCIter cbeginChildOff() const { return ChildOffCIter(*this, mTable.begin()); }
413  ChildAllCIter cbeginChildAll() const { return ChildAllCIter(*this, mTable.begin()); }
417  ChildOnIter beginChildOn() { return ChildOnIter(*this, mTable.begin()); }
418  ChildOffIter beginChildOff() { return ChildOffIter(*this, mTable.begin()); }
419  ChildAllIter beginChildAll() { return ChildAllIter(*this, mTable.begin()); }
420 
421  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(*this, mTable.begin()); }
422  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(*this, mTable.begin()); }
423  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(*this, mTable.begin()); }
427  ValueOnIter beginValueOn() { return ValueOnIter(*this, mTable.begin()); }
428  ValueOffIter beginValueOff() { return ValueOffIter(*this, mTable.begin()); }
429  ValueAllIter beginValueAll() { return ValueAllIter(*this, mTable.begin()); }
430 
431  /// Return the total amount of memory in bytes occupied by this node and its children.
432  Index64 memUsage() const;
433 
434  /// @brief Expand the specified bbox so it includes the active tiles of
435  /// this root node as well as all the active values in its child
436  /// nodes. If visitVoxels is false LeafNodes will be approximated
437  /// as dense, i.e. with all voxels active. Else the individual
438  /// active voxels are visited to produce a tight bbox.
439  void evalActiveBoundingBox(CoordBBox& bbox, bool visitVoxels = true) const;
440 
441  /// Return the bounding box of this RootNode, i.e., an infinite bounding box.
442  static CoordBBox getNodeBoundingBox() { return CoordBBox::inf(); }
443 
444  /// @brief Change inactive tiles or voxels with a value equal to +/- the
445  /// old background to the specified value (with the same sign). Active values
446  /// are unchanged.
447  ///
448  /// @param value The new background value
449  /// @param updateChildNodes If true the background values of the
450  /// child nodes is also updated. Else only the background value
451  /// stored in the RootNode itself is changed.
452  ///
453  /// @note Instead of setting @a updateChildNodes to true, consider
454  /// using tools::changeBackground or
455  /// tools::changeLevelSetBackground which are multi-threaded!
456  void setBackground(const ValueType& value, bool updateChildNodes);
457 
458  /// Return this node's background value.
459  const ValueType& background() const { return mBackground; }
460 
461  /// Return @c true if the given tile is inactive and has the background value.
462  bool isBackgroundTile(const Tile&) const;
463  //@{
464  /// Return @c true if the given iterator points to an inactive tile with the background value.
465  bool isBackgroundTile(const MapIter&) const;
466  bool isBackgroundTile(const MapCIter&) const;
467  //@}
468 
469  /// Return the number of background tiles.
470  size_t numBackgroundTiles() const;
471  /// @brief Remove all background tiles.
472  /// @return the number of tiles removed.
473  size_t eraseBackgroundTiles();
474  inline void clear();
475 
476  /// Return @c true if this node's table is either empty or contains only background tiles.
477  bool empty() const { return mTable.size() == numBackgroundTiles(); }
478 
479  /// @brief Expand this node's table so that (x, y, z) is included in the index range.
480  /// @return @c true if an expansion was performed (i.e., if (x, y, z) was not already
481  /// included in the index range).
482  bool expand(const Coord& xyz);
483 
484  static Index getLevel() { return LEVEL; }
485  static void getNodeLog2Dims(std::vector<Index>& dims);
486  static Index getChildDim() { return ChildType::DIM; }
487 
488  /// Return the number of entries in this node's table.
489  Index getTableSize() const { return static_cast<Index>(mTable.size()); }
490 
491  Index getWidth() const { return this->getMaxIndex()[0] - this->getMinIndex()[0]; }
492  Index getHeight() const { return this->getMaxIndex()[1] - this->getMinIndex()[1]; }
493  Index getDepth() const { return this->getMaxIndex()[2] - this->getMinIndex()[2]; }
494 
495  /// Return the smallest index of the current tree.
496  Coord getMinIndex() const;
497  /// Return the largest index of the current tree.
498  Coord getMaxIndex() const;
499  /// Return the current index range. Both min and max are inclusive.
500  void getIndexRange(CoordBBox& bbox) const;
501 
502  /// @brief Return @c true if the given tree has the same node and active value
503  /// topology as this tree (but possibly a different @c ValueType).
504  template<typename OtherChildType>
505  bool hasSameTopology(const RootNode<OtherChildType>& other) const;
506 
507  /// Return @c false if the other node's dimensions don't match this node's.
508  template<typename OtherChildType>
509  static bool hasSameConfiguration(const RootNode<OtherChildType>& other);
510 
511  /// Return @c true if values of the other node's ValueType can be converted
512  /// to values of this node's ValueType.
513  template<typename OtherChildType>
514  static bool hasCompatibleValueType(const RootNode<OtherChildType>& other);
515 
516  Index32 leafCount() const;
517  Index32 nonLeafCount() const;
518  Index64 onVoxelCount() const;
519  Index64 offVoxelCount() const;
520  Index64 onLeafVoxelCount() const;
521  Index64 offLeafVoxelCount() const;
522  Index64 onTileCount() const;
523 
524  bool isValueOn(const Coord& xyz) const;
525 
526  /// Return @c true if this root node, or any of its child nodes, have active tiles.
527  bool hasActiveTiles() const;
528 
529  const ValueType& getValue(const Coord& xyz) const;
530  bool probeValue(const Coord& xyz, ValueType& value) const;
531 
532  /// @brief Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides.
533  /// @details If (x, y, z) isn't explicitly represented in the tree (i.e.,
534  /// it is implicitly a background voxel), return -1.
535  int getValueDepth(const Coord& xyz) const;
536 
537  /// Set the active state of the voxel at the given coordinates but don't change its value.
538  void setActiveState(const Coord& xyz, bool on);
539  /// Set the value of the voxel at the given coordinates but don't change its active state.
540  void setValueOnly(const Coord& xyz, const ValueType& value);
541  /// Set the value of the voxel at the given coordinates and mark the voxel as active.
542  void setValueOn(const Coord& xyz, const ValueType& value);
543  /// Mark the voxel at the given coordinates as inactive but don't change its value.
544  void setValueOff(const Coord& xyz);
545  /// Set the value of the voxel at the given coordinates and mark the voxel as inactive.
546  void setValueOff(const Coord& xyz, const ValueType& value);
547 
548  /// @brief Apply a functor to the value of the voxel at the given coordinates
549  /// and mark the voxel as active.
550  template<typename ModifyOp>
551  void modifyValue(const Coord& xyz, const ModifyOp& op);
552  /// Apply a functor to the voxel at the given coordinates.
553  template<typename ModifyOp>
554  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op);
555 
556  //@{
557  /// @brief Set all voxels within a given axis-aligned box to a constant value.
558  /// @param bbox inclusive coordinates of opposite corners of an axis-aligned box
559  /// @param value the value to which to set voxels within the box
560  /// @param active if true, mark voxels within the box as active,
561  /// otherwise mark them as inactive
562  /// @note This operation generates a sparse, but not always optimally sparse,
563  /// representation of the filled box. Follow fill operations with a prune()
564  /// operation for optimal sparseness.
565  void fill(const CoordBBox& bbox, const ValueType& value, bool active = true);
566  void sparseFill(const CoordBBox& bbox, const ValueType& value, bool active = true)
567  {
568  this->fill(bbox, value, active);
569  }
570  //@}
571 
572  /// @brief Set all voxels within a given axis-aligned box to a constant value.
573  /// @param bbox inclusive coordinates of opposite corners of an axis-aligned box.
574  /// @param value the value to which to set voxels within the box.
575  /// @param active if true, mark voxels within the box as active,
576  /// otherwise mark them as inactive.
577  ///
578  /// @note This operation generates a dense representation of the
579  /// filled box. This implies that active tiles are voxelized, i.e. only active
580  /// voxels are generated from this fill operation.
581  void denseFill(const CoordBBox& bbox, const ValueType& value, bool active = true);
582 
583  /// @brief Copy into a dense grid the values of all voxels, both active and inactive,
584  /// that intersect a given bounding box.
585  /// @param bbox inclusive bounding box of the voxels to be copied into the dense grid
586  /// @param dense dense grid with a stride in @e z of one (see tools::Dense
587  /// in tools/Dense.h for the required API)
588  template<typename DenseT>
589  void copyToDense(const CoordBBox& bbox, DenseT& dense) const;
590 
591 
592  //
593  // I/O
594  //
595  bool writeTopology(std::ostream&, bool toHalf = false) const;
596  bool readTopology(std::istream&, bool fromHalf = false);
597 
598  void writeBuffers(std::ostream&, bool toHalf = false) const;
599  void readBuffers(std::istream&, bool fromHalf = false);
600  void readBuffers(std::istream&, const CoordBBox&, bool fromHalf = false);
601 
602 
603  //
604  // Voxel access
605  //
606  /// Return the value of the voxel at the given coordinates and, if necessary, update
607  /// the accessor with pointers to the nodes along the path from the root node to
608  /// the node containing the voxel.
609  /// @note Used internally by ValueAccessor.
610  template<typename AccessorT>
611  const ValueType& getValueAndCache(const Coord& xyz, AccessorT&) const;
612  /// Return @c true if the voxel at the given coordinates is active and, if necessary,
613  /// update the accessor with pointers to the nodes along the path from the root node
614  /// to the node containing the voxel.
615  /// @note Used internally by ValueAccessor.
616  template<typename AccessorT>
617  bool isValueOnAndCache(const Coord& xyz, AccessorT&) const;
618 
619  /// Change the value of the voxel at the given coordinates and mark it as active.
620  /// If necessary, update the accessor with pointers to the nodes along the path
621  /// from the root node to the node containing the voxel.
622  /// @note Used internally by ValueAccessor.
623  template<typename AccessorT>
624  void setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
625 
626  /// Set the value of the voxel at the given coordinates without changing its active state.
627  /// If necessary, update the accessor with pointers to the nodes along the path
628  /// from the root node to the node containing the voxel.
629  /// @note Used internally by ValueAccessor.
630  template<typename AccessorT>
631  void setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
632 
633  /// Apply a functor to the value of the voxel at the given coordinates
634  /// and mark the voxel as active.
635  /// If necessary, update the accessor with pointers to the nodes along the path
636  /// from the root node to the node containing the voxel.
637  /// @note Used internally by ValueAccessor.
638  template<typename ModifyOp, typename AccessorT>
639  void modifyValueAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&);
640 
641  /// Apply a functor to the voxel at the given coordinates.
642  /// If necessary, update the accessor with pointers to the nodes along the path
643  /// from the root node to the node containing the voxel.
644  /// @note Used internally by ValueAccessor.
645  template<typename ModifyOp, typename AccessorT>
646  void modifyValueAndActiveStateAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&);
647 
648  /// Change the value of the voxel at the given coordinates and mark it as inactive.
649  /// If necessary, update the accessor with pointers to the nodes along the path
650  /// from the root node to the node containing the voxel.
651  /// @note Used internally by ValueAccessor.
652  template<typename AccessorT>
653  void setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
654 
655  /// Set the active state of the voxel at the given coordinates without changing its value.
656  /// If necessary, update the accessor with pointers to the nodes along the path
657  /// from the root node to the node containing the voxel.
658  /// @note Used internally by ValueAccessor.
659  template<typename AccessorT>
660  void setActiveStateAndCache(const Coord& xyz, bool on, AccessorT&);
661 
662  /// Return, in @a value, the value of the voxel at the given coordinates and,
663  /// if necessary, update the accessor with pointers to the nodes along
664  /// the path from the root node to the node containing the voxel.
665  /// @return @c true if the voxel at the given coordinates is active
666  /// @note Used internally by ValueAccessor.
667  template<typename AccessorT>
668  bool probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT&) const;
669 
670  /// Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides.
671  /// If (x, y, z) isn't explicitly represented in the tree (i.e., it is implicitly
672  /// a background voxel), return -1. If necessary, update the accessor with pointers
673  /// to the nodes along the path from the root node to the node containing the voxel.
674  /// @note Used internally by ValueAccessor.
675  template<typename AccessorT>
676  int getValueDepthAndCache(const Coord& xyz, AccessorT&) const;
677 
678  /// Set all voxels that lie outside the given axis-aligned box to the background.
679  void clip(const CoordBBox&);
680 
681  /// @brief Reduce the memory footprint of this tree by replacing with tiles
682  /// any nodes whose values are all the same (optionally to within a tolerance)
683  /// and have the same active state.
684  ///
685  /// @note Consider instead using tools::prune which is multi-threaded!
686  void prune(const ValueType& tolerance = zeroVal<ValueType>());
687 
688  /// @brief Add the given leaf node to this tree, creating a new branch if necessary.
689  /// If a leaf node with the same origin already exists, replace it.
690  void addLeaf(LeafNodeType* leaf);
691 
692  /// @brief Same as addLeaf() but, if necessary, update the given accessor with pointers
693  /// to the nodes along the path from the root node to the node containing the coordinate.
694  template<typename AccessorT>
695  void addLeafAndCache(LeafNodeType* leaf, AccessorT&);
696 
697  /// @brief Return a pointer to the node of type @c NodeT that contains voxel (x, y, z)
698  /// and replace it with a tile of the specified value and state.
699  /// If no such node exists, leave the tree unchanged and return @c nullptr.
700  ///
701  /// @note The caller takes ownership of the node and is responsible for deleting it.
702  ///
703  /// @warning Since this method potentially removes nodes and branches of the tree,
704  /// it is important to clear the caches of all ValueAccessors associated with this tree.
705  template<typename NodeT>
706  NodeT* stealNode(const Coord& xyz, const ValueType& value, bool state);
707 
708  /// @brief Add a tile containing voxel (x, y, z) at the root level,
709  /// deleting the existing branch if necessary.
710  void addTile(const Coord& xyz, const ValueType& value, bool state);
711 
712  /// @brief Add a tile containing voxel (x, y, z) at the specified tree level,
713  /// creating a new branch if necessary. Delete any existing lower-level nodes
714  /// that contain (x, y, z).
715  void addTile(Index level, const Coord& xyz, const ValueType& value, bool state);
716 
717  /// @brief Same as addTile() but, if necessary, update the given accessor with pointers
718  /// to the nodes along the path from the root node to the node containing the coordinate.
719  template<typename AccessorT>
720  void addTileAndCache(Index level, const Coord& xyz, const ValueType&, bool state, AccessorT&);
721 
722  /// @brief Return a pointer to the leaf node that contains voxel (x, y, z).
723  /// If no such node exists, create one that preserves the values and
724  /// active states of all voxels.
725  /// @details Use this method to preallocate a static tree topology
726  /// over which to safely perform multithreaded processing.
727  LeafNodeType* touchLeaf(const Coord& xyz);
728 
729  /// @brief Same as touchLeaf() but, if necessary, update the given accessor with pointers
730  /// to the nodes along the path from the root node to the node containing the coordinate.
731  template<typename AccessorT>
732  LeafNodeType* touchLeafAndCache(const Coord& xyz, AccessorT& acc);
733 
734  //@{
735  /// @brief Return a pointer to the node that contains voxel (x, y, z).
736  /// If no such node exists, return @c nullptr.
737  template <typename NodeT>
738  NodeT* probeNode(const Coord& xyz);
739  template <typename NodeT>
740  const NodeT* probeConstNode(const Coord& xyz) const;
741  //@}
742 
743  //@{
744  /// @brief Same as probeNode() but, if necessary, update the given accessor with pointers
745  /// to the nodes along the path from the root node to the node containing the coordinate.
746  template<typename NodeT, typename AccessorT>
747  NodeT* probeNodeAndCache(const Coord& xyz, AccessorT& acc);
748  template<typename NodeT, typename AccessorT>
749  const NodeT* probeConstNodeAndCache(const Coord& xyz, AccessorT& acc) const;
750  //@}
751 
752  //@{
753  /// @brief Return a pointer to the leaf node that contains voxel (x, y, z).
754  /// If no such node exists, return @c nullptr.
755  LeafNodeType* probeLeaf(const Coord& xyz);
756  const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
757  const LeafNodeType* probeLeaf(const Coord& xyz) const;
758  //@}
759 
760  //@{
761  /// @brief Same as probeLeaf() but, if necessary, update the given accessor with pointers
762  /// to the nodes along the path from the root node to the node containing the coordinate.
763  template<typename AccessorT>
764  LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc);
765  template<typename AccessorT>
766  const LeafNodeType* probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const;
767  template<typename AccessorT>
768  const LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc) const;
769  //@}
770 
771 
772  //
773  // Aux methods
774  //
775 
776  //@{
777  /// @brief Adds all nodes of a certain type to a container with the following API:
778  /// @code
779  /// struct ArrayT {
780  /// typedef value_type;// defines the type of nodes to be added to the array
781  /// void push_back(value_type nodePtr);// method that add nodes to the array
782  /// };
783  /// @endcode
784  /// @details An example of a wrapper around a c-style array is:
785  /// @code
786  /// struct MyArray {
787  /// typedef LeafType* value_type;
788  /// value_type* ptr;
789  /// MyArray(value_type* array) : ptr(array) {}
790  /// void push_back(value_type leaf) { *ptr++ = leaf; }
791  ///};
792  /// @endcode
793  /// @details An example that constructs a list of pointer to all leaf nodes is:
794  /// @code
795  /// std::vector<const LeafNodeType*> array;//most std contains have the required API
796  /// array.reserve(tree.leafCount());//this is a fast preallocation.
797  /// tree.getNodes(array);
798  /// @endcode
799  template<typename ArrayT> void getNodes(ArrayT& array);
800  template<typename ArrayT> void getNodes(ArrayT& array) const;
801  //@}
802 
803  //@{
804  /// @brief Steals all nodes of a certain type from the tree and
805  /// adds them to a container with the following API:
806  /// @code
807  /// struct ArrayT {
808  /// typedef value_type;// defines the type of nodes to be added to the array
809  /// void push_back(value_type nodePtr);// method that add nodes to the array
810  /// };
811  /// @endcode
812  /// @details An example of a wrapper around a c-style array is:
813  /// @code
814  /// struct MyArray {
815  /// typedef LeafType* value_type;
816  /// value_type* ptr;
817  /// MyArray(value_type* array) : ptr(array) {}
818  /// void push_back(value_type leaf) { *ptr++ = leaf; }
819  ///};
820  /// @endcode
821  /// @details An example that constructs a list of pointer to all leaf nodes is:
822  /// @code
823  /// std::vector<const LeafNodeType*> array;//most std contains have the required API
824  /// array.reserve(tree.leafCount());//this is a fast preallocation.
825  /// tree.stealNodes(array);
826  /// @endcode
827  template<typename ArrayT>
828  void stealNodes(ArrayT& array, const ValueType& value, bool state);
829  template<typename ArrayT>
830  void stealNodes(ArrayT& array) { this->stealNodes(array, mBackground, false); }
831  //@}
832 
833  /// @brief Densify active tiles, i.e., replace them with leaf-level active voxels.
834  ///
835  /// @param threaded if true, this operation is multi-threaded (over the internal nodes).
836  ///
837  /// @warning This method can explode the tree's memory footprint, especially if it
838  /// contains active tiles at the upper levels, e.g. root level!
839  void voxelizeActiveTiles(bool threaded = true);
840 
841  /// @brief Efficiently merge another tree into this tree using one of several schemes.
842  /// @details This operation is primarily intended to combine trees that are mostly
843  /// non-overlapping (for example, intermediate trees from computations that are
844  /// parallelized across disjoint regions of space).
845  /// @note This operation is not guaranteed to produce an optimally sparse tree.
846  /// Follow merge() with prune() for optimal sparseness.
847  /// @warning This operation always empties the other tree.
848  template<MergePolicy Policy> void merge(RootNode& other);
849 
850  /// @brief Union this tree's set of active values with the active values
851  /// of the other tree, whose @c ValueType may be different.
852  /// @details The resulting state of a value is active if the corresponding value
853  /// was already active OR if it is active in the other tree. Also, a resulting
854  /// value maps to a voxel if the corresponding value already mapped to a voxel
855  /// OR if it is a voxel in the other tree. Thus, a resulting value can only
856  /// map to a tile if the corresponding value already mapped to a tile
857  /// AND if it is a tile value in other tree.
858  ///
859  /// @note This operation modifies only active states, not values.
860  /// Specifically, active tiles and voxels in this tree are not changed, and
861  /// tiles or voxels that were inactive in this tree but active in the other tree
862  /// are marked as active in this tree but left with their original values.
863  template<typename OtherChildType>
864  void topologyUnion(const RootNode<OtherChildType>& other);
865 
866  /// @brief Intersects this tree's set of active values with the active values
867  /// of the other tree, whose @c ValueType may be different.
868  /// @details The resulting state of a value is active only if the corresponding
869  /// value was already active AND if it is active in the other tree. Also, a
870  /// resulting value maps to a voxel if the corresponding value
871  /// already mapped to an active voxel in either of the two grids
872  /// and it maps to an active tile or voxel in the other grid.
873  ///
874  /// @note This operation can delete branches in this grid if they
875  /// overlap with inactive tiles in the other grid. Likewise active
876  /// voxels can be turned into inactive voxels resulting in leaf
877  /// nodes with no active values. Thus, it is recommended to
878  /// subsequently call prune.
879  template<typename OtherChildType>
881 
882  /// @brief Difference this tree's set of active values with the active values
883  /// of the other tree, whose @c ValueType may be different. So a
884  /// resulting voxel will be active only if the original voxel is
885  /// active in this tree and inactive in the other tree.
886  ///
887  /// @note This operation can delete branches in this grid if they
888  /// overlap with active tiles in the other grid. Likewise active
889  /// voxels can be turned into inactive voxels resulting in leaf
890  /// nodes with no active values. Thus, it is recommended to
891  /// subsequently call prune.
892  template<typename OtherChildType>
893  void topologyDifference(const RootNode<OtherChildType>& other);
894 
895  template<typename CombineOp>
896  void combine(RootNode& other, CombineOp&, bool prune = false);
897 
898  template<typename CombineOp, typename OtherRootNode /*= RootNode*/>
899  void combine2(const RootNode& other0, const OtherRootNode& other1,
900  CombineOp& op, bool prune = false);
901 
902  /// @brief Call the templated functor BBoxOp with bounding box
903  /// information for all active tiles and leaf nodes in the tree.
904  /// An additional level argument is provided for each callback.
905  ///
906  /// @note The bounding boxes are guaranteed to be non-overlapping.
907  template<typename BBoxOp> void visitActiveBBox(BBoxOp&) const;
908 
909  template<typename VisitorOp> void visit(VisitorOp&);
910  template<typename VisitorOp> void visit(VisitorOp&) const;
911 
912  template<typename OtherRootNodeType, typename VisitorOp>
913  void visit2(OtherRootNodeType& other, VisitorOp&);
914  template<typename OtherRootNodeType, typename VisitorOp>
915  void visit2(OtherRootNodeType& other, VisitorOp&) const;
916 
917 private:
918  /// During topology-only construction, access is needed
919  /// to protected/private members of other template instances.
920  template<typename> friend class RootNode;
921 
922  template<typename, typename, bool> friend struct RootNodeCopyHelper;
923  template<typename, typename, typename, bool> friend struct RootNodeCombineHelper;
924 
925  /// Currently no-op, but can be used to define empty and delete keys for mTable
926  void initTable() {}
927  //@{
928  /// @internal Used by doVisit2().
929  void resetTable(MapType& table) { mTable.swap(table); table.clear(); }
930  void resetTable(const MapType&) const {}
931  //@}
932 
933  Index getChildCount() const;
934  Index getTileCount() const;
935  Index getActiveTileCount() const;
936  Index getInactiveTileCount() const;
937 
938  /// Return a MapType key for the given coordinates.
939  static Coord coordToKey(const Coord& xyz) { return xyz & ~(ChildType::DIM - 1); }
940 
941  /// Insert this node's mTable keys into the given set.
942  void insertKeys(CoordSet&) const;
943 
944  /// Return @c true if this node's mTable contains the given key.
945  bool hasKey(const Coord& key) const { return mTable.find(key) != mTable.end(); }
946  //@{
947  /// @brief Look up the given key in this node's mTable.
948  /// @return an iterator pointing to the matching mTable entry or to mTable.end().
949  MapIter findKey(const Coord& key) { return mTable.find(key); }
950  MapCIter findKey(const Coord& key) const { return mTable.find(key); }
951  //@}
952  //@{
953  /// @brief Convert the given coordinates to a key and look the key up in this node's mTable.
954  /// @return an iterator pointing to the matching mTable entry or to mTable.end().
955  MapIter findCoord(const Coord& xyz) { return mTable.find(coordToKey(xyz)); }
956  MapCIter findCoord(const Coord& xyz) const { return mTable.find(coordToKey(xyz)); }
957  //@}
958  /// @brief Convert the given coordinates to a key and look the key up in this node's mTable.
959  /// @details If the key is not found, insert a background tile with that key.
960  /// @return an iterator pointing to the matching mTable entry.
961  MapIter findOrAddCoord(const Coord& xyz);
962 
963  /// @brief Verify that the tree rooted at @a other has the same configuration
964  /// (levels, branching factors and node dimensions) as this tree, but allow
965  /// their ValueTypes to differ.
966  /// @throw TypeError if the other tree's configuration doesn't match this tree's.
967  template<typename OtherChildType>
968  static void enforceSameConfiguration(const RootNode<OtherChildType>& other);
969 
970  /// @brief Verify that @a other has values of a type that can be converted
971  /// to this node's ValueType.
972  /// @details For example, values of type float are compatible with values of type Vec3s,
973  /// because a Vec3s can be constructed from a float. But the reverse is not true.
974  /// @throw TypeError if the other node's ValueType is not convertible into this node's.
975  template<typename OtherChildType>
976  static void enforceCompatibleValueTypes(const RootNode<OtherChildType>& other);
977 
978  template<typename CombineOp, typename OtherRootNode /*= RootNode*/>
979  void doCombine2(const RootNode&, const OtherRootNode&, CombineOp&, bool prune);
980 
981  template<typename RootNodeT, typename VisitorOp, typename ChildAllIterT>
982  static inline void doVisit(RootNodeT&, VisitorOp&);
983 
984  template<typename RootNodeT, typename OtherRootNodeT, typename VisitorOp,
985  typename ChildAllIterT, typename OtherChildAllIterT>
986  static inline void doVisit2(RootNodeT&, OtherRootNodeT&, VisitorOp&);
987 
988 
989  MapType mTable;
990  ValueType mBackground;
991 }; // end of RootNode class
992 
993 
994 ////////////////////////////////////////
995 
996 
997 /// @brief NodeChain<RootNodeType, RootNodeType::LEVEL>::Type is a hboost::mpl::vector
998 /// that lists the types of the nodes of the tree rooted at RootNodeType in reverse order,
999 /// from LeafNode to RootNode.
1000 /// @details For example, if RootNodeType is
1001 /// @code
1002 /// RootNode<InternalNode<InternalNode<LeafNode> > >
1003 /// @endcode
1004 /// then NodeChain::Type is
1005 /// @code
1006 /// hboost::mpl::vector<
1007 /// LeafNode,
1008 /// InternalNode<LeafNode>,
1009 /// InternalNode<InternalNode<LeafNode> >,
1010 /// RootNode<InternalNode<InternalNode<LeafNode> > > >
1011 /// @endcode
1012 ///
1013 /// @note Use the following to get the Nth node type, where N=0 is the LeafNodeType:
1014 /// @code
1015 /// hboost::mpl::at<NodeChainType, hboost::mpl::int_<N> >::type
1016 /// @endcode
1017 template<typename HeadT, int HeadLevel>
1018 struct NodeChain {
1019  typedef typename NodeChain<typename HeadT::ChildNodeType, HeadLevel-1>::Type SubtreeT;
1021 };
1022 
1023 /// Specialization to terminate NodeChain
1024 template<typename HeadT>
1025 struct NodeChain<HeadT, /*HeadLevel=*/1> {
1027 };
1028 
1029 
1030 ////////////////////////////////////////
1031 
1032 
1033 //@{
1034 /// Helper metafunction used to implement RootNode::SameConfiguration
1035 /// (which, as an inner class, can't be independently specialized)
1036 template<typename ChildT1, typename NodeT2>
1037 struct SameRootConfig {
1038  static const bool value = false;
1039 };
1040 
1041 template<typename ChildT1, typename ChildT2>
1042 struct SameRootConfig<ChildT1, RootNode<ChildT2> > {
1043  static const bool value = ChildT1::template SameConfiguration<ChildT2>::value;
1044 };
1045 //@}
1046 
1047 
1048 ////////////////////////////////////////
1049 
1050 
1051 template<typename ChildT>
1052 inline
1054 {
1055  this->initTable();
1056 }
1057 
1058 
1059 template<typename ChildT>
1060 inline
1061 RootNode<ChildT>::RootNode(const ValueType& background): mBackground(background)
1062 {
1063  this->initTable();
1064 }
1065 
1066 
1067 template<typename ChildT>
1068 template<typename OtherChildType>
1069 inline
1071  const ValueType& backgd, const ValueType& foregd, TopologyCopy):
1072  mBackground(backgd)
1073 {
1074  typedef RootNode<OtherChildType> OtherRootT;
1075 
1076  enforceSameConfiguration(other);
1077 
1078  const Tile bgTile(backgd, /*active=*/false), fgTile(foregd, true);
1079  this->initTable();
1080 
1081  for (typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
1082  mTable[i->first] = OtherRootT::isTile(i)
1083  ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
1084  : NodeStruct(*(new ChildT(OtherRootT::getChild(i), backgd, foregd, TopologyCopy())));
1085  }
1086 }
1087 
1088 
1089 template<typename ChildT>
1090 template<typename OtherChildType>
1091 inline
1093  const ValueType& backgd, TopologyCopy):
1094  mBackground(backgd)
1095 {
1096  typedef RootNode<OtherChildType> OtherRootT;
1097 
1098  enforceSameConfiguration(other);
1099 
1100  const Tile bgTile(backgd, /*active=*/false), fgTile(backgd, true);
1101  this->initTable();
1102  for (typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
1103  mTable[i->first] = OtherRootT::isTile(i)
1104  ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
1105  : NodeStruct(*(new ChildT(OtherRootT::getChild(i), backgd, TopologyCopy())));
1106  }
1107 }
1108 
1109 
1110 ////////////////////////////////////////
1111 
1112 
1113 // This helper class is a friend of RootNode and is needed so that assignment
1114 // with value conversion can be specialized for compatible and incompatible
1115 // pairs of RootNode types.
1116 template<typename RootT, typename OtherRootT, bool Compatible = false>
1117 struct RootNodeCopyHelper
1118 {
1119  static inline void copyWithValueConversion(RootT& self, const OtherRootT& other)
1120  {
1121  // If the two root nodes have different configurations or incompatible ValueTypes,
1122  // throw an exception.
1123  self.enforceSameConfiguration(other);
1124  self.enforceCompatibleValueTypes(other);
1125  // One of the above two tests should throw, so we should never get here:
1126  std::ostringstream ostr;
1127  ostr << "cannot convert a " << typeid(OtherRootT).name()
1128  << " to a " << typeid(RootT).name();
1129  OPENVDB_THROW(TypeError, ostr.str());
1130  }
1131 };
1132 
1133 // Specialization for root nodes of compatible types
1134 template<typename RootT, typename OtherRootT>
1135 struct RootNodeCopyHelper<RootT, OtherRootT, /*Compatible=*/true>
1136 {
1137  static inline void copyWithValueConversion(RootT& self, const OtherRootT& other)
1138  {
1139  typedef typename RootT::ValueType ValueT;
1140  typedef typename RootT::ChildNodeType ChildT;
1141  typedef typename RootT::NodeStruct NodeStruct;
1142  typedef typename RootT::Tile Tile;
1143  typedef typename OtherRootT::ValueType OtherValueT;
1144  typedef typename OtherRootT::MapCIter OtherMapCIter;
1145  typedef typename OtherRootT::Tile OtherTile;
1146 
1147  struct Local {
1148  /// @todo Consider using a value conversion functor passed as an argument instead.
1149  static inline ValueT convertValue(const OtherValueT& val) { return ValueT(val); }
1150  };
1151 
1152  self.mBackground = Local::convertValue(other.mBackground);
1153 
1154  self.clear();
1155  self.initTable();
1156 
1157  for (OtherMapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
1158  if (other.isTile(i)) {
1159  // Copy the other node's tile, but convert its value to this node's ValueType.
1160  const OtherTile& otherTile = other.getTile(i);
1161  self.mTable[i->first] = NodeStruct(
1162  Tile(Local::convertValue(otherTile.value), otherTile.active));
1163  } else {
1164  // Copy the other node's child, but convert its values to this node's ValueType.
1165  self.mTable[i->first] = NodeStruct(*(new ChildT(other.getChild(i))));
1166  }
1167  }
1168  }
1169 };
1170 
1171 
1172 // Overload for root nodes of the same type as this node
1173 template<typename ChildT>
1174 inline RootNode<ChildT>&
1176 {
1177  if (&other != this) {
1178  mBackground = other.mBackground;
1179 
1180  this->clear();
1181  this->initTable();
1182 
1183  for (MapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
1184  mTable[i->first] =
1185  isTile(i) ? NodeStruct(getTile(i)) : NodeStruct(*(new ChildT(getChild(i))));
1186  }
1187  }
1188  return *this;
1189 }
1190 
1191 // Overload for root nodes of different types
1192 template<typename ChildT>
1193 template<typename OtherChildType>
1194 inline RootNode<ChildT>&
1196 {
1197  typedef RootNode<OtherChildType> OtherRootT;
1198  typedef typename OtherRootT::ValueType OtherValueT;
1199  static const bool compatible = (SameConfiguration<OtherRootT>::value
1200  && CanConvertType</*from=*/OtherValueT, /*to=*/ValueType>::value);
1202  return *this;
1203 }
1204 
1205 
1206 ////////////////////////////////////////
1207 
1208 template<typename ChildT>
1209 inline void
1211 {
1212  if (math::isExactlyEqual(background, mBackground)) return;
1213 
1214  if (updateChildNodes) {
1215  // Traverse the tree, replacing occurrences of mBackground with background
1216  // and -mBackground with -background.
1217  for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1218  ChildT *child = iter->second.child;
1219  if (child) {
1220  child->resetBackground(/*old=*/mBackground, /*new=*/background);
1221  } else {
1222  Tile& tile = getTile(iter);
1223  if (tile.active) continue;//only change inactive tiles
1224  if (math::isApproxEqual(tile.value, mBackground)) {
1225  tile.value = background;
1226  } else if (math::isApproxEqual(tile.value, math::negative(mBackground))) {
1227  tile.value = math::negative(background);
1228  }
1229  }
1230  }
1231  }
1232  mBackground = background;
1233 }
1234 
1235 template<typename ChildT>
1236 inline bool
1237 RootNode<ChildT>::isBackgroundTile(const Tile& tile) const
1238 {
1239  return !tile.active && math::isApproxEqual(tile.value, mBackground);
1240 }
1241 
1242 template<typename ChildT>
1243 inline bool
1244 RootNode<ChildT>::isBackgroundTile(const MapIter& iter) const
1245 {
1246  return isTileOff(iter) && math::isApproxEqual(getTile(iter).value, mBackground);
1247 }
1248 
1249 template<typename ChildT>
1250 inline bool
1251 RootNode<ChildT>::isBackgroundTile(const MapCIter& iter) const
1252 {
1253  return isTileOff(iter) && math::isApproxEqual(getTile(iter).value, mBackground);
1254 }
1255 
1256 
1257 template<typename ChildT>
1258 inline size_t
1260 {
1261  size_t count = 0;
1262  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1263  if (this->isBackgroundTile(i)) ++count;
1264  }
1265  return count;
1266 }
1267 
1268 
1269 template<typename ChildT>
1270 inline size_t
1272 {
1273  std::set<Coord> keysToErase;
1274  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1275  if (this->isBackgroundTile(i)) keysToErase.insert(i->first);
1276  }
1277  for (std::set<Coord>::iterator i = keysToErase.begin(), e = keysToErase.end(); i != e; ++i) {
1278  mTable.erase(*i);
1279  }
1280  return keysToErase.size();
1281 }
1282 
1283 
1284 ////////////////////////////////////////
1285 
1286 
1287 template<typename ChildT>
1288 inline void
1289 RootNode<ChildT>::insertKeys(CoordSet& keys) const
1290 {
1291  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1292  keys.insert(i->first);
1293  }
1294 }
1295 
1296 
1297 template<typename ChildT>
1298 inline typename RootNode<ChildT>::MapIter
1299 RootNode<ChildT>::findOrAddCoord(const Coord& xyz)
1300 {
1301  const Coord key = coordToKey(xyz);
1302  std::pair<MapIter, bool> result = mTable.insert(
1303  typename MapType::value_type(key, NodeStruct(Tile(mBackground, /*active=*/false))));
1304  return result.first;
1305 }
1306 
1307 
1308 template<typename ChildT>
1309 inline bool
1310 RootNode<ChildT>::expand(const Coord& xyz)
1311 {
1312  const Coord key = coordToKey(xyz);
1313  std::pair<MapIter, bool> result = mTable.insert(
1314  typename MapType::value_type(key, NodeStruct(Tile(mBackground, /*active=*/false))));
1315  return result.second; // return true if the key did not already exist
1316 }
1317 
1318 
1319 ////////////////////////////////////////
1320 
1321 
1322 template<typename ChildT>
1323 inline void
1324 RootNode<ChildT>::getNodeLog2Dims(std::vector<Index>& dims)
1325 {
1326  dims.push_back(0); // magic number; RootNode has no Log2Dim
1327  ChildT::getNodeLog2Dims(dims);
1328 }
1329 
1330 
1331 template<typename ChildT>
1332 inline Coord
1334 {
1335  return mTable.empty() ? Coord(0) : mTable.begin()->first;
1336 }
1337 
1338 template<typename ChildT>
1339 inline Coord
1341 {
1342  return mTable.empty() ? Coord(0) : mTable.rbegin()->first + Coord(ChildT::DIM - 1);
1343 }
1344 
1345 
1346 template<typename ChildT>
1347 inline void
1348 RootNode<ChildT>::getIndexRange(CoordBBox& bbox) const
1349 {
1350  bbox.min() = this->getMinIndex();
1351  bbox.max() = this->getMaxIndex();
1352 }
1353 
1354 
1355 ////////////////////////////////////////
1356 
1357 
1358 template<typename ChildT>
1359 template<typename OtherChildType>
1360 inline bool
1362 {
1363  typedef RootNode<OtherChildType> OtherRootT;
1364  typedef typename OtherRootT::MapType OtherMapT;
1365  typedef typename OtherRootT::MapIter OtherIterT;
1366  typedef typename OtherRootT::MapCIter OtherCIterT;
1367 
1368  if (!hasSameConfiguration(other)) return false;
1369 
1370  // Create a local copy of the other node's table.
1371  OtherMapT copyOfOtherTable = other.mTable;
1372 
1373  // For each entry in this node's table...
1374  for (MapCIter thisIter = mTable.begin(); thisIter != mTable.end(); ++thisIter) {
1375  if (this->isBackgroundTile(thisIter)) continue; // ignore background tiles
1376 
1377  // Fail if there is no corresponding entry in the other node's table.
1378  OtherCIterT otherIter = other.findKey(thisIter->first);
1379  if (otherIter == other.mTable.end()) return false;
1380 
1381  // Fail if this entry is a tile and the other is a child or vice-versa.
1382  if (isChild(thisIter)) {//thisIter points to a child
1383  if (OtherRootT::isTile(otherIter)) return false;
1384  // Fail if both entries are children, but the children have different topology.
1385  if (!getChild(thisIter).hasSameTopology(&OtherRootT::getChild(otherIter))) return false;
1386  } else {//thisIter points to a tile
1387  if (OtherRootT::isChild(otherIter)) return false;
1388  if (getTile(thisIter).active != OtherRootT::getTile(otherIter).active) return false;
1389  }
1390 
1391  // Remove tiles and child nodes with matching topology from
1392  // the copy of the other node's table. This is required since
1393  // the two root tables can include an arbitrary number of
1394  // background tiles and still have the same topology!
1395  copyOfOtherTable.erase(otherIter->first);
1396  }
1397  // Fail if the remaining entries in copyOfOtherTable are not all background tiles.
1398  for (OtherIterT i = copyOfOtherTable.begin(), e = copyOfOtherTable.end(); i != e; ++i) {
1399  if (!other.isBackgroundTile(i)) return false;
1400  }
1401  return true;
1402 }
1403 
1404 
1405 template<typename ChildT>
1406 template<typename OtherChildType>
1407 inline bool
1409 {
1410  std::vector<Index> thisDims, otherDims;
1411  RootNode::getNodeLog2Dims(thisDims);
1413  return (thisDims == otherDims);
1414 }
1415 
1416 
1417 template<typename ChildT>
1418 template<typename OtherChildType>
1419 inline void
1421 {
1422  std::vector<Index> thisDims, otherDims;
1423  RootNode::getNodeLog2Dims(thisDims);
1425  if (thisDims != otherDims) {
1426  std::ostringstream ostr;
1427  ostr << "grids have incompatible configurations (" << thisDims[0];
1428  for (size_t i = 1, N = thisDims.size(); i < N; ++i) ostr << " x " << thisDims[i];
1429  ostr << " vs. " << otherDims[0];
1430  for (size_t i = 1, N = otherDims.size(); i < N; ++i) ostr << " x " << otherDims[i];
1431  ostr << ")";
1432  OPENVDB_THROW(TypeError, ostr.str());
1433  }
1434 }
1435 
1436 
1437 template<typename ChildT>
1438 template<typename OtherChildType>
1439 inline bool
1441 {
1442  typedef typename OtherChildType::ValueType OtherValueType;
1443  return CanConvertType</*from=*/OtherValueType, /*to=*/ValueType>::value;
1444 }
1445 
1446 
1447 template<typename ChildT>
1448 template<typename OtherChildType>
1449 inline void
1451 {
1452  typedef typename OtherChildType::ValueType OtherValueType;
1454  std::ostringstream ostr;
1455  ostr << "values of type " << typeNameAsString<OtherValueType>()
1456  << " cannot be converted to type " << typeNameAsString<ValueType>();
1457  OPENVDB_THROW(TypeError, ostr.str());
1458  }
1459 }
1460 
1461 
1462 ////////////////////////////////////////
1463 
1464 
1465 template<typename ChildT>
1466 inline Index64
1468 {
1469  Index64 sum = sizeof(*this);
1470  for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1471  if (const ChildT *child = iter->second.child) {
1472  sum += child->memUsage();
1473  }
1474  }
1475  return sum;
1476 }
1477 
1478 
1479 template<typename ChildT>
1480 inline void
1482 {
1483  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1484  delete i->second.child;
1485  }
1486  mTable.clear();
1487 }
1488 
1489 
1490 template<typename ChildT>
1491 inline void
1492 RootNode<ChildT>::evalActiveBoundingBox(CoordBBox& bbox, bool visitVoxels) const
1493 {
1494  for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1495  if (const ChildT *child = iter->second.child) {
1496  child->evalActiveBoundingBox(bbox, visitVoxels);
1497  } else if (isTileOn(iter)) {
1498  bbox.expand(iter->first, ChildT::DIM);
1499  }
1500  }
1501 }
1502 
1503 
1504 template<typename ChildT>
1505 inline Index
1507  Index sum = 0;
1508  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1509  if (isChild(i)) ++sum;
1510  }
1511  return sum;
1512 }
1513 
1514 
1515 template<typename ChildT>
1516 inline Index
1517 RootNode<ChildT>::getTileCount() const
1518 {
1519  Index sum = 0;
1520  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1521  if (isTile(i)) ++sum;
1522  }
1523  return sum;
1524 }
1525 
1526 
1527 template<typename ChildT>
1528 inline Index
1529 RootNode<ChildT>::getActiveTileCount() const
1530 {
1531  Index sum = 0;
1532  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1533  if (isTileOn(i)) ++sum;
1534  }
1535  return sum;
1536 }
1537 
1538 
1539 template<typename ChildT>
1540 inline Index
1541 RootNode<ChildT>::getInactiveTileCount() const
1542 {
1543  Index sum = 0;
1544  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1545  if (isTileOff(i)) ++sum;
1546  }
1547  return sum;
1548 }
1549 
1550 
1551 template<typename ChildT>
1552 inline Index32
1554 {
1555  Index32 sum = 0;
1556  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1557  if (isChild(i)) sum += getChild(i).leafCount();
1558  }
1559  return sum;
1560 }
1561 
1562 
1563 template<typename ChildT>
1564 inline Index32
1566 {
1567  Index32 sum = 1;
1568  if (ChildT::LEVEL != 0) {
1569  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1570  if (isChild(i)) sum += getChild(i).nonLeafCount();
1571  }
1572  }
1573  return sum;
1574 }
1575 
1576 
1577 template<typename ChildT>
1578 inline Index64
1580 {
1581  Index64 sum = 0;
1582  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1583  if (isChild(i)) {
1584  sum += getChild(i).onVoxelCount();
1585  } else if (isTileOn(i)) {
1586  sum += ChildT::NUM_VOXELS;
1587  }
1588  }
1589  return sum;
1590 }
1591 
1592 
1593 template<typename ChildT>
1594 inline Index64
1596 {
1597  Index64 sum = 0;
1598  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1599  if (isChild(i)) {
1600  sum += getChild(i).offVoxelCount();
1601  } else if (isTileOff(i) && !this->isBackgroundTile(i)) {
1602  sum += ChildT::NUM_VOXELS;
1603  }
1604  }
1605  return sum;
1606 }
1607 
1608 
1609 template<typename ChildT>
1610 inline Index64
1612 {
1613  Index64 sum = 0;
1614  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1615  if (isChild(i)) sum += getChild(i).onLeafVoxelCount();
1616  }
1617  return sum;
1618 }
1619 
1620 
1621 template<typename ChildT>
1622 inline Index64
1624 {
1625  Index64 sum = 0;
1626  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1627  if (isChild(i)) sum += getChild(i).offLeafVoxelCount();
1628  }
1629  return sum;
1630 }
1631 
1632 template<typename ChildT>
1633 inline Index64
1635 {
1636  Index64 sum = 0;
1637  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1638  if (isChild(i)) {
1639  sum += getChild(i).onTileCount();
1640  } else if (isTileOn(i)) {
1641  sum += 1;
1642  }
1643  }
1644  return sum;
1645 }
1646 
1647 ////////////////////////////////////////
1648 
1649 
1650 template<typename ChildT>
1651 inline bool
1652 RootNode<ChildT>::isValueOn(const Coord& xyz) const
1653 {
1654  MapCIter iter = this->findCoord(xyz);
1655  if (iter == mTable.end() || isTileOff(iter)) return false;
1656  return isTileOn(iter) ? true : getChild(iter).isValueOn(xyz);
1657 }
1658 
1659 template<typename ChildT>
1660 inline bool
1662 {
1663  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1664  if (isChild(i) ? getChild(i).hasActiveTiles() : getTile(i).active) return true;
1665  }
1666  return false;
1667 }
1668 
1669 template<typename ChildT>
1670 template<typename AccessorT>
1671 inline bool
1672 RootNode<ChildT>::isValueOnAndCache(const Coord& xyz, AccessorT& acc) const
1673 {
1674  MapCIter iter = this->findCoord(xyz);
1675  if (iter == mTable.end() || isTileOff(iter)) return false;
1676  if (isTileOn(iter)) return true;
1677  acc.insert(xyz, &getChild(iter));
1678  return getChild(iter).isValueOnAndCache(xyz, acc);
1679 }
1680 
1681 
1682 template<typename ChildT>
1683 inline const typename ChildT::ValueType&
1684 RootNode<ChildT>::getValue(const Coord& xyz) const
1685 {
1686  MapCIter iter = this->findCoord(xyz);
1687  return iter == mTable.end() ? mBackground
1688  : (isTile(iter) ? getTile(iter).value : getChild(iter).getValue(xyz));
1689 }
1690 
1691 template<typename ChildT>
1692 template<typename AccessorT>
1693 inline const typename ChildT::ValueType&
1694 RootNode<ChildT>::getValueAndCache(const Coord& xyz, AccessorT& acc) const
1695 {
1696  MapCIter iter = this->findCoord(xyz);
1697  if (iter == mTable.end()) return mBackground;
1698  if (isChild(iter)) {
1699  acc.insert(xyz, &getChild(iter));
1700  return getChild(iter).getValueAndCache(xyz, acc);
1701  }
1702  return getTile(iter).value;
1703 }
1704 
1705 
1706 template<typename ChildT>
1707 inline int
1708 RootNode<ChildT>::getValueDepth(const Coord& xyz) const
1709 {
1710  MapCIter iter = this->findCoord(xyz);
1711  return iter == mTable.end() ? -1
1712  : (isTile(iter) ? 0 : int(LEVEL) - int(getChild(iter).getValueLevel(xyz)));
1713 }
1714 
1715 template<typename ChildT>
1716 template<typename AccessorT>
1717 inline int
1718 RootNode<ChildT>::getValueDepthAndCache(const Coord& xyz, AccessorT& acc) const
1719 {
1720  MapCIter iter = this->findCoord(xyz);
1721  if (iter == mTable.end()) return -1;
1722  if (isTile(iter)) return 0;
1723  acc.insert(xyz, &getChild(iter));
1724  return int(LEVEL) - int(getChild(iter).getValueLevelAndCache(xyz, acc));
1725 }
1726 
1727 
1728 template<typename ChildT>
1729 inline void
1731 {
1732  MapIter iter = this->findCoord(xyz);
1733  if (iter != mTable.end() && !isTileOff(iter)) {
1734  if (isTileOn(iter)) {
1735  setChild(iter, *new ChildT(xyz, getTile(iter).value, /*active=*/true));
1736  }
1737  getChild(iter).setValueOff(xyz);
1738  }
1739 }
1740 
1741 
1742 template<typename ChildT>
1743 inline void
1744 RootNode<ChildT>::setActiveState(const Coord& xyz, bool on)
1745 {
1746  ChildT* child = nullptr;
1747  MapIter iter = this->findCoord(xyz);
1748  if (iter == mTable.end()) {
1749  if (on) {
1750  child = new ChildT(xyz, mBackground);
1751  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1752  } else {
1753  // Nothing to do; (x, y, z) is background and therefore already inactive.
1754  }
1755  } else if (isChild(iter)) {
1756  child = &getChild(iter);
1757  } else if (on != getTile(iter).active) {
1758  child = new ChildT(xyz, getTile(iter).value, !on);
1759  setChild(iter, *child);
1760  }
1761  if (child) child->setActiveState(xyz, on);
1762 }
1763 
1764 template<typename ChildT>
1765 template<typename AccessorT>
1766 inline void
1767 RootNode<ChildT>::setActiveStateAndCache(const Coord& xyz, bool on, AccessorT& acc)
1768 {
1769  ChildT* child = nullptr;
1770  MapIter iter = this->findCoord(xyz);
1771  if (iter == mTable.end()) {
1772  if (on) {
1773  child = new ChildT(xyz, mBackground);
1774  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1775  } else {
1776  // Nothing to do; (x, y, z) is background and therefore already inactive.
1777  }
1778  } else if (isChild(iter)) {
1779  child = &getChild(iter);
1780  } else if (on != getTile(iter).active) {
1781  child = new ChildT(xyz, getTile(iter).value, !on);
1782  setChild(iter, *child);
1783  }
1784  if (child) {
1785  acc.insert(xyz, child);
1786  child->setActiveStateAndCache(xyz, on, acc);
1787  }
1788 }
1789 
1790 
1791 template<typename ChildT>
1792 inline void
1793 RootNode<ChildT>::setValueOff(const Coord& xyz, const ValueType& value)
1794 {
1795  ChildT* child = nullptr;
1796  MapIter iter = this->findCoord(xyz);
1797  if (iter == mTable.end()) {
1798  if (!math::isExactlyEqual(mBackground, value)) {
1799  child = new ChildT(xyz, mBackground);
1800  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1801  }
1802  } else if (isChild(iter)) {
1803  child = &getChild(iter);
1804  } else if (isTileOn(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1805  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1806  setChild(iter, *child);
1807  }
1808  if (child) child->setValueOff(xyz, value);
1809 }
1810 
1811 template<typename ChildT>
1812 template<typename AccessorT>
1813 inline void
1814 RootNode<ChildT>::setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1815 {
1816  ChildT* child = nullptr;
1817  MapIter iter = this->findCoord(xyz);
1818  if (iter == mTable.end()) {
1819  if (!math::isExactlyEqual(mBackground, value)) {
1820  child = new ChildT(xyz, mBackground);
1821  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1822  }
1823  } else if (isChild(iter)) {
1824  child = &getChild(iter);
1825  } else if (isTileOn(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1826  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1827  setChild(iter, *child);
1828  }
1829  if (child) {
1830  acc.insert(xyz, child);
1831  child->setValueOffAndCache(xyz, value, acc);
1832  }
1833 }
1834 
1835 
1836 template<typename ChildT>
1837 inline void
1838 RootNode<ChildT>::setValueOn(const Coord& xyz, const ValueType& value)
1839 {
1840  ChildT* child = nullptr;
1841  MapIter iter = this->findCoord(xyz);
1842  if (iter == mTable.end()) {
1843  child = new ChildT(xyz, mBackground);
1844  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1845  } else if (isChild(iter)) {
1846  child = &getChild(iter);
1847  } else if (isTileOff(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1848  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1849  setChild(iter, *child);
1850  }
1851  if (child) child->setValueOn(xyz, value);
1852 }
1853 
1854 template<typename ChildT>
1855 template<typename AccessorT>
1856 inline void
1857 RootNode<ChildT>::setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1858 {
1859  ChildT* child = nullptr;
1860  MapIter iter = this->findCoord(xyz);
1861  if (iter == mTable.end()) {
1862  child = new ChildT(xyz, mBackground);
1863  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1864  } else if (isChild(iter)) {
1865  child = &getChild(iter);
1866  } else if (isTileOff(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1867  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1868  setChild(iter, *child);
1869  }
1870  if (child) {
1871  acc.insert(xyz, child);
1872  child->setValueAndCache(xyz, value, acc);
1873  }
1874 }
1875 
1876 
1877 template<typename ChildT>
1878 inline void
1879 RootNode<ChildT>::setValueOnly(const Coord& xyz, const ValueType& value)
1880 {
1881  ChildT* child = nullptr;
1882  MapIter iter = this->findCoord(xyz);
1883  if (iter == mTable.end()) {
1884  child = new ChildT(xyz, mBackground);
1885  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1886  } else if (isChild(iter)) {
1887  child = &getChild(iter);
1888  } else if (!math::isExactlyEqual(getTile(iter).value, value)) {
1889  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1890  setChild(iter, *child);
1891  }
1892  if (child) child->setValueOnly(xyz, value);
1893 }
1894 
1895 template<typename ChildT>
1896 template<typename AccessorT>
1897 inline void
1898 RootNode<ChildT>::setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1899 {
1900  ChildT* child = nullptr;
1901  MapIter iter = this->findCoord(xyz);
1902  if (iter == mTable.end()) {
1903  child = new ChildT(xyz, mBackground);
1904  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1905  } else if (isChild(iter)) {
1906  child = &getChild(iter);
1907  } else if (!math::isExactlyEqual(getTile(iter).value, value)) {
1908  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1909  setChild(iter, *child);
1910  }
1911  if (child) {
1912  acc.insert(xyz, child);
1913  child->setValueOnlyAndCache(xyz, value, acc);
1914  }
1915 }
1916 
1917 
1918 template<typename ChildT>
1919 template<typename ModifyOp>
1920 inline void
1921 RootNode<ChildT>::modifyValue(const Coord& xyz, const ModifyOp& op)
1922 {
1923  ChildT* child = nullptr;
1924  MapIter iter = this->findCoord(xyz);
1925  if (iter == mTable.end()) {
1926  child = new ChildT(xyz, mBackground);
1927  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1928  } else if (isChild(iter)) {
1929  child = &getChild(iter);
1930  } else {
1931  // Need to create a child if the tile is inactive,
1932  // in order to activate voxel (x, y, z).
1933  bool createChild = isTileOff(iter);
1934  if (!createChild) {
1935  // Need to create a child if applying the functor
1936  // to the tile value produces a different value.
1937  const ValueType& tileVal = getTile(iter).value;
1938  ValueType modifiedVal = tileVal;
1939  op(modifiedVal);
1940  createChild = !math::isExactlyEqual(tileVal, modifiedVal);
1941  }
1942  if (createChild) {
1943  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1944  setChild(iter, *child);
1945  }
1946  }
1947  if (child) child->modifyValue(xyz, op);
1948 }
1949 
1950 template<typename ChildT>
1951 template<typename ModifyOp, typename AccessorT>
1952 inline void
1953 RootNode<ChildT>::modifyValueAndCache(const Coord& xyz, const ModifyOp& op, AccessorT& acc)
1954 {
1955  ChildT* child = nullptr;
1956  MapIter iter = this->findCoord(xyz);
1957  if (iter == mTable.end()) {
1958  child = new ChildT(xyz, mBackground);
1959  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1960  } else if (isChild(iter)) {
1961  child = &getChild(iter);
1962  } else {
1963  // Need to create a child if the tile is inactive,
1964  // in order to activate voxel (x, y, z).
1965  bool createChild = isTileOff(iter);
1966  if (!createChild) {
1967  // Need to create a child if applying the functor
1968  // to the tile value produces a different value.
1969  const ValueType& tileVal = getTile(iter).value;
1970  ValueType modifiedVal = tileVal;
1971  op(modifiedVal);
1972  createChild = !math::isExactlyEqual(tileVal, modifiedVal);
1973  }
1974  if (createChild) {
1975  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1976  setChild(iter, *child);
1977  }
1978  }
1979  if (child) {
1980  acc.insert(xyz, child);
1981  child->modifyValueAndCache(xyz, op, acc);
1982  }
1983 }
1984 
1985 
1986 template<typename ChildT>
1987 template<typename ModifyOp>
1988 inline void
1989 RootNode<ChildT>::modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op)
1990 {
1991  ChildT* child = nullptr;
1992  MapIter iter = this->findCoord(xyz);
1993  if (iter == mTable.end()) {
1994  child = new ChildT(xyz, mBackground);
1995  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1996  } else if (isChild(iter)) {
1997  child = &getChild(iter);
1998  } else {
1999  const Tile& tile = getTile(iter);
2000  bool modifiedState = tile.active;
2001  ValueType modifiedVal = tile.value;
2002  op(modifiedVal, modifiedState);
2003  // Need to create a child if applying the functor to the tile
2004  // produces a different value or active state.
2005  if (modifiedState != tile.active || !math::isExactlyEqual(modifiedVal, tile.value)) {
2006  child = new ChildT(xyz, tile.value, tile.active);
2007  setChild(iter, *child);
2008  }
2009  }
2010  if (child) child->modifyValueAndActiveState(xyz, op);
2011 }
2012 
2013 template<typename ChildT>
2014 template<typename ModifyOp, typename AccessorT>
2015 inline void
2017  const Coord& xyz, const ModifyOp& op, AccessorT& acc)
2018 {
2019  ChildT* child = nullptr;
2020  MapIter iter = this->findCoord(xyz);
2021  if (iter == mTable.end()) {
2022  child = new ChildT(xyz, mBackground);
2023  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2024  } else if (isChild(iter)) {
2025  child = &getChild(iter);
2026  } else {
2027  const Tile& tile = getTile(iter);
2028  bool modifiedState = tile.active;
2029  ValueType modifiedVal = tile.value;
2030  op(modifiedVal, modifiedState);
2031  // Need to create a child if applying the functor to the tile
2032  // produces a different value or active state.
2033  if (modifiedState != tile.active || !math::isExactlyEqual(modifiedVal, tile.value)) {
2034  child = new ChildT(xyz, tile.value, tile.active);
2035  setChild(iter, *child);
2036  }
2037  }
2038  if (child) {
2039  acc.insert(xyz, child);
2040  child->modifyValueAndActiveStateAndCache(xyz, op, acc);
2041  }
2042 }
2043 
2044 
2045 template<typename ChildT>
2046 inline bool
2047 RootNode<ChildT>::probeValue(const Coord& xyz, ValueType& value) const
2048 {
2049  MapCIter iter = this->findCoord(xyz);
2050  if (iter == mTable.end()) {
2051  value = mBackground;
2052  return false;
2053  } else if (isChild(iter)) {
2054  return getChild(iter).probeValue(xyz, value);
2055  }
2056  value = getTile(iter).value;
2057  return isTileOn(iter);
2058 }
2059 
2060 template<typename ChildT>
2061 template<typename AccessorT>
2062 inline bool
2063 RootNode<ChildT>::probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT& acc) const
2064 {
2065  MapCIter iter = this->findCoord(xyz);
2066  if (iter == mTable.end()) {
2067  value = mBackground;
2068  return false;
2069  } else if (isChild(iter)) {
2070  acc.insert(xyz, &getChild(iter));
2071  return getChild(iter).probeValueAndCache(xyz, value, acc);
2072  }
2073  value = getTile(iter).value;
2074  return isTileOn(iter);
2075 }
2076 
2077 
2078 ////////////////////////////////////////
2079 
2080 template<typename ChildT>
2081 inline void
2082 RootNode<ChildT>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
2083 {
2084  if (bbox.empty()) return;
2085 
2086  Coord xyz, tileMax;
2087  for (int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) {
2088  xyz.setX(x);
2089  for (int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) {
2090  xyz.setY(y);
2091  for (int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) {
2092  xyz.setZ(z);
2093 
2094  // Get the bounds of the tile that contains voxel (x, y, z).
2095  Coord tileMin = coordToKey(xyz);
2096  tileMax = tileMin.offsetBy(ChildT::DIM - 1);
2097 
2098  if (xyz != tileMin || Coord::lessThan(bbox.max(), tileMax)) {
2099  // If the box defined by (xyz, bbox.max()) doesn't completely enclose
2100  // the tile to which xyz belongs, create a child node (or retrieve
2101  // the existing one).
2102  ChildT* child = nullptr;
2103  MapIter iter = this->findKey(tileMin);
2104  if (iter == mTable.end()) {
2105  // No child or tile exists. Create a child and initialize it
2106  // with the background value.
2107  child = new ChildT(xyz, mBackground);
2108  mTable[tileMin] = NodeStruct(*child);
2109  } else if (isTile(iter)) {
2110  // Replace the tile with a newly-created child that is initialized
2111  // with the tile's value and active state.
2112  const Tile& tile = getTile(iter);
2113  child = new ChildT(xyz, tile.value, tile.active);
2114  mTable[tileMin] = NodeStruct(*child);
2115  } else if (isChild(iter)) {
2116  child = &getChild(iter);
2117  }
2118  // Forward the fill request to the child.
2119  if (child) {
2120  const Coord tmp = Coord::minComponent(bbox.max(), tileMax);
2121  child->fill(CoordBBox(xyz, tmp), value, active);
2122  }
2123  } else {
2124  // If the box given by (xyz, bbox.max()) completely encloses
2125  // the tile to which xyz belongs, create the tile (if it
2126  // doesn't already exist) and give it the fill value.
2127  MapIter iter = this->findOrAddCoord(tileMin);
2128  setTile(iter, Tile(value, active));
2129  }
2130  }
2131  }
2132  }
2133 }
2134 
2135 template<typename ChildT>
2136 inline void
2137 RootNode<ChildT>::denseFill(const CoordBBox& bbox, const ValueType& value, bool active)
2138 {
2139  this->sparseFill(bbox, value, active);
2140  this->voxelizeActiveTiles(true);//multi-threaded
2141 }
2142 
2143 template<typename ChildT>
2144 template<typename DenseT>
2145 inline void
2146 RootNode<ChildT>::copyToDense(const CoordBBox& bbox, DenseT& dense) const
2147 {
2148  typedef typename DenseT::ValueType DenseValueType;
2149 
2150  const size_t xStride = dense.xStride(), yStride = dense.yStride(), zStride = dense.zStride();
2151  const Coord& min = dense.bbox().min();
2152  CoordBBox nodeBBox;
2153  for (Coord xyz = bbox.min(); xyz[0] <= bbox.max()[0]; xyz[0] = nodeBBox.max()[0] + 1) {
2154  for (xyz[1] = bbox.min()[1]; xyz[1] <= bbox.max()[1]; xyz[1] = nodeBBox.max()[1] + 1) {
2155  for (xyz[2] = bbox.min()[2]; xyz[2] <= bbox.max()[2]; xyz[2] = nodeBBox.max()[2] + 1) {
2156 
2157  // Get the coordinate bbox of the child node that contains voxel xyz.
2158  nodeBBox = CoordBBox::createCube(coordToKey(xyz), ChildT::DIM);
2159 
2160  // Get the coordinate bbox of the interection of inBBox and nodeBBox
2161  CoordBBox sub(xyz, Coord::minComponent(bbox.max(), nodeBBox.max()));
2162 
2163  MapCIter iter = this->findKey(nodeBBox.min());
2164  if (iter != mTable.end() && isChild(iter)) {//is a child
2165  getChild(iter).copyToDense(sub, dense);
2166  } else {//is background or a tile value
2167  const ValueType value = iter==mTable.end() ? mBackground : getTile(iter).value;
2168  sub.translate(-min);
2169  DenseValueType* a0 = dense.data() + zStride*sub.min()[2];
2170  for (Int32 x=sub.min()[0], ex=sub.max()[0]+1; x<ex; ++x) {
2171  DenseValueType* a1 = a0 + x*xStride;
2172  for (Int32 y=sub.min()[1], ey=sub.max()[1]+1; y<ey; ++y) {
2173  DenseValueType* a2 = a1 + y*yStride;
2174  for (Int32 z=sub.min()[2], ez=sub.max()[2]+1; z<ez; ++z, a2 += zStride) {
2175  *a2 = DenseValueType(value);
2176  }
2177  }
2178  }
2179  }
2180  }
2181  }
2182  }
2183 }
2184 
2185 ////////////////////////////////////////
2186 
2187 
2188 template<typename ChildT>
2189 inline bool
2190 RootNode<ChildT>::writeTopology(std::ostream& os, bool toHalf) const
2191 {
2192  if (!toHalf) {
2193  os.write(reinterpret_cast<const char*>(&mBackground), sizeof(ValueType));
2194  } else {
2195  ValueType truncatedVal = io::truncateRealToHalf(mBackground);
2196  os.write(reinterpret_cast<const char*>(&truncatedVal), sizeof(ValueType));
2197  }
2198  io::setGridBackgroundValuePtr(os, &mBackground);
2199 
2200  const Index numTiles = this->getTileCount(), numChildren = this->getChildCount();
2201  os.write(reinterpret_cast<const char*>(&numTiles), sizeof(Index));
2202  os.write(reinterpret_cast<const char*>(&numChildren), sizeof(Index));
2203 
2204  if (numTiles == 0 && numChildren == 0) return false;
2205 
2206  // Write tiles.
2207  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2208  if (isChild(i)) continue;
2209  os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 * sizeof(Int32));
2210  os.write(reinterpret_cast<const char*>(&getTile(i).value), sizeof(ValueType));
2211  os.write(reinterpret_cast<const char*>(&getTile(i).active), sizeof(bool));
2212  }
2213  // Write child nodes.
2214  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2215  if (isTile(i)) continue;
2216  os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 * sizeof(Int32));
2217  getChild(i).writeTopology(os, toHalf);
2218  }
2219 
2220  return true; // not empty
2221 }
2222 
2223 
2224 template<typename ChildT>
2225 inline bool
2226 RootNode<ChildT>::readTopology(std::istream& is, bool fromHalf)
2227 {
2228  // Delete the existing tree.
2229  this->clear();
2230 
2232  // Read and convert an older-format RootNode.
2233 
2234  // For backward compatibility with older file formats, read both
2235  // outside and inside background values.
2236  is.read(reinterpret_cast<char*>(&mBackground), sizeof(ValueType));
2237  ValueType inside;
2238  is.read(reinterpret_cast<char*>(&inside), sizeof(ValueType));
2239 
2240  io::setGridBackgroundValuePtr(is, &mBackground);
2241 
2242  // Read the index range.
2243  Coord rangeMin, rangeMax;
2244  is.read(reinterpret_cast<char*>(rangeMin.asPointer()), 3 * sizeof(Int32));
2245  is.read(reinterpret_cast<char*>(rangeMax.asPointer()), 3 * sizeof(Int32));
2246 
2247  this->initTable();
2248  Index tableSize = 0, log2Dim[4] = { 0, 0, 0, 0 };
2249  Int32 offset[3];
2250  for (int i = 0; i < 3; ++i) {
2251  offset[i] = rangeMin[i] >> ChildT::TOTAL;
2252  rangeMin[i] = offset[i] << ChildT::TOTAL;
2253  log2Dim[i] = 1 + util::FindHighestOn((rangeMax[i] >> ChildT::TOTAL) - offset[i]);
2254  tableSize += log2Dim[i];
2255  rangeMax[i] = (((1 << log2Dim[i]) + offset[i]) << ChildT::TOTAL) - 1;
2256  }
2257  log2Dim[3] = log2Dim[1] + log2Dim[2];
2258  tableSize = 1U << tableSize;
2259 
2260  // Read masks.
2261  util::RootNodeMask childMask(tableSize), valueMask(tableSize);
2262  childMask.load(is);
2263  valueMask.load(is);
2264 
2265  // Read child nodes/values.
2266  for (Index i = 0; i < tableSize; ++i) {
2267  // Compute origin = offset2coord(i).
2268  Index n = i;
2269  Coord origin;
2270  origin[0] = (n >> log2Dim[3]) + offset[0];
2271  n &= (1U << log2Dim[3]) - 1;
2272  origin[1] = (n >> log2Dim[2]) + offset[1];
2273  origin[2] = (n & ((1U << log2Dim[2]) - 1)) + offset[1];
2274  origin <<= ChildT::TOTAL;
2275 
2276  if (childMask.isOn(i)) {
2277  // Read in and insert a child node.
2278 #ifdef OPENVDB_2_ABI_COMPATIBLE
2279  ChildT* child = new ChildT(origin, mBackground);
2280 #else
2281  ChildT* child = new ChildT(PartialCreate(), origin, mBackground);
2282 #endif
2283  child->readTopology(is);
2284  mTable[origin] = NodeStruct(*child);
2285  } else {
2286  // Read in a tile value and insert a tile, but only if the value
2287  // is either active or non-background.
2288  ValueType value;
2289  is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
2290  if (valueMask.isOn(i) || (!math::isApproxEqual(value, mBackground))) {
2291  mTable[origin] = NodeStruct(Tile(value, valueMask.isOn(i)));
2292  }
2293  }
2294  }
2295  return true;
2296  }
2297 
2298  // Read a RootNode that was stored in the current format.
2299 
2300  is.read(reinterpret_cast<char*>(&mBackground), sizeof(ValueType));
2301  io::setGridBackgroundValuePtr(is, &mBackground);
2302 
2303  Index numTiles = 0, numChildren = 0;
2304  is.read(reinterpret_cast<char*>(&numTiles), sizeof(Index));
2305  is.read(reinterpret_cast<char*>(&numChildren), sizeof(Index));
2306 
2307  if (numTiles == 0 && numChildren == 0) return false;
2308 
2309  Int32 vec[3];
2310  ValueType value;
2311  bool active;
2312 
2313  // Read tiles.
2314  for (Index n = 0; n < numTiles; ++n) {
2315  is.read(reinterpret_cast<char*>(vec), 3 * sizeof(Int32));
2316  is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
2317  is.read(reinterpret_cast<char*>(&active), sizeof(bool));
2318  mTable[Coord(vec)] = NodeStruct(Tile(value, active));
2319  }
2320 
2321  // Read child nodes.
2322  for (Index n = 0; n < numChildren; ++n) {
2323  is.read(reinterpret_cast<char*>(vec), 3 * sizeof(Int32));
2324  Coord origin(vec);
2325 #ifdef OPENVDB_2_ABI_COMPATIBLE
2326  ChildT* child = new ChildT(origin, mBackground);
2327 #else
2328  ChildT* child = new ChildT(PartialCreate(), origin, mBackground);
2329 #endif
2330  child->readTopology(is, fromHalf);
2331  mTable[Coord(vec)] = NodeStruct(*child);
2332  }
2333 
2334  return true; // not empty
2335 }
2336 
2337 
2338 template<typename ChildT>
2339 inline void
2340 RootNode<ChildT>::writeBuffers(std::ostream& os, bool toHalf) const
2341 {
2342  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2343  if (isChild(i)) getChild(i).writeBuffers(os, toHalf);
2344  }
2345 }
2346 
2347 
2348 template<typename ChildT>
2349 inline void
2350 RootNode<ChildT>::readBuffers(std::istream& is, bool fromHalf)
2351 {
2352  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2353  if (isChild(i)) getChild(i).readBuffers(is, fromHalf);
2354  }
2355 }
2356 
2357 
2358 template<typename ChildT>
2359 inline void
2360 RootNode<ChildT>::readBuffers(std::istream& is, const CoordBBox& clipBBox, bool fromHalf)
2361 {
2362  const Tile bgTile(mBackground, /*active=*/false);
2363 
2364  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2365  if (isChild(i)) {
2366  // Stream in and clip the branch rooted at this child.
2367  // (We can't skip over children that lie outside the clipping region,
2368  // because buffers are serialized in depth-first order and need to be
2369  // unserialized in the same order.)
2370  ChildT& child = getChild(i);
2371  child.readBuffers(is, clipBBox, fromHalf);
2372  }
2373  }
2374  // Clip root-level tiles and prune children that were clipped.
2375  this->clip(clipBBox);
2376 }
2377 
2378 
2379 ////////////////////////////////////////
2380 
2381 
2382 template<typename ChildT>
2383 inline void
2384 RootNode<ChildT>::clip(const CoordBBox& clipBBox)
2385 {
2386  const Tile bgTile(mBackground, /*active=*/false);
2387 
2388  // Iterate over a copy of this node's table so that we can modify the original.
2389  // (Copying the table copies child node pointers, not the nodes themselves.)
2390  MapType copyOfTable(mTable);
2391  for (MapIter i = copyOfTable.begin(), e = copyOfTable.end(); i != e; ++i) {
2392  const Coord& xyz = i->first; // tile or child origin
2393  CoordBBox tileBBox(xyz, xyz.offsetBy(ChildT::DIM - 1)); // tile or child bounds
2394  if (!clipBBox.hasOverlap(tileBBox)) {
2395  // This table entry lies completely outside the clipping region. Delete it.
2396  setTile(this->findCoord(xyz), bgTile); // delete any existing child node first
2397  mTable.erase(xyz);
2398  } else if (!clipBBox.isInside(tileBBox)) {
2399  // This table entry does not lie completely inside the clipping region
2400  // and must be clipped.
2401  if (isChild(i)) {
2402  getChild(i).clip(clipBBox, mBackground);
2403  } else {
2404  // Replace this tile with a background tile, then fill the clip region
2405  // with the tile's original value. (This might create a child branch.)
2406  tileBBox.intersect(clipBBox);
2407  const Tile& origTile = getTile(i);
2408  setTile(this->findCoord(xyz), bgTile);
2409  this->sparseFill(tileBBox, origTile.value, origTile.active);
2410  }
2411  } else {
2412  // This table entry lies completely inside the clipping region. Leave it intact.
2413  }
2414  }
2415  this->prune(); // also erases root-level background tiles
2416 }
2417 
2418 
2419 ////////////////////////////////////////
2420 
2421 
2422 template<typename ChildT>
2423 inline void
2425 {
2426  bool state = false;
2427  ValueType value = zeroVal<ValueType>();
2428  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2429  if (this->isTile(i)) continue;
2430  this->getChild(i).prune(tolerance);
2431  if (this->getChild(i).isConstant(value, state, tolerance)) {
2432  this->setTile(i, Tile(value, state));
2433  }
2434  }
2435  this->eraseBackgroundTiles();
2436 }
2437 
2438 
2439 ////////////////////////////////////////
2440 
2441 
2442 template<typename ChildT>
2443 template<typename NodeT>
2444 inline NodeT*
2445 RootNode<ChildT>::stealNode(const Coord& xyz, const ValueType& value, bool state)
2446 {
2447  if ((NodeT::LEVEL == ChildT::LEVEL && !(hboost::is_same<NodeT, ChildT>::value)) ||
2448  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
2450  MapIter iter = this->findCoord(xyz);
2451  if (iter == mTable.end() || isTile(iter)) return nullptr;
2453  ? reinterpret_cast<NodeT*>(&stealChild(iter, Tile(value, state)))
2454  : getChild(iter).template stealNode<NodeT>(xyz, value, state);
2456 }
2457 
2458 
2459 ////////////////////////////////////////
2460 
2461 
2462 template<typename ChildT>
2463 inline void
2465 {
2466  if (leaf == nullptr) return;
2467  ChildT* child = nullptr;
2468  const Coord& xyz = leaf->origin();
2469  MapIter iter = this->findCoord(xyz);
2470  if (iter == mTable.end()) {
2471  if (ChildT::LEVEL>0) {
2472  child = new ChildT(xyz, mBackground, false);
2473  } else {
2474  child = reinterpret_cast<ChildT*>(leaf);
2475  }
2476  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2477  } else if (isChild(iter)) {
2478  if (ChildT::LEVEL>0) {
2479  child = &getChild(iter);
2480  } else {
2481  child = reinterpret_cast<ChildT*>(leaf);
2482  setChild(iter, *child);//this also deletes the existing child node
2483  }
2484  } else {//tile
2485  if (ChildT::LEVEL>0) {
2486  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2487  } else {
2488  child = reinterpret_cast<ChildT*>(leaf);
2489  }
2490  setChild(iter, *child);
2491  }
2492  child->addLeaf(leaf);
2493 }
2494 
2495 
2496 template<typename ChildT>
2497 template<typename AccessorT>
2498 inline void
2500 {
2501  if (leaf == nullptr) return;
2502  ChildT* child = nullptr;
2503  const Coord& xyz = leaf->origin();
2504  MapIter iter = this->findCoord(xyz);
2505  if (iter == mTable.end()) {
2506  if (ChildT::LEVEL>0) {
2507  child = new ChildT(xyz, mBackground, false);
2508  } else {
2509  child = reinterpret_cast<ChildT*>(leaf);
2510  }
2511  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2512  } else if (isChild(iter)) {
2513  if (ChildT::LEVEL>0) {
2514  child = &getChild(iter);
2515  } else {
2516  child = reinterpret_cast<ChildT*>(leaf);
2517  setChild(iter, *child);//this also deletes the existing child node
2518  }
2519  } else {//tile
2520  if (ChildT::LEVEL>0) {
2521  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2522  } else {
2523  child = reinterpret_cast<ChildT*>(leaf);
2524  }
2525  setChild(iter, *child);
2526  }
2527  acc.insert(xyz, child);
2528  child->addLeafAndCache(leaf, acc);
2529 }
2530 
2531 template<typename ChildT>
2532 inline void
2533 RootNode<ChildT>::addTile(const Coord& xyz, const ValueType& value, bool state)
2534 {
2535  MapIter iter = this->findCoord(xyz);
2536  if (iter == mTable.end()) {//background
2537  mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2538  } else {//child or tile
2539  setTile(iter, Tile(value, state));//this also deletes the existing child node
2540  }
2541 }
2542 
2543 template<typename ChildT>
2544 inline void
2546  const ValueType& value, bool state)
2547 {
2548  if (LEVEL >= level) {
2549  MapIter iter = this->findCoord(xyz);
2550  if (iter == mTable.end()) {//background
2551  if (LEVEL > level) {
2552  ChildT* child = new ChildT(xyz, mBackground, false);
2553  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2554  child->addTile(level, xyz, value, state);
2555  } else {
2556  mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2557  }
2558  } else if (isChild(iter)) {//child
2559  if (LEVEL > level) {
2560  getChild(iter).addTile(level, xyz, value, state);
2561  } else {
2562  setTile(iter, Tile(value, state));//this also deletes the existing child node
2563  }
2564  } else {//tile
2565  if (LEVEL > level) {
2566  ChildT* child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2567  setChild(iter, *child);
2568  child->addTile(level, xyz, value, state);
2569  } else {
2570  setTile(iter, Tile(value, state));
2571  }
2572  }
2573  }
2574 }
2575 
2576 
2577 template<typename ChildT>
2578 template<typename AccessorT>
2579 inline void
2580 RootNode<ChildT>::addTileAndCache(Index level, const Coord& xyz, const ValueType& value,
2581  bool state, AccessorT& acc)
2582 {
2583  if (LEVEL >= level) {
2584  MapIter iter = this->findCoord(xyz);
2585  if (iter == mTable.end()) {//background
2586  if (LEVEL > level) {
2587  ChildT* child = new ChildT(xyz, mBackground, false);
2588  acc.insert(xyz, child);
2589  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2590  child->addTileAndCache(level, xyz, value, state, acc);
2591  } else {
2592  mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2593  }
2594  } else if (isChild(iter)) {//child
2595  if (LEVEL > level) {
2596  ChildT* child = &getChild(iter);
2597  acc.insert(xyz, child);
2598  child->addTileAndCache(level, xyz, value, state, acc);
2599  } else {
2600  setTile(iter, Tile(value, state));//this also deletes the existing child node
2601  }
2602  } else {//tile
2603  if (LEVEL > level) {
2604  ChildT* child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2605  acc.insert(xyz, child);
2606  setChild(iter, *child);
2607  child->addTileAndCache(level, xyz, value, state, acc);
2608  } else {
2609  setTile(iter, Tile(value, state));
2610  }
2611  }
2612  }
2613 }
2614 
2615 
2616 ////////////////////////////////////////
2617 
2618 
2619 template<typename ChildT>
2620 inline typename ChildT::LeafNodeType*
2622 {
2623  ChildT* child = nullptr;
2624  MapIter iter = this->findCoord(xyz);
2625  if (iter == mTable.end()) {
2626  child = new ChildT(xyz, mBackground, false);
2627  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2628  } else if (isChild(iter)) {
2629  child = &getChild(iter);
2630  } else {
2631  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2632  setChild(iter, *child);
2633  }
2634  return child->touchLeaf(xyz);
2635 }
2636 
2637 
2638 template<typename ChildT>
2639 template<typename AccessorT>
2640 inline typename ChildT::LeafNodeType*
2641 RootNode<ChildT>::touchLeafAndCache(const Coord& xyz, AccessorT& acc)
2642 {
2643  ChildT* child = nullptr;
2644  MapIter iter = this->findCoord(xyz);
2645  if (iter == mTable.end()) {
2646  child = new ChildT(xyz, mBackground, false);
2647  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2648  } else if (isChild(iter)) {
2649  child = &getChild(iter);
2650  } else {
2651  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2652  setChild(iter, *child);
2653  }
2654  acc.insert(xyz, child);
2655  return child->touchLeafAndCache(xyz, acc);
2656 }
2657 
2658 
2659 ////////////////////////////////////////
2660 
2661 
2662 template<typename ChildT>
2663 template<typename NodeT>
2664 inline NodeT*
2666 {
2667  if ((NodeT::LEVEL == ChildT::LEVEL && !(hboost::is_same<NodeT, ChildT>::value)) ||
2668  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
2670  MapIter iter = this->findCoord(xyz);
2671  if (iter == mTable.end() || isTile(iter)) return nullptr;
2672  ChildT* child = &getChild(iter);
2674  ? reinterpret_cast<NodeT*>(child)
2675  : child->template probeNode<NodeT>(xyz);
2677 }
2678 
2679 
2680 template<typename ChildT>
2681 template<typename NodeT>
2682 inline const NodeT*
2683 RootNode<ChildT>::probeConstNode(const Coord& xyz) const
2684 {
2685  if ((NodeT::LEVEL == ChildT::LEVEL && !(hboost::is_same<NodeT, ChildT>::value)) ||
2686  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
2688  MapCIter iter = this->findCoord(xyz);
2689  if (iter == mTable.end() || isTile(iter)) return nullptr;
2690  const ChildT* child = &getChild(iter);
2692  ? reinterpret_cast<const NodeT*>(child)
2693  : child->template probeConstNode<NodeT>(xyz);
2695 }
2696 
2697 
2698 template<typename ChildT>
2699 inline typename ChildT::LeafNodeType*
2701 {
2702  return this->template probeNode<LeafNodeType>(xyz);
2703 }
2704 
2705 
2706 template<typename ChildT>
2707 inline const typename ChildT::LeafNodeType*
2708 RootNode<ChildT>::probeConstLeaf(const Coord& xyz) const
2709 {
2710  return this->template probeConstNode<LeafNodeType>(xyz);
2711 }
2712 
2713 
2714 template<typename ChildT>
2715 template<typename AccessorT>
2716 inline typename ChildT::LeafNodeType*
2717 RootNode<ChildT>::probeLeafAndCache(const Coord& xyz, AccessorT& acc)
2718 {
2719  return this->template probeNodeAndCache<LeafNodeType>(xyz, acc);
2720 }
2721 
2722 
2723 template<typename ChildT>
2724 template<typename AccessorT>
2725 inline const typename ChildT::LeafNodeType*
2726 RootNode<ChildT>::probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const
2727 {
2728  return this->template probeConstNodeAndCache<LeafNodeType>(xyz, acc);
2729 }
2730 
2731 
2732 template<typename ChildT>
2733 template<typename AccessorT>
2734 inline const typename ChildT::LeafNodeType*
2735 RootNode<ChildT>::probeLeafAndCache(const Coord& xyz, AccessorT& acc) const
2736 {
2737  return this->probeConstLeafAndCache(xyz, acc);
2738 }
2739 
2740 
2741 template<typename ChildT>
2742 template<typename NodeT, typename AccessorT>
2743 inline NodeT*
2744 RootNode<ChildT>::probeNodeAndCache(const Coord& xyz, AccessorT& acc)
2745 {
2746  if ((NodeT::LEVEL == ChildT::LEVEL && !(hboost::is_same<NodeT, ChildT>::value)) ||
2747  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
2749  MapIter iter = this->findCoord(xyz);
2750  if (iter == mTable.end() || isTile(iter)) return nullptr;
2751  ChildT* child = &getChild(iter);
2752  acc.insert(xyz, child);
2754  ? reinterpret_cast<NodeT*>(child)
2755  : child->template probeNodeAndCache<NodeT>(xyz, acc);
2757 }
2758 
2759 
2760 template<typename ChildT>
2761 template<typename NodeT,typename AccessorT>
2762 inline const NodeT*
2763 RootNode<ChildT>::probeConstNodeAndCache(const Coord& xyz, AccessorT& acc) const
2764 {
2765  if ((NodeT::LEVEL == ChildT::LEVEL && !(hboost::is_same<NodeT, ChildT>::value)) ||
2766  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
2768  MapCIter iter = this->findCoord(xyz);
2769  if (iter == mTable.end() || isTile(iter)) return nullptr;
2770  const ChildT* child = &getChild(iter);
2771  acc.insert(xyz, child);
2773  ? reinterpret_cast<const NodeT*>(child)
2774  : child->template probeConstNodeAndCache<NodeT>(xyz, acc);
2776 }
2777 
2778 
2779 ////////////////////////////////////////
2780 
2781 template<typename ChildT>
2782 template<typename ArrayT>
2783 inline void
2785 {
2786  typedef typename ArrayT::value_type NodePtr;
2787  HBOOST_STATIC_ASSERT(hboost::is_pointer<NodePtr>::value);
2788  typedef typename hboost::remove_pointer<NodePtr>::type NodeType;
2789  typedef typename hboost::remove_const<NodeType>::type NonConstNodeType;
2791  HBOOST_STATIC_ASSERT(result::value);
2792  typedef typename hboost::mpl::if_<hboost::is_const<NodeType>,
2793  const ChildT, ChildT>::type ArrayChildT;
2794 
2795  for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2796  if (ChildT* child = iter->second.child) {
2799  array.push_back(reinterpret_cast<NodePtr>(iter->second.child));
2800  } else {
2801  child->getNodes(array);//descent
2802  }
2804  }
2805  }
2806 }
2807 
2808 template<typename ChildT>
2809 template<typename ArrayT>
2810 inline void
2811 RootNode<ChildT>::getNodes(ArrayT& array) const
2812 {
2813  typedef typename ArrayT::value_type NodePtr;
2814  HBOOST_STATIC_ASSERT(hboost::is_pointer<NodePtr>::value);
2815  typedef typename hboost::remove_pointer<NodePtr>::type NodeType;
2816  HBOOST_STATIC_ASSERT(hboost::is_const<NodeType>::value);
2817  typedef typename hboost::remove_const<NodeType>::type NonConstNodeType;
2819  HBOOST_STATIC_ASSERT(result::value);
2820 
2821  for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2822  if (const ChildNodeType *child = iter->second.child) {
2825  array.push_back(reinterpret_cast<NodePtr>(iter->second.child));
2826  } else {
2827  child->getNodes(array);//descent
2828  }
2830  }
2831  }
2832 }
2833 
2834 ////////////////////////////////////////
2835 
2836 template<typename ChildT>
2837 template<typename ArrayT>
2838 inline void
2839 RootNode<ChildT>::stealNodes(ArrayT& array, const ValueType& value, bool state)
2840 {
2841  typedef typename ArrayT::value_type NodePtr;
2842  HBOOST_STATIC_ASSERT(hboost::is_pointer<NodePtr>::value);
2843  typedef typename hboost::remove_pointer<NodePtr>::type NodeType;
2844  typedef typename hboost::remove_const<NodeType>::type NonConstNodeType;
2846  HBOOST_STATIC_ASSERT(result::value);
2847  typedef typename hboost::mpl::if_<hboost::is_const<NodeType>,
2848  const ChildT, ChildT>::type ArrayChildT;
2849 
2850  for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2851  if (ChildT* child = iter->second.child) {
2854  array.push_back(reinterpret_cast<NodePtr>(&stealChild(iter, Tile(value, state))));
2855  } else {
2856  child->stealNodes(array, value, state);//descent
2857  }
2859  }
2860  }
2861 }
2862 
2863 
2864 ////////////////////////////////////////
2865 
2866 
2867 template<typename ChildT>
2868 inline void
2870 {
2871  // These is little point in multi-threaded over the root table since
2872  // each tile spans a huge index space (by default 4096^3) and hence we
2873  // expect few if any at all. In fact, you're very likeky to run out
2874  // of memory if this method is called on a tree with root-level
2875  // active tiles!
2876  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2877  if (this->isTileOff(i)) continue;
2878  ChildT* child = i->second.child;
2879  if (child == nullptr) {
2880  child = new ChildT(i->first, this->getTile(i).value, true);
2881  i->second.child = child;
2882  }
2883  child->voxelizeActiveTiles(threaded);
2884  }
2885 }
2886 
2887 
2888 ////////////////////////////////////////
2889 
2890 
2891 template<typename ChildT>
2892 template<MergePolicy Policy>
2893 inline void
2895 {
2897 
2898  switch (Policy) {
2899 
2900  default:
2901  case MERGE_ACTIVE_STATES:
2902  for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2903  MapIter j = mTable.find(i->first);
2904  if (other.isChild(i)) {
2905  if (j == mTable.end()) { // insert other node's child
2906  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
2907  child.resetBackground(other.mBackground, mBackground);
2908  mTable[i->first] = NodeStruct(child);
2909  } else if (isTile(j)) {
2910  if (isTileOff(j)) { // replace inactive tile with other node's child
2911  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
2912  child.resetBackground(other.mBackground, mBackground);
2913  setChild(j, child);
2914  }
2915  } else { // merge both child nodes
2916  getChild(j).template merge<MERGE_ACTIVE_STATES>(getChild(i),
2917  other.mBackground, mBackground);
2918  }
2919  } else if (other.isTileOn(i)) {
2920  if (j == mTable.end()) { // insert other node's active tile
2921  mTable[i->first] = i->second;
2922  } else if (!isTileOn(j)) {
2923  // Replace anything except an active tile with the other node's active tile.
2924  setTile(j, Tile(other.getTile(i).value, true));
2925  }
2926  }
2927  }
2928  break;
2929 
2930  case MERGE_NODES:
2931  for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2932  MapIter j = mTable.find(i->first);
2933  if (other.isChild(i)) {
2934  if (j == mTable.end()) { // insert other node's child
2935  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
2936  child.resetBackground(other.mBackground, mBackground);
2937  mTable[i->first] = NodeStruct(child);
2938  } else if (isTile(j)) { // replace tile with other node's child
2939  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
2940  child.resetBackground(other.mBackground, mBackground);
2941  setChild(j, child);
2942  } else { // merge both child nodes
2943  getChild(j).template merge<MERGE_NODES>(
2944  getChild(i), other.mBackground, mBackground);
2945  }
2946  }
2947  }
2948  break;
2949 
2951  for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2952  MapIter j = mTable.find(i->first);
2953  if (other.isChild(i)) {
2954  if (j == mTable.end()) {
2955  // Steal and insert the other node's child.
2956  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
2957  child.resetBackground(other.mBackground, mBackground);
2958  mTable[i->first] = NodeStruct(child);
2959  } else if (isTile(j)) {
2960  // Replace this node's tile with the other node's child.
2961  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
2962  child.resetBackground(other.mBackground, mBackground);
2963  const Tile tile = getTile(j);
2964  setChild(j, child);
2965  if (tile.active) {
2966  // Merge the other node's child with this node's active tile.
2967  child.template merge<MERGE_ACTIVE_STATES_AND_NODES>(
2968  tile.value, tile.active);
2969  }
2970  } else /*if (isChild(j))*/ {
2971  // Merge the other node's child into this node's child.
2972  getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(getChild(i),
2973  other.mBackground, mBackground);
2974  }
2975  } else if (other.isTileOn(i)) {
2976  if (j == mTable.end()) {
2977  // Insert a copy of the other node's active tile.
2978  mTable[i->first] = i->second;
2979  } else if (isTileOff(j)) {
2980  // Replace this node's inactive tile with a copy of the other's active tile.
2981  setTile(j, Tile(other.getTile(i).value, true));
2982  } else if (isChild(j)) {
2983  // Merge the other node's active tile into this node's child.
2984  const Tile& tile = getTile(i);
2985  getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(
2986  tile.value, tile.active);
2987  }
2988  } // else if (other.isTileOff(i)) {} // ignore the other node's inactive tiles
2989  }
2990  break;
2991  }
2992 
2993  // Empty the other tree so as not to leave it in a partially cannibalized state.
2994  other.clear();
2995 
2997 }
2998 
2999 
3000 ////////////////////////////////////////
3001 
3002 
3003 template<typename ChildT>
3004 template<typename OtherChildType>
3005 inline void
3007 {
3008  typedef RootNode<OtherChildType> OtherRootT;
3009  typedef typename OtherRootT::MapCIter OtherCIterT;
3010 
3011  enforceSameConfiguration(other);
3012 
3013  for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3014  MapIter j = mTable.find(i->first);
3015  if (other.isChild(i)) {
3016  if (j == mTable.end()) { // create child branch with identical topology
3017  mTable[i->first] = NodeStruct(
3018  *(new ChildT(other.getChild(i), mBackground, TopologyCopy())));
3019  } else if (this->isChild(j)) { // union with child branch
3020  this->getChild(j).topologyUnion(other.getChild(i));
3021  } else {// this is a tile so replace it with a child branch with identical topology
3022  ChildT* child = new ChildT(
3023  other.getChild(i), this->getTile(j).value, TopologyCopy());
3024  if (this->isTileOn(j)) child->setValuesOn();//this is an active tile
3025  this->setChild(j, *child);
3026  }
3027  } else if (other.isTileOn(i)) { // other is an active tile
3028  if (j == mTable.end()) { // insert an active tile
3029  mTable[i->first] = NodeStruct(Tile(mBackground, true));
3030  } else if (this->isChild(j)) {
3031  this->getChild(j).setValuesOn();
3032  } else if (this->isTileOff(j)) {
3033  this->setTile(j, Tile(this->getTile(j).value, true));
3034  }
3035  }
3036  }
3037 }
3038 
3039 template<typename ChildT>
3040 template<typename OtherChildType>
3041 inline void
3043 {
3044  typedef RootNode<OtherChildType> OtherRootT;
3045  typedef typename OtherRootT::MapCIter OtherCIterT;
3046 
3047  enforceSameConfiguration(other);
3048 
3049  std::set<Coord> tmp;//keys to erase
3050  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
3051  OtherCIterT j = other.mTable.find(i->first);
3052  if (this->isChild(i)) {
3053  if (j == other.mTable.end() || other.isTileOff(j)) {
3054  tmp.insert(i->first);//delete child branch
3055  } else if (other.isChild(j)) { // intersect with child branch
3056  this->getChild(i).topologyIntersection(other.getChild(j), mBackground);
3057  }
3058  } else if (this->isTileOn(i)) {
3059  if (j == other.mTable.end() || other.isTileOff(j)) {
3060  this->setTile(i, Tile(this->getTile(i).value, false));//turn inactive
3061  } else if (other.isChild(j)) { //replace with a child branch with identical topology
3062  ChildT* child =
3063  new ChildT(other.getChild(j), this->getTile(i).value, TopologyCopy());
3064  this->setChild(i, *child);
3065  }
3066  }
3067  }
3068  for (std::set<Coord>::iterator i = tmp.begin(), e = tmp.end(); i != e; ++i) {
3069  MapIter it = this->findCoord(*i);
3070  setTile(it, Tile()); // delete any existing child node first
3071  mTable.erase(it);
3072  }
3073 }
3074 
3075 template<typename ChildT>
3076 template<typename OtherChildType>
3077 inline void
3079 {
3080  typedef RootNode<OtherChildType> OtherRootT;
3081  typedef typename OtherRootT::MapCIter OtherCIterT;
3082 
3083  enforceSameConfiguration(other);
3084 
3085  for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3086  MapIter j = mTable.find(i->first);
3087  if (other.isChild(i)) {
3088  if (j == mTable.end() || this->isTileOff(j)) {
3089  //do nothing
3090  } else if (this->isChild(j)) { // difference with child branch
3091  this->getChild(j).topologyDifference(other.getChild(i), mBackground);
3092  } else if (this->isTileOn(j)) {
3093  // this is an active tile so create a child node and descent
3094  ChildT* child = new ChildT(j->first, this->getTile(j).value, true);
3095  child->topologyDifference(other.getChild(i), mBackground);
3096  this->setChild(j, *child);
3097  }
3098  } else if (other.isTileOn(i)) { // other is an active tile
3099  if (j == mTable.end() || this->isTileOff(j)) {
3100  // do nothing
3101  } else if (this->isChild(j)) {
3102  setTile(j, Tile()); // delete any existing child node first
3103  mTable.erase(j);
3104  } else if (this->isTileOn(j)) {
3105  this->setTile(j, Tile(this->getTile(j).value, false));
3106  }
3107  }
3108  }
3109 }
3110 
3111 ////////////////////////////////////////
3112 
3113 
3114 template<typename ChildT>
3115 template<typename CombineOp>
3116 inline void
3117 RootNode<ChildT>::combine(RootNode& other, CombineOp& op, bool prune)
3118 {
3120 
3121  CoordSet keys;
3122  this->insertKeys(keys);
3123  other.insertKeys(keys);
3124 
3125  for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3126  MapIter iter = findOrAddCoord(*i), otherIter = other.findOrAddCoord(*i);
3127  if (isTile(iter) && isTile(otherIter)) {
3128  // Both this node and the other node have constant values (tiles).
3129  // Combine the two values and store the result as this node's new tile value.
3130  op(args.setARef(getTile(iter).value)
3131  .setAIsActive(isTileOn(iter))
3132  .setBRef(getTile(otherIter).value)
3133  .setBIsActive(isTileOn(otherIter)));
3134  setTile(iter, Tile(args.result(), args.resultIsActive()));
3135 
3136  } else if (isChild(iter) && isTile(otherIter)) {
3137  // Combine this node's child with the other node's constant value.
3138  ChildT& child = getChild(iter);
3139  child.combine(getTile(otherIter).value, isTileOn(otherIter), op);
3140 
3141  } else if (isTile(iter) && isChild(otherIter)) {
3142  // Combine this node's constant value with the other node's child,
3143  // but use a new functor in which the A and B values are swapped,
3144  // since the constant value is the A value, not the B value.
3146  ChildT& child = getChild(otherIter);
3147  child.combine(getTile(iter).value, isTileOn(iter), swappedOp);
3148 
3149  // Steal the other node's child.
3150  setChild(iter, stealChild(otherIter, Tile()));
3151 
3152  } else /*if (isChild(iter) && isChild(otherIter))*/ {
3153  // Combine this node's child with the other node's child.
3154  ChildT &child = getChild(iter), &otherChild = getChild(otherIter);
3155  child.combine(otherChild, op);
3156  }
3157  if (prune && isChild(iter)) getChild(iter).prune();
3158  }
3159 
3160  // Combine background values.
3161  op(args.setARef(mBackground).setBRef(other.mBackground));
3162  mBackground = args.result();
3163 
3164  // Empty the other tree so as not to leave it in a partially cannibalized state.
3165  other.clear();
3166 }
3167 
3168 
3169 ////////////////////////////////////////
3170 
3171 
3172 // This helper class is a friend of RootNode and is needed so that combine2
3173 // can be specialized for compatible and incompatible pairs of RootNode types.
3174 template<typename CombineOp, typename RootT, typename OtherRootT, bool Compatible = false>
3175 struct RootNodeCombineHelper
3176 {
3177  static inline void combine2(RootT& self, const RootT&, const OtherRootT& other1,
3178  CombineOp&, bool)
3179  {
3180  // If the two root nodes have different configurations or incompatible ValueTypes,
3181  // throw an exception.
3182  self.enforceSameConfiguration(other1);
3183  self.enforceCompatibleValueTypes(other1);
3184  // One of the above two tests should throw, so we should never get here:
3185  std::ostringstream ostr;
3186  ostr << "cannot combine a " << typeid(OtherRootT).name()
3187  << " into a " << typeid(RootT).name();
3188  OPENVDB_THROW(TypeError, ostr.str());
3189  }
3190 };
3191 
3192 // Specialization for root nodes of compatible types
3193 template<typename CombineOp, typename RootT, typename OtherRootT>
3194 struct RootNodeCombineHelper<CombineOp, RootT, OtherRootT, /*Compatible=*/true>
3195 {
3196  static inline void combine2(RootT& self, const RootT& other0, const OtherRootT& other1,
3197  CombineOp& op, bool prune)
3198  {
3199  self.doCombine2(other0, other1, op, prune);
3200  }
3201 };
3202 
3203 
3204 template<typename ChildT>
3205 template<typename CombineOp, typename OtherRootNode>
3206 inline void
3207 RootNode<ChildT>::combine2(const RootNode& other0, const OtherRootNode& other1,
3208  CombineOp& op, bool prune)
3209 {
3210  typedef typename OtherRootNode::ValueType OtherValueType;
3211  static const bool compatible = (SameConfiguration<OtherRootNode>::value
3212  && CanConvertType</*from=*/OtherValueType, /*to=*/ValueType>::value);
3214  *this, other0, other1, op, prune);
3215 }
3216 
3217 
3218 template<typename ChildT>
3219 template<typename CombineOp, typename OtherRootNode>
3220 inline void
3221 RootNode<ChildT>::doCombine2(const RootNode& other0, const OtherRootNode& other1,
3222  CombineOp& op, bool prune)
3223 {
3224  enforceSameConfiguration(other1);
3225 
3226  typedef typename OtherRootNode::ValueType OtherValueT;
3227  typedef typename OtherRootNode::Tile OtherTileT;
3228  typedef typename OtherRootNode::NodeStruct OtherNodeStructT;
3229  typedef typename OtherRootNode::MapCIter OtherMapCIterT;
3230 
3232 
3233  CoordSet keys;
3234  other0.insertKeys(keys);
3235  other1.insertKeys(keys);
3236 
3237  const NodeStruct bg0(Tile(other0.mBackground, /*active=*/false));
3238  const OtherNodeStructT bg1(OtherTileT(other1.mBackground, /*active=*/false));
3239 
3240  for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3241  MapIter thisIter = this->findOrAddCoord(*i);
3242  MapCIter iter0 = other0.findKey(*i);
3243  OtherMapCIterT iter1 = other1.findKey(*i);
3244  const NodeStruct& ns0 = (iter0 != other0.mTable.end()) ? iter0->second : bg0;
3245  const OtherNodeStructT& ns1 = (iter1 != other1.mTable.end()) ? iter1->second : bg1;
3246  if (ns0.isTile() && ns1.isTile()) {
3247  // Both input nodes have constant values (tiles).
3248  // Combine the two values and add a new tile to this node with the result.
3249  op(args.setARef(ns0.tile.value)
3250  .setAIsActive(ns0.isTileOn())
3251  .setBRef(ns1.tile.value)
3252  .setBIsActive(ns1.isTileOn()));
3253  setTile(thisIter, Tile(args.result(), args.resultIsActive()));
3254  } else {
3255  if (!isChild(thisIter)) {
3256  // Add a new child with the same coordinates, etc. as the other node's child.
3257  const Coord& childOrigin =
3258  ns0.isChild() ? ns0.child->origin() : ns1.child->origin();
3259  setChild(thisIter, *(new ChildT(childOrigin, getTile(thisIter).value)));
3260  }
3261  ChildT& child = getChild(thisIter);
3262 
3263  if (ns0.isTile()) {
3264  // Combine node1's child with node0's constant value
3265  // and write the result into this node's child.
3266  child.combine2(ns0.tile.value, *ns1.child, ns0.isTileOn(), op);
3267  } else if (ns1.isTile()) {
3268  // Combine node0's child with node1's constant value
3269  // and write the result into this node's child.
3270  child.combine2(*ns0.child, ns1.tile.value, ns1.isTileOn(), op);
3271  } else {
3272  // Combine node0's child with node1's child
3273  // and write the result into this node's child.
3274  child.combine2(*ns0.child, *ns1.child, op);
3275  }
3276  }
3277  if (prune && isChild(thisIter)) getChild(thisIter).prune();
3278  }
3279 
3280  // Combine background values.
3281  op(args.setARef(other0.mBackground).setBRef(other1.mBackground));
3282  mBackground = args.result();
3283 }
3284 
3285 
3286 ////////////////////////////////////////
3287 
3288 
3289 template<typename ChildT>
3290 template<typename BBoxOp>
3291 inline void
3293 {
3294  const bool descent = op.template descent<LEVEL>();
3295  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
3296  if (this->isTileOff(i)) continue;
3297  if (this->isChild(i) && descent) {
3298  this->getChild(i).visitActiveBBox(op);
3299  } else {
3300 #ifdef _MSC_VER
3301  op.operator()<LEVEL>(CoordBBox::createCube(i->first, ChildT::DIM));
3302 #else
3303  op.template operator()<LEVEL>(CoordBBox::createCube(i->first, ChildT::DIM));
3304 #endif
3305  }
3306  }
3307 }
3308 
3309 
3310 template<typename ChildT>
3311 template<typename VisitorOp>
3312 inline void
3314 {
3315  doVisit<RootNode, VisitorOp, ChildAllIter>(*this, op);
3316 }
3317 
3318 
3319 template<typename ChildT>
3320 template<typename VisitorOp>
3321 inline void
3322 RootNode<ChildT>::visit(VisitorOp& op) const
3323 {
3324  doVisit<const RootNode, VisitorOp, ChildAllCIter>(*this, op);
3325 }
3326 
3327 
3328 template<typename ChildT>
3329 template<typename RootNodeT, typename VisitorOp, typename ChildAllIterT>
3330 inline void
3331 RootNode<ChildT>::doVisit(RootNodeT& self, VisitorOp& op)
3332 {
3333  typename RootNodeT::ValueType val;
3334  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
3335  if (op(iter)) continue;
3336  if (typename ChildAllIterT::ChildNodeType* child = iter.probeChild(val)) {
3337  child->visit(op);
3338  }
3339  }
3340 }
3341 
3342 
3343 ////////////////////////////////////////
3344 
3345 
3346 template<typename ChildT>
3347 template<typename OtherRootNodeType, typename VisitorOp>
3348 inline void
3349 RootNode<ChildT>::visit2(OtherRootNodeType& other, VisitorOp& op)
3350 {
3351  doVisit2<RootNode, OtherRootNodeType, VisitorOp, ChildAllIter,
3352  typename OtherRootNodeType::ChildAllIter>(*this, other, op);
3353 }
3354 
3355 
3356 template<typename ChildT>
3357 template<typename OtherRootNodeType, typename VisitorOp>
3358 inline void
3359 RootNode<ChildT>::visit2(OtherRootNodeType& other, VisitorOp& op) const
3360 {
3361  doVisit2<const RootNode, OtherRootNodeType, VisitorOp, ChildAllCIter,
3362  typename OtherRootNodeType::ChildAllCIter>(*this, other, op);
3363 }
3364 
3365 
3366 template<typename ChildT>
3367 template<
3368  typename RootNodeT,
3369  typename OtherRootNodeT,
3370  typename VisitorOp,
3371  typename ChildAllIterT,
3372  typename OtherChildAllIterT>
3373 inline void
3374 RootNode<ChildT>::doVisit2(RootNodeT& self, OtherRootNodeT& other, VisitorOp& op)
3375 {
3376  enforceSameConfiguration(other);
3377 
3378  typename RootNodeT::ValueType val;
3379  typename OtherRootNodeT::ValueType otherVal;
3380 
3381  // The two nodes are required to have corresponding table entries,
3382  // but since that might require background tiles to be added to one or both,
3383  // and the nodes might be const, we operate on shallow copies of the nodes instead.
3384  RootNodeT copyOfSelf(self.mBackground);
3385  copyOfSelf.mTable = self.mTable;
3386  OtherRootNodeT copyOfOther(other.mBackground);
3387  copyOfOther.mTable = other.mTable;
3388 
3389  // Add background tiles to both nodes as needed.
3390  CoordSet keys;
3391  self.insertKeys(keys);
3392  other.insertKeys(keys);
3393  for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3394  copyOfSelf.findOrAddCoord(*i);
3395  copyOfOther.findOrAddCoord(*i);
3396  }
3397 
3398  ChildAllIterT iter = copyOfSelf.beginChildAll();
3399  OtherChildAllIterT otherIter = copyOfOther.beginChildAll();
3400 
3401  for ( ; iter && otherIter; ++iter, ++otherIter)
3402  {
3403  const size_t skipBranch = static_cast<size_t>(op(iter, otherIter));
3404 
3405  typename ChildAllIterT::ChildNodeType* child =
3406  (skipBranch & 1U) ? nullptr : iter.probeChild(val);
3407  typename OtherChildAllIterT::ChildNodeType* otherChild =
3408  (skipBranch & 2U) ? nullptr : otherIter.probeChild(otherVal);
3409 
3410  if (child != nullptr && otherChild != nullptr) {
3411  child->visit2Node(*otherChild, op);
3412  } else if (child != nullptr) {
3413  child->visit2(otherIter, op);
3414  } else if (otherChild != nullptr) {
3415  otherChild->visit2(iter, op, /*otherIsLHS=*/true);
3416  }
3417  }
3418  // Remove any background tiles that were added above,
3419  // as well as any that were created by the visitors.
3420  copyOfSelf.eraseBackgroundTiles();
3421  copyOfOther.eraseBackgroundTiles();
3422 
3423  // If either input node is non-const, replace its table with
3424  // the (possibly modified) copy.
3425  self.resetTable(copyOfSelf.mTable);
3426  other.resetTable(copyOfOther.mTable);
3427 }
3428 
3429 } // namespace tree
3430 } // namespace OPENVDB_VERSION_NAME
3431 } // namespace openvdb
3432 
3433 #endif // OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
3434 
3435 // Copyright (c) 2012-2017 DreamWorks Animation LLC
3436 // All rights reserved. This software is distributed under the
3437 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
const AValueType & result() const
Get the output value.
Definition: Types.h:416
Vec2< T > minComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise minimum of the two vectors.
Definition: Vec2.h:553
static void combine2(RootT &self, const RootT &other0, const OtherRootT &other1, CombineOp &op, bool prune)
Definition: RootNode.h:3196
void setValueOffAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: RootNode.h:1814
static void copyWithValueConversion(RootT &self, const OtherRootT &other)
Definition: RootNode.h:1137
Color4< T > operator*(S a, const Color4< T > &v)
Definition: ImathColor.h:728
cvex test(vector P=0;int unbound=3;export float s=0;export vector Cf=0;)
Definition: test.vfl:11
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: Types.h:371
LeafNodeType * touchLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, create one that preserves the values and active states of all voxels.
Definition: RootNode.h:2621
Coord getMaxIndex() const
Return the largest index of the current tree.
Definition: RootNode.h:1340
bool empty() const
Return true if this node's table is either empty or contains only background tiles.
Definition: RootNode.h:477
ChildIter< const RootNode, MapCIter, ChildOnPred, const ChildType > ChildOnCIter
Definition: RootNode.h:397
ValueIter< const RootNode, MapCIter, ValueOnPred, const ValueType > ValueOnCIter
Definition: RootNode.h:404
LeafNodeType * probeLeafAndCache(const Coord &xyz, AccessorT &acc)
Same as probeLeaf() but, if necessary, update the given accessor with pointers to the nodes along the...
void topologyIntersection(const RootNode< OtherChildType > &other)
Intersects this tree's set of active values with the active values of the other tree, whose ValueType may be different.
Definition: RootNode.h:3042
bool isExactlyEqual(const T0 &a, const T1 &b)
Return true if a is exactly equal to b.
Definition: Math.h:407
void setBackground(const ValueType &value, bool updateChildNodes)
Change inactive tiles or voxels with a value equal to +/- the old background to the specified value (...
Definition: RootNode.h:1210
int getValueDepthAndCache(const Coord &xyz, AccessorT &) const
Definition: RootNode.h:1718
hboost::mpl::push_back< SubtreeT, HeadT >::type Type
Definition: RootNode.h:1020
const hboost::disable_if_c< VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:128
RootNode & operator=(const RootNode &other)
Copy a root node of the same type as this node.
Definition: RootNode.h:1175
hboost::mpl::vector< typename HeadT::ChildNodeType, HeadT >::type Type
Definition: RootNode.h:1026
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:116
void skip(T &in, int n)
Definition: ImfXdr.h:885
bool probeValue(const Coord &xyz, ValueType &value) const
Definition: RootNode.h:2047
void getIndexRange(CoordBBox &bbox) const
Return the current index range. Both min and max are inclusive.
Definition: RootNode.h:1348
const GLdouble * v
Definition: glcorearb.h:836
const ValueType & getValueAndCache(const Coord &xyz, AccessorT &) const
bool hasSameTopology(const RootNode< OtherChildType > &other) const
Return true if the given tree has the same node and active value topology as this tree (but possibly ...
Definition: RootNode.h:1361
png_infop png_color_16p * background
Definition: png.h:2326
GLdouble GLdouble GLdouble z
Definition: glcorearb.h:847
const ValueType & background() const
Return this node's background value.
Definition: RootNode.h:459
GLint level
Definition: glcorearb.h:107
ValueConverter<T>::Type is the type of a RootNode having the same child hierarchy as this node but a ...
Definition: RootNode.h:92
ChildIter< RootNode, MapIter, ChildOnPred, ChildType > ChildOnIter
Definition: RootNode.h:396
void merge(RootNode &other)
Efficiently merge another tree into this tree using one of several schemes.
Definition: RootNode.h:2894
Index64 memUsage() const
Return the total amount of memory in bytes occupied by this node and its children.
Definition: RootNode.h:1467
ValueIter< RootNode, MapIter, ValueOnPred, ValueType > ValueOnIter
Definition: RootNode.h:403
bool isBackgroundTile(const Tile &) const
Return true if the given tile is inactive and has the background value.
Definition: RootNode.h:1237
void setValueOnlyAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: RootNode.h:1898
DenseIter< RootNode, MapIter, ChildType, ValueType > ChildAllIter
Definition: RootNode.h:400
void modifyValueAndActiveStateAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition: RootNode.h:2016
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: RootNode.h:1989
const NodeT * probeConstNodeAndCache(const Coord &xyz, AccessorT &acc) const
Same as probeNode() but, if necessary, update the given accessor with pointers to the nodes along the...
Definition: RootNode.h:2763
GLint y
Definition: glcorearb.h:102
ValueIter< RootNode, MapIter, ChildOffPred, const ValueType > ChildOffIter
Definition: RootNode.h:398
ValueIter< const RootNode, MapCIter, ValueAllPred, const ValueType > ValueAllCIter
Definition: RootNode.h:408
void stealNodes(ArrayT &array)
Steals all nodes of a certain type from the tree and adds them to a container with the following API:...
Definition: RootNode.h:830
void prune(const ValueType &tolerance=zeroVal< ValueType >())
Reduce the memory footprint of this tree by replacing with tiles any nodes whose values are all the s...
Definition: RootNode.h:2424
void combine(RootNode &other, CombineOp &, bool prune=false)
Definition: RootNode.h:3117
ValueIter< const RootNode, MapCIter, ChildOffPred, ValueType > ChildOffCIter
Definition: RootNode.h:399
bool probeValueAndCache(const Coord &xyz, ValueType &value, AccessorT &) const
Definition: RootNode.h:2063
png_uint_32 i
Definition: png.h:2877
uint64 value_type
Definition: GA_PrimCompat.h:29
Tag dispatch class that distinguishes constructors during file input.
Definition: Types.h:505
Index32 FindHighestOn(Index32 v)
Return the most significant on bit of the given 32-bit value.
Definition: NodeMasks.h:151
SameConfiguration<OtherNodeType>::value is true if and only if OtherNodeType is the type of a RootNode ...
Definition: RootNode.h:100
NodeChain< RootNode, LEVEL >::Type NodeChainType
NodeChainType is a list of this tree's node types, from LeafNodeType to RootNode. ...
Definition: RootNode.h:86
LeafNodeType * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: RootNode.h:2700
static void getNodeLog2Dims(std::vector< Index > &dims)
Definition: RootNode.h:1324
static bool hasSameConfiguration(const RootNode< OtherChildType > &other)
Return false if the other node's dimensions don't match this node's.
Definition: RootNode.h:1408
bool isValueOn(const Coord &xyz) const
Definition: RootNode.h:1652
bool operator==(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:137
NodeChain< typename HeadT::ChildNodeType, HeadLevel-1 >::Type SubtreeT
Definition: RootNode.h:1019
GLdouble n
Definition: glcorearb.h:2007
void setActiveState(const Coord &xyz, bool on)
Set the active state of the voxel at the given coordinates but don't change its value.
Definition: RootNode.h:1744
Index getTableSize() const
Return the number of entries in this node's table.
Definition: RootNode.h:489
static bool hasCompatibleValueType(const RootNode< OtherChildType > &other)
Definition: RootNode.h:1440
void topologyUnion(const RootNode< OtherChildType > &other)
Union this tree's set of active values with the active values of the other tree, whose ValueType may ...
Definition: RootNode.h:3006
LeafNodeType * touchLeafAndCache(const Coord &xyz, AccessorT &acc)
Same as touchLeaf() but, if necessary, update the given accessor with pointers to the nodes along the...
T truncateRealToHalf(const T &val)
Return the given value truncated to 16-bit float precision.
Definition: Compression.h:153
void setValueOnly(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates but don't change its active state.
Definition: RootNode.h:1879
T distance(const UT_Vector4T< T > &v1, const UT_Vector4T< T > &v2)
Definition: UT_Vector4.h:634
#define OPENVDB_VERSION_NAME
Definition: version.h:43
RootNode()
Construct a new tree with a background value of 0.
Definition: RootNode.h:1053
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
static void combine2(RootT &self, const RootT &, const OtherRootT &other1, CombineOp &, bool)
Definition: RootNode.h:3177
HBOOST_STATIC_ASSERT(hboost::mpl::size< NodeChainType >::value==LEVEL+1)
bool hasActiveTiles() const
Return true if this root node, or any of its child nodes, have active tiles.
Definition: RootNode.h:1661
GLintptr offset
Definition: glcorearb.h:664
const ValueType & getValue(const Coord &xyz) const
Definition: RootNode.h:1684
void visit2(OtherRootNodeType &other, VisitorOp &)
Definition: RootNode.h:3349
NodeT * stealNode(const Coord &xyz, const ValueType &value, bool state)
Return a pointer to the node of type NodeT that contains voxel (x, y, z) and replace it with a tile o...
Definition: RootNode.h:2445
void combine2(const RootNode &other0, const OtherRootNode &other1, CombineOp &op, bool prune=false)
Definition: RootNode.h:3207
ValueIter< RootNode, MapIter, ValueOffPred, ValueType > ValueOffIter
Definition: RootNode.h:405
const LeafNodeType * probeConstLeafAndCache(const Coord &xyz, AccessorT &acc) const
Same as probeLeaf() but, if necessary, update the given accessor with pointers to the nodes along the...
void topologyDifference(const RootNode< OtherChildType > &other)
Difference this tree's set of active values with the active values of the other tree, whose ValueType may be different. So a resulting voxel will be active only if the original voxel is active in this tree and inactive in the other tree.
Definition: RootNode.h:3078
bool expand(const Coord &xyz)
Expand this node's table so that (x, y, z) is included in the index range.
Definition: RootNode.h:1310
void addLeaf(LeafNodeType *leaf)
Add the given leaf node to this tree, creating a new branch if necessary. If a leaf node with the sam...
Definition: RootNode.h:2464
void addTile(const Coord &xyz, const ValueType &value, bool state)
Add a tile containing voxel (x, y, z) at the root level, deleting the existing branch if necessary...
Definition: RootNode.h:2533
void stealNodes(ArrayT &array, const ValueType &value, bool state)
Steals all nodes of a certain type from the tree and adds them to a container with the following API:...
Definition: RootNode.h:2839
void setActiveStateAndCache(const Coord &xyz, bool on, AccessorT &)
Definition: RootNode.h:1767
GLuint const GLchar * name
Definition: glcorearb.h:785
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
Coord getMinIndex() const
Return the smallest index of the current tree.
Definition: RootNode.h:1333
bool writeTopology(std::ostream &, bool toHalf=false) const
Definition: RootNode.h:2190
ValueIter< const RootNode, MapCIter, ValueOffPred, const ValueType > ValueOffCIter
Definition: RootNode.h:406
void visitActiveBBox(BBoxOp &) const
Call the templated functor BBoxOp with bounding box information for all active tiles and leaf nodes i...
Definition: RootNode.h:3292
GLint GLsizei count
Definition: glcorearb.h:404
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
Definition: Platform.h:129
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don't change its value.
Definition: RootNode.h:1730
bool isApproxEqual(const Type &a, const Type &b)
Return true if a is equal to b to within the default floating-point comparison tolerance.
Definition: Math.h:370
static void copyWithValueConversion(RootT &self, const OtherRootT &other)
Definition: RootNode.h:1119
void denseFill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given axis-aligned box to a constant value.
Definition: RootNode.h:2137
void readBuffers(std::istream &, bool fromHalf=false)
Definition: RootNode.h:2350
CanConvertType<FromType, ToType>::value is true if a value of type ToType can be constructed from a v...
Definition: Types.h:233
ChildType::LeafNodeType LeafNodeType
Definition: RootNode.h:79
GLsizei const GLfloat * value
Definition: glcorearb.h:823
OPENVDB_API void setGridBackgroundValuePtr(std::ios_base &, const void *background)
Specify (a pointer to) the background value of the grid currently being read from or written to the g...
void writeBuffers(std::ostream &, bool toHalf=false) const
Definition: RootNode.h:2340
IMATH_INTERNAL_NAMESPACE_HEADER_ENTER T clip(const T &p, const Box< T > &box)
Definition: ImathBoxAlgo.h:89
RootNode(const RootNode< OtherChildType > &other)
Construct a new tree that reproduces the topology and active states of a tree of a different ValueTyp...
Definition: RootNode.h:120
size_t eraseBackgroundTiles()
Remove all background tiles.
Definition: RootNode.h:1271
void setValueAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: RootNode.h:1857
size_t numBackgroundTiles() const
Return the number of background tiles.
Definition: RootNode.h:1259
typedef int
Definition: png.h:1175
const NodeT * probeConstNode(const Coord &xyz) const
Return a pointer to the node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: RootNode.h:2683
void sparseFill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given axis-aligned box to a constant value.
Definition: RootNode.h:566
ValueIter< RootNode, MapIter, ValueAllPred, ValueType > ValueAllIter
Definition: RootNode.h:407
GLint GLenum GLint x
Definition: glcorearb.h:408
GLuint GLfloat * val
Definition: glcorearb.h:1607
GA_API const UT_StringHolder N
void copyToDense(const CoordBBox &bbox, DenseT &dense) const
Copy into a dense grid the values of all voxels, both active and inactive, that intersect a given bou...
Definition: RootNode.h:2146
const LeafNodeType * probeConstLeaf(const Coord &xyz) const
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: RootNode.h:2708
void modifyValue(const Coord &xyz, const ModifyOp &op)
Apply a functor to the value of the voxel at the given coordinates and mark the voxel as active...
Definition: RootNode.h:1921
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:107
CombineArgs & setARef(const AValueType &a)
Redirect the A value to a new external source.
Definition: Types.h:424
void modifyValueAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition: RootNode.h:1953
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_END
Definition: Platform.h:130
bool readTopology(std::istream &, bool fromHalf=false)
Definition: RootNode.h:2226
NodeT * probeNodeAndCache(const Coord &xyz, AccessorT &acc)
Same as probeNode() but, if necessary, update the given accessor with pointers to the nodes along the...
Definition: RootNode.h:2744
void voxelizeActiveTiles(bool threaded=true)
Densify active tiles, i.e., replace them with leaf-level active voxels.
Definition: RootNode.h:2869
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:503
RootNode< typename ChildType::template ValueConverter< OtherValueType >::Type > Type
Definition: RootNode.h:93
bool operator!=(const BaseDimensions< T > &a, const BaseDimensions< Y > &b)
Definition: Dimensions.h:165
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
void prune(TreeT &tree, typename TreeT::ValueType tolerance=zeroVal< typename TreeT::ValueType >(), bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing with tiles any nodes whose values are all the same...
Definition: Prune.h:374
T zeroVal()
Return the value of type T that corresponds to zero.
Definition: Math.h:94
DenseIter< const RootNode, MapCIter, const ChildType, const ValueType > ChildAllCIter
Definition: RootNode.h:401
void setValueOn(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: RootNode.h:1838
OPENVDB_API uint32_t getFormatVersion(std::ios_base &)
Return the file format version number associated with the given input stream.
void evalActiveBoundingBox(CoordBBox &bbox, bool visitVoxels=true) const
Expand the specified bbox so it includes the active tiles of this root node as well as all the active...
Definition: RootNode.h:1492
static CoordBBox getNodeBoundingBox()
Return the bounding box of this RootNode, i.e., an infinite bounding box.
Definition: RootNode.h:442
int getValueDepth(const Coord &xyz) const
Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides.
Definition: RootNode.h:1708
void addTileAndCache(Index level, const Coord &xyz, const ValueType &, bool state, AccessorT &)
Same as addTile() but, if necessary, update the given accessor with pointers to the nodes along the p...
Definition: RootNode.h:2580
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:101
void addLeafAndCache(LeafNodeType *leaf, AccessorT &)
Same as addLeaf() but, if necessary, update the given accessor with pointers to the nodes along the p...
Definition: RootNode.h:2499
void fill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given axis-aligned box to a constant value.
Definition: RootNode.h:2082
NodeChain<RootNodeType, RootNodeType::LEVEL>::Type is a hboost::mpl::vector that lists the types of t...
Definition: RootNode.h:68
bool isValueOnAndCache(const Coord &xyz, AccessorT &) const
Definition: RootNode.h:1672
void getNodes(ArrayT &array)
Adds all nodes of a certain type to a container with the following API:
Definition: RootNode.h:2784
void clip(const CoordBBox &)
Set all voxels that lie outside the given axis-aligned box to the background.
Definition: RootNode.h:2384
NodeT * probeNode(const Coord &xyz)
Return a pointer to the node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: RootNode.h:2665