Upstream version 7.36.149.0

[platform/framework/web/crosswalk.git] / src / third_party / skia / src / pathops / SkPathOpsOp.cpp

diff --git a/src/third_party/skia/src/pathops/SkPathOpsOp.cpp b/src/third_party/skia/src/pathops/SkPathOpsOp.cpp
index 1b7b03b..5af4753 100644 (file)
--- a/src/third_party/skia/src/pathops/SkPathOpsOp.cpp
+++ b/src/third_party/skia/src/pathops/SkPathOpsOp.cpp
@@ -9,23 +9,23 @@
 #include "SkPathOpsCommon.h"
 #include "SkPathWriter.h"
 
-// FIXME: this and find chase should be merge together, along with
-// other code that walks winding in angles
-// OPTIMIZATION: Probably, the walked winding should be rolled into the angle structure
-// so it isn't duplicated by walkers like this one
-static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int& nextEnd) {
+static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int* tIndex, int* endIndex) {
     while (chase.count()) {
         SkOpSpan* span;
         chase.pop(&span);
         const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
         SkOpSegment* segment = backPtr.fOther;
-        nextStart = backPtr.fOtherIndex;
-        SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
-        int done = 0;
-        if (segment->activeAngle(nextStart, &done, &angles)) {
-            SkOpAngle* last = angles.end() - 1;
-            nextStart = last->start();
-            nextEnd = last->end();
+        *tIndex = backPtr.fOtherIndex;
+        bool sortable = true;
+        bool done = true;
+        *endIndex = -1;
+        if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done,
+                &sortable)) {
+            if (last->unorderable()) {
+                continue;
+            }
+            *tIndex = last->start();
+            *endIndex = last->end();
    #if TRY_ROTATE
             *chase.insert(0) = span;
    #else
@@ -33,52 +33,31 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int
    #endif
             return last->segment();
         }
-        if (done == angles.count()) {
+        if (done) {
             continue;
         }
-        SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
-        bool sortable = SkOpSegment::SortAngles(angles, &sorted,
-                SkOpSegment::kMayBeUnordered_SortAngleKind);
-        int angleCount = sorted.count();
-#if DEBUG_SORT
-        sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, sortable);
-#endif
         if (!sortable) {
             continue;
         }
         // find first angle, initialize winding to computed fWindSum
-        int firstIndex = -1;
-        const SkOpAngle* angle;
-        bool foundAngle = true;
+        const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex);
+        const SkOpAngle* firstAngle = angle;
+        SkDEBUGCODE(bool loop = false);
+        int winding;
         do {
-            ++firstIndex;
-            if (firstIndex >= angleCount) {
-                foundAngle = false;
-                break;
-            }
-            angle = sorted[firstIndex];
+            angle = angle->next();
+            SkASSERT(angle != firstAngle || !loop);
+            SkDEBUGCODE(loop |= angle == firstAngle);
             segment = angle->segment();
-        } while (segment->windSum(angle) == SK_MinS32);
-        if (!foundAngle) {
-            continue;
-        }
-    #if DEBUG_SORT
-        segment->debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
-    #endif
+            winding = segment->windSum(angle);
+        } while (winding == SK_MinS32);
         int sumMiWinding = segment->updateWindingReverse(angle);
         int sumSuWinding = segment->updateOppWindingReverse(angle);
         if (segment->operand()) {
             SkTSwap<int>(sumMiWinding, sumSuWinding);
         }
-        int nextIndex = firstIndex + 1;
-        int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
         SkOpSegment* first = NULL;
-        do {
-            SkASSERT(nextIndex != firstIndex);
-            if (nextIndex == angleCount) {
-                nextIndex = 0;
-            }
-            angle = sorted[nextIndex];
+        while ((angle = angle->next()) != firstAngle) {
             segment = angle->segment();
             int start = angle->start();
             int end = angle->end();
@@ -88,13 +67,13 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int
             if (!segment->done(angle)) {
                 if (!first) {
                     first = segment;
-                    nextStart = start;
-                    nextEnd = end;
+                    *tIndex = start;
+                    *endIndex = end;
                 }
                 (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
                     oppSumWinding, angle);
             }
-        } while (++nextIndex != lastIndex);
+        }
         if (first) {
        #if TRY_ROTATE
             *chase.insert(0) = span;
@@ -140,29 +119,36 @@ static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp o
     bool firstContour = true;
     bool unsortable = false;
     bool topUnsortable = false;
+    bool firstPass = true;
+    SkPoint lastTopLeft;
     SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
     do {
         int index, endIndex;
-        bool done;
+        bool topDone;
+        lastTopLeft = topLeft;
         SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kBinarySingle, &firstContour,
-                &index, &endIndex, &topLeft, &topUnsortable, &done);
+                &index, &endIndex, &topLeft, &topUnsortable, &topDone, firstPass);
         if (!current) {
-            if (topUnsortable || !done) {
-                topUnsortable = false;
+            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;
         }
+        firstPass = !topUnsortable || lastTopLeft != topLeft;
         SkTDArray<SkOpSpan*> chaseArray;
         do {
             if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) {
                 do {
                     if (!unsortable && current->done()) {
-            #if DEBUG_ACTIVE_SPANS
-                        DebugShowActiveSpans(contourList);
-            #endif
                         if (simple->isEmpty()) {
                             simple->init();
                         }
@@ -199,7 +185,6 @@ static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp o
                     if (!unsortable && !simple->isEmpty()) {
                         unsortable = current->checkSmall(min);
                     }
-                    SkASSERT(unsortable || simple->isEmpty());
                     if (!current->done(min)) {
                         current->addCurveTo(index, endIndex, simple, true);
                         current->markDoneBinary(min);
@@ -208,11 +193,13 @@ static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp o
                 simple->close();
             } else {
                 SkOpSpan* last = current->markAndChaseDoneBinary(index, endIndex);
-                if (last && !last->fLoop) {
+                if (last && !last->fChased && !last->fLoop) {
+                    last->fChased = true;
+                    SkASSERT(!SkPathOpsDebug::ChaseContains(chaseArray, last));
                     *chaseArray.append() = last;
                 }
             }
-            current = findChaseOp(chaseArray, index, endIndex);
+            current = findChaseOp(chaseArray, &index, &endIndex);
         #if DEBUG_ACTIVE_SPANS
             DebugShowActiveSpans(contourList);
         #endif
@@ -304,7 +291,9 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
     for (index = 0; index < contourList.count(); ++index) {
         total += contourList[index]->segments().count();
     }
-    HandleCoincidence(&contourList, total);
+    if (!HandleCoincidence(&contourList, total)) {
+        return false;
+    }
     // construct closed contours
     SkPathWriter wrapper(*result);
     bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper);