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