If you only want to fill a path of bezier curves (e.g. for text rendering) you can do without the "distance" part from "signed distance field" [0], leaving you with a "signed field" aka. an implicit curve [1].
Meaning not having to calculate the exact distance but only the sign (inside or outside) can be done without all the crazy iterative root finding in an actually cheap manner with only four multiplications and one addition per pixel / fragment / sample for a rational cubic curve [3].
[0]: https://en.wikipedia.org/wiki/Signed_distance_function
[1]: https://en.wikipedia.org/wiki/Implicit_curve
[2]: https://github.com/Lichtso/contrast_renderer/blob/a189d64a13...
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?
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.
Though it is very unpractical because the offset curve of a cubic bezier curve is not a cubic bezier curve anymore, instead it is an analytic curve of degree 10. Thus, in practice the offset curves for stroking are either approximated by polygons or implicitly sampled from signed distance fields.
Raph Levien has a good blog post about it:
https://raphlinus.github.io/curves/2022/09/09/parallel-bezie...
One more thing: Offset curves are different form classical scaling from a center point in all but the most trivial cases where there exists such a center; namely regular polygons. And cubic bezier curves can be concave, even have a self intersecting loop or form a cusp.
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< t1 < t0 (aka P1 on c1) and the additional constraint d(P,P1) < d0 (note here the inequality is strict so that we won't find P0 again) if it exist.
- define d1 = d(P,P1)
- Find a point P2 local minimum of d(P,P2) subject to the constraint P2=C(t2) with t0 < t2 < 1 (aka P2 on c2) and the additional constraint d(P,P2) < d0 (note here the inequality is strict so that we won't find P0 again) if it exist.
- 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.
amelius•6h ago