Operating System: macOS
Version / Commit SHA: Pretty old, but I'm pretty sure this is still an issue
Other: Apple clang
Describe the bug
In general, VolumeHDDA::march is O(1) or O(number of nodes it has to visit) -- that is, it's fast. But at the root node, VolumeHDDA::march is O(maxTime). If you construct a VolumeHDDA with an empty grid and shoot a ray with maxTime == INFINITY (or just maxTime being very very large, take O(maxTime), because the root level doesn't have spatial data, so it walks off forever (or until it gets to maxTime. This makes it hard to do some things that should be easy.
To Reproduce
Steps to reproduce the behavior:
Use HDDA to march an infinite ray (Ray{}, which is from the origin in +x direction from t0 = math::Delta<RealT>::value() to t1 = std::numeric_limits<RealT>::max()) at an empty grid.
Note it goes into an infinite loop.
Expected behavior
VolumeHDDA is generally very fast, jumping over empty space. I'd expect it to try to do that at the root level. There's some room for different approaches. Simplest would be to give march a callback so the caller can make it terminate, so } while (mDDA.step()); becomes something like } while (mDDA.step() && !stopRequested());.
Possibly better: if we are the root-level hdda, then if we have taken more root-level steps than there are root children and we land in an empty root-level location, then bbox the root children, intersect the ray with that bbox, and just march along that segment. (I say "more root-level steps than there are root children" because then the big-O perf doesn't change from the current behavior.)
Additional context
If we add a callback, it also means the caller could pass in [&stopToken] { return stopToken.stop_requested(); }, which has its own benefit.
Environment
Operating System: macOS Version / Commit SHA: Pretty old, but I'm pretty sure this is still an issue Other: Apple clang
Describe the bug
In general,
VolumeHDDA::marchis O(1) or O(number of nodes it has to visit) -- that is, it's fast. But at the root node,VolumeHDDA::marchis O(maxTime). If you construct aVolumeHDDAwith an empty grid and shoot a ray withmaxTime == INFINITY(or justmaxTimebeing very very large, take O(maxTime), because the root level doesn't have spatial data, so it walks off forever (or until it gets tomaxTime. This makes it hard to do some things that should be easy.To Reproduce
Steps to reproduce the behavior:
marchan infinite ray (Ray{}, which is from the origin in +x direction fromt0 = math::Delta<RealT>::value()tot1 = std::numeric_limits<RealT>::max()) at an empty grid.Expected behavior
VolumeHDDAis generally very fast, jumping over empty space. I'd expect it to try to do that at the root level. There's some room for different approaches. Simplest would be to givemarcha callback so the caller can make it terminate, so} while (mDDA.step());becomes something like} while (mDDA.step() && !stopRequested());.Possibly better: if we are the root-level hdda, then if we have taken more root-level steps than there are root children and we land in an empty root-level location, then bbox the root children, intersect the ray with that bbox, and just march along that segment. (I say "more root-level steps than there are root children" because then the big-O perf doesn't change from the current behavior.)
Additional context
If we add a callback, it also means the caller could pass in
[&stopToken] { return stopToken.stop_requested(); }, which has its own benefit.