• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright 2015 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 SkPathPriv_DEFINED
9 #define SkPathPriv_DEFINED
10 
11 #include "include/core/SkPath.h"
12 
13 static_assert(0 == static_cast<int>(SkPathFillType::kWinding), "fill_type_mismatch");
14 static_assert(1 == static_cast<int>(SkPathFillType::kEvenOdd), "fill_type_mismatch");
15 static_assert(2 == static_cast<int>(SkPathFillType::kInverseWinding), "fill_type_mismatch");
16 static_assert(3 == static_cast<int>(SkPathFillType::kInverseEvenOdd), "fill_type_mismatch");
17 
18 class SkPathPriv {
19 public:
20 #ifdef SK_BUILD_FOR_ANDROID_FRAMEWORK
21     static const int kPathRefGenIDBitCnt = 30; // leave room for the fill type (skbug.com/1762)
22 #else
23     static const int kPathRefGenIDBitCnt = 32;
24 #endif
25 
26     static constexpr SkScalar kW0PlaneDistance = 0.05f;
27 
28     enum FirstDirection : int {
29         kCW_FirstDirection,         // == SkPathDirection::kCW
30         kCCW_FirstDirection,        // == SkPathDirection::kCCW
31         kUnknown_FirstDirection,
32     };
33 
AsFirstDirection(SkPathDirection dir)34     static FirstDirection AsFirstDirection(SkPathDirection dir) {
35         // since we agree numerically for the values in Direction, we can just cast.
36         return (FirstDirection)dir;
37     }
38 
39     /**
40      *  Return the opposite of the specified direction. kUnknown is its own
41      *  opposite.
42      */
OppositeFirstDirection(FirstDirection dir)43     static FirstDirection OppositeFirstDirection(FirstDirection dir) {
44         static const FirstDirection gOppositeDir[] = {
45             kCCW_FirstDirection, kCW_FirstDirection, kUnknown_FirstDirection,
46         };
47         return gOppositeDir[dir];
48     }
49 
50     /**
51      *  Tries to quickly compute the direction of the first non-degenerate
52      *  contour. If it can be computed, return true and set dir to that
53      *  direction. If it cannot be (quickly) determined, return false and ignore
54      *  the dir parameter. If the direction was determined, it is cached to make
55      *  subsequent calls return quickly.
56      */
57     static bool CheapComputeFirstDirection(const SkPath&, FirstDirection* dir);
58 
59     /**
60      *  Returns true if the path's direction can be computed via
61      *  cheapComputDirection() and if that computed direction matches the
62      *  specified direction. If dir is kUnknown, returns true if the direction
63      *  cannot be computed.
64      */
CheapIsFirstDirection(const SkPath & path,FirstDirection dir)65     static bool CheapIsFirstDirection(const SkPath& path, FirstDirection dir) {
66         FirstDirection computedDir = kUnknown_FirstDirection;
67         (void)CheapComputeFirstDirection(path, &computedDir);
68         return computedDir == dir;
69     }
70 
IsClosedSingleContour(const SkPath & path)71     static bool IsClosedSingleContour(const SkPath& path) {
72         int verbCount = path.countVerbs();
73         if (verbCount == 0)
74             return false;
75         int moveCount = 0;
76         auto verbs = path.fPathRef->verbsBegin();
77         for (int i = 0; i < verbCount; i++) {
78             switch (verbs[i]) {
79                 case SkPath::Verb::kMove_Verb:
80                     moveCount += 1;
81                     if (moveCount > 1) {
82                         return false;
83                     }
84                     break;
85                 case SkPath::Verb::kClose_Verb:
86                     if (i == verbCount - 1) {
87                         return true;
88                     }
89                     return false;
90                 default: break;
91             }
92         }
93         return false;
94     }
95 
AddGenIDChangeListener(const SkPath & path,sk_sp<SkPathRef::GenIDChangeListener> listener)96     static void AddGenIDChangeListener(const SkPath& path,
97                                        sk_sp<SkPathRef::GenIDChangeListener> listener) {
98         path.fPathRef->addGenIDChangeListener(std::move(listener));
99     }
100 
101     /**
102      * This returns true for a rect that begins and ends at the same corner and has either a move
103      * followed by four lines or a move followed by 3 lines and a close. None of the parameters are
104      * optional. This does not permit degenerate line or point rectangles.
105      */
106     static bool IsSimpleClosedRect(const SkPath& path, SkRect* rect, SkPathDirection* direction,
107                                    unsigned* start);
108 
109     /**
110      * Creates a path from arc params using the semantics of SkCanvas::drawArc. This function
111      * assumes empty ovals and zero sweeps have already been filtered out.
112      */
113     static void CreateDrawArcPath(SkPath* path, const SkRect& oval, SkScalar startAngle,
114                                   SkScalar sweepAngle, bool useCenter, bool isFillNoPathEffect);
115 
116     /**
117      * Determines whether an arc produced by CreateDrawArcPath will be convex. Assumes a non-empty
118      * oval.
119      */
120     static bool DrawArcIsConvex(SkScalar sweepAngle, bool useCenter, bool isFillNoPathEffect);
121 
122     /**
123      * Returns a C++11-iterable object that traverses a path's verbs in order. e.g:
124      *
125      *   for (SkPath::Verb verb : SkPathPriv::Verbs(path)) {
126      *       ...
127      *   }
128      */
129     struct Verbs {
130     public:
VerbsVerbs131         Verbs(const SkPath& path) : fPathRef(path.fPathRef.get()) {}
132         struct Iter {
133             void operator++() { fVerb++; }
134             bool operator!=(const Iter& b) { return fVerb != b.fVerb; }
135             SkPath::Verb operator*() { return static_cast<SkPath::Verb>(*fVerb); }
136             const uint8_t* fVerb;
137         };
beginVerbs138         Iter begin() { return Iter{fPathRef->verbsBegin()}; }
endVerbs139         Iter end() { return Iter{fPathRef->verbsEnd()}; }
140     private:
141         Verbs(const Verbs&) = delete;
142         Verbs& operator=(const Verbs&) = delete;
143         SkPathRef* fPathRef;
144     };
145 
146     /**
147      * Returns a pointer to the verb data.
148      */
VerbData(const SkPath & path)149     static const uint8_t* VerbData(const SkPath& path) {
150         return path.fPathRef->verbsBegin();
151     }
152 
153     /** Returns a raw pointer to the path points */
PointData(const SkPath & path)154     static const SkPoint* PointData(const SkPath& path) {
155         return path.fPathRef->points();
156     }
157 
158     /** Returns the number of conic weights in the path */
ConicWeightCnt(const SkPath & path)159     static int ConicWeightCnt(const SkPath& path) {
160         return path.fPathRef->countWeights();
161     }
162 
163     /** Returns a raw pointer to the path conic weights. */
ConicWeightData(const SkPath & path)164     static const SkScalar* ConicWeightData(const SkPath& path) {
165         return path.fPathRef->conicWeights();
166     }
167 
168     /** Returns true if path formed by pts is convex.
169 
170         @param pts    SkPoint array of path
171         @param count  number of entries in array
172 
173         @return       true if pts represent a convex geometry
174     */
175     static bool IsConvex(const SkPoint pts[], int count);
176 
177     /** Returns true if the underlying SkPathRef has one single owner. */
TestingOnly_unique(const SkPath & path)178     static bool TestingOnly_unique(const SkPath& path) {
179         return path.fPathRef->unique();
180     }
181 
182     /** Returns true if constructed by addCircle(), addOval(); and in some cases,
183      addRoundRect(), addRRect(). SkPath constructed with conicTo() or rConicTo() will not
184      return true though SkPath draws oval.
185 
186      rect receives bounds of oval.
187      dir receives SkPathDirection of oval: kCW_Direction if clockwise, kCCW_Direction if
188      counterclockwise.
189      start receives start of oval: 0 for top, 1 for right, 2 for bottom, 3 for left.
190 
191      rect, dir, and start are unmodified if oval is not found.
192 
193      Triggers performance optimizations on some GPU surface implementations.
194 
195      @param rect   storage for bounding SkRect of oval; may be nullptr
196      @param dir    storage for SkPathDirection; may be nullptr
197      @param start  storage for start of oval; may be nullptr
198      @return       true if SkPath was constructed by method that reduces to oval
199      */
IsOval(const SkPath & path,SkRect * rect,SkPathDirection * dir,unsigned * start)200     static bool IsOval(const SkPath& path, SkRect* rect, SkPathDirection* dir, unsigned* start) {
201         bool isCCW = false;
202         bool result = path.fPathRef->isOval(rect, &isCCW, start);
203         if (dir && result) {
204             *dir = isCCW ? SkPathDirection::kCCW : SkPathDirection::kCW;
205         }
206         return result;
207     }
208 
209     /** Returns true if constructed by addRoundRect(), addRRect(); and if construction
210      is not empty, not SkRect, and not oval. SkPath constructed with other calls
211      will not return true though SkPath draws SkRRect.
212 
213      rrect receives bounds of SkRRect.
214      dir receives SkPathDirection of oval: kCW_Direction if clockwise, kCCW_Direction if
215      counterclockwise.
216      start receives start of SkRRect: 0 for top, 1 for right, 2 for bottom, 3 for left.
217 
218      rrect, dir, and start are unmodified if SkRRect is not found.
219 
220      Triggers performance optimizations on some GPU surface implementations.
221 
222      @param rrect  storage for bounding SkRect of SkRRect; may be nullptr
223      @param dir    storage for SkPathDirection; may be nullptr
224      @param start  storage for start of SkRRect; may be nullptr
225      @return       true if SkPath contains only SkRRect
226      */
IsRRect(const SkPath & path,SkRRect * rrect,SkPathDirection * dir,unsigned * start)227     static bool IsRRect(const SkPath& path, SkRRect* rrect, SkPathDirection* dir,
228                         unsigned* start) {
229         bool isCCW = false;
230         bool result = path.fPathRef->isRRect(rrect, &isCCW, start);
231         if (dir && result) {
232             *dir = isCCW ? SkPathDirection::kCCW : SkPathDirection::kCW;
233         }
234         return result;
235     }
236 
237     /**
238      *  Sometimes in the drawing pipeline, we have to perform math on path coordinates, even after
239      *  the path is in device-coordinates. Tessellation and clipping are two examples. Usually this
240      *  is pretty modest, but it can involve subtracting/adding coordinates, or multiplying by
241      *  small constants (e.g. 2,3,4). To try to preflight issues where these optionations could turn
242      *  finite path values into infinities (or NaNs), we allow the upper drawing code to reject
243      *  the path if its bounds (in device coordinates) is too close to max float.
244      */
TooBigForMath(const SkRect & bounds)245     static bool TooBigForMath(const SkRect& bounds) {
246         // This value is just a guess. smaller is safer, but we don't want to reject largish paths
247         // that we don't have to.
248         constexpr SkScalar scale_down_to_allow_for_small_multiplies = 0.25f;
249         constexpr SkScalar max = SK_ScalarMax * scale_down_to_allow_for_small_multiplies;
250 
251         // use ! expression so we return true if bounds contains NaN
252         return !(bounds.fLeft >= -max && bounds.fTop >= -max &&
253                  bounds.fRight <= max && bounds.fBottom <= max);
254     }
TooBigForMath(const SkPath & path)255     static bool TooBigForMath(const SkPath& path) {
256         return TooBigForMath(path.getBounds());
257     }
258 
259     // Returns number of valid points for each SkPath::Iter verb
PtsInIter(unsigned verb)260     static int PtsInIter(unsigned verb) {
261         static const uint8_t gPtsInVerb[] = {
262             1,  // kMove    pts[0]
263             2,  // kLine    pts[0..1]
264             3,  // kQuad    pts[0..2]
265             3,  // kConic   pts[0..2]
266             4,  // kCubic   pts[0..3]
267             0,  // kClose
268             0   // kDone
269         };
270 
271         SkASSERT(verb < SK_ARRAY_COUNT(gPtsInVerb));
272         return gPtsInVerb[verb];
273     }
274 
IsAxisAligned(const SkPath & path)275     static bool IsAxisAligned(const SkPath& path) {
276         SkRect tmp;
277         return (path.fPathRef->fIsRRect | path.fPathRef->fIsOval) || path.isRect(&tmp);
278     }
279 
AllPointsEq(const SkPoint pts[],int count)280     static bool AllPointsEq(const SkPoint pts[], int count) {
281         for (int i = 1; i < count; ++i) {
282             if (pts[0] != pts[i]) {
283                 return false;
284             }
285         }
286         return true;
287     }
288 
289     static bool IsRectContour(const SkPath&, bool allowPartial, int* currVerb,
290                               const SkPoint** ptsPtr, bool* isClosed, SkPathDirection* direction,
291                               SkRect* rect);
292 
293     /** Returns true if SkPath is equivalent to nested SkRect pair when filled.
294      If false, rect and dirs are unchanged.
295      If true, rect and dirs are written to if not nullptr:
296      setting rect[0] to outer SkRect, and rect[1] to inner SkRect;
297      setting dirs[0] to SkPathDirection of outer SkRect, and dirs[1] to SkPathDirection of
298      inner SkRect.
299 
300      @param rect  storage for SkRect pair; may be nullptr
301      @param dirs  storage for SkPathDirection pair; may be nullptr
302      @return      true if SkPath contains nested SkRect pair
303      */
304     static bool IsNestedFillRects(const SkPath&, SkRect rect[2],
305                                   SkPathDirection dirs[2] = nullptr);
306 
IsInverseFillType(SkPathFillType fill)307     static bool IsInverseFillType(SkPathFillType fill) {
308         return (static_cast<int>(fill) & 2) != 0;
309     }
310 
311     /** Returns equivalent SkPath::FillType representing SkPath fill inside its bounds.
312      .
313 
314      @param fill  one of: kWinding_FillType, kEvenOdd_FillType,
315      kInverseWinding_FillType, kInverseEvenOdd_FillType
316      @return      fill, or kWinding_FillType or kEvenOdd_FillType if fill is inverted
317      */
ConvertToNonInverseFillType(SkPathFillType fill)318     static SkPathFillType ConvertToNonInverseFillType(SkPathFillType fill) {
319         return (SkPathFillType)(static_cast<int>(fill) & 1);
320     }
321 
322     /**
323      *  If needed (to not blow-up under a perspective matrix), clip the path, returning the
324      *  answer in "result", and return true.
325      *
326      *  Note result might be empty (if the path was completely clipped out).
327      *
328      *  If no clipping is needed, returns false and "result" is left unchanged.
329      */
330     static bool PerspectiveClip(const SkPath& src, const SkMatrix&, SkPath* result);
331 };
332 
333 // Lightweight variant of SkPath::Iter that only returns segments (e.g. lines/conics).
334 // Does not return kMove or kClose.
335 // Always "auto-closes" each contour.
336 // Roughly the same as SkPath::Iter(path, true), but does not return moves or closes
337 //
338 class SkPathEdgeIter {
339     const uint8_t*  fVerbs;
340     const uint8_t*  fVerbsStop;
341     const SkPoint*  fPts;
342     const SkPoint*  fMoveToPtr;
343     const SkScalar* fConicWeights;
344     SkPoint         fScratch[2];    // for auto-close lines
345     bool            fNeedsCloseLine;
346     bool            fNextIsNewContour;
347     SkDEBUGCODE(bool fIsConic);
348 
349     enum {
350         kIllegalEdgeValue = 99
351     };
352 
353 public:
354     SkPathEdgeIter(const SkPath& path);
355 
conicWeight()356     SkScalar conicWeight() const {
357         SkASSERT(fIsConic);
358         return *fConicWeights;
359     }
360 
361     enum class Edge {
362         kLine  = SkPath::kLine_Verb,
363         kQuad  = SkPath::kQuad_Verb,
364         kConic = SkPath::kConic_Verb,
365         kCubic = SkPath::kCubic_Verb,
366     };
367 
EdgeToVerb(Edge e)368     static SkPath::Verb EdgeToVerb(Edge e) {
369         return SkPath::Verb(e);
370     }
371 
372     struct Result {
373         const SkPoint*  fPts;   // points for the segment, or null if done
374         Edge            fEdge;
375         bool            fIsNewContour;
376 
377         // Returns true when it holds an Edge, false when the path is done.
378         operator bool() { return fPts != nullptr; }
379     };
380 
next()381     Result next() {
382         auto closeline = [&]() {
383             fScratch[0] = fPts[-1];
384             fScratch[1] = *fMoveToPtr;
385             fNeedsCloseLine = false;
386             fNextIsNewContour = true;
387             return Result{ fScratch, Edge::kLine, false };
388         };
389 
390         for (;;) {
391             SkASSERT(fVerbs <= fVerbsStop);
392             if (fVerbs == fVerbsStop) {
393                 return fNeedsCloseLine
394                     ? closeline()
395                     : Result{ nullptr, Edge(kIllegalEdgeValue), false };
396             }
397 
398             SkDEBUGCODE(fIsConic = false;)
399 
400             const auto v = *fVerbs++;
401             switch (v) {
402                 case SkPath::kMove_Verb: {
403                     if (fNeedsCloseLine) {
404                         auto res = closeline();
405                         fMoveToPtr = fPts++;
406                         return res;
407                     }
408                     fMoveToPtr = fPts++;
409                 } break;
410                 case SkPath::kClose_Verb:
411                     if (fNeedsCloseLine) return closeline();
412                     break;
413                 default: {
414                     // Actual edge.
415                     const int pts_count = (v+2) / 2,
416                               cws_count = (v & (v-1)) / 2;
417                     SkASSERT(pts_count == SkPathPriv::PtsInIter(v) - 1);
418 
419                     fNeedsCloseLine = true;
420                     fPts           += pts_count;
421                     fConicWeights  += cws_count;
422 
423                     SkDEBUGCODE(fIsConic = (v == SkPath::kConic_Verb);)
424                     SkASSERT(fIsConic == (cws_count > 0));
425 
426                     bool isNewContour = fNextIsNewContour;
427                     fNextIsNewContour = false;
428                     return { &fPts[-(pts_count + 1)], Edge(v), isNewContour };
429                 }
430             }
431         }
432     }
433 };
434 
435 // Parses out each contour in a path. Example usage:
436 //
437 //   SkTPathContourParser parser;
438 //   while (parser.parseNextContour()) {
439 //       for (int i = 0; i < parser.countVerbs(); ++i) {
440 //           switch (parser.atVerb(i)) {
441 //               ...
442 //           }
443 //       }
444 //   }
445 //
446 // TSubclass must inherit from "SkTPathContourParser<TSubclass>", and must contain two methods:
447 //
448 //      // Called on each implicit or explicit moveTo.
449 //      void resetGeometry(const SkPoint& startPoint);
450 //
451 //      // Called on each lineTo, quadTo, conicTo, and cubicTo.
452 //      void geometryTo(SkPathVerb, const SkPoint& endpoint);
453 //
454 // If no special tracking of endpoints is required, then use SkPathContourParser below.
455 template<typename TSubclass> class SkTPathContourParser {
456 public:
SkTPathContourParser(const SkPath & path)457     SkTPathContourParser(const SkPath& path)
458             : fPath(path)
459             , fVerbs(SkPathPriv::VerbData(fPath))
460             , fNumRemainingVerbs(fPath.countVerbs())
461             , fPoints(SkPathPriv::PointData(fPath)) {}
462 
463     // Returns the number of verbs in the current contour, plus 1 so we can inject kDone at the end.
countVerbs()464     int countVerbs() const { return fVerbsIdx + 1; }
465 
466     // Returns the ith non-move verb in the current contour.
atVerb(int i)467     SkPathVerb atVerb(int i) const {
468         SkASSERT(i >= 0 && i <= fVerbsIdx);
469         SkPathVerb verb = (i < fVerbsIdx) ? (SkPathVerb)fVerbs[i] : SkPathVerb::kDone;
470         SkASSERT(SkPathVerb::kMove != verb);
471         return verb;
472     }
473 
474     // Returns the current contour's starting point.
startPoint()475     SkPoint startPoint() const { return fStartPoint; }
476 
477     // Returns the ith point in the current contour, not including the start point. (i.e., index 0
478     // is the first point immediately following the start point from the path's point array.)
atPoint(int i)479     const SkPoint& atPoint(int i) const {
480         SkASSERT(i >= 0 && i < fPtsIdx);
481         return fPoints[i];
482     }
483 
484     // Advances the internal state to the next contour in the path. Returns false if there are no
485     // more contours.
486     //
487     //   SkTPathContourParser parser;
488     //   while (parser.parseNextContour()) {
489     //       ...
490     //   }
parseNextContour()491     bool parseNextContour() {
492         this->advance();
493         fStartPoint = {0, 0};
494         static_cast<TSubclass*>(this)->resetGeometry(fStartPoint);
495 
496         bool hasGeometry = false;
497 
498         while (fVerbsIdx < fNumRemainingVerbs) {
499             switch (uint8_t verb = fVerbs[fVerbsIdx]) {
500                 case SkPath::kMove_Verb:
501                     if (!hasGeometry) {
502                         fStartPoint = fPoints[fPtsIdx];
503                         static_cast<TSubclass*>(this)->resetGeometry(fStartPoint);
504                         ++fVerbsIdx;
505                         ++fPtsIdx;
506                         this->advance();
507                         continue;
508                     }
509                     return true;
510 
511                 static_assert(SkPath::kLine_Verb  == 1); case 1:
512                 static_assert(SkPath::kQuad_Verb  == 2); case 2:
513                 static_assert(SkPath::kConic_Verb == 3); case 3:
514                 static_assert(SkPath::kCubic_Verb == 4); case 4:
515                     static constexpr int kPtsAdvance[] = {0, 1, 2, 2, 3};
516                     fPtsIdx += kPtsAdvance[verb];
517                     static_cast<TSubclass*>(this)->geometryTo((SkPathVerb)verb,
518                                                               fPoints[fPtsIdx - 1]);
519                     hasGeometry = true;
520                     break;
521             }
522             ++fVerbsIdx;
523         }
524 
525         return hasGeometry;
526     }
527 
528 private:
advance()529     void advance() {
530         fVerbs += fVerbsIdx;
531         fNumRemainingVerbs -= fVerbsIdx;
532         fVerbsIdx = 0;
533         fPoints += fPtsIdx;
534         fPtsIdx = 0;
535     }
536 
537     const SkPath& fPath;
538 
539     const uint8_t* fVerbs;
540     int fNumRemainingVerbs = 0;
541     int fVerbsIdx = 0;
542 
543     const SkPoint* fPoints;
544     SkPoint fStartPoint;
545     int fPtsIdx = 0;
546 };
547 
548 class SkPathContourParser : public SkTPathContourParser<SkPathContourParser> {
549 public:
SkPathContourParser(const SkPath & path)550     SkPathContourParser(const SkPath& path) : SkTPathContourParser(path) {}
551     // Called on each implicit or explicit moveTo.
resetGeometry(const SkPoint & startPoint)552     void resetGeometry(const SkPoint& startPoint) { /* No-op */ }
553     // Called on each lineTo, quadTo, conicTo, and cubicTo.
geometryTo(SkPathVerb,const SkPoint & endpoint)554     void geometryTo(SkPathVerb, const SkPoint& endpoint) { /* No-op */ }
555 };
556 
557 #endif
558