OpenVDB  3.1.0
Dense.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2015 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 //
35 
36 #ifndef OPENVDB_TOOLS_DENSE_HAS_BEEN_INCLUDED
37 #define OPENVDB_TOOLS_DENSE_HAS_BEEN_INCLUDED
38 
39 #include <openvdb/Types.h>
40 #include <openvdb/Grid.h>
41 #include <openvdb/tree/ValueAccessor.h>
42 #include <openvdb/Exceptions.h>
43 #include <tbb/parallel_for.h>
44 #include <boost/scoped_array.hpp>
45 #include <boost/scoped_ptr.hpp>
46 #include "Prune.h"
47 
48 namespace openvdb {
50 namespace OPENVDB_VERSION_NAME {
51 namespace tools {
52 
58 template<typename DenseT, typename GridOrTreeT>
59 void
61  const GridOrTreeT& sparse,
62  DenseT& dense,
63  bool serial = false);
64 
65 
72 template<typename DenseT, typename GridOrTreeT>
73 void
75  const DenseT& dense,
76  GridOrTreeT& sparse,
77  const typename GridOrTreeT::ValueType& tolerance,
78  bool serial = false);
79 
80 
82 
92 
96 template<typename ValueT, MemoryLayout Layout> class DenseBase;
97 
101 template<typename ValueT>
102 class DenseBase<ValueT, LayoutZYX>
103 {
104 public:
111  inline size_t coordToOffset(size_t i, size_t j, size_t k) const { return i*mX + j*mY + k; }
112 
117  inline Coord offsetToLocalCoord(size_t n) const
118  {
119  const size_t x = n / mX;
120  n -= mX*x;
121  const size_t y = n / mY;
122  return Coord(Coord::ValueType(x), Coord::ValueType(y), Coord::ValueType(n - mY*y));
123  }
124 
127  inline size_t xStride() const { return mX; }
128 
131  inline size_t yStride() const { return mY; }
132 
135  static size_t zStride() { return 1; }
136 
137 protected:
139  DenseBase(const CoordBBox& bbox) : mBBox(bbox), mY(bbox.dim()[2]), mX(mY*bbox.dim()[1]) {}
140 
141  const CoordBBox mBBox;//signed coordinates of the domain represented by the grid
142  const size_t mY, mX;//strides in the y and x direction
143 };// end of DenseBase<ValueT, LayoutZYX>
144 
148 template<typename ValueT>
149 class DenseBase<ValueT, LayoutXYZ>
150 {
151 public:
158  inline size_t coordToOffset(size_t i, size_t j, size_t k) const { return i + j*mY + k*mZ; }
159 
164  inline Coord offsetToLocalCoord(size_t n) const
165  {
166  const size_t z = n / mZ;
167  n -= mZ*z;
168  const size_t y = n / mY;
169  return Coord(Coord::ValueType(n - mY*y), Coord::ValueType(y), Coord::ValueType(z));
170  }
171 
174  static size_t xStride() { return 1; }
175 
178  inline size_t yStride() const { return mY; }
179 
182  inline size_t zStride() const { return mZ; }
183 
184 protected:
186  DenseBase(const CoordBBox& bbox) : mBBox(bbox), mY(bbox.dim()[0]), mZ(mY*bbox.dim()[1]) {}
187 
188  const CoordBBox mBBox;//signed coordinates of the domain represented by the grid
189  const size_t mY, mZ;//strides in the y and z direction
190 };// end of DenseBase<ValueT, LayoutXYZ>
191 
204 template<typename ValueT, MemoryLayout Layout = LayoutZYX>
205 class Dense : public DenseBase<ValueT, Layout>
206 {
207 public:
208  typedef ValueT ValueType;
210 
216  Dense(const CoordBBox& bbox) : BaseT(bbox) { this->init(); }
217 
224  Dense(const CoordBBox& bbox, const ValueT& value) : BaseT(bbox)
225  {
226  this->init();
227  this->fill(value);
228  }
229 
239  Dense(const CoordBBox& bbox, ValueT* data) : BaseT(bbox), mData(data)
240  {
241  if (BaseT::mBBox.empty()) {
242  OPENVDB_THROW(ValueError, "can't construct a dense grid with an empty bounding box");
243  }
244  }
245 
253  Dense(const Coord& dim, const Coord& min = Coord(0))
254  : BaseT(CoordBBox(min, min+dim.offsetBy(-1)))
255  {
256  this->init();
257  }
258 
260  static MemoryLayout memoryLayout() { return Layout; }
261 
264  inline ValueT* data() { return mData; }
265 
268  inline const ValueT* data() const { return mData; }
269 
272  inline const CoordBBox& bbox() const { return BaseT::mBBox; }
273 
275  inline const Coord& origin() const { return BaseT::mBBox.min(); }
276 
278  inline Index64 valueCount() const { return BaseT::mBBox.volume(); }
279 
281  inline void setValue(size_t offset, const ValueT& value) { mData[offset] = value; }
282 
284  const ValueT& getValue(size_t offset) const { return mData[offset]; }
285 
288  inline void setValue(size_t i, size_t j, size_t k, const ValueT& value)
289  {
290  mData[BaseT::coordToOffset(i,j,k)] = value;
291  }
292 
295  inline const ValueT& getValue(size_t i, size_t j, size_t k) const
296  {
297  return mData[BaseT::coordToOffset(i,j,k)];
298  }
299 
302  inline void setValue(const Coord& xyz, const ValueT& value)
303  {
304  mData[this->coordToOffset(xyz)] = value;
305  }
306 
309  inline const ValueT& getValue(const Coord& xyz) const
310  {
311  return mData[this->coordToOffset(xyz)];
312  }
313 
315  inline void fill(const ValueT& value)
316  {
317  size_t size = this->valueCount();
318  ValueT* a = mData;
319  while(size--) *a++ = value;
320  }
321 
328  inline size_t coordToOffset(const Coord& xyz) const
329  {
330  assert(BaseT::mBBox.isInside(xyz));
331  return BaseT::coordToOffset(size_t(xyz[0]-BaseT::mBBox.min()[0]),
332  size_t(xyz[1]-BaseT::mBBox.min()[1]),
333  size_t(xyz[2]-BaseT::mBBox.min()[2]));
334  }
335 
337  inline Coord offsetToCoord(size_t n) const
338  {
339  return this->offsetToLocalCoord(n) + BaseT::mBBox.min();
340  }
341 
343  inline Index64 memUsage() const
344  {
345  return sizeof(*this) + BaseT::mBBox.volume() * sizeof(ValueType);
346  }
347 
348 private:
349 
351  void init()
352  {
353  if (BaseT::mBBox.empty()) {
354  OPENVDB_THROW(ValueError, "can't construct a dense grid with an empty bounding box");
355  }
356  mArray.reset(new ValueT[BaseT::mBBox.volume()]);
357  mData = mArray.get();
358  }
359 
360  boost::scoped_array<ValueT> mArray;
361  ValueT* mData;//raw c-style pointer to values
362 };// end of Dense
363 
365 
366 
373 template<typename _TreeT, typename _DenseT = Dense<typename _TreeT::ValueType> >
375 {
376 public:
377  typedef _DenseT DenseT;
378  typedef _TreeT TreeT;
379  typedef typename TreeT::ValueType ValueT;
380 
381  CopyToDense(const TreeT& tree, DenseT& dense)
382  : mRoot(&(tree.root())), mDense(&dense) {}
383 
384  void copy(bool serial = false) const
385  {
386  if (serial) {
387  mRoot->copyToDense(mDense->bbox(), *mDense);
388  } else {
389  tbb::parallel_for(mDense->bbox(), *this);
390  }
391  }
392 
394  void operator()(const CoordBBox& bbox) const
395  {
396  mRoot->copyToDense(bbox, *mDense);
397  }
398 
399 private:
400  const typename TreeT::RootNodeType* mRoot;
401  DenseT* mDense;
402 };// CopyToDense
403 
404 
405 // Convenient wrapper function for the CopyToDense class
406 template<typename DenseT, typename GridOrTreeT>
407 void
408 copyToDense(const GridOrTreeT& sparse, DenseT& dense, bool serial)
409 {
410  typedef TreeAdapter<GridOrTreeT> Adapter;
411  typedef typename Adapter::TreeType TreeT;
412 
413  CopyToDense<TreeT, DenseT> op(Adapter::constTree(sparse), dense);
414  op.copy(serial);
415 }
416 
417 
419 
420 
430 template<typename _TreeT, typename _DenseT = Dense<typename _TreeT::ValueType> >
432 {
433 public:
434  typedef _DenseT DenseT;
435  typedef _TreeT TreeT;
436  typedef typename TreeT::ValueType ValueT;
437  typedef typename TreeT::LeafNodeType LeafT;
439 
440  CopyFromDense(const DenseT& dense, TreeT& tree, const ValueT& tolerance)
441  : mDense(&dense),
442  mTree(&tree),
443  mBlocks(NULL),
444  mTolerance(tolerance),
445  mAccessor(tree.empty() ? NULL : new AccessorT(tree))
446  {
447  }
449  : mDense(other.mDense),
450  mTree(other.mTree),
451  mBlocks(other.mBlocks),
452  mTolerance(other.mTolerance),
453  mAccessor(other.mAccessor.get() == NULL ? NULL : new AccessorT(*mTree))
454  {
455  }
456 
458  void copy(bool serial = false)
459  {
460  mBlocks = new std::vector<Block>();
461  const CoordBBox& bbox = mDense->bbox();
462  // Pre-process: Construct a list of blocks aligned with (potential) leaf nodes
463  for (CoordBBox sub=bbox; sub.min()[0] <= bbox.max()[0]; sub.min()[0] = sub.max()[0] + 1) {
464  for (sub.min()[1] = bbox.min()[1]; sub.min()[1] <= bbox.max()[1];
465  sub.min()[1] = sub.max()[1] + 1)
466  {
467  for (sub.min()[2] = bbox.min()[2]; sub.min()[2] <= bbox.max()[2];
468  sub.min()[2] = sub.max()[2] + 1)
469  {
470  sub.max() = Coord::minComponent(bbox.max(),
471  (sub.min()&(~(LeafT::DIM-1u))).offsetBy(LeafT::DIM-1u));
472  mBlocks->push_back(Block(sub));
473  }
474  }
475  }
476 
477  // Multi-threaded process: Convert dense grid into leaf nodes and tiles
478  if (serial) {
479  (*this)(tbb::blocked_range<size_t>(0, mBlocks->size()));
480  } else {
481  tbb::parallel_for(tbb::blocked_range<size_t>(0, mBlocks->size()), *this);
482  }
483 
484  // Post-process: Insert leaf nodes and tiles into the tree, and prune the tiles only!
485  tree::ValueAccessor<TreeT> acc(*mTree);
486  for (size_t m=0, size = mBlocks->size(); m<size; ++m) {
487  Block& block = (*mBlocks)[m];
488  if (block.leaf) {
489  acc.addLeaf(block.leaf);
490  } else if (block.tile.second) {//only background tiles are inactive
491  acc.addTile(1, block.bbox.min(), block.tile.first, true);//leaf tile
492  }
493  }
494  delete mBlocks;
495  mBlocks = NULL;
496 
497  tools::pruneTiles(*mTree, mTolerance);//multi-threaded
498  }
499 
502  void operator()(const tbb::blocked_range<size_t> &r) const
503  {
504  assert(mBlocks);
505  LeafT* leaf = new LeafT();
506 
507  for (size_t m=r.begin(), n=0, end = r.end(); m != end; ++m, ++n) {
508 
509  Block& block = (*mBlocks)[m];
510  const CoordBBox &bbox = block.bbox;
511 
512  if (mAccessor.get() == NULL) {//i.e. empty target tree
513  leaf->fill(mTree->background(), false);
514  } else {//account for existing leaf nodes in the target tree
515  if (const LeafT* target = mAccessor->probeConstLeaf(bbox.min())) {
516  (*leaf) = (*target);
517  } else {
518  ValueT value = zeroVal<ValueT>();
519  bool state = mAccessor->probeValue(bbox.min(), value);
520  leaf->fill(value, state);
521  }
522  }
523 
524  leaf->copyFromDense(bbox, *mDense, mTree->background(), mTolerance);
525 
526  if (!leaf->isConstant(block.tile.first, block.tile.second, mTolerance)) {
527  leaf->setOrigin(bbox.min() & (~(LeafT::DIM - 1)));
528  block.leaf = leaf;
529  leaf = new LeafT();
530  }
531  }// loop over blocks
532 
533  delete leaf;
534  }
535 
536 private:
537  struct Block {
538  CoordBBox bbox;
539  LeafT* leaf;
540  std::pair<ValueT, bool> tile;
541  Block(const CoordBBox& b) : bbox(b), leaf(NULL) {}
542  };
543 
544  const DenseT* mDense;
545  TreeT* mTree;
546  std::vector<Block>* mBlocks;
547  ValueT mTolerance;
548  boost::scoped_ptr<AccessorT> mAccessor;
549 };// CopyFromDense
550 
551 
552 // Convenient wrapper function for the CopyFromDense class
553 template<typename DenseT, typename GridOrTreeT>
554 void
555 copyFromDense(const DenseT& dense, GridOrTreeT& sparse,
556  const typename GridOrTreeT::ValueType& tolerance, bool serial)
557 {
558  typedef TreeAdapter<GridOrTreeT> Adapter;
559  typedef typename Adapter::TreeType TreeT;
560 
561  CopyFromDense<TreeT, DenseT> op(dense, Adapter::tree(sparse), tolerance);
562  op.copy(serial);
563 }
564 
565 } // namespace tools
566 } // namespace OPENVDB_VERSION_NAME
567 } // namespace openvdb
568 
569 #endif // OPENVDB_TOOLS_DENSE_HAS_BEEN_INCLUDED
570 
571 // Copyright (c) 2012-2015 DreamWorks Animation LLC
572 // All rights reserved. This software is distributed under the
573 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
void addLeaf(LeafNodeT *leaf)
Add the specified leaf to this tree, possibly creating a child branch in the process. If the leaf node already exists, replace it.
Definition: ValueAccessor.h:374
const Coord & origin() const
Return the grid's origin in index coordinates.
Definition: Dense.h:275
CopyFromDense(const CopyFromDense &other)
Definition: Dense.h:448
void setValue(const Coord &xyz, const ValueT &value)
Set the value of the voxel at the given signed coordinates.
Definition: Dense.h:302
Dense(const CoordBBox &bbox)
Construct a dense grid with a given range of coordinates.
Definition: Dense.h:216
TreeT::ValueType ValueT
Definition: Dense.h:379
void copyToDense(const GridOrTreeT &sparse, DenseT &dense, bool serial=false)
Populate a dense grid with the values of voxels from a sparse grid, where the sparse grid intersects ...
Definition: Dense.h:408
const CoordBBox & bbox() const
Return the bounding box of the signed index domain of this grid.
Definition: Dense.h:272
size_t yStride() const
Return the stride of the array in the y direction ( = dimZ).
Definition: Dense.h:131
size_t zStride() const
Return the stride of the array in the y direction ( = dimX*dimY).
Definition: Dense.h:182
Base class for Dense which is defined below.
Definition: Dense.h:96
Definition: Exceptions.h:88
static size_t zStride()
Return the stride of the array in the z direction ( = 1).
Definition: Dense.h:135
Dense(const Coord &dim, const Coord &min=Coord(0))
Construct a dense grid with a given origin and dimensions.
Definition: Dense.h:253
void operator()(const CoordBBox &bbox) const
Public method called by tbb::parallel_for.
Definition: Dense.h:394
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
CopyFromDense(const DenseT &dense, TreeT &tree, const ValueT &tolerance)
Definition: Dense.h:440
Copy the values from a dense grid into an OpenVDB tree.
Definition: Dense.h:431
Dense(const CoordBBox &bbox, const ValueT &value)
Construct a dense grid with a given range of coordinates and initial value.
Definition: Dense.h:224
static size_t xStride()
Return the stride of the array in the x direction ( = 1).
Definition: Dense.h:174
void copy(bool serial=false)
Copy values from the dense grid to the sparse tree.
Definition: Dense.h:458
const ValueT & getValue(const Coord &xyz) const
Return the value of the voxel at the given signed coordinates.
Definition: Dense.h:309
const boost::disable_if_c< VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:105
static MemoryLayout memoryLayout()
Return the memory layout for this grid (see above for definitions).
Definition: Dense.h:260
size_t coordToOffset(size_t i, size_t j, size_t k) const
Return the linear offset into this grid's value array given by unsigned coordinates (i...
Definition: Dense.h:158
void setValue(size_t i, size_t j, size_t k, const ValueT &value)
Set the value of the voxel at unsigned index coordinates (i, j, k).
Definition: Dense.h:288
TreeT::ValueType ValueT
Definition: Dense.h:436
Defined various multi-threaded utility functions for trees.
Vec2< T > minComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise minimum of the two vectors.
Definition: Vec2.h:511
size_t yStride() const
Return the stride of the array in the y direction ( = dimX).
Definition: Dense.h:178
Copy an OpenVDB tree into an existing dense grid.
Definition: Dense.h:374
TreeT::LeafNodeType LeafT
Definition: Dense.h:437
#define OPENVDB_VERSION_NAME
Definition: version.h:43
const CoordBBox mBBox
Definition: Dense.h:188
ValueT ValueType
Definition: Dense.h:208
void copy(bool serial=false) const
Definition: Dense.h:384
Definition: Dense.h:91
const ValueT & getValue(size_t i, size_t j, size_t k) const
Return the value of the voxel at unsigned index coordinates (i, j, k).
Definition: Dense.h:295
Dense is a simple dense grid API used by the CopyToDense and CopyFromDense classes defined below...
Definition: Dense.h:205
_DenseT DenseT
Definition: Dense.h:434
Coord offsetToLocalCoord(size_t n) const
Return the local coordinate corresponding to the specified linear offset.
Definition: Dense.h:117
Definition: Exceptions.h:39
void addTile(Index level, const Coord &xyz, const ValueType &value, bool state)
Add a tile at the specified tree level that contains voxel (x, y, z), possibly deleting existing node...
Definition: ValueAccessor.h:382
void copyFromDense(const DenseT &dense, GridOrTreeT &sparse, const typename GridOrTreeT::ValueType &tolerance, bool serial=false)
Populate a sparse grid with the values of all of the voxels of a dense grid.
Definition: Dense.h:555
Index64 valueCount() const
Return the number of voxels contained in this grid.
Definition: Dense.h:278
_TreeT TreeT
Definition: Dense.h:378
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:880
_TreeT TreeT
Definition: Dense.h:435
Coord offsetToLocalCoord(size_t n) const
Return the index coordinate corresponding to the specified linear offset.
Definition: Dense.h:164
const CoordBBox mBBox
Definition: Dense.h:141
void setValue(size_t offset, const ValueT &value)
Set the value of the voxel at the given array offset.
Definition: Dense.h:281
tree::ValueAccessor< TreeT > AccessorT
Definition: Dense.h:438
DenseBase(const CoordBBox &bbox)
Protected constructor so as to prevent direct instantiation.
Definition: Dense.h:186
Index64 memUsage() const
Return the memory footprint of this Dense grid in bytes.
Definition: Dense.h:343
Dense(const CoordBBox &bbox, ValueT *data)
Construct a dense grid that wraps an external array.
Definition: Dense.h:239
size_t coordToOffset(size_t i, size_t j, size_t k) const
Return the linear offset into this grid's value array given by unsigned coordinates (i...
Definition: Dense.h:111
uint64_t Index64
Definition: Types.h:57
size_t xStride() const
Return the stride of the array in the x direction ( = dimY*dimZ).
Definition: Dense.h:127
CopyToDense(const TreeT &tree, DenseT &dense)
Definition: Dense.h:381
const ValueT * data() const
Return a raw pointer to this grid's value array.
Definition: Dense.h:268
_DenseT DenseT
Definition: Dense.h:377
Coord offsetToCoord(size_t n) const
Return the global coordinate corresponding to the specified linear offset.
Definition: Dense.h:337
Definition: Dense.h:91
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
DenseBase(const CoordBBox &bbox)
Protected constructor so as to prevent direct instantiation.
Definition: Dense.h:139
DenseBase< ValueT, Layout > BaseT
Definition: Dense.h:209
const ValueT & getValue(size_t offset) const
Return the value of the voxel at the given array offset.
Definition: Dense.h:284
void fill(const ValueT &value)
Fill this grid with a constant value.
Definition: Dense.h:315
ValueT * data()
Return a raw pointer to this grid's value array.
Definition: Dense.h:264
size_t coordToOffset(const Coord &xyz) const
Return the linear offset into this grid's value array given by the specified signed coordinates...
Definition: Dense.h:328
MemoryLayout
Definition: Dense.h:91
void operator()(const tbb::blocked_range< size_t > &r) const
Public method called by tbb::parallel_for.
Definition: Dense.h:502
void pruneTiles(TreeT &tree, typename TreeT::ValueType tolerance=zeroVal< typename TreeT::ValueType >(), bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing with tiles any non-leaf nodes whose values are all...
Definition: Prune.h:357