Proposal: Intersection trait

[richard-uk1]

Currently there is some support for intersection within kurbo, but it is spread around. I propose a new trait called ParamCurveIntersect defined like

pub trait ParamCurveIntersect<T, const N: usize> {
    fn intersections(&self, other: &T) -> ArrayVec<(t, t), N>;
}

Implementers are encouraged to implement the trait in both directions (i.e. if they impl ParamCurveIntersect<T, _> for U then they should also impl ParamCurveIntersect<U, _> for T. A blanket impl is not possible because of the case impl ParamCurveIntersect<T, _> for T, and might not be desirable anyway.

The trait signature assumes that the number of intersections is bounded and small. We could instead fix N (to e.g. 9, the maximum number of cubic Bezier intersections), but this could lead to wasted space.

Existing work

There is some existing work for intersections.

• BezPath::intersect_line
• PathSeg::intersect_line
• CurveFitExample::intersect (private)
• examples/quad_intersect.rs
• Cubic intersection experimental branch #258 - 'better than fat line'
• Curve curve intersection, take two #199 - fat line algo adapted from lyon
• Curve curve intersection tylers #219 - more robust version of Curve curve intersection, take two #199?

[raphlinus]

I'm not sold on this, for a variety of reasons, but I could be swayed if there were really clearly defined use cases. To me, the primary use case is implementing boolean path ops (we should have a tracking issue for that), and I don't believe that this signature is sufficient for that.

Biggest problem: just listing intersections is not adequate for robust path operations. In general, you need to know the orientation (y = 0 and y = x^n intersect at the origin, but the sign of the orientation only flips for odd n), and there's also the rather serious problem of detecting the case when two curve segments are nearly (within epsilon) on top of each other. My understanding is that algorithms based on adaptive subdivision behave very poorly in the latter case; they tend to keep subdividing, and will likely report some arbitrary set of intersections. So I firmly believe that a key step toward path ops is designing an intersection method with the appropriate signature. In particular, it should report orientation explicitly when it is possible to determine robustly, and also that relevant subranges are within epsilon Fréchet distance. My current thinking is geared strongly toward sweep line algorithms so that one cartesian coordinate is preferred over the other, and ranges are reported in terms of that coordinate, but algorithms in the literature seem to lean more toward reporting based on the t parameter. (To a certain extent, these aren't hugely different because a sweep line algorithm will by necessity split curves to be monotonic wrt the sweep direction, but it affects details of the method signature)

Additional problem: the proposed trait represents intersection of the curve type with another curve of the same type, but that's not the only case. Line/curve intersections are also important for path ops, and tend to be quite a bit easier to implement (it's just a polynomial solve of the same order as the Bézier). Also, if we're considering a hypothetical SVG path representation including arcs (#265), then we'd need to solve at least the arc/cubic case as well. Thinking about this now, it may be the best approach to both these problems is to have an enum type analogous to PathSeg, and the n^2 cases would be dealt with by match on self and other.

My sense right now. The next step in this journey should be actually implementing robust path ops for BezPath, which is a hard enough problem, and doesn't require any new generic traits. When that's done, we should take a look at the intersection primitives, addressing two separate but related questions:

• Is there a generic trait that could practically be implemented for a wider variety of curve types than cubic Béziers? Based on my sweep-line exploration, it's likely that the methods would include: create bounding parabolas, intersect with line, and possibly additional stuff for bounds on Fréchet distance (which in turn may be based on either arc length parametrization or ray casting)
• Are there use cases other than path ops that would consume these intersection primitives, or do we preserve more implementation flexibility by considering them an internal detail of path ops?

[raphlinus]

I'm realizing that in the above writeup, I'm mixing up two distinct concepts. Let me separate them now.

One concept is a trait method that represents the results of curve intersection, taking as input a pair of curve segements, without specifying in any way how that's computed. To handle the n^2 matrix of possible curve types, this trait would be implemented on an enum. It would be broadly similar to what's proposed, though I still argue that just returning t values of intersection points is inadequate for robust path ops; an extension would allow for higher-order intersections and nearly-coincident ranges.

The other concept is a trait method (or set of trait methods) to measure a single curve for the purpose of computing intersections with other curves. My work-in-progress suggests that a core method is to compute a bounding parabola for a given range. Bounding parabolas can than be used to derive orientation (if they don't intersect at all), determine that two curves are within a certain Hausdorff distance (which is probably equivalent enough in practice to Fréchet, especially if this is only used for monotonic curve segments, or drive subdivision: any intersections will by definition be contained in the intersection of the two bounding parabolas.

That second approach is potentially an appealing solution to the general n^2 problem, for example computing an intersection between an arc and a cubic Bézier. You'd still want to handle the other special cases, for example there's now code for analytical computation of the intersection between two quadratics, using a quartic solver.

My conclusion is the same; we need to think more carefully about use cases first, and it would also be very helpful to have a complete implementation of path ops on Bézier paths before thinking too much about generalizing it.

[richard-uk1]

Thanks for the detailed response. I want to respond to one small point, and then talk more generally.

Additional problem: the proposed trait represents intersection of the curve type with another curve of the same type, but that's not the only case.

The signature actually allows Self and T to be different types. They can be the same (and it often makes sense to implement the case T = Self), but they don't have to be. For example you could impl ParamCurveIntersect<QuadBez, 2> for Line.

---

More generally, I think I have a slightly different use case. For stroking paths, then it is perhaps true that the only use of computing intersections is in the 'unioning' the derived fill. But I'm also interested in path offsets as a tool for designers. For this use case, my current plan is to compute the offset of each segment, join them (depending on some linejoin-like parameter), find intersections and split the curve at intersection points, then cull any geometry whose nearest point is nearer than the offset distance. It's also possible that the 'cull geometry that gets near' is a bad strategy and I should instead use boolean path ops to compute the stroke, then taking the stroke outline as the offset. I'm not sure - any tips are very welcome!

I've spent some time reading the Inkscape implementation, but then when I actually tried offsetting geometry it produced awful results for anything with significant curvature, so maybe that's not the place to look for inspiration.

These thoughts are a bit half-baked, so I may add to them as I understand things better.

[richard-uk1]

I'm going to use this thread to put up ideas for discussion:

I've been thinking about the discussion around intersections, and have come up with the following type for intersections. Please feed back suggestions.

enum Intersection {
    Point {
        /// The `t` value of the first parameter.
        t_left: f64,
        t_right: f64,
    },
    Segment {
        t_left: Range<f64>,
        t_right: Range<f64>,
    },
}

Some discussion points:

• The Point variant could also include the point in Cartesian coordinates (takes more space but potentially provides a more accurate value).
• For segment, I don't feel like it makes sense to report the start and end points in cartesian coordinates, unless you called it baseline or something like that. You could include the actual path, but what should the path be (BezPath?, CubicBez?, generic?). I feel like this would be over-engineering and you should just plug either range into the original curves.
• This type doesn't include any way of working out the orientation of the intersection (do the curves 'touch tangents', or do they actually cross?). Should this be reported, or derived in another step. Is it sufficient to say whether the lines cross or not, or is more information required?
• The idea would be that these types also contain 'near misses', where the left_curve.eval(t_left) != right_curve.eval(t_right) exactly. Should near misses like this be a separate variant, or perhaps intersections where the lines don't cross should be a separate variant, and include both hits and misses.
• Do we need to capture the case where 3 segments intersect at the same point, or where segments self-intersect in a way so there are more than 2 curves locally intersecting? Or is it enough to consider pair-wise intersections, and split up self-intersecting curves so they don't self-intersect?