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#include "include/private/SkIDChangeListener.h"
13
14static_assert(0 == static_cast<int>(SkPathFillType::kWinding), "fill_type_mismatch");
15static_assert(1 == static_cast<int>(SkPathFillType::kEvenOdd), "fill_type_mismatch");
16static_assert(2 == static_cast<int>(SkPathFillType::kInverseWinding), "fill_type_mismatch");
17static_assert(3 == static_cast<int>(SkPathFillType::kInverseEvenOdd), "fill_type_mismatch");
18
19class SkPathPriv {
20public:
21#ifdef SK_BUILD_FOR_ANDROID_FRAMEWORK
22 static const int kPathRefGenIDBitCnt = 30; // leave room for the fill type (skbug.com/1762)
23#else
24 static const int kPathRefGenIDBitCnt = 32;
25#endif
26
27 static constexpr SkScalar kW0PlaneDistance = 0.05f;
28
29 enum FirstDirection : int {
30 kCW_FirstDirection, // == SkPathDirection::kCW
31 kCCW_FirstDirection, // == SkPathDirection::kCCW
32 kUnknown_FirstDirection,
33 };
34
35 static FirstDirection AsFirstDirection(SkPathDirection dir) {
36 // since we agree numerically for the values in Direction, we can just cast.
37 return (FirstDirection)dir;
38 }
39
40 /**
41 * Return the opposite of the specified direction. kUnknown is its own
42 * opposite.
43 */
44 static FirstDirection OppositeFirstDirection(FirstDirection dir) {
45 static const FirstDirection gOppositeDir[] = {
46 kCCW_FirstDirection, kCW_FirstDirection, kUnknown_FirstDirection,
47 };
48 return gOppositeDir[dir];
49 }
50
51 /**
52 * Tries to quickly compute the direction of the first non-degenerate
53 * contour. If it can be computed, return true and set dir to that
54 * direction. If it cannot be (quickly) determined, return false and ignore
55 * the dir parameter. If the direction was determined, it is cached to make
56 * subsequent calls return quickly.
57 */
58 static bool CheapComputeFirstDirection(const SkPath&, FirstDirection* dir);
59
60 /**
61 * Returns true if the path's direction can be computed via
62 * cheapComputDirection() and if that computed direction matches the
63 * specified direction. If dir is kUnknown, returns true if the direction
64 * cannot be computed.
65 */
66 static bool CheapIsFirstDirection(const SkPath& path, FirstDirection dir) {
67 FirstDirection computedDir = kUnknown_FirstDirection;
68 (void)CheapComputeFirstDirection(path, &computedDir);
69 return computedDir == dir;
70 }
71
72 static bool IsClosedSingleContour(const SkPath& path) {
73 int verbCount = path.countVerbs();
74 if (verbCount == 0)
75 return false;
76 int moveCount = 0;
77 auto verbs = path.fPathRef->verbsBegin();
78 for (int i = 0; i < verbCount; i++) {
79 switch (verbs[i]) {
80 case SkPath::Verb::kMove_Verb:
81 moveCount += 1;
82 if (moveCount > 1) {
83 return false;
84 }
85 break;
86 case SkPath::Verb::kClose_Verb:
87 if (i == verbCount - 1) {
88 return true;
89 }
90 return false;
91 default: break;
92 }
93 }
94 return false;
95 }
96
97 static void AddGenIDChangeListener(const SkPath& path, sk_sp<SkIDChangeListener> 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:
131 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 };
138 Iter begin() { return Iter{fPathRef->verbsBegin()}; }
139 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 */
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 */
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 */
159 static int ConicWeightCnt(const SkPath& path) {
160 return path.fPathRef->countWeights();
161 }
162
163 /** Returns a raw pointer to the path conic weights. */
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. */
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 */
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 */
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 */
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 }
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
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
275 static bool IsAxisAligned(const SkPath& path) {
276 SkRect tmp;
277 return (path.fPathRef->fIsRRect | path.fPathRef->fIsOval) || path.isRect(&tmp);
278 }
279
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
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 */
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 * Gets the number of GenIDChangeListeners. If another thread has access to this path then
334 * this may be stale before return and only indicates that the count was the return value
335 * at some point during the execution of the function.
336 */
337 static int GenIDChangeListenersCount(const SkPath&);
338};
339
340// Lightweight variant of SkPath::Iter that only returns segments (e.g. lines/conics).
341// Does not return kMove or kClose.
342// Always "auto-closes" each contour.
343// Roughly the same as SkPath::Iter(path, true), but does not return moves or closes
344//
345class SkPathEdgeIter {
346 const uint8_t* fVerbs;
347 const uint8_t* fVerbsStop;
348 const SkPoint* fPts;
349 const SkPoint* fMoveToPtr;
350 const SkScalar* fConicWeights;
351 SkPoint fScratch[2]; // for auto-close lines
352 bool fNeedsCloseLine;
353 bool fNextIsNewContour;
354 SkDEBUGCODE(bool fIsConic);
355
356 enum {
357 kIllegalEdgeValue = 99
358 };
359
360public:
361 SkPathEdgeIter(const SkPath& path);
362
363 SkScalar conicWeight() const {
364 SkASSERT(fIsConic);
365 return *fConicWeights;
366 }
367
368 enum class Edge {
369 kLine = SkPath::kLine_Verb,
370 kQuad = SkPath::kQuad_Verb,
371 kConic = SkPath::kConic_Verb,
372 kCubic = SkPath::kCubic_Verb,
373 };
374
375 static SkPath::Verb EdgeToVerb(Edge e) {
376 return SkPath::Verb(e);
377 }
378
379 struct Result {
380 const SkPoint* fPts; // points for the segment, or null if done
381 Edge fEdge;
382 bool fIsNewContour;
383
384 // Returns true when it holds an Edge, false when the path is done.
385 operator bool() { return fPts != nullptr; }
386 };
387
388 Result next() {
389 auto closeline = [&]() {
390 fScratch[0] = fPts[-1];
391 fScratch[1] = *fMoveToPtr;
392 fNeedsCloseLine = false;
393 fNextIsNewContour = true;
394 return Result{ fScratch, Edge::kLine, false };
395 };
396
397 for (;;) {
398 SkASSERT(fVerbs <= fVerbsStop);
399 if (fVerbs == fVerbsStop) {
400 return fNeedsCloseLine
401 ? closeline()
402 : Result{ nullptr, Edge(kIllegalEdgeValue), false };
403 }
404
405 SkDEBUGCODE(fIsConic = false;)
406
407 const auto v = *fVerbs++;
408 switch (v) {
409 case SkPath::kMove_Verb: {
410 if (fNeedsCloseLine) {
411 auto res = closeline();
412 fMoveToPtr = fPts++;
413 return res;
414 }
415 fMoveToPtr = fPts++;
416 } break;
417 case SkPath::kClose_Verb:
418 if (fNeedsCloseLine) return closeline();
419 break;
420 default: {
421 // Actual edge.
422 const int pts_count = (v+2) / 2,
423 cws_count = (v & (v-1)) / 2;
424 SkASSERT(pts_count == SkPathPriv::PtsInIter(v) - 1);
425
426 fNeedsCloseLine = true;
427 fPts += pts_count;
428 fConicWeights += cws_count;
429
430 SkDEBUGCODE(fIsConic = (v == SkPath::kConic_Verb);)
431 SkASSERT(fIsConic == (cws_count > 0));
432
433 bool isNewContour = fNextIsNewContour;
434 fNextIsNewContour = false;
435 return { &fPts[-(pts_count + 1)], Edge(v), isNewContour };
436 }
437 }
438 }
439 }
440};
441
442// Parses out each contour in a path. Example usage:
443//
444// SkTPathContourParser parser;
445// while (parser.parseNextContour()) {
446// for (int i = 0; i < parser.countVerbs(); ++i) {
447// switch (parser.atVerb(i)) {
448// ...
449// }
450// }
451// }
452//
453// TSubclass must inherit from "SkTPathContourParser<TSubclass>", and must contain two methods:
454//
455// // Called on each implicit or explicit moveTo.
456// void resetGeometry(const SkPoint& startPoint);
457//
458// // Called on each lineTo, quadTo, conicTo, and cubicTo.
459// void geometryTo(SkPathVerb, const SkPoint& endpoint);
460//
461// If no special tracking of endpoints is required, then use SkPathContourParser below.
462template<typename TSubclass> class SkTPathContourParser {
463public:
464 SkTPathContourParser(const SkPath& path)
465 : fPath(path)
466 , fVerbs(SkPathPriv::VerbData(fPath))
467 , fNumRemainingVerbs(fPath.countVerbs())
468 , fPoints(SkPathPriv::PointData(fPath)) {}
469
470 // Returns the number of verbs in the current contour, plus 1 so we can inject kDone at the end.
471 int countVerbs() const { return fVerbsIdx + 1; }
472
473 // Returns the ith non-move verb in the current contour.
474 SkPathVerb atVerb(int i) const {
475 SkASSERT(i >= 0 && i <= fVerbsIdx);
476 SkPathVerb verb = (i < fVerbsIdx) ? (SkPathVerb)fVerbs[i] : SkPathVerb::kDone;
477 SkASSERT(SkPathVerb::kMove != verb);
478 return verb;
479 }
480
481 // Returns the current contour's starting point.
482 SkPoint startPoint() const { return fStartPoint; }
483
484 // Returns the ith point in the current contour, not including the start point. (i.e., index 0
485 // is the first point immediately following the start point from the path's point array.)
486 const SkPoint& atPoint(int i) const {
487 SkASSERT(i >= 0 && i < fPtsIdx);
488 return fPoints[i];
489 }
490
491 // Advances the internal state to the next contour in the path. Returns false if there are no
492 // more contours.
493 //
494 // SkTPathContourParser parser;
495 // while (parser.parseNextContour()) {
496 // ...
497 // }
498 bool parseNextContour() {
499 this->advance();
500 fStartPoint = {0, 0};
501 static_cast<TSubclass*>(this)->resetGeometry(fStartPoint);
502
503 bool hasGeometry = false;
504
505 while (fVerbsIdx < fNumRemainingVerbs) {
506 switch (uint8_t verb = fVerbs[fVerbsIdx]) {
507 case SkPath::kMove_Verb:
508 if (!hasGeometry) {
509 fStartPoint = fPoints[fPtsIdx];
510 static_cast<TSubclass*>(this)->resetGeometry(fStartPoint);
511 ++fVerbsIdx;
512 ++fPtsIdx;
513 this->advance();
514 continue;
515 }
516 return true;
517
518 static_assert(SkPath::kLine_Verb == 1); case 1:
519 static_assert(SkPath::kQuad_Verb == 2); case 2:
520 static_assert(SkPath::kConic_Verb == 3); case 3:
521 static_assert(SkPath::kCubic_Verb == 4); case 4:
522 static constexpr int kPtsAdvance[] = {0, 1, 2, 2, 3};
523 fPtsIdx += kPtsAdvance[verb];
524 static_cast<TSubclass*>(this)->geometryTo((SkPathVerb)verb,
525 fPoints[fPtsIdx - 1]);
526 hasGeometry = true;
527 break;
528 }
529 ++fVerbsIdx;
530 }
531
532 return hasGeometry;
533 }
534
535private:
536 void advance() {
537 fVerbs += fVerbsIdx;
538 fNumRemainingVerbs -= fVerbsIdx;
539 fVerbsIdx = 0;
540 fPoints += fPtsIdx;
541 fPtsIdx = 0;
542 }
543
544 const SkPath& fPath;
545
546 const uint8_t* fVerbs;
547 int fNumRemainingVerbs = 0;
548 int fVerbsIdx = 0;
549
550 const SkPoint* fPoints;
551 SkPoint fStartPoint;
552 int fPtsIdx = 0;
553};
554
555class SkPathContourParser : public SkTPathContourParser<SkPathContourParser> {
556public:
557 SkPathContourParser(const SkPath& path) : SkTPathContourParser(path) {}
558 // Called on each implicit or explicit moveTo.
559 void resetGeometry(const SkPoint& startPoint) { /* No-op */ }
560 // Called on each lineTo, quadTo, conicTo, and cubicTo.
561 void geometryTo(SkPathVerb, const SkPoint& endpoint) { /* No-op */ }
562};
563
564#endif
565