SkStroke.cpp revision b3eb687f8a89eb1eacd1afb4016401eb392f66ab
1/* 2 * Copyright 2008 The Android Open Source Project 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 8#include "SkStrokerPriv.h" 9#include "SkGeometry.h" 10#include "SkPath.h" 11 12#if QUAD_STROKE_APPROXIMATION 13 14 enum { 15 kTangent_RecursiveLimit, 16 kCubic_RecursiveLimit, 17 kQuad_RecursiveLimit 18 }; 19 20 // quads with extreme widths (e.g. (0,1) (1,6) (0,3) width=5e7) recurse to point of failure 21 // largest seen for normal cubics : 5, 26 22 // largest seen for normal quads : 11 23 static const int kRecursiveLimits[] = { 5*3, 26*3, 11*3 }; // 3x limits seen in practical tests 24 25 SK_COMPILE_ASSERT(SK_ARRAY_COUNT(kRecursiveLimits) == kQuad_RecursiveLimit + 1, 26 recursive_limits_mismatch); 27 28 #ifdef SK_DEBUG // enables tweaking these values at runtime from SampleApp 29 bool gDebugStrokerErrorSet = false; 30 SkScalar gDebugStrokerError; 31 32 int gMaxRecursion[SK_ARRAY_COUNT(kRecursiveLimits)] = { 0 }; 33 #endif 34 #ifndef DEBUG_QUAD_STROKER 35 #define DEBUG_QUAD_STROKER 0 36 #endif 37 38 #if DEBUG_QUAD_STROKER 39 /* Enable to show the decisions made in subdividing the curve -- helpful when the resulting 40 stroke has more than the optimal number of quadratics and lines */ 41 #define STROKER_RESULT(resultType, depth, quadPts, format, ...) \ 42 SkDebugf("[%d] %s " format "\n", depth, __FUNCTION__, __VA_ARGS__), \ 43 SkDebugf(" " #resultType " t=(%g,%g)\n", quadPts->fStartT, quadPts->fEndT), \ 44 resultType 45 #define STROKER_DEBUG_PARAMS(...) , __VA_ARGS__ 46 #else 47 #define STROKER_RESULT(resultType, depth, quadPts, format, ...) \ 48 resultType 49 #define STROKER_DEBUG_PARAMS(...) 50 #endif 51 52#endif 53 54#define kMaxQuadSubdivide 5 55#define kMaxCubicSubdivide 7 56 57static inline bool degenerate_vector(const SkVector& v) { 58 return !SkPoint::CanNormalize(v.fX, v.fY); 59} 60 61#if !QUAD_STROKE_APPROXIMATION 62static inline bool normals_too_curvy(const SkVector& norm0, SkVector& norm1) { 63 /* root2/2 is a 45-degree angle 64 make this constant bigger for more subdivisions (but not >= 1) 65 */ 66 static const SkScalar kFlatEnoughNormalDotProd = 67 SK_ScalarSqrt2/2 + SK_Scalar1/10; 68 69 SkASSERT(kFlatEnoughNormalDotProd > 0 && 70 kFlatEnoughNormalDotProd < SK_Scalar1); 71 72 return SkPoint::DotProduct(norm0, norm1) <= kFlatEnoughNormalDotProd; 73} 74 75static inline bool normals_too_pinchy(const SkVector& norm0, SkVector& norm1) { 76 // if the dot-product is -1, then we are definitely too pinchy. We tweak 77 // that by an epsilon to ensure we have significant bits in our test 78 static const int kMinSigBitsForDot = 8; 79 static const SkScalar kDotEpsilon = FLT_EPSILON * (1 << kMinSigBitsForDot); 80 static const SkScalar kTooPinchyNormalDotProd = kDotEpsilon - 1; 81 82 // just some sanity asserts to help document the expected range 83 SkASSERT(kTooPinchyNormalDotProd >= -1); 84 SkASSERT(kTooPinchyNormalDotProd < SkDoubleToScalar(-0.999)); 85 86 SkScalar dot = SkPoint::DotProduct(norm0, norm1); 87 return dot <= kTooPinchyNormalDotProd; 88} 89#endif 90 91static bool set_normal_unitnormal(const SkPoint& before, const SkPoint& after, 92 SkScalar radius, 93 SkVector* normal, SkVector* unitNormal) { 94 if (!unitNormal->setNormalize(after.fX - before.fX, after.fY - before.fY)) { 95 return false; 96 } 97 unitNormal->rotateCCW(); 98 unitNormal->scale(radius, normal); 99 return true; 100} 101 102static bool set_normal_unitnormal(const SkVector& vec, 103 SkScalar radius, 104 SkVector* normal, SkVector* unitNormal) { 105 if (!unitNormal->setNormalize(vec.fX, vec.fY)) { 106 return false; 107 } 108 unitNormal->rotateCCW(); 109 unitNormal->scale(radius, normal); 110 return true; 111} 112 113/////////////////////////////////////////////////////////////////////////////// 114#if QUAD_STROKE_APPROXIMATION 115 116struct SkQuadConstruct { // The state of the quad stroke under construction. 117 SkPoint fQuad[3]; // the stroked quad parallel to the original curve 118 SkPoint fTangentStart; // a point tangent to fQuad[0] 119 SkPoint fTangentEnd; // a point tangent to fQuad[2] 120 SkScalar fStartT; // a segment of the original curve 121 SkScalar fMidT; // " 122 SkScalar fEndT; // " 123 bool fStartSet; // state to share common points across structs 124 bool fEndSet; // " 125 126 // return false if start and end are too close to have a unique middle 127 bool init(SkScalar start, SkScalar end) { 128 fStartT = start; 129 fMidT = (start + end) * SK_ScalarHalf; 130 fEndT = end; 131 fStartSet = fEndSet = false; 132 return fStartT < fMidT && fMidT < fEndT; 133 } 134 135 bool initWithStart(SkQuadConstruct* parent) { 136 if (!init(parent->fStartT, parent->fMidT)) { 137 return false; 138 } 139 fQuad[0] = parent->fQuad[0]; 140 fTangentStart = parent->fTangentStart; 141 fStartSet = true; 142 return true; 143 } 144 145 bool initWithEnd(SkQuadConstruct* parent) { 146 if (!init(parent->fMidT, parent->fEndT)) { 147 return false; 148 } 149 fQuad[2] = parent->fQuad[2]; 150 fTangentEnd = parent->fTangentEnd; 151 fEndSet = true; 152 return true; 153 } 154}; 155#endif 156 157class SkPathStroker { 158public: 159#if QUAD_STROKE_APPROXIMATION 160 SkPathStroker(const SkPath& src, 161 SkScalar radius, SkScalar miterLimit, SkScalar error, SkPaint::Cap cap, 162 SkPaint::Join join); 163#else 164 SkPathStroker(const SkPath& src, 165 SkScalar radius, SkScalar miterLimit, SkPaint::Cap cap, 166 SkPaint::Join join); 167#endif 168 169 void moveTo(const SkPoint&); 170 void lineTo(const SkPoint&); 171 void quadTo(const SkPoint&, const SkPoint&); 172 void cubicTo(const SkPoint&, const SkPoint&, const SkPoint&); 173 void close(bool isLine) { this->finishContour(true, isLine); } 174 175 void done(SkPath* dst, bool isLine) { 176 this->finishContour(false, isLine); 177 fOuter.addPath(fExtra); 178 dst->swap(fOuter); 179 } 180 181private: 182#if QUAD_STROKE_APPROXIMATION 183 SkScalar fError; 184#endif 185 SkScalar fRadius; 186 SkScalar fInvMiterLimit; 187 188 SkVector fFirstNormal, fPrevNormal, fFirstUnitNormal, fPrevUnitNormal; 189 SkPoint fFirstPt, fPrevPt; // on original path 190 SkPoint fFirstOuterPt; 191 int fSegmentCount; 192 bool fPrevIsLine; 193 194 SkStrokerPriv::CapProc fCapper; 195 SkStrokerPriv::JoinProc fJoiner; 196 197 SkPath fInner, fOuter; // outer is our working answer, inner is temp 198 SkPath fExtra; // added as extra complete contours 199 200#if QUAD_STROKE_APPROXIMATION 201 enum StrokeType { 202 kOuter_StrokeType = 1, // use sign-opposite values later to flip perpendicular axis 203 kInner_StrokeType = -1 204 } fStrokeType; 205 206 enum ResultType { 207 kSplit_ResultType, // the caller should split the quad stroke in two 208 kDegenerate_ResultType, // the caller should add a line 209 kQuad_ResultType, // the caller should (continue to try to) add a quad stroke 210 kNormalError_ResultType, // the cubic's normal couldn't be computed -- abort 211 }; 212 213 enum ReductionType { 214 kPoint_ReductionType, // all curve points are practically identical 215 kLine_ReductionType, // the control point is on the line between the ends 216 kQuad_ReductionType, // the control point is outside the line between the ends 217 kDegenerate_ReductionType, // the control point is on the line but outside the ends 218 kDegenerate2_ReductionType, // two control points are on the line but outside ends (cubic) 219 kDegenerate3_ReductionType, // three areas of max curvature found (for cubic) 220 }; 221 222 enum IntersectRayType { 223 kCtrlPt_RayType, 224 kResultType_RayType, 225 }; 226 227 int fRecursionDepth; // track stack depth to abort if numerics run amok 228 bool fFoundTangents; // do less work until tangents meet (cubic) 229 230 void addDegenerateLine(const SkQuadConstruct* ); 231 ReductionType CheckCubicLinear(const SkPoint cubic[4], SkPoint reduction[3], 232 const SkPoint** tanPtPtr); 233 ReductionType CheckQuadLinear(const SkPoint quad[3], SkPoint* reduction); 234 ResultType compareQuadCubic(const SkPoint cubic[4], SkQuadConstruct* ); 235 ResultType compareQuadQuad(const SkPoint quad[3], SkQuadConstruct* ); 236 bool cubicMidOnLine(const SkPoint cubic[4], const SkQuadConstruct* ) const; 237 bool cubicPerpRay(const SkPoint cubic[4], SkScalar t, SkPoint* tPt, SkPoint* onPt, 238 SkPoint* tangent) const; 239 bool cubicQuadEnds(const SkPoint cubic[4], SkQuadConstruct* ); 240 bool cubicQuadMid(const SkPoint cubic[4], const SkQuadConstruct* , SkPoint* mid) const; 241 bool cubicStroke(const SkPoint cubic[4], SkQuadConstruct* ); 242 void init(StrokeType strokeType, SkQuadConstruct* , SkScalar tStart, SkScalar tEnd); 243 ResultType intersectRay(SkQuadConstruct* , IntersectRayType STROKER_DEBUG_PARAMS(int) ) const; 244 bool ptInQuadBounds(const SkPoint quad[3], const SkPoint& pt) const; 245 void quadPerpRay(const SkPoint quad[3], SkScalar t, SkPoint* tPt, SkPoint* onPt, 246 SkPoint* tangent) const; 247 bool quadStroke(const SkPoint quad[3], SkQuadConstruct* ); 248 void setCubicEndNormal(const SkPoint cubic[4], 249 const SkVector& normalAB, const SkVector& unitNormalAB, 250 SkVector* normalCD, SkVector* unitNormalCD); 251 void setQuadEndNormal(const SkPoint quad[3], 252 const SkVector& normalAB, const SkVector& unitNormalAB, 253 SkVector* normalBC, SkVector* unitNormalBC); 254 void setRayPts(const SkPoint& tPt, SkVector* dxy, SkPoint* onPt, SkPoint* tangent) const; 255 static bool SlightAngle(SkQuadConstruct* ); 256 ResultType strokeCloseEnough(const SkPoint stroke[3], const SkPoint ray[2], 257 SkQuadConstruct* STROKER_DEBUG_PARAMS(int depth) ) const; 258 ResultType tangentsMeet(const SkPoint cubic[4], SkQuadConstruct* ); 259#endif 260 261 void finishContour(bool close, bool isLine); 262 void preJoinTo(const SkPoint&, SkVector* normal, SkVector* unitNormal, 263 bool isLine); 264 void postJoinTo(const SkPoint&, const SkVector& normal, 265 const SkVector& unitNormal); 266 267 void line_to(const SkPoint& currPt, const SkVector& normal); 268#if !QUAD_STROKE_APPROXIMATION 269 void quad_to(const SkPoint pts[3], 270 const SkVector& normalAB, const SkVector& unitNormalAB, 271 SkVector* normalBC, SkVector* unitNormalBC, 272 int subDivide); 273 void cubic_to(const SkPoint pts[4], 274 const SkVector& normalAB, const SkVector& unitNormalAB, 275 SkVector* normalCD, SkVector* unitNormalCD, 276 int subDivide); 277#endif 278}; 279 280/////////////////////////////////////////////////////////////////////////////// 281 282void SkPathStroker::preJoinTo(const SkPoint& currPt, SkVector* normal, 283 SkVector* unitNormal, bool currIsLine) { 284 SkASSERT(fSegmentCount >= 0); 285 286 SkScalar prevX = fPrevPt.fX; 287 SkScalar prevY = fPrevPt.fY; 288 289 SkAssertResult(set_normal_unitnormal(fPrevPt, currPt, fRadius, normal, 290 unitNormal)); 291 292 if (fSegmentCount == 0) { 293 fFirstNormal = *normal; 294 fFirstUnitNormal = *unitNormal; 295 fFirstOuterPt.set(prevX + normal->fX, prevY + normal->fY); 296 297 fOuter.moveTo(fFirstOuterPt.fX, fFirstOuterPt.fY); 298 fInner.moveTo(prevX - normal->fX, prevY - normal->fY); 299 } else { // we have a previous segment 300 fJoiner(&fOuter, &fInner, fPrevUnitNormal, fPrevPt, *unitNormal, 301 fRadius, fInvMiterLimit, fPrevIsLine, currIsLine); 302 } 303 fPrevIsLine = currIsLine; 304} 305 306void SkPathStroker::postJoinTo(const SkPoint& currPt, const SkVector& normal, 307 const SkVector& unitNormal) { 308 fPrevPt = currPt; 309 fPrevUnitNormal = unitNormal; 310 fPrevNormal = normal; 311 fSegmentCount += 1; 312} 313 314void SkPathStroker::finishContour(bool close, bool currIsLine) { 315 if (fSegmentCount > 0) { 316 SkPoint pt; 317 318 if (close) { 319 fJoiner(&fOuter, &fInner, fPrevUnitNormal, fPrevPt, 320 fFirstUnitNormal, fRadius, fInvMiterLimit, 321 fPrevIsLine, currIsLine); 322 fOuter.close(); 323 // now add fInner as its own contour 324 fInner.getLastPt(&pt); 325 fOuter.moveTo(pt.fX, pt.fY); 326 fOuter.reversePathTo(fInner); 327 fOuter.close(); 328 } else { // add caps to start and end 329 // cap the end 330 fInner.getLastPt(&pt); 331 fCapper(&fOuter, fPrevPt, fPrevNormal, pt, 332 currIsLine ? &fInner : NULL); 333 fOuter.reversePathTo(fInner); 334 // cap the start 335 fCapper(&fOuter, fFirstPt, -fFirstNormal, fFirstOuterPt, 336 fPrevIsLine ? &fInner : NULL); 337 fOuter.close(); 338 } 339 } 340 // since we may re-use fInner, we rewind instead of reset, to save on 341 // reallocating its internal storage. 342 fInner.rewind(); 343 fSegmentCount = -1; 344} 345 346/////////////////////////////////////////////////////////////////////////////// 347 348#if QUAD_STROKE_APPROXIMATION 349SkPathStroker::SkPathStroker(const SkPath& src, 350 SkScalar radius, SkScalar miterLimit, SkScalar error, 351 SkPaint::Cap cap, SkPaint::Join join) 352#else 353SkPathStroker::SkPathStroker(const SkPath& src, 354 SkScalar radius, SkScalar miterLimit, 355 SkPaint::Cap cap, SkPaint::Join join) 356#endif 357 : fRadius(radius) { 358 359 /* This is only used when join is miter_join, but we initialize it here 360 so that it is always defined, to fis valgrind warnings. 361 */ 362 fInvMiterLimit = 0; 363 364 if (join == SkPaint::kMiter_Join) { 365 if (miterLimit <= SK_Scalar1) { 366 join = SkPaint::kBevel_Join; 367 } else { 368 fInvMiterLimit = SkScalarInvert(miterLimit); 369 } 370 } 371 fCapper = SkStrokerPriv::CapFactory(cap); 372 fJoiner = SkStrokerPriv::JoinFactory(join); 373 fSegmentCount = -1; 374 fPrevIsLine = false; 375 376 // Need some estimate of how large our final result (fOuter) 377 // and our per-contour temp (fInner) will be, so we don't spend 378 // extra time repeatedly growing these arrays. 379 // 380 // 3x for result == inner + outer + join (swag) 381 // 1x for inner == 'wag' (worst contour length would be better guess) 382 fOuter.incReserve(src.countPoints() * 3); 383 fOuter.setIsVolatile(true); 384 fInner.incReserve(src.countPoints()); 385 fInner.setIsVolatile(true); 386#if QUAD_STROKE_APPROXIMATION 387#ifdef SK_DEBUG 388 if (!gDebugStrokerErrorSet) { 389 gDebugStrokerError = error; 390 } 391 fError = gDebugStrokerError; 392#else 393 fError = error; 394#endif 395 fRecursionDepth = 0; 396#endif 397} 398 399void SkPathStroker::moveTo(const SkPoint& pt) { 400 if (fSegmentCount > 0) { 401 this->finishContour(false, false); 402 } 403 fSegmentCount = 0; 404 fFirstPt = fPrevPt = pt; 405} 406 407void SkPathStroker::line_to(const SkPoint& currPt, const SkVector& normal) { 408 fOuter.lineTo(currPt.fX + normal.fX, currPt.fY + normal.fY); 409 fInner.lineTo(currPt.fX - normal.fX, currPt.fY - normal.fY); 410} 411 412void SkPathStroker::lineTo(const SkPoint& currPt) { 413 if (SkPath::IsLineDegenerate(fPrevPt, currPt)) { 414 return; 415 } 416 SkVector normal, unitNormal; 417 418 this->preJoinTo(currPt, &normal, &unitNormal, true); 419 this->line_to(currPt, normal); 420 this->postJoinTo(currPt, normal, unitNormal); 421} 422 423#if !QUAD_STROKE_APPROXIMATION 424void SkPathStroker::quad_to(const SkPoint pts[3], 425 const SkVector& normalAB, const SkVector& unitNormalAB, 426 SkVector* normalBC, SkVector* unitNormalBC, 427 int subDivide) { 428 if (!set_normal_unitnormal(pts[1], pts[2], fRadius, 429 normalBC, unitNormalBC)) { 430 // pts[1] nearly equals pts[2], so just draw a line to pts[2] 431 this->line_to(pts[2], normalAB); 432 *normalBC = normalAB; 433 *unitNormalBC = unitNormalAB; 434 return; 435 } 436 437 if (--subDivide >= 0 && normals_too_curvy(unitNormalAB, *unitNormalBC)) { 438 SkPoint tmp[5]; 439 SkVector norm, unit; 440 441 SkChopQuadAtHalf(pts, tmp); 442 this->quad_to(&tmp[0], normalAB, unitNormalAB, &norm, &unit, subDivide); 443 this->quad_to(&tmp[2], norm, unit, normalBC, unitNormalBC, subDivide); 444 } else { 445 SkVector normalB; 446 447 normalB = pts[2] - pts[0]; 448 normalB.rotateCCW(); 449 SkScalar dot = SkPoint::DotProduct(unitNormalAB, *unitNormalBC); 450 SkAssertResult(normalB.setLength(SkScalarDiv(fRadius, 451 SkScalarSqrt((SK_Scalar1 + dot)/2)))); 452 453 fOuter.quadTo( pts[1].fX + normalB.fX, pts[1].fY + normalB.fY, 454 pts[2].fX + normalBC->fX, pts[2].fY + normalBC->fY); 455 fInner.quadTo( pts[1].fX - normalB.fX, pts[1].fY - normalB.fY, 456 pts[2].fX - normalBC->fX, pts[2].fY - normalBC->fY); 457 } 458} 459#endif 460 461#if QUAD_STROKE_APPROXIMATION 462void SkPathStroker::setQuadEndNormal(const SkPoint quad[3], const SkVector& normalAB, 463 const SkVector& unitNormalAB, SkVector* normalBC, SkVector* unitNormalBC) { 464 if (!set_normal_unitnormal(quad[1], quad[2], fRadius, normalBC, unitNormalBC)) { 465 *normalBC = normalAB; 466 *unitNormalBC = unitNormalAB; 467 } 468} 469 470void SkPathStroker::setCubicEndNormal(const SkPoint cubic[4], const SkVector& normalAB, 471 const SkVector& unitNormalAB, SkVector* normalCD, SkVector* unitNormalCD) { 472 SkVector ab = cubic[1] - cubic[0]; 473 SkVector cd = cubic[3] - cubic[2]; 474 475 bool degenerateAB = degenerate_vector(ab); 476 bool degenerateCD = degenerate_vector(cd); 477 478 if (degenerateAB && degenerateCD) { 479 goto DEGENERATE_NORMAL; 480 } 481 482 if (degenerateAB) { 483 ab = cubic[2] - cubic[0]; 484 degenerateAB = degenerate_vector(ab); 485 } 486 if (degenerateCD) { 487 cd = cubic[3] - cubic[1]; 488 degenerateCD = degenerate_vector(cd); 489 } 490 if (degenerateAB || degenerateCD) { 491DEGENERATE_NORMAL: 492 *normalCD = normalAB; 493 *unitNormalCD = unitNormalAB; 494 return; 495 } 496 SkAssertResult(set_normal_unitnormal(cd, fRadius, normalCD, unitNormalCD)); 497} 498 499void SkPathStroker::init(StrokeType strokeType, SkQuadConstruct* quadPts, SkScalar tStart, 500 SkScalar tEnd) { 501 fStrokeType = strokeType; 502 fFoundTangents = false; 503 quadPts->init(tStart, tEnd); 504} 505 506// returns the distance squared from the point to the line 507static SkScalar pt_to_line(const SkPoint& pt, const SkPoint& lineStart, const SkPoint& lineEnd) { 508 SkVector dxy = lineEnd - lineStart; 509 if (degenerate_vector(dxy)) { 510 return pt.distanceToSqd(lineStart); 511 } 512 SkVector ab0 = pt - lineStart; 513 SkScalar numer = dxy.dot(ab0); 514 SkScalar denom = dxy.dot(dxy); 515 SkScalar t = numer / denom; 516 SkPoint hit; 517 hit.fX = lineStart.fX * (1 - t) + lineEnd.fX * t; 518 hit.fY = lineStart.fY * (1 - t) + lineEnd.fY * t; 519 return hit.distanceToSqd(pt); 520} 521 522/* Given a cubic, determine if all four points are in a line. 523 Return true if the inner points is close to a line connecting the outermost points. 524 525 Find the outermost point by looking for the largest difference in X or Y. 526 Given the indices of the outermost points, and that outer_1 is greater than outer_2, 527 this table shows the index of the smaller of the remaining points: 528 529 outer_2 530 0 1 2 3 531 outer_1 ---------------- 532 0 | - 2 1 1 533 1 | - - 0 0 534 2 | - - - 0 535 3 | - - - - 536 537 If outer_1 == 0 and outer_2 == 1, the smaller of the remaining indices (2 and 3) is 2. 538 539 This table can be collapsed to: (1 + (2 >> outer_2)) >> outer_1 540 541 Given three indices (outer_1 outer_2 mid_1) from 0..3, the remaining index is: 542 543 mid_2 == (outer_1 ^ outer_2 ^ mid_1) 544 */ 545static bool cubic_in_line(const SkPoint cubic[4]) { 546 SkScalar ptMax = -1; 547 int outer1, outer2; 548 for (int index = 0; index < 3; ++index) { 549 for (int inner = index + 1; inner < 4; ++inner) { 550 SkVector testDiff = cubic[inner] - cubic[index]; 551 SkScalar testMax = SkTMax(SkScalarAbs(testDiff.fX), SkScalarAbs(testDiff.fY)); 552 if (ptMax < testMax) { 553 outer1 = index; 554 outer2 = inner; 555 ptMax = testMax; 556 } 557 } 558 } 559 SkASSERT(outer1 >= 0 && outer1 <= 2); 560 SkASSERT(outer2 >= 1 && outer2 <= 3); 561 SkASSERT(outer1 < outer2); 562 int mid1 = (1 + (2 >> outer2)) >> outer1; 563 SkASSERT(mid1 >= 0 && mid1 <= 2); 564 SkASSERT(outer1 != mid1 && outer2 != mid1); 565 int mid2 = outer1 ^ outer2 ^ mid1; 566 SkASSERT(mid2 >= 1 && mid2 <= 3); 567 SkASSERT(mid2 != outer1 && mid2 != outer2 && mid2 != mid1); 568 SkASSERT(((1 << outer1) | (1 << outer2) | (1 << mid1) | (1 << mid2)) == 0x0f); 569 SkScalar lineSlop = ptMax * ptMax * 0.00001f; // this multiplier is pulled out of the air 570 return pt_to_line(cubic[mid1], cubic[outer1], cubic[outer2]) <= lineSlop 571 && pt_to_line(cubic[mid2], cubic[outer1], cubic[outer2]) <= lineSlop; 572} 573 574/* Given quad, see if all there points are in a line. 575 Return true if the inside point is close to a line connecting the outermost points. 576 577 Find the outermost point by looking for the largest difference in X or Y. 578 Since the XOR of the indices is 3 (0 ^ 1 ^ 2) 579 the missing index equals: outer_1 ^ outer_2 ^ 3 580 */ 581static bool quad_in_line(const SkPoint quad[3]) { 582 SkScalar ptMax = -1; 583 int outer1, outer2; 584 for (int index = 0; index < 2; ++index) { 585 for (int inner = index + 1; inner < 3; ++inner) { 586 SkVector testDiff = quad[inner] - quad[index]; 587 SkScalar testMax = SkTMax(SkScalarAbs(testDiff.fX), SkScalarAbs(testDiff.fY)); 588 if (ptMax < testMax) { 589 outer1 = index; 590 outer2 = inner; 591 ptMax = testMax; 592 } 593 } 594 } 595 SkASSERT(outer1 >= 0 && outer1 <= 1); 596 SkASSERT(outer2 >= 1 && outer2 <= 2); 597 SkASSERT(outer1 < outer2); 598 int mid = outer1 ^ outer2 ^ 3; 599 SkScalar lineSlop = ptMax * ptMax * 0.00001f; // this multiplier is pulled out of the air 600 return pt_to_line(quad[mid], quad[outer1], quad[outer2]) <= lineSlop; 601} 602 603SkPathStroker::ReductionType SkPathStroker::CheckCubicLinear(const SkPoint cubic[4], 604 SkPoint reduction[3], const SkPoint** tangentPtPtr) { 605 bool degenerateAB = degenerate_vector(cubic[1] - cubic[0]); 606 bool degenerateBC = degenerate_vector(cubic[2] - cubic[1]); 607 bool degenerateCD = degenerate_vector(cubic[3] - cubic[2]); 608 if (degenerateAB & degenerateBC & degenerateCD) { 609 return kPoint_ReductionType; 610 } 611 if (degenerateAB + degenerateBC + degenerateCD == 2) { 612 return kLine_ReductionType; 613 } 614 if (!cubic_in_line(cubic)) { 615 *tangentPtPtr = degenerateAB ? &cubic[2] : &cubic[1]; 616 return kQuad_ReductionType; 617 } 618 SkScalar tValues[3]; 619 int count = SkFindCubicMaxCurvature(cubic, tValues); 620 if (count == 0) { 621 return kLine_ReductionType; 622 } 623 for (int index = 0; index < count; ++index) { 624 SkScalar t = tValues[index]; 625 SkEvalCubicAt(cubic, t, &reduction[index], NULL, NULL); 626 } 627 SK_COMPILE_ASSERT(kQuad_ReductionType + 1 == kDegenerate_ReductionType, enum_out_of_whack); 628 SK_COMPILE_ASSERT(kQuad_ReductionType + 2 == kDegenerate2_ReductionType, enum_out_of_whack); 629 SK_COMPILE_ASSERT(kQuad_ReductionType + 3 == kDegenerate3_ReductionType, enum_out_of_whack); 630 631 return (ReductionType) (kQuad_ReductionType + count); 632} 633 634SkPathStroker::ReductionType SkPathStroker::CheckQuadLinear(const SkPoint quad[3], 635 SkPoint* reduction) { 636 bool degenerateAB = degenerate_vector(quad[1] - quad[0]); 637 bool degenerateBC = degenerate_vector(quad[2] - quad[1]); 638 if (degenerateAB & degenerateBC) { 639 return kPoint_ReductionType; 640 } 641 if (degenerateAB | degenerateBC) { 642 return kLine_ReductionType; 643 } 644 if (!quad_in_line(quad)) { 645 return kQuad_ReductionType; 646 } 647 SkScalar t = SkFindQuadMaxCurvature(quad); 648 if (0 == t) { 649 return kLine_ReductionType; 650 } 651 SkEvalQuadAt(quad, t, reduction, NULL); 652 return kDegenerate_ReductionType; 653} 654 655#else 656 657void SkPathStroker::cubic_to(const SkPoint pts[4], 658 const SkVector& normalAB, const SkVector& unitNormalAB, 659 SkVector* normalCD, SkVector* unitNormalCD, 660 int subDivide) { 661 SkVector ab = pts[1] - pts[0]; 662 SkVector cd = pts[3] - pts[2]; 663 SkVector normalBC, unitNormalBC; 664 665 bool degenerateAB = degenerate_vector(ab); 666 bool degenerateCD = degenerate_vector(cd); 667 668 if (degenerateAB && degenerateCD) { 669DRAW_LINE: 670 this->line_to(pts[3], normalAB); 671 *normalCD = normalAB; 672 *unitNormalCD = unitNormalAB; 673 return; 674 } 675 676 if (degenerateAB) { 677 ab = pts[2] - pts[0]; 678 degenerateAB = degenerate_vector(ab); 679 } 680 if (degenerateCD) { 681 cd = pts[3] - pts[1]; 682 degenerateCD = degenerate_vector(cd); 683 } 684 if (degenerateAB || degenerateCD) { 685 goto DRAW_LINE; 686 } 687 SkAssertResult(set_normal_unitnormal(cd, fRadius, normalCD, unitNormalCD)); 688 bool degenerateBC = !set_normal_unitnormal(pts[1], pts[2], fRadius, 689 &normalBC, &unitNormalBC); 690#ifndef SK_IGNORE_CUBIC_STROKE_FIX 691 if (--subDivide < 0) { 692 goto DRAW_LINE; 693 } 694#endif 695 if (degenerateBC || normals_too_curvy(unitNormalAB, unitNormalBC) || 696 normals_too_curvy(unitNormalBC, *unitNormalCD)) { 697#ifdef SK_IGNORE_CUBIC_STROKE_FIX 698 // subdivide if we can 699 if (--subDivide < 0) { 700 goto DRAW_LINE; 701 } 702#endif 703 SkPoint tmp[7]; 704 SkVector norm, unit, dummy, unitDummy; 705 706 SkChopCubicAtHalf(pts, tmp); 707 this->cubic_to(&tmp[0], normalAB, unitNormalAB, &norm, &unit, 708 subDivide); 709 // we use dummys since we already have a valid (and more accurate) 710 // normals for CD 711 this->cubic_to(&tmp[3], norm, unit, &dummy, &unitDummy, subDivide); 712 } else { 713 SkVector normalB, normalC; 714 715 // need normals to inset/outset the off-curve pts B and C 716 717 SkVector unitBC = pts[2] - pts[1]; 718 unitBC.normalize(); 719 unitBC.rotateCCW(); 720 721 normalB = unitNormalAB + unitBC; 722 normalC = *unitNormalCD + unitBC; 723 724 SkScalar dot = SkPoint::DotProduct(unitNormalAB, unitBC); 725 SkAssertResult(normalB.setLength(SkScalarDiv(fRadius, 726 SkScalarSqrt((SK_Scalar1 + dot)/2)))); 727 dot = SkPoint::DotProduct(*unitNormalCD, unitBC); 728 SkAssertResult(normalC.setLength(SkScalarDiv(fRadius, 729 SkScalarSqrt((SK_Scalar1 + dot)/2)))); 730 731 fOuter.cubicTo( pts[1].fX + normalB.fX, pts[1].fY + normalB.fY, 732 pts[2].fX + normalC.fX, pts[2].fY + normalC.fY, 733 pts[3].fX + normalCD->fX, pts[3].fY + normalCD->fY); 734 735 fInner.cubicTo( pts[1].fX - normalB.fX, pts[1].fY - normalB.fY, 736 pts[2].fX - normalC.fX, pts[2].fY - normalC.fY, 737 pts[3].fX - normalCD->fX, pts[3].fY - normalCD->fY); 738 } 739} 740#endif 741 742void SkPathStroker::quadTo(const SkPoint& pt1, const SkPoint& pt2) { 743#if QUAD_STROKE_APPROXIMATION 744 const SkPoint quad[3] = { fPrevPt, pt1, pt2 }; 745 SkPoint reduction; 746 ReductionType reductionType = CheckQuadLinear(quad, &reduction); 747 if (kPoint_ReductionType == reductionType) { 748 return; 749 } 750 if (kLine_ReductionType == reductionType) { 751 this->lineTo(pt2); 752 return; 753 } 754 if (kDegenerate_ReductionType == reductionType) { 755 this->lineTo(reduction); 756 SkStrokerPriv::JoinProc saveJoiner = fJoiner; 757 fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join); 758 this->lineTo(pt2); 759 fJoiner = saveJoiner; 760 return; 761 } 762 SkASSERT(kQuad_ReductionType == reductionType); 763 SkVector normalAB, unitAB, normalBC, unitBC; 764 this->preJoinTo(pt1, &normalAB, &unitAB, false); 765 SkQuadConstruct quadPts; 766 this->init(kOuter_StrokeType, &quadPts, 0, 1); 767 if (!this->quadStroke(quad, &quadPts)) { 768 return; 769 } 770 this->init(kInner_StrokeType, &quadPts, 0, 1); 771 if (!this->quadStroke(quad, &quadPts)) { 772 return; 773 } 774 this->setQuadEndNormal(quad, normalAB, unitAB, &normalBC, &unitBC); 775#else 776 bool degenerateAB = SkPath::IsLineDegenerate(fPrevPt, pt1); 777 bool degenerateBC = SkPath::IsLineDegenerate(pt1, pt2); 778 779 if (degenerateAB | degenerateBC) { 780 if (degenerateAB ^ degenerateBC) { 781 this->lineTo(pt2); 782 } 783 return; 784 } 785 786 SkVector normalAB, unitAB, normalBC, unitBC; 787 788 this->preJoinTo(pt1, &normalAB, &unitAB, false); 789 790 { 791 SkPoint pts[3], tmp[5]; 792 pts[0] = fPrevPt; 793 pts[1] = pt1; 794 pts[2] = pt2; 795 796 if (SkChopQuadAtMaxCurvature(pts, tmp) == 2) { 797 unitBC.setNormalize(pts[2].fX - pts[1].fX, pts[2].fY - pts[1].fY); 798 unitBC.rotateCCW(); 799 if (normals_too_pinchy(unitAB, unitBC)) { 800 normalBC = unitBC; 801 normalBC.scale(fRadius); 802 803 fOuter.lineTo(tmp[2].fX + normalAB.fX, tmp[2].fY + normalAB.fY); 804 fOuter.lineTo(tmp[2].fX + normalBC.fX, tmp[2].fY + normalBC.fY); 805 fOuter.lineTo(tmp[4].fX + normalBC.fX, tmp[4].fY + normalBC.fY); 806 807 fInner.lineTo(tmp[2].fX - normalAB.fX, tmp[2].fY - normalAB.fY); 808 fInner.lineTo(tmp[2].fX - normalBC.fX, tmp[2].fY - normalBC.fY); 809 fInner.lineTo(tmp[4].fX - normalBC.fX, tmp[4].fY - normalBC.fY); 810 811 fExtra.addCircle(tmp[2].fX, tmp[2].fY, fRadius, 812 SkPath::kCW_Direction); 813 } else { 814 this->quad_to(&tmp[0], normalAB, unitAB, &normalBC, &unitBC, 815 kMaxQuadSubdivide); 816 SkVector n = normalBC; 817 SkVector u = unitBC; 818 this->quad_to(&tmp[2], n, u, &normalBC, &unitBC, 819 kMaxQuadSubdivide); 820 } 821 } else { 822 this->quad_to(pts, normalAB, unitAB, &normalBC, &unitBC, 823 kMaxQuadSubdivide); 824 } 825 } 826#endif 827 828 this->postJoinTo(pt2, normalBC, unitBC); 829} 830 831#if QUAD_STROKE_APPROXIMATION 832// Given a point on the curve and its derivative, scale the derivative by the radius, and 833// compute the perpendicular point and its tangent. 834void SkPathStroker::setRayPts(const SkPoint& tPt, SkVector* dxy, SkPoint* onPt, 835 SkPoint* tangent) const { 836 if (!dxy->setLength(fRadius)) { // consider moving double logic into SkPoint::setLength 837 double xx = dxy->fX; 838 double yy = dxy->fY; 839 double dscale = fRadius / sqrt(xx * xx + yy * yy); 840 dxy->fX = SkDoubleToScalar(xx * dscale); 841 dxy->fY = SkDoubleToScalar(yy * dscale); 842 } 843 SkScalar axisFlip = SkIntToScalar(fStrokeType); // go opposite ways for outer, inner 844 onPt->fX = tPt.fX + axisFlip * dxy->fY; 845 onPt->fY = tPt.fY - axisFlip * dxy->fX; 846 if (tangent) { 847 tangent->fX = onPt->fX + dxy->fX; 848 tangent->fY = onPt->fY + dxy->fY; 849 } 850} 851 852// Given a cubic and t, return the point on curve, its perpendicular, and the perpendicular tangent. 853// Returns false if the perpendicular could not be computed (because the derivative collapsed to 0) 854bool SkPathStroker::cubicPerpRay(const SkPoint cubic[4], SkScalar t, SkPoint* tPt, SkPoint* onPt, 855 SkPoint* tangent) const { 856 SkVector dxy; 857 SkEvalCubicAt(cubic, t, tPt, &dxy, NULL); 858 if (dxy.fX == 0 && dxy.fY == 0) { 859 if (SkScalarNearlyZero(t)) { 860 dxy = cubic[2] - cubic[0]; 861 } else if (SkScalarNearlyZero(1 - t)) { 862 dxy = cubic[3] - cubic[1]; 863 } else { 864 return false; 865 } 866 if (dxy.fX == 0 && dxy.fY == 0) { 867 dxy = cubic[3] - cubic[0]; 868 } 869 } 870 setRayPts(*tPt, &dxy, onPt, tangent); 871 return true; 872} 873 874// Given a cubic and a t range, find the start and end if they haven't been found already. 875bool SkPathStroker::cubicQuadEnds(const SkPoint cubic[4], SkQuadConstruct* quadPts) { 876 if (!quadPts->fStartSet) { 877 SkPoint cubicStartPt; 878 if (!this->cubicPerpRay(cubic, quadPts->fStartT, &cubicStartPt, &quadPts->fQuad[0], 879 &quadPts->fTangentStart)) { 880 return false; 881 } 882 quadPts->fStartSet = true; 883 } 884 if (!quadPts->fEndSet) { 885 SkPoint cubicEndPt; 886 if (!this->cubicPerpRay(cubic, quadPts->fEndT, &cubicEndPt, &quadPts->fQuad[2], 887 &quadPts->fTangentEnd)) { 888 return false; 889 } 890 quadPts->fEndSet = true; 891 } 892 return true; 893} 894 895bool SkPathStroker::cubicQuadMid(const SkPoint cubic[4], const SkQuadConstruct* quadPts, 896 SkPoint* mid) const { 897 SkPoint cubicMidPt; 898 return this->cubicPerpRay(cubic, quadPts->fMidT, &cubicMidPt, mid, NULL); 899} 900 901// Given a quad and t, return the point on curve, its perpendicular, and the perpendicular tangent. 902void SkPathStroker::quadPerpRay(const SkPoint quad[3], SkScalar t, SkPoint* tPt, SkPoint* onPt, 903 SkPoint* tangent) const { 904 SkVector dxy; 905 SkEvalQuadAt(quad, t, tPt, &dxy); 906 if (dxy.fX == 0 && dxy.fY == 0) { 907 dxy = quad[2] - quad[0]; 908 } 909 setRayPts(*tPt, &dxy, onPt, tangent); 910} 911 912// Find the intersection of the stroke tangents to construct a stroke quad. 913// Return whether the stroke is a degenerate (a line), a quad, or must be split. 914// Optionally compute the quad's control point. 915SkPathStroker::ResultType SkPathStroker::intersectRay(SkQuadConstruct* quadPts, 916 IntersectRayType intersectRayType STROKER_DEBUG_PARAMS(int depth)) const { 917 const SkPoint& start = quadPts->fQuad[0]; 918 const SkPoint& end = quadPts->fQuad[2]; 919 SkVector aLen = quadPts->fTangentStart - start; 920 SkVector bLen = quadPts->fTangentEnd - end; 921 SkScalar denom = aLen.cross(bLen); 922 SkVector ab0 = start - end; 923 SkScalar numerA = bLen.cross(ab0); 924 SkScalar numerB = aLen.cross(ab0); 925 if (!SkScalarNearlyZero(denom)) { 926 // if the perpendicular distances from the quad points to the opposite tangent line 927 // are small, a straight line is good enough 928 SkScalar dist1 = pt_to_line(start, end, quadPts->fTangentEnd); 929 SkScalar dist2 = pt_to_line(end, start, quadPts->fTangentStart); 930 if (SkTMax(dist1, dist2) <= fError * fError) { 931 return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts, 932 "SkTMax(dist1=%g, dist2=%g) <= fError * fError", dist1, dist2); 933 } 934 if ((numerA >= 0) != (numerB >= 0)) { 935 if (kCtrlPt_RayType == intersectRayType) { 936 numerA /= denom; 937 SkPoint* ctrlPt = &quadPts->fQuad[1]; 938 ctrlPt->fX = start.fX * (1 - numerA) + quadPts->fTangentStart.fX * numerA; 939 ctrlPt->fY = start.fY * (1 - numerA) + quadPts->fTangentStart.fY * numerA; 940 } 941 return STROKER_RESULT(kQuad_ResultType, depth, quadPts, 942 "(numerA=%g >= 0) != (numerB=%g >= 0)", numerA, numerB); 943 } 944 return STROKER_RESULT(kSplit_ResultType, depth, quadPts, 945 "(numerA=%g >= 0) == (numerB=%g >= 0)", numerA, numerB); 946 } else { // if the lines are parallel, straight line is good enough 947 return STROKER_RESULT(kDegenerate_ResultType, depth, quadPts, 948 "SkScalarNearlyZero(denom=%g)", denom); 949 } 950} 951 952// Given a cubic and a t-range, determine if the stroke can be described by a quadratic. 953SkPathStroker::ResultType SkPathStroker::tangentsMeet(const SkPoint cubic[4], 954 SkQuadConstruct* quadPts) { 955 if (!this->cubicQuadEnds(cubic, quadPts)) { 956 return kNormalError_ResultType; 957 } 958 return intersectRay(quadPts, kResultType_RayType STROKER_DEBUG_PARAMS(fRecursionDepth)); 959} 960 961// Intersect the line with the quad and return the t values on the quad where the line crosses. 962static int intersect_quad_ray(const SkPoint line[2], const SkPoint quad[3], SkScalar roots[2]) { 963 SkVector vec = line[1] - line[0]; 964 SkScalar r[3]; 965 for (int n = 0; n < 3; ++n) { 966 r[n] = (quad[n].fY - line[0].fY) * vec.fX - (quad[n].fX - line[0].fX) * vec.fY; 967 } 968 SkScalar A = r[2]; 969 SkScalar B = r[1]; 970 SkScalar C = r[0]; 971 A += C - 2 * B; // A = a - 2*b + c 972 B -= C; // B = -(b - c) 973 return SkFindUnitQuadRoots(A, 2 * B, C, roots); 974} 975 976// Return true if the point is close to the bounds of the quad. This is used as a quick reject. 977bool SkPathStroker::ptInQuadBounds(const SkPoint quad[3], const SkPoint& pt) const { 978 SkScalar xMin = SkTMin(SkTMin(quad[0].fX, quad[1].fX), quad[2].fX); 979 if (pt.fX + fError < xMin) { 980 return false; 981 } 982 SkScalar xMax = SkTMax(SkTMax(quad[0].fX, quad[1].fX), quad[2].fX); 983 if (pt.fX - fError > xMax) { 984 return false; 985 } 986 SkScalar yMin = SkTMin(SkTMin(quad[0].fY, quad[1].fY), quad[2].fY); 987 if (pt.fY + fError < yMin) { 988 return false; 989 } 990 SkScalar yMax = SkTMax(SkTMax(quad[0].fY, quad[1].fY), quad[2].fY); 991 if (pt.fY - fError > yMax) { 992 return false; 993 } 994 return true; 995} 996 997static bool points_within_dist(const SkPoint& nearPt, const SkPoint& farPt, SkScalar limit) { 998 return nearPt.distanceToSqd(farPt) <= limit * limit; 999} 1000 1001static bool sharp_angle(const SkPoint quad[3]) { 1002 SkVector smaller = quad[1] - quad[0]; 1003 SkVector larger = quad[1] - quad[2]; 1004 SkScalar smallerLen = smaller.lengthSqd(); 1005 SkScalar largerLen = larger.lengthSqd(); 1006 if (smallerLen > largerLen) { 1007 SkTSwap(smaller, larger); 1008 largerLen = smallerLen; 1009 } 1010 if (!smaller.setLength(largerLen)) { 1011 return false; 1012 } 1013 SkScalar dot = smaller.dot(larger); 1014 return dot > 0; 1015} 1016 1017SkPathStroker::ResultType SkPathStroker::strokeCloseEnough(const SkPoint stroke[3], 1018 const SkPoint ray[2], SkQuadConstruct* quadPts STROKER_DEBUG_PARAMS(int depth)) const { 1019 SkPoint strokeMid; 1020 SkEvalQuadAt(stroke, SK_ScalarHalf, &strokeMid); 1021 // measure the distance from the curve to the quad-stroke midpoint, compare to radius 1022 if (points_within_dist(ray[0], strokeMid, fError)) { // if the difference is small 1023 if (sharp_angle(quadPts->fQuad)) { 1024 return STROKER_RESULT(kSplit_ResultType, depth, quadPts, 1025 "sharp_angle (1) =%g,%g, %g,%g, %g,%g", 1026 quadPts->fQuad[0].fX, quadPts->fQuad[0].fY, 1027 quadPts->fQuad[1].fX, quadPts->fQuad[1].fY, 1028 quadPts->fQuad[2].fX, quadPts->fQuad[2].fY); 1029 } 1030 return STROKER_RESULT(kQuad_ResultType, depth, quadPts, 1031 "points_within_dist(ray[0]=%g,%g, strokeMid=%g,%g, fError)", 1032 ray[0].fX, ray[0].fY, strokeMid.fX, strokeMid.fY); 1033 } 1034 // measure the distance to quad's bounds (quick reject) 1035 // an alternative : look for point in triangle 1036 if (!ptInQuadBounds(stroke, ray[0])) { // if far, subdivide 1037 return STROKER_RESULT(kSplit_ResultType, depth, quadPts, 1038 "!pt_in_quad_bounds(stroke=(%g,%g %g,%g %g,%g), ray[0]=%g,%g)", 1039 stroke[0].fX, stroke[0].fY, stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY, 1040 ray[0].fX, ray[0].fY); 1041 } 1042 // measure the curve ray distance to the quad-stroke 1043 SkScalar roots[2]; 1044 int rootCount = intersect_quad_ray(ray, stroke, roots); 1045 if (rootCount != 1) { 1046 return STROKER_RESULT(kSplit_ResultType, depth, quadPts, 1047 "rootCount=%d != 1", rootCount); 1048 } 1049 SkPoint quadPt; 1050 SkEvalQuadAt(stroke, roots[0], &quadPt); 1051 SkScalar error = fError * (SK_Scalar1 - SkScalarAbs(roots[0] - 0.5f) * 2); 1052 if (points_within_dist(ray[0], quadPt, error)) { // if the difference is small, we're done 1053 if (sharp_angle(quadPts->fQuad)) { 1054 return STROKER_RESULT(kSplit_ResultType, depth, quadPts, 1055 "sharp_angle (2) =%g,%g, %g,%g, %g,%g", 1056 quadPts->fQuad[0].fX, quadPts->fQuad[0].fY, 1057 quadPts->fQuad[1].fX, quadPts->fQuad[1].fY, 1058 quadPts->fQuad[2].fX, quadPts->fQuad[2].fY); 1059 } 1060 return STROKER_RESULT(kQuad_ResultType, depth, quadPts, 1061 "points_within_dist(ray[0]=%g,%g, quadPt=%g,%g, error=%g)", 1062 ray[0].fX, ray[0].fY, quadPt.fX, quadPt.fY, error); 1063 } 1064 // otherwise, subdivide 1065 return STROKER_RESULT(kSplit_ResultType, depth, quadPts, "%s", "fall through"); 1066} 1067 1068SkPathStroker::ResultType SkPathStroker::compareQuadCubic(const SkPoint cubic[4], 1069 SkQuadConstruct* quadPts) { 1070 // get the quadratic approximation of the stroke 1071 if (!this->cubicQuadEnds(cubic, quadPts)) { 1072 return kNormalError_ResultType; 1073 } 1074 ResultType resultType = intersectRay(quadPts, kCtrlPt_RayType 1075 STROKER_DEBUG_PARAMS(fRecursionDepth) ); 1076 if (resultType != kQuad_ResultType) { 1077 return resultType; 1078 } 1079 // project a ray from the curve to the stroke 1080 SkPoint ray[2]; // point near midpoint on quad, midpoint on cubic 1081 if (!this->cubicPerpRay(cubic, quadPts->fMidT, &ray[1], &ray[0], NULL)) { 1082 return kNormalError_ResultType; 1083 } 1084 return strokeCloseEnough(quadPts->fQuad, ray, quadPts STROKER_DEBUG_PARAMS(fRecursionDepth)); 1085} 1086 1087// if false is returned, caller splits quadratic approximation 1088SkPathStroker::ResultType SkPathStroker::compareQuadQuad(const SkPoint quad[3], 1089 SkQuadConstruct* quadPts) { 1090 // get the quadratic approximation of the stroke 1091 if (!quadPts->fStartSet) { 1092 SkPoint quadStartPt; 1093 this->quadPerpRay(quad, quadPts->fStartT, &quadStartPt, &quadPts->fQuad[0], 1094 &quadPts->fTangentStart); 1095 quadPts->fStartSet = true; 1096 } 1097 if (!quadPts->fEndSet) { 1098 SkPoint quadEndPt; 1099 this->quadPerpRay(quad, quadPts->fEndT, &quadEndPt, &quadPts->fQuad[2], 1100 &quadPts->fTangentEnd); 1101 quadPts->fEndSet = true; 1102 } 1103 ResultType resultType = intersectRay(quadPts, kCtrlPt_RayType 1104 STROKER_DEBUG_PARAMS(fRecursionDepth)); 1105 if (resultType != kQuad_ResultType) { 1106 return resultType; 1107 } 1108 // project a ray from the curve to the stroke 1109 SkPoint ray[2]; 1110 this->quadPerpRay(quad, quadPts->fMidT, &ray[1], &ray[0], NULL); 1111 return strokeCloseEnough(quadPts->fQuad, ray, quadPts STROKER_DEBUG_PARAMS(fRecursionDepth)); 1112} 1113 1114void SkPathStroker::addDegenerateLine(const SkQuadConstruct* quadPts) { 1115 const SkPoint* quad = quadPts->fQuad; 1116 SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner; 1117 path->lineTo(quad[2].fX, quad[2].fY); 1118} 1119 1120bool SkPathStroker::cubicMidOnLine(const SkPoint cubic[4], const SkQuadConstruct* quadPts) const { 1121 SkPoint strokeMid; 1122 if (!cubicQuadMid(cubic, quadPts, &strokeMid)) { 1123 return false; 1124 } 1125 SkScalar dist = pt_to_line(strokeMid, quadPts->fQuad[0], quadPts->fQuad[2]); 1126 return dist < fError * fError; 1127} 1128 1129bool SkPathStroker::cubicStroke(const SkPoint cubic[4], SkQuadConstruct* quadPts) { 1130 if (!fFoundTangents) { 1131 ResultType resultType = this->tangentsMeet(cubic, quadPts); 1132 if (kQuad_ResultType != resultType) { 1133 if (kNormalError_ResultType == resultType) { 1134 return false; 1135 } 1136 if ((kDegenerate_ResultType == resultType 1137 || points_within_dist(quadPts->fQuad[0], quadPts->fQuad[2], fError)) 1138 && cubicMidOnLine(cubic, quadPts)) { 1139 addDegenerateLine(quadPts); 1140 return true; 1141 } 1142 } else { 1143 fFoundTangents = true; 1144 } 1145 } 1146 if (fFoundTangents) { 1147 ResultType resultType = this->compareQuadCubic(cubic, quadPts); 1148 if (kQuad_ResultType == resultType) { 1149 SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner; 1150 const SkPoint* stroke = quadPts->fQuad; 1151 path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY); 1152 return true; 1153 } 1154 if (kDegenerate_ResultType == resultType) { 1155 addDegenerateLine(quadPts); 1156 return true; 1157 } 1158 if (kNormalError_ResultType == resultType) { 1159 return false; 1160 } 1161 } 1162 if (!SkScalarIsFinite(quadPts->fQuad[2].fX) || !SkScalarIsFinite(quadPts->fQuad[2].fY)) { 1163 return false; // just abort if projected quad isn't representable 1164 } 1165 SkDEBUGCODE(gMaxRecursion[fFoundTangents] = SkTMax(gMaxRecursion[fFoundTangents], 1166 fRecursionDepth + 1)); 1167 if (++fRecursionDepth > kRecursiveLimits[fFoundTangents]) { 1168 return false; // just abort if projected quad isn't representable 1169 } 1170 SkQuadConstruct half; 1171 if (!half.initWithStart(quadPts)) { 1172 addDegenerateLine(quadPts); 1173 return true; 1174 } 1175 if (!this->cubicStroke(cubic, &half)) { 1176 return false; 1177 } 1178 if (!half.initWithEnd(quadPts)) { 1179 addDegenerateLine(quadPts); 1180 return true; 1181 } 1182 if (!this->cubicStroke(cubic, &half)) { 1183 return false; 1184 } 1185 --fRecursionDepth; 1186 return true; 1187} 1188 1189bool SkPathStroker::quadStroke(const SkPoint quad[3], SkQuadConstruct* quadPts) { 1190 ResultType resultType = this->compareQuadQuad(quad, quadPts); 1191 if (kQuad_ResultType == resultType) { 1192 const SkPoint* stroke = quadPts->fQuad; 1193 SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner; 1194 path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY); 1195 return true; 1196 } 1197 if (kDegenerate_ResultType == resultType) { 1198 addDegenerateLine(quadPts); 1199 return true; 1200 } 1201 SkDEBUGCODE(gMaxRecursion[kQuad_RecursiveLimit] = SkTMax(gMaxRecursion[kQuad_RecursiveLimit], 1202 fRecursionDepth + 1)); 1203 if (++fRecursionDepth > kRecursiveLimits[kQuad_RecursiveLimit]) { 1204 return false; // just abort if projected quad isn't representable 1205 } 1206 SkQuadConstruct half; 1207 (void) half.initWithStart(quadPts); 1208 if (!this->quadStroke(quad, &half)) { 1209 return false; 1210 } 1211 (void) half.initWithEnd(quadPts); 1212 if (!this->quadStroke(quad, &half)) { 1213 return false; 1214 } 1215 --fRecursionDepth; 1216 return true; 1217} 1218 1219#endif 1220 1221void SkPathStroker::cubicTo(const SkPoint& pt1, const SkPoint& pt2, 1222 const SkPoint& pt3) { 1223#if QUAD_STROKE_APPROXIMATION 1224 const SkPoint cubic[4] = { fPrevPt, pt1, pt2, pt3 }; 1225 SkPoint reduction[3]; 1226 const SkPoint* tangentPt; 1227 ReductionType reductionType = CheckCubicLinear(cubic, reduction, &tangentPt); 1228 if (kPoint_ReductionType == reductionType) { 1229 return; 1230 } 1231 if (kLine_ReductionType == reductionType) { 1232 this->lineTo(pt3); 1233 return; 1234 } 1235 if (kDegenerate_ReductionType <= reductionType && kDegenerate3_ReductionType >= reductionType) { 1236 this->lineTo(reduction[0]); 1237 SkStrokerPriv::JoinProc saveJoiner = fJoiner; 1238 fJoiner = SkStrokerPriv::JoinFactory(SkPaint::kRound_Join); 1239 if (kDegenerate2_ReductionType <= reductionType) { 1240 this->lineTo(reduction[1]); 1241 } 1242 if (kDegenerate3_ReductionType == reductionType) { 1243 this->lineTo(reduction[2]); 1244 } 1245 this->lineTo(pt3); 1246 fJoiner = saveJoiner; 1247 return; 1248 } 1249 SkASSERT(kQuad_ReductionType == reductionType); 1250 SkVector normalAB, unitAB, normalCD, unitCD; 1251 this->preJoinTo(*tangentPt, &normalAB, &unitAB, false); 1252 SkScalar tValues[2]; 1253 int count = SkFindCubicInflections(cubic, tValues); 1254 SkScalar lastT = 0; 1255 for (int index = 0; index <= count; ++index) { 1256 SkScalar nextT = index < count ? tValues[index] : 1; 1257 SkQuadConstruct quadPts; 1258 this->init(kOuter_StrokeType, &quadPts, lastT, nextT); 1259 if (!this->cubicStroke(cubic, &quadPts)) { 1260 return; 1261 } 1262 this->init(kInner_StrokeType, &quadPts, lastT, nextT); 1263 if (!this->cubicStroke(cubic, &quadPts)) { 1264 return; 1265 } 1266 lastT = nextT; 1267 } 1268 this->setCubicEndNormal(cubic, normalAB, unitAB, &normalCD, &unitCD); 1269#else 1270 bool degenerateAB = SkPath::IsLineDegenerate(fPrevPt, pt1); 1271 bool degenerateBC = SkPath::IsLineDegenerate(pt1, pt2); 1272 bool degenerateCD = SkPath::IsLineDegenerate(pt2, pt3); 1273 1274 if (degenerateAB + degenerateBC + degenerateCD >= 2 1275 || (degenerateAB && SkPath::IsLineDegenerate(fPrevPt, pt2))) { 1276 this->lineTo(pt3); 1277 return; 1278 } 1279 1280 SkVector normalAB, unitAB, normalCD, unitCD; 1281 1282 // find the first tangent (which might be pt1 or pt2 1283 { 1284 const SkPoint* nextPt = &pt1; 1285 if (degenerateAB) 1286 nextPt = &pt2; 1287 this->preJoinTo(*nextPt, &normalAB, &unitAB, false); 1288 } 1289 1290 { 1291 SkPoint pts[4], tmp[13]; 1292 int i, count; 1293 SkVector n, u; 1294 SkScalar tValues[3]; 1295 1296 pts[0] = fPrevPt; 1297 pts[1] = pt1; 1298 pts[2] = pt2; 1299 pts[3] = pt3; 1300 1301 count = SkChopCubicAtMaxCurvature(pts, tmp, tValues); 1302 n = normalAB; 1303 u = unitAB; 1304 for (i = 0; i < count; i++) { 1305 this->cubic_to(&tmp[i * 3], n, u, &normalCD, &unitCD, 1306 kMaxCubicSubdivide); 1307 if (i == count - 1) { 1308 break; 1309 } 1310 n = normalCD; 1311 u = unitCD; 1312 1313 } 1314 } 1315#endif 1316 1317 this->postJoinTo(pt3, normalCD, unitCD); 1318} 1319 1320/////////////////////////////////////////////////////////////////////////////// 1321/////////////////////////////////////////////////////////////////////////////// 1322 1323#include "SkPaintDefaults.h" 1324 1325SkStroke::SkStroke() { 1326 fWidth = SK_Scalar1; 1327 fMiterLimit = SkPaintDefaults_MiterLimit; 1328 fCap = SkPaint::kDefault_Cap; 1329 fJoin = SkPaint::kDefault_Join; 1330 fDoFill = false; 1331} 1332 1333SkStroke::SkStroke(const SkPaint& p) { 1334 fWidth = p.getStrokeWidth(); 1335 fMiterLimit = p.getStrokeMiter(); 1336 fCap = (uint8_t)p.getStrokeCap(); 1337 fJoin = (uint8_t)p.getStrokeJoin(); 1338 fDoFill = SkToU8(p.getStyle() == SkPaint::kStrokeAndFill_Style); 1339} 1340 1341SkStroke::SkStroke(const SkPaint& p, SkScalar width) { 1342 fWidth = width; 1343 fMiterLimit = p.getStrokeMiter(); 1344 fCap = (uint8_t)p.getStrokeCap(); 1345 fJoin = (uint8_t)p.getStrokeJoin(); 1346 fDoFill = SkToU8(p.getStyle() == SkPaint::kStrokeAndFill_Style); 1347} 1348 1349#if QUAD_STROKE_APPROXIMATION 1350void SkStroke::setError(SkScalar error) { 1351 SkASSERT(error > 0); 1352 fError = error; 1353} 1354#endif 1355 1356void SkStroke::setWidth(SkScalar width) { 1357 SkASSERT(width >= 0); 1358 fWidth = width; 1359} 1360 1361void SkStroke::setMiterLimit(SkScalar miterLimit) { 1362 SkASSERT(miterLimit >= 0); 1363 fMiterLimit = miterLimit; 1364} 1365 1366void SkStroke::setCap(SkPaint::Cap cap) { 1367 SkASSERT((unsigned)cap < SkPaint::kCapCount); 1368 fCap = SkToU8(cap); 1369} 1370 1371void SkStroke::setJoin(SkPaint::Join join) { 1372 SkASSERT((unsigned)join < SkPaint::kJoinCount); 1373 fJoin = SkToU8(join); 1374} 1375 1376/////////////////////////////////////////////////////////////////////////////// 1377 1378// If src==dst, then we use a tmp path to record the stroke, and then swap 1379// its contents with src when we're done. 1380class AutoTmpPath { 1381public: 1382 AutoTmpPath(const SkPath& src, SkPath** dst) : fSrc(src) { 1383 if (&src == *dst) { 1384 *dst = &fTmpDst; 1385 fSwapWithSrc = true; 1386 } else { 1387 (*dst)->reset(); 1388 fSwapWithSrc = false; 1389 } 1390 } 1391 1392 ~AutoTmpPath() { 1393 if (fSwapWithSrc) { 1394 fTmpDst.swap(*const_cast<SkPath*>(&fSrc)); 1395 } 1396 } 1397 1398private: 1399 SkPath fTmpDst; 1400 const SkPath& fSrc; 1401 bool fSwapWithSrc; 1402}; 1403 1404void SkStroke::strokePath(const SkPath& src, SkPath* dst) const { 1405 SkASSERT(&src != NULL && dst != NULL); 1406 1407 SkScalar radius = SkScalarHalf(fWidth); 1408 1409 AutoTmpPath tmp(src, &dst); 1410 1411 if (radius <= 0) { 1412 return; 1413 } 1414 1415 // If src is really a rect, call our specialty strokeRect() method 1416 { 1417 bool isClosed; 1418 SkPath::Direction dir; 1419 if (src.isRect(&isClosed, &dir) && isClosed) { 1420 this->strokeRect(src.getBounds(), dst, dir); 1421 // our answer should preserve the inverseness of the src 1422 if (src.isInverseFillType()) { 1423 SkASSERT(!dst->isInverseFillType()); 1424 dst->toggleInverseFillType(); 1425 } 1426 return; 1427 } 1428 } 1429 1430 SkAutoConicToQuads converter; 1431 const SkScalar conicTol = SK_Scalar1 / 4; 1432 1433#if QUAD_STROKE_APPROXIMATION 1434 SkPathStroker stroker(src, radius, fMiterLimit, fError, this->getCap(), 1435 this->getJoin()); 1436#else 1437 SkPathStroker stroker(src, radius, fMiterLimit, this->getCap(), 1438 this->getJoin()); 1439#endif 1440 SkPath::Iter iter(src, false); 1441 SkPath::Verb lastSegment = SkPath::kMove_Verb; 1442 1443 for (;;) { 1444 SkPoint pts[4]; 1445 switch (iter.next(pts, false)) { 1446 case SkPath::kMove_Verb: 1447 stroker.moveTo(pts[0]); 1448 break; 1449 case SkPath::kLine_Verb: 1450 stroker.lineTo(pts[1]); 1451 lastSegment = SkPath::kLine_Verb; 1452 break; 1453 case SkPath::kQuad_Verb: 1454 stroker.quadTo(pts[1], pts[2]); 1455 lastSegment = SkPath::kQuad_Verb; 1456 break; 1457 case SkPath::kConic_Verb: { 1458 // todo: if we had maxcurvature for conics, perhaps we should 1459 // natively extrude the conic instead of converting to quads. 1460 const SkPoint* quadPts = 1461 converter.computeQuads(pts, iter.conicWeight(), conicTol); 1462 for (int i = 0; i < converter.countQuads(); ++i) { 1463 stroker.quadTo(quadPts[1], quadPts[2]); 1464 quadPts += 2; 1465 } 1466 lastSegment = SkPath::kQuad_Verb; 1467 } break; 1468 case SkPath::kCubic_Verb: 1469 stroker.cubicTo(pts[1], pts[2], pts[3]); 1470 lastSegment = SkPath::kCubic_Verb; 1471 break; 1472 case SkPath::kClose_Verb: 1473 stroker.close(lastSegment == SkPath::kLine_Verb); 1474 break; 1475 case SkPath::kDone_Verb: 1476 goto DONE; 1477 } 1478 } 1479DONE: 1480 stroker.done(dst, lastSegment == SkPath::kLine_Verb); 1481 1482 if (fDoFill) { 1483 if (src.cheapIsDirection(SkPath::kCCW_Direction)) { 1484 dst->reverseAddPath(src); 1485 } else { 1486 dst->addPath(src); 1487 } 1488 } else { 1489 // Seems like we can assume that a 2-point src would always result in 1490 // a convex stroke, but testing has proved otherwise. 1491 // TODO: fix the stroker to make this assumption true (without making 1492 // it slower that the work that will be done in computeConvexity()) 1493#if 0 1494 // this test results in a non-convex stroke :( 1495 static void test(SkCanvas* canvas) { 1496 SkPoint pts[] = { 146.333328, 192.333328, 300.333344, 293.333344 }; 1497 SkPaint paint; 1498 paint.setStrokeWidth(7); 1499 paint.setStrokeCap(SkPaint::kRound_Cap); 1500 canvas->drawLine(pts[0].fX, pts[0].fY, pts[1].fX, pts[1].fY, paint); 1501 } 1502#endif 1503#if 0 1504 if (2 == src.countPoints()) { 1505 dst->setIsConvex(true); 1506 } 1507#endif 1508 } 1509 1510 // our answer should preserve the inverseness of the src 1511 if (src.isInverseFillType()) { 1512 SkASSERT(!dst->isInverseFillType()); 1513 dst->toggleInverseFillType(); 1514 } 1515} 1516 1517static SkPath::Direction reverse_direction(SkPath::Direction dir) { 1518 SkASSERT(SkPath::kUnknown_Direction != dir); 1519 return SkPath::kCW_Direction == dir ? SkPath::kCCW_Direction : SkPath::kCW_Direction; 1520} 1521 1522static void addBevel(SkPath* path, const SkRect& r, const SkRect& outer, SkPath::Direction dir) { 1523 SkPoint pts[8]; 1524 1525 if (SkPath::kCW_Direction == dir) { 1526 pts[0].set(r.fLeft, outer.fTop); 1527 pts[1].set(r.fRight, outer.fTop); 1528 pts[2].set(outer.fRight, r.fTop); 1529 pts[3].set(outer.fRight, r.fBottom); 1530 pts[4].set(r.fRight, outer.fBottom); 1531 pts[5].set(r.fLeft, outer.fBottom); 1532 pts[6].set(outer.fLeft, r.fBottom); 1533 pts[7].set(outer.fLeft, r.fTop); 1534 } else { 1535 pts[7].set(r.fLeft, outer.fTop); 1536 pts[6].set(r.fRight, outer.fTop); 1537 pts[5].set(outer.fRight, r.fTop); 1538 pts[4].set(outer.fRight, r.fBottom); 1539 pts[3].set(r.fRight, outer.fBottom); 1540 pts[2].set(r.fLeft, outer.fBottom); 1541 pts[1].set(outer.fLeft, r.fBottom); 1542 pts[0].set(outer.fLeft, r.fTop); 1543 } 1544 path->addPoly(pts, 8, true); 1545} 1546 1547void SkStroke::strokeRect(const SkRect& origRect, SkPath* dst, 1548 SkPath::Direction dir) const { 1549 SkASSERT(dst != NULL); 1550 dst->reset(); 1551 1552 SkScalar radius = SkScalarHalf(fWidth); 1553 if (radius <= 0) { 1554 return; 1555 } 1556 1557 SkScalar rw = origRect.width(); 1558 SkScalar rh = origRect.height(); 1559 if ((rw < 0) ^ (rh < 0)) { 1560 dir = reverse_direction(dir); 1561 } 1562 SkRect rect(origRect); 1563 rect.sort(); 1564 // reassign these, now that we know they'll be >= 0 1565 rw = rect.width(); 1566 rh = rect.height(); 1567 1568 SkRect r(rect); 1569 r.outset(radius, radius); 1570 1571 SkPaint::Join join = (SkPaint::Join)fJoin; 1572 if (SkPaint::kMiter_Join == join && fMiterLimit < SK_ScalarSqrt2) { 1573 join = SkPaint::kBevel_Join; 1574 } 1575 1576 switch (join) { 1577 case SkPaint::kMiter_Join: 1578 dst->addRect(r, dir); 1579 break; 1580 case SkPaint::kBevel_Join: 1581 addBevel(dst, rect, r, dir); 1582 break; 1583 case SkPaint::kRound_Join: 1584 dst->addRoundRect(r, radius, radius, dir); 1585 break; 1586 default: 1587 break; 1588 } 1589 1590 if (fWidth < SkMinScalar(rw, rh) && !fDoFill) { 1591 r = rect; 1592 r.inset(radius, radius); 1593 dst->addRect(r, reverse_direction(dir)); 1594 } 1595} 1596