OpenVDB  1.1.0
LeafNode.h
Go to the documentation of this file.
1 
2 //
3 // Copyright (c) 2012-2013 DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
30 
31 #ifndef OPENVDB_TREE_LEAFNODE_HAS_BEEN_INCLUDED
32 #define OPENVDB_TREE_LEAFNODE_HAS_BEEN_INCLUDED
33 
34 #include <iostream>
35 #include <algorithm> // for std::swap
36 #include <cstring> // for std::memcpy()
37 #include <boost/shared_ptr.hpp>
38 #include <boost/static_assert.hpp>
39 #include <boost/bind.hpp>
40 #include <tbb/blocked_range.h>
41 #include <tbb/parallel_for.h>
42 #include <openvdb/Types.h>
43 #include <openvdb/util/NodeMasks.h>
44 #include <openvdb/io/Compression.h> // for io::readData(), etc.
45 #include "Iterator.h"
46 #include "Util.h"
47 
48 
49 class TestLeaf;
50 template<typename> class TestLeafIO;
51 
52 namespace openvdb {
54 namespace OPENVDB_VERSION_NAME {
55 namespace tree {
56 
61 template<typename T, Index Log2Dim>
62 class LeafNode
63 {
64 public:
65  typedef T ValueType;
67  typedef boost::shared_ptr<LeafNode> Ptr;
69 
70  static const Index
71  LOG2DIM = Log2Dim, // needed by parent nodes
72  TOTAL = Log2Dim, // needed by parent nodes
73  DIM = 1 << TOTAL, // dimension along one coordinate direction
74  NUM_VALUES = 1 << 3 * Log2Dim,
75  NUM_VOXELS = NUM_VALUES, // total number of voxels represented by this node
76  SIZE = NUM_VALUES,
77  LEVEL = 0; // level 0 = leaf
78 
81  template<typename OtherValueType>
82  struct ValueConverter {
84  };
85 
88  class Buffer
89  {
90  public:
92  Buffer(): mData(new ValueType[SIZE]) {}
94  Buffer(const ValueType& val) : mData(new ValueType[SIZE]) { this->fill(val); }
96  Buffer(const Buffer& other) : mData(new ValueType[SIZE]) { *this = other; }
98  ~Buffer() { delete [] mData; }
100  void fill(const ValueType& val)
101  {
102  ValueType* target = mData;
103  Index size = SIZE;
104  while (size--) *target++ = val;
105  }
107  const ValueType& getValue(Index i) const { assert(i < SIZE); return mData[i]; }
109  const ValueType& operator[](Index i) const { return this->getValue(i); }
111  void setValue(Index i, const ValueType& val) { assert(i < SIZE); mData[i] = val; }
113  Buffer& operator=(const Buffer& other)
114  {
115  ValueType* target = mData;
116  const ValueType* source = other.mData;
117  Index size = SIZE;
118  while (size--) *target++ = *source++;
119  return *this;
120  }
123  bool operator==(const Buffer& other) const
124  {
125  const ValueType* target = mData;
126  const ValueType* source = other.mData;
127  Index size = SIZE;
128  while (size--) if(!math::isExactlyEqual(*target++, *source++)) return false;
129  return true;
130  }
133  bool operator!=(const Buffer& other) const { return !(other == *this); }
135  void swap(Buffer& other)
136  {
137  ValueType* tmp = mData;
138  mData = other.mData;
139  other.mData = tmp;
140  }
142  static Index memUsage() { return sizeof(ValueType*) + SIZE * sizeof(ValueType); }
144  static Index size() { return SIZE; }
145 
146  private:
149  ValueType& operator[](Index i) { assert(i < SIZE); return mData[i]; }
150 
151  friend class ::TestLeaf;
152  // Allow the parent LeafNode to access this Buffer's data pointer.
153  friend class LeafNode;
154 
155  ValueType* mData;
156  }; // class Buffer
157 
158 
160  LeafNode();
161 
166  explicit LeafNode(const Coord& coords,
167  const ValueType& value = zeroVal<ValueType>(),
168  bool active = false);
169 
171  LeafNode(const LeafNode&);
172 
174  template<typename OtherValueType>
176  const ValueType& offValue, const ValueType& onValue, TopologyCopy);
177 
179  template<typename OtherValueType>
181  const ValueType& background, TopologyCopy);
182 
184  ~LeafNode();
185 
186  //
187  // Statistics
188  //
190  static Index log2dim() { return Log2Dim; }
192  static Index dim() { return DIM; }
194  static Index size() { return SIZE; }
196  static Index numValues() { return SIZE; }
198  static Index getLevel() { return LEVEL; }
200  static void getNodeLog2Dims(std::vector<Index>& dims) { dims.push_back(Log2Dim); }
202  static Index getChildDim() { return 1; }
204  static Index32 leafCount() { return 1; }
206  static Index32 nonLeafCount() { return 0; }
207 
209  Index64 onVoxelCount() const { return mValueMask.countOn(); }
211  Index64 offVoxelCount() const { return mValueMask.countOff(); }
212  Index64 onLeafVoxelCount() const { return onVoxelCount(); }
213  Index64 offLeafVoxelCount() const { return offVoxelCount(); }
215  bool isEmpty() const { return mValueMask.isOff(); }
217  bool isDense() const { return mValueMask.isOn(); }
218 
220  Index64 memUsage() const;
221 
223  void evalActiveVoxelBoundingBox(CoordBBox&) const;
224 
227  CoordBBox getNodeBoundingBox() const { return CoordBBox::createCube(mOrigin, DIM); }
228 
230  const Coord& getOrigin() const { return mOrigin; }
231  void getOrigin(Coord& origin) const { origin = mOrigin; }
232  void getOrigin(Int32& x, Int32& y, Int32& z) const { mOrigin.asXYZ(x, y, z); }
233 
235  static Index coord2offset(const Coord& xyz);
237  static void offset2coord(Index n, Coord &xyz);
239  Coord offset2globalCoord(Index n) const;
240 
242  std::string str() const;
243 
246  template<typename OtherType, Index OtherLog2Dim>
247  bool hasSameTopology(const LeafNode<OtherType, OtherLog2Dim>* other) const;
248 
250  bool operator==(const LeafNode& other) const;
251  bool operator!=(const LeafNode& other) const { return !(other == *this); }
252 
253 protected:
257 
258  // Type tags to disambiguate template instantiations
259  struct ValueOn {}; struct ValueOff {}; struct ValueAll {};
260  struct ChildOn {}; struct ChildOff {}; struct ChildAll {};
261 
262  template<typename MaskIterT, typename NodeT, typename ValueT, typename TagT>
263  struct ValueIter:
264  // Derives from SparseIteratorBase, but can also be used as a dense iterator,
265  // if MaskIterT is a dense mask iterator type.
266  public SparseIteratorBase<
267  MaskIterT, ValueIter<MaskIterT, NodeT, ValueT, TagT>, NodeT, ValueT>
268  {
270 
272  ValueIter(const MaskIterT& iter, NodeT* parent): BaseT(iter, parent) {}
273 
274  ValueT& getItem(Index pos) const { return this->parent().getValue(pos); }
275  ValueT& getValue() const { return this->parent().getValue(this->pos()); }
276 
277  // Note: setItem() can't be called on const iterators.
278  void setItem(Index pos, const ValueT& value) const
279  {
280  this->parent().setValueOnly(pos, value);
281  }
282  // Note: setValue() can't be called on const iterators.
283  void setValue(const ValueT& value) const
284  {
285  this->parent().setValueOnly(this->pos(), value);
286  }
287  };
288 
290  template<typename MaskIterT, typename NodeT, typename TagT>
291  struct ChildIter:
292  public SparseIteratorBase<MaskIterT, ChildIter<MaskIterT, NodeT, TagT>, NodeT, ValueType>
293  {
295  ChildIter(const MaskIterT& iter, NodeT* parent): SparseIteratorBase<
296  MaskIterT, ChildIter<MaskIterT, NodeT, TagT>, NodeT, ValueType>(iter, parent) {}
297  };
298 
299  template<typename NodeT, typename ValueT, typename TagT>
300  struct DenseIter: public DenseIteratorBase<
301  MaskDenseIterator, DenseIter<NodeT, ValueT, TagT>, NodeT, /*ChildT=*/void, ValueT>
302  {
305 
307  DenseIter(const MaskDenseIterator& iter, NodeT* parent): BaseT(iter, parent) {}
308 
309  bool getItem(Index pos, void*& child, NonConstValueT& value) const
310  {
311  value = this->parent().getValue(pos);
312  child = NULL;
313  return false; // no child
314  }
315 
316  // Note: setItem() can't be called on const iterators.
317  //void setItem(Index pos, void* child) const {}
318 
319  // Note: unsetItem() can't be called on const iterators.
320  void unsetItem(Index pos, const ValueT& value) const
321  {
322  this->parent().setValueOnly(pos, value);
323  }
324  };
325 
326 public:
339 
340  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(mValueMask.beginOn(), this); }
341  ValueOnCIter beginValueOn() const { return ValueOnCIter(mValueMask.beginOn(), this); }
342  ValueOnIter beginValueOn() { return ValueOnIter(mValueMask.beginOn(), this); }
343  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(mValueMask.beginOff(), this); }
344  ValueOffCIter beginValueOff() const { return ValueOffCIter(mValueMask.beginOff(), this); }
345  ValueOffIter beginValueOff() { return ValueOffIter(mValueMask.beginOff(), this); }
346  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(mValueMask.beginDense(), this); }
347  ValueAllCIter beginValueAll() const { return ValueAllCIter(mValueMask.beginDense(), this); }
348  ValueAllIter beginValueAll() { return ValueAllIter(mValueMask.beginDense(), this); }
349 
350  ValueOnCIter cendValueOn() const { return ValueOnCIter(mValueMask.endOn(), this); }
351  ValueOnCIter endValueOn() const { return ValueOnCIter(mValueMask.endOn(), this); }
352  ValueOnIter endValueOn() { return ValueOnIter(mValueMask.endOn(), this); }
353  ValueOffCIter cendValueOff() const { return ValueOffCIter(mValueMask.endOff(), this); }
354  ValueOffCIter endValueOff() const { return ValueOffCIter(mValueMask.endOff(), this); }
355  ValueOffIter endValueOff() { return ValueOffIter(mValueMask.endOff(), this); }
356  ValueAllCIter cendValueAll() const { return ValueAllCIter(mValueMask.endDense(), this); }
357  ValueAllCIter endValueAll() const { return ValueAllCIter(mValueMask.endDense(), this); }
358  ValueAllIter endValueAll() { return ValueAllIter(mValueMask.endDense(), this); }
359 
360  // Note that [c]beginChildOn() and [c]beginChildOff() actually return end iterators,
361  // because leaf nodes have no children.
362  ChildOnCIter cbeginChildOn() const { return ChildOnCIter(mValueMask.endOn(), this); }
363  ChildOnCIter beginChildOn() const { return ChildOnCIter(mValueMask.endOn(), this); }
364  ChildOnIter beginChildOn() { return ChildOnIter(mValueMask.endOn(), this); }
365  ChildOffCIter cbeginChildOff() const { return ChildOffCIter(mValueMask.endOff(), this); }
366  ChildOffCIter beginChildOff() const { return ChildOffCIter(mValueMask.endOff(), this); }
367  ChildOffIter beginChildOff() { return ChildOffIter(mValueMask.endOff(), this); }
368  ChildAllCIter cbeginChildAll() const { return ChildAllCIter(mValueMask.beginDense(), this); }
369  ChildAllCIter beginChildAll() const { return ChildAllCIter(mValueMask.beginDense(), this); }
370  ChildAllIter beginChildAll() { return ChildAllIter(mValueMask.beginDense(), this); }
371 
372  ChildOnCIter cendChildOn() const { return ChildOnCIter(mValueMask.endOn(), this); }
373  ChildOnCIter endChildOn() const { return ChildOnCIter(mValueMask.endOn(), this); }
374  ChildOnIter endChildOn() { return ChildOnIter(mValueMask.endOn(), this); }
375  ChildOffCIter cendChildOff() const { return ChildOffCIter(mValueMask.endOff(), this); }
376  ChildOffCIter endChildOff() const { return ChildOffCIter(mValueMask.endOff(), this); }
377  ChildOffIter endChildOff() { return ChildOffIter(mValueMask.endOff(), this); }
378  ChildAllCIter cendChildAll() const { return ChildAllCIter(mValueMask.endDense(), this); }
379  ChildAllCIter endChildAll() const { return ChildAllCIter(mValueMask.endDense(), this); }
380  ChildAllIter endChildAll() { return ChildAllIter(mValueMask.endDense(), this); }
381 
382  //
383  // Buffer management
384  //
387  void swap(Buffer& other) { mBuffer.swap(other); }
388  const Buffer& buffer() const { return mBuffer; }
389  Buffer& buffer() { return mBuffer; }
390 
391  //
392  // I/O methods
393  //
397  void readTopology(std::istream& is, bool fromHalf = false);
401  void writeTopology(std::ostream& os, bool toHalf = false) const;
402 
406  void readBuffers(std::istream& is, bool fromHalf = false);
410  void writeBuffers(std::ostream& os, bool toHalf = false) const;
411 
412  size_t streamingSize(bool toHalf = false) const;
413 
414  //
415  // Accessor methods
416  //
418  const ValueType& getValue(const Coord& xyz) const;
420  const ValueType& getValue(Index offset) const;
421 
425  bool probeValue(const Coord& xyz, ValueType& val) const;
429  bool probeValue(Index offset, ValueType& val) const;
430 
432  static Index getValueLevel(const Coord&) { return LEVEL; }
433 
435  void setActiveState(const Coord& xyz, bool on);
436 
438  void setValueOff(const Coord& xyz) { mValueMask.setOff(LeafNode::coord2offset(xyz)); }
440  void setValueOff(Index offset) { assert(offset < SIZE); mValueMask.setOff(offset); }
441 
443  void setValueOff(const Coord& xyz, const ValueType& val);
445  void setValueOff(Index offset, const ValueType& val);
446 
448  void setValueOn(const Coord& xyz) { mValueMask.setOn(LeafNode::coord2offset(xyz)); }
450  void setValueOn(Index offset) { assert(offset < SIZE); mValueMask.setOn(offset); }
452  void setValueOn(const Coord& xyz, const ValueType& val) {
453  this->setValueOn(LeafNode::coord2offset(xyz), val);
454  }
456  void setValue(const Coord& xyz, const ValueType& val) { this->setValueOn(xyz, val); };
458  void setValueOn(Index offset, const ValueType& val) {
459  mBuffer[offset] = val;
460  mValueMask.setOn(offset);
461  }
462 
465  void setValueOnMin(const Coord& xyz, const ValueType& val) {
466  this->setValueOnMin(LeafNode::coord2offset(xyz), val);
467  }
470  void setValueOnMin(Index offset, const ValueType& val) {
471  mBuffer[offset] = std::min(val, mBuffer[offset]);
472  mValueMask.setOn(offset);
473  }
474 
477  void setValueOnMax(const Coord& xyz, const ValueType& val) {
478  this->setValueOnMax(LeafNode::coord2offset(xyz), val);
479  }
482  void setValueOnMax(Index offset, const ValueType& val) {
483  mBuffer[offset] = std::max(val, mBuffer[offset]);
484  mValueMask.setOn(offset);
485  }
486 
489  void setValueOnSum(const Coord& xyz, const ValueType& val) {
490  this->setValueOnSum(LeafNode::coord2offset(xyz), val);
491  }
494  void setValueOnSum(Index offset, const ValueType& val) {
495  mBuffer[offset] += val;
496  mValueMask.setOn(offset);
497  }
498 
501  void setValueOnly(const Coord& xyz, const ValueType& val) {
502  this->setValueOnly(LeafNode::coord2offset(xyz), val);
503  }
508  void setValueOnly(Index offset, const ValueType& val) {
509  assert(offset<SIZE); mBuffer[offset] = val;
510  }
511 
513  void addValue(const ValueType& val);
515  void scaleValue(const ValueType& scale);
516 
518  void setValuesOn() { mValueMask.setOn(); }
520  void setValuesOff() { mValueMask.setOff(); }
521 
523  bool isValueOn(const Coord& xyz) const { return this->isValueOn(LeafNode::coord2offset(xyz)); }
525  bool isValueOn(Index offset) const { return mValueMask.isOn(offset); }
526 
528  static bool hasActiveTiles() { return false; }
529 
532  void fill(const CoordBBox& bbox, const ValueType&, bool active = true);
533 
535  void fill(const ValueType& value);
536 
538  void fill(const ValueType& value, bool active);
539 
542  template<typename AccessorT>
543  const ValueType& getValueAndCache(const Coord& xyz, AccessorT&) const
544  {
545  return this->getValue(xyz);
546  }
547 
550  template<typename AccessorT>
551  bool isValueOnAndCache(const Coord& xyz, AccessorT&) const { return this->isValueOn(xyz); }
552 
555  template<typename AccessorT>
556  void setValueAndCache(const Coord& xyz, const ValueType& val, AccessorT&)
557  {
558  this->setValueOn(xyz, val);
559  }
560 
564  template<typename AccessorT>
565  void setValueOnlyAndCache(const Coord& xyz, const ValueType& val, AccessorT&)
566  {
567  this->setValueOnly(xyz, val);
568  }
569 
574  template<typename AccessorT>
575  void setValueOnSumAndCache(const Coord& xyz, const ValueType& val, AccessorT&)
576  {
577  this->setValueOnSum(xyz, val);
578  }
579 
582  template<typename AccessorT>
583  void setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT&)
584  {
585  this->setValueOff(xyz, value);
586  }
587 
591  template<typename AccessorT>
592  void setActiveStateAndCache(const Coord& xyz, bool on, AccessorT&)
593  {
594  this->setActiveState(xyz, on);
595  }
596 
600  template<typename AccessorT>
601  bool probeValueAndCache(const Coord& xyz, ValueType& val, AccessorT&) const
602  {
603  return this->probeValue(xyz, val);
604  }
605 
609  template<typename AccessorT>
610  const ValueType& getValue(const Coord& xyz, bool& state, int& level, AccessorT&) const
611  {
612  const Index offset = this->coord2offset(xyz);
613  state = mValueMask.isOn(offset);
614  level = LEVEL;
615  return mBuffer[offset];
616  }
617 
620  template<typename AccessorT>
621  static Index getValueLevelAndCache(const Coord&, AccessorT&) { return LEVEL; }
622 
626  const ValueType& getFirstValue() const { return mBuffer[0]; }
628  const ValueType& getLastValue() const { return mBuffer[SIZE - 1]; }
629 
632  void resetBackground(const ValueType& oldBackground, const ValueType& newBackground);
633 
643  void signedFloodFill(const ValueType& background);
644 
651  void signedFloodFill(const ValueType& outside, const ValueType& inside);
652 
653  void negate();
654 
655  void merge(const LeafNode&);
656  void merge(const LeafNode& other, const ValueType& /*bg*/, const ValueType& /*otherBG*/)
657  {
658  LeafNode::merge(other);
659  }
661 
666  template<typename OtherType>
667  void topologyUnion(const LeafNode<OtherType, Log2Dim>& other);
668 
677  template<typename OtherType>
678  void topologyIntersection(const LeafNode<OtherType, Log2Dim>& other, const ValueType&);
679 
680  template<typename CombineOp>
681  void combine(const LeafNode& other, CombineOp& op);
682  template<typename CombineOp>
683  void combine(const ValueType& value, bool valueIsActive, CombineOp& op);
684 
685  template<typename CombineOp>
686  void combine2(const LeafNode& other, const ValueType&, bool valueIsActive, CombineOp&);
687  template<typename CombineOp>
688  void combine2(const ValueType&, const LeafNode& other, bool valueIsActive, CombineOp&);
689  template<typename CombineOp>
690  void combine2(const LeafNode& b0, const LeafNode& b1, CombineOp&);
691 
697  template<typename BBoxOp> void visitActiveBBox(BBoxOp&) const;
698 
699  template<typename VisitorOp> void visit(VisitorOp&);
700  template<typename VisitorOp> void visit(VisitorOp&) const;
701 
702  template<typename OtherLeafNodeType, typename VisitorOp>
703  void visit2Node(OtherLeafNodeType& other, VisitorOp&);
704  template<typename OtherLeafNodeType, typename VisitorOp>
705  void visit2Node(OtherLeafNodeType& other, VisitorOp&) const;
706  template<typename IterT, typename VisitorOp>
707  void visit2(IterT& otherIter, VisitorOp&, bool otherIsLHS = false);
708  template<typename IterT, typename VisitorOp>
709  void visit2(IterT& otherIter, VisitorOp&, bool otherIsLHS = false) const;
710 
712 
713  template<typename PruneOp> void pruneOp(PruneOp&) {}
714  void prune(const ValueType& /*tolerance*/ = zeroVal<ValueType>()) {}
715  void pruneInactive(const ValueType&) {}
717 
718 
719  LeafNode* touchLeaf(const Coord&) { return this; }
720  template<typename AccessorT>
721  LeafNode* touchLeafAndCache(const Coord&, AccessorT&) { return this; }
722  LeafNode* probeLeaf(const Coord&) { return this; }
723  template<typename AccessorT>
724  LeafNode* probeLeafAndCache(const Coord&, AccessorT&) { return this; }
726 
727 
728  const LeafNode* probeConstLeaf(const Coord&) const { return this; }
729  template<typename AccessorT>
730  const LeafNode* probeConstLeafAndCache(const Coord&, AccessorT&) const { return this; }
732 
736  bool isConstant(ValueType& constValue, bool& state,
737  const ValueType& tolerance = zeroVal<ValueType>()) const;
739  bool isInactive() const { return mValueMask.isOff(); }
740 
741 protected:
742  friend class ::TestLeaf;
743  template<typename> friend class ::TestLeafIO;
744 
745  // During topology-only construction, access is needed
746  // to protected/private members of other template instances.
747  template<typename, Index> friend class LeafNode;
748 
755 
756  // Allow iterators to call mask accessor methods (see below).
761 
768 
769  // Mask accessors
770 public:
771  bool isValueMaskOn(Index n) const { return mValueMask.isOn(n); }
772  bool isValueMaskOn() const { return mValueMask.isOn(); }
773  bool isValueMaskOff(Index n) const { return mValueMask.isOff(n); }
774  bool isValueMaskOff() const { return mValueMask.isOff(); }
775  const NodeMaskType& getValueMask() const { return mValueMask; }
776  NodeMaskType& getValueMask() { return mValueMask; }
777  void setValueMask(const NodeMaskType& mask) { mValueMask = mask; }
778  bool isChildMaskOn(Index) const { return false; } // leaf nodes have no children
779  bool isChildMaskOff(Index) const { return true; }
780  bool isChildMaskOff() const { return true; }
781 protected:
782  void setValueMask(Index n, bool on) { mValueMask.set(n, on); }
783  void setValueMaskOn(Index n) { mValueMask.setOn(n); }
784  void setValueMaskOff(Index n) { mValueMask.setOff(n); }
785 
787  static void evalNodeOrigin(Coord& xyz) { xyz &= ~(DIM - 1); }
788 
789  template<typename NodeT, typename VisitorOp, typename ChildAllIterT>
790  static inline void doVisit(NodeT&, VisitorOp&);
791 
792  template<typename NodeT, typename OtherNodeT, typename VisitorOp,
793  typename ChildAllIterT, typename OtherChildAllIterT>
794  static inline void doVisit2Node(NodeT& self, OtherNodeT& other, VisitorOp&);
795 
796  template<typename NodeT, typename VisitorOp,
797  typename ChildAllIterT, typename OtherChildAllIterT>
798  static inline void doVisit2(NodeT& self, OtherChildAllIterT&, VisitorOp&, bool otherIsLHS);
799 
800 private:
801 
802  // Disallow copying.
803  LeafNode& operator=(const LeafNode&);
804 
805 }; // end of LeafNode class
806 
807 
809 
810 template<typename T, Index Log2Dim>
811 inline
813  mValueMask(),//default is off!
814  mOrigin(0, 0, 0)
815 {
816 }
817 
818 
819 template<typename T, Index Log2Dim>
820 inline
821 LeafNode<T, Log2Dim>::LeafNode(const Coord& xyz, const ValueType& val, bool active):
822  mBuffer(val),
823  mValueMask(active),
824  mOrigin(xyz & (~(DIM - 1)))
825 {
826 }
827 
828 template<typename T, Index Log2Dim>
829 template<typename OtherValueType>
830 inline
832  const ValueType& background, TopologyCopy):
833  mBuffer(background),
834  mValueMask(other.mValueMask),
835  mOrigin(other.mOrigin)
836 {
837 }
838 
839 template<typename T, Index Log2Dim>
840 template<typename OtherValueType>
841 inline
843  const ValueType& offValue, const ValueType& onValue, TopologyCopy):
844  mValueMask(other.mValueMask),
845  mOrigin(other.mOrigin)
846 {
847  for (Index i = 0; i < SIZE; ++i) {
848  mBuffer[i] = (mValueMask.isOn(i) ? onValue : offValue);
849  }
850 }
851 
852 template<typename T, Index Log2Dim>
853 inline
855  mBuffer(other.mBuffer),
856  mValueMask(other.mValueMask),
857  mOrigin(other.mOrigin)
858 {
859 }
860 
861 
862 template<typename T, Index Log2Dim>
863 inline
865 {
866 }
867 
868 
869 template<typename T, Index Log2Dim>
870 inline std::string
872 {
873  std::ostringstream ostr;
874  ostr << "LeafNode @" << mOrigin << ": " << mBuffer;
875  return ostr.str();
876 }
877 
878 
880 
881 
882 template<typename T, Index Log2Dim>
883 inline Index
885 {
886  assert ((xyz[0]&DIM-1u)<DIM && (xyz[1]&DIM-1u)<DIM && (xyz[2]&DIM-1u)<DIM);
887  return ((xyz[0]&DIM-1u)<<2*Log2Dim)
888  + ((xyz[1]&DIM-1u)<< Log2Dim)
889  + (xyz[2]&DIM-1u);
890 }
891 
892 
893 template<typename T, Index Log2Dim>
894 inline void
896 {
897  assert(n<(1<< 3*Log2Dim));
898  xyz.setX(n >> 2*Log2Dim);
899  n &= ((1<<2*Log2Dim)-1);
900  xyz.setY(n >> Log2Dim);
901  xyz.setZ(n & ((1<<Log2Dim)-1));
902 }
903 
904 
905 template<typename T, Index Log2Dim>
906 inline Coord
908 {
909  Coord local;
910  this->offset2coord(n, local);
911  return Coord(local + this->getOrigin());
912 }
913 
914 
916 
917 
918 template<typename ValueT, Index Log2Dim>
919 inline const ValueT&
921 {
922  return this->getValue(LeafNode::coord2offset(xyz));
923 }
924 
925 template<typename ValueT, Index Log2Dim>
926 inline const ValueT&
928 {
929  assert(offset < SIZE);
930  return mBuffer[offset];
931 }
932 
933 
934 template<typename T, Index Log2Dim>
935 inline bool
937 {
938  return this->probeValue(LeafNode::coord2offset(xyz), val);
939 }
940 
941 template<typename T, Index Log2Dim>
942 inline bool
944 {
945  assert(offset < SIZE);
946  val = mBuffer[offset];
947  return mValueMask.isOn(offset);
948 }
949 
950 
951 template<typename T, Index Log2Dim>
952 inline void
954 {
955  this->setValueOff(LeafNode::coord2offset(xyz), val);
956 }
957 
958 template<typename T, Index Log2Dim>
959 inline void
961 {
962  assert(offset < SIZE);
963  mBuffer[offset] = val;
964  mValueMask.setOff(offset);
965 }
966 
967 
968 template<typename T, Index Log2Dim>
969 inline void
971 {
972  mValueMask.set(this->coord2offset(xyz), on);
973 }
974 
975 
976 template<typename T, Index Log2Dim>
977 inline void
979 {
980  for (typename NodeMaskType::OnIterator iter = mValueMask.beginOn(); iter; ++iter) {
981  mBuffer[iter.pos()] += val;
982  }
983 }
984 
985 
986 template<typename T, Index Log2Dim>
987 inline void
989 {
990  for (typename NodeMaskType::OnIterator iter = mValueMask.beginOn(); iter; ++iter) {
991  mBuffer[iter.pos()] *= scale;
992  }
993 }
994 
995 
997 
998 
999 template<typename T, Index Log2Dim>
1000 inline void
1001 LeafNode<T, Log2Dim>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
1002 {
1003  for (Int32 x = bbox.min().x(); x <= bbox.max().x(); ++x) {
1004  const Index offsetX = (x&DIM-1u)<<2*Log2Dim;
1005  for (Int32 y = bbox.min().y(); y <= bbox.max().y(); ++y) {
1006  const Index offsetXY = offsetX + ((y&DIM-1u)<< Log2Dim);
1007  for (Int32 z = bbox.min().z(); z <= bbox.max().z(); ++z) {
1008  const Index offset = offsetXY + (z&DIM-1u);
1009  mBuffer[offset] = value;
1010  mValueMask.set(offset, active);
1011  }
1012  }
1013  }
1014 }
1015 
1016 template<typename T, Index Log2Dim>
1017 inline void
1019 {
1020  mBuffer.fill(value);
1021 }
1022 
1023 template<typename T, Index Log2Dim>
1024 inline void
1025 LeafNode<T, Log2Dim>::fill(const ValueType& value, bool active)
1026 {
1027  mBuffer.fill(value);
1028  mValueMask.set(active);
1029 }
1030 
1031 
1033 
1034 
1035 template<typename T, Index Log2Dim>
1036 inline void
1037 LeafNode<T, Log2Dim>::readTopology(std::istream& is, bool /*fromHalf*/)
1038 {
1039  mValueMask.load(is);
1040 }
1041 
1042 
1043 template<typename T, Index Log2Dim>
1044 inline void
1045 LeafNode<T, Log2Dim>::writeTopology(std::ostream& os, bool /*toHalf*/) const
1046 {
1047  mValueMask.save(os);
1048 }
1049 
1050 
1052 
1053 
1054 template<typename T, Index Log2Dim>
1055 inline void
1056 LeafNode<T,Log2Dim>::readBuffers(std::istream& is, bool fromHalf)
1057 {
1058  // Read in the value mask.
1059  mValueMask.load(is);
1060 
1061  int8_t numBuffers = 1;
1063  // Read in the origin.
1064  is.read(reinterpret_cast<char*>(&mOrigin), sizeof(Coord::ValueType) * 3);
1065 
1066  // Read in the number of buffers, which should now always be one.
1067  is.read(reinterpret_cast<char*>(&numBuffers), sizeof(int8_t));
1068  }
1069 
1070  io::readCompressedValues(is, mBuffer.mData, SIZE, mValueMask, fromHalf);
1071 
1072  if (numBuffers > 1) {
1073  // Read in and discard auxiliary buffers that were created with earlier
1074  // versions of the library. (Auxiliary buffers are not mask compressed.)
1075  const bool zipped = io::getDataCompression(is) & io::COMPRESS_ZIP;
1076  Buffer temp;
1077  for (int i = 1; i < numBuffers; ++i) {
1078  if (fromHalf) {
1079  io::HalfReader<io::RealToHalf<T>::isReal, T>::read(is, temp.mData, SIZE, zipped);
1080  } else {
1081  io::readData<T>(is, temp.mData, SIZE, zipped);
1082  }
1083  }
1084  }
1085 }
1086 
1087 
1088 template<typename T, Index Log2Dim>
1089 inline void
1090 LeafNode<T, Log2Dim>::writeBuffers(std::ostream& os, bool toHalf) const
1091 {
1092  // Write out the value mask.
1093  mValueMask.save(os);
1094 
1095  io::writeCompressedValues(os, mBuffer.mData, SIZE,
1096  mValueMask, /*childMask=*/NodeMaskType(), toHalf);
1097 }
1098 
1099 
1101 
1102 
1103 template<typename T, Index Log2Dim>
1104 inline bool
1106 {
1107  return mOrigin == other.mOrigin &&
1108  mValueMask == other.mValueMask &&
1109  mBuffer == other.mBuffer;
1110 }
1111 
1112 
1113 template<typename T, Index Log2Dim>
1114 inline Index64
1116 {
1117  return mBuffer.memUsage() + sizeof(mOrigin) + mValueMask.memUsage();
1118 }
1119 
1120 
1121 template<typename T, Index Log2Dim>
1122 inline void
1124 {
1125  const CoordBBox this_bbox = this->getNodeBoundingBox();
1126  if (bbox.isInside(this_bbox)) {
1127  // nothing to do
1128  } else if (this->isDense()) {
1129  bbox.expand(this_bbox);
1130  } else {
1131  for (ValueOnCIter iter=this->cbeginValueOn(); iter; ++iter) bbox.expand(iter.getCoord());
1132  }
1133 }
1134 
1135 
1136 template<typename T, Index Log2Dim>
1137 template<typename OtherType, Index OtherLog2Dim>
1138 inline bool
1140 {
1141  assert(other);
1142  return (Log2Dim == OtherLog2Dim && mValueMask == other->getValueMask());
1143 }
1144 
1145 
1146 template<typename T, Index Log2Dim>
1147 inline bool
1149  bool& state, const ValueType& tolerance) const
1150 {
1151  if (!mValueMask.isOn() && !mValueMask.isOff()) return false;
1152 
1153  state = mValueMask.isOn();
1154 
1155  bool allEqual = true;
1156  const T value = mBuffer[0];
1157  for (Index i = 1; allEqual && i < SIZE; ++i) {
1159  allEqual = math::isApproxEqual(mBuffer[i], value, tolerance);
1160  }
1161  if (allEqual) constValue = value;
1162  return allEqual;
1163 }
1164 
1165 template<typename T, Index Log2Dim>
1166 inline void
1168 {
1169  this->signedFloodFill(background, negative(background));
1170 }
1171 
1172 template<typename T, Index Log2Dim>
1173 inline void
1175  const ValueType& insideValue)
1176 {
1177  const Index first = mValueMask.findFirstOn();
1178  if (first < SIZE) {
1179  bool xInside = math::isNegative(mBuffer[first]), yInside = xInside, zInside = xInside;
1180  for (Index x = 0; x != (1 << Log2Dim); ++x) {
1181  const Index x00 = x << (2 * Log2Dim);
1182  if (mValueMask.isOn(x00)) {
1183  xInside = math::isNegative(mBuffer[x00]); // element(x, 0, 0)
1184  }
1185  yInside = xInside;
1186  for (Index y = 0; y != (1 << Log2Dim); ++y) {
1187  const Index xy0 = x00 + (y << Log2Dim);
1188  if (mValueMask.isOn(xy0)) {
1189  yInside = math::isNegative(mBuffer[xy0]); // element(x, y, 0)
1190  }
1191  zInside = yInside;
1192  for (Index z = 0; z != (1 << Log2Dim); ++z) {
1193  const Index xyz = xy0 + z; // element(x, y, z)
1194  if (mValueMask.isOn(xyz)) {
1195  zInside = math::isNegative(mBuffer[xyz]);
1196  } else {
1197  mBuffer[xyz] = zInside ? insideValue : outsideValue;
1198  }
1199  }
1200  }
1201  }
1202  } else {// if no active voxels exist simply use the sign of the first value
1203  mBuffer.fill(math::isNegative(mBuffer[0]) ? insideValue : outsideValue);
1204  }
1205 }
1206 
1207 
1208 template<typename T, Index Log2Dim>
1209 inline void
1211  const ValueType& newBackground)
1212 {
1213  typename NodeMaskType::OffIterator iter;
1214  // For all inactive values...
1215  for (iter = this->mValueMask.beginOff(); iter; ++iter) {
1216  ValueType &inactiveValue = mBuffer[iter.pos()];
1217  if (math::isApproxEqual(inactiveValue, oldBackground)) {
1218  inactiveValue = newBackground;
1219  } else if (math::isApproxEqual(inactiveValue, negative(oldBackground))) {
1220  inactiveValue = negative(newBackground);
1221  }
1222  }
1223 }
1224 
1225 
1226 template<typename T, Index Log2Dim>
1227 inline void
1229 {
1230  typename NodeMaskType::OnIterator iter = other.mValueMask.beginOn();
1231  for (; iter; ++iter) {
1232  const Index n = iter.pos();
1233  if (mValueMask.isOn(n)) continue;
1234  mBuffer[n] = other.mBuffer[n];
1235  mValueMask.setOn(n);
1236  }
1237 }
1238 
1239 
1240 template<typename T, Index Log2Dim>
1241 template<typename OtherType>
1242 inline void
1244 {
1245  mValueMask |= other.getValueMask();
1246 }
1247 
1248 template<typename T, Index Log2Dim>
1249 template<typename OtherType>
1250 inline void
1252  const ValueType&)
1253 {
1254  mValueMask &= other.getValueMask();
1255 }
1256 
1257 template<typename T, Index Log2Dim>
1258 inline void
1260 {
1261  for (Index i = 0; i < SIZE; ++i) {
1262  mBuffer[i] = -mBuffer[i];
1263  }
1264 }
1265 
1266 
1268 
1269 
1270 template<typename T, Index Log2Dim>
1271 template<typename CombineOp>
1272 inline void
1273 LeafNode<T, Log2Dim>::combine(const LeafNode& other, CombineOp& op)
1274 {
1275  CombineArgs<T> args;
1276  for (Index i = 0; i < SIZE; ++i) {
1277  op(args.setARef(mBuffer[i])
1278  .setAIsActive(mValueMask.isOn(i))
1279  .setBRef(other.mBuffer[i])
1280  .setBIsActive(other.mValueMask.isOn(i))
1281  .setResultRef(mBuffer[i]));
1282  mValueMask.set(i, args.resultIsActive());
1283  }
1284 }
1285 
1286 
1287 template<typename T, Index Log2Dim>
1288 template<typename CombineOp>
1289 inline void
1290 LeafNode<T, Log2Dim>::combine(const ValueType& value, bool valueIsActive, CombineOp& op)
1291 {
1292  CombineArgs<T> args;
1293  args.setBRef(value).setBIsActive(valueIsActive);
1294  for (Index i = 0; i < SIZE; ++i) {
1295  op(args.setARef(mBuffer[i])
1296  .setAIsActive(mValueMask.isOn(i))
1297  .setResultRef(mBuffer[i]));
1298  mValueMask.set(i, args.resultIsActive());
1299  }
1300 }
1301 
1302 
1304 
1305 
1306 template<typename T, Index Log2Dim>
1307 template<typename CombineOp>
1308 inline void
1310  bool valueIsActive, CombineOp& op)
1311 {
1312  CombineArgs<T> args;
1313  args.setBRef(value).setBIsActive(valueIsActive);
1314  for (Index i = 0; i < SIZE; ++i) {
1315  op(args.setARef(other.mBuffer[i])
1316  .setAIsActive(other.mValueMask.isOn(i))
1317  .setResultRef(mBuffer[i]));
1318  mValueMask.set(i, args.resultIsActive());
1319  }
1320 }
1321 
1322 
1323 template<typename T, Index Log2Dim>
1324 template<typename CombineOp>
1325 inline void
1327  bool valueIsActive, CombineOp& op)
1328 {
1329  CombineArgs<T> args;
1330  args.setARef(value).setAIsActive(valueIsActive);
1331  for (Index i = 0; i < SIZE; ++i) {
1332  op(args.setBRef(other.mBuffer[i])
1333  .setBIsActive(other.mValueMask.isOn(i))
1334  .setResultRef(mBuffer[i]));
1335  mValueMask.set(i, args.resultIsActive());
1336  }
1337 }
1338 
1339 
1340 template<typename T, Index Log2Dim>
1341 template<typename CombineOp>
1342 inline void
1343 LeafNode<T, Log2Dim>::combine2(const LeafNode& b0, const LeafNode& b1, CombineOp& op)
1344 {
1345  CombineArgs<T> args;
1346  for (Index i = 0; i < SIZE; ++i) {
1347  mValueMask.set(i, b0.mValueMask.isOn(i) || b1.mValueMask.isOn(i));
1348  op(args.setARef(b0.mBuffer[i])
1349  .setAIsActive(b0.mValueMask.isOn(i))
1350  .setBRef(b1.mBuffer[i])
1351  .setBIsActive(b1.mValueMask.isOn(i))
1352  .setResultRef(mBuffer[i]));
1353  mValueMask.set(i, args.resultIsActive());
1354  }
1355 }
1356 
1357 
1359 
1360 
1361 template<typename T, Index Log2Dim>
1362 template<typename BBoxOp>
1363 inline void
1365 {
1366  if (op.template descent<LEVEL>()) {
1367  for (ValueOnCIter i=this->cbeginValueOn(); i; ++i) {
1368 #ifdef _MSC_VER
1369  op.operator()<LEVEL>(CoordBBox::createCube(i.getCoord(), 1));
1370 #else
1371  op.template operator()<LEVEL>(CoordBBox::createCube(i.getCoord(), 1));
1372 #endif
1373  }
1374  } else {
1375 #ifdef _MSC_VER
1376  op.operator()<LEVEL>(this->getNodeBoundingBox());
1377 #else
1378  op.template operator()<LEVEL>(this->getNodeBoundingBox());
1379 #endif
1380  }
1381 }
1382 
1383 
1384 template<typename T, Index Log2Dim>
1385 template<typename VisitorOp>
1386 inline void
1388 {
1389  doVisit<LeafNode, VisitorOp, ChildAllIter>(*this, op);
1390 }
1391 
1392 
1393 template<typename T, Index Log2Dim>
1394 template<typename VisitorOp>
1395 inline void
1396 LeafNode<T, Log2Dim>::visit(VisitorOp& op) const
1397 {
1398  doVisit<const LeafNode, VisitorOp, ChildAllCIter>(*this, op);
1399 }
1400 
1401 
1402 template<typename T, Index Log2Dim>
1403 template<typename NodeT, typename VisitorOp, typename ChildAllIterT>
1404 inline void
1405 LeafNode<T, Log2Dim>::doVisit(NodeT& self, VisitorOp& op)
1406 {
1407  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
1408  op(iter);
1409  }
1410 }
1411 
1412 
1414 
1415 
1416 template<typename T, Index Log2Dim>
1417 template<typename OtherLeafNodeType, typename VisitorOp>
1418 inline void
1419 LeafNode<T, Log2Dim>::visit2Node(OtherLeafNodeType& other, VisitorOp& op)
1420 {
1421  doVisit2Node<LeafNode, OtherLeafNodeType, VisitorOp, ChildAllIter,
1422  typename OtherLeafNodeType::ChildAllIter>(*this, other, op);
1423 }
1424 
1425 
1426 template<typename T, Index Log2Dim>
1427 template<typename OtherLeafNodeType, typename VisitorOp>
1428 inline void
1429 LeafNode<T, Log2Dim>::visit2Node(OtherLeafNodeType& other, VisitorOp& op) const
1430 {
1431  doVisit2Node<const LeafNode, OtherLeafNodeType, VisitorOp, ChildAllCIter,
1432  typename OtherLeafNodeType::ChildAllCIter>(*this, other, op);
1433 }
1434 
1435 
1436 template<typename T, Index Log2Dim>
1437 template<
1438  typename NodeT,
1439  typename OtherNodeT,
1440  typename VisitorOp,
1441  typename ChildAllIterT,
1442  typename OtherChildAllIterT>
1443 inline void
1444 LeafNode<T, Log2Dim>::doVisit2Node(NodeT& self, OtherNodeT& other, VisitorOp& op)
1445 {
1446  // Allow the two nodes to have different ValueTypes, but not different dimensions.
1447  BOOST_STATIC_ASSERT(OtherNodeT::SIZE == NodeT::SIZE);
1448  BOOST_STATIC_ASSERT(OtherNodeT::LEVEL == NodeT::LEVEL);
1449 
1450  ChildAllIterT iter = self.beginChildAll();
1451  OtherChildAllIterT otherIter = other.beginChildAll();
1452 
1453  for ( ; iter && otherIter; ++iter, ++otherIter) {
1454  op(iter, otherIter);
1455  }
1456 }
1457 
1458 
1460 
1461 
1462 template<typename T, Index Log2Dim>
1463 template<typename IterT, typename VisitorOp>
1464 inline void
1465 LeafNode<T, Log2Dim>::visit2(IterT& otherIter, VisitorOp& op, bool otherIsLHS)
1466 {
1467  doVisit2<LeafNode, VisitorOp, ChildAllIter, IterT>(
1468  *this, otherIter, op, otherIsLHS);
1469 }
1470 
1471 
1472 template<typename T, Index Log2Dim>
1473 template<typename IterT, typename VisitorOp>
1474 inline void
1475 LeafNode<T, Log2Dim>::visit2(IterT& otherIter, VisitorOp& op, bool otherIsLHS) const
1476 {
1477  doVisit2<const LeafNode, VisitorOp, ChildAllCIter, IterT>(
1478  *this, otherIter, op, otherIsLHS);
1479 }
1480 
1481 
1482 template<typename T, Index Log2Dim>
1483 template<
1484  typename NodeT,
1485  typename VisitorOp,
1486  typename ChildAllIterT,
1487  typename OtherChildAllIterT>
1488 inline void
1489 LeafNode<T, Log2Dim>::doVisit2(NodeT& self, OtherChildAllIterT& otherIter,
1490  VisitorOp& op, bool otherIsLHS)
1491 {
1492  if (!otherIter) return;
1493 
1494  if (otherIsLHS) {
1495  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
1496  op(otherIter, iter);
1497  }
1498  } else {
1499  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
1500  op(iter, otherIter);
1501  }
1502  }
1503 }
1504 
1505 
1507 
1508 
1509 template<typename T, Index Log2Dim>
1510 inline std::ostream&
1511 operator<<(std::ostream& os, const typename LeafNode<T, Log2Dim>::Buffer& buf)
1512 {
1513  for (Index32 i = 0, N = buf.size(); i < N; ++i) os << buf.mData[i] << ", ";
1514  return os;
1515 }
1516 
1517 } // namespace tree
1518 } // namespace OPENVDB_VERSION_NAME
1519 } // namespace openvdb
1520 
1521 
1523 
1524 
1525 // Specialization for LeafNodes of type bool
1526 #include "LeafNodeBool.h"
1527 
1528 #endif // OPENVDB_TREE_LEAFNODE_HAS_BEEN_INCLUDED
1529 
1530 // Copyright (c) 2012-2013 DreamWorks Animation LLC
1531 // All rights reserved. This software is distributed under the
1532 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )