Item — HN Reader

I'm working on this as we speak. As as another commenter has mentioned, the "fat line" Bézier clipping algorithm is the current state of the art, but I'm confident at this point I can do better. The weakness of this class of algorithms is when two curves are very close to each other, then they keep subdividing. Another major challenge is numerical stability - getting a guarantee that no two curve segments in the output cross is tricky and requires careful definition of what correct operation means.

I'd love to work with a more mathematical colleague on the error bounds and so on. Ideally one who knows the way of the land regarding academic publication, as I think even what I have now is publishable.

Another good implementation to be aware of is Skia path ops[1], used quite a bit in production, including fonts.

[1]: https://skia.org/docs/dev/present/pathops/

3 comments

Numerical stability is a nightmare for the winding number algorithm. I've spent about 2 years on it already, but I believe I've managed to make it work. I used the paper from Eric Lengyel which worked it out with quadratic and extended it to cubics. I kept the topology classification strategy, but had to work out a different solution for the analytical resolution stitching. I'm planning to write about it; this serie of math articles are actually building up the foundations I need to explain it.

I'd be happy to discuss it though.

Yes, very happy to discuss; my email is raph.levien at the mail service operated by Google.

I think my approach may be less difficult, as it's based on accepting numerical errors when curves are within epsilon of each other. Thus, a lot of the guts of my algorithm is computing bounds and geometric intervals (adapting some ideas from North's master's thesis[1]). I'm I'm not yet convinced that precise orientation is even possible with cubics.

[1]: https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=...

If you still have the original paths, mustn't[0] "in" and "out" alternate?

[0] assuming intersection multiplicity degeneracy is handled elsewhere, but maybe not having to do that is what winding number provides?

This is exactly the hard part. If you have an intersection of even multiplicity, then they won't alternate. In addition, when you're using these things for path intersection, you also want to be notified of "near misses", because adding floating point roundoff could make these curves intersect even if the exact input doesn't.

> I'm working on this as we speak.

Cool! Is it going to be a part of Skia or something Google internal?

The first implementation will be in the kurbo codebase, in Rust, permissively licensed. If it works out as well as I'd like, the code will be only moderately complex, which I hope means others can implement the ideas without too much difficulty as well.

including fonts is a big recommendation, as they are often chock full of tangencies.