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