Commits

Anonymous committed 8943aca

commenting much of the boolean ops helper classes, and eliminating some dead code

  • Participants
  • Parent commits 643b355

Comments (0)

Files changed (7)

File VectorBoolean/FBBezierContour.h

     FBContourInsideHole
 } FBContourInside;
 
+// FBBezierContour represents a closed path of bezier curves (aka edges). Contours
+//  can be filled or represent a hole in another contour.
 @interface FBBezierContour : NSObject<NSCopying> {
     NSMutableArray *_edges;
     NSRect _bounds;
     FBContourInside _inside;
 }
 
+// Methods for building up the contour. The reverse forms flip points in the bezier curve before adding them
+//  to the contour. The crossing to crossing methods assuming the crossings are on the same edge. One of
+//  crossings can be nil, but not both.
 - (void) addCurve:(FBBezierCurve *)curve;
 - (void) addCurveFrom:(FBEdgeCrossing *)startCrossing to:(FBEdgeCrossing *)endCrossing;
 - (void) addReverseCurve:(FBBezierCurve *)curve;
 
 @property (readonly) NSArray *edges;
 @property (readonly) NSRect bounds;
-@property (readonly) NSPoint testPoint;
 @property (readonly) NSPoint firstPoint;
 @property FBContourInside inside;
 @property (readonly) NSArray *intersectingContours;

File VectorBoolean/FBBezierContour.m

 #import "FBDebug.h"
 #import "FBBezierIntersection.h"
 
