OpenVDB  2.0.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 
51 // Forward declaration (see definition below)
52 template<typename ValueT> class Dense;
53 
54 
60 template<typename DenseT, typename GridOrTreeT>
61 void
63  const GridOrTreeT& sparse,
64  DenseT& dense,
65  bool serial = false);
66 
67 
74 template<typename DenseT, typename GridOrTreeT>
75 void
77  const DenseT& dense,
78  GridOrTreeT& sparse,
79  const typename GridOrTreeT::ValueType& tolerance,
80  bool serial = false);
81 
82 
84 
85 
97 template<typename ValueT>
98 class Dense
99 {
100 public:
101  typedef ValueT ValueType;
102 
108  Dense(const CoordBBox& bbox)
109  : mBBox(bbox), mY(bbox.dim()[2]), mX(mY*bbox.dim()[1])
110  {
111  this->initArray();
112  }
113 
120  Dense(const CoordBBox& bbox, const ValueT& value)
121  : mBBox(bbox), mY(bbox.dim()[2]), mX(mY*bbox.dim()[1])
122  {
123  this->initArray();
124  this->fill(value);
125  }
126 
136  Dense(const CoordBBox& bbox, ValueT* data)
137  : mBBox(bbox), mData(data), mY(mBBox.dim()[2]), mX(mY*mBBox.dim()[1])
138  {
139  if (mBBox.empty()) {
140  OPENVDB_THROW(ValueError, "can't construct a dense grid with an empty bounding box");
141  }
142  }
143 
151  Dense(const Coord& dim, const Coord& min = Coord(0))
152  : mBBox(min, min+dim.offsetBy(-1)), mY(mBBox.dim()[2]), mX(mY*mBBox.dim()[1])
153  {
154  this->initArray();
155  }
156 
159  ValueT* data() { return mData; }
160 
163  const ValueT* data() const { return mData; }
164 
167  const CoordBBox& bbox() const { return mBBox; }
168 
171  size_t xStride() const { return mX; }
172 
175  size_t yStride() const { return mY; }
176 
178  Index64 valueCount() const { return mBBox.volume(); }
179 
181  void setValue(size_t offset, const ValueT& value) { mData[offset] = value; }
182 
184  const ValueT& getValue(size_t offset) const { return mData[offset]; }
185 
188  void setValue(size_t i, size_t j, size_t k, const ValueT& value)
189  {
190  mData[this->coordToOffset(i,j,k)] = value;
191  }
192 
195  const ValueT& getValue(size_t i, size_t j, size_t k) const
196  {
197  return mData[this->coordToOffset(i,j,k)];
198  }
199 
202  void setValue(const Coord& xyz, const ValueT& value)
203  {
204  mData[this->coordToOffset(xyz)] = value;
205  }
206 
209  const ValueT& getValue(const Coord& xyz) const
210  {
211  return mData[this->coordToOffset(xyz)];
212  }
213 
215  void fill(const ValueT& value)
216  {
217  size_t size = this->valueCount();
218  ValueT* a = mData;
219  while(size--) *a++ = value;
220  }
221 
228  inline size_t coordToOffset(size_t i, size_t j, size_t k) const
229  {
230  return k + j*mY + i*mX;
231  }
232 
239  inline size_t coordToOffset(Coord xyz) const
240  {
241  assert(mBBox.isInside(xyz));
242  return this->coordToOffset(size_t(xyz[0]-mBBox.min()[0]),
243  size_t(xyz[1]-mBBox.min()[1]),
244  size_t(xyz[2]-mBBox.min()[2]));
245  }
246 
247  Index64 memUsage() const{ return sizeof(*this) + mBBox.volume() * sizeof(ValueType); }
248 
249 private:
250  void initArray()
251  {
252  if (mBBox.empty()) {
253  OPENVDB_THROW(ValueError, "can't construct a dense grid with an empty bounding box");
254  }
255  mArray.reset(new ValueT[mBBox.volume()]);
256  mData = mArray.get();
257  }
258 
259  const CoordBBox mBBox;//signed coordinates of the domain represented by the grid
260  boost::shared_array<ValueT> mArray;
261  ValueT* mData;//raw c-style pointer to values
262  const size_t mY, mX;//strides in x and y (by design it's 1 in z)
263 };// end of Dense
264 
265 
267 
268 
275 template<typename _TreeT, typename _DenseT = Dense<typename _TreeT::ValueType> >
277 {
278 public:
279  typedef _DenseT DenseT;
280  typedef _TreeT TreeT;
281  typedef typename TreeT::ValueType ValueT;
282 
283  CopyToDense(const TreeT& tree, DenseT& dense)
284  : mRoot(&(tree.root())), mDense(&dense) {}
285 
286  void copy(bool serial = false) const
287  {
288  if (serial) {
289  mRoot->copyToDense(mDense->bbox(), *mDense);
290  } else {
291  tbb::parallel_for(mDense->bbox(), *this);
292  }
293  }
294 
296  void operator()(const CoordBBox& bbox) const
297  {
298  mRoot->copyToDense(bbox, *mDense);
299  }
300 
301 private:
302  const typename TreeT::RootNodeType* mRoot;
303  DenseT* mDense;
304 };// CopyToDense
305 
306 
307 // Convenient wrapper function for the CopyToDense class
308 template<typename DenseT, typename GridOrTreeT>
309 void
310 copyToDense(const GridOrTreeT& sparse, DenseT& dense, bool serial)
311 {
312  typedef TreeAdapter<GridOrTreeT> Adapter;
313  typedef typename Adapter::TreeType TreeT;
314 
315  CopyToDense<TreeT, DenseT> op(Adapter::constTree(sparse), dense);
316  op.copy(serial);
317 }
318 
319 
321 
322 
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  typedef typename TreeT::LeafNodeType LeafT;
341 
342  CopyFromDense(const DenseT& dense, TreeT& tree, const ValueT& tolerance)
343  : mDense(&dense),
344  mTree(&tree),
345  mBlocks(NULL),
346  mTolerance(tolerance),
347  mAccessor(tree.empty() ? NULL : new AccessorT(tree))
348  {
349  }
351  : mDense(other.mDense),
352  mTree(other.mTree),
353  mBlocks(other.mBlocks),
354  mTolerance(other.mTolerance),
355  mAccessor(other.mAccessor.get() == NULL ? NULL : new AccessorT(*mTree))
356  {
357  }
358 
360  void copy(bool serial = false)
361  {
362  mBlocks = new std::vector<Block>();
363  const CoordBBox& bbox = mDense->bbox();
364  // Pre-process: Construct a list of blocks alligned with (potential) leaf nodes
365  for (CoordBBox sub=bbox; sub.min()[0] <= bbox.max()[0]; sub.min()[0] = sub.max()[0] + 1) {
366  for (sub.min()[1] = bbox.min()[1]; sub.min()[1] <= bbox.max()[1];
367  sub.min()[1] = sub.max()[1] + 1)
368  {
369  for (sub.min()[2] = bbox.min()[2]; sub.min()[2] <= bbox.max()[2];
370  sub.min()[2] = sub.max()[2] + 1)
371  {
372  sub.max() = Coord::minComponent(bbox.max(),
373  (sub.min()&(~(LeafT::DIM-1u))).offsetBy(LeafT::DIM-1u));
374  mBlocks->push_back(Block(sub));
375  }
376  }
377  }
378 
379  // Multi-threaded process: Convert dense grid into leaf nodes and tiles
380  if (serial) {
381  (*this)(tbb::blocked_range<size_t>(0, mBlocks->size()));
382  } else {
383  tbb::parallel_for(tbb::blocked_range<size_t>(0, mBlocks->size()), *this);
384  }
385 
386  // Post-process: Insert leaf nodes and tiles into the tree, and prune the tiles only!
387  tree::ValueAccessor<TreeT> acc(*mTree);
388  for (size_t m=0, size = mBlocks->size(); m<size; ++m) {
389  Block& block = (*mBlocks)[m];
390  if (block.leaf) {
391  acc.addLeaf(block.leaf);
392  } else if (block.tile.second) {//only background tiles are inactive
393  acc.addTile(1, block.bbox.min(), block.tile.first, true);//leaf tile
394  }
395  }
396  delete mBlocks;
397  mBlocks = NULL;
398 
399  mTree->root().pruneTiles(mTolerance);
400  }
401 
404  void operator()(const tbb::blocked_range<size_t> &r) const
405  {
406  assert(mBlocks);
407  LeafT* leaf = new LeafT();
408 
409  for (size_t m=r.begin(), n=0, end = r.end(); m != end; ++m, ++n) {
410 
411  Block& block = (*mBlocks)[m];
412  const CoordBBox &bbox = block.bbox;
413 
414  if (mAccessor.get() == NULL) {//i.e. empty target tree
415  leaf->fill(mTree->background(), false);
416  } else {//account for existing leaf nodes in the target tree
417  if (const LeafT* target = mAccessor->probeConstLeaf(bbox.min())) {
418  (*leaf) = (*target);
419  } else {
420  ValueT value = zeroVal<ValueT>();
421  bool state = mAccessor->probeValue(bbox.min(), value);
422  leaf->fill(value, state);
423  }
424  }
425 
426  leaf->copyFromDense(bbox, *mDense, mTree->background(), mTolerance);
427 
428  if (!leaf->isConstant(block.tile.first, block.tile.second, mTolerance)) {
429  leaf->setOrigin(bbox.min() & (~(LeafT::DIM - 1)));
430  block.leaf = leaf;
431  leaf = new LeafT();
432  }
433  }// loop over blocks
434 
435  delete leaf;
436  }
437 
438 private:
439  struct Block {
440  CoordBBox bbox;
441  LeafT* leaf;
442  std::pair<ValueT, bool> tile;
443  Block(const CoordBBox& b) : bbox(b), leaf(NULL) {}
444  };
445 
446  const DenseT* mDense;
447  TreeT* mTree;
448  std::vector<Block>* mBlocks;
449  ValueT mTolerance;
450  boost::scoped_ptr<AccessorT> mAccessor;
451 };// CopyFromDense
452 
453 
454 // Convenient wrapper function for the CopyFromDense class
455 template<typename DenseT, typename GridOrTreeT>
456 void
457 copyFromDense(const DenseT& dense, GridOrTreeT& sparse,
458  const typename GridOrTreeT::ValueType& tolerance, bool serial)
459 {
460  typedef TreeAdapter<GridOrTreeT> Adapter;
461  typedef typename Adapter::TreeType TreeT;
462 
463  CopyFromDense<TreeT, DenseT> op(dense, Adapter::tree(sparse), tolerance);
464  op.copy(serial);
465 }
466 
467 } // namespace tools
468 } // namespace OPENVDB_VERSION_NAME
469 } // namespace openvdb
470 
471 #endif // OPENVDB_TOOLS_DENSE_HAS_BEEN_INCLUDED
472 
473 // Copyright (c) 2012-2013 DreamWorks Animation LLC
474 // All rights reserved. This software is distributed under the
475 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
CopyToDense(const TreeT &tree, DenseT &dense)
Definition: Dense.h:283
Copy an OpenVDB tree into an existing dense grid.
Definition: Dense.h:276
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
Dense(const CoordBBox &bbox)
Construct a dense grid with a given range of coordinates.
Definition: Dense.h:108
void operator()(const tbb::blocked_range< size_t > &r) const
Public method called by tbb::parallel_for.
Definition: Dense.h:404
void fill(const ValueT &value)
Fill this grid with a constant value.
Definition: Dense.h:215
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
TreeT::ValueType ValueT
Definition: Dense.h:338
tree::ValueAccessor< TreeT > AccessorT
Definition: Dense.h:340
void setValue(const Coord &xyz, const ValueT &value)
Set the value of the voxel at the given signed coordinates.
Definition: Dense.h:202
_TreeT TreeT
Definition: Dense.h:280
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
_DenseT DenseT
Definition: Dense.h:279
const ValueT & getValue(const Coord &xyz) const
Return the value of the voxel at the given signed coordinates.
Definition: Dense.h:209
Vec2< T > minComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise minimum of the two vectors.
Definition: Vec2.h:482
Index64 memUsage() const
Definition: Dense.h:247
const ValueT & getValue(size_t offset) const
Return the value of the voxel at the given array offset.
Definition: Dense.h:184
CopyFromDense(const DenseT &dense, TreeT &tree, const ValueT &tolerance)
Definition: Dense.h:342
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
Dense(const CoordBBox &bbox, const ValueT &value)
Construct a dense grid with a given range of coordinates and initial value.
Definition: Dense.h:120
void copy(bool serial=false)
Copy values from the dense grid to the sparse tree.
Definition: Dense.h:360
#define OPENVDB_VERSION_NAME
Definition: version.h:45
Copy the values from a dense grid into an OpenVDB tree.
Definition: Dense.h:333
Dense is a simple dense grid API used by the CopyToDense and CopyFromDense classes defined below...
Definition: Dense.h:52
Index64 valueCount() const
Return the number of voxels contained in this grid.
Definition: Dense.h:178
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:457
_DenseT DenseT
Definition: Dense.h:336
OPENVDB_API Hermite min(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
ValueT ValueType
Definition: Dense.h:101
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:195
void setValue(size_t offset, const ValueT &value)
Set the value of the voxel at the given array offset.
Definition: Dense.h:181
size_t xStride() const
Return the stride of the array in the x direction ( = dimY*dimZ).
Definition: Dense.h:171
TreeT::ValueType ValueT
Definition: Dense.h:281
CopyFromDense(const CopyFromDense &other)
Definition: Dense.h:350
void copy(bool serial=false) const
Definition: Dense.h:286
size_t yStride() const
Return the stride of the array in the y direction ( = dimZ).
Definition: Dense.h:175
_TreeT TreeT
Definition: Dense.h:337
const ValueT * data() const
Return a raw pointer to this grid&#39;s value array.
Definition: Dense.h:163
Definition: Exceptions.h:88
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:188
TreeT::LeafNodeType LeafT
Definition: Dense.h:339
ValueT * data()
Return a raw pointer to this grid&#39;s value array.
Definition: Dense.h:159
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:310
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:56
Dense(const CoordBBox &bbox, ValueT *data)
Construct a dense grid that wraps an external array.
Definition: Dense.h:136
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:228
uint64_t Index64
Definition: Types.h:55
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:239
const CoordBBox & bbox() const
Return the bounding box of the signed index domain of this grid.
Definition: Dense.h:167
void operator()(const CoordBBox &bbox) const
Public method called by tbb::parallel_for.
Definition: Dense.h:296