OpenVDB  0.104.0
NodeMasks.h
Go to the documentation of this file.
1 
2 //
3 // Copyright (c) 2012 DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
30 //
34 
35 
36 #ifndef OPENVDB_UTIL_NODEMASK_HAS_BEEN_INCLUDED
37 #define OPENVDB_UTIL_NODEMASK_HAS_BEEN_INCLUDED
38 
39 #include <cassert>
40 #include <cstring>
41 #include <iostream>// for cout
42 #include <openvdb/Types.h>
43 
44 
45 namespace openvdb {
47 namespace OPENVDB_VERSION_NAME {
48 namespace util {
49 
50 inline Index32
52 {
53  v = v - ((v >> 1) & 0x55555555);
54  v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
55  return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
56 }
57 
58 inline Index32 CountOff(Index32 v) { return 32-CountOn(v); }
59 
60 
62 inline Index32
64 {
65  static const Index32 MultiplyDeBruijnBitPosition[32] = {
66  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
67  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
68  };
69  return MultiplyDeBruijnBitPosition[Index32((v & -v) * 0x077CB531U) >> 27];
70 }
71 
73 inline Index32
75 {
76  static const Index32 MultiplyDeBruijnBitPosition[32] = {
77  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
78  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
79  };
80  v |= v >> 1; // first round down to one less than a power of 2
81  v |= v >> 2;
82  v |= v >> 4;
83  v |= v >> 8;
84  v |= v >> 16;
85  return MultiplyDeBruijnBitPosition[Index32(v * 0x07C4ACDDU) >> 27];
86 }
87 
88 
89 // This class is 32-bit specefic, hence the use if Index32 vs Index!
90 template<Index Log2Dim>
91 class NodeMask
92 {
93 public:
94  static const Index32 LOG2DIM = Log2Dim;
95  static const Index32 DIM = 1<<Log2Dim;
96  static const Index32 BIT_SIZE = 1<<3*Log2Dim;
97  static const Index32 INT_SIZE = (1<<(3*Log2Dim-3))>>2;
98  BOOST_STATIC_ASSERT( Log2Dim>1 );
99 
100 protected:
101  Index32 mBits[INT_SIZE];// only member data!!
102 
103 public:
104  // Default is always off!
105  NodeMask() { this->setOff(); }
106 
107  NodeMask(bool on) { this->set(on); }
108 
109  NodeMask(const NodeMask &B) { *this = B; }
110 
112 
113  void operator = (const NodeMask &B)
114  {
115  for (Index32 i=0; i<INT_SIZE; ++i) mBits[i]=B.mBits[i];
116  }
117 
119  {
120  protected:
121  Index32 mPos;//bit position
122  const NodeMask* mParent;//this iterator can't change the parent_mask!
123  public:
124  BaseIterator() : mPos(BIT_SIZE), mParent(NULL) {}
125  BaseIterator(Index32 pos,const NodeMask *parent) :
126  mPos(pos), mParent(parent) {
127  assert( (parent==NULL && pos==0 ) || (parent!=NULL && pos<=BIT_SIZE) );
128  }
129  bool operator==(const BaseIterator &iter) const {return mPos == iter.mPos;}
130  bool operator!=(const BaseIterator &iter) const {return mPos != iter.mPos;}
131  bool operator< (const BaseIterator &iter) const {return mPos < iter.mPos;}
132  void operator=(const BaseIterator &iter) {
133  mPos = iter.mPos;
134  mParent = iter.mParent;
135  }
136  Index32 offset() const {return mPos;}
137 
138  Index32 pos() const {return mPos;}
139 
140  OPENVDB_DEPRECATED Index32 getOffset() const {return mPos;}
141 
142  bool test() const {
143  assert(mPos <= BIT_SIZE);
144  return (mPos != BIT_SIZE);
145  }
146 
147  operator bool() const {return this->test();}
148  }; // class BaseIterator
149 
151  class OnIterator: public BaseIterator
152  {
153  protected:
154  using BaseIterator::mPos;//bit position;
155  using BaseIterator::mParent;//this iterator can't change the parent_mask!
156  public:
158  OnIterator(Index32 pos,const NodeMask *parent) : BaseIterator(pos,parent) {}
159  void increment() {
160  assert(mParent!=NULL);
161  mPos=mParent->findNextOn(mPos+1);
162  assert(mPos <= BIT_SIZE);
163  }
164  void increment(Index n) {
165  for (Index i=0; i<n && this->next(); ++i) {}
166  }
167  bool next() {
168  this->increment();
169  return this->test();
170  }
171  bool operator*() const {return true;}
173  this->increment();
174  return *this;
175  }
176  }; // class OnIterator
177 
178  class OffIterator: public BaseIterator
179  {
180  protected:
181  using BaseIterator::mPos;//bit position;
182  using BaseIterator::mParent;//this iterator can't change the parent_mask!
183  public:
185  OffIterator(Index32 pos,const NodeMask *parent) : BaseIterator(pos,parent) {}
186  void increment() {
187  assert(mParent!=NULL);
188  mPos=mParent->findNextOff(mPos+1);
189  assert(mPos <= BIT_SIZE);
190  }
191  void increment(Index n) {
192  for (Index i=0; i<n && this->next(); ++i) {}
193  }
194  bool next() {
195  this->increment();
196  return this->test();
197  }
198  bool operator*() const {return false;}
200  this->increment();
201  return *this;
202  }
203  }; // class OffIterator
204 
206  {
207  protected:
208  using BaseIterator::mPos;//bit position;
209  using BaseIterator::mParent;//this iterator can't change the parent_mask!
210 
211  public:
213  DenseIterator(Index32 pos,const NodeMask *parent) : BaseIterator(pos,parent) {}
214  void increment() {
215  assert(mParent!=NULL);
216  mPos += 1;//careful - the increment might go beyond the end
217  assert(mPos<= BIT_SIZE);
218  }
219  void increment(Index n) {
220  for (Index i=0; i<n && this->next(); ++i) {}
221  }
222  bool next() {
223  this->increment();
224  return this->test();
225  }
226  bool operator*() const {return mParent->isOn(mPos);}
228  this->increment();
229  return *this;
230  }
231  }; // class DenseIterator
232 
233  OnIterator beginOn() const { return OnIterator(this->findFirstOn(),this); }
234  OnIterator endOn() const { return OnIterator(BIT_SIZE,this); }
235  OffIterator beginOff() const { return OffIterator(this->findFirstOff(),this); }
236  OffIterator endOff() const { return OffIterator(BIT_SIZE,this); }
237  DenseIterator beginDense() const { return DenseIterator(0,this); }
238  DenseIterator endDense() const { return DenseIterator(BIT_SIZE,this); }
239 
240  bool operator == (const NodeMask &B) const {
241  for (Index32 i=0; i<INT_SIZE; ++i) if (mBits[i] != B.mBits[i]) return false;
242  return true;
243  }
244 
245  bool operator != (const NodeMask &B) const {
246  for (Index32 i=0; i<INT_SIZE; ++i) if (mBits[i] != B.mBits[i]) return true;
247  return false;
248  }
249 
250  //
251  // Bitwise logical operations
252  //
253  NodeMask operator!() const { NodeMask m(*this); m.toggle(); return m; }
254  const NodeMask& operator&=(const NodeMask& other) {
255  for (Index32 i = 0; i < INT_SIZE; ++i) mBits[i] &= other.mBits[i];
256  return *this;
257  }
258  const NodeMask& operator|=(const NodeMask& other) {
259  for (Index32 i = 0; i < INT_SIZE; ++i) mBits[i] |= other.mBits[i];
260  return *this;
261  }
262  const NodeMask& operator^=(const NodeMask& other) {
263  for (Index32 i = 0; i < INT_SIZE; ++i) mBits[i] ^= other.mBits[i];
264  return *this;
265  }
266  NodeMask operator&(const NodeMask& other) const { NodeMask m(*this); m &= other; return m; }
267  NodeMask operator|(const NodeMask& other) const { NodeMask m(*this); m |= other; return m; }
268  NodeMask operator^(const NodeMask& other) const { NodeMask m(*this); m ^= other; return m; }
269 
270  Index32 getMemUsage() const {return sizeof(this);}
271 
272  Index32 countOn() const {
273  Index32 n=0;
274  for (Index32 i=0; i< INT_SIZE; ++i) n += CountOn(mBits[i]);
275  return n;
276  }
277 
278  Index32 countOff() const { return BIT_SIZE-this->countOn(); }
279 
280  void setOn(Index32 i) {
281  assert( (i>>5) < INT_SIZE);
282  mBits[i>>5] |= 1<<(i&31);
283  }
284 
285  void setOff(Index32 i) {
286  assert( (i>>5) < INT_SIZE);
287  mBits[i>>5] &= ~(1<<(i&31));
288  }
289 
290  void set(Index32 i, bool On) { On ? this->setOn(i) : this->setOff(i); }
291 
292  void set(bool On) {
293  const Index32 val = On ? 0xFFFFFFFF : 0x00000000;
294  for (Index32 i=0; i<INT_SIZE; ++i) mBits[i] = val;
295  }
296 
297  void setOn() { for (Index32 i=0; i<INT_SIZE; ++i) mBits[i]=0xFFFFFFFF; }
298  void setOff() { for (Index32 i=0; i<INT_SIZE; ++i) mBits[i]=0x00000000; }
299  void toggle(Index32 i) {
300  assert( (i>>5) < INT_SIZE);
301  mBits[i>>5] ^= 1<<(i&31);
302  }
303  void toggle() { for (Index32 i=0; i<INT_SIZE; ++i) mBits[i]=~mBits[i]; }
304  void setFirstOn() { this->setOn(0); }
305  void setLastOn() { this->setOn(BIT_SIZE-1); }
306  void setFirstOff() { this->setOff(0); }
307  void setLastOff() { this->setOff(BIT_SIZE-1); }
308  bool isOn(Index32 i) const {
309  assert( (i>>5) < INT_SIZE);
310  return ( mBits[i >> 5] & (1<<(i&31)) );
311  }
312  bool isOff(Index32 i) const {
313  assert( (i>>5) < INT_SIZE);
314  return ( ~mBits[i >> 5] & (1<<(i&31)) );
315  }
316  bool isOn() const { //all on
317  for (Index32 i=0; i<INT_SIZE; ++i) if (mBits[i] != 0xFFFFFFFF) return false;
318  return true;
319  }
320  bool isOff() const { //all off
321  for (Index32 i=0; i<INT_SIZE; ++i) if (mBits[i] != 0x00000000) return false;
322  return true;
323  }
325  Index32 i=0;
326  while(!mBits[i]) if (++i == INT_SIZE) return BIT_SIZE;//reached end
327  return 32*i + FindLowestOn(mBits[i]);
328  }
330  Index32 i=0;
331  while(!(~mBits[i])) if (++i == INT_SIZE) return BIT_SIZE;//reached end
332  return 32*i + FindLowestOn(~mBits[i]);
333  }
334 
336 
337  template<typename WordT>
338  WordT getWord(Index n) const {
339  assert(n*8*sizeof(WordT) < BIT_SIZE);
340  return reinterpret_cast<const WordT*>(mBits)[n];
341  }
342  template<typename WordT>
343  WordT& getWord(Index n) {
344  assert(n*8*sizeof(WordT) < BIT_SIZE);
345  return reinterpret_cast<WordT*>(mBits)[n];
346  }
348 
349  /*
351  static size_t serialSize() { return INT_SIZE*sizeof(Index32); }
352 
353  inline void serialSave(char*& buffer) const {
354  Index32*& target = reinterpret_cast<Index32*&>(buffer);
355  const Index32* source = mBits;
356  size_t size = INT_SIZE;
357  while (size--) *target++ = *source++;
358  }
359 
360  inline void serialLoad(char*& buffer) {
361  Index32*& source = reinterpret_cast<Index32*&>(buffer);
362  Index32* target = mBits;
363  size_t size = INT_SIZE;
364  while (size--) *target++ = *source++;
365  }
366  */
367 
368  void save(std::ostream& os) const {
369  os.write((const char *)mBits,INT_SIZE*sizeof(Index32));
370  }
371  void load(std::istream& is) {
372  is.read((char *)mBits,INT_SIZE*sizeof(Index32));
373  }
375  void printInfo(std::ostream& os=std::cout) const {
376  os << "NodeMask: Log2Dim="<<DIM<<" Bit-size="<<BIT_SIZE<<" Int-size="<<INT_SIZE<<std::endl;
377  }
378  void printBits(std::ostream& os=std::cout, Index32 max_out=80u) const {
379  const Index32 n=(BIT_SIZE>max_out?max_out:BIT_SIZE);
380  for (Index32 i=0; i < n; ++i) {
381  if ( !(i&31) )
382  os << "||";
383  else if ( !(i%8) )
384  os << "|";
385  os << this->isOn(i);
386  }
387  os << "|" << std::endl;
388  }
389  void printAll(std::ostream& os=std::cout, Index32 max_out=80u) const {
390  this->printInfo(os);
391  this->printBits(os,max_out);
392  }
393 
394  Index32 findNextOn(Index32 start) const {
395  Index32 n=start>>5;//initiate
396  if (n>=INT_SIZE) return BIT_SIZE; // check for out of bounds
397  Index32 m=start&31, b=mBits[n];
398  if (b & (1<<m)) return start;//simpel case: next is on
399  b &= 0xFFFFFFFF << m;// mask out lower bits
400  while(!b && ++n<INT_SIZE) b = mBits[n];// find next none-zero int
401  return (!b ? BIT_SIZE : 32*n + FindLowestOn(b));//catch last-int=0
402  }
403 
404  Index32 findNextOff(Index32 start) const {
405  Index32 n=start>>5;// isolate the relevant int
406  if (n>=INT_SIZE) return BIT_SIZE; // check for out of bounds
407  Index32 m=start&31, b=~mBits[n];
408  if (b & (1<<m)) return start;//simpel case: next is off
409  b &= 0xFFFFFFFF<<m;// mask out lower bits
410  while(!b && ++n<INT_SIZE) b = ~mBits[n];// find next none-zero int
411  return (!b ? BIT_SIZE : 32*n + FindLowestOn(b));//catch last-int=0
412  }
413 
414  Index32 memUsage() const {
415  return INT_SIZE*sizeof(Index32);//in bytes
416  }
417 };
418 
419 
420 // This class is 32-bit specefic, hence the use if Index32 vs Index!
422 {
423 protected:
424  Index32 mBitSize, mIntSize;
426 
427 public:
428  RootNodeMask(): mBitSize(0), mIntSize(0), mBits(NULL) {}
430  mBitSize(bit_size), mIntSize(((bit_size-1)>>5)+1), mBits(new Index32[mIntSize])
431  {
432  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
433  }
435  mBitSize(B.mBitSize), mIntSize(B.mIntSize), mBits(new Index32[mIntSize])
436  {
437  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=B.mBits[i];
438  }
439  ~RootNodeMask() {delete [] mBits;}
440 
441  void init(Index32 bit_size) {
442  mBitSize = bit_size;
443  mIntSize =((bit_size-1)>>5)+1;
444  delete [] mBits;
445  mBits = new Index32[mIntSize];
446  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
447  }
448 
449  Index getBitSize() const {return mBitSize;}
450 
451  Index getIntSize() const {return mIntSize;}
452 
453  void operator = (const RootNodeMask &B) {
454  if (mBitSize!=B.mBitSize) {
455  mBitSize=B.mBitSize;
456  mIntSize=B.mIntSize;
457  delete [] mBits;
458  mBits = new Index32[mIntSize];
459  }
460  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=B.mBits[i];
461  }
462 
464  {
465  protected:
466  Index32 mPos;//bit position
468  const RootNodeMask* mParent;//this iterator can't change the parent_mask!
469  public:
470  BaseIterator() : mPos(0), mBitSize(0), mParent(NULL) {}
471  BaseIterator(Index32 pos,const RootNodeMask *parent)
472  : mPos(pos), mBitSize(parent->getBitSize()), mParent(parent) {
473  assert( pos<=mBitSize );
474  }
475  bool operator==(const BaseIterator &iter) const {return mPos == iter.mPos;}
476  bool operator!=(const BaseIterator &iter) const {return mPos != iter.mPos;}
477  bool operator< (const BaseIterator &iter) const {return mPos < iter.mPos;}
478  void operator=(const BaseIterator &iter) {
479  mPos = iter.mPos;
480  mBitSize = iter.mBitSize;
481  mParent = iter.mParent;
482  }
483 
484  OPENVDB_DEPRECATED Index32 getOffset() const {return mPos;}
485 
486  Index32 offset() const {return mPos;}
487 
488  Index32 pos() const {return mPos;}
489 
490  bool test() const {
491  assert(mPos <= mBitSize);
492  return (mPos != mBitSize);
493  }
494 
495  operator bool() const {return this->test();}
496  }; // class BaseIterator
497 
499  class OnIterator: public BaseIterator
500  {
501  protected:
502  using BaseIterator::mPos;//bit position;
503  using BaseIterator::mBitSize;//bit size;
504  using BaseIterator::mParent;//this iterator can't change the parent_mask!
505  public:
507  OnIterator(Index32 pos,const RootNodeMask *parent) : BaseIterator(pos,parent) {}
508  void increment() {
509  assert(mParent!=NULL);
510  mPos=mParent->findNextOn(mPos+1);
511  assert(mPos <= mBitSize);
512  }
513  void increment(Index n) {
514  for (Index i=0; i<n && this->next(); ++i) {}
515  }
516  bool next() {
517  this->increment();
518  return this->test();
519  }
520  bool operator*() const {return true;}
522  this->increment();
523  return *this;
524  }
525  }; // class OnIterator
526 
527  class OffIterator: public BaseIterator
528  {
529  protected:
530  using BaseIterator::mPos;//bit position;
531  using BaseIterator::mBitSize;//bit size;
532  using BaseIterator::mParent;//this iterator can't change the parent_mask!
533  public:
535  OffIterator(Index32 pos,const RootNodeMask *parent) : BaseIterator(pos,parent) {}
536  void increment() {
537  assert(mParent!=NULL);
538  mPos=mParent->findNextOff(mPos+1);
539  assert(mPos <= mBitSize);
540  }
541  void increment(Index n) {
542  for (Index i=0; i<n && this->next(); ++i) {}
543  }
544  bool next() {
545  this->increment();
546  return this->test();
547  }
548  bool operator*() const {return true;}
550  this->increment();
551  return *this;
552  }
553  }; // class OffIterator
554 
556  {
557  protected:
558  using BaseIterator::mPos;//bit position;
559  using BaseIterator::mBitSize;//bit size;
560  using BaseIterator::mParent;//this iterator can't change the parent_mask!
561  public:
563  DenseIterator(Index32 pos,const RootNodeMask *parent) : BaseIterator(pos,parent) {}
564  void increment() {
565  assert(mParent!=NULL);
566  mPos += 1;//carefull - the increament might go beyond the end
567  assert(mPos<= mBitSize);
568  }
569  void increment(Index n) {
570  for (Index i=0; i<n && this->next(); ++i) {}
571  }
572  bool next() {
573  this->increment();
574  return this->test();
575  }
576  bool operator*() const {return mParent->isOn(mPos);}
578  this->increment();
579  return *this;
580  }
581  }; // class DenseIterator
582 
583  OnIterator beginOn() const { return OnIterator(this->findFirstOn(),this); }
584  OnIterator endOn() const { return OnIterator(mBitSize,this); }
585  OffIterator beginOff() const { return OffIterator(this->findFirstOff(),this); }
586  OffIterator endOff() const { return OffIterator(mBitSize,this); }
587  DenseIterator beginDense() const { return DenseIterator(0,this); }
588  DenseIterator endDense() const { return DenseIterator(mBitSize,this); }
589 
590  bool operator == (const RootNodeMask &B) const {
591  if (mBitSize != B.mBitSize) return false;
592  for (Index32 i=0; i<mIntSize; ++i) if (mBits[i] != B.mBits[i]) return false;
593  return true;
594  }
595 
596  bool operator != (const RootNodeMask &B) const {
597  if (mBitSize != B.mBitSize) return true;
598  for (Index32 i=0; i<mIntSize; ++i) if (mBits[i] != B.mBits[i]) return true;
599  return false;
600  }
601 
602  //
603  // Bitwise logical operations
604  //
605  RootNodeMask operator!() const { RootNodeMask m = *this; m.toggle(); return m; }
606  const RootNodeMask& operator&=(const RootNodeMask& other) {
607  assert(mIntSize == other.mIntSize);
608  for (Index32 i = 0, N = std::min(mIntSize, other.mIntSize); i < N; ++i) {
609  mBits[i] &= other.mBits[i];
610  }
611  for (Index32 i = other.mIntSize; i < mIntSize; ++i) mBits[i] = 0x00000000;
612  return *this;
613  }
614  const RootNodeMask& operator|=(const RootNodeMask& other) {
615  assert(mIntSize == other.mIntSize);
616  for (Index32 i = 0, N = std::min(mIntSize, other.mIntSize); i < N; ++i) {
617  mBits[i] |= other.mBits[i];
618  }
619  return *this;
620  }
621  const RootNodeMask& operator^=(const RootNodeMask& other) {
622  assert(mIntSize == other.mIntSize);
623  for (Index32 i = 0, N = std::min(mIntSize, other.mIntSize); i < N; ++i) {
624  mBits[i] ^= other.mBits[i];
625  }
626  return *this;
627  }
628  RootNodeMask operator&(const RootNodeMask& other) const {
629  RootNodeMask m(*this); m &= other; return m;
630  }
631  RootNodeMask operator|(const RootNodeMask& other) const {
632  RootNodeMask m(*this); m |= other; return m;
633  }
634  RootNodeMask operator^(const RootNodeMask& other) const {
635  RootNodeMask m(*this); m ^= other; return m;
636  }
637 
638 
639  Index32 getMemUsage() const {return mIntSize*sizeof(Index32) + sizeof(this);}
640 
641  Index32 countOn() const {
642  assert(mBits);
643  Index32 n=0;
644  for (Index32 i=0; i< mIntSize; ++i) n += CountOn(mBits[i]);
645  return n;
646  }
647 
648  Index32 countOff() const { return mBitSize-this->countOn(); }
649 
650  void setOn(Index32 i) {
651  assert(mBits);
652  assert( (i>>5) < mIntSize);
653  mBits[i>>5] |= 1<<(i&31);
654  }
655 
656  void setOff(Index32 i) {
657  assert(mBits);
658  assert( (i>>5) < mIntSize);
659  mBits[i>>5] &= ~(1<<(i&31));
660  }
661 
662  void set(Index32 i, bool On) { On ? this->setOn(i) : this->setOff(i); }
663 
664  void setOn() {
665  assert(mBits);
666  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=0xFFFFFFFF;
667  }
668  void setOff() {
669  assert(mBits);
670  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=0x00000000;
671  }
672  void toggle(Index32 i) {
673  assert(mBits);
674  assert( (i>>5) < mIntSize);
675  mBits[i>>5] ^= 1<<(i&31);
676  }
677  void toggle() {
678  assert(mBits);
679  for (Index32 i=0; i<mIntSize; ++i) mBits[i]=~mBits[i];
680  }
681  void setFirstOn() { this->setOn(0); }
682  void setLastOn() { this->setOn(mBitSize-1); }
683  void setFirstOff() { this->setOff(0); }
684  void setLastOff() { this->setOff(mBitSize-1); }
685  bool isOn(Index32 i) const {
686  assert(mBits);
687  assert( (i>>5) < mIntSize);
688  return ( mBits[i >> 5] & (1<<(i&31)) );
689  }
690  bool isOff(Index32 i) const {
691  assert(mBits);
692  assert( (i>>5) < mIntSize);
693  return ( ~mBits[i >> 5] & (1<<(i&31)) );
694  }
695 
696  bool isOn() const {
697  if (!mBits) return false;//undefined is off
698  for (Index32 i=0; i<mIntSize; ++i) if (mBits[i] != 0xFFFFFFFF) return false;
699  return true;
700  }
701 
702  bool isOff() const {
703  if (!mBits) return true;//undefined is off
704  for (Index32 i=0; i<mIntSize; ++i) if (mBits[i] != 0) return false;
705  return true;
706  }
707 
709  assert(mBits);
710  Index32 i=0;
711  while(!mBits[i]) if (++i == mIntSize) return mBitSize;//reached end
712  return 32*i + FindLowestOn(mBits[i]);
713  }
714 
716  assert(mBits);
717  Index32 i=0;
718  while(!(~mBits[i])) if (++i == mIntSize) return mBitSize;//reached end
719  return 32*i + FindLowestOn(~mBits[i]);
720  }
721 
722  void save(std::ostream& os) const {
723  assert(mBits);
724  os.write((const char *)mBits,mIntSize*sizeof(Index32));
725  }
726  void load(std::istream& is) {
727  assert(mBits);
728  is.read((char *)mBits,mIntSize*sizeof(Index32));
729  }
731  void printInfo(std::ostream& os=std::cout) const {
732  os << "RootNodeMask: Bit-size="<<mBitSize<<" Int-size="<<mIntSize<<std::endl;
733  }
734 
735  void printBits(std::ostream& os=std::cout, Index32 max_out=80u) const {
736  const Index32 n=(mBitSize>max_out?max_out:mBitSize);
737  for (Index32 i=0; i < n; ++i) {
738  if ( !(i&31) )
739  os << "||";
740  else if ( !(i%8) )
741  os << "|";
742  os << this->isOn(i);
743  }
744  os << "|" << std::endl;
745  }
746 
747  void printAll(std::ostream& os=std::cout, Index32 max_out=80u) const {
748  this->printInfo(os);
749  this->printBits(os,max_out);
750  }
751 
752  Index32 findNextOn(Index32 start) const {
753  assert(mBits);
754  Index32 n = start >> 5, m = start & 31;//initiate
755  if (n>=mIntSize) return mBitSize; // check for out of bounds
756  Index32 b = mBits[n];
757  if (b & (1<<m)) return start;//simple case
758  b &= 0xFFFFFFFF << m;// mask lower bits
759  while(!b && ++n<mIntSize) b = mBits[n];// find next nonzero int
760  return (!b ? mBitSize : 32*n + FindLowestOn(b));//catch last-int=0
761  }
762 
763  Index32 findNextOff(Index32 start) const {
764  assert(mBits);
765  Index32 n = start >> 5, m = start & 31;//initiate
766  if (n>=mIntSize) return mBitSize; // check for out of bounds
767  Index32 b = ~mBits[n];
768  if (b & (1<<m)) return start;//simple case
769  b &= 0xFFFFFFFF<<m;// mask lower bits
770  while(!b && ++n<mIntSize) b = ~mBits[n];// find next nonzero int
771  return (!b ? mBitSize : 32*n + FindLowestOn(b));//catch last-int=0
772  }
773 
774  Index32 memUsage() const {
775  assert(mBits);
776  return sizeof(Index32*)+(2+mIntSize)*sizeof(Index32);//in bytes
777  }
778 }; // class RootNodeMask
779 
780 } // namespace util
781 } // namespace OPENVDB_VERSION_NAME
782 } // namespace openvdb
783 
784 #endif // OPENVDB_UTIL_NODEMASK_HAS_BEEN_INCLUDED
785 
786 // Copyright (c) 2012 DreamWorks Animation LLC
787 // All rights reserved. This software is distributed under the
788 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )