Shadow Ray Reduction using a Filtered Adaptive Multi-Level Hash Cache
Paper draft | 2006 Diplomarbeit (PDF) | Dev Log
Author: Manuel Kugelmann Status: Implementation in progress. Paper draft in progress.
The core ideas behind this project — control variates, Russian roulette, spatial hashing, variance-driven sampling — are not new. They are textbook Monte Carlo techniques (Knuth 1973; Hammersley and Handscomb 1964) and well-known data structures. The contribution of the 2006 thesis was combining them in a specific way for visibility estimation in rendering. Much of the same ground has since been covered independently by others, often with better engineering, better framing, or both. We all stand on the shoulders of giants.
The 2006 thesis. Manuel Kugelmann's 2006 Diplomarbeit ("Efficient Adaptive Global Illumination Algorithms", Universität Ulm, supervisor Alexander Keller) developed a framework called prediction with correction (Sec. 3.4): a spatial hash map stores cached predictions used as control variates, with Russian roulette deciding whether to trace a correction ray and variance driving the RR survival probability (Sec. 3.4.1). The framework was applied to visibility prediction (Sec. 3.2.2), contribution prediction (Sec. 3.2.3), and other cached quantities. The approach of using variance — not absolute light — to drive sampling rate, and the use of spatial hashing for the cache, was inspired by A. Keller's lectures on the role of variance and the "curse of dimensionality". The test case was Instant Radiosity [Keller 1997], but the caching is algorithm-agnostic — it operates on pairwise queries regardless of the rendering algorithm.
The thesis was never properly finished and remained unpublished. Its artifacts (text and code) likely linger in the Universität Ulm archives and A. Keller's archives. A definitive hardcopy and compact disk with source code exists in Manuel Kugelmann's storage.
Prior and parallel work on CV+RR. Using a control variate instead of zero on RR termination is at least implicit in the "go with the winners" family (Aldous and Vazirani 1994; Grassberger 2002). In the graphics context, Szécsi, Szirmay-Kalos and Kelemen 2003 formalized the non-zero termination estimate for rendering (CV with fixed RR probability). Szirmay-Kalos et al. 2005 added variance-driven RR using a scene-global radiance estimate. The 2006 thesis arrived at the same CV+VRRR math independently, differing mainly in the estimation source (per-point spatial cache rather than a scene-global constant) and the variance feedback loop (cache quality drives trace rate and spatial resolution). The overlap with both Szécsi et al. and Szirmay-Kalos et al. was discovered late in the writing process.
Spatial hashing. The spatial grids were visible in the thesis screenshots, but the use of spatial hashing to map grid cells to memory went unmentioned — it was treated as an implementation detail, not a contribution. The practical inspiration came from ODE (Open Dynamics Engine, Russell Smith, 2001–2004), which uses spatial hashing for broad-phase collision detection. Kugelmann encountered ODE through a Universität Ulm course project (Animal Race).
 |
 |
