compute initial winding from projected rays

src/pathops/SkPathOpsOp.cpp

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 #include "SkAddIntersections.h"
 #include "SkOpCoincidence.h"
 #include "SkOpEdgeBuilder.h"
 #include "SkPathOpsCommon.h"
@@ skipping 80 matching lines @@
             *chase.insert(0) = span;
        #else
             *chase.append() = span;
        #endif
             return first;
         }
     }
     return NULL;
 }
 
-static bool bridgeOp(SkTDArray<SkOpContour* >& contourList, const SkPathOp op,
+static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op,
         const int xorMask, const int xorOpMask, SkPathWriter* simple, SkChunkAlloc* allocator) {
-    bool firstContour = true;
     bool unsortable = false;
-    bool topUnsortable = false;
-    bool firstPass = true;
-    SkDPoint lastTopLeft;
-    SkDPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
     do {
-        SkOpSpanBase* start = NULL;
-        SkOpSpanBase* end = NULL;
-        bool topDone;
-        bool onlyVertical = false;
-        lastTopLeft = topLeft;
-        SkOpSegment* current = FindSortableTop(contourList, firstPass, SkOpAngle::kBinarySingle,
-                &firstContour, &start, &end, &topLeft, &topUnsortable, &topDone, &onlyVertical,
-                allocator);
-        if (!current) {
-            if ((!topUnsortable || firstPass) && !topDone) {
-                SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
-                if (lastTopLeft.fX == SK_ScalarMin && lastTopLeft.fY == SK_ScalarMin) {
-                    if (firstPass) {
-                        firstPass = false;
-                    } else {
-                        break;
-                    }
-                }
-                topLeft.fX = topLeft.fY = SK_ScalarMin;
-                continue;
-            }
-            break;
-        } else if (onlyVertical) {
+        SkOpSpan* span = FindSortableTop(contourList);
+        if (!span) {
             break;
         }
-        firstPass = !topUnsortable || lastTopLeft != topLeft;
+        SkOpSegment* current = span->segment();
+        SkOpSpanBase* start = span->next();
+        SkOpSpanBase* end = span;
         SkTDArray<SkOpSpanBase*> chase;
         do {
             if (current->activeOp(start, end, xorMask, xorOpMask, op)) {
                 do {
                     if (!unsortable && current->done()) {
                         break;
                     }
                     SkASSERT(unsortable || !current->done());
                     SkOpSpanBase* nextStart = start;
                     SkOpSpanBase* nextEnd = end;
@@ skipping 107 matching lines @@
     fprintf(file, "    path.reset();\n");
     fprintf(file, "    path.setFillType((SkPath::FillType) %d);\n", two.getFillType());
     dump_path(file, two, false, true);
     fprintf(file, "    SkPath path2(path);\n");
     fprintf(file, "    testPathOp(reporter, path1, path2, (SkPathOp) %d, filename);\n", op);
     fprintf(file, "}\n");    
     fclose(file);
 }
 #endif
 
-bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
+bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result,
+        bool expectSuccess) {
     SkChunkAlloc allocator(4096);  // FIXME: add a constant expression here, tune
     SkOpContour contour;
+    SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
     SkOpCoincidence coincidence;
-    SkOpGlobalState globalState(&coincidence  SkDEBUGPARAMS(&contour));
+    SkOpGlobalState globalState(&coincidence, contourList);
 #if DEBUGGING_PATHOPS_FROM_HOST
     dump_op(one, two, op);
 #endif    
 #if 0 && DEBUG_SHOW_TEST_NAME
     char* debugName = DEBUG_FILENAME_STRING;
     if (debugName && debugName[0]) {
         SkPathOpsDebug::BumpTestName(debugName);
         SkPathOpsDebug::ShowPath(one, two, op, debugName);
     }
 #endif
     op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
     SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()]
             ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType;
     const SkPath* minuend = &one;
     const SkPath* subtrahend = &two;
     if (op == kReverseDifference_SkPathOp) {
         minuend = &two;
         subtrahend = &one;
         op = kDifference_SkPathOp;
     }
-#if DEBUG_SORT || DEBUG_SWAP_TOP
+#if DEBUG_SORT
     SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
 #endif
     // turn path into list of segments
     SkOpEdgeBuilder builder(*minuend, &contour, &allocator, &globalState);
     if (builder.unparseable()) {
         return false;
     }
     const int xorMask = builder.xorMask();
     builder.addOperand(*subtrahend);
     if (!builder.finish(&allocator)) {
         return false;
     }
 #if DEBUG_DUMP_SEGMENTS
     contour.dumpSegments(op);
 #endif
 
     const int xorOpMask = builder.xorMask();
-    SkTDArray<SkOpContour* > contourList;
-    MakeContourList(&contour, contourList, xorMask == kEvenOdd_PathOpsMask,
-            xorOpMask == kEvenOdd_PathOpsMask);
-    SkOpContour** currentPtr = contourList.begin();
-    if (!currentPtr) {
+    if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask,
+            xorOpMask == kEvenOdd_PathOpsMask)) {
         result->reset();
         result->setFillType(fillType);
         return true;
     }
-    if ((*currentPtr)->count() == 0) {
-        SkASSERT((*currentPtr)->next() == NULL);
-        result->reset();
-        result->setFillType(fillType);
-        return true;
-    }
-    SkOpContour** listEnd = contourList.end();
     // find all intersections between segments
+    SkOpContour* current = contourList;
     do {
-        SkOpContour** nextPtr = currentPtr;
-        SkOpContour* current = *currentPtr++;
-        SkOpContour* next;
-        do {
-            next = *nextPtr++;
-        } while (AddIntersectTs(current, next, &coincidence, &allocator) && nextPtr != listEnd);
-    } while (currentPtr != listEnd);
+        SkOpContour* next = current;
+        while (AddIntersectTs(current, next, &coincidence, &allocator)
+                && (next = next->next()))
+            ;
+    } while ((current = current->next()));
 #if DEBUG_VALIDATE
     globalState.setPhase(SkOpGlobalState::kWalking);
 #endif
-    // eat through coincident edges
-    if (!HandleCoincidence(&contourList, &coincidence, &allocator, &globalState)) {
+    if (!HandleCoincidence(contourList, &coincidence, &allocator)) {
         return false;
     }
     // construct closed contours
     result->reset();
     result->setFillType(fillType);
     SkPathWriter wrapper(*result);
     bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper, &allocator);
     {  // if some edges could not be resolved, assemble remaining fragments
         SkPath temp;
         temp.setFillType(fillType);
         SkPathWriter assembled(temp);
         Assemble(wrapper, &assembled);
         *result = *assembled.nativePath();
         result->setFillType(fillType);
     }
     return true;
 }
+
+bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
+    return OpDebug(one, two, op, result, true);
+}