OpenVDB  3.0.0
RootNode.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2014 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 //
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 <boost/type_traits/remove_const.hpp>
43 #include <boost/type_traits/remove_pointer.hpp>
44 #include <boost/type_traits/is_pointer.hpp>
45 #include <boost/type_traits/is_const.hpp>
46 #include <boost/mpl/contains.hpp>
47 #include <boost/mpl/if.hpp>
48 #include <boost/mpl/vector.hpp>//for boost::mpl::vector
49 #include <boost/mpl/at.hpp>
50 #include <boost/mpl/push_back.hpp>
51 #include <boost/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 
82  static const Index LEVEL = 1 + ChildType::LEVEL; // level 0 = leaf
83 
86  BOOST_STATIC_ASSERT(boost::mpl::size<NodeChainType>::value == LEVEL + 1);
87 
90  template<typename OtherValueType>
91  struct ValueConverter {
93  };
94 
98  template<typename OtherNodeType>
101  };
102 
103 
105  RootNode();
106 
108  explicit RootNode(const ValueType& background);
109 
110  RootNode(const RootNode& other) { *this = other; }
111 
118  template<typename OtherChildType>
119  explicit RootNode(const RootNode<OtherChildType>& other) { *this = other; }
120 
129  template<typename OtherChildType>
130  RootNode(const RootNode<OtherChildType>& other,
131  const ValueType& background, const ValueType& foreground, TopologyCopy);
132 
143  template<typename OtherChildType>
144  RootNode(const RootNode<OtherChildType>& other, const ValueType& background, TopologyCopy);
145 
147  RootNode& operator=(const RootNode& other);
155  template<typename OtherChildType>
156  RootNode& operator=(const RootNode<OtherChildType>& other);
157 
158  ~RootNode() { this->clearTable(); }
159 
160 private:
161  struct Tile {
162  Tile(): value(zeroVal<ValueType>()), active(false) {}
163  Tile(const ValueType& v, bool b): value(v), active(b) {}
164  ValueType value;
165  bool active;
166  };
167 
168  // This lightweight struct pairs child pointers and tiles.
169  struct NodeStruct {
170  ChildType* child;
171  Tile tile;
172 
173  NodeStruct(): child(NULL) {}
174  NodeStruct(ChildType& c): child(&c) {}
175  NodeStruct(const Tile& t): child(NULL), tile(t) {}
176  ~NodeStruct() {}
177 
178  bool isChild() const { return child != NULL; }
179  bool isTile() const { return child == NULL; }
180  bool isTileOff() const { return isTile() && !tile.active; }
181  bool isTileOn() const { return isTile() && tile.active; }
182 
183  void set(ChildType& c) { delete child; child = &c; }
184  void set(const Tile& t) { delete child; child = NULL; tile = t; }
185  ChildType& steal(const Tile& t) { ChildType* c = child; child = NULL; tile = t; return *c; }
186  };
187 
188  typedef std::map<Coord, NodeStruct> MapType;
189  typedef typename MapType::iterator MapIter;
190  typedef typename MapType::const_iterator MapCIter;
191 
192  typedef std::set<Coord> CoordSet;
193  typedef typename CoordSet::iterator CoordSetIter;
194  typedef typename CoordSet::const_iterator CoordSetCIter;
195 
196  static void setTile(const MapIter& i, const Tile& t) { i->second.set(t); }
197  static void setChild(const MapIter& i, ChildType& c) { i->second.set(c); }
198  static Tile& getTile(const MapIter& i) { return i->second.tile; }
199  static const Tile& getTile(const MapCIter& i) { return i->second.tile; }
200  static ChildType& getChild(const MapIter& i) { return *(i->second.child); }
201  static const ChildType& getChild(const MapCIter& i) { return *(i->second.child); }
202  static ChildType& stealChild(const MapIter& i, const Tile& t) {return i->second.steal(t);}
203  static const ChildType& stealChild(const MapCIter& i,const Tile& t) {return i->second.steal(t);}
204 
205  static bool isChild(const MapCIter& i) { return i->second.isChild(); }
206  static bool isChild(const MapIter& i) { return i->second.isChild(); }
207  static bool isTile(const MapCIter& i) { return i->second.isTile(); }
208  static bool isTile(const MapIter& i) { return i->second.isTile(); }
209  static bool isTileOff(const MapCIter& i) { return i->second.isTileOff(); }
210  static bool isTileOff(const MapIter& i) { return i->second.isTileOff(); }
211  static bool isTileOn(const MapCIter& i) { return i->second.isTileOn(); }
212  static bool isTileOn(const MapIter& i) { return i->second.isTileOn(); }
213 
214  struct NullPred {
215  static inline bool test(const MapIter&) { return true; }
216  static inline bool test(const MapCIter&) { return true; }
217  };
218  struct ValueOnPred {
219  static inline bool test(const MapIter& i) { return isTileOn(i); }
220  static inline bool test(const MapCIter& i) { return isTileOn(i); }
221  };
222  struct ValueOffPred {
223  static inline bool test(const MapIter& i) { return isTileOff(i); }
224  static inline bool test(const MapCIter& i) { return isTileOff(i); }
225  };
226  struct ValueAllPred {
227  static inline bool test(const MapIter& i) { return isTile(i); }
228  static inline bool test(const MapCIter& i) { return isTile(i); }
229  };
230  struct ChildOnPred {
231  static inline bool test(const MapIter& i) { return isChild(i); }
232  static inline bool test(const MapCIter& i) { return isChild(i); }
233  };
234  struct ChildOffPred {
235  static inline bool test(const MapIter& i) { return isTile(i); }
236  static inline bool test(const MapCIter& i) { return isTile(i); }
237  };
238 
239  template<typename _RootNodeT, typename _MapIterT, typename FilterPredT>
240  class BaseIter
241  {
242  public:
243  typedef _RootNodeT RootNodeT;
244  typedef _MapIterT MapIterT; // either MapIter or MapCIter
245 
246  bool operator==(const BaseIter& other) const
247  {
248  return (mParentNode == other.mParentNode) && (mIter == other.mIter);
249  }
250  bool operator!=(const BaseIter& other) const { return !(*this == other); }
251 
252  RootNodeT* getParentNode() const { return mParentNode; }
254  RootNodeT& parent() const
255  {
256  if (!mParentNode) OPENVDB_THROW(ValueError, "iterator references a null parent node");
257  return *mParentNode;
258  }
259 
260  bool test() const { assert(mParentNode); return mIter != mParentNode->mTable.end(); }
261  operator bool() const { return this->test(); }
262 
263  void increment() { ++mIter; this->skip(); }
264  bool next() { this->increment(); return this->test(); }
265  void increment(Index n) { for (int i = 0; i < n && this->next(); ++i) {} }
266 
269  Index pos() const
270  {
271  return !mParentNode ? 0U : Index(std::distance(mParentNode->mTable.begin(), mIter));
272  }
273 
274  bool isValueOn() const { return RootNodeT::isTileOn(mIter); }
275  bool isValueOff() const { return RootNodeT::isTileOff(mIter); }
276  void setValueOn(bool on = true) const { mIter->second.tile.active = on; }
277  void setValueOff() const { mIter->second.tile.active = false; }
278 
280  Coord getCoord() const { return mIter->first; }
282  void getCoord(Coord& xyz) const { xyz = this->getCoord(); }
283 
284  protected:
285  BaseIter(): mParentNode(NULL) {}
286  BaseIter(RootNodeT& parent, const MapIterT& iter): mParentNode(&parent), mIter(iter) {}
287 
288  void skip() { while (this->test() && !FilterPredT::test(mIter)) ++mIter; }
289 
290  RootNodeT* mParentNode;
291  MapIterT mIter;
292  }; // BaseIter
293 
294  template<typename RootNodeT, typename MapIterT, typename FilterPredT, typename ChildNodeT>
295  class ChildIter: public BaseIter<RootNodeT, MapIterT, FilterPredT>
296  {
297  public:
298  typedef BaseIter<RootNodeT, MapIterT, FilterPredT> BaseT;
299  typedef RootNodeT NodeType;
300  typedef NodeType ValueType;
301  typedef ChildNodeT ChildNodeType;
302  typedef typename boost::remove_const<NodeType>::type NonConstNodeType;
303  typedef typename boost::remove_const<ValueType>::type NonConstValueType;
304  typedef typename boost::remove_const<ChildNodeType>::type NonConstChildNodeType;
305  using BaseT::mIter;
306 
307  ChildIter() {}
308  ChildIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
309 
310  ChildIter& operator++() { BaseT::increment(); return *this; }
311 
312  ChildNodeT& getValue() const { return getChild(mIter); }
313  ChildNodeT& operator*() const { return this->getValue(); }
314  ChildNodeT* operator->() const { return &this->getValue(); }
315  }; // ChildIter
316 
317  template<typename RootNodeT, typename MapIterT, typename FilterPredT, typename ValueT>
318  class ValueIter: public BaseIter<RootNodeT, MapIterT, FilterPredT>
319  {
320  public:
321  typedef BaseIter<RootNodeT, MapIterT, FilterPredT> BaseT;
322  typedef RootNodeT NodeType;
323  typedef ValueT ValueType;
324  typedef typename boost::remove_const<NodeType>::type NonConstNodeType;
325  typedef typename boost::remove_const<ValueT>::type NonConstValueType;
326  using BaseT::mIter;
327 
328  ValueIter() {}
329  ValueIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
330 
331  ValueIter& operator++() { BaseT::increment(); return *this; }
332 
333  ValueT& getValue() const { return getTile(mIter).value; }
334  ValueT& operator*() const { return this->getValue(); }
335  ValueT* operator->() const { return &(this->getValue()); }
336 
337  void setValue(const ValueT& v) const { assert(isTile(mIter)); getTile(mIter).value = v; }
338 
339  template<typename ModifyOp>
340  void modifyValue(const ModifyOp& op) const
341  {
342  assert(isTile(mIter));
343  op(getTile(mIter).value);
344  }
345  }; // ValueIter
346 
347  template<typename RootNodeT, typename MapIterT, typename ChildNodeT, typename ValueT>
348  class DenseIter: public BaseIter<RootNodeT, MapIterT, NullPred>
349  {
350  public:
351  typedef BaseIter<RootNodeT, MapIterT, NullPred> BaseT;
352  typedef RootNodeT NodeType;
353  typedef ValueT ValueType;
354  typedef ChildNodeT ChildNodeType;
355  typedef typename boost::remove_const<NodeType>::type NonConstNodeType;
356  typedef typename boost::remove_const<ValueT>::type NonConstValueType;
357  typedef typename boost::remove_const<ChildNodeT>::type NonConstChildNodeType;
358  using BaseT::mIter;
359 
360  DenseIter() {}
361  DenseIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) {}
362 
363  DenseIter& operator++() { BaseT::increment(); return *this; }
364 
365  bool isChildNode() const { return isChild(mIter); }
366 
367  ChildNodeT* probeChild(NonConstValueType& value) const
368  {
369  if (isChild(mIter)) return &getChild(mIter);
370  value = getTile(mIter).value;
371  return NULL;
372  }
373  bool probeChild(ChildNodeT*& child, NonConstValueType& value) const
374  {
375  child = this->probeChild(value);
376  return child != NULL;
377  }
378  bool probeValue(NonConstValueType& value) const { return !this->probeChild(value); }
379 
380  void setChild(ChildNodeT& c) const { RootNodeT::setChild(mIter, c); }
381  void setChild(ChildNodeT* c) const { assert(c != NULL); RootNodeT::setChild(mIter, *c); }
382  void setValue(const ValueT& v) const
383  {
384  if (isTile(mIter)) getTile(mIter).value = v;
388  else stealChild(mIter, Tile(v, /*active=*/true));
389  }
390  }; // DenseIter
391 
392 public:
393  typedef ChildIter<RootNode, MapIter, ChildOnPred, ChildType> ChildOnIter;
394  typedef ChildIter<const RootNode, MapCIter, ChildOnPred, const ChildType> ChildOnCIter;
395  typedef ValueIter<RootNode, MapIter, ChildOffPred, const ValueType> ChildOffIter;
396  typedef ValueIter<const RootNode, MapCIter, ChildOffPred, ValueType> ChildOffCIter;
397  typedef DenseIter<RootNode, MapIter, ChildType, ValueType> ChildAllIter;
398  typedef DenseIter<const RootNode, MapCIter, const ChildType, const ValueType> ChildAllCIter;
399 
400  typedef ValueIter<RootNode, MapIter, ValueOnPred, ValueType> ValueOnIter;
401  typedef ValueIter<const RootNode, MapCIter, ValueOnPred, const ValueType> ValueOnCIter;
402  typedef ValueIter<RootNode, MapIter, ValueOffPred, ValueType> ValueOffIter;
403  typedef ValueIter<const RootNode, MapCIter, ValueOffPred, const ValueType> ValueOffCIter;
404  typedef ValueIter<RootNode, MapIter, ValueAllPred, ValueType> ValueAllIter;
405  typedef ValueIter<const RootNode, MapCIter, ValueAllPred, const ValueType> ValueAllCIter;
406 
407 
408  ChildOnCIter cbeginChildOn() const { return ChildOnCIter(*this, mTable.begin()); }
409  ChildOffCIter cbeginChildOff() const { return ChildOffCIter(*this, mTable.begin()); }
410  ChildAllCIter cbeginChildAll() const { return ChildAllCIter(*this, mTable.begin()); }
411  ChildOnCIter beginChildOn() const { return cbeginChildOn(); }
412  ChildOffCIter beginChildOff() const { return cbeginChildOff(); }
413  ChildAllCIter beginChildAll() const { return cbeginChildAll(); }
414  ChildOnIter beginChildOn() { return ChildOnIter(*this, mTable.begin()); }
415  ChildOffIter beginChildOff() { return ChildOffIter(*this, mTable.begin()); }
416  ChildAllIter beginChildAll() { return ChildAllIter(*this, mTable.begin()); }
417 
418  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(*this, mTable.begin()); }
419  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(*this, mTable.begin()); }
420  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(*this, mTable.begin()); }
421  ValueOnCIter beginValueOn() const { return cbeginValueOn(); }
422  ValueOffCIter beginValueOff() const { return cbeginValueOff(); }
423  ValueAllCIter beginValueAll() const { return cbeginValueAll(); }
424  ValueOnIter beginValueOn() { return ValueOnIter(*this, mTable.begin()); }
425  ValueOffIter beginValueOff() { return ValueOffIter(*this, mTable.begin()); }
426  ValueAllIter beginValueAll() { return ValueAllIter(*this, mTable.begin()); }
427 
429  Index64 memUsage() const;
430 
436  void evalActiveBoundingBox(CoordBBox& bbox, bool visitVoxels = true) const;
437 
439  static CoordBBox getNodeBoundingBox() { return CoordBBox::inf(); }
440 
453  void setBackground(const ValueType& value, bool updateChildNodes);
454 
456  const ValueType& background() const { return mBackground; }
457 
459  bool isBackgroundTile(const Tile&) const;
461  bool isBackgroundTile(const MapIter&) const;
463  bool isBackgroundTile(const MapCIter&) const;
465 
467  size_t numBackgroundTiles() const;
470  size_t eraseBackgroundTiles();
471  void clear() { this->clearTable(); }
472 
474  bool empty() const { return mTable.size() == numBackgroundTiles(); }
475 
479  bool expand(const Coord& xyz);
480 
481  static Index getLevel() { return LEVEL; }
482  static void getNodeLog2Dims(std::vector<Index>& dims);
483  static Index getChildDim() { return ChildType::DIM; }
484 
486  Index getTableSize() const { return static_cast<Index>(mTable.size()); }
487 
488  Index getWidth() const { return this->getMaxIndex()[0] - this->getMinIndex()[0]; }
489  Index getHeight() const { return this->getMaxIndex()[1] - this->getMinIndex()[1]; }
490  Index getDepth() const { return this->getMaxIndex()[2] - this->getMinIndex()[2]; }
491 
493  Coord getMinIndex() const;
495  Coord getMaxIndex() const;
497  void getIndexRange(CoordBBox& bbox) const;
498 
501  template<typename OtherChildType>
502  bool hasSameTopology(const RootNode<OtherChildType>& other) const;
503 
505  template<typename OtherChildType>
506  static bool hasSameConfiguration(const RootNode<OtherChildType>& other);
507 
510  template<typename OtherChildType>
511  static bool hasCompatibleValueType(const RootNode<OtherChildType>& other);
512 
513  Index32 leafCount() const;
514  Index32 nonLeafCount() const;
515  Index64 onVoxelCount() const;
516  Index64 offVoxelCount() const;
517  Index64 onLeafVoxelCount() const;
518  Index64 offLeafVoxelCount() const;
519  Index64 onTileCount() const;
520 
521  bool isValueOn(const Coord& xyz) const;
522 
523  bool hasActiveTiles() const;
524 
525  const ValueType& getValue(const Coord& xyz) const;
526  bool probeValue(const Coord& xyz, ValueType& value) const;
527 
531  int getValueDepth(const Coord& xyz) const;
532 
534  void setActiveState(const Coord& xyz, bool on);
536  void setValueOnly(const Coord& xyz, const ValueType& value);
538  void setValueOn(const Coord& xyz, const ValueType& value);
540  void setValueOff(const Coord& xyz);
542  void setValueOff(const Coord& xyz, const ValueType& value);
543 
546  template<typename ModifyOp>
547  void modifyValue(const Coord& xyz, const ModifyOp& op);
549  template<typename ModifyOp>
550  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op);
551 
558  void fill(const CoordBBox& bbox, const ValueType& value, bool active = true);
559 
565  template<typename DenseT>
566  void copyToDense(const CoordBBox& bbox, DenseT& dense) const;
567 
568 
569  //
570  // I/O
571  //
572  bool writeTopology(std::ostream&, bool toHalf = false) const;
573  bool readTopology(std::istream&, bool fromHalf = false);
574 
575  void writeBuffers(std::ostream&, bool toHalf = false) const;
576  void readBuffers(std::istream&, bool fromHalf = false);
577  void readBuffers(std::istream&, const CoordBBox&, bool fromHalf = false);
578 
579 
580  //
581  // Voxel access
582  //
587  template<typename AccessorT>
588  const ValueType& getValueAndCache(const Coord& xyz, AccessorT&) const;
593  template<typename AccessorT>
594  bool isValueOnAndCache(const Coord& xyz, AccessorT&) const;
595 
600  template<typename AccessorT>
601  void setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
602 
607  template<typename AccessorT>
608  void setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
609 
615  template<typename ModifyOp, typename AccessorT>
616  void modifyValueAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&);
617 
622  template<typename ModifyOp, typename AccessorT>
623  void modifyValueAndActiveStateAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&);
624 
629  template<typename AccessorT>
630  void setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
631 
636  template<typename AccessorT>
637  void setActiveStateAndCache(const Coord& xyz, bool on, AccessorT&);
638 
644  template<typename AccessorT>
645  bool probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT&) const;
646 
652  template<typename AccessorT>
653  int getValueDepthAndCache(const Coord& xyz, AccessorT&) const;
654 
656  void clip(const CoordBBox&);
657 
661  void prune(const ValueType& tolerance = zeroVal<ValueType>());
662 
665  void addLeaf(LeafNodeType* leaf);
666 
669  template<typename AccessorT>
670  void addLeafAndCache(LeafNodeType* leaf, AccessorT&);
671 
680  template<typename NodeT>
681  NodeT* stealNode(const Coord& xyz, const ValueType& value, bool state);
682 
685  void addTile(const Coord& xyz, const ValueType& value, bool state);
686 
690  void addTile(Index level, const Coord& xyz, const ValueType& value, bool state);
691 
694  template<typename AccessorT>
695  void addTileAndCache(Index level, const Coord& xyz, const ValueType&, bool state, AccessorT&);
696 
702  LeafNodeType* touchLeaf(const Coord& xyz);
703 
706  template<typename AccessorT>
707  LeafNodeType* touchLeafAndCache(const Coord& xyz, AccessorT& acc);
708 
710  template <typename NodeT>
713  NodeT* probeNode(const Coord& xyz);
714  template <typename NodeT>
715  const NodeT* probeConstNode(const Coord& xyz) const;
717 
719  template<typename NodeT, typename AccessorT>
722  NodeT* probeNodeAndCache(const Coord& xyz, AccessorT& acc);
723  template<typename NodeT, typename AccessorT>
724  const NodeT* probeConstNodeAndCache(const Coord& xyz, AccessorT& acc) const;
726 
728  LeafNodeType* probeLeaf(const Coord& xyz);
731  const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
732  const LeafNodeType* probeLeaf(const Coord& xyz) const;
734 
736  template<typename AccessorT>
739  LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc);
740  template<typename AccessorT>
741  const LeafNodeType* probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const;
742  template<typename AccessorT>
743  const LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc) const;
745 
746 
747  //
748  // Aux methods
749  //
750 
752  template<typename ArrayT> void getNodes(ArrayT& array);
775  template<typename ArrayT> void getNodes(ArrayT& array) const;
777 
779  void voxelizeActiveTiles();
780 
788  template<MergePolicy Policy> void merge(RootNode& other);
789 
803  template<typename OtherChildType>
804  void topologyUnion(const RootNode<OtherChildType>& other);
805 
819  template<typename OtherChildType>
820  void topologyIntersection(const RootNode<OtherChildType>& other);
821 
832  template<typename OtherChildType>
833  void topologyDifference(const RootNode<OtherChildType>& other);
834 
835  template<typename CombineOp>
836  void combine(RootNode& other, CombineOp&, bool prune = false);
837 
838  template<typename CombineOp, typename OtherRootNode /*= RootNode*/>
839  void combine2(const RootNode& other0, const OtherRootNode& other1,
840  CombineOp& op, bool prune = false);
841 
847  template<typename BBoxOp> void visitActiveBBox(BBoxOp&) const;
848 
849  template<typename VisitorOp> void visit(VisitorOp&);
850  template<typename VisitorOp> void visit(VisitorOp&) const;
851 
852  template<typename OtherRootNodeType, typename VisitorOp>
853  void visit2(OtherRootNodeType& other, VisitorOp&);
854  template<typename OtherRootNodeType, typename VisitorOp>
855  void visit2(OtherRootNodeType& other, VisitorOp&) const;
856 
857 private:
860  template<typename> friend class RootNode;
861 
862  template<typename, typename, bool> friend struct RootNodeCopyHelper;
863  template<typename, typename, typename, bool> friend struct RootNodeCombineHelper;
864 
866  void initTable() {}
867  inline void clearTable();
869  void resetTable(MapType& table) { mTable.swap(table); table.clear(); }
871  void resetTable(const MapType&) const {}
873 
874  Index getChildCount() const;
875  Index getTileCount() const;
876  Index getActiveTileCount() const;
877  Index getInactiveTileCount() const;
878 
880  static Coord coordToKey(const Coord& xyz) { return xyz & ~(ChildType::DIM - 1); }
881 
883  void insertKeys(CoordSet&) const;
884 
886  bool hasKey(const Coord& key) const { return mTable.find(key) != mTable.end(); }
888  MapIter findKey(const Coord& key) { return mTable.find(key); }
891  MapCIter findKey(const Coord& key) const { return mTable.find(key); }
893 
894  MapIter findCoord(const Coord& xyz) { return mTable.find(coordToKey(xyz)); }
897  MapCIter findCoord(const Coord& xyz) const { return mTable.find(coordToKey(xyz)); }
899  MapIter findOrAddCoord(const Coord& xyz);
903 
908  template<typename OtherChildType>
909  static void enforceSameConfiguration(const RootNode<OtherChildType>& other);
910 
916  template<typename OtherChildType>
917  static void enforceCompatibleValueTypes(const RootNode<OtherChildType>& other);
918 
919  template<typename CombineOp, typename OtherRootNode /*= RootNode*/>
920  void doCombine2(const RootNode&, const OtherRootNode&, CombineOp&, bool prune);
921 
922  template<typename RootNodeT, typename VisitorOp, typename ChildAllIterT>
923  static inline void doVisit(RootNodeT&, VisitorOp&);
924 
925  template<typename RootNodeT, typename OtherRootNodeT, typename VisitorOp,
926  typename ChildAllIterT, typename OtherChildAllIterT>
927  static inline void doVisit2(RootNodeT&, OtherRootNodeT&, VisitorOp&);
928 
929 
930  MapType mTable;
931  ValueType mBackground;
932 }; // end of RootNode class
933 
934 
936 
937 
958 template<typename HeadT, int HeadLevel>
959 struct NodeChain {
960  typedef typename NodeChain<typename HeadT::ChildNodeType, HeadLevel-1>::Type SubtreeT;
961  typedef typename boost::mpl::push_back<SubtreeT, HeadT>::type Type;
962 };
963 
965 template<typename HeadT>
966 struct NodeChain<HeadT, /*HeadLevel=*/1> {
967  typedef typename boost::mpl::vector<typename HeadT::ChildNodeType, HeadT>::type Type;
968 };
969 
970 
972 
973 
975 template<typename ChildT1, typename NodeT2>
978 struct SameRootConfig {
979  static const bool value = false;
980 };
981 
982 template<typename ChildT1, typename ChildT2>
983 struct SameRootConfig<ChildT1, RootNode<ChildT2> > {
984  static const bool value = ChildT1::template SameConfiguration<ChildT2>::value;
985 };
987 
988 
990 
991 
992 template<typename ChildT>
993 inline
994 RootNode<ChildT>::RootNode(): mBackground(zeroVal<ValueType>())
995 {
996  this->initTable();
997 }
998 
999 
1000 template<typename ChildT>
1001 inline
1002 RootNode<ChildT>::RootNode(const ValueType& background): mBackground(background)
1003 {
1004  this->initTable();
1005 }
1006 
1007 
1008 template<typename ChildT>
1009 template<typename OtherChildType>
1010 inline
1012  const ValueType& backgd, const ValueType& foregd, TopologyCopy):
1013  mBackground(backgd)
1014 {
1015  typedef RootNode<OtherChildType> OtherRootT;
1016 
1017  enforceSameConfiguration(other);
1018 
1019  const Tile bgTile(backgd, /*active=*/false), fgTile(foregd, true);
1020  this->initTable();
1021 
1022  for (typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
1023  mTable[i->first] = OtherRootT::isTile(i)
1024  ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
1025  : NodeStruct(*(new ChildT(OtherRootT::getChild(i), backgd, foregd, TopologyCopy())));
1026  }
1027 }
1028 
1029 
1030 template<typename ChildT>
1031 template<typename OtherChildType>
1032 inline
1034  const ValueType& backgd, TopologyCopy):
1035  mBackground(backgd)
1036 {
1037  typedef RootNode<OtherChildType> OtherRootT;
1038 
1039  enforceSameConfiguration(other);
1040 
1041  const Tile bgTile(backgd, /*active=*/false), fgTile(backgd, true);
1042  this->initTable();
1043  for (typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
1044  mTable[i->first] = OtherRootT::isTile(i)
1045  ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
1046  : NodeStruct(*(new ChildT(OtherRootT::getChild(i), backgd, TopologyCopy())));
1047  }
1048 }
1049 
1050 
1052 
1053 
1054 // This helper class is a friend of RootNode and is needed so that assignment
1055 // with value conversion can be specialized for compatible and incompatible
1056 // pairs of RootNode types.
1057 template<typename RootT, typename OtherRootT, bool Compatible = false>
1058 struct RootNodeCopyHelper
1059 {
1060  static inline void copyWithValueConversion(RootT& self, const OtherRootT& other)
1061  {
1062  // If the two root nodes have different configurations or incompatible ValueTypes,
1063  // throw an exception.
1064  self.enforceSameConfiguration(other);
1065  self.enforceCompatibleValueTypes(other);
1066  // One of the above two tests should throw, so we should never get here:
1067  std::ostringstream ostr;
1068  ostr << "cannot convert a " << typeid(OtherRootT).name()
1069  << " to a " << typeid(RootT).name();
1070  OPENVDB_THROW(TypeError, ostr.str());
1071  }
1072 };
1073 
1074 // Specialization for root nodes of compatible types
1075 template<typename RootT, typename OtherRootT>
1076 struct RootNodeCopyHelper<RootT, OtherRootT, /*Compatible=*/true>
1077 {
1078  static inline void copyWithValueConversion(RootT& self, const OtherRootT& other)
1079  {
1080  typedef typename RootT::ValueType ValueT;
1081  typedef typename RootT::ChildNodeType ChildT;
1082  typedef typename RootT::NodeStruct NodeStruct;
1083  typedef typename RootT::Tile Tile;
1084  typedef typename OtherRootT::ValueType OtherValueT;
1085  typedef typename OtherRootT::MapCIter OtherMapCIter;
1086  typedef typename OtherRootT::Tile OtherTile;
1087 
1088  struct Local {
1090  static inline ValueT convertValue(const OtherValueT& val) { return ValueT(val); }
1091  };
1092 
1093  self.mBackground = Local::convertValue(other.mBackground);
1094 
1095  self.clearTable();
1096  self.initTable();
1097 
1098  for (OtherMapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
1099  if (other.isTile(i)) {
1100  // Copy the other node's tile, but convert its value to this node's ValueType.
1101  const OtherTile& otherTile = other.getTile(i);
1102  self.mTable[i->first] = NodeStruct(
1103  Tile(Local::convertValue(otherTile.value), otherTile.active));
1104  } else {
1105  // Copy the other node's child, but convert its values to this node's ValueType.
1106  self.mTable[i->first] = NodeStruct(*(new ChildT(other.getChild(i))));
1107  }
1108  }
1109  }
1110 };
1111 
1112 
1113 // Overload for root nodes of the same type as this node
1114 template<typename ChildT>
1115 inline RootNode<ChildT>&
1117 {
1118  if (&other != this) {
1119  mBackground = other.mBackground;
1120 
1121  this->clearTable();
1122  this->initTable();
1123 
1124  for (MapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
1125  mTable[i->first] =
1126  isTile(i) ? NodeStruct(getTile(i)) : NodeStruct(*(new ChildT(getChild(i))));
1127  }
1128  }
1129  return *this;
1130 }
1131 
1132 // Overload for root nodes of different types
1133 template<typename ChildT>
1134 template<typename OtherChildType>
1135 inline RootNode<ChildT>&
1137 {
1138  typedef RootNode<OtherChildType> OtherRootT;
1139  typedef typename OtherRootT::ValueType OtherValueT;
1140  static const bool compatible = (SameConfiguration<OtherRootT>::value
1141  && CanConvertType</*from=*/OtherValueT, /*to=*/ValueType>::value);
1143  return *this;
1144 }
1145 
1146 
1148 
1149 template<typename ChildT>
1150 inline void
1151 RootNode<ChildT>::setBackground(const ValueType& background, bool updateChildNodes)
1152 {
1153  if (math::isExactlyEqual(background, mBackground)) return;
1154 
1155  if (updateChildNodes) {
1156  // Traverse the tree, replacing occurrences of mBackground with background
1157  // and -mBackground with -background.
1158  for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1159  ChildT *child = iter->second.child;
1160  if (child) {
1161  child->resetBackground(/*old=*/mBackground, /*new=*/background);
1162  } else {
1163  Tile& tile = getTile(iter);
1164  if (tile.active) continue;//only change inactive tiles
1165  if (math::isApproxEqual(tile.value, mBackground)) {
1166  tile.value = background;
1167  } else if (math::isApproxEqual(tile.value, math::negative(mBackground))) {
1168  tile.value = math::negative(background);
1169  }
1170  }
1171  }
1172  }
1173  mBackground = background;
1174 }
1175 
1176 template<typename ChildT>
1177 inline bool
1178 RootNode<ChildT>::isBackgroundTile(const Tile& tile) const
1179 {
1180  return !tile.active && math::isApproxEqual(tile.value, mBackground);
1181 }
1182 
1183 template<typename ChildT>
1184 inline bool
1185 RootNode<ChildT>::isBackgroundTile(const MapIter& iter) const
1186 {
1187  return isTileOff(iter) && math::isApproxEqual(getTile(iter).value, mBackground);
1188 }
1189 
1190 template<typename ChildT>
1191 inline bool
1192 RootNode<ChildT>::isBackgroundTile(const MapCIter& iter) const
1193 {
1194  return isTileOff(iter) && math::isApproxEqual(getTile(iter).value, mBackground);
1195 }
1196 
1197 
1198 template<typename ChildT>
1199 inline size_t
1201 {
1202  size_t count = 0;
1203  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1204  if (this->isBackgroundTile(i)) ++count;
1205  }
1206  return count;
1207 }
1208 
1209 
1210 template<typename ChildT>
1211 inline size_t
1213 {
1214  std::set<Coord> keysToErase;
1215  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1216  if (this->isBackgroundTile(i)) keysToErase.insert(i->first);
1217  }
1218  for (std::set<Coord>::iterator i = keysToErase.begin(), e = keysToErase.end(); i != e; ++i) {
1219  mTable.erase(*i);
1220  }
1221  return keysToErase.size();
1222 }
1223 
1224 
1226 
1227 
1228 template<typename ChildT>
1229 inline void
1230 RootNode<ChildT>::insertKeys(CoordSet& keys) const
1231 {
1232  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1233  keys.insert(i->first);
1234  }
1235 }
1236 
1237 
1238 template<typename ChildT>
1239 inline typename RootNode<ChildT>::MapIter
1240 RootNode<ChildT>::findOrAddCoord(const Coord& xyz)
1241 {
1242  const Coord key = coordToKey(xyz);
1243  std::pair<MapIter, bool> result = mTable.insert(
1244  typename MapType::value_type(key, NodeStruct(Tile(mBackground, /*active=*/false))));
1245  return result.first;
1246 }
1247 
1248 
1249 template<typename ChildT>
1250 inline bool
1251 RootNode<ChildT>::expand(const Coord& xyz)
1252 {
1253  const Coord key = coordToKey(xyz);
1254  std::pair<MapIter, bool> result = mTable.insert(
1255  typename MapType::value_type(key, NodeStruct(Tile(mBackground, /*active=*/false))));
1256  return result.second; // return true if the key did not already exist
1257 }
1258 
1259 
1261 
1262 
1263 template<typename ChildT>
1264 inline void
1265 RootNode<ChildT>::getNodeLog2Dims(std::vector<Index>& dims)
1266 {
1267  dims.push_back(0); // magic number; RootNode has no Log2Dim
1268  ChildT::getNodeLog2Dims(dims);
1269 }
1270 
1271 
1272 template<typename ChildT>
1273 inline Coord
1275 {
1276  return mTable.empty() ? Coord(0) : mTable.begin()->first;
1277 }
1278 
1279 template<typename ChildT>
1280 inline Coord
1282 {
1283  return mTable.empty() ? Coord(0) : mTable.rbegin()->first + Coord(ChildT::DIM - 1);
1284 }
1285 
1286 
1287 template<typename ChildT>
1288 inline void
1289 RootNode<ChildT>::getIndexRange(CoordBBox& bbox) const
1290 {
1291  bbox.min() = this->getMinIndex();
1292  bbox.max() = this->getMaxIndex();
1293 }
1294 
1295 
1297 
1298 
1299 template<typename ChildT>
1300 template<typename OtherChildType>
1301 inline bool
1303 {
1304  typedef RootNode<OtherChildType> OtherRootT;
1305  typedef typename OtherRootT::MapType OtherMapT;
1306  typedef typename OtherRootT::MapIter OtherIterT;
1307  typedef typename OtherRootT::MapCIter OtherCIterT;
1308 
1309  if (!hasSameConfiguration(other)) return false;
1310 
1311  // Create a local copy of the other node's table.
1312  OtherMapT copyOfOtherTable = other.mTable;
1313 
1314  // For each entry in this node's table...
1315  for (MapCIter thisIter = mTable.begin(); thisIter != mTable.end(); ++thisIter) {
1316  if (this->isBackgroundTile(thisIter)) continue; // ignore background tiles
1317 
1318  // Fail if there is no corresponding entry in the other node's table.
1319  OtherCIterT otherIter = other.findKey(thisIter->first);
1320  if (otherIter == other.mTable.end()) return false;
1321 
1322  // Fail if this entry is a tile and the other is a child or vice-versa.
1323  if (isChild(thisIter)) {//thisIter points to a child
1324  if (OtherRootT::isTile(otherIter)) return false;
1325  // Fail if both entries are children, but the children have different topology.
1326  if (!getChild(thisIter).hasSameTopology(&OtherRootT::getChild(otherIter))) return false;
1327  } else {//thisIter points to a tile
1328  if (OtherRootT::isChild(otherIter)) return false;
1329  if (getTile(thisIter).active != OtherRootT::getTile(otherIter).active) return false;
1330  }
1331 
1332  // Remove tiles and child nodes with matching topology from
1333  // the copy of the other node's table. This is required since
1334  // the two root tables can include an arbitrary number of
1335  // background tiles and still have the same topology!
1336  copyOfOtherTable.erase(otherIter->first);
1337  }
1338  // Fail if the remaining entries in copyOfOtherTable are not all background tiles.
1339  for (OtherIterT i = copyOfOtherTable.begin(), e = copyOfOtherTable.end(); i != e; ++i) {
1340  if (!other.isBackgroundTile(i)) return false;
1341  }
1342  return true;
1343 }
1344 
1345 
1346 template<typename ChildT>
1347 template<typename OtherChildType>
1348 inline bool
1350 {
1351  std::vector<Index> thisDims, otherDims;
1352  RootNode::getNodeLog2Dims(thisDims);
1354  return (thisDims == otherDims);
1355 }
1356 
1357 
1358 template<typename ChildT>
1359 template<typename OtherChildType>
1360 inline void
1362 {
1363  std::vector<Index> thisDims, otherDims;
1364  RootNode::getNodeLog2Dims(thisDims);
1366  if (thisDims != otherDims) {
1367  std::ostringstream ostr;
1368  ostr << "grids have incompatible configurations (" << thisDims[0];
1369  for (size_t i = 1, N = thisDims.size(); i < N; ++i) ostr << " x " << thisDims[i];
1370  ostr << " vs. " << otherDims[0];
1371  for (size_t i = 1, N = otherDims.size(); i < N; ++i) ostr << " x " << otherDims[i];
1372  ostr << ")";
1373  OPENVDB_THROW(TypeError, ostr.str());
1374  }
1375 }
1376 
1377 
1378 template<typename ChildT>
1379 template<typename OtherChildType>
1380 inline bool
1382 {
1383  typedef typename OtherChildType::ValueType OtherValueType;
1384  return CanConvertType</*from=*/OtherValueType, /*to=*/ValueType>::value;
1385 }
1386 
1387 
1388 template<typename ChildT>
1389 template<typename OtherChildType>
1390 inline void
1392 {
1393  typedef typename OtherChildType::ValueType OtherValueType;
1395  std::ostringstream ostr;
1396  ostr << "values of type " << typeNameAsString<OtherValueType>()
1397  << " cannot be converted to type " << typeNameAsString<ValueType>();
1398  OPENVDB_THROW(TypeError, ostr.str());
1399  }
1400 }
1401 
1402 
1404 
1405 
1406 template<typename ChildT>
1407 inline Index64
1409 {
1410  Index64 sum = sizeof(*this);
1411  for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1412  if (const ChildT *child = iter->second.child) {
1413  sum += child->memUsage();
1414  }
1415  }
1416  return sum;
1417 }
1418 
1419 
1420 template<typename ChildT>
1421 inline void
1423 {
1424  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1425  delete i->second.child;
1426  }
1427  mTable.clear();
1428 }
1429 
1430 
1431 template<typename ChildT>
1432 inline void
1433 RootNode<ChildT>::evalActiveBoundingBox(CoordBBox& bbox, bool visitVoxels) const
1434 {
1435  for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1436  if (const ChildT *child = iter->second.child) {
1437  child->evalActiveBoundingBox(bbox, visitVoxels);
1438  } else if (isTileOn(iter)) {
1439  bbox.expand(iter->first, ChildT::DIM);
1440  }
1441  }
1442 }
1443 
1444 
1445 template<typename ChildT>
1446 inline Index
1448  Index sum = 0;
1449  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1450  if (isChild(i)) ++sum;
1451  }
1452  return sum;
1453 }
1454 
1455 
1456 template<typename ChildT>
1457 inline Index
1458 RootNode<ChildT>::getTileCount() const
1459 {
1460  Index sum = 0;
1461  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1462  if (isTile(i)) ++sum;
1463  }
1464  return sum;
1465 }
1466 
1467 
1468 template<typename ChildT>
1469 inline Index
1470 RootNode<ChildT>::getActiveTileCount() const
1471 {
1472  Index sum = 0;
1473  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1474  if (isTileOn(i)) ++sum;
1475  }
1476  return sum;
1477 }
1478 
1479 
1480 template<typename ChildT>
1481 inline Index
1482 RootNode<ChildT>::getInactiveTileCount() const
1483 {
1484  Index sum = 0;
1485  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1486  if (isTileOff(i)) ++sum;
1487  }
1488  return sum;
1489 }
1490 
1491 
1492 template<typename ChildT>
1493 inline Index32
1495 {
1496  Index32 sum = 0;
1497  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1498  if (isChild(i)) sum += getChild(i).leafCount();
1499  }
1500  return sum;
1501 }
1502 
1503 
1504 template<typename ChildT>
1505 inline Index32
1507 {
1508  Index32 sum = 1;
1509  if (ChildT::LEVEL != 0) {
1510  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1511  if (isChild(i)) sum += getChild(i).nonLeafCount();
1512  }
1513  }
1514  return sum;
1515 }
1516 
1517 
1518 template<typename ChildT>
1519 inline Index64
1521 {
1522  Index64 sum = 0;
1523  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1524  if (isChild(i)) {
1525  sum += getChild(i).onVoxelCount();
1526  } else if (isTileOn(i)) {
1527  sum += ChildT::NUM_VOXELS;
1528  }
1529  }
1530  return sum;
1531 }
1532 
1533 
1534 template<typename ChildT>
1535 inline Index64
1537 {
1538  Index64 sum = 0;
1539  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1540  if (isChild(i)) {
1541  sum += getChild(i).offVoxelCount();
1542  } else if (isTileOff(i) && !this->isBackgroundTile(i)) {
1543  sum += ChildT::NUM_VOXELS;
1544  }
1545  }
1546  return sum;
1547 }
1548 
1549 
1550 template<typename ChildT>
1551 inline Index64
1553 {
1554  Index64 sum = 0;
1555  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1556  if (isChild(i)) sum += getChild(i).onLeafVoxelCount();
1557  }
1558  return sum;
1559 }
1560 
1561 
1562 template<typename ChildT>
1563 inline Index64
1565 {
1566  Index64 sum = 0;
1567  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1568  if (isChild(i)) sum += getChild(i).offLeafVoxelCount();
1569  }
1570  return sum;
1571 }
1572 
1573 template<typename ChildT>
1574 inline Index64
1576 {
1577  Index64 sum = 0;
1578  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1579  if (isChild(i)) {
1580  sum += getChild(i).onTileCount();
1581  } else if (isTileOn(i)) {
1582  sum += 1;
1583  }
1584  }
1585  return sum;
1586 }
1587 
1589 
1590 
1591 template<typename ChildT>
1592 inline bool
1593 RootNode<ChildT>::isValueOn(const Coord& xyz) const
1594 {
1595  MapCIter iter = this->findCoord(xyz);
1596  if (iter == mTable.end() || isTileOff(iter)) return false;
1597  return isTileOn(iter) ? true : getChild(iter).isValueOn(xyz);
1598 }
1599 
1600 template<typename ChildT>
1601 inline bool
1603 {
1604  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1605  if (isChild(i) ? getChild(i).hasActiveTiles() : getTile(i).active) return true;
1606  }
1607  return false;
1608 }
1609 
1610 template<typename ChildT>
1611 template<typename AccessorT>
1612 inline bool
1613 RootNode<ChildT>::isValueOnAndCache(const Coord& xyz, AccessorT& acc) const
1614 {
1615  MapCIter iter = this->findCoord(xyz);
1616  if (iter == mTable.end() || isTileOff(iter)) return false;
1617  if (isTileOn(iter)) return true;
1618  acc.insert(xyz, &getChild(iter));
1619  return getChild(iter).isValueOnAndCache(xyz, acc);
1620 }
1621 
1622 
1623 template<typename ChildT>
1624 inline const typename ChildT::ValueType&
1625 RootNode<ChildT>::getValue(const Coord& xyz) const
1626 {
1627  MapCIter iter = this->findCoord(xyz);
1628  return iter == mTable.end() ? mBackground
1629  : (isTile(iter) ? getTile(iter).value : getChild(iter).getValue(xyz));
1630 }
1631 
1632 template<typename ChildT>
1633 template<typename AccessorT>
1634 inline const typename ChildT::ValueType&
1635 RootNode<ChildT>::getValueAndCache(const Coord& xyz, AccessorT& acc) const
1636 {
1637  MapCIter iter = this->findCoord(xyz);
1638  if (iter == mTable.end()) return mBackground;
1639  if (isChild(iter)) {
1640  acc.insert(xyz, &getChild(iter));
1641  return getChild(iter).getValueAndCache(xyz, acc);
1642  }
1643  return getTile(iter).value;
1644 }
1645 
1646 
1647 template<typename ChildT>
1648 inline int
1649 RootNode<ChildT>::getValueDepth(const Coord& xyz) const
1650 {
1651  MapCIter iter = this->findCoord(xyz);
1652  return iter == mTable.end() ? -1
1653  : (isTile(iter) ? 0 : int(LEVEL) - int(getChild(iter).getValueLevel(xyz)));
1654 }
1655 
1656 template<typename ChildT>
1657 template<typename AccessorT>
1658 inline int
1659 RootNode<ChildT>::getValueDepthAndCache(const Coord& xyz, AccessorT& acc) const
1660 {
1661  MapCIter iter = this->findCoord(xyz);
1662  if (iter == mTable.end()) return -1;
1663  if (isTile(iter)) return 0;
1664  acc.insert(xyz, &getChild(iter));
1665  return int(LEVEL) - int(getChild(iter).getValueLevelAndCache(xyz, acc));
1666 }
1667 
1668 
1669 template<typename ChildT>
1670 inline void
1672 {
1673  MapIter iter = this->findCoord(xyz);
1674  if (iter != mTable.end() && !isTileOff(iter)) {
1675  if (isTileOn(iter)) {
1676  setChild(iter, *new ChildT(xyz, getTile(iter).value, /*active=*/true));
1677  }
1678  getChild(iter).setValueOff(xyz);
1679  }
1680 }
1681 
1682 
1683 template<typename ChildT>
1684 inline void
1685 RootNode<ChildT>::setActiveState(const Coord& xyz, bool on)
1686 {
1687  ChildT* child = NULL;
1688  MapIter iter = this->findCoord(xyz);
1689  if (iter == mTable.end()) {
1690  if (on) {
1691  child = new ChildT(xyz, mBackground);
1692  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1693  } else {
1694  // Nothing to do; (x, y, z) is background and therefore already inactive.
1695  }
1696  } else if (isChild(iter)) {
1697  child = &getChild(iter);
1698  } else if (on != getTile(iter).active) {
1699  child = new ChildT(xyz, getTile(iter).value, !on);
1700  setChild(iter, *child);
1701  }
1702  if (child) child->setActiveState(xyz, on);
1703 }
1704 
1705 template<typename ChildT>
1706 template<typename AccessorT>
1707 inline void
1708 RootNode<ChildT>::setActiveStateAndCache(const Coord& xyz, bool on, AccessorT& acc)
1709 {
1710  ChildT* child = NULL;
1711  MapIter iter = this->findCoord(xyz);
1712  if (iter == mTable.end()) {
1713  if (on) {
1714  child = new ChildT(xyz, mBackground);
1715  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1716  } else {
1717  // Nothing to do; (x, y, z) is background and therefore already inactive.
1718  }
1719  } else if (isChild(iter)) {
1720  child = &getChild(iter);
1721  } else if (on != getTile(iter).active) {
1722  child = new ChildT(xyz, getTile(iter).value, !on);
1723  setChild(iter, *child);
1724  }
1725  if (child) {
1726  acc.insert(xyz, child);
1727  child->setActiveStateAndCache(xyz, on, acc);
1728  }
1729 }
1730 
1731 
1732 template<typename ChildT>
1733 inline void
1734 RootNode<ChildT>::setValueOff(const Coord& xyz, const ValueType& value)
1735 {
1736  ChildT* child = NULL;
1737  MapIter iter = this->findCoord(xyz);
1738  if (iter == mTable.end()) {
1739  if (!math::isExactlyEqual(mBackground, value)) {
1740  child = new ChildT(xyz, mBackground);
1741  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1742  }
1743  } else if (isChild(iter)) {
1744  child = &getChild(iter);
1745  } else if (isTileOn(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1746  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1747  setChild(iter, *child);
1748  }
1749  if (child) child->setValueOff(xyz, value);
1750 }
1751 
1752 template<typename ChildT>
1753 template<typename AccessorT>
1754 inline void
1755 RootNode<ChildT>::setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1756 {
1757  ChildT* child = NULL;
1758  MapIter iter = this->findCoord(xyz);
1759  if (iter == mTable.end()) {
1760  if (!math::isExactlyEqual(mBackground, value)) {
1761  child = new ChildT(xyz, mBackground);
1762  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1763  }
1764  } else if (isChild(iter)) {
1765  child = &getChild(iter);
1766  } else if (isTileOn(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1767  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1768  setChild(iter, *child);
1769  }
1770  if (child) {
1771  acc.insert(xyz, child);
1772  child->setValueOffAndCache(xyz, value, acc);
1773  }
1774 }
1775 
1776 
1777 template<typename ChildT>
1778 inline void
1779 RootNode<ChildT>::setValueOn(const Coord& xyz, const ValueType& value)
1780 {
1781  ChildT* child = NULL;
1782  MapIter iter = this->findCoord(xyz);
1783  if (iter == mTable.end()) {
1784  child = new ChildT(xyz, mBackground);
1785  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1786  } else if (isChild(iter)) {
1787  child = &getChild(iter);
1788  } else if (isTileOff(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1789  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1790  setChild(iter, *child);
1791  }
1792  if (child) child->setValueOn(xyz, value);
1793 }
1794 
1795 template<typename ChildT>
1796 template<typename AccessorT>
1797 inline void
1798 RootNode<ChildT>::setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1799 {
1800  ChildT* child = NULL;
1801  MapIter iter = this->findCoord(xyz);
1802  if (iter == mTable.end()) {
1803  child = new ChildT(xyz, mBackground);
1804  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1805  } else if (isChild(iter)) {
1806  child = &getChild(iter);
1807  } else if (isTileOff(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1808  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1809  setChild(iter, *child);
1810  }
1811  if (child) {
1812  acc.insert(xyz, child);
1813  child->setValueAndCache(xyz, value, acc);
1814  }
1815 }
1816 
1817 
1818 template<typename ChildT>
1819 inline void
1820 RootNode<ChildT>::setValueOnly(const Coord& xyz, const ValueType& value)
1821 {
1822  ChildT* child = NULL;
1823  MapIter iter = this->findCoord(xyz);
1824  if (iter == mTable.end()) {
1825  child = new ChildT(xyz, mBackground);
1826  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1827  } else if (isChild(iter)) {
1828  child = &getChild(iter);
1829  } else if (!math::isExactlyEqual(getTile(iter).value, value)) {
1830  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1831  setChild(iter, *child);
1832  }
1833  if (child) child->setValueOnly(xyz, value);
1834 }
1835 
1836 template<typename ChildT>
1837 template<typename AccessorT>
1838 inline void
1839 RootNode<ChildT>::setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1840 {
1841  ChildT* child = NULL;
1842  MapIter iter = this->findCoord(xyz);
1843  if (iter == mTable.end()) {
1844  child = new ChildT(xyz, mBackground);
1845  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1846  } else if (isChild(iter)) {
1847  child = &getChild(iter);
1848  } else if (!math::isExactlyEqual(getTile(iter).value, value)) {
1849  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1850  setChild(iter, *child);
1851  }
1852  if (child) {
1853  acc.insert(xyz, child);
1854  child->setValueOnlyAndCache(xyz, value, acc);
1855  }
1856 }
1857 
1858 
1859 template<typename ChildT>
1860 template<typename ModifyOp>
1861 inline void
1862 RootNode<ChildT>::modifyValue(const Coord& xyz, const ModifyOp& op)
1863 {
1864  ChildT* child = NULL;
1865  MapIter iter = this->findCoord(xyz);
1866  if (iter == mTable.end()) {
1867  child = new ChildT(xyz, mBackground);
1868  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1869  } else if (isChild(iter)) {
1870  child = &getChild(iter);
1871  } else {
1872  // Need to create a child if the tile is inactive,
1873  // in order to activate voxel (x, y, z).
1874  bool createChild = isTileOff(iter);
1875  if (!createChild) {
1876  // Need to create a child if applying the functor
1877  // to the tile value produces a different value.
1878  const ValueType& tileVal = getTile(iter).value;
1879  ValueType modifiedVal = tileVal;
1880  op(modifiedVal);
1881  createChild = !math::isExactlyEqual(tileVal, modifiedVal);
1882  }
1883  if (createChild) {
1884  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1885  setChild(iter, *child);
1886  }
1887  }
1888  if (child) child->modifyValue(xyz, op);
1889 }
1890 
1891 template<typename ChildT>
1892 template<typename ModifyOp, typename AccessorT>
1893 inline void
1894 RootNode<ChildT>::modifyValueAndCache(const Coord& xyz, const ModifyOp& op, AccessorT& acc)
1895 {
1896  ChildT* child = NULL;
1897  MapIter iter = this->findCoord(xyz);
1898  if (iter == mTable.end()) {
1899  child = new ChildT(xyz, mBackground);
1900  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1901  } else if (isChild(iter)) {
1902  child = &getChild(iter);
1903  } else {
1904  // Need to create a child if the tile is inactive,
1905  // in order to activate voxel (x, y, z).
1906  bool createChild = isTileOff(iter);
1907  if (!createChild) {
1908  // Need to create a child if applying the functor
1909  // to the tile value produces a different value.
1910  const ValueType& tileVal = getTile(iter).value;
1911  ValueType modifiedVal = tileVal;
1912  op(modifiedVal);
1913  createChild = !math::isExactlyEqual(tileVal, modifiedVal);
1914  }
1915  if (createChild) {
1916  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1917  setChild(iter, *child);
1918  }
1919  }
1920  if (child) {
1921  acc.insert(xyz, child);
1922  child->modifyValueAndCache(xyz, op, acc);
1923  }
1924 }
1925 
1926 
1927 template<typename ChildT>
1928 template<typename ModifyOp>
1929 inline void
1930 RootNode<ChildT>::modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op)
1931 {
1932  ChildT* child = NULL;
1933  MapIter iter = this->findCoord(xyz);
1934  if (iter == mTable.end()) {
1935  child = new ChildT(xyz, mBackground);
1936  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1937  } else if (isChild(iter)) {
1938  child = &getChild(iter);
1939  } else {
1940  const Tile& tile = getTile(iter);
1941  bool modifiedState = tile.active;
1942  ValueType modifiedVal = tile.value;
1943  op(modifiedVal, modifiedState);
1944  // Need to create a child if applying the functor to the tile
1945  // produces a different value or active state.
1946  if (modifiedState != tile.active || !math::isExactlyEqual(modifiedVal, tile.value)) {
1947  child = new ChildT(xyz, tile.value, tile.active);
1948  setChild(iter, *child);
1949  }
1950  }
1951  if (child) child->modifyValueAndActiveState(xyz, op);
1952 }
1953 
1954 template<typename ChildT>
1955 template<typename ModifyOp, typename AccessorT>
1956 inline void
1958  const Coord& xyz, const ModifyOp& op, AccessorT& acc)
1959 {
1960  ChildT* child = NULL;
1961  MapIter iter = this->findCoord(xyz);
1962  if (iter == mTable.end()) {
1963  child = new ChildT(xyz, mBackground);
1964  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1965  } else if (isChild(iter)) {
1966  child = &getChild(iter);
1967  } else {
1968  const Tile& tile = getTile(iter);
1969  bool modifiedState = tile.active;
1970  ValueType modifiedVal = tile.value;
1971  op(modifiedVal, modifiedState);
1972  // Need to create a child if applying the functor to the tile
1973  // produces a different value or active state.
1974  if (modifiedState != tile.active || !math::isExactlyEqual(modifiedVal, tile.value)) {
1975  child = new ChildT(xyz, tile.value, tile.active);
1976  setChild(iter, *child);
1977  }
1978  }
1979  if (child) {
1980  acc.insert(xyz, child);
1981  child->modifyValueAndActiveStateAndCache(xyz, op, acc);
1982  }
1983 }
1984 
1985 
1986 template<typename ChildT>
1987 inline bool
1988 RootNode<ChildT>::probeValue(const Coord& xyz, ValueType& value) const
1989 {
1990  MapCIter iter = this->findCoord(xyz);
1991  if (iter == mTable.end()) {
1992  value = mBackground;
1993  return false;
1994  } else if (isChild(iter)) {
1995  return getChild(iter).probeValue(xyz, value);
1996  }
1997  value = getTile(iter).value;
1998  return isTileOn(iter);
1999 }
2000 
2001 template<typename ChildT>
2002 template<typename AccessorT>
2003 inline bool
2004 RootNode<ChildT>::probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT& acc) const
2005 {
2006  MapCIter iter = this->findCoord(xyz);
2007  if (iter == mTable.end()) {
2008  value = mBackground;
2009  return false;
2010  } else if (isChild(iter)) {
2011  acc.insert(xyz, &getChild(iter));
2012  return getChild(iter).probeValueAndCache(xyz, value, acc);
2013  }
2014  value = getTile(iter).value;
2015  return isTileOn(iter);
2016 }
2017 
2018 
2020 
2021 
2022 template<typename ChildT>
2023 inline void
2024 RootNode<ChildT>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
2025 {
2026  if (bbox.empty()) return;
2027 
2028  Coord xyz, tileMax;
2029  for (int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) {
2030  xyz.setX(x);
2031  for (int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) {
2032  xyz.setY(y);
2033  for (int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) {
2034  xyz.setZ(z);
2035 
2036  // Get the bounds of the tile that contains voxel (x, y, z).
2037  Coord tileMin = coordToKey(xyz);
2038  tileMax = tileMin.offsetBy(ChildT::DIM - 1);
2039 
2040  if (xyz != tileMin || Coord::lessThan(bbox.max(), tileMax)) {
2041  // If the box defined by (xyz, bbox.max()) doesn't completely enclose
2042  // the tile to which xyz belongs, create a child node (or retrieve
2043  // the existing one).
2044  ChildT* child = NULL;
2045  MapIter iter = this->findKey(tileMin);
2046  if (iter == mTable.end()) {
2047  // No child or tile exists. Create a child and initialize it
2048  // with the background value.
2049  child = new ChildT(xyz, mBackground);
2050  mTable[tileMin] = NodeStruct(*child);
2051  } else if (isTile(iter)) {
2052  // Replace the tile with a newly-created child that is initialized
2053  // with the tile's value and active state.
2054  const Tile& tile = getTile(iter);
2055  child = new ChildT(xyz, tile.value, tile.active);
2056  mTable[tileMin] = NodeStruct(*child);
2057  } else if (isChild(iter)) {
2058  child = &getChild(iter);
2059  }
2060  // Forward the fill request to the child.
2061  if (child) {
2062  child->fill(CoordBBox(xyz, Coord::minComponent(bbox.max(), tileMax)),
2063  value, active);
2064  }
2065  } else {
2066  // If the box given by (xyz, bbox.max()) completely encloses
2067  // the tile to which xyz belongs, create the tile (if it
2068  // doesn't already exist) and give it the fill value.
2069  MapIter iter = this->findOrAddCoord(tileMin);
2070  setTile(iter, Tile(value, active));
2071  }
2072  }
2073  }
2074  }
2075 }
2076 
2077 template<typename ChildT>
2078 template<typename DenseT>
2079 inline void
2080 RootNode<ChildT>::copyToDense(const CoordBBox& bbox, DenseT& dense) const
2081 {
2082  typedef typename DenseT::ValueType DenseValueType;
2083 
2084  const size_t xStride = dense.xStride(), yStride = dense.yStride(), zStride = dense.zStride();
2085  const Coord& min = dense.bbox().min();
2086  CoordBBox nodeBBox;
2087  for (Coord xyz = bbox.min(); xyz[0] <= bbox.max()[0]; xyz[0] = nodeBBox.max()[0] + 1) {
2088  for (xyz[1] = bbox.min()[1]; xyz[1] <= bbox.max()[1]; xyz[1] = nodeBBox.max()[1] + 1) {
2089  for (xyz[2] = bbox.min()[2]; xyz[2] <= bbox.max()[2]; xyz[2] = nodeBBox.max()[2] + 1) {
2090 
2091  // Get the coordinate bbox of the child node that contains voxel xyz.
2092  nodeBBox = CoordBBox::createCube(coordToKey(xyz), ChildT::DIM);
2093 
2094  // Get the coordinate bbox of the interection of inBBox and nodeBBox
2095  CoordBBox sub(xyz, Coord::minComponent(bbox.max(), nodeBBox.max()));
2096 
2097  MapCIter iter = this->findKey(nodeBBox.min());
2098  if (iter != mTable.end() && isChild(iter)) {//is a child
2099  getChild(iter).copyToDense(sub, dense);
2100  } else {//is background or a tile value
2101  const ValueType value = iter==mTable.end() ? mBackground : getTile(iter).value;
2102  sub.translate(-min);
2103  DenseValueType* a0 = dense.data() + zStride*sub.min()[2];
2104  for (Int32 x=sub.min()[0], ex=sub.max()[0]+1; x<ex; ++x) {
2105  DenseValueType* a1 = a0 + x*xStride;
2106  for (Int32 y=sub.min()[1], ey=sub.max()[1]+1; y<ey; ++y) {
2107  DenseValueType* a2 = a1 + y*yStride;
2108  for (Int32 z=sub.min()[2], ez=sub.max()[2]+1; z<ez; ++z, a2 += zStride) {
2109  *a2 = DenseValueType(value);
2110  }
2111  }
2112  }
2113  }
2114  }
2115  }
2116  }
2117 }
2118 
2120 
2121 
2122 template<typename ChildT>
2123 inline bool
2124 RootNode<ChildT>::writeTopology(std::ostream& os, bool toHalf) const
2125 {
2126  if (!toHalf) {
2127  os.write(reinterpret_cast<const char*>(&mBackground), sizeof(ValueType));
2128  } else {
2129  ValueType truncatedVal = io::truncateRealToHalf(mBackground);
2130  os.write(reinterpret_cast<const char*>(&truncatedVal), sizeof(ValueType));
2131  }
2132  io::setGridBackgroundValuePtr(os, &mBackground);
2133 
2134  const Index numTiles = this->getTileCount(), numChildren = this->getChildCount();
2135  os.write(reinterpret_cast<const char*>(&numTiles), sizeof(Index));
2136  os.write(reinterpret_cast<const char*>(&numChildren), sizeof(Index));
2137 
2138  if (numTiles == 0 && numChildren == 0) return false;
2139 
2140  // Write tiles.
2141  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2142  if (isChild(i)) continue;
2143  os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 * sizeof(Int32));
2144  os.write(reinterpret_cast<const char*>(&getTile(i).value), sizeof(ValueType));
2145  os.write(reinterpret_cast<const char*>(&getTile(i).active), sizeof(bool));
2146  }
2147  // Write child nodes.
2148  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2149  if (isTile(i)) continue;
2150  os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 * sizeof(Int32));
2151  getChild(i).writeTopology(os, toHalf);
2152  }
2153 
2154  return true; // not empty
2155 }
2156 
2157 
2158 template<typename ChildT>
2159 inline bool
2160 RootNode<ChildT>::readTopology(std::istream& is, bool fromHalf)
2161 {
2162  // Delete the existing tree.
2163  this->clearTable();
2164 
2166  // Read and convert an older-format RootNode.
2167 
2168  // For backward compatibility with older file formats, read both
2169  // outside and inside background values.
2170  is.read(reinterpret_cast<char*>(&mBackground), sizeof(ValueType));
2171  ValueType inside;
2172  is.read(reinterpret_cast<char*>(&inside), sizeof(ValueType));
2173 
2174  io::setGridBackgroundValuePtr(is, &mBackground);
2175 
2176  // Read the index range.
2177  Coord rangeMin, rangeMax;
2178  is.read(reinterpret_cast<char*>(rangeMin.asPointer()), 3 * sizeof(Int32));
2179  is.read(reinterpret_cast<char*>(rangeMax.asPointer()), 3 * sizeof(Int32));
2180 
2181  this->initTable();
2182  Index tableSize = 0, log2Dim[4] = { 0, 0, 0, 0 };
2183  Int32 offset[3];
2184  for (int i = 0; i < 3; ++i) {
2185  offset[i] = rangeMin[i] >> ChildT::TOTAL;
2186  rangeMin[i] = offset[i] << ChildT::TOTAL;
2187  log2Dim[i] = 1 + util::FindHighestOn((rangeMax[i] >> ChildT::TOTAL) - offset[i]);
2188  tableSize += log2Dim[i];
2189  rangeMax[i] = (((1 << log2Dim[i]) + offset[i]) << ChildT::TOTAL) - 1;
2190  }
2191  log2Dim[3] = log2Dim[1] + log2Dim[2];
2192  tableSize = 1U << tableSize;
2193 
2194  // Read masks.
2195  util::RootNodeMask childMask(tableSize), valueMask(tableSize);
2196  childMask.load(is);
2197  valueMask.load(is);
2198 
2199  // Read child nodes/values.
2200  for (Index i = 0; i < tableSize; ++i) {
2201  // Compute origin = offset2coord(i).
2202  Index n = i;
2203  Coord origin;
2204  origin[0] = (n >> log2Dim[3]) + offset[0];
2205  n &= (1U << log2Dim[3]) - 1;
2206  origin[1] = (n >> log2Dim[2]) + offset[1];
2207  origin[2] = (n & ((1U << log2Dim[2]) - 1)) + offset[1];
2208  origin <<= ChildT::TOTAL;
2209 
2210  if (childMask.isOn(i)) {
2211  // Read in and insert a child node.
2212 #ifdef OPENVDB_2_ABI_COMPATIBLE
2213  ChildT* child = new ChildT(origin, mBackground);
2214 #else
2215  ChildT* child = new ChildT(PartialCreate(), origin, mBackground);
2216 #endif
2217  child->readTopology(is);
2218  mTable[origin] = NodeStruct(*child);
2219  } else {
2220  // Read in a tile value and insert a tile, but only if the value
2221  // is either active or non-background.
2222  ValueType value;
2223  is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
2224  if (valueMask.isOn(i) || (!math::isApproxEqual(value, mBackground))) {
2225  mTable[origin] = NodeStruct(Tile(value, valueMask.isOn(i)));
2226  }
2227  }
2228  }
2229  return true;
2230  }
2231 
2232  // Read a RootNode that was stored in the current format.
2233 
2234  is.read(reinterpret_cast<char*>(&mBackground), sizeof(ValueType));
2235  io::setGridBackgroundValuePtr(is, &mBackground);
2236 
2237  Index numTiles = 0, numChildren = 0;
2238  is.read(reinterpret_cast<char*>(&numTiles), sizeof(Index));
2239  is.read(reinterpret_cast<char*>(&numChildren), sizeof(Index));
2240 
2241  if (numTiles == 0 && numChildren == 0) return false;
2242 
2243  Int32 vec[3];
2244  ValueType value;
2245  bool active;
2246 
2247  // Read tiles.
2248  for (Index n = 0; n < numTiles; ++n) {
2249  is.read(reinterpret_cast<char*>(vec), 3 * sizeof(Int32));
2250  is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
2251  is.read(reinterpret_cast<char*>(&active), sizeof(bool));
2252  mTable[Coord(vec)] = NodeStruct(Tile(value, active));
2253  }
2254 
2255  // Read child nodes.
2256  for (Index n = 0; n < numChildren; ++n) {
2257  is.read(reinterpret_cast<char*>(vec), 3 * sizeof(Int32));
2258  Coord origin(vec);
2259 #ifdef OPENVDB_2_ABI_COMPATIBLE
2260  ChildT* child = new ChildT(origin, mBackground);
2261 #else
2262  ChildT* child = new ChildT(PartialCreate(), origin, mBackground);
2263 #endif
2264  child->readTopology(is, fromHalf);
2265  mTable[Coord(vec)] = NodeStruct(*child);
2266  }
2267 
2268  return true; // not empty
2269 }
2270 
2271 
2272 template<typename ChildT>
2273 inline void
2274 RootNode<ChildT>::writeBuffers(std::ostream& os, bool toHalf) const
2275 {
2276  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2277  if (isChild(i)) getChild(i).writeBuffers(os, toHalf);
2278  }
2279 }
2280 
2281 
2282 template<typename ChildT>
2283 inline void
2284 RootNode<ChildT>::readBuffers(std::istream& is, bool fromHalf)
2285 {
2286  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2287  if (isChild(i)) getChild(i).readBuffers(is, fromHalf);
2288  }
2289 }
2290 
2291 
2292 template<typename ChildT>
2293 inline void
2294 RootNode<ChildT>::readBuffers(std::istream& is, const CoordBBox& clipBBox, bool fromHalf)
2295 {
2296  const Tile bgTile(mBackground, /*active=*/false);
2297 
2298  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2299  if (isChild(i)) {
2300  // Stream in and clip the branch rooted at this child.
2301  // (We can't skip over children that lie outside the clipping region,
2302  // because buffers are serialized in depth-first order and need to be
2303  // unserialized in the same order.)
2304  ChildT& child = getChild(i);
2305  child.readBuffers(is, clipBBox, fromHalf);
2306  }
2307  }
2308  // Clip root-level tiles and prune children that were clipped.
2309  this->clip(clipBBox);
2310 }
2311 
2312 
2314 
2315 
2316 template<typename ChildT>
2317 inline void
2318 RootNode<ChildT>::clip(const CoordBBox& clipBBox)
2319 {
2320  const Tile bgTile(mBackground, /*active=*/false);
2321 
2322  // Iterate over a copy of this node's table so that we can modify the original.
2323  // (Copying the table copies child node pointers, not the nodes themselves.)
2324  MapType copyOfTable(mTable);
2325  for (MapIter i = copyOfTable.begin(), e = copyOfTable.end(); i != e; ++i) {
2326  const Coord& xyz = i->first; // tile or child origin
2327  CoordBBox tileBBox(xyz, xyz.offsetBy(ChildT::DIM - 1)); // tile or child bounds
2328  if (!clipBBox.hasOverlap(tileBBox)) {
2329  // This table entry lies completely outside the clipping region. Delete it.
2330  setTile(this->findCoord(xyz), bgTile); // delete any existing child node first
2331  mTable.erase(xyz);
2332  } else if (!clipBBox.isInside(tileBBox)) {
2333  // This table entry does not lie completely inside the clipping region
2334  // and must be clipped.
2335  if (isChild(i)) {
2336  getChild(i).clip(clipBBox, mBackground);
2337  } else {
2338  // Replace this tile with a background tile, then fill the clip region
2339  // with the tile's original value. (This might create a child branch.)
2340  tileBBox.intersect(clipBBox);
2341  const Tile& origTile = getTile(i);
2342  setTile(this->findCoord(xyz), bgTile);
2343  this->fill(tileBBox, origTile.value, origTile.active);
2344  }
2345  } else {
2346  // This table entry lies completely inside the clipping region. Leave it intact.
2347  }
2348  }
2349  this->prune(); // also erases root-level background tiles
2350 }
2351 
2352 
2354 
2355 
2356 template<typename ChildT>
2357 inline void
2358 RootNode<ChildT>::prune(const ValueType& tolerance)
2359 {
2360  bool state = false;
2361  ValueType value = zeroVal<ValueType>();
2362  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2363  if (this->isTile(i)) continue;
2364  this->getChild(i).prune(tolerance);
2365  if (this->getChild(i).isConstant(value, state, tolerance)) {
2366  this->setTile(i, Tile(value, state));
2367  }
2368  }
2369  this->eraseBackgroundTiles();
2370 }
2371 
2372 
2374 
2375 
2376 template<typename ChildT>
2377 template<typename NodeT>
2378 inline NodeT*
2379 RootNode<ChildT>::stealNode(const Coord& xyz, const ValueType& value, bool state)
2380 {
2381  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2382  NodeT::LEVEL > ChildT::LEVEL) return NULL;
2384  MapIter iter = this->findCoord(xyz);
2385  if (iter == mTable.end() || isTile(iter)) return NULL;
2386  return (boost::is_same<NodeT, ChildT>::value)
2387  ? reinterpret_cast<NodeT*>(&stealChild(iter, Tile(value, state)))
2388  : getChild(iter).template stealNode<NodeT>(xyz, value, state);
2390 }
2391 
2392 
2394 
2395 
2396 template<typename ChildT>
2397 inline void
2398 RootNode<ChildT>::addLeaf(LeafNodeType* leaf)
2399 {
2400  if (leaf == NULL) return;
2401  ChildT* child = NULL;
2402  const Coord& xyz = leaf->origin();
2403  MapIter iter = this->findCoord(xyz);
2404  if (iter == mTable.end()) {
2405  if (ChildT::LEVEL>0) {
2406  child = new ChildT(xyz, mBackground, false);
2407  } else {
2408  child = reinterpret_cast<ChildT*>(leaf);
2409  }
2410  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2411  } else if (isChild(iter)) {
2412  if (ChildT::LEVEL>0) {
2413  child = &getChild(iter);
2414  } else {
2415  child = reinterpret_cast<ChildT*>(leaf);
2416  setChild(iter, *child);//this also deletes the existing child node
2417  }
2418  } else {//tile
2419  if (ChildT::LEVEL>0) {
2420  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2421  } else {
2422  child = reinterpret_cast<ChildT*>(leaf);
2423  }
2424  setChild(iter, *child);
2425  }
2426  child->addLeaf(leaf);
2427 }
2428 
2429 
2430 template<typename ChildT>
2431 template<typename AccessorT>
2432 inline void
2433 RootNode<ChildT>::addLeafAndCache(LeafNodeType* leaf, AccessorT& acc)
2434 {
2435  if (leaf == NULL) return;
2436  ChildT* child = NULL;
2437  const Coord& xyz = leaf->origin();
2438  MapIter iter = this->findCoord(xyz);
2439  if (iter == mTable.end()) {
2440  if (ChildT::LEVEL>0) {
2441  child = new ChildT(xyz, mBackground, false);
2442  } else {
2443  child = reinterpret_cast<ChildT*>(leaf);
2444  }
2445  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2446  } else if (isChild(iter)) {
2447  if (ChildT::LEVEL>0) {
2448  child = &getChild(iter);
2449  } else {
2450  child = reinterpret_cast<ChildT*>(leaf);
2451  setChild(iter, *child);//this also deletes the existing child node
2452  }
2453  } else {//tile
2454  if (ChildT::LEVEL>0) {
2455  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2456  } else {
2457  child = reinterpret_cast<ChildT*>(leaf);
2458  }
2459  setChild(iter, *child);
2460  }
2461  acc.insert(xyz, child);
2462  child->addLeafAndCache(leaf, acc);
2463 }
2464 
2465 template<typename ChildT>
2466 inline void
2467 RootNode<ChildT>::addTile(const Coord& xyz, const ValueType& value, bool state)
2468 {
2469  MapIter iter = this->findCoord(xyz);
2470  if (iter == mTable.end()) {//background
2471  mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2472  } else {//child or tile
2473  setTile(iter, Tile(value, state));//this also deletes the existing child node
2474  }
2475 }
2476 
2477 template<typename ChildT>
2478 inline void
2479 RootNode<ChildT>::addTile(Index level, const Coord& xyz,
2480  const ValueType& value, bool state)
2481 {
2482  if (LEVEL >= level) {
2483  MapIter iter = this->findCoord(xyz);
2484  if (iter == mTable.end()) {//background
2485  if (LEVEL > level) {
2486  ChildT* child = new ChildT(xyz, mBackground, false);
2487  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2488  child->addTile(level, xyz, value, state);
2489  } else {
2490  mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2491  }
2492  } else if (isChild(iter)) {//child
2493  if (LEVEL > level) {
2494  getChild(iter).addTile(level, xyz, value, state);
2495  } else {
2496  setTile(iter, Tile(value, state));//this also deletes the existing child node
2497  }
2498  } else {//tile
2499  if (LEVEL > level) {
2500  ChildT* child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2501  setChild(iter, *child);
2502  child->addTile(level, xyz, value, state);
2503  } else {
2504  setTile(iter, Tile(value, state));
2505  }
2506  }
2507  }
2508 }
2509 
2510 
2511 template<typename ChildT>
2512 template<typename AccessorT>
2513 inline void
2514 RootNode<ChildT>::addTileAndCache(Index level, const Coord& xyz, const ValueType& value,
2515  bool state, AccessorT& acc)
2516 {
2517  if (LEVEL >= level) {
2518  MapIter iter = this->findCoord(xyz);
2519  if (iter == mTable.end()) {//background
2520  if (LEVEL > level) {
2521  ChildT* child = new ChildT(xyz, mBackground, false);
2522  acc.insert(xyz, child);
2523  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2524  child->addTileAndCache(level, xyz, value, state, acc);
2525  } else {
2526  mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2527  }
2528  } else if (isChild(iter)) {//child
2529  if (LEVEL > level) {
2530  ChildT* child = &getChild(iter);
2531  acc.insert(xyz, child);
2532  child->addTileAndCache(level, xyz, value, state, acc);
2533  } else {
2534  setTile(iter, Tile(value, state));//this also deletes the existing child node
2535  }
2536  } else {//tile
2537  if (LEVEL > level) {
2538  ChildT* child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2539  acc.insert(xyz, child);
2540  setChild(iter, *child);
2541  child->addTileAndCache(level, xyz, value, state, acc);
2542  } else {
2543  setTile(iter, Tile(value, state));
2544  }
2545  }
2546  }
2547 }
2548 
2549 
2551 
2552 
2553 template<typename ChildT>
2554 inline typename ChildT::LeafNodeType*
2556 {
2557  ChildT* child = NULL;
2558  MapIter iter = this->findCoord(xyz);
2559  if (iter == mTable.end()) {
2560  child = new ChildT(xyz, mBackground, false);
2561  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2562  } else if (isChild(iter)) {
2563  child = &getChild(iter);
2564  } else {
2565  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2566  setChild(iter, *child);
2567  }
2568  return child->touchLeaf(xyz);
2569 }
2570 
2571 
2572 template<typename ChildT>
2573 template<typename AccessorT>
2574 inline typename ChildT::LeafNodeType*
2575 RootNode<ChildT>::touchLeafAndCache(const Coord& xyz, AccessorT& acc)
2576 {
2577  ChildT* child = NULL;
2578  MapIter iter = this->findCoord(xyz);
2579  if (iter == mTable.end()) {
2580  child = new ChildT(xyz, mBackground, false);
2581  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2582  } else if (isChild(iter)) {
2583  child = &getChild(iter);
2584  } else {
2585  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2586  setChild(iter, *child);
2587  }
2588  acc.insert(xyz, child);
2589  return child->touchLeafAndCache(xyz, acc);
2590 }
2591 
2592 
2594 
2595 
2596 template<typename ChildT>
2597 template<typename NodeT>
2598 inline NodeT*
2600 {
2601  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2602  NodeT::LEVEL > ChildT::LEVEL) return NULL;
2604  MapIter iter = this->findCoord(xyz);
2605  if (iter == mTable.end() || isTile(iter)) return NULL;
2606  ChildT* child = &getChild(iter);
2607  return (boost::is_same<NodeT, ChildT>::value)
2608  ? reinterpret_cast<NodeT*>(child)
2609  : child->template probeNode<NodeT>(xyz);
2611 }
2612 
2613 
2614 template<typename ChildT>
2615 template<typename NodeT>
2616 inline const NodeT*
2617 RootNode<ChildT>::probeConstNode(const Coord& xyz) const
2618 {
2619  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2620  NodeT::LEVEL > ChildT::LEVEL) return NULL;
2622  MapCIter iter = this->findCoord(xyz);
2623  if (iter == mTable.end() || isTile(iter)) return NULL;
2624  const ChildT* child = &getChild(iter);
2625  return (boost::is_same<NodeT, ChildT>::value)
2626  ? reinterpret_cast<const NodeT*>(child)
2627  : child->template probeConstNode<NodeT>(xyz);
2629 }
2630 
2631 
2632 template<typename ChildT>
2633 inline typename ChildT::LeafNodeType*
2635 {
2636  return this->template probeNode<LeafNodeType>(xyz);
2637 }
2638 
2639 
2640 template<typename ChildT>
2641 inline const typename ChildT::LeafNodeType*
2642 RootNode<ChildT>::probeConstLeaf(const Coord& xyz) const
2643 {
2644  return this->template probeConstNode<LeafNodeType>(xyz);
2645 }
2646 
2647 
2648 template<typename ChildT>
2649 template<typename AccessorT>
2650 inline typename ChildT::LeafNodeType*
2651 RootNode<ChildT>::probeLeafAndCache(const Coord& xyz, AccessorT& acc)
2652 {
2653  return this->template probeNodeAndCache<LeafNodeType>(xyz, acc);
2654 }
2655 
2656 
2657 template<typename ChildT>
2658 template<typename AccessorT>
2659 inline const typename ChildT::LeafNodeType*
2660 RootNode<ChildT>::probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const
2661 {
2662  return this->template probeConstNodeAndCache<LeafNodeType>(xyz, acc);
2663 }
2664 
2665 
2666 template<typename ChildT>
2667 template<typename AccessorT>
2668 inline const typename ChildT::LeafNodeType*
2669 RootNode<ChildT>::probeLeafAndCache(const Coord& xyz, AccessorT& acc) const
2670 {
2671  return this->probeConstLeafAndCache(xyz, acc);
2672 }
2673 
2674 
2675 template<typename ChildT>
2676 template<typename NodeT, typename AccessorT>
2677 inline NodeT*
2678 RootNode<ChildT>::probeNodeAndCache(const Coord& xyz, AccessorT& acc)
2679 {
2680  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2681  NodeT::LEVEL > ChildT::LEVEL) return NULL;
2683  MapIter iter = this->findCoord(xyz);
2684  if (iter == mTable.end() || isTile(iter)) return NULL;
2685  ChildT* child = &getChild(iter);
2686  acc.insert(xyz, child);
2687  return (boost::is_same<NodeT, ChildT>::value)
2688  ? reinterpret_cast<NodeT*>(child)
2689  : child->template probeNodeAndCache<NodeT>(xyz, acc);
2691 }
2692 
2693 
2694 template<typename ChildT>
2695 template<typename NodeT,typename AccessorT>
2696 inline const NodeT*
2697 RootNode<ChildT>::probeConstNodeAndCache(const Coord& xyz, AccessorT& acc) const
2698 {
2699  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2700  NodeT::LEVEL > ChildT::LEVEL) return NULL;
2702  MapCIter iter = this->findCoord(xyz);
2703  if (iter == mTable.end() || isTile(iter)) return NULL;
2704  const ChildT* child = &getChild(iter);
2705  acc.insert(xyz, child);
2706  return (boost::is_same<NodeT, ChildT>::value)
2707  ? reinterpret_cast<const NodeT*>(child)
2708  : child->template probeConstNodeAndCache<NodeT>(xyz, acc);
2710 }
2711 
2712 
2714 
2715 template<typename ChildT>
2716 template<typename ArrayT>
2717 inline void
2719 {
2720  typedef typename ArrayT::value_type NodePtr;
2721  BOOST_STATIC_ASSERT(boost::is_pointer<NodePtr>::value);
2722  typedef typename boost::remove_pointer<NodePtr>::type NodeType;
2723  typedef typename boost::remove_const<NodeType>::type NonConstNodeType;
2724  typedef typename boost::mpl::contains<NodeChainType, NonConstNodeType>::type result;
2725  BOOST_STATIC_ASSERT(result::value);
2726  typedef typename boost::mpl::if_<boost::is_const<NodeType>,
2727  const ChildT, ChildT>::type ArrayChildT;
2728 
2729  for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2730  if (ChildT* child = iter->second.child) {
2732  if (boost::is_same<NodePtr, ArrayChildT*>::value) {
2733  array.push_back(reinterpret_cast<NodePtr>(iter->second.child));
2734  } else {
2735  child->getNodes(array);//descent
2736  }
2738  }
2739  }
2740 }
2741 
2742 template<typename ChildT>
2743 template<typename ArrayT>
2744 inline void
2745 RootNode<ChildT>::getNodes(ArrayT& array) const
2746 {
2747  typedef typename ArrayT::value_type NodePtr;
2748  BOOST_STATIC_ASSERT(boost::is_pointer<NodePtr>::value);
2749  typedef typename boost::remove_pointer<NodePtr>::type NodeType;
2750  BOOST_STATIC_ASSERT(boost::is_const<NodeType>::value);
2751  typedef typename boost::remove_const<NodeType>::type NonConstNodeType;
2752  typedef typename boost::mpl::contains<NodeChainType, NonConstNodeType>::type result;
2753  BOOST_STATIC_ASSERT(result::value);
2754 
2755  for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2756  if (const ChildNodeType *child = iter->second.child) {
2758  if (boost::is_same<NodePtr, const ChildT*>::value) {
2759  array.push_back(reinterpret_cast<NodePtr>(iter->second.child));
2760  } else {
2761  child->getNodes(array);//descent
2762  }
2764  }
2765  }
2766 }
2767 
2768 
2770 
2771 
2772 template<typename ChildT>
2773 inline void
2775 {
2776  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2777  if (this->isTileOff(i)) continue;
2778  ChildT* child = i->second.child;
2779  if (child==NULL) {
2780  child = new ChildT(i->first, this->getTile(i).value, true);
2781  i->second.child = child;
2782  }
2783  child->voxelizeActiveTiles();
2784  }
2785 }
2786 
2787 
2789 
2790 
2791 template<typename ChildT>
2792 template<MergePolicy Policy>
2793 inline void
2795 {
2797 
2798  switch (Policy) {
2799 
2800  default:
2801  case MERGE_ACTIVE_STATES:
2802  for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2803  MapIter j = mTable.find(i->first);
2804  if (other.isChild(i)) {
2805  if (j == mTable.end()) { // insert other node's child
2806  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
2807  child.resetBackground(other.mBackground, mBackground);
2808  mTable[i->first] = NodeStruct(child);
2809  } else if (isTile(j)) {
2810  if (isTileOff(j)) { // replace inactive tile with other node's child
2811  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
2812  child.resetBackground(other.mBackground, mBackground);
2813  setChild(j, child);
2814  }
2815  } else { // merge both child nodes
2816  getChild(j).template merge<MERGE_ACTIVE_STATES>(getChild(i),
2817  other.mBackground, mBackground);
2818  }
2819  } else if (other.isTileOn(i)) {
2820  if (j == mTable.end()) { // insert other node's active tile
2821  mTable[i->first] = i->second;
2822  } else if (!isTileOn(j)) {
2823  // Replace anything except an active tile with the other node's active tile.
2824  setTile(j, Tile(other.getTile(i).value, true));
2825  }
2826  }
2827  }
2828  break;
2829 
2830  case MERGE_NODES:
2831  for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2832  MapIter j = mTable.find(i->first);
2833  if (other.isChild(i)) {
2834  if (j == mTable.end()) { // insert other node's child
2835  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
2836  child.resetBackground(other.mBackground, mBackground);
2837  mTable[i->first] = NodeStruct(child);
2838  } else if (isTile(j)) { // replace tile with other node's child
2839  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
2840  child.resetBackground(other.mBackground, mBackground);
2841  setChild(j, child);
2842  } else { // merge both child nodes
2843  getChild(j).template merge<MERGE_NODES>(
2844  getChild(i), other.mBackground, mBackground);
2845  }
2846  }
2847  }
2848  break;
2849 
2851  for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2852  MapIter j = mTable.find(i->first);
2853  if (other.isChild(i)) {
2854  if (j == mTable.end()) {
2855  // Steal and insert the other node's child.
2856  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
2857  child.resetBackground(other.mBackground, mBackground);
2858  mTable[i->first] = NodeStruct(child);
2859  } else if (isTile(j)) {
2860  // Replace this node's tile with the other node's child.
2861  ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
2862  child.resetBackground(other.mBackground, mBackground);
2863  const Tile tile = getTile(j);
2864  setChild(j, child);
2865  if (tile.active) {
2866  // Merge the other node's child with this node's active tile.
2867  child.template merge<MERGE_ACTIVE_STATES_AND_NODES>(
2868  tile.value, tile.active);
2869  }
2870  } else /*if (isChild(j))*/ {
2871  // Merge the other node's child into this node's child.
2872  getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(getChild(i),
2873  other.mBackground, mBackground);
2874  }
2875  } else if (other.isTileOn(i)) {
2876  if (j == mTable.end()) {
2877  // Insert a copy of the other node's active tile.
2878  mTable[i->first] = i->second;
2879  } else if (isTileOff(j)) {
2880  // Replace this node's inactive tile with a copy of the other's active tile.
2881  setTile(j, Tile(other.getTile(i).value, true));
2882  } else if (isChild(j)) {
2883  // Merge the other node's active tile into this node's child.
2884  const Tile& tile = getTile(i);
2885  getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(
2886  tile.value, tile.active);
2887  }
2888  } // else if (other.isTileOff(i)) {} // ignore the other node's inactive tiles
2889  }
2890  break;
2891  }
2892 
2893  // Empty the other tree so as not to leave it in a partially cannibalized state.
2894  other.clear();
2895 
2897 }
2898 
2899 
2901 
2902 
2903 template<typename ChildT>
2904 template<typename OtherChildType>
2905 inline void
2907 {
2908  typedef RootNode<OtherChildType> OtherRootT;
2909  typedef typename OtherRootT::MapCIter OtherCIterT;
2910 
2911  enforceSameConfiguration(other);
2912 
2913  for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2914  MapIter j = mTable.find(i->first);
2915  if (other.isChild(i)) {
2916  if (j == mTable.end()) { // create child branch with identical topology
2917  mTable[i->first] = NodeStruct(
2918  *(new ChildT(other.getChild(i), mBackground, TopologyCopy())));
2919  } else if (this->isChild(j)) { // union with child branch
2920  this->getChild(j).topologyUnion(other.getChild(i));
2921  } else {// this is a tile so replace it with a child branch with identical topology
2922  ChildT* child = new ChildT(
2923  other.getChild(i), this->getTile(j).value, TopologyCopy());
2924  if (this->isTileOn(j)) child->setValuesOn();//this is an active tile
2925  this->setChild(j, *child);
2926  }
2927  } else if (other.isTileOn(i)) { // other is an active tile
2928  if (j == mTable.end()) { // insert an active tile
2929  mTable[i->first] = NodeStruct(Tile(mBackground, true));
2930  } else if (this->isChild(j)) {
2931  this->getChild(j).setValuesOn();
2932  } else if (this->isTileOff(j)) {
2933  this->setTile(j, Tile(this->getTile(j).value, true));
2934  }
2935  }
2936  }
2937 }
2938 
2939 template<typename ChildT>
2940 template<typename OtherChildType>
2941 inline void
2943 {
2944  typedef RootNode<OtherChildType> OtherRootT;
2945  typedef typename OtherRootT::MapCIter OtherCIterT;
2946 
2947  enforceSameConfiguration(other);
2948 
2949  std::set<Coord> tmp;//keys to erase
2950  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2951  OtherCIterT j = other.mTable.find(i->first);
2952  if (this->isChild(i)) {
2953  if (j == other.mTable.end() || other.isTileOff(j)) {
2954  tmp.insert(i->first);//delete child branch
2955  } else if (other.isChild(j)) { // intersect with child branch
2956  this->getChild(i).topologyIntersection(other.getChild(j), mBackground);
2957  }
2958  } else if (this->isTileOn(i)) {
2959  if (j == other.mTable.end() || other.isTileOff(j)) {
2960  this->setTile(i, Tile(this->getTile(i).value, false));//turn inactive
2961  } else if (other.isChild(j)) { //replace with a child branch with identical topology
2962  ChildT* child =
2963  new ChildT(other.getChild(j), this->getTile(i).value, TopologyCopy());
2964  this->setChild(i, *child);
2965  }
2966  }
2967  }
2968  for (std::set<Coord>::iterator i = tmp.begin(), e = tmp.end(); i != e; ++i) {
2969  MapIter it = this->findCoord(*i);
2970  setTile(it, Tile()); // delete any existing child node first
2971  mTable.erase(it);
2972  }
2973 }
2974 
2975 template<typename ChildT>
2976 template<typename OtherChildType>
2977 inline void
2979 {
2980  typedef RootNode<OtherChildType> OtherRootT;
2981  typedef typename OtherRootT::MapCIter OtherCIterT;
2982 
2983  enforceSameConfiguration(other);
2984 
2985  for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2986  MapIter j = mTable.find(i->first);
2987  if (other.isChild(i)) {
2988  if (j == mTable.end() || this->isTileOff(j)) {
2989  //do nothing
2990  } else if (this->isChild(j)) { // difference with child branch
2991  this->getChild(j).topologyDifference(other.getChild(i), mBackground);
2992  } else if (this->isTileOn(j)) {
2993  // this is an active tile so create a child node and descent
2994  ChildT* child = new ChildT(j->first, this->getTile(j).value, true);
2995  child->topologyDifference(other.getChild(i), mBackground);
2996  this->setChild(j, *child);
2997  }
2998  } else if (other.isTileOn(i)) { // other is an active tile
2999  if (j == mTable.end() || this->isTileOff(j)) {
3000  // do nothing
3001  } else if (this->isChild(j)) {
3002  setTile(j, Tile()); // delete any existing child node first
3003  mTable.erase(j);
3004  } else if (this->isTileOn(j)) {
3005  this->setTile(j, Tile(this->getTile(j).value, false));
3006  }
3007  }
3008  }
3009 }
3010 
3012 
3013 
3014 template<typename ChildT>
3015 template<typename CombineOp>
3016 inline void
3017 RootNode<ChildT>::combine(RootNode& other, CombineOp& op, bool prune)
3018 {
3020 
3021  CoordSet keys;
3022  this->insertKeys(keys);
3023  other.insertKeys(keys);
3024 
3025  for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3026  MapIter iter = findOrAddCoord(*i), otherIter = other.findOrAddCoord(*i);
3027  if (isTile(iter) && isTile(otherIter)) {
3028  // Both this node and the other node have constant values (tiles).
3029  // Combine the two values and store the result as this node's new tile value.
3030  op(args.setARef(getTile(iter).value)
3031  .setAIsActive(isTileOn(iter))
3032  .setBRef(getTile(otherIter).value)
3033  .setBIsActive(isTileOn(otherIter)));
3034  setTile(iter, Tile(args.result(), args.resultIsActive()));
3035 
3036  } else if (isChild(iter) && isTile(otherIter)) {
3037  // Combine this node's child with the other node's constant value.
3038  ChildT& child = getChild(iter);
3039  child.combine(getTile(otherIter).value, isTileOn(otherIter), op);
3040 
3041  } else if (isTile(iter) && isChild(otherIter)) {
3042  // Combine this node's constant value with the other node's child,
3043  // but use a new functor in which the A and B values are swapped,
3044  // since the constant value is the A value, not the B value.
3046  ChildT& child = getChild(otherIter);
3047  child.combine(getTile(iter).value, isTileOn(iter), swappedOp);
3048 
3049  // Steal the other node's child.
3050  setChild(iter, stealChild(otherIter, Tile()));
3051 
3052  } else /*if (isChild(iter) && isChild(otherIter))*/ {
3053  // Combine this node's child with the other node's child.
3054  ChildT &child = getChild(iter), &otherChild = getChild(otherIter);
3055  child.combine(otherChild, op);
3056  }
3057  if (prune && isChild(iter)) getChild(iter).prune();
3058  }
3059 
3060  // Combine background values.
3061  op(args.setARef(mBackground).setBRef(other.mBackground));
3062  mBackground = args.result();
3063 
3064  // Empty the other tree so as not to leave it in a partially cannibalized state.
3065  other.clear();
3066 }
3067 
3068 
3070 
3071 
3072 // This helper class is a friend of RootNode and is needed so that combine2
3073 // can be specialized for compatible and incompatible pairs of RootNode types.
3074 template<typename CombineOp, typename RootT, typename OtherRootT, bool Compatible = false>
3075 struct RootNodeCombineHelper
3076 {
3077  static inline void combine2(RootT& self, const RootT&, const OtherRootT& other1,
3078  CombineOp&, bool)
3079  {
3080  // If the two root nodes have different configurations or incompatible ValueTypes,
3081  // throw an exception.
3082  self.enforceSameConfiguration(other1);
3083  self.enforceCompatibleValueTypes(other1);
3084  // One of the above two tests should throw, so we should never get here:
3085  std::ostringstream ostr;
3086  ostr << "cannot combine a " << typeid(OtherRootT).name()
3087  << " into a " << typeid(RootT).name();
3088  OPENVDB_THROW(TypeError, ostr.str());
3089  }
3090 };
3091 
3092 // Specialization for root nodes of compatible types
3093 template<typename CombineOp, typename RootT, typename OtherRootT>
3094 struct RootNodeCombineHelper<CombineOp, RootT, OtherRootT, /*Compatible=*/true>
3095 {
3096  static inline void combine2(RootT& self, const RootT& other0, const OtherRootT& other1,
3097  CombineOp& op, bool prune)
3098  {
3099  self.doCombine2(other0, other1, op, prune);
3100  }
3101 };
3102 
3103 
3104 template<typename ChildT>
3105 template<typename CombineOp, typename OtherRootNode>
3106 inline void
3107 RootNode<ChildT>::combine2(const RootNode& other0, const OtherRootNode& other1,
3108  CombineOp& op, bool prune)
3109 {
3110  typedef typename OtherRootNode::ValueType OtherValueType;
3111  static const bool compatible = (SameConfiguration<OtherRootNode>::value
3112  && CanConvertType</*from=*/OtherValueType, /*to=*/ValueType>::value);
3114  *this, other0, other1, op, prune);
3115 }
3116 
3117 
3118 template<typename ChildT>
3119 template<typename CombineOp, typename OtherRootNode>
3120 inline void
3121 RootNode<ChildT>::doCombine2(const RootNode& other0, const OtherRootNode& other1,
3122  CombineOp& op, bool prune)
3123 {
3124  enforceSameConfiguration(other1);
3125 
3126  typedef typename OtherRootNode::ValueType OtherValueT;
3127  typedef typename OtherRootNode::Tile OtherTileT;
3128  typedef typename OtherRootNode::NodeStruct OtherNodeStructT;
3129  typedef typename OtherRootNode::MapCIter OtherMapCIterT;
3130 
3132 
3133  CoordSet keys;
3134  other0.insertKeys(keys);
3135  other1.insertKeys(keys);
3136 
3137  const NodeStruct bg0(Tile(other0.mBackground, /*active=*/false));
3138  const OtherNodeStructT bg1(OtherTileT(other1.mBackground, /*active=*/false));
3139 
3140  for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3141  MapIter thisIter = this->findOrAddCoord(*i);
3142  MapCIter iter0 = other0.findKey(*i);
3143  OtherMapCIterT iter1 = other1.findKey(*i);
3144  const NodeStruct& ns0 = (iter0 != other0.mTable.end()) ? iter0->second : bg0;
3145  const OtherNodeStructT& ns1 = (iter1 != other1.mTable.end()) ? iter1->second : bg1;
3146  if (ns0.isTile() && ns1.isTile()) {
3147  // Both input nodes have constant values (tiles).
3148  // Combine the two values and add a new tile to this node with the result.
3149  op(args.setARef(ns0.tile.value)
3150  .setAIsActive(ns0.isTileOn())
3151  .setBRef(ns1.tile.value)
3152  .setBIsActive(ns1.isTileOn()));
3153  setTile(thisIter, Tile(args.result(), args.resultIsActive()));
3154  } else {
3155  if (!isChild(thisIter)) {
3156  // Add a new child with the same coordinates, etc. as the other node's child.
3157  const Coord& childOrigin =
3158  ns0.isChild() ? ns0.child->origin() : ns1.child->origin();
3159  setChild(thisIter, *(new ChildT(childOrigin, getTile(thisIter).value)));
3160  }
3161  ChildT& child = getChild(thisIter);
3162 
3163  if (ns0.isTile()) {
3164  // Combine node1's child with node0's constant value
3165  // and write the result into this node's child.
3166  child.combine2(ns0.tile.value, *ns1.child, ns0.isTileOn(), op);
3167  } else if (ns1.isTile()) {
3168  // Combine node0's child with node1's constant value
3169  // and write the result into this node's child.
3170  child.combine2(*ns0.child, ns1.tile.value, ns1.isTileOn(), op);
3171  } else {
3172  // Combine node0's child with node1's child
3173  // and write the result into this node's child.
3174  child.combine2(*ns0.child, *ns1.child, op);
3175  }
3176  }
3177  if (prune && isChild(thisIter)) getChild(thisIter).prune();
3178  }
3179 
3180  // Combine background values.
3181  op(args.setARef(other0.mBackground).setBRef(other1.mBackground));
3182  mBackground = args.result();
3183 }
3184 
3185 
3187 
3188 
3189 template<typename ChildT>
3190 template<typename BBoxOp>
3191 inline void
3193 {
3194  const bool descent = op.template descent<LEVEL>();
3195  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
3196  if (this->isTileOff(i)) continue;
3197  if (this->isChild(i) && descent) {
3198  this->getChild(i).visitActiveBBox(op);
3199  } else {
3200 #ifdef _MSC_VER
3201  op.operator()<LEVEL>(CoordBBox::createCube(i->first, ChildT::DIM));
3202 #else
3203  op.template operator()<LEVEL>(CoordBBox::createCube(i->first, ChildT::DIM));
3204 #endif
3205  }
3206  }
3207 }
3208 
3209 
3210 template<typename ChildT>
3211 template<typename VisitorOp>
3212 inline void
3214 {
3215  doVisit<RootNode, VisitorOp, ChildAllIter>(*this, op);
3216 }
3217 
3218 
3219 template<typename ChildT>
3220 template<typename VisitorOp>
3221 inline void
3222 RootNode<ChildT>::visit(VisitorOp& op) const
3223 {
3224  doVisit<const RootNode, VisitorOp, ChildAllCIter>(*this, op);
3225 }
3226 
3227 
3228 template<typename ChildT>
3229 template<typename RootNodeT, typename VisitorOp, typename ChildAllIterT>
3230 inline void
3231 RootNode<ChildT>::doVisit(RootNodeT& self, VisitorOp& op)
3232 {
3233  typename RootNodeT::ValueType val;
3234  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
3235  if (op(iter)) continue;
3236  if (typename ChildAllIterT::ChildNodeType* child = iter.probeChild(val)) {
3237  child->visit(op);
3238  }
3239  }
3240 }
3241 
3242 
3244 
3245 
3246 template<typename ChildT>
3247 template<typename OtherRootNodeType, typename VisitorOp>
3248 inline void
3249 RootNode<ChildT>::visit2(OtherRootNodeType& other, VisitorOp& op)
3250 {
3251  doVisit2<RootNode, OtherRootNodeType, VisitorOp, ChildAllIter,
3252  typename OtherRootNodeType::ChildAllIter>(*this, other, op);
3253 }
3254 
3255 
3256 template<typename ChildT>
3257 template<typename OtherRootNodeType, typename VisitorOp>
3258 inline void
3259 RootNode<ChildT>::visit2(OtherRootNodeType& other, VisitorOp& op) const
3260 {
3261  doVisit2<const RootNode, OtherRootNodeType, VisitorOp, ChildAllCIter,
3262  typename OtherRootNodeType::ChildAllCIter>(*this, other, op);
3263 }
3264 
3265 
3266 template<typename ChildT>
3267 template<
3268  typename RootNodeT,
3269  typename OtherRootNodeT,
3270  typename VisitorOp,
3271  typename ChildAllIterT,
3272  typename OtherChildAllIterT>
3273 inline void
3274 RootNode<ChildT>::doVisit2(RootNodeT& self, OtherRootNodeT& other, VisitorOp& op)
3275 {
3276  enforceSameConfiguration(other);
3277 
3278  typename RootNodeT::ValueType val;
3279  typename OtherRootNodeT::ValueType otherVal;
3280 
3281  // The two nodes are required to have corresponding table entries,
3282  // but since that might require background tiles to be added to one or both,
3283  // and the nodes might be const, we operate on shallow copies of the nodes instead.
3284  RootNodeT copyOfSelf(self.mBackground);
3285  copyOfSelf.mTable = self.mTable;
3286  OtherRootNodeT copyOfOther(other.mBackground);
3287  copyOfOther.mTable = other.mTable;
3288 
3289  // Add background tiles to both nodes as needed.
3290  CoordSet keys;
3291  self.insertKeys(keys);
3292  other.insertKeys(keys);
3293  for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3294  copyOfSelf.findOrAddCoord(*i);
3295  copyOfOther.findOrAddCoord(*i);
3296  }
3297 
3298  ChildAllIterT iter = copyOfSelf.beginChildAll();
3299  OtherChildAllIterT otherIter = copyOfOther.beginChildAll();
3300 
3301  for ( ; iter && otherIter; ++iter, ++otherIter)
3302  {
3303  const size_t skipBranch = static_cast<size_t>(op(iter, otherIter));
3304 
3305  typename ChildAllIterT::ChildNodeType* child =
3306  (skipBranch & 1U) ? NULL : iter.probeChild(val);
3307  typename OtherChildAllIterT::ChildNodeType* otherChild =
3308  (skipBranch & 2U) ? NULL : otherIter.probeChild(otherVal);
3309 
3310  if (child != NULL && otherChild != NULL) {
3311  child->visit2Node(*otherChild, op);
3312  } else if (child != NULL) {
3313  child->visit2(otherIter, op);
3314  } else if (otherChild != NULL) {
3315  otherChild->visit2(iter, op, /*otherIsLHS=*/true);
3316  }
3317  }
3318  // Remove any background tiles that were added above,
3319  // as well as any that were created by the visitors.
3320  copyOfSelf.eraseBackgroundTiles();
3321  copyOfOther.eraseBackgroundTiles();
3322 
3323  // If either input node is non-const, replace its table with
3324  // the (possibly modified) copy.
3325  self.resetTable(copyOfSelf.mTable);
3326  other.resetTable(copyOfOther.mTable);
3327 }
3328 
3329 } // namespace tree
3330 } // namespace OPENVDB_VERSION_NAME
3331 } // namespace openvdb
3332 
3333 #endif // OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
3334 
3335 // Copyright (c) 2012-2014 DreamWorks Animation LLC
3336 // All rights reserved. This software is distributed under the
3337 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
static void copyWithValueConversion(RootT &self, const OtherRootT &other)
Definition: RootNode.h:1060
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:1862
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:1302
Definition: Types.h:424
bool isValueOn(const Coord &xyz) const
Definition: RootNode.h:1593
T truncateRealToHalf(const T &val)
Return the given value truncated to 16-bit float precision.
Definition: Compression.h:125
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:2398
void visit2(OtherRootNodeType &other, VisitorOp &)
Definition: RootNode.h:3249
const ValueType & getValue(const Coord &xyz) const
Definition: RootNode.h:1625
ChildOffCIter beginChildOff() const
Definition: RootNode.h:412
Vec2< T > minComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise minimum of the two vectors.
Definition: Vec2.h:497
Index getHeight() const
Definition: RootNode.h:489
RootNode(const RootNode &other)
Definition: RootNode.h:110
LeafNodeType * touchLeafAndCache(const Coord &xyz, AccessorT &acc)
Same as touchLeaf() but, if necessary, update the given accessor with pointers to the nodes along the...
ValueAllCIter cbeginValueAll() const
Definition: RootNode.h:420
void clip(const CoordBBox &)
Set all voxels that lie outside the given axis-aligned box to the background.
Definition: RootNode.h:2318
Index getDepth() const
Definition: RootNode.h:490
NodeChain< RootNode, LEVEL >::Type NodeChainType
NodeChainType is a list of this tree's node types, from LeafNodeType to RootNode. ...
Definition: RootNode.h:85
size_t eraseBackgroundTiles()
Remove all background tiles.
Definition: RootNode.h:1212
ValueOnCIter cbeginValueOn() const
Definition: RootNode.h:418
ValueIter< const RootNode, MapCIter, ValueOffPred, const ValueType > ValueOffCIter
Definition: RootNode.h:403
boost::mpl::vector< typename HeadT::ChildNodeType, HeadT >::type Type
Definition: RootNode.h:967
uint64_t Index64
Definition: Types.h:58
static void combine2(RootT &self, const RootT &other0, const OtherRootT &other1, CombineOp &op, bool prune)
Definition: RootNode.h:3096
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...
ChildAllIter beginChildAll()
Definition: RootNode.h:416
static void getNodeLog2Dims(std::vector< Index > &dims)
Definition: RootNode.h:1265
Definition: Types.h:385
const ValueType & getValueAndCache(const Coord &xyz, AccessorT &) const
ValueOffCIter beginValueOff() const
Definition: RootNode.h:422
void getNodes(ArrayT &array)
Adds all nodes of a certain type to a container with the following API:
Definition: RootNode.h:2718
size_t numBackgroundTiles() const
Return the number of background tiles.
Definition: RootNode.h:1200
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
void setValueAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: RootNode.h:1798
void readBuffers(std::istream &, bool fromHalf=false)
Definition: RootNode.h:2284
bool resultIsActive() const
Definition: Types.h:358
ValueIter< const RootNode, MapCIter, ChildOffPred, ValueType > ChildOffCIter
Definition: RootNode.h:396
Mat3< typename promote< T0, T1 >::type > operator*(const Mat3< T0 > &m0, const Mat3< T1 > &m1)
Matrix multiplication.
Definition: Mat3.h:608
bool readTopology(std::istream &, bool fromHalf=false)
Definition: RootNode.h:2160
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:1779
bool operator!=(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Inequality operator, does exact floating point comparisons.
Definition: Vec3.h:458
ValueOffCIter cbeginValueOff() const
Definition: RootNode.h:419
CombineArgs & setARef(const AValueType &a)
Redirect the A value to a new external source.
Definition: Types.h:347
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:2080
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 NULL.
Definition: RootNode.h:2642
void copyToDense(const GridOrTreeT &sparse, DenseT &dense, bool serial=false)
Populate a dense grid with the values of voxels from a sparse grid, where the sparse grid intersects ...
Definition: Dense.h:369
static CoordBBox getNodeBoundingBox()
Return the bounding box of this RootNode, i.e., an infinite bounding box.
Definition: RootNode.h:439
void voxelizeActiveTiles()
Densify active tiles, i.e., replace them with leaf-level active voxels.
Definition: RootNode.h:2774
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:2467
ValueIter< RootNode, MapIter, ChildOffPred, const ValueType > ChildOffIter
Definition: RootNode.h:395
int32_t Int32
Definition: Types.h:61
ChildAllCIter beginChildAll() const
Definition: RootNode.h:413
ChildType::ValueType ValueType
Definition: RootNode.h:80
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:2358
Index32 FindHighestOn(Index32 v)
Return the most significant on bit of the given 32-bit value.
Definition: NodeMasks.h:151
RootNode & operator=(const RootNode &other)
Copy a root node of the same type as this node.
Definition: RootNode.h:1116
static void combine2(RootT &self, const RootT &, const OtherRootT &other1, CombineOp &, bool)
Definition: RootNode.h:3077
ChildIter< RootNode, MapIter, ChildOnPred, ChildType > ChildOnIter
Definition: RootNode.h:393
int getValueDepthAndCache(const Coord &xyz, AccessorT &) const
Definition: RootNode.h:1659
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:2978
ChildOnCIter cbeginChildOn() const
Definition: RootNode.h:408
void combine(FloatTreeT &lhsDist, IntTreeT &lhsIndex, FloatTreeT &rhsDist, IntTreeT &rhsIndex)
Definition: MeshToVolume.h:403
ChildOnIter beginChildOn()
Definition: RootNode.h:414
ChildType::LeafNodeType LeafNodeType
Definition: RootNode.h:79
ChildOffIter beginChildOff()
Definition: RootNode.h:415
void combine2(const RootNode &other0, const OtherRootNode &other1, CombineOp &op, bool prune=false)
Definition: RootNode.h:3107
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:2678
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:1649
Index getWidth() const
Definition: RootNode.h:488
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:2379
~RootNode()
Definition: RootNode.h:158
bool probeValue(const Coord &xyz, ValueType &value) const
Definition: RootNode.h:1988
static bool hasSameConfiguration(const RootNode< OtherChildType > &other)
Return false if the other node's dimensions don't match this node's.
Definition: RootNode.h:1349
NodeChain< typename HeadT::ChildNodeType, HeadLevel-1 >::Type SubtreeT
Definition: RootNode.h:960
bool isBackgroundTile(const Tile &) const
Return true if the given tile is inactive and has the background value.
Definition: RootNode.h:1178
NodeChain::Type is a boost::mpl::vector that lists the types of th...
Definition: RootNode.h:68
DenseIter< RootNode, MapIter, ChildType, ValueType > ChildAllIter
Definition: RootNode.h:397
ValueConverter::Type is the type of a RootNode having the same child hierarchy as this node but a ...
Definition: RootNode.h:91
#define OPENVDB_VERSION_NAME
Definition: version.h:43
Definition: Types.h:263
ChildOnCIter beginChildOn() const
Definition: RootNode.h:411
ValueAllIter beginValueAll()
Definition: RootNode.h:426
OPENVDB_API uint32_t getFormatVersion(std::ios_base &)
Return the file format version number associated with the given input stream.
SameConfiguration::value is true if and only if OtherNodeType is the type of a RootNod...
Definition: RootNode.h:99
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don't change its value.
Definition: RootNode.h:1671
void combine(RootNode &other, CombineOp &, bool prune=false)
Definition: RootNode.h:3017
Index32 Index
Definition: Types.h:59
Index32 leafCount() const
Definition: RootNode.h:1494
DenseIter< const RootNode, MapCIter, const ChildType, const ValueType > ChildAllCIter
Definition: RootNode.h:398
Definition: Exceptions.h:87
void fill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given box to a constant value, if necessary subdividing tiles that intersect ...
Definition: RootNode.h:2024
ValueOnIter beginValueOn()
Definition: RootNode.h:424
bool empty() const
Return true if this node's table is either empty or contains only background tiles.
Definition: RootNode.h:474
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: Types.h:309
Coord getMinIndex() const
Return the smallest index of the current tree.
Definition: RootNode.h:1274
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 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:2433
Index64 offVoxelCount() const
Definition: RootNode.h:1536
void setActiveStateAndCache(const Coord &xyz, bool on, AccessorT &)
Definition: RootNode.h:1708
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:2942
void modifyValueAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition: RootNode.h:1894
ValueIter< RootNode, MapIter, ValueAllPred, ValueType > ValueAllIter
Definition: RootNode.h:404
Definition: Exceptions.h:39
Index64 onVoxelCount() const
Definition: RootNode.h:1520
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
Definition: Platform.h:121
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: RootNode.h:1930
void setValueOffAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: RootNode.h:1755
ChildOffCIter cbeginChildOff() const
Definition: RootNode.h:409
const ValueType & background() const
Return this node's background value.
Definition: RootNode.h:456
OPENVDB_API Hermite min(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
RootNode()
Construct a new tree with a background value of 0.
Definition: RootNode.h:994
ValueIter< const RootNode, MapCIter, ValueOnPred, const ValueType > ValueOnCIter
Definition: RootNode.h:401
bool isApproxEqual(const Hermite &lhs, const Hermite &rhs)
Definition: Hermite.h:470
NodeT * probeNode(const Coord &xyz)
Return a pointer to the node that contains voxel (x, y, z). If no such node exists, return NULL.
Definition: RootNode.h:2599
void clear()
Definition: RootNode.h:471
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:1433
void load(std::istream &is)
Definition: NodeMasks.h:1235
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:2555
const AValueType & result() const
Get the output value.
Definition: Types.h:339
LeafNodeType * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return NULL.
Definition: RootNode.h:2634
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:107
OPENVDB_STATIC_SPECIALIZATION GridType::Ptr clip(const GridType &grid, const BBoxd &)
Clip the given grid against a world-space bounding box and return a new grid containing the result...
Definition: Clip.h:364
ChildAllCIter cbeginChildAll() const
Definition: RootNode.h:410
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:1820
ValueAllCIter beginValueAll() const
Definition: RootNode.h:423
ChildIter< const RootNode, MapCIter, ChildOnPred, const ChildType > ChildOnCIter
Definition: RootNode.h:394
Definition: RootNode.h:69
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:119
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 NULL.
Definition: RootNode.h:2617
Index64 onTileCount() const
Definition: RootNode.h:1575
Index getTableSize() const
Return the number of entries in this node's table.
Definition: RootNode.h:486
bool operator==(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Equality operator, does exact floating point comparisons.
Definition: Vec3.h:450
bool hasActiveTiles() const
Definition: RootNode.h:1602
static void copyWithValueConversion(RootT &self, const OtherRootT &other)
Definition: RootNode.h:1078
void writeBuffers(std::ostream &, bool toHalf=false) const
Definition: RootNode.h:2274
Index64 onLeafVoxelCount() const
Definition: RootNode.h:1552
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:1685
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_END
Definition: Platform.h:122
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:2906
static Index getLevel()
Definition: RootNode.h:481
Index64 offLeafVoxelCount() const
Definition: RootNode.h:1564
boost::mpl::push_back< SubtreeT, HeadT >::type Type
Definition: RootNode.h:961
bool expand(const Coord &xyz)
Expand this node's table so that (x, y, z) is included in the index range.
Definition: RootNode.h:1251
bool isExactlyEqual(const T0 &a, const T1 &b)
Return true if a is exactly equal to b.
Definition: Math.h:391
bool isValueOnAndCache(const Coord &xyz, AccessorT &) const
Definition: RootNode.h:1613
ValueOffIter beginValueOff()
Definition: RootNode.h:425
CanConvertType::value is true if a value of type ToType can be constructed from a v...
Definition: Types.h:184
ValueIter< const RootNode, MapCIter, ValueAllPred, const ValueType > ValueAllCIter
Definition: RootNode.h:405
ValueOnCIter beginValueOn() const
Definition: RootNode.h:421
bool probeValueAndCache(const Coord &xyz, ValueType &value, AccessorT &) const
Definition: RootNode.h:2004
ValueIter< RootNode, MapIter, ValueOnPred, ValueType > ValueOnIter
Definition: RootNode.h:400
uint32_t Index32
Definition: Types.h:57
Definition: Types.h:426
ChildType ChildNodeType
Definition: RootNode.h:78
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
Definition: RootNode.h:75
static bool hasCompatibleValueType(const RootNode< OtherChildType > &other)
Definition: RootNode.h:1381
RootNode< typename ChildType::template ValueConverter< OtherValueType >::Type > Type
Definition: RootNode.h:92
Index32 nonLeafCount() const
Definition: RootNode.h:1506
void visit(VisitorOp &)
Definition: RootNode.h:3213
void getIndexRange(CoordBBox &bbox) const
Return the current index range. Both min and max are inclusive.
Definition: RootNode.h:1289
T zeroVal()
Return the value of type T that corresponds to zero.
Definition: Math.h:85
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:2697
static Index getChildDim()
Definition: RootNode.h:483
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:1151
Index64 memUsage() const
Return the total amount of memory in bytes occupied by this node and its children.
Definition: RootNode.h:1408
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:2514
void merge(RootNode &other)
Efficiently merge another tree into this tree using one of several schemes.
Definition: RootNode.h:2794
void modifyValueAndActiveStateAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition: RootNode.h:1957
Coord getMaxIndex() const
Return the largest index of the current tree.
Definition: RootNode.h:1281
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 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:314
bool isOn(Index32 i) const
Definition: NodeMasks.h:1194
void visitActiveBBox(BBoxOp &) const
Call the templated functor BBoxOp with bounding box information for all active tiles and leaf nodes i...
Definition: RootNode.h:3192
ValueIter< RootNode, MapIter, ValueOffPred, ValueType > ValueOffIter
Definition: RootNode.h:402
bool writeTopology(std::ostream &, bool toHalf=false) const
Definition: RootNode.h:2124
Definition: NodeMasks.h:928
void setValueOnlyAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: RootNode.h:1839