michael@0: /*
michael@0:  * Copyright 2012 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: #include "SkGeometry.h"
michael@0: #include "SkOpEdgeBuilder.h"
michael@0: #include "SkReduceOrder.h"
michael@0: 
michael@0: void SkOpEdgeBuilder::init() {
michael@0:     fCurrentContour = NULL;
michael@0:     fOperand = false;
michael@0:     fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
michael@0:             : kWinding_PathOpsMask;
michael@0: #ifdef SK_DEBUG
michael@0:     SkPathOpsDebug::gContourID = 0;
michael@0:     SkPathOpsDebug::gSegmentID = 0;
michael@0: #endif
michael@0:     fUnparseable = false;
michael@0:     fSecondHalf = preFetch();
michael@0: }
michael@0: 
michael@0: void SkOpEdgeBuilder::addOperand(const SkPath& path) {
michael@0:     SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb);
michael@0:     fPathVerbs.pop_back();
michael@0:     fPath = &path;
michael@0:     fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
michael@0:             : kWinding_PathOpsMask;
michael@0:     preFetch();
michael@0: }
michael@0: 
michael@0: bool SkOpEdgeBuilder::finish() {
michael@0:     if (fUnparseable || !walk()) {
michael@0:         return false;
michael@0:     }
michael@0:     complete();
michael@0:     if (fCurrentContour && !fCurrentContour->segments().count()) {
michael@0:         fContours.pop_back();
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) {
michael@0:     if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) {
michael@0:         fPathVerbs.push_back(SkPath::kLine_Verb);
michael@0:         fPathPts.push_back_n(1, &curveStart);
michael@0:     } else {
michael@0:         fPathPts[fPathPts.count() - 1] = curveStart;
michael@0:     }
michael@0:     fPathVerbs.push_back(SkPath::kClose_Verb);
michael@0: }
michael@0: 
michael@0: int SkOpEdgeBuilder::preFetch() {
michael@0:     if (!fPath->isFinite()) {
michael@0:         fUnparseable = true;
michael@0:         return 0;
michael@0:     }
michael@0:     SkAutoConicToQuads quadder;
michael@0:     const SkScalar quadderTol = SK_Scalar1 / 16;
michael@0:     SkPath::RawIter iter(*fPath);
michael@0:     SkPoint curveStart;
michael@0:     SkPoint curve[4];
michael@0:     SkPoint pts[4];
michael@0:     SkPath::Verb verb;
michael@0:     bool lastCurve = false;
michael@0:     do {
michael@0:         verb = iter.next(pts);
michael@0:         switch (verb) {
michael@0:             case SkPath::kMove_Verb:
michael@0:                 if (!fAllowOpenContours && lastCurve) {
michael@0:                     closeContour(curve[0], curveStart);
michael@0:                 }
michael@0:                 fPathVerbs.push_back(verb);
michael@0:                 fPathPts.push_back(pts[0]);
michael@0:                 curveStart = curve[0] = pts[0];
michael@0:                 lastCurve = false;
michael@0:                 continue;
michael@0:             case SkPath::kLine_Verb:
michael@0:                 if (SkDPoint::ApproximatelyEqual(curve[0], pts[1])) {
michael@0:                     uint8_t lastVerb = fPathVerbs.back();
michael@0:                     if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) {
michael@0:                         fPathPts.back() = pts[1];
michael@0:                     }
michael@0:                     continue;  // skip degenerate points
michael@0:                 }
michael@0:                 break;
michael@0:             case SkPath::kQuad_Verb:
michael@0:                 curve[1] = pts[1];
michael@0:                 curve[2] = pts[2];
michael@0:                 verb = SkReduceOrder::Quad(curve, pts);
michael@0:                 if (verb == SkPath::kMove_Verb) {
michael@0:                     continue;  // skip degenerate points
michael@0:                 }
michael@0:                 break;
michael@0:             case SkPath::kConic_Verb: {
michael@0:                     const SkPoint* quadPts = quadder.computeQuads(pts, iter.conicWeight(),
michael@0:                             quadderTol);
michael@0:                     const int nQuads = quadder.countQuads();
michael@0:                     for (int i = 0; i < nQuads; ++i) {
michael@0:                        fPathVerbs.push_back(SkPath::kQuad_Verb);
michael@0:                     }
michael@0:                     fPathPts.push_back_n(nQuads * 2, quadPts);
michael@0:                     curve[0] = quadPts[nQuads * 2 - 1];
michael@0:                     lastCurve = true;
michael@0:                 }
michael@0:                 continue;
michael@0:             case SkPath::kCubic_Verb:
michael@0:                 curve[1] = pts[1];
michael@0:                 curve[2] = pts[2];
michael@0:                 curve[3] = pts[3];
michael@0:                 verb = SkReduceOrder::Cubic(curve, pts);
michael@0:                 if (verb == SkPath::kMove_Verb) {
michael@0:                     continue;  // skip degenerate points
michael@0:                 }
michael@0:                 break;
michael@0:             case SkPath::kClose_Verb:
michael@0:                 closeContour(curve[0], curveStart);
michael@0:                 lastCurve = false;
michael@0:                 continue;
michael@0:             case SkPath::kDone_Verb:
michael@0:                 continue;
michael@0:         }
michael@0:         fPathVerbs.push_back(verb);
michael@0:         int ptCount = SkPathOpsVerbToPoints(verb);
michael@0:         fPathPts.push_back_n(ptCount, &pts[1]);
michael@0:         curve[0] = pts[ptCount];
michael@0:         lastCurve = true;
michael@0:     } while (verb != SkPath::kDone_Verb);
michael@0:     if (!fAllowOpenContours && lastCurve) {
michael@0:         closeContour(curve[0], curveStart);
michael@0:     }
michael@0:     fPathVerbs.push_back(SkPath::kDone_Verb);
michael@0:     return fPathVerbs.count() - 1;
michael@0: }
michael@0: 
michael@0: bool SkOpEdgeBuilder::close() {
michael@0:     complete();
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool SkOpEdgeBuilder::walk() {
michael@0:     uint8_t* verbPtr = fPathVerbs.begin();
michael@0:     uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
michael@0:     const SkPoint* pointsPtr = fPathPts.begin() - 1;
michael@0:     SkPath::Verb verb;
michael@0:     while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
michael@0:         if (verbPtr == endOfFirstHalf) {
michael@0:             fOperand = true;
michael@0:         }
michael@0:         verbPtr++;
michael@0:         switch (verb) {
michael@0:             case SkPath::kMove_Verb:
michael@0:                 if (fCurrentContour) {
michael@0:                     if (fAllowOpenContours) {
michael@0:                         complete();
michael@0:                     } else if (!close()) {
michael@0:                         return false;
michael@0:                     }
michael@0:                 }
michael@0:                 if (!fCurrentContour) {
michael@0:                     fCurrentContour = fContours.push_back_n(1);
michael@0:                     fCurrentContour->setOperand(fOperand);
michael@0:                     fCurrentContour->setXor(fXorMask[fOperand] == kEvenOdd_PathOpsMask);
michael@0:                 }
michael@0:                 pointsPtr += 1;
michael@0:                 continue;
michael@0:             case SkPath::kLine_Verb:
michael@0:                 fCurrentContour->addLine(pointsPtr);
michael@0:                 break;
michael@0:             case SkPath::kQuad_Verb:
michael@0:                 fCurrentContour->addQuad(pointsPtr);
michael@0:                 break;
michael@0:             case SkPath::kCubic_Verb:
michael@0:                 fCurrentContour->addCubic(pointsPtr);
michael@0:                 break;
michael@0:             case SkPath::kClose_Verb:
michael@0:                 SkASSERT(fCurrentContour);
michael@0:                 if (!close()) {
michael@0:                     return false;
michael@0:                 }
michael@0:                 continue;
michael@0:             default:
michael@0:                 SkDEBUGFAIL("bad verb");
michael@0:                 return false;
michael@0:         }
michael@0:         pointsPtr += SkPathOpsVerbToPoints(verb);
michael@0:         SkASSERT(fCurrentContour);
michael@0:     }
michael@0:    if (fCurrentContour && !fAllowOpenContours && !close()) {
michael@0:        return false;
michael@0:    }
michael@0:    return true;
michael@0: }