Move more of SkPath into SkPathRef

src/core/SkPathRef.cpp

 /*
  * Copyright 2013 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkBuffer.h"
 #include "SkPath.h"
 #include "SkPathRef.h"
@@ skipping 10 matching lines @@
     } else {
         SkPathRef* copy = SkNEW(SkPathRef);
         copy->copy(**pathRef, incReserveVerbs, incReservePoints);
         pathRef->reset(copy);
     }
     fPathRef = *pathRef;
     fPathRef->fGenerationID = 0;
     SkDEBUGCODE(sk_atomic_inc(&fPathRef->fEditorsAttached);)
 }
 
-SkPoint* SkPathRef::Editor::growForConic(SkScalar w) {
-    SkDEBUGCODE(fPathRef->validate();)
-    SkPoint* pts = fPathRef->growForVerb(SkPath::kConic_Verb);
-    *fPathRef->fConicWeights.append() = w;
-    return pts;
-}
-
 //////////////////////////////////////////////////////////////////////////////
 void SkPathRef::CreateTransformedCopy(SkAutoTUnref<SkPathRef>* dst,
                                       const SkPathRef& src,
                                       const SkMatrix& matrix) {
     SkDEBUGCODE(src.validate();)
     if (matrix.isIdentity()) {
         if (*dst != &src) {
             src.ref();
             dst->reset(const_cast<SkPathRef*>(&src));
             SkDEBUGCODE((*dst)->validate();)
@@ skipping 32 matching lines @@
                 (*dst)->fBounds.setEmpty();
             }
         } else {
             (*dst)->fIsFinite = false;
             (*dst)->fBounds.setEmpty();
         }
     } else {
         (*dst)->fBoundsIsDirty = true;
     }
 
+    (*dst)->fLastMoveToIndex = src.fLastMoveToIndex;
+    (*dst)->fSegmentMask = src.fSegmentMask;
+    (*dst)->fConvexity   = src.fConvexity;
+
+    if (SkPathRef::kUnknown_Direction == src.fDirection) {
+        (*dst)->fDirection = SkPathRef::kUnknown_Direction;
+    } else {
+        SkScalar det2x2 =
+            SkScalarMul(matrix.get(SkMatrix::kMScaleX), matrix.get(SkMatrix::kMScaleY)) -
+            SkScalarMul(matrix.get(SkMatrix::kMSkewX), matrix.get(SkMatrix::kMSkewY));
+        if (det2x2 < 0) {
+            (*dst)->fDirection = SkPathRef::OppositeDirection(src.getDirection());
+        } else if (det2x2 > 0) {
+            (*dst)->fDirection = src.fDirection;
+        } else {
+            (*dst)->fDirection = SkPathRef::kUnknown_Direction;
+        }
+    }
+
+    // It's an oval only if it stays a rect.
+    (*dst)->fIsOval = src.fIsOval && matrix.rectStaysRect();
+
     SkDEBUGCODE((*dst)->validate();)
 }
 
 SkPathRef* SkPathRef::CreateFromBuffer(SkRBuffer* buffer
 #ifndef DELETE_THIS_CODE_WHEN_SKPS_ARE_REBUILT_AT_V14_AND_ALL_OTHER_INSTANCES_TOO
                                    , bool newFormat, int32_t oldPacked
 #endif
     ) {
     SkPathRef* ref = SkNEW(SkPathRef);
+    int32_t packed;
 #ifndef DELETE_THIS_CODE_WHEN_SKPS_ARE_REBUILT_AT_V14_AND_ALL_OTHER_INSTANCES_TOO
     if (newFormat) {
 #endif
-        int32_t packed = buffer->readU32();
-
-        ref->fIsFinite = (packed >> kIsFinite_SerializationShift) & 1;
+        packed = buffer->readU32();
 #ifndef DELETE_THIS_CODE_WHEN_SKPS_ARE_REBUILT_AT_V14_AND_ALL_OTHER_INSTANCES_TOO
-    } else {
-        ref->fIsFinite = (oldPacked >> SkPath::kOldIsFinite_SerializationShift) & 1;
     }
 #endif
 
     ref->fGenerationID = buffer->readU32();
     int32_t verbCount = buffer->readS32();
     int32_t pointCount = buffer->readS32();
     int32_t conicCount = buffer->readS32();
     ref->resetToSize(verbCount, pointCount, conicCount);
 
+#ifndef DELETE_THIS_CODE_WHEN_SKPS_ARE_REBUILT_AT_V14_AND_ALL_OTHER_INSTANCES_TOO
+    if (newFormat) {
+#endif
+        ref->fSegmentMask = (packed >> kSegmentMask_SerializationShift) & 0xF;
+        ref->fConvexity = (packed >> kConvexity_SerializationShift) & 0xFF;
+        ref->fIsOval = (packed >> kIsOval_SerializationShift) & 1;
+        ref->fIsFinite = (packed >> kIsFinite_SerializationShift) & 1;
+        ref->fDirection = (packed >> kDirection_SerializationShift) & 0x3;
+#ifndef DELETE_THIS_CODE_WHEN_SKPS_ARE_REBUILT_AT_V14_AND_ALL_OTHER_INSTANCES_TOO
+    } else {
+        ref->fSegmentMask = (oldPacked >> SkPath::kOldSegmentMask_SerializationShift) & 0xF;
+        ref->fConvexity = (oldPacked >> SkPath::kOldConvexity_SerializationShift) & 0xFF;
+        ref->fIsOval = (oldPacked >> SkPath::kOldIsOval_SerializationShift) & 1;
+        ref->fIsFinite = (oldPacked >> SkPath::kOldIsFinite_SerializationShift) & 1;
+        ref->fDirection = (oldPacked >> SkPath::kOldDirection_SerializationShift) & 0x3;
+    }
+#endif
+
     SkASSERT(verbCount == ref->countVerbs());
     SkASSERT(pointCount == ref->countPoints());
     SkASSERT(conicCount == ref->fConicWeights.count());
     buffer->read(ref->verbsMemWritable(), verbCount * sizeof(uint8_t));
     buffer->read(ref->fPoints, pointCount * sizeof(SkPoint));
     buffer->read(ref->fConicWeights.begin(), conicCount * sizeof(SkScalar));
     buffer->read(&ref->fBounds, sizeof(SkRect));
     ref->fBoundsIsDirty = false;
+
+#ifdef SK_DEBUG_PATH
+    int lastMoveToIndex = kINITIAL_LASTMOVETOINDEX_VALUE;
+    int pointCnt = 0;
+
+    for (int i = 0; i < ref->fVerbCnt; ++i) {
+        switch (ref->fVerbs[~i]) {
+            case kMove_Verb:
+                lastMoveToIndex = pointCnt;
+                ++pointCnt;
+                break;
+            case kLine_Verb:
+                ++pointCnt;
+                break;
+            case kQuad_Verb:
+                pointCnt += 2;
+                break;
+            case kConic_Verb:
+                pointCnt += 2;
+                break;
+            case kCubic_Verb:
+                pointCnt += 3;
+                break;
+            case kClose_Verb:
+                if (lastMoveToIndex >= 0) {
+                    lastMoveToIndex = ~lastMoveToIndex;
+                }
+                break;
+            case kDone_Verb:
+                // fall through
+            default:
+                SkDEBUGFAIL("default is not reached");
+        }
+    }
+    ref->fLastMoveToIndex = lastMoveToIndex;
+#endif
+
     return ref;
 }
 
 void SkPathRef::Rewind(SkAutoTUnref<SkPathRef>* pathRef) {
     if ((*pathRef)->unique()) {
         SkDEBUGCODE((*pathRef)->validate();)
         (*pathRef)->fBoundsIsDirty = true;  // this also invalidates fIsFinite
         (*pathRef)->fVerbCnt = 0;
         (*pathRef)->fPointCnt = 0;
         (*pathRef)->fFreeSpace = (*pathRef)->currSize();
         (*pathRef)->fGenerationID = 0;
         (*pathRef)->fConicWeights.rewind();
+        (*pathRef)->fLastMoveToIndex = kINITIAL_LASTMOVETOINDEX_VALUE;
+        (*pathRef)->fSegmentMask = 0;
+        (*pathRef)->fConvexity = kUnknown_Convexity;
+        (*pathRef)->fDirection = kUnknown_Direction;
+        (*pathRef)->fIsOval = false;
         SkDEBUGCODE((*pathRef)->validate();)
     } else {
         int oldVCnt = (*pathRef)->countVerbs();
         int oldPCnt = (*pathRef)->countPoints();
         pathRef->reset(SkNEW(SkPathRef));
         (*pathRef)->resetToSize(0, 0, 0, oldVCnt, oldPCnt);
     }
 }
 
 bool SkPathRef::operator== (const SkPathRef& ref) const {
     SkDEBUGCODE(this->validate();)
     SkDEBUGCODE(ref.validate();)
+    // note: don't need to look at isConvex or bounds, since just comparing the
+    // raw data is sufficient.
+
+    // We explicitly check fSegmentMask as a quick-reject. We could skip it,
+    // since it is only a cache of info in the fVerbs, but its a fast way to
+    // notice a difference
+    if (fSegmentMask != ref.fSegmentMask) {
+        return false;
+    }
     bool genIDMatch = fGenerationID && fGenerationID == ref.fGenerationID;
 #ifdef SK_RELEASE
     if (genIDMatch) {
         return true;
     }
 #endif
     if (fPointCnt != ref.fPointCnt ||
         fVerbCnt != ref.fVerbCnt) {
         SkASSERT(!genIDMatch);
         return false;
@@ skipping 25 matching lines @@
 }
 
 void SkPathRef::writeToBuffer(SkWBuffer* buffer) {
     SkDEBUGCODE(this->validate();)
     SkDEBUGCODE(size_t beforePos = buffer->pos();)
 
     // Call getBounds() to ensure (as a side-effect) that fBounds
     // and fIsFinite are computed.
     const SkRect& bounds = this->getBounds();
 
-    int32_t packed = ((fIsFinite & 1) << kIsFinite_SerializationShift);
+    int32_t packed = ((fIsFinite & 1) << kIsFinite_SerializationShift) |
+                     ((fIsOval & 1) << kIsOval_SerializationShift) |    
+                     (fConvexity << kConvexity_SerializationShift) |    
+                     (fSegmentMask << kSegmentMask_SerializationShift) |        
+                     (fDirection << kDirection_SerializationShift);
     buffer->write32(packed);
 
     // TODO: write gen ID here. Problem: We don't know if we're cross process or not from
     // SkWBuffer. Until this is fixed we write 0.
     buffer->write32(0);
     buffer->write32(fVerbCnt);
     buffer->write32(fPointCnt);
     buffer->write32(fConicWeights.count());
     buffer->write(verbsMemBegin(), fVerbCnt * sizeof(uint8_t));
     buffer->write(fPoints, fPointCnt * sizeof(SkPoint));
@@ skipping 21 matching lines @@
     memcpy(this->fPoints, ref.fPoints, ref.fPointCnt * sizeof(SkPoint));
     fConicWeights = ref.fConicWeights;
     // We could call genID() here to force a real ID (instead of 0). However, if we're making
     // a copy then presumably we intend to make a modification immediately afterwards.
     fGenerationID = ref.fGenerationID;
     fBoundsIsDirty = ref.fBoundsIsDirty;
     if (!fBoundsIsDirty) {
         fBounds = ref.fBounds;
         fIsFinite = ref.fIsFinite;
     }
+    fLastMoveToIndex = ref.fLastMoveToIndex;
+    fSegmentMask = ref.fSegmentMask;
+    fConvexity = ref.fConvexity;
+    fDirection = ref.fDirection;
+    fIsOval = ref.fIsOval;
     SkDEBUGCODE(this->validate();)
 }
 
-SkPoint* SkPathRef::growForVerb(int /* SkPath::Verb*/ verb) {
+// In some cases we need to inject a leading moveTo before we add points
+// for lineTo, quadTo, conicTo, cubicTo
+//
+// SkPath path; path.lineTo(...);   <--- need a leading moveTo(0, 0)
+// SkPath path; ... path.close(); path.lineTo(...) <-- need a moveTo(previous moveTo)
+SkPoint* SkPathRef::growForVerb(Verb verb) {
     SkDEBUGCODE(this->validate();)
     int pCnt;
+    bool dirtyAfterEdit = true;
+    bool moveInjectionNeeded = false;
+    uint8_t newMask = 0;
+    int newLastMoveToIndex = fLastMoveToIndex;
+
     switch (verb) {
-        case SkPath::kMove_Verb:
+        case kMove_Verb:
+            // remember the index
+            newLastMoveToIndex = this->countPoints();
+            pCnt = 1;
+            dirtyAfterEdit = false;
+            break;
+        case kLine_Verb:
+            moveInjectionNeeded = fLastMoveToIndex < 0;
+            newMask = kLine_SegmentMask;
             pCnt = 1;
             break;
-        case SkPath::kLine_Verb:
-            pCnt = 1;
-            break;
-        case SkPath::kQuad_Verb:
-            // fall through
-        case SkPath::kConic_Verb:
+        case kQuad_Verb:
+            moveInjectionNeeded = fLastMoveToIndex < 0;
+            newMask = kQuad_SegmentMask;
             pCnt = 2;
             break;
-        case SkPath::kCubic_Verb:
+        case kConic_Verb:
+            moveInjectionNeeded = fLastMoveToIndex < 0;
+            newMask = kConic_SegmentMask;
+            pCnt = 2;
+            break;
+        case kCubic_Verb:
+            moveInjectionNeeded = fLastMoveToIndex < 0;
+            newMask = kCubic_SegmentMask;
             pCnt = 3;
             break;
-        case SkPath::kClose_Verb:
+        case kClose_Verb:
+            // signal that we need a moveTo to follow us (unless we're done)
+            newLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1);
             pCnt = 0;
+            dirtyAfterEdit = false;
             break;
-        case SkPath::kDone_Verb:
+        case kDone_Verb:
             SkDEBUGFAIL("growForVerb called for kDone");
             // fall through
         default:
             SkDEBUGFAIL("default is not reached");
+            dirtyAfterEdit = false;
             pCnt = 0;
     }
     size_t space = sizeof(uint8_t) + pCnt * sizeof (SkPoint);
+    if (moveInjectionNeeded) {
+        space += sizeof(uint8_t) + sizeof(SkPoint);
+    }
     this->makeSpace(space);
-    this->fVerbs[~fVerbCnt] = verb;
+    fLastMoveToIndex = newLastMoveToIndex;
+    if (moveInjectionNeeded) {
+        SkASSERT(dirtyAfterEdit);
+        this->injectMove();
+    } else {
+        fLastMoveToIndex = newLastMoveToIndex;
+    }
+    fVerbs[~fVerbCnt] = verb;
+    fSegmentMask |= newMask;
     SkPoint* ret = fPoints + fPointCnt;
     fVerbCnt += 1;
     fPointCnt += pCnt;
     fFreeSpace -= space;
     fBoundsIsDirty = true;  // this also invalidates fIsFinite
+    if (dirtyAfterEdit) {
+        fConvexity = kUnknown_Convexity;
+        fDirection = kUnknown_Direction;
+        fIsOval = false;
+    }
+
     SkDEBUGCODE(this->validate();)
     return ret;
 }
 
 int32_t SkPathRef::genID() const {
     SkASSERT(!fEditorsAttached);
     if (!fGenerationID) {
         if (0 == fPointCnt && 0 == fVerbCnt) {
             fGenerationID = kEmptyGenID;
         } else {
@@ skipping 14 matching lines @@
     SkASSERT(static_cast<ptrdiff_t>(fFreeSpace) >= 0);
     SkASSERT(reinterpret_cast<intptr_t>(fVerbs) - reinterpret_cast<intptr_t>(fPoints) >= 0);
     SkASSERT((NULL == fPoints) == (NULL == fVerbs));
     SkASSERT(!(NULL == fPoints && 0 != fFreeSpace));
     SkASSERT(!(NULL == fPoints && 0 != fFreeSpace));
     SkASSERT(!(NULL == fPoints && fPointCnt));
     SkASSERT(!(NULL == fVerbs && fVerbCnt));
     SkASSERT(this->currSize() ==
                 fFreeSpace + sizeof(SkPoint) * fPointCnt + sizeof(uint8_t) * fVerbCnt);
 
-#ifdef SK_DEBUG
     if (!fBoundsIsDirty && !fBounds.isEmpty()) {
         bool isFinite = true;
         for (int i = 0; i < fPointCnt; ++i) {
             SkASSERT(fPoints[i].fX >= fBounds.fLeft && fPoints[i].fX <= fBounds.fRight &&
                         fPoints[i].fY >= fBounds.fTop && fPoints[i].fY <= fBounds.fBottom);
             if (!fPoints[i].isFinite()) {
                 isFinite = false;
             }
         }
         SkASSERT(SkToBool(fIsFinite) == isFinite);
     }
+
+#ifdef SK_DEBUG_PATH
+    if (!fBoundsIsDirty) {
+        SkRect bounds;
+
+        bool isFinite = ComputePtBounds(&bounds, fPoints, fPointCnt);
+        SkASSERT(SkToBool(fIsFinite) == isFinite);
+
+        if (fPointCnt <= 1) {
+            // if we're empty, fBounds may be empty but translated, so we can't
+            // necessarily compare to bounds directly
+            // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will
+            // be [2, 2, 2, 2]
+            SkASSERT(bounds.isEmpty());
+            SkASSERT(fBounds.isEmpty());
+        } else {
+            if (bounds.isEmpty()) {
+                SkASSERT(fBounds.isEmpty());
+            } else {
+                if (!fBounds.isEmpty()) {
+                    SkASSERT(fBounds.contains(bounds));
+                }
+            }
+        }
+    }
+
+    uint32_t mask = 0;
+    int pointCnt = 0;
+    int lastMoveToIndex = ~0;
+    for (int i = 0; i < fVerbCnt; i++) {
+        switch (fVerbs[~i]) {
+            case kMove_Verb:
+                lastMoveToIndex = pointCnt;
+                ++pointCnt;
+                break;
+            case kLine_Verb:
+                mask |= kLine_SegmentMask;
+                ++pointCnt;
+                break;
+            case kQuad_Verb:
+                mask |= kQuad_SegmentMask;
+                pointCnt += 2;
+                break;
+            case kConic_Verb:
+                mask |= kConic_SegmentMask;
+                pointCnt += 2;
+                break;
+            case kCubic_Verb:
+                mask |= kCubic_SegmentMask;
+                pointCnt += 3;
+                break;
+            case kClose_Verb:
+                if (lastMoveToIndex >= 0) {
+                    lastMoveToIndex = ~lastMoveToIndex;
+                }
+                break;
+            case kDone_Verb:
+                SkDEBUGFAIL("Done verb shouldn't be recorded.");
+                break;
+            default:
+                SkDEBUGFAIL("Unknown Verb");
+                break;
+        }
+    }
+    SkASSERT(mask == fSegmentMask);
+    SkASSERT(lastMoveToIndex == fLastMoveToIndex);
+#endif // SK_DEBUG_PATH
+}
 #endif
+
+///////////////////////////////////////////////////////////////////////////////
+
+static int sign(SkScalar x) { return x < 0; }
+#define kValueNeverReturnedBySign   2
+
+static int CrossProductSign(const SkVector& a, const SkVector& b) {
+    return SkScalarSignAsInt(SkPoint::CrossProduct(a, b));
+}
+
+// only valid for a single contour
+struct Convexicator {
+    Convexicator()
+    : fPtCount(0)
+    , fConvexity(SkPathRef::kConvex_Convexity)
+    , fDirection(SkPathRef::kUnknown_Direction) {
+        fSign = 0;
+        // warnings
+        fCurrPt.set(0, 0);
+        fVec0.set(0, 0);
+        fVec1.set(0, 0);
+        fFirstVec.set(0, 0);
+
+        fDx = fDy = 0;
+        fSx = fSy = kValueNeverReturnedBySign;
+    }
+
+    SkPathRef::Convexity getConvexity() const { return fConvexity; }
+
+    /** The direction returned is only valid if the path is determined convex */
+    SkPathRef::Direction getDirection() const { return fDirection; }
+
+    void addPt(const SkPoint& pt) {
+        if (SkPathRef::kConcave_Convexity == fConvexity) {
+            return;
+        }
+
+        if (0 == fPtCount) {
+            fCurrPt = pt;
+            ++fPtCount;
+        } else {
+            SkVector vec = pt - fCurrPt;
+            if (vec.fX || vec.fY) {
+                fCurrPt = pt;
+                if (++fPtCount == 2) {
+                    fFirstVec = fVec1 = vec;
+                } else {
+                    SkASSERT(fPtCount > 2);
+                    this->addVec(vec);
+                }
+
+                int sx = sign(vec.fX);
+                int sy = sign(vec.fY);
+                fDx += (sx != fSx);
+                fDy += (sy != fSy);
+                fSx = sx;
+                fSy = sy;
+
+                if (fDx > 3 || fDy > 3) {
+                    fConvexity = SkPathRef::kConcave_Convexity;
+                }
+            }
+        }
+    }
+
+    void close() {
+        if (fPtCount > 2) {
+            this->addVec(fFirstVec);
+        }
+    }
+
+private:
+    void addVec(const SkVector& vec) {
+        SkASSERT(vec.fX || vec.fY);
+        fVec0 = fVec1;
+        fVec1 = vec;
+        int sign = CrossProductSign(fVec0, fVec1);
+        if (0 == fSign) {
+            fSign = sign;
+            if (1 == sign) {
+                fDirection = SkPathRef::kCW_Direction;
+            } else if (-1 == sign) {
+                fDirection = SkPathRef::kCCW_Direction;
+            }
+        } else if (sign) {
+            if (fSign != sign) {
+                fConvexity = SkPathRef::kConcave_Convexity;
+                fDirection = SkPathRef::kUnknown_Direction;
+            }
+        }
+    }
+
+    SkPoint              fCurrPt;
+    SkVector             fVec0, fVec1, fFirstVec;
+    int                  fPtCount;   // non-degenerate points
+    int                  fSign;
+    SkPathRef::Convexity fConvexity;
+    SkPathRef::Direction fDirection;
+    int                  fDx, fDy, fSx, fSy;
+};
+
+SkPathRef::Convexity SkPathRef::internalGetConvexity() const {
+    SkASSERT(kUnknown_Convexity == fConvexity);
+    SkPoint         pts[4];
+    SkPath::Verb    verb;
+    SkPath::Iter    iter(this, true);
+
+    int             contourCount = 0;
+    int             count;
+    Convexicator    state;
+
+    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
+        switch (verb) {
+            case SkPath::kMove_Verb:
+                if (++contourCount > 1) {
+                    fConvexity = kConcave_Convexity;
+                    return kConcave_Convexity;
+                }
+                pts[1] = pts[0];
+                count = 1;
+                break;
+            case SkPath::kLine_Verb: count = 1; break;
+            case SkPath::kQuad_Verb: count = 2; break;
+            case SkPath::kConic_Verb: count = 2; break;
+            case SkPath::kCubic_Verb: count = 3; break;
+            case SkPath::kClose_Verb:
+                state.close();
+                count = 0;
+                break;
+            default:
+                SkDEBUGFAIL("bad verb");
+                fConvexity = kConcave_Convexity;
+                return kConcave_Convexity;
+        }
+
+        for (int i = 1; i <= count; i++) {
+            state.addPt(pts[i]);
+        }
+        // early exit
+        if (kConcave_Convexity == state.getConvexity()) {
+            fConvexity = kConcave_Convexity;
+            return kConcave_Convexity;
+        }
+    }
+    fConvexity = state.getConvexity();
+    if (kConvex_Convexity == fConvexity && kUnknown_Direction == fDirection) {
+        fDirection = state.getDirection();
+    }
+    return static_cast<Convexity>(fConvexity);
+}
+
+class ContourIter {
+public:
+    ContourIter(const SkPathRef& pathRef);
+
+    bool done() const { return fDone; }
+    // if !done() then these may be called
+    int count() const { return fCurrPtCount; }
+    const SkPoint* pts() const { return fCurrPt; }
+    void next();
+
+private:
+    int fCurrPtCount;
+    const SkPoint* fCurrPt;
+    const uint8_t* fCurrVerb;
+    const uint8_t* fStopVerbs;
+    const SkScalar* fCurrConicWeight;
+    bool fDone;
+    SkDEBUGCODE(int fContourCounter;)
+};
+
+ContourIter::ContourIter(const SkPathRef& pathRef) {
+    fStopVerbs = pathRef.verbsMemBegin();
+    fDone = false;
+    fCurrPt = pathRef.points();
+    fCurrVerb = pathRef.verbs();
+    fCurrConicWeight = pathRef.conicWeights();
+    fCurrPtCount = 0;
+    SkDEBUGCODE(fContourCounter = 0;)
+    this->next();
+}
+
+void ContourIter::next() {
+    if (fCurrVerb <= fStopVerbs) {
+        fDone = true;
+    }
+    if (fDone) {
+        return;
+    }
+
+    // skip pts of prev contour
+    fCurrPt += fCurrPtCount;
+
+    SkASSERT(SkPathRef::kMove_Verb == fCurrVerb[~0]);
+    int ptCount = 1;    // moveTo
+    const uint8_t* verbs = fCurrVerb;
+
+    for (--verbs; verbs > fStopVerbs; --verbs) {
+        switch (verbs[~0]) {
+            case SkPathRef::kMove_Verb:
+                goto CONTOUR_END;
+            case SkPathRef::kLine_Verb:
+                ptCount += 1;
+                break;
+            case SkPathRef::kConic_Verb:
+                fCurrConicWeight += 1;
+                // fall-through
+            case SkPathRef::kQuad_Verb:
+                ptCount += 2;
+                break;
+            case SkPathRef::kCubic_Verb:
+                ptCount += 3;
+                break;
+            case SkPathRef::kClose_Verb:
+                break;
+            default:
+                SkDEBUGFAIL("unexpected verb");
+                break;
+        }
+    }
+CONTOUR_END:
+    fCurrPtCount = ptCount;
+    fCurrVerb = verbs;
+    SkDEBUGCODE(++fContourCounter;)
+}
+
+// returns cross product of (p1 - p0) and (p2 - p0)
+static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
+    SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0);
+    // We may get 0 when the above subtracts underflow. We expect this to be
+    // very rare and lazily promote to double.
+    if (0 == cross) {
+        double p0x = SkScalarToDouble(p0.fX);
+        double p0y = SkScalarToDouble(p0.fY);
+
+        double p1x = SkScalarToDouble(p1.fX);
+        double p1y = SkScalarToDouble(p1.fY);
+
+        double p2x = SkScalarToDouble(p2.fX);
+        double p2y = SkScalarToDouble(p2.fY);
+
+        cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) -
+                                 (p1y - p0y) * (p2x - p0x));
+
+    }
+    return cross;
+}
+
+// Returns the first pt with the maximum Y coordinate
+static int find_max_y(const SkPoint pts[], int count) {
+    SkASSERT(count > 0);
+    SkScalar max = pts[0].fY;
+    int firstIndex = 0;
+    for (int i = 1; i < count; ++i) {
+        SkScalar y = pts[i].fY;
+        if (y > max) {
+            max = y;
+            firstIndex = i;
+        }
+    }
+    return firstIndex;
+}
+
+static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) {
+    int i = index;
+    for (;;) {
+        i = (i + inc) % n;
+        if (i == index) {   // we wrapped around, so abort
+            break;
+        }
+        if (pts[index] != pts[i]) { // found a different point, success!
+            break;
+        }
+    }
+    return i;
+}
+
+/**
+ *  Starting at index, and moving forward (incrementing), find the xmin and
+ *  xmax of the contiguous points that have the same Y.
+ */
+static int find_min_max_x_at_y(const SkPoint pts[], int index, int n,
+                               int* maxIndexPtr) {
+    const SkScalar y = pts[index].fY;
+    SkScalar min = pts[index].fX;
+    SkScalar max = min;
+    int minIndex = index;
+    int maxIndex = index;
+    for (int i = index + 1; i < n; ++i) {
+        if (pts[i].fY != y) {
+            break;
+        }
+        SkScalar x = pts[i].fX;
+        if (x < min) {
+            min = x;
+            minIndex = i;
+        } else if (x > max) {
+            max = x;
+            maxIndex = i;
+        }
+    }
+    *maxIndexPtr = maxIndex;
+    return minIndex;
+}
+
+static void crossToDir(SkScalar cross, SkPathRef::Direction* dir) {
+    if (dir) {
+        *dir = cross > 0 ? SkPathRef::kCW_Direction : SkPathRef::kCCW_Direction;
+    }
+}
+
+#if 0
+#include "SkString.h"
+#include "../utils/SkParsePath.h"
+static void dumpPath(const SkPath& path) {
+    SkString str;
+    SkParsePath::ToSVGString(path, &str);
+    SkDebugf("%s\n", str.c_str());
 }
 #endif