| Kugelmann 2006 — spatial hash grid, shadow test count | VisCache 2026 — pos_norm__dir_dist1, x16 SPP (~79% ray savings) |
What was not in 2006. The Bernoulli optimization (var = μ(1−μ), requiring no separate variance accumulator for binary visibility) was not realized — the thesis used generalized variance estimation across all cached quantities. Narrowing to binary visibility allows exploiting the Bernoulli structure. GPU implementation, modern hash functions, LOD-in-key, and ReSTIR integration are all new (see Key additions below).
Since the thesis was unpublished with no online abstract or indexed metadata, independent rediscovery of these ideas by the community is the expected and natural outcome.
Let's try an LLM-assisted speed run of getting the old 2006 work up to date ...
Most shadow rays in real-time path tracing are redundant — nearby surface points querying the same light region overwhelmingly agree on the outcome. We store binary visibility predictions in a flat, multilevel spatial hash table with 8-byte entries and lock-free atomic updates, and correct cached predictions stochastically so that the estimator remains unbiased regardless of cache quality.
The prediction-with-correction (Control Variate + Variance-driven Russian Roulette Residual) estimator converts any visibility prediction into an unbiased shadow ray estimator:
variance = µ(1 − µ)
p = clamp(variance / varianceThreshold, pMin, 1.0)
if random < p:
V = traceShadowRay()
return µ + (V - µ) / p # unbiased correction
else:
return µ # no trace, use cached mean
The Bernoulli structure of binary visibility makes this easy: The same scalar µ gives both the cached estimate and the variance.
The variance signal drives two reinforcing mechanisms simultaneously (coupled dual adaptation):
- Correction rate — variance steers the number of samples via RR
- Spatial resolution — variance gates which resolution levels of the cache get writes
High-variance regions trace more often and at finer spatial resolution. Low-variance regions trace rarely and only update the coarse level. This one-signal-two-decisions coupling is what makes the cache self-regulating without per-scene tuning.
The cache is algorithm-agnostic — it operates on pairwise visibility queries regardless of the rendering algorithm generating them.
The hash key decomposes the visibility query into shading point (position + surface normal) and query (direction + distance). This exploits free geometric information that symmetric position × position addressing cannot:
- Normal disambiguates thin geometry and corners — nearby points with different normals get separate entries
- Direction enables angular LOD — coarse angular bins where visibility is smooth, fine bins at shadow edges
- Distance monotonicity — if occluded at distance d, everything farther is also blocked; one any-hit ray (using the free
CommittedRayT()) propagates V=0 to all farther distance bins at zero cost
A secondary position × position mode is available for GI revalidation queries. Both modes coexist in the same flat hash table.
Key additions beyond Kugelmann 2006
- Position+normal × direction+distance addressing — exploits surface normal, angular LOD, and distance monotonicity
- Position Jitter as Filtering — intrinsic box filter across cell boundaries, based on Binder et al. 2018
- Good and Fast Hash — based on PCG3D Jarzynski & Olano 2020
- Hash Collision Handling — fingerprint like Binder et al. 2018, double-hash probing, pressure-scaled eviction
- LOD in the hash key — multiple resolutions in one flat table Gautron 2020, Gautron 2021
- Coupled variance adaptation — variance drives correction rate and spatial resolution like in Stotko et al. 2025
- GPU implementation — built on NVIDIA Falcor 8.0 Kallweit et al. 2022
- Cache-weighted light selection — cached μ weights ReSTIR candidate selection like Bokšanský & Meister 2025
- ReSTIR integration — example integration with ReSTIR DI Bitterli et al. 2020 and ReSTIR PT Lin et al. 2022
The visibility cache plugs into two points of the ReSTIR pipeline. During light selection, the cached mean µ replaces the usual visibility assumption in the RIS target function, yielding µ-weighted candidate selection that steers samples toward actually visible lights. During visibility revalidation, the correction estimator replaces unconditional occlusion rays with variance-driven Russian Roulette, reducing shadow rays while maintaining equal quality. This offers a middle way between skipping revalidation completely (biased) and full revalidation (expensive). Note: Instead of our visibility cache any other prediction of visibility, e.g. from ReSTIR reservoir data, can be used.
The individual ideas in the 2006 thesis — control variates, Russian roulette, spatial hashing, variance-driven sampling — are well-established techniques. Many researchers independently arrived at similar combinations. This is a non-exhaustive selection; there is likely more work we are not yet aware of.
Control Variate + Russian Roulette in rendering. Szécsi et al. 2003 and Szirmay-Kalos et al. 2005 preceded the 2006 thesis (see History). More recently, Dereviannykh et al. 2024 (Neural Two-Level MC) use a related approach — their MLMC residual estimator shares the cached-estimate-plus-unbiased-correction structure, framed as two-level Monte Carlo with an MIS-based termination heuristic.
Visibility Caching. The idea of caching visibility to reduce shadow rays predates 2006 — Ward 1991 used heuristic ordering to skip predictable shadow rays. Independent work arrived at the idea through different paths: Popov et al. 2013 an adaptive octree for offline rendering, Guo et al. 2020 (NEE++) per-voxel-pair visibility caching, SHaRC (Benyoub et al. 2024) a world-space radiance hash (RTX SDK), Bokšanský & Meister 2025 a neural visibility cache, and Tokuyoshi 2024 efficient visibility reuse across spatiotemporal neighbors in ReSTIR. Zhang, Lin et al. 2025 avoid shadow rays entirely for most lights via ReSTIR-selected shadow maps. Conner et al. 2025 (MegaLights, Unreal Engine 5) trace a fixed budget of shadow rays per pixel via stochastic light importance sampling.
Spatial Hashing in rendering. Spatial hashing was independently adopted in rendering by Binder et al. 2018 (path-space filtering), Gautron 2020/2021 (ambient occlusion), Müller et al. 2022 (Instant NGP — multi-resolution hash encoding, backbone of Bokšanský & Meister 2025 and Dereviannykh et al. 2024), and SHaRC (Benyoub et al. 2024) (world-space spatial hash, RTX SDK).
Variance-driven adaptive sampling. Vorba and Křivánek 2016 (ADRRS) precompute an adjoint importance function to set per-event RR/splitting weight windows. Rath et al. 2022 (EARS) uses efficiency-aware RR/splitting for path continuation; Meyer et al. 2024 (MARS) generalize to per-technique sample counts. Jin et al. 2025 (NRRS) pioneer neural networks with hash-grid encoding for learning RR factors in wavefront path tracing. Stotko et al. 2025 (MrHash) independently couples variance to spatial resolution in a flat hash (TSDF domain). All operate on path continuation decisions, not shadow ray gating — our work is orthogonal.
| Paper | Relation |
|---|---|
| Kugelmann 2006 (Diplomarbeit) | Direct ancestor — CV+RR with per-point spatial cache, variance-driven adaptive sampling |
| Szécsi et al. 2003 | Non-zero termination estimate for rendering (CV, fixed RR probability) |
| Szirmay-Kalos et al. 2005 | Variance-driven splitting/RR for path tracing |
| Teschner et al. 2003 | Spatial hashing for collision detection — foundational technique |
| Smith 2001–2004 (ODE) | Broad-phase collision via spatial hashing; inspiration for spatial hashing in 2006 thesis |
| Binder et al. 2018 | Spatial hashing, jitter-quantize, fingerprint collision detection |
| Gautron 2020, Gautron 2021 | LOD in hash key, lock-free GPU hash updates |
| Jarzynski & Olano 2020 (JCGT) | PCG3D hash function |
| Stotko et al. 2025 (MrHash) | Variance-driven resolution in flat hash (TSDF domain) |
| Vorba and Křivánek 2016 (ADRRS) | Adjoint-driven RR/splitting weight windows for path continuation |
| Rath et al. 2022 (EARS) | Efficiency-aware RR/splitting for path continuation |
| Meyer et al. 2024 (MARS) | Per-technique sample allocation via RR/splitting |
| Jin et al. 2025 (NRRS) | Neural RR factors with hash-grid encoding for wavefront path tracing |
| Guo et al. 2020 (NEE++) | Voxel-to-voxel visibility probability caching |
| Popov et al. 2013 | Adaptive quantization visibility caching (offline) |
| Benyoub et al. 2024 (SHaRC) | Spatial Hash Radiance Cache — world-space hash, roughness-gated LoD (RTX SDK) |
| Lin et al. 2022 (GRIS/ReSTIR_PT) | Baseline for GI revalidation |
| Tokuyoshi 2024 | Efficient visibility reuse across spatiotemporal neighbors in ReSTIR |
| Zhang, Lin et al. 2025 (ReSTIR Shadow Maps) | ReSTIR-selected shadow maps — avoids shadow rays for most lights |
| Conner et al. 2025 (MegaLights) | Fixed-budget stochastic direct lighting in Unreal Engine 5 |
| Bitterli et al. 2020 (ReSTIR DI) | Spatiotemporal reservoir resampling for direct lighting; integration target |
| Bokšanský & Meister 2025 (JCGT) | Neural visibility cache for light selection |
| Dereviannykh et al. 2024 (Neural Two-Level MC) | MLMC residual shares cached-estimate + correction structure (but framed as MLMC, not CV; BTH is MIS-based, not variance-driven RR), multi-level hash encodings |
| Müller et al. 2022 (Instant NGP) | Multi-resolution hash encoding — spatial hashing for neural graphics; backbone of Bokšanský 2025 and Dereviannykh 2024 |
| Kallweit et al. 2022 (Falcor) | GPU rendering framework used as implementation base |
cmd /c "curl -sL https://raw.githubusercontent.com/ManuelKugelmann/VisCacheSketch/main/scripts/install.bat?%RANDOM% -o %TEMP%\vc-install.bat && %TEMP%\vc-install.bat"Idempotent — safe to re-run. Clones (or pulls), downloads test scenes, downloads the latest release, runs CPU tests, and launches Mogwai with Bistro.
See Getting Started for build-from-source, Linux/WSL, and release usage.