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 fOperand = false; 13 fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask 14 : kWinding_PathOpsMask; 15 fUnparseable = false; 16 fSecondHalf = preFetch(); 17 } 18 19 // very tiny points cause numerical instability : don't allow them 20 static void force_small_to_zero(SkPoint* pt) { 21 if (SkScalarAbs(pt->fX) < FLT_EPSILON_ORDERABLE_ERR) { 22 pt->fX = 0; 23 } 24 if (SkScalarAbs(pt->fY) < FLT_EPSILON_ORDERABLE_ERR) { 25 pt->fY = 0; 26 } 27 } 28 29 static bool can_add_curve(SkPath::Verb verb, SkPoint* curve) { 30 if (SkPath::kMove_Verb == verb) { 31 return false; 32 } 33 for (int index = 0; index <= SkPathOpsVerbToPoints(verb); ++index) { 34 force_small_to_zero(&curve[index]); 35 } 36 return SkPath::kLine_Verb != verb || !SkDPoint::ApproximatelyEqual(curve[0], curve[1]); 37 } 38 39 void SkOpEdgeBuilder::addOperand(const SkPath& path) { 40 SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb); 41 fPathVerbs.pop(); 42 fPath = &path; 43 fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask 44 : kWinding_PathOpsMask; 45 preFetch(); 46 } 47 48 bool SkOpEdgeBuilder::finish() { 49 fOperand = false; 50 if (fUnparseable || !walk()) { 51 return false; 52 } 53 complete(); 54 SkOpContour* contour = fContourBuilder.contour(); 55 if (contour && !contour->count()) { 56 fContoursHead->remove(contour); 57 } 58 return true; 59 } 60 61 void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) { 62 if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) { 63 *fPathVerbs.append() = SkPath::kLine_Verb; 64 *fPathPts.append() = curveStart; 65 } else { 66 int verbCount = fPathVerbs.count(); 67 int ptsCount = fPathPts.count(); 68 if (SkPath::kLine_Verb == fPathVerbs[verbCount - 1] 69 && fPathPts[ptsCount - 2] == curveStart) { 70 fPathVerbs.pop(); 71 fPathPts.pop(); 72 } else { 73 fPathPts[ptsCount - 1] = curveStart; 74 } 75 } 76 *fPathVerbs.append() = SkPath::kClose_Verb; 77 } 78 79 int SkOpEdgeBuilder::preFetch() { 80 if (!fPath->isFinite()) { 81 fUnparseable = true; 82 return 0; 83 } 84 SkPath::RawIter iter(*fPath); 85 SkPoint curveStart; 86 SkPoint curve[4]; 87 SkPoint pts[4]; 88 SkPath::Verb verb; 89 bool lastCurve = false; 90 do { 91 verb = iter.next(pts); 92 switch (verb) { 93 case SkPath::kMove_Verb: 94 if (!fAllowOpenContours && lastCurve) { 95 closeContour(curve[0], curveStart); 96 } 97 *fPathVerbs.append() = verb; 98 force_small_to_zero(&pts[0]); 99 *fPathPts.append() = pts[0]; 100 curveStart = curve[0] = pts[0]; 101 lastCurve = false; 102 continue; 103 case SkPath::kLine_Verb: 104 force_small_to_zero(&pts[1]); 105 if (SkDPoint::ApproximatelyEqual(curve[0], pts[1])) { 106 uint8_t lastVerb = fPathVerbs.top(); 107 if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) { 108 fPathPts.top() = curve[0] = pts[1]; 109 } 110 continue; // skip degenerate points 111 } 112 break; 113 case SkPath::kQuad_Verb: 114 force_small_to_zero(&pts[1]); 115 force_small_to_zero(&pts[2]); 116 curve[1] = pts[1]; 117 curve[2] = pts[2]; 118 verb = SkReduceOrder::Quad(curve, pts); 119 if (verb == SkPath::kMove_Verb) { 120 continue; // skip degenerate points 121 } 122 break; 123 case SkPath::kConic_Verb: 124 force_small_to_zero(&pts[1]); 125 force_small_to_zero(&pts[2]); 126 curve[1] = pts[1]; 127 curve[2] = pts[2]; 128 verb = SkReduceOrder::Quad(curve, pts); 129 if (SkPath::kQuad_Verb == verb && 1 != iter.conicWeight()) { 130 verb = SkPath::kConic_Verb; 131 } else if (verb == SkPath::kMove_Verb) { 132 continue; // skip degenerate points 133 } 134 break; 135 case SkPath::kCubic_Verb: 136 force_small_to_zero(&pts[1]); 137 force_small_to_zero(&pts[2]); 138 force_small_to_zero(&pts[3]); 139 curve[1] = pts[1]; 140 curve[2] = pts[2]; 141 curve[3] = pts[3]; 142 verb = SkReduceOrder::Cubic(curve, pts); 143 if (verb == SkPath::kMove_Verb) { 144 continue; // skip degenerate points 145 } 146 break; 147 case SkPath::kClose_Verb: 148 closeContour(curve[0], curveStart); 149 lastCurve = false; 150 continue; 151 case SkPath::kDone_Verb: 152 continue; 153 } 154 *fPathVerbs.append() = verb; 155 int ptCount = SkPathOpsVerbToPoints(verb); 156 fPathPts.append(ptCount, &pts[1]); 157 if (verb == SkPath::kConic_Verb) { 158 *fWeights.append() = iter.conicWeight(); 159 } 160 curve[0] = pts[ptCount]; 161 lastCurve = true; 162 } while (verb != SkPath::kDone_Verb); 163 if (!fAllowOpenContours && lastCurve) { 164 closeContour(curve[0], curveStart); 165 } 166 *fPathVerbs.append() = SkPath::kDone_Verb; 167 return fPathVerbs.count() - 1; 168 } 169 170 bool SkOpEdgeBuilder::close() { 171 complete(); 172 return true; 173 } 174 175 bool SkOpEdgeBuilder::walk() { 176 uint8_t* verbPtr = fPathVerbs.begin(); 177 uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf]; 178 SkPoint* pointsPtr = fPathPts.begin(); 179 SkScalar* weightPtr = fWeights.begin(); 180 SkPath::Verb verb; 181 SkOpContour* contour = fContourBuilder.contour(); 182 int moveToPtrBump = 0; 183 while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) { 184 if (verbPtr == endOfFirstHalf) { 185 fOperand = true; 186 } 187 verbPtr++; 188 switch (verb) { 189 case SkPath::kMove_Verb: 190 if (contour && contour->count()) { 191 if (fAllowOpenContours) { 192 complete(); 193 } else if (!close()) { 194 return false; 195 } 196 } 197 if (!contour) { 198 fContourBuilder.setContour(contour = fContoursHead->appendContour()); 199 } 200 contour->init(fGlobalState, fOperand, 201 fXorMask[fOperand] == kEvenOdd_PathOpsMask); 202 pointsPtr += moveToPtrBump; 203 moveToPtrBump = 1; 204 continue; 205 case SkPath::kLine_Verb: 206 fContourBuilder.addLine(pointsPtr); 207 break; 208 case SkPath::kQuad_Verb: 209 { 210 SkVector v1 = pointsPtr[1] - pointsPtr[0]; 211 SkVector v2 = pointsPtr[2] - pointsPtr[1]; 212 if (v1.dot(v2) < 0) { 213 SkPoint pair[5]; 214 if (SkChopQuadAtMaxCurvature(pointsPtr, pair) == 1) { 215 goto addOneQuad; 216 } 217 if (!SkScalarsAreFinite(&pair[0].fX, SK_ARRAY_COUNT(pair) * 2)) { 218 return false; 219 } 220 for (unsigned index = 0; index < SK_ARRAY_COUNT(pair); ++index) { 221 force_small_to_zero(&pair[index]); 222 } 223 SkPoint cStorage[2][2]; 224 SkPath::Verb v1 = SkReduceOrder::Quad(&pair[0], cStorage[0]); 225 SkPath::Verb v2 = SkReduceOrder::Quad(&pair[2], cStorage[1]); 226 SkPoint* curve1 = v1 != SkPath::kLine_Verb ? &pair[0] : cStorage[0]; 227 SkPoint* curve2 = v2 != SkPath::kLine_Verb ? &pair[2] : cStorage[1]; 228 if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) { 229 fContourBuilder.addCurve(v1, curve1); 230 fContourBuilder.addCurve(v2, curve2); 231 break; 232 } 233 } 234 } 235 addOneQuad: 236 fContourBuilder.addQuad(pointsPtr); 237 break; 238 case SkPath::kConic_Verb: { 239 SkVector v1 = pointsPtr[1] - pointsPtr[0]; 240 SkVector v2 = pointsPtr[2] - pointsPtr[1]; 241 SkScalar weight = *weightPtr++; 242 if (v1.dot(v2) < 0) { 243 // FIXME: max curvature for conics hasn't been implemented; use placeholder 244 SkScalar maxCurvature = SkFindQuadMaxCurvature(pointsPtr); 245 if (0 < maxCurvature && maxCurvature < 1) { 246 SkConic conic(pointsPtr, weight); 247 SkConic pair[2]; 248 if (!conic.chopAt(maxCurvature, pair)) { 249 // if result can't be computed, use original 250 fContourBuilder.addConic(pointsPtr, weight); 251 break; 252 } 253 SkPoint cStorage[2][3]; 254 SkPath::Verb v1 = SkReduceOrder::Conic(pair[0], cStorage[0]); 255 SkPath::Verb v2 = SkReduceOrder::Conic(pair[1], cStorage[1]); 256 SkPoint* curve1 = v1 != SkPath::kLine_Verb ? pair[0].fPts : cStorage[0]; 257 SkPoint* curve2 = v2 != SkPath::kLine_Verb ? pair[1].fPts : cStorage[1]; 258 if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) { 259 fContourBuilder.addCurve(v1, curve1, pair[0].fW); 260 fContourBuilder.addCurve(v2, curve2, pair[1].fW); 261 break; 262 } 263 } 264 } 265 fContourBuilder.addConic(pointsPtr, weight); 266 } break; 267 case SkPath::kCubic_Verb: 268 { 269 // Split complex cubics (such as self-intersecting curves or 270 // ones with difficult curvature) in two before proceeding. 271 // This can be required for intersection to succeed. 272 SkScalar splitT[3]; 273 int breaks = SkDCubic::ComplexBreak(pointsPtr, splitT); 274 if (!breaks) { 275 fContourBuilder.addCubic(pointsPtr); 276 break; 277 } 278 SkASSERT(breaks <= (int) SK_ARRAY_COUNT(splitT)); 279 struct Splitsville { 280 double fT[2]; 281 SkPoint fPts[4]; 282 SkPoint fReduced[4]; 283 SkPath::Verb fVerb; 284 bool fCanAdd; 285 } splits[4]; 286 SkASSERT(SK_ARRAY_COUNT(splits) == SK_ARRAY_COUNT(splitT) + 1); 287 SkTQSort(splitT, &splitT[breaks - 1]); 288 for (int index = 0; index <= breaks; ++index) { 289 Splitsville* split = &splits[index]; 290 split->fT[0] = index ? splitT[index - 1] : 0; 291 split->fT[1] = index < breaks ? splitT[index] : 1; 292 SkDCubic part = SkDCubic::SubDivide(pointsPtr, split->fT[0], split->fT[1]); 293 if (!part.toFloatPoints(split->fPts)) { 294 return false; 295 } 296 split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced); 297 SkPoint* curve = SkPath::kCubic_Verb == verb 298 ? split->fPts : split->fReduced; 299 split->fCanAdd = can_add_curve(split->fVerb, curve); 300 } 301 for (int index = 0; index <= breaks; ++index) { 302 Splitsville* split = &splits[index]; 303 if (!split->fCanAdd) { 304 continue; 305 } 306 int prior = index; 307 while (prior > 0 && !splits[prior - 1].fCanAdd) { 308 --prior; 309 } 310 if (prior < index) { 311 split->fT[0] = splits[prior].fT[0]; 312 split->fPts[0] = splits[prior].fPts[0]; 313 } 314 int next = index; 315 int breakLimit = SkTMin(breaks, (int) SK_ARRAY_COUNT(splits) - 1); 316 while (next < breakLimit && !splits[next + 1].fCanAdd) { 317 ++next; 318 } 319 if (next > index) { 320 split->fT[1] = splits[next].fT[1]; 321 split->fPts[3] = splits[next].fPts[3]; 322 } 323 if (prior < index || next > index) { 324 split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced); 325 } 326 SkPoint* curve = SkPath::kCubic_Verb == split->fVerb 327 ? split->fPts : split->fReduced; 328 if (!can_add_curve(split->fVerb, curve)) { 329 return false; 330 } 331 fContourBuilder.addCurve(split->fVerb, curve); 332 } 333 } 334 break; 335 case SkPath::kClose_Verb: 336 SkASSERT(contour); 337 if (!close()) { 338 return false; 339 } 340 contour = nullptr; 341 continue; 342 default: 343 SkDEBUGFAIL("bad verb"); 344 return false; 345 } 346 SkASSERT(contour); 347 if (contour->count()) { 348 contour->debugValidate(); 349 } 350 pointsPtr += SkPathOpsVerbToPoints(verb); 351 } 352 fContourBuilder.flush(); 353 if (contour && contour->count() &&!fAllowOpenContours && !close()) { 354 return false; 355 } 356 return true; 357 } 358
