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