OpenVDB  2.1.0
Dense.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2013 DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
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_ptr.hpp>
45 
46 namespace openvdb {
48 namespace OPENVDB_VERSION_NAME {
49 namespace tools {
50 
56 template<typename DenseT, typename GridOrTreeT>
57 void
59  const GridOrTreeT& sparse,
60  DenseT& dense,
61  bool serial = false);
62 
63 
70 template<typename DenseT, typename GridOrTreeT>
71 void
73  const DenseT& dense,
74  GridOrTreeT& sparse,
75  const typename GridOrTreeT::ValueType& tolerance,
76  bool serial = false);
77 
78 
80 
90 
94 template<typename ValueT, MemoryLayout Layout> class DenseBase;
95 
99 template<typename ValueT>
100 class DenseBase<ValueT, LayoutZYX>
101 {
102 public:
106  inline size_t coordToOffset(size_t i, size_t j, size_t k) const { return i*mX + j*mY + k; }
107 
110  inline size_t xStride() const { return mX; }
111 
114  inline size_t yStride() const { return mY; }
115 
118  static size_t zStride() { return 1; }
119 
120 protected:
122  DenseBase(const CoordBBox& bbox) : mBBox(bbox), mY(bbox.dim()[2]), mX(mY*bbox.dim()[1]) {}
123 
124  const CoordBBox mBBox;//signed coordinates of the domain represented by the grid
125  const size_t mY, mX;//strides in the y and x direction
126 };// end of DenseBase<ValueT, LayoutZYX>
127 
131 template<typename ValueT>
132 class DenseBase<ValueT, LayoutXYZ>
133 {
134 public:
138  inline size_t coordToOffset(size_t i, size_t j, size_t k) const { return i + j*mY + k*mZ; }
139 
142  static size_t xStride() { return 1; }
143 
146  inline size_t yStride() const { return mY; }
147 
150  inline size_t zStride() const { return mZ; }
151 
152 protected:
154  DenseBase(const CoordBBox& bbox) : mBBox(bbox), mY(bbox.dim()[0]), mZ(mY*bbox.dim()[1]) {}
155 
156  const CoordBBox mBBox;//signed coordinates of the domain represented by the grid
157  const size_t mY, mZ;//strides in the y and z direction
158 };// end of DenseBase<ValueT, LayoutXYZ>
159 
172 template<typename ValueT, MemoryLayout Layout = LayoutZYX>
173 class Dense : public DenseBase<ValueT, Layout>
174 {
175 public:
176  typedef ValueT ValueType;
178 
184  Dense(const CoordBBox& bbox) : BaseT(bbox) { this->init(); }
185 
192  Dense(const CoordBBox& bbox, const ValueT& value) : BaseT(bbox)
193  {
194  this->init();
195  this->fill(value);
196  }
197 
207  Dense(const CoordBBox& bbox, ValueT* data) : BaseT(bbox), mData(data)
208  {
209  if (BaseT::mBBox.empty()) {
210  OPENVDB_THROW(ValueError, "can't construct a dense grid with an empty bounding box");
211  }
212  }
213 
221  Dense(const Coord& dim, const Coord& min = Coord(0))
222  : BaseT(CoordBBox(min, min+dim.offsetBy(-1)))
223  {
224  this->init();
225  }
226 
228  static MemoryLayout memoryLayout() { return Layout; }
229 
232  inline ValueT* data() { return mData; }
233 
236  inline const ValueT* data() const { return mData; }
237 
240  inline const CoordBBox& bbox() const { return BaseT::mBBox; }
241 
243  inline Index64 valueCount() const { return BaseT::mBBox.volume(); }
244 
246  inline void setValue(size_t offset, const ValueT& value) { mData[offset] = value; }
247 
249  const ValueT& getValue(size_t offset) const { return mData[offset]; }
250 
253  inline void setValue(size_t i, size_t j, size_t k, const ValueT& value)
254  {
255  mData[BaseT::coordToOffset(i,j,k)] = value;
256  }
257 
260  inline const ValueT& getValue(size_t i, size_t j, size_t k) const
261  {
262  return mData[BaseT::coordToOffset(i,j,k)];
263  }
264 
267  inline void setValue(const Coord& xyz, const ValueT& value)
268  {
269  mData[this->coordToOffset(xyz)] = value;
270  }
271 
274  inline const ValueT& getValue(const Coord& xyz) const
275  {
276  return mData[this->coordToOffset(xyz)];
277  }
278 
280  inline void fill(const ValueT& value)
281  {
282  size_t size = this->valueCount();
283  ValueT* a = mData;
284  while(size--) *a++ = value;
285  }
286 
293  inline size_t coordToOffset(Coord xyz) const
294  {
295  assert(BaseT::mBBox.isInside(xyz));
296  return BaseT::coordToOffset(size_t(xyz[0]-BaseT::mBBox.min()[0]),
297  size_t(xyz[1]-BaseT::mBBox.min()[1]),
298  size_t(xyz[2]-BaseT::mBBox.min()[2]));
299  }
300 
302  inline Index64 memUsage() const
303  {
304  return sizeof(*this) + BaseT::mBBox.volume() * sizeof(ValueType);
305  }
306 
307 private:
308 
310  void init()
311  {
312  if (BaseT::mBBox.empty()) {
313  OPENVDB_THROW(ValueError, "can't construct a dense grid with an empty bounding box");
314  }
315  mArray.reset(new ValueT[BaseT::mBBox.volume()]);
316  mData = mArray.get();
317  }
318 
319  boost::shared_array<ValueT> mArray;
320  ValueT* mData;//raw c-style pointer to values
321 };// end of Dense
322 
324 
325 
332 template<typename _TreeT, typename _DenseT = Dense<typename _TreeT::ValueType> >
334 {
335 public:
336  typedef _DenseT DenseT;
337  typedef _TreeT TreeT;
338  typedef typename TreeT::ValueType ValueT;
339 
340  CopyToDense(const TreeT& tree, DenseT& dense)
341  : mRoot(&(tree.root())), mDense(&dense) {}
342 
343  void copy(bool serial = false) const
344  {
345  if (serial) {
346  mRoot->copyToDense(mDense->bbox(), *mDense);
347  } else {
348  tbb::parallel_for(mDense->bbox(), *this);
349  }
350  }
351 
353  void operator()(const CoordBBox& bbox) const
354  {
355  mRoot->copyToDense(bbox, *mDense);
356  }
357 
358 private:
359  const typename TreeT::RootNodeType* mRoot;
360  DenseT* mDense;
361 };// CopyToDense
362 
363 
364 // Convenient wrapper function for the CopyToDense class
365 template<typename DenseT, typename GridOrTreeT>
366 void
367 copyToDense(const GridOrTreeT& sparse, DenseT& dense, bool serial)
368 {
369  typedef TreeAdapter<GridOrTreeT> Adapter;
370  typedef typename Adapter::TreeType TreeT;
371 
372  CopyToDense<TreeT, DenseT> op(Adapter::constTree(sparse), dense);
373  op.copy(serial);
374 }
375 
376 
378 
379 
389 template<typename _TreeT, typename _DenseT = Dense<typename _TreeT::ValueType> >
391 {
392 public:
393  typedef _DenseT DenseT;
394  typedef _TreeT TreeT;
395  typedef typename TreeT::ValueType ValueT;
396  typedef typename TreeT::LeafNodeType LeafT;
398 
399  CopyFromDense(const DenseT& dense, TreeT& tree, const ValueT& tolerance)
400  : mDense(&dense),
401  mTree(&tree),
402  mBlocks(NULL),
403  mTolerance(tolerance),
404  mAccessor(tree.empty() ? NULL : new AccessorT(tree))
405  {
406  }
408  : mDense(other.mDense),
409  mTree(other.mTree),
410  mBlocks(other.mBlocks),
411  mTolerance(other.mTolerance),
412  mAccessor(other.mAccessor.get() == NULL ? NULL : new AccessorT(*mTree))
413  {
414  }
415 
417  void copy(bool serial = false)
418  {
419  mBlocks = new std::vector<Block>();
420  const CoordBBox& bbox = mDense->bbox();
421  // Pre-process: Construct a list of blocks alligned with (potential) leaf nodes
422  for (CoordBBox sub=bbox; sub.min()[0] <= bbox.max()[0]; sub.min()[0] = sub.max()[0] + 1) {
423  for (sub.min()[1] = bbox.min()[1]; sub.min()[1] <= bbox.max()[1];
424  sub.min()[1] = sub.max()[1] + 1)
425  {
426  for (sub.min()[2] = bbox.min()[2]; sub.min()[2] <= bbox.max()[2];
427  sub.min()[2] = sub.max()[2] + 1)
428  {
429  sub.max() = Coord::minComponent(bbox.max(),
430  (sub.min()&(~(LeafT::DIM-1u))).offsetBy(LeafT::DIM-1u));
431  mBlocks->push_back(Block(sub));
432  }
433  }
434  }
435 
436  // Multi-threaded process: Convert dense grid into leaf nodes and tiles
437  if (serial) {
438  (*this)(tbb::blocked_range<size_t>(0, mBlocks->size()));
439  } else {
440  tbb::parallel_for(tbb::blocked_range<size_t>(0, mBlocks->size()), *this);
441  }
442 
443  // Post-process: Insert leaf nodes and tiles into the tree, and prune the tiles only!
444  tree::ValueAccessor<TreeT> acc(*mTree);
445  for (size_t m=0, size = mBlocks->size(); m<size; ++m) {
446  Block& block = (*mBlocks)[m];
447  if (block.leaf) {
448  acc.addLeaf(block.leaf);
449  } else if (block.tile.second) {//only background tiles are inactive
450  acc.addTile(1, block.bbox.min(), block.tile.first, true);//leaf tile
451  }
452  }
453  delete mBlocks;
454  mBlocks = NULL;
455 
456  mTree->root().pruneTiles(mTolerance);
457  }
458 
461  void operator()(const tbb::blocked_range<size_t> &r) const
462  {
463  assert(mBlocks);
464  LeafT* leaf = new LeafT();
465 
466  for (size_t m=r.begin(), n=0, end = r.end(); m != end; ++m, ++n) {
467 
468  Block& block = (*mBlocks)[m];
469  const CoordBBox &bbox = block.bbox;
470 
471  if (mAccessor.get() == NULL) {//i.e. empty target tree
472  leaf->fill(mTree->background(), false);
473  } else {//account for existing leaf nodes in the target tree
474  if (const LeafT* target = mAccessor->probeConstLeaf(bbox.min())) {
475  (*leaf) = (*target);
476  } else {
477  ValueT value = zeroVal<ValueT>();
478  bool state = mAccessor->probeValue(bbox.min(), value);
479  leaf->fill(value, state);
480  }
481  }
482 
483  leaf->copyFromDense(bbox, *mDense, mTree->background(), mTolerance);
484 
485  if (!leaf->isConstant(block.tile.first, block.tile.second, mTolerance)) {
486  leaf->setOrigin(bbox.min() & (~(LeafT::DIM - 1)));
487  block.leaf = leaf;
488  leaf = new LeafT();
489  }
490  }// loop over blocks
491 
492  delete leaf;
493  }
494 
495 private:
496  struct Block {
497  CoordBBox bbox;
498  LeafT* leaf;
499  std::pair<ValueT, bool> tile;
500  Block(const CoordBBox& b) : bbox(b), leaf(NULL) {}
501  };
502 
503  const DenseT* mDense;
504  TreeT* mTree;
505  std::vector<Block>* mBlocks;
506  ValueT mTolerance;
507  boost::scoped_ptr<AccessorT> mAccessor;
508 };// CopyFromDense
509 
510 
511 // Convenient wrapper function for the CopyFromDense class
512 template<typename DenseT, typename GridOrTreeT>
513 void
514 copyFromDense(const DenseT& dense, GridOrTreeT& sparse,
515  const typename GridOrTreeT::ValueType& tolerance, bool serial)
516 {
517  typedef TreeAdapter<GridOrTreeT> Adapter;
518  typedef typename Adapter::TreeType TreeT;
519 
520  CopyFromDense<TreeT, DenseT> op(dense, Adapter::tree(sparse), tolerance);
521  op.copy(serial);
522 }
523 
524 } // namespace tools
525 } // namespace OPENVDB_VERSION_NAME
526 } // namespace openvdb
527 
528 #endif // OPENVDB_TOOLS_DENSE_HAS_BEEN_INCLUDED
529 
530 // Copyright (c) 2012-2013 DreamWorks Animation LLC
531 // All rights reserved. This software is distributed under the
532 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
static MemoryLayout memoryLayout()
Return the memory layout for this grid (see above for definitions).
Definition: Dense.h:228
Index64 memUsage() const
Return the memory footprint of this Dense grid in bytes.
Definition: Dense.h:302
void copy(bool serial=false) const
Definition: Dense.h:343
size_t xStride() const
Return the stride of the array in the x direction ( = dimY*dimZ).
Definition: Dense.h:110
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:328
OPENVDB_API Hermite min(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
Index64 valueCount() const
Return the number of voxels contained in this grid.
Definition: Dense.h:243
tree::ValueAccessor< TreeT > AccessorT
Definition: Dense.h:397
Copy the values from a dense grid into an OpenVDB tree.
Definition: Dense.h:390
size_t yStride() const
Return the stride of the array in the y direction ( = dimX).
Definition: Dense.h:146
static size_t zStride()
Return the stride of the array in the z direction ( = 1).
Definition: Dense.h:118
void operator()(const tbb::blocked_range< size_t > &r) const
Public method called by tbb::parallel_for.
Definition: Dense.h:461
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
Definition: Exceptions.h:88
TreeT::ValueType ValueT
Definition: Dense.h:395
Dense(const CoordBBox &bbox, ValueT *data)
Construct a dense grid that wraps an external array.
Definition: Dense.h:207
void setValue(size_t offset, const ValueT &value)
Set the value of the voxel at the given array offset.
Definition: Dense.h:246
DenseBase(const CoordBBox &bbox)
Protected constructor so as to prevent direct instantiation.
Definition: Dense.h:122
ValueT * data()
Return a raw pointer to this grid&#39;s value array.
Definition: Dense.h:232
TreeT::ValueType ValueT
Definition: Dense.h:338
const ValueT * data() const
Return a raw pointer to this grid&#39;s value array.
Definition: Dense.h:236
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:253
CopyFromDense(const DenseT &dense, TreeT &tree, const ValueT &tolerance)
Definition: Dense.h:399
const CoordBBox mBBox
Definition: Dense.h:156
const CoordBBox & bbox() const
Return the bounding box of the signed index domain of this grid.
Definition: Dense.h:240
Copy an OpenVDB tree into an existing dense grid.
Definition: Dense.h:333
const CoordBBox mBBox
Definition: Dense.h:124
Vec2< T > minComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise minimum of the two vectors.
Definition: Vec2.h:482
DenseBase(const CoordBBox &bbox)
Protected constructor so as to prevent direct instantiation.
Definition: Dense.h:154
size_t zStride() const
Return the stride of the array in the y direction ( = dimX*dimY).
Definition: Dense.h:150
size_t coordToOffset(Coord xyz) const
Return the linear offset into this grid&#39;s value array given by the specified signed coordinates...
Definition: Dense.h:293
void copy(bool serial=false)
Copy values from the dense grid to the sparse tree.
Definition: Dense.h:417
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:336
void fill(const ValueT &value)
Fill this grid with a constant value.
Definition: Dense.h:280
size_t coordToOffset(size_t i, size_t j, size_t k) const
Return the linear offset into this grid&#39;s value array given by unsigned coordinates (i...
Definition: Dense.h:106
#define OPENVDB_VERSION_NAME
Definition: version.h:45
CopyToDense(const TreeT &tree, DenseT &dense)
Definition: Dense.h:340
Dense is a simple dense grid API used by the CopyToDense and CopyFromDense classes defined below...
Definition: Dense.h:173
uint64_t Index64
Definition: Types.h:55
DenseBase< ValueT, Layout > BaseT
Definition: Dense.h:177
_DenseT DenseT
Definition: Dense.h:393
Definition: Dense.h:89
MemoryLayout
Definition: Dense.h:89
void setValue(const Coord &xyz, const ValueT &value)
Set the value of the voxel at the given signed coordinates.
Definition: Dense.h:267
void copyToDense(const GridOrTreeT &sparse, DenseT &dense, bool serial=false)
Populate a dense grid with the values of voxels from a sparse grid, where the sparse grid intersects ...
Definition: Dense.h:367
Base class for Dense which is defined below.
Definition: Dense.h:94
void operator()(const CoordBBox &bbox) const
Public method called by tbb::parallel_for.
Definition: Dense.h:353
_TreeT TreeT
Definition: Dense.h:394
size_t coordToOffset(size_t i, size_t j, size_t k) const
Return the linear offset into this grid&#39;s value array given by unsigned coordinates (i...
Definition: Dense.h:138
_TreeT TreeT
Definition: Dense.h:337
Dense(const CoordBBox &bbox)
Construct a dense grid with a given range of coordinates.
Definition: Dense.h:184
CopyFromDense(const CopyFromDense &other)
Definition: Dense.h:407
static size_t xStride()
Return the stride of the array in the x direction ( = 1).
Definition: Dense.h:142
TreeT::LeafNodeType LeafT
Definition: Dense.h:396
_DenseT DenseT
Definition: Dense.h:336
size_t yStride() const
Return the stride of the array in the y direction ( = dimZ).
Definition: Dense.h:114
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:67
This adapter allows code that is templated on a Tree type to accept either a Tree type or a Grid type...
Definition: Grid.h:823
const ValueT & getValue(const Coord &xyz) const
Return the value of the voxel at the given signed coordinates.
Definition: Dense.h:274
Definition: Dense.h:89
const ValueT & getValue(size_t offset) const
Return the value of the voxel at the given array offset.
Definition: Dense.h:249
ValueT ValueType
Definition: Dense.h:176
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:260
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:514
Dense(const CoordBBox &bbox, const ValueT &value)
Construct a dense grid with a given range of coordinates and initial value.
Definition: Dense.h:192