AcademySoftwareFoundation / AcademySoftwareFoundation/openvdb

[BUG] VolumeHDDA with a semi-infinite ray that misses, marches off in an infinite loop.

Open
#1,710 0 comments 0 reactions 0 assignees View on GitHub
bug
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.