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