Fixups for clipstack, convexity test for paths.

Review URL http://codereview.appspot.com/4250056/

git-svn-id: http://skia.googlecode.com/svn/trunk@891 2bbb7eff-a529-9590-31e7-b0007b416f81

1 files changed, 326 insertions, 49 deletions

diff --git a/gpu/src/GrPath.cpp b/gpu/src/GrPath.cpp
index ca5c43baa2..fc53ac2335 100644
--- a/gpu/src/GrPath.cpp
+++ b/gpu/src/GrPath.cpp
@@ -1,6 +1,8 @@
 #include "GrPath.h"
 
-GrPath::GrPath() {}
+GrPath::GrPath() {
+    fConvexHint = kNone_ConvexHint;
+}
 
 GrPath::GrPath(const GrPath& src) : INHERITED() {
     GrPath::Iter iter(src);
@@ -15,13 +17,13 @@ GrPath::~GrPath() {
 }
 
 bool GrPath::operator ==(const GrPath& path) const {
-    if (fVerbs.count() != path.fVerbs.count() ||
+    if (fCmds.count() != path.fCmds.count() ||
         fPts.count() != path.fPts.count()) {
         return false;
     }
 
-    for (int v = 0; v < fVerbs.count(); ++v) {
-        if (fVerbs[v] != path.fVerbs[v]) {
+    for (int v = 0; v < fCmds.count(); ++v) {
+        if (fCmds[v] != path.fCmds[v]) {
             return false;
         }
     }
@@ -35,31 +37,31 @@ bool GrPath::operator ==(const GrPath& path) const {
 }
 
 void GrPath::ensureMoveTo() {
-    if (fVerbs.isEmpty() || this->wasLastVerb(kClose)) {
-        *fVerbs.append() = kMove;
+    if (fCmds.isEmpty() || this->wasLastVerb(kClose_PathCmd)) {
+        *fCmds.append() = kMove_PathCmd;
         fPts.append()->set(0, 0);
     }
 }
 
 void GrPath::moveTo(GrScalar x, GrScalar y) {
-    if (this->wasLastVerb(kMove)) {
+    if (this->wasLastVerb(kMove_PathCmd)) {
         // overwrite prev kMove value
         fPts[fPts.count() - 1].set(x, y);
     } else {
-        *fVerbs.append() = kMove;
+        *fCmds.append() = kMove_PathCmd;
         fPts.append()->set(x, y);
     }
 }
 
 void GrPath::lineTo(GrScalar x, GrScalar y) {
     this->ensureMoveTo();
-    *fVerbs.append() = kLine;
+    *fCmds.append() = kLine_PathCmd;
     fPts.append()->set(x, y);
 }
 
 void GrPath::quadTo(GrScalar x0, GrScalar y0, GrScalar x1, GrScalar y1) {
     this->ensureMoveTo();
-    *fVerbs.append() = kQuad;
+    *fCmds.append() = kQuadratic_PathCmd;
     fPts.append()->set(x0, y0);
     fPts.append()->set(x1, y1);
 }
@@ -67,100 +69,371 @@ void GrPath::quadTo(GrScalar x0, GrScalar y0, GrScalar x1, GrScalar y1) {
 void GrPath::cubicTo(GrScalar x0, GrScalar y0, GrScalar x1, GrScalar y1,
                      GrScalar x2, GrScalar y2) {
     this->ensureMoveTo();
-    *fVerbs.append() = kCubic;
+    *fCmds.append() = kCubic_PathCmd;
     fPts.append()->set(x0, y0);
     fPts.append()->set(x1, y1);
     fPts.append()->set(x2, y2);
 }
 
 void GrPath::close() {
-    if (!fVerbs.isEmpty() && !this->wasLastVerb(kClose)) {
+    if (!fCmds.isEmpty() && !this->wasLastVerb(kClose_PathCmd)) {
         // should we allow kMove followed by kClose?
-        *fVerbs.append() = kClose;
+        *fCmds.append() = kClose_PathCmd;
     }
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 
+static bool check_two_vecs(const GrVec& prevVec,
+                           const GrVec& currVec,
+                           GrScalar turnDir,
+                           int* xDir,
+                           int* yDir,
+                           int* flipX, 
+                           int* flipY) {
+    if (currVec.fX * *xDir < 0) {
+        ++*flipX;
+        if (*flipX > 2) {
+            return false;
+        }
+        *xDir = -*xDir;
+    }
+    if (currVec.fY * *yDir < 0) {
+        ++*flipY;
+        if (*flipY > 2) {
+            return false;
+        }
+        *yDir = -*yDir;
+    }
+    GrScalar d = prevVec.cross(currVec);
+    return (d * turnDir) >= 0;
+}
+
+static void init_from_two_vecs(const GrVec& firstVec,
+                               const GrVec& secondVec,
+                               GrScalar* turnDir,
+                               int* xDir, int* yDir) {
+    *turnDir = firstVec.cross(secondVec);
+    if (firstVec.fX > 0) {
+        *xDir = 1;
+    } else if (firstVec.fX < 0) {
+        *xDir = -1;
+    } else {
+        *xDir = 0;
+    }
+    if (firstVec.fY > 0) {
+        *yDir = 1;
+    } else if (firstVec.fY < 0) {
+        *yDir = -1;
+    } else {
+        *yDir = 0;
+    }
+}
+
 void GrPath::resetFromIter(GrPathIter* iter) {
     fPts.reset();
-    fVerbs.reset();
+    fCmds.reset();
 
-    GrPoint pts[4];
-    GrPathIter::Command cmd;
+    fConvexHint = iter->convexHint();
+
+    // first point of the subpath
+    GrPoint firstPt;
+    // first edge of the subpath
+    GrVec firstVec;
+    // vec of most recently processed edge, that wasn't degenerate
+    GrVec previousVec;
+    // most recently processed point
+    GrPoint previousPt;
+
+    // sign indicates whether we're bending left or right
+    GrScalar turnDir;
+    // number of times the direction has flipped in x or y
 
-    while ((cmd = iter->next(pts)) != GrPathIter::kEnd_Command) {
+    // we track which direction we are moving in x/y and the
+    // number of times it changes.
+    int xDir;
+    int yDir;
+    int flipX;
+    int flipY;
+
+    // counts number of sub path pts that didn't add a degenerate edge.
+    int subPathPts = 0;
+
+    int numSubPaths = 0;
+    iter->rewind();
+    GrPathCmd cmd;
+    GrPoint pts[4];
+    bool subPathClosed;
+    do {
+        cmd = iter->next(pts);
+        // If the convexity test is ever updated to handle multiple subpaths
+        // the loop has to be adjusted to handle moving to a new subpath without
+        // closing the previous one. Currently the implicit closing vectors for a
+        // filled path would never be examined.
         switch (cmd) {
-            case GrPathIter::kMove_Command:
+            case kMove_PathCmd:
                 this->moveTo(pts[0].fX, pts[0].fY);
+                subPathPts = 0;
+                subPathClosed = false;
                 break;
-            case GrPathIter::kLine_Command:
+            case kLine_PathCmd:
                 this->lineTo(pts[1].fX, pts[1].fY);
                 break;
-            case GrPathIter::kQuadratic_Command:
+            case kQuadratic_PathCmd:
                 this->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
                 break;
-            case GrPathIter::kCubic_Command:
+            case kCubic_PathCmd:
                 this->cubicTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY,
                               pts[3].fX, pts[3].fY);
                 break;
-            case GrPathIter::kClose_Command:
+            case kClose_PathCmd:
                 this->close();
+                subPathClosed = true;
                 break;
-            case GrPathIter::kEnd_Command:
-                // never get here, but include it to avoid the warning
+            case kEnd_PathCmd:
                 break;
         }
+        int n = NumPathCmdPoints(cmd);
+        if (0 == subPathPts && n > 0) {
+            previousPt = pts[0];
+            firstPt = previousPt;
+            flipX = 0;
+            flipY = 0;
+            turnDir = 0;
+            subPathPts = 1;
+            ++numSubPaths;
+        }
+        // either we skip the first pt because it is redundant with
+        // last point of the previous subpath cmd or we just ate it
+        // in the above if.
+        int consumed = 1;
+        if (numSubPaths < 2 && kNone_ConvexHint == fConvexHint) {
+            while (consumed < n) {
+                GrAssert(pts[consumed-1] == previousPt);
+                GrVec vec;
+                vec.setBetween(previousPt, pts[consumed]);
+                if (vec.fX || vec.fY) {
+                    if (subPathPts >= 2) {
+                        if (0 == turnDir) { 
+                            firstVec = previousVec;
+                            init_from_two_vecs(firstVec, vec, 
+                                               &turnDir, &xDir, &yDir);
+                            // here we aren't checking whether the x/y dirs
+                            // change between the first and second edge. It
+                            // gets covered when the path is closed.
+                        } else {
+                            if (!check_two_vecs(previousVec, vec, turnDir,
+                                                &xDir, &yDir,
+                                                &flipX, &flipY)) {
+                                fConvexHint = kConcave_ConvexHint;
+                                break;
+                            }
+                        }
+                    }
+                    previousVec = vec;
+                    previousPt = pts[consumed];
+                    ++subPathPts;
+                }
+                ++consumed;
+            }
+            if (subPathPts > 2 && (kClose_PathCmd == cmd || 
+                        (!subPathClosed && kEnd_PathCmd == cmd ))) {
+                // if an additional vector is needed to close the loop check
+                // that it validates against the previous vector.
+                GrVec vec;
+                vec.setBetween(previousPt, firstPt);
+                if (vec.fX || vec.fY) {
+                    if (!check_two_vecs(previousVec, vec, turnDir, 
+                                        &xDir, &yDir, &flipX, &flipY)) {
+                        fConvexHint = kConcave_ConvexHint;
+                        break;
+                    }
+                    previousVec = vec;
+                }
+                // check that closing vector validates against the first vector.
+                if (!check_two_vecs(previousVec, firstVec, turnDir, 
+                                    &xDir, &yDir, &flipX, &flipY)) {
+                    fConvexHint = kConcave_ConvexHint;
+                    break;
+                }
+            }
+        }
+    } while (cmd != kEnd_PathCmd);
+    if (kNone_ConvexHint == fConvexHint && numSubPaths < 2) {
+        fConvexHint = kConvex_ConvexHint;
+    } else {
+        bool recurse = false;
+        if (recurse) {
+            this->resetFromIter(iter);
+        }
     }
-    fConvexHint = iter->convexHint();
 }
 
+void GrPath::ConvexUnitTest() {
+    GrPath testPath;
+    GrPath::Iter testIter;
+
+    GrPath pt;
+    pt.moveTo(0, 0);
+    pt.close();
+
+    testIter.reset(pt);
+    testPath.resetFromIter(&testIter);
+    GrAssert(kConvex_ConvexHint == testPath.getConvexHint());
+
+    GrPath line;
+    line.moveTo(GrIntToScalar(12), GrIntToScalar(20));
+    line.lineTo(GrIntToScalar(-12), GrIntToScalar(-20));
+    line.close();
+
+    testIter.reset(line);
+    testPath.resetFromIter(&testIter);
+    GrAssert(kConvex_ConvexHint == testPath.getConvexHint());
+
+    GrPath triLeft;
+    triLeft.moveTo(0, 0);
+    triLeft.lineTo(1, 0);
+    triLeft.lineTo(1, 1);
+    triLeft.close();
+
+    testIter.reset(triLeft);
+    testPath.resetFromIter(&testIter);
+    GrAssert(kConvex_ConvexHint == testPath.getConvexHint());
+
+    GrPath triRight;
+    triRight.moveTo(0, 0);
+    triRight.lineTo(-1, 0);
+    triRight.lineTo(1, 1);
+    triRight.close();
+
+    testIter.reset(triRight);
+    testPath.resetFromIter(&testIter);
+    GrAssert(kConvex_ConvexHint == testPath.getConvexHint());
+    
+    GrPath square;
+    square.moveTo(0, 0);
+    square.lineTo(1, 0);
+    square.lineTo(1, 1);
+    square.lineTo(0, 1);
+    square.close();
+
+    testIter.reset(square);
+    testPath.resetFromIter(&testIter);
+    GrAssert(kConvex_ConvexHint == testPath.getConvexHint());
+
+    GrPath redundantSquare;
+    square.moveTo(0, 0);
+    square.lineTo(0, 0);
+    square.lineTo(0, 0);
+    square.lineTo(1, 0);
+    square.lineTo(1, 0);
+    square.lineTo(1, 0);
+    square.lineTo(1, 1);
+    square.lineTo(1, 1);
+    square.lineTo(1, 1);
+    square.lineTo(0, 1);
+    square.lineTo(0, 1);
+    square.lineTo(0, 1);
+    square.close();
+    
+    testIter.reset(redundantSquare);
+    testPath.resetFromIter(&testIter);
+    GrAssert(kConvex_ConvexHint == testPath.getConvexHint());
+
+    GrPath bowTie;
+    bowTie.moveTo(0, 0);
+    bowTie.lineTo(0, 0);
+    bowTie.lineTo(0, 0);
+    bowTie.lineTo(1, 1);
+    bowTie.lineTo(1, 1);
+    bowTie.lineTo(1, 1);
+    bowTie.lineTo(1, 0);
+    bowTie.lineTo(1, 0);
+    bowTie.lineTo(1, 0);
+    bowTie.lineTo(0, 1);
+    bowTie.lineTo(0, 1);
+    bowTie.lineTo(0, 1);
+    bowTie.close();
+    
+    testIter.reset(bowTie);
+    testPath.resetFromIter(&testIter);
+    GrAssert(kConcave_ConvexHint == testPath.getConvexHint());
+
+    GrPath spiral;
+    spiral.moveTo(0, 0);
+    spiral.lineTo(1, 0);
+    spiral.lineTo(1, 1);
+    spiral.lineTo(0, 1);
+    spiral.lineTo(0,.5);
+    spiral.lineTo(.5,.5);
+    spiral.lineTo(.5,.75);
+    spiral.close();
+
+    testIter.reset(spiral);
+    testPath.resetFromIter(&testIter);
+    GrAssert(kConcave_ConvexHint == testPath.getConvexHint());
+
+    GrPath dent;
+    dent.moveTo(0, 0);
+    dent.lineTo(1, 1);
+    dent.lineTo(0, 1);
+    dent.lineTo(-.5,2);
+    dent.lineTo(-2, 1);
+    dent.close();
+
+    testIter.reset(dent);
+    testPath.resetFromIter(&testIter);
+    GrAssert(kConcave_ConvexHint == testPath.getConvexHint());
+}
 ///////////////////////////////////////////////////////////////////////////////
 
-GrPath::Iter::Iter(const GrPath& path) : fPath(path) {
+GrPath::Iter::Iter() : fPath(NULL) {
+}
+
+GrPath::Iter::Iter(const GrPath& path) : fPath(&path) {
     this->rewind();
 }
 
-GrPathIter::Command GrPath::Iter::next(GrPoint points[]) {
-    if (fVerbIndex == fPath.fVerbs.count()) {
-        GrAssert(fPtIndex == fPath.fPts.count());
-        return GrPathIter::kEnd_Command;
+GrPathCmd GrPath::Iter::next(GrPoint points[]) {
+    if (fCmdIndex == fPath->fCmds.count()) {
+        GrAssert(fPtIndex == fPath->fPts.count());
+        return kEnd_PathCmd;
     } else {
-        GrAssert(fVerbIndex < fPath.fVerbs.count());
+        GrAssert(fCmdIndex < fPath->fCmds.count());
     }
 
-    uint8_t cmd = fPath.fVerbs[fVerbIndex++];
-    const GrPoint* srcPts = fPath.fPts.begin() + fPtIndex;
+    GrPathCmd cmd = fPath->fCmds[fCmdIndex++];
+    const GrPoint* srcPts = fPath->fPts.begin() + fPtIndex;
 
     switch (cmd) {
-        case kMove:
+        case kMove_PathCmd:
             if (points) {
                 points[0] = srcPts[0];
             }
             fLastPt = srcPts[0];
-            GrAssert(fPtIndex <= fPath.fPts.count() + 1);
+            GrAssert(fPtIndex <= fPath->fPts.count() + 1);
             fPtIndex += 1;
             break;
-        case kLine:
+        case kLine_PathCmd:
             if (points) {
                 points[0] = fLastPt;
                 points[1] = srcPts[0];
             }
             fLastPt = srcPts[0];
-            GrAssert(fPtIndex <= fPath.fPts.count() + 1);
+            GrAssert(fPtIndex <= fPath->fPts.count() + 1);
             fPtIndex += 1;
             break;
-        case kQuad:
+        case kQuadratic_PathCmd:
             if (points) {
                 points[0] = fLastPt;
                 points[1] = srcPts[0];
                 points[2] = srcPts[1];
             }
-            fLastPt = srcPts[2];
-            GrAssert(fPtIndex <= fPath.fPts.count() + 2);
+            fLastPt = srcPts[1];
+            GrAssert(fPtIndex <= fPath->fPts.count() + 2);
             fPtIndex += 2;
             break;
-        case kCubic:
+        case kCubic_PathCmd:
             if (points) {
                 points[0] = fLastPt;
                 points[1] = srcPts[0];
@@ -168,29 +441,33 @@ GrPathIter::Command GrPath::Iter::next(GrPoint points[]) {
                 points[3] = srcPts[2];
             }
             fLastPt = srcPts[2];
-            GrAssert(fPtIndex <= fPath.fPts.count() + 3);
+            GrAssert(fPtIndex <= fPath->fPts.count() + 3);
             fPtIndex += 3;
             break;
-        case kClose:
+        case kClose_PathCmd:
             break;
         default:
-            GrAssert(!"unknown grpath verb");
+            GrAssert(!"unknown grpath cmd");
             break;
     }
-    return (GrPathIter::Command)cmd;
+    return cmd;
 }
 
-GrPathIter::ConvexHint GrPath::Iter::convexHint() const {
-    return fPath.getConvexHint();
+GrConvexHint GrPath::Iter::convexHint() const {
+    return fPath->getConvexHint();
 }
 
-GrPathIter::Command GrPath::Iter::next() {
+GrPathCmd GrPath::Iter::next() {
     return this->next(NULL);
 }
 
 void GrPath::Iter::rewind() {
-    fVerbIndex = fPtIndex = 0;
+    this->reset(*fPath);
 }
 
+void GrPath::Iter::reset(const GrPath& path) {
+    fPath = &path;
+    fCmdIndex = fPtIndex = 0;
+}