OpenVDB  4.0.1
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/ )
void hits(RayT &ray, AccessorT &acc, ListT &times)
Definition: DDA.h:236
TimeSpanT march(RayT &ray, AccessorT &acc)
Definition: DDA.h:224
void print(std::ostream &os=std::cout) const
Print information about this DDA for debugging.
Definition: DDA.h:141
A Digital Differential Analyzer specialized for OpenVDB grids.
Definition: DDA.h:60
void init(const RayT &ray)
Definition: DDA.h:102
Helper class that implements Hierarchical Digital Differential Analyzers and is specialized for ray i...
Definition: DDA.h:170
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
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
const Type & Min(const Type &a, const Type &b)
Return the minimum of two values.
Definition: Math.h:622
RayT::RealType RealType
Definition: DDA.h:63
Vec3Type Vec3T
Definition: DDA.h:66
void init(const RayT &ray, RealT startTime)
Definition: DDA.h:104
TreeT::RootNodeType::NodeChainType ChainT
Definition: DDA.h:217
size_t MinIndex(const Vec3T &v)
Return the index [0,1,2] of the smallest value in a 3D vector.
Definition: Math.h:890
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:48
boost::mpl::at< ChainT, boost::mpl::int_< NodeLevel > >::type NodeT
Definition: DDA.h:173
static bool test(TesterT &tester)
Definition: DDA.h:195
TreeT::LeafNodeType LeafT
Definition: DDA.h:302
void hits(RayT &ray, AccessorT &acc, ListT &times)
Definition: DDA.h:316
DDA(const RayT &ray, RealT startTime)
Definition: DDA.h:73
#define OPENVDB_VERSION_NAME
Definition: version.h:43
RayT::TimeSpan TimeSpanT
Definition: DDA.h:219
RayT::TimeSpan TimeSpanT
Definition: DDA.h:303
TreeT::RootNodeType::NodeChainType ChainT
Definition: DDA.h:172
DDA(const RayT &ray, RealT startTime, RealT maxTime)
Definition: DDA.h:75
Definition: Exceptions.h:39
RealType RealT
Definition: DDA.h:64
void init(const RayT &ray, RealT startTime, RealT maxTime)
Definition: DDA.h:77
RealType maxTime() const
Return the maximum time (parameterized along the Ray).
Definition: DDA.h:132
const boost::disable_if_c< VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:132
Helper class that implements Hierarchical Digital Differential Analyzers for ray intersections agains...
Definition: DDA.h:213
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
DDA()
uninitialized constructor
Definition: DDA.h:69
VolumeHDDA()
Definition: DDA.h:221
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
TimeSpanT march(RayT &ray, AccessorT &acc)
Definition: DDA.h:308
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(const RayT &ray)
Definition: DDA.h:71
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
RayT::Vec3Type Vec3Type
Definition: DDA.h:65
static bool test(TesterT &tester)
Definition: DDA.h:176
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:324