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