OpenVDB  5.0.0
DDA.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2017 DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
30 //
36 
37 #ifndef OPENVDB_MATH_DDA_HAS_BEEN_INCLUDED
38 #define OPENVDB_MATH_DDA_HAS_BEEN_INCLUDED
39 
40 #include "Coord.h"
41 #include "Math.h"
42 #include "Vec3.h"
43 #include <iostream>// for std::ostream
44 #include <limits>// for std::numeric_limits<Type>::max()
45 
46 namespace openvdb {
48 namespace OPENVDB_VERSION_NAME {
49 namespace math {
50 
59 template<typename RayT, Index Log2Dim = 0>
60 class DDA
61 {
62 public:
63  typedef typename RayT::RealType RealType;
64  typedef RealType RealT;
65  typedef typename RayT::Vec3Type Vec3Type;
66  typedef Vec3Type Vec3T;
67 
69  DDA() {}
70 
71  DDA(const RayT& ray) { this->init(ray); }
72 
73  DDA(const RayT& ray, RealT startTime) { this->init(ray, startTime); }
74 
75  DDA(const RayT& ray, RealT startTime, RealT maxTime) { this->init(ray, startTime, maxTime); }
76 
77  inline void init(const RayT& ray, RealT startTime, RealT maxTime)
78  {
79  assert(startTime <= maxTime);
80  static const int DIM = 1 << Log2Dim;
81  mT0 = startTime;
82  mT1 = maxTime;
83  const Vec3T &pos = ray(mT0), &dir = ray.dir(), &inv = ray.invDir();
84  mVoxel = Coord::floor(pos) & (~(DIM-1));
85  for (int axis = 0; axis < 3; ++axis) {
86  if (math::isZero(dir[axis])) {//handles dir = +/- 0
87  mStep[axis] = 0;//dummy value
88  mNext[axis] = std::numeric_limits<RealT>::max();//i.e. disabled!
89  mDelta[axis] = std::numeric_limits<RealT>::max();//dummy value
90  } else if (inv[axis] > 0) {
91  mStep[axis] = DIM;
92  mNext[axis] = mT0 + (mVoxel[axis] + DIM - pos[axis]) * inv[axis];
93  mDelta[axis] = mStep[axis] * inv[axis];
94  } else {
95  mStep[axis] = -DIM;
96  mNext[axis] = mT0 + (mVoxel[axis] - pos[axis]) * inv[axis];
97  mDelta[axis] = mStep[axis] * inv[axis];
98  }
99  }
100  }
101 
102  inline void init(const RayT& ray) { this->init(ray, ray.t0(), ray.t1()); }
103 
104  inline void init(const RayT& ray, RealT startTime) { this->init(ray, startTime, ray.t1()); }
105 
108  inline bool step()
109  {
110  const int stepAxis = static_cast<int>(math::MinIndex(mNext));
111  mT0 = mNext[stepAxis];
112  mNext[stepAxis] += mDelta[stepAxis];
113  mVoxel[stepAxis] += mStep[stepAxis];
114  return mT0 <= mT1;
115  }
116 
122  inline const Coord& voxel() const { return mVoxel; }
123 
129  inline RealType time() const { return mT0; }
130 
132  inline RealType maxTime() const { return mT1; }
133 
137  inline RealType next() const { return math::Min(mT1, mNext[0], mNext[1], mNext[2]); }
138 
141  void print(std::ostream& os = std::cout) const
142  {
143  os << "Dim=" << (1<<Log2Dim) << " time=" << mT0 << " next()="
144  << this->next() << " voxel=" << mVoxel << " next=" << mNext
145  << " delta=" << mDelta << " step=" << mStep << std::endl;
146  }
147 
148 private:
149  RealT mT0, mT1;
150  Coord mVoxel, mStep;
151  Vec3T mDelta, mNext;
152 }; // class DDA
153 
156 template<typename RayT, Index Log2Dim>
157 inline std::ostream& operator<<(std::ostream& os, const DDA<RayT, Log2Dim>& dda)
158 {
159  os << "Dim=" << (1<<Log2Dim) << " time=" << dda.time()
160  << " next()=" << dda.next() << " voxel=" << dda.voxel();
161  return os;
162 }
163 
165 
166 
169 template<typename TreeT, int NodeLevel>
171 {
172  typedef typename TreeT::RootNodeType::NodeChainType ChainT;
173  typedef typename boost::mpl::at<ChainT, boost::mpl::int_<NodeLevel> >::type NodeT;
174 
175  template <typename TesterT>
176  static bool test(TesterT& tester)
177  {
179  do {
180  if (tester.template hasNode<NodeT>(dda.voxel())) {
181  tester.setRange(dda.time(), dda.next());
182  if (LevelSetHDDA<TreeT, NodeLevel-1>::test(tester)) return true;
183  }
184  } while(dda.step());
185  return false;
186  }
187 };
188 
191 template<typename TreeT>
192 struct LevelSetHDDA<TreeT, -1>
193 {
194  template <typename TesterT>
195  static bool test(TesterT& tester)
196  {
197  math::DDA<typename TesterT::RayT, 0> dda(tester.ray());
198  tester.init(dda.time());
199  do { if (tester(dda.voxel(), dda.next())) return true; } while(dda.step());
200  return false;
201  }
202 };
203 
205 
212 template <typename TreeT, typename RayT, int ChildNodeLevel>
214 {
215 public:
216 
217  typedef typename TreeT::RootNodeType::NodeChainType ChainT;
218  typedef typename boost::mpl::at<ChainT, boost::mpl::int_<ChildNodeLevel> >::type NodeT;
219  typedef typename RayT::TimeSpan TimeSpanT;
220 
222 
223  template <typename AccessorT>
224  TimeSpanT march(RayT& ray, AccessorT &acc)
225  {
226  TimeSpanT t(-1, -1);
227  if (ray.valid()) this->march(ray, acc, t);
228  return t;
229  }
230 
235  template <typename AccessorT, typename ListT>
236  void hits(RayT& ray, AccessorT &acc, ListT& times)
237  {
238  TimeSpanT t(-1,-1);
239  times.clear();
240  this->hits(ray, acc, times, t);
241  if (t.valid()) times.push_back(t);
242  }
243 
244 private:
245 
246  friend class VolumeHDDA<TreeT, RayT, ChildNodeLevel+1>;
247 
248  template <typename AccessorT>
249  bool march(RayT& ray, AccessorT &acc, TimeSpanT& t)
250  {
251  mDDA.init(ray);
252  do {
253  if (acc.template probeConstNode<NodeT>(mDDA.voxel()) != NULL) {//child node
254  ray.setTimes(mDDA.time(), mDDA.next());
255  if (mHDDA.march(ray, acc, t)) return true;//terminate
256  } else if (acc.isValueOn(mDDA.voxel())) {//hit an active tile
257  if (t.t0<0) t.t0 = mDDA.time();//this is the first hit so set t0
258  } else if (t.t0>=0) {//hit an inactive tile after hitting active values
259  t.t1 = mDDA.time();//set end of active ray segment
260  if (t.valid()) return true;//terminate
261  t.set(-1, -1);//reset to an empty and invalid time-span
262  }
263  } while (mDDA.step());
264  if (t.t0>=0) t.t1 = mDDA.maxTime();
265  return false;
266  }
267 
272  template <typename AccessorT, typename ListT>
273  void hits(RayT& ray, AccessorT &acc, ListT& times, TimeSpanT& t)
274  {
275  mDDA.init(ray);
276  do {
277  if (acc.template probeConstNode<NodeT>(mDDA.voxel()) != NULL) {//child node
278  ray.setTimes(mDDA.time(), mDDA.next());
279  mHDDA.hits(ray, acc, times, t);
280  } else if (acc.isValueOn(mDDA.voxel())) {//hit an active tile
281  if (t.t0<0) t.t0 = mDDA.time();//this is the first hit so set t0
282  } else if (t.t0>=0) {//hit an inactive tile after hitting active values
283  t.t1 = mDDA.time();//set end of active ray segment
284  if (t.valid()) times.push_back(t);
285  t.set(-1,-1);//reset to an empty and invalid time-span
286  }
287  } while (mDDA.step());
288  if (t.t0>=0) t.t1 = mDDA.maxTime();
289  }
290 
292  VolumeHDDA<TreeT, RayT, ChildNodeLevel-1> mHDDA;
293 };
294 
297 template <typename TreeT, typename RayT>
298 class VolumeHDDA<TreeT, RayT, 0>
299 {
300 public:
301 
302  typedef typename TreeT::LeafNodeType LeafT;
303  typedef typename RayT::TimeSpan TimeSpanT;
304 
306 
307  template <typename AccessorT>
308  TimeSpanT march(RayT& ray, AccessorT &acc)
309  {
310  TimeSpanT t(-1, -1);
311  if (ray.valid()) this->march(ray, acc, t);
312  return t;
313  }
314 
315  template <typename AccessorT, typename ListT>
316  void hits(RayT& ray, AccessorT &acc, ListT& times)
317  {
318  TimeSpanT t(-1,-1);
319  times.clear();
320  this->hits(ray, acc, times, t);
321  if (t.valid()) times.push_back(t);
322  }
323 
324 private:
325 
326  friend class VolumeHDDA<TreeT, RayT, 1>;
327 
328  template <typename AccessorT>
329  bool march(RayT& ray, AccessorT &acc, TimeSpanT& t)
330  {
331  mDDA.init(ray);
332  do {
333  if (acc.template probeConstNode<LeafT>(mDDA.voxel()) ||
334  acc.isValueOn(mDDA.voxel())) {//hit a leaf or an active tile
335  if (t.t0<0) t.t0 = mDDA.time();//this is the first hit
336  } else if (t.t0>=0) {//hit an inactive tile after hitting active values
337  t.t1 = mDDA.time();//set end of active ray segment
338  if (t.valid()) return true;//terminate
339  t.set(-1, -1);//reset to an empty and invalid time-span
340  }
341  } while (mDDA.step());
342  if (t.t0>=0) t.t1 = mDDA.maxTime();
343  return false;
344  }
345 
346  template <typename AccessorT, typename ListT>
347  void hits(RayT& ray, AccessorT &acc, ListT& times, TimeSpanT& t)
348  {
349  mDDA.init(ray);
350  do {
351  if (acc.template probeConstNode<LeafT>(mDDA.voxel()) ||
352  acc.isValueOn(mDDA.voxel())) {//hit a leaf or an active tile
353  if (t.t0<0) t.t0 = mDDA.time();//this is the first hit
354  } else if (t.t0>=0) {//hit an inactive tile after hitting active values
355  t.t1 = mDDA.time();//set end of active ray segment
356  if (t.valid()) times.push_back(t);
357  t.set(-1, -1);//reset to an empty and invalid time-span
358  }
359  } while (mDDA.step());
360  if (t.t0>=0) t.t1 = mDDA.maxTime();
361  }
363 };
364 
365 } // namespace math
366 } // namespace OPENVDB_VERSION_NAME
367 } // namespace openvdb
368 
369 #endif // OPENVDB_MATH_DDA_HAS_BEEN_INCLUDED
370 
371 // Copyright (c) 2012-2017 DreamWorks Animation LLC
372 // All rights reserved. This software is distributed under the
373 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
Helper class that implements Hierarchical Digital Differential Analyzers and is specialized for ray i...
Definition: DDA.h:170
static bool test(TesterT &tester)
Definition: DDA.h:195
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:137
RayT::TimeSpan TimeSpanT
Definition: DDA.h:303
Helper class that implements Hierarchical Digital Differential Analyzers for ray intersections agains...
Definition: DDA.h:213
RayT::TimeSpan TimeSpanT
Definition: DDA.h:219
static bool test(TesterT &tester)
Definition: DDA.h:176
TreeT::RootNodeType::NodeChainType ChainT
Definition: DDA.h:172
RealType RealT
Definition: DDA.h:64
RayT::Vec3Type Vec3Type
Definition: DDA.h:65
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:133
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
static Coord floor(const Vec3< T > &xyz)
Return the largest integer coordinates that are not greater than xyz (node centered conversion)...
Definition: Coord.h:83
void hits(RayT &ray, AccessorT &acc, ListT &times)
Definition: DDA.h:236
size_t MinIndex(const Vec3T &v)
Return the index [0,1,2] of the smallest value in a 3D vector.
Definition: Math.h:886
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:122
DDA()
uninitialized constructor
Definition: DDA.h:69
void print(std::ostream &os=std::cout) const
Print information about this DDA for debugging.
Definition: DDA.h:141
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:51
TreeT::RootNodeType::NodeChainType ChainT
Definition: DDA.h:217
VolumeHDDA()
Definition: DDA.h:221
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:129
void init(const RayT &ray, RealT startTime, RealT maxTime)
Definition: DDA.h:77
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:136
void hits(RayT &ray, AccessorT &acc, ListT &times)
Definition: DDA.h:316
RealType maxTime() const
Return the maximum time (parameterized along the Ray).
Definition: DDA.h:132
Definition: Exceptions.h:39
TreeT::LeafNodeType LeafT
Definition: DDA.h:302
TimeSpanT march(RayT &ray, AccessorT &acc)
Definition: DDA.h:308
boost::mpl::at< ChainT, boost::mpl::int_< ChildNodeLevel > >::type NodeT
Definition: DDA.h:218
bool isZero(const Type &x)
Return true if x is exactly equal to zero.
Definition: Math.h:308
A Digital Differential Analyzer specialized for OpenVDB grids.
Definition: DDA.h:60
const Type & Min(const Type &a, const Type &b)
Return the minimum of two values.
Definition: Math.h:606
void init(const RayT &ray, RealT startTime)
Definition: DDA.h:104
bool step()
Increment the voxel index to next intersected voxel or node and returns true if the step in time does...
Definition: DDA.h:108
DDA(const RayT &ray)
Definition: DDA.h:71
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:188
TimeSpanT march(RayT &ray, AccessorT &acc)
Definition: DDA.h:224
Vec3Type Vec3T
Definition: DDA.h:66
void init(const RayT &ray)
Definition: DDA.h:102
DDA(const RayT &ray, RealT startTime)
Definition: DDA.h:73
DDA(const RayT &ray, RealT startTime, RealT maxTime)
Definition: DDA.h:75
boost::mpl::at< ChainT, boost::mpl::int_< NodeLevel > >::type NodeT
Definition: DDA.h:173
RayT::RealType RealType
Definition: DDA.h:63