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