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).
Description
@inproceedings{10.1145:3105762.3105783,
booktitle = {Eurographics/ ACM SIGGRAPH Symposium on High Performance Graphics},
editor = {Vlastimil Havran and Karthik Vaiyanathan},
title = {{Exploiting Budan-Fourier and Vincent's Theorems for Ray Tracing 3D Bézier Curves}},
author = {Reshetov, Alexander},
year = {2017},
publisher = {ACM},
ISSN = {2079-8679},
ISBN = {978-1-4503-5101-0},
DOI = {10.1145/3105762.3105783}
}