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

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).

Publication Date

Uploaded Files