OpenVDB  8.1.1
DDA.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 //
9 
10 #ifndef OPENVDB_MATH_DDA_HAS_BEEN_INCLUDED
11 #define OPENVDB_MATH_DDA_HAS_BEEN_INCLUDED
12 
13 #include "Coord.h"
14 #include "Math.h"
15 #include "Vec3.h"
16 #include <openvdb/Types.h>
17 #include <iostream> // for std::ostream
18 #include <limits> // for std::numeric_limits<Type>::max()
19 
20 namespace openvdb {
22 namespace OPENVDB_VERSION_NAME {
23 namespace math {
24 
33 template<typename RayT, Index Log2Dim = 0>
34 class DDA
35 {
36 public:
37  using RealType = typename RayT::RealType;
38  using RealT = RealType;
39  using Vec3Type = typename RayT::Vec3Type;
40  using Vec3T = Vec3Type;
41 
43  DDA() {}
44 
45  DDA(const RayT& ray) { this->init(ray); }
46 
47  DDA(const RayT& ray, RealT startTime) { this->init(ray, startTime); }
48 
49  DDA(const RayT& ray, RealT startTime, RealT maxTime) { this->init(ray, startTime, maxTime); }
50 
51  inline void init(const RayT& ray, RealT startTime, RealT maxTime)
52  {
53  assert(startTime <= maxTime);
54  static const int DIM = 1 << Log2Dim;
55  mT0 = startTime;
56  mT1 = maxTime;
57  const Vec3T &pos = ray(mT0), &dir = ray.dir(), &inv = ray.invDir();
58  mVoxel = Coord::floor(pos) & (~(DIM-1));
59  for (int axis = 0; axis < 3; ++axis) {
60  if (math::isZero(dir[axis])) {//handles dir = +/- 0
61  mStep[axis] = 0;//dummy value
62  mNext[axis] = std::numeric_limits<RealT>::max();//i.e. disabled!
63  mDelta[axis] = std::numeric_limits<RealT>::max();//dummy value
64  } else if (inv[axis] > 0) {
65  mStep[axis] = DIM;
66  mNext[axis] = mT0 + (mVoxel[axis] + DIM - pos[axis]) * inv[axis];
67  mDelta[axis] = mStep[axis] * inv[axis];
68  } else {
69  mStep[axis] = -DIM;
70  mNext[axis] = mT0 + (mVoxel[axis] - pos[axis]) * inv[axis];
71  mDelta[axis] = mStep[axis] * inv[axis];
72  }
73  }
74  }
75 
76  inline void init(const RayT& ray) { this->init(ray, ray.t0(), ray.t1()); }
77 
78  inline void init(const RayT& ray, RealT startTime) { this->init(ray, startTime, ray.t1()); }
79 
82  inline bool step()
83  {
84  const int stepAxis = static_cast<int>(math::MinIndex(mNext));
85  mT0 = mNext[stepAxis];
86  mNext[stepAxis] += mDelta[stepAxis];
87  mVoxel[stepAxis] += mStep[stepAxis];
88  return mT0 <= mT1;
89  }
90 
96  inline const Coord& voxel() const { return mVoxel; }
97 
103  inline RealType time() const { return mT0; }
104 
106  inline RealType maxTime() const { return mT1; }
107 
111  inline RealType next() const { return math::Min(mT1, mNext[0], mNext[1], mNext[2]); }
112 
115  void print(std::ostream& os = std::cout) const
116  {
117  os << "Dim=" << (1<<Log2Dim) << " time=" << mT0 << " next()="
118  << this->next() << " voxel=" << mVoxel << " next=" << mNext
119  << " delta=" << mDelta << " step=" << mStep << std::endl;
120  }
121 
122 private:
123  RealT mT0, mT1;
124  Coord mVoxel, mStep;
125  Vec3T mDelta, mNext;
126 }; // class DDA
127 
130 template<typename RayT, Index Log2Dim>
131 inline std::ostream& operator<<(std::ostream& os, const DDA<RayT, Log2Dim>& dda)
132 {
133  os << "Dim=" << (1<<Log2Dim) << " time=" << dda.time()
134  << " next()=" << dda.next() << " voxel=" << dda.voxel();
135  return os;
136 }
137 
139 
140 
143 template<typename TreeT, int NodeLevel>
145 {
146  using ChainT = typename TreeT::RootNodeType::NodeChainType;
147  using NodeT = typename ChainT::template Get<NodeLevel>;
148 
149  template <typename TesterT>
150  static bool test(TesterT& tester)
151  {
153  do {
154  if (tester.template hasNode<NodeT>(dda.voxel())) {
155  tester.setRange(dda.time(), dda.next());
156  if (LevelSetHDDA<TreeT, NodeLevel-1>::test(tester)) return true;
157  }
158  } while(dda.step());
159  return false;
160  }
161 };
162 
165 template<typename TreeT>
166 struct LevelSetHDDA<TreeT, -1>
167 {
168  template <typename TesterT>
169  static bool test(TesterT& tester)
170  {
171  math::DDA<typename TesterT::RayT, 0> dda(tester.ray());
172  tester.init(dda.time());
173  do { if (tester(dda.voxel(), dda.next())) return true; } while(dda.step());
174  return false;
175  }
176 };
177 
179 
186 template <typename TreeT, typename RayT, int ChildNodeLevel>
188 {
189 public:
190 
191  using ChainT = typename TreeT::RootNodeType::NodeChainType;
192  using NodeT = typename ChainT::template Get<ChildNodeLevel>;
193  using TimeSpanT = typename RayT::TimeSpan;
194 
196 
197  template <typename AccessorT>
198  TimeSpanT march(RayT& ray, AccessorT &acc)
199  {
200  TimeSpanT t(-1, -1);
201  if (ray.valid()) this->march(ray, acc, t);
202  return t;
203  }
204 
209  template <typename AccessorT, typename ListT>
210  void hits(RayT& ray, AccessorT &acc, ListT& times)
211  {
212  TimeSpanT t(-1,-1);
213  times.clear();
214  this->hits(ray, acc, times, t);
215  if (t.valid()) times.push_back(t);
216  }
217 
218 private:
219 
220  friend class VolumeHDDA<TreeT, RayT, ChildNodeLevel+1>;
221 
222  template <typename AccessorT>
223  bool march(RayT& ray, AccessorT &acc, TimeSpanT& t)
224  {
225  mDDA.init(ray);
226  do {
227  if (acc.template probeConstNode<NodeT>(mDDA.voxel()) != nullptr) {//child node
228  ray.setTimes(mDDA.time(), mDDA.next());
229  if (mHDDA.march(ray, acc, t)) return true;//terminate
230  } else if (acc.isValueOn(mDDA.voxel())) {//hit an active tile
231  if (t.t0<0) t.t0 = mDDA.time();//this is the first hit so set t0
232  } else if (t.t0>=0) {//hit an inactive tile after hitting active values
233  t.t1 = mDDA.time();//set end of active ray segment
234  if (t.valid()) return true;//terminate
235  t.set(-1, -1);//reset to an empty and invalid time-span
236  }
237  } while (mDDA.step());
238  if (t.t0>=0) t.t1 = mDDA.maxTime();
239  return false;
240  }
241 
246  template <typename AccessorT, typename ListT>
247  void hits(RayT& ray, AccessorT &acc, ListT& times, TimeSpanT& t)
248  {
249  mDDA.init(ray);
250  do {
251  if (acc.template probeConstNode<NodeT>(mDDA.voxel()) != nullptr) {//child node
252  ray.setTimes(mDDA.time(), mDDA.next());
253  mHDDA.hits(ray, acc, times, t);
254  } else if (acc.isValueOn(mDDA.voxel())) {//hit an active tile
255  if (t.t0<0) t.t0 = mDDA.time();//this is the first hit so set t0
256  } else if (t.t0>=0) {//hit an inactive tile after hitting active values
257  t.t1 = mDDA.time();//set end of active ray segment
258  if (t.valid()) times.push_back(t);
259  t.set(-1,-1);//reset to an empty and invalid time-span
260  }
261  } while (mDDA.step());
262  if (t.t0>=0) t.t1 = mDDA.maxTime();
263  }
264 
266  VolumeHDDA<TreeT, RayT, ChildNodeLevel-1> mHDDA;
267 };
268 
271 template <typename TreeT, typename RayT>
272 class VolumeHDDA<TreeT, RayT, 0>
273 {
274 public:
275 
276  using LeafT = typename TreeT::LeafNodeType;
277  using TimeSpanT = typename RayT::TimeSpan;
278 
280 
281  template <typename AccessorT>
282  TimeSpanT march(RayT& ray, AccessorT &acc)
283  {
284  TimeSpanT t(-1, -1);
285  if (ray.valid()) this->march(ray, acc, t);
286  return t;
287  }
288 
289  template <typename AccessorT, typename ListT>
290  void hits(RayT& ray, AccessorT &acc, ListT& times)
291  {
292  TimeSpanT t(-1,-1);
293  times.clear();
294  this->hits(ray, acc, times, t);
295  if (t.valid()) times.push_back(t);
296  }
297 
298 private:
299 
300  friend class VolumeHDDA<TreeT, RayT, 1>;
301 
302  template <typename AccessorT>
303  bool march(RayT& ray, AccessorT &acc, TimeSpanT& t)
304  {
305  mDDA.init(ray);
306  do {
307  if (acc.template probeConstNode<LeafT>(mDDA.voxel()) ||
308  acc.isValueOn(mDDA.voxel())) {//hit a leaf or an active tile
309  if (t.t0<0) t.t0 = mDDA.time();//this is the first hit
310  } else if (t.t0>=0) {//hit an inactive tile after hitting active values
311  t.t1 = mDDA.time();//set end of active ray segment
312  if (t.valid()) return true;//terminate
313  t.set(-1, -1);//reset to an empty and invalid time-span
314  }
315  } while (mDDA.step());
316  if (t.t0>=0) t.t1 = mDDA.maxTime();
317  return false;
318  }
319 
320  template <typename AccessorT, typename ListT>
321  void hits(RayT& ray, AccessorT &acc, ListT& times, TimeSpanT& t)
322  {
323  mDDA.init(ray);
324  do {
325  if (acc.template probeConstNode<LeafT>(mDDA.voxel()) ||
326  acc.isValueOn(mDDA.voxel())) {//hit a leaf or an active tile
327  if (t.t0<0) t.t0 = mDDA.time();//this is the first hit
328  } else if (t.t0>=0) {//hit an inactive tile after hitting active values
329  t.t1 = mDDA.time();//set end of active ray segment
330  if (t.valid()) times.push_back(t);
331  t.set(-1, -1);//reset to an empty and invalid time-span
332  }
333  } while (mDDA.step());
334  if (t.t0>=0) t.t1 = mDDA.maxTime();
335  }
337 };
338 
339 } // namespace math
340 } // namespace OPENVDB_VERSION_NAME
341 } // namespace openvdb
342 
343 #endif // OPENVDB_MATH_DDA_HAS_BEEN_INCLUDED
void init(const RayT &ray, RealT startTime, RealT maxTime)
Definition: DDA.h:51
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
DDA(const RayT &ray, RealT startTime, RealT maxTime)
Definition: DDA.h:49
RealType time() const
Return the time (parameterized along the Ray) of the first hit of a tree node of size 2^Log2Dim...
Definition: DDA.h:103
TimeSpanT march(RayT &ray, AccessorT &acc)
Definition: DDA.h:282
TimeSpanT march(RayT &ray, AccessorT &acc)
Definition: DDA.h:198
VolumeHDDA()
Definition: DDA.h:195
typename openvdb::v8_1::tree::Tree::RootNodeType::NodeChainType ChainT
Definition: DDA.h:191
typename ChainT::template Get< NodeLevel > NodeT
Definition: DDA.h:147
bool step()
Increment the voxel index to next intersected voxel or node and returns true if the step in time does...
Definition: DDA.h:82
bool isZero(const Type &x)
Return true if x is exactly equal to zero.
Definition: Math.h:338
const Type & Min(const Type &a, const Type &b)
Return the minimum of two values.
Definition: Math.h:659
RealType maxTime() const
Return the maximum time (parameterized along the Ray).
Definition: DDA.h:106
void init(const RayT &ray)
Definition: DDA.h:76
Helper class that implements Hierarchical Digital Differential Analyzers for ray intersections agains...
Definition: DDA.h:187
static bool test(TesterT &tester)
Definition: DDA.h:150
size_t MinIndex(const Vec3T &v)
Return the index [0,1,2] of the smallest value in a 3D vector.
Definition: Math.h:938
typename TreeT::RootNodeType::NodeChainType ChainT
Definition: DDA.h:146
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:107
typename TreeT::LeafNodeType LeafT
Definition: DDA.h:276
void hits(RayT &ray, AccessorT &acc, ListT &times)
Definition: DDA.h:290
DDA(const RayT &ray, RealT startTime)
Definition: DDA.h:47
Definition: openvdb/Exceptions.h:13
const Coord & voxel() const
Return the index coordinates of the next node or voxel intersected by the ray. If Log2Dim = 0 the ret...
Definition: DDA.h:96
Helper class that implements Hierarchical Digital Differential Analyzers and is specialized for ray i...
Definition: DDA.h:144
typename RayT::TimeSpan TimeSpanT
Definition: DDA.h:277
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:25
typename ChainT::template Get< ChildNodeLevel > NodeT
Definition: DDA.h:192
void print(std::ostream &os=std::cout) const
Print information about this DDA for debugging.
Definition: DDA.h:115
typename RayT::RealType RealType
Definition: DDA.h:37
A Digital Differential Analyzer specialized for OpenVDB grids.
Definition: DDA.h:34
void hits(RayT &ray, AccessorT &acc, ListT &times)
Definition: DDA.h:210
RealType next() const
Return the time (parameterized along the Ray) of the second (i.e. next) hit of a tree node of size 2^...
Definition: DDA.h:111
void init(const RayT &ray, RealT startTime)
Definition: DDA.h:78
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:116
static bool test(TesterT &tester)
Definition: DDA.h:169
DDA(const RayT &ray)
Definition: DDA.h:45
DDA()
uninitialized constructor
Definition: DDA.h:43
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:178