3 ms·
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
by ux 4y ago
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.
- raphlinus 4y agoYes, 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=2206&context=etd https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=...
- 082349872349872 4y agoIf 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?
- raphlinus 4y agoThis 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.