Open raphlinus opened 1 year ago
derekdreery
commented
1 year ago My plan here (as discussed in office hours) is to implement Bentley-Ottman verbatim from the paper (as much as possible). This will teach me a lot about scan-line algorithms (which I'm not super experienced with), and also will provide a benchmark for other options.
justvanrossum
commented
3 weeks ago I'd just like to put this out there as a feature request: skia-pathops does aggressive merging of contours in cases where it shouldn't be strictly necessary (at least from a naive standpoint). This is in the context of a drawing program.
Desired behavior: path 1 contains two overlapping contours, path 2 contains a contour that overlaps both contours in path 1. After subtracting path 2 from path 1, it would be nice for path 1 to still be made of two contours (with the overlap in tact). Discussion and examples here: https://github.com/fonttools/skia-pathops/issues/74
I hope this use case can be considered to be in scope for this highly anticipated future feature.
A fundamental but difficult operation in 2D vector graphics is boolean path operations. I would like to implement them well in kurbo.
Definition of the problem
Given the goal of a principled, robust solution, it is important to define the problem carefully.
The first step is to redefine the boolean operations into functions from winding number to winding number, where the range is either 0 or 1. This function is evaluated on the sum of winding numbers of the source paths. Union is |wind|>0, intersection is |wind|>1, symmetric difference is wind mod 2. Asymmetric difference is implemented by negating the winding numbers of one path (equivalent to reversing the directions of the subpaths) and using wind>0. All these are very well defined if the source paths have (0, 1) winding numbers everywhere; if that is not the case, then a regularization step can be run on the individual paths and a |wind|>0 rule.
The key correctness criterion is this:
For every point that is not within epsilon distance of the source paths, the winding number of the resulting path is equal to the rule function applied to the winding number of the source paths.
Given that epsilon is small, a consequence is that rendering the resulting path is visually indistinguishable from the true result. Another consequence is that extraneous geometry not present in the source is precluded.
There is a secondary correctness criterion related to robustness.
Robustness
For paths consisting entirely of linear segments and rational coordinates, an exact solution is possible, because all intersections are rational. A fair amount of the academic literature goes this direction; the Bartuschka et al reference below explores it deeply, and the [Shewchuk Robust Predicates] have a similar flavor, though they use arbitrary precision rather than rationals, exploiting performance gains from using plain floats when robustness is not at issue.
For curves, we cannot do that. Solving cubic Bézier intersection numerically is a hard enough problem as it is (mathematically, it reduces to a 9th order polynomial), but doing so with exact representations of algebraic numbers is clearly impractical.
I propose an approach based on a 3-way orientation predicate. Either one segment is robustly to the left of the other, robustly to the right, or they are within epsilon of each other (measured using some variant of Fréchet distance). For lines, this can be defined; it boils down to a 3-way point/line orientation predicate applied to the endpoints. If all endpoints are within epsilon of the other line, then the two lines are within epsilon of each other. Details of a draft of the proposed point/line orientation predicate are given in a draft blog post.
Developing a robust 3-way orientation predicate for curves remains to be done. This alone is a challenging and interesting research problem. When some ranges of the curve are epsilon-close but others are cleanly separated, a goal is to subdivide the curve segments so the subdivisions can be robustly oriented.
If two or more segments are within epsilon of each other, then they are consolidated during output. If the application of the rule results in the same value on either side of the cluster, the cluster can be deleted entirely. Otherwise, a segment is generated representing the cluster (choosing a representative segment from the cluster is valid, thanks to the correctness rule stated above).
A second correctness criterion enforces a very strict version of correctness:
For every scan line, the path segments in the output are all robustly ordered. Further, each segment causes a transition of winding number either from 0 to 1 or 1 to 0.
It is not immediately obvious that such a solution is even possible, but I believe it is. As a conceptual existence proof, first flatten the path to within epsilon, then apply robustness techniques to line segments. Again, in the worst case, subdivide all line segments at all y coordinates that appear, including both endpoints and intersection points. Then all line segments intersecting any given scan line at y all have the same y0 and y1 values (with y0 <= y <= y1), and they can be robustly ordered simply by comparing x coordinates (and the x coordinates do not cross, otherwise there would be an intersection point in the middle). Obviously, this is an excessive amount of flattening and subdivision, so a major goal of the algorithm is to apply such things adaptively, only when needed to resolve ambiguous orientation.
This second correctness criterion informs an invariant to be maintained during the main sweep-line algorithm (based on Bentley-Ottmann). Essentially, the active list consists of a sequence of clusters of line segments, each of which is robustly oriented with respect to the previous cluster. The details of course will be more complex. In many cases, the intersection primitive will identify a subdivision point (analogous to an intersection point for lines, which implies a swap of the active list to maintain orientation), so that orientation is only guaranteed through to the subdivision point, at which point orientation will be re-evaluated and maybe the active list re-ordered. (A parabola touching a line at the vertex is an example of an intersection of even order, so the active list need not be reordered. The algorithm would be expected to subdivide the path at the intersection point to maintain the robust ordering)
Curve-curve intersection
An important primitive, which has gotten a fair amount of attention in the academic literature, is computation of the intersections between two curve segments. In ℝ², either two cubic Béziers are either coincident for some overlap of t ranges or they intersect at up to 9 points. I believe we need a primitive that reports explicit orientations (when they can be determined robustly) or ranges that are within some epsilon of Fréchet distance.
Further, I believe it is possible to do better than the current state of the art, which is based on the "fat line" algorithm. My approach is to compute bounding parabolas. A prototype exists in #258.
It may be practical to compute quadratic/quadratic intersection analytically; a draft implementation currently exists in
examples/quad_intersect.rs. However, numerical stability issues are unknown, and the current implementation won't give useful results if the quadratics come close to each other (possibly within epsilon) but don't actually intersect. Line/Bézier intersection is tractable and implementations exist, but again special attention will be needed around "close but no touch" cases to ensure robustness.A related proposal is #274, which would define an intersection trait that could be implemented for arbitrary curve types. I believe we should do robust Bézier path intersection before trying to generalize it too much. Also see #219 for a proposed fat line intersection algorithm for cubics.
References
See also https://github.com/raphlinus/raphlinus.github.io/issues/79 for more discussion, including notes toward a blog post or series of posts.