Accelerating median depth computation in Gaussian Splatting by tightening the binary search interval using sorted Gaussian structure and superlinear root-finding.
In Gaussian Splatting, computing median depth along a camera ray requires finding the depth d* where accumulated transmittance crosses T = 0.5. The transmittance function is:
The current approach uses a fixed-width interval for binary search, wasting iterations when the bracket is too wide and failing when the median falls outside. We propose adaptive bracketing strategies that tighten this interval.
The transmittance T(d) decreases monotonically along a camera ray. The fixed bracket (red) spans the entire scene, while the Gaussian-informed bracket (green) tightly captures the T=0.5 crossing.
Select the number of Gaussians per ray to see how each strategy performs.
How evaluation cost changes as the number of Gaussians per ray increases.
The Gaussian+ITP strategy exhibits a much shallower slope than the baseline, confirming superlinear convergence.
Evaluation cost over 50 simulated training frames. The Gaussian+ITP method is efficient from frame 1, requiring no warmup.
Phase 1 (Gaussian-Informed Scan): During the existing front-to-back alpha-compositing pass, track when cumulative transmittance first drops below 0.5. Record the bracket [dk-1, dk + 3σk]. Cost: one comparison and two stores per Gaussian (negligible on GPU).
Phase 2 (ITP Refinement): Apply the Interpolate-Truncate-Project method within the tight bracket. ITP combines regula falsi interpolation with bisection guarantees, achieving superlinear convergence on the smooth transmittance function. Typically converges in 3-5 evaluations.
Result: Total per-ray cost of ~8 transmittance evaluations vs. ~20 for the fixed baseline, a 2.4x reduction in search overhead.