Field3D
SparseField.h
Go to the documentation of this file.
1 //----------------------------------------------------------------------------//
2 
3 /*
4  * Copyright (c) 2009 Sony Pictures Imageworks Inc
5  *
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  * Redistributions in binary form must reproduce the above copyright
15  * notice, this list of conditions and the following disclaimer in the
16  * documentation and/or other materials provided with the
17  * distribution. Neither the name of Sony Pictures Imageworks nor the
18  * names of its contributors may be used to endorse or promote
19  * products derived from this software without specific prior written
20  * permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
25  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
28  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
29  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
31  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
32  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
33  * OF THE POSSIBILITY OF SUCH DAMAGE.
34  */
35 
36 //----------------------------------------------------------------------------//
37 
42 //----------------------------------------------------------------------------//
43 
44 #ifndef _INCLUDED_Field3D_SparseField_H_
45 #define _INCLUDED_Field3D_SparseField_H_
46 
47 //----------------------------------------------------------------------------//
48 
49 #include <vector>
50 
51 #include <boost/thread/mutex.hpp>
52 #include <boost/lexical_cast.hpp>
53 
54 #include "Field.h"
55 #include "SparseFile.h"
56 
57 #define BLOCK_ORDER 4 // 2^BLOCK_ORDER is the block size along each axis
58 
59 //----------------------------------------------------------------------------//
60 
61 #include "ns.h"
62 
64 
65 //----------------------------------------------------------------------------//
66 // Forward declarations
67 //----------------------------------------------------------------------------//
68 
69 template <class Field_T>
71 template <class Field_T>
73 
74 //----------------------------------------------------------------------------//
75 // LinearSparseFieldInterp
76 //----------------------------------------------------------------------------//
77 
78 /* \class LinearSparseFieldInterp
79  \ingroup field
80  \brief Linear interpolator optimized for fields with a fastValue function
81 */
82 
83 //----------------------------------------------------------------------------//
84 
85 template <typename Data_T>
87 {
88 public:
89 
90  // Typedefs ------------------------------------------------------------------
91 
92  typedef Data_T value_type;
93  typedef boost::intrusive_ptr<LinearSparseFieldInterp> Ptr;
94 
95  // RTTI replacement ----------------------------------------------------------
96 
99 
100  static const char *staticClassName()
101  {
102  return "LinearSparseFieldInterp";
103  }
104 
105  static const char* staticClassType()
106  {
107  return ms_classType.name();
108  }
109 
110  // Main methods --------------------------------------------------------------
111 
112  value_type sample(const SparseField<Data_T> &field, const V3d &vsP) const
113  {
114  // Pixel centers are at .5 coordinates
115  // NOTE: Don't use contToDisc for this, we're looking for sample
116  // point locations, not coordinate shifts.
117  FIELD3D_VEC3_T<double> p(vsP - FIELD3D_VEC3_T<double>(0.5));
118 
119  // Lower left corner
120  V3i c1(static_cast<int>(floor(p.x)),
121  static_cast<int>(floor(p.y)),
122  static_cast<int>(floor(p.z)));
123  // Upper right corner
124  V3i c2(c1 + V3i(1));
125  // C1 fractions
126  FIELD3D_VEC3_T<double> f1(static_cast<FIELD3D_VEC3_T<double> >(c2) - p);
127  // C2 fraction
128  FIELD3D_VEC3_T<double> f2(static_cast<FIELD3D_VEC3_T<double> >(1.0) - f1);
129 
130  const Box3i &dataWindow = field.dataWindow();
131 
132  // Clamp the coordinates
133  c1.x = std::min(dataWindow.max.x, std::max(dataWindow.min.x, c1.x));
134  c1.y = std::min(dataWindow.max.y, std::max(dataWindow.min.y, c1.y));
135  c1.z = std::min(dataWindow.max.z, std::max(dataWindow.min.z, c1.z));
136  c2.x = std::min(dataWindow.max.x, std::max(dataWindow.min.x, c2.x));
137  c2.y = std::min(dataWindow.max.y, std::max(dataWindow.min.y, c2.y));
138  c2.z = std::min(dataWindow.max.z, std::max(dataWindow.min.z, c2.z));
139 
140  // Determine which block we're in
141  int i = c1.x, j = c1.y, k = c1.z, vi, vj, vk, bi, bj, bk;
142  field.applyDataWindowOffset(i, j, k);
143  field.getVoxelInBlock(i, j, k, vi, vj, vk);
144  field.getBlockCoord(i, j, k, bi, bj, bk);
145  int blockSize = 1 << field.blockOrder();
146 
147  // If in the middle of a block, optimize lookup stencil
148  if (vi < blockSize - 1 && vj < blockSize - 1 && vk < blockSize - 1) {
149  if (field.blockIsAllocated(bi, bj, bk)) {
150  // Ensure block data is active and kept alive
151  const int blockId = field.blockId(bi, bj, bk);
152  const bool isDynamicLoad = field.isDynamicLoad();
153  if (isDynamicLoad) {
154  field.incBlockRef(blockId);
155  field.activateBlock(blockId);
156  }
157  // Only do work if the block is allocated
158  const Data_T * const p = field.blockData(bi, bj, bk);
159  const Data_T * const c111 =
160  p + vi + vj * blockSize + vk * blockSize * blockSize;
161  const Data_T * const c121 = c111 + blockSize * (c2.y - c1.y);
162  const Data_T * const
163  c112 = c111 + blockSize * blockSize * (c2.z - c1.z);
164  const Data_T * const c122 = c112 + blockSize * (c2.y - c1.y);
165  int xInc = c2.x - c1.x;
166  Data_T value = static_cast<Data_T>
167  (f1.x * (f1.y * (f1.z * *c111 +
168  f2.z * *c112) +
169  f2.y * (f1.z * *c121 +
170  f2.z * *c122)) +
171  f2.x * (f1.y * (f1.z * *(c111 + xInc) +
172  f2.z * *(c112 + xInc)) +
173  f2.y * (f1.z * *(c121 + xInc) +
174  f2.z * *(c122 + xInc))));
175  // Decrement the block ref count
176  if (isDynamicLoad) {
177  field.decBlockRef(blockId);
178  }
179  // Done.
180  return value;
181  } else {
182  return static_cast<Data_T>(field.getBlockEmptyValue(bi, bj, bk));
183  }
184  } else {
185  return static_cast<Data_T>
186  (f1.x * (f1.y * (f1.z * field.fastValue(c1.x, c1.y, c1.z) +
187  f2.z * field.fastValue(c1.x, c1.y, c2.z)) +
188  f2.y * (f1.z * field.fastValue(c1.x, c2.y, c1.z) +
189  f2.z * field.fastValue(c1.x, c2.y, c2.z))) +
190  f2.x * (f1.y * (f1.z * field.fastValue(c2.x, c1.y, c1.z) +
191  f2.z * field.fastValue(c2.x, c1.y, c2.z)) +
192  f2.y * (f1.z * field.fastValue(c2.x, c2.y, c1.z) +
193  f2.z * field.fastValue(c2.x, c2.y, c2.z))));
194  }
195 
196  }
197 
198 private:
199 
200  // Static data members -------------------------------------------------------
201 
203 
204  // Typedefs ------------------------------------------------------------------
205 
207  typedef RefBase base;
208 
209 };
210 
211 //----------------------------------------------------------------------------//
212 
214 
215 //----------------------------------------------------------------------------//
216 // SparseBlock
217 //----------------------------------------------------------------------------//
218 
221 namespace Sparse {
222 
226 template <typename Data_T>
227 struct SparseBlock : boost::noncopyable
228 {
229  // Constructors --------------------------------------------------------------
230 
233  : isAllocated(false),
234  emptyValue(static_cast<Data_T>(0)),
235  data(NULL)
236  { /* Empty */ }
237 
240  {
241  if (data) {
242  delete[] data;
243  }
244  }
245 
246  // Main methods --------------------------------------------------------------
247 
249  inline Data_T& value(int i, int j, int k, int blockOrder)
251  { return data[(k << blockOrder << blockOrder) + (j << blockOrder) + i]; }
252 
255  inline const Data_T& value(int i, int j, int k, int blockOrder) const
256  { return data[(k << blockOrder << blockOrder) + (j << blockOrder) + i]; }
257 
259  void resize(int n)
260  {
261  // First hold lock
262  boost::mutex::scoped_lock lock(ms_resizeMutex);
263  // Perform work
264  if (data) {
265  delete[] data;
266  }
267  data = new Data_T[n];
268  isAllocated = true;
269  std::fill_n(data, n, emptyValue);
270  }
271 
273  void clear()
274  {
275  // First hold lock
276  boost::mutex::scoped_lock lock(ms_resizeMutex);
277  // Perform work
278  if (data) {
279  delete[] data;
280  data = NULL;
281  }
282  }
283 
285  void copy(const SparseBlock &other, size_t n)
286  {
287  if (other.isAllocated) {
288  if (!data) {
289  resize(n);
290  }
291  Data_T *p = data, *end = data + n, *o = other.data;
292  while (p != end) {
293  *p++ = *o++;
294  }
295  } else {
296  clear();
297  }
298  }
299 
300  // Data members --------------------------------------------------------------
301 
304 
308  Data_T emptyValue;
309 
311  Data_T *data;
312 
313 private:
314 
316  SparseBlock(const SparseBlock&);
318  const SparseBlock& operator=(const SparseBlock&);
319 
320  // Data members --------------------------------------------------------------
321 
325  static boost::mutex ms_resizeMutex;
326 
327 };
328 
329 } // namespace Sparse
330 
331 //----------------------------------------------------------------------------//
332 // SparseField
333 //----------------------------------------------------------------------------//
334 
347 //----------------------------------------------------------------------------//
348 
349 template <class Data_T>
351  : public ResizableField<Data_T>
352 {
353 public:
354 
355  // Typedefs ------------------------------------------------------------------
356 
357  typedef boost::intrusive_ptr<SparseField> Ptr;
358  typedef std::vector<Ptr> Vec;
359 
362 
363  // RTTI replacement ----------------------------------------------------------
364 
367 
368  static const char *staticClassName()
369  {
370  return "SparseField";
371  }
372 
373  static const char *staticClassType()
374  {
376  }
377 
378  // Constructors --------------------------------------------------------------
379 
382 
384  SparseField();
385 
387  SparseField(const SparseField &o);
388 
390  ~SparseField();
391 
394  SparseField& operator=(const SparseField &o);
395 
396  // \}
397 
398  // Main methods --------------------------------------------------------------
399 
401  virtual void clear(const Data_T &value);
402 
405  void setBlockOrder(int order);
406 
408  int blockOrder() const;
409 
411  int blockSize() const;
412 
414  bool voxelIsInAllocatedBlock(int i, int j, int k) const;
415 
417  bool blockIsAllocated(int bi, int bj, int bk) const;
418 
421  const Data_T getBlockEmptyValue(int bi, int bj, int bk) const;
422 
425  void setBlockEmptyValue(int bi, int bj, int bk, const Data_T &val);
426 
428  bool blockIndexIsValid(int bi, int bj, int bk) const;
429 
431  V3i blockRes() const;
432 
438  template <typename Functor_T>
439  int releaseBlocks(Functor_T func);
440 
442  int blockId(int blockI, int blockJ, int blockK) const;
443 
447  void getBlockCoord(int i, int j, int k, int &bi, int &bj, int &bk) const;
448 
452  void getVoxelInBlock(int i, int j, int k, int &vi, int &vj, int &vk) const;
453 
455  void applyDataWindowOffset(int &i, int &j, int &k) const
456  {
457  i -= base::m_dataWindow.min.x;
458  j -= base::m_dataWindow.min.y;
459  k -= base::m_dataWindow.min.z;
460  }
461 
463  bool isDynamicLoad() const
464  { return m_fileManager != NULL; }
465 
467  void incBlockRef(const int blockId) const;
468 
470  void activateBlock(const int blockId) const;
471 
473  void decBlockRef(const int blockId) const;
474 
475  // Threading-related ---------------------------------------------------------
476 
478  size_t numGrains() const;
481  bool getGrainBounds(const size_t idx, Box3i &vsBounds) const;
482 
483  // From Field base class -----------------------------------------------------
484 
487  virtual Data_T value(int i, int j, int k) const;
488  virtual long long int memSize() const;
489  virtual size_t voxelCount() const;
491 
492  // From WritableField base class ---------------------------------------------
493 
496  virtual Data_T& lvalue(int i, int j, int k);
498 
499  // Concrete voxel access -----------------------------------------------------
500 
502  Data_T fastValue(int i, int j, int k) const;
504  Data_T& fastLValue(int i, int j, int k);
505 
508  Data_T* blockData(int bi, int bj, int bk) const;
509 
510  // From FieldBase ------------------------------------------------------------
511 
514 
516 
517  virtual FieldBase::Ptr clone() const
518  { return Ptr(new SparseField(*this)); }
519 
521 
522  // Iterators -----------------------------------------------------------------
523 
526 
528  class const_iterator;
529 
531  const_iterator cbegin() const;
533  const_iterator cbegin(const Box3i &subset) const;
535  const_iterator cend() const;
538  const_iterator cend(const Box3i &subset) const;
539 
543  class iterator;
544 
546  iterator begin();
548  iterator begin(const Box3i &subset);
550  iterator end();
553  iterator end(const Box3i &subset);
554 
558  class block_iterator;
559 
560  block_iterator blockBegin() const;
562  block_iterator blockEnd() const;
563 
565 
566  // Internal utility functions ------------------------------------------------
567 
570  void addReference(const std::string &filename, const std::string &layerPath,
571  int valuesPerBlock, int occupiedBlocks);
574  void setupReferenceBlocks();
575 
576  protected:
577 
578  friend class SparseFieldIO;
579 
580  // Typedefs ------------------------------------------------------------------
581 
584 
585  // From ResizableField class -------------------------------------------------
586 
587  virtual void sizeChanged()
588  {
589  // Call base class
590  base::sizeChanged();
591  setupBlocks();
592  }
593 
594  // Convenience methods -------------------------------------------------------
595 
598 
600  void setupBlocks();
601 
603  void deallocBlock(Block &block, const Data_T &emptyValue);
604 
606 
607  // Data members --------------------------------------------------------------
608 
616  Block *m_blocks;
618  size_t m_numBlocks;
619 
624  int m_fileId;
625 
627  Data_T m_dummy;
628 
629 private:
630 
631  // Static data members -------------------------------------------------------
632 
634 
635  // Utility methods -----------------------------------------------------------
636 
639  void copySparseField(const SparseField &o);
640 
643  void copyBlockStates(const SparseField<Data_T> &o);
644 
645 };
646 
647 //----------------------------------------------------------------------------//
648 // Static member instantiations
649 //----------------------------------------------------------------------------//
650 
652 
653 namespace Sparse {
654 
655 template <typename Data_T>
656 boost::mutex SparseBlock<Data_T>::ms_resizeMutex;
657 
658 }
659 
660 //----------------------------------------------------------------------------//
661 // Typedefs
662 //----------------------------------------------------------------------------//
663 
670 
671 //------------------------------------------------------------------------------
672 // Helper functions
673 //------------------------------------------------------------------------------
674 
675 template <typename Data_T>
676 Box3i blockCoords(const Box3i &dvsBounds, const SparseField<Data_T> *f)
677 {
678  Box3i dbsBounds;
679  if (f) {
680  f->getBlockCoord(dvsBounds.min.x, dvsBounds.min.y, dvsBounds.min.z,
681  dbsBounds.min.x, dbsBounds.min.y, dbsBounds.min.z);
682  f->getBlockCoord(dvsBounds.max.x, dvsBounds.max.y, dvsBounds.max.z,
683  dbsBounds.max.x, dbsBounds.max.y, dbsBounds.max.z);
684  }
685  return dbsBounds;
686 }
687 
688 //----------------------------------------------------------------------------//
689 // Helper functors
690 //----------------------------------------------------------------------------//
691 
692 namespace Sparse {
693 
696 template <typename Data_T>
698 {
707  bool check(const SparseBlock<Data_T> &block, Data_T &retEmptyValue,
708  const V3i &validSize, const V3i &blockSize)
709  {
710  // Store first value
711  Data_T first = block.data[0];
712  // Iterate over rest
713  bool match = true;
714  size_t len = blockSize.x * blockSize.y * blockSize.z;
715  if (validSize == blockSize) {
716  // interior block so look at all voxels
717  for (size_t i = 0; i < len; i++) {
718  if (block.data[i] != first) {
719  match = false;
720  break;
721  }
722  }
723  } else {
724  // only look at valid voxels
725  int x=0, y=0, z=0;
726  for (size_t i = 0; i < len; i++, x++) {
727  if (x >= blockSize.x) {
728  x = 0;
729  ++y;
730  if (y >= blockSize.y) {
731  y = 0;
732  ++z;
733  }
734  }
735  if (x >= validSize.x || y >= validSize.y || z >= validSize.z) {
736  continue;
737  }
738  if (block.data[i] != first) {
739  match = false;
740  break;
741  }
742  }
743  } // end of interior block test
744 
745  if (match) {
746  retEmptyValue = first;
747  return true;
748  } else {
749  return false;
750  }
751  }
752 };
753 
754 //----------------------------------------------------------------------------//
755 
756 template <typename Data_T>
757 inline bool isAnyLess(const Data_T &left, const Data_T &right)
758 {
759  return (std::abs(left) < right);
760 }
761 
762 //----------------------------------------------------------------------------//
763 
764 template <>
765 inline bool isAnyLess(const V3h &left, const V3h &right)
766 {
767  return (std::abs(left.x) < right.x ||
768  std::abs(left.y) < right.y ||
769  std::abs(left.z) < right.z );
770 }
771 
772 //----------------------------------------------------------------------------//
773 
774 template <>
775 inline bool isAnyLess(const V3f &left, const V3f &right)
776 {
777  return (std::abs(left.x) < right.x ||
778  std::abs(left.y) < right.y ||
779  std::abs(left.z) < right.z );
780 }
781 
782 //----------------------------------------------------------------------------//
783 
784 template <>
785 inline bool isAnyLess(const V3d &left, const V3d &right)
786 {
787  return (std::abs(left.x) < right.x ||
788  std::abs(left.y) < right.y ||
789  std::abs(left.z) < right.z );
790 }
791 
792 //----------------------------------------------------------------------------//
793 
797 template <typename Data_T>
799 {
801  CheckMaxAbs(Data_T maxValue)
802  : m_maxValue(maxValue)
803  { }
812  bool check(const SparseBlock<Data_T> &block, Data_T &retEmptyValue,
813  const V3i &validSize, const V3i &blockSize)
814  {
815  // Store first value
816  Data_T first = block.data[0];
817  // Iterate over rest
818  bool allGreater = true;
819  size_t len = blockSize.x * blockSize.y * blockSize.z;
820 
821  if (validSize == blockSize) {
822  // interior block so look at all voxels
823  for (size_t i = 0; i < len; i++) {
824  if (isAnyLess<Data_T>(block.data[i], m_maxValue)) {
825  allGreater = false;
826  break;
827  }
828  }
829  } else {
830  // only look at valid voxels
831  int x=0, y=0, z=0;
832  for (size_t i = 0; i < len; i++, x++) {
833  if (x >= blockSize.x) {
834  x = 0;
835  ++y;
836  if (y >= blockSize.y) {
837  y = 0;
838  ++z;
839  }
840  }
841  if (x >= validSize.x || y >= validSize.y || z >= validSize.z) {
842  continue;
843  }
844  if (isAnyLess<Data_T>(block.data[i], m_maxValue)) {
845  allGreater = false;
846  break;
847  }
848  }
849  } // end of interior block test
850 
851  if (allGreater) {
852  retEmptyValue = first;
853  return true;
854  } else {
855  return false;
856  }
857  }
858 private:
859  Data_T m_maxValue;
860 };
861 
862 //----------------------------------------------------------------------------//
863 
864 } // namespace Sparse
865 
866 //----------------------------------------------------------------------------//
867 // SparseField::const_iterator
868 //----------------------------------------------------------------------------//
869 
871 template <class Data_T>
873 {
874  public:
875 #if defined(WIN32) || __MAC_OS_X_VERSION_MIN_REQUIRED >= 1090
876  typedef std::forward_iterator_tag iterator_category;
877  typedef Data_T value_type;
878  typedef ptrdiff_t difference_type;
879  typedef ptrdiff_t distance_type;
880  typedef Data_T *pointer;
881  typedef Data_T& reference;
882 #endif
883 
885  const_iterator(const class_type &field,
886  const Box3i &window,
887  const V3i &currentPos, int blockOrder)
888  : x(currentPos.x), y(currentPos.y), z(currentPos.z),
889  m_p(NULL), m_blockIsActivated(false),
890  m_blockStepsTicker(0), m_blockOrder(blockOrder),
891  m_blockId(-1), m_window(window), m_field(&field)
892  {
893  m_manager = m_field->m_fileManager;
894  setupNextBlock(x, y, z);
895  }
897  if (m_manager && m_blockId >= 0 &&
898  m_blockId < static_cast<int>(m_field->m_numBlocks)) {
899  if (m_field->m_blocks[m_blockId].isAllocated)
900  m_manager->decBlockRef<Data_T>(m_field->m_fileId, m_blockId);
901  }
902  }
903  const const_iterator& operator ++ ()
904  {
905  bool resetPtr = false;
906  // Check against end of data window
907  if (x == m_window.max.x) {
908  if (y == m_window.max.y) {
909  x = m_window.min.x;
910  y = m_window.min.y;
911  ++z;
912  resetPtr = true;
913  } else {
914  x = m_window.min.x;
915  ++y;
916  resetPtr = true;
917  }
918  } else {
919  ++x;
920  }
921  // These can both safely be incremented here
922  ++m_blockStepsTicker;
923  // ... but only step forward if we're in a non-empty block
924  if (!m_isEmptyBlock && (!m_manager || m_blockIsActivated))
925  ++m_p;
926  // Check if we've reached the end of this block
927  if (m_blockStepsTicker == (1 << m_blockOrder))
928  resetPtr = true;
929  if (resetPtr) {
930  // If we have, we need to reset the current block, etc.
931  m_blockStepsTicker = 0;
932  setupNextBlock(x, y, z);
933  }
934  return *this;
935  }
936  template <class Iter_T>
937  inline bool operator == (const Iter_T &rhs) const
938  {
939  return x == rhs.x && y == rhs.y && z == rhs.z;
940  }
941  template <class Iter_T>
942  inline bool operator != (const Iter_T &rhs) const
943  {
944  return x != rhs.x || y != rhs.y || z != rhs.z;
945  }
946  inline const Data_T& operator * () const
947  {
948  if (!m_isEmptyBlock && m_manager && !m_blockIsActivated) {
949  m_manager->activateBlock<Data_T>(m_field->m_fileId, m_blockId);
950  m_blockIsActivated = true;
951  const Block &block = m_field->m_blocks[m_blockId];
952  int vi, vj, vk;
953  m_field->getVoxelInBlock(x, y, z, vi, vj, vk);
954  m_p = &block.value(vi, vj, vk, m_blockOrder);
955  }
956  return *m_p;
957  }
958  inline const Data_T* operator -> () const
959  {
960  if (!m_isEmptyBlock && m_manager && !m_blockIsActivated) {
961  SparseFileManager *manager = m_field->m_fileManager;
962  manager->activateBlock<Data_T>(m_field->m_fileId, m_blockId);
963  m_blockIsActivated = true;
964  const Block &block = m_field->m_blocks[m_blockId];
965  int vi, vj, vk;
966  m_field->getVoxelInBlock(x, y, z, vi, vj, vk);
967  m_p = &block.value(vi, vj, vk, m_blockOrder);
968  }
969  return m_p;
970  }
971 
972  // Public data members -------------------------------------------------------
973 
975  int x, y, z;
976 
977 private:
978 
979  // Typedefs ------------------------------------------------------------------
980 
982 
983  // Convenience methods -------------------------------------------------------
984 
985  void setupNextBlock(int i, int j, int k)
986  {
987  m_field->applyDataWindowOffset(i, j, k);
988  m_field->getBlockCoord(i, j, k, m_blockI, m_blockJ, m_blockK);
989  int oldBlockId = m_blockId;
990  m_blockId = m_field->blockId(m_blockI, m_blockJ, m_blockK);
991  if (m_manager && oldBlockId != m_blockId &&
992  oldBlockId >= 0 &&
993  oldBlockId < static_cast<int>(m_field->m_numBlocks) &&
994  m_field->m_blocks[oldBlockId].isAllocated) {
995  m_manager->decBlockRef<Data_T>(m_field->m_fileId, oldBlockId);
996  }
997  if (m_blockId >= m_field->m_blockXYSize * m_field->m_blockRes.z) {
998  m_isEmptyBlock = true;
999  return;
1000  }
1001 
1002  const Block &block = m_field->m_blocks[m_blockId];
1003  int vi, vj, vk;
1004  m_field->getVoxelInBlock(i, j, k, vi, vj, vk);
1005  m_blockStepsTicker = vi;
1006  if (block.isAllocated) {
1007  if (m_manager && oldBlockId != m_blockId && m_blockId >= 0) {
1008  m_manager->incBlockRef<Data_T>(m_field->m_fileId, m_blockId);
1009  // this is a managed field, so the block may not be loaded
1010  // yet, so don't bother setting m_p yet (it'll get set in the
1011  // * and -> operators when the block is activated)
1012  } else {
1013  // only set m_p to the voxel's address if this is not a
1014  // managed field, i.e., if the data is already in memory.
1015  m_p = &block.value(vi, vj, vk, m_blockOrder);
1016  }
1017  m_isEmptyBlock = false;
1018  } else {
1019  m_p = &block.emptyValue;
1020  m_isEmptyBlock = true;
1021  }
1022  if (m_field->m_fileManager) {
1023  m_blockIsActivated = false;
1024  }
1025  }
1026 
1028  mutable const Data_T *m_p;
1033  mutable bool m_blockIsActivated;
1039  int m_blockI, m_blockJ, m_blockK, m_blockId;
1043  const class_type *m_field;
1046 };
1047 
1048 //----------------------------------------------------------------------------//
1049 // SparseField::iterator
1050 //----------------------------------------------------------------------------/
1051 
1053 template <class Data_T>
1054 class SparseField<Data_T>::iterator
1055 {
1056  public:
1057 #if defined(WIN32) || __MAC_OS_X_VERSION_MIN_REQUIRED >= 1090
1058  typedef std::forward_iterator_tag iterator_category;
1059  typedef Data_T value_type;
1060  typedef ptrdiff_t difference_type;
1061  typedef ptrdiff_t distance_type;
1062  typedef Data_T *pointer;
1063  typedef Data_T& reference;
1064 #endif
1065 
1067  iterator(class_type &field,
1068  const Box3i &window,
1069  const V3i &currentPos, int blockOrder)
1070  : x(currentPos.x), y(currentPos.y), z(currentPos.z),
1071  m_p(NULL), m_blockStepsTicker(0), m_blockOrder(blockOrder),
1072  m_blockId(-1), m_window(window), m_field(&field)
1073  {
1074  setupNextBlock(x, y, z);
1075  }
1076  const iterator& operator ++ ()
1077  {
1078  bool resetPtr = false;
1079  // Check against end of data window
1080  if (x == m_window.max.x) {
1081  if (y == m_window.max.y) {
1082  x = m_window.min.x;
1083  y = m_window.min.y;
1084  ++z;
1085  resetPtr = true;
1086  } else {
1087  x = m_window.min.x;
1088  ++y;
1089  resetPtr = true;
1090  }
1091  } else {
1092  ++x;
1093  }
1094  // These can both safely be incremented here
1095  ++m_blockStepsTicker;
1096  // ... but only step forward if we're in a non-empty block
1097  if (!m_isEmptyBlock)
1098  ++m_p;
1099  // Check if we've reached the end of this block
1100  if (m_blockStepsTicker == (1 << m_blockOrder))
1101  resetPtr = true;
1102  if (resetPtr) {
1103  // If we have, we need to reset the current block, etc.
1104  m_blockStepsTicker = 0;
1105  setupNextBlock(x, y, z);
1106  }
1107  return *this;
1108  }
1109  inline bool operator == (const iterator &rhs) const
1110  {
1111  return x == rhs.x && y == rhs.y && z == rhs.z;
1112  }
1113  inline bool operator != (const iterator &rhs) const
1114  {
1115  return x != rhs.x || y != rhs.y || z != rhs.z;
1116  }
1117  inline Data_T& operator * ()
1118  {
1119  if (m_field->m_fileManager) {
1120  assert(false && "Dereferencing iterator on a dynamic-read sparse field");
1121  Msg::print(Msg::SevWarning, "Dereferencing iterator on a dynamic-read "
1122  "sparse field");
1123  return *m_p;
1124  }
1125  // If the block is currently empty, we must allocate it
1126  if (m_isEmptyBlock) {
1127  // Touch the voxel to allocate the block
1128  m_field->lvalue(x, y, z);
1129  // Set up the block again
1130  setupNextBlock(x, y, z);
1131  }
1132  return *m_p;
1133  }
1134  inline Data_T* operator -> ()
1135  {
1136  if (m_field->m_fileManager) {
1137  assert(false && "Dereferencing iterator on a dynamic-read sparse field");
1138  Msg::print(Msg::SevWarning, "Dereferencing iterator on a dynamic-read "
1139  "sparse field");
1140  return m_p;
1141  }
1142  // If the block is currently empty, we must allocate it
1143  if (m_isEmptyBlock) {
1144  // Touch the voxel to allocate the block
1145  m_field->lvalue(x, y, z);
1146  // Set up the block again
1147  setupNextBlock(x, y, z);
1148  }
1149  return m_p;
1150  }
1151  // Public data members
1152  int x, y, z;
1153 private:
1156  void setupNextBlock(int i, int j, int k)
1157  {
1158  m_field->applyDataWindowOffset(i, j, k);
1159  m_field->getBlockCoord(i, j, k, m_blockI, m_blockJ, m_blockK);
1160  m_blockId = m_field->blockId(m_blockI, m_blockJ, m_blockK);
1161  if (m_blockId >= m_field->m_blockXYSize * m_field->m_blockRes.z) {
1162  m_isEmptyBlock = true;
1163  return;
1164  }
1165  Block &block = m_field->m_blocks[m_blockId];
1166  int vi, vj, vk;
1167  m_field->getVoxelInBlock(i, j, k, vi, vj, vk);
1168  m_blockStepsTicker = vi;
1169  if (block.isAllocated) {
1170  m_p = &block.value(vi, vj, vk, m_blockOrder);
1171  m_isEmptyBlock = false;
1172  } else {
1173  m_p = &block.emptyValue;
1174  m_isEmptyBlock = true;
1175  }
1176  }
1178  Data_T *m_p;
1186  int m_blockI, m_blockJ, m_blockK, m_blockId;
1190  class_type *m_field;
1191 };
1192 
1193 //----------------------------------------------------------------------------//
1194 // SparseField::block_iterator
1195 //----------------------------------------------------------------------------/
1196 
1199 template <class Data_T>
1201 {
1202  public:
1206  block_iterator(const class_type &field, const Box3i &window,
1207  const V3i &currentPos)
1208  : x(currentPos.x), y(currentPos.y), z(currentPos.z),
1209  m_window(window), m_field(field)
1210  {
1211  recomputeBlockBoundingBox();
1212  }
1214  const block_iterator& operator ++ ()
1215  {
1216  if (x == m_window.max.x) {
1217  if (y == m_window.max.y) {
1218  x = m_window.min.x;
1219  y = m_window.min.y;
1220  ++z;
1221  } else {
1222  x = m_window.min.x;
1223  ++y;
1224  }
1225  } else {
1226  ++x;
1227  }
1228  recomputeBlockBoundingBox();
1229  return *this;
1230  }
1232  inline bool operator == (const block_iterator &rhs) const
1233  {
1234  return x == rhs.x && y == rhs.y && z == rhs.z;
1235  }
1237  inline bool operator != (const block_iterator &rhs) const
1238  {
1239  return x != rhs.x || y != rhs.y || z != rhs.z;
1240  }
1243  {
1244  return m_currentBlockWindow;
1245  }
1247  int x, y, z;
1248 private:
1250  {
1251  Box3i box;
1252  int blockSize = m_field.blockSize();
1253  box.min = V3i(x * blockSize, y * blockSize, z * blockSize);
1254  box.max = box.min + V3i(blockSize - 1, blockSize - 1, blockSize - 1);
1255  // Clamp the box
1256  box.min = FIELD3D_CLIP(box.min, m_field.dataWindow());
1257  box.max = FIELD3D_CLIP(box.max, m_field.dataWindow());
1258  // Set the member variable
1259  m_currentBlockWindow = box;
1260  }
1264  const class_type& m_field;
1267 };
1268 
1269 //----------------------------------------------------------------------------//
1270 // SparseField implementations
1271 //----------------------------------------------------------------------------//
1272 
1273 template <class Data_T>
1275  : base(),
1276  m_blockOrder(BLOCK_ORDER),
1277  m_blocks(NULL),
1278  m_fileManager(NULL)
1279 {
1280  setupBlocks();
1281 }
1282 
1283 //----------------------------------------------------------------------------//
1284 
1285 template <class Data_T>
1287  : base(o),
1289  m_blocks(NULL),
1291 {
1292  copySparseField(o);
1293 }
1294 
1295 //----------------------------------------------------------------------------//
1296 
1297 template <class Data_T>
1299 {
1300  if (m_fileManager) {
1301  // this file is dynamically managed, so we need to ensure the
1302  // cache doesn't point to this field's blocks because they are
1303  // about to be deleted
1305  }
1306  if (m_blocks) {
1307  delete[] m_blocks;
1308  }
1309 }
1310 
1311 //----------------------------------------------------------------------------//
1312 
1313 template <class Data_T>
1316 {
1317  if (this != &o) {
1318  this->base::operator=(o);
1319  copySparseField(o);
1320  }
1321  return *this;
1322 }
1323 
1324 //----------------------------------------------------------------------------//
1325 
1326 template <class Data_T>
1327 void
1329 {
1331  if (o.m_fileManager) {
1332  // allocate m_blocks, sets m_blockRes, m_blockXYSize, m_blocks
1333  setupBlocks();
1335  SparseFile::Reference<Data_T> *oldReference =
1336  m_fileManager->reference<Data_T>(o.m_fileId);
1337  addReference(oldReference->filename, oldReference->layerPath,
1338  oldReference->valuesPerBlock,
1339  oldReference->occupiedBlocks);
1340  copyBlockStates(o);
1342  } else {
1343  // directly copy all values and blocks from the source, no extra setup
1344  m_blockRes = o.m_blockRes;
1346  if (m_blocks) {
1347  delete[] m_blocks;
1348  }
1350  m_blocks = new Block[m_numBlocks];
1351  for (size_t i = 0; i < m_numBlocks; ++i) {
1354  m_blocks[i].copy(o.m_blocks[i],
1356  }
1357  m_fileId = -1;
1358  m_fileManager = NULL;
1359  }
1360 }
1361 
1362 //----------------------------------------------------------------------------//
1363 
1364 template <class Data_T>
1365 void SparseField<Data_T>::addReference(const std::string &filename,
1366  const std::string &layerPath,
1367  int valuesPerBlock,
1368  int occupiedBlocks)
1369 {
1371  m_fileId = m_fileManager->getNextId<Data_T>(filename, layerPath);
1372  // Set up the manager data
1373  SparseFile::Reference<Data_T> *reference =
1374  m_fileManager->reference<Data_T>(m_fileId);
1375  reference->valuesPerBlock = valuesPerBlock;
1376  reference->occupiedBlocks = occupiedBlocks;
1377  reference->setNumBlocks(m_numBlocks);
1378 }
1379 
1380 //----------------------------------------------------------------------------//
1381 
1382 template <class Data_T>
1384 {
1385  if (m_numBlocks != o.m_numBlocks) return;
1386 
1387  for (size_t i = 0; i < m_numBlocks; ++i) {
1390  m_blocks[i].clear();
1391  }
1392 }
1393 
1394 //----------------------------------------------------------------------------//
1395 
1396 template <class Data_T>
1398 {
1399  if (!m_fileManager || m_fileId < 0) return;
1400 
1401  SparseFile::Reference<Data_T> *reference =
1402  m_fileManager->reference<Data_T>(m_fileId);
1403 
1404  std::vector<int>::iterator fb = reference->fileBlockIndices.begin();
1406  reference->blocks.begin();
1407  int nextBlockIdx = 0;
1408  for (size_t i = 0; i < m_numBlocks; ++i, ++fb, ++bp) {
1409  if (m_blocks[i].isAllocated) {
1410  *fb = nextBlockIdx;
1411  *bp = m_blocks + i;
1412  nextBlockIdx++;
1413  } else {
1414  *fb = -1;
1415  }
1416  }
1417 }
1418 
1419 //----------------------------------------------------------------------------//
1420 
1421 template <class Data_T>
1423 {
1424  // If we're clearing, we can get rid of all current blocks
1425  setupBlocks();
1426  Block *p = m_blocks, *end = m_blocks + m_numBlocks;
1427  while (p != end) {
1428  p->emptyValue = value;
1429  ++p;
1430  }
1431 }
1432 
1433 //----------------------------------------------------------------------------//
1434 
1435 template <class Data_T>
1437 {
1438  m_blockOrder = order;
1439  setupBlocks();
1440 }
1441 
1442 //----------------------------------------------------------------------------//
1443 
1444 template <class Data_T>
1446 {
1447  return m_blockOrder;
1448 }
1449 
1450 //----------------------------------------------------------------------------//
1451 
1452 template <class Data_T>
1454 {
1455  return 1 << m_blockOrder;
1456 }
1457 
1458 //----------------------------------------------------------------------------//
1459 
1460 template <class Data_T>
1461 bool SparseField<Data_T>::voxelIsInAllocatedBlock(int i, int j, int k) const
1462 {
1463  int bi, bj, bk;
1464  applyDataWindowOffset(i, j, k);
1465  getBlockCoord(i, j, k, bi, bj, bk);
1466  return blockIsAllocated(bi, bj, bk);
1467 }
1468 
1469 //----------------------------------------------------------------------------//
1470 
1471 template <class Data_T>
1472 bool SparseField<Data_T>::blockIsAllocated(int bi, int bj, int bk) const
1473 {
1474  const Block &block = m_blocks[blockId(bi, bj, bk)];
1475  return block.isAllocated;
1476 }
1477 
1478 //----------------------------------------------------------------------------//
1479 
1480 template <class Data_T>
1481 const Data_T SparseField<Data_T>::getBlockEmptyValue(int bi, int bj, int bk) const
1482 {
1483  return m_blocks[blockId(bi, bj, bk)].emptyValue;
1484 }
1485 
1486 //----------------------------------------------------------------------------//
1487 
1488 template <class Data_T>
1489 void SparseField<Data_T>::setBlockEmptyValue(int bi, int bj, int bk,
1490  const Data_T &val)
1491 {
1492  Block &block = m_blocks[blockId(bi, bj, bk)];
1493  if (block.isAllocated) {
1494  deallocBlock(block, val);
1495  } else {
1496  block.emptyValue = val;
1497  }
1498 }
1499 
1500 //----------------------------------------------------------------------------//
1501 
1502 template <class Data_T>
1503 bool SparseField<Data_T>::blockIndexIsValid(int bi, int bj, int bk) const
1504 {
1505  return bi >= 0 && bj >= 0 && bk >= 0 &&
1506  bi < m_blockRes.x && bj < m_blockRes.y && bk < m_blockRes.z;
1507 }
1508 
1509 //----------------------------------------------------------------------------//
1510 
1511 template <class Data_T>
1513 {
1514  return m_blockRes;
1515 }
1516 
1517 //----------------------------------------------------------------------------//
1518 
1519 template <class Data_T>
1520 template <typename Functor_T>
1522 {
1523  Data_T emptyValue;
1524  int numDeallocs = 0;
1525 
1526  // If the block is on the edge of the field, it may have unused
1527  // voxels, with undefined values. We need to pass the range of
1528  // valid voxels into the check function, so it only looks at valid
1529  // voxels.
1530  V3i dataRes = FieldRes::dataResolution();
1531  V3i validSize;
1532  V3i blockAllocSize(blockSize());
1533 
1534  int bx = 0, by = 0, bz = 0;
1535  for (size_t i = 0; i < m_numBlocks; ++i, ++bx) {
1536  if (bx >= m_blockRes.x) {
1537  bx = 0;
1538  ++by;
1539  if (by >= m_blockRes.y) {
1540  by = 0;
1541  ++bz;
1542  }
1543  }
1544  validSize = blockAllocSize;
1545  if (bx == m_blockRes.x-1) {
1546  validSize.x = dataRes.x - bx * blockAllocSize.x;
1547  }
1548  if (by == m_blockRes.y-1) {
1549  validSize.y = dataRes.y - by * blockAllocSize.y;
1550  }
1551  if (bz == m_blockRes.z-1) {
1552  validSize.z = dataRes.z - bz * blockAllocSize.z;
1553  }
1554 
1555  if (m_blocks[i].isAllocated) {
1556  if (func.check(m_blocks[i], emptyValue, validSize, blockAllocSize)) {
1557  deallocBlock(m_blocks[i], emptyValue);
1558  numDeallocs++;
1559  }
1560  }
1561  }
1562  return numDeallocs;
1563 }
1564 
1565 //----------------------------------------------------------------------------//
1566 
1567 template <class Data_T>
1568 Data_T SparseField<Data_T>::value(int i, int j, int k) const
1569 {
1570  return fastValue(i, j, k);
1571 }
1572 
1573 //----------------------------------------------------------------------------//
1574 
1575 template <class Data_T>
1576 Data_T& SparseField<Data_T>::lvalue(int i, int j, int k)
1577 {
1578  return fastLValue(i, j, k);
1579 }
1580 
1581 //----------------------------------------------------------------------------//
1582 
1583 template <class Data_T>
1584 Data_T SparseField<Data_T>::fastValue(int i, int j, int k) const
1585 {
1586  assert (i >= base::m_dataWindow.min.x);
1587  assert (i <= base::m_dataWindow.max.x);
1588  assert (j >= base::m_dataWindow.min.y);
1589  assert (j <= base::m_dataWindow.max.y);
1590  assert (k >= base::m_dataWindow.min.z);
1591  assert (k <= base::m_dataWindow.max.z);
1592  // Add crop window offset
1593  applyDataWindowOffset(i, j, k);
1594  // Find block coord
1595  int bi, bj, bk;
1596  getBlockCoord(i, j, k, bi, bj, bk);
1597  // Find coord in block
1598  int vi, vj, vk;
1599  getVoxelInBlock(i, j, k, vi, vj, vk);
1600  // Get the actual block
1601  int id = blockId(bi, bj, bk);
1602  const Block &block = m_blocks[id];
1603  // Check if block data is allocated
1604  if (block.isAllocated) {
1605  if (m_fileManager) {
1606  m_fileManager->incBlockRef<Data_T>(m_fileId, id);
1607  m_fileManager->activateBlock<Data_T>(m_fileId, id);
1608  Data_T tmpValue = block.value(vi, vj, vk, m_blockOrder);
1609  m_fileManager->decBlockRef<Data_T>(m_fileId, id);
1610  return tmpValue;
1611  } else {
1612  return block.value(vi, vj, vk, m_blockOrder);
1613  }
1614  } else {
1615  return block.emptyValue;
1616  }
1617 }
1618 
1619 //----------------------------------------------------------------------------//
1620 
1622 template <class Data_T>
1623 Data_T& SparseField<Data_T>::fastLValue(int i, int j, int k)
1624 {
1625  assert (i >= base::m_dataWindow.min.x);
1626  assert (i <= base::m_dataWindow.max.x);
1627  assert (j >= base::m_dataWindow.min.y);
1628  assert (j <= base::m_dataWindow.max.y);
1629  assert (k >= base::m_dataWindow.min.z);
1630  assert (k <= base::m_dataWindow.max.z);
1631 
1632  if (m_fileManager) {
1633  assert(false && "Called fastLValue() on a dynamic-read sparse field");
1634  Msg::print(Msg::SevWarning, "Called fastLValue() on a dynamic-read "
1635  "sparse field");
1636  return m_dummy;
1637  }
1638 
1639  // Add crop window offset
1640  applyDataWindowOffset(i, j, k);
1641  // Find block coord
1642  int bi, bj, bk;
1643  getBlockCoord(i, j, k, bi, bj, bk);
1644  // Find coord in block
1645  int vi, vj, vk;
1646  getVoxelInBlock(i, j, k, vi, vj, vk);
1647  // Get the actual block
1648  int id = blockId(bi, bj, bk);
1649  Block &block = m_blocks[id];
1650  // If block is allocated, return a reference to the data
1651  if (block.isAllocated) {
1652  return block.value(vi, vj, vk, m_blockOrder);
1653  } else {
1654  // ... Otherwise, allocate block
1655  size_t blockSize = 1 << m_blockOrder << m_blockOrder << m_blockOrder;
1656  block.resize(blockSize);
1657  return block.value(vi, vj, vk, m_blockOrder);
1658  }
1659 }
1660 
1661 //----------------------------------------------------------------------------//
1662 
1663 template <class Data_T>
1664 Data_T* SparseField<Data_T>::blockData(int bi, int bj, int bk) const
1665 {
1666  int id = blockId(bi, bj, bk);
1667  const Block &block = m_blocks[id];
1668  if (block.isAllocated) {
1669  return block.data;
1670  } else {
1671  return NULL;
1672  }
1673 }
1674 
1675 //----------------------------------------------------------------------------//
1676 
1677 template <class Data_T>
1678 long long int SparseField<Data_T>::memSize() const
1679 {
1680  long long int blockSize = m_numBlocks * sizeof(Block);
1681  long long int dataSize = 0;
1682 
1683  for (size_t i = 0; i < m_numBlocks; ++i) {
1684  if (m_blocks[i].data) {
1685  dataSize += (1 << m_blockOrder << m_blockOrder << m_blockOrder) *
1686  sizeof(Data_T);
1687  }
1688  }
1689 
1690  return sizeof(*this) + dataSize + blockSize;
1691 }
1692 
1693 //----------------------------------------------------------------------------//
1694 
1695 template <class Data_T>
1697 {
1698  size_t count = 0;
1699  const size_t blockSize = (1 << m_blockOrder << m_blockOrder << m_blockOrder);
1700 
1701  for (size_t i = 0; i < m_numBlocks; ++i) {
1702  if (m_blocks[i].isAllocated) {
1703  count += blockSize;
1704  }
1705  }
1706 
1707  return count;
1708 }
1709 
1710 //----------------------------------------------------------------------------//
1711 
1712 template <class Data_T>
1715 {
1716  if (FieldRes::dataResolution() == V3i(0))
1717  return cend();
1719  m_blockOrder);
1720 }
1721 
1722 //----------------------------------------------------------------------------//
1723 
1724 template <class Data_T>
1727 {
1728  if (subset.isEmpty())
1729  return cend(subset);
1730  return const_iterator(*this, subset, subset.min, m_blockOrder);
1731 }
1732 
1733 //----------------------------------------------------------------------------//
1734 
1735 template <class Data_T>
1738 {
1739  return const_iterator(*this, base::m_dataWindow,
1740  V3i(base::m_dataWindow.min.x,
1741  base::m_dataWindow.min.y,
1742  base::m_dataWindow.max.z + 1),
1743  m_blockOrder);
1744 }
1745 
1746 //----------------------------------------------------------------------------//
1747 
1748 template <class Data_T>
1750 SparseField<Data_T>::cend(const Box3i &subset) const
1751 {
1752  return const_iterator(*this, subset,
1753  V3i(subset.min.x,
1754  subset.min.y,
1755  subset.max.z + 1), m_blockOrder);
1756 }
1757 
1758 //----------------------------------------------------------------------------//
1759 
1760 template <class Data_T>
1763 {
1764  if (FieldRes::dataResolution() == V3i(0))
1765  return end();
1766  return iterator(*this, base::m_dataWindow,
1768 
1769 //----------------------------------------------------------------------------//
1770 
1771 template <class Data_T>
1774 {
1775  if (subset.isEmpty())
1776  return end(subset);
1777  return iterator(*this, subset, subset.min, m_blockOrder);
1778 }
1779 
1780 //----------------------------------------------------------------------------//
1781 
1782 template <class Data_T>
1785 {
1786  return iterator(*this, base::m_dataWindow,
1787  V3i(base::m_dataWindow.min.x,
1788  base::m_dataWindow.min.y,
1789  base::m_dataWindow.max.z + 1), m_blockOrder);
1790 }
1791 
1792 //----------------------------------------------------------------------------//
1793 
1794 template <class Data_T>
1797 {
1798  return iterator(*this, subset,
1799  V3i(subset.min.x, subset.min.y, subset.max.z + 1),
1800  m_blockOrder);
1801 }
1802 
1803 //----------------------------------------------------------------------------//
1804 
1805 template <class Data_T>
1808 {
1809  if (FieldRes::dataResolution() == V3i(0))
1810  return blockEnd();
1811  return block_iterator(*this, Box3i(V3i(0), m_blockRes - V3i(1)),
1812  V3i(0));
1813 }
1814 
1815 //----------------------------------------------------------------------------//
1816 
1817 template <class Data_T>
1820 {
1821  return block_iterator(*this, Box3i(V3i(0), m_blockRes - V3i(1)),
1822  V3i(0, 0, m_blockRes.z));
1823 }
1824 
1825 //----------------------------------------------------------------------------//
1826 
1827 template <class Data_T>
1829 {
1830  // Do calculation in floating point so we can round up later
1831  V3f res(base::m_dataWindow.size() + V3i(1));
1832  V3f blockRes(res / (1 << m_blockOrder));
1833  blockRes.x = ceil(blockRes.x);
1834  blockRes.y = ceil(blockRes.y);
1835  blockRes.z = ceil(blockRes.z);
1836  V3i intBlockRes(static_cast<int>(blockRes.x),
1837  static_cast<int>(blockRes.y),
1838  static_cast<int>(blockRes.z));
1839  m_blockRes = intBlockRes;
1841  if (m_blocks) {
1842  delete[] m_blocks;
1843  }
1844  m_numBlocks = intBlockRes.x * intBlockRes.y * intBlockRes.z;
1845  m_blocks = new Block[m_numBlocks];
1846 }
1847 
1848 //----------------------------------------------------------------------------//
1849 
1850 template <class Data_T>
1851 int SparseField<Data_T>::blockId(int blockI, int blockJ, int blockK) const
1852 {
1853  return blockK * m_blockXYSize + blockJ * m_blockRes.x + blockI;
1854 }
1855 
1856 //----------------------------------------------------------------------------//
1857 
1859 template <class Data_T>
1860 void SparseField<Data_T>::getBlockCoord(int i, int j, int k,
1861  int &bi, int &bj, int &bk) const
1862 {
1863  assert(i >= 0);
1864  assert(j >= 0);
1865  assert(k >= 0);
1866  bi = i >> m_blockOrder;
1867  bj = j >> m_blockOrder;
1868  bk = k >> m_blockOrder;
1869 }
1870 
1871 //----------------------------------------------------------------------------//
1872 
1874 template <class Data_T>
1875 void SparseField<Data_T>::getVoxelInBlock(int i, int j, int k,
1876  int &vi, int &vj, int &vk) const
1877 {
1878  assert(i >= 0);
1879  assert(j >= 0);
1880  assert(k >= 0);
1881  vi = i & ((1 << m_blockOrder) - 1);
1882  vj = j & ((1 << m_blockOrder) - 1);
1883  vk = k & ((1 << m_blockOrder) - 1);
1884 }
1885 
1886 //----------------------------------------------------------------------------//
1887 
1888 template <class Data_T>
1890 {
1892 }
1893 
1894 //----------------------------------------------------------------------------//
1895 
1896 template <class Data_T>
1898 {
1900 }
1901 
1902 //----------------------------------------------------------------------------//
1903 
1904 template <class Data_T>
1906 {
1908 }
1909 
1910 //----------------------------------------------------------------------------//
1911 
1912 template <class Data_T>
1914 {
1915  return m_numBlocks;
1916 }
1917 
1918 //----------------------------------------------------------------------------//
1919 
1920 template <class Data_T>
1921 bool SparseField<Data_T>::getGrainBounds(const size_t idx, Box3i &bounds) const
1922 {
1923  // Block size
1924  const size_t blockSide = (1 << m_blockOrder);
1925  // Block coordinate
1926  const V3i bCoord = indexToCoord(idx, m_blockRes);
1927  // Block bbox
1928  const V3i start(bCoord * blockSide + base::m_dataWindow.min);
1929  const V3i end (start + Imath::V3i(blockSide - 1));
1930  // Bounds must be clipped against data window
1931  const Box3i unclipped(start, end);
1932  bounds = clipBounds(unclipped, base::m_dataWindow);
1933  // Whether it's a contiguous block
1934  return bounds == unclipped;
1935 }
1936 
1937 //----------------------------------------------------------------------------//
1938 
1939 template <class Data_T>
1940 void SparseField<Data_T>::deallocBlock(Block &block, const Data_T &emptyValue)
1941 {
1942  block.isAllocated = false;
1944  block.clear();
1945  block.emptyValue = emptyValue;
1946 }
1947 
1948 //----------------------------------------------------------------------------//
1949 
1951 
1952 //----------------------------------------------------------------------------//
1953 
1954 #endif // Include guard
const class_type & m_field
Pointer to field we&#39;re traversing.
Definition: SparseField.h:1264
int m_blockOrder
Block size.
Definition: SparseField.h:1184
SparseField< double > SparseFieldd
Definition: SparseField.h:666
void removeFieldFromCache(int refIdx)
Definition: SparseFile.h:1152
#define FIELD3D_NAMESPACE_HEADER_CLOSE
Definition: ns.h:58
V3i blockRes() const
Returns the resolution of the block array.
Definition: SparseField.h:1512
Box3i clipBounds(const Box3i &bbox, const Box3i &bounds)
Definition: Field.h:1144
Imath::Box3i Box3i
Definition: SpiMathLib.h:77
void addReference(const std::string &filename, const std::string &layerPath, int valuesPerBlock, int occupiedBlocks)
Internal function to create a Reference for the current field, for use in dynamic reading...
Definition: SparseField.h:1365
Box3i blockCoords(const Box3i &dvsBounds, const SparseField< Data_T > *f)
Definition: SparseField.h:676
RefBase base
Convenience typedef for referring to base class.
Definition: SparseField.h:207
V3i m_blockRes
Block array resolution.
Definition: SparseField.h:612
size_t numGrains() const
Number of &#39;grains&#39; to use with threaded access.
Definition: SparseField.h:1913
bool check(const SparseBlock< Data_T > &block, Data_T &retEmptyValue, const V3i &validSize, const V3i &blockSize)
Checks whether a given block can be released. It&#39;s safe to assume that the block is allocated if this...
Definition: SparseField.h:707
int releaseBlocks(Functor_T func)
Releases any blocks that are deemed empty. This can be used to clean up after algorithms that write "...
Definition: SparseField.h:1521
Data_T & value(int i, int j, int k, int blockOrder)
Gets the value of a given voxel.
Definition: SparseField.h:249
iterator begin()
Iterator to first element.
Definition: SparseField.h:1762
const Data_T getBlockEmptyValue(int bi, int bj, int bk) const
Returns the constant value of an block, whether it&#39;s allocated already or not..
Definition: SparseField.h:1481
bool voxelIsInAllocatedBlock(int i, int j, int k) const
Checks if a voxel is in an allocated block.
Definition: SparseField.h:1461
int m_fileId
File id. Used with m_fileManager if active. Otherwise -1.
Definition: SparseField.h:624
SparseField< float > SparseFieldf
Definition: SparseField.h:665
void activateBlock(int fileId, int blockIdx)
Called by SparseField when it&#39;s about to read from a block. This should not be called by the user...
Definition: SparseFile.h:1206
static const char * staticClassType()
Definition: SparseField.h:373
Box3i m_window
Window to traverse.
Definition: SparseField.h:1188
Data_T fastValue(int i, int j, int k) const
Read access to voxel. Notice that this is non-virtual.
Definition: SparseField.h:1584
RefBase & operator=(const RefBase &)
Assignment operator.
Definition: RefCount.h:134
void applyDataWindowOffset(int &i, int &j, int &k) const
Applies data window offset.
Definition: SparseField.h:455
const Data_T & value(int i, int j, int k, int blockOrder) const
Gets the const value of a given voxel.
Definition: SparseField.h:255
void incBlockRef(int fileId, int blockIdx)
Increments the usage reference count on the specified block, to prevent it from getting unloaded whil...
Definition: SparseFile.h:1242
int m_blockXYSize
Block array res.x * res.y.
Definition: SparseField.h:614
#define FIELD3D_CLIP
Definition: SpiMathLib.h:90
int blockId(int blockI, int blockJ, int blockK) const
Calculates the block number based on a block i,j,k index.
Definition: SparseField.h:1851
Data_T * m_p
Current pointed-to element.
Definition: SparseField.h:1178
bool isDynamicLoad() const
Whether the field is dynamically loaded.
Definition: SparseField.h:463
block_iterator(const class_type &field, const Box3i &window, const V3i &currentPos)
Constructor.
Definition: SparseField.h:1206
void setBlockEmptyValue(int bi, int bj, int bk, const Data_T &val)
Sets the constant value of an block. If the block is already allocated, it gets deallocated.
Definition: SparseField.h:1489
Contains functions controlling the loading of sparse fields.
void setupReferenceBlocks()
Internal function to setup the Reference&#39;s block pointers, for use with dynamic reading.
Definition: SparseField.h:1397
boost::intrusive_ptr< FieldBase > Ptr
Definition: Field.h:97
value_type sample(const SparseField< Data_T > &field, const V3d &vsP) const
Definition: SparseField.h:112
int x
Current x/y/z coord.
Definition: SparseField.h:975
Data_T * data
Pointer to data. Null if block is unallocated.
Definition: SparseField.h:311
~SparseField()
Destructor.
Definition: SparseField.h:1298
FIELD3D_API void print(Severity severity, const std::string &message)
Sends the string to the assigned output, prefixing the message with the severity. ...
Definition: Log.cpp:66
FIELD3D_VEC3_T< T > operator*(S s, const FIELD3D_VEC3_T< T > vec)
Scalar times Vec3 multiplication. Makes the interpolation calls cleaner.
Definition: FieldInterp.h:1558
int m_blockOrder
Block order (size = 2^blockOrder)
Definition: SparseField.h:610
std::vector< int > fileBlockIndices
Index in file for each block.
Definition: SparseFile.h:119
boost::intrusive_ptr< SparseField > Ptr
Definition: SparseField.h:357
int m_blockStepsTicker
Ticker for how many more steps to take before resetting the pointer.
Definition: SparseField.h:1182
static TemplatedFieldType< LinearSparseFieldInterp< Data_T > > ms_classType
Definition: SparseField.h:202
void activateBlock(const int blockId) const
Activates a given block.
Definition: SparseField.h:1897
bool check(const SparseBlock< Data_T > &block, Data_T &retEmptyValue, const V3i &validSize, const V3i &blockSize)
Checks whether a given block can be released. It&#39;s safe to assume that the block is allocated if this...
Definition: SparseField.h:812
void setupNextBlock(int i, int j, int k)
Convenience.
Definition: SparseField.h:1156
std::string layerPath
Definition: SparseFile.h:114
virtual Data_T & lvalue(int i, int j, int k)
Write access to a voxel. The coordinates are global coordinates.
Definition: SparseField.h:1576
SparseField()
Constructs an empty buffer.
Definition: SparseField.h:1274
SparseField< V3f > SparseField3f
Definition: SparseField.h:668
SparseField< Data_T > class_type
Definition: SparseField.h:365
Box3i m_dataWindow
Defines the area where data is allocated. This should be treated as a closed (i.e. inclusive) interval.
Definition: Field.h:315
#define BLOCK_ORDER
Definition: SparseField.h:57
Data_T emptyValue
The value to use if the block isn&#39;t allocated. We allow setting this per block so that we for example...
Definition: SparseField.h:308
SparseField< half > SparseFieldh
Definition: SparseField.h:664
Imath::Vec3< half > V3h
Definition: SpiMathLib.h:72
boost::intrusive_ptr< LinearSparseFieldInterp > Ptr
Definition: SparseField.h:93
Sparse::SparseBlock< Data_T > Block
Definition: SparseField.h:1154
iterator end()
Iterator pointing one element past the last valid one.
Definition: SparseField.h:1784
Imath::V3i V3i
Definition: SpiMathLib.h:71
static TemplatedFieldType< SparseField< Data_T > > ms_classType
Definition: SparseField.h:633
FIELD3D_CLASSTYPE_TEMPL_INSTANTIATION(LinearSparseFieldInterp)
SparseField< Data_T > class_type
Definition: SparseField.h:1066
BlockPtrs blocks
Pointers to each block. This is so we can go in and manipulate them as we please. ...
Definition: SparseFile.h:125
Namespace for sparse field specifics.
Definition: SparseField.h:221
void decBlockRef(const int blockId) const
Decrements the block ref count for the given block.
Definition: SparseField.h:1905
FIELD3D_VEC3_T< T > floor(const FIELD3D_VEC3_T< T > &v)
Floor function for Vec3.
Definition: CoordSys.h:95
void copySparseField(const SparseField &o)
Copies internal data, including blocks, from another SparseField, used by copy constructor and operat...
Definition: SparseField.h:1328
Checks if all the absolute values in the SparseBlock are greater than some number. Useful for making narrow band levelsets Used by SparseField::releaseBlocks().
Definition: SparseField.h:798
virtual void clear(const Data_T &value)
Clears all the voxels in the storage.
Definition: SparseField.h:1422
void resize(int n)
Alloc data.
Definition: SparseField.h:259
static const char * staticClassName()
Definition: SparseField.h:368
const Data_T * m_p
Current pointed-to element.
Definition: SparseField.h:1028
bool blockIsAllocated(int bi, int bj, int bk) const
Checks if a block is allocated.
Definition: SparseField.h:1472
Data_T & fastLValue(int i, int j, int k)
Write access to voxel. Notice that this is non-virtual.
Definition: SparseField.h:1623
CheckMaxAbs(Data_T maxValue)
Constructor. Takes max value.
Definition: SparseField.h:801
Box3i m_currentBlockWindow
Bounding box in voxel coordinates for the current block.
Definition: SparseField.h:1266
static const char * staticClassType()
Definition: SparseField.h:105
Imath::V3d V3d
Definition: SpiMathLib.h:74
virtual Data_T value(int i, int j, int k) const
Read access to a voxel. The coordinates are in integer voxel space .
Definition: SparseField.h:1568
Data_T m_dummy
Dummy value used when needing to return but indicating a failed call.
Definition: SparseField.h:627
LinearSparseFieldInterp class_type
Definition: SparseField.h:97
Box3i m_window
Bounding box for block indices.
Definition: SparseField.h:1262
void setBlockOrder(int order)
Sets the block order (i.e. the power-of-2 to use as block size.
Definition: SparseField.h:1436
Imath::V3f V3f
Definition: SpiMathLib.h:73
bool getGrainBounds(const size_t idx, Box3i &vsBounds) const
Bounding box of the given &#39;grain&#39;.
Definition: SparseField.h:1921
iterator(class_type &field, const Box3i &window, const V3i &currentPos, int blockOrder)
Definition: SparseField.h:1067
void copy(const SparseBlock &other, size_t n)
Copy data from another block.
Definition: SparseField.h:285
block_iterator blockBegin() const
Definition: SparseField.h:1807
int m_blockOrder
Block size.
Definition: SparseField.h:1037
virtual size_t voxelCount() const
Counts the number of voxels. For most fields, this is just the volume of the data window...
Definition: SparseField.h:1696
void setupBlocks()
Initializes the block structure. Will clear any existing data.
Definition: SparseField.h:1828
bool isAllocated
Whether the block is allocated or not.
Definition: SparseField.h:303
int getNextId(const std::string filename, const std::string layerPath)
Returns the id of the next cache item. This is stored in the SparseField in order to reference its fi...
Definition: SparseFile.h:1135
Used to return a string for the name of a templated field.
Definition: Traits.h:116
V3i const dataResolution() const
Definition: Field.h:261
virtual FieldBase::Ptr clone() const
Returns a pointer to a copy of the field, pure virtual so ensure derived classes properly implement i...
Definition: SparseField.h:517
virtual long long int memSize() const
Returns the memory usage (in bytes)
Definition: SparseField.h:1678
int x
Current block index.
Definition: SparseField.h:1247
void decBlockRef(int fileId, int blockIdx)
Decrements the usage reference count on the specified block, after its value is no longer being used ...
Definition: SparseFile.h:1255
Storage for one individual block of a SparseField.
Definition: SparseField.h:227
SparseField< Data_T > class_type
Convenience typedef.
Definition: SparseField.h:1204
std::string filename
Definition: SparseFile.h:113
bool blockIndexIsValid(int bi, int bj, int bk) const
Returns whether a block index is valid.
Definition: SparseField.h:1503
void incBlockRef(const int blockId) const
Increments the block ref count for the given block.
Definition: SparseField.h:1889
Box3i m_window
Window to traverse.
Definition: SparseField.h:1041
void clear()
Remove data.
Definition: SparseField.h:273
LinearSparseFieldInterp< Data_T > LinearInterp
Definition: SparseField.h:360
static const char * staticClassName()
Definition: SparseField.h:100
Contains Field, WritableField and ResizableField classes.
bool match(const std::string &name, const std::string &attribute, const std::vector< std::string > &patterns, const MatchFlags flags=MatchEmptyPattern)
Matches a <name>:<attribute> string against a set of patterns.
static boost::mutex ms_resizeMutex
Prevents concurrent allocation of blocks. There should be little contention, and this prevents multip...
Definition: SparseField.h:325
block_iterator blockEnd() const
Const iterator pointing to element one past the last valid block.
Definition: SparseField.h:1819
void getVoxelInBlock(int i, int j, int k, int &vi, int &vj, int &vk) const
Calculates the coordinates in a block for the given voxel index.
Definition: SparseField.h:1875
const_iterator cend() const
Const iterator pointing one element past the last valid one.
Definition: SparseField.h:1737
SparseField< V3d > SparseField3d
Definition: SparseField.h:669
void getBlockCoord(int i, int j, int k, int &bi, int &bj, int &bk) const
Calculates the block coordinates that a given set of voxel coords are in.
Definition: SparseField.h:1860
void copyBlockStates(const SparseField< Data_T > &o)
Internal function to copy empty values and allocated flags, without copying data, used when copying a...
Definition: SparseField.h:1383
const class_type * m_field
Reference to field we&#39;re traversing.
Definition: SparseField.h:1043
std::vector< Ptr > Vec
Definition: SparseField.h:358
Sparse::SparseBlock< Data_T > Block
Definition: SparseField.h:583
const_iterator(const class_type &field, const Box3i &window, const V3i &currentPos, int blockOrder)
Definition: SparseField.h:885
V3i indexToCoord(const size_t idx, const V3i &res)
Definition: Field.h:1186
size_t m_numBlocks
Number of blocks in field.
Definition: SparseField.h:618
CubicGenericFieldInterp< SparseField< Data_T > > CubicInterp
Definition: SparseField.h:361
const char * name()
Definition: Traits.h:118
ResizableField< Data_T > base
Definition: SparseField.h:582
SparseField & operator=(const SparseField &o)
Assignment operator. For cache-managed fields, it creates a new file reference, and for non-managed f...
Definition: SparseField.h:1315
bool m_isEmptyBlock
Whether we&#39;re at an empty block and we don&#39;t increment m_p.
Definition: SparseField.h:1180
bool m_isEmptyBlock
Whether we&#39;re at an empty block and we don&#39;t increment m_p.
Definition: SparseField.h:1030
int blockOrder() const
Returns the block order.
Definition: SparseField.h:1445
bool m_blockIsActivated
Used with delayed-load fields. Check if we&#39;ve already activated the current blocks.
Definition: SparseField.h:1033
Sparse::SparseBlock< Data_T > Block
Definition: SparseField.h:981
void deallocBlock(Block &block, const Data_T &emptyValue)
Deallocated the data of the given block and sets its empty value.
Definition: SparseField.h:1940
This Field subclass stores voxel data in block-allocated arrays.
Definition: SparseField.h:350
SparseFile::Reference< Data_T > * reference(int index)
Returns a reference to the Reference object with the given index.
Definition: SparseFile.h:1197
FIELD3D_VEC3_T< T > ceil(const FIELD3D_VEC3_T< T > &v)
Ceil function for Vec3.
Definition: CoordSys.h:105
static SparseFileManager & singleton()
Returns a reference to the singleton instance.
Definition: SparseFile.cpp:63
const Box3i & dataWindow() const
Returns the data window. Any coordinate inside this window is safe to pass to value() in the Field su...
Definition: Field.h:258
virtual void sizeChanged()
Subclasses should re-implement this if they need to perform memory allocations, etc. every time the size of the storage changes.
Definition: SparseField.h:587
Checks if all the values in the SparseBlock are equal. Used by SparseField::releaseBlocks().
Definition: SparseField.h:697
const Box3i & blockBoundingBox()
Returns a reference to the bounding box representing the current block.
Definition: SparseField.h:1242
Data_T * blockData(int bi, int bj, int bk) const
Returns a pointer to the data in a block, or null if the given block is unallocated.
Definition: SparseField.h:1664
SparseField< V3h > SparseField3h
Definition: SparseField.h:667
DEFINE_FIELD_RTTI_CONCRETE_CLASS
Definition: SparseField.h:366
SparseField< Data_T > class_type
Definition: SparseField.h:884
SparseFileManager * m_manager
Pointer to the singleton file manager.
Definition: SparseField.h:1045
SparseFileManager * m_fileManager
Pointer to SparseFileManager. Used when doing dynamic reading. NULL if not in use.
Definition: SparseField.h:622
int m_blockStepsTicker
Ticker for how many more steps to take before resetting the pointer.
Definition: SparseField.h:1035
bool isAnyLess(const V3d &left, const V3d &right)
Definition: SparseField.h:785
const_iterator cbegin() const
Const iterator to first element. "cbegin" matches the tr1 c++ standard.
Definition: SparseField.h:1714
int blockSize() const
Returns the block size.
Definition: SparseField.h:1453
void setupNextBlock(int i, int j, int k)
Definition: SparseField.h:985
Block * m_blocks
Array of blocks. Not using std::vector since SparseBlock is noncopyable.
Definition: SparseField.h:616
class_type * m_field
Reference to field we&#39;re traversing.
Definition: SparseField.h:1190
FIELD3D_CLASSNAME_CLASSTYPE_IMPLEMENTATION
Definition: SparseField.h:515
std::string name
Optional name of the field.
Definition: Field.h:176