OpenVDB  5.2.0
PointMove.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2018 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 
58 
59 #ifndef OPENVDB_POINTS_POINT_MOVE_HAS_BEEN_INCLUDED
60 #define OPENVDB_POINTS_POINT_MOVE_HAS_BEEN_INCLUDED
61 
62 #include <openvdb/openvdb.h>
63 
64 #include <openvdb/points/PointDataGrid.h>
65 #include <openvdb/points/PointMask.h>
66 
67 #include <tbb/concurrent_vector.h>
68 
69 #include <algorithm>
70 #include <iterator> // for std::begin(), std::end()
71 #include <map>
72 #include <numeric> // for std::iota()
73 #include <tuple>
74 #include <unordered_map>
75 #include <vector>
76 
77 class TestPointMove;
78 
79 
80 namespace openvdb {
82 namespace OPENVDB_VERSION_NAME {
83 namespace points {
84 
85 // dummy object for future use
86 namespace future { struct Advect { }; }
87 
88 
95 template <typename PointDataGridT, typename DeformerT, typename FilterT = NullFilter>
96 inline void movePoints(PointDataGridT& points,
97  DeformerT& deformer,
98  const FilterT& filter = NullFilter(),
99  future::Advect* objectNotInUse = nullptr,
100  bool threaded = true);
101 
102 
110 template <typename PointDataGridT, typename DeformerT, typename FilterT = NullFilter>
111 inline void movePoints(PointDataGridT& points,
112  const math::Transform& transform,
113  DeformerT& deformer,
114  const FilterT& filter = NullFilter(),
115  future::Advect* objectNotInUse = nullptr,
116  bool threaded = true);
117 
118 
120 template <typename T>
122 {
123 public:
124  using Vec3T = typename math::Vec3<T>;
125  using LeafVecT = std::vector<Vec3T>;
126  using LeafMapT = std::unordered_map<Index, Vec3T>;
127 
128  // Internal data cache to allow the deformer to offer light-weight copying
129  struct Cache
130  {
131  struct Leaf
132  {
134  void clear() {
135  vecData.clear();
136  mapData.clear();
137  totalSize = 0;
138  }
139 
142  Index totalSize = 0;
143  }; // struct Leaf
144 
145  std::vector<Leaf> leafs;
146  }; // struct Cache
147 
149  explicit CachedDeformer(Cache& cache);
150 
156  template <typename PointDataGridT, typename DeformerT, typename FilterT>
157  void evaluate(PointDataGridT& grid, DeformerT& deformer, const FilterT& filter,
158  bool threaded = true);
159 
162  template <typename LeafT>
163  void reset(const LeafT& leaf, size_t idx);
164 
166  template <typename IndexIterT>
167  void apply(Vec3d& position, const IndexIterT& iter) const;
168 
169 private:
170  friend class ::TestPointMove;
171 
172  Cache& mCache;
173  LeafVecT mLocalLeafVec;
174  const LeafVecT* mLeafVec = nullptr;
175  const LeafMapT* mLeafMap = nullptr;
176 }; // class CachedDeformer
177 
178 
180 
181 
182 namespace point_move_internal {
183 
184 
185 using IndexTriple = std::tuple<Index, Index, Index>;
186 using IndexTripleArray = tbb::concurrent_vector<IndexTriple>;
187 using GlobalPointIndexMap = std::vector<IndexTripleArray>;
188 
189 using IndexPair = std::pair<Index, Index>;
190 using IndexPairArray = std::vector<IndexPair>;
191 using LocalPointIndexMap = std::vector<IndexPairArray>;
192 
193 using IndexArray = std::vector<Index>;
194 using OffsetMap = std::vector<IndexArray>;
195 
196 // TODO: The following infrastructure - ArrayProcessor, PerformTypedMoveOp, processTypedArray()
197 // is required to improve AttributeArray copying performance beyond using the virtual function
198 // AttributeArray::set(Index, AttributeArray&, Index), however an ABI=6+ addition to AttributeArray
199 // could eliminate this cost for the typical case where ValueType and CodecType are the same in
200 // source and target arrays, as they are here.
201 
202 
204 template<typename ValueType, typename OpType>
206  static inline void call(OpType& op, const AttributeArray& array) {
207 #ifdef _MSC_VER
208  op.operator()<ValueType>(array);
209 #else
210  op.template operator()<ValueType>(array);
211 #endif
212  }
213 };
214 
217 template<typename ArrayType, typename OpType>
218 bool
219 processTypedArray(const ArrayType& array, OpType& op)
220 {
221  using namespace openvdb;
222  using namespace openvdb::math;
223  if (array.template hasValueType<bool>()) ArrayProcessor<bool, OpType>::call(op, array);
224  else if (array.template hasValueType<int16_t>()) ArrayProcessor<int16_t, OpType>::call(op, array);
225  else if (array.template hasValueType<int32_t>()) ArrayProcessor<int32_t, OpType>::call(op, array);
226  else if (array.template hasValueType<int64_t>()) ArrayProcessor<int64_t, OpType>::call(op, array);
227  else if (array.template hasValueType<float>()) ArrayProcessor<float, OpType>::call(op, array);
228  else if (array.template hasValueType<double>()) ArrayProcessor<double, OpType>::call(op, array);
229  else if (array.template hasValueType<Vec3<int32_t>>()) ArrayProcessor<Vec3<int32_t>, OpType>::call(op, array);
230  else if (array.template hasValueType<Vec3<float>>()) ArrayProcessor<Vec3<float>, OpType>::call(op, array);
231  else if (array.template hasValueType<Vec3<double>>()) ArrayProcessor<Vec3<double>, OpType>::call(op, array);
232  else if (array.template hasValueType<GroupType>()) ArrayProcessor<GroupType, OpType>::call(op, array);
233  else if (array.template hasValueType<StringIndexType>()) ArrayProcessor<StringIndexType, OpType>::call(op, array);
234  else if (array.template hasValueType<Mat3<float>>()) ArrayProcessor<Mat3<float>, OpType>::call(op, array);
235  else if (array.template hasValueType<Mat3<double>>()) ArrayProcessor<Mat3<double>, OpType>::call(op, array);
236  else if (array.template hasValueType<Mat4<float>>()) ArrayProcessor<Mat4<float>, OpType>::call(op, array);
237  else if (array.template hasValueType<Mat4<double>>()) ArrayProcessor<Mat4<double>, OpType>::call(op, array);
238  else if (array.template hasValueType<Quat<float>>()) ArrayProcessor<Quat<float>, OpType>::call(op, array);
239  else if (array.template hasValueType<Quat<double>>()) ArrayProcessor<Quat<double>, OpType>::call(op, array);
240  else return false;
241  return true;
242 }
243 
244 
247 {
248  using HandleArray = std::vector<AttributeHandle<int>::Ptr>;
249 
250  AttributeHandles(const size_t size)
251  : mHandles() { mHandles.reserve(size); }
252 
253  AttributeArray& getArray(const Index leafOffset)
254  {
255  auto* handle = reinterpret_cast<AttributeWriteHandle<int>*>(mHandles[leafOffset].get());
256  assert(handle);
257  return handle->array();
258  }
259 
260  const AttributeArray& getConstArray(const Index leafOffset) const
261  {
262  const auto* handle = mHandles[leafOffset].get();
263  assert(handle);
264  return handle->array();
265  }
266 
267  template <typename ValueT>
269  {
270  auto* handle = reinterpret_cast<AttributeHandle<ValueT>*>(mHandles[leafOffset].get());
271  assert(handle);
272  return *handle;
273  }
274 
275  template <typename ValueT>
277  {
278  auto* handle = reinterpret_cast<AttributeWriteHandle<ValueT>*>(mHandles[leafOffset].get());
279  assert(handle);
280  return *handle;
281  }
282 
285  {
287  : mHandles(handles) { }
288 
289  template<typename ValueT>
290  void operator()(const AttributeArray& array) const
291  {
292  auto* handleAsInt = reinterpret_cast<AttributeHandle<int>*>(
293  new AttributeHandle<ValueT>(array));
294  mHandles.emplace_back(handleAsInt);
295  }
296 
297  private:
298  HandleArray& mHandles;
299  }; // struct CacheHandleOp
300 
301  template <typename LeafRangeT>
302  void cache(const LeafRangeT& range, const Index attributeIndex)
303  {
304  using namespace openvdb::math;
305 
306  mHandles.clear();
307  CacheHandleOp op(mHandles);
308 
309  for (auto leaf = range.begin(); leaf; ++leaf) {
310  auto& array = leaf->attributeArray(attributeIndex);
311  processTypedArray(array, op);
312  }
313  }
314 
315 private:
316  HandleArray mHandles;
317 }; // struct AttributeHandles
318 
319 
320 template <typename DeformerT, typename TreeT, typename FilterT>
322 {
323  using LeafT = typename TreeT::LeafNodeType;
324  using LeafArrayT = std::vector<LeafT*>;
326 
327  BuildMoveMapsOp(const DeformerT& deformer,
328  GlobalPointIndexMap& globalMoveLeafMap,
329  LocalPointIndexMap& localMoveLeafMap,
330  const std::map<Coord, Index>& targetLeafMap,
331  const math::Transform& targetTransform,
332  const math::Transform& sourceTransform,
333  const FilterT& filter)
334  : mDeformer(deformer)
335  , mGlobalMoveLeafMap(globalMoveLeafMap)
336  , mLocalMoveLeafMap(localMoveLeafMap)
337  , mTargetLeafMap(targetLeafMap)
338  , mTargetTransform(targetTransform)
339  , mSourceTransform(sourceTransform)
340  , mFilter(filter) { }
341 
342  void operator()(LeafT& leaf, size_t idx) const
343  {
344  DeformerT deformer(mDeformer);
345  deformer.reset(leaf, idx);
346 
347  // determine source leaf node origin and offset in the source leaf vector
348 
349  Coord sourceLeafOrigin = leaf.origin();
350 
351  auto sourceHandle = AttributeWriteHandle<Vec3f>::create(leaf.attributeArray("P"));
352 
353  for (auto iter = leaf.beginIndexOn(mFilter); iter; iter++) {
354 
355  const bool useIndexSpace = DeformerTraits<DeformerT>::IndexSpace;
356 
357  // extract index-space position and apply index-space deformation (if applicable)
358 
359  Vec3d positionIS = sourceHandle->get(*iter) + iter.getCoord().asVec3d();
360  if (useIndexSpace) {
361  deformer.apply(positionIS, iter);
362  }
363 
364  // transform to world-space position and apply world-space deformation (if applicable)
365 
366  Vec3d positionWS = mSourceTransform.indexToWorld(positionIS);
367  if (!useIndexSpace) {
368  deformer.apply(positionWS, iter);
369  }
370 
371  // transform to index-space position of target grid
372 
373  positionIS = mTargetTransform.worldToIndex(positionWS);
374 
375  // determine target voxel and offset
376 
377  Coord targetVoxel = Coord::round(positionIS);
378  Index targetOffset = LeafT::coordToOffset(targetVoxel);
379 
380  // set new local position in source transform space (if point has been deformed)
381 
382  Vec3d voxelPosition(positionIS - targetVoxel.asVec3d());
383  sourceHandle->set(*iter, voxelPosition);
384 
385  // determine target leaf node origin and offset in the target leaf vector
386 
387  Coord targetLeafOrigin = targetVoxel & ~(LeafT::DIM - 1);
388  assert(mTargetLeafMap.find(targetLeafOrigin) != mTargetLeafMap.end());
389  const Index targetLeafOffset(mTargetLeafMap.at(targetLeafOrigin));
390 
391  // insert into move map based on whether point ends up in a new leaf node or not
392 
393  if (targetLeafOrigin == sourceLeafOrigin) {
394  mLocalMoveLeafMap[targetLeafOffset].emplace_back(targetOffset, *iter);
395  }
396  else {
397  mGlobalMoveLeafMap[targetLeafOffset].push_back(IndexTriple(idx,
398  targetOffset, *iter));
399  }
400  }
401  }
402 
403 private:
404  const DeformerT& mDeformer;
405  GlobalPointIndexMap& mGlobalMoveLeafMap;
406  LocalPointIndexMap& mLocalMoveLeafMap;
407  const std::map<Coord, Index>& mTargetLeafMap;
408  const math::Transform& mTargetTransform;
409  const math::Transform& mSourceTransform;
410  const FilterT& mFilter;
411 }; // struct BuildMoveMapsOp
412 
413 template <typename LeafT>
414 inline Index
415 indexOffsetFromVoxel(const Index voxelOffset, const LeafT& leaf, IndexArray& offsets)
416 {
417  // compute the target point index by summing the point index of the previous
418  // voxel with the current number of points added to this voxel, tracked by the
419  // offsets array
420 
421  Index targetOffset = Index(offsets[voxelOffset]++);
422  if (voxelOffset > 0) {
423  targetOffset += Index(leaf.getValue(voxelOffset - 1));
424  }
425  return targetOffset;
426 }
427 
428 template <typename TreeT>
430 {
431  using LeafT = typename TreeT::LeafNodeType;
432  using LeafArrayT = std::vector<LeafT*>;
434 
436  AttributeHandles& targetHandles,
437  AttributeHandles& sourceHandles,
438  const Index attributeIndex,
439  const GlobalPointIndexMap& moveLeafMap)
440  : mOffsetMap(offsetMap)
441  , mTargetHandles(targetHandles)
442  , mSourceHandles(sourceHandles)
443  , mAttributeIndex(attributeIndex)
444  , mMoveLeafMap(moveLeafMap) { }
445 
447  {
448  PerformTypedMoveOp(AttributeHandles& targetHandles, AttributeHandles& sourceHandles,
449  int targetOffset, const LeafT& targetLeaf,
450  IndexArray& offsets, const IndexTripleArray& indices)
451  : mTargetHandles(targetHandles)
452  , mSourceHandles(sourceHandles)
453  , mTargetOffset(targetOffset)
454  , mTargetLeaf(targetLeaf)
455  , mOffsets(offsets)
456  , mIndices(indices) { }
457 
458  template<typename ValueT>
459  void operator()(const AttributeArray&) const
460  {
461  auto& targetHandle = mTargetHandles.getWriteHandle<ValueT>(mTargetOffset);
462  targetHandle.expand();
463 
464  // build a sorted index vector that references the indices in order of their source
465  // leafs and voxels to ensure determinism in the resulting point orders
466 
467  std::vector<int> sortedIndices(mIndices.size());
468  std::iota(std::begin(sortedIndices), std::end(sortedIndices), 0);
469  std::sort(std::begin(sortedIndices), std::end(sortedIndices),
470  [&](int i, int j)
471  {
472  const Index& indexI0(std::get<0>(mIndices[i]));
473  const Index& indexJ0(std::get<0>(mIndices[j]));
474  if (indexI0 < indexJ0) return true;
475  if (indexI0 > indexJ0) return false;
476  return std::get<2>(mIndices[i]) < std::get<2>(mIndices[j]);
477  }
478  );
479 
480  for (const auto& index : sortedIndices) {
481  const auto& it = mIndices[index];
482  const auto& sourceHandle = mSourceHandles.getHandle<ValueT>(std::get<0>(it));
483  const Index targetIndex = indexOffsetFromVoxel(std::get<1>(it), mTargetLeaf, mOffsets);
484  for (Index i = 0; i < sourceHandle.stride(); i++) {
485  ValueT sourceValue = sourceHandle.get(std::get<2>(it), i);
486  targetHandle.set(targetIndex, i, sourceValue);
487  }
488  }
489  }
490 
491  private:
492  AttributeHandles& mTargetHandles;
493  AttributeHandles& mSourceHandles;
494  int mTargetOffset;
495  const LeafT& mTargetLeaf;
496  IndexArray& mOffsets;
497  const IndexTripleArray& mIndices;
498  }; // struct PerformTypedMoveOp
499 
500  void performMove(int targetOffset, const LeafT& targetLeaf,
501  IndexArray& offsets, const IndexTripleArray& indices) const
502  {
503  auto& targetArray = mTargetHandles.getArray(targetOffset);
504 
505  for (const auto& it : indices) {
506  const auto& sourceArray = mSourceHandles.getConstArray(std::get<0>(it));
507  const Index tgtOffset = indexOffsetFromVoxel(std::get<1>(it), targetLeaf, offsets);
508  targetArray.set(tgtOffset, sourceArray, std::get<2>(it));
509  }
510  }
511 
512  void operator()(LeafT& leaf, size_t aIdx) const
513  {
514  const Index idx = Index(aIdx);
515  const auto& moveIndices = mMoveLeafMap.at(idx);
516  if (moveIndices.empty()) return;
517 
518  // extract per-voxel offsets for this leaf
519 
520  auto& offsets = mOffsetMap[idx];
521 
522  const auto& array = leaf.constAttributeArray(mAttributeIndex);
523 
524  PerformTypedMoveOp op(mTargetHandles, mSourceHandles, idx, leaf, offsets, moveIndices);
525  if (!processTypedArray(array, op)) {
526  this->performMove(idx, leaf, offsets, moveIndices);
527  }
528  }
529 
530 private:
531  OffsetMap& mOffsetMap;
532  AttributeHandles& mTargetHandles;
533  AttributeHandles& mSourceHandles;
534  const Index mAttributeIndex;
535  const GlobalPointIndexMap& mMoveLeafMap;
536 }; // struct GlobalMovePointsOp
537 
538 template <typename TreeT>
540 {
541  using LeafT = typename TreeT::LeafNodeType;
542  using LeafArrayT = std::vector<LeafT*>;
544 
546  AttributeHandles& targetHandles,
547  const IndexArray& sourceIndices,
548  AttributeHandles& sourceHandles,
549  const Index attributeIndex,
550  const LocalPointIndexMap& moveLeafMap)
551  : mOffsetMap(offsetMap)
552  , mTargetHandles(targetHandles)
553  , mSourceIndices(sourceIndices)
554  , mSourceHandles(sourceHandles)
555  , mAttributeIndex(attributeIndex)
556  , mMoveLeafMap(moveLeafMap) { }
557 
559  {
560  PerformTypedMoveOp(AttributeHandles& targetHandles, AttributeHandles& sourceHandles,
561  int targetOffset, int sourceOffset, const LeafT& targetLeaf,
562  IndexArray& offsets, const IndexPairArray& indices)
563  : mTargetHandles(targetHandles)
564  , mSourceHandles(sourceHandles)
565  , mTargetOffset(targetOffset)
566  , mSourceOffset(sourceOffset)
567  , mTargetLeaf(targetLeaf)
568  , mOffsets(offsets)
569  , mIndices(indices) { }
570 
571  template<typename ValueT>
572  void operator()(const AttributeArray&) const
573  {
574  auto& targetHandle = mTargetHandles.getWriteHandle<ValueT>(mTargetOffset);
575  const auto& sourceHandle = mSourceHandles.getHandle<ValueT>(mSourceOffset);
576 
577  targetHandle.expand();
578 
579  for (const auto& it : mIndices) {
580  const Index targetIndex = indexOffsetFromVoxel(it.first, mTargetLeaf, mOffsets);
581  for (Index i = 0; i < sourceHandle.stride(); i++) {
582  ValueT sourceValue = sourceHandle.get(it.second, i);
583  targetHandle.set(targetIndex, i, sourceValue);
584  }
585  }
586  }
587 
588  private:
589  AttributeHandles& mTargetHandles;
590  AttributeHandles& mSourceHandles;
591  int mTargetOffset;
592  int mSourceOffset;
593  const LeafT& mTargetLeaf;
594  IndexArray& mOffsets;
595  const IndexPairArray& mIndices;
596  }; // struct PerformTypedMoveOp
597 
598  template <typename ValueT>
599  void performTypedMove(int sourceOffset, int targetOffset, const LeafT& targetLeaf,
600  IndexArray& offsets, const IndexPairArray& indices) const
601  {
602  auto& targetHandle = mTargetHandles.getWriteHandle<ValueT>(targetOffset);
603  const auto& sourceHandle = mSourceHandles.getHandle<ValueT>(sourceOffset);
604 
605  targetHandle.expand();
606 
607  for (const auto& it : indices) {
608  const Index tgtOffset = indexOffsetFromVoxel(it.first, targetLeaf, offsets);
609  for (Index i = 0; i < sourceHandle.stride(); i++) {
610  ValueT sourceValue = sourceHandle.get(it.second, i);
611  targetHandle.set(tgtOffset, i, sourceValue);
612  }
613  }
614  }
615 
616  void performMove(int targetOffset, int sourceOffset, const LeafT& targetLeaf,
617  IndexArray& offsets, const IndexPairArray& indices) const
618  {
619  auto& targetArray = mTargetHandles.getArray(targetOffset);
620  const auto& sourceArray = mSourceHandles.getConstArray(sourceOffset);
621 
622  for (const auto& it : indices) {
623  const Index tgtOffset = indexOffsetFromVoxel(it.first, targetLeaf, offsets);
624  targetArray.set(tgtOffset, sourceArray, it.second);
625  }
626  }
627 
628  void operator()(const LeafT& leaf, size_t aIdx) const
629  {
630  const Index idx = Index(aIdx);
631  const auto& moveIndices = mMoveLeafMap.at(idx);
632  if (moveIndices.empty()) return;
633 
634  // extract target leaf and per-voxel offsets for this leaf
635 
636  auto& offsets = mOffsetMap[idx];
637 
638  // extract source leaf that has the same origin as the target leaf (if any)
639 
640  assert(idx < mSourceIndices.size());
641  const Index sourceOffset(mSourceIndices[idx]);
642 
643  const auto& array = leaf.constAttributeArray(mAttributeIndex);
644 
645  PerformTypedMoveOp op(mTargetHandles, mSourceHandles,
646  idx, sourceOffset, leaf, offsets, moveIndices);
647  if (!processTypedArray(array, op)) {
648  this->performMove(idx, sourceOffset, leaf, offsets, moveIndices);
649  }
650  }
651 
652 private:
653  OffsetMap& mOffsetMap;
654  AttributeHandles& mTargetHandles;
655  const IndexArray& mSourceIndices;
656  AttributeHandles& mSourceHandles;
657  const Index mAttributeIndex;
658  const LocalPointIndexMap& mMoveLeafMap;
659 }; // struct LocalMovePointsOp
660 
661 } // namespace point_move_internal
662 
663 
665 
666 
667 template <typename PointDataGridT, typename DeformerT, typename FilterT>
668 inline void movePoints( PointDataGridT& points,
669  const math::Transform& transform,
670  DeformerT& deformer,
671  const FilterT& filter,
672  future::Advect* objectNotInUse,
673  bool threaded)
674 {
675  using PointDataTreeT = typename PointDataGridT::TreeType;
676  using LeafT = typename PointDataTreeT::LeafNodeType;
677  using LeafManagerT = typename tree::LeafManager<PointDataTreeT>;
678 
679  using namespace point_move_internal;
680 
681  // this object is for future use only
682  assert(!objectNotInUse);
683  (void)objectNotInUse;
684 
685  PointDataTreeT& tree = points.tree();
686 
687  // early exit if no LeafNodes
688 
689  PointDataTree::LeafCIter iter = tree.cbeginLeaf();
690 
691  if (!iter) return;
692 
693  // build voxel topology taking into account any point group deletion
694 
695  auto newPoints = point_mask_internal::convertPointsToScalar<PointDataGrid>(
696  points, transform, filter, deformer, threaded);
697  auto& newTree = newPoints->tree();
698 
699  // create leaf managers for both trees
700 
701  LeafManagerT sourceLeafManager(tree);
702  LeafManagerT targetLeafManager(newTree);
703 
704  // initialize attribute handles
705  AttributeHandles sourceHandles(sourceLeafManager.leafCount());
706  AttributeHandles targetHandles(targetLeafManager.leafCount());
707 
708  // extract the existing attribute set
709  const auto& existingAttributeSet = points.tree().cbeginLeaf()->attributeSet();
710 
711  // build a coord -> index map for looking up target leafs by origin and a faster
712  // unordered map for finding the source index from a target index
713 
714  std::map<Coord, Index> targetLeafMap;
715  std::vector<Index> sourceIndices(targetLeafManager.leafCount(),
717 
718  OffsetMap offsetMap(targetLeafManager.leafCount());
719 
720  {
721  std::map<Coord, Index> sourceLeafMap;
722  auto sourceRange = sourceLeafManager.leafRange();
723  for (auto leaf = sourceRange.begin(); leaf; ++leaf) {
724  sourceLeafMap.insert({leaf->origin(), leaf.pos()});
725  }
726  auto targetRange = targetLeafManager.leafRange();
727  for (auto leaf = targetRange.begin(); leaf; ++leaf) {
728  targetLeafMap.insert({leaf->origin(), leaf.pos()});
729  }
730 
731  // perform four independent per-leaf operations in parallel
732  targetLeafManager.foreach(
733  [&](LeafT& leaf, size_t idx) {
734  // map frequency => cumulative histogram
735  auto* buffer = leaf.buffer().data();
736  for (Index i = 1; i < leaf.buffer().size(); i++) {
737  buffer[i] = buffer[i-1] + buffer[i];
738  }
739  // replace attribute set with a copy of the existing one
740  leaf.replaceAttributeSet(new AttributeSet(existingAttributeSet, leaf.getLastValue()),
741  /*allowMismatchingDescriptors=*/true);
742  // store the index of the source leaf in a corresponding target leaf array
743  const auto it = sourceLeafMap.find(leaf.origin());
744  if (it != sourceLeafMap.end()) {
745  sourceIndices[idx] = it->second;
746  }
747  // allocate offset maps
748  offsetMap[idx].resize(LeafT::SIZE);
749  },
750  threaded);
751  }
752 
753  // moving leaf
754 
755  GlobalPointIndexMap globalMoveLeafMap(targetLeafManager.leafCount());
756  LocalPointIndexMap localMoveLeafMap(targetLeafManager.leafCount());
757 
758  // build global and local move leaf maps and update local positions
759 
760  if (filter.state() == index::ALL) {
761  NullFilter nullFilter;
762  BuildMoveMapsOp<DeformerT, PointDataTreeT, NullFilter> op(deformer,
763  globalMoveLeafMap, localMoveLeafMap, targetLeafMap,
764  transform, points.transform(), nullFilter);
765  sourceLeafManager.foreach(op, threaded);
766  } else {
767  BuildMoveMapsOp<DeformerT, PointDataTreeT, FilterT> op(deformer,
768  globalMoveLeafMap, localMoveLeafMap, targetLeafMap,
769  transform, points.transform(), filter);
770  sourceLeafManager.foreach(op, threaded);
771  }
772 
773  for (const auto& it : existingAttributeSet.descriptor().map()) {
774 
775  const Index attributeIndex = static_cast<Index>(it.second);
776 
777  // zero offsets
778  targetLeafManager.foreach(
779  [&offsetMap](const LeafT& /*leaf*/, size_t idx) {
780  std::fill(offsetMap[Index(idx)].begin(), offsetMap[Index(idx)].end(), 0);
781  },
782  threaded);
783 
784  // cache attribute handles
785 
786  sourceHandles.cache(sourceLeafManager.leafRange(), attributeIndex);
787  targetHandles.cache(targetLeafManager.leafRange(), attributeIndex);
788 
789  // move points between leaf nodes
790 
791  GlobalMovePointsOp<PointDataTreeT> globalMoveOp(offsetMap, targetHandles,
792  sourceHandles, attributeIndex, globalMoveLeafMap);
793  targetLeafManager.foreach(globalMoveOp, threaded);
794 
795  // move points within leaf nodes
796 
797  LocalMovePointsOp<PointDataTreeT> localMoveOp(offsetMap, targetHandles,
798  sourceIndices, sourceHandles,
799  attributeIndex, localMoveLeafMap);
800  targetLeafManager.foreach(localMoveOp, threaded);
801  }
802 
803  points.setTree(newPoints->treePtr());
804 }
805 
806 
807 template <typename PointDataGridT, typename DeformerT, typename FilterT>
808 inline void movePoints( PointDataGridT& points,
809  DeformerT& deformer,
810  const FilterT& filter,
811  future::Advect* objectNotInUse,
812  bool threaded)
813 {
814  movePoints(points, points.transform(), deformer, filter, objectNotInUse, threaded);
815 }
816 
817 
819 
820 
821 template <typename T>
823  : mCache(cache) { }
824 
825 
826 template <typename T>
827 template <typename PointDataGridT, typename DeformerT, typename FilterT>
828 void CachedDeformer<T>::evaluate(PointDataGridT& grid, DeformerT& deformer, const FilterT& filter,
829  bool threaded)
830 {
831  using TreeT = typename PointDataGridT::TreeType;
832  using LeafT = typename TreeT::LeafNodeType;
833  using LeafManagerT = typename tree::LeafManager<TreeT>;
834  LeafManagerT leafManager(grid.tree());
835 
836  // initialize cache
837  auto& leafs = mCache.leafs;
838  leafs.resize(leafManager.leafCount());
839 
840  const auto& transform = grid.transform();
841 
842  // insert deformed positions into the cache
843 
844  auto cachePositionsOp = [&](const LeafT& leaf, size_t idx) {
845 
846  const Index64 totalPointCount = leaf.pointCount();
847  if (totalPointCount == 0) return;
848 
849  // deformer is copied to ensure that it is unique per-thread
850 
851  DeformerT newDeformer(deformer);
852 
853  // if more than half the number of total points are evaluated by the filter, prefer
854  // accessing the data from a vector instead of a hash map for faster performance
855  const Index64 vectorThreshold = totalPointCount / 2;
856 
857  newDeformer.reset(leaf, idx);
858 
859  auto handle = AttributeHandle<Vec3f>::create(leaf.constAttributeArray("P"));
860 
861  auto& cache = leafs[idx];
862  cache.clear();
863 
864  // only insert into a vector directly if the filter evaluates all points and the
865  // number of active points is greater than the vector threshold
866  const bool useVector = filter.state() == index::ALL &&
867  (leaf.isDense() || (leaf.onPointCount() > vectorThreshold));
868  if (useVector) {
869  cache.vecData.resize(totalPointCount);
870  }
871 
872  for (auto iter = leaf.beginIndexOn(filter); iter; iter++) {
873 
874  // extract index-space position and apply index-space deformation (if defined)
875 
876  Vec3d position = handle->get(*iter) + iter.getCoord().asVec3d();
877 
878  // if deformer is designed to be used in index-space, perform deformation prior
879  // to transforming position to world-space, otherwise perform deformation afterwards
880 
882  newDeformer.apply(position, iter);
883  position = transform.indexToWorld(position);
884  }
885  else {
886  position = transform.indexToWorld(position);
887  newDeformer.apply(position, iter);
888  }
889 
890  // insert new position into the cache
891 
892  if (useVector) {
893  cache.vecData[*iter] = static_cast<Vec3T>(position);
894  }
895  else {
896  cache.mapData.insert({*iter, static_cast<Vec3T>(position)});
897  }
898  }
899 
900  // after insertion, move the data into a vector if the threshold is reached
901 
902  if (!useVector && cache.mapData.size() > vectorThreshold) {
903  cache.vecData.resize(totalPointCount);
904  for (const auto& it : cache.mapData) {
905  cache.vecData[it.first] = it.second;
906  }
907  cache.mapData.clear();
908  }
909 
910  // store the total number of points to allow use of an expanded vector on access
911 
912  if (!cache.mapData.empty()) {
913  cache.totalSize = static_cast<Index>(totalPointCount);
914  }
915  };
916 
917  leafManager.foreach(cachePositionsOp, threaded);
918 }
919 
920 
921 template <typename T>
922 template <typename LeafT>
923 void CachedDeformer<T>::reset(const LeafT& /*leaf*/, size_t idx)
924 {
925  if (idx >= mCache.leafs.size()) {
926  if (mCache.leafs.empty()) {
927  throw IndexError("No leafs in cache, perhaps CachedDeformer has not been evaluated?");
928  } else {
929  throw IndexError("Leaf index is out-of-range of cache leafs.");
930  }
931  }
932  auto& cache = mCache.leafs[idx];
933  if (!cache.mapData.empty()) {
934  // expand into a local vector if there are greater than 16 values in the hash map
935  // and the expanded vector would contain fewer values than 256 times those in the
936  // hash map, this trades a little extra storage for faster random access performance
937  if (cache.mapData.size() > 16 &&
938  cache.totalSize < (cache.mapData.size() * 256)) {
939  if (cache.totalSize < cache.mapData.size()) {
940  throw ValueError("Cache total size is not valid.");
941  }
942  mLocalLeafVec.resize(cache.totalSize);
943  for (const auto& it : cache.mapData) {
944  assert(it.first < cache.totalSize);
945  mLocalLeafVec[it.first] = it.second;
946  }
947  mLeafVec = &mLocalLeafVec;
948  mLeafMap = nullptr;
949  }
950  else {
951  mLeafMap = &cache.mapData;
952  mLeafVec = nullptr;
953  }
954  }
955  else {
956  mLeafVec = &cache.vecData;
957  mLeafMap = nullptr;
958  }
959 }
960 
961 
962 template <typename T>
963 template <typename IndexIterT>
964 void CachedDeformer<T>::apply(Vec3d& position, const IndexIterT& iter) const
965 {
966  assert(*iter >= 0);
967 
968  if (mLeafMap) {
969  auto it = mLeafMap->find(*iter);
970  if (it == mLeafMap->end()) return;
971  position = static_cast<openvdb::Vec3d>(it->second);
972  }
973  else {
974  assert(mLeafVec);
975 
976  if (mLeafVec->empty()) return;
977  assert(*iter < mLeafVec->size());
978  position = static_cast<openvdb::Vec3d>((*mLeafVec)[*iter]);
979  }
980 }
981 
982 
983 } // namespace points
984 } // namespace OPENVDB_VERSION_NAME
985 } // namespace openvdb
986 
987 #endif // OPENVDB_POINTS_POINT_MOVE_HAS_BEEN_INCLUDED
988 
989 // Copyright (c) 2012-2018 DreamWorks Animation LLC
990 // All rights reserved. This software is distributed under the
991 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
typename TreeT::LeafNodeType LeafT
Definition: PointMove.h:323
void cache(const LeafRangeT &range, const Index attributeIndex)
Definition: PointMove.h:302
std::vector< Leaf > leafs
Definition: PointMove.h:145
Definition: Mat.h:197
bool processTypedArray(const ArrayType &array, OpType &op)
Utility function that, given a generic attribute array, calls a functor with the fully-resolved value...
Definition: PointMove.h:219
Write-able version of AttributeHandle.
Definition: AttributeArray.h:715
void movePoints(PointDataGridT &points, const math::Transform &transform, DeformerT &deformer, const FilterT &filter=NullFilter(), future::Advect *objectNotInUse=nullptr, bool threaded=true)
Move points in a PointDataGrid using a custom deformer and a new transform.
Definition: PointMove.h:668
std::vector< LeafT * > LeafArrayT
Definition: PointMove.h:432
Helper class used internally by processTypedArray()
Definition: PointMove.h:205
void operator()(LeafT &leaf, size_t aIdx) const
Definition: PointMove.h:512
std::vector< Vec3T > LeafVecT
Definition: PointMove.h:125
typename tree::LeafManager< TreeT > LeafManagerT
Definition: PointMove.h:433
std::vector< IndexTripleArray > GlobalPointIndexMap
Definition: PointMove.h:187
std::vector< IndexArray > OffsetMap
Definition: PointMove.h:194
void operator()(const LeafT &leaf, size_t aIdx) const
Definition: PointMove.h:628
void operator()(const AttributeArray &) const
Definition: PointMove.h:572
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:51
AttributeWriteHandle< ValueT > & getWriteHandle(const Index leafOffset)
Definition: PointMove.h:276
Definition: Mat.h:196
typename tree::LeafManager< TreeT > LeafManagerT
Definition: PointMove.h:325
A Deformer that caches the resulting positions from evaluating another Deformer.
Definition: PointMove.h:121
const AttributeArray & getConstArray(const Index leafOffset) const
Definition: PointMove.h:260
AttributeArray & getArray(const Index leafOffset)
Definition: PointMove.h:253
PerformTypedMoveOp(AttributeHandles &targetHandles, AttributeHandles &sourceHandles, int targetOffset, const LeafT &targetLeaf, IndexArray &offsets, const IndexTripleArray &indices)
Definition: PointMove.h:448
std::unordered_map< Index, Vec3T > LeafMapT
Definition: PointMove.h:126
typename math::Vec3< T > Vec3T
Definition: PointMove.h:124
void operator()(LeafT &leaf, size_t idx) const
Definition: PointMove.h:342
PerformTypedMoveOp(AttributeHandles &targetHandles, AttributeHandles &sourceHandles, int targetOffset, int sourceOffset, const LeafT &targetLeaf, IndexArray &offsets, const IndexPairArray &indices)
Definition: PointMove.h:560
void clear()
clear data buffers and reset counter
Definition: PointMove.h:134
Index size() const
Definition: AttributeArray.h:667
std::vector< AttributeHandle< int >::Ptr > HandleArray
Definition: PointMove.h:248
Definition: IndexIterator.h:70
static Ptr create(const AttributeArray &array, const bool preserveCompression=true)
Definition: AttributeArray.h:1864
4x4 -matrix class.
Definition: Mat3.h:49
Vec3< double > Vec3d
Definition: Vec3.h:679
std::vector< LeafT * > LeafArrayT
Definition: PointMove.h:542
Cache read and write attribute handles to amortize construction cost.
Definition: PointMove.h:246
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:136
static void call(OpType &op, const AttributeArray &array)
Definition: PointMove.h:206
Vec3d indexToWorld(const Vec3d &xyz) const
Apply this transformation to the given coordinates.
Definition: Transform.h:135
GlobalMovePointsOp(OffsetMap &offsetMap, AttributeHandles &targetHandles, AttributeHandles &sourceHandles, const Index attributeIndex, const GlobalPointIndexMap &moveLeafMap)
Definition: PointMove.h:435
Definition: Exceptions.h:92
std::tuple< Index, Index, Index > IndexTriple
Definition: PointMove.h:185
CacheHandleOp(HandleArray &handles)
Definition: PointMove.h:286
Definition: PointMove.h:86
Index indexOffsetFromVoxel(const Index voxelOffset, const LeafT &leaf, IndexArray &offsets)
Definition: PointMove.h:415
LocalMovePointsOp(OffsetMap &offsetMap, AttributeHandles &targetHandles, const IndexArray &sourceIndices, AttributeHandles &sourceHandles, const Index attributeIndex, const LocalPointIndexMap &moveLeafMap)
Definition: PointMove.h:545
Definition: Transform.h:66
Definition: Exceptions.h:40
Deformer Traits for optionally configuring deformers to be applied in index-space. The default is world-space.
Definition: PointMask.h:103
Base class for tree-traversal iterators over all leaf nodes (but not leaf voxels) ...
Definition: TreeIterator.h:1235
tbb::concurrent_vector< IndexTriple > IndexTripleArray
Definition: PointMove.h:186
A no-op filter that can be used when iterating over all indices.
Definition: IndexIterator.h:77
Create a handle and reinterpret cast as an int handle to store.
Definition: PointMove.h:284
Index32 Index
Definition: Types.h:61
3x3 matrix class.
Definition: Mat3.h:55
Definition: AttributeArray.h:644
Base class for storing attribute data.
Definition: AttributeArray.h:118
uint64_t Index64
Definition: Types.h:60
void operator()(const AttributeArray &) const
Definition: PointMove.h:459
static Coord round(const Vec3< T > &xyz)
Return xyz rounded to the closest integer coordinates (cell centered conversion). ...
Definition: Coord.h:77
void performMove(int targetOffset, const LeafT &targetLeaf, IndexArray &offsets, const IndexTripleArray &indices) const
Definition: PointMove.h:500
std::vector< IndexPair > IndexPairArray
Definition: PointMove.h:190
void reset(const LeafT &leaf, size_t idx)
Definition: PointMove.h:923
This class manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional auxil...
Definition: LeafManager.h:110
LeafVecT vecData
Definition: PointMove.h:140
typename TreeT::LeafNodeType LeafT
Definition: PointMove.h:541
AttributeHandles(const size_t size)
Definition: PointMove.h:250
Definition: Exceptions.h:84
void performTypedMove(int sourceOffset, int targetOffset, const LeafT &targetLeaf, IndexArray &offsets, const IndexPairArray &indices) const
Definition: PointMove.h:599
void evaluate(PointDataGridT &grid, DeformerT &deformer, const FilterT &filter, bool threaded=true)
Definition: PointMove.h:828
void apply(Vec3d &position, const IndexIterT &iter) const
Retrieve the new position from the cache.
Definition: PointMove.h:964
AttributeHandle< ValueT > & getHandle(const Index leafOffset)
Definition: PointMove.h:268
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:133
void performMove(int targetOffset, int sourceOffset, const LeafT &targetLeaf, IndexArray &offsets, const IndexPairArray &indices) const
Definition: PointMove.h:616
Ordered collection of uniquely-named attribute arrays.
Definition: AttributeSet.h:62
typename TreeT::LeafNodeType LeafT
Definition: PointMove.h:431
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:188
typename tree::LeafManager< TreeT > LeafManagerT
Definition: PointMove.h:543
std::vector< Index > IndexArray
Definition: PointMove.h:193
LeafMapT mapData
Definition: PointMove.h:141
std::vector< IndexPairArray > LocalPointIndexMap
Definition: PointMove.h:191
Vec3d asVec3d() const
Definition: Coord.h:170
std::pair< Index, Index > IndexPair
Definition: PointMove.h:189
BuildMoveMapsOp(const DeformerT &deformer, GlobalPointIndexMap &globalMoveLeafMap, LocalPointIndexMap &localMoveLeafMap, const std::map< Coord, Index > &targetLeafMap, const math::Transform &targetTransform, const math::Transform &sourceTransform, const FilterT &filter)
Definition: PointMove.h:327
void operator()(const AttributeArray &array) const
Definition: PointMove.h:290
std::vector< LeafT * > LeafArrayT
Definition: PointMove.h:324