OpenVDB  1.1.0
RootNode.h
Go to the documentation of this file.
1 
2 //
3 // Copyright (c) 2012-2013 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 <boost/type_traits/remove_const.hpp>
42 #include <openvdb/Exceptions.h>
43 #include <openvdb/Types.h>
44 #include <openvdb/io/Compression.h> // for truncateRealToHalf()
45 #include <openvdb/math/Math.h> // for isZero(), isExactlyEqual(), etc.
46 #include <openvdb/math/BBox.h>
47 #include <openvdb/util/NodeMasks.h> // for backward compatibility only (see readTopology())
48 #include <openvdb/version.h>
49 #include "Util.h"
50 
51 
52 namespace openvdb {
54 namespace OPENVDB_VERSION_NAME {
55 namespace tree {
56 
57 template<typename ChildType>
58 class RootNode
59 {
60 public:
61  typedef ChildType ChildNodeType;
62  typedef typename ChildType::LeafNodeType LeafNodeType;
63  typedef typename ChildType::ValueType ValueType;
64 
65  static const Index LEVEL = 1 + ChildType::LEVEL; // level 0 = leaf
66 
69  template<typename OtherValueType>
70  struct ValueConverter {
72  };
73 
74 
76  RootNode();
77 
79  explicit RootNode(const ValueType& background);
80 
81  RootNode(const RootNode& other) { *this = other; }
82 
94  template<typename OtherChildType>
96  const ValueType& background, const ValueType& foreground,
97  TopologyCopy);
98 
114  template<typename OtherChildType>
115  RootNode(const RootNode<OtherChildType>& other, const ValueType& background,
116  TopologyCopy);
117 
118  RootNode& operator=(const RootNode& other);
119 
120  ~RootNode() { this->clearTable(); }
121 
122 private:
123  struct Tile {
124  Tile(): value(zeroVal<ValueType>()), active(false) {}
125  Tile(const ValueType& v, bool b): value(v), active(b) {}
126  ValueType value;
127  bool active;
128  };
129 
130  // This lightweight struct pairs child pointers and tiles
131  struct NodeStruct {
132  ChildType* child;
133  Tile tile;
134 
135  NodeStruct(): child(NULL) {}
136  NodeStruct(ChildType& c): child(&c) {}
137  NodeStruct(const Tile& t): child(NULL), tile(t) {}
138  ~NodeStruct() {}
139 
140  bool isChild() const { return child != NULL; }
141  bool isTile() const { return child == NULL; }
142  bool isTileOff() const { return isTile() && !tile.active; }
143  bool isTileOn() const { return isTile() && tile.active; }
144 
145  void set(ChildType& c) { delete child; child = &c; }
146  void set(const Tile& t) { delete child; child = NULL; tile = t; }
147  ChildType& steal(const Tile& t) { ChildType* c = child; child = NULL; tile = t; return *c; }
148  };
149 
150  typedef std::map<Coord, NodeStruct> MapType;
151  typedef typename MapType::iterator MapIter;
152  typedef typename MapType::const_iterator MapCIter;
153 
154  typedef std::set<Coord> CoordSet;
155  typedef typename CoordSet::iterator CoordSetIter;
156  typedef typename CoordSet::const_iterator CoordSetCIter;
157 
158  static void setTile(const MapIter& i, const Tile& t) { i->second.set(t); }
159  static void setChild(const MapIter& i, ChildType& c) { i->second.set(c); }
160  static Tile& getTile(const MapIter& i) { return i->second.tile; }
161  static const Tile& getTile(const MapCIter& i) { return i->second.tile; }
162  static ChildType& getChild(const MapIter& i) { return *(i->second.child); }
163  static const ChildType& getChild(const MapCIter& i) { return *(i->second.child); }
164  static ChildType& stealChild(const MapIter& i, const Tile& t) {return i->second.steal(t);}
165  static const ChildType& stealChild(const MapCIter& i,const Tile& t) {return i->second.steal(t);}
166 
167  static bool isChild(const MapCIter& i) { return i->second.isChild(); }
168  static bool isChild(const MapIter& i) { return i->second.isChild(); }
169  static bool isTile(const MapCIter& i) { return i->second.isTile(); }
170  static bool isTile(const MapIter& i) { return i->second.isTile(); }
171  static bool isTileOff(const MapCIter& i) { return i->second.isTileOff(); }
172  static bool isTileOff(const MapIter& i) { return i->second.isTileOff(); }
173  static bool isTileOn(const MapCIter& i) { return i->second.isTileOn(); }
174  static bool isTileOn(const MapIter& i) { return i->second.isTileOn(); }
175 
176  struct NullPred {
177  static inline bool test(const MapIter&) { return true; }
178  static inline bool test(const MapCIter&) { return true; }
179  };
180  struct ValueOnPred {
181  static inline bool test(const MapIter& i) { return isTileOn(i); }
182  static inline bool test(const MapCIter& i) { return isTileOn(i); }
183  };
184  struct ValueOffPred {
185  static inline bool test(const MapIter& i) { return isTileOff(i); }
186  static inline bool test(const MapCIter& i) { return isTileOff(i); }
187  };
188  struct ValueAllPred {
189  static inline bool test(const MapIter& i) { return isTile(i); }
190  static inline bool test(const MapCIter& i) { return isTile(i); }
191  };
192  struct ChildOnPred {
193  static inline bool test(const MapIter& i) { return isChild(i); }
194  static inline bool test(const MapCIter& i) { return isChild(i); }
195  };
196  struct ChildOffPred {
197  static inline bool test(const MapIter& i) { return isTile(i); }
198  static inline bool test(const MapCIter& i) { return isTile(i); }
199  };
200 
201  template<typename _RootNodeT, typename _MapIterT, typename FilterPredT>
202  class BaseIter
203  {
204  public:
205  typedef _RootNodeT RootNodeT;
206  typedef _MapIterT MapIterT; // either MapIter or MapCIter
207 
208  bool operator==(const BaseIter& other) const
209  {
210  return (mParentNode == other.mParentNode) && (mIter == other.mIter);
211  }
212  bool operator!=(const BaseIter& other) const { return !(*this == other); }
213 
214  RootNodeT* getParentNode() const { return mParentNode; }
216  RootNodeT& parent() const
217  {
218  if (!mParentNode) OPENVDB_THROW(ValueError, "iterator references a null parent node");
219  return *mParentNode;
220  }
221 
222  bool test() const { assert(mParentNode); return mIter != mParentNode->mTable.end(); }
223  operator bool() const { return this->test(); }
224 
225  void increment() { ++mIter; this->skip(); }
226  bool next() { this->increment(); return this->test(); }
227  void increment(Index n) { for (int i = 0; i < n && this->next(); ++i) {} }
228 
231  Index pos() const
232  {
233  return !mParentNode ? 0U : Index(std::distance(mParentNode->mTable.begin(), mIter));
234  }
235 
236  bool isValueOn() const { return RootNodeT::isTileOn(mIter); }
237  bool isValueOff() const { return RootNodeT::isTileOff(mIter); }
238  void setValueOn(bool on = true) const { mIter->second.tile.active = on; }
239  void setValueOff() const { mIter->second.tile.active = false; }
240 
242  Coord getCoord() const { return mIter->first; }
244  void getCoord(Coord& xyz) const { xyz = this->getCoord(); }
245 
246  protected:
247  BaseIter(): mParentNode(NULL) {}
248  BaseIter(RootNodeT& parent, const MapIterT& iter): mParentNode(&parent), mIter(iter) {}
249 
250  void skip() { while (this->test() && !FilterPredT::test(mIter)) ++mIter; }
251 
252  RootNodeT* mParentNode;
253  MapIterT mIter;
254  }; // BaseIter
255 
256  template<typename RootNodeT, typename MapIterT, typename FilterPredT, typename ChildNodeT>
257  class ChildIter: public BaseIter<RootNodeT, MapIterT, FilterPredT>
258  {
259  public:
260  typedef BaseIter<RootNodeT, MapIterT, FilterPredT> BaseT;
261  typedef RootNodeT NodeType;
262  typedef NodeType ValueType;
263  typedef ChildNodeT ChildNodeType;
264  typedef typename boost::remove_const<NodeType>::type NonConstNodeType;
265  typedef typename boost::remove_const<ValueType>::type NonConstValueType;
266  typedef typename boost::remove_const<ChildNodeType>::type NonConstChildNodeType;
267  using BaseT::mIter;
268 
269  ChildIter() {}
270  ChildIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
271 
272  ChildIter& operator++() { BaseT::increment(); return *this; }
273 
274  ChildNodeT& getValue() const { return getChild(mIter); }
275  ChildNodeT& operator*() const { return this->getValue(); }
276  ChildNodeT* operator->() const { return &this->getValue(); }
277  }; // ChildIter
278 
279  template<typename RootNodeT, typename MapIterT, typename FilterPredT, typename ValueT>
280  class ValueIter: public BaseIter<RootNodeT, MapIterT, FilterPredT>
281  {
282  public:
283  typedef BaseIter<RootNodeT, MapIterT, FilterPredT> BaseT;
284  typedef RootNodeT NodeType;
285  typedef ValueT ValueType;
286  typedef typename boost::remove_const<NodeType>::type NonConstNodeType;
287  typedef typename boost::remove_const<ValueT>::type NonConstValueType;
288  using BaseT::mIter;
289 
290  ValueIter() {}
291  ValueIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
292 
293  ValueIter& operator++() { BaseT::increment(); return *this; }
294 
295  ValueT& getValue() const { return getTile(mIter).value; }
296  ValueT& operator*() const { return this->getValue(); }
297  ValueT* operator->() const { return &(this->getValue()); }
298 
299  void setValue(const ValueT& v) const { assert(isTile(mIter)); getTile(mIter).value = v; }
300  }; // ValueIter
301 
302  template<typename RootNodeT, typename MapIterT, typename ChildNodeT, typename ValueT>
303  class DenseIter: public BaseIter<RootNodeT, MapIterT, NullPred>
304  {
305  public:
306  typedef BaseIter<RootNodeT, MapIterT, NullPred> BaseT;
307  typedef RootNodeT NodeType;
308  typedef ValueT ValueType;
309  typedef ChildNodeT ChildNodeType;
310  typedef typename boost::remove_const<NodeType>::type NonConstNodeType;
311  typedef typename boost::remove_const<ValueT>::type NonConstValueType;
312  typedef typename boost::remove_const<ChildNodeT>::type NonConstChildNodeType;
313  using BaseT::mIter;
314 
315  DenseIter() {}
316  DenseIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) {}
317 
318  DenseIter& operator++() { BaseT::increment(); return *this; }
319 
320  bool isChildNode() const { return isChild(mIter); }
321 
322  ChildNodeT* probeChild(NonConstValueType& value) const
323  {
324  if (isChild(mIter)) return &getChild(mIter);
325  value = getTile(mIter).value;
326  return NULL;
327  }
328  bool probeChild(ChildNodeT*& child, NonConstValueType& value) const
329  {
330  child = this->probeChild(value);
331  return child != NULL;
332  }
333  bool probeValue(NonConstValueType& value) const { return !this->probeChild(value); }
334 
335  void setChild(ChildNodeT& c) const { RootNodeT::setChild(mIter, c); }
336  void setChild(ChildNodeT* c) const { assert(c != NULL); RootNodeT::setChild(mIter, *c); }
337  void setValue(const ValueT& v) const
338  {
339  if (isTile(mIter)) getTile(mIter).value = v;
343  else stealChild(mIter, Tile(v, /*active=*/true));
344  }
345  }; // DenseIter
346 
347 public:
348  typedef ChildIter<RootNode, MapIter, ChildOnPred, ChildType> ChildOnIter;
349  typedef ChildIter<const RootNode, MapCIter, ChildOnPred, const ChildType> ChildOnCIter;
350  typedef ValueIter<RootNode, MapIter, ChildOffPred, const ValueType> ChildOffIter;
351  typedef ValueIter<const RootNode, MapCIter, ChildOffPred, ValueType> ChildOffCIter;
352  typedef DenseIter<RootNode, MapIter, ChildType, ValueType> ChildAllIter;
353  typedef DenseIter<const RootNode, MapCIter, const ChildType, const ValueType> ChildAllCIter;
354 
355  typedef ValueIter<RootNode, MapIter, ValueOnPred, ValueType> ValueOnIter;
356  typedef ValueIter<const RootNode, MapCIter, ValueOnPred, const ValueType> ValueOnCIter;
357  typedef ValueIter<RootNode, MapIter, ValueOffPred, ValueType> ValueOffIter;
358  typedef ValueIter<const RootNode, MapCIter, ValueOffPred, const ValueType> ValueOffCIter;
359  typedef ValueIter<RootNode, MapIter, ValueAllPred, ValueType> ValueAllIter;
360  typedef ValueIter<const RootNode, MapCIter, ValueAllPred, const ValueType> ValueAllCIter;
361 
362 
363  ChildOnCIter cbeginChildOn() const { return ChildOnCIter(*this, mTable.begin()); }
364  ChildOffCIter cbeginChildOff() const { return ChildOffCIter(*this, mTable.begin()); }
365  ChildAllCIter cbeginChildAll() const { return ChildAllCIter(*this, mTable.begin()); }
366  ChildOnCIter beginChildOn() const { return cbeginChildOn(); }
367  ChildOffCIter beginChildOff() const { return cbeginChildOff(); }
368  ChildAllCIter beginChildAll() const { return cbeginChildAll(); }
369  ChildOnIter beginChildOn() { return ChildOnIter(*this, mTable.begin()); }
370  ChildOffIter beginChildOff() { return ChildOffIter(*this, mTable.begin()); }
371  ChildAllIter beginChildAll() { return ChildAllIter(*this, mTable.begin()); }
372 
373  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(*this, mTable.begin()); }
374  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(*this, mTable.begin()); }
375  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(*this, mTable.begin()); }
376  ValueOnCIter beginValueOn() const { return cbeginValueOn(); }
377  ValueOffCIter beginValueOff() const { return cbeginValueOff(); }
378  ValueAllCIter beginValueAll() const { return cbeginValueAll(); }
379  ValueOnIter beginValueOn() { return ValueOnIter(*this, mTable.begin()); }
380  ValueOffIter beginValueOff() { return ValueOffIter(*this, mTable.begin()); }
381  ValueAllIter beginValueAll() { return ValueAllIter(*this, mTable.begin()); }
382 
384  Index64 memUsage() const;
385 
388  void evalActiveVoxelBoundingBox(CoordBBox& bbox) const;
389 
392 
396  void setBackground(const ValueType& value);
398  const ValueType& background() const { return mBackground; }
400  OPENVDB_DEPRECATED ValueType getBackground() const { return mBackground; }
401 
403  bool isBackgroundTile(const Tile&) const;
405 
406  bool isBackgroundTile(const MapIter&) const;
407  bool isBackgroundTile(const MapCIter&) const;
409 
411  size_t numBackgroundTiles() const;
414  size_t eraseBackgroundTiles();
415  void clear() { this->clearTable(); }
416 
418  bool empty() const { return mTable.size() == numBackgroundTiles(); }
419 
423  bool expand(const Coord& xyz);
424 
425  static Index getLevel() { return LEVEL; }
426  static void getNodeLog2Dims(std::vector<Index>& dims);
427  static Index getChildDim() { return ChildType::DIM; }
428 
430  Index getTableSize() const { return mTable.size(); }
431 
432  Index getWidth() const { return this->getMaxIndex()[0] - this->getMinIndex()[0]; }
433  Index getHeight() const { return this->getMaxIndex()[1] - this->getMinIndex()[1]; }
434  Index getDepth() const { return this->getMaxIndex()[2] - this->getMinIndex()[2]; }
435 
437  Coord getMinIndex() const;
439  Coord getMaxIndex() const;
441  void getIndexRange(CoordBBox& bbox) const;
442 
445  template<typename OtherChildType>
446  bool hasSameTopology(const RootNode<OtherChildType>& other) const;
447 
449  template<typename OtherChildType>
450  static bool hasSameConfiguration(const RootNode<OtherChildType>& other);
451 
452  Index32 leafCount() const;
453  Index32 nonLeafCount() const;
454  Index64 onVoxelCount() const;
455  Index64 offVoxelCount() const;
456  Index64 onLeafVoxelCount() const;
457  Index64 offLeafVoxelCount() const;
458 
459  bool isValueOn(const Coord& xyz) const;
460 
461  bool hasActiveTiles() const;
462 
463  const ValueType& getValue(const Coord& xyz) const;
464  bool probeValue(const Coord& xyz, ValueType& value) const;
465 
469  int getValueDepth(const Coord& xyz) const;
470 
472  void setActiveState(const Coord& xyz, bool on);
473 
475  void setValueOff(const Coord& xyz);
477  void setValueOff(const Coord& xyz, const ValueType& value);
478 
479  void setValueOn(const Coord& xyz, const ValueType& value);
480  void setValueOnly(const Coord& xyz, const ValueType& value);
481  void setValueOnMin(const Coord& xyz, const ValueType& value);
482  void setValueOnMax(const Coord& xyz, const ValueType& value);
483  void setValueOnSum(const Coord& xyz, const ValueType& value);
484 
491  void fill(const CoordBBox& bbox, const ValueType& value, bool active = true);
492 
493 
494  //
495  // I/O
496  //
497  bool writeTopology(std::ostream&, bool toHalf = false) const;
498  bool readTopology(std::istream&, bool fromHalf = false);
499 
500  void writeBuffers(std::ostream&, bool toHalf = false) const;
501  void readBuffers(std::istream&, bool fromHalf = false);
502 
507  template<typename AccessorT>
508  const ValueType& getValueAndCache(const Coord& xyz, AccessorT&) const;
513  template<typename AccessorT>
514  bool isValueOnAndCache(const Coord& xyz, AccessorT&) const;
515 
520  template<typename AccessorT>
521  void setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
522 
527  template<typename AccessorT>
528  void setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
529 
535  template<typename AccessorT>
536  void setValueOnSumAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
537 
542  template<typename AccessorT>
543  void setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
544 
549  template<typename AccessorT>
550  void setActiveStateAndCache(const Coord& xyz, bool on, AccessorT&);
551 
556  template<typename AccessorT>
557  bool probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT&) const;
558 
564  template<typename AccessorT>
565  int getValueDepthAndCache(const Coord& xyz, AccessorT&) const;
566 
573  template<typename PruneOp> void pruneOp(PruneOp&);
574 
578  void prune(const ValueType& tolerance = zeroVal<ValueType>());
579 
582  void pruneInactive(const ValueType&);
583 
586  void pruneInactive();
587 
594  LeafNodeType* touchLeaf(const Coord& xyz);
595 
598  LeafNodeType* probeLeaf(const Coord& xyz);
601  const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
602 
605  template<typename AccessorT>
606  LeafNodeType* touchLeafAndCache(const Coord& xyz, AccessorT&);
607 
610  template<typename AccessorT>
611  LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT&);
614  template<typename AccessorT>
615  const LeafNodeType* probeConstLeafAndCache(const Coord& xyz, AccessorT&) const;
616 
622  void signedFloodFill();
623 
630  void signedFloodFill(const ValueType& outside, const ValueType& inside);
631 
637  void merge(RootNode& other);
638 
640  void voxelizeActiveTiles();
641 
655  template<typename OtherChildType>
656  void topologyUnion(const RootNode<OtherChildType>& other);
657 
658  template<typename CombineOp>
659  void combine(RootNode& other, CombineOp&, bool prune = false);
660 
661  template<typename CombineOp>
662  void combine2(const RootNode& other0, const RootNode& other1,
663  CombineOp& op, bool prune = false);
664 
670  template<typename BBoxOp> void visitActiveBBox(BBoxOp&) const;
671 
672  template<typename VisitorOp> void visit(VisitorOp&);
673  template<typename VisitorOp> void visit(VisitorOp&) const;
674 
675  template<typename OtherRootNodeType, typename VisitorOp>
676  void visit2(OtherRootNodeType& other, VisitorOp&);
677  template<typename OtherRootNodeType, typename VisitorOp>
678  void visit2(OtherRootNodeType& other, VisitorOp&) const;
679 
680 private:
683  template<typename> friend class RootNode;
684 
686  void initTable() {}
687  inline void clearTable();
689 
690  void resetTable(MapType& table) { mTable.swap(table); table.clear(); }
691  void resetTable(const MapType&) const {}
693 
694  Index getChildCount() const;
695  Index getTileCount() const;
696  Index getActiveTileCount() const;
697  Index getInactiveTileCount() const;
698 
700  static Coord coordToKey(const Coord& xyz) { return xyz & ~(ChildType::DIM - 1); }
701 
703  void insertKeys(CoordSet&) const;
704 
706  bool hasKey(const Coord& key) const { return mTable.find(key) != mTable.end(); }
708 
709 
710  MapIter findKey(const Coord& key) { return mTable.find(key); }
711  MapCIter findKey(const Coord& key) const { return mTable.find(key); }
713 
714 
715 
716  MapIter findCoord(const Coord& xyz) { return mTable.find(coordToKey(xyz)); }
717  MapCIter findCoord(const Coord& xyz) const { return mTable.find(coordToKey(xyz)); }
719 
720 
721 
722  MapIter findOrAddCoord(const Coord& xyz);
723 
725  template<typename OtherChildType>
726  static void enforceSameConfiguration(const RootNode<OtherChildType>& other);
727 
728  template<typename RootNodeT, typename VisitorOp, typename ChildAllIterT>
729  static inline void doVisit(RootNodeT&, VisitorOp&);
730 
731  template<typename RootNodeT, typename OtherRootNodeT, typename VisitorOp,
732  typename ChildAllIterT, typename OtherChildAllIterT>
733  static inline void doVisit2(RootNodeT&, OtherRootNodeT&, VisitorOp&);
734 
735 
736  MapType mTable;
737  ValueType mBackground;
738 }; // end of RootNode class
739 
740 
742 
743 
744 template<typename ChildT>
745 inline
746 RootNode<ChildT>::RootNode(): mBackground(zeroVal<ValueType>())
747 {
748  this->initTable();
749 }
750 
751 
752 template<typename ChildT>
753 inline
754 RootNode<ChildT>::RootNode(const ValueType& background) : mBackground(background)
755 {
756  this->initTable();
757 }
758 
759 
760 template<typename ChildT>
761 template<typename OtherChildType>
762 inline
764  const ValueType& backgd, const ValueType& foregd, TopologyCopy):
765  mBackground(backgd)
766 {
767  typedef RootNode<OtherChildType> OtherRootT;
768 
770  enforceSameConfiguration(other);
771 
772  const Tile bgTile(backgd, /*active=*/false), fgTile(foregd, true);
773  this->initTable();
774 
775  for (typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
776  mTable[i->first] = OtherRootT::isTile(i)
777  ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
778  : NodeStruct(*(new ChildT(OtherRootT::getChild(i), backgd, foregd, TopologyCopy())));
779  }
780 }
781 
782 
783 template<typename ChildT>
784 template<typename OtherChildType>
785 inline
787  const ValueType& backgd, TopologyCopy):
788  mBackground(backgd)
789 {
790  typedef RootNode<OtherChildType> OtherRootT;
791 
793  enforceSameConfiguration(other);
794 
795  const Tile bgTile(backgd, /*active=*/false), fgTile(backgd, true);
796  this->initTable();
797  for (typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
798  mTable[i->first] = OtherRootT::isTile(i)
799  ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
800  : NodeStruct(*(new ChildT(OtherRootT::getChild(i), backgd, TopologyCopy())));
801  }
802 }
803 
804 
805 template<typename ChildT>
806 inline RootNode<ChildT>&
808 {
809  mBackground = other.mBackground;
810 
811  this->clearTable();
812  this->initTable();
813 
814  for (MapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
815  mTable[i->first] =
816  isTile(i) ? NodeStruct(getTile(i)) : NodeStruct(*(new ChildT(getChild(i))));
817  }
818  return *this;
819 }
820 
821 
823 
824 
825 template<typename ChildT>
826 inline void
828 {
829  if (math::isExactlyEqual(background, mBackground)) return;
830 
831  // Traverse the tree, replacing occurrences of mBackground with background
832  // and -mBackground with -background.
833  for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
834  ChildT *child = iter->second.child;
835  if (child) {
836  child->resetBackground(/*old=*/mBackground, /*new=*/background);
837  } else {
838  Tile& tile = getTile(iter);
839  if (tile.active) continue;//only change inactive tiles
840  if (math::isApproxEqual(tile.value, mBackground)) {
841  tile.value = background;
842  } else if (math::isApproxEqual(tile.value, negative(mBackground))) {
843  tile.value = negative(background);
844  }
845  }
846  }
847  mBackground = background;
848 }
849 
850 
851 template<typename ChildT>
852 inline bool
853 RootNode<ChildT>::isBackgroundTile(const Tile& tile) const
854 {
855  return !tile.active && math::isApproxEqual(tile.value, mBackground);
856 }
857 
858 template<typename ChildT>
859 inline bool
860 RootNode<ChildT>::isBackgroundTile(const MapIter& iter) const
861 {
862  return isTileOff(iter) && math::isApproxEqual(getTile(iter).value, mBackground);
863 }
864 
865 template<typename ChildT>
866 inline bool
867 RootNode<ChildT>::isBackgroundTile(const MapCIter& iter) const
868 {
869  return isTileOff(iter) && math::isApproxEqual(getTile(iter).value, mBackground);
870 }
871 
872 
873 template<typename ChildT>
874 inline size_t
876 {
877  size_t count = 0;
878  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
879  if (this->isBackgroundTile(i)) ++count;
880  }
881  return count;
882 }
883 
884 
885 template<typename ChildT>
886 inline size_t
888 {
889  std::set<Coord> keysToErase;
890  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
891  if (this->isBackgroundTile(i)) keysToErase.insert(i->first);
892  }
893  for (std::set<Coord>::iterator i = keysToErase.begin(), e = keysToErase.end(); i != e; ++i) {
894  mTable.erase(*i);
895  }
896  return keysToErase.size();
897 }
898 
899 
901 
902 
903 template<typename ChildT>
904 inline void
905 RootNode<ChildT>::insertKeys(CoordSet& keys) const
906 {
907  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
908  keys.insert(i->first);
909  }
910 }
911 
912 
913 template<typename ChildT>
914 inline typename RootNode<ChildT>::MapIter
915 RootNode<ChildT>::findOrAddCoord(const Coord& xyz)
916 {
917  const Coord key = coordToKey(xyz);
918  std::pair<MapIter, bool> result = mTable.insert(
919  typename MapType::value_type(key, NodeStruct(Tile(mBackground, /*active=*/false))));
920  return result.first;
921 }
922 
923 
924 template<typename ChildT>
925 inline bool
927 {
928  const Coord key = coordToKey(xyz);
929  std::pair<MapIter, bool> result = mTable.insert(
930  typename MapType::value_type(key, NodeStruct(Tile(mBackground, /*active=*/false))));
931  return result.second; // return true if the key did not already exist
932 }
933 
934 
936 
937 
938 template<typename ChildT>
939 inline void
940 RootNode<ChildT>::getNodeLog2Dims(std::vector<Index>& dims)
941 {
942  dims.push_back(0); // magic number; RootNode has no Log2Dim
943  ChildT::getNodeLog2Dims(dims);
944 }
945 
946 
947 template<typename ChildT>
948 inline Coord
950 {
951  return mTable.empty() ? Coord(0) : mTable.begin()->first;
952 }
953 
954 template<typename ChildT>
955 inline Coord
957 {
958  return mTable.empty() ? Coord(0) : mTable.rbegin()->first + Coord(ChildT::DIM - 1);
959 }
960 
961 
962 template<typename ChildT>
963 inline void
965 {
966  bbox.min() = this->getMinIndex();
967  bbox.max() = this->getMaxIndex();
968 }
969 
970 
972 
973 
974 template<typename ChildT>
975 template<typename OtherChildType>
976 inline bool
978 {
979  typedef RootNode<OtherChildType> OtherRootT;
980  typedef typename OtherRootT::MapType OtherMapT;
981  typedef typename OtherRootT::MapIter OtherIterT;
982  typedef typename OtherRootT::MapCIter OtherCIterT;
983 
984  if (!hasSameConfiguration(other)) return false;
985 
986  // Create a local copy of the other node's table.
987  OtherMapT copyOfOtherTable = other.mTable;
988 
989  // For each entry in this node's table...
990  for (MapCIter thisIter = mTable.begin(); thisIter != mTable.end(); ++thisIter) {
991  if (this->isBackgroundTile(thisIter)) continue; // ignore background tiles
992 
993  // Fail if there is no corresponding entry in the other node's table.
994  OtherCIterT otherIter = other.findKey(thisIter->first);
995  if (otherIter == other.mTable.end()) return false;
996 
997  // Fail if this entry is a tile and the other is a child or vice-versa.
998  if (isChild(thisIter)) {//thisIter points to a child
999  if (OtherRootT::isTile(otherIter)) return false;
1000  // Fail if both entries are children, but the children have different topology.
1001  if (!getChild(thisIter).hasSameTopology(&OtherRootT::getChild(otherIter))) return false;
1002  } else {//thisIter points to a tile
1003  if (OtherRootT::isChild(otherIter)) return false;
1004  if (getTile(thisIter).active != OtherRootT::getTile(otherIter).active) return false;
1005  }
1006 
1007  // Remove tiles and child nodes with matching topology from
1008  // the copy of the other node's table. This is required since
1009  // the two root tables can include an arbitrary number of
1010  // background tiles and still have the same topology!
1011  copyOfOtherTable.erase(otherIter->first);
1012  }
1013  // Fail if the remaining entries in copyOfOtherTable are not all background tiles.
1014  for (OtherIterT i = copyOfOtherTable.begin(), e = copyOfOtherTable.end(); i != e; ++i) {
1015  if (!other.isBackgroundTile(i)) return false;
1016  }
1017  return true;
1018 }
1019 
1020 
1021 template<typename ChildT>
1022 template<typename OtherChildType>
1023 inline bool
1025 {
1026  std::vector<Index> thisDims, otherDims;
1027  RootNode::getNodeLog2Dims(thisDims);
1029  return (thisDims == otherDims);
1030 }
1031 
1032 
1033 template<typename ChildT>
1034 template<typename OtherChildType>
1035 inline void
1037 {
1038  std::vector<Index> thisDims, otherDims;
1039  RootNode::getNodeLog2Dims(thisDims);
1041  if (thisDims != otherDims) {
1042  std::ostringstream ostr;
1043  ostr << "grids have incompatible configurations (" << thisDims[0];
1044  for (size_t i = 1, N = thisDims.size(); i < N; ++i) ostr << " x " << thisDims[i];
1045  ostr << " vs. " << otherDims[0];
1046  for (size_t i = 1, N = otherDims.size(); i < N; ++i) ostr << " x " << otherDims[i];
1047  ostr << ")";
1048  OPENVDB_THROW(TypeError, ostr.str());
1049  }
1050 }
1051 
1052 
1054 
1055 
1056 template<typename ChildT>
1057 inline Index64
1059 {
1060  Index64 sum = sizeof(*this);
1061  for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1062  if (const ChildT *child = iter->second.child) {
1063  sum += child->memUsage();
1064  }
1065  }
1066  return sum;
1067 }
1068 
1069 template<typename ChildT>
1070 inline void
1072 {
1073  for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1074  if (const ChildT *child = iter->second.child) {
1075  child->evalActiveVoxelBoundingBox(bbox);
1076  } else if (isTileOn(iter)) {
1077  bbox.expand(iter->first, ChildT::DIM);
1078  }
1079  }
1080 }
1081 
1082 
1083 template<typename ChildT>
1084 inline void
1086 {
1087  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1088  delete i->second.child;
1089  }
1090  mTable.clear();
1091 }
1092 
1093 
1094 template<typename ChildT>
1095 inline Index
1096 RootNode<ChildT>::getChildCount() const {
1097  Index sum = 0;
1098  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1099  if (isChild(i)) ++sum;
1100  }
1101  return sum;
1102 }
1103 
1104 
1105 template<typename ChildT>
1106 inline Index
1107 RootNode<ChildT>::getTileCount() const
1108 {
1109  Index sum = 0;
1110  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1111  if (isTile(i)) ++sum;
1112  }
1113  return sum;
1114 }
1115 
1116 
1117 template<typename ChildT>
1118 inline Index
1119 RootNode<ChildT>::getActiveTileCount() const
1120 {
1121  Index sum = 0;
1122  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1123  if (isTileOn(i)) ++sum;
1124  }
1125  return sum;
1126 }
1127 
1128 
1129 template<typename ChildT>
1130 inline Index
1131 RootNode<ChildT>::getInactiveTileCount() const
1132 {
1133  Index sum = 0;
1134  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1135  if (isTileOff(i)) ++sum;
1136  }
1137  return sum;
1138 }
1139 
1140 
1141 template<typename ChildT>
1142 inline Index32
1144 {
1145  Index32 sum = 0;
1146  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1147  if (isChild(i)) sum += getChild(i).leafCount();
1148  }
1149  return sum;
1150 }
1151 
1152 
1153 template<typename ChildT>
1154 inline Index32
1156 {
1157  Index32 sum = 1;
1158  if (ChildT::LEVEL != 0) {
1159  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1160  if (isChild(i)) sum += getChild(i).nonLeafCount();
1161  }
1162  }
1163  return sum;
1164 }
1165 
1166 
1167 template<typename ChildT>
1168 inline Index64
1170 {
1171  Index64 sum = 0;
1172  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1173  if (isChild(i)) {
1174  sum += getChild(i).onVoxelCount();
1175  } else if (isTileOn(i)) {
1176  sum += ChildT::NUM_VOXELS;
1177  }
1178  }
1179  return sum;
1180 }
1181 
1182 
1183 template<typename ChildT>
1184 inline Index64
1186 {
1187  Index64 sum = 0;
1188  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1189  if (isChild(i)) {
1190  sum += getChild(i).offVoxelCount();
1191  } else if (isTileOff(i) && !this->isBackgroundTile(i)) {
1192  sum += ChildT::NUM_VOXELS;
1193  }
1194  }
1195  return sum;
1196 }
1197 
1198 
1199 template<typename ChildT>
1200 inline Index64
1202 {
1203  Index64 sum = 0;
1204  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1205  if (isChild(i)) sum += getChild(i).onLeafVoxelCount();
1206  }
1207  return sum;
1208 }
1209 
1210 
1211 template<typename ChildT>
1212 inline Index64
1214 {
1215  Index64 sum = 0;
1216  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1217  if (isChild(i)) sum += getChild(i).offLeafVoxelCount();
1218  }
1219  return sum;
1220 }
1221 
1222 
1224 
1225 
1226 template<typename ChildT>
1227 inline bool
1229 {
1230  MapCIter iter = this->findCoord(xyz);
1231  if (iter == mTable.end() || isTileOff(iter)) return false;
1232  return isTileOn(iter) ? true : getChild(iter).isValueOn(xyz);
1233 }
1234 
1235 template<typename ChildT>
1236 inline bool
1238 {
1239  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1240  if (isChild(i) ? getChild(i).hasActiveTiles() : getTile(i).active) return true;
1241  }
1242  return false;
1243 }
1244 
1245 template<typename ChildT>
1246 template<typename AccessorT>
1247 inline bool
1248 RootNode<ChildT>::isValueOnAndCache(const Coord& xyz, AccessorT& acc) const
1249 {
1250  MapCIter iter = this->findCoord(xyz);
1251  if (iter == mTable.end() || isTileOff(iter)) return false;
1252  if (isTileOn(iter)) return true;
1253  acc.insert(xyz, &getChild(iter));
1254  return getChild(iter).isValueOnAndCache(xyz, acc);
1255 }
1256 
1257 
1258 template<typename ChildT>
1259 inline const typename ChildT::ValueType&
1261 {
1262  MapCIter iter = this->findCoord(xyz);
1263  return iter == mTable.end() ? mBackground
1264  : (isTile(iter) ? getTile(iter).value : getChild(iter).getValue(xyz));
1265 }
1266 
1267 template<typename ChildT>
1268 template<typename AccessorT>
1269 inline const typename ChildT::ValueType&
1270 RootNode<ChildT>::getValueAndCache(const Coord& xyz, AccessorT& acc) const
1271 {
1272  MapCIter iter = this->findCoord(xyz);
1273  if (iter == mTable.end()) return mBackground;
1274  if (isChild(iter)) {
1275  acc.insert(xyz, &getChild(iter));
1276  return getChild(iter).getValueAndCache(xyz, acc);
1277  }
1278  return getTile(iter).value;
1279 }
1280 
1281 
1282 template<typename ChildT>
1283 inline int
1285 {
1286  MapCIter iter = this->findCoord(xyz);
1287  return iter == mTable.end() ? -1
1288  : (isTile(iter) ? 0 : int(LEVEL) - int(getChild(iter).getValueLevel(xyz)));
1289 }
1290 
1291 template<typename ChildT>
1292 template<typename AccessorT>
1293 inline int
1294 RootNode<ChildT>::getValueDepthAndCache(const Coord& xyz, AccessorT& acc) const
1295 {
1296  MapCIter iter = this->findCoord(xyz);
1297  if (iter == mTable.end()) return -1;
1298  if (isTile(iter)) return 0;
1299  acc.insert(xyz, &getChild(iter));
1300  return int(LEVEL) - int(getChild(iter).getValueLevelAndCache(xyz, acc));
1301 }
1302 
1303 
1304 template<typename ChildT>
1305 inline void
1307 {
1308  MapIter iter = this->findCoord(xyz);
1309  if (iter != mTable.end() && !isTileOff(iter)) {
1310  if (isTileOn(iter)) {
1311  setChild(iter, *new ChildT(xyz, getTile(iter).value, /*active=*/true));
1312  }
1313  getChild(iter).setValueOff(xyz);
1314  }
1315 }
1316 
1317 
1318 template<typename ChildT>
1319 inline void
1321 {
1322  ChildT* child = NULL;
1323  MapIter iter = this->findCoord(xyz);
1324  if (iter == mTable.end()) {
1325  if (on) {
1326  child = new ChildT(xyz, mBackground);
1327  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1328  } else {
1329  // Nothing to do; (x, y, z) is background and therefore already inactive.
1330  }
1331  } else if (isChild(iter)) {
1332  child = &getChild(iter);
1333  } else if (on != getTile(iter).active) {
1334  child = new ChildT(xyz, getTile(iter).value, !on);
1335  setChild(iter, *child);
1336  }
1337  if (child) child->setActiveState(xyz, on);
1338 }
1339 
1340 template<typename ChildT>
1341 template<typename AccessorT>
1342 inline void
1343 RootNode<ChildT>::setActiveStateAndCache(const Coord& xyz, bool on, AccessorT& acc)
1344 {
1345  ChildT* child = NULL;
1346  MapIter iter = this->findCoord(xyz);
1347  if (iter == mTable.end()) {
1348  if (on) {
1349  child = new ChildT(xyz, mBackground);
1350  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1351  } else {
1352  // Nothing to do; (x, y, z) is background and therefore already inactive.
1353  }
1354  } else if (isChild(iter)) {
1355  child = &getChild(iter);
1356  } else if (on != getTile(iter).active) {
1357  child = new ChildT(xyz, getTile(iter).value, !on);
1358  setChild(iter, *child);
1359  }
1360  if (child) {
1361  acc.insert(xyz, child);
1362  child->setActiveStateAndCache(xyz, on, acc);
1363  }
1364 }
1365 
1366 
1367 template<typename ChildT>
1368 inline void
1370 {
1371  ChildT* child = NULL;
1372  MapIter iter = this->findCoord(xyz);
1373  if (iter == mTable.end()) {
1374  if (!math::isExactlyEqual(mBackground, value)) {
1375  child = new ChildT(xyz, mBackground);
1376  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1377  }
1378  } else if (isChild(iter)) {
1379  child = &getChild(iter);
1380  } else if (isTileOn(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1381  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1382  setChild(iter, *child);
1383  }
1384  if (child) child->setValueOff(xyz, value);
1385 }
1386 
1387 template<typename ChildT>
1388 template<typename AccessorT>
1389 inline void
1390 RootNode<ChildT>::setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1391 {
1392  ChildT* child = NULL;
1393  MapIter iter = this->findCoord(xyz);
1394  if (iter == mTable.end()) {
1395  if (!math::isExactlyEqual(mBackground, value)) {
1396  child = new ChildT(xyz, mBackground);
1397  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1398  }
1399  } else if (isChild(iter)) {
1400  child = &getChild(iter);
1401  } else if (isTileOn(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1402  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1403  setChild(iter, *child);
1404  }
1405  if (child) {
1406  acc.insert(xyz, child);
1407  child->setValueOffAndCache(xyz, value, acc);
1408  }
1409 }
1410 
1411 
1412 template<typename ChildT>
1413 inline void
1415 {
1416  ChildT* child = NULL;
1417  MapIter iter = this->findCoord(xyz);
1418  if (iter == mTable.end()) {
1419  child = new ChildT(xyz, mBackground);
1420  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1421  } else if (isChild(iter)) {
1422  child = &getChild(iter);
1423  } else if (isTileOff(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1424  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1425  setChild(iter, *child);
1426  }
1427  if (child) child->setValueOn(xyz, value);
1428 }
1429 
1430 template<typename ChildT>
1431 template<typename AccessorT>
1432 inline void
1433 RootNode<ChildT>::setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1434 {
1435  ChildT* child = NULL;
1436  MapIter iter = this->findCoord(xyz);
1437  if (iter == mTable.end()) {
1438  child = new ChildT(xyz, mBackground);
1439  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1440  } else if (isChild(iter)) {
1441  child = &getChild(iter);
1442  } else if (isTileOff(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1443  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1444  setChild(iter, *child);
1445  }
1446  if (child) {
1447  acc.insert(xyz, child);
1448  child->setValueAndCache(xyz, value, acc);
1449  }
1450 }
1451 
1452 
1453 template<typename ChildT>
1454 inline void
1456 {
1457  ChildT* child = NULL;
1458  MapIter iter = this->findCoord(xyz);
1459  if (iter == mTable.end()) {
1460  child = new ChildT(xyz, mBackground);
1461  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1462  } else if (isChild(iter)) {
1463  child = &getChild(iter);
1464  } else if (!math::isExactlyEqual(getTile(iter).value, value)) {
1465  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1466  setChild(iter, *child);
1467  }
1468  if (child) child->setValueOnly(xyz, value);
1469 }
1470 
1471 template<typename ChildT>
1472 template<typename AccessorT>
1473 inline void
1474 RootNode<ChildT>::setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1475 {
1476  ChildT* child = NULL;
1477  MapIter iter = this->findCoord(xyz);
1478  if (iter == mTable.end()) {
1479  child = new ChildT(xyz, mBackground);
1480  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1481  } else if (isChild(iter)) {
1482  child = &getChild(iter);
1483  } else if (!math::isExactlyEqual(getTile(iter).value, value)) {
1484  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1485  setChild(iter, *child);
1486  }
1487  if (child) {
1488  acc.insert(xyz, child);
1489  child->setValueOnlyAndCache(xyz, value, acc);
1490  }
1491 }
1492 
1493 
1494 template<typename ChildT>
1495 inline void
1497 {
1498  ChildT* child = NULL;
1499  MapIter iter = this->findCoord(xyz);
1500  if (iter == mTable.end()) {
1501  child = new ChildT(xyz, mBackground);
1502  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1503  } else if (isChild(iter)) {
1504  child = &getChild(iter);
1505  } else if (isTileOff(iter) || getTile(iter).value > value) {
1506  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1507  setChild(iter, *child);
1508  }
1509  if (child) child->setValueOnMin(xyz, value);
1510 }
1511 
1512 
1513 template<typename ChildT>
1514 inline void
1516 {
1517  ChildT* child = NULL;
1518  MapIter iter = this->findCoord(xyz);
1519  if (iter == mTable.end()) {
1520  child = new ChildT(xyz, mBackground);
1521  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1522  } else if (isChild(iter)) {
1523  child = &getChild(iter);
1524  } else if (isTileOff(iter) || getTile(iter).value < value) {
1525  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1526  setChild(iter, *child);
1527  }
1528  if (child) child->setValueOnMax(xyz, value);
1529 }
1530 
1531 
1532 template<typename ChildT>
1533 inline void
1535 {
1536  ChildT* child = NULL;
1537  MapIter iter = this->findCoord(xyz);
1538  if (iter == mTable.end()) {
1539  child = new ChildT(xyz, mBackground);
1540  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1541  } else if (isChild(iter)) {
1542  child = &getChild(iter);
1543  } else if (isTileOff(iter) || !math::isZero(addend)) {
1544  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1545  setChild(iter, *child);
1546  }
1547  if (child) child->setValueOnSum(xyz, addend);
1548 }
1549 
1550 template<typename ChildT>
1551 template<typename AccessorT>
1552 inline void
1554  const ValueType& addend, AccessorT& acc)
1555 {
1556  ChildT* child = NULL;
1557  MapIter iter = this->findCoord(xyz);
1558  if (iter == mTable.end()) {
1559  child = new ChildT(xyz, mBackground);
1560  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1561  } else if (isChild(iter)) {
1562  child = &getChild(iter);
1563  } else if (isTileOff(iter) || !math::isZero(addend)) {
1564  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1565  setChild(iter, *child);
1566  }
1567  if (child) {
1568  acc.insert(xyz, child);
1569  child->setValueOnSumAndCache(xyz, addend, acc);
1570  }
1571 }
1572 
1573 
1574 template<typename ChildT>
1575 inline bool
1577 {
1578  MapCIter iter = this->findCoord(xyz);
1579  if (iter == mTable.end()) {
1580  value = mBackground;
1581  return false;
1582  } else if (isChild(iter)) {
1583  return getChild(iter).probeValue(xyz, value);
1584  }
1585  value = getTile(iter).value;
1586  return isTileOn(iter);
1587 }
1588 
1589 template<typename ChildT>
1590 template<typename AccessorT>
1591 inline bool
1592 RootNode<ChildT>::probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT& acc) const
1593 {
1594  MapCIter iter = this->findCoord(xyz);
1595  if (iter == mTable.end()) {
1596  value = mBackground;
1597  return false;
1598  } else if (isChild(iter)) {
1599  acc.insert(xyz, &getChild(iter));
1600  return getChild(iter).probeValueAndCache(xyz, value, acc);
1601  }
1602  value = getTile(iter).value;
1603  return isTileOn(iter);
1604 }
1605 
1606 
1608 
1609 
1610 template<typename ChildT>
1611 inline void
1612 RootNode<ChildT>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
1613 {
1614  if (bbox.empty()) return;
1615 
1616  Coord xyz, tileMax;
1617  for (int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) {
1618  xyz.setX(x);
1619  for (int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) {
1620  xyz.setY(y);
1621  for (int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) {
1622  xyz.setZ(z);
1623 
1624  // Get the bounds of the tile that contains voxel (x, y, z).
1625  Coord tileMin = coordToKey(xyz);
1626  tileMax = tileMin.offsetBy(ChildT::DIM - 1);
1627 
1628  if (xyz != tileMin || Coord::lessThan(bbox.max(), tileMax)) {
1629  // If the box defined by (xyz, bbox.max()) doesn't completely enclose
1630  // the tile to which xyz belongs, create a child node (or retrieve
1631  // the existing one).
1632  ChildT* child = NULL;
1633  MapIter iter = this->findKey(tileMin);
1634  if (iter == mTable.end()) {
1635  // No child or tile exists. Create a child and initialize it
1636  // with the background value.
1637  child = new ChildT(xyz, mBackground);
1638  mTable[tileMin] = NodeStruct(*child);
1639  } else if (isTile(iter)) {
1640  // Replace the tile with a newly-created child that is initialized
1641  // with the tile's value and active state.
1642  const Tile& tile = getTile(iter);
1643  child = new ChildT(xyz, tile.value, tile.active);
1644  mTable[tileMin] = NodeStruct(*child);
1645  } else if (isChild(iter)) {
1646  child = &getChild(iter);
1647  }
1648  // Forward the fill request to the child.
1649  if (child) {
1650  child->fill(CoordBBox(xyz, Coord::minComponent(bbox.max(), tileMax)),
1651  value, active);
1652  }
1653  } else {
1654  // If the box given by (xyz, bbox.max()) completely encloses
1655  // the tile to which xyz belongs, create the tile (if it
1656  // doesn't already exist) and give it the fill value.
1657  MapIter iter = this->findOrAddCoord(tileMin);
1658  setTile(iter, Tile(value, active));
1659  }
1660  }
1661  }
1662  }
1663 }
1664 
1665 
1667 
1668 
1669 template<typename ChildT>
1670 inline bool
1671 RootNode<ChildT>::writeTopology(std::ostream& os, bool toHalf) const
1672 {
1673  if (!toHalf) {
1674  os.write(reinterpret_cast<const char*>(&mBackground), sizeof(ValueType));
1675  } else {
1676  ValueType truncatedVal = io::truncateRealToHalf(mBackground);
1677  os.write(reinterpret_cast<const char*>(&truncatedVal), sizeof(ValueType));
1678  }
1679  io::setGridBackgroundValuePtr(os, &mBackground);
1680 
1681  const Index numTiles = this->getTileCount(), numChildren = this->getChildCount();
1682  os.write(reinterpret_cast<const char*>(&numTiles), sizeof(Index));
1683  os.write(reinterpret_cast<const char*>(&numChildren), sizeof(Index));
1684 
1685  if (numTiles == 0 && numChildren == 0) return false;
1686 
1687  // Write tiles.
1688  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1689  if (isChild(i)) continue;
1690  os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 * sizeof(Int32));
1691  os.write(reinterpret_cast<const char*>(&getTile(i).value), sizeof(ValueType));
1692  os.write(reinterpret_cast<const char*>(&getTile(i).active), sizeof(bool));
1693  }
1694  // Write child nodes.
1695  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1696  if (isTile(i)) continue;
1697  os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 * sizeof(Int32));
1698  getChild(i).writeTopology(os, toHalf);
1699  }
1700 
1701  return true; // not empty
1702 }
1703 
1704 
1705 template<typename ChildT>
1706 inline bool
1707 RootNode<ChildT>::readTopology(std::istream& is, bool fromHalf)
1708 {
1709  // Delete the existing tree.
1710  this->clearTable();
1711 
1713  // Read and convert an older-format RootNode.
1714 
1715  // For backward compatibility with older file formats, read both
1716  // outside and inside background values.
1717  is.read(reinterpret_cast<char*>(&mBackground), sizeof(ValueType));
1718  ValueType inside;
1719  is.read(reinterpret_cast<char*>(&inside), sizeof(ValueType));
1720 
1721  io::setGridBackgroundValuePtr(is, &mBackground);
1722 
1723  // Read the index range.
1724  Coord rangeMin, rangeMax;
1725  is.read(reinterpret_cast<char*>(rangeMin.asPointer()), 3 * sizeof(Int32));
1726  is.read(reinterpret_cast<char*>(rangeMax.asPointer()), 3 * sizeof(Int32));
1727 
1728  this->initTable();
1729  Index tableSize = 0, log2Dim[4] = { 0, 0, 0, 0 };
1730  Int32 offset[3];
1731  for (int i = 0; i < 3; ++i) {
1732  offset[i] = rangeMin[i] >> ChildT::TOTAL;
1733  rangeMin[i] = offset[i] << ChildT::TOTAL;
1734  log2Dim[i] = 1 + util::FindHighestOn((rangeMax[i] >> ChildT::TOTAL) - offset[i]);
1735  tableSize += log2Dim[i];
1736  rangeMax[i] = (((1 << log2Dim[i]) + offset[i]) << ChildT::TOTAL) - 1;
1737  }
1738  log2Dim[3] = log2Dim[1] + log2Dim[2];
1739  tableSize = 1U << tableSize;
1740 
1741  // Read masks.
1742  util::RootNodeMask childMask(tableSize), valueMask(tableSize);
1743  childMask.load(is);
1744  valueMask.load(is);
1745 
1746  // Read child nodes/values.
1747  for (Index i = 0; i < tableSize; ++i) {
1748  // Compute origin = offset2coord(i).
1749  Index n = i;
1750  Coord origin;
1751  origin[0] = (n >> log2Dim[3]) + offset[0];
1752  n &= (1U << log2Dim[3]) - 1;
1753  origin[1] = (n >> log2Dim[2]) + offset[1];
1754  origin[2] = (n & ((1U << log2Dim[2]) - 1)) + offset[1];
1755  origin <<= ChildT::TOTAL;
1756 
1757  if (childMask.isOn(i)) {
1758  // Read in and insert a child node.
1759  ChildT* child = new ChildT(origin, mBackground);
1760  child->readTopology(is);
1761  mTable[origin] = NodeStruct(*child);
1762  } else {
1763  // Read in a tile value and insert a tile, but only if the value
1764  // is either active or non-background.
1765  ValueType value;
1766  is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
1767  if (valueMask.isOn(i) || (!math::isApproxEqual(value, mBackground))) {
1768  mTable[origin] = NodeStruct(Tile(value, valueMask.isOn(i)));
1769  }
1770  }
1771  }
1772  return true;
1773  }
1774 
1775  // Read a RootNode that was stored in the current format.
1776 
1777  is.read(reinterpret_cast<char*>(&mBackground), sizeof(ValueType));
1778  io::setGridBackgroundValuePtr(is, &mBackground);
1779 
1780  Index numTiles = 0, numChildren = 0;
1781  is.read(reinterpret_cast<char*>(&numTiles), sizeof(Index));
1782  is.read(reinterpret_cast<char*>(&numChildren), sizeof(Index));
1783 
1784  if (numTiles == 0 && numChildren == 0) return false;
1785 
1786  Int32 vec[3];
1787  ValueType value;
1788  bool active;
1789 
1790  // Read tiles.
1791  for (Index n = 0; n < numTiles; ++n) {
1792  is.read(reinterpret_cast<char*>(vec), 3 * sizeof(Int32));
1793  is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
1794  is.read(reinterpret_cast<char*>(&active), sizeof(bool));
1795  mTable[Coord(vec)] = NodeStruct(Tile(value, active));
1796  }
1797 
1798  // Read child nodes.
1799  for (Index n = 0; n < numChildren; ++n) {
1800  is.read(reinterpret_cast<char*>(vec), 3 * sizeof(Int32));
1801  Coord origin(vec);
1802  ChildT* child = new ChildT(origin, mBackground);
1803  child->readTopology(is, fromHalf);
1804  mTable[Coord(vec)] = NodeStruct(*child);
1805  }
1806 
1807  return true; // not empty
1808 }
1809 
1810 
1811 template<typename ChildT>
1812 inline void
1813 RootNode<ChildT>::writeBuffers(std::ostream& os, bool toHalf) const
1814 {
1815  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1816  if (isChild(i)) getChild(i).writeBuffers(os, toHalf);
1817  }
1818 }
1819 
1820 
1821 template<typename ChildT>
1822 inline void
1823 RootNode<ChildT>::readBuffers(std::istream& is, bool fromHalf)
1824 {
1825  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1826  if (isChild(i)) getChild(i).readBuffers(is, fromHalf);
1827  }
1828 }
1829 
1830 
1832 
1833 
1834 template<typename ChildT>
1835 template<typename PruneOp>
1836 inline void
1838 {
1839  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1840  if (this->isTile(i)|| !op(this->getChild(i))) continue;
1841  this->setTile(i, Tile(op.value, op.state));
1842  }
1843  this->eraseBackgroundTiles();
1844 }
1845 
1846 
1847 template<typename ChildT>
1848 inline void
1850 {
1851  TolerancePrune<ValueType> op(tolerance);
1852  this->pruneOp(op);
1853 }
1854 
1855 
1856 template<typename ChildT>
1857 inline void
1859 {
1860  InactivePrune<ValueType> op(bg);
1861  this->pruneOp(op);
1862 }
1863 
1864 
1865 template<typename ChildT>
1866 inline void
1868 {
1869  this->pruneInactive(mBackground);
1870 }
1871 
1872 
1874 
1875 
1876 template<typename ChildT>
1877 inline typename ChildT::LeafNodeType*
1879 {
1880  ChildT* child = NULL;
1881  MapIter iter = this->findCoord(xyz);
1882  if (iter == mTable.end()) {
1883  child = new ChildT(xyz, mBackground, false);
1884  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1885  } else if (isChild(iter)) {
1886  child = &getChild(iter);
1887  } else {
1888  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1889  setChild(iter, *child);
1890  }
1891  return child->touchLeaf(xyz);
1892 }
1893 
1894 
1895 template<typename ChildT>
1896 template<typename AccessorT>
1897 inline typename ChildT::LeafNodeType*
1898 RootNode<ChildT>::touchLeafAndCache(const Coord& xyz, AccessorT& acc)
1899 {
1900  ChildT* child = NULL;
1901  MapIter iter = this->findCoord(xyz);
1902  if (iter == mTable.end()) {
1903  child = new ChildT(xyz, mBackground, false);
1904  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1905  } else if (isChild(iter)) {
1906  child = &getChild(iter);
1907  } else {
1908  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1909  setChild(iter, *child);
1910  }
1911  acc.insert(xyz, child);
1912  return child->touchLeafAndCache(xyz, acc);
1913 }
1914 
1915 
1917 
1918 
1919 template<typename ChildT>
1920 inline typename ChildT::LeafNodeType*
1922 {
1923  MapIter iter = this->findCoord(xyz);
1924  if (iter == mTable.end() || isTile(iter)) return NULL;
1925  return getChild(iter).probeLeaf(xyz);
1926 }
1927 
1928 
1929 template<typename ChildT>
1930 inline const typename ChildT::LeafNodeType*
1932 {
1933  MapCIter iter = this->findCoord(xyz);
1934  if (iter == mTable.end() || isTile(iter)) return NULL;
1935  return getChild(iter).probeConstLeaf(xyz);
1936 }
1937 
1938 
1939 template<typename ChildT>
1940 template<typename AccessorT>
1941 inline typename ChildT::LeafNodeType*
1942 RootNode<ChildT>::probeLeafAndCache(const Coord& xyz, AccessorT& acc)
1943 {
1944  MapIter iter = this->findCoord(xyz);
1945  if (iter == mTable.end() || isTile(iter)) return NULL;
1946  ChildT* child = &getChild(iter);
1947  acc.insert(xyz, child);
1948  return child->probeLeafAndCache(xyz, acc);
1949 }
1950 
1951 
1952 template<typename ChildT>
1953 template<typename AccessorT>
1954 inline const typename ChildT::LeafNodeType*
1955 RootNode<ChildT>::probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const
1956 {
1957  MapCIter iter = this->findCoord(xyz);
1958  if (iter == mTable.end() || isTile(iter)) return NULL;
1959  const ChildT* child = &getChild(iter);
1960  acc.insert(xyz, child);
1961  return child->probeConstLeafAndCache(xyz, acc);
1962 }
1963 
1964 
1966 
1967 
1968 template<typename ChildT>
1969 inline void
1971 {
1972  this->signedFloodFill(mBackground, negative(mBackground));
1973 }
1974 
1975 
1976 template<typename ChildT>
1977 inline void
1979 {
1980  const ValueType zero = zeroVal<ValueType>();
1981 
1982  mBackground = outside;
1983 
1984  // First, flood fill all child nodes and put child-keys into a sorted set
1985  CoordSet nodeKeys;
1986  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1987  if (this->isTile(i)) continue;
1988  getChild(i).signedFloodFill(outside, inside);
1989  nodeKeys.insert(i->first);//only add inactive tiles!
1990  }
1991 
1992  // We employ a simple z-scanline algorithm that inserts inactive
1993  // tiles with the inside value if they are sandwiched
1994  // between inside child nodes only!
1995  const Tile insideTile(inside, /*on=*/false);
1996  CoordSetCIter b = nodeKeys.begin(), e = nodeKeys.end();
1997  if ( b == e ) return;
1998  for (CoordSetCIter a = b++; b != e; ++a, ++b) {
1999  Coord d = *b - *a; // delta of neighboring keys
2000  if (d[0]!=0 || d[1]!=0 || d[2]==Int32(ChildT::DIM)) continue;//not z-scanline or neighbors
2001  MapIter i = mTable.find(*a), j = mTable.find(*b);
2002  const ValueType fill[] = { getChild(i).getLastValue(), getChild(j).getFirstValue() };
2003  if (!(fill[0] < zero) || !(fill[1] < zero)) continue; // scanline isn't inside
2004  for (Coord c = *a + Coord(0u,0u,ChildT::DIM); c[2] != (*b)[2]; c[2] += ChildT::DIM) {
2005  mTable[c] = insideTile;
2006  }
2007  }
2008 }
2009 
2010 
2012 
2013 
2014 template<typename ChildT>
2015 inline void
2017 {
2018  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2019  if (this->isTileOff(i)) continue;
2020  ChildT* child = i->second.child;
2021  if (child==NULL) {
2022  child = new ChildT(i->first, this->getTile(i).value, true);
2023  i->second.child = child;
2024  }
2025  child->voxelizeActiveTiles();
2026  }
2027 }
2028 
2029 
2031 
2032 
2033 template<typename ChildT>
2034 inline void
2036 {
2037  for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2038  MapIter j = mTable.find(i->first);
2039  if (other.isChild(i)) {
2040  if (j == mTable.end()) { // insert other child node
2041  mTable[i->first]=NodeStruct(stealChild(i, Tile(other.mBackground, /*on=*/false)));
2042  } else if (isTile(j)) { // replace tile with other child node
2043  setChild(j, stealChild(i, Tile(other.mBackground, /*on=*/false)));
2044  } else { // merge both child nodes
2045  getChild(j).merge(getChild(i),other.mBackground, mBackground);
2046  }
2047  } else { // other is a tile
2048  if (j == mTable.end()) { // insert other tile
2049  mTable[i->first] = i->second;
2050  } else continue; // ignore other tile
2051  }
2052  }
2053  // Empty the other tree so as not to leave it in a partially cannibalized state.
2054  other.clear();
2055 }
2056 
2057 
2059 
2060 
2061 template<typename ChildT>
2062 template<typename OtherChildType>
2063 inline void
2065 {
2066  typedef RootNode<OtherChildType> OtherRootT;
2067  typedef typename OtherRootT::MapCIter OtherCIterT;
2068 
2069  enforceSameConfiguration(other);
2070 
2071  for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2072  MapIter j = mTable.find(i->first);
2073  if (other.isChild(i)) {
2074  if (j == mTable.end()) { // create child branch with identical topology
2075  mTable[i->first] = NodeStruct(
2076  *(new ChildT(other.getChild(i), mBackground, TopologyCopy())));
2077  } else if (this->isChild(j)) { // union with child branch
2078  this->getChild(j).topologyUnion(other.getChild(i));
2079  } else {// this is a tile so replace it with a child branch with identical topology
2080  ChildT* child = new ChildT(
2081  other.getChild(i), this->getTile(j).value, TopologyCopy());
2082  if (this->isTileOn(j)) child->setValuesOn();//this is an active tile
2083  this->setChild(j, *child);
2084  }
2085  } else if (other.isTileOn(i)) { // other is an active tile
2086  if (j == mTable.end()) { // insert an active tile
2087  mTable[i->first] = NodeStruct(Tile(mBackground, true));
2088  } else if (this->isChild(j)) {
2089  this->getChild(j).setValuesOn();
2090  } else if (this->isTileOff(j)) {
2091  this->setTile(j, Tile(this->getTile(j).value, true));
2092  }
2093  }
2094  }
2095 }
2096 
2097 
2099 
2100 
2101 template<typename ChildT>
2102 template<typename CombineOp>
2103 inline void
2104 RootNode<ChildT>::combine(RootNode& other, CombineOp& op, bool prune)
2105 {
2107 
2108  CoordSet keys;
2109  this->insertKeys(keys);
2110  other.insertKeys(keys);
2111 
2112  for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
2113  MapIter iter = findOrAddCoord(*i), otherIter = other.findOrAddCoord(*i);
2114  if (isTile(iter) && isTile(otherIter)) {
2115  // Both this node and the other node have constant values (tiles).
2116  // Combine the two values and store the result as this node's new tile value.
2117  op(args.setARef(getTile(iter).value)
2118  .setAIsActive(isTileOn(iter))
2119  .setBRef(getTile(otherIter).value)
2120  .setBIsActive(isTileOn(otherIter)));
2121  setTile(iter, Tile(args.result(), args.resultIsActive()));
2122 
2123  } else if (isChild(iter) && isTile(otherIter)) {
2124  // Combine this node's child with the other node's constant value.
2125  ChildT& child = getChild(iter);
2126  child.combine(getTile(otherIter).value, isTileOn(otherIter), op);
2127 
2128  } else if (isTile(iter) && isChild(otherIter)) {
2129  // Combine this node's constant value with the other node's child,
2130  // but use a new functor in which the A and B values are swapped,
2131  // since the constant value is the A value, not the B value.
2133  ChildT& child = getChild(otherIter);
2134  child.combine(getTile(iter).value, isTileOn(iter), swappedOp);
2135 
2136  // Steal the other node's child.
2137  setChild(iter, stealChild(otherIter, Tile()));
2138 
2139  } else /*if (isChild(iter) && isChild(otherIter))*/ {
2140  // Combine this node's child with the other node's child.
2141  ChildT &child = getChild(iter), &otherChild = getChild(otherIter);
2142  child.combine(otherChild, op);
2143  }
2144  if (prune && isChild(iter)) getChild(iter).prune();
2145  }
2146 
2147  // Combine background values.
2148  op(args.setARef(mBackground).setBRef(other.mBackground));
2149  mBackground = args.result();
2150 
2151  // Empty the other tree so as not to leave it in a partially cannibalized state.
2152  other.clear();
2153 }
2154 
2155 
2157 
2158 
2159 template<typename ChildT>
2160 template<typename CombineOp>
2161 inline void
2162 RootNode<ChildT>::combine2(const RootNode& other0, const RootNode& other1,
2163  CombineOp& op, bool prune)
2164 {
2166 
2167  CoordSet keys;
2168  other0.insertKeys(keys);
2169  other1.insertKeys(keys);
2170 
2171  const NodeStruct
2172  bg0(Tile(other0.mBackground, /*active=*/false)),
2173  bg1(Tile(other1.mBackground, /*active=*/false));
2174 
2175  for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
2176  MapIter thisIter = this->findOrAddCoord(*i);
2177  MapCIter iter0 = other0.findKey(*i), iter1 = other1.findKey(*i);
2178  const NodeStruct
2179  &ns0 = (iter0 != other0.mTable.end()) ? iter0->second : bg0,
2180  &ns1 = (iter1 != other1.mTable.end()) ? iter1->second : bg1;
2181  if (ns0.isTile() && ns1.isTile()) {
2182  // Both input nodes have constant values (tiles).
2183  // Combine the two values and add a new tile to this node with the result.
2184  op(args.setARef(ns0.tile.value)
2185  .setAIsActive(ns0.isTileOn())
2186  .setBRef(ns1.tile.value)
2187  .setBIsActive(ns1.isTileOn()));
2188  setTile(thisIter, Tile(args.result(), args.resultIsActive()));
2189  } else {
2190  ChildT& otherChild = ns0.isChild() ? *ns0.child : *ns1.child;
2191  if (!isChild(thisIter)) {
2192  // Add a new child with the same coordinates, etc. as the other node's child.
2193  setChild(thisIter,
2194  *(new ChildT(otherChild.getOrigin(), getTile(thisIter).value)));
2195  }
2196  ChildT& child = getChild(thisIter);
2197 
2198  if (ns0.isTile()) {
2199  // Combine node1's child with node0's constant value
2200  // and write the result into this node's child.
2201  child.combine2(ns0.tile.value, *ns1.child, ns0.isTileOn(), op);
2202  } else if (ns1.isTile()) {
2203  // Combine node0's child with node1's constant value
2204  // and write the result into this node's child.
2205  child.combine2(*ns0.child, ns1.tile.value, ns1.isTileOn(), op);
2206  } else {
2207  // Combine node0's child with node1's child
2208  // and write the result into this node's child.
2209  child.combine2(*ns0.child, *ns1.child, op);
2210  }
2211  }
2212  if (prune && isChild(thisIter)) getChild(thisIter).prune();
2213  }
2214 
2215  // Combine background values.
2216  op(args.setARef(other0.mBackground).setBRef(other1.mBackground));
2217  mBackground = args.result();
2218 }
2219 
2220 
2222 
2223 
2224 template<typename ChildT>
2225 template<typename BBoxOp>
2226 inline void
2228 {
2229  const bool descent = op.template descent<LEVEL>();
2230  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2231  if (this->isTileOff(i)) continue;
2232  if (this->isChild(i) && descent) {
2233  this->getChild(i).visitActiveBBox(op);
2234  } else {
2235 #ifdef _MSC_VER
2236  op.operator()<LEVEL>(CoordBBox::createCube(i->first, ChildT::DIM));
2237 #else
2238  op.template operator()<LEVEL>(CoordBBox::createCube(i->first, ChildT::DIM));
2239 #endif
2240  }
2241  }
2242 }
2243 
2244 
2245 template<typename ChildT>
2246 template<typename VisitorOp>
2247 inline void
2249 {
2250  doVisit<RootNode, VisitorOp, ChildAllIter>(*this, op);
2251 }
2252 
2253 
2254 template<typename ChildT>
2255 template<typename VisitorOp>
2256 inline void
2257 RootNode<ChildT>::visit(VisitorOp& op) const
2258 {
2259  doVisit<const RootNode, VisitorOp, ChildAllCIter>(*this, op);
2260 }
2261 
2262 
2263 template<typename ChildT>
2264 template<typename RootNodeT, typename VisitorOp, typename ChildAllIterT>
2265 inline void
2266 RootNode<ChildT>::doVisit(RootNodeT& self, VisitorOp& op)
2267 {
2268  typename RootNodeT::ValueType val;
2269  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
2270  if (op(iter)) continue;
2271  if (typename ChildAllIterT::ChildNodeType* child = iter.probeChild(val)) {
2272  child->visit(op);
2273  }
2274  }
2275 }
2276 
2277 
2279 
2280 
2281 template<typename ChildT>
2282 template<typename OtherRootNodeType, typename VisitorOp>
2283 inline void
2284 RootNode<ChildT>::visit2(OtherRootNodeType& other, VisitorOp& op)
2285 {
2286  doVisit2<RootNode, OtherRootNodeType, VisitorOp, ChildAllIter,
2287  typename OtherRootNodeType::ChildAllIter>(*this, other, op);
2288 }
2289 
2290 
2291 template<typename ChildT>
2292 template<typename OtherRootNodeType, typename VisitorOp>
2293 inline void
2294 RootNode<ChildT>::visit2(OtherRootNodeType& other, VisitorOp& op) const
2295 {
2296  doVisit2<const RootNode, OtherRootNodeType, VisitorOp, ChildAllCIter,
2297  typename OtherRootNodeType::ChildAllCIter>(*this, other, op);
2298 }
2299 
2300 
2301 template<typename ChildT>
2302 template<
2303  typename RootNodeT,
2304  typename OtherRootNodeT,
2305  typename VisitorOp,
2306  typename ChildAllIterT,
2307  typename OtherChildAllIterT>
2308 inline void
2309 RootNode<ChildT>::doVisit2(RootNodeT& self, OtherRootNodeT& other, VisitorOp& op)
2310 {
2313  enforceSameConfiguration(other);
2314 
2315  typename RootNodeT::ValueType val;
2316  typename OtherRootNodeT::ValueType otherVal;
2317 
2318  // The two nodes are required to have corresponding table entries,
2319  // but since that might require background tiles to be added to one or both,
2320  // and the nodes might be const, we operate on shallow copies of the nodes instead.
2321  RootNodeT copyOfSelf(self.mBackground);
2322  copyOfSelf.mTable = self.mTable;
2323  OtherRootNodeT copyOfOther(other.mBackground);
2324  copyOfOther.mTable = other.mTable;
2325 
2326  // Add background tiles to both nodes as needed.
2327  CoordSet keys;
2328  self.insertKeys(keys);
2329  other.insertKeys(keys);
2330  for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
2331  copyOfSelf.findOrAddCoord(*i);
2332  copyOfOther.findOrAddCoord(*i);
2333  }
2334 
2335  ChildAllIterT iter = copyOfSelf.beginChildAll();
2336  OtherChildAllIterT otherIter = copyOfOther.beginChildAll();
2337 
2338  for ( ; iter && otherIter; ++iter, ++otherIter)
2339  {
2340  const size_t skipBranch = static_cast<size_t>(op(iter, otherIter));
2341 
2342  typename ChildAllIterT::ChildNodeType* child =
2343  (skipBranch & 1U) ? NULL : iter.probeChild(val);
2344  typename OtherChildAllIterT::ChildNodeType* otherChild =
2345  (skipBranch & 2U) ? NULL : otherIter.probeChild(otherVal);
2346 
2347  if (child != NULL && otherChild != NULL) {
2348  child->visit2Node(*otherChild, op);
2349  } else if (child != NULL) {
2350  child->visit2(otherIter, op);
2351  } else if (otherChild != NULL) {
2352  otherChild->visit2(iter, op, /*otherIsLHS=*/true);
2353  }
2354  }
2355  // Remove any background tiles that were added above,
2356  // as well as any that were created by the visitors.
2357  copyOfSelf.eraseBackgroundTiles();
2358  copyOfOther.eraseBackgroundTiles();
2359 
2360  // If either input node is non-const, replace its table with
2361  // the (possibly modified) copy.
2362  self.resetTable(copyOfSelf.mTable);
2363  other.resetTable(copyOfOther.mTable);
2364 }
2365 
2366 } // namespace tree
2367 } // namespace OPENVDB_VERSION_NAME
2368 } // namespace openvdb
2369 
2370 #endif // OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
2371 
2372 // Copyright (c) 2012-2013 DreamWorks Animation LLC
2373 // All rights reserved. This software is distributed under the
2374 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )