OpenVDB  1.2.0
RootNode.h
Go to the documentation of this file.
1 //
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  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 
499  template<typename DenseT>
500  void copyToDense(const CoordBBox& bbox, DenseT& dense) const;
501 
502  //
503  // I/O
504  //
505  bool writeTopology(std::ostream&, bool toHalf = false) const;
506  bool readTopology(std::istream&, bool fromHalf = false);
507 
508  void writeBuffers(std::ostream&, bool toHalf = false) const;
509  void readBuffers(std::istream&, bool fromHalf = false);
510 
515  template<typename AccessorT>
516  const ValueType& getValueAndCache(const Coord& xyz, AccessorT&) const;
521  template<typename AccessorT>
522  bool isValueOnAndCache(const Coord& xyz, AccessorT&) const;
523 
528  template<typename AccessorT>
529  void setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
530 
535  template<typename AccessorT>
536  void setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
537 
543  template<typename AccessorT>
544  void setValueOnSumAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
545 
550  template<typename AccessorT>
551  void setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
552 
557  template<typename AccessorT>
558  void setActiveStateAndCache(const Coord& xyz, bool on, AccessorT&);
559 
564  template<typename AccessorT>
565  bool probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT&) const;
566 
572  template<typename AccessorT>
573  int getValueDepthAndCache(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 
596  void pruneTiles(const ValueType&);
597 
600  void addLeaf(LeafNodeType* leaf);
601 
604  template<typename AccessorT>
605  void addLeafAndCache(LeafNodeType* leaf, AccessorT&);
606 
615  template<typename NodeT>
616  NodeT* stealNode(const Coord& xyz, const ValueType& value, bool state);
617 
620  void addTile(Index level, const Coord& xyz, const ValueType& value, bool state);
621 
624  template<typename AccessorT>
625  void addTileAndCache(Index level, const Coord& xyz, const ValueType& value,
626  bool state, AccessorT&);
627 
634  LeafNodeType* touchLeaf(const Coord& xyz);
635 
638  template<typename AccessorT>
639  LeafNodeType* touchLeafAndCache(const Coord& xyz, AccessorT& acc);
640 
643  template <typename NodeT>
644  NodeT* probeNode(const Coord& xyz);
645  template <typename NodeT>
646  const NodeT* probeConstNode(const Coord& xyz) const;
647 
651  template<typename NodeT, typename AccessorT>
652  NodeT* probeNodeAndCache(const Coord& xyz, AccessorT& acc);
653 
656  template<typename NodeT, typename AccessorT>
657  const NodeT* probeConstNodeAndCache(const Coord& xyz, AccessorT& acc) const;
658 
661  LeafNodeType* probeLeaf(const Coord& xyz) {return this->template probeNode<LeafNodeType>(xyz);}
662 
665  const LeafNodeType* probeConstLeaf(const Coord& xyz) const
666  {
667  return this->template probeConstNode<LeafNodeType>(xyz);
668  }
670  const LeafNodeType* probeLeaf(const Coord& xyz) const { return this->probeConstLeaf(xyz); }
671 
674  template<typename AccessorT>
675  LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc)
676  {
677  return this->template probeNodeAndCache<LeafNodeType>(xyz, acc);
678  }
679 
682  template<typename AccessorT>
683  const LeafNodeType* probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const
684  {
685  return this->template probeConstNodeAndCache<LeafNodeType>(xyz, acc);
686  }
688  template<typename AccessorT>
689  const LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc) const
690  {
691  return this->probeConstLeafAndCache(xyz, acc);
692  }
693 
695  template<typename NodeT>
696  static bool hasNodeType();
697 
703  void signedFloodFill();
704 
711  void signedFloodFill(const ValueType& outside, const ValueType& inside);
712 
718  void merge(RootNode& other);
719 
721  void voxelizeActiveTiles();
722 
736  template<typename OtherChildType>
737  void topologyUnion(const RootNode<OtherChildType>& other);
738 
739  template<typename CombineOp>
740  void combine(RootNode& other, CombineOp&, bool prune = false);
741 
742  template<typename CombineOp>
743  void combine2(const RootNode& other0, const RootNode& other1,
744  CombineOp& op, bool prune = false);
745 
751  template<typename BBoxOp> void visitActiveBBox(BBoxOp&) const;
752 
753  template<typename VisitorOp> void visit(VisitorOp&);
754  template<typename VisitorOp> void visit(VisitorOp&) const;
755 
756  template<typename OtherRootNodeType, typename VisitorOp>
757  void visit2(OtherRootNodeType& other, VisitorOp&);
758  template<typename OtherRootNodeType, typename VisitorOp>
759  void visit2(OtherRootNodeType& other, VisitorOp&) const;
760 
761 private:
764  template<typename> friend class RootNode;
765 
767  void initTable() {}
768  inline void clearTable();
770  void resetTable(MapType& table) { mTable.swap(table); table.clear(); }
772  void resetTable(const MapType&) const {}
774 
775  Index getChildCount() const;
776  Index getTileCount() const;
777  Index getActiveTileCount() const;
778  Index getInactiveTileCount() const;
779 
781  static Coord coordToKey(const Coord& xyz) { return xyz & ~(ChildType::DIM - 1); }
782 
784  void insertKeys(CoordSet&) const;
785 
787  bool hasKey(const Coord& key) const { return mTable.find(key) != mTable.end(); }
789  MapIter findKey(const Coord& key) { return mTable.find(key); }
792  MapCIter findKey(const Coord& key) const { return mTable.find(key); }
794 
795  MapIter findCoord(const Coord& xyz) { return mTable.find(coordToKey(xyz)); }
798  MapCIter findCoord(const Coord& xyz) const { return mTable.find(coordToKey(xyz)); }
800  MapIter findOrAddCoord(const Coord& xyz);
804 
806  template<typename OtherChildType>
807  static void enforceSameConfiguration(const RootNode<OtherChildType>& other);
808 
809  template<typename RootNodeT, typename VisitorOp, typename ChildAllIterT>
810  static inline void doVisit(RootNodeT&, VisitorOp&);
811 
812  template<typename RootNodeT, typename OtherRootNodeT, typename VisitorOp,
813  typename ChildAllIterT, typename OtherChildAllIterT>
814  static inline void doVisit2(RootNodeT&, OtherRootNodeT&, VisitorOp&);
815 
816 
817  MapType mTable;
818  ValueType mBackground;
819 }; // end of RootNode class
820 
821 
823 
824 
825 template<typename ChildT>
826 inline
828 {
829  this->initTable();
830 }
831 
832 
833 template<typename ChildT>
834 inline
835 RootNode<ChildT>::RootNode(const ValueType& background) : mBackground(background)
836 {
837  this->initTable();
838 }
839 
840 
841 template<typename ChildT>
842 template<typename OtherChildType>
843 inline
845  const ValueType& backgd, const ValueType& foregd, TopologyCopy):
846  mBackground(backgd)
847 {
848  typedef RootNode<OtherChildType> OtherRootT;
849 
851  enforceSameConfiguration(other);
852 
853  const Tile bgTile(backgd, /*active=*/false), fgTile(foregd, true);
854  this->initTable();
855 
856  for (typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
857  mTable[i->first] = OtherRootT::isTile(i)
858  ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
859  : NodeStruct(*(new ChildT(OtherRootT::getChild(i), backgd, foregd, TopologyCopy())));
860  }
861 }
862 
863 
864 template<typename ChildT>
865 template<typename OtherChildType>
866 inline
868  const ValueType& backgd, TopologyCopy):
869  mBackground(backgd)
870 {
871  typedef RootNode<OtherChildType> OtherRootT;
872 
874  enforceSameConfiguration(other);
875 
876  const Tile bgTile(backgd, /*active=*/false), fgTile(backgd, true);
877  this->initTable();
878  for (typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
879  mTable[i->first] = OtherRootT::isTile(i)
880  ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
881  : NodeStruct(*(new ChildT(OtherRootT::getChild(i), backgd, TopologyCopy())));
882  }
883 }
884 
885 
886 template<typename ChildT>
887 inline RootNode<ChildT>&
889 {
890  mBackground = other.mBackground;
891 
892  this->clearTable();
893  this->initTable();
894 
895  for (MapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
896  mTable[i->first] =
897  isTile(i) ? NodeStruct(getTile(i)) : NodeStruct(*(new ChildT(getChild(i))));
898  }
899  return *this;
900 }
901 
902 
904 
905 
906 template<typename ChildT>
907 inline void
909 {
910  if (math::isExactlyEqual(background, mBackground)) return;
911 
912  // Traverse the tree, replacing occurrences of mBackground with background
913  // and -mBackground with -background.
914  for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
915  ChildT *child = iter->second.child;
916  if (child) {
917  child->resetBackground(/*old=*/mBackground, /*new=*/background);
918  } else {
919  Tile& tile = getTile(iter);
920  if (tile.active) continue;//only change inactive tiles
921  if (math::isApproxEqual(tile.value, mBackground)) {
922  tile.value = background;
923  } else if (math::isApproxEqual(tile.value, negative(mBackground))) {
924  tile.value = negative(background);
925  }
926  }
927  }
928  mBackground = background;
929 }
930 
931 
932 template<typename ChildT>
933 inline bool
934 RootNode<ChildT>::isBackgroundTile(const Tile& tile) const
935 {
936  return !tile.active && math::isApproxEqual(tile.value, mBackground);
937 }
938 
939 template<typename ChildT>
940 inline bool
941 RootNode<ChildT>::isBackgroundTile(const MapIter& iter) const
942 {
943  return isTileOff(iter) && math::isApproxEqual(getTile(iter).value, mBackground);
944 }
945 
946 template<typename ChildT>
947 inline bool
948 RootNode<ChildT>::isBackgroundTile(const MapCIter& iter) const
949 {
950  return isTileOff(iter) && math::isApproxEqual(getTile(iter).value, mBackground);
951 }
952 
953 
954 template<typename ChildT>
955 inline size_t
957 {
958  size_t count = 0;
959  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
960  if (this->isBackgroundTile(i)) ++count;
961  }
962  return count;
963 }
964 
965 
966 template<typename ChildT>
967 inline size_t
969 {
970  std::set<Coord> keysToErase;
971  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
972  if (this->isBackgroundTile(i)) keysToErase.insert(i->first);
973  }
974  for (std::set<Coord>::iterator i = keysToErase.begin(), e = keysToErase.end(); i != e; ++i) {
975  mTable.erase(*i);
976  }
977  return keysToErase.size();
978 }
979 
980 
982 
983 
984 template<typename ChildT>
985 inline void
986 RootNode<ChildT>::insertKeys(CoordSet& keys) const
987 {
988  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
989  keys.insert(i->first);
990  }
991 }
992 
993 
994 template<typename ChildT>
995 inline typename RootNode<ChildT>::MapIter
996 RootNode<ChildT>::findOrAddCoord(const Coord& xyz)
997 {
998  const Coord key = coordToKey(xyz);
999  std::pair<MapIter, bool> result = mTable.insert(
1000  typename MapType::value_type(key, NodeStruct(Tile(mBackground, /*active=*/false))));
1001  return result.first;
1002 }
1003 
1004 
1005 template<typename ChildT>
1006 inline bool
1008 {
1009  const Coord key = coordToKey(xyz);
1010  std::pair<MapIter, bool> result = mTable.insert(
1011  typename MapType::value_type(key, NodeStruct(Tile(mBackground, /*active=*/false))));
1012  return result.second; // return true if the key did not already exist
1013 }
1014 
1015 
1017 
1018 
1019 template<typename ChildT>
1020 inline void
1021 RootNode<ChildT>::getNodeLog2Dims(std::vector<Index>& dims)
1022 {
1023  dims.push_back(0); // magic number; RootNode has no Log2Dim
1024  ChildT::getNodeLog2Dims(dims);
1025 }
1026 
1027 
1028 template<typename ChildT>
1029 inline Coord
1031 {
1032  return mTable.empty() ? Coord(0) : mTable.begin()->first;
1033 }
1034 
1035 template<typename ChildT>
1036 inline Coord
1038 {
1039  return mTable.empty() ? Coord(0) : mTable.rbegin()->first + Coord(ChildT::DIM - 1);
1040 }
1041 
1042 
1043 template<typename ChildT>
1044 inline void
1046 {
1047  bbox.min() = this->getMinIndex();
1048  bbox.max() = this->getMaxIndex();
1049 }
1050 
1051 
1053 
1054 
1055 template<typename ChildT>
1056 template<typename OtherChildType>
1057 inline bool
1059 {
1060  typedef RootNode<OtherChildType> OtherRootT;
1061  typedef typename OtherRootT::MapType OtherMapT;
1062  typedef typename OtherRootT::MapIter OtherIterT;
1063  typedef typename OtherRootT::MapCIter OtherCIterT;
1064 
1065  if (!hasSameConfiguration(other)) return false;
1066 
1067  // Create a local copy of the other node's table.
1068  OtherMapT copyOfOtherTable = other.mTable;
1069 
1070  // For each entry in this node's table...
1071  for (MapCIter thisIter = mTable.begin(); thisIter != mTable.end(); ++thisIter) {
1072  if (this->isBackgroundTile(thisIter)) continue; // ignore background tiles
1073 
1074  // Fail if there is no corresponding entry in the other node's table.
1075  OtherCIterT otherIter = other.findKey(thisIter->first);
1076  if (otherIter == other.mTable.end()) return false;
1077 
1078  // Fail if this entry is a tile and the other is a child or vice-versa.
1079  if (isChild(thisIter)) {//thisIter points to a child
1080  if (OtherRootT::isTile(otherIter)) return false;
1081  // Fail if both entries are children, but the children have different topology.
1082  if (!getChild(thisIter).hasSameTopology(&OtherRootT::getChild(otherIter))) return false;
1083  } else {//thisIter points to a tile
1084  if (OtherRootT::isChild(otherIter)) return false;
1085  if (getTile(thisIter).active != OtherRootT::getTile(otherIter).active) return false;
1086  }
1087 
1088  // Remove tiles and child nodes with matching topology from
1089  // the copy of the other node's table. This is required since
1090  // the two root tables can include an arbitrary number of
1091  // background tiles and still have the same topology!
1092  copyOfOtherTable.erase(otherIter->first);
1093  }
1094  // Fail if the remaining entries in copyOfOtherTable are not all background tiles.
1095  for (OtherIterT i = copyOfOtherTable.begin(), e = copyOfOtherTable.end(); i != e; ++i) {
1096  if (!other.isBackgroundTile(i)) return false;
1097  }
1098  return true;
1099 }
1100 
1101 
1102 template<typename ChildT>
1103 template<typename OtherChildType>
1104 inline bool
1106 {
1107  std::vector<Index> thisDims, otherDims;
1108  RootNode::getNodeLog2Dims(thisDims);
1110  return (thisDims == otherDims);
1111 }
1112 
1113 
1114 template<typename ChildT>
1115 template<typename OtherChildType>
1116 inline void
1118 {
1119  std::vector<Index> thisDims, otherDims;
1120  RootNode::getNodeLog2Dims(thisDims);
1122  if (thisDims != otherDims) {
1123  std::ostringstream ostr;
1124  ostr << "grids have incompatible configurations (" << thisDims[0];
1125  for (size_t i = 1, N = thisDims.size(); i < N; ++i) ostr << " x " << thisDims[i];
1126  ostr << " vs. " << otherDims[0];
1127  for (size_t i = 1, N = otherDims.size(); i < N; ++i) ostr << " x " << otherDims[i];
1128  ostr << ")";
1129  OPENVDB_THROW(TypeError, ostr.str());
1130  }
1131 }
1132 
1133 
1135 
1136 
1137 template<typename ChildT>
1138 inline Index64
1140 {
1141  Index64 sum = sizeof(*this);
1142  for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1143  if (const ChildT *child = iter->second.child) {
1144  sum += child->memUsage();
1145  }
1146  }
1147  return sum;
1148 }
1149 
1150 template<typename ChildT>
1151 inline void
1153 {
1154  for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1155  if (const ChildT *child = iter->second.child) {
1156  child->evalActiveVoxelBoundingBox(bbox);
1157  } else if (isTileOn(iter)) {
1158  bbox.expand(iter->first, ChildT::DIM);
1159  }
1160  }
1161 }
1162 
1163 
1164 template<typename ChildT>
1165 inline void
1167 {
1168  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1169  delete i->second.child;
1170  }
1171  mTable.clear();
1172 }
1173 
1174 
1175 template<typename ChildT>
1176 inline Index
1177 RootNode<ChildT>::getChildCount() const {
1178  Index sum = 0;
1179  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1180  if (isChild(i)) ++sum;
1181  }
1182  return sum;
1183 }
1184 
1185 
1186 template<typename ChildT>
1187 inline Index
1188 RootNode<ChildT>::getTileCount() const
1189 {
1190  Index sum = 0;
1191  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1192  if (isTile(i)) ++sum;
1193  }
1194  return sum;
1195 }
1196 
1197 
1198 template<typename ChildT>
1199 inline Index
1200 RootNode<ChildT>::getActiveTileCount() const
1201 {
1202  Index sum = 0;
1203  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1204  if (isTileOn(i)) ++sum;
1205  }
1206  return sum;
1207 }
1208 
1209 
1210 template<typename ChildT>
1211 inline Index
1212 RootNode<ChildT>::getInactiveTileCount() const
1213 {
1214  Index sum = 0;
1215  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1216  if (isTileOff(i)) ++sum;
1217  }
1218  return sum;
1219 }
1220 
1221 
1222 template<typename ChildT>
1223 inline Index32
1225 {
1226  Index32 sum = 0;
1227  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1228  if (isChild(i)) sum += getChild(i).leafCount();
1229  }
1230  return sum;
1231 }
1232 
1233 
1234 template<typename ChildT>
1235 inline Index32
1237 {
1238  Index32 sum = 1;
1239  if (ChildT::LEVEL != 0) {
1240  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1241  if (isChild(i)) sum += getChild(i).nonLeafCount();
1242  }
1243  }
1244  return sum;
1245 }
1246 
1247 
1248 template<typename ChildT>
1249 inline Index64
1251 {
1252  Index64 sum = 0;
1253  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1254  if (isChild(i)) {
1255  sum += getChild(i).onVoxelCount();
1256  } else if (isTileOn(i)) {
1257  sum += ChildT::NUM_VOXELS;
1258  }
1259  }
1260  return sum;
1261 }
1262 
1263 
1264 template<typename ChildT>
1265 inline Index64
1267 {
1268  Index64 sum = 0;
1269  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1270  if (isChild(i)) {
1271  sum += getChild(i).offVoxelCount();
1272  } else if (isTileOff(i) && !this->isBackgroundTile(i)) {
1273  sum += ChildT::NUM_VOXELS;
1274  }
1275  }
1276  return sum;
1277 }
1278 
1279 
1280 template<typename ChildT>
1281 inline Index64
1283 {
1284  Index64 sum = 0;
1285  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1286  if (isChild(i)) sum += getChild(i).onLeafVoxelCount();
1287  }
1288  return sum;
1289 }
1290 
1291 
1292 template<typename ChildT>
1293 inline Index64
1295 {
1296  Index64 sum = 0;
1297  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1298  if (isChild(i)) sum += getChild(i).offLeafVoxelCount();
1299  }
1300  return sum;
1301 }
1302 
1303 
1305 
1306 
1307 template<typename ChildT>
1308 inline bool
1310 {
1311  MapCIter iter = this->findCoord(xyz);
1312  if (iter == mTable.end() || isTileOff(iter)) return false;
1313  return isTileOn(iter) ? true : getChild(iter).isValueOn(xyz);
1314 }
1315 
1316 template<typename ChildT>
1317 inline bool
1319 {
1320  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1321  if (isChild(i) ? getChild(i).hasActiveTiles() : getTile(i).active) return true;
1322  }
1323  return false;
1324 }
1325 
1326 template<typename ChildT>
1327 template<typename AccessorT>
1328 inline bool
1329 RootNode<ChildT>::isValueOnAndCache(const Coord& xyz, AccessorT& acc) const
1330 {
1331  MapCIter iter = this->findCoord(xyz);
1332  if (iter == mTable.end() || isTileOff(iter)) return false;
1333  if (isTileOn(iter)) return true;
1334  acc.insert(xyz, &getChild(iter));
1335  return getChild(iter).isValueOnAndCache(xyz, acc);
1336 }
1337 
1338 
1339 template<typename ChildT>
1340 inline const typename ChildT::ValueType&
1342 {
1343  MapCIter iter = this->findCoord(xyz);
1344  return iter == mTable.end() ? mBackground
1345  : (isTile(iter) ? getTile(iter).value : getChild(iter).getValue(xyz));
1346 }
1347 
1348 template<typename ChildT>
1349 template<typename AccessorT>
1350 inline const typename ChildT::ValueType&
1351 RootNode<ChildT>::getValueAndCache(const Coord& xyz, AccessorT& acc) const
1352 {
1353  MapCIter iter = this->findCoord(xyz);
1354  if (iter == mTable.end()) return mBackground;
1355  if (isChild(iter)) {
1356  acc.insert(xyz, &getChild(iter));
1357  return getChild(iter).getValueAndCache(xyz, acc);
1358  }
1359  return getTile(iter).value;
1360 }
1361 
1362 
1363 template<typename ChildT>
1364 inline int
1366 {
1367  MapCIter iter = this->findCoord(xyz);
1368  return iter == mTable.end() ? -1
1369  : (isTile(iter) ? 0 : int(LEVEL) - int(getChild(iter).getValueLevel(xyz)));
1370 }
1371 
1372 template<typename ChildT>
1373 template<typename AccessorT>
1374 inline int
1375 RootNode<ChildT>::getValueDepthAndCache(const Coord& xyz, AccessorT& acc) const
1376 {
1377  MapCIter iter = this->findCoord(xyz);
1378  if (iter == mTable.end()) return -1;
1379  if (isTile(iter)) return 0;
1380  acc.insert(xyz, &getChild(iter));
1381  return int(LEVEL) - int(getChild(iter).getValueLevelAndCache(xyz, acc));
1382 }
1383 
1384 
1385 template<typename ChildT>
1386 inline void
1388 {
1389  MapIter iter = this->findCoord(xyz);
1390  if (iter != mTable.end() && !isTileOff(iter)) {
1391  if (isTileOn(iter)) {
1392  setChild(iter, *new ChildT(xyz, getTile(iter).value, /*active=*/true));
1393  }
1394  getChild(iter).setValueOff(xyz);
1395  }
1396 }
1397 
1398 
1399 template<typename ChildT>
1400 inline void
1402 {
1403  ChildT* child = NULL;
1404  MapIter iter = this->findCoord(xyz);
1405  if (iter == mTable.end()) {
1406  if (on) {
1407  child = new ChildT(xyz, mBackground);
1408  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1409  } else {
1410  // Nothing to do; (x, y, z) is background and therefore already inactive.
1411  }
1412  } else if (isChild(iter)) {
1413  child = &getChild(iter);
1414  } else if (on != getTile(iter).active) {
1415  child = new ChildT(xyz, getTile(iter).value, !on);
1416  setChild(iter, *child);
1417  }
1418  if (child) child->setActiveState(xyz, on);
1419 }
1420 
1421 template<typename ChildT>
1422 template<typename AccessorT>
1423 inline void
1424 RootNode<ChildT>::setActiveStateAndCache(const Coord& xyz, bool on, AccessorT& acc)
1425 {
1426  ChildT* child = NULL;
1427  MapIter iter = this->findCoord(xyz);
1428  if (iter == mTable.end()) {
1429  if (on) {
1430  child = new ChildT(xyz, mBackground);
1431  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1432  } else {
1433  // Nothing to do; (x, y, z) is background and therefore already inactive.
1434  }
1435  } else if (isChild(iter)) {
1436  child = &getChild(iter);
1437  } else if (on != getTile(iter).active) {
1438  child = new ChildT(xyz, getTile(iter).value, !on);
1439  setChild(iter, *child);
1440  }
1441  if (child) {
1442  acc.insert(xyz, child);
1443  child->setActiveStateAndCache(xyz, on, acc);
1444  }
1445 }
1446 
1447 
1448 template<typename ChildT>
1449 inline void
1451 {
1452  ChildT* child = NULL;
1453  MapIter iter = this->findCoord(xyz);
1454  if (iter == mTable.end()) {
1455  if (!math::isExactlyEqual(mBackground, value)) {
1456  child = new ChildT(xyz, mBackground);
1457  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1458  }
1459  } else if (isChild(iter)) {
1460  child = &getChild(iter);
1461  } else if (isTileOn(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1462  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1463  setChild(iter, *child);
1464  }
1465  if (child) child->setValueOff(xyz, value);
1466 }
1467 
1468 template<typename ChildT>
1469 template<typename AccessorT>
1470 inline void
1471 RootNode<ChildT>::setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1472 {
1473  ChildT* child = NULL;
1474  MapIter iter = this->findCoord(xyz);
1475  if (iter == mTable.end()) {
1476  if (!math::isExactlyEqual(mBackground, value)) {
1477  child = new ChildT(xyz, mBackground);
1478  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1479  }
1480  } else if (isChild(iter)) {
1481  child = &getChild(iter);
1482  } else if (isTileOn(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1483  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1484  setChild(iter, *child);
1485  }
1486  if (child) {
1487  acc.insert(xyz, child);
1488  child->setValueOffAndCache(xyz, value, acc);
1489  }
1490 }
1491 
1492 
1493 template<typename ChildT>
1494 inline void
1496 {
1497  ChildT* child = NULL;
1498  MapIter iter = this->findCoord(xyz);
1499  if (iter == mTable.end()) {
1500  child = new ChildT(xyz, mBackground);
1501  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1502  } else if (isChild(iter)) {
1503  child = &getChild(iter);
1504  } else if (isTileOff(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1505  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1506  setChild(iter, *child);
1507  }
1508  if (child) child->setValueOn(xyz, value);
1509 }
1510 
1511 template<typename ChildT>
1512 template<typename AccessorT>
1513 inline void
1514 RootNode<ChildT>::setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1515 {
1516  ChildT* child = NULL;
1517  MapIter iter = this->findCoord(xyz);
1518  if (iter == mTable.end()) {
1519  child = new ChildT(xyz, mBackground);
1520  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1521  } else if (isChild(iter)) {
1522  child = &getChild(iter);
1523  } else if (isTileOff(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1524  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1525  setChild(iter, *child);
1526  }
1527  if (child) {
1528  acc.insert(xyz, child);
1529  child->setValueAndCache(xyz, value, acc);
1530  }
1531 }
1532 
1533 
1534 template<typename ChildT>
1535 inline void
1537 {
1538  ChildT* child = NULL;
1539  MapIter iter = this->findCoord(xyz);
1540  if (iter == mTable.end()) {
1541  child = new ChildT(xyz, mBackground);
1542  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1543  } else if (isChild(iter)) {
1544  child = &getChild(iter);
1545  } else if (!math::isExactlyEqual(getTile(iter).value, value)) {
1546  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1547  setChild(iter, *child);
1548  }
1549  if (child) child->setValueOnly(xyz, value);
1550 }
1551 
1552 template<typename ChildT>
1553 template<typename AccessorT>
1554 inline void
1555 RootNode<ChildT>::setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1556 {
1557  ChildT* child = NULL;
1558  MapIter iter = this->findCoord(xyz);
1559  if (iter == mTable.end()) {
1560  child = new ChildT(xyz, mBackground);
1561  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1562  } else if (isChild(iter)) {
1563  child = &getChild(iter);
1564  } else if (!math::isExactlyEqual(getTile(iter).value, value)) {
1565  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1566  setChild(iter, *child);
1567  }
1568  if (child) {
1569  acc.insert(xyz, child);
1570  child->setValueOnlyAndCache(xyz, value, acc);
1571  }
1572 }
1573 
1574 
1575 template<typename ChildT>
1576 inline void
1578 {
1579  ChildT* child = NULL;
1580  MapIter iter = this->findCoord(xyz);
1581  if (iter == mTable.end()) {
1582  child = new ChildT(xyz, mBackground);
1583  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1584  } else if (isChild(iter)) {
1585  child = &getChild(iter);
1586  } else if (isTileOff(iter) || getTile(iter).value > value) {
1587  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1588  setChild(iter, *child);
1589  }
1590  if (child) child->setValueOnMin(xyz, value);
1591 }
1592 
1593 
1594 template<typename ChildT>
1595 inline void
1597 {
1598  ChildT* child = NULL;
1599  MapIter iter = this->findCoord(xyz);
1600  if (iter == mTable.end()) {
1601  child = new ChildT(xyz, mBackground);
1602  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1603  } else if (isChild(iter)) {
1604  child = &getChild(iter);
1605  } else if (isTileOff(iter) || getTile(iter).value < value) {
1606  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1607  setChild(iter, *child);
1608  }
1609  if (child) child->setValueOnMax(xyz, value);
1610 }
1611 
1612 
1613 template<typename ChildT>
1614 inline void
1616 {
1617  ChildT* child = NULL;
1618  MapIter iter = this->findCoord(xyz);
1619  if (iter == mTable.end()) {
1620  child = new ChildT(xyz, mBackground);
1621  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1622  } else if (isChild(iter)) {
1623  child = &getChild(iter);
1624  } else if (isTileOff(iter) || !math::isZero(addend)) {
1625  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1626  setChild(iter, *child);
1627  }
1628  if (child) child->setValueOnSum(xyz, addend);
1629 }
1630 
1631 template<typename ChildT>
1632 template<typename AccessorT>
1633 inline void
1635  const ValueType& addend, AccessorT& acc)
1636 {
1637  ChildT* child = NULL;
1638  MapIter iter = this->findCoord(xyz);
1639  if (iter == mTable.end()) {
1640  child = new ChildT(xyz, mBackground);
1641  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1642  } else if (isChild(iter)) {
1643  child = &getChild(iter);
1644  } else if (isTileOff(iter) || !math::isZero(addend)) {
1645  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1646  setChild(iter, *child);
1647  }
1648  if (child) {
1649  acc.insert(xyz, child);
1650  child->setValueOnSumAndCache(xyz, addend, acc);
1651  }
1652 }
1653 
1654 
1655 template<typename ChildT>
1656 inline bool
1658 {
1659  MapCIter iter = this->findCoord(xyz);
1660  if (iter == mTable.end()) {
1661  value = mBackground;
1662  return false;
1663  } else if (isChild(iter)) {
1664  return getChild(iter).probeValue(xyz, value);
1665  }
1666  value = getTile(iter).value;
1667  return isTileOn(iter);
1668 }
1669 
1670 template<typename ChildT>
1671 template<typename AccessorT>
1672 inline bool
1673 RootNode<ChildT>::probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT& acc) const
1674 {
1675  MapCIter iter = this->findCoord(xyz);
1676  if (iter == mTable.end()) {
1677  value = mBackground;
1678  return false;
1679  } else if (isChild(iter)) {
1680  acc.insert(xyz, &getChild(iter));
1681  return getChild(iter).probeValueAndCache(xyz, value, acc);
1682  }
1683  value = getTile(iter).value;
1684  return isTileOn(iter);
1685 }
1686 
1687 
1689 
1690 
1691 template<typename ChildT>
1692 inline void
1693 RootNode<ChildT>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
1694 {
1695  if (bbox.empty()) return;
1696 
1697  Coord xyz, tileMax;
1698  for (int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) {
1699  xyz.setX(x);
1700  for (int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) {
1701  xyz.setY(y);
1702  for (int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) {
1703  xyz.setZ(z);
1704 
1705  // Get the bounds of the tile that contains voxel (x, y, z).
1706  Coord tileMin = coordToKey(xyz);
1707  tileMax = tileMin.offsetBy(ChildT::DIM - 1);
1708 
1709  if (xyz != tileMin || Coord::lessThan(bbox.max(), tileMax)) {
1710  // If the box defined by (xyz, bbox.max()) doesn't completely enclose
1711  // the tile to which xyz belongs, create a child node (or retrieve
1712  // the existing one).
1713  ChildT* child = NULL;
1714  MapIter iter = this->findKey(tileMin);
1715  if (iter == mTable.end()) {
1716  // No child or tile exists. Create a child and initialize it
1717  // with the background value.
1718  child = new ChildT(xyz, mBackground);
1719  mTable[tileMin] = NodeStruct(*child);
1720  } else if (isTile(iter)) {
1721  // Replace the tile with a newly-created child that is initialized
1722  // with the tile's value and active state.
1723  const Tile& tile = getTile(iter);
1724  child = new ChildT(xyz, tile.value, tile.active);
1725  mTable[tileMin] = NodeStruct(*child);
1726  } else if (isChild(iter)) {
1727  child = &getChild(iter);
1728  }
1729  // Forward the fill request to the child.
1730  if (child) {
1731  child->fill(CoordBBox(xyz, Coord::minComponent(bbox.max(), tileMax)),
1732  value, active);
1733  }
1734  } else {
1735  // If the box given by (xyz, bbox.max()) completely encloses
1736  // the tile to which xyz belongs, create the tile (if it
1737  // doesn't already exist) and give it the fill value.
1738  MapIter iter = this->findOrAddCoord(tileMin);
1739  setTile(iter, Tile(value, active));
1740  }
1741  }
1742  }
1743  }
1744 }
1745 
1746 template<typename ChildT>
1747 template<typename DenseT>
1748 inline void
1749 RootNode<ChildT>::copyToDense(const CoordBBox& bbox, DenseT& dense) const
1750 {
1751  const size_t xStride = dense.xStride(), yStride = dense.yStride();// zStride=1
1752  const Coord& min = dense.bbox().min();
1753  CoordBBox nodeBBox;
1754  for (Coord xyz = bbox.min(); xyz[0] <= bbox.max()[0]; xyz[0] = nodeBBox.max()[0] + 1) {
1755  for (xyz[1] = bbox.min()[1]; xyz[1] <= bbox.max()[1]; xyz[1] = nodeBBox.max()[1] + 1) {
1756  for (xyz[2] = bbox.min()[2]; xyz[2] <= bbox.max()[2]; xyz[2] = nodeBBox.max()[2] + 1) {
1757 
1758  // Get the coordinate bbox of the child node that contains voxel xyz.
1759  nodeBBox = CoordBBox::createCube(coordToKey(xyz), ChildT::DIM);
1760 
1761  // Get the coordinate bbox of the interection of inBBox and nodeBBox
1762  CoordBBox sub(xyz, Coord::minComponent(bbox.max(), nodeBBox.max()));
1763 
1764  MapCIter iter = this->findKey(nodeBBox.min());
1765  if (iter != mTable.end() && isChild(iter)) {//is a child
1766  getChild(iter).copyToDense(sub, dense);
1767  } else {//is background or a tile value
1768  const ValueType value = iter==mTable.end() ? mBackground : getTile(iter).value;
1769  sub.translate(-min);
1770  ValueType* a0 = dense.data() + sub.min()[2];
1771  for (Int32 x=sub.min()[0], ex=sub.max()[0]+1; x<ex; ++x) {
1772  ValueType* a1 = a0 + x*xStride;
1773  for (Int32 y=sub.min()[1], ey=sub.max()[1]+1; y<ey; ++y) {
1774  ValueType* a2 = a1 + y*yStride;
1775  for (Int32 z=sub.min()[2], ez=sub.max()[2]+1; z<ez; ++z) *a2++ = value;
1776  }
1777  }
1778  }
1779  }
1780  }
1781  }
1782 }
1783 
1785 
1786 
1787 template<typename ChildT>
1788 inline bool
1789 RootNode<ChildT>::writeTopology(std::ostream& os, bool toHalf) const
1790 {
1791  if (!toHalf) {
1792  os.write(reinterpret_cast<const char*>(&mBackground), sizeof(ValueType));
1793  } else {
1794  ValueType truncatedVal = io::truncateRealToHalf(mBackground);
1795  os.write(reinterpret_cast<const char*>(&truncatedVal), sizeof(ValueType));
1796  }
1797  io::setGridBackgroundValuePtr(os, &mBackground);
1798 
1799  const Index numTiles = this->getTileCount(), numChildren = this->getChildCount();
1800  os.write(reinterpret_cast<const char*>(&numTiles), sizeof(Index));
1801  os.write(reinterpret_cast<const char*>(&numChildren), sizeof(Index));
1802 
1803  if (numTiles == 0 && numChildren == 0) return false;
1804 
1805  // Write tiles.
1806  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1807  if (isChild(i)) continue;
1808  os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 * sizeof(Int32));
1809  os.write(reinterpret_cast<const char*>(&getTile(i).value), sizeof(ValueType));
1810  os.write(reinterpret_cast<const char*>(&getTile(i).active), sizeof(bool));
1811  }
1812  // Write child nodes.
1813  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1814  if (isTile(i)) continue;
1815  os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 * sizeof(Int32));
1816  getChild(i).writeTopology(os, toHalf);
1817  }
1818 
1819  return true; // not empty
1820 }
1821 
1822 
1823 template<typename ChildT>
1824 inline bool
1825 RootNode<ChildT>::readTopology(std::istream& is, bool fromHalf)
1826 {
1827  // Delete the existing tree.
1828  this->clearTable();
1829 
1831  // Read and convert an older-format RootNode.
1832 
1833  // For backward compatibility with older file formats, read both
1834  // outside and inside background values.
1835  is.read(reinterpret_cast<char*>(&mBackground), sizeof(ValueType));
1836  ValueType inside;
1837  is.read(reinterpret_cast<char*>(&inside), sizeof(ValueType));
1838 
1839  io::setGridBackgroundValuePtr(is, &mBackground);
1840 
1841  // Read the index range.
1842  Coord rangeMin, rangeMax;
1843  is.read(reinterpret_cast<char*>(rangeMin.asPointer()), 3 * sizeof(Int32));
1844  is.read(reinterpret_cast<char*>(rangeMax.asPointer()), 3 * sizeof(Int32));
1845 
1846  this->initTable();
1847  Index tableSize = 0, log2Dim[4] = { 0, 0, 0, 0 };
1848  Int32 offset[3];
1849  for (int i = 0; i < 3; ++i) {
1850  offset[i] = rangeMin[i] >> ChildT::TOTAL;
1851  rangeMin[i] = offset[i] << ChildT::TOTAL;
1852  log2Dim[i] = 1 + util::FindHighestOn((rangeMax[i] >> ChildT::TOTAL) - offset[i]);
1853  tableSize += log2Dim[i];
1854  rangeMax[i] = (((1 << log2Dim[i]) + offset[i]) << ChildT::TOTAL) - 1;
1855  }
1856  log2Dim[3] = log2Dim[1] + log2Dim[2];
1857  tableSize = 1U << tableSize;
1858 
1859  // Read masks.
1860  util::RootNodeMask childMask(tableSize), valueMask(tableSize);
1861  childMask.load(is);
1862  valueMask.load(is);
1863 
1864  // Read child nodes/values.
1865  for (Index i = 0; i < tableSize; ++i) {
1866  // Compute origin = offset2coord(i).
1867  Index n = i;
1868  Coord origin;
1869  origin[0] = (n >> log2Dim[3]) + offset[0];
1870  n &= (1U << log2Dim[3]) - 1;
1871  origin[1] = (n >> log2Dim[2]) + offset[1];
1872  origin[2] = (n & ((1U << log2Dim[2]) - 1)) + offset[1];
1873  origin <<= ChildT::TOTAL;
1874 
1875  if (childMask.isOn(i)) {
1876  // Read in and insert a child node.
1877  ChildT* child = new ChildT(origin, mBackground);
1878  child->readTopology(is);
1879  mTable[origin] = NodeStruct(*child);
1880  } else {
1881  // Read in a tile value and insert a tile, but only if the value
1882  // is either active or non-background.
1883  ValueType value;
1884  is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
1885  if (valueMask.isOn(i) || (!math::isApproxEqual(value, mBackground))) {
1886  mTable[origin] = NodeStruct(Tile(value, valueMask.isOn(i)));
1887  }
1888  }
1889  }
1890  return true;
1891  }
1892 
1893  // Read a RootNode that was stored in the current format.
1894 
1895  is.read(reinterpret_cast<char*>(&mBackground), sizeof(ValueType));
1896  io::setGridBackgroundValuePtr(is, &mBackground);
1897 
1898  Index numTiles = 0, numChildren = 0;
1899  is.read(reinterpret_cast<char*>(&numTiles), sizeof(Index));
1900  is.read(reinterpret_cast<char*>(&numChildren), sizeof(Index));
1901 
1902  if (numTiles == 0 && numChildren == 0) return false;
1903 
1904  Int32 vec[3];
1905  ValueType value;
1906  bool active;
1907 
1908  // Read tiles.
1909  for (Index n = 0; n < numTiles; ++n) {
1910  is.read(reinterpret_cast<char*>(vec), 3 * sizeof(Int32));
1911  is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
1912  is.read(reinterpret_cast<char*>(&active), sizeof(bool));
1913  mTable[Coord(vec)] = NodeStruct(Tile(value, active));
1914  }
1915 
1916  // Read child nodes.
1917  for (Index n = 0; n < numChildren; ++n) {
1918  is.read(reinterpret_cast<char*>(vec), 3 * sizeof(Int32));
1919  Coord origin(vec);
1920  ChildT* child = new ChildT(origin, mBackground);
1921  child->readTopology(is, fromHalf);
1922  mTable[Coord(vec)] = NodeStruct(*child);
1923  }
1924 
1925  return true; // not empty
1926 }
1927 
1928 
1929 template<typename ChildT>
1930 inline void
1931 RootNode<ChildT>::writeBuffers(std::ostream& os, bool toHalf) const
1932 {
1933  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1934  if (isChild(i)) getChild(i).writeBuffers(os, toHalf);
1935  }
1936 }
1937 
1938 
1939 template<typename ChildT>
1940 inline void
1941 RootNode<ChildT>::readBuffers(std::istream& is, bool fromHalf)
1942 {
1943  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1944  if (isChild(i)) getChild(i).readBuffers(is, fromHalf);
1945  }
1946 }
1947 
1948 
1950 
1951 
1952 template<typename ChildT>
1953 template<typename PruneOp>
1954 inline void
1956 {
1957  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1958  if (this->isTile(i)|| !op(this->getChild(i))) continue;
1959  this->setTile(i, Tile(op.value, op.state));
1960  }
1961  this->eraseBackgroundTiles();
1962 }
1963 
1964 
1965 template<typename ChildT>
1966 inline void
1968 {
1969  TolerancePrune<ValueType> op(tolerance);
1970  this->pruneOp(op);
1971 }
1972 
1973 
1974 template<typename ChildT>
1975 inline void
1977 {
1978  InactivePrune<ValueType> op(bg);
1979  this->pruneOp(op);
1980 }
1981 
1982 
1983 template<typename ChildT>
1984 inline void
1986 {
1987  this->pruneInactive(mBackground);
1988 }
1989 
1990 
1991 template<typename ChildT>
1992 inline void
1994 {
1995  TolerancePrune<ValueType, /*Terminate at level=*/1> op(tolerance);
1996  this->pruneOp(op);
1997 }
1998 
1999 
2001 
2002 template<typename ChildT>
2003 template<typename NodeT>
2004 inline NodeT*
2005 RootNode<ChildT>::stealNode(const Coord& xyz, const ValueType& value, bool state)
2006 {
2007  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2008  NodeT::LEVEL > ChildT::LEVEL) return NULL;
2010  MapIter iter = this->findCoord(xyz);
2011  if (iter == mTable.end() || isTile(iter)) return NULL;
2012  return (boost::is_same<NodeT, ChildT>::value)
2013  ? reinterpret_cast<NodeT*>(&stealChild(iter, Tile(value, state)))
2014  : getChild(iter).template stealNode<NodeT>(xyz, value, state);
2016 }
2017 
2018 
2020 
2021 
2022 template<typename ChildT>
2023 inline void
2025 {
2026  if (leaf == NULL) return;
2027  ChildT* child = NULL;
2028  const Coord& xyz = leaf->origin();
2029  MapIter iter = this->findCoord(xyz);
2030  if (iter == mTable.end()) {
2031  if (ChildT::LEVEL>0) {
2032  child = new ChildT(xyz, mBackground, false);
2033  } else {
2034  child = reinterpret_cast<ChildT*>(leaf);
2035  }
2036  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2037  } else if (isChild(iter)) {
2038  if (ChildT::LEVEL>0) {
2039  child = &getChild(iter);
2040  } else {
2041  child = reinterpret_cast<ChildT*>(leaf);
2042  setChild(iter, *child);//this also deletes the existing child node
2043  }
2044  } else {//tile
2045  if (ChildT::LEVEL>0) {
2046  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2047  } else {
2048  child = reinterpret_cast<ChildT*>(leaf);
2049  }
2050  setChild(iter, *child);
2051  }
2052  child->addLeaf(leaf);
2053 }
2054 
2055 
2056 template<typename ChildT>
2057 template<typename AccessorT>
2058 inline void
2060 {
2061  if (leaf == NULL) return;
2062  ChildT* child = NULL;
2063  const Coord& xyz = leaf->origin();
2064  MapIter iter = this->findCoord(xyz);
2065  if (iter == mTable.end()) {
2066  if (ChildT::LEVEL>0) {
2067  child = new ChildT(xyz, mBackground, false);
2068  } else {
2069  child = reinterpret_cast<ChildT*>(leaf);
2070  }
2071  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2072  } else if (isChild(iter)) {
2073  if (ChildT::LEVEL>0) {
2074  child = &getChild(iter);
2075  } else {
2076  child = reinterpret_cast<ChildT*>(leaf);
2077  setChild(iter, *child);//this also deletes the existing child node
2078  }
2079  } else {//tile
2080  if (ChildT::LEVEL>0) {
2081  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2082  } else {
2083  child = reinterpret_cast<ChildT*>(leaf);
2084  }
2085  setChild(iter, *child);
2086  }
2087  acc.insert(xyz, child);
2088  child->addLeafAndCache(leaf, acc);
2089 }
2090 
2091 
2092 template<typename ChildT>
2093 inline void
2095  const ValueType& value, bool state)
2096 {
2097  if (LEVEL >= level && level > 0) {
2098  MapIter iter = this->findCoord(xyz);
2099  if (iter == mTable.end()) {//background
2100  if (LEVEL > level) {
2101  ChildT* child = new ChildT(xyz, mBackground, false);
2102  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2103  child->addTile(level, xyz, value, state);
2104  } else {
2105  mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2106  }
2107  } else if (isChild(iter)) {//child
2108  if (LEVEL > level) {
2109  getChild(iter).addTile(level, xyz, value, state);
2110  } else {
2111  setTile(iter, Tile(value, state));//this also deletes the existing child node
2112  }
2113  } else {//tile
2114  if (LEVEL > level) {
2115  ChildT* child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2116  setChild(iter, *child);
2117  child->addTile(level, xyz, value, state);
2118  } else {
2119  setTile(iter, Tile(value, state));
2120  }
2121  }
2122  }
2123 }
2124 
2125 
2126 template<typename ChildT>
2127 template<typename AccessorT>
2128 inline void
2129 RootNode<ChildT>::addTileAndCache(Index level, const Coord& xyz, const ValueType& value,
2130  bool state, AccessorT& acc)
2131 {
2132  if (LEVEL >= level && level > 0) {
2133  MapIter iter = this->findCoord(xyz);
2134  if (iter == mTable.end()) {//background
2135  if (LEVEL > level) {
2136  ChildT* child = new ChildT(xyz, mBackground, false);
2137  acc.insert(xyz, child);
2138  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2139  child->addTileAndCache(level, xyz, value, state, acc);
2140  } else {
2141  mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2142  }
2143  } else if (isChild(iter)) {//child
2144  if (LEVEL > level) {
2145  ChildT* child = &getChild(iter);
2146  acc.insert(xyz, child);
2147  child->addTileAndCache(level, xyz, value, state, acc);
2148  } else {
2149  setTile(iter, Tile(value, state));//this also deletes the existing child node
2150  }
2151  } else {//tile
2152  if (LEVEL > level) {
2153  ChildT* child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2154  acc.insert(xyz, child);
2155  setChild(iter, *child);
2156  child->addTileAndCache(level, xyz, value, state, acc);
2157  } else {
2158  setTile(iter, Tile(value, state));
2159  }
2160  }
2161  }
2162 }
2163 
2164 
2166 
2167 
2168 template<typename ChildT>
2169 inline typename ChildT::LeafNodeType*
2171 {
2172  ChildT* child = NULL;
2173  MapIter iter = this->findCoord(xyz);
2174  if (iter == mTable.end()) {
2175  child = new ChildT(xyz, mBackground, false);
2176  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2177  } else if (isChild(iter)) {
2178  child = &getChild(iter);
2179  } else {
2180  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2181  setChild(iter, *child);
2182  }
2183  return child->touchLeaf(xyz);
2184 }
2185 
2186 
2187 template<typename ChildT>
2188 template<typename AccessorT>
2189 inline typename ChildT::LeafNodeType*
2190 RootNode<ChildT>::touchLeafAndCache(const Coord& xyz, AccessorT& acc)
2191 {
2192  ChildT* child = NULL;
2193  MapIter iter = this->findCoord(xyz);
2194  if (iter == mTable.end()) {
2195  child = new ChildT(xyz, mBackground, false);
2196  mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2197  } else if (isChild(iter)) {
2198  child = &getChild(iter);
2199  } else {
2200  child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2201  setChild(iter, *child);
2202  }
2203  acc.insert(xyz, child);
2204  return child->touchLeafAndCache(xyz, acc);
2205 }
2206 
2207 
2209 
2210 template<typename ChildT>
2211 template<typename NodeT>
2212 inline bool
2214 {
2215  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2216  NodeT::LEVEL > ChildT::LEVEL) return false;
2218  return ChildT::template hasNodeType<NodeT>();
2220 }
2221 
2223 
2224 template<typename ChildT>
2225 template<typename NodeT>
2226 inline NodeT*
2228 {
2229  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2230  NodeT::LEVEL > ChildT::LEVEL) return NULL;
2232  MapIter iter = this->findCoord(xyz);
2233  if (iter == mTable.end() || isTile(iter)) return NULL;
2234  ChildT* child = &getChild(iter);
2235  return (boost::is_same<NodeT, ChildT>::value)
2236  ? reinterpret_cast<NodeT*>(child)
2237  : child->template probeNode<NodeT>(xyz);
2239 }
2240 template<typename ChildT>
2241 template<typename NodeT>
2242 inline const NodeT*
2244 {
2245  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2246  NodeT::LEVEL > ChildT::LEVEL) return NULL;
2248  MapCIter iter = this->findCoord(xyz);
2249  if (iter == mTable.end() || isTile(iter)) return NULL;
2250  const ChildT* child = &getChild(iter);
2251  return (boost::is_same<NodeT, ChildT>::value)
2252  ? reinterpret_cast<const NodeT*>(child)
2253  : child->template probeConstNode<NodeT>(xyz);
2255 }
2256 template<typename ChildT>
2257 template<typename NodeT, typename AccessorT>
2258 inline NodeT*
2259 RootNode<ChildT>::probeNodeAndCache(const Coord& xyz, AccessorT& acc)
2260 {
2261  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2262  NodeT::LEVEL > ChildT::LEVEL) return NULL;
2264  MapIter iter = this->findCoord(xyz);
2265  if (iter == mTable.end() || isTile(iter)) return NULL;
2266  ChildT* child = &getChild(iter);
2267  acc.insert(xyz, child);
2268  return (boost::is_same<NodeT, ChildT>::value)
2269  ? reinterpret_cast<NodeT*>(child)
2270  : child->template probeNodeAndCache<NodeT>(xyz, acc);
2272 }
2273 
2274 template<typename ChildT>
2275 template<typename NodeT,typename AccessorT>
2276 inline const NodeT*
2277 RootNode<ChildT>::probeConstNodeAndCache(const Coord& xyz, AccessorT& acc) const
2278 {
2279  if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2280  NodeT::LEVEL > ChildT::LEVEL) return NULL;
2282  MapCIter iter = this->findCoord(xyz);
2283  if (iter == mTable.end() || isTile(iter)) return NULL;
2284  const ChildT* child = &getChild(iter);
2285  acc.insert(xyz, child);
2286  return (boost::is_same<NodeT, ChildT>::value)
2287  ? reinterpret_cast<const NodeT*>(child)
2288  : child->template probeConstNodeAndCache<NodeT>(xyz, acc);
2290 }
2291 
2293 
2294 
2295 template<typename ChildT>
2296 inline void
2298 {
2299  this->signedFloodFill(mBackground, negative(mBackground));
2300 }
2301 
2302 
2303 template<typename ChildT>
2304 inline void
2306 {
2307  const ValueType zero = zeroVal<ValueType>();
2308 
2309  mBackground = outside;
2310 
2311  // First, flood fill all child nodes and put child-keys into a sorted set
2312  CoordSet nodeKeys;
2313  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2314  if (this->isTile(i)) continue;
2315  getChild(i).signedFloodFill(outside, inside);
2316  nodeKeys.insert(i->first);//only add inactive tiles!
2317  }
2318 
2319  // We employ a simple z-scanline algorithm that inserts inactive
2320  // tiles with the inside value if they are sandwiched
2321  // between inside child nodes only!
2322  const Tile insideTile(inside, /*on=*/false);
2323  CoordSetCIter b = nodeKeys.begin(), e = nodeKeys.end();
2324  if ( b == e ) return;
2325  for (CoordSetCIter a = b++; b != e; ++a, ++b) {
2326  Coord d = *b - *a; // delta of neighboring keys
2327  if (d[0]!=0 || d[1]!=0 || d[2]==Int32(ChildT::DIM)) continue;//not z-scanline or neighbors
2328  MapIter i = mTable.find(*a), j = mTable.find(*b);
2329  const ValueType fill[] = { getChild(i).getLastValue(), getChild(j).getFirstValue() };
2330  if (!(fill[0] < zero) || !(fill[1] < zero)) continue; // scanline isn't inside
2331  for (Coord c = *a + Coord(0u,0u,ChildT::DIM); c[2] != (*b)[2]; c[2] += ChildT::DIM) {
2332  mTable[c] = insideTile;
2333  }
2334  }
2335 }
2336 
2337 
2339 
2340 
2341 template<typename ChildT>
2342 inline void
2344 {
2345  for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2346  if (this->isTileOff(i)) continue;
2347  ChildT* child = i->second.child;
2348  if (child==NULL) {
2349  child = new ChildT(i->first, this->getTile(i).value, true);
2350  i->second.child = child;
2351  }
2352  child->voxelizeActiveTiles();
2353  }
2354 }
2355 
2356 
2358 
2359 
2360 template<typename ChildT>
2361 inline void
2363 {
2364  for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2365  MapIter j = mTable.find(i->first);
2366  if (other.isChild(i)) {
2367  if (j == mTable.end()) { // insert other child node
2368  mTable[i->first]=NodeStruct(stealChild(i, Tile(other.mBackground, /*on=*/false)));
2369  } else if (isTile(j)) { // replace tile with other child node
2370  setChild(j, stealChild(i, Tile(other.mBackground, /*on=*/false)));
2371  } else { // merge both child nodes
2372  getChild(j).merge(getChild(i),other.mBackground, mBackground);
2373  }
2374  } else { // other is a tile
2375  if (j == mTable.end()) { // insert other tile
2376  mTable[i->first] = i->second;
2377  } else continue; // ignore other tile
2378  }
2379  }
2380  // Empty the other tree so as not to leave it in a partially cannibalized state.
2381  other.clear();
2382 }
2383 
2384 
2386 
2387 
2388 template<typename ChildT>
2389 template<typename OtherChildType>
2390 inline void
2392 {
2393  typedef RootNode<OtherChildType> OtherRootT;
2394  typedef typename OtherRootT::MapCIter OtherCIterT;
2395 
2396  enforceSameConfiguration(other);
2397 
2398  for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2399  MapIter j = mTable.find(i->first);
2400  if (other.isChild(i)) {
2401  if (j == mTable.end()) { // create child branch with identical topology
2402  mTable[i->first] = NodeStruct(
2403  *(new ChildT(other.getChild(i), mBackground, TopologyCopy())));
2404  } else if (this->isChild(j)) { // union with child branch
2405  this->getChild(j).topologyUnion(other.getChild(i));
2406  } else {// this is a tile so replace it with a child branch with identical topology
2407  ChildT* child = new ChildT(
2408  other.getChild(i), this->getTile(j).value, TopologyCopy());
2409  if (this->isTileOn(j)) child->setValuesOn();//this is an active tile
2410  this->setChild(j, *child);
2411  }
2412  } else if (other.isTileOn(i)) { // other is an active tile
2413  if (j == mTable.end()) { // insert an active tile
2414  mTable[i->first] = NodeStruct(Tile(mBackground, true));
2415  } else if (this->isChild(j)) {
2416  this->getChild(j).setValuesOn();
2417  } else if (this->isTileOff(j)) {
2418  this->setTile(j, Tile(this->getTile(j).value, true));
2419  }
2420  }
2421  }
2422 }
2423 
2424 
2426 
2427 
2428 template<typename ChildT>
2429 template<typename CombineOp>
2430 inline void
2431 RootNode<ChildT>::combine(RootNode& other, CombineOp& op, bool prune)
2432 {
2434 
2435  CoordSet keys;
2436  this->insertKeys(keys);
2437  other.insertKeys(keys);
2438 
2439  for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
2440  MapIter iter = findOrAddCoord(*i), otherIter = other.findOrAddCoord(*i);
2441  if (isTile(iter) && isTile(otherIter)) {
2442  // Both this node and the other node have constant values (tiles).
2443  // Combine the two values and store the result as this node's new tile value.
2444  op(args.setARef(getTile(iter).value)
2445  .setAIsActive(isTileOn(iter))
2446  .setBRef(getTile(otherIter).value)
2447  .setBIsActive(isTileOn(otherIter)));
2448  setTile(iter, Tile(args.result(), args.resultIsActive()));
2449 
2450  } else if (isChild(iter) && isTile(otherIter)) {
2451  // Combine this node's child with the other node's constant value.
2452  ChildT& child = getChild(iter);
2453  child.combine(getTile(otherIter).value, isTileOn(otherIter), op);
2454 
2455  } else if (isTile(iter) && isChild(otherIter)) {
2456  // Combine this node's constant value with the other node's child,
2457  // but use a new functor in which the A and B values are swapped,
2458  // since the constant value is the A value, not the B value.
2460  ChildT& child = getChild(otherIter);
2461  child.combine(getTile(iter).value, isTileOn(iter), swappedOp);
2462 
2463  // Steal the other node's child.
2464  setChild(iter, stealChild(otherIter, Tile()));
2465 
2466  } else /*if (isChild(iter) && isChild(otherIter))*/ {
2467  // Combine this node's child with the other node's child.
2468  ChildT &child = getChild(iter), &otherChild = getChild(otherIter);
2469  child.combine(otherChild, op);
2470  }
2471  if (prune && isChild(iter)) getChild(iter).prune();
2472  }
2473 
2474  // Combine background values.
2475  op(args.setARef(mBackground).setBRef(other.mBackground));
2476  mBackground = args.result();
2477 
2478  // Empty the other tree so as not to leave it in a partially cannibalized state.
2479  other.clear();
2480 }
2481 
2482 
2484 
2485 
2486 template<typename ChildT>
2487 template<typename CombineOp>
2488 inline void
2489 RootNode<ChildT>::combine2(const RootNode& other0, const RootNode& other1,
2490  CombineOp& op, bool prune)
2491 {
2493 
2494  CoordSet keys;
2495  other0.insertKeys(keys);
2496  other1.insertKeys(keys);
2497 
2498  const NodeStruct
2499  bg0(Tile(other0.mBackground, /*active=*/false)),
2500  bg1(Tile(other1.mBackground, /*active=*/false));
2501 
2502  for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
2503  MapIter thisIter = this->findOrAddCoord(*i);
2504  MapCIter iter0 = other0.findKey(*i), iter1 = other1.findKey(*i);
2505  const NodeStruct
2506  &ns0 = (iter0 != other0.mTable.end()) ? iter0->second : bg0,
2507  &ns1 = (iter1 != other1.mTable.end()) ? iter1->second : bg1;
2508  if (ns0.isTile() && ns1.isTile()) {
2509  // Both input nodes have constant values (tiles).
2510  // Combine the two values and add a new tile to this node with the result.
2511  op(args.setARef(ns0.tile.value)
2512  .setAIsActive(ns0.isTileOn())
2513  .setBRef(ns1.tile.value)
2514  .setBIsActive(ns1.isTileOn()));
2515  setTile(thisIter, Tile(args.result(), args.resultIsActive()));
2516  } else {
2517  ChildT& otherChild = ns0.isChild() ? *ns0.child : *ns1.child;
2518  if (!isChild(thisIter)) {
2519  // Add a new child with the same coordinates, etc. as the other node's child.
2520  setChild(thisIter,
2521  *(new ChildT(otherChild.getOrigin(), getTile(thisIter).value)));
2522  }
2523  ChildT& child = getChild(thisIter);
2524 
2525  if (ns0.isTile()) {
2526  // Combine node1's child with node0's constant value
2527  // and write the result into this node's child.
2528  child.combine2(ns0.tile.value, *ns1.child, ns0.isTileOn(), op);
2529  } else if (ns1.isTile()) {
2530  // Combine node0's child with node1's constant value
2531  // and write the result into this node's child.
2532  child.combine2(*ns0.child, ns1.tile.value, ns1.isTileOn(), op);
2533  } else {
2534  // Combine node0's child with node1's child
2535  // and write the result into this node's child.
2536  child.combine2(*ns0.child, *ns1.child, op);
2537  }
2538  }
2539  if (prune && isChild(thisIter)) getChild(thisIter).prune();
2540  }
2541 
2542  // Combine background values.
2543  op(args.setARef(other0.mBackground).setBRef(other1.mBackground));
2544  mBackground = args.result();
2545 }
2546 
2547 
2549 
2550 
2551 template<typename ChildT>
2552 template<typename BBoxOp>
2553 inline void
2555 {
2556  const bool descent = op.template descent<LEVEL>();
2557  for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2558  if (this->isTileOff(i)) continue;
2559  if (this->isChild(i) && descent) {
2560  this->getChild(i).visitActiveBBox(op);
2561  } else {
2562 #ifdef _MSC_VER
2563  op.operator()<LEVEL>(CoordBBox::createCube(i->first, ChildT::DIM));
2564 #else
2565  op.template operator()<LEVEL>(CoordBBox::createCube(i->first, ChildT::DIM));
2566 #endif
2567  }
2568  }
2569 }
2570 
2571 
2572 template<typename ChildT>
2573 template<typename VisitorOp>
2574 inline void
2576 {
2577  doVisit<RootNode, VisitorOp, ChildAllIter>(*this, op);
2578 }
2579 
2580 
2581 template<typename ChildT>
2582 template<typename VisitorOp>
2583 inline void
2584 RootNode<ChildT>::visit(VisitorOp& op) const
2585 {
2586  doVisit<const RootNode, VisitorOp, ChildAllCIter>(*this, op);
2587 }
2588 
2589 
2590 template<typename ChildT>
2591 template<typename RootNodeT, typename VisitorOp, typename ChildAllIterT>
2592 inline void
2593 RootNode<ChildT>::doVisit(RootNodeT& self, VisitorOp& op)
2594 {
2595  typename RootNodeT::ValueType val;
2596  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
2597  if (op(iter)) continue;
2598  if (typename ChildAllIterT::ChildNodeType* child = iter.probeChild(val)) {
2599  child->visit(op);
2600  }
2601  }
2602 }
2603 
2604 
2606 
2607 
2608 template<typename ChildT>
2609 template<typename OtherRootNodeType, typename VisitorOp>
2610 inline void
2611 RootNode<ChildT>::visit2(OtherRootNodeType& other, VisitorOp& op)
2612 {
2613  doVisit2<RootNode, OtherRootNodeType, VisitorOp, ChildAllIter,
2614  typename OtherRootNodeType::ChildAllIter>(*this, other, op);
2615 }
2616 
2617 
2618 template<typename ChildT>
2619 template<typename OtherRootNodeType, typename VisitorOp>
2620 inline void
2621 RootNode<ChildT>::visit2(OtherRootNodeType& other, VisitorOp& op) const
2622 {
2623  doVisit2<const RootNode, OtherRootNodeType, VisitorOp, ChildAllCIter,
2624  typename OtherRootNodeType::ChildAllCIter>(*this, other, op);
2625 }
2626 
2627 
2628 template<typename ChildT>
2629 template<
2630  typename RootNodeT,
2631  typename OtherRootNodeT,
2632  typename VisitorOp,
2633  typename ChildAllIterT,
2634  typename OtherChildAllIterT>
2635 inline void
2636 RootNode<ChildT>::doVisit2(RootNodeT& self, OtherRootNodeT& other, VisitorOp& op)
2637 {
2640  enforceSameConfiguration(other);
2641 
2642  typename RootNodeT::ValueType val;
2643  typename OtherRootNodeT::ValueType otherVal;
2644 
2645  // The two nodes are required to have corresponding table entries,
2646  // but since that might require background tiles to be added to one or both,
2647  // and the nodes might be const, we operate on shallow copies of the nodes instead.
2648  RootNodeT copyOfSelf(self.mBackground);
2649  copyOfSelf.mTable = self.mTable;
2650  OtherRootNodeT copyOfOther(other.mBackground);
2651  copyOfOther.mTable = other.mTable;
2652 
2653  // Add background tiles to both nodes as needed.
2654  CoordSet keys;
2655  self.insertKeys(keys);
2656  other.insertKeys(keys);
2657  for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
2658  copyOfSelf.findOrAddCoord(*i);
2659  copyOfOther.findOrAddCoord(*i);
2660  }
2661 
2662  ChildAllIterT iter = copyOfSelf.beginChildAll();
2663  OtherChildAllIterT otherIter = copyOfOther.beginChildAll();
2664 
2665  for ( ; iter && otherIter; ++iter, ++otherIter)
2666  {
2667  const size_t skipBranch = static_cast<size_t>(op(iter, otherIter));
2668 
2669  typename ChildAllIterT::ChildNodeType* child =
2670  (skipBranch & 1U) ? NULL : iter.probeChild(val);
2671  typename OtherChildAllIterT::ChildNodeType* otherChild =
2672  (skipBranch & 2U) ? NULL : otherIter.probeChild(otherVal);
2673 
2674  if (child != NULL && otherChild != NULL) {
2675  child->visit2Node(*otherChild, op);
2676  } else if (child != NULL) {
2677  child->visit2(otherIter, op);
2678  } else if (otherChild != NULL) {
2679  otherChild->visit2(iter, op, /*otherIsLHS=*/true);
2680  }
2681  }
2682  // Remove any background tiles that were added above,
2683  // as well as any that were created by the visitors.
2684  copyOfSelf.eraseBackgroundTiles();
2685  copyOfOther.eraseBackgroundTiles();
2686 
2687  // If either input node is non-const, replace its table with
2688  // the (possibly modified) copy.
2689  self.resetTable(copyOfSelf.mTable);
2690  other.resetTable(copyOfOther.mTable);
2691 }
2692 
2693 } // namespace tree
2694 } // namespace OPENVDB_VERSION_NAME
2695 } // namespace openvdb
2696 
2697 #endif // OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
2698 
2699 // Copyright (c) 2012-2013 DreamWorks Animation LLC
2700 // All rights reserved. This software is distributed under the
2701 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )