HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DDA.h
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (c) 2012-2018 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 //
29 ///////////////////////////////////////////////////////////////////////////
30 //
31 /// @file DDA.h
32 ///
33 /// @author Ken Museth
34 ///
35 /// @brief Digital Differential Analyzers specialized for VDB.
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 <openvdb/Types.h>
44 #include <iostream>// for std::ostream
45 #include <limits>// for std::numeric_limits<Type>::max()
46 #include <hboost/mpl/at.hpp>
47 
48 namespace openvdb {
50 namespace OPENVDB_VERSION_NAME {
51 namespace math {
52 
53 /// @brief A Digital Differential Analyzer specialized for OpenVDB grids
54 /// @note Conceptually similar to Bresenham's line algorithm applied
55 /// to a 3D Ray intersecting OpenVDB nodes or voxels. Log2Dim = 0
56 /// corresponds to a voxel and Log2Dim a tree node of size 2^Log2Dim.
57 ///
58 /// @note The Ray template class is expected to have the following
59 /// methods: test(time), t0(), t1(), invDir(), and operator()(time).
60 /// See the example Ray class above for their definition.
61 template<typename RayT, Index Log2Dim = 0>
62 class DDA
63 {
64 public:
65  typedef typename RayT::RealType RealType;
66  typedef RealType RealT;
67  typedef typename RayT::Vec3Type Vec3Type;
68  typedef Vec3Type Vec3T;
69 
70  /// @brief uninitialized constructor
71  DDA() {}
72 
73  DDA(const RayT& ray) { this->init(ray); }
74 
75  DDA(const RayT& ray, RealT startTime) { this->init(ray, startTime); }
76 
77  DDA(const RayT& ray, RealT startTime, RealT maxTime) { this->init(ray, startTime, maxTime); }
78 
79  inline void init(const RayT& ray, RealT startTime, RealT maxTime)
80  {
81  assert(startTime <= maxTime);
82  static const int DIM = 1 << Log2Dim;
83  mT0 = startTime;
84  mT1 = maxTime;
85  const Vec3T &pos = ray(mT0), &dir = ray.dir(), &inv = ray.invDir();
86  mVoxel = Coord::floor(pos) & (~(DIM-1));
87  for (int axis = 0; axis < 3; ++axis) {
88  if (math::isZero(dir[axis])) {//handles dir = +/- 0
89  mStep[axis] = 0;//dummy value
90  mNext[axis] = std::numeric_limits<RealT>::max();//i.e. disabled!
91  mDelta[axis] = std::numeric_limits<RealT>::max();//dummy value
92  } else if (inv[axis] > 0) {
93  mStep[axis] = DIM;
94  mNext[axis] = mT0 + (mVoxel[axis] + DIM - pos[axis]) * inv[axis];
95  mDelta[axis] = mStep[axis] * inv[axis];
96  } else {
97  mStep[axis] = -DIM;
98  mNext[axis] = mT0 + (mVoxel[axis] - pos[axis]) * inv[axis];
99  mDelta[axis] = mStep[axis] * inv[axis];
100  }
101  }
102  }
103 
104  inline void init(const RayT& ray) { this->init(ray, ray.t0(), ray.t1()); }
105 
106  inline void init(const RayT& ray, RealT startTime) { this->init(ray, startTime, ray.t1()); }
107 
108  /// @brief Increment the voxel index to next intersected voxel or node
109  /// and returns true if the step in time does not exceed maxTime.
110  inline bool step()
111  {
112  const int stepAxis = static_cast<int>(math::MinIndex(mNext));
113  mT0 = mNext[stepAxis];
114  mNext[stepAxis] += mDelta[stepAxis];
115  mVoxel[stepAxis] += mStep[stepAxis];
116  return mT0 <= mT1;
117  }
118 
119  /// @brief Return the index coordinates of the next node or voxel
120  /// intersected by the ray. If Log2Dim = 0 the return value is the
121  /// actual signed coordinate of the voxel, else it is the origin
122  /// of the corresponding VDB tree node or tile.
123  /// @note Incurs no computational overhead.
124  inline const Coord& voxel() const { return mVoxel; }
125 
126  /// @brief Return the time (parameterized along the Ray) of the
127  /// first hit of a tree node of size 2^Log2Dim.
128  /// @details This value is initialized to startTime or ray.t0()
129  /// depending on the constructor used.
130  /// @note Incurs no computational overhead.
131  inline RealType time() const { return mT0; }
132 
133  /// @brief Return the maximum time (parameterized along the Ray).
134  inline RealType maxTime() const { return mT1; }
135 
136  /// @brief Return the time (parameterized along the Ray) of the
137  /// second (i.e. next) hit of a tree node of size 2^Log2Dim.
138  /// @note Incurs a (small) computational overhead.
139  inline RealType next() const { return math::Min(mT1, mNext[0], mNext[1], mNext[2]); }
140 
141  /// @brief Print information about this DDA for debugging.
142  /// @param os a stream to which to write textual information.
143  void print(std::ostream& os = std::cout) const
144  {
145  os << "Dim=" << (1<<Log2Dim) << " time=" << mT0 << " next()="
146  << this->next() << " voxel=" << mVoxel << " next=" << mNext
147  << " delta=" << mDelta << " step=" << mStep << std::endl;
148  }
149 
150 private:
151  RealT mT0, mT1;
152  Coord mVoxel, mStep;
153  Vec3T mDelta, mNext;
154 }; // class DDA
155 
156 /// @brief Output streaming of the Ray class.
157 /// @note Primarily intended for debugging.
158 template<typename RayT, Index Log2Dim>
159 inline std::ostream& operator<<(std::ostream& os, const DDA<RayT, Log2Dim>& dda)
160 {
161  os << "Dim=" << (1<<Log2Dim) << " time=" << dda.time()
162  << " next()=" << dda.next() << " voxel=" << dda.voxel();
163  return os;
164 }
165 
166 /////////////////////////////////////////// LevelSetHDDA ////////////////////////////////////////////
167 
168 
169 /// @brief Helper class that implements Hierarchical Digital Differential Analyzers
170 /// and is specialized for ray intersections with level sets
171 template<typename TreeT, int NodeLevel>
173 {
174  typedef typename TreeT::RootNodeType::NodeChainType ChainT;
175  typedef typename hboost::mpl::at<ChainT, hboost::mpl::int_<NodeLevel> >::type NodeT;
176 
177  template <typename TesterT>
178  static bool test(TesterT& tester)
179  {
181  do {
182  if (tester.template hasNode<NodeT>(dda.voxel())) {
183  tester.setRange(dda.time(), dda.next());
184  if (LevelSetHDDA<TreeT, NodeLevel-1>::test(tester)) return true;
185  }
186  } while(dda.step());
187  return false;
188  }
189 };
190 
191 /// @brief Specialization of Hierarchical Digital Differential Analyzer
192 /// class that intersects a ray against the voxels of a level set
193 template<typename TreeT>
194 struct LevelSetHDDA<TreeT, -1>
195 {
196  template <typename TesterT>
197  static bool test(TesterT& tester)
198  {
199  math::DDA<typename TesterT::RayT, 0> dda(tester.ray());
200  tester.init(dda.time());
201  do { if (tester(dda.voxel(), dda.next())) return true; } while(dda.step());
202  return false;
203  }
204 };
205 
206 //////////////////////////////////////////// VolumeHDDA /////////////////////////////////////////////
207 
208 /// @brief Helper class that implements Hierarchical Digital Differential Analyzers
209 /// for ray intersections against a generic volume.
210 ///
211 /// @details The template argument ChildNodeLevel specifies the entry
212 /// upper node level used for the hierarchical ray-marching. The final
213 /// lowest level is always the leaf node level, i.e. not the voxel level!
214 template <typename TreeT, typename RayT, int ChildNodeLevel>
216 {
217 public:
218 
219  typedef typename TreeT::RootNodeType::NodeChainType ChainT;
220  typedef typename hboost::mpl::at<ChainT, hboost::mpl::int_<ChildNodeLevel> >::type NodeT;
221  typedef typename RayT::TimeSpan TimeSpanT;
222 
224 
225  template <typename AccessorT>
226  TimeSpanT march(RayT& ray, AccessorT &acc)
227  {
228  TimeSpanT t(-1, -1);
229  if (ray.valid()) this->march(ray, acc, t);
230  return t;
231  }
232 
233  /// ListType is a list of RayType::TimeSpan and is required to
234  /// have the two methods: clear() and push_back(). Thus, it could
235  /// be std::vector<typename RayType::TimeSpan> or
236  /// std::deque<typename RayType::TimeSpan>.
237  template <typename AccessorT, typename ListT>
238  void hits(RayT& ray, AccessorT &acc, ListT& times)
239  {
240  TimeSpanT t(-1,-1);
241  times.clear();
242  this->hits(ray, acc, times, t);
243  if (t.valid()) times.push_back(t);
244  }
245 
246 private:
247 
248  friend class VolumeHDDA<TreeT, RayT, ChildNodeLevel+1>;
249 
250  template <typename AccessorT>
251  bool march(RayT& ray, AccessorT &acc, TimeSpanT& t)
252  {
253  mDDA.init(ray);
254  do {
255  if (acc.template probeConstNode<NodeT>(mDDA.voxel()) != NULL) {//child node
256  ray.setTimes(mDDA.time(), mDDA.next());
257  if (mHDDA.march(ray, acc, t)) return true;//terminate
258  } else if (acc.isValueOn(mDDA.voxel())) {//hit an active tile
259  if (t.t0<0) t.t0 = mDDA.time();//this is the first hit so set t0
260  } else if (t.t0>=0) {//hit an inactive tile after hitting active values
261  t.t1 = mDDA.time();//set end of active ray segment
262  if (t.valid()) return true;//terminate
263  t.set(-1, -1);//reset to an empty and invalid time-span
264  }
265  } while (mDDA.step());
266  if (t.t0>=0) t.t1 = mDDA.maxTime();
267  return false;
268  }
269 
270  /// ListType is a list of RayType::TimeSpan and is required to
271  /// have the two methods: clear() and push_back(). Thus, it could
272  /// be std::vector<typename RayType::TimeSpan> or
273  /// std::deque<typename RayType::TimeSpan>.
274  template <typename AccessorT, typename ListT>
275  void hits(RayT& ray, AccessorT &acc, ListT& times, TimeSpanT& t)
276  {
277  mDDA.init(ray);
278  do {
279  if (acc.template probeConstNode<NodeT>(mDDA.voxel()) != NULL) {//child node
280  ray.setTimes(mDDA.time(), mDDA.next());
281  mHDDA.hits(ray, acc, times, t);
282  } else if (acc.isValueOn(mDDA.voxel())) {//hit an active tile
283  if (t.t0<0) t.t0 = mDDA.time();//this is the first hit so set t0
284  } else if (t.t0>=0) {//hit an inactive tile after hitting active values
285  t.t1 = mDDA.time();//set end of active ray segment
286  if (t.valid()) times.push_back(t);
287  t.set(-1,-1);//reset to an empty and invalid time-span
288  }
289  } while (mDDA.step());
290  if (t.t0>=0) t.t1 = mDDA.maxTime();
291  }
292 
293  math::DDA<RayT, NodeT::TOTAL> mDDA;
294  VolumeHDDA<TreeT, RayT, ChildNodeLevel-1> mHDDA;
295 };
296 
297 /// @brief Specialization of Hierarchical Digital Differential Analyzer
298 /// class that intersects against the leafs or tiles of a generic volume.
299 template <typename TreeT, typename RayT>
300 class VolumeHDDA<TreeT, RayT, 0>
301 {
302 public:
303 
304  typedef typename TreeT::LeafNodeType LeafT;
305  typedef typename RayT::TimeSpan TimeSpanT;
306 
308 
309  template <typename AccessorT>
310  TimeSpanT march(RayT& ray, AccessorT &acc)
311  {
312  TimeSpanT t(-1, -1);
313  if (ray.valid()) this->march(ray, acc, t);
314  return t;
315  }
316 
317  template <typename AccessorT, typename ListT>
318  void hits(RayT& ray, AccessorT &acc, ListT& times)
319  {
320  TimeSpanT t(-1,-1);
321  times.clear();
322  this->hits(ray, acc, times, t);
323  if (t.valid()) times.push_back(t);
324  }
325 
326 private:
327 
328  friend class VolumeHDDA<TreeT, RayT, 1>;
329 
330  template <typename AccessorT>
331  bool march(RayT& ray, AccessorT &acc, TimeSpanT& t)
332  {
333  mDDA.init(ray);
334  do {
335  if (acc.template probeConstNode<LeafT>(mDDA.voxel()) ||
336  acc.isValueOn(mDDA.voxel())) {//hit a leaf or an active tile
337  if (t.t0<0) t.t0 = mDDA.time();//this is the first hit
338  } else if (t.t0>=0) {//hit an inactive tile after hitting active values
339  t.t1 = mDDA.time();//set end of active ray segment
340  if (t.valid()) return true;//terminate
341  t.set(-1, -1);//reset to an empty and invalid time-span
342  }
343  } while (mDDA.step());
344  if (t.t0>=0) t.t1 = mDDA.maxTime();
345  return false;
346  }
347 
348  template <typename AccessorT, typename ListT>
349  void hits(RayT& ray, AccessorT &acc, ListT& times, TimeSpanT& t)
350  {
351  mDDA.init(ray);
352  do {
353  if (acc.template probeConstNode<LeafT>(mDDA.voxel()) ||
354  acc.isValueOn(mDDA.voxel())) {//hit a leaf or an active tile
355  if (t.t0<0) t.t0 = mDDA.time();//this is the first hit
356  } else if (t.t0>=0) {//hit an inactive tile after hitting active values
357  t.t1 = mDDA.time();//set end of active ray segment
358  if (t.valid()) times.push_back(t);
359  t.set(-1, -1);//reset to an empty and invalid time-span
360  }
361  } while (mDDA.step());
362  if (t.t0>=0) t.t1 = mDDA.maxTime();
363  }
364  math::DDA<RayT, LeafT::TOTAL> mDDA;
365 };
366 
367 } // namespace math
368 } // namespace OPENVDB_VERSION_NAME
369 } // namespace openvdb
370 
371 #endif // OPENVDB_MATH_DDA_HAS_BEEN_INCLUDED
372 
373 // Copyright (c) 2012-2018 DreamWorks Animation LLC
374 // All rights reserved. This software is distributed under the
375 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
void hits(RayT &ray, AccessorT &acc, ListT &times)
Definition: DDA.h:238
void init(const RayT &ray)
Definition: DDA.h:104
TimeSpanT march(RayT &ray, AccessorT &acc)
Definition: DDA.h:226
DDA()
uninitialized constructor
Definition: DDA.h:71
static bool test(TesterT &tester)
Definition: DDA.h:178
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:139
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:189
A Digital Differential Analyzer specialized for OpenVDB grids.
Definition: DDA.h:62
void init(const RayT &ray, RealT startTime, RealT maxTime)
Definition: DDA.h:79
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:51
TreeT::RootNodeType::NodeChainType ChainT
Definition: DDA.h:219
hboost::mpl::at< ChainT, hboost::mpl::int_< NodeLevel > >::type NodeT
Definition: DDA.h:175
size_t MinIndex(const Vec3T &v)
Return the index [0,1,2] of the smallest value in a 3D vector.
Definition: Math.h:890
hboost::mpl::at< ChainT, hboost::mpl::int_< ChildNodeLevel > >::type NodeT
Definition: DDA.h:220
TreeT::RootNodeType::NodeChainType ChainT
Definition: DDA.h:174
void print(std::ostream &os=std::cout) const
Print information about this DDA for debugging.
Definition: DDA.h:143
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...
DDA(const RayT &ray, RealT startTime)
Definition: DDA.h:75
bool step()
Increment the voxel index to next intersected voxel or node and returns true if the step in time does...
Definition: DDA.h:110
DDA(const RayT &ray, RealT startTime, RealT maxTime)
Definition: DDA.h:77
TimeSpanT march(RayT &ray, AccessorT &acc)
Definition: DDA.h:310
void init(const RayT &ray, RealT startTime)
Definition: DDA.h:106
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:131
int floor(T x)
Definition: ImathFun.h:150
Helper class that implements Hierarchical Digital Differential Analyzers and is specialized for ray i...
Definition: DDA.h:172
RealType maxTime() const
Return the maximum time (parameterized along the Ray).
Definition: DDA.h:134
void hits(RayT &ray, AccessorT &acc, ListT &times)
Definition: DDA.h:318
const Type & Min(const Type &a, const Type &b)
Return the minimum of two values.
Definition: Math.h:610
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:107
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:124
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:135
bool isZero(const Type &x)
Return true if x is exactly equal to zero.
Definition: Math.h:308
Helper class that implements Hierarchical Digital Differential Analyzers for ray intersections agains...
Definition: DDA.h:215