Safe from the Losing Fight

In my last post I showed how to find the intersection points between two bezier curves. While interesting, it’s merely a stop on the way to implementing boolean operations for bezier paths. This time I’ll show how to conceptually perform the four common boolean operations: union, intersect, difference, and exclusive or. I’ll cover the actual algorithms for implementing the four operations in the next post.

Conceptually Speaking

I think it’s helpful to start out with a simple case and see how this will work conceptually. I’ll start with the following example:

Here I have a rectangle and circle overlapping. The intersections have already been calculated and circled in green. Now I consider the shapes as wireframes:

In my head, I divide up each path into sections based on the intersection points. There are two kinds of sections: one that is outside the other path, and one that is inside the other path. Performing a boolean operation is just a matter of picking the correct section from each path.

Here I’ve used a dashed style to mark which parts of the path are inside of the other path. Once I’ve separated the paths into the inside and outside parts, it’s easy to perform the boolean operations conceptually.

A union is a logical or, so I want all the outside sections:

The intersect operation is a logical and, so I just want the inside sections:

Difference is where I take a path and remove the parts that intersect with the other path. For that I want the outside sections of the subject (the rectangle), and the inside sections of the clip (the circle):

For now I’m going to ignore logical exclusive or because it requires properly handling subpaths and holes, which I’m not ready to talk about just yet. However I will say that exclusive or isn’t a primitive like the other operations, but is defined in terms of union, intersect, and difference. Specifically A Xor B is defined as (A Union B) Difference (A Intersect B).

Where is inside?

Before I go any further, I need to define what it means for a point or path to be “inside” of another. The previous examples were simple and just by eyeing them I could tell if a point or path section was inside or not. However, I’ll need something more robust for more complex operations.

Traditionally there are two ways to determine if a given point is inside a closed path or not. First, there’s the winding rule. I count how many times the path winds around the given point. If it’s more than 0, then the point is inside the path. This is default way NSBezierPath determines if a point is inside a path or not.

The second way is the even odd rule, which is the one I use in my implementation and for the rest of this post. I draw a ray from the given point to outside the bounds of the path. I then count how many times the ray intersects the path. If it is an odd number of times, then the point is inside the path. If even, it’s outside.

The star in the above diagram is one closed path. I’ve added three points A, B, and C to various places in the diagram, and applied the even odd rule to determine if they’re inside the star or not. The red arrow represents the ray I drew from the point to the outside of the path. (It doesn’t have to be a horizontal ray, it can go in any direction.) The ray from point A crosses the path exactly once, an odd number of times meaning it falls inside the star. The ray from point C crosses the path twice (even) so it is outside the star. Just by looking at the diagram it’s easy to see that A is inside and C is outside.

However, when I cast a ray from point B it also intersects with the star an even number of times, meaning it lies outside the path. This isn’t necessarily intuitive by looking at the diagram, but it is important for allowing holes in a path.

Both the winding rule and the even odd rule are called fill rules, because their main purpose is to determine which parts of a path are filled. Using the even odd rule the star above would be filled like:

The star has a hole in the middle. However, this isn’t the only way holes can be introduced to a path. Holes can be formed by unconnected subpaths. For example:

Here both the rectangle and ellipse are part of the same path; they’re just disjoint subpaths. As with the star, the same even odd rule applies meaning point A is inside the path, but B is not. The rectangle would be filled, except for the area the ellipse defines.

Nonintersecting Paths

Now that I’m done with that detour into fill rules and holes, I want to get back to boolean operations between two paths. I started with how to compute the results of a boolean operation if the two paths intersect, but what if the paths don’t intersect? There are two non-intersecting states I care about: when one path contains the other, and when the two paths lie outside of each other. I’ll start with two examples illustrating both of these states:

Contained
Disjoint

For the union operation, I want to eliminate any paths that are contained by another path. However a path is only contained by another if it falls inside the filled region as defined by the even odd rule. If the two paths lie outside of each other, the result of a union is both of them. So union-ing my two examples would result in:

Contained
Disjoint

