10#ifndef OPENVDB_MATH_DDA_HAS_BEEN_INCLUDED
11#define OPENVDB_MATH_DDA_HAS_BEEN_INCLUDED
33template<
typename RayT, Index Log2Dim = 0>
45 DDA(
const RayT& ray) { this->init(ray); }
47 DDA(
const RayT& ray,
RealT startTime) { this->init(ray, startTime); }
49 DDA(
const RayT& ray,
RealT startTime,
RealT maxTime) { this->init(ray, startTime, maxTime); }
53 assert(startTime <= maxTime);
54 static const int DIM = 1 << Log2Dim;
57 const Vec3T &pos = ray(mT0), &dir = ray.dir(), &inv = ray.invDir();
58 mVoxel = Coord::floor(pos) & (~(DIM-1));
59 for (
int axis = 0; axis < 3; ++axis) {
60 if (math::isZero(dir[axis])) {
62 mNext[axis] = std::numeric_limits<RealT>::max();
63 mDelta[axis] = std::numeric_limits<RealT>::max();
64 }
else if (inv[axis] > 0) {
66 mNext[axis] = mT0 + (mVoxel[axis] + DIM - pos[axis]) * inv[axis];
67 mDelta[axis] = mStep[axis] * inv[axis];
70 mNext[axis] = mT0 + (mVoxel[axis] - pos[axis]) * inv[axis];
71 mDelta[axis] = mStep[axis] * inv[axis];
76 inline void init(
const RayT& ray) { this->
init(ray, ray.t0(), ray.t1()); }
78 inline void init(
const RayT& ray,
RealT startTime) { this->
init(ray, startTime, ray.t1()); }
84 const int stepAxis =
static_cast<int>(math::MinIndex(mNext));
85 mT0 = mNext[stepAxis];
86 mNext[stepAxis] += mDelta[stepAxis];
87 mVoxel[stepAxis] += mStep[stepAxis];
111 inline RealType next()
const {
return math::Min(mT1, mNext[0], mNext[1], mNext[2]); }
115 void print(std::ostream& os = std::cout)
const
117 os <<
"Dim=" << (1<<Log2Dim) <<
" time=" << mT0 <<
" next()="
118 << this->next() <<
" voxel=" << mVoxel <<
" next=" << mNext
119 <<
" delta=" << mDelta <<
" step=" << mStep << std::endl;
130template<
typename RayT, Index Log2Dim>
133 os <<
"Dim=" << (1<<Log2Dim) <<
" time=" << dda.
time()
134 <<
" next()=" << dda.
next() <<
" voxel=" << dda.
voxel();
143template<
typename TreeT,
int NodeLevel>
146 using ChainT =
typename TreeT::RootNodeType::NodeChainType;
147 using NodeT =
typename ChainT::template Get<NodeLevel>;
149 template <
typename TesterT>
150 static bool test(TesterT& tester)
154 if (tester.template hasNode<NodeT>(dda.
voxel())) {
155 tester.setRange(dda.
time(), dda.
next());
165template<
typename TreeT>
168 template <
typename TesterT>
169 static bool test(TesterT& tester)
172 tester.init(dda.
time());
173 do {
if (tester(dda.
voxel(), dda.
next()))
return true; }
while(dda.
step());
186template <
typename TreeT,
typename RayT,
int ChildNodeLevel>
191 using ChainT =
typename TreeT::RootNodeType::NodeChainType;
192 using NodeT =
typename ChainT::template Get<ChildNodeLevel>;
197 template <
typename AccessorT>
201 if (ray.valid()) this->march(ray, acc, t);
209 template <
typename AccessorT,
typename ListT>
210 void hits(RayT& ray, AccessorT &acc, ListT& times)
214 this->hits(ray, acc, times, t);
215 if (t.valid()) times.push_back(t);
220 friend class VolumeHDDA<TreeT, RayT, ChildNodeLevel+1>;
222 template <
typename AccessorT>
223 bool march(RayT& ray, AccessorT &acc, TimeSpanT& t)
227 if (acc.template probeConstNode<NodeT>(mDDA.voxel()) !=
nullptr) {
228 ray.setTimes(mDDA.time(), mDDA.next());
229 if (mHDDA.march(ray, acc, t))
return true;
230 }
else if (acc.isValueOn(mDDA.voxel())) {
231 if (t.t0<0) t.t0 = mDDA.time();
232 }
else if (t.t0>=0) {
234 if (t.valid())
return true;
237 }
while (mDDA.step());
238 if (t.t0>=0) t.t1 = mDDA.maxTime();
246 template <
typename AccessorT,
typename ListT>
247 void hits(RayT& ray, AccessorT &acc, ListT& times, TimeSpanT& t)
251 if (acc.template probeConstNode<NodeT>(mDDA.voxel()) !=
nullptr) {
252 ray.setTimes(mDDA.time(), mDDA.next());
253 mHDDA.
hits(ray, acc, times, t);
254 }
else if (acc.isValueOn(mDDA.voxel())) {
255 if (t.t0<0) t.t0 = mDDA.time();
256 }
else if (t.t0>=0) {
258 if (t.valid()) times.push_back(t);
261 }
while (mDDA.step());
262 if (t.t0>=0) t.t1 = mDDA.maxTime();
265 math::DDA<RayT, NodeT::TOTAL> mDDA;
266 VolumeHDDA<TreeT, RayT, ChildNodeLevel-1> mHDDA;
271template <
typename TreeT,
typename RayT>
276 using LeafT =
typename TreeT::LeafNodeType;
281 template <
typename AccessorT>
285 if (ray.valid()) this->march(ray, acc, t);
289 template <
typename AccessorT,
typename ListT>
290 void hits(RayT& ray, AccessorT &acc, ListT& times)
294 this->hits(ray, acc, times, t);
295 if (t.valid()) times.push_back(t);
302 template <
typename AccessorT>
303 bool march(RayT& ray, AccessorT &acc, TimeSpanT& t)
307 if (acc.template probeConstNode<LeafT>(mDDA.voxel()) ||
308 acc.isValueOn(mDDA.voxel())) {
309 if (t.t0<0) t.t0 = mDDA.time();
310 }
else if (t.t0>=0) {
312 if (t.valid())
return true;
315 }
while (mDDA.step());
316 if (t.t0>=0) t.t1 = mDDA.maxTime();
320 template <
typename AccessorT,
typename ListT>
321 void hits(RayT& ray, AccessorT &acc, ListT& times, TimeSpanT& t)
325 if (acc.template probeConstNode<LeafT>(mDDA.voxel()) ||
326 acc.isValueOn(mDDA.voxel())) {
327 if (t.t0<0) t.t0 = mDDA.time();
328 }
else if (t.t0>=0) {
330 if (t.valid()) times.push_back(t);
333 }
while (mDDA.step());
334 if (t.t0>=0) t.t1 = mDDA.maxTime();
336 math::DDA<RayT, LeafT::TOTAL> mDDA;
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:25
A Digital Differential Analyzer specialized for OpenVDB grids.
Definition: DDA.h:35
bool step()
Increment the voxel index to next intersected voxel or node and returns true if the step in time does...
Definition: DDA.h:82
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:96
DDA(const RayT &ray)
Definition: DDA.h:45
DDA(const RayT &ray, RealT startTime)
Definition: DDA.h:47
DDA(const RayT &ray, RealT startTime, RealT maxTime)
Definition: DDA.h:49
RealType RealT
Definition: DDA.h:38
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:111
RealType maxTime() const
Return the maximum time (parameterized along the Ray).
Definition: DDA.h:106
void init(const RayT &ray)
Definition: DDA.h:76
void init(const RayT &ray, RealT startTime)
Definition: DDA.h:78
Vec3Type Vec3T
Definition: DDA.h:40
void init(const RayT &ray, RealT startTime, RealT maxTime)
Definition: DDA.h:51
DDA()
uninitialized constructor
Definition: DDA.h:43
typename RayT::Vec3Type Vec3Type
Definition: DDA.h:39
typename RayT::RealType RealType
Definition: DDA.h:37
void print(std::ostream &os=std::cout) const
Print information about this DDA for debugging.
Definition: DDA.h:115
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:103
typename RayT::TimeSpan TimeSpanT
Definition: DDA.h:277
typename TreeT::LeafNodeType LeafT
Definition: DDA.h:276
VolumeHDDA()
Definition: DDA.h:279
TimeSpanT march(RayT &ray, AccessorT &acc)
Definition: DDA.h:282
void hits(RayT &ray, AccessorT &acc, ListT ×)
Definition: DDA.h:290
Helper class that implements Hierarchical Digital Differential Analyzers for ray intersections agains...
Definition: DDA.h:188
typename RayT::TimeSpan TimeSpanT
Definition: DDA.h:193
VolumeHDDA()
Definition: DDA.h:195
TimeSpanT march(RayT &ray, AccessorT &acc)
Definition: DDA.h:198
typename ChainT::template Get< ChildNodeLevel > NodeT
Definition: DDA.h:192
void hits(RayT &ray, AccessorT &acc, ListT ×)
Definition: DDA.h:210
typename TreeT::RootNodeType::NodeChainType ChainT
Definition: DDA.h:191
std::ostream & operator<<(std::ostream &ostr, const Metadata &metadata)
Write a Metadata to an output stream.
Definition: Metadata.h:351
Definition: Exceptions.h:13
static bool test(TesterT &tester)
Definition: DDA.h:169
Helper class that implements Hierarchical Digital Differential Analyzers and is specialized for ray i...
Definition: DDA.h:145
typename ChainT::template Get< NodeLevel > NodeT
Definition: DDA.h:147
static bool test(TesterT &tester)
Definition: DDA.h:150
typename TreeT::RootNodeType::NodeChainType ChainT
Definition: DDA.h:146
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:121
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:212