Fast calculation of the distance to cubic Bezier curves on the GPU • Hacker News Board

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

#31

Post by turtledragonfly » Sat, Oct 18, 2025, 11:28 PM UTC

Pretty cool. I haven't dived into the details of this post, but it's a problem I've been wrangling with from time to time in my game.

Below is a series of writings on this topic that I enjoyed, by James Blinn, of "Blinn-Phong reflection" fame (and more). Not state-of-the-art, but an interesting read. It's just for cubics, which is what you need to solve the distance formula for quadratic bezier curves (my particular case), rather than the harder cubic curves of the linked article.

* https://courses.cs.washington.edu/courses/cse590b/13au/lectu...

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

#32

Post by mmorse1217 » Sun, Oct 19, 2025, 12:16 AM UTC

ux wrote: post #29

mmorse1217 wrote: post #28

Hey, thanks for the nice post. I really enjoyed reading it; it’s good see this kind of thing on the front page. Since you’re interested in doing this on GPU, an approach that might be interesting to you (although not necessarily more efficient) would be to leverage the intrinsic properties of Bezier curves to feed a near-optimal initial guess to Newton. Some useful facts about Bezier curves: i) Bezier control points…

Thank you! Do we have a guarantee that these subcurves are solvable with Newton's method? The approach with derivatives has this because we know there is one crossing, and also clipping them to the zero-derivatives makes sure there won't be multiple curve "pits".

The trick is that you only solve Newton on a single subcurve: you recursively find the closest control point on all subcurves, split that subcurve and repeat until the closest control point doesn’t move much, or just however many subdivision steps work in practice. So the last curve that you apply Newton to should be smooth enough to succeed. I think there are edge cases with cusps, but I can’t exactly remember the theoretical guarantees anymore.

I think this is the main reference for this algorithm (should be able to search for the pdf): https://www.sciencedirect.com/science/article/abs/pii/S01678...

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

#33

Post by raphlinus » Sun, Oct 19, 2025, 12:25 AM UTC

sfpotter wrote: post #30

This is quite a complicated approach that misses out on most of the basic numerical and geometric methods that will make the problem simpler. I would recommend looking outside of recent SIGGRAPH papers. Brushing up on the basics of Bernstein polynomials, B-splines, and rootfinding methods will lead you to develop simpler algorithms which are likely faster.

I'm extremely curious what those basic methods are. We're in the process of replacing the higher order rootfinding in kurbo with a new solver based on Yuksel's method[1]. If you know of simpler, faster techniques that would be quite interesting.

[1]: https://crates.io/crates/polycool

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

#34

Post by cyberax » Sun, Oct 19, 2025, 12:38 AM UTC

Would an undergrad-level algorithm be faster here?

1. Find the derivative, and use an analytic formula for the roots of a quartic equation.

2. Then evaluate the value at the zeros to look for the intervals that cross the [0,1] segment.

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

#35

Post by mmorse1217 » Sun, Oct 19, 2025, 12:42 AM UTC

raphlinus wrote: post #33

sfpotter wrote: post #30

This is quite a complicated approach that misses out on most of the basic numerical and geometric methods that will make the problem simpler. I would recommend looking outside of recent SIGGRAPH papers. Brushing up on the basics of Bernstein polynomials, B-splines, and rootfinding methods will lead you to develop simpler algorithms which are likely faster.

I'm extremely curious what those basic methods are. We're in the process of replacing the higher order rootfinding in kurbo with a new solver based on Yuksel's method[1]. If you know of simpler, faster techniques that would be quite interesting. [1]: https://crates.io/crates/polycool

This is a pretty good foundational reference for Bézier curves and b-splines https://www.sciencedirect.com/book/9780122490521/curves-and-...

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

#36

Post by GistNoesis » Sun, Oct 19, 2025, 6:21 AM UTC

mmorse1217 wrote: post #28

Hey, thanks for the nice post. I really enjoyed reading it; it’s good see this kind of thing on the front page. Since you’re interested in doing this on GPU, an approach that might be interesting to you (although not necessarily more efficient) would be to leverage the intrinsic properties of Bezier curves to feed a near-optimal initial guess to Newton. Some useful facts about Bezier curves: i) Bezier control points…

Thanks, that the same approach I was suggesting in my other comment in this thread https://news.ycombinator.com/item?id=45628245 . But couldn't find literature specific to the Bezier curves to help break the communication gap, and my specific knowledge of Bezier Curve isn't deep enough.

I am happy to see other people use the approach I consider more natural.

It's a generic global optimization approach and geometry is always full of pathological edge cases, so it's hard to tell if you miss any. Getting to work in the average case is usually easy, but to be sure it always work is much harder.

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

#37

Post by mmorse1217 » Sun, Oct 19, 2025, 12:55 PM UTC

GistNoesis wrote: post #36

mmorse1217 wrote: post #28

Hey, thanks for the nice post. I really enjoyed reading it; it’s good see this kind of thing on the front page. Since you’re interested in doing this on GPU, an approach that might be interesting to you (although not necessarily more efficient) would be to leverage the intrinsic properties of Bezier curves to feed a near-optimal initial guess to Newton. Some useful facts about Bezier curves: i) Bezier control points…

Thanks, that the same approach I was suggesting in my other comment in this thread https://news.ycombinator.com/item?id=45628245 . But couldn't find literature specific to the Bezier curves to help break the communication gap, and my specific knowledge of Bezier Curve isn't deep enough. I am happy to see other people use the approach I consider more natural. It's a generic global optimization approach and geometry is…

Your comment motivated me to also comment :) I agree: Bézier curves and b-splines have a lot of rich geometry baked it, so it makes sense to use it, especially if you can avoid second derivatives. I think I misunderstood your comment about the extra control point work to find an initial guess. It looks like we’re saying something pretty close though: you can split the curve smartly to remove the single crossing in this case, which skips all the recursion that I’m suggesting, which is probably better.

Yes the real trouble is true optimality guarantees. I remember that there were edge cases of the above approach needed that a lot of subdivision steps to succeed for general degree curves, so it might end up worse than a more rigorously justified approach in these cases.