Intersect, being the logical and, eliminates any area where both paths aren’t filled. In the case where one path contains another, the contained path is the one where both paths are filled. If the two paths don’t overlap in any way, then the result is nil.

Contained
Disjoint	(nil)

Difference starts with one path, which I’ll call A, and removes all the places that another path, B, fills. In the case of containment which path contains the other matters. If I’m computing A –B, and A contains B, then I’ll add B as a hole subpath to path A. If B contains A, then all of A subtracted away, and I’m left with nil. If the paths don’t overlap, and I’m computing A –B, then nothing changes and I’m left with A as the result.

For this example, assume the blue rectangle is A and the red ellipse is B.

Contained (A –B)
Contained (B –A)	(nil)
Disjoint (A –B)
Disjoint (B –A)

Intersecting Holes

Now that I’ve discovered holes, it’s time to see what happens when a path intersects with one. The process is the same as performing the operations on two normal paths, except which section (inside or outside) I chose to go in the result. I’ll start with a simple example:

In the above diagram, the blue rectangle and ellipse form one path, with the ellipse being a hole. The red circle forms the second path. As before the inside sections of the intersecting (sub)paths are shown in a dashed style.

For a union I’d normally choose the outside sections of both paths. However since the blue ellipse is a hole, the red circle should intrude into it. So I would pick the inside of the red circle and the outside of the blue ellipse. More generally, I would always pick the outside section of a path, unless the other path was a hole, then I’d pick the inside section. The union result would be:

Note that since the blue rectangle is nonintersecting, it passes straight through to the result. (See the previous section about nonintersecting paths.)

Intersect would normally choose the inside sections of each path. However, both paths clearly don’t exist inside of a hole. So when I choose which section to output for a given path, if the other path is a hole I’ll pick the outside section instead of the usual inside section. Here are the results of the intersect on these two paths:

In the intersect I remove the blue rectangle entirely, since it is a nonintersecting (sub)path.

In a difference operation the order of the operands matters, so I’ll take each direction separately. If I subtract the red (path B) from the blue (path A), normally I would chose the outside of A and the inside of B. However, just from eyeballing the paths I can tell that I should take the outside of B. When choosing which section to output for B, I look to see if A is a hole. If it is, I take the outside of B instead the inside, resulting in:

To compute B –A, I would usually pick the outside of B and the inside of A. But since A is a hole, I choose the inside of B, with the following results:

By now I’ve noticed a pattern for all the boolean operations. I choose the section of a path I normally would for that operation, unless the intersecting path is a hole. If it is I pick the opposite section than I normally would.

Exclusive Or Revisited

Now that I know about holes and how to perform union, intersect and difference on non-intersecting paths I can tackle exclusive or. I’ll return to the first example:

Now I take both the union and the intersect of both these paths, then subtract the intersect from the union for the final result. Below is the intermediate step after the union and intersect have been computed, but before the difference.

The union is in blue, and the intersect is in red. This diagram is a good illustration of an edge case. Technically there are two intersections between these two paths where the original rectangle and ellipse meet. However the two paths don’t fully cross each other at these intersections, they just meet at a point. Because of this, I ignore them. This holds true for any intersection: if the paths don’t cross each other then I ignore it for the purposes of boolean operations.

Since there are no crossing intersections, taking the difference happens between two paths that don’t intersect, and I fall back to those rules. The result of the xor:

There are two subpaths in the result: the union and the intersect subpaths. The interior subpath from the intersect thus forms a hole. If the result were filled, it would be:

Conclusion

All these pieces come together to be able to handle boolean operations for complex paths. First I handle all the intersecting subpaths as described, whether they are fill or hole. Then I process all nonintersecting subpaths, ignoring any intersecting subpaths for those computations.

This time I focused strictly on how to perform the boolean operations conceptually, based on the assumption I could find all the intersections. I covered how to think about paths as inside and outside sections, and how to perform boolean operations based on picking the correct section from each path. This is an important foundation for next time, when I’ll dig into the algorithms that actually implement these boolean operations.