0f65d45
committed
Commits
Comments (0)
Files changed (3)

+2 9VectorBoolean/Canvas.m

+3 0VectorBoolean/FBBezierCurve.h

+176 36VectorBoolean/FBBezierCurve.m
VectorBoolean/FBBezierCurve.h
+// FBBezierCurve is one cubic 2D bezier curve. It represents one segment of a bezier path, and is where
VectorBoolean/FBBezierCurve.m
return (point2.x  point1.x) * (point3.y  point1.y)  (point2.y  point1.y) * (point3.x  point1.x);
static BOOL LineIntersectsHorizontalLine(NSPoint startPoint, NSPoint endPoint, CGFloat y, NSPoint *intersectPoint)
static NSPoint BezierWithPoints(NSUInteger degree, NSPoint *bezierPoints, CGFloat parameter, NSPoint *leftCurve, NSPoint *rightCurve)
+ // Helper method to easily convert a bezier path into an array of FBBezierCurves. Very straight forward,
+ (id) bezierCurveWithEndPoint1:(NSPoint)endPoint1 controlPoint1:(NSPoint)controlPoint1 controlPoint2:(NSPoint)controlPoint2 endPoint2:(NSPoint)endPoint2
return [[[FBBezierCurve alloc] initWithEndPoint1:endPoint1 controlPoint1:controlPoint1 controlPoint2:controlPoint2 endPoint2:endPoint2] autorelease];
 (NSArray *) intersectionsWithBezierCurve:(FBBezierCurve *)curve usRange:(FBRange *)usRange themRange:(FBRange *)themRange originalUs:(FBBezierCurve *)originalUs originalThem:(FBBezierCurve *)originalThem
