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() - 1; 179 SkScalar* weightPtr = fWeights.begin(); 180 SkPath::Verb verb; 181 SkOpContour* contour = fContourBuilder.contour(); 182 while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) { 183 if (verbPtr == endOfFirstHalf) { 184 fOperand = true; 185 } 186 verbPtr++; 187 switch (verb) { 188 case SkPath::kMove_Verb: 189 if (contour && contour->count()) { 190 if (fAllowOpenContours) { 191 complete(); 192 } else if (!close()) { 193 return false; 194 } 195 } 196 if (!contour) { 197 fContourBuilder.setContour(contour = fContoursHead->appendContour()); 198 } 199 contour->init(fGlobalState, fOperand, 200 fXorMask[fOperand] == kEvenOdd_PathOpsMask); 201 pointsPtr += 1; 202 continue; 203 case SkPath::kLine_Verb: 204 fContourBuilder.addLine(pointsPtr); 205 break; 206 case SkPath::kQuad_Verb: 207 { 208 SkVector v1 = pointsPtr[1] - pointsPtr[0]; 209 SkVector v2 = pointsPtr[2] - pointsPtr[1]; 210 if (v1.dot(v2) < 0) { 211 SkPoint pair[5]; 212 if (SkChopQuadAtMaxCurvature(pointsPtr, pair) == 1) { 213 goto addOneQuad; 214 } 215 if (!SkScalarsAreFinite(&pair[0].fX, SK_ARRAY_COUNT(pair) * 2)) { 216 return false; 217 } 218 for (unsigned index = 0; index < SK_ARRAY_COUNT(pair); ++index) { 219 force_small_to_zero(&pair[index]); 220 } 221 SkPoint cStorage[2][2]; 222 SkPath::Verb v1 = SkReduceOrder::Quad(&pair[0], cStorage[0]); 223 SkPath::Verb v2 = SkReduceOrder::Quad(&pair[2], cStorage[1]); 224 SkPoint* curve1 = v1 != SkPath::kLine_Verb ? &pair[0] : cStorage[0]; 225 SkPoint* curve2 = v2 != SkPath::kLine_Verb ? &pair[2] : cStorage[1]; 226 if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) { 227 fContourBuilder.addCurve(v1, curve1); 228 fContourBuilder.addCurve(v2, curve2); 229 break; 230 } 231 } 232 } 233 addOneQuad: 234 fContourBuilder.addQuad(pointsPtr); 235 break; 236 case SkPath::kConic_Verb: { 237 SkVector v1 = pointsPtr[1] - pointsPtr[0]; 238 SkVector v2 = pointsPtr[2] - pointsPtr[1]; 239 SkScalar weight = *weightPtr++; 240 if (v1.dot(v2) < 0) { 241 // FIXME: max curvature for conics hasn't been implemented; use placeholder 242 SkScalar maxCurvature = SkFindQuadMaxCurvature(pointsPtr); 243 if (maxCurvature > 0) { 244 SkConic conic(pointsPtr, weight); 245 SkConic pair[2]; 246 if (!conic.chopAt(maxCurvature, pair)) { 247 // if result can't be computed, use original 248 fContourBuilder.addConic(pointsPtr, weight); 249 break; 250 } 251 SkPoint cStorage[2][3]; 252 SkPath::Verb v1 = SkReduceOrder::Conic(pair[0], cStorage[0]); 253 SkPath::Verb v2 = SkReduceOrder::Conic(pair[1], cStorage[1]); 254 SkPoint* curve1 = v1 != SkPath::kLine_Verb ? pair[0].fPts : cStorage[0]; 255 SkPoint* curve2 = v2 != SkPath::kLine_Verb ? pair[1].fPts : cStorage[1]; 256 if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) { 257 fContourBuilder.addCurve(v1, curve1, pair[0].fW); 258 fContourBuilder.addCurve(v2, curve2, pair[1].fW); 259 break; 260 } 261 } 262 } 263 fContourBuilder.addConic(pointsPtr, weight); 264 } break; 265 case SkPath::kCubic_Verb: 266 { 267 // Split complex cubics (such as self-intersecting curves or 268 // ones with difficult curvature) in two before proceeding. 269 // This can be required for intersection to succeed. 270 SkScalar splitT[3]; 271 int breaks = SkDCubic::ComplexBreak(pointsPtr, splitT); 272 if (!breaks) { 273 fContourBuilder.addCubic(pointsPtr); 274 break; 275 } 276 SkASSERT(breaks <= (int) SK_ARRAY_COUNT(splitT)); 277 struct Splitsville { 278 double fT[2]; 279 SkPoint fPts[4]; 280 SkPoint fReduced[4]; 281 SkPath::Verb fVerb; 282 bool fCanAdd; 283 } splits[4]; 284 SkASSERT(SK_ARRAY_COUNT(splits) == SK_ARRAY_COUNT(splitT) + 1); 285 SkTQSort(splitT, &splitT[breaks - 1]); 286 for (int index = 0; index <= breaks; ++index) { 287 Splitsville* split = &splits[index]; 288 split->fT[0] = index ? splitT[index - 1] : 0; 289 split->fT[1] = index < breaks ? splitT[index] : 1; 290 SkDCubic part = SkDCubic::SubDivide(pointsPtr, split->fT[0], split->fT[1]); 291 if (!part.toFloatPoints(split->fPts)) { 292 return false; 293 } 294 split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced); 295 SkPoint* curve = SkPath::kCubic_Verb == verb 296 ? split->fPts : split->fReduced; 297 split->fCanAdd = can_add_curve(split->fVerb, curve); 298 } 299 for (int index = 0; index <= breaks; ++index) { 300 Splitsville* split = &splits[index]; 301 if (!split->fCanAdd) { 302 continue; 303 } 304 int prior = index; 305 while (prior > 0 && !splits[prior - 1].fCanAdd) { 306 --prior; 307 } 308 if (prior < index) { 309 split->fT[0] = splits[prior].fT[0]; 310 } 311 int next = index; 312 int breakLimit = SkTMin(breaks, (int) SK_ARRAY_COUNT(splits) - 1); 313 while (next < breakLimit && !splits[next + 1].fCanAdd) { 314 ++next; 315 } 316 if (next > index) { 317 split->fT[1] = splits[next].fT[1]; 318 } 319 if (prior < index || next > index) { 320 if (0 == split->fT[0] && 1 == split->fT[1]) { 321 fContourBuilder.addCubic(pointsPtr); 322 break; 323 } 324 SkDCubic part = SkDCubic::SubDivide(pointsPtr, split->fT[0], 325 split->fT[1]); 326 if (!part.toFloatPoints(split->fPts)) { 327 return false; 328 } 329 split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced); 330 } 331 SkPoint* curve = SkPath::kCubic_Verb == split->fVerb 332 ? split->fPts : split->fReduced; 333 SkAssertResult(can_add_curve(split->fVerb, curve)); 334 fContourBuilder.addCurve(split->fVerb, curve); 335 } 336 } 337 break; 338 case SkPath::kClose_Verb: 339 SkASSERT(contour); 340 if (!close()) { 341 return false; 342 } 343 contour = nullptr; 344 continue; 345 default: 346 SkDEBUGFAIL("bad verb"); 347 return false; 348 } 349 SkASSERT(contour); 350 if (contour->count()) { 351 contour->debugValidate(); 352 } 353 pointsPtr += SkPathOpsVerbToPoints(verb); 354 } 355 fContourBuilder.flush(); 356 if (contour && contour->count() &&!fAllowOpenContours && !close()) { 357 return false; 358 } 359 return true; 360 } 361
