AcademySoftwareFoundation / AcademySoftwareFoundation/openvdb
[BUG] VolumeHDDA with a semi-infinite ray that misses, marches off in an infinite loop.
- Dominant language
- C++
- Stars
- 3.4k
- Forks
- 774
- Avg merge
- 3d 9h
- Merged PRs (30d)
- 34
Description
### 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::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:
1. Use HDDA to `march` an infinite ray (`Ray{}`, which is from the origin in +x direction from `t0 = math::Delta::value()` to `t1 = std::numeric_limits::max()`) at an empty grid.
2. 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.
Contributor guide
Research direction
Start at VolumeHDDA::march and reproduce the empty-grid case with an unbounded Ray{} and maxTime at infinity. Compare the proposed termination or root-level skipping approaches, then verify that marching a missed semi-infinite ray terminates without the current unbounded loop.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- computer-graphics, performance
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100