+ // This is the main work loop. At a high level this method sits in a loop and removes sections (ranges) of the two bezier curves that it knows
+ // don't intersect (how it knows that is covered in the appropriate method). The idea is to whittle the curves down to the point where they
+ // do intersect. When the range where they intersect converges (i.e. matches to 6 decimal places) or there are more than 500 attempts, the loop
+ // stops. A special case is when we're not able to remove at least 20% of the curves on a given interation. In that case we assume there are likely
+ static const NSUInteger maxIterations = 500; // how many iterations to allow before we just give up
+ static const CGFloat minimumChangeNeeded = 0.20; // how much to clip off for a given iteration minimum before we subdivide the curve
+ FBBezierCurve *them = curve; // them is the other curve we're intersecting with, but clipped down to where the intersection is
// Don't check for convergence until we actually see if we intersect or not. i.e. Make sure we go through at least once, otherwise the results
+ // don't mean anything. Be sure to stop as soon as either range converges, otherwise calculations for the other range goes funky because one
while ( iterations < maxIterations && ((iterations == 0)  (!FBRangeHasConverged(*usRange, places) && !FBRangeHasConverged(*themRange, places))) ) {
+ // Remove the range from ourselves that doesn't intersect with them. If the other curve is already a point, use the previous iteration's
us = [us bezierClipWithBezierCurve:them.isPoint ? previousThem : them original:originalUs rangeOfOriginal:usRange intersects:&intersects];
them = [them bezierClipWithBezierCurve:us.isPoint ? previousUs : us original:originalThem rangeOfOriginal:themRange intersects:&intersects];
+ // If either curve has been reduced to a point, stop now even if the range hasn't properly converged. Once curves become points, the math
+ FBRange themRangeCopy1 = *themRange; // make a local copy because it'll get modified when we recurse
+ FBRange themRangeCopy2 = *themRange; // make a local copy because it'll get modified when we recurse
NSArray *intersections1 = [us1 intersectionsWithBezierCurve:them usRange:&usRange1 themRange:&themRangeCopy1 originalUs:originalUs originalThem:originalThem];
NSArray *intersections2 = [us2 intersectionsWithBezierCurve:them usRange:&usRange2 themRange:&themRangeCopy2 originalUs:originalUs originalThem:originalThem];
FBRange themRange1 = FBRangeMake(themRange>minimum, (themRange>minimum + themRange>maximum) / 2.0);
FBRange themRange2 = FBRangeMake((themRange>minimum + themRange>maximum) / 2.0, themRange>maximum);
NSArray *intersections1 = [us intersectionsWithBezierCurve:them1 usRange:&usRangeCopy1 themRange:&themRange1 originalUs:originalUs originalThem:originalThem];
NSArray *intersections2 = [us intersectionsWithBezierCurve:them2 usRange:&usRangeCopy2 themRange:&themRange2 originalUs:originalUs originalThem:originalThem];
+ // It's possible that one of the curves has converged, but the other hasn't. Since the math becomes wonky once a curve becomes a point,
+ // the loop stops as soon as either curve converges. However for our purposes we need _both_ curves to converge; that is we need
+ // the parameter for each curve where they intersect. Fortunately, since one curve did converge we know the 2D point where they converge,
+ // plus we have a reasonable approximation for the parameter for the curve that didn't. That means we can use Newton's method to refine
NSPoint intersectionPoint = [originalUs pointAtParameter:usRange>minimum leftBezierCurve:nil rightBezierCurve:nil];
+ CGFloat refinedParameter = FBRangeAverage(*themRange); // Although the range didn't converge, it should be a reasonable approximation which is all Newton needs
NSPoint intersectionPoint = [originalThem pointAtParameter:themRange>minimum leftBezierCurve:nil rightBezierCurve:nil];
+ CGFloat refinedParameter = FBRangeAverage(*usRange); // Although the range didn't converge, it should be a reasonable approximation which is all Newton needs
+ // Return the final intersection, which we represent by the original curves and the parameters where they intersect. The parameter values are useful
return [NSArray arrayWithObject:[FBBezierIntersection intersectionWithCurve1:originalUs parameter1:usRange>minimum curve2:originalThem parameter2:themRange>minimum]];
 (FBBezierCurve *) bezierClipWithBezierCurve:(FBBezierCurve *)curve original:(FBBezierCurve *)originalCurve rangeOfOriginal:(FBRange *)originalRange intersects:(BOOL *)intersects
+ // This method does the clipping of self. It removes the parts of self that we can determine don't intersect
+ // with curve. It'll return the clipped version of self, update originalRange which corresponds to the range
+ // on the original curve that the return value represents. Finally, it'll set the intersects out parameter
+ // Draw a line through the two endpoints of the other curve, which we'll call the fat line. Measure the
+ // signed distance between the control points on the other curve and the fat line. The distance from the line
+ // will give us the fat line bounds. Any part of our curve that lies further away from the fat line than the
+ // We actually use two different fat lines. The first one uses the end points of the other curve, and the second
+ // one is perpendicular to the first. Most of the time, the first fat line will clip off more, but sometimes the
+ // second proves to be a better fat line in that it clips off more. We use both in order to converge more quickly.
+ // Compute the regular fat line using the end points, then compute the range that could still possibly intersect
+ // A range of [1, 0] is a special sentinel value meaning "they don't intersect". If they don't, bail early to save time
+ // Combine to form Voltron. Take the intersection of the regular fat line range and the perpendicular one.
FBRange clippedRange = FBRangeMake(MAX(regularClippedRange.minimum, perpendicularClippedRange.minimum), MIN(regularClippedRange.maximum, perpendicularClippedRange.maximum));
 FBRange newRange = FBRangeMake(FBRangeScaleNormalizedValue(*originalRange, clippedRange.minimum), FBRangeScaleNormalizedValue(*originalRange, clippedRange.maximum));
+ // Right now the clipped range is relative to ourself, not the original curve. So map the newly clipped range onto the original range
+ FBRange newRange = FBRangeMake(FBRangeScaleNormalizedValue(*originalRange, clippedRange.minimum), FBRangeScaleNormalizedValue(*originalRange, clippedRange.maximum));
+ // Actually divide the curve, but be sure to use the original curve. This helps with errors building up.
+ // This method computes the range of self that could possibly intersect with the fat line passed in (and thus with the curve enclosed by the fat line).
+ // To do that, we first compute the signed distance of all our points (end and control) from the fat line, and map those onto a bezier curve at
+ // evenly spaced intervals from [0..1]. The parts of the distance bezier that fall inside of the fat line bounds, correspond to the parts of ourself
+ // that could potentially intersect with the other curve. Ideally, we'd calculate where the distance bezier intersected the horizontal lines representing
+ // the fat line bounds. However, computing those intersections is hard and costly. So instead we'll compute the convex hull, and intersect those lines
+ // with the fat line bounds. The intersection with the lowest x coordinate will be the minimum, and the intersection with the highest x coordinate will
+ // The convex hull (for cubic beziers) is the four points that define the curve. A useful property of the convex hull is that the entire curve lies
FBBezierCurve *distanceBezier = [FBBezierCurve bezierCurveWithEndPoint1:NSMakePoint(0, FBNormalizedLineDistanceFromPoint(fatLine, _endPoint1)) controlPoint1:NSMakePoint(1.0/3.0, FBNormalizedLineDistanceFromPoint(fatLine, _controlPoint1)) controlPoint2:NSMakePoint(2.0/3.0, FBNormalizedLineDistanceFromPoint(fatLine, _controlPoint2)) endPoint2:NSMakePoint(1.0, FBNormalizedLineDistanceFromPoint(fatLine, _endPoint2))];
+ NSArray *convexHull = [distanceBezier convexHull]; // the convex hull can be anywhere from 2 to 4 points.
+ // This is a very special case that I really wish I could get rid of. If perfectly horizontal and perfectly vertical lines intersect at both of their end points,
+ // the convex hull becomes a horizontal line on top of the minimum and maximum lines, which makes the line intersection calculation wonky. At this point, we
+ // throw our hands up and just say "we don't know where in here they intersect". If we don't do this, we end up saying they don't intersect at all, which could
if ( [convexHull count] == 2 && FBAreValuesClose(startPoint.y, endPoint.y) && FBAreValuesClose(startPoint.y, bounds.minimum) && !FBAreValuesClose(bounds.minimum, bounds.maximum) )
if ( [convexHull count] == 2 && FBAreValuesClose(startPoint.y, endPoint.y) && FBAreValuesClose(startPoint.y, bounds.maximum) && !FBAreValuesClose(bounds.minimum, bounds.maximum) )
 (NSPoint) pointAtParameter:(CGFloat)parameter leftBezierCurve:(FBBezierCurve **)leftBezierCurve rightBezierCurve:(FBBezierCurve **)rightBezierCurve
+ // This method is a simple wrapper around the BezierWithPoints() helper function. It computes the 2D point at the given parameter,
+ // Compute the convex hull for this bezier curve. The convex hull is made up of the end and control points.
+ // The hard part is determine the order they go in, and if any are inside or colinear with the convex hull.
+ // We're using the Graham Scan algorithm to determine the convex hull. It finds the points that form the outside
NSMutableArray *points = [NSMutableArray arrayWithObjects:[NSValue valueWithPoint:_endPoint1], [NSValue valueWithPoint:_controlPoint1], [NSValue valueWithPoint:_controlPoint2], [NSValue valueWithPoint:_endPoint2], nil];
+ // First, find the point that is on the bottom right, and move it to the first position in our array.
+ // Sort the points by the angle they form with the horizontal line on the lowest point, ascending.
VectorBoolean/Canvas.m