reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1 | /* |
epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 2 | * Copyright 2008 The Android Open Source Project |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 3 | * |
epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 6 | */ |
| 7 | |
| 8 | #include "SkStrokerPriv.h" |
| 9 | #include "SkGeometry.h" |
| 10 | #include "SkPath.h" |
| 11 | |
| 12 | #define kMaxQuadSubdivide 5 |
reed@google.com | 7a90daf | 2013-04-10 18:44:00 +0000 | [diff] [blame] | 13 | #define kMaxCubicSubdivide 7 |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 14 | |
| 15 | static inline bool degenerate_vector(const SkVector& v) { |
reed@google.com | 55b5f4b | 2011-09-07 12:23:41 +0000 | [diff] [blame] | 16 | return !SkPoint::CanNormalize(v.fX, v.fY); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 17 | } |
| 18 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 19 | static inline bool normals_too_curvy(const SkVector& norm0, SkVector& norm1) { |
| 20 | /* root2/2 is a 45-degree angle |
| 21 | make this constant bigger for more subdivisions (but not >= 1) |
| 22 | */ |
| 23 | static const SkScalar kFlatEnoughNormalDotProd = |
| 24 | SK_ScalarSqrt2/2 + SK_Scalar1/10; |
| 25 | |
| 26 | SkASSERT(kFlatEnoughNormalDotProd > 0 && |
| 27 | kFlatEnoughNormalDotProd < SK_Scalar1); |
| 28 | |
| 29 | return SkPoint::DotProduct(norm0, norm1) <= kFlatEnoughNormalDotProd; |
| 30 | } |
| 31 | |
| 32 | static inline bool normals_too_pinchy(const SkVector& norm0, SkVector& norm1) { |
reed@google.com | 439df28 | 2013-08-15 20:57:42 +0000 | [diff] [blame] | 33 | // if the dot-product is -1, then we are definitely too pinchy. We tweak |
| 34 | // that by an epsilon to ensure we have significant bits in our test |
| 35 | static const int kMinSigBitsForDot = 8; |
| 36 | static const SkScalar kDotEpsilon = FLT_EPSILON * (1 << kMinSigBitsForDot); |
| 37 | static const SkScalar kTooPinchyNormalDotProd = kDotEpsilon - 1; |
skia.committer@gmail.com | c9917c0 | 2013-08-16 07:01:49 +0000 | [diff] [blame] | 38 | |
reed@google.com | 439df28 | 2013-08-15 20:57:42 +0000 | [diff] [blame] | 39 | // just some sanity asserts to help document the expected range |
| 40 | SkASSERT(kTooPinchyNormalDotProd >= -1); |
| 41 | SkASSERT(kTooPinchyNormalDotProd < SkDoubleToScalar(-0.999)); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 42 | |
reed@google.com | 439df28 | 2013-08-15 20:57:42 +0000 | [diff] [blame] | 43 | SkScalar dot = SkPoint::DotProduct(norm0, norm1); |
| 44 | return dot <= kTooPinchyNormalDotProd; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 45 | } |
| 46 | |
| 47 | static bool set_normal_unitnormal(const SkPoint& before, const SkPoint& after, |
| 48 | SkScalar radius, |
| 49 | SkVector* normal, SkVector* unitNormal) { |
| 50 | if (!unitNormal->setNormalize(after.fX - before.fX, after.fY - before.fY)) { |
| 51 | return false; |
| 52 | } |
| 53 | unitNormal->rotateCCW(); |
| 54 | unitNormal->scale(radius, normal); |
| 55 | return true; |
| 56 | } |
| 57 | |
| 58 | static bool set_normal_unitnormal(const SkVector& vec, |
| 59 | SkScalar radius, |
| 60 | SkVector* normal, SkVector* unitNormal) { |
| 61 | if (!unitNormal->setNormalize(vec.fX, vec.fY)) { |
| 62 | return false; |
| 63 | } |
| 64 | unitNormal->rotateCCW(); |
| 65 | unitNormal->scale(radius, normal); |
| 66 | return true; |
| 67 | } |
| 68 | |
| 69 | /////////////////////////////////////////////////////////////////////////////// |
| 70 | |
| 71 | class SkPathStroker { |
| 72 | public: |
reed@google.com | 2e0d727 | 2012-05-15 13:33:57 +0000 | [diff] [blame] | 73 | SkPathStroker(const SkPath& src, |
| 74 | SkScalar radius, SkScalar miterLimit, SkPaint::Cap cap, |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 75 | SkPaint::Join join); |
| 76 | |
| 77 | void moveTo(const SkPoint&); |
| 78 | void lineTo(const SkPoint&); |
| 79 | void quadTo(const SkPoint&, const SkPoint&); |
| 80 | void cubicTo(const SkPoint&, const SkPoint&, const SkPoint&); |
| 81 | void close(bool isLine) { this->finishContour(true, isLine); } |
| 82 | |
| 83 | void done(SkPath* dst, bool isLine) { |
| 84 | this->finishContour(false, isLine); |
| 85 | fOuter.addPath(fExtra); |
| 86 | dst->swap(fOuter); |
| 87 | } |
| 88 | |
| 89 | private: |
| 90 | SkScalar fRadius; |
| 91 | SkScalar fInvMiterLimit; |
| 92 | |
| 93 | SkVector fFirstNormal, fPrevNormal, fFirstUnitNormal, fPrevUnitNormal; |
| 94 | SkPoint fFirstPt, fPrevPt; // on original path |
| 95 | SkPoint fFirstOuterPt; |
| 96 | int fSegmentCount; |
| 97 | bool fPrevIsLine; |
| 98 | |
| 99 | SkStrokerPriv::CapProc fCapper; |
| 100 | SkStrokerPriv::JoinProc fJoiner; |
| 101 | |
| 102 | SkPath fInner, fOuter; // outer is our working answer, inner is temp |
| 103 | SkPath fExtra; // added as extra complete contours |
| 104 | |
| 105 | void finishContour(bool close, bool isLine); |
| 106 | void preJoinTo(const SkPoint&, SkVector* normal, SkVector* unitNormal, |
| 107 | bool isLine); |
| 108 | void postJoinTo(const SkPoint&, const SkVector& normal, |
| 109 | const SkVector& unitNormal); |
| 110 | |
| 111 | void line_to(const SkPoint& currPt, const SkVector& normal); |
| 112 | void quad_to(const SkPoint pts[3], |
| 113 | const SkVector& normalAB, const SkVector& unitNormalAB, |
| 114 | SkVector* normalBC, SkVector* unitNormalBC, |
| 115 | int subDivide); |
| 116 | void cubic_to(const SkPoint pts[4], |
| 117 | const SkVector& normalAB, const SkVector& unitNormalAB, |
| 118 | SkVector* normalCD, SkVector* unitNormalCD, |
| 119 | int subDivide); |
| 120 | }; |
| 121 | |
| 122 | /////////////////////////////////////////////////////////////////////////////// |
| 123 | |
| 124 | void SkPathStroker::preJoinTo(const SkPoint& currPt, SkVector* normal, |
| 125 | SkVector* unitNormal, bool currIsLine) { |
| 126 | SkASSERT(fSegmentCount >= 0); |
| 127 | |
| 128 | SkScalar prevX = fPrevPt.fX; |
| 129 | SkScalar prevY = fPrevPt.fY; |
| 130 | |
| 131 | SkAssertResult(set_normal_unitnormal(fPrevPt, currPt, fRadius, normal, |
| 132 | unitNormal)); |
| 133 | |
| 134 | if (fSegmentCount == 0) { |
| 135 | fFirstNormal = *normal; |
| 136 | fFirstUnitNormal = *unitNormal; |
| 137 | fFirstOuterPt.set(prevX + normal->fX, prevY + normal->fY); |
| 138 | |
| 139 | fOuter.moveTo(fFirstOuterPt.fX, fFirstOuterPt.fY); |
| 140 | fInner.moveTo(prevX - normal->fX, prevY - normal->fY); |
| 141 | } else { // we have a previous segment |
| 142 | fJoiner(&fOuter, &fInner, fPrevUnitNormal, fPrevPt, *unitNormal, |
| 143 | fRadius, fInvMiterLimit, fPrevIsLine, currIsLine); |
| 144 | } |
| 145 | fPrevIsLine = currIsLine; |
| 146 | } |
| 147 | |
| 148 | void SkPathStroker::postJoinTo(const SkPoint& currPt, const SkVector& normal, |
| 149 | const SkVector& unitNormal) { |
| 150 | fPrevPt = currPt; |
| 151 | fPrevUnitNormal = unitNormal; |
| 152 | fPrevNormal = normal; |
| 153 | fSegmentCount += 1; |
| 154 | } |
| 155 | |
| 156 | void SkPathStroker::finishContour(bool close, bool currIsLine) { |
| 157 | if (fSegmentCount > 0) { |
| 158 | SkPoint pt; |
| 159 | |
| 160 | if (close) { |
| 161 | fJoiner(&fOuter, &fInner, fPrevUnitNormal, fPrevPt, |
| 162 | fFirstUnitNormal, fRadius, fInvMiterLimit, |
| 163 | fPrevIsLine, currIsLine); |
| 164 | fOuter.close(); |
| 165 | // now add fInner as its own contour |
| 166 | fInner.getLastPt(&pt); |
| 167 | fOuter.moveTo(pt.fX, pt.fY); |
| 168 | fOuter.reversePathTo(fInner); |
| 169 | fOuter.close(); |
| 170 | } else { // add caps to start and end |
| 171 | // cap the end |
| 172 | fInner.getLastPt(&pt); |
| 173 | fCapper(&fOuter, fPrevPt, fPrevNormal, pt, |
| 174 | currIsLine ? &fInner : NULL); |
| 175 | fOuter.reversePathTo(fInner); |
| 176 | // cap the start |
| 177 | fCapper(&fOuter, fFirstPt, -fFirstNormal, fFirstOuterPt, |
| 178 | fPrevIsLine ? &fInner : NULL); |
| 179 | fOuter.close(); |
| 180 | } |
| 181 | } |
reed@google.com | 2e0d727 | 2012-05-15 13:33:57 +0000 | [diff] [blame] | 182 | // since we may re-use fInner, we rewind instead of reset, to save on |
| 183 | // reallocating its internal storage. |
| 184 | fInner.rewind(); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 185 | fSegmentCount = -1; |
| 186 | } |
| 187 | |
| 188 | /////////////////////////////////////////////////////////////////////////////// |
| 189 | |
reed@google.com | 2e0d727 | 2012-05-15 13:33:57 +0000 | [diff] [blame] | 190 | SkPathStroker::SkPathStroker(const SkPath& src, |
| 191 | SkScalar radius, SkScalar miterLimit, |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 192 | SkPaint::Cap cap, SkPaint::Join join) |
| 193 | : fRadius(radius) { |
| 194 | |
| 195 | /* This is only used when join is miter_join, but we initialize it here |
| 196 | so that it is always defined, to fis valgrind warnings. |
| 197 | */ |
| 198 | fInvMiterLimit = 0; |
| 199 | |
| 200 | if (join == SkPaint::kMiter_Join) { |
| 201 | if (miterLimit <= SK_Scalar1) { |
| 202 | join = SkPaint::kBevel_Join; |
| 203 | } else { |
| 204 | fInvMiterLimit = SkScalarInvert(miterLimit); |
| 205 | } |
| 206 | } |
| 207 | fCapper = SkStrokerPriv::CapFactory(cap); |
| 208 | fJoiner = SkStrokerPriv::JoinFactory(join); |
| 209 | fSegmentCount = -1; |
| 210 | fPrevIsLine = false; |
reed@google.com | 2e0d727 | 2012-05-15 13:33:57 +0000 | [diff] [blame] | 211 | |
| 212 | // Need some estimate of how large our final result (fOuter) |
| 213 | // and our per-contour temp (fInner) will be, so we don't spend |
| 214 | // extra time repeatedly growing these arrays. |
| 215 | // |
| 216 | // 3x for result == inner + outer + join (swag) |
| 217 | // 1x for inner == 'wag' (worst contour length would be better guess) |
| 218 | fOuter.incReserve(src.countPoints() * 3); |
| 219 | fInner.incReserve(src.countPoints()); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 220 | } |
| 221 | |
| 222 | void SkPathStroker::moveTo(const SkPoint& pt) { |
| 223 | if (fSegmentCount > 0) { |
| 224 | this->finishContour(false, false); |
| 225 | } |
| 226 | fSegmentCount = 0; |
| 227 | fFirstPt = fPrevPt = pt; |
| 228 | } |
| 229 | |
| 230 | void SkPathStroker::line_to(const SkPoint& currPt, const SkVector& normal) { |
| 231 | fOuter.lineTo(currPt.fX + normal.fX, currPt.fY + normal.fY); |
| 232 | fInner.lineTo(currPt.fX - normal.fX, currPt.fY - normal.fY); |
| 233 | } |
| 234 | |
| 235 | void SkPathStroker::lineTo(const SkPoint& currPt) { |
schenney@chromium.org | 4da06ab | 2011-12-20 15:14:18 +0000 | [diff] [blame] | 236 | if (SkPath::IsLineDegenerate(fPrevPt, currPt)) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 237 | return; |
| 238 | } |
| 239 | SkVector normal, unitNormal; |
| 240 | |
| 241 | this->preJoinTo(currPt, &normal, &unitNormal, true); |
| 242 | this->line_to(currPt, normal); |
| 243 | this->postJoinTo(currPt, normal, unitNormal); |
| 244 | } |
| 245 | |
| 246 | void SkPathStroker::quad_to(const SkPoint pts[3], |
| 247 | const SkVector& normalAB, const SkVector& unitNormalAB, |
| 248 | SkVector* normalBC, SkVector* unitNormalBC, |
| 249 | int subDivide) { |
| 250 | if (!set_normal_unitnormal(pts[1], pts[2], fRadius, |
| 251 | normalBC, unitNormalBC)) { |
| 252 | // pts[1] nearly equals pts[2], so just draw a line to pts[2] |
| 253 | this->line_to(pts[2], normalAB); |
| 254 | *normalBC = normalAB; |
| 255 | *unitNormalBC = unitNormalAB; |
| 256 | return; |
| 257 | } |
| 258 | |
| 259 | if (--subDivide >= 0 && normals_too_curvy(unitNormalAB, *unitNormalBC)) { |
| 260 | SkPoint tmp[5]; |
| 261 | SkVector norm, unit; |
| 262 | |
| 263 | SkChopQuadAtHalf(pts, tmp); |
| 264 | this->quad_to(&tmp[0], normalAB, unitNormalAB, &norm, &unit, subDivide); |
| 265 | this->quad_to(&tmp[2], norm, unit, normalBC, unitNormalBC, subDivide); |
| 266 | } else { |
mike@reedtribe.org | dec8125 | 2012-12-24 03:10:30 +0000 | [diff] [blame] | 267 | SkVector normalB; |
skia.committer@gmail.com | 2157983 | 2012-12-25 02:01:27 +0000 | [diff] [blame] | 268 | |
mike@reedtribe.org | dec8125 | 2012-12-24 03:10:30 +0000 | [diff] [blame] | 269 | normalB = pts[2] - pts[0]; |
| 270 | normalB.rotateCCW(); |
| 271 | SkScalar dot = SkPoint::DotProduct(unitNormalAB, *unitNormalBC); |
| 272 | SkAssertResult(normalB.setLength(SkScalarDiv(fRadius, |
| 273 | SkScalarSqrt((SK_Scalar1 + dot)/2)))); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 274 | |
| 275 | fOuter.quadTo( pts[1].fX + normalB.fX, pts[1].fY + normalB.fY, |
| 276 | pts[2].fX + normalBC->fX, pts[2].fY + normalBC->fY); |
| 277 | fInner.quadTo( pts[1].fX - normalB.fX, pts[1].fY - normalB.fY, |
| 278 | pts[2].fX - normalBC->fX, pts[2].fY - normalBC->fY); |
| 279 | } |
| 280 | } |
| 281 | |
| 282 | void SkPathStroker::cubic_to(const SkPoint pts[4], |
| 283 | const SkVector& normalAB, const SkVector& unitNormalAB, |
| 284 | SkVector* normalCD, SkVector* unitNormalCD, |
| 285 | int subDivide) { |
| 286 | SkVector ab = pts[1] - pts[0]; |
| 287 | SkVector cd = pts[3] - pts[2]; |
| 288 | SkVector normalBC, unitNormalBC; |
| 289 | |
| 290 | bool degenerateAB = degenerate_vector(ab); |
| 291 | bool degenerateCD = degenerate_vector(cd); |
| 292 | |
| 293 | if (degenerateAB && degenerateCD) { |
| 294 | DRAW_LINE: |
| 295 | this->line_to(pts[3], normalAB); |
| 296 | *normalCD = normalAB; |
| 297 | *unitNormalCD = unitNormalAB; |
| 298 | return; |
| 299 | } |
| 300 | |
| 301 | if (degenerateAB) { |
| 302 | ab = pts[2] - pts[0]; |
| 303 | degenerateAB = degenerate_vector(ab); |
| 304 | } |
| 305 | if (degenerateCD) { |
| 306 | cd = pts[3] - pts[1]; |
| 307 | degenerateCD = degenerate_vector(cd); |
| 308 | } |
| 309 | if (degenerateAB || degenerateCD) { |
| 310 | goto DRAW_LINE; |
| 311 | } |
| 312 | SkAssertResult(set_normal_unitnormal(cd, fRadius, normalCD, unitNormalCD)); |
| 313 | bool degenerateBC = !set_normal_unitnormal(pts[1], pts[2], fRadius, |
| 314 | &normalBC, &unitNormalBC); |
reed@google.com | 5687a3e | 2013-03-12 12:57:04 +0000 | [diff] [blame] | 315 | #ifndef SK_IGNORE_CUBIC_STROKE_FIX |
reed@google.com | 7a90daf | 2013-04-10 18:44:00 +0000 | [diff] [blame] | 316 | if (--subDivide < 0) { |
| 317 | goto DRAW_LINE; |
reed@google.com | 5687a3e | 2013-03-12 12:57:04 +0000 | [diff] [blame] | 318 | } |
| 319 | #endif |
reed@android.com | 0ea42c1 | 2009-06-17 19:21:01 +0000 | [diff] [blame] | 320 | if (degenerateBC || normals_too_curvy(unitNormalAB, unitNormalBC) || |
| 321 | normals_too_curvy(unitNormalBC, *unitNormalCD)) { |
reed@google.com | 5687a3e | 2013-03-12 12:57:04 +0000 | [diff] [blame] | 322 | #ifdef SK_IGNORE_CUBIC_STROKE_FIX |
reed@android.com | 0ea42c1 | 2009-06-17 19:21:01 +0000 | [diff] [blame] | 323 | // subdivide if we can |
| 324 | if (--subDivide < 0) { |
| 325 | goto DRAW_LINE; |
| 326 | } |
reed@google.com | 5687a3e | 2013-03-12 12:57:04 +0000 | [diff] [blame] | 327 | #endif |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 328 | SkPoint tmp[7]; |
| 329 | SkVector norm, unit, dummy, unitDummy; |
| 330 | |
| 331 | SkChopCubicAtHalf(pts, tmp); |
| 332 | this->cubic_to(&tmp[0], normalAB, unitNormalAB, &norm, &unit, |
| 333 | subDivide); |
| 334 | // we use dummys since we already have a valid (and more accurate) |
| 335 | // normals for CD |
| 336 | this->cubic_to(&tmp[3], norm, unit, &dummy, &unitDummy, subDivide); |
| 337 | } else { |
| 338 | SkVector normalB, normalC; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 339 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 340 | // need normals to inset/outset the off-curve pts B and C |
| 341 | |
reed@google.com | bdd82f4 | 2013-03-08 16:47:39 +0000 | [diff] [blame] | 342 | SkVector unitBC = pts[2] - pts[1]; |
| 343 | unitBC.normalize(); |
| 344 | unitBC.rotateCCW(); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 345 | |
reed@google.com | bdd82f4 | 2013-03-08 16:47:39 +0000 | [diff] [blame] | 346 | normalB = unitNormalAB + unitBC; |
| 347 | normalC = *unitNormalCD + unitBC; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 348 | |
reed@google.com | bdd82f4 | 2013-03-08 16:47:39 +0000 | [diff] [blame] | 349 | SkScalar dot = SkPoint::DotProduct(unitNormalAB, unitBC); |
| 350 | SkAssertResult(normalB.setLength(SkScalarDiv(fRadius, |
| 351 | SkScalarSqrt((SK_Scalar1 + dot)/2)))); |
| 352 | dot = SkPoint::DotProduct(*unitNormalCD, unitBC); |
| 353 | SkAssertResult(normalC.setLength(SkScalarDiv(fRadius, |
| 354 | SkScalarSqrt((SK_Scalar1 + dot)/2)))); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 355 | |
| 356 | fOuter.cubicTo( pts[1].fX + normalB.fX, pts[1].fY + normalB.fY, |
| 357 | pts[2].fX + normalC.fX, pts[2].fY + normalC.fY, |
| 358 | pts[3].fX + normalCD->fX, pts[3].fY + normalCD->fY); |
| 359 | |
| 360 | fInner.cubicTo( pts[1].fX - normalB.fX, pts[1].fY - normalB.fY, |
| 361 | pts[2].fX - normalC.fX, pts[2].fY - normalC.fY, |
| 362 | pts[3].fX - normalCD->fX, pts[3].fY - normalCD->fY); |
| 363 | } |
| 364 | } |
| 365 | |
| 366 | void SkPathStroker::quadTo(const SkPoint& pt1, const SkPoint& pt2) { |
schenney@chromium.org | 4da06ab | 2011-12-20 15:14:18 +0000 | [diff] [blame] | 367 | bool degenerateAB = SkPath::IsLineDegenerate(fPrevPt, pt1); |
| 368 | bool degenerateBC = SkPath::IsLineDegenerate(pt1, pt2); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 369 | |
| 370 | if (degenerateAB | degenerateBC) { |
| 371 | if (degenerateAB ^ degenerateBC) { |
| 372 | this->lineTo(pt2); |
| 373 | } |
| 374 | return; |
| 375 | } |
| 376 | |
| 377 | SkVector normalAB, unitAB, normalBC, unitBC; |
| 378 | |
| 379 | this->preJoinTo(pt1, &normalAB, &unitAB, false); |
| 380 | |
| 381 | { |
| 382 | SkPoint pts[3], tmp[5]; |
| 383 | pts[0] = fPrevPt; |
| 384 | pts[1] = pt1; |
| 385 | pts[2] = pt2; |
| 386 | |
| 387 | if (SkChopQuadAtMaxCurvature(pts, tmp) == 2) { |
| 388 | unitBC.setNormalize(pts[2].fX - pts[1].fX, pts[2].fY - pts[1].fY); |
| 389 | unitBC.rotateCCW(); |
| 390 | if (normals_too_pinchy(unitAB, unitBC)) { |
| 391 | normalBC = unitBC; |
| 392 | normalBC.scale(fRadius); |
| 393 | |
| 394 | fOuter.lineTo(tmp[2].fX + normalAB.fX, tmp[2].fY + normalAB.fY); |
| 395 | fOuter.lineTo(tmp[2].fX + normalBC.fX, tmp[2].fY + normalBC.fY); |
| 396 | fOuter.lineTo(tmp[4].fX + normalBC.fX, tmp[4].fY + normalBC.fY); |
| 397 | |
| 398 | fInner.lineTo(tmp[2].fX - normalAB.fX, tmp[2].fY - normalAB.fY); |
| 399 | fInner.lineTo(tmp[2].fX - normalBC.fX, tmp[2].fY - normalBC.fY); |
| 400 | fInner.lineTo(tmp[4].fX - normalBC.fX, tmp[4].fY - normalBC.fY); |
| 401 | |
| 402 | fExtra.addCircle(tmp[2].fX, tmp[2].fY, fRadius, |
| 403 | SkPath::kCW_Direction); |
| 404 | } else { |
| 405 | this->quad_to(&tmp[0], normalAB, unitAB, &normalBC, &unitBC, |
| 406 | kMaxQuadSubdivide); |
| 407 | SkVector n = normalBC; |
| 408 | SkVector u = unitBC; |
| 409 | this->quad_to(&tmp[2], n, u, &normalBC, &unitBC, |
| 410 | kMaxQuadSubdivide); |
| 411 | } |
| 412 | } else { |
| 413 | this->quad_to(pts, normalAB, unitAB, &normalBC, &unitBC, |
| 414 | kMaxQuadSubdivide); |
| 415 | } |
| 416 | } |
| 417 | |
| 418 | this->postJoinTo(pt2, normalBC, unitBC); |
| 419 | } |
| 420 | |
| 421 | void SkPathStroker::cubicTo(const SkPoint& pt1, const SkPoint& pt2, |
| 422 | const SkPoint& pt3) { |
schenney@chromium.org | 4da06ab | 2011-12-20 15:14:18 +0000 | [diff] [blame] | 423 | bool degenerateAB = SkPath::IsLineDegenerate(fPrevPt, pt1); |
| 424 | bool degenerateBC = SkPath::IsLineDegenerate(pt1, pt2); |
| 425 | bool degenerateCD = SkPath::IsLineDegenerate(pt2, pt3); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 426 | |
| 427 | if (degenerateAB + degenerateBC + degenerateCD >= 2) { |
| 428 | this->lineTo(pt3); |
| 429 | return; |
| 430 | } |
| 431 | |
| 432 | SkVector normalAB, unitAB, normalCD, unitCD; |
| 433 | |
| 434 | // find the first tangent (which might be pt1 or pt2 |
| 435 | { |
| 436 | const SkPoint* nextPt = &pt1; |
| 437 | if (degenerateAB) |
| 438 | nextPt = &pt2; |
| 439 | this->preJoinTo(*nextPt, &normalAB, &unitAB, false); |
| 440 | } |
| 441 | |
| 442 | { |
| 443 | SkPoint pts[4], tmp[13]; |
| 444 | int i, count; |
| 445 | SkVector n, u; |
| 446 | SkScalar tValues[3]; |
| 447 | |
| 448 | pts[0] = fPrevPt; |
| 449 | pts[1] = pt1; |
| 450 | pts[2] = pt2; |
| 451 | pts[3] = pt3; |
| 452 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 453 | count = SkChopCubicAtMaxCurvature(pts, tmp, tValues); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 454 | n = normalAB; |
| 455 | u = unitAB; |
| 456 | for (i = 0; i < count; i++) { |
| 457 | this->cubic_to(&tmp[i * 3], n, u, &normalCD, &unitCD, |
| 458 | kMaxCubicSubdivide); |
| 459 | if (i == count - 1) { |
| 460 | break; |
| 461 | } |
| 462 | n = normalCD; |
| 463 | u = unitCD; |
| 464 | |
| 465 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 466 | } |
| 467 | |
| 468 | this->postJoinTo(pt3, normalCD, unitCD); |
| 469 | } |
| 470 | |
| 471 | /////////////////////////////////////////////////////////////////////////////// |
| 472 | /////////////////////////////////////////////////////////////////////////////// |
| 473 | |
reed@google.com | aefdd06 | 2012-02-29 13:03:00 +0000 | [diff] [blame] | 474 | #include "SkPaintDefaults.h" |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 475 | |
| 476 | SkStroke::SkStroke() { |
reed@google.com | aefdd06 | 2012-02-29 13:03:00 +0000 | [diff] [blame] | 477 | fWidth = SK_Scalar1; |
| 478 | fMiterLimit = SkPaintDefaults_MiterLimit; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 479 | fCap = SkPaint::kDefault_Cap; |
| 480 | fJoin = SkPaint::kDefault_Join; |
| 481 | fDoFill = false; |
| 482 | } |
| 483 | |
| 484 | SkStroke::SkStroke(const SkPaint& p) { |
| 485 | fWidth = p.getStrokeWidth(); |
| 486 | fMiterLimit = p.getStrokeMiter(); |
| 487 | fCap = (uint8_t)p.getStrokeCap(); |
| 488 | fJoin = (uint8_t)p.getStrokeJoin(); |
| 489 | fDoFill = SkToU8(p.getStyle() == SkPaint::kStrokeAndFill_Style); |
| 490 | } |
| 491 | |
| 492 | SkStroke::SkStroke(const SkPaint& p, SkScalar width) { |
| 493 | fWidth = width; |
| 494 | fMiterLimit = p.getStrokeMiter(); |
| 495 | fCap = (uint8_t)p.getStrokeCap(); |
| 496 | fJoin = (uint8_t)p.getStrokeJoin(); |
| 497 | fDoFill = SkToU8(p.getStyle() == SkPaint::kStrokeAndFill_Style); |
| 498 | } |
| 499 | |
| 500 | void SkStroke::setWidth(SkScalar width) { |
| 501 | SkASSERT(width >= 0); |
| 502 | fWidth = width; |
| 503 | } |
| 504 | |
| 505 | void SkStroke::setMiterLimit(SkScalar miterLimit) { |
| 506 | SkASSERT(miterLimit >= 0); |
| 507 | fMiterLimit = miterLimit; |
| 508 | } |
| 509 | |
| 510 | void SkStroke::setCap(SkPaint::Cap cap) { |
| 511 | SkASSERT((unsigned)cap < SkPaint::kCapCount); |
| 512 | fCap = SkToU8(cap); |
| 513 | } |
| 514 | |
| 515 | void SkStroke::setJoin(SkPaint::Join join) { |
| 516 | SkASSERT((unsigned)join < SkPaint::kJoinCount); |
| 517 | fJoin = SkToU8(join); |
| 518 | } |
| 519 | |
| 520 | /////////////////////////////////////////////////////////////////////////////// |
| 521 | |
reed@google.com | fd4be26 | 2012-05-25 01:04:12 +0000 | [diff] [blame] | 522 | // If src==dst, then we use a tmp path to record the stroke, and then swap |
| 523 | // its contents with src when we're done. |
| 524 | class AutoTmpPath { |
| 525 | public: |
| 526 | AutoTmpPath(const SkPath& src, SkPath** dst) : fSrc(src) { |
| 527 | if (&src == *dst) { |
| 528 | *dst = &fTmpDst; |
| 529 | fSwapWithSrc = true; |
| 530 | } else { |
| 531 | (*dst)->reset(); |
| 532 | fSwapWithSrc = false; |
| 533 | } |
| 534 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 535 | |
reed@google.com | fd4be26 | 2012-05-25 01:04:12 +0000 | [diff] [blame] | 536 | ~AutoTmpPath() { |
| 537 | if (fSwapWithSrc) { |
| 538 | fTmpDst.swap(*const_cast<SkPath*>(&fSrc)); |
| 539 | } |
| 540 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 541 | |
reed@google.com | fd4be26 | 2012-05-25 01:04:12 +0000 | [diff] [blame] | 542 | private: |
| 543 | SkPath fTmpDst; |
| 544 | const SkPath& fSrc; |
| 545 | bool fSwapWithSrc; |
| 546 | }; |
| 547 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 548 | void SkStroke::strokePath(const SkPath& src, SkPath* dst) const { |
| 549 | SkASSERT(&src != NULL && dst != NULL); |
| 550 | |
| 551 | SkScalar radius = SkScalarHalf(fWidth); |
| 552 | |
reed@google.com | fd4be26 | 2012-05-25 01:04:12 +0000 | [diff] [blame] | 553 | AutoTmpPath tmp(src, &dst); |
| 554 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 555 | if (radius <= 0) { |
| 556 | return; |
| 557 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 558 | |
reed@google.com | 603dbed | 2012-11-20 19:00:28 +0000 | [diff] [blame] | 559 | // If src is really a rect, call our specialty strokeRect() method |
| 560 | { |
reed@google.com | 04fdaa1 | 2012-11-21 15:48:20 +0000 | [diff] [blame] | 561 | bool isClosed; |
| 562 | SkPath::Direction dir; |
robertphillips@google.com | 8fd1603 | 2013-06-25 15:39:58 +0000 | [diff] [blame] | 563 | if (src.isRect(&isClosed, &dir) && isClosed) { |
| 564 | this->strokeRect(src.getBounds(), dst, dir); |
commit-bot@chromium.org | 6803c21 | 2014-05-04 18:08:27 +0000 | [diff] [blame] | 565 | // our answer should preserve the inverseness of the src |
| 566 | if (src.isInverseFillType()) { |
reed@google.com | b9971cb | 2012-11-20 21:33:05 +0000 | [diff] [blame] | 567 | SkASSERT(!dst->isInverseFillType()); |
| 568 | dst->toggleInverseFillType(); |
| 569 | } |
reed@google.com | 603dbed | 2012-11-20 19:00:28 +0000 | [diff] [blame] | 570 | return; |
| 571 | } |
| 572 | } |
| 573 | |
reed@google.com | 7de1e3f | 2013-06-12 17:46:41 +0000 | [diff] [blame] | 574 | SkAutoConicToQuads converter; |
| 575 | const SkScalar conicTol = SK_Scalar1 / 4; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 576 | |
reed@google.com | 2e0d727 | 2012-05-15 13:33:57 +0000 | [diff] [blame] | 577 | SkPathStroker stroker(src, radius, fMiterLimit, this->getCap(), |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 578 | this->getJoin()); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 579 | SkPath::Iter iter(src, false); |
reed@google.com | 7de1e3f | 2013-06-12 17:46:41 +0000 | [diff] [blame] | 580 | SkPath::Verb lastSegment = SkPath::kMove_Verb; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 581 | |
reed@google.com | 7de1e3f | 2013-06-12 17:46:41 +0000 | [diff] [blame] | 582 | for (;;) { |
| 583 | SkPoint pts[4]; |
| 584 | switch (iter.next(pts, false)) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 585 | case SkPath::kMove_Verb: |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 586 | stroker.moveTo(pts[0]); |
| 587 | break; |
| 588 | case SkPath::kLine_Verb: |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 589 | stroker.lineTo(pts[1]); |
reed@google.com | 7de1e3f | 2013-06-12 17:46:41 +0000 | [diff] [blame] | 590 | lastSegment = SkPath::kLine_Verb; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 591 | break; |
| 592 | case SkPath::kQuad_Verb: |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 593 | stroker.quadTo(pts[1], pts[2]); |
reed@google.com | 7de1e3f | 2013-06-12 17:46:41 +0000 | [diff] [blame] | 594 | lastSegment = SkPath::kQuad_Verb; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 595 | break; |
reed@google.com | 7de1e3f | 2013-06-12 17:46:41 +0000 | [diff] [blame] | 596 | case SkPath::kConic_Verb: { |
| 597 | // todo: if we had maxcurvature for conics, perhaps we should |
| 598 | // natively extrude the conic instead of converting to quads. |
| 599 | const SkPoint* quadPts = |
| 600 | converter.computeQuads(pts, iter.conicWeight(), conicTol); |
| 601 | for (int i = 0; i < converter.countQuads(); ++i) { |
| 602 | stroker.quadTo(quadPts[1], quadPts[2]); |
| 603 | quadPts += 2; |
| 604 | } |
| 605 | lastSegment = SkPath::kQuad_Verb; |
| 606 | } break; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 607 | case SkPath::kCubic_Verb: |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 608 | stroker.cubicTo(pts[1], pts[2], pts[3]); |
reed@google.com | 7de1e3f | 2013-06-12 17:46:41 +0000 | [diff] [blame] | 609 | lastSegment = SkPath::kCubic_Verb; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 610 | break; |
| 611 | case SkPath::kClose_Verb: |
| 612 | stroker.close(lastSegment == SkPath::kLine_Verb); |
| 613 | break; |
reed@google.com | 7de1e3f | 2013-06-12 17:46:41 +0000 | [diff] [blame] | 614 | case SkPath::kDone_Verb: |
| 615 | goto DONE; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 616 | } |
| 617 | } |
reed@google.com | 7de1e3f | 2013-06-12 17:46:41 +0000 | [diff] [blame] | 618 | DONE: |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 619 | stroker.done(dst, lastSegment == SkPath::kLine_Verb); |
| 620 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 621 | if (fDoFill) { |
reed@google.com | 1ae2090 | 2012-01-10 21:30:57 +0000 | [diff] [blame] | 622 | if (src.cheapIsDirection(SkPath::kCCW_Direction)) { |
reed@google.com | 69a9943 | 2012-01-10 18:00:10 +0000 | [diff] [blame] | 623 | dst->reverseAddPath(src); |
| 624 | } else { |
| 625 | dst->addPath(src); |
reed@google.com | 63d7374 | 2012-01-10 15:33:12 +0000 | [diff] [blame] | 626 | } |
reed@android.com | f2b98d6 | 2010-12-20 18:26:13 +0000 | [diff] [blame] | 627 | } else { |
reed@google.com | effe847 | 2011-10-31 12:55:49 +0000 | [diff] [blame] | 628 | // Seems like we can assume that a 2-point src would always result in |
| 629 | // a convex stroke, but testing has proved otherwise. |
| 630 | // TODO: fix the stroker to make this assumption true (without making |
| 631 | // it slower that the work that will be done in computeConvexity()) |
| 632 | #if 0 |
| 633 | // this test results in a non-convex stroke :( |
| 634 | static void test(SkCanvas* canvas) { |
| 635 | SkPoint pts[] = { 146.333328, 192.333328, 300.333344, 293.333344 }; |
| 636 | SkPaint paint; |
| 637 | paint.setStrokeWidth(7); |
| 638 | paint.setStrokeCap(SkPaint::kRound_Cap); |
| 639 | canvas->drawLine(pts[0].fX, pts[0].fY, pts[1].fX, pts[1].fY, paint); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 640 | } |
reed@google.com | 4d03c11 | 2011-10-31 12:12:12 +0000 | [diff] [blame] | 641 | #endif |
reed@google.com | effe847 | 2011-10-31 12:55:49 +0000 | [diff] [blame] | 642 | #if 0 |
| 643 | if (2 == src.countPoints()) { |
reed@android.com | f2b98d6 | 2010-12-20 18:26:13 +0000 | [diff] [blame] | 644 | dst->setIsConvex(true); |
| 645 | } |
reed@google.com | effe847 | 2011-10-31 12:55:49 +0000 | [diff] [blame] | 646 | #endif |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 647 | } |
reed@google.com | bb47232 | 2011-12-21 15:53:13 +0000 | [diff] [blame] | 648 | |
commit-bot@chromium.org | 6803c21 | 2014-05-04 18:08:27 +0000 | [diff] [blame] | 649 | // our answer should preserve the inverseness of the src |
| 650 | if (src.isInverseFillType()) { |
reed@google.com | bb47232 | 2011-12-21 15:53:13 +0000 | [diff] [blame] | 651 | SkASSERT(!dst->isInverseFillType()); |
| 652 | dst->toggleInverseFillType(); |
| 653 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 654 | } |
| 655 | |
reed@google.com | 603dbed | 2012-11-20 19:00:28 +0000 | [diff] [blame] | 656 | static SkPath::Direction reverse_direction(SkPath::Direction dir) { |
| 657 | SkASSERT(SkPath::kUnknown_Direction != dir); |
| 658 | return SkPath::kCW_Direction == dir ? SkPath::kCCW_Direction : SkPath::kCW_Direction; |
| 659 | } |
| 660 | |
| 661 | static void addBevel(SkPath* path, const SkRect& r, const SkRect& outer, SkPath::Direction dir) { |
| 662 | SkPoint pts[8]; |
| 663 | |
| 664 | if (SkPath::kCW_Direction == dir) { |
| 665 | pts[0].set(r.fLeft, outer.fTop); |
| 666 | pts[1].set(r.fRight, outer.fTop); |
| 667 | pts[2].set(outer.fRight, r.fTop); |
| 668 | pts[3].set(outer.fRight, r.fBottom); |
| 669 | pts[4].set(r.fRight, outer.fBottom); |
| 670 | pts[5].set(r.fLeft, outer.fBottom); |
| 671 | pts[6].set(outer.fLeft, r.fBottom); |
| 672 | pts[7].set(outer.fLeft, r.fTop); |
| 673 | } else { |
| 674 | pts[7].set(r.fLeft, outer.fTop); |
| 675 | pts[6].set(r.fRight, outer.fTop); |
| 676 | pts[5].set(outer.fRight, r.fTop); |
| 677 | pts[4].set(outer.fRight, r.fBottom); |
| 678 | pts[3].set(r.fRight, outer.fBottom); |
| 679 | pts[2].set(r.fLeft, outer.fBottom); |
| 680 | pts[1].set(outer.fLeft, r.fBottom); |
| 681 | pts[0].set(outer.fLeft, r.fTop); |
| 682 | } |
| 683 | path->addPoly(pts, 8, true); |
| 684 | } |
| 685 | |
reed@google.com | 04fdaa1 | 2012-11-21 15:48:20 +0000 | [diff] [blame] | 686 | void SkStroke::strokeRect(const SkRect& origRect, SkPath* dst, |
| 687 | SkPath::Direction dir) const { |
reed@google.com | 603dbed | 2012-11-20 19:00:28 +0000 | [diff] [blame] | 688 | SkASSERT(dst != NULL); |
| 689 | dst->reset(); |
| 690 | |
| 691 | SkScalar radius = SkScalarHalf(fWidth); |
| 692 | if (radius <= 0) { |
| 693 | return; |
| 694 | } |
| 695 | |
reed@google.com | 603dbed | 2012-11-20 19:00:28 +0000 | [diff] [blame] | 696 | SkScalar rw = origRect.width(); |
| 697 | SkScalar rh = origRect.height(); |
| 698 | if ((rw < 0) ^ (rh < 0)) { |
reed@google.com | 04fdaa1 | 2012-11-21 15:48:20 +0000 | [diff] [blame] | 699 | dir = reverse_direction(dir); |
reed@google.com | 603dbed | 2012-11-20 19:00:28 +0000 | [diff] [blame] | 700 | } |
| 701 | SkRect rect(origRect); |
| 702 | rect.sort(); |
| 703 | // reassign these, now that we know they'll be >= 0 |
| 704 | rw = rect.width(); |
| 705 | rh = rect.height(); |
| 706 | |
| 707 | SkRect r(rect); |
| 708 | r.outset(radius, radius); |
| 709 | |
| 710 | SkPaint::Join join = (SkPaint::Join)fJoin; |
| 711 | if (SkPaint::kMiter_Join == join && fMiterLimit < SK_ScalarSqrt2) { |
| 712 | join = SkPaint::kBevel_Join; |
| 713 | } |
| 714 | |
reed@google.com | b2e138c | 2012-11-21 16:36:34 +0000 | [diff] [blame] | 715 | switch (join) { |
reed@google.com | 603dbed | 2012-11-20 19:00:28 +0000 | [diff] [blame] | 716 | case SkPaint::kMiter_Join: |
| 717 | dst->addRect(r, dir); |
| 718 | break; |
| 719 | case SkPaint::kBevel_Join: |
| 720 | addBevel(dst, rect, r, dir); |
| 721 | break; |
| 722 | case SkPaint::kRound_Join: |
reed@google.com | 04fdaa1 | 2012-11-21 15:48:20 +0000 | [diff] [blame] | 723 | dst->addRoundRect(r, radius, radius, dir); |
reed@google.com | 603dbed | 2012-11-20 19:00:28 +0000 | [diff] [blame] | 724 | break; |
reed@google.com | c19468e | 2012-11-21 18:34:15 +0000 | [diff] [blame] | 725 | default: |
| 726 | break; |
reed@google.com | 603dbed | 2012-11-20 19:00:28 +0000 | [diff] [blame] | 727 | } |
| 728 | |
reed@google.com | b9971cb | 2012-11-20 21:33:05 +0000 | [diff] [blame] | 729 | if (fWidth < SkMinScalar(rw, rh) && !fDoFill) { |
reed@google.com | 603dbed | 2012-11-20 19:00:28 +0000 | [diff] [blame] | 730 | r = rect; |
| 731 | r.inset(radius, radius); |
| 732 | dst->addRect(r, reverse_direction(dir)); |
| 733 | } |
| 734 | } |