OpenVDB 10.0.1
Loading...
Searching...
No Matches
InternalNode.h
Go to the documentation of this file.
1// Copyright Contributors to the OpenVDB Project
2// SPDX-License-Identifier: MPL-2.0
3//
4/// @file InternalNode.h
5///
6/// @brief Internal table nodes for OpenVDB trees
7
8#ifndef OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED
9#define OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED
10
11#include <openvdb/Platform.h>
13#include <openvdb/io/Compression.h> // for io::readCompressedValues(), etc.
14#include <openvdb/math/Math.h> // for math::isExactlyEqual(), etc.
15#include <openvdb/version.h>
16#include <openvdb/Types.h>
17#include "Iterator.h"
18#include "NodeUnion.h"
19#include <tbb/parallel_for.h>
20#include <memory>
21#include <type_traits>
22
23
24namespace openvdb {
26namespace OPENVDB_VERSION_NAME {
27namespace tree {
28
29template<typename, Index, typename> struct SameInternalConfig; // forward declaration
30
31
32template<typename _ChildNodeType, Index Log2Dim>
34{
35public:
36 using ChildNodeType = _ChildNodeType;
37 using LeafNodeType = typename ChildNodeType::LeafNodeType;
38 using ValueType = typename ChildNodeType::ValueType;
39 using BuildType = typename ChildNodeType::BuildType;
42
43 static const Index
44 LOG2DIM = Log2Dim, // log2 of tile count in one dimension
45 TOTAL = Log2Dim + ChildNodeType::TOTAL, // log2 of voxel count in one dimension
46 DIM = 1 << TOTAL, // total voxel count in one dimension
47 NUM_VALUES = 1 << (3 * Log2Dim), // total voxel count represented by this node
48 LEVEL = 1 + ChildNodeType::LEVEL; // level 0 = leaf
49 static const Index64
50 NUM_VOXELS = uint64_t(1) << (3 * TOTAL); // total voxel count represented by this node
51
52 /// @brief ValueConverter<T>::Type is the type of an InternalNode having the same
53 /// child hierarchy and dimensions as this node but a different value type, T.
54 template<typename OtherValueType>
56 using Type = InternalNode<typename ChildNodeType::template ValueConverter<
57 OtherValueType>::Type, Log2Dim>;
58 };
59
60 /// @brief SameConfiguration<OtherNodeType>::value is @c true if and only if OtherNodeType
61 /// is the type of an InternalNode with the same dimensions as this node and whose
62 /// ChildNodeType has the same configuration as this node's ChildNodeType.
63 template<typename OtherNodeType>
68
69
70 /// @brief Default constructor
71 /// @warning The resulting InternalNode is uninitialized
73
74 /// @brief Constructor of an InternalNode with dense inactive tiles of the specified value.
75 /// @param offValue Background value used for inactive values
76 explicit InternalNode(const ValueType& offValue);
77
78 /// @brief Constructs an InternalNode with dense tiles
79 /// @param origin The location in index space of the fist tile value
80 /// @param fillValue Value assigned to all the tiles
81 /// @param active State assigned to all the tiles
82 InternalNode(const Coord& origin, const ValueType& fillValue, bool active = false);
83
84 InternalNode(PartialCreate, const Coord&, const ValueType& fillValue, bool active = false);
85
86 /// @brief Deep copy constructor
87 ///
88 /// @note This method is multi-threaded!
90
91 /// @brief Value conversion copy constructor
92 ///
93 /// @note This method is multi-threaded!
94 template<typename OtherChildNodeType>
96
97 /// @brief Topology copy constructor
98 ///
99 /// @note This method is multi-threaded!
100 template<typename OtherChildNodeType>
102 const ValueType& background, TopologyCopy);
103
104 /// @brief Topology copy constructor
105 ///
106 /// @note This method is multi-threaded!
107 template<typename OtherChildNodeType>
109 const ValueType& offValue, const ValueType& onValue, TopologyCopy);
110
112
113protected:
117
118 // Type tags to disambiguate template instantiations
119 struct ValueOn {}; struct ValueOff {}; struct ValueAll {};
120 struct ChildOn {}; struct ChildOff {}; struct ChildAll {};
121
122 // The following class templates implement the iterator interfaces specified in Iterator.h
123 // by providing getItem(), setItem() and/or modifyItem() methods.
124
125 // Sparse iterator that visits child nodes of an InternalNode
126 template<typename NodeT, typename ChildT, typename MaskIterT, typename TagT>
128 MaskIterT, ChildIter<NodeT, ChildT, MaskIterT, TagT>, NodeT, ChildT>
129 {
131 ChildIter(const MaskIterT& iter, NodeT* parent): SparseIteratorBase<
132 MaskIterT, ChildIter<NodeT, ChildT, MaskIterT, TagT>, NodeT, ChildT>(iter, parent) {}
133
134 ChildT& getItem(Index pos) const
135 {
136 assert(this->parent().isChildMaskOn(pos));
137 return *(this->parent().getChildNode(pos));
138 }
139
140 // Note: setItem() can't be called on const iterators.
141 void setItem(Index pos, const ChildT& c) const { this->parent().resetChildNode(pos, &c); }
142
143 // Note: modifyItem() isn't implemented, since it's not useful for child node pointers.
144 };// ChildIter
145
146 // Sparse iterator that visits tile values of an InternalNode
147 template<typename NodeT, typename ValueT, typename MaskIterT, typename TagT>
149 MaskIterT, ValueIter<NodeT, ValueT, MaskIterT, TagT>, NodeT, ValueT>
150 {
152 ValueIter(const MaskIterT& iter, NodeT* parent): SparseIteratorBase<
153 MaskIterT, ValueIter<NodeT, ValueT, MaskIterT, TagT>, NodeT, ValueT>(iter, parent) {}
154
155 const ValueT& getItem(Index pos) const { return this->parent().mNodes[pos].getValue(); }
156
157 // Note: setItem() can't be called on const iterators.
158 void setItem(Index pos, const ValueT& v) const { this->parent().mNodes[pos].setValue(v); }
159
160 // Note: modifyItem() can't be called on const iterators.
161 template<typename ModifyOp>
162 void modifyItem(Index pos, const ModifyOp& op) const
163 {
164 op(this->parent().mNodes[pos].getValue());
165 }
166 };// ValueIter
167
168 // Dense iterator that visits both tiles and child nodes of an InternalNode
169 template<typename NodeT, typename ChildT, typename ValueT, typename TagT>
171 MaskDenseIterator, DenseIter<NodeT, ChildT, ValueT, TagT>, NodeT, ChildT, ValueT>
172 {
175
177 DenseIter(const MaskDenseIterator& iter, NodeT* parent):
178 DenseIteratorBase<MaskDenseIterator, DenseIter, NodeT, ChildT, ValueT>(iter, parent) {}
179
180 bool getItem(Index pos, ChildT*& child, NonConstValueT& value) const
181 {
182 if (this->parent().isChildMaskOn(pos)) {
183 child = this->parent().getChildNode(pos);
184 return true;
185 }
186 child = nullptr;
187 value = this->parent().mNodes[pos].getValue();
188 return false;
189 }
190
191 // Note: setItem() can't be called on const iterators.
192 void setItem(Index pos, ChildT* child) const
193 {
194 this->parent().resetChildNode(pos, child);
195 }
196
197 // Note: unsetItem() can't be called on const iterators.
198 void unsetItem(Index pos, const ValueT& value) const
199 {
200 this->parent().unsetChildNode(pos, value);
201 }
202 };// DenseIter
203
204public:
205 // Iterators (see Iterator.h for usage)
212
219
220 ChildOnCIter cbeginChildOn() const { return ChildOnCIter(mChildMask.beginOn(), this); }
221 ChildOffCIter cbeginChildOff() const { return ChildOffCIter(mChildMask.beginOff(), this); }
222 ChildAllCIter cbeginChildAll() const { return ChildAllCIter(mChildMask.beginDense(), this); }
223 ChildOnCIter beginChildOn() const { return cbeginChildOn(); }
224 ChildOffCIter beginChildOff() const { return cbeginChildOff(); }
225 ChildAllCIter beginChildAll() const { return cbeginChildAll(); }
226 ChildOnIter beginChildOn() { return ChildOnIter(mChildMask.beginOn(), this); }
227 ChildOffIter beginChildOff() { return ChildOffIter(mChildMask.beginOff(), this); }
228 ChildAllIter beginChildAll() { return ChildAllIter(mChildMask.beginDense(), this); }
229
230 ValueOnCIter cbeginValueOn() const { return ValueOnCIter(mValueMask.beginOn(), this); }
231 /// @warning This iterator will also visit child nodes so use isChildMaskOn to skip them!
232 ValueOffCIter cbeginValueOff() const { return ValueOffCIter(mValueMask.beginOff(), this); }
233 ValueAllCIter cbeginValueAll() const { return ValueAllCIter(mChildMask.beginOff(), this); }
234 ValueOnCIter beginValueOn() const { return cbeginValueOn(); }
235 /// @warning This iterator will also visit child nodes so use isChildMaskOn to skip them!
236 ValueOffCIter beginValueOff() const { return cbeginValueOff(); }
237 ValueAllCIter beginValueAll() const { return cbeginValueAll(); }
238 ValueOnIter beginValueOn() { return ValueOnIter(mValueMask.beginOn(), this); }
239 /// @warning This iterator will also visit child nodes so use isChildMaskOn to skip them!
240 ValueOffIter beginValueOff() { return ValueOffIter(mValueMask.beginOff(), this); }
241 ValueAllIter beginValueAll() { return ValueAllIter(mChildMask.beginOff(), this); }
242
243
244 /// @return The dimension of this InternalNode
245 /// @details The number of voxels in one coordinate direction covered by this node
246 static Index dim() { return DIM; }
247 /// @return The level of this node
248 /// @details Level 0 is by definition the level of the leaf nodes
249 static Index getLevel() { return LEVEL; }
250 /// @brief Populated an std::vector with the dimension of all the
251 /// nodes in the branch starting with this node.
252 static void getNodeLog2Dims(std::vector<Index>& dims);
253 /// @return The dimension of the child nodes of this node.
254 /// @details The number of voxels in one coordinate direction
255 /// covered by a child node of this node.
256 static Index getChildDim() { return ChildNodeType::DIM; }
257
258 /// Return the linear table offset of the given global or local coordinates.
259 static Index coordToOffset(const Coord& xyz);
260 /// @brief Return the local coordinates for a linear table offset,
261 /// where offset 0 has coordinates (0, 0, 0).
262 static void offsetToLocalCoord(Index n, Coord& xyz);
263 /// Return the global coordinates for a linear table offset.
264 Coord offsetToGlobalCoord(Index n) const;
265
266 /// Return the grid index coordinates of this node's local origin.
267 const Coord& origin() const { return mOrigin; }
268 /// Set the grid index coordinates of this node's local origin.
269 void setOrigin(const Coord& origin) { mOrigin = origin; }
270
271#if OPENVDB_ABI_VERSION_NUMBER >= 9
272 /// Return the transient data value.
273 Index32 transientData() const { return mTransientData; }
274 /// Set the transient data value.
275 void setTransientData(Index32 transientData) { mTransientData = transientData; }
276#endif
277
278 Index32 leafCount() const;
279 void nodeCount(std::vector<Index32> &vec) const;
280 Index32 nonLeafCount() const;
281 Index32 childCount() const;
282 Index64 onVoxelCount() const;
283 Index64 offVoxelCount() const;
284 Index64 onLeafVoxelCount() const;
285 Index64 offLeafVoxelCount() const;
286 Index64 onTileCount() const;
287
288 /// Return the total amount of memory in bytes occupied by this node and its children.
289 Index64 memUsage() const;
290
291 /// @brief Expand the specified bounding box so that it includes the active tiles
292 /// of this internal node as well as all the active values in its child nodes.
293 /// If visitVoxels is false LeafNodes will be approximated as dense, i.e. with all
294 /// voxels active. Else the individual active voxels are visited to produce a tight bbox.
295 void evalActiveBoundingBox(CoordBBox& bbox, bool visitVoxels = true) const;
296
297 /// @brief Return the bounding box of this node, i.e., the full index space
298 /// spanned by the node regardless of its content.
299 CoordBBox getNodeBoundingBox() const { return CoordBBox::createCube(mOrigin, DIM); }
300
301 /// @return True if this node contains no child nodes.
302 bool isEmpty() const { return mChildMask.isOff(); }
303
304 /// Return @c true if all of this node's table entries have the same active state
305 /// and the same constant value to within the given tolerance,
306 /// and return that value in @a firstValue and the active state in @a state.
307 ///
308 /// @note This method also returns @c false if this node contains any child nodes.
309 bool isConstant(ValueType& firstValue, bool& state,
310 const ValueType& tolerance = zeroVal<ValueType>()) const;
311
312 /// Return @c true if all of this node's tables entries have
313 /// the same active @a state and the range of its values satisfy
314 /// (@a maxValue - @a minValue) <= @a tolerance.
315 ///
316 /// @param minValue Is updated with the minimum of all values IF method
317 /// returns @c true. Else the value is undefined!
318 /// @param maxValue Is updated with the maximum of all values IF method
319 /// returns @c true. Else the value is undefined!
320 /// @param state Is updated with the state of all values IF method
321 /// returns @c true. Else the value is undefined!
322 /// @param tolerance The tolerance used to determine if values are
323 /// approximately constant.
324 ///
325 /// @note This method also returns @c false if this node contains any child nodes.
326 bool isConstant(ValueType& minValue, ValueType& maxValue,
327 bool& state, const ValueType& tolerance = zeroVal<ValueType>()) const;
328
329 /// Return @c true if this node has no children and only contains inactive values.
330 bool isInactive() const { return this->isChildMaskOff() && this->isValueMaskOff(); }
331
332 /// Return @c true if the voxel at the given coordinates is active.
333 bool isValueOn(const Coord& xyz) const;
334 /// Return @c true if the voxel at the given offset is active.
335 bool isValueOn(Index offset) const { return mValueMask.isOn(offset); }
336
337 /// Return @c true if this node or any of its child nodes have any active tiles.
338 bool hasActiveTiles() const;
339
340 const ValueType& getValue(const Coord& xyz) const;
341 bool probeValue(const Coord& xyz, ValueType& value) const;
342
343 /// @brief Return the level of the tree (0 = leaf) at which the value
344 /// at the given coordinates resides.
345 Index getValueLevel(const Coord& xyz) const;
346
347 /// @brief If the first entry in this node's table is a tile, return the tile's value.
348 /// Otherwise, return the result of calling getFirstValue() on the child.
349 const ValueType& getFirstValue() const;
350 /// @brief If the last entry in this node's table is a tile, return the tile's value.
351 /// Otherwise, return the result of calling getLastValue() on the child.
352 const ValueType& getLastValue() const;
353
354 /// Set the active state of the voxel at the given coordinates but don't change its value.
355 void setActiveState(const Coord& xyz, bool on);
356 /// Set the value of the voxel at the given coordinates but don't change its active state.
357 void setValueOnly(const Coord& xyz, const ValueType& value);
358 /// Mark the voxel at the given coordinates as active but don't change its value.
359 void setValueOn(const Coord& xyz);
360 /// Set the value of the voxel at the given coordinates and mark the voxel as active.
361 void setValueOn(const Coord& xyz, const ValueType& value);
362 /// Mark the voxel at the given coordinates as inactive but don't change its value.
363 void setValueOff(const Coord& xyz);
364 /// Set the value of the voxel at the given coordinates and mark the voxel as inactive.
365 void setValueOff(const Coord& xyz, const ValueType& value);
366
367 /// @brief Apply a functor to the value of the voxel at the given coordinates
368 /// and mark the voxel as active.
369 template<typename ModifyOp>
370 void modifyValue(const Coord& xyz, const ModifyOp& op);
371 /// Apply a functor to the voxel at the given coordinates.
372 template<typename ModifyOp>
373 void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op);
374
375 /// Return the value of the voxel at the given coordinates and, if necessary, update
376 /// the accessor with pointers to the nodes along the path from the root node to
377 /// the node containing the voxel.
378 /// @note Used internally by ValueAccessor.
379 template<typename AccessorT>
380 const ValueType& getValueAndCache(const Coord& xyz, AccessorT&) const;
381
382 /// Return @c true if the voxel at the given coordinates is active and, if necessary,
383 /// update the accessor with pointers to the nodes along the path from the root node
384 /// to the node containing the voxel.
385 /// @note Used internally by ValueAccessor.
386 template<typename AccessorT>
387 bool isValueOnAndCache(const Coord& xyz, AccessorT&) const;
388
389 /// Change the value of the voxel at the given coordinates and mark it as active.
390 /// If necessary, update the accessor with pointers to the nodes along the path
391 /// from the root node to the node containing the voxel.
392 /// @note Used internally by ValueAccessor.
393 template<typename AccessorT>
394 void setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
395
396 /// Set the value of the voxel at the given coordinate but preserves its active state.
397 /// If necessary, update the accessor with pointers to the nodes along the path
398 /// from the root node to the node containing the voxel.
399 /// @note Used internally by ValueAccessor.
400 template<typename AccessorT>
401 void setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
402
403 /// @brief Apply a functor to the value of the voxel at the given coordinates
404 /// and mark the voxel as active.
405 /// If necessary, update the accessor with pointers to the nodes along the path
406 /// from the root node to the node containing the voxel.
407 /// @note Used internally by ValueAccessor.
408 template<typename ModifyOp, typename AccessorT>
409 void modifyValueAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&);
410
411 /// Apply a functor to the voxel at the given coordinates.
412 /// If necessary, update the accessor with pointers to the nodes along the path
413 /// from the root node to the node containing the voxel.
414 /// @note Used internally by ValueAccessor.
415 template<typename ModifyOp, typename AccessorT>
416 void modifyValueAndActiveStateAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&);
417
418 /// Change the value of the voxel at the given coordinates and mark it as inactive.
419 /// If necessary, update the accessor with pointers to the nodes along the path
420 /// from the root node to the node containing the voxel.
421 /// @note Used internally by ValueAccessor.
422 template<typename AccessorT>
423 void setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
424
425 /// Set the active state of the voxel at the given coordinates without changing its value.
426 /// If necessary, update the accessor with pointers to the nodes along the path
427 /// from the root node to the node containing the voxel.
428 /// @note Used internally by ValueAccessor.
429 template<typename AccessorT>
430 void setActiveStateAndCache(const Coord& xyz, bool on, AccessorT&);
431
432 /// Return, in @a value, the value of the voxel at the given coordinates and,
433 /// if necessary, update the accessor with pointers to the nodes along
434 /// the path from the root node to the node containing the voxel.
435 /// @return @c true if the voxel at the given coordinates is active
436 /// @note Used internally by ValueAccessor.
437 template<typename AccessorT>
438 bool probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT&) const;
439
440 /// @brief Return the level of the tree (0 = leaf) at which the value
441 /// at the given coordinates resides.
442 ///
443 /// If necessary, update the accessor with pointers to the nodes along the path
444 /// from the root node to the node containing the voxel.
445 /// @note Used internally by ValueAccessor.
446 template<typename AccessorT>
447 Index getValueLevelAndCache(const Coord& xyz, AccessorT&) const;
448
449 /// Mark all values (both tiles and voxels) as active.
450 void setValuesOn();
451
452 //
453 // I/O
454 //
455 void writeTopology(std::ostream&, bool toHalf = false) const;
456 void readTopology(std::istream&, bool fromHalf = false);
457 void writeBuffers(std::ostream&, bool toHalf = false) const;
458 void readBuffers(std::istream&, bool fromHalf = false);
459 void readBuffers(std::istream&, const CoordBBox&, bool fromHalf = false);
460
461
462 //
463 // Aux methods
464 //
465
466 /// Change the sign of all the values represented in this node and its child nodes.
467 void negate();
468
469 /// @brief Set all voxels within a given axis-aligned box to a constant value.
470 /// @param bbox inclusive coordinates of opposite corners of an axis-aligned box
471 /// @param value the value to which to set voxels within the box
472 /// @param active if true, mark voxels within the box as active,
473 /// otherwise mark them as inactive
474 /// @note This operation generates a sparse, but not always optimally sparse,
475 /// representation of the filled box. Follow fill operations with a prune()
476 /// operation for optimal sparseness.
477 void fill(const CoordBBox& bbox, const ValueType& value, bool active = true);
478
479 /// @brief Set all voxels within a given axis-aligned box to a constant value
480 /// and ensure that those voxels are all represented at the leaf level.
481 /// @param bbox inclusive coordinates of opposite corners of an axis-aligned box.
482 /// @param value the value to which to set voxels within the box.
483 /// @param active if true, mark voxels within the box as active,
484 /// otherwise mark them as inactive.
485 /// @sa voxelizeActiveTiles()
486 void denseFill(const CoordBBox& bbox, const ValueType& value, bool active = true);
487
488 /// @brief Densify active tiles, i.e., replace them with leaf-level active voxels.
489 /// @param threaded if true, this operation is multi-threaded (over the internal nodes).
490 /// @sa denseFill()
491 void voxelizeActiveTiles(bool threaded = true);
492
493 /// @brief Copy into a dense grid the values of the voxels that lie within
494 /// a given bounding box.
495 /// @param bbox inclusive bounding box of the voxels to be copied into the dense grid
496 /// @param dense dense grid with a stride in @e z of one (see tools::Dense
497 /// in tools/Dense.h for the required API)
498 /// @note @a bbox is assumed to be identical to or contained in the coordinate domains
499 /// of both the dense grid and this node, i.e., no bounds checking is performed.
500 template<typename DenseT>
501 void copyToDense(const CoordBBox& bbox, DenseT& dense) const;
502
503 /// @brief Efficiently merge another tree into this tree using one of several schemes.
504 /// @warning This operation cannibalizes the other tree.
505 template<MergePolicy Policy>
506 void merge(InternalNode& other, const ValueType& background, const ValueType& otherBackground);
507
508 /// @brief Merge, using one of several schemes, this node (and its descendants)
509 /// with a tile of the same dimensions and the given value and active state.
510 template<MergePolicy Policy> void merge(const ValueType& tileValue, bool tileActive);
511
512 /// @brief Union this branch's set of active values with the other branch's
513 /// active values. The value type of the other branch can be different.
514 /// @details The resulting state of a value is active if the corresponding value
515 /// was already active OR if it is active in the other tree. Also, a resulting
516 /// value maps to a voxel if the corresponding value already mapped to a voxel
517 /// OR if it is a voxel in the other tree. Thus, a resulting value can only
518 /// map to a tile if the corresponding value already mapped to a tile
519 /// AND if it is a tile value in other tree.
520 ///
521 /// Specifically, active tiles and voxels in this branch are not changed, and
522 /// tiles or voxels that were inactive in this branch but active in the other branch
523 /// are marked as active in this branch but left with their original values.
524 template<typename OtherChildNodeType>
525 void topologyUnion(const InternalNode<OtherChildNodeType, Log2Dim>& other, const bool preserveTiles = false);
526
527 /// @brief Intersects this tree's set of active values with the active values
528 /// of the other tree, whose @c ValueType may be different.
529 /// @details The resulting state of a value is active only if the corresponding
530 /// value was already active AND if it is active in the other tree. Also, a
531 /// resulting value maps to a voxel if the corresponding value
532 /// already mapped to an active voxel in either of the two grids
533 /// and it maps to an active tile or voxel in the other grid.
534 ///
535 /// @note This operation can delete branches in this grid if they
536 /// overlap with inactive tiles in the other grid. Likewise active
537 /// voxels can be turned into inactive voxels resulting in leaf
538 /// nodes with no active values. Thus, it is recommended to
539 /// subsequently call prune.
540 template<typename OtherChildNodeType>
542 const ValueType& background);
543
544 /// @brief Difference this node's set of active values with the active values
545 /// of the other node, whose @c ValueType may be different. So a
546 /// resulting voxel will be active only if the original voxel is
547 /// active in this node and inactive in the other node.
548 ///
549 /// @details The last dummy argument is required to match the signature
550 /// for InternalNode::topologyDifference.
551 ///
552 /// @note This operation modifies only active states, not
553 /// values. Also note that this operation can result in all voxels
554 /// being inactive so consider subsequently calling prune.
555 template<typename OtherChildNodeType>
557 const ValueType& background);
558
559 template<typename CombineOp>
560 void combine(InternalNode& other, CombineOp&);
561 template<typename CombineOp>
562 void combine(const ValueType& value, bool valueIsActive, CombineOp&);
563
564 template<typename CombineOp, typename OtherNodeType /*= InternalNode*/>
565 void combine2(const InternalNode& other0, const OtherNodeType& other1, CombineOp&);
566 template<typename CombineOp, typename OtherNodeType /*= InternalNode*/>
567 void combine2(const ValueType& value, const OtherNodeType& other, bool valIsActive, CombineOp&);
568 template<typename CombineOp, typename OtherValueType>
569 void combine2(const InternalNode& other, const OtherValueType&, bool valIsActive, CombineOp&);
570
571 /// Set all voxels that lie outside the given axis-aligned box to the background.
572 void clip(const CoordBBox&, const ValueType& background);
573
574 /// @brief Reduce the memory footprint of this tree by replacing with tiles
575 /// any nodes whose values are all the same (optionally to within a tolerance)
576 /// and have the same active state.
577 void prune(const ValueType& tolerance = zeroVal<ValueType>());
578
579 /// @brief Add the specified leaf to this node, possibly creating a child branch
580 /// in the process. If the leaf node already exists, replace it.
581 void addLeaf(LeafNodeType* leaf);
582
583 /// @brief Same as addLeaf() except, if necessary, update the accessor with pointers
584 /// to the nodes along the path from the root node to the node containing the coordinate.
585 template<typename AccessorT>
586 void addLeafAndCache(LeafNodeType* leaf, AccessorT&);
587
588 /// @brief Return a pointer to the node of type @c NodeT that contains voxel (x, y, z)
589 /// and replace it with a tile of the specified value and state.
590 /// If no such node exists, leave the tree unchanged and return @c nullptr.
591 ///
592 /// @note The caller takes ownership of the node and is responsible for deleting it.
593 ///
594 /// @warning Since this method potentially removes nodes and branches of the tree,
595 /// it is important to clear the caches of all ValueAccessors associated with this tree.
596 template<typename NodeT>
597 NodeT* stealNode(const Coord& xyz, const ValueType& value, bool state);
598
599 /// @brief Add the given child node at this level deducing the offset from it's origin.
600 /// If a child node with this offset already exists, delete the old node and add the
601 /// new node in its place (i.e. ownership of the new child node is transferred to
602 /// this InternalNode)
603 /// @return @c true if inserting the child has been successful, otherwise the caller
604 /// retains ownership of the node and is responsible for deleting it.
605 bool addChild(ChildNodeType* child);
606
607 /// @brief Add a tile at the specified tree level that contains voxel (x, y, z),
608 /// possibly creating a parent branch or deleting a child branch in the process.
609 void addTile(Index level, const Coord& xyz, const ValueType& value, bool state);
610
611 /// @brief Delete any existing child branch at the specified offset and add a tile.
612 void addTile(Index offset, const ValueType& value, bool state);
613
614 /// @brief Same as addTile() except, if necessary, update the accessor with pointers
615 /// to the nodes along the path from the root node to the node containing (x, y, z).
616 template<typename AccessorT>
617 void addTileAndCache(Index level, const Coord& xyz, const ValueType&, bool state, AccessorT&);
618
619 //@{
620 /// @brief Return a pointer to the node that contains voxel (x, y, z).
621 /// If no such node exists, return nullptr.
622 template<typename NodeType> NodeType* probeNode(const Coord& xyz);
623 template<typename NodeType> const NodeType* probeConstNode(const Coord& xyz) const;
624 //@}
625
626 //@{
627 /// @brief Same as probeNode() except, if necessary, update the accessor with pointers
628 /// to the nodes along the path from the root node to the node containing (x, y, z).
629 template<typename NodeType, typename AccessorT>
630 NodeType* probeNodeAndCache(const Coord& xyz, AccessorT&);
631 template<typename NodeType, typename AccessorT>
632 const NodeType* probeConstNodeAndCache(const Coord& xyz, AccessorT&) const;
633 //@}
634
635 //@{
636 /// @brief Return a pointer to the leaf node that contains voxel (x, y, z).
637 /// If no such node exists, return @c nullptr.
638 LeafNodeType* probeLeaf(const Coord& xyz);
639 const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
640 const LeafNodeType* probeLeaf(const Coord& xyz) const;
641 //@}
642
643 //@{
644 /// @brief Same as probeLeaf() except, if necessary, update the accessor with pointers
645 /// to the nodes along the path from the root node to the node containing (x, y, z).
646 template<typename AccessorT>
647 LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc);
648 template<typename AccessorT>
649 const LeafNodeType* probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const;
650 template<typename AccessorT>
651 const LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc) const;
652 //@}
653
654 /// @brief Return the leaf node that contains voxel (x, y, z).
655 /// If no such node exists, create one, but preserve the values and
656 /// active states of all voxels.
657 ///
658 /// @details Use this method to preallocate a static tree topology
659 /// over which to safely perform multithreaded processing.
660 LeafNodeType* touchLeaf(const Coord& xyz);
661
662 /// @brief Same as touchLeaf() except, if necessary, update the accessor with pointers
663 /// to the nodes along the path from the root node to the node containing the coordinate.
664 template<typename AccessorT>
665 LeafNodeType* touchLeafAndCache(const Coord& xyz, AccessorT&);
666
667 //@{
668 /// @brief Adds all nodes of a certain type to a container with the following API:
669 /// @code
670 /// struct ArrayT {
671 /// using value_type = ...;// defines the type of nodes to be added to the array
672 /// void push_back(value_type nodePtr);// method that add nodes to the array
673 /// };
674 /// @endcode
675 /// @details An example of a wrapper around a c-style array is:
676 /// @code
677 /// struct MyArray {
678 /// using value_type = LeafType*;
679 /// value_type* ptr;
680 /// MyArray(value_type* array) : ptr(array) {}
681 /// void push_back(value_type leaf) { *ptr++ = leaf; }
682 ///};
683 /// @endcode
684 /// @details An example that constructs a list of pointer to all leaf nodes is:
685 /// @code
686 /// std::vector<const LeafNodeType*> array;//most std contains have the required API
687 /// array.reserve(tree.leafCount());//this is a fast preallocation.
688 /// tree.getNodes(array);
689 /// @endcode
690 template<typename ArrayT>
691 void getNodes(ArrayT& array);
692 template<typename ArrayT>
693 void getNodes(ArrayT& array) const;
694 //@}
695
696 /// @brief Steals all nodes of a certain type from the tree and
697 /// adds them to a container with the following API:
698 /// @code
699 /// struct ArrayT {
700 /// using value_type = ...;// defines the type of nodes to be added to the array
701 /// void push_back(value_type nodePtr);// method that add nodes to the array
702 /// };
703 /// @endcode
704 /// @details An example of a wrapper around a c-style array is:
705 /// @code
706 /// struct MyArray {
707 /// using value_type = LeafType*;
708 /// value_type* ptr;
709 /// MyArray(value_type* array) : ptr(array) {}
710 /// void push_back(value_type leaf) { *ptr++ = leaf; }
711 ///};
712 /// @endcode
713 /// @details An example that constructs a list of pointer to all leaf nodes is:
714 /// @code
715 /// std::vector<const LeafNodeType*> array;//most std contains have the required API
716 /// array.reserve(tree.leafCount());//this is a fast preallocation.
717 /// tree.stealNodes(array);
718 /// @endcode
719 template<typename ArrayT>
720 void stealNodes(ArrayT& array, const ValueType& value, bool state);
721
722 /// @brief Change inactive tiles or voxels with value oldBackground to newBackground
723 /// or -oldBackground to -newBackground. Active values are unchanged.
724 void resetBackground(const ValueType& oldBackground, const ValueType& newBackground);
725
726 /// @brief Return @c true if the given tree branch has the same node and active value
727 /// topology as this tree branch (but possibly a different @c ValueType).
728 template<typename OtherChildNodeType, Index OtherLog2Dim>
729 bool hasSameTopology(const InternalNode<OtherChildNodeType, OtherLog2Dim>* other) const;
730
731protected:
732 //@{
733 /// Allow iterators to call mask accessor methods (setValueMask(), setChildMask(), etc.).
734 /// @todo Make mask accessors public?
738 //@}
739
740 /// @brief During topology-only construction, access is needed
741 /// to protected/private members of other template instances.
742 template<typename, Index> friend class InternalNode;
743
744 // Mask accessors
745public:
746 bool isValueMaskOn(Index n) const { return mValueMask.isOn(n); }
747 bool isValueMaskOn() const { return mValueMask.isOn(); }
748 bool isValueMaskOff(Index n) const { return mValueMask.isOff(n); }
749 bool isValueMaskOff() const { return mValueMask.isOff(); }
750 bool isChildMaskOn(Index n) const { return mChildMask.isOn(n); }
751 bool isChildMaskOff(Index n) const { return mChildMask.isOff(n); }
752 bool isChildMaskOff() const { return mChildMask.isOff(); }
753 const NodeMaskType& getValueMask() const { return mValueMask; }
754 const NodeMaskType& getChildMask() const { return mChildMask; }
756 {
757 NodeMaskType mask = mValueMask;
758 mask |= mChildMask;
759 mask.toggle();
760 return mask;
761 }
762 const UnionType* getTable() const { return mNodes; }
763protected:
764 //@{
765 /// Use a mask accessor to ensure consistency between the child and value masks;
766 /// i.e., the value mask should always be off wherever the child mask is on.
767 void setValueMask(Index n, bool on) { mValueMask.set(n, mChildMask.isOn(n) ? false : on); }
768 //@}
769
770 void makeChildNodeEmpty(Index n, const ValueType& value);
771 void setChildNode( Index i, ChildNodeType* child);//assumes a tile
772 void resetChildNode(Index i, ChildNodeType* child);//checks for an existing child
773 ChildNodeType* unsetChildNode(Index i, const ValueType& value);
774
775 ///@{
776 /// @brief Returns a pointer to the child node at the linear offset n.
777 /// @warning This protected method assumes that a child node exists at
778 /// the specified linear offset!
779 ChildNodeType* getChildNode(Index n);
780 const ChildNodeType* getChildNode(Index n) const;
781 ///@}
782
783 ///@{
784 /// @brief Protected member classes for recursive multi-threading
785 struct VoxelizeActiveTiles;
786 template<typename OtherInternalNode> struct DeepCopy;
787 template<typename OtherInternalNode> struct TopologyCopy1;
788 template<typename OtherInternalNode> struct TopologyCopy2;
789 template<typename OtherInternalNode> struct TopologyUnion;
790 template<typename OtherInternalNode> struct TopologyDifference;
791 template<typename OtherInternalNode> struct TopologyIntersection;
792 ///@}
793
794 UnionType mNodes[NUM_VALUES];
796 /// Global grid index coordinates (x,y,z) of the local origin of this node
798#if OPENVDB_ABI_VERSION_NUMBER >= 9
799 /// Transient data (not serialized)
800 Index32 mTransientData = 0;
801#endif
802}; // class InternalNode
803
804
805////////////////////////////////////////
806
807
808//@{
809/// Helper metafunction used to implement InternalNode::SameConfiguration
810/// (which, as an inner class, can't be independently specialized)
811template<typename ChildT1, Index Dim1, typename NodeT2>
813 static const bool value = false;
814};
815
816template<typename ChildT1, Index Dim1, typename ChildT2>
817struct SameInternalConfig<ChildT1, Dim1, InternalNode<ChildT2, Dim1> > {
818 static const bool value = ChildT1::template SameConfiguration<ChildT2>::value;
819};
820//@}
821
822
823////////////////////////////////////////
824
825
826template<typename ChildT, Index Log2Dim>
827inline
829{
830 for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(background);
831}
832
833
834template<typename ChildT, Index Log2Dim>
835inline
836InternalNode<ChildT, Log2Dim>::InternalNode(const Coord& origin, const ValueType& val, bool active):
837 mOrigin(origin[0] & ~(DIM - 1), // zero out the low-order bits
838 origin[1] & ~(DIM - 1),
839 origin[2] & ~(DIM - 1))
840{
841 if (active) mValueMask.setOn();
842 for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(val);
843}
844
845
846// For InternalNodes, the PartialCreate constructor is identical to its
847// non-PartialCreate counterpart.
848template<typename ChildT, Index Log2Dim>
849inline
851 const Coord& origin, const ValueType& val, bool active)
852 : mOrigin(origin[0] & ~(DIM-1), origin[1] & ~(DIM-1), origin[2] & ~(DIM-1))
853{
854 if (active) mValueMask.setOn();
855 for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(val);
856}
857
858template<typename ChildT, Index Log2Dim>
859template<typename OtherInternalNode>
860struct InternalNode<ChildT, Log2Dim>::DeepCopy
861{
862 DeepCopy(const OtherInternalNode* source, InternalNode* target) : s(source), t(target) {
863 tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
864 //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//serial
865 }
866 void operator()(const tbb::blocked_range<Index> &r) const {
867 for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
868 if (s->mChildMask.isOff(i)) {
869 t->mNodes[i].setValue(ValueType(s->mNodes[i].getValue()));
870 } else {
871 t->mNodes[i].setChild(new ChildNodeType(*(s->mNodes[i].getChild())));
872 }
873 }
874 }
875 const OtherInternalNode* s;
877};// DeepCopy
878
879template<typename ChildT, Index Log2Dim>
880inline
882 : mChildMask(other.mChildMask)
883 , mValueMask(other.mValueMask)
884 , mOrigin(other.mOrigin)
885#if OPENVDB_ABI_VERSION_NUMBER >= 9
886 , mTransientData(other.mTransientData)
887#endif
888{
889 DeepCopy<InternalNode<ChildT, Log2Dim> > tmp(&other, this);
890}
891
892
893// Copy-construct from a node with the same configuration but a different ValueType.
894template<typename ChildT, Index Log2Dim>
895template<typename OtherChildNodeType>
896inline
898 : mChildMask(other.mChildMask)
899 , mValueMask(other.mValueMask)
900 , mOrigin(other.mOrigin)
901#if OPENVDB_ABI_VERSION_NUMBER >= 9
902 , mTransientData(other.mTransientData)
903#endif
904{
906}
907
908template<typename ChildT, Index Log2Dim>
909template<typename OtherInternalNode>
910struct InternalNode<ChildT, Log2Dim>::TopologyCopy1
911{
912 TopologyCopy1(const OtherInternalNode* source, InternalNode* target,
913 const ValueType& background) : s(source), t(target), b(background) {
914 tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
915 //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//serial
916 }
917 void operator()(const tbb::blocked_range<Index> &r) const {
918 for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
919 if (s->isChildMaskOn(i)) {
920 t->mNodes[i].setChild(new ChildNodeType(*(s->mNodes[i].getChild()),
921 b, TopologyCopy()));
922 } else {
923 t->mNodes[i].setValue(b);
924 }
925 }
926 }
927 const OtherInternalNode* s;
929 const ValueType &b;
930};// TopologyCopy1
931
932template<typename ChildT, Index Log2Dim>
933template<typename OtherChildNodeType>
934inline
936 const ValueType& background, TopologyCopy)
937 : mChildMask(other.mChildMask)
938 , mValueMask(other.mValueMask)
939 , mOrigin(other.mOrigin)
940#if OPENVDB_ABI_VERSION_NUMBER >= 9
941 , mTransientData(other.mTransientData)
942#endif
943{
944 TopologyCopy1<InternalNode<OtherChildNodeType, Log2Dim> > tmp(&other, this, background);
945}
946
947template<typename ChildT, Index Log2Dim>
948template<typename OtherInternalNode>
949struct InternalNode<ChildT, Log2Dim>::TopologyCopy2
950{
951 TopologyCopy2(const OtherInternalNode* source, InternalNode* target,
952 const ValueType& offValue, const ValueType& onValue)
953 : s(source), t(target), offV(offValue), onV(onValue) {
954 tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
955 }
956 void operator()(const tbb::blocked_range<Index> &r) const {
957 for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
958 if (s->isChildMaskOn(i)) {
959 t->mNodes[i].setChild(new ChildNodeType(*(s->mNodes[i].getChild()),
960 offV, onV, TopologyCopy()));
961 } else {
962 t->mNodes[i].setValue(s->isValueMaskOn(i) ? onV : offV);
963 }
964 }
965 }
966 const OtherInternalNode* s;
968 const ValueType &offV, &onV;
969 };// TopologyCopy2
970
971template<typename ChildT, Index Log2Dim>
972template<typename OtherChildNodeType>
973inline
975 const ValueType& offValue,
976 const ValueType& onValue, TopologyCopy)
977 : mChildMask(other.mChildMask)
978 , mValueMask(other.mValueMask)
979 , mOrigin(other.mOrigin)
980#if OPENVDB_ABI_VERSION_NUMBER >= 9
981 , mTransientData(other.mTransientData)
982#endif
983{
984 TopologyCopy2<InternalNode<OtherChildNodeType, Log2Dim> > tmp(&other, this, offValue, onValue);
985}
986
987
988template<typename ChildT, Index Log2Dim>
989inline
991{
992 for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
993 delete mNodes[iter.pos()].getChild();
994 }
995}
996
997
998////////////////////////////////////////
999
1000
1001template<typename ChildT, Index Log2Dim>
1002inline Index32
1004{
1005 if (ChildNodeType::getLevel() == 0) return mChildMask.countOn();
1006 Index32 sum = 0;
1007 for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1008 sum += iter->leafCount();
1009 }
1010 return sum;
1011}
1012
1013template<typename ChildT, Index Log2Dim>
1014inline void
1015InternalNode<ChildT, Log2Dim>::nodeCount(std::vector<Index32> &vec) const
1016{
1017 assert(vec.size() > ChildNodeType::LEVEL);
1018 const auto count = mChildMask.countOn();
1019 if (ChildNodeType::LEVEL > 0 && count > 0) {
1020 for (auto iter = this->cbeginChildOn(); iter; ++iter) iter->nodeCount(vec);
1021 }
1022 vec[ChildNodeType::LEVEL] += count;
1023}
1024
1025
1026template<typename ChildT, Index Log2Dim>
1027inline Index32
1029{
1030 Index32 sum = 1;
1031 if (ChildNodeType::getLevel() == 0) return sum;
1032 for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1033 sum += iter->nonLeafCount();
1034 }
1035 return sum;
1036}
1037
1038
1039template<typename ChildT, Index Log2Dim>
1040inline Index32
1042{
1043 return this->getChildMask().countOn();
1044}
1045
1046
1047template<typename ChildT, Index Log2Dim>
1048inline Index64
1050{
1051 Index64 sum = ChildT::NUM_VOXELS * mValueMask.countOn();
1052 for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1053 sum += iter->onVoxelCount();
1054 }
1055 return sum;
1056}
1057
1058
1059template<typename ChildT, Index Log2Dim>
1060inline Index64
1062{
1063 Index64 sum = ChildT::NUM_VOXELS * (NUM_VALUES-mValueMask.countOn()-mChildMask.countOn());
1064 for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1065 sum += iter->offVoxelCount();
1066 }
1067 return sum;
1068}
1069
1070
1071template<typename ChildT, Index Log2Dim>
1072inline Index64
1074{
1075 Index64 sum = 0;
1076 for (ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
1077 sum += mNodes[iter.pos()].getChild()->onLeafVoxelCount();
1078 }
1079 return sum;
1080}
1081
1082
1083template<typename ChildT, Index Log2Dim>
1084inline Index64
1086{
1087 Index64 sum = 0;
1088 for (ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
1089 sum += mNodes[iter.pos()].getChild()->offLeafVoxelCount();
1090 }
1091 return sum;
1092}
1093
1094template<typename ChildT, Index Log2Dim>
1095inline Index64
1097{
1098 Index64 sum = mValueMask.countOn();
1099 for (ChildOnCIter iter = this->cbeginChildOn(); LEVEL>1 && iter; ++iter) {
1100 sum += iter->onTileCount();
1101 }
1102 return sum;
1103}
1104
1105template<typename ChildT, Index Log2Dim>
1106inline Index64
1108{
1109 Index64 sum = NUM_VALUES * sizeof(UnionType) + mChildMask.memUsage()
1110 + mValueMask.memUsage() + sizeof(mOrigin);
1111 for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1112 sum += iter->memUsage();
1113 }
1114 return sum;
1115}
1116
1117
1118template<typename ChildT, Index Log2Dim>
1119inline void
1121{
1122 if (bbox.isInside(this->getNodeBoundingBox())) return;
1123
1124 for (ValueOnCIter i = this->cbeginValueOn(); i; ++i) {
1125 bbox.expand(i.getCoord(), ChildT::DIM);
1126 }
1127 for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) {
1128 i->evalActiveBoundingBox(bbox, visitVoxels);
1129 }
1130}
1131
1132
1133////////////////////////////////////////
1134
1135
1136template<typename ChildT, Index Log2Dim>
1137inline void
1139{
1140 bool state = false;
1141 ValueType value = zeroVal<ValueType>();
1142 for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1143 const Index i = iter.pos();
1144 ChildT* child = mNodes[i].getChild();
1145 child->prune(tolerance);
1146 if (child->isConstant(value, state, tolerance)) {
1147 delete child;
1148 mChildMask.setOff(i);
1149 mValueMask.set(i, state);
1150 mNodes[i].setValue(value);
1151 }
1152 }
1153}
1154
1155
1156////////////////////////////////////////
1157
1158
1159template<typename ChildT, Index Log2Dim>
1160template<typename NodeT>
1161inline NodeT*
1163{
1164 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
1165 NodeT::LEVEL > ChildT::LEVEL) return nullptr;
1167 const Index n = this->coordToOffset(xyz);
1168 if (mChildMask.isOff(n)) return nullptr;
1169 ChildT* child = mNodes[n].getChild();
1170 if (std::is_same<NodeT, ChildT>::value) {
1171 mChildMask.setOff(n);
1172 mValueMask.set(n, state);
1173 mNodes[n].setValue(value);
1174 }
1175 return (std::is_same<NodeT, ChildT>::value)
1176 ? reinterpret_cast<NodeT*>(child)
1177 : child->template stealNode<NodeT>(xyz, value, state);
1179}
1180
1181
1182////////////////////////////////////////
1183
1184
1185template<typename ChildT, Index Log2Dim>
1186template<typename NodeT>
1187inline NodeT*
1189{
1190 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
1191 NodeT::LEVEL > ChildT::LEVEL) return nullptr;
1193 const Index n = this->coordToOffset(xyz);
1194 if (mChildMask.isOff(n)) return nullptr;
1195 ChildT* child = mNodes[n].getChild();
1196 return (std::is_same<NodeT, ChildT>::value)
1197 ? reinterpret_cast<NodeT*>(child)
1198 : child->template probeNode<NodeT>(xyz);
1200}
1201
1202
1203template<typename ChildT, Index Log2Dim>
1204template<typename NodeT, typename AccessorT>
1205inline NodeT*
1207{
1208 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
1209 NodeT::LEVEL > ChildT::LEVEL) return nullptr;
1211 const Index n = this->coordToOffset(xyz);
1212 if (mChildMask.isOff(n)) return nullptr;
1213 ChildT* child = mNodes[n].getChild();
1214 acc.insert(xyz, child);
1215 return (std::is_same<NodeT, ChildT>::value)
1216 ? reinterpret_cast<NodeT*>(child)
1217 : child->template probeNodeAndCache<NodeT>(xyz, acc);
1219}
1220
1221
1222template<typename ChildT, Index Log2Dim>
1223template<typename NodeT>
1224inline const NodeT*
1226{
1227 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
1228 NodeT::LEVEL > ChildT::LEVEL) return nullptr;
1230 const Index n = this->coordToOffset(xyz);
1231 if (mChildMask.isOff(n)) return nullptr;
1232 const ChildT* child = mNodes[n].getChild();
1233 return (std::is_same<NodeT, ChildT>::value)
1234 ? reinterpret_cast<const NodeT*>(child)
1235 : child->template probeConstNode<NodeT>(xyz);
1237}
1238
1239
1240template<typename ChildT, Index Log2Dim>
1241template<typename NodeT, typename AccessorT>
1242inline const NodeT*
1244{
1245 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
1246 NodeT::LEVEL > ChildT::LEVEL) return nullptr;
1248 const Index n = this->coordToOffset(xyz);
1249 if (mChildMask.isOff(n)) return nullptr;
1250 const ChildT* child = mNodes[n].getChild();
1251 acc.insert(xyz, child);
1252 return (std::is_same<NodeT, ChildT>::value)
1253 ? reinterpret_cast<const NodeT*>(child)
1254 : child->template probeConstNodeAndCache<NodeT>(xyz, acc);
1256}
1257
1258
1259////////////////////////////////////////
1260
1261
1262template<typename ChildT, Index Log2Dim>
1263inline typename ChildT::LeafNodeType*
1265{
1266 return this->template probeNode<LeafNodeType>(xyz);
1267}
1268
1269
1270template<typename ChildT, Index Log2Dim>
1271template<typename AccessorT>
1272inline typename ChildT::LeafNodeType*
1274{
1275 return this->template probeNodeAndCache<LeafNodeType>(xyz, acc);
1276}
1277
1278
1279template<typename ChildT, Index Log2Dim>
1280template<typename AccessorT>
1281inline const typename ChildT::LeafNodeType*
1283{
1284 return this->probeConstLeafAndCache(xyz, acc);
1285}
1286
1287
1288template<typename ChildT, Index Log2Dim>
1289inline const typename ChildT::LeafNodeType*
1291{
1292 return this->template probeConstNode<LeafNodeType>(xyz);
1293}
1294
1295
1296template<typename ChildT, Index Log2Dim>
1297template<typename AccessorT>
1298inline const typename ChildT::LeafNodeType*
1300{
1301 return this->template probeConstNodeAndCache<LeafNodeType>(xyz, acc);
1302}
1303
1304
1305////////////////////////////////////////
1306
1307
1308template<typename ChildT, Index Log2Dim>
1309inline void
1311{
1312 assert(leaf != nullptr);
1313 const Coord& xyz = leaf->origin();
1314 const Index n = this->coordToOffset(xyz);
1315 ChildT* child = nullptr;
1316 if (mChildMask.isOff(n)) {
1317 if (ChildT::LEVEL>0) {
1318 child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1319 } else {
1320 child = reinterpret_cast<ChildT*>(leaf);
1321 }
1322 this->setChildNode(n, child);
1323 } else {
1324 if (ChildT::LEVEL>0) {
1325 child = mNodes[n].getChild();
1326 } else {
1327 delete mNodes[n].getChild();
1328 child = reinterpret_cast<ChildT*>(leaf);
1329 mNodes[n].setChild(child);
1330 }
1331 }
1332 child->addLeaf(leaf);
1333}
1334
1335
1336template<typename ChildT, Index Log2Dim>
1337template<typename AccessorT>
1338inline void
1340{
1341 assert(leaf != nullptr);
1342 const Coord& xyz = leaf->origin();
1343 const Index n = this->coordToOffset(xyz);
1344 ChildT* child = nullptr;
1345 if (mChildMask.isOff(n)) {
1346 if (ChildT::LEVEL>0) {
1347 child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1348 acc.insert(xyz, child);//we only cache internal nodes
1349 } else {
1350 child = reinterpret_cast<ChildT*>(leaf);
1351 }
1352 this->setChildNode(n, child);
1353 } else {
1354 if (ChildT::LEVEL>0) {
1355 child = mNodes[n].getChild();
1356 acc.insert(xyz, child);//we only cache internal nodes
1357 } else {
1358 delete mNodes[n].getChild();
1359 child = reinterpret_cast<ChildT*>(leaf);
1360 mNodes[n].setChild(child);
1361 }
1362 }
1363 child->addLeafAndCache(leaf, acc);
1364}
1365
1366
1367////////////////////////////////////////
1368
1369
1370template<typename ChildT, Index Log2Dim>
1371inline bool
1373{
1374 assert(child);
1375 const Coord& xyz = child->origin();
1376 // verify that the child belongs in this internal node
1377 if (Coord((xyz & ~(DIM-1))) != this->origin()) return false;
1378 // compute the offset and insert the child node
1379 const Index n = this->coordToOffset(xyz);
1380 // this also deletes an existing child node
1381 this->resetChildNode(n, child);
1382 return true;
1383}
1384
1385
1386template<typename ChildT, Index Log2Dim>
1387inline void
1389{
1390 assert(n < NUM_VALUES);
1391 this->makeChildNodeEmpty(n, value);
1392 mValueMask.set(n, state);
1393}
1394
1395
1396template<typename ChildT, Index Log2Dim>
1397inline void
1399 const ValueType& value, bool state)
1400{
1401 if (LEVEL >= level) {
1402 const Index n = this->coordToOffset(xyz);
1403 if (mChildMask.isOff(n)) {// tile case
1404 if (LEVEL > level) {
1405 ChildT* child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1406 this->setChildNode(n, child);
1407 child->addTile(level, xyz, value, state);
1408 } else {
1409 mValueMask.set(n, state);
1410 mNodes[n].setValue(value);
1411 }
1412 } else {// child branch case
1413 ChildT* child = mNodes[n].getChild();
1414 if (LEVEL > level) {
1415 child->addTile(level, xyz, value, state);
1416 } else {
1417 delete child;
1418 mChildMask.setOff(n);
1419 mValueMask.set(n, state);
1420 mNodes[n].setValue(value);
1421 }
1422 }
1423 }
1424}
1425
1426
1427template<typename ChildT, Index Log2Dim>
1428template<typename AccessorT>
1429inline void
1431 const ValueType& value, bool state, AccessorT& acc)
1432{
1433 if (LEVEL >= level) {
1434 const Index n = this->coordToOffset(xyz);
1435 if (mChildMask.isOff(n)) {// tile case
1436 if (LEVEL > level) {
1437 ChildT* child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1438 this->setChildNode(n, child);
1439 acc.insert(xyz, child);
1440 child->addTileAndCache(level, xyz, value, state, acc);
1441 } else {
1442 mValueMask.set(n, state);
1443 mNodes[n].setValue(value);
1444 }
1445 } else {// child branch case
1446 ChildT* child = mNodes[n].getChild();
1447 if (LEVEL > level) {
1448 acc.insert(xyz, child);
1449 child->addTileAndCache(level, xyz, value, state, acc);
1450 } else {
1451 delete child;
1452 mChildMask.setOff(n);
1453 mValueMask.set(n, state);
1454 mNodes[n].setValue(value);
1455 }
1456 }
1457 }
1458}
1459
1460
1461////////////////////////////////////////
1462
1463
1464template<typename ChildT, Index Log2Dim>
1465inline typename ChildT::LeafNodeType*
1467{
1468 const Index n = this->coordToOffset(xyz);
1469 ChildT* child = nullptr;
1470 if (mChildMask.isOff(n)) {
1471 child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1472 this->setChildNode(n, child);
1473 } else {
1474 child = mNodes[n].getChild();
1475 }
1476 return child->touchLeaf(xyz);
1477}
1478
1479
1480template<typename ChildT, Index Log2Dim>
1481template<typename AccessorT>
1482inline typename ChildT::LeafNodeType*
1484{
1485 const Index n = this->coordToOffset(xyz);
1486 if (mChildMask.isOff(n)) {
1487 this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), mValueMask.isOn(n)));
1488 }
1489 acc.insert(xyz, mNodes[n].getChild());
1490 return mNodes[n].getChild()->touchLeafAndCache(xyz, acc);
1491}
1492
1493
1494////////////////////////////////////////
1495
1496
1497template<typename ChildT, Index Log2Dim>
1498inline bool
1500 const ValueType& tolerance) const
1501{
1502 if (!mChildMask.isOff() || !mValueMask.isConstant(state)) return false;// early termination
1503
1504 firstValue = mNodes[0].getValue();
1505 for (Index i = 1; i < NUM_VALUES; ++i) {
1506 if (!math::isApproxEqual(mNodes[i].getValue(), firstValue, tolerance)) {
1507 return false; // early termination
1508 }
1509 }
1510 return true;
1511}
1512
1513
1514////////////////////////////////////////
1515
1516
1517template<typename ChildT, Index Log2Dim>
1518inline bool
1520 ValueType& maxValue,
1521 bool& state,
1522 const ValueType& tolerance) const
1523{
1524
1525 if (!mChildMask.isOff() || !mValueMask.isConstant(state)) return false;// early termination
1526 minValue = maxValue = mNodes[0].getValue();
1527 for (Index i = 1; i < NUM_VALUES; ++i) {
1528 const ValueType& v = mNodes[i].getValue();
1529 if (v < minValue) {
1530 if ((maxValue - v) > tolerance) return false;// early termination
1531 minValue = v;
1532 } else if (v > maxValue) {
1533 if ((v - minValue) > tolerance) return false;// early termination
1534 maxValue = v;
1535 }
1536 }
1537 return true;
1538}
1539
1540
1541////////////////////////////////////////
1542
1543
1544template<typename ChildT, Index Log2Dim>
1545inline bool
1547{
1549 const bool anyActiveTiles = !mValueMask.isOff();
1550 if (LEVEL==1 || anyActiveTiles) return anyActiveTiles;
1551 for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1552 if (iter->hasActiveTiles()) return true;
1553 }
1554 return false;
1556}
1557
1558
1559template<typename ChildT, Index Log2Dim>
1560inline bool
1562{
1563 const Index n = this->coordToOffset(xyz);
1564 if (this->isChildMaskOff(n)) return this->isValueMaskOn(n);
1565 return mNodes[n].getChild()->isValueOn(xyz);
1566}
1567
1568template<typename ChildT, Index Log2Dim>
1569template<typename AccessorT>
1570inline bool
1572{
1573 const Index n = this->coordToOffset(xyz);
1574 if (this->isChildMaskOff(n)) return this->isValueMaskOn(n);
1575 acc.insert(xyz, mNodes[n].getChild());
1576 return mNodes[n].getChild()->isValueOnAndCache(xyz, acc);
1577}
1578
1579
1580template<typename ChildT, Index Log2Dim>
1581inline const typename ChildT::ValueType&
1583{
1584 const Index n = this->coordToOffset(xyz);
1585 return this->isChildMaskOff(n) ? mNodes[n].getValue()
1586 : mNodes[n].getChild()->getValue(xyz);
1587}
1588
1589template<typename ChildT, Index Log2Dim>
1590template<typename AccessorT>
1591inline const typename ChildT::ValueType&
1593{
1594 const Index n = this->coordToOffset(xyz);
1595 if (this->isChildMaskOn(n)) {
1596 acc.insert(xyz, mNodes[n].getChild());
1597 return mNodes[n].getChild()->getValueAndCache(xyz, acc);
1598 }
1599 return mNodes[n].getValue();
1600}
1601
1602
1603template<typename ChildT, Index Log2Dim>
1604inline Index
1606{
1607 const Index n = this->coordToOffset(xyz);
1608 return this->isChildMaskOff(n) ? LEVEL : mNodes[n].getChild()->getValueLevel(xyz);
1609}
1610
1611template<typename ChildT, Index Log2Dim>
1612template<typename AccessorT>
1613inline Index
1615{
1616 const Index n = this->coordToOffset(xyz);
1617 if (this->isChildMaskOn(n)) {
1618 acc.insert(xyz, mNodes[n].getChild());
1619 return mNodes[n].getChild()->getValueLevelAndCache(xyz, acc);
1620 }
1621 return LEVEL;
1622}
1623
1624
1625template<typename ChildT, Index Log2Dim>
1626inline bool
1628{
1629 const Index n = this->coordToOffset(xyz);
1630 if (this->isChildMaskOff(n)) {
1631 value = mNodes[n].getValue();
1632 return this->isValueMaskOn(n);
1633 }
1634 return mNodes[n].getChild()->probeValue(xyz, value);
1635}
1636
1637template<typename ChildT, Index Log2Dim>
1638template<typename AccessorT>
1639inline bool
1641 ValueType& value, AccessorT& acc) const
1642{
1643 const Index n = this->coordToOffset(xyz);
1644 if (this->isChildMaskOn(n)) {
1645 acc.insert(xyz, mNodes[n].getChild());
1646 return mNodes[n].getChild()->probeValueAndCache(xyz, value, acc);
1647 }
1648 value = mNodes[n].getValue();
1649 return this->isValueMaskOn(n);
1650}
1651
1652
1653template<typename ChildT, Index Log2Dim>
1654inline void
1656{
1657 const Index n = this->coordToOffset(xyz);
1658 bool hasChild = this->isChildMaskOn(n);
1659 if (!hasChild && this->isValueMaskOn(n)) {
1660 // If the voxel belongs to a constant tile that is active,
1661 // a child subtree must be constructed.
1662 hasChild = true;
1663 this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), /*active=*/true));
1664 }
1665 if (hasChild) mNodes[n].getChild()->setValueOff(xyz);
1666}
1667
1668
1669template<typename ChildT, Index Log2Dim>
1670inline void
1672{
1673 const Index n = this->coordToOffset(xyz);
1674 bool hasChild = this->isChildMaskOn(n);
1675 if (!hasChild && !this->isValueMaskOn(n)) {
1676 // If the voxel belongs to a constant tile that is inactive,
1677 // a child subtree must be constructed.
1678 hasChild = true;
1679 this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), /*active=*/false));
1680 }
1681 if (hasChild) mNodes[n].getChild()->setValueOn(xyz);
1682}
1683
1684
1685template<typename ChildT, Index Log2Dim>
1686inline void
1688{
1689 const Index n = InternalNode::coordToOffset(xyz);
1690 bool hasChild = this->isChildMaskOn(n);
1691 if (!hasChild) {
1692 const bool active = this->isValueMaskOn(n);
1693 if (active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1694 // If the voxel belongs to a tile that is either active or that
1695 // has a constant value that is different from the one provided,
1696 // a child subtree must be constructed.
1697 hasChild = true;
1698 this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1699 }
1700 }
1701 if (hasChild) mNodes[n].getChild()->setValueOff(xyz, value);
1702}
1703
1704template<typename ChildT, Index Log2Dim>
1705template<typename AccessorT>
1706inline void
1708 const ValueType& value, AccessorT& acc)
1709{
1710 const Index n = InternalNode::coordToOffset(xyz);
1711 bool hasChild = this->isChildMaskOn(n);
1712 if (!hasChild) {
1713 const bool active = this->isValueMaskOn(n);
1714 if (active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1715 // If the voxel belongs to a tile that is either active or that
1716 // has a constant value that is different from the one provided,
1717 // a child subtree must be constructed.
1718 hasChild = true;
1719 this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1720 }
1721 }
1722 if (hasChild) {
1723 ChildT* child = mNodes[n].getChild();
1724 acc.insert(xyz, child);
1725 child->setValueOffAndCache(xyz, value, acc);
1726 }
1727}
1728
1729
1730template<typename ChildT, Index Log2Dim>
1731inline void
1733{
1734 const Index n = this->coordToOffset(xyz);
1735 bool hasChild = this->isChildMaskOn(n);
1736 if (!hasChild) {
1737 const bool active = this->isValueMaskOn(n); // tile's active state
1738 if (!active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1739 // If the voxel belongs to a tile that is either inactive or that
1740 // has a constant value that is different from the one provided,
1741 // a child subtree must be constructed.
1742 hasChild = true;
1743 this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1744 }
1745 }
1746 if (hasChild) mNodes[n].getChild()->setValueOn(xyz, value);
1747}
1748
1749template<typename ChildT, Index Log2Dim>
1750template<typename AccessorT>
1751inline void
1753 const ValueType& value, AccessorT& acc)
1754{
1755 const Index n = this->coordToOffset(xyz);
1756 bool hasChild = this->isChildMaskOn(n);
1757 if (!hasChild) {
1758 const bool active = this->isValueMaskOn(n);
1759 if (!active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1760 // If the voxel belongs to a tile that is either inactive or that
1761 // has a constant value that is different from the one provided,
1762 // a child subtree must be constructed.
1763 hasChild = true;
1764 this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1765 }
1766 }
1767 if (hasChild) {
1768 acc.insert(xyz, mNodes[n].getChild());
1769 mNodes[n].getChild()->setValueAndCache(xyz, value, acc);
1770 }
1771}
1772
1773
1774template<typename ChildT, Index Log2Dim>
1775inline void
1777{
1778 const Index n = this->coordToOffset(xyz);
1779 bool hasChild = this->isChildMaskOn(n);
1780 if (!hasChild && !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1781 // If the voxel has a tile value that is different from the one provided,
1782 // a child subtree must be constructed.
1783 const bool active = this->isValueMaskOn(n);
1784 hasChild = true;
1785 this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1786 }
1787 if (hasChild) mNodes[n].getChild()->setValueOnly(xyz, value);
1788}
1789
1790template<typename ChildT, Index Log2Dim>
1791template<typename AccessorT>
1792inline void
1794 const ValueType& value, AccessorT& acc)
1795{
1796 const Index n = this->coordToOffset(xyz);
1797 bool hasChild = this->isChildMaskOn(n);
1798 if (!hasChild && !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1799 // If the voxel has a tile value that is different from the one provided,
1800 // a child subtree must be constructed.
1801 const bool active = this->isValueMaskOn(n);
1802 hasChild = true;
1803 this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1804 }
1805 if (hasChild) {
1806 acc.insert(xyz, mNodes[n].getChild());
1807 mNodes[n].getChild()->setValueOnlyAndCache(xyz, value, acc);
1808 }
1809}
1810
1811
1812template<typename ChildT, Index Log2Dim>
1813inline void
1815{
1816 const Index n = this->coordToOffset(xyz);
1817 bool hasChild = this->isChildMaskOn(n);
1818 if (!hasChild) {
1819 if (on != this->isValueMaskOn(n)) {
1820 // If the voxel belongs to a tile with the wrong active state,
1821 // then a child subtree must be constructed.
1822 // 'on' is the voxel's new state, therefore '!on' is the tile's current state
1823 hasChild = true;
1824 this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1825 }
1826 }
1827 if (hasChild) mNodes[n].getChild()->setActiveState(xyz, on);
1828}
1829
1830template<typename ChildT, Index Log2Dim>
1831template<typename AccessorT>
1832inline void
1834{
1835 const Index n = this->coordToOffset(xyz);
1836 bool hasChild = this->isChildMaskOn(n);
1837 if (!hasChild) {
1838 if (on != this->isValueMaskOn(n)) {
1839 // If the voxel belongs to a tile with the wrong active state,
1840 // then a child subtree must be constructed.
1841 // 'on' is the voxel's new state, therefore '!on' is the tile's current state
1842 hasChild = true;
1843 this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1844 }
1845 }
1846 if (hasChild) {
1847 ChildT* child = mNodes[n].getChild();
1848 acc.insert(xyz, child);
1849 child->setActiveStateAndCache(xyz, on, acc);
1850 }
1851}
1852
1853
1854template<typename ChildT, Index Log2Dim>
1855inline void
1857{
1858 mValueMask = !mChildMask;
1859 for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1860 mNodes[iter.pos()].getChild()->setValuesOn();
1861 }
1862}
1863
1864
1865template<typename ChildT, Index Log2Dim>
1866template<typename ModifyOp>
1867inline void
1869{
1870 const Index n = InternalNode::coordToOffset(xyz);
1871 bool hasChild = this->isChildMaskOn(n);
1872 if (!hasChild) {
1873 // Need to create a child if the tile is inactive,
1874 // in order to activate voxel (x, y, z).
1875 const bool active = this->isValueMaskOn(n);
1876 bool createChild = !active;
1877 if (!createChild) {
1878 // Need to create a child if applying the functor
1879 // to the tile value produces a different value.
1880 const ValueType& tileVal = mNodes[n].getValue();
1881 ValueType modifiedVal = tileVal;
1882 op(modifiedVal);
1883 createChild = !math::isExactlyEqual(tileVal, modifiedVal);
1884 }
1885 if (createChild) {
1886 hasChild = true;
1887 this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1888 }
1889 }
1890 if (hasChild) mNodes[n].getChild()->modifyValue(xyz, op);
1891}
1892
1893template<typename ChildT, Index Log2Dim>
1894template<typename ModifyOp, typename AccessorT>
1895inline void
1897 AccessorT& acc)
1898{
1899 const Index n = InternalNode::coordToOffset(xyz);
1900 bool hasChild = this->isChildMaskOn(n);
1901 if (!hasChild) {
1902 // Need to create a child if the tile is inactive,
1903 // in order to activate voxel (x, y, z).
1904 const bool active = this->isValueMaskOn(n);
1905 bool createChild = !active;
1906 if (!createChild) {
1907 // Need to create a child if applying the functor
1908 // to the tile value produces a different value.
1909 const ValueType& tileVal = mNodes[n].getValue();
1910 ValueType modifiedVal = tileVal;
1911 op(modifiedVal);
1912 createChild = !math::isExactlyEqual(tileVal, modifiedVal);
1913 }
1914 if (createChild) {
1915 hasChild = true;
1916 this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1917 }
1918 }
1919 if (hasChild) {
1920 ChildNodeType* child = mNodes[n].getChild();
1921 acc.insert(xyz, child);
1922 child->modifyValueAndCache(xyz, op, acc);
1923 }
1924}
1925
1926
1927template<typename ChildT, Index Log2Dim>
1928template<typename ModifyOp>
1929inline void
1931{
1932 const Index n = InternalNode::coordToOffset(xyz);
1933 bool hasChild = this->isChildMaskOn(n);
1934 if (!hasChild) {
1935 const bool tileState = this->isValueMaskOn(n);
1936 const ValueType& tileVal = mNodes[n].getValue();
1937 bool modifiedState = !tileState;
1938 ValueType modifiedVal = tileVal;
1939 op(modifiedVal, modifiedState);
1940 // Need to create a child if applying the functor to the tile
1941 // produces a different value or active state.
1942 if (modifiedState != tileState || !math::isExactlyEqual(modifiedVal, tileVal)) {
1943 hasChild = true;
1944 this->setChildNode(n, new ChildNodeType(xyz, tileVal, tileState));
1945 }
1946 }
1947 if (hasChild) mNodes[n].getChild()->modifyValueAndActiveState(xyz, op);
1948}
1949
1950template<typename ChildT, Index Log2Dim>
1951template<typename ModifyOp, typename AccessorT>
1952inline void
1954 const Coord& xyz, const ModifyOp& op, AccessorT& acc)
1955{
1956 const Index n = InternalNode::coordToOffset(xyz);
1957 bool hasChild = this->isChildMaskOn(n);
1958 if (!hasChild) {
1959 const bool tileState = this->isValueMaskOn(n);
1960 const ValueType& tileVal = mNodes[n].getValue();
1961 bool modifiedState = !tileState;
1962 ValueType modifiedVal = tileVal;
1963 op(modifiedVal, modifiedState);
1964 // Need to create a child if applying the functor to the tile
1965 // produces a different value or active state.
1966 if (modifiedState != tileState || !math::isExactlyEqual(modifiedVal, tileVal)) {
1967 hasChild = true;
1968 this->setChildNode(n, new ChildNodeType(xyz, tileVal, tileState));
1969 }
1970 }
1971 if (hasChild) {
1972 ChildNodeType* child = mNodes[n].getChild();
1973 acc.insert(xyz, child);
1974 child->modifyValueAndActiveStateAndCache(xyz, op, acc);
1975 }
1976}
1977
1978
1979////////////////////////////////////////
1980
1981
1982template<typename ChildT, Index Log2Dim>
1983inline void
1985{
1986 CoordBBox nodeBBox = this->getNodeBoundingBox();
1987 if (!clipBBox.hasOverlap(nodeBBox)) {
1988 // This node lies completely outside the clipping region. Fill it with background tiles.
1989 this->fill(nodeBBox, background, /*active=*/false);
1990 } else if (clipBBox.isInside(nodeBBox)) {
1991 // This node lies completely inside the clipping region. Leave it intact.
1992 return;
1993 }
1994
1995 // This node isn't completely contained inside the clipping region.
1996 // Clip tiles and children, and replace any that lie outside the region
1997 // with background tiles.
1998
1999 for (Index pos = 0; pos < NUM_VALUES; ++pos) {
2000 const Coord xyz = this->offsetToGlobalCoord(pos); // tile or child origin
2001 CoordBBox tileBBox(xyz, xyz.offsetBy(ChildT::DIM - 1)); // tile or child bounds
2002 if (!clipBBox.hasOverlap(tileBBox)) {
2003 // This table entry lies completely outside the clipping region.
2004 // Replace it with a background tile.
2005 this->makeChildNodeEmpty(pos, background);
2006 mValueMask.setOff(pos);
2007 } else if (!clipBBox.isInside(tileBBox)) {
2008 // This table entry does not lie completely inside the clipping region
2009 // and must be clipped.
2010 if (this->isChildMaskOn(pos)) {
2011 mNodes[pos].getChild()->clip(clipBBox, background);
2012 } else {
2013 // Replace this tile with a background tile, then fill the clip region
2014 // with the tile's original value. (This might create a child branch.)
2015 tileBBox.intersect(clipBBox);
2016 const ValueType val = mNodes[pos].getValue();
2017 const bool on = this->isValueMaskOn(pos);
2018 mNodes[pos].setValue(background);
2019 mValueMask.setOff(pos);
2020 this->fill(tileBBox, val, on);
2021 }
2022 } else {
2023 // This table entry lies completely inside the clipping region. Leave it intact.
2024 }
2025 }
2026}
2027
2028
2029////////////////////////////////////////
2030
2031
2032template<typename ChildT, Index Log2Dim>
2033inline void
2035{
2036 auto clippedBBox = this->getNodeBoundingBox();
2037 clippedBBox.intersect(bbox);
2038 if (!clippedBBox) return;
2039
2040 // Iterate over the fill region in axis-aligned, tile-sized chunks.
2041 // (The first and last chunks along each axis might be smaller than a tile.)
2042 Coord xyz, tileMin, tileMax;
2043 for (int x = clippedBBox.min().x(); x <= clippedBBox.max().x(); x = tileMax.x() + 1) {
2044 xyz.setX(x);
2045 for (int y = clippedBBox.min().y(); y <= clippedBBox.max().y(); y = tileMax.y() + 1) {
2046 xyz.setY(y);
2047 for (int z = clippedBBox.min().z(); z <= clippedBBox.max().z(); z = tileMax.z() + 1) {
2048 xyz.setZ(z);
2049
2050 // Get the bounds of the tile that contains voxel (x, y, z).
2051 const Index n = this->coordToOffset(xyz);
2052 tileMin = this->offsetToGlobalCoord(n);
2053 tileMax = tileMin.offsetBy(ChildT::DIM - 1);
2054
2055 if (xyz != tileMin || Coord::lessThan(clippedBBox.max(), tileMax)) {
2056 // If the box defined by (xyz, clippedBBox.max()) doesn't completely enclose
2057 // the tile to which xyz belongs, create a child node (or retrieve
2058 // the existing one).
2059 ChildT* child = nullptr;
2060 if (this->isChildMaskOff(n)) {
2061 // Replace the tile with a newly-created child that is initialized
2062 // with the tile's value and active state.
2063 child = new ChildT{xyz, mNodes[n].getValue(), this->isValueMaskOn(n)};
2064 this->setChildNode(n, child);
2065 } else {
2066 child = mNodes[n].getChild();
2067 }
2068
2069 // Forward the fill request to the child.
2070 if (child) {
2071 const Coord tmp = Coord::minComponent(clippedBBox.max(), tileMax);
2072 child->fill(CoordBBox(xyz, tmp), value, active);
2073 }
2074
2075 } else {
2076 // If the box given by (xyz, clippedBBox.max()) completely encloses
2077 // the tile to which xyz belongs, create the tile (if it
2078 // doesn't already exist) and give it the fill value.
2079 this->makeChildNodeEmpty(n, value);
2080 mValueMask.set(n, active);
2081 }
2082 }
2083 }
2084 }
2085}
2086
2087
2088template<typename ChildT, Index Log2Dim>
2089inline void
2091{
2092 auto clippedBBox = this->getNodeBoundingBox();
2093 clippedBBox.intersect(bbox);
2094 if (!clippedBBox) return;
2095
2096 // Iterate over the fill region in axis-aligned, tile-sized chunks.
2097 // (The first and last chunks along each axis might be smaller than a tile.)
2098 Coord xyz, tileMin, tileMax;
2099 for (int x = clippedBBox.min().x(); x <= clippedBBox.max().x(); x = tileMax.x() + 1) {
2100 xyz.setX(x);
2101 for (int y = clippedBBox.min().y(); y <= clippedBBox.max().y(); y = tileMax.y() + 1) {
2102 xyz.setY(y);
2103 for (int z = clippedBBox.min().z(); z <= clippedBBox.max().z(); z = tileMax.z() + 1) {
2104 xyz.setZ(z);
2105
2106 // Get the table index of the tile that contains voxel (x, y, z).
2107 const auto n = this->coordToOffset(xyz);
2108
2109 // Retrieve the child node at index n, or replace the tile at index n with a child.
2110 ChildT* child = nullptr;
2111 if (this->isChildMaskOn(n)) {
2112 child = mNodes[n].getChild();
2113 } else {
2114 // Replace the tile with a newly-created child that is filled
2115 // with the tile's value and active state.
2116 child = new ChildT{xyz, mNodes[n].getValue(), this->isValueMaskOn(n)};
2117 this->setChildNode(n, child);
2118 }
2119
2120 // Get the bounds of the tile that contains voxel (x, y, z).
2121 tileMin = this->offsetToGlobalCoord(n);
2122 tileMax = tileMin.offsetBy(ChildT::DIM - 1);
2123
2124 // Forward the fill request to the child.
2125 child->denseFill(CoordBBox{xyz, clippedBBox.max()}, value, active);
2126 }
2127 }
2128 }
2129}
2130
2131
2132////////////////////////////////////////
2133
2134
2135template<typename ChildT, Index Log2Dim>
2136template<typename DenseT>
2137inline void
2139{
2140 using DenseValueType = typename DenseT::ValueType;
2141
2142 const size_t xStride = dense.xStride(), yStride = dense.yStride(), zStride = dense.zStride();
2143 const Coord& min = dense.bbox().min();
2144 for (Coord xyz = bbox.min(), max; xyz[0] <= bbox.max()[0]; xyz[0] = max[0] + 1) {
2145 for (xyz[1] = bbox.min()[1]; xyz[1] <= bbox.max()[1]; xyz[1] = max[1] + 1) {
2146 for (xyz[2] = bbox.min()[2]; xyz[2] <= bbox.max()[2]; xyz[2] = max[2] + 1) {
2147 const Index n = this->coordToOffset(xyz);
2148 // Get max coordinates of the child node that contains voxel xyz.
2149 max = this->offsetToGlobalCoord(n).offsetBy(ChildT::DIM-1);
2150
2151 // Get the bbox of the interection of bbox and the child node
2152 CoordBBox sub(xyz, Coord::minComponent(bbox.max(), max));
2153
2154 if (this->isChildMaskOn(n)) {//is a child
2155 mNodes[n].getChild()->copyToDense(sub, dense);
2156 } else {//a tile value
2157 const ValueType value = mNodes[n].getValue();
2158 sub.translate(-min);
2159 DenseValueType* a0 = dense.data() + zStride*sub.min()[2];
2160 for (Int32 x=sub.min()[0], ex=sub.max()[0]+1; x<ex; ++x) {
2161 DenseValueType* a1 = a0 + x*xStride;
2162 for (Int32 y=sub.min()[1], ey=sub.max()[1]+1; y<ey; ++y) {
2163 DenseValueType* a2 = a1 + y*yStride;
2164 for (Int32 z = sub.min()[2], ez = sub.max()[2]+1;
2165 z < ez; ++z, a2 += zStride)
2166 {
2167 *a2 = DenseValueType(value);
2168 }
2169 }
2170 }
2171 }
2172 }
2173 }
2174 }
2175}
2176
2177
2178////////////////////////////////////////
2179
2180
2181template<typename ChildT, Index Log2Dim>
2182inline void
2183InternalNode<ChildT, Log2Dim>::writeTopology(std::ostream& os, bool toHalf) const
2184{
2185 mChildMask.save(os);
2186 mValueMask.save(os);
2187
2188 {
2189 // Copy all of this node's values into an array.
2190 std::unique_ptr<ValueType[]> valuePtr(new ValueType[NUM_VALUES]);
2191 ValueType* values = valuePtr.get();
2192 const ValueType zero = zeroVal<ValueType>();
2193 for (Index i = 0; i < NUM_VALUES; ++i) {
2194 values[i] = (mChildMask.isOff(i) ? mNodes[i].getValue() : zero);
2195 }
2196 // Compress (optionally) and write out the contents of the array.
2197 io::writeCompressedValues(os, values, NUM_VALUES, mValueMask, mChildMask, toHalf);
2198 }
2199 // Write out the child nodes in order.
2200 for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2201 iter->writeTopology(os, toHalf);
2202 }
2203}
2204
2205
2206template<typename ChildT, Index Log2Dim>
2207inline void
2208InternalNode<ChildT, Log2Dim>::readTopology(std::istream& is, bool fromHalf)
2209{
2210 const ValueType background = (!io::getGridBackgroundValuePtr(is) ? zeroVal<ValueType>()
2211 : *static_cast<const ValueType*>(io::getGridBackgroundValuePtr(is)));
2212
2213 mChildMask.load(is);
2214 mValueMask.load(is);
2215
2217 for (Index i = 0; i < NUM_VALUES; ++i) {
2218 if (this->isChildMaskOn(i)) {
2220 new ChildNodeType(PartialCreate(), offsetToGlobalCoord(i), background);
2221 mNodes[i].setChild(child);
2222 child->readTopology(is);
2223 } else {
2225 is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
2226 mNodes[i].setValue(value);
2227 }
2228 }
2229 } else {
2230 const bool oldVersion =
2232 const Index numValues = (oldVersion ? mChildMask.countOff() : NUM_VALUES);
2233 {
2234 // Read in (and uncompress, if necessary) all of this node's values
2235 // into a contiguous array.
2236 std::unique_ptr<ValueType[]> valuePtr(new ValueType[numValues]);
2237 ValueType* values = valuePtr.get();
2238 io::readCompressedValues(is, values, numValues, mValueMask, fromHalf);
2239
2240 // Copy values from the array into this node's table.
2241 if (oldVersion) {
2242 Index n = 0;
2243 for (ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
2244 mNodes[iter.pos()].setValue(values[n++]);
2245 }
2246 assert(n == numValues);
2247 } else {
2248 for (ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
2249 mNodes[iter.pos()].setValue(values[iter.pos()]);
2250 }
2251 }
2252 }
2253 // Read in all child nodes and insert them into the table at their proper locations.
2254 for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2255 ChildNodeType* child = new ChildNodeType(PartialCreate(), iter.getCoord(), background);
2256 mNodes[iter.pos()].setChild(child);
2257 child->readTopology(is, fromHalf);
2258 }
2259 }
2260}
2261
2262
2263////////////////////////////////////////
2264
2265
2266template<typename ChildT, Index Log2Dim>
2267inline const typename ChildT::ValueType&
2269{
2270 return (this->isChildMaskOn(0) ? mNodes[0].getChild()->getFirstValue() : mNodes[0].getValue());
2271}
2272
2273
2274template<typename ChildT, Index Log2Dim>
2275inline const typename ChildT::ValueType&
2277{
2278 const Index n = NUM_VALUES - 1;
2279 return (this->isChildMaskOn(n) ? mNodes[n].getChild()->getLastValue() : mNodes[n].getValue());
2280}
2281
2282
2283////////////////////////////////////////
2284
2285
2286template<typename ChildT, Index Log2Dim>
2287inline void
2289{
2290 for (Index i = 0; i < NUM_VALUES; ++i) {
2291 if (this->isChildMaskOn(i)) {
2292 mNodes[i].getChild()->negate();
2293 } else {
2294 mNodes[i].setValue(math::negative(mNodes[i].getValue()));
2295 }
2296 }
2297
2298}
2299
2300
2301////////////////////////////////////////
2302
2303
2304template<typename ChildT, Index Log2Dim>
2306{
2307 VoxelizeActiveTiles(InternalNode &node) : mNode(&node) {
2308 //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//single thread for debugging
2309 tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
2310
2311 node.mChildMask |= node.mValueMask;
2312 node.mValueMask.setOff();
2313 }
2314 void operator()(const tbb::blocked_range<Index> &r) const
2315 {
2316 for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
2317 if (mNode->mChildMask.isOn(i)) {// Loop over node's child nodes
2318 mNode->mNodes[i].getChild()->voxelizeActiveTiles(true);
2319 } else if (mNode->mValueMask.isOn(i)) {// Loop over node's active tiles
2320 const Coord &ijk = mNode->offsetToGlobalCoord(i);
2321 ChildNodeType *child = new ChildNodeType(ijk, mNode->mNodes[i].getValue(), true);
2322 child->voxelizeActiveTiles(true);
2323 mNode->mNodes[i].setChild(child);
2324 }
2325 }
2326 }
2328};// VoxelizeActiveTiles
2329
2330template<typename ChildT, Index Log2Dim>
2331inline void
2333{
2334 if (threaded) {
2335 VoxelizeActiveTiles tmp(*this);
2336 } else {
2337 for (ValueOnIter iter = this->beginValueOn(); iter; ++iter) {
2338 this->setChildNode(iter.pos(),
2339 new ChildNodeType(iter.getCoord(), iter.getValue(), true));
2340 }
2341 for (ChildOnIter iter = this->beginChildOn(); iter; ++iter)
2342 iter->voxelizeActiveTiles(false);
2343 }
2344}
2345
2346
2347////////////////////////////////////////
2348
2349
2350template<typename ChildT, Index Log2Dim>
2351template<MergePolicy Policy>
2352inline void
2354 const ValueType& background, const ValueType& otherBackground)
2355{
2357
2358 switch (Policy) {
2359
2361 default:
2362 {
2363 for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
2364 const Index n = iter.pos();
2365 if (mChildMask.isOn(n)) {
2366 // Merge this node's child with the other node's child.
2367 mNodes[n].getChild()->template merge<MERGE_ACTIVE_STATES>(*iter,
2368 background, otherBackground);
2369 } else if (mValueMask.isOff(n)) {
2370 // Replace this node's inactive tile with the other node's child
2371 // and replace the other node's child with a tile of undefined value
2372 // (which is okay since the other tree is assumed to be cannibalized
2373 // in the process of merging).
2374 ChildNodeType* child = other.mNodes[n].getChild();
2375 other.mChildMask.setOff(n);
2376 child->resetBackground(otherBackground, background);
2377 this->setChildNode(n, child);
2378 }
2379 }
2380
2381 // Copy active tile values.
2382 for (ValueOnCIter iter = other.cbeginValueOn(); iter; ++iter) {
2383 const Index n = iter.pos();
2384 if (mValueMask.isOff(n)) {
2385 // Replace this node's child or inactive tile with the other node's active tile.
2386 this->makeChildNodeEmpty(n, iter.getValue());
2387 mValueMask.setOn(n);
2388 }
2389 }
2390 break;
2391 }
2392
2393 case MERGE_NODES:
2394 {
2395 for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
2396 const Index n = iter.pos();
2397 if (mChildMask.isOn(n)) {
2398 // Merge this node's child with the other node's child.
2399 mNodes[n].getChild()->template merge<Policy>(*iter, background, otherBackground);
2400 } else {
2401 // Replace this node's tile (regardless of its active state) with
2402 // the other node's child and replace the other node's child with
2403 // a tile of undefined value (which is okay since the other tree
2404 // is assumed to be cannibalized in the process of merging).
2405 ChildNodeType* child = other.mNodes[n].getChild();
2406 other.mChildMask.setOff(n);
2407 child->resetBackground(otherBackground, background);
2408 this->setChildNode(n, child);
2409 }
2410 }
2411 break;
2412 }
2413
2415 {
2416 // Transfer children from the other tree to this tree.
2417 for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
2418 const Index n = iter.pos();
2419 if (mChildMask.isOn(n)) {
2420 // Merge this node's child with the other node's child.
2421 mNodes[n].getChild()->template merge<Policy>(*iter, background, otherBackground);
2422 } else {
2423 // Replace this node's tile with the other node's child, leaving the other
2424 // node with an inactive tile of undefined value (which is okay since
2425 // the other tree is assumed to be cannibalized in the process of merging).
2426 ChildNodeType* child = other.mNodes[n].getChild();
2427 other.mChildMask.setOff(n);
2428 child->resetBackground(otherBackground, background);
2429 if (mValueMask.isOn(n)) {
2430 // Merge the child with this node's active tile.
2431 child->template merge<Policy>(mNodes[n].getValue(), /*on=*/true);
2432 mValueMask.setOff(n);
2433 }
2434 mChildMask.setOn(n);
2435 mNodes[n].setChild(child);
2436 }
2437 }
2438
2439 // Merge active tiles into this tree.
2440 for (ValueOnCIter iter = other.cbeginValueOn(); iter; ++iter) {
2441 const Index n = iter.pos();
2442 if (mChildMask.isOn(n)) {
2443 // Merge the other node's active tile into this node's child.
2444 mNodes[n].getChild()->template merge<Policy>(iter.getValue(), /*on=*/true);
2445 } else if (mValueMask.isOff(n)) {
2446 // Replace this node's inactive tile with the other node's active tile.
2447 mNodes[n].setValue(iter.getValue());
2448 mValueMask.setOn(n);
2449 }
2450 }
2451 break;
2452 }
2453
2454 }
2456}
2457
2458
2459template<typename ChildT, Index Log2Dim>
2460template<MergePolicy Policy>
2461inline void
2462InternalNode<ChildT, Log2Dim>::merge(const ValueType& tileValue, bool tileActive)
2463{
2465
2466 if (Policy != MERGE_ACTIVE_STATES_AND_NODES) return;
2467
2468 // For MERGE_ACTIVE_STATES_AND_NODES, inactive tiles in the other tree are ignored.
2469 if (!tileActive) return;
2470
2471 // Iterate over this node's children and inactive tiles.
2472 for (ValueOffIter iter = this->beginValueOff(); iter; ++iter) {
2473 const Index n = iter.pos();
2474 if (mChildMask.isOn(n)) {
2475 // Merge the other node's active tile into this node's child.
2476 mNodes[n].getChild()->template merge<Policy>(tileValue, /*on=*/true);
2477 } else {
2478 // Replace this node's inactive tile with the other node's active tile.
2479 iter.setValue(tileValue);
2480 mValueMask.setOn(n);
2481 }
2482 }
2484}
2485
2486
2487////////////////////////////////////////
2488
2489
2490template<typename ChildT, Index Log2Dim>
2491template<typename OtherInternalNode>
2493{
2494 using W = typename NodeMaskType::Word;
2495 struct A { inline void operator()(W &tV, const W& sV, const W& tC) const
2496 { tV = (tV | sV) & ~tC; }
2497 };
2498 TopologyUnion(const OtherInternalNode* source, InternalNode* target, const bool preserveTiles)
2499 : s(source), t(target), mPreserveTiles(preserveTiles) {
2500 //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//single thread for debugging
2501 tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
2502
2503 // Bit processing is done in a single thread!
2504 if (!mPreserveTiles) t->mChildMask |= s->mChildMask;//serial but very fast bitwise post-process
2505 else t->mChildMask |= (s->mChildMask & !t->mValueMask);
2506
2507 A op;
2508 t->mValueMask.foreach(s->mValueMask, t->mChildMask, op);
2509 assert((t->mValueMask & t->mChildMask).isOff());//no overlapping active tiles or child nodes
2510 }
2511 void operator()(const tbb::blocked_range<Index> &r) const {
2512 for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
2513 if (s->mChildMask.isOn(i)) {// Loop over other node's child nodes
2514 const typename OtherInternalNode::ChildNodeType& other = *(s->mNodes[i].getChild());
2515 if (t->mChildMask.isOn(i)) {//this has a child node
2516 t->mNodes[i].getChild()->topologyUnion(other, mPreserveTiles);
2517 } else {// this is a tile so replace it with a child branch with identical topology
2518 if (!mPreserveTiles || t->mValueMask.isOff(i)) { // force child topology
2519 ChildT* child = new ChildT(other, t->mNodes[i].getValue(), TopologyCopy());
2520 if (t->mValueMask.isOn(i)) child->setValuesOn();//activate all values
2521 t->mNodes[i].setChild(child);
2522 }
2523 }
2524 } else if (s->mValueMask.isOn(i) && t->mChildMask.isOn(i)) {
2525 t->mNodes[i].getChild()->setValuesOn();
2526 }
2527 }
2528 }
2529 const OtherInternalNode* s;
2531 const bool mPreserveTiles;
2532};// TopologyUnion
2533
2534template<typename ChildT, Index Log2Dim>
2535template<typename OtherChildT>
2536inline void
2538{
2539 TopologyUnion<InternalNode<OtherChildT, Log2Dim> > tmp(&other, this, preserveTiles);
2540}
2541
2542template<typename ChildT, Index Log2Dim>
2543template<typename OtherInternalNode>
2544struct InternalNode<ChildT, Log2Dim>::TopologyIntersection
2545{
2546 using W = typename NodeMaskType::Word;
2547 struct A { inline void operator()(W &tC, const W& sC, const W& sV, const W& tV) const
2548 { tC = (tC & (sC | sV)) | (tV & sC); }
2549 };
2550 TopologyIntersection(const OtherInternalNode* source, InternalNode* target,
2551 const ValueType& background) : s(source), t(target), b(background) {
2552 //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//single thread for debugging
2553 tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
2554
2555 // Bit processing is done in a single thread!
2556 A op;
2557 t->mChildMask.foreach(s->mChildMask, s->mValueMask, t->mValueMask, op);
2558
2559 t->mValueMask &= s->mValueMask;
2560 assert((t->mValueMask & t->mChildMask).isOff());//no overlapping active tiles or child nodes
2561 }
2562 void operator()(const tbb::blocked_range<Index> &r) const {
2563 for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
2564 if (t->mChildMask.isOn(i)) {// Loop over this node's child nodes
2565 ChildT* child = t->mNodes[i].getChild();
2566 if (s->mChildMask.isOn(i)) {//other also has a child node
2567 child->topologyIntersection(*(s->mNodes[i].getChild()), b);
2568 } else if (s->mValueMask.isOff(i)) {//other is an inactive tile
2569 delete child;//convert child to an inactive tile
2570 t->mNodes[i].setValue(b);
2571 }
2572 } else if (t->mValueMask.isOn(i) && s->mChildMask.isOn(i)) {//active tile -> a branch
2573 t->mNodes[i].setChild(new ChildT(*(s->mNodes[i].getChild()),
2574 t->mNodes[i].getValue(), TopologyCopy()));
2575 }
2576 }
2577 }
2578 const OtherInternalNode* s;
2580 const ValueType& b;
2581};// TopologyIntersection
2582
2583template<typename ChildT, Index Log2Dim>
2584template<typename OtherChildT>
2585inline void
2591
2592template<typename ChildT, Index Log2Dim>
2593template<typename OtherInternalNode>
2594struct InternalNode<ChildT, Log2Dim>::TopologyDifference
2595{
2596 using W = typename NodeMaskType::Word;
2597 struct A {inline void operator()(W &tC, const W& sC, const W& sV, const W& tV) const
2598 { tC = (tC & (sC | ~sV)) | (tV & sC); }
2599 };
2600 struct B {inline void operator()(W &tV, const W& sC, const W& sV, const W& tC) const
2601 { tV &= ~((tC & sV) | (sC | sV)); }
2602 };
2603 TopologyDifference(const OtherInternalNode* source, InternalNode* target,
2604 const ValueType& background) : s(source), t(target), b(background) {
2605 //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//single thread for debugging
2606 tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
2607
2608 // Bit processing is done in a single thread!
2609 const NodeMaskType oldChildMask(t->mChildMask);//important to avoid cross pollution
2610 A op1;
2611 t->mChildMask.foreach(s->mChildMask, s->mValueMask, t->mValueMask, op1);
2612
2613 B op2;
2614 t->mValueMask.foreach(t->mChildMask, s->mValueMask, oldChildMask, op2);
2615 assert((t->mValueMask & t->mChildMask).isOff());//no overlapping active tiles or child nodes
2616 }
2617 void operator()(const tbb::blocked_range<Index> &r) const {
2618 for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
2619 if (t->mChildMask.isOn(i)) {// Loop over this node's child nodes
2620 ChildT* child = t->mNodes[i].getChild();
2621 if (s->mChildMask.isOn(i)) {
2622 child->topologyDifference(*(s->mNodes[i].getChild()), b);
2623 } else if (s->mValueMask.isOn(i)) {
2624 delete child;//convert child to an inactive tile
2625 t->mNodes[i].setValue(b);
2626 }
2627 } else if (t->mValueMask.isOn(i)) {//this is an active tile
2628 if (s->mChildMask.isOn(i)) {
2629 const typename OtherInternalNode::ChildNodeType& other =
2630 *(s->mNodes[i].getChild());
2631 ChildT* child = new ChildT(other.origin(), t->mNodes[i].getValue(), true);
2632 child->topologyDifference(other, b);
2633 t->mNodes[i].setChild(child);//replace the active tile with a child branch
2634 }
2635 }
2636 }
2637 }
2638 const OtherInternalNode* s;
2640 const ValueType& b;
2641};// TopologyDifference
2642
2643template<typename ChildT, Index Log2Dim>
2644template<typename OtherChildT>
2645inline void
2651
2652
2653////////////////////////////////////////
2654
2655
2656template<typename ChildT, Index Log2Dim>
2657template<typename CombineOp>
2658inline void
2660{
2661 const ValueType zero = zeroVal<ValueType>();
2662
2664
2665 for (Index i = 0; i < NUM_VALUES; ++i) {
2666 if (this->isChildMaskOff(i) && other.isChildMaskOff(i)) {
2667 // Both this node and the other node have constant values (tiles).
2668 // Combine the two values and store the result as this node's new tile value.
2669 op(args.setARef(mNodes[i].getValue())
2670 .setAIsActive(isValueMaskOn(i))
2671 .setBRef(other.mNodes[i].getValue())
2672 .setBIsActive(other.isValueMaskOn(i)));
2673 mNodes[i].setValue(args.result());
2674 mValueMask.set(i, args.resultIsActive());
2675 } else if (this->isChildMaskOn(i) && other.isChildMaskOff(i)) {
2676 // Combine this node's child with the other node's constant value.
2677 ChildNodeType* child = mNodes[i].getChild();
2678 assert(child);
2679 if (child) {
2680 child->combine(other.mNodes[i].getValue(), other.isValueMaskOn(i), op);
2681 }
2682 } else if (this->isChildMaskOff(i) && other.isChildMaskOn(i)) {
2683 // Combine this node's constant value with the other node's child.
2684 ChildNodeType* child = other.mNodes[i].getChild();
2685 assert(child);
2686 if (child) {
2687 // Combine this node's constant value with the other node's child,
2688 // but use a new functor in which the A and B values are swapped,
2689 // since the constant value is the A value, not the B value.
2691 child->combine(mNodes[i].getValue(), isValueMaskOn(i), swappedOp);
2692
2693 // Steal the other node's child.
2694 other.mChildMask.setOff(i);
2695 other.mNodes[i].setValue(zero);
2696 this->setChildNode(i, child);
2697 }
2698
2699 } else /*if (isChildMaskOn(i) && other.isChildMaskOn(i))*/ {
2700 // Combine this node's child with the other node's child.
2702 *child = mNodes[i].getChild(),
2703 *otherChild = other.mNodes[i].getChild();
2704 assert(child);
2705 assert(otherChild);
2706 if (child && otherChild) {
2707 child->combine(*otherChild, op);
2708 }
2709 }
2710 }
2711}
2712
2713
2714template<typename ChildT, Index Log2Dim>
2715template<typename CombineOp>
2716inline void
2717InternalNode<ChildT, Log2Dim>::combine(const ValueType& value, bool valueIsActive, CombineOp& op)
2718{
2720
2721 for (Index i = 0; i < NUM_VALUES; ++i) {
2722 if (this->isChildMaskOff(i)) {
2723 // Combine this node's constant value with the given constant value.
2724 op(args.setARef(mNodes[i].getValue())
2725 .setAIsActive(isValueMaskOn(i))
2726 .setBRef(value)
2727 .setBIsActive(valueIsActive));
2728 mNodes[i].setValue(args.result());
2729 mValueMask.set(i, args.resultIsActive());
2730 } else /*if (isChildMaskOn(i))*/ {
2731 // Combine this node's child with the given constant value.
2732 ChildNodeType* child = mNodes[i].getChild();
2733 assert(child);
2734 if (child) child->combine(value, valueIsActive, op);
2735 }
2736 }
2737}
2738
2739
2740////////////////////////////////////////
2741
2742
2743template<typename ChildT, Index Log2Dim>
2744template<typename CombineOp, typename OtherNodeType>
2745inline void
2746InternalNode<ChildT, Log2Dim>::combine2(const InternalNode& other0, const OtherNodeType& other1,
2747 CombineOp& op)
2748{
2750
2751 for (Index i = 0; i < NUM_VALUES; ++i) {
2752 if (other0.isChildMaskOff(i) && other1.isChildMaskOff(i)) {
2753 op(args.setARef(other0.mNodes[i].getValue())
2754 .setAIsActive(other0.isValueMaskOn(i))
2755 .setBRef(other1.mNodes[i].getValue())
2756 .setBIsActive(other1.isValueMaskOn(i)));
2757 // Replace child i with a constant value.
2758 this->makeChildNodeEmpty(i, args.result());
2759 mValueMask.set(i, args.resultIsActive());
2760 } else {
2761 if (this->isChildMaskOff(i)) {
2762 // Add a new child with the same coordinates, etc. as the other node's child.
2763 const Coord& childOrigin = other0.isChildMaskOn(i)
2764 ? other0.mNodes[i].getChild()->origin()
2765 : other1.mNodes[i].getChild()->origin();
2766 this->setChildNode(i, new ChildNodeType(childOrigin, mNodes[i].getValue()));
2767 }
2768
2769 if (other0.isChildMaskOff(i)) {
2770 // Combine node1's child with node0's constant value
2771 // and write the result into child i.
2772 mNodes[i].getChild()->combine2(other0.mNodes[i].getValue(),
2773 *other1.mNodes[i].getChild(), other0.isValueMaskOn(i), op);
2774 } else if (other1.isChildMaskOff(i)) {
2775 // Combine node0's child with node1's constant value
2776 // and write the result into child i.
2777 mNodes[i].getChild()->combine2(*other0.mNodes[i].getChild(),
2778 other1.mNodes[i].getValue(), other1.isValueMaskOn(i), op);
2779 } else {
2780 // Combine node0's child with node1's child
2781 // and write the result into child i.
2782 mNodes[i].getChild()->combine2(*other0.mNodes[i].getChild(),
2783 *other1.mNodes[i].getChild(), op);
2784 }
2785 }
2786 }
2787}
2788
2789
2790template<typename ChildT, Index Log2Dim>
2791template<typename CombineOp, typename OtherNodeType>
2792inline void
2794 bool valueIsActive, CombineOp& op)
2795{
2797
2798 for (Index i = 0; i < NUM_VALUES; ++i) {
2799 if (other.isChildMaskOff(i)) {
2800 op(args.setARef(value)
2801 .setAIsActive(valueIsActive)
2802 .setBRef(other.mNodes[i].getValue())
2803 .setBIsActive(other.isValueMaskOn(i)));
2804 // Replace child i with a constant value.
2805 this->makeChildNodeEmpty(i, args.result());
2806 mValueMask.set(i, args.resultIsActive());
2807 } else {
2808 typename OtherNodeType::ChildNodeType* otherChild = other.mNodes[i].getChild();
2809 assert(otherChild);
2810 if (this->isChildMaskOff(i)) {
2811 // Add a new child with the same coordinates, etc.
2812 // as the other node's child.
2813 this->setChildNode(i, new ChildNodeType(*otherChild));
2814 }
2815 // Combine the other node's child with a constant value
2816 // and write the result into child i.
2817 mNodes[i].getChild()->combine2(value, *otherChild, valueIsActive, op);
2818 }
2819 }
2820}
2821
2822
2823template<typename ChildT, Index Log2Dim>
2824template<typename CombineOp, typename OtherValueType>
2825inline void
2827 bool valueIsActive, CombineOp& op)
2828{
2830
2831 for (Index i = 0; i < NUM_VALUES; ++i) {
2832 if (other.isChildMaskOff(i)) {
2833 op(args.setARef(other.mNodes[i].getValue())
2834 .setAIsActive(other.isValueMaskOn(i))
2835 .setBRef(value)
2836 .setBIsActive(valueIsActive));
2837 // Replace child i with a constant value.
2838 this->makeChildNodeEmpty(i, args.result());
2839 mValueMask.set(i, args.resultIsActive());
2840 } else {
2841 ChildNodeType* otherChild = other.mNodes[i].getChild();
2842 assert(otherChild);
2843 if (this->isChildMaskOff(i)) {
2844 // Add a new child with the same coordinates, etc. as the other node's child.
2845 this->setChildNode(i,
2846 new ChildNodeType(otherChild->origin(), mNodes[i].getValue()));
2847 }
2848 // Combine the other node's child with a constant value
2849 // and write the result into child i.
2850 mNodes[i].getChild()->combine2(*otherChild, value, valueIsActive, op);
2851 }
2852 }
2853}
2854
2855
2856////////////////////////////////////////
2857
2858
2859template<typename ChildT, Index Log2Dim>
2860inline void
2861InternalNode<ChildT, Log2Dim>::writeBuffers(std::ostream& os, bool toHalf) const
2862{
2863 for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2864 iter->writeBuffers(os, toHalf);
2865 }
2866}
2867
2868
2869template<typename ChildT, Index Log2Dim>
2870inline void
2871InternalNode<ChildT, Log2Dim>::readBuffers(std::istream& is, bool fromHalf)
2872{
2873 for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2874 iter->readBuffers(is, fromHalf);
2875 }
2876}
2877
2878
2879template<typename ChildT, Index Log2Dim>
2880inline void
2882 const CoordBBox& clipBBox, bool fromHalf)
2883{
2884 for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2885 // Stream in the branch rooted at this child.
2886 // (We can't skip over children that lie outside the clipping region,
2887 // because buffers are serialized in depth-first order and need to be
2888 // unserialized in the same order.)
2889 iter->readBuffers(is, clipBBox, fromHalf);
2890 }
2891
2892 // Get this tree's background value.
2893 ValueType background = zeroVal<ValueType>();
2894 if (const void* bgPtr = io::getGridBackgroundValuePtr(is)) {
2895 background = *static_cast<const ValueType*>(bgPtr);
2896 }
2897 this->clip(clipBBox, background);
2898}
2899
2900
2901////////////////////////////////////////
2902
2903
2904template<typename ChildT, Index Log2Dim>
2905void
2907{
2908 dims.push_back(Log2Dim);
2909 ChildNodeType::getNodeLog2Dims(dims);
2910}
2911
2912
2913template<typename ChildT, Index Log2Dim>
2914inline void
2916{
2917 assert(n<(1<<3*Log2Dim));
2918 xyz.setX(n >> 2*Log2Dim);
2919 n &= ((1<<2*Log2Dim)-1);
2920 xyz.setY(n >> Log2Dim);
2921 xyz.setZ(n & ((1<<Log2Dim)-1));
2922}
2923
2924
2925template<typename ChildT, Index Log2Dim>
2926inline Index
2928{
2929 return (((xyz[0] & (DIM-1u)) >> ChildNodeType::TOTAL) << 2*Log2Dim)
2930 + (((xyz[1] & (DIM-1u)) >> ChildNodeType::TOTAL) << Log2Dim)
2931 + ((xyz[2] & (DIM-1u)) >> ChildNodeType::TOTAL);
2932}
2933
2934
2935template<typename ChildT, Index Log2Dim>
2936inline Coord
2938{
2939 Coord local;
2940 this->offsetToLocalCoord(n, local);
2941 local <<= ChildT::TOTAL;
2942 return local + this->origin();
2943}
2944
2945
2946////////////////////////////////////////
2947
2948
2949template<typename ChildT, Index Log2Dim>
2950template<typename ArrayT>
2951inline void
2953{
2954 using T = typename ArrayT::value_type;
2955 static_assert(std::is_pointer<T>::value, "argument to getNodes() must be a pointer array");
2956 using ArrayChildT = typename std::conditional<
2957 std::is_const<typename std::remove_pointer<T>::type>::value, const ChildT, ChildT>::type;
2958 for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2960 if (std::is_same<T, ArrayChildT*>::value) {
2961 array.push_back(reinterpret_cast<T>(mNodes[iter.pos()].getChild()));
2962 } else {
2963 iter->getNodes(array);//descent
2964 }
2966 }
2967}
2968
2969template<typename ChildT, Index Log2Dim>
2970template<typename ArrayT>
2971inline void
2973{
2974 using T = typename ArrayT::value_type;
2975 static_assert(std::is_pointer<T>::value, "argument to getNodes() must be a pointer array");
2976 static_assert(std::is_const<typename std::remove_pointer<T>::type>::value,
2977 "argument to getNodes() must be an array of const node pointers");
2978 for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2980 if (std::is_same<T, const ChildT*>::value) {
2981 array.push_back(reinterpret_cast<T>(mNodes[iter.pos()].getChild()));
2982 } else {
2983 iter->getNodes(array);//descent
2984 }
2986 }
2987}
2988
2989
2990////////////////////////////////////////
2991
2992
2993template<typename ChildT, Index Log2Dim>
2994template<typename ArrayT>
2995inline void
2997{
2998 using T = typename ArrayT::value_type;
2999 static_assert(std::is_pointer<T>::value, "argument to stealNodes() must be a pointer array");
3000 using ArrayChildT = typename std::conditional<
3001 std::is_const<typename std::remove_pointer<T>::type>::value, const ChildT, ChildT>::type;
3003 for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
3004 const Index n = iter.pos();
3005 if (std::is_same<T, ArrayChildT*>::value) {
3006 array.push_back(reinterpret_cast<T>(mNodes[n].getChild()));
3007 mValueMask.set(n, state);
3008 mNodes[n].setValue(value);
3009 } else {
3010 iter->stealNodes(array, value, state);//descent
3011 }
3012 }
3013 if (std::is_same<T, ArrayChildT*>::value) mChildMask.setOff();
3015}
3016
3017
3018////////////////////////////////////////
3019
3020
3021template<typename ChildT, Index Log2Dim>
3022inline void
3024 const ValueType& newBackground)
3025{
3026 if (math::isExactlyEqual(oldBackground, newBackground)) return;
3027 for (Index i = 0; i < NUM_VALUES; ++i) {
3028 if (this->isChildMaskOn(i)) {
3029 mNodes[i].getChild()->resetBackground(oldBackground, newBackground);
3030 } else if (this->isValueMaskOff(i)) {
3031 if (math::isApproxEqual(mNodes[i].getValue(), oldBackground)) {
3032 mNodes[i].setValue(newBackground);
3033 } else if (math::isApproxEqual(mNodes[i].getValue(), math::negative(oldBackground))) {
3034 mNodes[i].setValue(math::negative(newBackground));
3035 }
3036 }
3037 }
3038}
3039
3040template<typename ChildT, Index Log2Dim>
3041template<typename OtherChildNodeType, Index OtherLog2Dim>
3042inline bool
3045{
3046 if (Log2Dim != OtherLog2Dim || mChildMask != other->mChildMask ||
3047 mValueMask != other->mValueMask) return false;
3048 for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
3049 if (!iter->hasSameTopology(other->mNodes[iter.pos()].getChild())) return false;
3050 }
3051 return true;
3052}
3053
3054
3055template<typename ChildT, Index Log2Dim>
3056inline void
3058{
3059 assert(child);
3060 if (this->isChildMaskOn(i)) {
3061 delete mNodes[i].getChild();
3062 } else {
3063 mChildMask.setOn(i);
3064 mValueMask.setOff(i);
3065 }
3066 mNodes[i].setChild(child);
3067}
3068
3069template<typename ChildT, Index Log2Dim>
3070inline void
3072{
3073 assert(child);
3074 assert(mChildMask.isOff(i));
3075 mChildMask.setOn(i);
3076 mValueMask.setOff(i);
3077 mNodes[i].setChild(child);
3078}
3079
3080
3081template<typename ChildT, Index Log2Dim>
3082inline ChildT*
3084{
3085 if (this->isChildMaskOff(i)) {
3086 mNodes[i].setValue(value);
3087 return nullptr;
3088 }
3089 ChildNodeType* child = mNodes[i].getChild();
3090 mChildMask.setOff(i);
3091 mNodes[i].setValue(value);
3092 return child;
3093}
3094
3095
3096template<typename ChildT, Index Log2Dim>
3097inline void
3099{
3100 delete this->unsetChildNode(n, value);
3101}
3102
3103template<typename ChildT, Index Log2Dim>
3104inline ChildT*
3106{
3107 assert(this->isChildMaskOn(n));
3108 return mNodes[n].getChild();
3109}
3110
3111
3112template<typename ChildT, Index Log2Dim>
3113inline const ChildT*
3115{
3116 assert(this->isChildMaskOn(n));
3117 return mNodes[n].getChild();
3118}
3119
3120} // namespace tree
3121} // namespace OPENVDB_VERSION_NAME
3122} // namespace openvdb
3123
3124#endif // OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED
ValueT value
Definition GridBuilder.h:1290
ChildT * child
Definition GridBuilder.h:1289
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_END
Definition Platform.h:118
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
Definition Platform.h:117
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition Types.h:530
CombineArgs & setARef(const AValueType &a)
Redirect the A value to a new external source.
Definition Types.h:582
const AValueType & result() const
Get the output value.
Definition Types.h:574
CombineArgs & setBIsActive(bool b)
Set the active state of the B value.
Definition Types.h:598
CombineArgs & setBRef(const BValueType &b)
Redirect the B value to a new external source.
Definition Types.h:584
bool resultIsActive() const
Definition Types.h:593
CombineArgs & setAIsActive(bool b)
Set the active state of the A value.
Definition Types.h:596
Tag dispatch class that distinguishes constructors that deep copy.
Definition Types.h:646
Tag dispatch class that distinguishes constructors during file input.
Definition Types.h:650
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition Types.h:644
Axis-aligned bounding box of signed integer coordinates.
Definition Coord.h:249
void translate(const Coord &t)
Translate this bounding box by (tx, ty, tz).
Definition Coord.h:458
void expand(ValueType padding)
Pad this bounding box with the specified padding.
Definition Coord.h:418
const Coord & min() const
Definition Coord.h:321
bool hasOverlap(const CoordBBox &b) const
Return true if the given bounding box overlaps with this bounding box.
Definition Coord.h:412
const Coord & max() const
Definition Coord.h:322
bool isInside(const Coord &xyz) const
Return true if point (x, y, z) is inside this bounding box.
Definition Coord.h:400
void intersect(const CoordBBox &bbox)
Intersect this bounding box with the given bounding box.
Definition Coord.h:444
Signed (x, y, z) 32-bit integer coordinates.
Definition Coord.h:25
Int32 y() const
Definition Coord.h:131
Coord offsetBy(Int32 dx, Int32 dy, Int32 dz) const
Definition Coord.h:91
void minComponent(const Coord &other)
Perform a component-wise minimum with the other Coord.
Definition Coord.h:175
Int32 x() const
Definition Coord.h:130
Coord & setZ(Int32 z)
Definition Coord.h:81
Coord & setY(Int32 y)
Definition Coord.h:80
static Coord max()
Return the largest possible coordinate.
Definition Coord.h:46
static bool lessThan(const Coord &a, const Coord &b)
Definition Coord.h:208
Int32 z() const
Definition Coord.h:132
Coord & setX(Int32 x)
Definition Coord.h:79
Definition InternalNode.h:34
void setValueAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition InternalNode.h:1752
bool isValueOn(Index offset) const
Return true if the voxel at the given offset is active.
Definition InternalNode.h:335
void merge(InternalNode &other, const ValueType &background, const ValueType &otherBackground)
Efficiently merge another tree into this tree using one of several schemes.
Definition InternalNode.h:2353
ChildOnCIter cbeginChildOn() const
Definition InternalNode.h:220
const ValueType & getFirstValue() const
If the first entry in this node's table is a tile, return the tile's value. Otherwise,...
Definition InternalNode.h:2268
CoordBBox getNodeBoundingBox() const
Return the bounding box of this node, i.e., the full index space spanned by the node regardless of it...
Definition InternalNode.h:299
ChildOnCIter beginChildOn() const
Definition InternalNode.h:223
ChildOnIter beginChildOn()
Definition InternalNode.h:226
NodeType * probeNode(const Coord &xyz)
Return a pointer to the node that contains voxel (x, y, z). If no such node exists,...
bool isChildMaskOff(Index n) const
Definition InternalNode.h:751
bool isValueOn(const Coord &xyz) const
Return true if the voxel at the given coordinates is active.
Definition InternalNode.h:1561
void writeTopology(std::ostream &, bool toHalf=false) const
Definition InternalNode.h:2183
void copyToDense(const CoordBBox &bbox, DenseT &dense) const
Copy into a dense grid the values of the voxels that lie within a given bounding box.
Definition InternalNode.h:2138
void setChildNode(Index i, ChildNodeType *child)
Definition InternalNode.h:3071
bool isChildMaskOff() const
Definition InternalNode.h:752
ValueOffCIter cbeginValueOff() const
Definition InternalNode.h:232
LeafNodeType * probeLeafAndCache(const Coord &xyz, AccessorT &acc)
Same as probeLeaf() except, if necessary, update the accessor with pointers to the nodes along the pa...
Index32 transientData() const
Return the transient data value.
Definition InternalNode.h:273
void addLeafAndCache(LeafNodeType *leaf, AccessorT &)
Same as addLeaf() except, if necessary, update the accessor with pointers to the nodes along the path...
Definition InternalNode.h:1339
static Index getChildDim()
Definition InternalNode.h:256
const NodeMaskType & getChildMask() const
Definition InternalNode.h:754
Index32 nonLeafCount() const
Definition InternalNode.h:1028
void topologyIntersection(const InternalNode< OtherChildNodeType, Log2Dim > &other, const ValueType &background)
Intersects this tree's set of active values with the active values of the other tree,...
NodeMaskType mChildMask
Definition InternalNode.h:795
bool isValueMaskOff() const
Definition InternalNode.h:749
void getNodes(ArrayT &array)
Adds all nodes of a certain type to a container with the following API:
Definition InternalNode.h:2952
bool isValueMaskOn() const
Definition InternalNode.h:747
NodeT * stealNode(const Coord &xyz, const ValueType &value, bool state)
Return a pointer to the node of type NodeT that contains voxel (x, y, z) and replace it with a tile o...
Definition InternalNode.h:1162
void voxelizeActiveTiles(bool threaded=true)
Densify active tiles, i.e., replace them with leaf-level active voxels.
Definition InternalNode.h:2332
NodeMaskType mValueMask
Definition InternalNode.h:795
InternalNode()
Default constructor.
Definition InternalNode.h:72
bool isChildMaskOn(Index n) const
Definition InternalNode.h:750
~InternalNode()
Definition InternalNode.h:990
Index64 onLeafVoxelCount() const
Definition InternalNode.h:1073
const LeafNodeType * probeConstLeafAndCache(const Coord &xyz, AccessorT &acc) const
NodeMaskType getValueOffMask() const
Definition InternalNode.h:755
LeafNodeType * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists,...
Definition InternalNode.h:1264
ValueAllCIter cbeginValueAll() const
Definition InternalNode.h:233
void prune(const ValueType &tolerance=zeroVal< ValueType >())
Reduce the memory footprint of this tree by replacing with tiles any nodes whose values are all the s...
Definition InternalNode.h:1138
ValueOnCIter beginValueOn() const
Definition InternalNode.h:234
Index64 offLeafVoxelCount() const
Definition InternalNode.h:1085
void resetBackground(const ValueType &oldBackground, const ValueType &newBackground)
Change inactive tiles or voxels with value oldBackground to newBackground or -oldBackground to -newBa...
Definition InternalNode.h:3023
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 creating a parent bran...
Definition InternalNode.h:1398
void setOrigin(const Coord &origin)
Set the grid index coordinates of this node's local origin.
Definition InternalNode.h:269
const Coord & origin() const
Return the grid index coordinates of this node's local origin.
Definition InternalNode.h:267
bool isInactive() const
Return true if this node has no children and only contains inactive values.
Definition InternalNode.h:330
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition InternalNode.h:1930
void setValueOnlyAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition InternalNode.h:1793
void combine2(const InternalNode &other0, const OtherNodeType &other1, CombineOp &)
Definition InternalNode.h:2746
friend class InternalNode
During topology-only construction, access is needed to protected/private members of other template in...
Definition InternalNode.h:742
bool isValueMaskOff(Index n) const
Definition InternalNode.h:748
void setValueOnly(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates but don't change its active state.
Definition InternalNode.h:1776
const LeafNodeType * probeConstLeaf(const Coord &xyz) const
Definition InternalNode.h:1290
Index getValueLevelAndCache(const Coord &xyz, AccessorT &) const
Return the level of the tree (0 = leaf) at which the value at the given coordinates resides.
Definition InternalNode.h:1614
const NodeType * probeConstNodeAndCache(const Coord &xyz, AccessorT &) const
void fill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given axis-aligned box to a constant value.
Definition InternalNode.h:2034
ValueOffCIter beginValueOff() const
Definition InternalNode.h:236
void setValueOffAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition InternalNode.h:1707
void addLeaf(LeafNodeType *leaf)
Add the specified leaf to this node, possibly creating a child branch in the process....
Definition InternalNode.h:1310
const ValueType & getValueAndCache(const Coord &xyz, AccessorT &) const
ChildAllCIter cbeginChildAll() const
Definition InternalNode.h:222
void clip(const CoordBBox &, const ValueType &background)
Set all voxels that lie outside the given axis-aligned box to the background.
Definition InternalNode.h:1984
ChildAllIter beginChildAll()
Definition InternalNode.h:228
static Index getLevel()
Definition InternalNode.h:249
bool isValueOnAndCache(const Coord &xyz, AccessorT &) const
Definition InternalNode.h:1571
void topologyDifference(const InternalNode< OtherChildNodeType, Log2Dim > &other, const ValueType &background)
Difference this node's set of active values with the active values of the other node,...
bool probeValue(const Coord &xyz, ValueType &value) const
Definition InternalNode.h:1627
void setActiveState(const Coord &xyz, bool on)
Set the active state of the voxel at the given coordinates but don't change its value.
Definition InternalNode.h:1814
ValueOnIter beginValueOn()
Definition InternalNode.h:238
void modifyValueAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Apply a functor to the value of the voxel at the given coordinates and mark the voxel as active....
Definition InternalNode.h:1896
void topologyUnion(const InternalNode< OtherChildNodeType, Log2Dim > &other, const bool preserveTiles=false)
Union this branch's set of active values with the other branch's active values. The value type of the...
ChildOffCIter cbeginChildOff() const
Definition InternalNode.h:221
ChildOffIter beginChildOff()
Definition InternalNode.h:227
Index64 onVoxelCount() const
Definition InternalNode.h:1049
ChildOffCIter beginChildOff() const
Definition InternalNode.h:224
static Index coordToOffset(const Coord &xyz)
Return the linear table offset of the given global or local coordinates.
Definition InternalNode.h:2927
void addTileAndCache(Index level, const Coord &xyz, const ValueType &, bool state, AccessorT &)
Same as addTile() except, if necessary, update the accessor with pointers to the nodes along the path...
Definition InternalNode.h:1430
typename ChildNodeType::LeafNodeType LeafNodeType
Definition InternalNode.h:37
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don't change its value.
Definition InternalNode.h:1655
NodeType * probeNodeAndCache(const Coord &xyz, AccessorT &)
Same as probeNode() except, if necessary, update the accessor with pointers to the nodes along the pa...
void writeBuffers(std::ostream &, bool toHalf=false) const
Definition InternalNode.h:2861
ValueOnCIter cbeginValueOn() const
Definition InternalNode.h:230
typename ChildNodeType::ValueType ValueType
Definition InternalNode.h:38
Index32 leafCount() const
Definition InternalNode.h:1003
const LeafNodeType * probeLeaf(const Coord &xyz) const
void resetChildNode(Index i, ChildNodeType *child)
Definition InternalNode.h:3057
Index32 childCount() const
Definition InternalNode.h:1041
Index getValueLevel(const Coord &xyz) const
Return the level of the tree (0 = leaf) at which the value at the given coordinates resides.
Definition InternalNode.h:1605
Index64 onTileCount() const
Definition InternalNode.h:1096
void modifyValue(const Coord &xyz, const ModifyOp &op)
Apply a functor to the value of the voxel at the given coordinates and mark the voxel as active.
Definition InternalNode.h:1868
bool hasSameTopology(const InternalNode< OtherChildNodeType, OtherLog2Dim > *other) const
Return true if the given tree branch has the same node and active value topology as this tree branch ...
Definition InternalNode.h:3043
void setValueMask(Index n, bool on)
Definition InternalNode.h:767
Index64 offVoxelCount() const
Definition InternalNode.h:1061
typename NodeMaskType::OffIterator MaskOffIterator
Definition InternalNode.h:115
bool isConstant(ValueType &firstValue, bool &state, const ValueType &tolerance=zeroVal< ValueType >()) const
Definition InternalNode.h:1499
LeafNodeType * touchLeaf(const Coord &xyz)
Return the leaf node that contains voxel (x, y, z). If no such node exists, create one,...
Definition InternalNode.h:1466
void denseFill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given axis-aligned box to a constant value and ensure that those voxels are a...
Definition InternalNode.h:2090
static const Index NUM_VALUES
Definition InternalNode.h:47
UnionType mNodes[NUM_VALUES]
Definition InternalNode.h:794
void negate()
Change the sign of all the values represented in this node and its child nodes.
Definition InternalNode.h:2288
void readTopology(std::istream &, bool fromHalf=false)
Definition InternalNode.h:2208
Coord offsetToGlobalCoord(Index n) const
Return the global coordinates for a linear table offset.
Definition InternalNode.h:2937
ChildAllCIter beginChildAll() const
Definition InternalNode.h:225
void setActiveStateAndCache(const Coord &xyz, bool on, AccessorT &)
Definition InternalNode.h:1833
void setValuesOn()
Mark all values (both tiles and voxels) as active.
Definition InternalNode.h:1856
void makeChildNodeEmpty(Index n, const ValueType &value)
Definition InternalNode.h:3098
void setTransientData(Index32 transientData)
Set the transient data value.
Definition InternalNode.h:275
typename ChildNodeType::BuildType BuildType
Definition InternalNode.h:39
LeafNodeType * touchLeafAndCache(const Coord &xyz, AccessorT &)
Same as touchLeaf() except, if necessary, update the accessor with pointers to the nodes along the pa...
void stealNodes(ArrayT &array, const ValueType &value, bool state)
Steals all nodes of a certain type from the tree and adds them to a container with the following API:
Definition InternalNode.h:2996
ChildNodeType * getChildNode(Index n)
Returns a pointer to the child node at the linear offset n.
Definition InternalNode.h:3105
typename NodeMaskType::OnIterator MaskOnIterator
Definition InternalNode.h:114
const LeafNodeType * probeLeafAndCache(const Coord &xyz, AccessorT &acc) const
bool probeValueAndCache(const Coord &xyz, ValueType &value, AccessorT &) const
Definition InternalNode.h:1640
bool addChild(ChildNodeType *child)
Add the given child node at this level deducing the offset from it's origin. If a child node with thi...
Definition InternalNode.h:1372
void evalActiveBoundingBox(CoordBBox &bbox, bool visitVoxels=true) const
Expand the specified bounding box so that it includes the active tiles of this internal node as well ...
Definition InternalNode.h:1120
bool isEmpty() const
Definition InternalNode.h:302
const UnionType * getTable() const
Definition InternalNode.h:762
static void getNodeLog2Dims(std::vector< Index > &dims)
Populated an std::vector with the dimension of all the nodes in the branch starting with this node.
Definition InternalNode.h:2906
ValueOffIter beginValueOff()
Definition InternalNode.h:240
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don't change its value.
Definition InternalNode.h:1671
_ChildNodeType ChildNodeType
Definition InternalNode.h:36
static void offsetToLocalCoord(Index n, Coord &xyz)
Return the local coordinates for a linear table offset, where offset 0 has coordinates (0,...
Definition InternalNode.h:2915
const NodeMaskType & getValueMask() const
Definition InternalNode.h:753
const NodeType * probeConstNode(const Coord &xyz) const
bool hasActiveTiles() const
Return true if this node or any of its child nodes have any active tiles.
Definition InternalNode.h:1546
void combine(InternalNode &other, CombineOp &)
Definition InternalNode.h:2659
const ValueType & getValue(const Coord &xyz) const
Definition InternalNode.h:1582
void nodeCount(std::vector< Index32 > &vec) const
Definition InternalNode.h:1015
Index64 memUsage() const
Return the total amount of memory in bytes occupied by this node and its children.
Definition InternalNode.h:1107
ChildNodeType * unsetChildNode(Index i, const ValueType &value)
Definition InternalNode.h:3083
void readBuffers(std::istream &, bool fromHalf=false)
Definition InternalNode.h:2871
typename NodeMaskType::DenseIterator MaskDenseIterator
Definition InternalNode.h:116
void modifyValueAndActiveStateAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition InternalNode.h:1953
ValueAllCIter beginValueAll() const
Definition InternalNode.h:237
Coord mOrigin
Global grid index coordinates (x,y,z) of the local origin of this node.
Definition InternalNode.h:797
static Index dim()
Definition InternalNode.h:246
bool isValueMaskOn(Index n) const
Definition InternalNode.h:746
ValueAllIter beginValueAll()
Definition InternalNode.h:241
const ValueType & getLastValue() const
If the last entry in this node's table is a tile, return the tile's value. Otherwise,...
Definition InternalNode.h:2276
Base class for iterators over internal and leaf nodes.
Definition Iterator.h:30
const ValueT & getValue() const
Definition NodeUnion.h:43
ChildT * getChild() const
Definition NodeUnion.h:40
void setValue(const ValueT &val)
Definition NodeUnion.h:45
Definition NodeMasks.h:271
Bit mask for the internal and leaf nodes of VDB. This is a 64-bit implementation.
Definition NodeMasks.h:308
Index64 Word
Definition NodeMasks.h:316
void toggle(Index32 n)
Toggle the state of the nth bit.
Definition NodeMasks.h:483
void setOff(Index32 n)
Set the nth bit off.
Definition NodeMasks.h:457
void setOn(Index32 n)
Set the nth bit on.
Definition NodeMasks.h:452
Definition NodeMasks.h:240
Definition NodeMasks.h:209
void writeCompressedValues(std::ostream &os, ValueT *srcBuf, Index srcCount, const MaskT &valueMask, const MaskT &childMask, bool toHalf)
Definition Compression.h:645
OPENVDB_API uint32_t getFormatVersion(std::ios_base &)
Return the file format version number associated with the given input stream.
void readCompressedValues(std::istream &is, ValueT *destBuf, Index destCount, const MaskT &valueMask, bool fromHalf)
Definition Compression.h:465
OPENVDB_API const void * getGridBackgroundValuePtr(std::ios_base &)
Return a pointer to the background value of the grid currently being read from or written to the give...
bool isApproxEqual(const Type &a, const Type &b, const Type &tolerance)
Return true if a is equal to b to within the given tolerance.
Definition Math.h:406
T negative(const T &val)
Return the unary negation of the given value.
Definition Math.h:128
bool isExactlyEqual(const T0 &a, const T1 &b)
Return true if a is exactly equal to b.
Definition Math.h:443
Index32 Index
Definition Types.h:54
uint32_t Index32
Definition Types.h:52
@ OPENVDB_FILE_VERSION_NODE_MASK_COMPRESSION
Definition version.h.in:256
@ OPENVDB_FILE_VERSION_INTERNALNODE_COMPRESSION
Definition version.h.in:247
int32_t Int32
Definition Types.h:56
uint64_t Index64
Definition Types.h:53
@ MERGE_ACTIVE_STATES
Definition Types.h:468
@ MERGE_NODES
Definition Types.h:469
@ MERGE_ACTIVE_STATES_AND_NODES
Definition Types.h:470
Definition Exceptions.h:13
Definition Types.h:621
Base class for dense iterators over internal and leaf nodes.
Definition Iterator.h:179
typename std::remove_const< UnsetItemT >::type NonConstValueType
Definition Iterator.h:184
ChildIter(const MaskIterT &iter, NodeT *parent)
Definition InternalNode.h:131
ChildIter()
Definition InternalNode.h:130
ChildT & getItem(Index pos) const
Definition InternalNode.h:134
void setItem(Index pos, const ChildT &c) const
Definition InternalNode.h:141
Definition InternalNode.h:120
DeepCopy(const OtherInternalNode *source, InternalNode *target)
Definition InternalNode.h:862
InternalNode * t
Definition InternalNode.h:876
const OtherInternalNode * s
Definition InternalNode.h:875
void operator()(const tbb::blocked_range< Index > &r) const
Definition InternalNode.h:866
DenseIter(const MaskDenseIterator &iter, NodeT *parent)
Definition InternalNode.h:177
void unsetItem(Index pos, const ValueT &value) const
Definition InternalNode.h:198
void setItem(Index pos, ChildT *child) const
Definition InternalNode.h:192
DenseIter()
Definition InternalNode.h:176
bool getItem(Index pos, ChildT *&child, NonConstValueT &value) const
Definition InternalNode.h:180
typename BaseT::NonConstValueType NonConstValueT
Definition InternalNode.h:174
SameConfiguration<OtherNodeType>::value is true if and only if OtherNodeType is the type of an Intern...
Definition InternalNode.h:64
TopologyCopy1(const OtherInternalNode *source, InternalNode *target, const ValueType &background)
Definition InternalNode.h:912
InternalNode * t
Definition InternalNode.h:928
const OtherInternalNode * s
Definition InternalNode.h:927
const ValueType & b
Definition InternalNode.h:929
void operator()(const tbb::blocked_range< Index > &r) const
Definition InternalNode.h:917
const ValueType & offV
Definition InternalNode.h:968
TopologyCopy2(const OtherInternalNode *source, InternalNode *target, const ValueType &offValue, const ValueType &onValue)
Definition InternalNode.h:951
InternalNode * t
Definition InternalNode.h:967
const OtherInternalNode * s
Definition InternalNode.h:966
void operator()(const tbb::blocked_range< Index > &r) const
Definition InternalNode.h:956
void operator()(W &tC, const W &sC, const W &sV, const W &tV) const
Definition InternalNode.h:2597
void operator()(W &tV, const W &sC, const W &sV, const W &tC) const
Definition InternalNode.h:2600
TopologyDifference(const OtherInternalNode *source, InternalNode *target, const ValueType &background)
Definition InternalNode.h:2603
typename NodeMaskType::Word W
Definition InternalNode.h:2596
InternalNode * t
Definition InternalNode.h:2639
const OtherInternalNode * s
Definition InternalNode.h:2638
const ValueType & b
Definition InternalNode.h:2640
void operator()(const tbb::blocked_range< Index > &r) const
Definition InternalNode.h:2617
void operator()(W &tC, const W &sC, const W &sV, const W &tV) const
Definition InternalNode.h:2547
TopologyIntersection(const OtherInternalNode *source, InternalNode *target, const ValueType &background)
Definition InternalNode.h:2550
typename NodeMaskType::Word W
Definition InternalNode.h:2546
InternalNode * t
Definition InternalNode.h:2579
const OtherInternalNode * s
Definition InternalNode.h:2578
const ValueType & b
Definition InternalNode.h:2580
void operator()(const tbb::blocked_range< Index > &r) const
Definition InternalNode.h:2562
void operator()(W &tV, const W &sV, const W &tC) const
Definition InternalNode.h:2495
typename NodeMaskType::Word W
Definition InternalNode.h:2494
InternalNode * t
Definition InternalNode.h:2530
const bool mPreserveTiles
Definition InternalNode.h:2531
const OtherInternalNode * s
Definition InternalNode.h:2529
void operator()(const tbb::blocked_range< Index > &r) const
Definition InternalNode.h:2511
TopologyUnion(const OtherInternalNode *source, InternalNode *target, const bool preserveTiles)
Definition InternalNode.h:2498
ValueConverter<T>::Type is the type of an InternalNode having the same child hierarchy and dimensions...
Definition InternalNode.h:55
void modifyItem(Index pos, const ModifyOp &op) const
Definition InternalNode.h:162
ValueIter(const MaskIterT &iter, NodeT *parent)
Definition InternalNode.h:152
const ValueT & getItem(Index pos) const
Definition InternalNode.h:155
ValueIter()
Definition InternalNode.h:151
void setItem(Index pos, const ValueT &v) const
Definition InternalNode.h:158
Definition InternalNode.h:119
InternalNode * mNode
Definition InternalNode.h:2327
void operator()(const tbb::blocked_range< Index > &r) const
Definition InternalNode.h:2314
VoxelizeActiveTiles(InternalNode &node)
Definition InternalNode.h:2307
Definition InternalNode.h:812
Base class for sparse iterators over internal and leaf nodes.
Definition Iterator.h:115
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition version.h.in:121
#define OPENVDB_USE_VERSION_NAMESPACE
Definition version.h.in:212