Move more of SkPath into SkPathRef

include/core/SkPathRef.h

 
 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #ifndef SkPathRef_DEFINED
 #define SkPathRef_DEFINED
 
 #include "SkMatrix.h"
 #include "SkPoint.h"
 #include "SkRect.h"
 #include "SkRefCnt.h"
 #include "SkTDArray.h"
 #include <stddef.h> // ptrdiff_t
 
 class SkRBuffer;
 class SkWBuffer;
 
 /**
  * Holds the path verbs and points. It is versioned by a generation ID. None of its public methods
  * modify the contents. To modify or append to the verbs/points wrap the SkPathRef in an
  * SkPathRef::Editor object. Installing the editor resets the generation ID. It also performs
- * copy-on-write if the SkPathRef is shared by multipls SkPaths. The caller passes the Editor's
+ * copy-on-write if the SkPathRef is shared by multiple SkPaths. The caller passes the Editor's
  * constructor a SkAutoTUnref, which may be updated to point to a new SkPathRef after the editor's
  * constructor returns.
  *
  * The points and verbs are stored in a single allocation. The points are at the begining of the
  * allocation while the verbs are stored at end of the allocation, in reverse order. Thus the points
  * and verbs both grow into the middle of the allocation until the meet. To access verb i in the
  * verb array use ref.verbs()[~i] (because verbs() returns a pointer just beyond the first
  * logical verb or the last verb in memory).
  */
 
 class SK_API SkPathRef : public ::SkRefCnt {
 public:
     SK_DECLARE_INST_COUNT(SkPathRef);
 
+    enum Verb {
+        kMove_Verb,     //!< iter.next returns 1 point
+        kLine_Verb,     //!< iter.next returns 2 points
+        kQuad_Verb,     //!< iter.next returns 3 points
+        kConic_Verb,    //!< iter.next returns 3 points + iter.conicWeight()
+        kCubic_Verb,    //!< iter.next returns 4 points
+        kClose_Verb,    //!< iter.next returns 1 point (contour's moveTo pt)
+        kDone_Verb,     //!< iter.next returns 0 points
+    };
+
     class Editor {
     public:
         Editor(SkAutoTUnref<SkPathRef>* pathRef,
                int incReserveVerbs = 0,
                int incReservePoints = 0);
 
         ~Editor() { SkDEBUGCODE(sk_atomic_dec(&fPathRef->fEditorsAttached);) }
 
         /**
          * Returns the array of points.
          */
         SkPoint* points() { return fPathRef->fPoints; }
 
         /**
          * Gets the ith point. Shortcut for this->points() + i
          */
         SkPoint* atPoint(int i) {
             SkASSERT((unsigned) i < (unsigned) fPathRef->fPointCnt);
             return this->points() + i;
         };
 
         /**
          * Adds the verb and allocates space for the number of points indicated by the verb. The
          * return value is a pointer to where the points for the verb should be written.
          */
-        SkPoint* growForVerb(int /*SkPath::Verb*/ verb) {
+        SkPoint* growForVerb(Verb verb) {
             SkDEBUGCODE(fPathRef->validate();)
             return fPathRef->growForVerb(verb);
         }
 
-        SkPoint* growForConic(SkScalar w);
-
+        SkPoint* growForConic(SkScalar w) {
+            SkDEBUGCODE(fPathRef->validate();)
+            SkPoint* pts = fPathRef->growForVerb(kConic_Verb);
+            *fPathRef->fConicWeights.append() = w;
+            return pts;
+        }
         /**
-         * Allocates space for additional verbs and points and returns pointers to the new verbs and
-         * points. verbs will point one beyond the first new verb (index it using [~<i>]). pts points
-         * at the first new point (indexed normally [<i>]).
+         * Allocates space for additional lines and returns a pointer to the new
+         * points. The return pointer points at the first new point (indexed normally [<i>]).
          */
-        void grow(int newVerbs, int newPts, uint8_t** verbs, SkPoint** pts) {
-            SkASSERT(NULL != verbs);
-            SkASSERT(NULL != pts);
+        SkPoint* growForLines(int numLines) {
             SkDEBUGCODE(fPathRef->validate();)
-            int oldVerbCnt = fPathRef->fVerbCnt;
-            int oldPointCnt = fPathRef->fPointCnt;
-            SkASSERT(verbs && pts);
-            fPathRef->grow(newVerbs, newPts);
-            *verbs = fPathRef->fVerbs - oldVerbCnt;
-            *pts = fPathRef->fPoints + oldPointCnt;
-            SkDEBUGCODE(fPathRef->validate();)
+            return fPathRef->growForLines(numLines);
         }
 
         /**
          * Resets the path ref to a new verb and point count. The new verbs and points are
          * uninitialized.
          */
         void resetToSize(int newVerbCnt, int newPointCnt, int newConicCount) {
             fPathRef->resetToSize(newVerbCnt, newPointCnt, newConicCount);
         }
+
         /**
          * Gets the path ref that is wrapped in the Editor.
          */
         SkPathRef* pathRef() { return fPathRef; }
 
     private:
         SkPathRef* fPathRef;
     };
 
 public:
     /**
      * Gets a path ref with no verbs or points.
      */
     static SkPathRef* CreateEmpty() {
         static SkPathRef* gEmptyPathRef;
         if (!gEmptyPathRef) {
             gEmptyPathRef = SkNEW(SkPathRef); // leak!
             gEmptyPathRef->computeBounds();   // Premptively avoid a race to clear fBoundsIsDirty.
         }
         return SkRef(gEmptyPathRef);
     }
 
+    enum Direction {
+        /** Direction either has not been or could not be computed */
+        kUnknown_Direction,
+        /** clockwise direction for adding closed contours */
+        kCW_Direction,
+        /** counter-clockwise direction for adding closed contours */
+        kCCW_Direction,
+    };
+
+    /**
+     *  Return the opposite of the specified direction. kUnknown is its own
+     *  opposite.
+     */
+    static Direction OppositeDirection(Direction dir) {
+        static const Direction gOppositeDir[] = {
+            kUnknown_Direction,
+            kCCW_Direction,
+            kCW_Direction
+        };
+        return gOppositeDir[dir];
+    }
+
+    Direction getDirection() const { return (Direction) fDirection; }
+
+    enum Convexity {
+        kUnknown_Convexity,
+        kConvex_Convexity,
+        kConcave_Convexity
+    };
+
+    /**
+     *  Return the path's convexity, as stored in the path. If it is currently unknown,
+     *  then this function will attempt to compute the convexity (and cache the result).
+     */
+    Convexity getConvexity() const {
+        if (kUnknown_Convexity != fConvexity) {
+            return static_cast<Convexity>(fConvexity);
+        } else {
+            return this->internalGetConvexity();
+        }
+    }
+
+    /**
+     *  Return the currently cached value for convexity, even if that is set to
+     *  kUnknown_Convexity. Note: getConvexity() will automatically call
+     *  ComputeConvexity and cache its return value if the current setting is
+     *  kUnknown.
+     */
+    Convexity getConvexityOrUnknown() const { 
+        return (Convexity) fConvexity; 
+    }
+
+    /**
+     *  Store a convexity setting in the path. There is no automatic check to
+     *  see if this value actually agrees with the return value that would be
+     *  computed by getConvexity().
+     *
+     *  Note: even if this is set to a "known" value, if the path is later
+     *  changed (e.g. lineTo(), addRect(), etc.) then the cached value will be
+     *  reset to kUnknown_Convexity.
+     */
+    void setConvexity(Convexity convexity) {
+        fConvexity = convexity;
+    }
+
+    /** Returns true if the path is an oval.
+     *
+     * @param rect      returns the bounding rect of this oval. It's a circle
+     *                  if the height and width are the same.
+     *
+     * @return true if this path is an oval.
+     *              Tracking whether a path is an oval is considered an
+     *              optimization for performance and so some paths that are in
+     *              fact ovals can report false.
+     */
+    bool isOval(SkRect* rect) const {
+        if (fIsOval && NULL != rect) {
+            *rect = this->getBounds();
+        }
+        return SkToBool(fIsOval);
+    }
+
     /**
      *  Returns true if all of the points in this path are finite, meaning there
      *  are no infinities and no NaNs.
      */
     bool isFinite() const {
         if (fBoundsIsDirty) {
             this->computeBounds();
         }
         return SkToBool(fIsFinite);
     }
 
+    enum SegmentMask {
+        kLine_SegmentMask   = 1 << 0,
+        kQuad_SegmentMask   = 1 << 1,
+        kConic_SegmentMask  = 1 << 2,
+        kCubic_SegmentMask  = 1 << 3,
+    };
+
+    /**
+     *  Returns a mask, where each bit corresponding to a SegmentMask is
+     *  set if the path contains 1 or more segments of that type.
+     *  Returns 0 for an empty path (no segments).
+     */
+    uint32_t getSegmentMasks() const { return fSegmentMask; }
+
     bool hasComputedBounds() const {
         return !fBoundsIsDirty;
     }
 
     /** Returns the bounds of the path's points. If the path contains 0 or 1
         points, the bounds is set to (0,0,0,0), and isEmpty() will return true.
         Note: this bounds may be larger than the actual shape, since curves
         do not extend as far as their control points.
     */
     const SkRect& getBounds() const {
@@ skipping 88 matching lines @@
      */
     void writeToBuffer(SkWBuffer* buffer);
 
     /**
      * Gets the number of bytes that would be written in writeBuffer()
      */
     uint32_t writeSize();
 
 private:
     enum SerializationOffsets {
+        kDirection_SerializationShift = 26, // requires 2 bits
         kIsFinite_SerializationShift = 25,  // requires 1 bit
+        kIsOval_SerializationShift = 24,    // requires 1 bit
+        kConvexity_SerializationShift = 16, // requires 8 bits
+        // FillType (in SkPath) takes up 8
+        kSegmentMask_SerializationShift = 0 // requires 4 bits
     };
 
+    // flag to require a moveTo if we begin with something else, like lineTo etc.
+    static const int kINITIAL_LASTMOVETOINDEX_VALUE = ~0;
+
     SkPathRef() {
         fBoundsIsDirty = true;    // this also invalidates fIsFinite
         fPointCnt = 0;
         fVerbCnt = 0;
         fVerbs = NULL;
         fPoints = NULL;
         fFreeSpace = 0;
         fGenerationID = kEmptyGenID;
         SkDEBUGCODE(fEditorsAttached = 0;)
+        fLastMoveToIndex = kINITIAL_LASTMOVETOINDEX_VALUE;
+        fSegmentMask = 0;
+        fConvexity = kUnknown_Convexity;
+        fDirection = kUnknown_Direction;
+        fIsOval = false;
         SkDEBUGCODE(this->validate();)
     }
 
     void copy(const SkPathRef& ref, int additionalReserveVerbs, int additionalReservePoints);
 
     // Return true if the computed bounds are finite.
-    static bool ComputePtBounds(SkRect* bounds, const SkPathRef& ref) {
-        int count = ref.countPoints();
+    static bool ComputePtBounds(SkRect* bounds, const SkPoint* points, int count) {
         if (count <= 1) {  // we ignore just 1 point (moveto)
             bounds->setEmpty();
-            return count ? ref.points()->isFinite() : true;
+            return count ? points->isFinite() : true;
         } else {
-            return bounds->setBoundsCheck(ref.points(), count);
+            return bounds->setBoundsCheck(points, count);
         }
     }
 
     // called, if dirty, by getBounds()
     void computeBounds() const {
         SkDEBUGCODE(this->validate();)
         SkASSERT(fBoundsIsDirty);
 
-        fIsFinite = ComputePtBounds(&fBounds, *this);
+        fIsFinite = ComputePtBounds(&fBounds, this->points(), this->countPoints());
         fBoundsIsDirty = false;
     }
 
     /** Makes additional room but does not change the counts or change the genID */
     void incReserve(int additionalVerbs, int additionalPoints) {
         SkDEBUGCODE(this->validate();)
         size_t space = additionalVerbs * sizeof(uint8_t) + additionalPoints * sizeof (SkPoint);
         this->makeSpace(space);
         SkDEBUGCODE(this->validate();)
     }
 
     /** Resets the path ref with verbCount verbs and pointCount points, all uninitialized. Also
      *  allocates space for reserveVerb additional verbs and reservePoints additional points.*/
     void resetToSize(int verbCount, int pointCount, int conicCount,
                      int reserveVerbs = 0, int reservePoints = 0) {
         SkDEBUGCODE(this->validate();)
         fBoundsIsDirty = true;      // this also invalidates fIsFinite
         fGenerationID = 0;
 
+        fLastMoveToIndex = kINITIAL_LASTMOVETOINDEX_VALUE;
+        fSegmentMask = 0;
+        fConvexity = kUnknown_Convexity;
+        fDirection = kUnknown_Direction;
+        fIsOval = false;
+
         size_t newSize = sizeof(uint8_t) * verbCount + sizeof(SkPoint) * pointCount;
         size_t newReserve = sizeof(uint8_t) * reserveVerbs + sizeof(SkPoint) * reservePoints;
         size_t minSize = newSize + newReserve;
 
         ptrdiff_t sizeDelta = this->currSize() - minSize;
 
         if (sizeDelta < 0 || static_cast<size_t>(sizeDelta) >= 3 * minSize) {
             sk_free(fPoints);
             fPoints = NULL;
             fVerbs = NULL;
             fFreeSpace = 0;
             fVerbCnt = 0;
             fPointCnt = 0;
             this->makeSpace(minSize);
             fVerbCnt = verbCount;
             fPointCnt = pointCount;
             fFreeSpace -= newSize;
         } else {
             fPointCnt = pointCount;
             fVerbCnt = verbCount;
             fFreeSpace = this->currSize() - minSize;
         }
         fConicWeights.setCount(conicCount);
         SkDEBUGCODE(this->validate();)
     }
 
+    // This method assumes space has already been allocated for the new
+    // verb and point.
+    void injectMove() {
+        SkScalar x, y;
+        if (this->countVerbs() == 0) {
+            x = y = 0;
+        } else {
+            const SkPoint& pt = this->atPoint(~fLastMoveToIndex);
+            x = pt.fX;
+            y = pt.fY;
+        }
+        fPoints[fPointCnt].set(x, y);
+        fLastMoveToIndex = fPointCnt;
+        ++fPointCnt;
+        fVerbs[~fVerbCnt] = kMove_Verb;
+        ++fVerbCnt;
+    }
+
+
     /**
-     * Increases the verb count by newVerbs and the point count be newPoints. New verbs and points
-     * are uninitialized.
+     * Increases the verb and point count by numLines. The new points
+     * are uninitialized. All the new verbs are set to kLine_SegmentMask.
      */
-    void grow(int newVerbs, int newPoints) {
+    SkPoint* growForLines(int numLines) {
+        // This value is just made-up for now. When numLines is 3, calling memset was much
+        // slower than just writing the loop. This seems odd, and hopefully in the
+        // future this will appear to have been a fluke...
+        static const unsigned int kMIN_COUNT_FOR_MEMSET_TO_BE_FAST = 16;
+
+        // TODO: The following isn't hyper-optimized for the lines case since
+        // it should be expanded to handle quads, conics and cubics
         SkDEBUGCODE(this->validate();)
-        size_t space = newVerbs * sizeof(uint8_t) + newPoints * sizeof (SkPoint);
+        bool dirtyAfterEdit = true;
+        bool moveInjectionNeeded = false;
+
+        moveInjectionNeeded = fLastMoveToIndex < 0;
+
+        size_t space = numLines * sizeof(uint8_t) + numLines * sizeof (SkPoint);
+        if (moveInjectionNeeded) {
+            space += sizeof(uint8_t) + sizeof(SkPoint);
+        }
         this->makeSpace(space);
-        fVerbCnt += newVerbs;
-        fPointCnt += newPoints;
+        if (moveInjectionNeeded) {
+            SkASSERT(dirtyAfterEdit);
+            this->injectMove();
+        }
+        SkPoint* ret = fPoints + fPointCnt;
+        uint8_t* vb = fVerbs - fVerbCnt;
+
+        // cast to unsigned, so if MIN_COUNT_FOR_MEMSET_TO_BE_FAST is defined to
+        // be 0, the compiler will remove the test/branch entirely.
+        if ((unsigned)numLines >= kMIN_COUNT_FOR_MEMSET_TO_BE_FAST) {
+            memset(vb - numLines, kLine_Verb, numLines);
+        } else {
+            for (int i = 0; i < numLines; ++i) {
+                vb[~i] = kLine_Verb;
+            }
+        }
+        fSegmentMask |= kLine_SegmentMask;
+
+        fVerbCnt += numLines;
+        fPointCnt += numLines;
         fFreeSpace -= space;
         fBoundsIsDirty = true;  // this also invalidates fIsFinite
+
+        if (dirtyAfterEdit) {
+            fConvexity = kUnknown_Convexity;
+            fDirection = kUnknown_Direction;
+            fIsOval = false;
+        }
+
         SkDEBUGCODE(this->validate();)
+        return ret;
     }
 
     /**
      * Increases the verb count 1, records the new verb, and creates room for the requisite number
      * of additional points. A pointer to the first point is returned. Any new points are
      * uninitialized.
      */
-    SkPoint* growForVerb(int /*SkPath::Verb*/ verb);
+    SkPoint* growForVerb(Verb verb);
 
     /**
      * Ensures that the free space available in the path ref is >= size. The verb and point counts
      * are not changed.
      */
     void makeSpace(size_t size) {
         SkDEBUGCODE(this->validate();)
         ptrdiff_t growSize = size - fFreeSpace;
         if (growSize <= 0) {
             return;
@@ skipping 41 matching lines @@
     /**
      * Gets an ID that uniquely identifies the contents of the path ref. If two path refs have the
      * same ID then they have the same verbs and points. However, two path refs may have the same
      * contents but different genIDs. Zero is reserved and means an ID has not yet been determined
      * for the path ref.
      */
     int32_t genID() const;
 
     SkDEBUGCODE(void validate() const;)
 
+    Convexity internalGetConvexity() const;
+
+    void setIsOval(bool isOval) { fIsOval = isOval; }
+    void setDirection(Direction direction) { fDirection = direction; }
+
+    /**
+     *  Tries to quickly compute the direction of the first non-degenerate
+     *  contour. If it can be computed, return true and set dir to that
+     *  direction. If it cannot be (quickly) determined, return false and ignore
+     *  the dir parameter. If the direction was determined, it is cached to make
+     *  subsequent calls return quickly.
+     */
+    bool cheapComputeDirection(Direction* dir) const;
+
     enum {
         kMinSize = 256,
     };
 
     mutable SkRect      fBounds;
+    int                 fLastMoveToIndex;
+
+    uint8_t             fSegmentMask;
     mutable uint8_t     fBoundsIsDirty;
+    mutable uint8_t     fConvexity;
+    mutable uint8_t     fDirection;
     mutable SkBool8     fIsFinite;    // only meaningful if bounds are valid
+    mutable SkBool8     fIsOval;
 
     SkPoint*            fPoints; // points to begining of the allocation
     uint8_t*            fVerbs; // points just past the end of the allocation (verbs grow backwards)
     int                 fVerbCnt;
     int                 fPointCnt;
     size_t              fFreeSpace; // redundant but saves computation
     SkTDArray<SkScalar> fConicWeights;
 
     enum {
         kEmptyGenID = 1, // GenID reserved for path ref with zero points and zero verbs.
     };
     mutable int32_t     fGenerationID;
     SkDEBUGCODE(int32_t fEditorsAttached;) // assert that only one editor in use at any time.
 
+    friend class SkPath;
+
     typedef SkRefCnt INHERITED;
 };
 
 #endif