Fast calculation of the distance to cubic Bezier curves on the GPU

The naive generic way of finding distances from point P to curve C([0,1]) is a procedure quite standard for global minimization : repeat "find a local minimum on the space constrained to be better than any previous minimum"

- Find a point P0 local minimum of d(P,P0) subject to the constraint P0=C(t0) (aka P0 is on C)

- define d0 = d(P,P0)

- Bisect the curve at t1 into two curves C1 = C([0,t0]) and C2([t0,1])

- Find a point P1 local minimum of d(P,P1) subject to the constraint P1=C(t1) with 0- define d1 = d(P,P1)

- Find a point P2 local minimum of d(P,P2) subject to the constraint P2=C(t2) with t0 - define d2 = d(P,P2)

Here in the case of cubic Bezier the curve have only one loop so you don't need to bissect anymore. If curves where higher order like spirals, you would need to cascade the problems with a shrinking distance constraint (aka looking only for points in R^2 inside the circle

So the distance is min over all local minimum found = min( d0,d1,d2)

Here the local minimization problems are in R^n (and inside disks centered around P) with n the dimension of the space, and because this is numerical approximation, you can either use slack (dual) variables to find the tx which express the on Curve constraint or barrier methods to express the disk constraints once a t parametrization has been chosen.

Multivariate Newton is guaranteed to work because distances are positive so the Sequential Quadratic Programming problems are convex (scipy minimize "SLSQP"). (Whereas the author needed 5 polynomials root, you can only need to solve for 3 points because each solve solves for two coordinates).

A local minimum is a point which satisfy the KKT conditions.

This procedure is quite standard : it's for example use to find the eigenvalues of matrices iteratively. Or finding all solutions to a minimization problem.

Where this procedure shines, is when you have multiple splines, and you want to find the minimal distance to them : you can partition the space efficiently and not compute distances to part of curves which are to far away to have a chance to be a minimum. This will scale independently of the resolution of your chain spline. (imagine a spiral the number of local minimum you need to encounter are proportional to the complexity of the scene and not the resolution of the spiral)

But when you are speaking about computing the whole signed distance field, you should often take the step of solving the Eikonal equation over the space instead of computing individual distances.

These are the coefficients of the implicit curve, finding them can be done once upfront.

For integral quadratic bezier curves that is trivial as they are constant, see: https://www.shadertoy.com/view/fsXcDj

For rational cubic bezier curves it is more involved, see: https://www.shadertoy.com/view/ttVfzh

And for the full complexity of dealing with self intersecting loops and cusps see: https://github.com/Lichtso/contrast_renderer/blob/main/src/f...

> The winding number logic is usually super involved, especially when multiple sub-shapes start overlap and subtracting each other. Is this covered or orthogonal to what you are talking about?

Orthogonal: The implicit curve only tells you if you are inside or outside (the sign of the SDF), so that is technically sufficient, but usually you want more things: Some kind of anti-aliasing, composite shapes of more than one bezier curve and boolean operators for masking / clipping. Using the stencil buffer for counting the winding number allows to do all of that very easily without tessellation or decomposition at path intersections.

> Can you elaborate on it or provide resources?

If you are interested in the theory behind implicit curve rendering and how to handle the edge cases of cubic bezier curves checkout these papers:

Loop, Charles, and Jim Blinn. "Resolution independent curve rendering using programmable graphics hardware." https://www.microsoft.com/en-us/research/wp-content/uploads/...

BARROWCLOUGH, Oliver JD. "A basis for the implicit representation of planar rational cubic Bézier curves." https://arxiv.org/abs/1605.08669

Yes, as I said it is relevant for text rendering, but not necessarily 2D. It can also be embedded in a 3D perspective as long as the text itself is planar. Meaning you can directly render text in a 3D scene this way without rendering to a texture first.

> But real shadows and lighting would require the distance aspect, no?

I think the difference is in stroke vs fill, not the illumination (as you could still use shadow mapping / projection). In stroking you need to calculate an offset curve either explicitly or implicitly sample it from a signed distance field. Thus the exact distance matters for stroking, for filling it does not.