Something any serious vector graphics application has to implement is boolean operations. Boolean operations allow the user to combine bezier paths in interesting and powerful ways to create new shapes. The four common ones are:

Operation Example
(None) Union (Logical Or) Intersect (Logical And) Difference Join (Exclusive Or) Implementing them is somewhat involved, so I’m breaking the explanation up into two articles. This post will focus on finding intersections between individual bezier curves, and the next will show how to implement the boolean operations based on that. The algorithm presented will be able to handle arbitrary closed bezier paths, including those with holes and self intersections.

If you’re impatient, you can skip straight to the commented source code. As usual, I’ve released it under the MIT license. I encourage you to play with the sample application to see what it can do.

## Clipping until it converges

This post I’m focusing on finding intersections between individual bezier curves using an algorithm called bezier clipping. It’s described in the paper “Curve intersection using Bezier clipping” by TW Sederberg and T Nishita. If you’re following along in the source code, it’s implemented in the FBBezierCurve class.

The first thing to realize is that finding intersections between curves isn’t exact. I won’t be able to plug the inputs into a formula and get back all the points where the curves intersect. Instead, I’ll iteratively whittle down the curves to ranges that could possibly intersect until I get down to a point or eliminate the curve entirely.

So the pseudocode for the main loop would be:

``` FBBezierCurve *us = ...; // passed in FBBezierCurve *them = ...; // passed in FBRange usRange = FBRangeMake(0, 1); FBRange themRange = FBRangeMake(0, 1); while ( !FBRangeHasConverged(usRange) && !FBRangeHasConverged(themRange) ) { BOOL intersects = NO; us = [us bezierClipWithBezierCurve:them range:&usRange intersects:&intersects]; if ( !intersects ) return; // no intersections them = [them bezierClipWithBezierCurve:us range:&themRange intersects:&intersects]; if ( !intersects ) return; // no intersections } ```

Here a FBBezierCurve is one cubic bezier curve, as defined by two end points and two control points. FBRange is a parameter range defined by a minimum and maximum. A parameter value falls between [0..1] and is used for the parametric form of a bezier curve. In my case it keeps track of the range of the curve that could possibly intersect with the other curve.

The method bezierClipWithBezierCurve: refines the range passed in by determining the range where self could intersect with the curve passed in. It can also determine if there is no range where the two curves intersect. Don’t worry about how this is done right now, I’ll explain it later.

Each time through the loop I clip each curve a bit more, refining the range where the two curves might possibly intersect. The refined range is fed into the next iteration of the loop, which refines it a bit more. This continues until the minimum and maximum values of the range are close enough to be satisfactory (in my implementation, six decimal places). It’s also possible I discover, in clipping one curve against the other, that they don’t intersect at all. In that case, I can stop there.

The pseudocode above handles the common case where there is one (or no) intersection between the two curves. However cubic bezier curves can intersect up to nine times, so I need a way to detect when there are multiple intersections, and a way to find them. Detecting the possibility is easy; each time through the loop I compute how much I’ve reduced the intersection ranges by. If it’s less than 20%, then it’s likely there are multiple intersections, which would prevent the range from converging quickly.

Once I detect that I might have multiple intersections, I look at which range (and thus curve) is bigger. I split the correspond curve in half. I then recurse: for each of the halves I find the intersections between it and the other full curve. I take the combined results and return.

If you want to see the main loop in all it’s excruciating detail, check out the commented intersectionsWithBezierCurve:usRange:themRange:originalUs:originalThem: method. There are some implementation details I didn’t cover here, but are explained in the comments.

## Fat Lines

In the previous section I glossed over how I can refine the range of a curve that could possibly intersect with the other curve. I’ll tackle how to do that now.

What I really need is a way to more simply represent the area a given bezier curve could possibly inhabit. Once I have that I can determine which parts of the other bezier lie inside of that area (and thus possibly intersect), and which don’t.

To this end, Sederberg and Nishita introduce the concept of a fat line. A fat line is a line through the end points of the bezier curve, but fat enough it encloses the entire curve. Above you can see the bezier curve in blue and the fat line in the pink color, crossing through the curve’s end points. In code, the fat line is represented by a line (the dashed line above), plus two signed distances describing how far to extend the fat line above and below the dashed line. (Signed distance just means the value is negative if it falls below the line, positive if above.) The two distances form the bounds of the fat line, and are called the minimum and maximum bounds.

Computing an approximation to the minimum and maximum bounds is straightforward if I take advantage of the convex hull property. The convex hull is the polygon formed by connecting the end and control points with line segments. The convex hull property states that the polygon will completely enclose the bezier curve, as you can see below. The curve is in blue and the convex hull in red. So to compute the minimum and maximum bounds, I just compute the signed distances of the end and control points from the dashed line and chose the minimum and maximum distances. As you can see, using the convex hull to compute the minimum and maximum bounds doesn’t produce optimal results (i.e. the fat line fits loosely around the curve, not tightly). However the approximate bounds are cheap to compute and are good enough for my purposes.

