News for hackers. Stuff that matters.

A comment on Deconstructing Bézier Curves. Parent comment

Re:Deconstructing Bézier Curves by ux on Tuesday August 16, 2022 @09:24AM (#32482394)
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.

[ Parent | on HN ]
Re:Deconstructing Bézier Curves by raphlinus on Tuesday August 16, 2022 @09:52AM (#32482718)
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=...

[ Parent | on HN ]
Re:Deconstructing Bézier Curves by 082349872349872 on Tuesday August 16, 2022 @01:55PM (#32486363)
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?

[ Parent | on HN ]
Re:Deconstructing Bézier Curves by raphlinus on Tuesday August 16, 2022 @02:05PM (#32486499)
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.
[ Parent | on HN ]