37 #ifndef OPENVDB_MATH_DDA_HAS_BEEN_INCLUDED
38 #define OPENVDB_MATH_DDA_HAS_BEEN_INCLUDED
59 template<
typename RayT, Index Log2Dim = 0>
71 DDA(
const RayT& ray) { this->init(ray); }
73 DDA(
const RayT& ray, RealT startTime) { this->init(ray, startTime); }
75 DDA(
const RayT& ray, RealT startTime, RealT maxTime) { this->init(ray, startTime, maxTime); }
77 inline void init(
const RayT& ray, RealT startTime, RealT maxTime)
79 assert(startTime <= maxTime);
80 static const int DIM = 1 << Log2Dim;
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) {
90 }
else if (inv[axis] > 0) {
92 mNext[axis] = mT0 + (mVoxel[axis] + DIM - pos[axis]) * inv[axis];
93 mDelta[axis] = mStep[axis] * inv[axis];
96 mNext[axis] = mT0 + (mVoxel[axis] - pos[axis]) * inv[axis];
97 mDelta[axis] = mStep[axis] * inv[axis];
102 inline void init(
const RayT& ray) { this->
init(ray, ray.t0(), ray.t1()); }
104 inline void init(
const RayT& ray, RealT startTime) { this->
init(ray, startTime, ray.t1()); }
111 mT0 = mNext[stepAxis];
112 mNext[stepAxis] += mDelta[stepAxis];
113 mVoxel[stepAxis] += mStep[stepAxis];
129 inline RealType
time()
const {
return mT0; }
132 inline RealType
maxTime()
const {
return mT1; }
137 inline RealType
next()
const {
return math::Min(mT1, mNext[0], mNext[1], mNext[2]); }
141 void print(std::ostream& os = std::cout)
const
143 os <<
"Dim=" << (1<<Log2Dim) <<
" time=" << mT0 <<
" next()="
144 << this->next() <<
" voxel=" << mVoxel <<
" next=" << mNext
145 <<
" delta=" << mDelta <<
" step=" << mStep << std::endl;
156 template<
typename RayT, Index Log2Dim>
157 inline std::ostream& operator<<(std::ostream& os, const DDA<RayT, Log2Dim>& dda)
159 os <<
"Dim=" << (1<<Log2Dim) <<
" time=" << dda.time()
160 <<
" next()=" << dda.next() <<
" voxel=" << dda.voxel();
169 template<
typename TreeT,
int NodeLevel>
172 typedef typename TreeT::RootNodeType::NodeChainType
ChainT;
173 typedef typename boost::mpl::at<ChainT, boost::mpl::int_<NodeLevel> >::type
NodeT;
175 template <
typename TesterT>
176 static bool test(TesterT& tester)
180 if (tester.template hasNode<NodeT>(dda.voxel())) {
181 tester.setRange(dda.time(), dda.next());
191 template<
typename TreeT>
194 template <
typename TesterT>
195 static bool test(TesterT& tester)
198 tester.
init(dda.time());
199 do {
if (tester(dda.voxel(), dda.next()))
return true; }
while(dda.step());
212 template <
typename TreeT,
typename RayT,
int ChildNodeLevel>
217 typedef typename TreeT::RootNodeType::NodeChainType
ChainT;
218 typedef typename boost::mpl::at<ChainT, boost::mpl::int_<ChildNodeLevel> >::type
NodeT;
224 TimeSpanT
march(RayT& ray, AccessorT &acc)
227 if (ray.valid()) this->march(ray, acc, t);
235 template <
typename ListType>
236 void hits(RayT& ray, AccessorT &acc, ListType& times)
240 this->hits(ray, acc, times, t);
241 if (t.valid()) times.push_back(t);
248 bool march(RayT& ray, AccessorT &acc, TimeSpanT& t)
252 if (acc.template probeConstNode<NodeT>(mDDA.voxel()) != NULL) {
253 ray.setTimes(mDDA.time(), mDDA.next());
254 if (mHDDA.march(ray, acc, t))
return true;
255 }
else if (acc.
isValueOn(mDDA.voxel())) {
256 if (t.t0<0) t.t0 = mDDA.time();
257 }
else if (t.t0>=0) {
259 if (t.valid())
return true;
262 }
while (mDDA.step());
263 if (t.t0>=0) t.t1 = mDDA.maxTime();
271 template <
typename ListType>
272 void hits(RayT& ray, AccessorT &acc, ListType& times, TimeSpanT& t)
276 if (acc.template probeConstNode<NodeT>(mDDA.voxel()) != NULL) {
277 ray.setTimes(mDDA.time(), mDDA.next());
278 mHDDA.
hits(ray, acc, times, t);
279 }
else if (acc.isValueOn(mDDA.voxel())) {
280 if (t.t0<0) t.t0 = mDDA.time();
281 }
else if (t.t0>=0) {
283 if (t.valid()) times.push_back(t);
286 }
while (mDDA.step());
287 if (t.t0>=0) t.t1 = mDDA.maxTime();
290 math::DDA<RayT, NodeT::TOTAL> mDDA;
291 VolumeHDDA<TreeT, RayT, ChildNodeLevel-1> mHDDA;
296 template <
typename TreeT,
typename RayT>
301 typedef typename TreeT::LeafNodeType
LeafT;
307 TimeSpanT
march(RayT& ray, AccessorT &acc)
310 if (ray.valid()) this->march(ray, acc, t);
314 template <
typename ListType>
315 void hits(RayT& ray, AccessorT &acc, ListType& times)
319 this->hits(ray, acc, times, t);
320 if (t.valid()) times.push_back(t);
327 bool march(RayT& ray, AccessorT &acc, TimeSpanT& t)
331 if (acc.template probeConstNode<LeafT>(mDDA.voxel()) ||
333 if (t.t0<0) t.t0 = mDDA.time();
334 }
else if (t.t0>=0) {
336 if (t.valid())
return true;
339 }
while (mDDA.step());
340 if (t.t0>=0) t.t1 = mDDA.maxTime();
344 template <
typename ListType>
345 void hits(RayT& ray, AccessorT &acc, ListType& times, TimeSpanT& t)
349 if (acc.template probeConstNode<LeafT>(mDDA.voxel()) ||
350 acc.isValueOn(mDDA.voxel())) {
351 if (t.t0<0) t.t0 = mDDA.time();
352 }
else if (t.t0>=0) {
354 if (t.valid()) times.push_back(t);
357 }
while (mDDA.step());
358 if (t.t0>=0) t.t1 = mDDA.maxTime();
360 math::DDA<RayT, LeafT::TOTAL> mDDA;
367 #endif // OPENVDB_MATH_DDA_HAS_BEEN_INCLUDED
void hits(RayT &ray, AccessorT &acc, ListType ×)
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
VolumeHDDA()
Definition: DDA.h:305
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 ×)
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