pathops version two

src/pathops/SkOpEdgeBuilder.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 "SkGeometry.h"
 #include "SkOpEdgeBuilder.h"
 #include "SkReduceOrder.h"
 
 void SkOpEdgeBuilder::init() {
-    fCurrentContour = NULL;
+    fCurrentContour = fContoursHead;
     fOperand = false;
     fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
             : kWinding_PathOpsMask;
     fUnparseable = false;
     fSecondHalf = preFetch();
 }
 
 void SkOpEdgeBuilder::addOperand(const SkPath& path) {
     SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb);
-    fPathVerbs.pop_back();
+    fPathVerbs.pop();
     fPath = &path;
     fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
             : kWinding_PathOpsMask;
     preFetch();
 }
 
-bool SkOpEdgeBuilder::finish() {
-    if (fUnparseable || !walk()) {
+int SkOpEdgeBuilder::count() const {
+    SkOpContour* contour = fContoursHead;
+    int count = 0;
+    while (contour) {
+        count += contour->count() > 0;
+        contour = contour->next();
+    }
+    return count;
+}
+
+bool SkOpEdgeBuilder::finish(SkChunkAlloc* allocator) {
+    fOperand = false;
+    if (fUnparseable || !walk(allocator)) {
         return false;
     }
     complete();
-    if (fCurrentContour && !fCurrentContour->segments().count()) {
-        fContours.pop_back();
+    if (fCurrentContour && !fCurrentContour->count()) {
+        fContoursHead->remove(fCurrentContour);
     }
     return true;
 }
 
 void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) {
     if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) {
-        fPathVerbs.push_back(SkPath::kLine_Verb);
-        fPathPts.push_back_n(1, &curveStart);
+        *fPathVerbs.append() = SkPath::kLine_Verb;
+        *fPathPts.append() = curveStart;
     } else {
         fPathPts[fPathPts.count() - 1] = curveStart;
     }
-    fPathVerbs.push_back(SkPath::kClose_Verb);
+    *fPathVerbs.append() = SkPath::kClose_Verb;
 }
 
 // very tiny points cause numerical instability : don't allow them
 static void force_small_to_zero(SkPoint* pt) {
     if (SkScalarAbs(pt->fX) < FLT_EPSILON_ORDERABLE_ERR) {
         pt->fX = 0;
     }
     if (SkScalarAbs(pt->fY) < FLT_EPSILON_ORDERABLE_ERR) {
         pt->fY = 0;
     }
 }
 
-
 int SkOpEdgeBuilder::preFetch() {
     if (!fPath->isFinite()) {
         fUnparseable = true;
         return 0;
     }
     SkAutoConicToQuads quadder;
     const SkScalar quadderTol = SK_Scalar1 / 16;
     SkPath::RawIter iter(*fPath);
     SkPoint curveStart;
     SkPoint curve[4];
     SkPoint pts[4];
     SkPath::Verb verb;
     bool lastCurve = false;
     do {
         verb = iter.next(pts);
         switch (verb) {
             case SkPath::kMove_Verb:
                 if (!fAllowOpenContours && lastCurve) {
                     closeContour(curve[0], curveStart);
                 }
-                fPathVerbs.push_back(verb);
+                *fPathVerbs.append() = verb;
                 force_small_to_zero(&pts[0]);
-                fPathPts.push_back(pts[0]);
+                *fPathPts.append() = pts[0];
                 curveStart = curve[0] = pts[0];
                 lastCurve = false;
                 continue;
             case SkPath::kLine_Verb:
                 force_small_to_zero(&pts[1]);
                 if (SkDPoint::ApproximatelyEqual(curve[0], pts[1])) {
-                    uint8_t lastVerb = fPathVerbs.back();
+                    uint8_t lastVerb = fPathVerbs.top();
                     if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) {
-                        fPathPts.back() = pts[1];
+                        fPathPts.top() = pts[1];
                     }
                     continue;  // skip degenerate points
                 }
                 break;
             case SkPath::kQuad_Verb:
                 force_small_to_zero(&pts[1]);
                 force_small_to_zero(&pts[2]);
                 curve[1] = pts[1];
                 curve[2] = pts[2];
                 verb = SkReduceOrder::Quad(curve, pts);
                 if (verb == SkPath::kMove_Verb) {
                     continue;  // skip degenerate points
                 }
                 break;
             case SkPath::kConic_Verb: {
                     const SkPoint* quadPts = quadder.computeQuads(pts, iter.conicWeight(),
                             quadderTol);
                     const int nQuads = quadder.countQuads();
                     for (int i = 0; i < nQuads; ++i) {
-                       fPathVerbs.push_back(SkPath::kQuad_Verb);
+                       *fPathVerbs.append() = SkPath::kQuad_Verb;
                     }
-                    fPathPts.push_back_n(nQuads * 2, &quadPts[1]);
+                    fPathPts.append(nQuads * 2, &quadPts[1]);
                     curve[0] = pts[2];
                     lastCurve = true;
                 }
                 continue;
             case SkPath::kCubic_Verb:
                 force_small_to_zero(&pts[1]);
                 force_small_to_zero(&pts[2]);
                 force_small_to_zero(&pts[3]);
                 curve[1] = pts[1];
                 curve[2] = pts[2];
                 curve[3] = pts[3];
                 verb = SkReduceOrder::Cubic(curve, pts);
                 if (verb == SkPath::kMove_Verb) {
                     continue;  // skip degenerate points
                 }
                 break;
             case SkPath::kClose_Verb:
                 closeContour(curve[0], curveStart);
                 lastCurve = false;
                 continue;
             case SkPath::kDone_Verb:
                 continue;
         }
-        fPathVerbs.push_back(verb);
+        *fPathVerbs.append() = verb;
         int ptCount = SkPathOpsVerbToPoints(verb);
-        fPathPts.push_back_n(ptCount, &pts[1]);
+        fPathPts.append(ptCount, &pts[1]);
         curve[0] = pts[ptCount];
         lastCurve = true;
     } while (verb != SkPath::kDone_Verb);
     if (!fAllowOpenContours && lastCurve) {
         closeContour(curve[0], curveStart);
     }
-    fPathVerbs.push_back(SkPath::kDone_Verb);
+    *fPathVerbs.append() = SkPath::kDone_Verb;
     return fPathVerbs.count() - 1;
 }
 
 bool SkOpEdgeBuilder::close() {
     complete();
     return true;
 }
 
