123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357 |
- /*
- * 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 "src/core/SkGeometry.h"
- #include "src/pathops/SkOpEdgeBuilder.h"
- #include "src/pathops/SkReduceOrder.h"
- void SkOpEdgeBuilder::init() {
- fOperand = false;
- fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
- : kWinding_PathOpsMask;
- fUnparseable = false;
- fSecondHalf = preFetch();
- }
- // 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;
- }
- }
- static bool can_add_curve(SkPath::Verb verb, SkPoint* curve) {
- if (SkPath::kMove_Verb == verb) {
- return false;
- }
- for (int index = 0; index <= SkPathOpsVerbToPoints(verb); ++index) {
- force_small_to_zero(&curve[index]);
- }
- return SkPath::kLine_Verb != verb || !SkDPoint::ApproximatelyEqual(curve[0], curve[1]);
- }
- void SkOpEdgeBuilder::addOperand(const SkPath& path) {
- SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb);
- fPathVerbs.pop();
- fPath = &path;
- fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
- : kWinding_PathOpsMask;
- preFetch();
- }
- bool SkOpEdgeBuilder::finish() {
- fOperand = false;
- if (fUnparseable || !walk()) {
- return false;
- }
- complete();
- SkOpContour* contour = fContourBuilder.contour();
- if (contour && !contour->count()) {
- fContoursHead->remove(contour);
- }
- return true;
- }
- void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) {
- if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) {
- *fPathVerbs.append() = SkPath::kLine_Verb;
- *fPathPts.append() = curveStart;
- } else {
- int verbCount = fPathVerbs.count();
- int ptsCount = fPathPts.count();
- if (SkPath::kLine_Verb == fPathVerbs[verbCount - 1]
- && fPathPts[ptsCount - 2] == curveStart) {
- fPathVerbs.pop();
- fPathPts.pop();
- } else {
- fPathPts[ptsCount - 1] = curveStart;
- }
- }
- *fPathVerbs.append() = SkPath::kClose_Verb;
- }
- int SkOpEdgeBuilder::preFetch() {
- if (!fPath->isFinite()) {
- fUnparseable = true;
- return 0;
- }
- 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.append() = verb;
- force_small_to_zero(&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.top();
- if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) {
- fPathPts.top() = curve[0] = 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:
- 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 (SkPath::kQuad_Verb == verb && 1 != iter.conicWeight()) {
- verb = SkPath::kConic_Verb;
- } else if (verb == SkPath::kMove_Verb) {
- continue; // skip degenerate points
- }
- break;
- 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.append() = verb;
- int ptCount = SkPathOpsVerbToPoints(verb);
- fPathPts.append(ptCount, &pts[1]);
- if (verb == SkPath::kConic_Verb) {
- *fWeights.append() = iter.conicWeight();
- }
- curve[0] = pts[ptCount];
- lastCurve = true;
- } while (verb != SkPath::kDone_Verb);
- if (!fAllowOpenContours && lastCurve) {
- closeContour(curve[0], curveStart);
- }
- *fPathVerbs.append() = SkPath::kDone_Verb;
- return fPathVerbs.count() - 1;
- }
- bool SkOpEdgeBuilder::close() {
- complete();
- return true;
- }
- bool SkOpEdgeBuilder::walk() {
- uint8_t* verbPtr = fPathVerbs.begin();
- uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
- SkPoint* pointsPtr = fPathPts.begin();
- SkScalar* weightPtr = fWeights.begin();
- SkPath::Verb verb;
- SkOpContour* contour = fContourBuilder.contour();
- int moveToPtrBump = 0;
- while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
- if (verbPtr == endOfFirstHalf) {
- fOperand = true;
- }
- verbPtr++;
- switch (verb) {
- case SkPath::kMove_Verb:
- if (contour && contour->count()) {
- if (fAllowOpenContours) {
- complete();
- } else if (!close()) {
- return false;
- }
- }
- if (!contour) {
- fContourBuilder.setContour(contour = fContoursHead->appendContour());
- }
- contour->init(fGlobalState, fOperand,
- fXorMask[fOperand] == kEvenOdd_PathOpsMask);
- pointsPtr += moveToPtrBump;
- moveToPtrBump = 1;
- continue;
- case SkPath::kLine_Verb:
- fContourBuilder.addLine(pointsPtr);
- break;
- case SkPath::kQuad_Verb:
- {
- SkVector v1 = pointsPtr[1] - pointsPtr[0];
- SkVector v2 = pointsPtr[2] - pointsPtr[1];
- if (v1.dot(v2) < 0) {
- SkPoint pair[5];
- if (SkChopQuadAtMaxCurvature(pointsPtr, pair) == 1) {
- goto addOneQuad;
- }
- if (!SkScalarsAreFinite(&pair[0].fX, SK_ARRAY_COUNT(pair) * 2)) {
- return false;
- }
- for (unsigned index = 0; index < SK_ARRAY_COUNT(pair); ++index) {
- force_small_to_zero(&pair[index]);
- }
- SkPoint cStorage[2][2];
- SkPath::Verb v1 = SkReduceOrder::Quad(&pair[0], cStorage[0]);
- SkPath::Verb v2 = SkReduceOrder::Quad(&pair[2], cStorage[1]);
- SkPoint* curve1 = v1 != SkPath::kLine_Verb ? &pair[0] : cStorage[0];
- SkPoint* curve2 = v2 != SkPath::kLine_Verb ? &pair[2] : cStorage[1];
- if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
- fContourBuilder.addCurve(v1, curve1);
- fContourBuilder.addCurve(v2, curve2);
- break;
- }
- }
- }
- addOneQuad:
- fContourBuilder.addQuad(pointsPtr);
- break;
- case SkPath::kConic_Verb: {
- SkVector v1 = pointsPtr[1] - pointsPtr[0];
- SkVector v2 = pointsPtr[2] - pointsPtr[1];
- SkScalar weight = *weightPtr++;
- if (v1.dot(v2) < 0) {
- // FIXME: max curvature for conics hasn't been implemented; use placeholder
- SkScalar maxCurvature = SkFindQuadMaxCurvature(pointsPtr);
- if (0 < maxCurvature && maxCurvature < 1) {
- SkConic conic(pointsPtr, weight);
- SkConic pair[2];
- if (!conic.chopAt(maxCurvature, pair)) {
- // if result can't be computed, use original
- fContourBuilder.addConic(pointsPtr, weight);
- break;
- }
- SkPoint cStorage[2][3];
- SkPath::Verb v1 = SkReduceOrder::Conic(pair[0], cStorage[0]);
- SkPath::Verb v2 = SkReduceOrder::Conic(pair[1], cStorage[1]);
- SkPoint* curve1 = v1 != SkPath::kLine_Verb ? pair[0].fPts : cStorage[0];
- SkPoint* curve2 = v2 != SkPath::kLine_Verb ? pair[1].fPts : cStorage[1];
- if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
- fContourBuilder.addCurve(v1, curve1, pair[0].fW);
- fContourBuilder.addCurve(v2, curve2, pair[1].fW);
- break;
- }
- }
- }
- fContourBuilder.addConic(pointsPtr, weight);
- } break;
- case SkPath::kCubic_Verb:
- {
- // Split complex cubics (such as self-intersecting curves or
- // ones with difficult curvature) in two before proceeding.
- // This can be required for intersection to succeed.
- SkScalar splitT[3];
- int breaks = SkDCubic::ComplexBreak(pointsPtr, splitT);
- if (!breaks) {
- fContourBuilder.addCubic(pointsPtr);
- break;
- }
- SkASSERT(breaks <= (int) SK_ARRAY_COUNT(splitT));
- struct Splitsville {
- double fT[2];
- SkPoint fPts[4];
- SkPoint fReduced[4];
- SkPath::Verb fVerb;
- bool fCanAdd;
- } splits[4];
- SkASSERT(SK_ARRAY_COUNT(splits) == SK_ARRAY_COUNT(splitT) + 1);
- SkTQSort(splitT, &splitT[breaks - 1]);
- for (int index = 0; index <= breaks; ++index) {
- Splitsville* split = &splits[index];
- split->fT[0] = index ? splitT[index - 1] : 0;
- split->fT[1] = index < breaks ? splitT[index] : 1;
- SkDCubic part = SkDCubic::SubDivide(pointsPtr, split->fT[0], split->fT[1]);
- if (!part.toFloatPoints(split->fPts)) {
- return false;
- }
- split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced);
- SkPoint* curve = SkPath::kCubic_Verb == verb
- ? split->fPts : split->fReduced;
- split->fCanAdd = can_add_curve(split->fVerb, curve);
- }
- for (int index = 0; index <= breaks; ++index) {
- Splitsville* split = &splits[index];
- if (!split->fCanAdd) {
- continue;
- }
- int prior = index;
- while (prior > 0 && !splits[prior - 1].fCanAdd) {
- --prior;
- }
- if (prior < index) {
- split->fT[0] = splits[prior].fT[0];
- split->fPts[0] = splits[prior].fPts[0];
- }
- int next = index;
- int breakLimit = SkTMin(breaks, (int) SK_ARRAY_COUNT(splits) - 1);
- while (next < breakLimit && !splits[next + 1].fCanAdd) {
- ++next;
- }
- if (next > index) {
- split->fT[1] = splits[next].fT[1];
- split->fPts[3] = splits[next].fPts[3];
- }
- if (prior < index || next > index) {
- split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced);
- }
- SkPoint* curve = SkPath::kCubic_Verb == split->fVerb
- ? split->fPts : split->fReduced;
- if (!can_add_curve(split->fVerb, curve)) {
- return false;
- }
- fContourBuilder.addCurve(split->fVerb, curve);
- }
- }
- break;
- case SkPath::kClose_Verb:
- SkASSERT(contour);
- if (!close()) {
- return false;
- }
- contour = nullptr;
- continue;
- default:
- SkDEBUGFAIL("bad verb");
- return false;
- }
- SkASSERT(contour);
- if (contour->count()) {
- contour->debugValidate();
- }
- pointsPtr += SkPathOpsVerbToPoints(verb);
- }
- fContourBuilder.flush();
- if (contour && contour->count() &&!fAllowOpenContours && !close()) {
- return false;
- }
- return true;
- }
|