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