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 SkPoint cStorage[2][2]; 219 SkPath::Verb v1 = SkReduceOrder::Quad(&pair[0], cStorage[0]); 220 SkPath::Verb v2 = SkReduceOrder::Quad(&pair[2], cStorage[1]); 221 SkPoint* curve1 = v1 != SkPath::kLine_Verb ? &pair[0] : cStorage[0]; 222 SkPoint* curve2 = v2 != SkPath::kLine_Verb ? &pair[2] : cStorage[1]; 223 if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) { 224 fContourBuilder.addCurve(v1, curve1); 225 fContourBuilder.addCurve(v2, curve2); 226 break; 227 } 228 } 229 } 230 addOneQuad: 231 fContourBuilder.addQuad(pointsPtr); 232 break; 233 case SkPath::kConic_Verb: { 234 SkVector v1 = pointsPtr[1] - pointsPtr[0]; 235 SkVector v2 = pointsPtr[2] - pointsPtr[1]; 236 SkScalar weight = *weightPtr++; 237 if (v1.dot(v2) < 0) { 238 // FIXME: max curvature for conics hasn't been implemented; use placeholder 239 SkScalar maxCurvature = SkFindQuadMaxCurvature(pointsPtr); 240 if (maxCurvature > 0) { 241 SkConic conic(pointsPtr, weight); 242 SkConic pair[2]; 243 if (!conic.chopAt(maxCurvature, pair)) { 244 // if result can't be computed, use original 245 fContourBuilder.addConic(pointsPtr, weight); 246 break; 247 } 248 SkPoint cStorage[2][3]; 249 SkPath::Verb v1 = SkReduceOrder::Conic(pair[0], cStorage[0]); 250 SkPath::Verb v2 = SkReduceOrder::Conic(pair[1], cStorage[1]); 251 SkPoint* curve1 = v1 != SkPath::kLine_Verb ? pair[0].fPts : cStorage[0]; 252 SkPoint* curve2 = v2 != SkPath::kLine_Verb ? pair[1].fPts : cStorage[1]; 253 if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) { 254 fContourBuilder.addCurve(v1, curve1, pair[0].fW); 255 fContourBuilder.addCurve(v2, curve2, pair[1].fW); 256 break; 257 } 258 } 259 } 260 fContourBuilder.addConic(pointsPtr, weight); 261 } break; 262 case SkPath::kCubic_Verb: 263 { 264 // Split complex cubics (such as self-intersecting curves or 265 // ones with difficult curvature) in two before proceeding. 266 // This can be required for intersection to succeed. 267 SkScalar splitT[3]; 268 int breaks = SkDCubic::ComplexBreak(pointsPtr, splitT); 269 if (!breaks) { 270 fContourBuilder.addCubic(pointsPtr); 271 break; 272 } 273 SkASSERT(breaks <= (int) SK_ARRAY_COUNT(splitT)); 274 struct Splitsville { 275 double fT[2]; 276 SkPoint fPts[4]; 277 SkPoint fReduced[4]; 278 SkPath::Verb fVerb; 279 bool fCanAdd; 280 } splits[4]; 281 SkASSERT(SK_ARRAY_COUNT(splits) == SK_ARRAY_COUNT(splitT) + 1); 282 SkTQSort(splitT, &splitT[breaks - 1]); 283 for (int index = 0; index <= breaks; ++index) { 284 Splitsville* split = &splits[index]; 285 split->fT[0] = index ? splitT[index - 1] : 0; 286 split->fT[1] = index < breaks ? splitT[index] : 1; 287 SkDCubic part = SkDCubic::SubDivide(pointsPtr, split->fT[0], split->fT[1]); 288 if (!part.toFloatPoints(split->fPts)) { 289 return false; 290 } 291 split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced); 292 SkPoint* curve = SkPath::kCubic_Verb == verb 293 ? split->fPts : split->fReduced; 294 split->fCanAdd = can_add_curve(split->fVerb, curve); 295 } 296 for (int index = 0; index <= breaks; ++index) { 297 Splitsville* split = &splits[index]; 298 if (!split->fCanAdd) { 299 continue; 300 } 301 int prior = index; 302 while (prior > 0 && !splits[prior - 1].fCanAdd) { 303 --prior; 304 } 305 if (prior < index) { 306 split->fT[0] = splits[prior].fT[0]; 307 } 308 int next = index; 309 while (next < breaks && !splits[next + 1].fCanAdd) { 310 ++next; 311 } 312 if (next > index) { 313 split->fT[1] = splits[next].fT[1]; 314 } 315 if (prior < index || next > index) { 316 if (0 == split->fT[0] && 1 == split->fT[1]) { 317 fContourBuilder.addCubic(pointsPtr); 318 break; 319 } 320 SkDCubic part = SkDCubic::SubDivide(pointsPtr, split->fT[0], 321 split->fT[1]); 322 if (!part.toFloatPoints(split->fPts)) { 323 return false; 324 } 325 split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced); 326 } 327 SkPoint* curve = SkPath::kCubic_Verb == split->fVerb 328 ? split->fPts : split->fReduced; 329 SkAssertResult(can_add_curve(split->fVerb, curve)); 330 fContourBuilder.addCurve(split->fVerb, curve); 331 } 332 } 333 break; 334 case SkPath::kClose_Verb: 335 SkASSERT(contour); 336 if (!close()) { 337 return false; 338 } 339 contour = nullptr; 340 continue; 341 default: 342 SkDEBUGFAIL("bad verb"); 343 return false; 344 } 345 SkASSERT(contour); 346 if (contour->count()) { 347 contour->debugValidate(); 348 } 349 pointsPtr += SkPathOpsVerbToPoints(verb); 350 } 351 fContourBuilder.flush(); 352 if (contour && contour->count() &&!fAllowOpenContours && !close()) { 353 return false; 354 } 355 return true; 356 } 357