-bool SkOpEdgeBuilder::walk() {
+bool SkOpEdgeBuilder::walk(SkChunkAlloc* allocator) {
     uint8_t* verbPtr = fPathVerbs.begin();
     uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
-    const SkPoint* pointsPtr = fPathPts.begin() - 1;
+    SkPoint* pointsPtr = fPathPts.begin() - 1;
     SkPath::Verb verb;
     while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
         if (verbPtr == endOfFirstHalf) {
             fOperand = true;
         }
         verbPtr++;
         switch (verb) {
             case SkPath::kMove_Verb:
-                if (fCurrentContour) {
+                if (fCurrentContour && fCurrentContour->count()) {
                     if (fAllowOpenContours) {
                         complete();
                     } else if (!close()) {
                         return false;
                     }
                 }
                 if (!fCurrentContour) {
-                    fCurrentContour = fContours.push_back_n(1);
-                    fCurrentContour->setOperand(fOperand);
-                    fCurrentContour->setXor(fXorMask[fOperand] == kEvenOdd_PathOpsMask);
+                    fCurrentContour = fContoursHead->appendContour(allocator);
                 }
+                fCurrentContour->init(fGlobalState, fOperand,
+                    fXorMask[fOperand] == kEvenOdd_PathOpsMask);
                 pointsPtr += 1;
                 continue;
             case SkPath::kLine_Verb:
-                fCurrentContour->addLine(pointsPtr);
+                fCurrentContour->addLine(pointsPtr, fAllocator);
                 break;
             case SkPath::kQuad_Verb:
-                fCurrentContour->addQuad(pointsPtr);
+                fCurrentContour->addQuad(pointsPtr, fAllocator);
                 break;
-            case SkPath::kCubic_Verb:
-                fCurrentContour->addCubic(pointsPtr);
-                break;
+            case SkPath::kCubic_Verb: {
+                // split self-intersecting cubics in two before proceeding
+                // if the cubic is convex, it doesn't self intersect.
+                SkScalar loopT;
+                if (SkDCubic::ComplexBreak(pointsPtr, &loopT)) {
+                    SkPoint cubicPair[7]; 
+                    SkChopCubicAt(pointsPtr, cubicPair, loopT);
+                    SkPoint cStorage[2][4];
+                    SkPath::Verb v1 = SkReduceOrder::Cubic(&cubicPair[0], cStorage[0]);
+                    SkPath::Verb v2 = SkReduceOrder::Cubic(&cubicPair[3], cStorage[1]);
+                    if (v1 != SkPath::kMove_Verb && v2 != SkPath::kMove_Verb) {
+                        SkPoint* curve1 = v1 == SkPath::kCubic_Verb ? &cubicPair[0] : cStorage[0];
+                        SkPoint* curve2 = v2 == SkPath::kCubic_Verb ? &cubicPair[3] : cStorage[1];
+                        for (size_t index = 0; index < SK_ARRAY_COUNT(curve1); ++index) {
+                            force_small_to_zero(&curve1[index]);
+                            force_small_to_zero(&curve2[index]);
+                        }
+                        fCurrentContour->addCurve(v1, curve1, fAllocator);
+                        fCurrentContour->addCurve(v2, curve2, fAllocator);
+                    } else {
+                        fCurrentContour->addCubic(pointsPtr, fAllocator);
+                    }
+                } else {
+                    fCurrentContour->addCubic(pointsPtr, fAllocator);
+                }
+                } break;
             case SkPath::kClose_Verb:
                 SkASSERT(fCurrentContour);
                 if (!close()) {
                     return false;
                 }
                 continue;
             default:
                 SkDEBUGFAIL("bad verb");
                 return false;
         }
+        SkASSERT(fCurrentContour);
+        fCurrentContour->debugValidate();
         pointsPtr += SkPathOpsVerbToPoints(verb);
-        SkASSERT(fCurrentContour);
     }
-   if (fCurrentContour && !fAllowOpenContours && !close()) {
+   if (fCurrentContour && fCurrentContour->count() &&!fAllowOpenContours && !close()) {
        return false;
    }
    return true;
 }