+
+namespace {
+// for use with convex_dir_test
+double mul(double a, double b) { return a * b; }
+SkScalar mul(SkScalar a, SkScalar b) { return SkScalarMul(a, b); }
+double toDouble(SkScalar a) { return SkScalarToDouble(a); }
+SkScalar toScalar(SkScalar a) { return a; }
+
+// determines the winding direction of a convex polygon with the precision
+// of T. CAST_SCALAR casts an SkScalar to T.
+template <typename T, T (CAST_SCALAR)(SkScalar)>
+bool convex_dir_test(int n, const SkPoint pts[], SkPathRef::Direction* dir) {
+    // we find the first three points that form a non-degenerate
+    // triangle. If there are no such points then the path is
+    // degenerate. The first is always point 0. Now we find the second
+    // point.
+    int i = 0;
+    enum { kX = 0, kY = 1 };
+    T v0[2];
+    while (1) {
+        v0[kX] = CAST_SCALAR(pts[i].fX) - CAST_SCALAR(pts[0].fX);
+        v0[kY] = CAST_SCALAR(pts[i].fY) - CAST_SCALAR(pts[0].fY);
+        if (v0[kX] || v0[kY]) {
+            break;
+        }
+        if (++i == n - 1) {
+            return false;
+        }
+    }
+    // now find a third point that is not colinear with the first two
+    // points and check the orientation of the triangle (which will be
+    // the same as the orientation of the path).
+    for (++i; i < n; ++i) {
+        T v1[2];
+        v1[kX] = CAST_SCALAR(pts[i].fX) - CAST_SCALAR(pts[0].fX);
+        v1[kY] = CAST_SCALAR(pts[i].fY) - CAST_SCALAR(pts[0].fY);
+        T cross = mul(v0[kX], v1[kY]) - mul(v0[kY], v1[kX]);
+        if (0 != cross) {
+            *dir = cross > 0 ? SkPathRef::kCW_Direction : SkPathRef::kCCW_Direction;
+            return true;
+        }
+    }
+    return false;
+}
+}
+
+/*
+ *  We loop through all contours, and keep the computed cross-product of the
+ *  contour that contained the global y-max. If we just look at the first
+ *  contour, we may find one that is wound the opposite way (correctly) since
+ *  it is the interior of a hole (e.g. 'o'). Thus we must find the contour
+ *  that is outer most (or at least has the global y-max) before we can consider
+ *  its cross product.
+ */
+bool SkPathRef::cheapComputeDirection(Direction* dir) const {
+//    dumpPath(*this);
+    // don't want to pay the cost for computing this if it
+    // is unknown, so we don't call isConvex()
+
+    if (kUnknown_Direction != fDirection) {
+        *dir = static_cast<Direction>(fDirection);
+        return true;
+    }
+    const SkPathRef::Convexity conv = this->getConvexityOrUnknown();
+
+    ContourIter iter(*this);
+
+    // initialize with our logical y-min
+    SkScalar ymax = this->getBounds().fTop;
+    SkScalar ymaxCross = 0;
+
+    for (; !iter.done(); iter.next()) {
+        int n = iter.count();
+        if (n < 3) {
+            continue;
+        }
+
+        const SkPoint* pts = iter.pts();
+        SkScalar cross = 0;
+        if (SkPathRef::kConvex_Convexity == conv) {
+            // We try first at scalar precision, and then again at double
+            // precision. This is because the vectors computed between distant
+            // points may lose too much precision.
+            if (convex_dir_test<SkScalar, toScalar>(n, pts, dir)) {
+                fDirection = *dir;
+                return true;
+            }
+            if (convex_dir_test<double, toDouble>(n, pts, dir)) {
+                fDirection = *dir;
+                return true;
+            } else {
+                return false;
+            }
+        } else {
+            int index = find_max_y(pts, n);
+            if (pts[index].fY < ymax) {
+                continue;
+            }
+
+            // If there is more than 1 distinct point at the y-max, we take the
+            // x-min and x-max of them and just subtract to compute the dir.
+            if (pts[(index + 1) % n].fY == pts[index].fY) {
+                int maxIndex;
+                int minIndex = find_min_max_x_at_y(pts, index, n, &maxIndex);
+                if (minIndex == maxIndex) {
+                    goto TRY_CROSSPROD;
+                }
+                SkASSERT(pts[minIndex].fY == pts[index].fY);
+                SkASSERT(pts[maxIndex].fY == pts[index].fY);
+                SkASSERT(pts[minIndex].fX <= pts[maxIndex].fX);
+                // we just subtract the indices, and let that auto-convert to
+                // SkScalar, since we just want - or + to signal the direction.
+                cross = minIndex - maxIndex;
+            } else {
+                TRY_CROSSPROD:
+                // Find a next and prev index to use for the cross-product test,
+                // but we try to find pts that form non-zero vectors from pts[index]
+                //
+                // Its possible that we can't find two non-degenerate vectors, so
+                // we have to guard our search (e.g. all the pts could be in the
+                // same place).
+
+                // we pass n - 1 instead of -1 so we don't foul up % operator by
+                // passing it a negative LH argument.
+                int prev = find_diff_pt(pts, index, n, n - 1);
+                if (prev == index) {
+                    // completely degenerate, skip to next contour
+                    continue;
+                }
+                int next = find_diff_pt(pts, index, n, 1);
+                SkASSERT(next != index);
+                cross = cross_prod(pts[prev], pts[index], pts[next]);
+                // if we get a zero and the points are horizontal, then we look at the spread in
+                // x-direction. We really should continue to walk away from the degeneracy until
+                // there is a divergence.
+                if (0 == cross && pts[prev].fY == pts[index].fY && pts[next].fY == pts[index].fY) {
+                    // construct the subtract so we get the correct Direction below
+                    cross = pts[index].fX - pts[next].fX;
+                }
+            }
+
+            if (cross) {
+                // record our best guess so far
+                ymax = pts[index].fY;
+                ymaxCross = cross;
+            }
+        }
+    }
+    if (ymaxCross) {
+        crossToDir(ymaxCross, dir);
+        fDirection = *dir;
+        return true;
+    } else {
+        return false;
+    }
+}
+