1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3
4 /// @file points/IndexIterator.h
5 ///
6 /// @author Dan Bailey
7 ///
8 /// @brief Index Iterators.
9
10 #ifndef OPENVDB_POINTS_INDEX_ITERATOR_HAS_BEEN_INCLUDED
11 #define OPENVDB_POINTS_INDEX_ITERATOR_HAS_BEEN_INCLUDED
12
13 #include <openvdb/version.h>
14 #include <openvdb/Types.h>
15
16 namespace openvdb {
17 OPENVDB_USE_VERSION_NAMESPACE
18 namespace OPENVDB_VERSION_NAME {
19 namespace points {
20
21
22 /// @brief Count up the number of times the iterator can iterate
23 ///
24 /// @param iter the iterator.
25 ///
26 /// @note counting by iteration only performed where a dynamic filter is in use,
27 template <typename IterT>
28 inline Index64 iterCount(const IterT& iter);
29
30
31 ////////////////////////////////////////
32
33
34 namespace index {
35 // Enum for informing early-exit optimizations
36 // PARTIAL - No optimizations are possible
37 // NONE - No indices to evaluate, can skip computation
38 // ALL - All indices to evaluate, can skip filtering
39 enum State
40 {
41 PARTIAL=0,
42 NONE,
43 ALL
44 };
45 }
46
47
48 /// @brief A no-op filter that can be used when iterating over all indices
49 /// @see points/IndexFilter.h for the documented interface for an index filter
50 class NullFilter
51 {
52 public:
initialized()53 static bool initialized() { return true; }
state()54 static index::State state() { return index::ALL; }
55 template <typename LeafT>
state(const LeafT &)56 static index::State state(const LeafT&) { return index::ALL; }
57
reset(const LeafT &)58 template <typename LeafT> void reset(const LeafT&) { }
valid(const IterT &)59 template <typename IterT> static bool valid(const IterT&) { return true; }
60 }; // class NullFilter
61
62
63 /// @brief A forward iterator over array indices in a single voxel
64 class ValueVoxelCIter
65 {
66 public:
67 struct Parent
68 {
69 Parent() = default;
ParentParent70 explicit Parent(Index32 offset): mOffset(offset) { }
getValueParent71 Index32 getValue(unsigned /*offset*/) const { return mOffset; }
72 private:
73 Index32 mOffset = 0;
74 }; // struct Parent
75
76 using NodeType = Parent;
77
78 ValueVoxelCIter() = default;
ValueVoxelCIter(Index32 prevOffset,Index32 offset)79 ValueVoxelCIter(Index32 prevOffset, Index32 offset)
80 : mOffset(offset), mParent(prevOffset) {}
ValueVoxelCIter(const ValueVoxelCIter & other)81 ValueVoxelCIter(const ValueVoxelCIter& other)
82 : mOffset(other.mOffset), mParent(other.mParent), mValid(other.mValid) {}
83
84 /// @brief Return the item to which this iterator is currently pointing.
85 Index32 operator*() { return mOffset; }
86 Index32 operator*() const { return mOffset; }
87
88 /// @brief Advance to the next (valid) item (prefix).
89 ValueVoxelCIter& operator++() { mValid = false; return *this; }
90
91 operator bool() const { return mValid; }
test()92 bool test() const { return mValid; }
end()93 Index32 end() const { return mOffset+1; }
94
reset(Index32,Index32)95 void reset(Index32 /*item*/, Index32 /*end*/) {}
96
parent()97 Parent& parent() { return mParent; }
offset()98 Index32 offset() { return mOffset; }
next()99 inline bool next() { this->operator++(); return this->test(); }
100
101 /// @brief For efficiency, Coord and active state assumed to be readily available
102 /// when iterating over indices of a single voxel
getCoord()103 Coord getCoord [[noreturn]] () const {
104 OPENVDB_THROW(RuntimeError, "ValueVoxelCIter does not provide a valid Coord.");
105 }
getCoord(Coord &)106 void getCoord [[noreturn]] (Coord& /*coord*/) const {
107 OPENVDB_THROW(RuntimeError, "ValueVoxelCIter does not provide a valid Coord.");
108 }
isValueOn()109 bool isValueOn [[noreturn]] () const {
110 OPENVDB_THROW(RuntimeError, "ValueVoxelCIter does not test if voxel is active.");
111 }
112
113 /// @{
114 /// @brief Equality operators
115 bool operator==(const ValueVoxelCIter& other) const { return mOffset == other.mOffset; }
116 bool operator!=(const ValueVoxelCIter& other) const { return !this->operator==(other); }
117 /// @}
118
119 private:
120 Index32 mOffset = 0;
121 Parent mParent;
122 mutable bool mValid = true;
123 }; // class ValueVoxelCIter
124
125
126 /// @brief A forward iterator over array indices with filtering
127 /// IteratorT can be either IndexIter or ValueIndexIter (or some custom index iterator)
128 /// FilterT should be a struct or class with a valid() method than can be evaluated per index
129 /// Here's a simple filter example that only accepts even indices:
130 ///
131 /// struct EvenIndexFilter
132 /// {
133 /// bool valid(const Index32 offset) const {
134 /// return (offset % 2) == 0;
135 /// }
136 /// };
137 ///
138 template <typename IteratorT, typename FilterT>
139 class IndexIter
140 {
141 public:
142 /// @brief A forward iterator over array indices from a value iterator (such as ValueOnCIter)
143 class ValueIndexIter
144 {
145 public:
ValueIndexIter(const IteratorT & iter)146 ValueIndexIter(const IteratorT& iter)
147 : mIter(iter), mParent(&mIter.parent())
148 {
149 if (mIter) {
150 assert(mParent);
151 Index32 start = (mIter.offset() > 0 ?
152 Index32(mParent->getValue(mIter.offset() - 1)) : Index32(0));
153 this->reset(start, *mIter);
154 if (mItem >= mEnd) this->operator++();
155 }
156 }
ValueIndexIter(const ValueIndexIter & other)157 ValueIndexIter(const ValueIndexIter& other)
158 : mEnd(other.mEnd), mItem(other.mItem), mIter(other.mIter), mParent(other.mParent)
159 {
160 assert(mParent);
161 }
162 ValueIndexIter& operator=(const ValueIndexIter&) = default;
163
end()164 inline Index32 end() const { return mEnd; }
165
reset(Index32 item,Index32 end)166 inline void reset(Index32 item, Index32 end) {
167 mItem = item;
168 mEnd = end;
169 }
170
171 /// @brief Returns the item to which this iterator is currently pointing.
172 inline Index32 operator*() { assert(mIter); return mItem; }
173 inline Index32 operator*() const { assert(mIter); return mItem; }
174
175 /// @brief Return @c true if this iterator is not yet exhausted.
176 inline operator bool() const { return mIter; }
test()177 inline bool test() const { return mIter; }
178
179 /// @brief Advance to the next (valid) item (prefix).
180 inline ValueIndexIter& operator++() {
181 ++mItem;
182 while (mItem >= mEnd && mIter.next()) {
183 assert(mParent);
184 this->reset(mParent->getValue(mIter.offset() - 1), *mIter);
185 }
186 return *this;
187 }
188
189 /// @brief Advance to the next (valid) item.
next()190 inline bool next() { this->operator++(); return this->test(); }
increment()191 inline bool increment() { this->next(); return this->test(); }
192
193 /// Return the coordinates of the item to which the value iterator is pointing.
getCoord()194 inline Coord getCoord() const { assert(mIter); return mIter.getCoord(); }
195 /// Return in @a xyz the coordinates of the item to which the value iterator is pointing.
getCoord(Coord & xyz)196 inline void getCoord(Coord& xyz) const { assert(mIter); xyz = mIter.getCoord(); }
197
198 /// @brief Return @c true if this iterator is pointing to an active value.
isValueOn()199 inline bool isValueOn() const { assert(mIter); return mIter.isValueOn(); }
200
201 /// Return the const value iterator
valueIter()202 inline const IteratorT& valueIter() const { return mIter; }
203
204 /// @brief Equality operators
205 bool operator==(const ValueIndexIter& other) const { return mItem == other.mItem; }
206 bool operator!=(const ValueIndexIter& other) const { return !this->operator==(other); }
207
208 private:
209 Index32 mEnd = 0;
210 Index32 mItem = 0;
211 IteratorT mIter;
212 const typename IteratorT::NodeType* mParent;
213 }; // ValueIndexIter
214
IndexIter(const IteratorT & iterator,const FilterT & filter)215 IndexIter(const IteratorT& iterator, const FilterT& filter)
216 : mIterator(iterator)
217 , mFilter(filter)
218 {
219 if (!mFilter.initialized()) {
220 OPENVDB_THROW(RuntimeError,
221 "Filter needs to be initialized before constructing the iterator.");
222 }
223 if (mIterator) {
224 this->reset(*mIterator, mIterator.end());
225 }
226 }
IndexIter(const IndexIter & other)227 IndexIter(const IndexIter& other)
228 : mIterator(other.mIterator)
229 , mFilter(other.mFilter)
230 {
231 if (!mFilter.initialized()) {
232 OPENVDB_THROW(RuntimeError,
233 "Filter needs to be initialized before constructing the iterator.");
234 }
235 }
236 IndexIter& operator=(const IndexIter& other)
237 {
238 if (&other != this) {
239 mIterator = other.mIterator;
240 mFilter = other.mFilter;
241 if (!mFilter.initialized()) {
242 OPENVDB_THROW(RuntimeError,
243 "Filter needs to be initialized before constructing the iterator.");
244 }
245 }
246 return *this;
247 }
248
end()249 Index32 end() const { return mIterator.end(); }
250
251 /// @brief Reset the begining and end of the iterator.
reset(Index32 begin,Index32 end)252 void reset(Index32 begin, Index32 end) {
253 mIterator.reset(begin, end);
254 while (mIterator.test() && !mFilter.template valid<ValueIndexIter>(mIterator)) {
255 ++mIterator;
256 }
257 }
258
259 /// @brief Returns the item to which this iterator is currently pointing.
260 Index32 operator*() { assert(mIterator); return *mIterator; }
261 Index32 operator*() const { assert(mIterator); return *mIterator; }
262
263 /// @brief Return @c true if this iterator is not yet exhausted.
264 operator bool() const { return mIterator.test(); }
test()265 bool test() const { return mIterator.test(); }
266
267 /// @brief Advance to the next (valid) item (prefix).
268 IndexIter& operator++() {
269 while (true) {
270 ++mIterator;
271 if (!mIterator.test() || mFilter.template valid<ValueIndexIter>(mIterator)) {
272 break;
273 }
274 }
275 return *this;
276 }
277
278 /// @brief Advance to the next (valid) item (postfix).
279 IndexIter operator++(int /*dummy*/) {
280 IndexIter newIterator(*this);
281 this->operator++();
282 return newIterator;
283 }
284
285 /// @brief Advance to the next (valid) item.
next()286 bool next() { this->operator++(); return this->test(); }
increment()287 bool increment() { this->next(); return this->test(); }
288
289 /// Return the const filter
filter()290 inline const FilterT& filter() const { return mFilter; }
291
292 /// Return the coordinates of the item to which the value iterator is pointing.
getCoord()293 inline Coord getCoord() const { assert(mIterator); return mIterator.getCoord(); }
294 /// Return in @a xyz the coordinates of the item to which the value iterator is pointing.
getCoord(Coord & xyz)295 inline void getCoord(Coord& xyz) const { assert(mIterator); xyz = mIterator.getCoord(); }
296
297 /// @brief Return @c true if the value iterator is pointing to an active value.
isValueOn()298 inline bool isValueOn() const { assert(mIterator); return mIterator.valueIter().isValueOn(); }
299
300 /// @brief Equality operators
301 bool operator==(const IndexIter& other) const { return mIterator == other.mIterator; }
302 bool operator!=(const IndexIter& other) const { return !this->operator==(other); }
303
304 private:
305 ValueIndexIter mIterator;
306 FilterT mFilter;
307 }; // class IndexIter
308
309
310 ////////////////////////////////////////
311
312
313 template <typename IterT>
iterCount(const IterT & iter)314 inline Index64 iterCount(const IterT& iter)
315 {
316 Index64 size = 0;
317 for (IterT newIter(iter); newIter; ++newIter, ++size) { }
318 return size;
319 }
320
321
322 ////////////////////////////////////////
323
324
325 } // namespace points
326 } // namespace OPENVDB_VERSION_NAME
327 } // namespace openvdb
328
329 #endif // OPENVDB_POINTS_INDEX_ITERATOR_HAS_BEEN_INCLUDED
330