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 } 209
