track oval in SkPath

Committed on behalf of Guanqun.Lu@gmail.com

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



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

3 files changed, 285 insertions, 0 deletions

diff --git a/include/core/SkPath.h b/include/core/SkPath.h
index 01b5488e6d..025e7099b5 100644
--- a/include/core/SkPath.h
+++ b/include/core/SkPath.h
@@ -161,6 +161,18 @@ public:
         this->setConvexity(isConvex ? kConvex_Convexity : kConcave_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;
+
     /** Clear any lines and curves from the path, making it empty. This frees up
         internal storage associated with those segments.
         This does NOT change the fill-type setting nor isConvex
@@ -747,6 +759,8 @@ private:
     uint8_t             fSegmentMask;
     mutable uint8_t     fBoundsIsDirty;
     mutable uint8_t     fConvexity;
+
+    mutable SkBool8     fIsOval;
 #ifdef SK_BUILD_FOR_ANDROID
     uint32_t            fGenerationID;
     const SkPath*       fSourcePath;
@@ -778,7 +792,10 @@ private:
     //
     inline void injectMoveToIfNeeded();
 
+    inline bool hasOnlyMoveTos() const;
+
     friend class SkAutoPathBoundsUpdate;
+    friend class SkAutoDisableOvalCheck;
 };
 
 #endif
diff --git a/src/core/SkPath.cpp b/src/core/SkPath.cpp
index 7f58ae347e..94246201ea 100644
--- a/src/core/SkPath.cpp
+++ b/src/core/SkPath.cpp
@@ -32,6 +32,21 @@ static bool is_degenerate(const SkPath& path) {
     return SkPath::kDone_Verb == iter.next(pts);
 }
 
+class SkAutoDisableOvalCheck {
+public:
+    SkAutoDisableOvalCheck(SkPath* path) : fPath(path) {
+        fSaved = fPath->fIsOval;
+    }
+
+    ~SkAutoDisableOvalCheck() {
+        fPath->fIsOval = fSaved;
+    }
+
+private:
+    SkPath* fPath;
+    bool    fSaved;
+};
+
 /*  This guy's constructor/destructor bracket a path editing operation. It is
     used when we know the bounds of the amount we are going to add to the path
     (usually a new contour, but not required).
@@ -119,6 +134,7 @@ SkPath::SkPath()
     fConvexity = kUnknown_Convexity;
     fSegmentMask = 0;
     fLastMoveToIndex = INITIAL_LASTMOVETOINDEX_VALUE;
+    fIsOval = false;
 #ifdef SK_BUILD_FOR_ANDROID
     fGenerationID = 0;
     fSourcePath = NULL;
@@ -151,6 +167,7 @@ SkPath& SkPath::operator=(const SkPath& src) {
         fConvexity      = src.fConvexity;
         fSegmentMask    = src.fSegmentMask;
         fLastMoveToIndex = src.fLastMoveToIndex;
+        fIsOval         = src.fIsOval;
         GEN_ID_INC;
     }
     SkDEBUGCODE(this->validate();)
@@ -182,6 +199,7 @@ void SkPath::swap(SkPath& other) {
         SkTSwap<uint8_t>(fConvexity, other.fConvexity);
         SkTSwap<uint8_t>(fSegmentMask, other.fSegmentMask);
         SkTSwap<int>(fLastMoveToIndex, other.fLastMoveToIndex);
+        SkTSwap<SkBool8>(fIsOval, other.fIsOval);
         GEN_ID_INC;
     }
 }
@@ -210,6 +228,7 @@ void SkPath::reset() {
     fConvexity = kUnknown_Convexity;
     fSegmentMask = 0;
     fLastMoveToIndex = INITIAL_LASTMOVETOINDEX_VALUE;
+    fIsOval = false;
 }
 
 void SkPath::rewind() {
@@ -222,6 +241,7 @@ void SkPath::rewind() {
     fBoundsIsDirty = true;
     fSegmentMask = 0;
     fLastMoveToIndex = INITIAL_LASTMOVETOINDEX_VALUE;
+    fIsOval = false;
 }
 
 bool SkPath::isEmpty() const {
@@ -388,6 +408,7 @@ void SkPath::setLastPt(SkScalar x, SkScalar y) {
     if (count == 0) {
         this->moveTo(x, y);
     } else {
+        fIsOval = false;
         fPts[count - 1].set(x, y);
         GEN_ID_INC;
     }
@@ -415,6 +436,7 @@ void SkPath::setConvexity(Convexity c) {
     do {                                 \
         fBoundsIsDirty = true;           \
         fConvexity = kUnknown_Convexity; \
+        fIsOval = false;                 \
     } while (0)
 
 #define DIRTY_AFTER_EDIT_NO_CONVEXITY_CHANGE    \
@@ -729,7 +751,31 @@ void SkPath::addRoundRect(const SkRect& rect, const SkScalar rad[],
     this->close();
 }
 
+bool SkPath::hasOnlyMoveTos() const {
+    const uint8_t* verbs = fVerbs.begin();
+    const uint8_t* verbStop = fVerbs.end();
+    while (verbs != verbStop) {
+        if (*verbs == kLine_Verb ||
+            *verbs == kQuad_Verb ||
+            *verbs == kCubic_Verb) {
+            return false;
+        }
+        ++verbs;
+    }
+    return true;
+}
+
 void SkPath::addOval(const SkRect& oval, Direction dir) {
+    /* If addOval() is called after previous moveTo(),
+       this path is still marked as an oval. This is used to
+       fit into WebKit's calling sequences.
+       We can't simply check isEmpty() in this case, as additional
+       moveTo() would mark the path non empty.
+     */
+    fIsOval = hasOnlyMoveTos();
+
+    SkAutoDisableOvalCheck adoc(this);
+
     SkAutoPathBoundsUpdate apbu(this, oval);
 
     SkScalar    cx = oval.centerX();
@@ -795,6 +841,17 @@ void SkPath::addOval(const SkRect& oval, Direction dir) {
     this->close();
 }
 
+bool SkPath::isOval(SkRect* rect) const {
+    if (isEmpty() || !fIsOval) {
+        return false;
+    }
+
+    if (rect) {
+        *rect = getBounds();
+    }
+    return true;
+}
+
 void SkPath::addCircle(SkScalar x, SkScalar y, SkScalar r, Direction dir) {
     if (r > 0) {
         SkRect  rect;
@@ -970,6 +1027,8 @@ void SkPath::addPath(const SkPath& path, SkScalar dx, SkScalar dy) {
 void SkPath::addPath(const SkPath& path, const SkMatrix& matrix) {
     this->incReserve(path.fPts.count());
 
+    fIsOval = false;
+
     RawIter iter(path);
     SkPoint pts[4];
     Verb    verb;
@@ -1023,6 +1082,8 @@ void SkPath::pathTo(const SkPath& path) {
 
     this->incReserve(vcount);
 
+    fIsOval = false;
+
     const uint8_t*  verbs = path.fVerbs.begin();
     const SkPoint*  pts = path.fPts.begin() + 1;    // 1 for the initial moveTo
 
@@ -1055,6 +1116,8 @@ void SkPath::reversePathTo(const SkPath& path) {
 
     this->incReserve(vcount);
 
+    fIsOval = false;
+
     const uint8_t*  verbs = path.fVerbs.begin();
     const SkPoint*  pts = path.fPts.begin();
 
@@ -1095,6 +1158,8 @@ void SkPath::reverseAddPath(const SkPath& src) {
     const uint8_t* startVerbs = src.fVerbs.begin();
     const uint8_t* verbs = src.fVerbs.end();
 
+    fIsOval = false;
+
     bool needMove = true;
     bool needClose = false;
     while (verbs > startVerbs) {
@@ -1228,8 +1293,19 @@ void SkPath::transform(const SkMatrix& matrix, SkPath* dst) const {
             dst->fFillType = fFillType;
             dst->fSegmentMask = fSegmentMask;
             dst->fConvexity = fConvexity;
+            dst->fIsOval = fIsOval;
         }
+
         matrix.mapPoints(dst->fPts.begin(), fPts.begin(), fPts.count());
+
+        // isOval() must be called after dst->fPts are changed.
+        // otherwise, isOval() would call validate() implicitly and
+        // at that time it finds its control points are not bound by fBounds.
+        if (this->isOval(NULL)) {
+            // It's an oval only if it stays a rect.
+            dst->fIsOval = matrix.rectStaysRect();
+        }
+
         SkDEBUGCODE(dst->validate();)
     }
 }
diff --git a/tests/PathTest.cpp b/tests/PathTest.cpp
index d88454795f..c3f4a4f509 100644
--- a/tests/PathTest.cpp
+++ b/tests/PathTest.cpp
@@ -1053,6 +1053,196 @@ static void test_raw_iter(skiatest::Reporter* reporter) {
     }
 }
 
+static void check_for_circle(skiatest::Reporter* reporter,
+                             const SkPath& path, bool expected) {
+    SkRect rect;
+    REPORTER_ASSERT(reporter, path.isOval(&rect) == expected);
+    if (expected) {
+        REPORTER_ASSERT(reporter, rect.height() == rect.width());
+    }
+}
+
+static void test_circle_skew(skiatest::Reporter* reporter,
+                             const SkPath& path) {
+    SkPath tmp;
+
+    SkMatrix m;
+    m.setSkew(SkIntToScalar(3), SkIntToScalar(5));
+    path.transform(m, &tmp);
+    check_for_circle(reporter, tmp, false);
+}
+
+static void test_circle_translate(skiatest::Reporter* reporter,
+                                  const SkPath& path) {
+    SkPath tmp;
+
+    // translate at small offset
+    SkMatrix m;
+    m.setTranslate(SkIntToScalar(15), SkIntToScalar(15));
+    path.transform(m, &tmp);
+    check_for_circle(reporter, tmp, true);
+
+    tmp.reset();
+    m.reset();
+
+    // translate at a relatively big offset
+    m.setTranslate(SkIntToScalar(1000), SkIntToScalar(1000));
+    path.transform(m, &tmp);
+    check_for_circle(reporter, tmp, true);
+}
+
+static void test_circle_rotate(skiatest::Reporter* reporter,
+                               const SkPath& path) {
+    for (int angle = 0; angle < 360; ++angle) {
+        SkPath tmp;
+        SkMatrix m;
+        m.setRotate(SkIntToScalar(angle));
+        path.transform(m, &tmp);
+
+        // TODO: a rotated circle whose rotated angle is not a mutiple of 90
+        // degrees is not an oval anymore, this can be improved.  we made this
+        // for the simplicity of our implementation.
+        if (angle % 90 == 0) {
+            check_for_circle(reporter, tmp, true);
+        } else {
+            check_for_circle(reporter, tmp, false);
+        }
+    }
+}
+
+static void test_circle_with_direction(skiatest::Reporter* reporter,
+                                       SkPath::Direction dir) {
+    SkPath path;
+
+    // circle at origin
+    path.addCircle(0, 0, SkIntToScalar(20), dir);
+    check_for_circle(reporter, path, true);
+    test_circle_rotate(reporter, path);
+    test_circle_translate(reporter, path);
+    test_circle_skew(reporter, path);
+
+    // circle at an offset at (10, 10)
+    path.reset();
+    path.addCircle(SkIntToScalar(10), SkIntToScalar(10),
+                   SkIntToScalar(20), dir);
+    check_for_circle(reporter, path, true);
+    test_circle_rotate(reporter, path);
+    test_circle_translate(reporter, path);
+    test_circle_skew(reporter, path);
+}
+
+static void test_circle_with_add_paths(skiatest::Reporter* reporter) {
+    SkPath path;
+    SkPath circle;
+    SkPath rect;
+    SkPath empty;
+
+    circle.addCircle(0, 0, SkIntToScalar(10), SkPath::kCW_Direction);
+    rect.addRect(SkIntToScalar(5), SkIntToScalar(5),
+                 SkIntToScalar(20), SkIntToScalar(20), SkPath::kCW_Direction);
+
+    SkMatrix translate;
+    translate.setTranslate(SkIntToScalar(12), SkIntToScalar(12));
+
+    // For simplicity, all the path concatenation related operations
+    // would mark it non-circle, though in theory it's still a circle.
+
+    // empty + circle (translate)
+    path = empty;
+    path.addPath(circle, translate);
+    check_for_circle(reporter, path, false);
+
+    // circle + empty (translate)
+    path = circle;
+    path.addPath(empty, translate);
+    check_for_circle(reporter, path, false);
+
+    // test reverseAddPath
+    path = circle;
+    path.reverseAddPath(rect);
+    check_for_circle(reporter, path, false);
+}
+
+static void test_circle(skiatest::Reporter* reporter) {
+    test_circle_with_direction(reporter, SkPath::kCW_Direction);
+    test_circle_with_direction(reporter, SkPath::kCCW_Direction);
+
+    // multiple addCircle()
+    SkPath path;
+    path.addCircle(0, 0, SkIntToScalar(10), SkPath::kCW_Direction);
+    path.addCircle(0, 0, SkIntToScalar(20), SkPath::kCW_Direction);
+    check_for_circle(reporter, path, false);
+
+    // some extra lineTo() would make isOval() fail
+    path.reset();
+    path.addCircle(0, 0, SkIntToScalar(10), SkPath::kCW_Direction);
+    path.lineTo(0, 0);
+    check_for_circle(reporter, path, false);
+
+    // not back to the original point
+    path.reset();
+    path.addCircle(0, 0, SkIntToScalar(10), SkPath::kCW_Direction);
+    path.setLastPt(SkIntToScalar(5), SkIntToScalar(5));
+    check_for_circle(reporter, path, false);
+
+    test_circle_with_add_paths(reporter);
+}
+
+static void test_oval(skiatest::Reporter* reporter) {
+    SkRect rect;
+    SkMatrix m;
+    SkPath path;
+
+    rect = SkRect::MakeWH(SkIntToScalar(30), SkIntToScalar(50));
+    path.addOval(rect);
+
+    REPORTER_ASSERT(reporter, path.isOval(NULL));
+
+    m.setRotate(90);
+    SkPath tmp;
+    path.transform(m, &tmp);
+    // an oval rotated 90 degrees is still an oval.
+    REPORTER_ASSERT(reporter, tmp.isOval(NULL));
+
+    m.reset();
+    m.setRotate(30);
+    tmp.reset();
+    path.transform(m, &tmp);
+    // an oval rotated 30 degrees is not an oval anymore.
+    REPORTER_ASSERT(reporter, !tmp.isOval(NULL));
+
+    // since empty path being transformed.
+    path.reset();
+    tmp.reset();
+    m.reset();
+    path.transform(m, &tmp);
+    REPORTER_ASSERT(reporter, !tmp.isOval(NULL));
+
+    // empty path is not an oval
+    tmp.reset();
+    REPORTER_ASSERT(reporter, !tmp.isOval(NULL));
+
+    // only has moveTo()s
+    tmp.reset();
+    tmp.moveTo(0, 0);
+    tmp.moveTo(SkIntToScalar(10), SkIntToScalar(10));
+    REPORTER_ASSERT(reporter, !tmp.isOval(NULL));
+
+    // mimic WebKit's calling convention,
+    // call moveTo() first and then call addOval()
+    path.reset();
+    path.moveTo(0, 0);
+    path.addOval(rect);
+    REPORTER_ASSERT(reporter, path.isOval(NULL));
+
+    // copy path
+    path.reset();
+    tmp.reset();
+    tmp.addOval(rect);
+    path = tmp;
+    REPORTER_ASSERT(reporter, path.isOval(NULL));
+}
+
 void TestPath(skiatest::Reporter* reporter) {
     {
         SkSize size;
@@ -1138,6 +1328,8 @@ void TestPath(skiatest::Reporter* reporter) {
     test_bounds(reporter);
     test_iter(reporter);
     test_raw_iter(reporter);
+    test_circle(reporter);
+    test_oval(reporter);
 }
 
 #include "TestClassDef.h"