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