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); }
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 (
size_t 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];
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());
208 template <
typename TreeT,
typename RayT,
int ChildNodeLevel>
213 typedef typename TreeT::RootNodeType::NodeChainType
ChainT;
214 typedef typename boost::mpl::at<ChainT, boost::mpl::int_<ChildNodeLevel> >::type
NodeT;
223 if (ray.valid()) this->march(ray, acc, t);
231 this->hits(ray, acc, times, t);
232 if (t.valid()) times.push_back(t);
243 if (acc.template probeConstNode<NodeT>(mDDA.voxel()) != NULL) {
244 ray.setTimes(mDDA.time(), mDDA.next());
245 if (mHDDA.march(ray, acc, t))
return true;
246 }
else if (acc.
isValueOn(mDDA.voxel())) {
247 if (t.t0<0) t.t0 = mDDA.time();
248 }
else if (t.t0>=0) {
250 if (t.valid())
return true;
253 }
while (mDDA.step());
254 if (t.t0>=0) t.t1 = mDDA.maxTime();
258 void hits(RayT& ray, AccessorT &acc, std::vector<TimeSpanT>& times, TimeSpanT& t)
262 if (acc.template probeConstNode<NodeT>(mDDA.voxel()) != NULL) {
263 ray.setTimes(mDDA.time(), mDDA.next());
264 mHDDA.
hits(ray, acc, times, t);
265 }
else if (acc.isValueOn(mDDA.voxel())) {
266 if (t.t0<0) t.t0 = mDDA.time();
267 }
else if (t.t0>=0) {
269 if (t.valid()) times.push_back(t);
272 }
while (mDDA.step());
273 if (t.t0>=0) t.t1 = mDDA.maxTime();
276 math::DDA<RayT, NodeT::TOTAL> mDDA;
277 VolumeHDDA<TreeT, RayT, ChildNodeLevel-1> mHDDA;
282 template <
typename TreeT,
typename RayT>
287 typedef typename TreeT::LeafNodeType
LeafT;
296 if (ray.valid()) this->march(ray, acc, t);
304 this->hits(ray, acc, times, t);
305 if (t.valid()) times.push_back(t);
316 if (acc.template probeConstNode<LeafT>(mDDA.voxel()) ||
318 if (t.t0<0) t.t0 = mDDA.time();
319 }
else if (t.t0>=0) {
321 if (t.valid())
return true;
324 }
while (mDDA.step());
325 if (t.t0>=0) t.t1 = mDDA.maxTime();
329 void hits(RayT& ray, AccessorT &acc, std::vector<TimeSpanT>& times, TimeSpanT& t)
333 if (acc.template probeConstNode<LeafT>(mDDA.voxel()) ||
334 acc.isValueOn(mDDA.voxel())) {
335 if (t.t0<0) t.t0 = mDDA.time();
336 }
else if (t.t0>=0) {
338 if (t.valid()) times.push_back(t);
341 }
while (mDDA.step());
342 if (t.t0>=0) t.t1 = mDDA.maxTime();
344 math::DDA<RayT, LeafT::TOTAL> mDDA;
351 #endif // OPENVDB_MATH_DDA_HAS_BEEN_INCLUDED
static bool test(TesterT &tester)
Definition: DDA.h:195
void hits(RayT &ray, AccessorT &acc, std::vector< TimeSpanT > ×)
Definition: DDA.h:227
void init(const RayT &ray)
Definition: DDA.h:102
TreeT::RootNodeType::NodeChainType ChainT
Definition: DDA.h:172
void print(std::ostream &os=std::cout) const
Print information about this DDA for debugging.
Definition: DDA.h:141
tree::ValueAccessor< const TreeT > AccessorT
Definition: DDA.h:288
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
Vec3Type Vec3T
Definition: DDA.h:66
void init(const RayT &ray, RealT startTime)
Definition: DDA.h:104
TimeSpanT march(RayT &ray, AccessorT &acc)
Definition: DDA.h:220
RayT::RealType RealType
Definition: DDA.h:63
boost::mpl::at< ChainT, boost::mpl::int_< NodeLevel > >::type NodeT
Definition: DDA.h:173
void hits(RayT &ray, AccessorT &acc, std::vector< TimeSpanT > ×)
Definition: DDA.h:300
A Digital Differential Analyzer specialized for OpenVDB grids.
Definition: DDA.h:60
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
boost::mpl::at< ChainT, boost::mpl::int_< ChildNodeLevel > >::type NodeT
Definition: DDA.h:214
VolumeHDDA()
Definition: DDA.h:218
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:176
#define OPENVDB_VERSION_NAME
Definition: version.h:45
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:47
DDA(const RayT &ray, RealT startTime)
Definition: DDA.h:73
OPENVDB_API Hermite max(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
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
size_t MinIndex(const Vec3T &v)
Return the index [0,1,2] of the smallest value in a 3D vector.
Definition: Math.h:801
RayT::TimeSpan TimeSpanT
Definition: DDA.h:289
void init(const RayT &ray, RealT startTime, RealT maxTime)
Definition: DDA.h:77
VolumeHDDA()
Definition: DDA.h:291
DDA()
uninitialized constructor
Definition: DDA.h:69
TreeT::RootNodeType::NodeChainType ChainT
Definition: DDA.h:213
DDA(const RayT &ray, RealT startTime, RealT maxTime)
Definition: DDA.h:75
RealType RealT
Definition: DDA.h:64
DDA(const RayT &ray)
Definition: DDA.h:71
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
RealType maxTime() const
Return the maximum time (parameterized along the Ray).
Definition: DDA.h:132
tree::ValueAccessor< const TreeT > AccessorT
Definition: DDA.h:215
TimeSpanT march(RayT &ray, AccessorT &acc)
Definition: DDA.h:293
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
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:217
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:67
bool isZero(const Type &x)
Return true if x is exactly equal to zero.
Definition: Math.h:274
RayT::Vec3Type Vec3Type
Definition: DDA.h:65
TreeT::LeafNodeType LeafT
Definition: DDA.h:287
Helper class that implements Hierarchical Digital Differential Analyzers for ray intersections agains...
Definition: DDA.h:209
RayT::TimeSpan TimeSpanT
Definition: DDA.h:216
const Type & Min(const Type &a, const Type &b)
Return the minimum of two values.
Definition: Math.h:566