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