OpenVDB  3.0.0
DDA.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2014 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;
220  typedef typename RayT::TimeSpan TimeSpanT;
221 
223 
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 ListType>
236  void hits(RayT& ray, AccessorT &acc, ListType& 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  bool march(RayT& ray, AccessorT &acc, TimeSpanT& t)
249  {
250  mDDA.init(ray);
251  do {
252  if (acc.template probeConstNode<NodeT>(mDDA.voxel()) != NULL) {//child node
253  ray.setTimes(mDDA.time(), mDDA.next());
254  if (mHDDA.march(ray, acc, t)) return true;//terminate
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()) return true;//terminate
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  return false;
265  }
266 
271  template <typename ListType>
272  void hits(RayT& ray, AccessorT &acc, ListType& times, TimeSpanT& t)
273  {
274  mDDA.init(ray);
275  do {
276  if (acc.template probeConstNode<NodeT>(mDDA.voxel()) != NULL) {//child node
277  ray.setTimes(mDDA.time(), mDDA.next());
278  mHDDA.hits(ray, acc, times, t);
279  } else if (acc.isValueOn(mDDA.voxel())) {//hit an active tile
280  if (t.t0<0) t.t0 = mDDA.time();//this is the first hit so set t0
281  } else if (t.t0>=0) {//hit an inactive tile after hitting active values
282  t.t1 = mDDA.time();//set end of active ray segment
283  if (t.valid()) times.push_back(t);
284  t.set(-1,-1);//reset to an empty and invalid time-span
285  }
286  } while (mDDA.step());
287  if (t.t0>=0) t.t1 = mDDA.maxTime();
288  }
289 
290  math::DDA<RayT, NodeT::TOTAL> mDDA;
291  VolumeHDDA<TreeT, RayT, ChildNodeLevel-1> mHDDA;
292 };
293 
296 template <typename TreeT, typename RayT>
297 class VolumeHDDA<TreeT, RayT, 0>
298 {
299 public:
300 
301  typedef typename TreeT::LeafNodeType LeafT;
303  typedef typename RayT::TimeSpan TimeSpanT;
304 
306 
307  TimeSpanT march(RayT& ray, AccessorT &acc)
308  {
309  TimeSpanT t(-1, -1);
310  if (ray.valid()) this->march(ray, acc, t);
311  return t;
312  }
313 
314  template <typename ListType>
315  void hits(RayT& ray, AccessorT &acc, ListType& times)
316  {
317  TimeSpanT t(-1,-1);
318  times.clear();
319  this->hits(ray, acc, times, t);
320  if (t.valid()) times.push_back(t);
321  }
322 
323 private:
324 
325  friend class VolumeHDDA<TreeT, RayT, 1>;
326 
327  bool march(RayT& ray, AccessorT &acc, TimeSpanT& t)
328  {
329  mDDA.init(ray);
330  do {
331  if (acc.template probeConstNode<LeafT>(mDDA.voxel()) ||
332  acc.isValueOn(mDDA.voxel())) {//hit a leaf or an active tile
333  if (t.t0<0) t.t0 = mDDA.time();//this is the first hit
334  } else if (t.t0>=0) {//hit an inactive tile after hitting active values
335  t.t1 = mDDA.time();//set end of active ray segment
336  if (t.valid()) return true;//terminate
337  t.set(-1, -1);//reset to an empty and invalid time-span
338  }
339  } while (mDDA.step());
340  if (t.t0>=0) t.t1 = mDDA.maxTime();
341  return false;
342  }
343 
344  template <typename ListType>
345  void hits(RayT& ray, AccessorT &acc, ListType& times, TimeSpanT& t)
346  {
347  mDDA.init(ray);
348  do {
349  if (acc.template probeConstNode<LeafT>(mDDA.voxel()) ||
350  acc.isValueOn(mDDA.voxel())) {//hit a leaf or an active tile
351  if (t.t0<0) t.t0 = mDDA.time();//this is the first hit
352  } else if (t.t0>=0) {//hit an inactive tile after hitting active values
353  t.t1 = mDDA.time();//set end of active ray segment
354  if (t.valid()) times.push_back(t);
355  t.set(-1, -1);//reset to an empty and invalid time-span
356  }
357  } while (mDDA.step());
358  if (t.t0>=0) t.t1 = mDDA.maxTime();
359  }
360  math::DDA<RayT, LeafT::TOTAL> mDDA;
361 };
362 
363 } // namespace math
364 } // namespace OPENVDB_VERSION_NAME
365 } // namespace openvdb
366 
367 #endif // OPENVDB_MATH_DDA_HAS_BEEN_INCLUDED
368 
369 // Copyright (c) 2012-2014 DreamWorks Animation LLC
370 // All rights reserved. This software is distributed under the
371 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
void hits(RayT &ray, AccessorT &acc, ListType &times)
Definition: DDA.h:236
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
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
tree::ValueAccessor< const TreeT > AccessorT
Definition: DDA.h:219
const Type & Min(const Type &a, const Type &b)
Return the minimum of two values.
Definition: Math.h:606
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:47
boost::mpl::at< ChainT, boost::mpl::int_< NodeLevel > >::type NodeT
Definition: DDA.h:173
tree::ValueAccessor< const TreeT > AccessorT
Definition: DDA.h:302
static bool test(TesterT &tester)
Definition: DDA.h:195
TreeT::LeafNodeType LeafT
Definition: DDA.h:301
DDA(const RayT &ray, RealT startTime)
Definition: DDA.h:73
#define OPENVDB_VERSION_NAME
Definition: version.h:43
RayT::TimeSpan TimeSpanT
Definition: DDA.h:220
RayT::TimeSpan TimeSpanT
Definition: DDA.h:303
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:217
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
size_t MinIndex(const Vec3T &v)
Return the index [0,1,2] of the smallest value in a 3D vector.
Definition: Math.h:856
TimeSpanT march(RayT &ray, AccessorT &acc)
Definition: DDA.h:224
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
void hits(RayT &ray, AccessorT &acc, ListType &times)
Definition: DDA.h:315
VolumeHDDA()
Definition: DDA.h:222
OPENVDB_API Hermite max(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
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
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
bool isZero(const Type &x)
Return true if x is exactly equal to zero.
Definition: Math.h:314
TimeSpanT march(RayT &ray, AccessorT &acc)
Definition: DDA.h:307
boost::mpl::at< ChainT, boost::mpl::int_< ChildNodeLevel > >::type NodeT
Definition: DDA.h:218