1 /* 2 * Copyright 2020 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #ifndef skgpu_tessellate_StrokeIterator_DEFINED 9 #define skgpu_tessellate_StrokeIterator_DEFINED 10 11 #include "include/core/SkMatrix.h" 12 #include "include/core/SkPaint.h" 13 #include "include/core/SkPathTypes.h" 14 #include "include/core/SkPoint.h" 15 #include "include/core/SkStrokeRec.h" 16 #include "include/private/base/SkAssert.h" 17 #include "src/core/SkPathPriv.h" 18 19 #include <array> 20 21 class SkPath; 22 23 namespace skgpu::tess { 24 25 // This class iterates over the stroke geometry defined by a path and stroke. It automatically 26 // converts closes and square caps to lines, and round caps to circles so the user doesn't have to 27 // worry about it. At each location it provides a verb and "prevVerb" so there is context about the 28 // preceding join. Usage: 29 // 30 // StrokeIterator iter(path, stroke); 31 // while (iter.next()) { // Call next() first. 32 // iter.verb(); 33 // iter.pts(); 34 // iter.w(); 35 // iter.prevVerb(); 36 // iter.prevPts(); 37 // } 38 // 39 class StrokeIterator { 40 public: StrokeIterator(const SkPath & path,const SkStrokeRec * stroke,const SkMatrix * viewMatrix)41 StrokeIterator(const SkPath& path, const SkStrokeRec* stroke, const SkMatrix* viewMatrix) 42 : fViewMatrix(viewMatrix), fStroke(stroke) { 43 SkPathPriv::Iterate it(path); 44 fIter = it.begin(); 45 fEnd = it.end(); 46 } 47 48 enum class Verb { 49 // Verbs that describe stroke geometry. 50 kLine = (int)SkPathVerb::kLine, 51 kQuad = (int)SkPathVerb::kQuad, 52 kConic = (int)SkPathVerb::kConic, 53 kCubic = (int)SkPathVerb::kCubic, 54 kCircle, // A stroke-width circle drawn as a 180-degree point stroke. 55 56 // Helper verbs that notify callers to update their own iteration state. 57 kMoveWithinContour, 58 kContourFinished 59 }; IsVerbGeometric(Verb verb)60 constexpr static bool IsVerbGeometric(Verb verb) { return verb < Verb::kMoveWithinContour; } 61 62 // Must be called first. Loads the next pair of "prev" and "current" stroke. Returns false if 63 // iteration is complete. next()64 bool next() { 65 if (fQueueCount) { 66 SkASSERT(fQueueCount >= 2); 67 this->popFront(); 68 if (fQueueCount >= 2) { 69 return true; 70 } 71 SkASSERT(fQueueCount == 1); 72 if (this->atVerb(0) == Verb::kContourFinished) { 73 // Don't let "kContourFinished" be prevVerb at the start of the next contour. 74 fQueueCount = 0; 75 } 76 } 77 for (; fIter != fEnd; ++fIter) { 78 SkASSERT(fQueueCount == 0 || fQueueCount == 1); 79 auto [verb, pts, w] = *fIter; 80 switch (verb) { 81 case SkPathVerb::kMove: 82 if (!this->finishOpenContour()) { 83 continue; 84 } 85 break; 86 case SkPathVerb::kCubic: 87 if (pts[3] == pts[2]) { 88 [[fallthrough]]; // i.e., "if (p3 == p2 && p2 == p1 && p1 == p0)" 89 case SkPathVerb::kConic: 90 case SkPathVerb::kQuad: 91 if (pts[2] == pts[1]) { 92 [[fallthrough]]; // i.e., "if (p2 == p1 && p1 == p0)" 93 case SkPathVerb::kLine: 94 if (pts[1] == pts[0]) { 95 fLastDegenerateStrokePt = pts; 96 continue; 97 }}} 98 this->enqueue((Verb)verb, pts, w); 99 if (fQueueCount == 1) { 100 // Defer the first verb until the end when we know what it's joined to. 101 fFirstVerbInContour = (Verb)verb; 102 fFirstPtsInContour = pts; 103 fFirstWInContour = w; 104 continue; 105 } 106 break; 107 case SkPathVerb::kClose: 108 if (!fQueueCount) { 109 fLastDegenerateStrokePt = pts; 110 continue; 111 } 112 if (pts[0] != fFirstPtsInContour[0]) { 113 // Draw a line back to the contour's starting point. 114 fClosePts = {pts[0], fFirstPtsInContour[0]}; 115 this->enqueue(Verb::kLine, fClosePts.data(), nullptr); 116 } 117 // Repeat the first verb, this time as the "current" stroke instead of the prev. 118 this->enqueue(fFirstVerbInContour, fFirstPtsInContour, fFirstWInContour); 119 this->enqueue(Verb::kContourFinished, nullptr, nullptr); 120 fLastDegenerateStrokePt = nullptr; 121 break; 122 } 123 SkASSERT(fQueueCount >= 2); 124 ++fIter; 125 return true; 126 } 127 return this->finishOpenContour(); 128 } 129 prevVerb()130 Verb prevVerb() const { return this->atVerb(0); } prevPts()131 const SkPoint* prevPts() const { return this->atPts(0); } 132 verb()133 Verb verb() const { return this->atVerb(1); } pts()134 const SkPoint* pts() const { return this->atPts(1); } w()135 float w() const { return this->atW(1); } 136 firstVerbInContour()137 Verb firstVerbInContour() const { SkASSERT(fQueueCount > 0); return fFirstVerbInContour; } firstPtsInContour()138 const SkPoint* firstPtsInContour() const { 139 SkASSERT(fQueueCount > 0); 140 return fFirstPtsInContour; 141 } 142 143 private: 144 constexpr static int kQueueBufferCount = 8; atVerb(int i)145 Verb atVerb(int i) const { 146 SkASSERT(0 <= i && i < fQueueCount); 147 return fVerbs[(fQueueFrontIdx + i) & (kQueueBufferCount - 1)]; 148 } backVerb()149 Verb backVerb() const { 150 return this->atVerb(fQueueCount - 1); 151 } atPts(int i)152 const SkPoint* atPts(int i) const { 153 SkASSERT(0 <= i && i < fQueueCount); 154 return fPts[(fQueueFrontIdx + i) & (kQueueBufferCount - 1)]; 155 } backPts()156 const SkPoint* backPts() const { 157 return this->atPts(fQueueCount - 1); 158 } atW(int i)159 float atW(int i) const { 160 SkASSERT(0 <= i && i < fQueueCount); 161 const float* w = fW[(fQueueFrontIdx + i) & (kQueueBufferCount - 1)]; 162 SkASSERT(w); 163 return *w; 164 } enqueue(Verb verb,const SkPoint * pts,const float * w)165 void enqueue(Verb verb, const SkPoint* pts, const float* w) { 166 SkASSERT(fQueueCount < kQueueBufferCount); 167 int i = (fQueueFrontIdx + fQueueCount) & (kQueueBufferCount - 1); 168 fVerbs[i] = verb; 169 fPts[i] = pts; 170 fW[i] = w; 171 ++fQueueCount; 172 } popFront()173 void popFront() { 174 SkASSERT(fQueueCount > 0); 175 ++fQueueFrontIdx; 176 --fQueueCount; 177 } 178 179 // Finishes the current contour without closing it. Enqueues any necessary caps as well as the 180 // contour's first stroke that we deferred at the beginning. 181 // Returns false and makes no changes if the current contour was already finished. finishOpenContour()182 bool finishOpenContour() { 183 if (fQueueCount) { 184 SkASSERT(this->backVerb() == Verb::kLine || this->backVerb() == Verb::kQuad || 185 this->backVerb() == Verb::kConic || this->backVerb() == Verb::kCubic); 186 switch (fStroke->getCap()) { 187 case SkPaint::kButt_Cap: 188 // There are no caps, but inject a "move" so the first stroke doesn't get joined 189 // with the end of the contour when it's processed. 190 this->enqueue(Verb::kMoveWithinContour, fFirstPtsInContour, fFirstWInContour); 191 break; 192 case SkPaint::kRound_Cap: { 193 // The "kCircle" verb serves as our barrier to prevent the first stroke from 194 // getting joined with the end of the contour. We just need to make sure that 195 // the first point of the contour goes last. 196 int backIdx = SkPathPriv::PtsInIter((unsigned)this->backVerb()) - 1; 197 this->enqueue(Verb::kCircle, this->backPts() + backIdx, nullptr); 198 this->enqueue(Verb::kCircle, fFirstPtsInContour, fFirstWInContour); 199 break; 200 } 201 case SkPaint::kSquare_Cap: 202 this->fillSquareCapPoints(); // Fills in fEndingCapPts and fBeginningCapPts. 203 // Append the ending cap onto the current contour. 204 this->enqueue(Verb::kLine, fEndingCapPts.data(), nullptr); 205 // Move to the beginning cap and append it right before (and joined to) the 206 // first stroke (that we will add below). 207 this->enqueue(Verb::kMoveWithinContour, fBeginningCapPts.data(), nullptr); 208 this->enqueue(Verb::kLine, fBeginningCapPts.data(), nullptr); 209 break; 210 } 211 } else if (fLastDegenerateStrokePt) { 212 // fQueueCount=0 means this subpath is zero length. Generates caps on its location. 213 // 214 // "Any zero length subpath ... shall be stroked if the 'stroke-linecap' property has 215 // a value of round or square producing respectively a circle or a square." 216 // 217 // (https://www.w3.org/TR/SVG11/painting.html#StrokeProperties) 218 // 219 switch (fStroke->getCap()) { 220 case SkPaint::kButt_Cap: 221 // Zero-length contour with butt caps. There are no caps and no first stroke to 222 // generate. 223 return false; 224 case SkPaint::kRound_Cap: 225 this->enqueue(Verb::kCircle, fLastDegenerateStrokePt, nullptr); 226 // Setting the "first" stroke as the circle causes it to be added again below, 227 // this time as the "current" stroke. 228 fFirstVerbInContour = Verb::kCircle; 229 fFirstPtsInContour = fLastDegenerateStrokePt; 230 fFirstWInContour = nullptr; 231 break; 232 case SkPaint::kSquare_Cap: { 233 SkPoint outset; 234 if (!fStroke->isHairlineStyle()) { 235 // Implement degenerate square caps as a stroke-width square in path space. 236 outset = {fStroke->getWidth() * .5f, 0}; 237 } else { 238 // If the stroke is hairline, draw a 1x1 device-space square instead. This 239 // is equivalent to using: 240 // 241 // outset = inverse(fViewMatrix).mapVector(.5, 0) 242 // 243 // And since the matrix cannot have perspective, we only need to invert the 244 // upper 2x2 of the viewMatrix to achieve this. 245 SkASSERT(!fViewMatrix->hasPerspective()); 246 float a=fViewMatrix->getScaleX(), b=fViewMatrix->getSkewX(), 247 c=fViewMatrix->getSkewY(), d=fViewMatrix->getScaleY(); 248 float det = a*d - b*c; 249 if (det > 0) { 250 // outset = inverse(|a b|) * |.5| 251 // |c d| | 0| 252 // 253 // == 1/det * | d -b| * |.5| 254 // |-c a| | 0| 255 // 256 // == | d| * .5/det 257 // |-c| 258 outset = SkVector{d, -c} * (.5f / det); 259 } else { 260 outset = {1, 0}; 261 } 262 } 263 fEndingCapPts = {*fLastDegenerateStrokePt - outset, 264 *fLastDegenerateStrokePt + outset}; 265 // Add the square first as the "prev" join. 266 this->enqueue(Verb::kLine, fEndingCapPts.data(), nullptr); 267 this->enqueue(Verb::kMoveWithinContour, fEndingCapPts.data(), nullptr); 268 // Setting the "first" stroke as the square causes it to be added again below, 269 // this time as the "current" stroke. 270 fFirstVerbInContour = Verb::kLine; 271 fFirstPtsInContour = fEndingCapPts.data(); 272 fFirstWInContour = nullptr; 273 break; 274 } 275 } 276 } else { 277 // This contour had no lines, beziers, or "close" verbs. There are no caps and no first 278 // stroke to generate. 279 return false; 280 } 281 282 // Repeat the first verb, this time as the "current" stroke instead of the prev. 283 this->enqueue(fFirstVerbInContour, fFirstPtsInContour, fFirstWInContour); 284 this->enqueue(Verb::kContourFinished, nullptr, nullptr); 285 fLastDegenerateStrokePt = nullptr; 286 return true; 287 } 288 289 // We implement square caps as two extra "kLine" verbs. This method finds the endpoints for 290 // those lines. fillSquareCapPoints()291 void fillSquareCapPoints() { 292 // Find the endpoints of the cap at the end of the contour. 293 SkVector lastTangent; 294 const SkPoint* lastPts = this->backPts(); 295 Verb lastVerb = this->backVerb(); 296 switch (lastVerb) { 297 case Verb::kCubic: 298 lastTangent = lastPts[3] - lastPts[2]; 299 if (!lastTangent.isZero()) { 300 break; 301 } 302 [[fallthrough]]; 303 case Verb::kConic: 304 case Verb::kQuad: 305 lastTangent = lastPts[2] - lastPts[1]; 306 if (!lastTangent.isZero()) { 307 break; 308 } 309 [[fallthrough]]; 310 case Verb::kLine: 311 lastTangent = lastPts[1] - lastPts[0]; 312 SkASSERT(!lastTangent.isZero()); 313 break; 314 default: 315 SkUNREACHABLE; 316 } 317 if (!fStroke->isHairlineStyle()) { 318 // Extend the cap by 1/2 stroke width. 319 lastTangent *= (.5f * fStroke->getWidth()) / lastTangent.length(); 320 } else { 321 // Extend the cap by what will be 1/2 pixel after transformation. 322 lastTangent *= .5f / fViewMatrix->mapVector(lastTangent.fX, lastTangent.fY).length(); 323 } 324 SkPoint lastPoint = lastPts[SkPathPriv::PtsInIter((unsigned)lastVerb) - 1]; 325 fEndingCapPts = {lastPoint, lastPoint + lastTangent}; 326 327 // Find the endpoints of the cap at the beginning of the contour. 328 SkVector firstTangent = fFirstPtsInContour[1] - fFirstPtsInContour[0]; 329 if (firstTangent.isZero()) { 330 SkASSERT(fFirstVerbInContour == Verb::kQuad || fFirstVerbInContour == Verb::kConic || 331 fFirstVerbInContour == Verb::kCubic); 332 firstTangent = fFirstPtsInContour[2] - fFirstPtsInContour[0]; 333 if (firstTangent.isZero()) { 334 SkASSERT(fFirstVerbInContour == Verb::kCubic); 335 firstTangent = fFirstPtsInContour[3] - fFirstPtsInContour[0]; 336 SkASSERT(!firstTangent.isZero()); 337 } 338 } 339 if (!fStroke->isHairlineStyle()) { 340 // Set the the cap back by 1/2 stroke width. 341 firstTangent *= (-.5f * fStroke->getWidth()) / firstTangent.length(); 342 } else { 343 // Set the cap back by what will be 1/2 pixel after transformation. 344 firstTangent *= 345 -.5f / fViewMatrix->mapVector(firstTangent.fX, firstTangent.fY).length(); 346 } 347 fBeginningCapPts = {fFirstPtsInContour[0] + firstTangent, fFirstPtsInContour[0]}; 348 } 349 350 // Info and iterators from the original path. 351 const SkMatrix* const fViewMatrix; // For hairlines. 352 const SkStrokeRec* const fStroke; 353 SkPathPriv::RangeIter fIter; 354 SkPathPriv::RangeIter fEnd; 355 356 // Info for the current contour we are iterating. 357 Verb fFirstVerbInContour; 358 const SkPoint* fFirstPtsInContour; 359 const float* fFirstWInContour; 360 const SkPoint* fLastDegenerateStrokePt = nullptr; 361 362 // The queue is implemented as a roll-over array with a floating front index. 363 Verb fVerbs[kQueueBufferCount]; 364 const SkPoint* fPts[kQueueBufferCount]; 365 const float* fW[kQueueBufferCount]; 366 int fQueueFrontIdx = 0; 367 int fQueueCount = 0; 368 369 // Storage space for geometry that gets defined implicitly by the path, but does not have 370 // actual points in memory to reference. 371 std::array<SkPoint, 2> fClosePts; 372 std::array<SkPoint, 2> fEndingCapPts; 373 std::array<SkPoint, 2> fBeginningCapPts; 374 }; 375 376 } // namespace skgpu::tess 377 378 #endif // skgpu_tessellate_StrokeIterator_DEFINED 379