Fast calculation of the distance to cubic Bezier curves on the GPU
2 days ago
- #distance fields
- #Bézier curves
- #polynomial solving
- Bézier curves are fundamental for text and 2D shapes rendering, with computing the distance to a Bézier curve being a challenging problem.
- Quadratic curves (one control point) are easier to handle, while cubic curves (two control points) present more complexity.
- Distance fields enable various rendering possibilities, demonstrated through live visualizations and GLSL fragment shaders.
- The mathematical approach involves expressing Bézier curves as polynomials and solving for the minimum distance using derivatives.
- Two methods for solving quintic polynomial equations are discussed: the Aberth–Ehrlich method and a newer algorithm by Cem Yuksel.
- The Aberth–Ehrlich method, while quick, has flaws like working in complex space and unreliable initial guesses.
- Cem Yuksel's 2022 algorithm, optimized for GPU and simpler, proves more reliable and faster, though it requires adjustments for specific ranges.
- The ITP method was explored for faster convergence but showed more iterations compared to the bisection method in practice.
- The unrolled version of Cem Yuksel's algorithm is currently the best choice for solving the distance to Bézier curves, with potential improvements in cubic solvers.
- Future work includes extending the approach to chains of Bézier curves for complex shapes like font glyphs, leading to signed distance fields.