Based on the fat line, it’s easy to see if any given point could possibly intersect with the bezier curve. Simply compute the signed distance from the line to the point. If that signed distance lies inside the fat line bounds, then it could intersect. If not, then it definitely doesn’t intersect.

## Bezier clipping

I’ve simplified the clipping curve to a fat line and bounds, and can use it to see if a point could lie inside the clipping curve. Next I need to clip the subject bezier curve with the fat line. The above diagram shows a range on the subject bezier that falls inside of the fat line, and thus could intersect with the other bezier. The piece inside the fat line is the bezier curve I want to end up with.

I start by calculating the signed distances of the end and control points of the subject bezier to the fat line. Next I construct a bezier curve from these distances, like so:

``` NSPoint endPoint1 = NSMakePoint(0, distance(fatline, subjectCurve.endPoint1)); NSPoint controlPoint1 = NSMakePoint(1.0/3.0, distance(fatline, subjectCurve.controlPoint1)); NSPoint controlPoint2 = NSMakePoint(2.0/3.0, distance(fatline, subjectCurve.controlPoint2)); NSPoint endPoint2 = NSMakePoint(1, distance(fatline, subjectCurve.endPoint2)); ```

I spread the distance bezier points out evenly between 0.0 and 1.0 on the X axis, and use the distances from the fat line as Y values. By uniformly spreading the X values out, they will correspond to parameter values for the parametric form of the subject bezier. Since the Y axis is the distance from the fat line, I can just throw the fat line bounds on the graph. If I can calculate the X values of where the distance bezier crosses the minimum and maximum bounds, then I’ll have the range of the subject bezier that falls inside the fat line. To do that, I’ll once again rely on the convex hull property. In the above diagram, the convex hull is the dashed red line. Computing the intersection of two lines is easy, so I find the intersections of the convex hull with the horizontal minimum and maximum lines. The lowest and highest X values define the parameter range on the subject bezier curve that fall into the fat line bounds, and thus could intersect the other curve.

There are two special cases here, both occurring when the distance bezier doesn’t intersect with the minimum or maximum fat line bounds. If the distance bezier falls completely inside the fat line bounds, then I can’t whittle the subject bezier down any, and I’m forced to return the entire subject bezier untouched. If the distance bezier lies completely outside the fat line bounds, I know the two curves don’t intersect, and return that.

If I did successfully refine the possible intersecting range, I need to cut down the subject curve to match. Fortunately, de Casteljau’s algorithm makes it easy to split bezier curves at a specific parameter value. See the BezierWithPoints() helper function for the implementation of that algorithm.

That completes how to clip one bezier curve against another. To summarize: compute a fat line and bounds from the clipping bezier, compute a distance bezier from the other curve, and see where the distance bezier’s convex hull intersects the fat line bounds. Using the intersections’ x values as the parameter range where the curves could intersect, cut the subject bezier down to match the range.

## Points of interest

Although the above description presents the complete algorithm for finding intersections between two bezier curves, I wanted to point out a couple of other things. These are implementations details that I either found interesting and/or difficult.

1. After the main intersection loop (in intersectionsWithBezierCurve:usRange:themRange:originalUs:originalThem:) there’s a bit of code that checks to see if both curves have converged to a point. The loop bails as soon as one curve converges since the math for clipping falls apart as soon as one curve becomes a point. However for implementing the boolean operations, I need good parameter values for both curves. Since I know the 2D intersection point from the curve that converged, and I can guess a reasonable parameter value for the curve that didn’t, I can use Newton’s method to refine the parameter value of the curve that didn’t converge. Fortunately, that’s something I’ve done before when fitting curves to points.

2. In the method that clips one bezier curve against the other (bezierClipWithBezierCurve:original:rangeOfOriginal:intersects:) you’ll notice that I don’t compute and clip against one fat line, but two. The second fat line is perpendicular to the regular one: Most of the time the regular fat line will clip out more of the curve than the perpendicular one. However, clipping against the perpendicular fat line does help the possible intersection range converge more quickly.

3. I mention the convex hull a couple of times, but gloss over how to build it. It is made up of just the end and control points, but the order is important, and sometimes points need to be removed if they’re collinear. There are several algorithms to build the convex hull, but Graham Scan is supposedly the best for 2D curves. It took me a few tries to get it right. Not all of the reference implementations/descriptions that I found covered the edges cases, such as what to do when I encountered collinear points. The best I found ended up being this one.

Check out the convexHull method for my implementation.

## Conclusion

Although I’m finding bezier curve intersections for the purpose of performing boolean operations, it can be used for other applications as well. Heck if I know what those are though. So next time I’ll dive into implementing union, intersect, difference, and join.

Be sure to enjoy the complimentary source code in the mean time.