OpenVDB 11.0.0
Loading...
Searching...
No Matches
RootNode.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 RootNode.h
5///
6/// @brief The root node of an OpenVDB tree
7
8#ifndef OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
9#define OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
10
11#include <openvdb/Exceptions.h>
12#include <openvdb/Types.h>
13#include <openvdb/io/Compression.h> // for truncateRealToHalf()
14#include <openvdb/math/Math.h> // for isZero(), isExactlyEqual(), etc.
15#include <openvdb/math/BBox.h>
16#include <openvdb/util/NodeMasks.h> // for backward compatibility only (see readTopology())
17#include <openvdb/version.h>
18#include <tbb/parallel_for.h>
19#include <map>
20#include <set>
21#include <sstream>
22#include <vector>
23
24
25namespace openvdb {
27namespace OPENVDB_VERSION_NAME {
28namespace tree {
29
30// Forward declarations
31template<typename HeadType, int HeadLevel> struct NodeChain;
32template<typename, typename> struct SameRootConfig;
33template<typename, typename, bool> struct RootNodeCopyHelper;
34template<typename, typename, typename, bool> struct RootNodeCombineHelper;
35
36
37template<typename ChildType>
39{
40public:
41 using ChildNodeType = ChildType;
42 using LeafNodeType = typename ChildType::LeafNodeType;
43 using ValueType = typename ChildType::ValueType;
44 using BuildType = typename ChildType::BuildType;
45
46 static const Index LEVEL = 1 + ChildType::LEVEL; // level 0 = leaf
47
48 /// NodeChainType is a list of this tree's node types, from LeafNodeType to RootNode.
50 static_assert(NodeChainType::Size == LEVEL + 1,
51 "wrong number of entries in RootNode node chain");
52
53 /// @brief ValueConverter<T>::Type is the type of a RootNode having the same
54 /// child hierarchy as this node but a different value type, T.
55 template<typename OtherValueType>
59
60 /// @brief SameConfiguration<OtherNodeType>::value is @c true if and only if
61 /// OtherNodeType is the type of a RootNode whose ChildNodeType has the same
62 /// configuration as this node's ChildNodeType.
63 template<typename OtherNodeType>
67
68
69 /// Construct a new tree with a background value of 0.
70 RootNode();
71
72 /// Construct a new tree with the given background value.
73 explicit RootNode(const ValueType& background);
74
75 RootNode(const RootNode& other) { *this = other; }
76
77 /// @brief Construct a new tree that reproduces the topology and active states
78 /// of a tree of a different ValueType but the same configuration (levels,
79 /// node dimensions and branching factors). Cast the other tree's values to
80 /// this tree's ValueType.
81 /// @throw TypeError if the other tree's configuration doesn't match this tree's
82 /// or if this tree's ValueType is not constructible from the other tree's ValueType.
83 template<typename OtherChildType>
84 explicit RootNode(const RootNode<OtherChildType>& other) { *this = other; }
85
86 /// @brief Construct a new tree that reproduces the topology and active states of
87 /// another tree (which may have a different ValueType), but not the other tree's values.
88 /// @details All tiles and voxels that are active in the other tree are set to
89 /// @a foreground in the new tree, and all inactive tiles and voxels are set to @a background.
90 /// @param other the root node of a tree having (possibly) a different ValueType
91 /// @param background the value to which inactive tiles and voxels are initialized
92 /// @param foreground the value to which active tiles and voxels are initialized
93 /// @throw TypeError if the other tree's configuration doesn't match this tree's.
94 template<typename OtherChildType>
96 const ValueType& background, const ValueType& foreground, TopologyCopy);
97
98 /// @brief Construct a new tree that reproduces the topology and active states of
99 /// another tree (which may have a different ValueType), but not the other tree's values.
100 /// All tiles and voxels in the new tree are set to @a background regardless of
101 /// their active states in the other tree.
102 /// @param other the root node of a tree having (possibly) a different ValueType
103 /// @param background the value to which inactive tiles and voxels are initialized
104 /// @note This copy constructor is generally faster than the one that takes both
105 /// a foreground and a background value. Its main application is in multithreaded
106 /// operations where the topology of the output tree exactly matches the input tree.
107 /// @throw TypeError if the other tree's configuration doesn't match this tree's.
108 template<typename OtherChildType>
109 RootNode(const RootNode<OtherChildType>& other, const ValueType& background, TopologyCopy);
110
111 /// @brief Copy a root node of the same type as this node.
112 RootNode& operator=(const RootNode& other);
113 /// @brief Copy a root node of the same tree configuration as this node
114 /// but a different ValueType.
115 /// @throw TypeError if the other tree's configuration doesn't match this tree's.
116 /// @note This node's ValueType must be constructible from the other node's ValueType.
117 /// For example, a root node with values of type float can be assigned to a root node
118 /// with values of type Vec3s, because a Vec3s can be constructed from a float.
119 /// But a Vec3s root node cannot be assigned to a float root node.
120 template<typename OtherChildType>
122
123 ~RootNode() { this->clear(); }
124
125private:
126 struct Tile {
127 Tile(): value(zeroVal<ValueType>()), active(false) {}
128 Tile(const ValueType& v, bool b): value(v), active(b) {}
129 ValueType value;
130 bool active;
131 };
132
133 // This lightweight struct pairs child pointers and tiles.
134 struct NodeStruct {
135 ChildType* child;
136 Tile tile;
137
138 NodeStruct(): child(nullptr) {}
139 NodeStruct(ChildType& c): child(&c) {}
140 NodeStruct(const Tile& t): child(nullptr), tile(t) {}
141 NodeStruct(const NodeStruct&) = default;
142 NodeStruct& operator=(const NodeStruct&) = default;
143 ~NodeStruct() {} ///< @note doesn't delete child
144
145 bool isChild() const { return child != nullptr; }
146 bool isTile() const { return child == nullptr; }
147 bool isTileOff() const { return isTile() && !tile.active; }
148 bool isTileOn() const { return isTile() && tile.active; }
149
150 void set(ChildType& c) { delete child; child = &c; }
151 void set(const Tile& t) { delete child; child = nullptr; tile = t; }
152 ChildType& steal(const Tile& t) { ChildType* c=child; child=nullptr; tile=t; return *c; }
153 };
154
155 using MapType = std::map<Coord, NodeStruct>;
156 using MapIter = typename MapType::iterator;
157 using MapCIter = typename MapType::const_iterator;
158
159 using CoordSet = std::set<Coord>;
160 using CoordSetIter = typename CoordSet::iterator;
161 using CoordSetCIter = typename CoordSet::const_iterator;
162
163 static void setTile(const MapIter& i, const Tile& t) { i->second.set(t); }
164 static void setChild(const MapIter& i, ChildType& c) { i->second.set(c); }
165 static Tile& getTile(const MapIter& i) { return i->second.tile; }
166 static const Tile& getTile(const MapCIter& i) { return i->second.tile; }
167 static ChildType& getChild(const MapIter& i) { return *(i->second.child); }
168 static const ChildType& getChild(const MapCIter& i) { return *(i->second.child); }
169 static ChildType& stealChild(const MapIter& i, const Tile& t) {return i->second.steal(t);}
170 static const ChildType& stealChild(const MapCIter& i,const Tile& t) {return i->second.steal(t);}
171
172 static bool isChild(const MapCIter& i) { return i->second.isChild(); }
173 static bool isChild(const MapIter& i) { return i->second.isChild(); }
174 static bool isTile(const MapCIter& i) { return i->second.isTile(); }
175 static bool isTile(const MapIter& i) { return i->second.isTile(); }
176 static bool isTileOff(const MapCIter& i) { return i->second.isTileOff(); }
177 static bool isTileOff(const MapIter& i) { return i->second.isTileOff(); }
178 static bool isTileOn(const MapCIter& i) { return i->second.isTileOn(); }
179 static bool isTileOn(const MapIter& i) { return i->second.isTileOn(); }
180
181 struct NullPred {
182 static inline bool test(const MapIter&) { return true; }
183 static inline bool test(const MapCIter&) { return true; }
184 };
185 struct ValueOnPred {
186 static inline bool test(const MapIter& i) { return isTileOn(i); }
187 static inline bool test(const MapCIter& i) { return isTileOn(i); }
188 };
189 struct ValueOffPred {
190 static inline bool test(const MapIter& i) { return isTileOff(i); }
191 static inline bool test(const MapCIter& i) { return isTileOff(i); }
192 };
193 struct ValueAllPred {
194 static inline bool test(const MapIter& i) { return isTile(i); }
195 static inline bool test(const MapCIter& i) { return isTile(i); }
196 };
197 struct ChildOnPred {
198 static inline bool test(const MapIter& i) { return isChild(i); }
199 static inline bool test(const MapCIter& i) { return isChild(i); }
200 };
201 struct ChildOffPred {
202 static inline bool test(const MapIter& i) { return isTile(i); }
203 static inline bool test(const MapCIter& i) { return isTile(i); }
204 };
205
206 template<typename _RootNodeT, typename _MapIterT, typename FilterPredT>
207 class BaseIter
208 {
209 public:
210 using RootNodeT = _RootNodeT;
211 using MapIterT = _MapIterT; // either MapIter or MapCIter
212
213 bool operator==(const BaseIter& other) const
214 {
215 return (mParentNode == other.mParentNode) && (mIter == other.mIter);
216 }
217 bool operator!=(const BaseIter& other) const { return !(*this == other); }
218
219 RootNodeT* getParentNode() const { return mParentNode; }
220 /// Return a reference to the node over which this iterator iterates.
221 RootNodeT& parent() const
222 {
223 if (!mParentNode) OPENVDB_THROW(ValueError, "iterator references a null parent node");
224 return *mParentNode;
225 }
226
227 bool test() const { assert(mParentNode); return mIter != mParentNode->mTable.end(); }
228 operator bool() const { return this->test(); }
229
230 void increment() { if (this->test()) { ++mIter; } this->skip(); }
231 bool next() { this->increment(); return this->test(); }
232 void increment(Index n) { for (Index i = 0; i < n && this->next(); ++i) {} }
233
234 /// @brief Return this iterator's position as an offset from
235 /// the beginning of the parent node's map.
236 Index pos() const
237 {
238 return !mParentNode ? 0U : Index(std::distance(mParentNode->mTable.begin(), mIter));
239 }
240
241 bool isValueOn() const { return RootNodeT::isTileOn(mIter); }
242 bool isValueOff() const { return RootNodeT::isTileOff(mIter); }
243 void setValueOn(bool on = true) const { mIter->second.tile.active = on; }
244 void setValueOff() const { mIter->second.tile.active = false; }
245
246 /// Return the coordinates of the item to which this iterator is pointing.
247 Coord getCoord() const { return mIter->first; }
248 /// Return in @a xyz the coordinates of the item to which this iterator is pointing.
249 void getCoord(Coord& xyz) const { xyz = this->getCoord(); }
250
251 protected:
252 BaseIter(): mParentNode(nullptr) {}
253 BaseIter(RootNodeT& parent, const MapIterT& iter): mParentNode(&parent), mIter(iter) {}
254
255 void skip() { while (this->test() && !FilterPredT::test(mIter)) ++mIter; }
256
257 RootNodeT* mParentNode;
258 MapIterT mIter;
259 }; // BaseIter
260
261 template<typename RootNodeT, typename MapIterT, typename FilterPredT, typename ChildNodeT>
262 class ChildIter: public BaseIter<RootNodeT, MapIterT, FilterPredT>
263 {
264 public:
265 using BaseT = BaseIter<RootNodeT, MapIterT, FilterPredT>;
266 using NodeType = RootNodeT;
267 using ValueType = NodeType;
268 using ChildNodeType = ChildNodeT;
269 using NonConstNodeType = typename std::remove_const<NodeType>::type;
270 using NonConstValueType = typename std::remove_const<ValueType>::type;
271 using NonConstChildNodeType = typename std::remove_const<ChildNodeType>::type;
272 using BaseT::mIter;
273
274 ChildIter() {}
275 ChildIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
276
277 ChildIter& operator++() { BaseT::increment(); return *this; }
278
279 ChildNodeT& getValue() const { return getChild(mIter); }
280 ChildNodeT& operator*() const { return this->getValue(); }
281 ChildNodeT* operator->() const { return &this->getValue(); }
282 }; // ChildIter
283
284 template<typename RootNodeT, typename MapIterT, typename FilterPredT, typename ValueT>
285 class ValueIter: public BaseIter<RootNodeT, MapIterT, FilterPredT>
286 {
287 public:
288 using BaseT = BaseIter<RootNodeT, MapIterT, FilterPredT>;
289 using NodeType = RootNodeT;
290 using ValueType = ValueT;
291 using NonConstNodeType = typename std::remove_const<NodeType>::type;
292 using NonConstValueType = typename std::remove_const<ValueT>::type;
293 using BaseT::mIter;
294
295 ValueIter() {}
296 ValueIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
297
298 ValueIter& operator++() { BaseT::increment(); return *this; }
299
300 ValueT& getValue() const { return getTile(mIter).value; }
301 ValueT& operator*() const { return this->getValue(); }
302 ValueT* operator->() const { return &(this->getValue()); }
303
304 void setValue(const ValueT& v) const { assert(isTile(mIter)); getTile(mIter).value = v; }
305
306 template<typename ModifyOp>
307 void modifyValue(const ModifyOp& op) const
308 {
309 assert(isTile(mIter));
310 op(getTile(mIter).value);
311 }
312 }; // ValueIter
313
314 template<typename RootNodeT, typename MapIterT, typename ChildNodeT, typename ValueT>
315 class DenseIter: public BaseIter<RootNodeT, MapIterT, NullPred>
316 {
317 public:
318 using BaseT = BaseIter<RootNodeT, MapIterT, NullPred>;
319 using NodeType = RootNodeT;
320 using ValueType = ValueT;
321 using ChildNodeType = ChildNodeT;
322 using NonConstNodeType = typename std::remove_const<NodeType>::type;
323 using NonConstValueType = typename std::remove_const<ValueT>::type;
324 using NonConstChildNodeType = typename std::remove_const<ChildNodeT>::type;
325 using BaseT::mIter;
326
327 DenseIter() {}
328 DenseIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) {}
329
330 DenseIter& operator++() { BaseT::increment(); return *this; }
331
332 bool isChildNode() const { return isChild(mIter); }
333
334 ChildNodeT* probeChild(NonConstValueType& value) const
335 {
336 if (isChild(mIter)) return &getChild(mIter);
337 value = getTile(mIter).value;
338 return nullptr;
339 }
340 bool probeChild(ChildNodeT*& child, NonConstValueType& value) const
341 {
342 child = this->probeChild(value);
343 return child != nullptr;
344 }
345 bool probeValue(NonConstValueType& value) const { return !this->probeChild(value); }
346
347 void setChild(ChildNodeT& c) const { RootNodeT::setChild(mIter, c); }
348 void setChild(ChildNodeT* c) const { assert(c != nullptr); RootNodeT::setChild(mIter, *c); }
349 void setValue(const ValueT& v) const
350 {
351 if (isTile(mIter)) getTile(mIter).value = v;
352 /// @internal For consistency with iterators for other node types
353 /// (see, e.g., InternalNode::DenseIter::unsetItem()), we don't call
354 /// setTile() here, because that would also delete the child.
355 else stealChild(mIter, Tile(v, /*active=*/true));
356 }
357 }; // DenseIter
358
359public:
360 using ChildOnIter = ChildIter<RootNode, MapIter, ChildOnPred, ChildType>;
361 using ChildOnCIter = ChildIter<const RootNode, MapCIter, ChildOnPred, const ChildType>;
362 using ChildOffIter = ValueIter<RootNode, MapIter, ChildOffPred, const ValueType>;
363 using ChildOffCIter = ValueIter<const RootNode, MapCIter, ChildOffPred, ValueType>;
364 using ChildAllIter = DenseIter<RootNode, MapIter, ChildType, ValueType>;
365 using ChildAllCIter = DenseIter<const RootNode, MapCIter, const ChildType, const ValueType>;
366
367 using ValueOnIter = ValueIter<RootNode, MapIter, ValueOnPred, ValueType>;
368 using ValueOnCIter = ValueIter<const RootNode, MapCIter, ValueOnPred, const ValueType>;
369 using ValueOffIter = ValueIter<RootNode, MapIter, ValueOffPred, ValueType>;
370 using ValueOffCIter = ValueIter<const RootNode, MapCIter, ValueOffPred, const ValueType>;
371 using ValueAllIter = ValueIter<RootNode, MapIter, ValueAllPred, ValueType>;
372 using ValueAllCIter = ValueIter<const RootNode, MapCIter, ValueAllPred, const ValueType>;
373
374
375 ChildOnCIter cbeginChildOn() const { return ChildOnCIter(*this, mTable.begin()); }
376 ChildOffCIter cbeginChildOff() const { return ChildOffCIter(*this, mTable.begin()); }
377 ChildAllCIter cbeginChildAll() const { return ChildAllCIter(*this, mTable.begin()); }
378 ChildOnCIter beginChildOn() const { return cbeginChildOn(); }
379 ChildOffCIter beginChildOff() const { return cbeginChildOff(); }
380 ChildAllCIter beginChildAll() const { return cbeginChildAll(); }
381 ChildOnIter beginChildOn() { return ChildOnIter(*this, mTable.begin()); }
382 ChildOffIter beginChildOff() { return ChildOffIter(*this, mTable.begin()); }
383 ChildAllIter beginChildAll() { return ChildAllIter(*this, mTable.begin()); }
384
385 ValueOnCIter cbeginValueOn() const { return ValueOnCIter(*this, mTable.begin()); }
386 ValueOffCIter cbeginValueOff() const { return ValueOffCIter(*this, mTable.begin()); }
387 ValueAllCIter cbeginValueAll() const { return ValueAllCIter(*this, mTable.begin()); }
388 ValueOnCIter beginValueOn() const { return cbeginValueOn(); }
389 ValueOffCIter beginValueOff() const { return cbeginValueOff(); }
390 ValueAllCIter beginValueAll() const { return cbeginValueAll(); }
391 ValueOnIter beginValueOn() { return ValueOnIter(*this, mTable.begin()); }
392 ValueOffIter beginValueOff() { return ValueOffIter(*this, mTable.begin()); }
393 ValueAllIter beginValueAll() { return ValueAllIter(*this, mTable.begin()); }
394
395 /// Return the total amount of memory in bytes occupied by this node and its children.
396 Index64 memUsage() const;
397
398 /// @brief Expand the specified bbox so it includes the active tiles of
399 /// this root node as well as all the active values in its child
400 /// nodes. If visitVoxels is false LeafNodes will be approximated
401 /// as dense, i.e. with all voxels active. Else the individual
402 /// active voxels are visited to produce a tight bbox.
403 void evalActiveBoundingBox(CoordBBox& bbox, bool visitVoxels = true) const;
404
405 /// Return the bounding box of this RootNode, i.e., an infinite bounding box.
406 static CoordBBox getNodeBoundingBox() { return CoordBBox::inf(); }
407
408 /// Return the transient data value.
409 Index32 transientData() const { return mTransientData; }
410 /// Set the transient data value.
411 void setTransientData(Index32 transientData) { mTransientData = transientData; }
412
413 /// @brief Change inactive tiles or voxels with a value equal to +/- the
414 /// old background to the specified value (with the same sign). Active values
415 /// are unchanged.
416 ///
417 /// @param value The new background value
418 /// @param updateChildNodes If true the background values of the
419 /// child nodes is also updated. Else only the background value
420 /// stored in the RootNode itself is changed.
421 ///
422 /// @note Instead of setting @a updateChildNodes to true, consider
423 /// using tools::changeBackground or
424 /// tools::changeLevelSetBackground which are multi-threaded!
425 void setBackground(const ValueType& value, bool updateChildNodes);
426
427 /// Return this node's background value.
428 const ValueType& background() const { return mBackground; }
429
430 /// Return @c true if the given tile is inactive and has the background value.
431 bool isBackgroundTile(const Tile&) const;
432 //@{
433 /// Return @c true if the given iterator points to an inactive tile with the background value.
434 bool isBackgroundTile(const MapIter&) const;
435 bool isBackgroundTile(const MapCIter&) const;
436 //@}
437
438 /// Return the number of background tiles.
439 size_t numBackgroundTiles() const;
440 /// @brief Remove all background tiles.
441 /// @return the number of tiles removed.
442 size_t eraseBackgroundTiles();
443 inline void clear();
444
445 /// Return @c true if this node's table is either empty or contains only background tiles.
446 bool empty() const { return mTable.size() == numBackgroundTiles(); }
447
448 /// @brief Expand this node's table so that (x, y, z) is included in the index range.
449 /// @return @c true if an expansion was performed (i.e., if (x, y, z) was not already
450 /// included in the index range).
451 bool expand(const Coord& xyz);
452
453 static Index getLevel() { return LEVEL; }
454 static void getNodeLog2Dims(std::vector<Index>& dims);
455 static Index getChildDim() { return ChildType::DIM; }
456
457 /// Return the number of entries in this node's table.
458 Index getTableSize() const { return static_cast<Index>(mTable.size()); }
459
460 Index getWidth() const { return this->getMaxIndex()[0] - this->getMinIndex()[0]; }
461 Index getHeight() const { return this->getMaxIndex()[1] - this->getMinIndex()[1]; }
462 Index getDepth() const { return this->getMaxIndex()[2] - this->getMinIndex()[2]; }
463
464 /// Return the smallest index of the current tree.
465 Coord getMinIndex() const;
466 /// Return the largest index of the current tree.
467 Coord getMaxIndex() const;
468 /// Return the current index range. Both min and max are inclusive.
469 void getIndexRange(CoordBBox& bbox) const;
470
471 /// @brief Return @c true if the given tree has the same node and active value
472 /// topology as this tree (but possibly a different @c ValueType).
473 template<typename OtherChildType>
474 bool hasSameTopology(const RootNode<OtherChildType>& other) const;
475
476 /// Return @c false if the other node's dimensions don't match this node's.
477 template<typename OtherChildType>
478 static bool hasSameConfiguration(const RootNode<OtherChildType>& other);
479
480 /// Return @c true if values of the other node's ValueType can be converted
481 /// to values of this node's ValueType.
482 template<typename OtherChildType>
483 static bool hasCompatibleValueType(const RootNode<OtherChildType>& other);
484
485 Index32 leafCount() const;
486 Index32 nonLeafCount() const;
487 Index32 childCount() const;
488 Index64 onVoxelCount() const;
489 Index64 offVoxelCount() const;
490 Index64 onLeafVoxelCount() const;
491 Index64 offLeafVoxelCount() const;
492 Index64 onTileCount() const;
493 void nodeCount(std::vector<Index32> &vec) const;
494
495 bool isValueOn(const Coord& xyz) const;
496
497 /// Return @c true if this root node, or any of its child nodes, have active tiles.
498 bool hasActiveTiles() const;
499
500 const ValueType& getValue(const Coord& xyz) const;
501 bool probeValue(const Coord& xyz, ValueType& value) const;
502
503 /// @brief Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides.
504 /// @details If (x, y, z) isn't explicitly represented in the tree (i.e.,
505 /// it is implicitly a background voxel), return -1.
506 int getValueDepth(const Coord& xyz) const;
507
508 /// Set the active state of the voxel at the given coordinates but don't change its value.
509 void setActiveState(const Coord& xyz, bool on);
510 /// Set the value of the voxel at the given coordinates but don't change its active state.
511 void setValueOnly(const Coord& xyz, const ValueType& value);
512 /// Set the value of the voxel at the given coordinates and mark the voxel as active.
513 void setValueOn(const Coord& xyz, const ValueType& value);
514 /// Mark the voxel at the given coordinates as inactive but don't change its value.
515 void setValueOff(const Coord& xyz);
516 /// Set the value of the voxel at the given coordinates and mark the voxel as inactive.
517 void setValueOff(const Coord& xyz, const ValueType& value);
518
519 /// @brief Apply a functor to the value of the voxel at the given coordinates
520 /// and mark the voxel as active.
521 template<typename ModifyOp>
522 void modifyValue(const Coord& xyz, const ModifyOp& op);
523 /// Apply a functor to the voxel at the given coordinates.
524 template<typename ModifyOp>
525 void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op);
526
527 //@{
528 /// @brief Set all voxels within a given axis-aligned box to a constant value.
529 /// @param bbox inclusive coordinates of opposite corners of an axis-aligned box
530 /// @param value the value to which to set voxels within the box
531 /// @param active if true, mark voxels within the box as active,
532 /// otherwise mark them as inactive
533 /// @note This operation generates a sparse, but not always optimally sparse,
534 /// representation of the filled box. Follow fill operations with a prune()
535 /// operation for optimal sparseness.
536 void fill(const CoordBBox& bbox, const ValueType& value, bool active = true);
537 void sparseFill(const CoordBBox& bbox, const ValueType& value, bool active = true)
538 {
539 this->fill(bbox, value, active);
540 }
541 //@}
542
543 /// @brief Set all voxels within a given axis-aligned box to a constant value
544 /// and ensure that those voxels are all represented at the leaf level.
545 /// @param bbox inclusive coordinates of opposite corners of an axis-aligned box.
546 /// @param value the value to which to set voxels within the box.
547 /// @param active if true, mark voxels within the box as active,
548 /// otherwise mark them as inactive.
549 /// @sa voxelizeActiveTiles()
550 void denseFill(const CoordBBox& bbox, const ValueType& value, bool active = true);
551
552 /// @brief Densify active tiles, i.e., replace them with leaf-level active voxels.
553 ///
554 /// @param threaded if true, this operation is multi-threaded (over the internal nodes).
555 ///
556 /// @warning This method can explode the tree's memory footprint, especially if it
557 /// contains active tiles at the upper levels (in particular the root level)!
558 ///
559 /// @sa denseFill()
560 void voxelizeActiveTiles(bool threaded = true);
561
562 /// @brief Copy into a dense grid the values of all voxels, both active and inactive,
563 /// that intersect a given bounding box.
564 /// @param bbox inclusive bounding box of the voxels to be copied into the dense grid
565 /// @param dense dense grid with a stride in @e z of one (see tools::Dense
566 /// in tools/Dense.h for the required API)
567 template<typename DenseT>
568 void copyToDense(const CoordBBox& bbox, DenseT& dense) const;
569
570
571 //
572 // I/O
573 //
574 bool writeTopology(std::ostream&, bool toHalf = false) const;
575 bool readTopology(std::istream&, bool fromHalf = false);
576
577 void writeBuffers(std::ostream&, bool toHalf = false) const;
578 void readBuffers(std::istream&, bool fromHalf = false);
579 void readBuffers(std::istream&, const CoordBBox&, bool fromHalf = false);
580
581
582 //
583 // Voxel access
584 //
585 /// Return the value of the voxel at the given coordinates and, if necessary, update
586 /// the accessor with pointers to the nodes along the path from the root node to
587 /// the node containing the voxel.
588 /// @note Used internally by ValueAccessor.
589 template<typename AccessorT>
590 const ValueType& getValueAndCache(const Coord& xyz, AccessorT&) const;
591 /// Return @c true if the voxel at the given coordinates is active and, if necessary,
592 /// update the accessor with pointers to the nodes along the path from the root node
593 /// to the node containing the voxel.
594 /// @note Used internally by ValueAccessor.
595 template<typename AccessorT>
596 bool isValueOnAndCache(const Coord& xyz, AccessorT&) const;
597
598 /// Change the value of the voxel at the given coordinates and mark it as active.
599 /// If necessary, update the accessor with pointers to the nodes along the path
600 /// from the root node to the node containing the voxel.
601 /// @note Used internally by ValueAccessor.
602 template<typename AccessorT>
603 void setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
604
605 /// Set the value of the voxel at the given coordinates without changing its active state.
606 /// If necessary, update the accessor with pointers to the nodes along the path
607 /// from the root node to the node containing the voxel.
608 /// @note Used internally by ValueAccessor.
609 template<typename AccessorT>
610 void setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
611
612 /// Apply a functor to the value of the voxel at the given coordinates
613 /// and mark the voxel as active.
614 /// If necessary, update the accessor with pointers to the nodes along the path
615 /// from the root node to the node containing the voxel.
616 /// @note Used internally by ValueAccessor.
617 template<typename ModifyOp, typename AccessorT>
618 void modifyValueAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&);
619
620 /// Apply a functor to the voxel at the given coordinates.
621 /// If necessary, update the accessor with pointers to the nodes along the path
622 /// from the root node to the node containing the voxel.
623 /// @note Used internally by ValueAccessor.
624 template<typename ModifyOp, typename AccessorT>
625 void modifyValueAndActiveStateAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&);
626
627 /// Change the value of the voxel at the given coordinates and mark it as inactive.
628 /// If necessary, update the accessor with pointers to the nodes along the path
629 /// from the root node to the node containing the voxel.
630 /// @note Used internally by ValueAccessor.
631 template<typename AccessorT>
632 void setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT&);
633
634 /// Set the active state of the voxel at the given coordinates without changing its value.
635 /// If necessary, update the accessor with pointers to the nodes along the path
636 /// from the root node to the node containing the voxel.
637 /// @note Used internally by ValueAccessor.
638 template<typename AccessorT>
639 void setActiveStateAndCache(const Coord& xyz, bool on, AccessorT&);
640
641 /// Return, in @a value, the value of the voxel at the given coordinates and,
642 /// if necessary, update the accessor with pointers to the nodes along
643 /// the path from the root node to the node containing the voxel.
644 /// @return @c true if the voxel at the given coordinates is active
645 /// @note Used internally by ValueAccessor.
646 template<typename AccessorT>
647 bool probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT&) const;
648
649 /// Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides.
650 /// If (x, y, z) isn't explicitly represented in the tree (i.e., it is implicitly
651 /// a background voxel), return -1. If necessary, update the accessor with pointers
652 /// to the nodes along the path from the root node to the node containing the voxel.
653 /// @note Used internally by ValueAccessor.
654 template<typename AccessorT>
655 int getValueDepthAndCache(const Coord& xyz, AccessorT&) const;
656
657 /// Set all voxels that lie outside the given axis-aligned box to the background.
658 void clip(const CoordBBox&);
659
660 /// @brief Reduce the memory footprint of this tree by replacing with tiles
661 /// any nodes whose values are all the same (optionally to within a tolerance)
662 /// and have the same active state.
663 ///
664 /// @note Consider instead using tools::prune which is multi-threaded!
665 void prune(const ValueType& tolerance = zeroVal<ValueType>());
666
667 /// @brief Add the given leaf node to this tree, creating a new branch if necessary.
668 /// If a leaf node with the same origin already exists, replace it.
669 void addLeaf(LeafNodeType* leaf);
670
671 /// @brief Same as addLeaf() but, if necessary, update the given accessor with pointers
672 /// to the nodes along the path from the root node to the node containing the coordinate.
673 template<typename AccessorT>
674 void addLeafAndCache(LeafNodeType* leaf, AccessorT&);
675
676 /// @brief Return a pointer to the node of type @c NodeT that contains voxel (x, y, z)
677 /// and replace it with a tile of the specified value and state.
678 /// If no such node exists, leave the tree unchanged and return @c nullptr.
679 ///
680 /// @note The caller takes ownership of the node and is responsible for deleting it.
681 ///
682 /// @warning Since this method potentially removes nodes and branches of the tree,
683 /// it is important to clear the caches of all ValueAccessors associated with this tree.
684 template<typename NodeT>
685 NodeT* stealNode(const Coord& xyz, const ValueType& value, bool state);
686
687 /// @brief Add the given child node at the root level.
688 /// If a child node with the same origin already exists, delete the old node and add
689 /// the new node in its place (i.e. ownership of the new child node is transferred
690 /// to this RootNode).
691 /// @return @c true (for consistency with InternalNode::addChild)
692 bool addChild(ChildType* child);
693
694 /// @brief Add a tile containing voxel (x, y, z) at the root level,
695 /// deleting the existing branch if necessary.
696 void addTile(const Coord& xyz, const ValueType& value, bool state);
697
698 /// @brief Add a tile containing voxel (x, y, z) at the specified tree level,
699 /// creating a new branch if necessary. Delete any existing lower-level nodes
700 /// that contain (x, y, z).
701 void addTile(Index level, const Coord& xyz, const ValueType& value, bool state);
702
703 /// @brief Same as addTile() but, if necessary, update the given accessor with pointers
704 /// to the nodes along the path from the root node to the node containing the coordinate.
705 template<typename AccessorT>
706 void addTileAndCache(Index level, const Coord& xyz, const ValueType&, bool state, AccessorT&);
707
708 /// @brief Return a pointer to the leaf node that contains voxel (x, y, z).
709 /// If no such node exists, create one that preserves the values and
710 /// active states of all voxels.
711 /// @details Use this method to preallocate a static tree topology
712 /// over which to safely perform multithreaded processing.
713 LeafNodeType* touchLeaf(const Coord& xyz);
714
715 /// @brief Same as touchLeaf() but, if necessary, update the given accessor with pointers
716 /// to the nodes along the path from the root node to the node containing the coordinate.
717 template<typename AccessorT>
718 LeafNodeType* touchLeafAndCache(const Coord& xyz, AccessorT& acc);
719
720 //@{
721 /// @brief Return a pointer to the node that contains voxel (x, y, z).
722 /// If no such node exists, return @c nullptr.
723 template <typename NodeT>
724 NodeT* probeNode(const Coord& xyz);
725 template <typename NodeT>
726 const NodeT* probeConstNode(const Coord& xyz) const;
727 //@}
728
729 //@{
730 /// @brief Same as probeNode() but, if necessary, update the given accessor with pointers
731 /// to the nodes along the path from the root node to the node containing the coordinate.
732 template<typename NodeT, typename AccessorT>
733 NodeT* probeNodeAndCache(const Coord& xyz, AccessorT& acc);
734 template<typename NodeT, typename AccessorT>
735 const NodeT* probeConstNodeAndCache(const Coord& xyz, AccessorT& acc) const;
736 //@}
737
738 //@{
739 /// @brief Return a pointer to the leaf node that contains voxel (x, y, z).
740 /// If no such node exists, return @c nullptr.
741 LeafNodeType* probeLeaf(const Coord& xyz);
742 const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
743 const LeafNodeType* probeLeaf(const Coord& xyz) const;
744 //@}
745
746 //@{
747 /// @brief Same as probeLeaf() but, if necessary, update the given accessor with pointers
748 /// to the nodes along the path from the root node to the node containing the coordinate.
749 template<typename AccessorT>
750 LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc);
751 template<typename AccessorT>
752 const LeafNodeType* probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const;
753 template<typename AccessorT>
754 const LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc) const;
755 //@}
756
757
758 //
759 // Aux methods
760 //
761
762 //@{
763 /// @brief Adds all nodes of a certain type to a container with the following API:
764 /// @code
765 /// struct ArrayT {
766 /// using value_type = ...;// defines the type of nodes to be added to the array
767 /// void push_back(value_type nodePtr);// method that add nodes to the array
768 /// };
769 /// @endcode
770 /// @details An example of a wrapper around a c-style array is:
771 /// @code
772 /// struct MyArray {
773 /// using value_type = LeafType*;
774 /// value_type* ptr;
775 /// MyArray(value_type* array) : ptr(array) {}
776 /// void push_back(value_type leaf) { *ptr++ = leaf; }
777 ///};
778 /// @endcode
779 /// @details An example that constructs a list of pointer to all leaf nodes is:
780 /// @code
781 /// std::vector<const LeafNodeType*> array;//most std contains have the required API
782 /// array.reserve(tree.leafCount());//this is a fast preallocation.
783 /// tree.getNodes(array);
784 /// @endcode
785 template<typename ArrayT> void getNodes(ArrayT& array);
786 template<typename ArrayT> void getNodes(ArrayT& array) const;
787 //@}
788
789 //@{
790 /// @brief Steals all nodes of a certain type from the tree and
791 /// adds them to a container with the following API:
792 /// @code
793 /// struct ArrayT {
794 /// using value_type = ...;// defines the type of nodes to be added to the array
795 /// void push_back(value_type nodePtr);// method that add nodes to the array
796 /// };
797 /// @endcode
798 /// @details An example of a wrapper around a c-style array is:
799 /// @code
800 /// struct MyArray {
801 /// using value_type = LeafType*;
802 /// value_type* ptr;
803 /// MyArray(value_type* array) : ptr(array) {}
804 /// void push_back(value_type leaf) { *ptr++ = leaf; }
805 ///};
806 /// @endcode
807 /// @details An example that constructs a list of pointer to all leaf nodes is:
808 /// @code
809 /// std::vector<const LeafNodeType*> array;//most std contains have the required API
810 /// array.reserve(tree.leafCount());//this is a fast preallocation.
811 /// tree.stealNodes(array);
812 /// @endcode
813 template<typename ArrayT>
814 void stealNodes(ArrayT& array, const ValueType& value, bool state);
815 template<typename ArrayT>
816 void stealNodes(ArrayT& array) { this->stealNodes(array, mBackground, false); }
817 //@}
818
819 /// @brief Efficiently merge another tree into this tree using one of several schemes.
820 /// @details This operation is primarily intended to combine trees that are mostly
821 /// non-overlapping (for example, intermediate trees from computations that are
822 /// parallelized across disjoint regions of space).
823 /// @note This operation is not guaranteed to produce an optimally sparse tree.
824 /// Follow merge() with prune() for optimal sparseness.
825 /// @warning This operation always empties the other tree.
826 template<MergePolicy Policy> void merge(RootNode& other);
827
828 /// @brief Union this tree's set of active values with the active values
829 /// of the other tree, whose @c ValueType may be different.
830 /// @details The resulting state of a value is active if the corresponding value
831 /// was already active OR if it is active in the other tree. Also, a resulting
832 /// value maps to a voxel if the corresponding value already mapped to a voxel
833 /// OR if it is a voxel in the other tree. Thus, a resulting value can only
834 /// map to a tile if the corresponding value already mapped to a tile
835 /// AND if it is a tile value in other tree.
836 ///
837 /// @note This operation modifies only active states, not values.
838 /// Specifically, active tiles and voxels in this tree are not changed, and
839 /// tiles or voxels that were inactive in this tree but active in the other tree
840 /// are marked as active in this tree but left with their original values.
841 ///
842 /// @note If preserveTiles is true, any active tile in this topology
843 /// will not be densified by overlapping child topology.
844 template<typename OtherChildType>
845 void topologyUnion(const RootNode<OtherChildType>& other, const bool preserveTiles = false);
846
847 /// @brief Intersects this tree's set of active values with the active values
848 /// of the other tree, whose @c ValueType may be different.
849 /// @details The resulting state of a value is active only if the corresponding
850 /// value was already active AND if it is active in the other tree. Also, a
851 /// resulting value maps to a voxel if the corresponding value
852 /// already mapped to an active voxel in either of the two grids
853 /// and it maps to an active tile or voxel in the other grid.
854 ///
855 /// @note This operation can delete branches in this grid if they
856 /// overlap with inactive tiles in the other grid. Likewise active
857 /// voxels can be turned into inactive voxels resulting in leaf
858 /// nodes with no active values. Thus, it is recommended to
859 /// subsequently call prune.
860 template<typename OtherChildType>
861 void topologyIntersection(const RootNode<OtherChildType>& other);
862
863 /// @brief Difference this tree's set of active values with the active values
864 /// of the other tree, whose @c ValueType may be different. So a
865 /// resulting voxel will be active only if the original voxel is
866 /// active in this tree and inactive in the other tree.
867 ///
868 /// @note This operation can delete branches in this grid if they
869 /// overlap with active tiles in the other grid. Likewise active
870 /// voxels can be turned into inactive voxels resulting in leaf
871 /// nodes with no active values. Thus, it is recommended to
872 /// subsequently call prune.
873 template<typename OtherChildType>
874 void topologyDifference(const RootNode<OtherChildType>& other);
875
876 template<typename CombineOp>
877 void combine(RootNode& other, CombineOp&, bool prune = false);
878
879 template<typename CombineOp, typename OtherRootNode /*= RootNode*/>
880 void combine2(const RootNode& other0, const OtherRootNode& other1,
881 CombineOp& op, bool prune = false);
882
883#if OPENVDB_ABI_VERSION_NUMBER >= 10
884 /// Return the grid index coordinates of this node's local origin.
885 const Coord& origin() const { return mOrigin; }
886 /// @brief change the origin on this root node
887 /// @param origin the index coordinates of the new alignment
888 ///
889 /// @warning This method will throw if the origin is non-zero, since
890 /// other tools do not yet support variable offsets.
891 void setOrigin(const Coord &origin);
892#endif
893
894private:
895 /// During topology-only construction, access is needed
896 /// to protected/private members of other template instances.
897 template<typename> friend class RootNode;
898
899 template<typename, typename, bool> friend struct RootNodeCopyHelper;
900 template<typename, typename, typename, bool> friend struct RootNodeCombineHelper;
901
902 /// Currently no-op, but can be used to define empty and delete keys for mTable
903 void initTable() {}
904 //@{
905 /// @internal Used by doVisit2().
906 void resetTable(MapType& table) { mTable.swap(table); table.clear(); }
907 void resetTable(const MapType&) const {}
908 //@}
909
910 Index getChildCount() const;
911 Index getTileCount() const;
912 Index getActiveTileCount() const;
913 Index getInactiveTileCount() const;
914
915#if OPENVDB_ABI_VERSION_NUMBER < 10
916 /// Static method that returns a MapType key for the given coordinates.
917 static Coord coordToKey(const Coord& xyz) {return xyz & ~(ChildType::DIM - 1); }
918#else
919 /// Return a MapType key for the given coordinates, offset by the mOrigin.
920 Coord coordToKey(const Coord& xyz) const { return (xyz - mOrigin) & ~(ChildType::DIM - 1); }
921#endif
922
923 /// Insert this node's mTable keys into the given set.
924 void insertKeys(CoordSet&) const;
925
926 /// Return @c true if this node's mTable contains the given key.
927 bool hasKey(const Coord& key) const { return mTable.find(key) != mTable.end(); }
928 //@{
929 /// @brief Look up the given key in this node's mTable.
930 /// @return an iterator pointing to the matching mTable entry or to mTable.end().
931 MapIter findKey(const Coord& key) { return mTable.find(key); }
932 MapCIter findKey(const Coord& key) const { return mTable.find(key); }
933 //@}
934 //@{
935 /// @brief Convert the given coordinates to a key and look the key up in this node's mTable.
936 /// @return an iterator pointing to the matching mTable entry or to mTable.end().
937 MapIter findCoord(const Coord& xyz) { return mTable.find(coordToKey(xyz)); }
938 MapCIter findCoord(const Coord& xyz) const { return mTable.find(coordToKey(xyz)); }
939 //@}
940 /// @brief Convert the given coordinates to a key and look the key up in this node's mTable.
941 /// @details If the key is not found, insert a background tile with that key.
942 /// @return an iterator pointing to the matching mTable entry.
943 MapIter findOrAddCoord(const Coord& xyz);
944
945 /// @brief Verify that the tree rooted at @a other has the same configuration
946 /// (levels, branching factors and node dimensions) as this tree, but allow
947 /// their ValueTypes to differ.
948 /// @throw TypeError if the other tree's configuration doesn't match this tree's.
949 template<typename OtherChildType>
950 static void enforceSameConfiguration(const RootNode<OtherChildType>& other);
951
952 /// @brief Verify that @a other has values of a type that can be converted
953 /// to this node's ValueType.
954 /// @details For example, values of type float are compatible with values of type Vec3s,
955 /// because a Vec3s can be constructed from a float. But the reverse is not true.
956 /// @throw TypeError if the other node's ValueType is not convertible into this node's.
957 template<typename OtherChildType>
958 static void enforceCompatibleValueTypes(const RootNode<OtherChildType>& other);
959
960 template<typename CombineOp, typename OtherRootNode /*= RootNode*/>
961 void doCombine2(const RootNode&, const OtherRootNode&, CombineOp&, bool prune);
962
963 MapType mTable;
964 ValueType mBackground;
965#if OPENVDB_ABI_VERSION_NUMBER >= 10
966 Coord mOrigin;
967#endif
968 /// Transient Data (not serialized)
969 Index32 mTransientData = 0;
970}; // end of RootNode class
971
972
973////////////////////////////////////////
974
975
976/// @brief NodeChain<RootNodeType, RootNodeType::LEVEL>::Type is a openvdb::TypeList
977/// that lists the types of the nodes of the tree rooted at RootNodeType in reverse order,
978/// from LeafNode to RootNode.
979/// @details For example, if RootNodeType is
980/// @code
981/// RootNode<InternalNode<InternalNode<LeafNode> > >
982/// @endcode
983/// then NodeChain::Type is
984/// @code
985/// openvdb::TypeList<
986/// LeafNode,
987/// InternalNode<LeafNode>,
988/// InternalNode<InternalNode<LeafNode> >,
989/// RootNode<InternalNode<InternalNode<LeafNode> > > >
990/// @endcode
991///
992/// @note Use the following to get the Nth node type, where N=0 is the LeafNodeType:
993/// @code
994/// NodeChainType::Get<N>;
995/// @endcode
996template<typename HeadT, int HeadLevel>
997struct NodeChain {
998 using SubtreeT = typename NodeChain<typename HeadT::ChildNodeType, HeadLevel-1>::Type;
999 using Type = typename SubtreeT::template Append<HeadT>;
1000};
1001
1002/// Specialization to terminate NodeChain
1003template<typename HeadT>
1004struct NodeChain<HeadT, /*HeadLevel=*/1> {
1006};
1007
1008
1009////////////////////////////////////////
1010
1011
1012//@{
1013/// Helper metafunction used to implement RootNode::SameConfiguration
1014/// (which, as an inner class, can't be independently specialized)
1015template<typename ChildT1, typename NodeT2>
1017 static const bool value = false;
1018};
1019
1020template<typename ChildT1, typename ChildT2>
1021struct SameRootConfig<ChildT1, RootNode<ChildT2> > {
1022 static const bool value = ChildT1::template SameConfiguration<ChildT2>::value;
1023};
1024//@}
1025
1026
1027////////////////////////////////////////
1028
1029
1030template<typename ChildT>
1031inline
1033 : mBackground(zeroVal<ValueType>())
1034#if OPENVDB_ABI_VERSION_NUMBER >= 10
1035 , mOrigin(0, 0, 0)
1036#endif
1037{
1038 this->initTable();
1039}
1040
1041
1042template<typename ChildT>
1043inline
1045 : mBackground(background)
1046#if OPENVDB_ABI_VERSION_NUMBER >= 10
1047 , mOrigin(0, 0, 0)
1048#endif
1049{
1050 this->initTable();
1051}
1052
1053
1054template<typename ChildT>
1055template<typename OtherChildType>
1056inline
1058 const ValueType& backgd, const ValueType& foregd, TopologyCopy)
1059 : mBackground(backgd)
1060#if OPENVDB_ABI_VERSION_NUMBER >= 10
1061 , mOrigin(other.mOrigin)
1062#endif
1063 , mTransientData(other.mTransientData)
1064{
1065 using OtherRootT = RootNode<OtherChildType>;
1066
1067#if OPENVDB_ABI_VERSION_NUMBER >= 10
1068 if (mOrigin != Coord(0,0,0)) {
1069 OPENVDB_THROW(ValueError, "RootNode::RootNode: non-zero offsets are currently not supported");
1070 }
1071#endif
1072
1073 enforceSameConfiguration(other);
1074
1075 const Tile bgTile(backgd, /*active=*/false), fgTile(foregd, true);
1076 this->initTable();
1077
1078 for (typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
1079 mTable[i->first] = OtherRootT::isTile(i)
1080 ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
1081 : NodeStruct(*(new ChildT(OtherRootT::getChild(i), backgd, foregd, TopologyCopy())));
1082 }
1083}
1084
1085
1086template<typename ChildT>
1087template<typename OtherChildType>
1088inline
1090 const ValueType& backgd, TopologyCopy)
1091 : mBackground(backgd)
1092#if OPENVDB_ABI_VERSION_NUMBER >= 10
1093 , mOrigin(other.mOrigin)
1094#endif
1095 , mTransientData(other.mTransientData)
1096{
1097 using OtherRootT = RootNode<OtherChildType>;
1098
1099#if OPENVDB_ABI_VERSION_NUMBER >= 10
1100 if (mOrigin != Coord(0,0,0)) {
1101 OPENVDB_THROW(ValueError, "RootNode::RootNode: non-zero offsets are currently not supported");
1102 }
1103#endif
1104
1105 enforceSameConfiguration(other);
1106
1107 const Tile bgTile(backgd, /*active=*/false), fgTile(backgd, true);
1108 this->initTable();
1109 for (typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
1110 mTable[i->first] = OtherRootT::isTile(i)
1111 ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
1112 : NodeStruct(*(new ChildT(OtherRootT::getChild(i), backgd, TopologyCopy())));
1113 }
1114}
1115
1116
1117////////////////////////////////////////
1118
1119
1120// This helper class is a friend of RootNode and is needed so that assignment
1121// with value conversion can be specialized for compatible and incompatible
1122// pairs of RootNode types.
1123template<typename RootT, typename OtherRootT, bool Compatible = false>
1125{
1126 static inline void copyWithValueConversion(RootT& self, const OtherRootT& other)
1127 {
1128 // If the two root nodes have different configurations or incompatible ValueTypes,
1129 // throw an exception.
1130 self.enforceSameConfiguration(other);
1131 self.enforceCompatibleValueTypes(other);
1132 // One of the above two tests should throw, so we should never get here:
1133 std::ostringstream ostr;
1134 ostr << "cannot convert a " << typeid(OtherRootT).name()
1135 << " to a " << typeid(RootT).name();
1136 OPENVDB_THROW(TypeError, ostr.str());
1137 }
1138};
1139
1140// Specialization for root nodes of compatible types
1141template<typename RootT, typename OtherRootT>
1142struct RootNodeCopyHelper<RootT, OtherRootT, /*Compatible=*/true>
1143{
1144 static inline void copyWithValueConversion(RootT& self, const OtherRootT& other)
1145 {
1146 using ValueT = typename RootT::ValueType;
1147 using ChildT = typename RootT::ChildNodeType;
1148 using NodeStruct = typename RootT::NodeStruct;
1149 using Tile = typename RootT::Tile;
1150 using OtherValueT = typename OtherRootT::ValueType;
1151 using OtherMapCIter = typename OtherRootT::MapCIter;
1152 using OtherTile = typename OtherRootT::Tile;
1153
1154 struct Local {
1155 /// @todo Consider using a value conversion functor passed as an argument instead.
1156 static inline ValueT convertValue(const OtherValueT& val) { return ValueT(val); }
1157 };
1158
1159 self.mBackground = Local::convertValue(other.mBackground);
1160#if OPENVDB_ABI_VERSION_NUMBER >= 10
1161 if (other.mOrigin != Coord(0,0,0)) {
1162 OPENVDB_THROW(ValueError, "RootNodeCopyHelper::copyWithValueConversion: non-zero offsets are currently not supported");
1163 }
1164 self.mOrigin = other.mOrigin;
1165#endif
1166 self.mTransientData = other.mTransientData;
1167
1168 self.clear();
1169 self.initTable();
1170
1171 for (OtherMapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
1172 if (other.isTile(i)) {
1173 // Copy the other node's tile, but convert its value to this node's ValueType.
1174 const OtherTile& otherTile = other.getTile(i);
1175 self.mTable[i->first] = NodeStruct(
1176 Tile(Local::convertValue(otherTile.value), otherTile.active));
1177 } else {
1178 // Copy the other node's child, but convert its values to this node's ValueType.
1179 self.mTable[i->first] = NodeStruct(*(new ChildT(other.getChild(i))));
1180 }
1181 }
1182 }
1183};
1184
1185
1186// Overload for root nodes of the same type as this node
1187template<typename ChildT>
1188inline RootNode<ChildT>&
1190{
1191 if (&other != this) {
1192 mBackground = other.mBackground;
1193#if OPENVDB_ABI_VERSION_NUMBER >= 10
1194 mOrigin = other.mOrigin;
1195 if (mOrigin != Coord(0,0,0)) {
1196 OPENVDB_THROW(ValueError, "RootNode::operator=: non-zero offsets are currently not supported");
1197 }
1198#endif
1199 mTransientData = other.mTransientData;
1200
1201 this->clear();
1202 this->initTable();
1203
1204 for (MapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
1205 mTable[i->first] =
1206 isTile(i) ? NodeStruct(getTile(i)) : NodeStruct(*(new ChildT(getChild(i))));
1207 }
1208 }
1209 return *this;
1210}
1211
1212// Overload for root nodes of different types
1213template<typename ChildT>
1214template<typename OtherChildType>
1215inline RootNode<ChildT>&
1217{
1218 using OtherRootT = RootNode<OtherChildType>;
1219 using OtherValueT = typename OtherRootT::ValueType;
1220 static const bool compatible = (SameConfiguration<OtherRootT>::value
1221 && CanConvertType</*from=*/OtherValueT, /*to=*/ValueType>::value);
1223 return *this;
1224}
1225
1226
1227////////////////////////////////////////
1228
1229template<typename ChildT>
1230inline void
1231RootNode<ChildT>::setBackground(const ValueType& background, bool updateChildNodes)
1232{
1233 if (math::isExactlyEqual(background, mBackground)) return;
1234
1235 if (updateChildNodes) {
1236 // Traverse the tree, replacing occurrences of mBackground with background
1237 // and -mBackground with -background.
1238 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1239 ChildT *child = iter->second.child;
1240 if (child) {
1241 child->resetBackground(/*old=*/mBackground, /*new=*/background);
1242 } else {
1243 Tile& tile = getTile(iter);
1244 if (tile.active) continue;//only change inactive tiles
1245 if (math::isApproxEqual(tile.value, mBackground)) {
1246 tile.value = background;
1247 } else if (math::isApproxEqual(tile.value, math::negative(mBackground))) {
1248 tile.value = math::negative(background);
1249 }
1250 }
1251 }
1252 }
1253 mBackground = background;
1254}
1255
1256template<typename ChildT>
1257inline bool
1259{
1260 return !tile.active && math::isApproxEqual(tile.value, mBackground);
1261}
1262
1263template<typename ChildT>
1264inline bool
1265RootNode<ChildT>::isBackgroundTile(const MapIter& iter) const
1266{
1267 return isTileOff(iter) && math::isApproxEqual(getTile(iter).value, mBackground);
1268}
1269
1270template<typename ChildT>
1271inline bool
1272RootNode<ChildT>::isBackgroundTile(const MapCIter& iter) const
1273{
1274 return isTileOff(iter) && math::isApproxEqual(getTile(iter).value, mBackground);
1275}
1276
1277
1278template<typename ChildT>
1279inline size_t
1281{
1282 size_t count = 0;
1283 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1284 if (this->isBackgroundTile(i)) ++count;
1285 }
1286 return count;
1287}
1288
1289
1290template<typename ChildT>
1291inline size_t
1293{
1294 std::set<Coord> keysToErase;
1295 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1296 if (this->isBackgroundTile(i)) keysToErase.insert(i->first);
1297 }
1298 for (std::set<Coord>::iterator i = keysToErase.begin(), e = keysToErase.end(); i != e; ++i) {
1299 mTable.erase(*i);
1300 }
1301 return keysToErase.size();
1302}
1303
1304
1305////////////////////////////////////////
1306
1307
1308template<typename ChildT>
1309inline void
1310RootNode<ChildT>::insertKeys(CoordSet& keys) const
1311{
1312 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1313 keys.insert(i->first);
1314 }
1315}
1316
1317
1318template<typename ChildT>
1319inline typename RootNode<ChildT>::MapIter
1320RootNode<ChildT>::findOrAddCoord(const Coord& xyz)
1321{
1322 const Coord key = coordToKey(xyz);
1323 std::pair<MapIter, bool> result = mTable.insert(
1324 typename MapType::value_type(key, NodeStruct(Tile(mBackground, /*active=*/false))));
1325 return result.first;
1326}
1327
1328
1329template<typename ChildT>
1330inline bool
1332{
1333 const Coord key = coordToKey(xyz);
1334 std::pair<MapIter, bool> result = mTable.insert(
1335 typename MapType::value_type(key, NodeStruct(Tile(mBackground, /*active=*/false))));
1336 return result.second; // return true if the key did not already exist
1337}
1338
1339
1340////////////////////////////////////////
1341
1342
1343template<typename ChildT>
1344inline void
1345RootNode<ChildT>::getNodeLog2Dims(std::vector<Index>& dims)
1346{
1347 dims.push_back(0); // magic number; RootNode has no Log2Dim
1348 ChildT::getNodeLog2Dims(dims);
1349}
1350
1351
1352template<typename ChildT>
1353inline Coord
1355{
1356 return mTable.empty() ? Coord(0) : mTable.begin()->first;
1357}
1358
1359template<typename ChildT>
1360inline Coord
1362{
1363 return mTable.empty() ? Coord(0) : mTable.rbegin()->first + Coord(ChildT::DIM - 1);
1364}
1365
1366
1367template<typename ChildT>
1368inline void
1370{
1371 bbox.min() = this->getMinIndex();
1372 bbox.max() = this->getMaxIndex();
1373}
1374
1375
1376////////////////////////////////////////
1377
1378
1379template<typename ChildT>
1380template<typename OtherChildType>
1381inline bool
1383{
1384 using OtherRootT = RootNode<OtherChildType>;
1385 using OtherMapT = typename OtherRootT::MapType;
1386 using OtherIterT = typename OtherRootT::MapIter;
1387 using OtherCIterT = typename OtherRootT::MapCIter;
1388
1389 if (!hasSameConfiguration(other)) return false;
1390
1391 // Create a local copy of the other node's table.
1392 OtherMapT copyOfOtherTable = other.mTable;
1393
1394 // For each entry in this node's table...
1395 for (MapCIter thisIter = mTable.begin(); thisIter != mTable.end(); ++thisIter) {
1396 if (this->isBackgroundTile(thisIter)) continue; // ignore background tiles
1397
1398 // Fail if there is no corresponding entry in the other node's table.
1399 OtherCIterT otherIter = other.findKey(thisIter->first);
1400 if (otherIter == other.mTable.end()) return false;
1401
1402 // Fail if this entry is a tile and the other is a child or vice-versa.
1403 if (isChild(thisIter)) {//thisIter points to a child
1404 if (OtherRootT::isTile(otherIter)) return false;
1405 // Fail if both entries are children, but the children have different topology.
1406 if (!getChild(thisIter).hasSameTopology(&OtherRootT::getChild(otherIter))) return false;
1407 } else {//thisIter points to a tile
1408 if (OtherRootT::isChild(otherIter)) return false;
1409 if (getTile(thisIter).active != OtherRootT::getTile(otherIter).active) return false;
1410 }
1411
1412 // Remove tiles and child nodes with matching topology from
1413 // the copy of the other node's table. This is required since
1414 // the two root tables can include an arbitrary number of
1415 // background tiles and still have the same topology!
1416 copyOfOtherTable.erase(otherIter->first);
1417 }
1418 // Fail if the remaining entries in copyOfOtherTable are not all background tiles.
1419 for (OtherIterT i = copyOfOtherTable.begin(), e = copyOfOtherTable.end(); i != e; ++i) {
1420 if (!other.isBackgroundTile(i)) return false;
1421 }
1422 return true;
1423}
1424
1425
1426template<typename ChildT>
1427template<typename OtherChildType>
1428inline bool
1430{
1431 std::vector<Index> thisDims, otherDims;
1432 RootNode::getNodeLog2Dims(thisDims);
1434 return (thisDims == otherDims);
1435}
1436
1437
1438template<typename ChildT>
1439template<typename OtherChildType>
1440inline void
1442{
1443 std::vector<Index> thisDims, otherDims;
1444 RootNode::getNodeLog2Dims(thisDims);
1446 if (thisDims != otherDims) {
1447 std::ostringstream ostr;
1448 ostr << "grids have incompatible configurations (" << thisDims[0];
1449 for (size_t i = 1, N = thisDims.size(); i < N; ++i) ostr << " x " << thisDims[i];
1450 ostr << " vs. " << otherDims[0];
1451 for (size_t i = 1, N = otherDims.size(); i < N; ++i) ostr << " x " << otherDims[i];
1452 ostr << ")";
1453 OPENVDB_THROW(TypeError, ostr.str());
1454 }
1455}
1456
1457
1458template<typename ChildT>
1459template<typename OtherChildType>
1460inline bool
1462{
1463 using OtherValueType = typename OtherChildType::ValueType;
1464 return CanConvertType</*from=*/OtherValueType, /*to=*/ValueType>::value;
1465}
1466
1467
1468template<typename ChildT>
1469template<typename OtherChildType>
1470inline void
1472{
1473 using OtherValueType = typename OtherChildType::ValueType;
1475 std::ostringstream ostr;
1476 ostr << "values of type " << typeNameAsString<OtherValueType>()
1477 << " cannot be converted to type " << typeNameAsString<ValueType>();
1478 OPENVDB_THROW(TypeError, ostr.str());
1479 }
1480}
1481
1482
1483////////////////////////////////////////
1484
1485
1486template<typename ChildT>
1487inline Index64
1489{
1490 Index64 sum = sizeof(*this);
1491 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1492 if (const ChildT *child = iter->second.child) {
1493 sum += child->memUsage();
1494 }
1495 }
1496 return sum;
1497}
1498
1499
1500template<typename ChildT>
1501inline void
1503{
1504 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1505 delete i->second.child;
1506 }
1507 mTable.clear();
1508}
1509
1510
1511template<typename ChildT>
1512inline void
1514{
1515 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1516 if (const ChildT *child = iter->second.child) {
1517 child->evalActiveBoundingBox(bbox, visitVoxels);
1518 } else if (isTileOn(iter)) {
1519 bbox.expand(iter->first, ChildT::DIM);
1520 }
1521 }
1522}
1523
1524
1525template<typename ChildT>
1526inline Index
1528 return this->childCount();
1529}
1530
1531
1532template<typename ChildT>
1533inline Index
1534RootNode<ChildT>::getTileCount() const
1535{
1536 Index sum = 0;
1537 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1538 if (isTile(i)) ++sum;
1539 }
1540 return sum;
1541}
1542
1543
1544template<typename ChildT>
1545inline Index
1546RootNode<ChildT>::getActiveTileCount() const
1547{
1548 Index sum = 0;
1549 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1550 if (isTileOn(i)) ++sum;
1551 }
1552 return sum;
1553}
1554
1555
1556template<typename ChildT>
1557inline Index
1558RootNode<ChildT>::getInactiveTileCount() const
1559{
1560 Index sum = 0;
1561 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1562 if (isTileOff(i)) ++sum;
1563 }
1564 return sum;
1565}
1566
1567
1568template<typename ChildT>
1569inline Index32
1571{
1572 Index32 sum = 0;
1573 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1574 if (isChild(i)) sum += getChild(i).leafCount();
1575 }
1576 return sum;
1577}
1578
1579
1580template<typename ChildT>
1581inline Index32
1583{
1584 Index32 sum = 1;
1585 if (ChildT::LEVEL != 0) {
1586 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1587 if (isChild(i)) sum += getChild(i).nonLeafCount();
1588 }
1589 }
1590 return sum;
1591}
1592
1593
1594template<typename ChildT>
1595inline Index32
1597{
1598 Index sum = 0;
1599 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1600 if (isChild(i)) ++sum;
1601 }
1602 return sum;
1603}
1604
1605
1606template<typename ChildT>
1607inline Index64
1609{
1610 Index64 sum = 0;
1611 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1612 if (isChild(i)) {
1613 sum += getChild(i).onVoxelCount();
1614 } else if (isTileOn(i)) {
1615 sum += ChildT::NUM_VOXELS;
1616 }
1617 }
1618 return sum;
1619}
1620
1621
1622template<typename ChildT>
1623inline Index64
1625{
1626 Index64 sum = 0;
1627 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1628 if (isChild(i)) {
1629 sum += getChild(i).offVoxelCount();
1630 } else if (isTileOff(i) && !this->isBackgroundTile(i)) {
1631 sum += ChildT::NUM_VOXELS;
1632 }
1633 }
1634 return sum;
1635}
1636
1637
1638template<typename ChildT>
1639inline Index64
1641{
1642 Index64 sum = 0;
1643 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1644 if (isChild(i)) sum += getChild(i).onLeafVoxelCount();
1645 }
1646 return sum;
1647}
1648
1649
1650template<typename ChildT>
1651inline Index64
1653{
1654 Index64 sum = 0;
1655 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1656 if (isChild(i)) sum += getChild(i).offLeafVoxelCount();
1657 }
1658 return sum;
1659}
1660
1661template<typename ChildT>
1662inline Index64
1664{
1665 Index64 sum = 0;
1666 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1667 if (isChild(i)) {
1668 sum += getChild(i).onTileCount();
1669 } else if (isTileOn(i)) {
1670 sum += 1;
1671 }
1672 }
1673 return sum;
1674}
1675
1676template<typename ChildT>
1677inline void
1678RootNode<ChildT>::nodeCount(std::vector<Index32> &vec) const
1679{
1680 assert(vec.size() > LEVEL);
1681 Index32 sum = 0;
1682 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1683 if (isChild(i)) {
1684 ++sum;
1685 getChild(i).nodeCount(vec);
1686 }
1687 }
1688 vec[LEVEL] = 1;// one root node
1689 vec[ChildNodeType::LEVEL] = sum;
1690}
1691
1692////////////////////////////////////////
1693
1694
1695template<typename ChildT>
1696inline bool
1698{
1699 MapCIter iter = this->findCoord(xyz);
1700 if (iter == mTable.end() || isTileOff(iter)) return false;
1701 return isTileOn(iter) ? true : getChild(iter).isValueOn(xyz);
1702}
1703
1704template<typename ChildT>
1705inline bool
1707{
1708 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1709 if (isChild(i) ? getChild(i).hasActiveTiles() : getTile(i).active) return true;
1710 }
1711 return false;
1712}
1713
1714template<typename ChildT>
1715template<typename AccessorT>
1716inline bool
1717RootNode<ChildT>::isValueOnAndCache(const Coord& xyz, AccessorT& acc) const
1718{
1719 MapCIter iter = this->findCoord(xyz);
1720 if (iter == mTable.end() || isTileOff(iter)) return false;
1721 if (isTileOn(iter)) return true;
1722 acc.insert(xyz, &getChild(iter));
1723 return getChild(iter).isValueOnAndCache(xyz, acc);
1724}
1725
1726
1727template<typename ChildT>
1728inline const typename ChildT::ValueType&
1730{
1731 MapCIter iter = this->findCoord(xyz);
1732 return iter == mTable.end() ? mBackground
1733 : (isTile(iter) ? getTile(iter).value : getChild(iter).getValue(xyz));
1734}
1735
1736template<typename ChildT>
1737template<typename AccessorT>
1738inline const typename ChildT::ValueType&
1739RootNode<ChildT>::getValueAndCache(const Coord& xyz, AccessorT& acc) const
1740{
1741 MapCIter iter = this->findCoord(xyz);
1742 if (iter == mTable.end()) return mBackground;
1743 if (isChild(iter)) {
1744 acc.insert(xyz, &getChild(iter));
1745 return getChild(iter).getValueAndCache(xyz, acc);
1746 }
1747 return getTile(iter).value;
1748}
1749
1750
1751template<typename ChildT>
1752inline int
1754{
1755 MapCIter iter = this->findCoord(xyz);
1756 return iter == mTable.end() ? -1
1757 : (isTile(iter) ? 0 : int(LEVEL) - int(getChild(iter).getValueLevel(xyz)));
1758}
1759
1760template<typename ChildT>
1761template<typename AccessorT>
1762inline int
1763RootNode<ChildT>::getValueDepthAndCache(const Coord& xyz, AccessorT& acc) const
1764{
1765 MapCIter iter = this->findCoord(xyz);
1766 if (iter == mTable.end()) return -1;
1767 if (isTile(iter)) return 0;
1768 acc.insert(xyz, &getChild(iter));
1769 return int(LEVEL) - int(getChild(iter).getValueLevelAndCache(xyz, acc));
1770}
1771
1772
1773template<typename ChildT>
1774inline void
1776{
1777 MapIter iter = this->findCoord(xyz);
1778 if (iter != mTable.end() && !isTileOff(iter)) {
1779 if (isTileOn(iter)) {
1780 setChild(iter, *new ChildT(xyz, getTile(iter).value, /*active=*/true));
1781 }
1782 getChild(iter).setValueOff(xyz);
1783 }
1784}
1785
1786
1787template<typename ChildT>
1788inline void
1790{
1791 ChildT* child = nullptr;
1792 MapIter iter = this->findCoord(xyz);
1793 if (iter == mTable.end()) {
1794 if (on) {
1795 child = new ChildT(xyz, mBackground);
1796 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1797 } else {
1798 // Nothing to do; (x, y, z) is background and therefore already inactive.
1799 }
1800 } else if (isChild(iter)) {
1801 child = &getChild(iter);
1802 } else if (on != getTile(iter).active) {
1803 child = new ChildT(xyz, getTile(iter).value, !on);
1804 setChild(iter, *child);
1805 }
1806 if (child) child->setActiveState(xyz, on);
1807}
1808
1809template<typename ChildT>
1810template<typename AccessorT>
1811inline void
1812RootNode<ChildT>::setActiveStateAndCache(const Coord& xyz, bool on, AccessorT& acc)
1813{
1814 ChildT* child = nullptr;
1815 MapIter iter = this->findCoord(xyz);
1816 if (iter == mTable.end()) {
1817 if (on) {
1818 child = new ChildT(xyz, mBackground);
1819 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1820 } else {
1821 // Nothing to do; (x, y, z) is background and therefore already inactive.
1822 }
1823 } else if (isChild(iter)) {
1824 child = &getChild(iter);
1825 } else if (on != getTile(iter).active) {
1826 child = new ChildT(xyz, getTile(iter).value, !on);
1827 setChild(iter, *child);
1828 }
1829 if (child) {
1830 acc.insert(xyz, child);
1831 child->setActiveStateAndCache(xyz, on, acc);
1832 }
1833}
1834
1835
1836template<typename ChildT>
1837inline void
1839{
1840 ChildT* child = nullptr;
1841 MapIter iter = this->findCoord(xyz);
1842 if (iter == mTable.end()) {
1843 if (!math::isExactlyEqual(mBackground, value)) {
1844 child = new ChildT(xyz, mBackground);
1845 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1846 }
1847 } else if (isChild(iter)) {
1848 child = &getChild(iter);
1849 } else if (isTileOn(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1850 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1851 setChild(iter, *child);
1852 }
1853 if (child) child->setValueOff(xyz, value);
1854}
1855
1856template<typename ChildT>
1857template<typename AccessorT>
1858inline void
1859RootNode<ChildT>::setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1860{
1861 ChildT* child = nullptr;
1862 MapIter iter = this->findCoord(xyz);
1863 if (iter == mTable.end()) {
1864 if (!math::isExactlyEqual(mBackground, value)) {
1865 child = new ChildT(xyz, mBackground);
1866 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1867 }
1868 } else if (isChild(iter)) {
1869 child = &getChild(iter);
1870 } else if (isTileOn(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1871 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1872 setChild(iter, *child);
1873 }
1874 if (child) {
1875 acc.insert(xyz, child);
1876 child->setValueOffAndCache(xyz, value, acc);
1877 }
1878}
1879
1880
1881template<typename ChildT>
1882inline void
1884{
1885 ChildT* child = nullptr;
1886 MapIter iter = this->findCoord(xyz);
1887 if (iter == mTable.end()) {
1888 child = new ChildT(xyz, mBackground);
1889 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1890 } else if (isChild(iter)) {
1891 child = &getChild(iter);
1892 } else if (isTileOff(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1893 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1894 setChild(iter, *child);
1895 }
1896 if (child) child->setValueOn(xyz, value);
1897}
1898
1899template<typename ChildT>
1900template<typename AccessorT>
1901inline void
1902RootNode<ChildT>::setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1903{
1904 ChildT* child = nullptr;
1905 MapIter iter = this->findCoord(xyz);
1906 if (iter == mTable.end()) {
1907 child = new ChildT(xyz, mBackground);
1908 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1909 } else if (isChild(iter)) {
1910 child = &getChild(iter);
1911 } else if (isTileOff(iter) || !math::isExactlyEqual(getTile(iter).value, value)) {
1912 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1913 setChild(iter, *child);
1914 }
1915 if (child) {
1916 acc.insert(xyz, child);
1917 child->setValueAndCache(xyz, value, acc);
1918 }
1919}
1920
1921
1922template<typename ChildT>
1923inline void
1925{
1926 ChildT* child = nullptr;
1927 MapIter iter = this->findCoord(xyz);
1928 if (iter == mTable.end()) {
1929 child = new ChildT(xyz, mBackground);
1930 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1931 } else if (isChild(iter)) {
1932 child = &getChild(iter);
1933 } else if (!math::isExactlyEqual(getTile(iter).value, value)) {
1934 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1935 setChild(iter, *child);
1936 }
1937 if (child) child->setValueOnly(xyz, value);
1938}
1939
1940template<typename ChildT>
1941template<typename AccessorT>
1942inline void
1943RootNode<ChildT>::setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc)
1944{
1945 ChildT* child = nullptr;
1946 MapIter iter = this->findCoord(xyz);
1947 if (iter == mTable.end()) {
1948 child = new ChildT(xyz, mBackground);
1949 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1950 } else if (isChild(iter)) {
1951 child = &getChild(iter);
1952 } else if (!math::isExactlyEqual(getTile(iter).value, value)) {
1953 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1954 setChild(iter, *child);
1955 }
1956 if (child) {
1957 acc.insert(xyz, child);
1958 child->setValueOnlyAndCache(xyz, value, acc);
1959 }
1960}
1961
1962
1963template<typename ChildT>
1964template<typename ModifyOp>
1965inline void
1966RootNode<ChildT>::modifyValue(const Coord& xyz, const ModifyOp& op)
1967{
1968 ChildT* child = nullptr;
1969 MapIter iter = this->findCoord(xyz);
1970 if (iter == mTable.end()) {
1971 child = new ChildT(xyz, mBackground);
1972 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1973 } else if (isChild(iter)) {
1974 child = &getChild(iter);
1975 } else {
1976 // Need to create a child if the tile is inactive,
1977 // in order to activate voxel (x, y, z).
1978 bool createChild = isTileOff(iter);
1979 if (!createChild) {
1980 // Need to create a child if applying the functor
1981 // to the tile value produces a different value.
1982 const ValueType& tileVal = getTile(iter).value;
1983 ValueType modifiedVal = tileVal;
1984 op(modifiedVal);
1985 createChild = !math::isExactlyEqual(tileVal, modifiedVal);
1986 }
1987 if (createChild) {
1988 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1989 setChild(iter, *child);
1990 }
1991 }
1992 if (child) child->modifyValue(xyz, op);
1993}
1994
1995template<typename ChildT>
1996template<typename ModifyOp, typename AccessorT>
1997inline void
1998RootNode<ChildT>::modifyValueAndCache(const Coord& xyz, const ModifyOp& op, AccessorT& acc)
1999{
2000 ChildT* child = nullptr;
2001 MapIter iter = this->findCoord(xyz);
2002 if (iter == mTable.end()) {
2003 child = new ChildT(xyz, mBackground);
2004 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2005 } else if (isChild(iter)) {
2006 child = &getChild(iter);
2007 } else {
2008 // Need to create a child if the tile is inactive,
2009 // in order to activate voxel (x, y, z).
2010 bool createChild = isTileOff(iter);
2011 if (!createChild) {
2012 // Need to create a child if applying the functor
2013 // to the tile value produces a different value.
2014 const ValueType& tileVal = getTile(iter).value;
2015 ValueType modifiedVal = tileVal;
2016 op(modifiedVal);
2017 createChild = !math::isExactlyEqual(tileVal, modifiedVal);
2018 }
2019 if (createChild) {
2020 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2021 setChild(iter, *child);
2022 }
2023 }
2024 if (child) {
2025 acc.insert(xyz, child);
2026 child->modifyValueAndCache(xyz, op, acc);
2027 }
2028}
2029
2030
2031template<typename ChildT>
2032template<typename ModifyOp>
2033inline void
2035{
2036 ChildT* child = nullptr;
2037 MapIter iter = this->findCoord(xyz);
2038 if (iter == mTable.end()) {
2039 child = new ChildT(xyz, mBackground);
2040 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2041 } else if (isChild(iter)) {
2042 child = &getChild(iter);
2043 } else {
2044 const Tile& tile = getTile(iter);
2045 bool modifiedState = tile.active;
2046 ValueType modifiedVal = tile.value;
2047 op(modifiedVal, modifiedState);
2048 // Need to create a child if applying the functor to the tile
2049 // produces a different value or active state.
2050 if (modifiedState != tile.active || !math::isExactlyEqual(modifiedVal, tile.value)) {
2051 child = new ChildT(xyz, tile.value, tile.active);
2052 setChild(iter, *child);
2053 }
2054 }
2055 if (child) child->modifyValueAndActiveState(xyz, op);
2056}
2057
2058template<typename ChildT>
2059template<typename ModifyOp, typename AccessorT>
2060inline void
2062 const Coord& xyz, const ModifyOp& op, AccessorT& acc)
2063{
2064 ChildT* child = nullptr;
2065 MapIter iter = this->findCoord(xyz);
2066 if (iter == mTable.end()) {
2067 child = new ChildT(xyz, mBackground);
2068 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2069 } else if (isChild(iter)) {
2070 child = &getChild(iter);
2071 } else {
2072 const Tile& tile = getTile(iter);
2073 bool modifiedState = tile.active;
2074 ValueType modifiedVal = tile.value;
2075 op(modifiedVal, modifiedState);
2076 // Need to create a child if applying the functor to the tile
2077 // produces a different value or active state.
2078 if (modifiedState != tile.active || !math::isExactlyEqual(modifiedVal, tile.value)) {
2079 child = new ChildT(xyz, tile.value, tile.active);
2080 setChild(iter, *child);
2081 }
2082 }
2083 if (child) {
2084 acc.insert(xyz, child);
2085 child->modifyValueAndActiveStateAndCache(xyz, op, acc);
2086 }
2087}
2088
2089
2090template<typename ChildT>
2091inline bool
2093{
2094 MapCIter iter = this->findCoord(xyz);
2095 if (iter == mTable.end()) {
2096 value = mBackground;
2097 return false;
2098 } else if (isChild(iter)) {
2099 return getChild(iter).probeValue(xyz, value);
2100 }
2101 value = getTile(iter).value;
2102 return isTileOn(iter);
2103}
2104
2105template<typename ChildT>
2106template<typename AccessorT>
2107inline bool
2108RootNode<ChildT>::probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT& acc) const
2109{
2110 MapCIter iter = this->findCoord(xyz);
2111 if (iter == mTable.end()) {
2112 value = mBackground;
2113 return false;
2114 } else if (isChild(iter)) {
2115 acc.insert(xyz, &getChild(iter));
2116 return getChild(iter).probeValueAndCache(xyz, value, acc);
2117 }
2118 value = getTile(iter).value;
2119 return isTileOn(iter);
2120}
2121
2122
2123////////////////////////////////////////
2124
2125
2126template<typename ChildT>
2127inline void
2128RootNode<ChildT>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
2129{
2130 if (bbox.empty()) return;
2131
2132 // Iterate over the fill region in axis-aligned, tile-sized chunks.
2133 // (The first and last chunks along each axis might be smaller than a tile.)
2134 Coord xyz, tileMax;
2135 for (int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) {
2136 xyz.setX(x);
2137 for (int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) {
2138 xyz.setY(y);
2139 for (int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) {
2140 xyz.setZ(z);
2141
2142 // Get the bounds of the tile that contains voxel (x, y, z).
2143 Coord tileMin = coordToKey(xyz);
2144 tileMax = tileMin.offsetBy(ChildT::DIM - 1);
2145
2146 if (xyz != tileMin || Coord::lessThan(bbox.max(), tileMax)) {
2147 // If the box defined by (xyz, bbox.max()) doesn't completely enclose
2148 // the tile to which xyz belongs, create a child node (or retrieve
2149 // the existing one).
2150 ChildT* child = nullptr;
2151 MapIter iter = this->findKey(tileMin);
2152 if (iter == mTable.end()) {
2153 // No child or tile exists. Create a child and initialize it
2154 // with the background value.
2155 child = new ChildT(xyz, mBackground);
2156 mTable[tileMin] = NodeStruct(*child);
2157 } else if (isTile(iter)) {
2158 // Replace the tile with a newly-created child that is filled
2159 // with the tile's value and active state.
2160 const Tile& tile = getTile(iter);
2161 child = new ChildT(xyz, tile.value, tile.active);
2162 mTable[tileMin] = NodeStruct(*child);
2163 } else if (isChild(iter)) {
2164 child = &getChild(iter);
2165 }
2166 // Forward the fill request to the child.
2167 if (child) {
2168 const Coord tmp = Coord::minComponent(bbox.max(), tileMax);
2169 child->fill(CoordBBox(xyz, tmp), value, active);
2170 }
2171 } else {
2172 // If the box given by (xyz, bbox.max()) completely encloses
2173 // the tile to which xyz belongs, create the tile (if it
2174 // doesn't already exist) and give it the fill value.
2175 MapIter iter = this->findOrAddCoord(tileMin);
2176 setTile(iter, Tile(value, active));
2177 }
2178 }
2179 }
2180 }
2181}
2182
2183
2184template<typename ChildT>
2185inline void
2186RootNode<ChildT>::denseFill(const CoordBBox& bbox, const ValueType& value, bool active)
2187{
2188 if (bbox.empty()) return;
2189
2190 if (active && mTable.empty()) {
2191 // If this tree is empty, then a sparse fill followed by (threaded)
2192 // densification of active tiles is the more efficient approach.
2193 sparseFill(bbox, value, active);
2194 voxelizeActiveTiles(/*threaded=*/true);
2195 return;
2196 }
2197
2198 // Iterate over the fill region in axis-aligned, tile-sized chunks.
2199 // (The first and last chunks along each axis might be smaller than a tile.)
2200 Coord xyz, tileMin, tileMax;
2201 for (int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) {
2202 xyz.setX(x);
2203 for (int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) {
2204 xyz.setY(y);
2205 for (int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) {
2206 xyz.setZ(z);
2207
2208 // Get the bounds of the tile that contains voxel (x, y, z).
2209 tileMin = coordToKey(xyz);
2210 tileMax = tileMin.offsetBy(ChildT::DIM - 1);
2211
2212 // Retrieve the table entry for the tile that contains xyz,
2213 // or, if there is no table entry, add a background tile.
2214 const auto iter = findOrAddCoord(tileMin);
2215
2216 if (isTile(iter)) {
2217 // If the table entry is a tile, replace it with a child node
2218 // that is filled with the tile's value and active state.
2219 const auto& tile = getTile(iter);
2220 auto* child = new ChildT{tileMin, tile.value, tile.active};
2221 setChild(iter, *child);
2222 }
2223 // Forward the fill request to the child.
2224 getChild(iter).denseFill(bbox, value, active);
2225 }
2226 }
2227 }
2228}
2229
2230
2231////////////////////////////////////////
2232
2233
2234template<typename ChildT>
2235inline void
2237{
2238 // There is little point in threading over the root table since each tile
2239 // spans a huge index space (by default 4096^3) and hence we expect few
2240 // active tiles if any at all. In fact, you're very likely to run out of
2241 // memory if this method is called on a tree with root-level active tiles!
2242 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2243 if (this->isTileOff(i)) continue;
2244 ChildT* child = i->second.child;
2245 if (child == nullptr) {
2246 // If this table entry is an active tile (i.e., not off and not a child node),
2247 // replace it with a child node filled with active tiles of the same value.
2248 child = new ChildT{i->first, this->getTile(i).value, true};
2249 i->second.child = child;
2250 }
2251 child->voxelizeActiveTiles(threaded);
2252 }
2253}
2254
2255
2256////////////////////////////////////////
2257
2258
2259template<typename ChildT>
2260template<typename DenseT>
2261inline void
2262RootNode<ChildT>::copyToDense(const CoordBBox& bbox, DenseT& dense) const
2263{
2264 using DenseValueType = typename DenseT::ValueType;
2265
2266 const size_t xStride = dense.xStride(), yStride = dense.yStride(), zStride = dense.zStride();
2267 const Coord& min = dense.bbox().min();
2268 CoordBBox nodeBBox;
2269 for (Coord xyz = bbox.min(); xyz[0] <= bbox.max()[0]; xyz[0] = nodeBBox.max()[0] + 1) {
2270 for (xyz[1] = bbox.min()[1]; xyz[1] <= bbox.max()[1]; xyz[1] = nodeBBox.max()[1] + 1) {
2271 for (xyz[2] = bbox.min()[2]; xyz[2] <= bbox.max()[2]; xyz[2] = nodeBBox.max()[2] + 1) {
2272
2273 // Get the coordinate bbox of the child node that contains voxel xyz.
2274 nodeBBox = CoordBBox::createCube(coordToKey(xyz), ChildT::DIM);
2275
2276 // Get the coordinate bbox of the interection of inBBox and nodeBBox
2277 CoordBBox sub(xyz, Coord::minComponent(bbox.max(), nodeBBox.max()));
2278
2279 MapCIter iter = this->findKey(nodeBBox.min());
2280 if (iter != mTable.end() && isChild(iter)) {//is a child
2281 getChild(iter).copyToDense(sub, dense);
2282 } else {//is background or a tile value
2283 const ValueType value = iter==mTable.end() ? mBackground : getTile(iter).value;
2284 sub.translate(-min);
2285 DenseValueType* a0 = dense.data() + zStride*sub.min()[2];
2286 for (Int32 x=sub.min()[0], ex=sub.max()[0]+1; x<ex; ++x) {
2287 DenseValueType* a1 = a0 + x*xStride;
2288 for (Int32 y=sub.min()[1], ey=sub.max()[1]+1; y<ey; ++y) {
2289 DenseValueType* a2 = a1 + y*yStride;
2290 for (Int32 z=sub.min()[2], ez=sub.max()[2]+1; z<ez; ++z, a2 += zStride) {
2291 *a2 = DenseValueType(value);
2292 }
2293 }
2294 }
2295 }
2296 }
2297 }
2298 }
2299}
2300
2301////////////////////////////////////////
2302
2303
2304template<typename ChildT>
2305inline bool
2306RootNode<ChildT>::writeTopology(std::ostream& os, bool toHalf) const
2307{
2308 if (!toHalf) {
2309 os.write(reinterpret_cast<const char*>(&mBackground), sizeof(ValueType));
2310 } else {
2311 ValueType truncatedVal = io::truncateRealToHalf(mBackground);
2312 os.write(reinterpret_cast<const char*>(&truncatedVal), sizeof(ValueType));
2313 }
2314 io::setGridBackgroundValuePtr(os, &mBackground);
2315
2316 const Index numTiles = this->getTileCount(), numChildren = this->childCount();
2317 os.write(reinterpret_cast<const char*>(&numTiles), sizeof(Index));
2318 os.write(reinterpret_cast<const char*>(&numChildren), sizeof(Index));
2319
2320 if (numTiles == 0 && numChildren == 0) return false;
2321
2322 // Write tiles.
2323 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2324 if (isChild(i)) continue;
2325 os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 * sizeof(Int32));
2326 os.write(reinterpret_cast<const char*>(&getTile(i).value), sizeof(ValueType));
2327 os.write(reinterpret_cast<const char*>(&getTile(i).active), sizeof(bool));
2328 }
2329 // Write child nodes.
2330 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2331 if (isTile(i)) continue;
2332 os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 * sizeof(Int32));
2333 getChild(i).writeTopology(os, toHalf);
2334 }
2335
2336 return true; // not empty
2337}
2338
2339
2340template<typename ChildT>
2341inline bool
2342RootNode<ChildT>::readTopology(std::istream& is, bool fromHalf)
2343{
2344 // Delete the existing tree.
2345 this->clear();
2346
2348 // Read and convert an older-format RootNode.
2349
2350 // For backward compatibility with older file formats, read both
2351 // outside and inside background values.
2352 is.read(reinterpret_cast<char*>(&mBackground), sizeof(ValueType));
2353 ValueType inside;
2354 is.read(reinterpret_cast<char*>(&inside), sizeof(ValueType));
2355
2356 io::setGridBackgroundValuePtr(is, &mBackground);
2357
2358 // Read the index range.
2359 Coord rangeMin, rangeMax;
2360 is.read(reinterpret_cast<char*>(rangeMin.asPointer()), 3 * sizeof(Int32));
2361 is.read(reinterpret_cast<char*>(rangeMax.asPointer()), 3 * sizeof(Int32));
2362
2363 this->initTable();
2364 Index tableSize = 0, log2Dim[4] = { 0, 0, 0, 0 };
2365 Int32 offset[3];
2366 for (int i = 0; i < 3; ++i) {
2367 offset[i] = rangeMin[i] >> ChildT::TOTAL;
2368 rangeMin[i] = offset[i] << ChildT::TOTAL;
2369 log2Dim[i] = 1 + util::FindHighestOn((rangeMax[i] >> ChildT::TOTAL) - offset[i]);
2370 tableSize += log2Dim[i];
2371 rangeMax[i] = (((1 << log2Dim[i]) + offset[i]) << ChildT::TOTAL) - 1;
2372 }
2373 log2Dim[3] = log2Dim[1] + log2Dim[2];
2374 tableSize = 1U << tableSize;
2375
2376 // Read masks.
2377 util::RootNodeMask childMask(tableSize), valueMask(tableSize);
2378 childMask.load(is);
2379 valueMask.load(is);
2380
2381 // Read child nodes/values.
2382 for (Index i = 0; i < tableSize; ++i) {
2383 // Compute origin = offset2coord(i).
2384 Index n = i;
2385 Coord origin;
2386 origin[0] = (n >> log2Dim[3]) + offset[0];
2387 n &= (1U << log2Dim[3]) - 1;
2388 origin[1] = (n >> log2Dim[2]) + offset[1];
2389 origin[2] = (n & ((1U << log2Dim[2]) - 1)) + offset[1];
2390 origin <<= ChildT::TOTAL;
2391
2392 if (childMask.isOn(i)) {
2393 // Read in and insert a child node.
2394 ChildT* child = new ChildT(PartialCreate(), origin, mBackground);
2395 child->readTopology(is);
2396 mTable[origin] = NodeStruct(*child);
2397 } else {
2398 // Read in a tile value and insert a tile, but only if the value
2399 // is either active or non-background.
2400 ValueType value;
2401 is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
2402 if (valueMask.isOn(i) || (!math::isApproxEqual(value, mBackground))) {
2403 mTable[origin] = NodeStruct(Tile(value, valueMask.isOn(i)));
2404 }
2405 }
2406 }
2407 return true;
2408 }
2409
2410 // Read a RootNode that was stored in the current format.
2411
2412 is.read(reinterpret_cast<char*>(&mBackground), sizeof(ValueType));
2413 io::setGridBackgroundValuePtr(is, &mBackground);
2414
2415 Index numTiles = 0, numChildren = 0;
2416 is.read(reinterpret_cast<char*>(&numTiles), sizeof(Index));
2417 is.read(reinterpret_cast<char*>(&numChildren), sizeof(Index));
2418
2419 if (numTiles == 0 && numChildren == 0) return false;
2420
2421 Int32 vec[3];
2422 ValueType value;
2423 bool active;
2424
2425 // Read tiles.
2426 for (Index n = 0; n < numTiles; ++n) {
2427 is.read(reinterpret_cast<char*>(vec), 3 * sizeof(Int32));
2428 is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
2429 is.read(reinterpret_cast<char*>(&active), sizeof(bool));
2430 mTable[Coord(vec)] = NodeStruct(Tile(value, active));
2431 }
2432
2433 // Read child nodes.
2434 for (Index n = 0; n < numChildren; ++n) {
2435 is.read(reinterpret_cast<char*>(vec), 3 * sizeof(Int32));
2436 Coord origin(vec);
2437 ChildT* child = new ChildT(PartialCreate(), origin, mBackground);
2438 child->readTopology(is, fromHalf);
2439 mTable[Coord(vec)] = NodeStruct(*child);
2440 }
2441
2442 return true; // not empty
2443}
2444
2445
2446template<typename ChildT>
2447inline void
2448RootNode<ChildT>::writeBuffers(std::ostream& os, bool toHalf) const
2449{
2450 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2451 if (isChild(i)) getChild(i).writeBuffers(os, toHalf);
2452 }
2453}
2454
2455
2456template<typename ChildT>
2457inline void
2458RootNode<ChildT>::readBuffers(std::istream& is, bool fromHalf)
2459{
2460 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2461 if (isChild(i)) getChild(i).readBuffers(is, fromHalf);
2462 }
2463}
2464
2465
2466template<typename ChildT>
2467inline void
2468RootNode<ChildT>::readBuffers(std::istream& is, const CoordBBox& clipBBox, bool fromHalf)
2469{
2470 const Tile bgTile(mBackground, /*active=*/false);
2471
2472 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2473 if (isChild(i)) {
2474 // Stream in and clip the branch rooted at this child.
2475 // (We can't skip over children that lie outside the clipping region,
2476 // because buffers are serialized in depth-first order and need to be
2477 // unserialized in the same order.)
2478 ChildT& child = getChild(i);
2479 child.readBuffers(is, clipBBox, fromHalf);
2480 }
2481 }
2482 // Clip root-level tiles and prune children that were clipped.
2483 this->clip(clipBBox);
2484}
2485
2486
2487////////////////////////////////////////
2488
2489
2490template<typename ChildT>
2491inline void
2493{
2494 const Tile bgTile(mBackground, /*active=*/false);
2495
2496 // Iterate over a copy of this node's table so that we can modify the original.
2497 // (Copying the table copies child node pointers, not the nodes themselves.)
2498 MapType copyOfTable(mTable);
2499 for (MapIter i = copyOfTable.begin(), e = copyOfTable.end(); i != e; ++i) {
2500 const Coord& xyz = i->first; // tile or child origin
2501 CoordBBox tileBBox(xyz, xyz.offsetBy(ChildT::DIM - 1)); // tile or child bounds
2502 if (!clipBBox.hasOverlap(tileBBox)) {
2503 // This table entry lies completely outside the clipping region. Delete it.
2504 setTile(this->findCoord(xyz), bgTile); // delete any existing child node first
2505 mTable.erase(xyz);
2506 } else if (!clipBBox.isInside(tileBBox)) {
2507 // This table entry does not lie completely inside the clipping region
2508 // and must be clipped.
2509 if (isChild(i)) {
2510 getChild(i).clip(clipBBox, mBackground);
2511 } else {
2512 // Replace this tile with a background tile, then fill the clip region
2513 // with the tile's original value. (This might create a child branch.)
2514 tileBBox.intersect(clipBBox);
2515 const Tile& origTile = getTile(i);
2516 setTile(this->findCoord(xyz), bgTile);
2517 this->sparseFill(tileBBox, origTile.value, origTile.active);
2518 }
2519 } else {
2520 // This table entry lies completely inside the clipping region. Leave it intact.
2521 }
2522 }
2523 this->prune(); // also erases root-level background tiles
2524}
2525
2526
2527////////////////////////////////////////
2528
2529
2530template<typename ChildT>
2531inline void
2533{
2534 bool state = false;
2535 ValueType value = zeroVal<ValueType>();
2536 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2537 if (this->isTile(i)) continue;
2538 this->getChild(i).prune(tolerance);
2539 if (this->getChild(i).isConstant(value, state, tolerance)) {
2540 this->setTile(i, Tile(value, state));
2541 }
2542 }
2543 this->eraseBackgroundTiles();
2544}
2545
2546
2547////////////////////////////////////////
2548
2549
2550template<typename ChildT>
2551template<typename NodeT>
2552inline NodeT*
2553RootNode<ChildT>::stealNode(const Coord& xyz, const ValueType& value, bool state)
2554{
2555 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2556 NodeT::LEVEL > ChildT::LEVEL) return nullptr;
2558 MapIter iter = this->findCoord(xyz);
2559 if (iter == mTable.end() || isTile(iter)) return nullptr;
2560 return (std::is_same<NodeT, ChildT>::value)
2561 ? reinterpret_cast<NodeT*>(&stealChild(iter, Tile(value, state)))
2562 : getChild(iter).template stealNode<NodeT>(xyz, value, state);
2564}
2565
2566
2567////////////////////////////////////////
2568
2569
2570template<typename ChildT>
2571inline void
2573{
2574 if (leaf == nullptr) return;
2575 ChildT* child = nullptr;
2576 const Coord& xyz = leaf->origin();
2577 MapIter iter = this->findCoord(xyz);
2578 if (iter == mTable.end()) {
2579 if (ChildT::LEVEL>0) {
2580 child = new ChildT(xyz, mBackground, false);
2581 } else {
2582 child = reinterpret_cast<ChildT*>(leaf);
2583 }
2584 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2585 } else if (isChild(iter)) {
2586 if (ChildT::LEVEL>0) {
2587 child = &getChild(iter);
2588 } else {
2589 child = reinterpret_cast<ChildT*>(leaf);
2590 setChild(iter, *child);//this also deletes the existing child node
2591 }
2592 } else {//tile
2593 if (ChildT::LEVEL>0) {
2594 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2595 } else {
2596 child = reinterpret_cast<ChildT*>(leaf);
2597 }
2598 setChild(iter, *child);
2599 }
2600 child->addLeaf(leaf);
2601}
2602
2603
2604template<typename ChildT>
2605template<typename AccessorT>
2606inline void
2608{
2609 if (leaf == nullptr) return;
2610 ChildT* child = nullptr;
2611 const Coord& xyz = leaf->origin();
2612 MapIter iter = this->findCoord(xyz);
2613 if (iter == mTable.end()) {
2614 if (ChildT::LEVEL>0) {
2615 child = new ChildT(xyz, mBackground, false);
2616 } else {
2617 child = reinterpret_cast<ChildT*>(leaf);
2618 }
2619 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2620 } else if (isChild(iter)) {
2621 if (ChildT::LEVEL>0) {
2622 child = &getChild(iter);
2623 } else {
2624 child = reinterpret_cast<ChildT*>(leaf);
2625 setChild(iter, *child);//this also deletes the existing child node
2626 }
2627 } else {//tile
2628 if (ChildT::LEVEL>0) {
2629 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2630 } else {
2631 child = reinterpret_cast<ChildT*>(leaf);
2632 }
2633 setChild(iter, *child);
2634 }
2635 acc.insert(xyz, child);
2636 child->addLeafAndCache(leaf, acc);
2637}
2638
2639template<typename ChildT>
2640inline bool
2641RootNode<ChildT>::addChild(ChildT* child)
2642{
2643 if (!child) return false;
2644 const Coord& xyz = child->origin();
2645 MapIter iter = this->findCoord(xyz);
2646 if (iter == mTable.end()) {//background
2647 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2648 } else {//child or tile
2649 setChild(iter, *child);//this also deletes the existing child node
2650 }
2651 return true;
2652}
2653
2654#if OPENVDB_ABI_VERSION_NUMBER >= 10
2655template<typename ChildT>
2656inline void
2658{
2659 mOrigin = origin;
2660 if (mOrigin != Coord(0,0,0)) {
2661 OPENVDB_THROW(ValueError, "RootNode::setOrigin: non-zero offsets are currently not supported");
2662 }
2663}
2664#endif
2665
2666template<typename ChildT>
2667inline void
2668RootNode<ChildT>::addTile(const Coord& xyz, const ValueType& value, bool state)
2669{
2670 MapIter iter = this->findCoord(xyz);
2671 if (iter == mTable.end()) {//background
2672 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2673 } else {//child or tile
2674 setTile(iter, Tile(value, state));//this also deletes the existing child node
2675 }
2676}
2677
2678template<typename ChildT>
2679inline void
2681 const ValueType& value, bool state)
2682{
2683 if (LEVEL >= level) {
2684 MapIter iter = this->findCoord(xyz);
2685 if (iter == mTable.end()) {//background
2686 if (LEVEL > level) {
2687 ChildT* child = new ChildT(xyz, mBackground, false);
2688 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2689 child->addTile(level, xyz, value, state);
2690 } else {
2691 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2692 }
2693 } else if (isChild(iter)) {//child
2694 if (LEVEL > level) {
2695 getChild(iter).addTile(level, xyz, value, state);
2696 } else {
2697 setTile(iter, Tile(value, state));//this also deletes the existing child node
2698 }
2699 } else {//tile
2700 if (LEVEL > level) {
2701 ChildT* child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2702 setChild(iter, *child);
2703 child->addTile(level, xyz, value, state);
2704 } else {
2705 setTile(iter, Tile(value, state));
2706 }
2707 }
2708 }
2709}
2710
2711
2712template<typename ChildT>
2713template<typename AccessorT>
2714inline void
2716 bool state, AccessorT& acc)
2717{
2718 if (LEVEL >= level) {
2719 MapIter iter = this->findCoord(xyz);
2720 if (iter == mTable.end()) {//background
2721 if (LEVEL > level) {
2722 ChildT* child = new ChildT(xyz, mBackground, false);
2723 acc.insert(xyz, child);
2724 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2725 child->addTileAndCache(level, xyz, value, state, acc);
2726 } else {
2727 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2728 }
2729 } else if (isChild(iter)) {//child
2730 if (LEVEL > level) {
2731 ChildT* child = &getChild(iter);
2732 acc.insert(xyz, child);
2733 child->addTileAndCache(level, xyz, value, state, acc);
2734 } else {
2735 setTile(iter, Tile(value, state));//this also deletes the existing child node
2736 }
2737 } else {//tile
2738 if (LEVEL > level) {
2739 ChildT* child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2740 acc.insert(xyz, child);
2741 setChild(iter, *child);
2742 child->addTileAndCache(level, xyz, value, state, acc);
2743 } else {
2744 setTile(iter, Tile(value, state));
2745 }
2746 }
2747 }
2748}
2749
2750
2751////////////////////////////////////////
2752
2753
2754template<typename ChildT>
2755inline typename ChildT::LeafNodeType*
2757{
2758 ChildT* child = nullptr;
2759 MapIter iter = this->findCoord(xyz);
2760 if (iter == mTable.end()) {
2761 child = new ChildT(xyz, mBackground, false);
2762 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2763 } else if (isChild(iter)) {
2764 child = &getChild(iter);
2765 } else {
2766 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2767 setChild(iter, *child);
2768 }
2769 return child->touchLeaf(xyz);
2770}
2771
2772
2773template<typename ChildT>
2774template<typename AccessorT>
2775inline typename ChildT::LeafNodeType*
2777{
2778 ChildT* child = nullptr;
2779 MapIter iter = this->findCoord(xyz);
2780 if (iter == mTable.end()) {
2781 child = new ChildT(xyz, mBackground, false);
2782 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2783 } else if (isChild(iter)) {
2784 child = &getChild(iter);
2785 } else {
2786 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2787 setChild(iter, *child);
2788 }
2789 acc.insert(xyz, child);
2790 return child->touchLeafAndCache(xyz, acc);
2791}
2792
2793
2794////////////////////////////////////////
2795
2796
2797template<typename ChildT>
2798template<typename NodeT>
2799inline NodeT*
2801{
2802 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2803 NodeT::LEVEL > ChildT::LEVEL) return nullptr;
2805 MapIter iter = this->findCoord(xyz);
2806 if (iter == mTable.end() || isTile(iter)) return nullptr;
2807 ChildT* child = &getChild(iter);
2808 return (std::is_same<NodeT, ChildT>::value)
2809 ? reinterpret_cast<NodeT*>(child)
2810 : child->template probeNode<NodeT>(xyz);
2812}
2813
2814
2815template<typename ChildT>
2816template<typename NodeT>
2817inline const NodeT*
2819{
2820 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2821 NodeT::LEVEL > ChildT::LEVEL) return nullptr;
2823 MapCIter iter = this->findCoord(xyz);
2824 if (iter == mTable.end() || isTile(iter)) return nullptr;
2825 const ChildT* child = &getChild(iter);
2826 return (std::is_same<NodeT, ChildT>::value)
2827 ? reinterpret_cast<const NodeT*>(child)
2828 : child->template probeConstNode<NodeT>(xyz);
2830}
2831
2832
2833template<typename ChildT>
2834inline typename ChildT::LeafNodeType*
2836{
2837 return this->template probeNode<LeafNodeType>(xyz);
2838}
2839
2840
2841template<typename ChildT>
2842inline const typename ChildT::LeafNodeType*
2844{
2845 return this->template probeConstNode<LeafNodeType>(xyz);
2846}
2847
2848
2849template<typename ChildT>
2850template<typename AccessorT>
2851inline typename ChildT::LeafNodeType*
2853{
2854 return this->template probeNodeAndCache<LeafNodeType>(xyz, acc);
2855}
2856
2857
2858template<typename ChildT>
2859template<typename AccessorT>
2860inline const typename ChildT::LeafNodeType*
2861RootNode<ChildT>::probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const
2862{
2863 return this->template probeConstNodeAndCache<LeafNodeType>(xyz, acc);
2864}
2865
2866
2867template<typename ChildT>
2868template<typename AccessorT>
2869inline const typename ChildT::LeafNodeType*
2870RootNode<ChildT>::probeLeafAndCache(const Coord& xyz, AccessorT& acc) const
2871{
2872 return this->probeConstLeafAndCache(xyz, acc);
2873}
2874
2875
2876template<typename ChildT>
2877template<typename NodeT, typename AccessorT>
2878inline NodeT*
2880{
2881 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2882 NodeT::LEVEL > ChildT::LEVEL) return nullptr;
2884 MapIter iter = this->findCoord(xyz);
2885 if (iter == mTable.end() || isTile(iter)) return nullptr;
2886 ChildT* child = &getChild(iter);
2887 acc.insert(xyz, child);
2888 return (std::is_same<NodeT, ChildT>::value)
2889 ? reinterpret_cast<NodeT*>(child)
2890 : child->template probeNodeAndCache<NodeT>(xyz, acc);
2892}
2893
2894
2895template<typename ChildT>
2896template<typename NodeT,typename AccessorT>
2897inline const NodeT*
2898RootNode<ChildT>::probeConstNodeAndCache(const Coord& xyz, AccessorT& acc) const
2899{
2900 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2901 NodeT::LEVEL > ChildT::LEVEL) return nullptr;
2903 MapCIter iter = this->findCoord(xyz);
2904 if (iter == mTable.end() || isTile(iter)) return nullptr;
2905 const ChildT* child = &getChild(iter);
2906 acc.insert(xyz, child);
2907 return (std::is_same<NodeT, ChildT>::value)
2908 ? reinterpret_cast<const NodeT*>(child)
2909 : child->template probeConstNodeAndCache<NodeT>(xyz, acc);
2911}
2912
2913
2914////////////////////////////////////////
2915
2916template<typename ChildT>
2917template<typename ArrayT>
2918inline void
2920{
2921 using NodePtr = typename ArrayT::value_type;
2922 static_assert(std::is_pointer<NodePtr>::value,
2923 "argument to getNodes() must be a pointer array");
2924 using NodeType = typename std::remove_pointer<NodePtr>::type;
2925 using NonConstNodeType = typename std::remove_const<NodeType>::type;
2926 static_assert(NodeChainType::template Contains<NonConstNodeType>,
2927 "can't extract non-const nodes from a const tree");
2928 using ArrayChildT = typename std::conditional<
2929 std::is_const<NodeType>::value, const ChildT, ChildT>::type;
2930
2931 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2932 if (ChildT* child = iter->second.child) {
2934 if (std::is_same<NodePtr, ArrayChildT*>::value) {
2935 array.push_back(reinterpret_cast<NodePtr>(iter->second.child));
2936 } else {
2937 child->getNodes(array);//descent
2938 }
2940 }
2941 }
2942}
2943
2944template<typename ChildT>
2945template<typename ArrayT>
2946inline void
2947RootNode<ChildT>::getNodes(ArrayT& array) const
2948{
2949 using NodePtr = typename ArrayT::value_type;
2950 static_assert(std::is_pointer<NodePtr>::value,
2951 "argument to getNodes() must be a pointer array");
2952 using NodeType = typename std::remove_pointer<NodePtr>::type;
2953 static_assert(std::is_const<NodeType>::value,
2954 "argument to getNodes() must be an array of const node pointers");
2955 using NonConstNodeType = typename std::remove_const<NodeType>::type;
2956 static_assert(NodeChainType::template Contains<NonConstNodeType>,
2957 "can't extract non-const nodes from a const tree");
2958
2959 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2960 if (const ChildNodeType *child = iter->second.child) {
2962 if (std::is_same<NodePtr, const ChildT*>::value) {
2963 array.push_back(reinterpret_cast<NodePtr>(iter->second.child));
2964 } else {
2965 child->getNodes(array);//descent
2966 }
2968 }
2969 }
2970}
2971
2972////////////////////////////////////////
2973
2974template<typename ChildT>
2975template<typename ArrayT>
2976inline void
2977RootNode<ChildT>::stealNodes(ArrayT& array, const ValueType& value, bool state)
2978{
2979 using NodePtr = typename ArrayT::value_type;
2980 static_assert(std::is_pointer<NodePtr>::value,
2981 "argument to stealNodes() must be a pointer array");
2982 using NodeType = typename std::remove_pointer<NodePtr>::type;
2983 using NonConstNodeType = typename std::remove_const<NodeType>::type;
2984 static_assert(NodeChainType::template Contains<NonConstNodeType>,
2985 "can't extract non-const nodes from a const tree");
2986 using ArrayChildT = typename std::conditional<
2987 std::is_const<NodeType>::value, const ChildT, ChildT>::type;
2988
2989 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2990 if (ChildT* child = iter->second.child) {
2992 if (std::is_same<NodePtr, ArrayChildT*>::value) {
2993 array.push_back(reinterpret_cast<NodePtr>(&stealChild(iter, Tile(value, state))));
2994 } else {
2995 child->stealNodes(array, value, state);//descent
2996 }
2998 }
2999 }
3000}
3001
3002
3003////////////////////////////////////////
3004
3005
3006template<typename ChildT>
3007template<MergePolicy Policy>
3008inline void
3010{
3012
3013 switch (Policy) {
3014
3015 default:
3017 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3018 MapIter j = mTable.find(i->first);
3019 if (other.isChild(i)) {
3020 if (j == mTable.end()) { // insert other node's child
3021 ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
3022 child.resetBackground(other.mBackground, mBackground);
3023 mTable[i->first] = NodeStruct(child);
3024 } else if (isTile(j)) {
3025 if (isTileOff(j)) { // replace inactive tile with other node's child
3026 ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
3027 child.resetBackground(other.mBackground, mBackground);
3028 setChild(j, child);
3029 }
3030 } else { // merge both child nodes
3031 getChild(j).template merge<MERGE_ACTIVE_STATES>(getChild(i),
3032 other.mBackground, mBackground);
3033 }
3034 } else if (other.isTileOn(i)) {
3035 if (j == mTable.end()) { // insert other node's active tile
3036 mTable[i->first] = i->second;
3037 } else if (!isTileOn(j)) {
3038 // Replace anything except an active tile with the other node's active tile.
3039 setTile(j, Tile(other.getTile(i).value, true));
3040 }
3041 }
3042 }
3043 break;
3044
3045 case MERGE_NODES:
3046 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3047 MapIter j = mTable.find(i->first);
3048 if (other.isChild(i)) {
3049 if (j == mTable.end()) { // insert other node's child
3050 ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
3051 child.resetBackground(other.mBackground, mBackground);
3052 mTable[i->first] = NodeStruct(child);
3053 } else if (isTile(j)) { // replace tile with other node's child
3054 ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
3055 child.resetBackground(other.mBackground, mBackground);
3056 setChild(j, child);
3057 } else { // merge both child nodes
3058 getChild(j).template merge<MERGE_NODES>(
3059 getChild(i), other.mBackground, mBackground);
3060 }
3061 }
3062 }
3063 break;
3064
3066 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3067 MapIter j = mTable.find(i->first);
3068 if (other.isChild(i)) {
3069 if (j == mTable.end()) {
3070 // Steal and insert the other node's child.
3071 ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
3072 child.resetBackground(other.mBackground, mBackground);
3073 mTable[i->first] = NodeStruct(child);
3074 } else if (isTile(j)) {
3075 // Replace this node's tile with the other node's child.
3076 ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false));
3077 child.resetBackground(other.mBackground, mBackground);
3078 const Tile tile = getTile(j);
3079 setChild(j, child);
3080 if (tile.active) {
3081 // Merge the other node's child with this node's active tile.
3082 child.template merge<MERGE_ACTIVE_STATES_AND_NODES>(
3083 tile.value, tile.active);
3084 }
3085 } else /*if (isChild(j))*/ {
3086 // Merge the other node's child into this node's child.
3087 getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(getChild(i),
3088 other.mBackground, mBackground);
3089 }
3090 } else if (other.isTileOn(i)) {
3091 if (j == mTable.end()) {
3092 // Insert a copy of the other node's active tile.
3093 mTable[i->first] = i->second;
3094 } else if (isTileOff(j)) {
3095 // Replace this node's inactive tile with a copy of the other's active tile.
3096 setTile(j, Tile(other.getTile(i).value, true));
3097 } else if (isChild(j)) {
3098 // Merge the other node's active tile into this node's child.
3099 const Tile& tile = getTile(i);
3100 getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(
3101 tile.value, tile.active);
3102 }
3103 } // else if (other.isTileOff(i)) {} // ignore the other node's inactive tiles
3104 }
3105 break;
3106 }
3107
3108 // Empty the other tree so as not to leave it in a partially cannibalized state.
3109 other.clear();
3110
3112}
3113
3114
3115////////////////////////////////////////
3116
3117
3118template<typename ChildT>
3119template<typename OtherChildType>
3120inline void
3121RootNode<ChildT>::topologyUnion(const RootNode<OtherChildType>& other, const bool preserveTiles)
3122{
3123 using OtherRootT = RootNode<OtherChildType>;
3124 using OtherCIterT = typename OtherRootT::MapCIter;
3125
3126 enforceSameConfiguration(other);
3127
3128 for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3129 MapIter j = mTable.find(i->first);
3130 if (other.isChild(i)) {
3131 if (j == mTable.end()) { // create child branch with identical topology
3132 mTable[i->first] = NodeStruct(
3133 *(new ChildT(other.getChild(i), mBackground, TopologyCopy())));
3134 } else if (this->isChild(j)) { // union with child branch
3135 this->getChild(j).topologyUnion(other.getChild(i), preserveTiles);
3136 } else {// this is a tile so replace it with a child branch with identical topology
3137 if (!preserveTiles || this->isTileOff(j)) { // force child topology
3138 ChildT* child = new ChildT(
3139 other.getChild(i), this->getTile(j).value, TopologyCopy());
3140 if (this->isTileOn(j)) child->setValuesOn();//this is an active tile
3141 this->setChild(j, *child);
3142 }
3143 }
3144 } else if (other.isTileOn(i)) { // other is an active tile
3145 if (j == mTable.end()) { // insert an active tile
3146 mTable[i->first] = NodeStruct(Tile(mBackground, true));
3147 } else if (this->isChild(j)) {
3148 this->getChild(j).setValuesOn();
3149 } else if (this->isTileOff(j)) {
3150 this->setTile(j, Tile(this->getTile(j).value, true));
3151 }
3152 }
3153 }
3154}
3155
3156template<typename ChildT>
3157template<typename OtherChildType>
3158inline void
3160{
3161 using OtherRootT = RootNode<OtherChildType>;
3162 using OtherCIterT = typename OtherRootT::MapCIter;
3163
3164 enforceSameConfiguration(other);
3165
3166 std::set<Coord> tmp;//keys to erase
3167 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
3168 OtherCIterT j = other.mTable.find(i->first);
3169 if (this->isChild(i)) {
3170 if (j == other.mTable.end() || other.isTileOff(j)) {
3171 tmp.insert(i->first);//delete child branch
3172 } else if (other.isChild(j)) { // intersect with child branch
3173 this->getChild(i).topologyIntersection(other.getChild(j), mBackground);
3174 }
3175 } else if (this->isTileOn(i)) {
3176 if (j == other.mTable.end() || other.isTileOff(j)) {
3177 this->setTile(i, Tile(this->getTile(i).value, false));//turn inactive
3178 } else if (other.isChild(j)) { //replace with a child branch with identical topology
3179 ChildT* child =
3180 new ChildT(other.getChild(j), this->getTile(i).value, TopologyCopy());
3181 this->setChild(i, *child);
3182 }
3183 }
3184 }
3185 for (std::set<Coord>::iterator i = tmp.begin(), e = tmp.end(); i != e; ++i) {
3186 MapIter it = this->findCoord(*i);
3187 setTile(it, Tile()); // delete any existing child node first
3188 mTable.erase(it);
3189 }
3190}
3191
3192template<typename ChildT>
3193template<typename OtherChildType>
3194inline void
3196{
3197 using OtherRootT = RootNode<OtherChildType>;
3198 using OtherCIterT = typename OtherRootT::MapCIter;
3199
3200 enforceSameConfiguration(other);
3201
3202 for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3203 MapIter j = mTable.find(i->first);
3204 if (other.isChild(i)) {
3205 if (j == mTable.end() || this->isTileOff(j)) {
3206 //do nothing
3207 } else if (this->isChild(j)) { // difference with child branch
3208 this->getChild(j).topologyDifference(other.getChild(i), mBackground);
3209 } else if (this->isTileOn(j)) {
3210 // this is an active tile so create a child node and descent
3211 ChildT* child = new ChildT(j->first, this->getTile(j).value, true);
3212 child->topologyDifference(other.getChild(i), mBackground);
3213 this->setChild(j, *child);
3214 }
3215 } else if (other.isTileOn(i)) { // other is an active tile
3216 if (j == mTable.end() || this->isTileOff(j)) {
3217 // do nothing
3218 } else if (this->isChild(j)) {
3219 setTile(j, Tile()); // delete any existing child node first
3220 mTable.erase(j);
3221 } else if (this->isTileOn(j)) {
3222 this->setTile(j, Tile(this->getTile(j).value, false));
3223 }
3224 }
3225 }
3226}
3227
3228////////////////////////////////////////
3229
3230
3231template<typename ChildT>
3232template<typename CombineOp>
3233inline void
3234RootNode<ChildT>::combine(RootNode& other, CombineOp& op, bool prune)
3235{
3237
3238 CoordSet keys;
3239 this->insertKeys(keys);
3240 other.insertKeys(keys);
3241
3242 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3243 MapIter iter = findOrAddCoord(*i), otherIter = other.findOrAddCoord(*i);
3244 if (isTile(iter) && isTile(otherIter)) {
3245 // Both this node and the other node have constant values (tiles).
3246 // Combine the two values and store the result as this node's new tile value.
3247 op(args.setARef(getTile(iter).value)
3248 .setAIsActive(isTileOn(iter))
3249 .setBRef(getTile(otherIter).value)
3250 .setBIsActive(isTileOn(otherIter)));
3251 setTile(iter, Tile(args.result(), args.resultIsActive()));
3252
3253 } else if (isChild(iter) && isTile(otherIter)) {
3254 // Combine this node's child with the other node's constant value.
3255 ChildT& child = getChild(iter);
3256 child.combine(getTile(otherIter).value, isTileOn(otherIter), op);
3257
3258 } else if (isTile(iter) && isChild(otherIter)) {
3259 // Combine this node's constant value with the other node's child,
3260 // but use a new functor in which the A and B values are swapped,
3261 // since the constant value is the A value, not the B value.
3263 ChildT& child = getChild(otherIter);
3264 child.combine(getTile(iter).value, isTileOn(iter), swappedOp);
3265
3266 // Steal the other node's child.
3267 setChild(iter, stealChild(otherIter, Tile()));
3268
3269 } else /*if (isChild(iter) && isChild(otherIter))*/ {
3270 // Combine this node's child with the other node's child.
3271 ChildT &child = getChild(iter), &otherChild = getChild(otherIter);
3272 child.combine(otherChild, op);
3273 }
3274 if (prune && isChild(iter)) getChild(iter).prune();
3275 }
3276
3277 // Combine background values.
3278 op(args.setARef(mBackground).setBRef(other.mBackground));
3279 mBackground = args.result();
3280
3281 // Empty the other tree so as not to leave it in a partially cannibalized state.
3282 other.clear();
3283}
3284
3285
3286////////////////////////////////////////
3287
3288
3289// This helper class is a friend of RootNode and is needed so that combine2
3290// can be specialized for compatible and incompatible pairs of RootNode types.
3291template<typename CombineOp, typename RootT, typename OtherRootT, bool Compatible = false>
3293{
3294 static inline void combine2(RootT& self, const RootT&, const OtherRootT& other1,
3295 CombineOp&, bool)
3296 {
3297 // If the two root nodes have different configurations or incompatible ValueTypes,
3298 // throw an exception.
3299 self.enforceSameConfiguration(other1);
3300 self.enforceCompatibleValueTypes(other1);
3301 // One of the above two tests should throw, so we should never get here:
3302 std::ostringstream ostr;
3303 ostr << "cannot combine a " << typeid(OtherRootT).name()
3304 << " into a " << typeid(RootT).name();
3305 OPENVDB_THROW(TypeError, ostr.str());
3306 }
3307};
3308
3309// Specialization for root nodes of compatible types
3310template<typename CombineOp, typename RootT, typename OtherRootT>
3311struct RootNodeCombineHelper<CombineOp, RootT, OtherRootT, /*Compatible=*/true>
3312{
3313 static inline void combine2(RootT& self, const RootT& other0, const OtherRootT& other1,
3314 CombineOp& op, bool prune)
3315 {
3316 self.doCombine2(other0, other1, op, prune);
3317 }
3318};
3319
3320
3321template<typename ChildT>
3322template<typename CombineOp, typename OtherRootNode>
3323inline void
3324RootNode<ChildT>::combine2(const RootNode& other0, const OtherRootNode& other1,
3325 CombineOp& op, bool prune)
3326{
3327 using OtherValueType = typename OtherRootNode::ValueType;
3328 static const bool compatible = (SameConfiguration<OtherRootNode>::value
3329 && CanConvertType</*from=*/OtherValueType, /*to=*/ValueType>::value);
3331 *this, other0, other1, op, prune);
3332}
3333
3334
3335template<typename ChildT>
3336template<typename CombineOp, typename OtherRootNode>
3337inline void
3338RootNode<ChildT>::doCombine2(const RootNode& other0, const OtherRootNode& other1,
3339 CombineOp& op, bool prune)
3340{
3341 enforceSameConfiguration(other1);
3342
3343 using OtherValueT = typename OtherRootNode::ValueType;
3344 using OtherTileT = typename OtherRootNode::Tile;
3345 using OtherNodeStructT = typename OtherRootNode::NodeStruct;
3346 using OtherMapCIterT = typename OtherRootNode::MapCIter;
3347
3349
3350 CoordSet keys;
3351 other0.insertKeys(keys);
3352 other1.insertKeys(keys);
3353
3354 const NodeStruct bg0(Tile(other0.mBackground, /*active=*/false));
3355 const OtherNodeStructT bg1(OtherTileT(other1.mBackground, /*active=*/false));
3356
3357 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3358 MapIter thisIter = this->findOrAddCoord(*i);
3359 MapCIter iter0 = other0.findKey(*i);
3360 OtherMapCIterT iter1 = other1.findKey(*i);
3361 const NodeStruct& ns0 = (iter0 != other0.mTable.end()) ? iter0->second : bg0;
3362 const OtherNodeStructT& ns1 = (iter1 != other1.mTable.end()) ? iter1->second : bg1;
3363 if (ns0.isTile() && ns1.isTile()) {
3364 // Both input nodes have constant values (tiles).
3365 // Combine the two values and add a new tile to this node with the result.
3366 op(args.setARef(ns0.tile.value)
3367 .setAIsActive(ns0.isTileOn())
3368 .setBRef(ns1.tile.value)
3369 .setBIsActive(ns1.isTileOn()));
3370 setTile(thisIter, Tile(args.result(), args.resultIsActive()));
3371 } else {
3372 if (!isChild(thisIter)) {
3373 // Add a new child with the same coordinates, etc. as the other node's child.
3374 const Coord& childOrigin =
3375 ns0.isChild() ? ns0.child->origin() : ns1.child->origin();
3376 setChild(thisIter, *(new ChildT(childOrigin, getTile(thisIter).value)));
3377 }
3378 ChildT& child = getChild(thisIter);
3379
3380 if (ns0.isTile()) {
3381 // Combine node1's child with node0's constant value
3382 // and write the result into this node's child.
3383 child.combine2(ns0.tile.value, *ns1.child, ns0.isTileOn(), op);
3384 } else if (ns1.isTile()) {
3385 // Combine node0's child with node1's constant value
3386 // and write the result into this node's child.
3387 child.combine2(*ns0.child, ns1.tile.value, ns1.isTileOn(), op);
3388 } else {
3389 // Combine node0's child with node1's child
3390 // and write the result into this node's child.
3391 child.combine2(*ns0.child, *ns1.child, op);
3392 }
3393 }
3394 if (prune && isChild(thisIter)) getChild(thisIter).prune();
3395 }
3396
3397 // Combine background values.
3398 op(args.setARef(other0.mBackground).setBRef(other1.mBackground));
3399 mBackground = args.result();
3400}
3401
3402
3403} // namespace tree
3404} // namespace OPENVDB_VERSION_NAME
3405} // namespace openvdb
3406
3407#endif // OPENVDB_TREE_ROOTNODE_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 during file input.
Definition Types.h:689
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition Types.h:683
Definition Exceptions.h:64
Definition Exceptions.h:65
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
bool empty() const
Return true if this bounding box is empty (i.e., encloses no coordinates).
Definition Coord.h:358
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
static CoordBBox createCube(const Coord &min, ValueType dim)
Definition Coord.h:315
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
const Int32 * asPointer() const
Definition Coord.h:141
Int32 x() const
Definition Coord.h:130
Coord & setZ(Int32 z)
Definition Coord.h:81
Coord & setY(Int32 y)
Definition Coord.h:80
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
void read(std::istream &is)
Definition Coord.h:219
Definition RootNode.h:39
static CoordBBox getNodeBoundingBox()
Return the bounding box of this RootNode, i.e., an infinite bounding box.
Definition RootNode.h:406
void setValueAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition RootNode.h:1902
DenseIter< RootNode, MapIter, ChildType, ValueType > ChildAllIter
Definition RootNode.h:364
static bool hasSameConfiguration(const RootNode< OtherChildType > &other)
Return false if the other node's dimensions don't match this node's.
Definition RootNode.h:1429
int getValueDepth(const Coord &xyz) const
Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides.
Definition RootNode.h:1753
ValueIter< const RootNode, MapCIter, ValueOffPred, const ValueType > ValueOffCIter
Definition RootNode.h:370
RootNode(const RootNode &other)
Definition RootNode.h:75
ChildOnCIter cbeginChildOn() const
Definition RootNode.h:375
ChildOnCIter beginChildOn() const
Definition RootNode.h:378
ChildOnIter beginChildOn()
Definition RootNode.h:381
Index getDepth() const
Definition RootNode.h:462
bool isValueOn(const Coord &xyz) const
Definition RootNode.h:1697
ValueIter< const RootNode, MapCIter, ValueOnPred, const ValueType > ValueOnCIter
Definition RootNode.h:368
void getIndexRange(CoordBBox &bbox) const
Return the current index range. Both min and max are inclusive.
Definition RootNode.h:1369
void copyToDense(const CoordBBox &bbox, DenseT &dense) const
Copy into a dense grid the values of all voxels, both active and inactive, that intersect a given bou...
Definition RootNode.h:2262
RootNode & operator=(const RootNode &other)
Copy a root node of the same type as this node.
Definition RootNode.h:1189
Coord getMaxIndex() const
Return the largest index of the current tree.
Definition RootNode.h:1361
ValueOffCIter cbeginValueOff() const
Definition RootNode.h:386
LeafNodeType * probeLeafAndCache(const Coord &xyz, AccessorT &acc)
Same as probeLeaf() but, if necessary, update the given accessor with pointers to the nodes along the...
Index32 transientData() const
Return the transient data value.
Definition RootNode.h:409
void addLeafAndCache(LeafNodeType *leaf, AccessorT &)
Same as addLeaf() but, if necessary, update the given accessor with pointers to the nodes along the p...
Definition RootNode.h:2607
static Index getChildDim()
Definition RootNode.h:455
RootNode & operator=(const RootNode< OtherChildType > &other)
Copy a root node of the same tree configuration as this node but a different ValueType.
Index32 nonLeafCount() const
Definition RootNode.h:1582
void combine(RootNode &other, CombineOp &, bool prune=false)
Definition RootNode.h:3234
bool addChild(ChildType *child)
Add the given child node at the root level. If a child node with the same origin already exists,...
void getNodes(ArrayT &array)
Adds all nodes of a certain type to a container with the following API:
Definition RootNode.h:2919
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 RootNode.h:2553
void voxelizeActiveTiles(bool threaded=true)
Densify active tiles, i.e., replace them with leaf-level active voxels.
Definition RootNode.h:2236
LeafNodeType * touchLeafAndCache(const Coord &xyz, AccessorT &acc)
Same as touchLeaf() but, if necessary, update the given accessor with pointers to the nodes along the...
ValueIter< RootNode, MapIter, ValueOffPred, ValueType > ValueOffIter
Definition RootNode.h:369
ValueIter< RootNode, MapIter, ValueAllPred, ValueType > ValueAllIter
Definition RootNode.h:371
void topologyUnion(const RootNode< OtherChildType > &other, const bool preserveTiles=false)
Union this tree's set of active values with the active values of the other tree, whose ValueType may ...
Definition RootNode.h:3121
Index64 onLeafVoxelCount() const
Definition RootNode.h:1640
const LeafNodeType * probeConstLeafAndCache(const Coord &xyz, AccessorT &acc) const
void clip(const CoordBBox &)
Set all voxels that lie outside the given axis-aligned box to the background.
Definition RootNode.h:2492
LeafNodeType * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists,...
Definition RootNode.h:2835
static bool hasCompatibleValueType(const RootNode< OtherChildType > &other)
Definition RootNode.h:1461
ValueAllCIter cbeginValueAll() const
Definition RootNode.h:387
NodeT * probeNodeAndCache(const Coord &xyz, AccessorT &acc)
Same as probeNode() but, if necessary, update the given accessor with pointers to the nodes along the...
Definition RootNode.h:2879
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 RootNode.h:2532
typename NodeChain< RootNode, LEVEL >::Type NodeChainType
NodeChainType is a list of this tree's node types, from LeafNodeType to RootNode.
Definition RootNode.h:49
bool isBackgroundTile(const Tile &) const
Return true if the given tile is inactive and has the background value.
Definition RootNode.h:1258
typename ChildType::LeafNodeType LeafNodeType
Definition RootNode.h:42
size_t eraseBackgroundTiles()
Remove all background tiles.
Definition RootNode.h:1292
void topologyDifference(const RootNode< OtherChildType > &other)
Difference this tree's set of active values with the active values of the other tree,...
Definition RootNode.h:3195
ValueIter< RootNode, MapIter, ValueOnPred, ValueType > ValueOnIter
Definition RootNode.h:367
ValueOnCIter beginValueOn() const
Definition RootNode.h:388
void merge(RootNode &other)
Efficiently merge another tree into this tree using one of several schemes.
Definition RootNode.h:3009
ChildIter< RootNode, MapIter, ChildOnPred, ChildType > ChildOnIter
Definition RootNode.h:360
Index64 offLeafVoxelCount() const
Definition RootNode.h:1652
Index getWidth() const
Definition RootNode.h:460
Index getTableSize() const
Return the number of entries in this node's table.
Definition RootNode.h:458
void setOrigin(const Coord &origin)
change the origin on this root node
Definition RootNode.h:2657
void combine2(const RootNode &other0, const OtherRootNode &other1, CombineOp &op, bool prune=false)
Definition RootNode.h:3324
const Coord & origin() const
Return the grid index coordinates of this node's local origin.
Definition RootNode.h:885
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition RootNode.h:2034
void setValueOnlyAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition RootNode.h:1943
size_t numBackgroundTiles() const
Return the number of background tiles.
Definition RootNode.h:1280
ValueIter< const RootNode, MapCIter, ChildOffPred, ValueType > ChildOffCIter
Definition RootNode.h:363
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 RootNode.h:1924
bool empty() const
Return true if this node's table is either empty or contains only background tiles.
Definition RootNode.h:446
const LeafNodeType * probeConstLeaf(const Coord &xyz) const
Definition RootNode.h:2843
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 RootNode.h:2128
ValueOffCIter beginValueOff() const
Definition RootNode.h:389
void setValueOffAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition RootNode.h:1859
void addLeaf(LeafNodeType *leaf)
Add the given leaf node to this tree, creating a new branch if necessary. If a leaf node with the sam...
Definition RootNode.h:2572
const ValueType & getValueAndCache(const Coord &xyz, AccessorT &) const
ChildAllCIter cbeginChildAll() const
Definition RootNode.h:377
void addTile(const Coord &xyz, const ValueType &value, bool state)
Add a tile containing voxel (x, y, z) at the root level, deleting the existing branch if necessary.
Definition RootNode.h:2668
ChildAllIter beginChildAll()
Definition RootNode.h:383
static Index getLevel()
Definition RootNode.h:453
bool writeTopology(std::ostream &, bool toHalf=false) const
Definition RootNode.h:2306
ValueIter< const RootNode, MapCIter, ValueAllPred, const ValueType > ValueAllCIter
Definition RootNode.h:372
bool isValueOnAndCache(const Coord &xyz, AccessorT &) const
Definition RootNode.h:1717
const NodeT * probeConstNodeAndCache(const Coord &xyz, AccessorT &acc) const
Definition RootNode.h:2898
bool probeValue(const Coord &xyz, ValueType &value) const
Definition RootNode.h:2092
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 RootNode.h:1789
ValueOnIter beginValueOn()
Definition RootNode.h:391
void modifyValueAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition RootNode.h:1998
ChildOffCIter cbeginChildOff() const
Definition RootNode.h:376
ChildOffIter beginChildOff()
Definition RootNode.h:382
Index64 onVoxelCount() const
Definition RootNode.h:1608
ChildOffCIter beginChildOff() const
Definition RootNode.h:379
void addTileAndCache(Index level, const Coord &xyz, const ValueType &, bool state, AccessorT &)
Same as addTile() but, if necessary, update the given accessor with pointers to the nodes along the p...
Definition RootNode.h:2715
typename ChildType::ValueType ValueType
Definition RootNode.h:43
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don't change its value.
Definition RootNode.h:1775
void writeBuffers(std::ostream &, bool toHalf=false) const
Definition RootNode.h:2448
ValueOnCIter cbeginValueOn() const
Definition RootNode.h:385
Index32 leafCount() const
Definition RootNode.h:1570
const LeafNodeType * probeLeaf(const Coord &xyz) const
Index32 childCount() const
Definition RootNode.h:1596
Index64 onTileCount() const
Definition RootNode.h:1663
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 RootNode.h:1966
~RootNode()
Definition RootNode.h:123
Index64 offVoxelCount() const
Definition RootNode.h:1624
LeafNodeType * touchLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists,...
Definition RootNode.h:2756
typename ChildType::BuildType BuildType
Definition RootNode.h:44
void setBackground(const ValueType &value, bool updateChildNodes)
Change inactive tiles or voxels with a value equal to +/- the old background to the specified value (...
Definition RootNode.h:1231
DenseIter< const RootNode, MapCIter, const ChildType, const ValueType > ChildAllCIter
Definition RootNode.h:365
bool hasSameTopology(const RootNode< OtherChildType > &other) const
Return true if the given tree has the same node and active value topology as this tree (but possibly ...
Definition RootNode.h:1382
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 RootNode.h:2186
ChildAllCIter beginChildAll() const
Definition RootNode.h:380
void setActiveStateAndCache(const Coord &xyz, bool on, AccessorT &)
Definition RootNode.h:1812
void topologyIntersection(const RootNode< OtherChildType > &other)
Intersects this tree's set of active values with the active values of the other tree,...
Definition RootNode.h:3159
void setTransientData(Index32 transientData)
Set the transient data value.
Definition RootNode.h:411
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 RootNode.h:2977
Index getHeight() const
Definition RootNode.h:461
void clear()
Definition RootNode.h:1502
const LeafNodeType * probeLeafAndCache(const Coord &xyz, AccessorT &acc) const
bool probeValueAndCache(const Coord &xyz, ValueType &value, AccessorT &) const
Definition RootNode.h:2108
const NodeT * probeConstNode(const Coord &xyz) const
Definition RootNode.h:2818
void evalActiveBoundingBox(CoordBBox &bbox, bool visitVoxels=true) const
Expand the specified bbox so it includes the active tiles of this root node as well as all the active...
Definition RootNode.h:1513
const ValueType & background() const
Return this node's background value.
Definition RootNode.h:428
static void getNodeLog2Dims(std::vector< Index > &dims)
Definition RootNode.h:1345
RootNode(const RootNode< OtherChildType > &other)
Construct a new tree that reproduces the topology and active states of a tree of a different ValueTyp...
Definition RootNode.h:84
ValueOffIter beginValueOff()
Definition RootNode.h:392
ValueIter< RootNode, MapIter, ChildOffPred, const ValueType > ChildOffIter
Definition RootNode.h:362
void sparseFill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Definition RootNode.h:537
Coord getMinIndex() const
Return the smallest index of the current tree.
Definition RootNode.h:1354
ChildType ChildNodeType
Definition RootNode.h:41
bool hasActiveTiles() const
Return true if this root node, or any of its child nodes, have active tiles.
Definition RootNode.h:1706
int getValueDepthAndCache(const Coord &xyz, AccessorT &) const
Definition RootNode.h:1763
const ValueType & getValue(const Coord &xyz) const
Definition RootNode.h:1729
void nodeCount(std::vector< Index32 > &vec) const
Definition RootNode.h:1678
Index64 memUsage() const
Return the total amount of memory in bytes occupied by this node and its children.
Definition RootNode.h:1488
void setValueOn(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active.
Definition RootNode.h:1883
void stealNodes(ArrayT &array)
Definition RootNode.h:816
bool expand(const Coord &xyz)
Expand this node's table so that (x, y, z) is included in the index range.
Definition RootNode.h:1331
void readBuffers(std::istream &, bool fromHalf=false)
Definition RootNode.h:2458
void modifyValueAndActiveStateAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition RootNode.h:2061
ValueAllCIter beginValueAll() const
Definition RootNode.h:390
NodeT * probeNode(const Coord &xyz)
Return a pointer to the node that contains voxel (x, y, z). If no such node exists,...
Definition RootNode.h:2800
bool readTopology(std::istream &, bool fromHalf=false)
Definition RootNode.h:2342
ChildIter< const RootNode, MapCIter, ChildOnPred, const ChildType > ChildOnCIter
Definition RootNode.h:361
ValueAllIter beginValueAll()
Definition RootNode.h:393
friend class RootNode
Definition RootNode.h:897
Definition NodeMasks.h:1067
bool isOn(Index32 i) const
Definition NodeMasks.h:1331
void load(std::istream &is)
Definition NodeMasks.h:1372
OPENVDB_API void setGridBackgroundValuePtr(std::ios_base &, const void *background)
Specify (a pointer to) the background value of the grid currently being read from or written to the g...
OPENVDB_API uint32_t getFormatVersion(std::ios_base &)
Return the file format version number associated with the given input stream.
T truncateRealToHalf(const T &val)
Return the given value truncated to 16-bit float precision.
Definition Compression.h:216
bool operator==(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Equality operator, does exact floating point comparisons.
Definition Vec3.h:473
Mat3< typename promote< T0, T1 >::type > operator*(const Mat3< T0 > &m0, const Mat3< T1 > &m1)
Multiply m0 by m1 and return the resulting matrix.
Definition Mat3.h:597
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
bool operator!=(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Inequality operator, does exact floating point comparisons.
Definition Vec3.h:481
Index32 FindHighestOn(Index32 v)
Return the most significant on bit of the given 32-bit value.
Definition NodeMasks.h:159
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_ROOTNODE_MAP
Definition version.h.in:246
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
const char * typeNameAsString()
Definition Types.h:516
Definition Exceptions.h:13
#define OPENVDB_THROW(exception, message)
Definition Exceptions.h:74
CanConvertType<FromType, ToType>::value is true if a value of type ToType can be constructed from a v...
Definition Types.h:403
Definition Types.h:660
A list of types (not necessarily unique)
Definition TypeList.h:578
NodeChain<RootNodeType, RootNodeType::LEVEL>::Type is a openvdb::TypeList that lists the types of the...
Definition RootNode.h:997
typename NodeChain< typename HeadT::ChildNodeType, HeadLevel-1 >::Type SubtreeT
Definition RootNode.h:998
typename SubtreeT::template Append< HeadT > Type
Definition RootNode.h:999
static void combine2(RootT &self, const RootT &other0, const OtherRootT &other1, CombineOp &op, bool prune)
Definition RootNode.h:3313
static void combine2(RootT &self, const RootT &, const OtherRootT &other1, CombineOp &, bool)
Definition RootNode.h:3294
static void copyWithValueConversion(RootT &self, const OtherRootT &other)
Definition RootNode.h:1144
static void copyWithValueConversion(RootT &self, const OtherRootT &other)
Definition RootNode.h:1126
SameConfiguration<OtherNodeType>::value is true if and only if OtherNodeType is the type of a RootNod...
Definition RootNode.h:64
ValueConverter<T>::Type is the type of a RootNode having the same child hierarchy as this node but a ...
Definition RootNode.h:56
Definition RootNode.h:1016
#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