src/third_party/skia/src/pathops/SkOpEdgeBuilder.cpp

   1 /*
   2  * Copyright 2012 Google Inc.
   3  *
   4  * Use of this source code is governed by a BSD-style license that can be
   5  * found in the LICENSE file.
   6  */
   7 #include "SkGeometry.h"
   8 #include "SkOpEdgeBuilder.h"
   9 #include "SkReduceOrder.h"
  10
  11 void SkOpEdgeBuilder::init() {
  12     fCurrentContour = NULL;
  13     fOperand = false;
  14     fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
  15             : kWinding_PathOpsMask;
  16     fUnparseable = false;
  17     fSecondHalf = preFetch();
  18 }
  19
  20 void SkOpEdgeBuilder::addOperand(const SkPath& path) {
  21     SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb);
  22     fPathVerbs.pop_back();
  23     fPath = &path;
  24     fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
  25             : kWinding_PathOpsMask;
  26     preFetch();
  27 }
  28
  29 bool SkOpEdgeBuilder::finish() {
  30     if (fUnparseable || !walk()) {
  31         return false;
  32     }
  33     complete();
  34     if (fCurrentContour && !fCurrentContour->segments().count()) {
  35         fContours.pop_back();
  36     }
  37     return true;
  38 }
  39
  40 void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) {
  41     if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) {
  42         fPathVerbs.push_back(SkPath::kLine_Verb);
  43         fPathPts.push_back_n(1, &curveStart);
  44     } else {
  45         fPathPts[fPathPts.count() - 1] = curveStart;
  46     }
  47     fPathVerbs.push_back(SkPath::kClose_Verb);
  48 }
  49
  50 // very tiny points cause numerical instability : don't allow them
  51 static void force_small_to_zero(SkPoint* pt) {
  52     if (SkScalarAbs(pt->fX) < FLT_EPSILON_ORDERABLE_ERR) {
  53         pt->fX = 0;
  54     }
  55     if (SkScalarAbs(pt->fY) < FLT_EPSILON_ORDERABLE_ERR) {
  56         pt->fY = 0;
  57     }
  58 }
  59
  60
  61 int SkOpEdgeBuilder::preFetch() {
  62     if (!fPath->isFinite()) {
  63         fUnparseable = true;
  64         return 0;
  65     }
  66     SkAutoConicToQuads quadder;
  67     const SkScalar quadderTol = SK_Scalar1 / 16;
  68     SkPath::RawIter iter(*fPath);
  69     SkPoint curveStart;
  70     SkPoint curve[4];
  71     SkPoint pts[4];
  72     SkPath::Verb verb;
  73     bool lastCurve = false;
  74     do {
  75         verb = iter.next(pts);
  76         switch (verb) {
  77             case SkPath::kMove_Verb:
  78                 if (!fAllowOpenContours && lastCurve) {
  79                     closeContour(curve[0], curveStart);
  80                 }
  81                 fPathVerbs.push_back(verb);
  82                 force_small_to_zero(&pts[0]);
  83                 fPathPts.push_back(pts[0]);
  84                 curveStart = curve[0] = pts[0];
  85                 lastCurve = false;
  86                 continue;
  87             case SkPath::kLine_Verb:
  88                 force_small_to_zero(&pts[1]);
  89                 if (SkDPoint::ApproximatelyEqual(curve[0], pts[1])) {
  90                     uint8_t lastVerb = fPathVerbs.back();
  91                     if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) {
  92                         fPathPts.back() = pts[1];
  93                     }
  94                     continue;  // skip degenerate points
  95                 }
  96                 break;
  97             case SkPath::kQuad_Verb:
  98                 force_small_to_zero(&pts[1]);
  99                 force_small_to_zero(&pts[2]);
 100                 curve[1] = pts[1];
 101                 curve[2] = pts[2];
 102                 verb = SkReduceOrder::Quad(curve, pts);
 103                 if (verb == SkPath::kMove_Verb) {
 104                     continue;  // skip degenerate points
 105                 }
 106                 break;
 107             case SkPath::kConic_Verb: {
 108                     const SkPoint* quadPts = quadder.computeQuads(pts, iter.conicWeight(),
 109                             quadderTol);
 110                     const int nQuads = quadder.countQuads();
 111                     for (int i = 0; i < nQuads; ++i) {
 112                        fPathVerbs.push_back(SkPath::kQuad_Verb);
 113                     }
 114                     fPathPts.push_back_n(nQuads * 2, quadPts);
 115                     curve[0] = quadPts[nQuads * 2 - 1];
 116                     lastCurve = true;
 117                 }
 118                 continue;
 119             case SkPath::kCubic_Verb:
 120                 force_small_to_zero(&pts[1]);
 121                 force_small_to_zero(&pts[2]);
 122                 force_small_to_zero(&pts[3]);
 123                 curve[1] = pts[1];
 124                 curve[2] = pts[2];
 125                 curve[3] = pts[3];
 126                 verb = SkReduceOrder::Cubic(curve, pts);
 127                 if (verb == SkPath::kMove_Verb) {
 128                     continue;  // skip degenerate points
 129                 }
 130                 break;
 131             case SkPath::kClose_Verb:
 132                 closeContour(curve[0], curveStart);
 133                 lastCurve = false;
 134                 continue;
 135             case SkPath::kDone_Verb:
 136                 continue;
 137         }
 138         fPathVerbs.push_back(verb);
 139         int ptCount = SkPathOpsVerbToPoints(verb);
 140         fPathPts.push_back_n(ptCount, &pts[1]);
 141         curve[0] = pts[ptCount];
 142         lastCurve = true;
 143     } while (verb != SkPath::kDone_Verb);
 144     if (!fAllowOpenContours && lastCurve) {
 145         closeContour(curve[0], curveStart);
 146     }
 147     fPathVerbs.push_back(SkPath::kDone_Verb);
 148     return fPathVerbs.count() - 1;
 149 }
 150
 151 bool SkOpEdgeBuilder::close() {
 152     complete();
 153     return true;
 154 }
 155
 156 bool SkOpEdgeBuilder::walk() {
 157     uint8_t* verbPtr = fPathVerbs.begin();
 158     uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
 159     const SkPoint* pointsPtr = fPathPts.begin() - 1;
 160     SkPath::Verb verb;
 161     while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
 162         if (verbPtr == endOfFirstHalf) {
 163             fOperand = true;
 164         }
 165         verbPtr++;
 166         switch (verb) {
 167             case SkPath::kMove_Verb:
 168                 if (fCurrentContour) {
 169                     if (fAllowOpenContours) {
 170                         complete();
 171                     } else if (!close()) {
 172                         return false;
 173                     }
 174                 }
 175                 if (!fCurrentContour) {
 176                     fCurrentContour = fContours.push_back_n(1);
 177                     fCurrentContour->setOperand(fOperand);
 178                     fCurrentContour->setXor(fXorMask[fOperand] == kEvenOdd_PathOpsMask);
 179                 }
 180                 pointsPtr += 1;
 181                 continue;
 182             case SkPath::kLine_Verb:
 183                 fCurrentContour->addLine(pointsPtr);
 184                 break;
 185             case SkPath::kQuad_Verb:
 186                 fCurrentContour->addQuad(pointsPtr);
 187                 break;
 188             case SkPath::kCubic_Verb:
 189                 fCurrentContour->addCubic(pointsPtr);
 190                 break;
 191             case SkPath::kClose_Verb:
 192                 SkASSERT(fCurrentContour);
 193                 if (!close()) {
 194                     return false;
 195                 }
 196                 continue;
 197             default:
 198                 SkDEBUGFAIL("bad verb");
 199                 return false;
 200         }
 201         pointsPtr += SkPathOpsVerbToPoints(verb);
 202         SkASSERT(fCurrentContour);
 203     }
 204    if (fCurrentContour && !fAllowOpenContours && !close()) {
 205        return false;
 206    }
 207    return true;
 208 }