-@interface FBBezierContour ()
-
-- (BOOL) testPoint:(NSPoint *)point onRay:(FBBezierCurve *)ray;
-
-@end
-
 @implementation FBBezierContour
 
 @synthesize edges=_edges;
 
 - (void) addCurve:(FBBezierCurve *)curve
 {
+    // Add the curve by wrapping it in an edge
     if ( curve == nil )
         return;
     FBContourEdge *edge = [[[FBContourEdge alloc] initWithBezierCurve:curve contour:self] autorelease];
 
 - (void) addCurveFrom:(FBEdgeCrossing *)startCrossing to:(FBEdgeCrossing *)endCrossing
 {
-    // First construct the curve
+    // First construct the curve that we're going to add, by seeing which crossing
+    //  is nil. If the crossing isn't given go to the end of the edge on that side.
     FBBezierCurve *curve = nil;
     if ( startCrossing == nil && endCrossing != nil ) {
         // From start to endCrossing
 
 - (void) addReverseCurve:(FBBezierCurve *)curve
 {
+    // Just reverse the points on the curve. Need to do this to ensure the end point from one edge, matches the start
+    //  on the next edge.
     if ( curve == nil )
         return;
     FBBezierCurve *reverseCurve = [FBBezierCurve bezierCurveWithEndPoint1:curve.endPoint2 controlPoint1:curve.controlPoint2 controlPoint2:curve.controlPoint1 endPoint2:curve.endPoint1];
 
 - (void) addReverseCurveFrom:(FBEdgeCrossing *)startCrossing to:(FBEdgeCrossing *)endCrossing
 {
-    // First construct the curve
+    // First construct the curve that we're going to add, by seeing which crossing
+    //  is nil. If the crossing isn't given go to the end of the edge on that side.
     FBBezierCurve *curve = nil;
     if ( startCrossing == nil && endCrossing != nil ) {
         // From start to endCrossing
 
 - (NSRect) bounds
 {
+    // Cache the bounds to save time
     if ( !NSEqualRects(_bounds, NSZeroRect) )
         return _bounds;
     
+    // If no edges, no bounds
     if ( [_edges count] == 0 )
         return NSZeroRect;
     
-    // Start with the first point
+    // Start with the first point to set the topLeft and bottom right points
     FBContourEdge *firstEdge = [_edges objectAtIndex:0];
     NSPoint topLeft = firstEdge.curve.endPoint1;
     NSPoint bottomRight = topLeft;
     return edge.curve.endPoint1;
 }
 
-- (NSPoint) testPoint
-{
-    if ( [_edges count] == 0 )
-        return NSZeroPoint;
-    
-    static const CGFloat FBRayOverlap = 10.0;
-    
-    NSUInteger count = MAX(ceilf(NSWidth(self.bounds)), ceilf(NSHeight(self.bounds)));
-    for (NSUInteger fraction = 2; fraction <= count; fraction++) {
-        CGFloat verticalSpacing = NSHeight(self.bounds) / (CGFloat)fraction;
-        for (CGFloat y = NSMinY(self.bounds) + verticalSpacing; y <= NSMaxY(self.bounds); y += verticalSpacing) {
-            FBBezierCurve *ray = [FBBezierCurve bezierCurveWithLineStartPoint:NSMakePoint(NSMinX(self.bounds) - FBRayOverlap, y) endPoint:NSMakePoint(NSMaxX(self.bounds) + FBRayOverlap, y)];
-            NSPoint testPoint = NSZeroPoint;
-            if ( [self testPoint:&testPoint onRay:ray] )
-                return testPoint;
-        }
-        
-        CGFloat horizontalSpacing = NSWidth(self.bounds) / (CGFloat)fraction;
-        for (CGFloat x = NSMinX(self.bounds) + horizontalSpacing; x <= NSMaxX(self.bounds); x += horizontalSpacing) {
-            FBBezierCurve *ray = [FBBezierCurve bezierCurveWithLineStartPoint:NSMakePoint(x, NSMinY(self.bounds) - FBRayOverlap) endPoint:NSMakePoint(x, NSMaxY(self.bounds) + FBRayOverlap)];
-            NSPoint testPoint = NSZeroPoint;
-            if ( [self testPoint:&testPoint onRay:ray] )
-                return testPoint;            
-        }
-    }
-    
-    return NSZeroPoint; // we're hosed
-}
-
-- (BOOL) testPoint:(NSPoint *)point onRay:(FBBezierCurve *)ray
-{
-    static const CGFloat FBMinimumIntersectionDistance = 2.0;
-    
-    BOOL horizontalRay = ray.endPoint1.y == ray.endPoint2.y; // ray has to be a vertical or horizontal line
-
-    // First, find all the intersections and sort them
-    NSMutableArray *intersections = [NSMutableArray arrayWithCapacity:10];
-    for (FBContourEdge *edge in _edges) 
-        [intersections addObjectsFromArray:[ray intersectionsWithBezierCurve:edge.curve]];
-    if ( [intersections count] < 2 )
-        return NO;
-    [intersections sortUsingComparator:^NSComparisonResult(id obj1, id obj2) {
-        FBBezierIntersection *intersection1 = obj1;
-        FBBezierIntersection *intersection2 = obj2;
-        if ( horizontalRay ) {
-            if ( intersection1.location.x < intersection2.location.x )
-                return NSOrderedAscending;
-            else if ( intersection1.location.x > intersection2.location.x )
-                return NSOrderedDescending;
-            else
-                return NSOrderedSame;
-        }
-        
-        if ( intersection1.location.y < intersection2.location.y )
-            return NSOrderedAscending;
-        else if ( intersection1.location.y > intersection2.location.y )
-            return NSOrderedDescending;
-        return NSOrderedSame;
-    }];
-    
-    
-    // Walk the intersections looking for when the ray crosses inside of the contour
-    for (NSUInteger i = 0; i < ([intersections count] - 1); i += 2) {
-        // Between these two intersections is "inside" the contour
-        FBBezierIntersection *firstIntersection = [intersections objectAtIndex:i];
-        FBBezierIntersection *secondIntersection = [intersections objectAtIndex:i + 1];
-        
-        // We don't want a point on the edge, so make sure there is a minimum distance between them
-        CGFloat distance = horizontalRay ? secondIntersection.location.x - firstIntersection.location.x : secondIntersection.location.y - firstIntersection.location.y;
-        if ( distance < FBMinimumIntersectionDistance )
-            continue;
-        
-        // We have a winner
-        if ( horizontalRay )
-            *point = NSMakePoint((secondIntersection.location.x + firstIntersection.location.x) / 2.0, firstIntersection.location.y);
-        else
-            *point = NSMakePoint(firstIntersection.location.x, (secondIntersection.location.y + firstIntersection.location.y) / 2.0);
-        return YES;
-    }
-    
-    return NO;
-}
-
 - (BOOL) containsPoint:(NSPoint)testPoint
 {
     // Create a test line from our point to somewhere outside our graph. We'll see how many times the test
-    //  line intersects edges of the graph. Based on the winding rule, if it's an odd number, we're inside
+    //  line intersects edges of the graph. Based on the even/odd rule, if it's an odd number, we're inside
     //  the graph, if even, outside.
     NSPoint lineEndPoint = NSMakePoint(testPoint.x > NSMinX(self.bounds) ? NSMinX(self.bounds) - 10 : NSMaxX(self.bounds) + 10, testPoint.y); /* just move us outside the bounds of the graph */
     FBBezierCurve *testCurve = [FBBezierCurve bezierCurveWithLineStartPoint:testPoint endPoint:lineEndPoint];
 
 - (void) markCrossingsAsEntryOrExitWithContour:(FBBezierContour *)otherContour markInside:(BOOL)markInside
 {
+    // Go through and mark all the crossings with the given contour as "entry" or "exit". This 
+    //  determines what part of ths contour is outputted. 
+    
     // When marking we need to start at a point that is clearly either inside or outside
-    //  the other graph.
+    //  the other graph, otherwise we could mark the crossings exactly opposite of what
+    //  they're supposed to be.
     FBContourEdge *startEdge = [self.edges objectAtIndex:0];
     FBContourEdge *stopValue = startEdge;
     while ( startEdge.isStartShared ) {
         startEdge = startEdge.next;
         if ( startEdge == stopValue )
-            break; // for safety
+            break; // for safety. But if we're here, we could be hosed
     }
     
-    // Calculate the first entry value
+    // Calculate the first entry value. We need to determine if the edge we're starting
+    //  on is inside or outside the otherContour.
     BOOL contains = [otherContour containsPoint:startEdge.curve.endPoint1];
     BOOL isEntry = markInside ? !contains : contains;
     
             if ( crossing.counterpart.edge.contour != otherContour )
                 continue;
             crossing.entry = isEntry;
-            isEntry = !isEntry; // toggle
+            isEntry = !isEntry; // toggle.
         }
         
         edge = edge.next;
 
 - (void) round
 {
+    // Go through and round all the end points to integral value
     for (FBContourEdge *edge in _edges)
         [edge round];
 }
 
 - (NSArray *) intersectingContours
 {
+    // Go and find all the unique contours that intersect this specific contour
     NSMutableArray *contours = [NSMutableArray arrayWithCapacity:3];
     for (FBContourEdge *edge in _edges) {
         NSArray *intersectingEdges = edge.intersectingEdges;

File VectorBoolean/FBBezierIntersection.h

 
 @class FBBezierCurve;
 
+// FBBezierIntersection stores where two bezier curves intersect. Initially it just stores
+//  the curves and the parameter values where they intersect. It can lazily compute
+//  the 2D point where they intersect, the left and right parts of the curves relative to
+//  the intersection point, if the intersection is tangent. 
 @interface FBBezierIntersection : NSObject {
     NSPoint _location;
     FBBezierCurve *_curve1;
 @property (readonly) FBBezierCurve *curve2LeftBezier;
 @property (readonly) FBBezierCurve *curve2RightBezier;
 
+// Intersections at the end points of curves have to be handled carefully, so here
+//  are some convience methods to determine if that's the case.
 @property (readonly, getter = isAtStartOfCurve1) BOOL atStartOfCurve1;
 @property (readonly, getter = isAtStopOfCurve1) BOOL atStopOfCurve1;
 @property (readonly, getter = isAtStartOfCurve2) BOOL atStartOfCurve2;

File VectorBoolean/FBBezierIntersection.m

 
     static const CGFloat FBPointCloseThreshold = 1e-7;
     
+    // Compute the tangents at the intersection. 
     NSPoint curve1LeftTangent = FBNormalizePoint(FBSubtractPoint(_curve1LeftBezier.controlPoint2, _curve1LeftBezier.endPoint2));
     NSPoint curve1RightTangent = FBNormalizePoint(FBSubtractPoint(_curve1RightBezier.controlPoint1, _curve1RightBezier.endPoint1));
     NSPoint curve2LeftTangent = FBNormalizePoint(FBSubtractPoint(_curve2LeftBezier.controlPoint2, _curve2LeftBezier.endPoint2));
     NSPoint curve2RightTangent = FBNormalizePoint(FBSubtractPoint(_curve2RightBezier.controlPoint1, _curve2RightBezier.endPoint1));
         
+    // See if the tangents are the same. If so, then we're tangent at the intersection point
     return FBArePointsCloseWithOptions(curve1LeftTangent, curve2LeftTangent, FBPointCloseThreshold) || FBArePointsCloseWithOptions(curve1LeftTangent, curve2RightTangent, FBPointCloseThreshold) || FBArePointsCloseWithOptions(curve1RightTangent, curve2LeftTangent, FBPointCloseThreshold) || FBArePointsCloseWithOptions(curve1RightTangent, curve2RightTangent, FBPointCloseThreshold);
 }
 

File VectorBoolean/FBContourEdge.h

 @class FBBezierContour;
 @class FBEdgeCrossing;
 
+// FBContourEdge wraps a bezier curve, and additionally, stores all the places
+//  on the curve where crossings happen.
 @interface FBContourEdge : NSObject {
     FBBezierCurve *_curve;
-    NSMutableArray *_crossings;
+    NSMutableArray *_crossings; // sorted by parameter of the intersection
     FBBezierContour *_contour;
     NSUInteger _index;
     BOOL _startShared;
 @property (readonly) NSArray *crossings;
 @property (readonly, assign) FBBezierContour *contour;
 @property NSUInteger index;
+
+// An easy way to iterate all the edges. Wraps around.
 @property (readonly) FBContourEdge *next;
 @property (readonly) FBContourEdge *previous;
+
 @property (readonly) FBEdgeCrossing *firstCrossing;
 @property (readonly) FBEdgeCrossing *lastCrossing;
 @property (readonly) NSArray *intersectingEdges;
 
+// Store if there are any intersections at either end of this edge.
 @property (getter = isStartShared) BOOL startShared;
 @property (getter = isStopShared) BOOL stopShared;
 

File VectorBoolean/FBContourEdge.m

 
 - (void) addCrossing:(FBEdgeCrossing *)crossing
 {
+    // Make sure the crossing can make it back to us, and keep all the crossings sorted
     crossing.edge = self;
     [_crossings addObject:crossing];
     [self sortCrossings];
 
 - (void) removeCrossing:(FBEdgeCrossing *)crossing
 {
+    // Keep the crossings sorted
     crossing.edge = nil;
     [_crossings removeObject:crossing];
     [self sortCrossings];
 
 - (void) sortCrossings
 {
+    // Sort by the "order" of the crossing, then assign indices so next and previous work correctly.
     [_crossings sortUsingComparator:^NSComparisonResult(id obj1, id obj2) {
         FBEdgeCrossing *crossing1 = obj1;
         FBEdgeCrossing *crossing2 = obj2;

File VectorBoolean/FBEdgeCrossing.h

 @class FBContourEdge;
 @class FBBezierCurve;
 
+// FBEdgeCrossing is used by the boolean operations code to hold data about
+//  where two edges actually cross (as opposed to just intersect). The main
+//  piece of data is the intersection, but it also holds a pointer to the
+//  crossing's counterpart in the other FBBezierGraph
 @interface FBEdgeCrossing : NSObject {
     FBBezierIntersection *_intersection;
     FBContourEdge *_edge;
 @property (getter = isEntry) BOOL entry;
 @property (getter = isProcessed) BOOL processed;
 @property NSUInteger index;
+
+// An easy way to iterate crossings. It doesn't wrap when it reaches the end.
 @property (readonly) FBEdgeCrossing *next;
 @property (readonly) FBEdgeCrossing *previous;
 
+// These properties pass through to the underlying intersection
 @property (readonly) CGFloat parameter;
 @property (readonly) FBBezierCurve *curve;
 @property (readonly) FBBezierCurve *leftCurve;