Exploiting Budan-Fourier and Vincent's Theorems for Ray Tracing 3D Bézier Curves

Abstract

We present a new approach to finding ray-cubic Bézier curve intersections by leveraging recent achievements in polynomial studies. Compared with the state-of-the-art adaptive linearization, it increases performance by 5-50 times, while also improving the accuracy by 1000X. Our algorithm quickly eliminates parts of the curve for which the distance to the given ray is guaranteed to be bigger than a model-specific threshold (maximum curve's half-width). We then reduce the interval with the isolated distance minimum even further and apply a single iteration of a non-linear root-finding technique (Ridders' method).