1/*
2 * Copyright 2012 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 SkPathRef_DEFINED
9#define SkPathRef_DEFINED
10
11#include "include/core/SkMatrix.h"
12#include "include/core/SkPathTypes.h"
13#include "include/core/SkPoint.h"
14#include "include/core/SkRRect.h"
15#include "include/core/SkRect.h"
16#include "include/core/SkRefCnt.h"
17#include "include/private/SkIDChangeListener.h"
18#include "include/private/SkMutex.h"
19#include "include/private/SkTDArray.h"
20#include "include/private/SkTemplates.h"
21#include "include/private/SkTo.h"
22
23#include <atomic>
24#include <limits>
25#include <tuple>
26
27struct SkPathView;
28class SkRBuffer;
29class SkWBuffer;
30
31/**
32 * Holds the path verbs and points. It is versioned by a generation ID. None of its public methods
33 * modify the contents. To modify or append to the verbs/points wrap the SkPathRef in an
34 * SkPathRef::Editor object. Installing the editor resets the generation ID. It also performs
35 * copy-on-write if the SkPathRef is shared by multiple SkPaths. The caller passes the Editor's
36 * constructor a pointer to a sk_sp<SkPathRef>, which may be updated to point to a new SkPathRef
37 * after the editor's constructor returns.
38 *
39 * The points and verbs are stored in a single allocation. The points are at the begining of the
40 * allocation while the verbs are stored at end of the allocation, in reverse order. Thus the points
41 * and verbs both grow into the middle of the allocation until the meet. To access verb i in the
42 * verb array use ref.verbs()[~i] (because verbs() returns a pointer just beyond the first
43 * logical verb or the last verb in memory).
44 */
45
46class SK_API SkPathRef final : public SkNVRefCnt<SkPathRef> {
47public:
48 SkPathRef(SkTDArray<SkPoint> points, SkTDArray<uint8_t> verbs, SkTDArray<SkScalar> weights,
49 unsigned segmentMask)
50 : fPoints(std::move(points))
51 , fVerbs(std::move(verbs))
52 , fConicWeights(std::move(weights))
53 {
54 fBoundsIsDirty = true; // this also invalidates fIsFinite
55 fGenerationID = 0; // recompute
56 fSegmentMask = segmentMask;
57 fIsOval = false;
58 fIsRRect = false;
59 // The next two values don't matter unless fIsOval or fIsRRect are true.
60 fRRectOrOvalIsCCW = false;
61 fRRectOrOvalStartIdx = 0xAC;
62 SkDEBUGCODE(fEditorsAttached.store(0);)
63 SkDEBUGCODE(this->validate();)
64 }
65
66 class Editor {
67 public:
68 Editor(sk_sp<SkPathRef>* pathRef,
69 int incReserveVerbs = 0,
70 int incReservePoints = 0);
71
72 ~Editor() { SkDEBUGCODE(fPathRef->fEditorsAttached--;) }
73
74 /**
75 * Returns the array of points.
76 */
77 SkPoint* writablePoints() { return fPathRef->getWritablePoints(); }
78 const SkPoint* points() const { return fPathRef->points(); }
79
80 /**
81 * Gets the ith point. Shortcut for this->points() + i
82 */
83 SkPoint* atPoint(int i) { return fPathRef->getWritablePoints() + i; }
84 const SkPoint* atPoint(int i) const { return &fPathRef->fPoints[i]; }
85
86 /**
87 * Adds the verb and allocates space for the number of points indicated by the verb. The
88 * return value is a pointer to where the points for the verb should be written.
89 * 'weight' is only used if 'verb' is kConic_Verb
90 */
91 SkPoint* growForVerb(int /*SkPath::Verb*/ verb, SkScalar weight = 0) {
92 SkDEBUGCODE(fPathRef->validate();)
93 return fPathRef->growForVerb(verb, weight);
94 }
95
96 /**
97 * Allocates space for multiple instances of a particular verb and the
98 * requisite points & weights.
99 * The return pointer points at the first new point (indexed normally [<i>]).
100 * If 'verb' is kConic_Verb, 'weights' will return a pointer to the
101 * space for the conic weights (indexed normally).
102 */
103 SkPoint* growForRepeatedVerb(int /*SkPath::Verb*/ verb,
104 int numVbs,
105 SkScalar** weights = nullptr) {
106 return fPathRef->growForRepeatedVerb(verb, numVbs, weights);
107 }
108
109 /**
110 * Concatenates all verbs from 'path' onto the pathRef's verbs array. Increases the point
111 * count by the number of points in 'path', and the conic weight count by the number of
112 * conics in 'path'.
113 *
114 * Returns pointers to the uninitialized points and conic weights data.
115 */
116 std::tuple<SkPoint*, SkScalar*> growForVerbsInPath(const SkPathRef& path) {
117 return fPathRef->growForVerbsInPath(path);
118 }
119
120 /**
121 * Resets the path ref to a new verb and point count. The new verbs and points are
122 * uninitialized.
123 */
124 void resetToSize(int newVerbCnt, int newPointCnt, int newConicCount) {
125 fPathRef->resetToSize(newVerbCnt, newPointCnt, newConicCount);
126 }
127
128 /**
129 * Gets the path ref that is wrapped in the Editor.
130 */
131 SkPathRef* pathRef() { return fPathRef; }
132
133 void setIsOval(bool isOval, bool isCCW, unsigned start) {
134 fPathRef->setIsOval(isOval, isCCW, start);
135 }
136
137 void setIsRRect(bool isRRect, bool isCCW, unsigned start) {
138 fPathRef->setIsRRect(isRRect, isCCW, start);
139 }
140
141 void setBounds(const SkRect& rect) { fPathRef->setBounds(rect); }
142
143 private:
144 SkPathRef* fPathRef;
145 };
146
147 class SK_API Iter {
148 public:
149 Iter();
150 Iter(const SkPathRef&);
151
152 void setPathRef(const SkPathRef&);
153
154 /** Return the next verb in this iteration of the path. When all
155 segments have been visited, return kDone_Verb.
156
157 If any point in the path is non-finite, return kDone_Verb immediately.
158
159 @param pts The points representing the current verb and/or segment
160 This must not be NULL.
161 @return The verb for the current segment
162 */
163 uint8_t next(SkPoint pts[4]);
164 uint8_t peek() const;
165
166 SkScalar conicWeight() const { return *fConicWeights; }
167
168 private:
169 const SkPoint* fPts;
170 const uint8_t* fVerbs;
171 const uint8_t* fVerbStop;
172 const SkScalar* fConicWeights;
173 };
174
175public:
176 /**
177 * Gets a path ref with no verbs or points.
178 */
179 static SkPathRef* CreateEmpty();
180
181 /**
182 * Returns true if all of the points in this path are finite, meaning there
183 * are no infinities and no NaNs.
184 */
185 bool isFinite() const {
186 if (fBoundsIsDirty) {
187 this->computeBounds();
188 }
189 return SkToBool(fIsFinite);
190 }
191
192 /**
193 * Returns a mask, where each bit corresponding to a SegmentMask is
194 * set if the path contains 1 or more segments of that type.
195 * Returns 0 for an empty path (no segments).
196 */
197 uint32_t getSegmentMasks() const { return fSegmentMask; }
198
199 /** Returns true if the path is an oval.
200 *
201 * @param rect returns the bounding rect of this oval. It's a circle
202 * if the height and width are the same.
203 * @param isCCW is the oval CCW (or CW if false).
204 * @param start indicates where the contour starts on the oval (see
205 * SkPath::addOval for intepretation of the index).
206 *
207 * @return true if this path is an oval.
208 * Tracking whether a path is an oval is considered an
209 * optimization for performance and so some paths that are in
210 * fact ovals can report false.
211 */
212 bool isOval(SkRect* rect, bool* isCCW, unsigned* start) const {
213 if (fIsOval) {
214 if (rect) {
215 *rect = this->getBounds();
216 }
217 if (isCCW) {
218 *isCCW = SkToBool(fRRectOrOvalIsCCW);
219 }
220 if (start) {
221 *start = fRRectOrOvalStartIdx;
222 }
223 }
224
225 return SkToBool(fIsOval);
226 }
227
228 bool isRRect(SkRRect* rrect, bool* isCCW, unsigned* start) const {
229 if (fIsRRect) {
230 if (rrect) {
231 *rrect = this->getRRect();
232 }
233 if (isCCW) {
234 *isCCW = SkToBool(fRRectOrOvalIsCCW);
235 }
236 if (start) {
237 *start = fRRectOrOvalStartIdx;
238 }
239 }
240 return SkToBool(fIsRRect);
241 }
242
243
244 bool hasComputedBounds() const {
245 return !fBoundsIsDirty;
246 }
247
248 /** Returns the bounds of the path's points. If the path contains 0 or 1
249 points, the bounds is set to (0,0,0,0), and isEmpty() will return true.
250 Note: this bounds may be larger than the actual shape, since curves
251 do not extend as far as their control points.
252 */
253 const SkRect& getBounds() const {
254 if (fBoundsIsDirty) {
255 this->computeBounds();
256 }
257 return fBounds;
258 }
259
260 SkRRect getRRect() const;
261
262 /**
263 * Transforms a path ref by a matrix, allocating a new one only if necessary.
264 */
265 static void CreateTransformedCopy(sk_sp<SkPathRef>* dst,
266 const SkPathRef& src,
267 const SkMatrix& matrix);
268
269 // static SkPathRef* CreateFromBuffer(SkRBuffer* buffer);
270
271 /**
272 * Rollsback a path ref to zero verbs and points with the assumption that the path ref will be
273 * repopulated with approximately the same number of verbs and points. A new path ref is created
274 * only if necessary.
275 */
276 static void Rewind(sk_sp<SkPathRef>* pathRef);
277
278 ~SkPathRef();
279 int countPoints() const { return fPoints.count(); }
280 int countVerbs() const { return fVerbs.count(); }
281 int countWeights() const { return fConicWeights.count(); }
282
283 /**
284 * Returns a pointer one beyond the first logical verb (last verb in memory order).
285 */
286 const uint8_t* verbsBegin() const { return fVerbs.begin(); }
287
288 /**
289 * Returns a const pointer to the first verb in memory (which is the last logical verb).
290 */
291 const uint8_t* verbsEnd() const { return fVerbs.end(); }
292
293 /**
294 * Returns a const pointer to the first point.
295 */
296 const SkPoint* points() const { return fPoints.begin(); }
297
298 /**
299 * Shortcut for this->points() + this->countPoints()
300 */
301 const SkPoint* pointsEnd() const { return this->points() + this->countPoints(); }
302
303 const SkScalar* conicWeights() const { return fConicWeights.begin(); }
304 const SkScalar* conicWeightsEnd() const { return fConicWeights.end(); }
305
306 /**
307 * Convenience methods for getting to a verb or point by index.
308 */
309 uint8_t atVerb(int index) const { return fVerbs[index]; }
310 const SkPoint& atPoint(int index) const { return fPoints[index]; }
311
312 bool operator== (const SkPathRef& ref) const;
313
314 /**
315 * Writes the path points and verbs to a buffer.
316 */
317 void writeToBuffer(SkWBuffer* buffer) const;
318
319 /**
320 * Gets the number of bytes that would be written in writeBuffer()
321 */
322 uint32_t writeSize() const;
323
324 void interpolate(const SkPathRef& ending, SkScalar weight, SkPathRef* out) const;
325
326 /**
327 * Gets an ID that uniquely identifies the contents of the path ref. If two path refs have the
328 * same ID then they have the same verbs and points. However, two path refs may have the same
329 * contents but different genIDs.
330 */
331 uint32_t genID() const;
332
333 void addGenIDChangeListener(sk_sp<SkIDChangeListener>); // Threadsafe.
334 int genIDChangeListenerCount(); // Threadsafe
335
336 bool isValid() const;
337 SkDEBUGCODE(void validate() const { SkASSERT(this->isValid()); } )
338
339 SkPathView view(SkPathFillType, SkPathConvexityType) const;
340
341private:
342 enum SerializationOffsets {
343 kLegacyRRectOrOvalStartIdx_SerializationShift = 28, // requires 3 bits, ignored.
344 kLegacyRRectOrOvalIsCCW_SerializationShift = 27, // requires 1 bit, ignored.
345 kLegacyIsRRect_SerializationShift = 26, // requires 1 bit, ignored.
346 kIsFinite_SerializationShift = 25, // requires 1 bit
347 kLegacyIsOval_SerializationShift = 24, // requires 1 bit, ignored.
348 kSegmentMask_SerializationShift = 0 // requires 4 bits (deprecated)
349 };
350
351 SkPathRef() {
352 fBoundsIsDirty = true; // this also invalidates fIsFinite
353 fGenerationID = kEmptyGenID;
354 fSegmentMask = 0;
355 fIsOval = false;
356 fIsRRect = false;
357 // The next two values don't matter unless fIsOval or fIsRRect are true.
358 fRRectOrOvalIsCCW = false;
359 fRRectOrOvalStartIdx = 0xAC;
360 SkDEBUGCODE(fEditorsAttached.store(0);)
361 SkDEBUGCODE(this->validate();)
362 }
363
364 void copy(const SkPathRef& ref, int additionalReserveVerbs, int additionalReservePoints);
365
366 // Doesn't read fSegmentMask, but (re)computes it from the verbs array
367 unsigned computeSegmentMask() const;
368
369 // Return true if the computed bounds are finite.
370 static bool ComputePtBounds(SkRect* bounds, const SkPathRef& ref) {
371 return bounds->setBoundsCheck(ref.points(), ref.countPoints());
372 }
373
374 // called, if dirty, by getBounds()
375 void computeBounds() const {
376 SkDEBUGCODE(this->validate();)
377 // TODO(mtklein): remove fBoundsIsDirty and fIsFinite,
378 // using an inverted rect instead of fBoundsIsDirty and always recalculating fIsFinite.
379 SkASSERT(fBoundsIsDirty);
380
381 fIsFinite = ComputePtBounds(&fBounds, *this);
382 fBoundsIsDirty = false;
383 }
384
385 void setBounds(const SkRect& rect) {
386 SkASSERT(rect.fLeft <= rect.fRight && rect.fTop <= rect.fBottom);
387 fBounds = rect;
388 fBoundsIsDirty = false;
389 fIsFinite = fBounds.isFinite();
390 }
391
392 /** Makes additional room but does not change the counts or change the genID */
393 void incReserve(int additionalVerbs, int additionalPoints) {
394 SkDEBUGCODE(this->validate();)
395 fPoints.setReserve(fPoints.count() + additionalPoints);
396 fVerbs.setReserve(fVerbs.count() + additionalVerbs);
397 SkDEBUGCODE(this->validate();)
398 }
399
400 /** Resets the path ref with verbCount verbs and pointCount points, all uninitialized. Also
401 * allocates space for reserveVerb additional verbs and reservePoints additional points.*/
402 void resetToSize(int verbCount, int pointCount, int conicCount,
403 int reserveVerbs = 0, int reservePoints = 0) {
404 SkDEBUGCODE(this->validate();)
405 this->callGenIDChangeListeners();
406 fBoundsIsDirty = true; // this also invalidates fIsFinite
407 fGenerationID = 0;
408
409 fSegmentMask = 0;
410 fIsOval = false;
411 fIsRRect = false;
412
413 fPoints.setReserve(pointCount + reservePoints);
414 fPoints.setCount(pointCount);
415 fVerbs.setReserve(verbCount + reserveVerbs);
416 fVerbs.setCount(verbCount);
417 fConicWeights.setCount(conicCount);
418 SkDEBUGCODE(this->validate();)
419 }
420
421 /**
422 * Increases the verb count by numVbs and point count by the required amount.
423 * The new points are uninitialized. All the new verbs are set to the specified
424 * verb. If 'verb' is kConic_Verb, 'weights' will return a pointer to the
425 * uninitialized conic weights.
426 */
427 SkPoint* growForRepeatedVerb(int /*SkPath::Verb*/ verb, int numVbs, SkScalar** weights);
428
429 /**
430 * Increases the verb count 1, records the new verb, and creates room for the requisite number
431 * of additional points. A pointer to the first point is returned. Any new points are
432 * uninitialized.
433 */
434 SkPoint* growForVerb(int /*SkPath::Verb*/ verb, SkScalar weight);
435
436 /**
437 * Concatenates all verbs from 'path' onto our own verbs array. Increases the point count by the
438 * number of points in 'path', and the conic weight count by the number of conics in 'path'.
439 *
440 * Returns pointers to the uninitialized points and conic weights data.
441 */
442 std::tuple<SkPoint*, SkScalar*> growForVerbsInPath(const SkPathRef& path);
443
444 /**
445 * Private, non-const-ptr version of the public function verbsMemBegin().
446 */
447 uint8_t* verbsBeginWritable() { return fVerbs.begin(); }
448
449 /**
450 * Called the first time someone calls CreateEmpty to actually create the singleton.
451 */
452 friend SkPathRef* sk_create_empty_pathref();
453
454 void setIsOval(bool isOval, bool isCCW, unsigned start) {
455 fIsOval = isOval;
456 fRRectOrOvalIsCCW = isCCW;
457 fRRectOrOvalStartIdx = SkToU8(start);
458 }
459
460 void setIsRRect(bool isRRect, bool isCCW, unsigned start) {
461 fIsRRect = isRRect;
462 fRRectOrOvalIsCCW = isCCW;
463 fRRectOrOvalStartIdx = SkToU8(start);
464 }
465
466 // called only by the editor. Note that this is not a const function.
467 SkPoint* getWritablePoints() {
468 SkDEBUGCODE(this->validate();)
469 fIsOval = false;
470 fIsRRect = false;
471 return fPoints.begin();
472 }
473
474 const SkPoint* getPoints() const {
475 SkDEBUGCODE(this->validate();)
476 return fPoints.begin();
477 }
478
479 void callGenIDChangeListeners();
480
481 enum {
482 kMinSize = 256,
483 };
484
485 mutable SkRect fBounds;
486
487 SkTDArray<SkPoint> fPoints;
488 SkTDArray<uint8_t> fVerbs;
489 SkTDArray<SkScalar> fConicWeights;
490
491 enum {
492 kEmptyGenID = 1, // GenID reserved for path ref with zero points and zero verbs.
493 };
494 mutable uint32_t fGenerationID;
495 SkDEBUGCODE(std::atomic<int> fEditorsAttached;) // assert only one editor in use at any time.
496
497 SkIDChangeListener::List fGenIDChangeListeners;
498
499 mutable uint8_t fBoundsIsDirty;
500 mutable bool fIsFinite; // only meaningful if bounds are valid
501
502 bool fIsOval;
503 bool fIsRRect;
504 // Both the circle and rrect special cases have a notion of direction and starting point
505 // The next two variables store that information for either.
506 bool fRRectOrOvalIsCCW;
507 uint8_t fRRectOrOvalStartIdx;
508 uint8_t fSegmentMask;
509
510 friend class PathRefTest_Private;
511 friend class ForceIsRRect_Private; // unit test isRRect
512 friend class SkPath;
513 friend class SkPathBuilder;
514 friend class SkPathPriv;
515};
516
517#endif
518