Consolidate ambient and spot code setup.

Uses shared code to create a polygon version of the path, as well as
computing the centroid and determining convexity. This makes things
more consistent and sets up for creating concave ambient shadows.

Bug: skia:7971
Change-Id: I3f36a423431361177ad9f53218b3ff0fdaa179e1
Reviewed-on: https://skia-review.googlesource.com/131585
Commit-Queue: Jim Van Verth <jvanverth@google.com>
Reviewed-by: Brian Salomon <bsalomon@google.com>

1 files changed, 165 insertions, 143 deletions

diff --git a/src/utils/SkShadowTessellator.cpp b/src/utils/SkShadowTessellator.cpp
index c07311c43d..61b1e97062 100755
--- a/src/utils/SkShadowTessellator.cpp
+++ b/src/utils/SkShadowTessellator.cpp
@@ -45,7 +45,11 @@ protected:
 
     bool setZOffset(const SkRect& bounds, bool perspective);
 
-    virtual void handleLine(const SkPoint& p) = 0;
+    bool accumulateCentroid(const SkPoint& c, const SkPoint& n);
+    bool checkConvexity(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2);
+    void finishPathPolygon();
+
+    void handleLine(const SkPoint& p);
     void handleLine(const SkMatrix& m, SkPoint* p);
 
     void handleQuad(const SkPoint pts[3]);
@@ -82,6 +86,13 @@ protected:
     SkTDArray<SkColor>  fColors;
     SkTDArray<uint16_t> fIndices;
 
+    SkTDArray<SkPoint>  fPathPolygon;
+    SkPoint             fCentroid;
+    SkScalar            fArea;
+    SkScalar            fLastArea;
+    int                 fAreaSignFlips;
+    SkScalar            fLastCross;
+
     int                 fFirstVertexIndex;
     SkVector            fFirstOutset;
     SkPoint             fFirstPoint;
@@ -143,9 +154,15 @@ static SkScalar perp_dot(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2
     return v0.cross(v1);
 }
 
+
 SkBaseShadowTessellator::SkBaseShadowTessellator(const SkPoint3& zPlaneParams, bool transparent)
         : fZPlaneParams(zPlaneParams)
         , fZOffset(0)
+        , fCentroid({0, 0})
+        , fArea(0)
+        , fLastArea(0)
+        , fAreaSignFlips(0)
+        , fLastCross(0)
         , fFirstVertexIndex(-1)
         , fSucceeded(false)
         , fTransparent(transparent)
@@ -182,6 +199,71 @@ bool SkBaseShadowTessellator::setZOffset(const SkRect& bounds, bool perspective)
     return false;
 }
 
+bool SkBaseShadowTessellator::accumulateCentroid(const SkPoint& curr, const SkPoint& next) {
+    if (duplicate_pt(curr, next)) {
+        return false;
+    }
+
+    SkScalar quadArea = curr.cross(next);
+    fCentroid.fX += (curr.fX + next.fX) * quadArea;
+    fCentroid.fY += (curr.fY + next.fY) * quadArea;
+    fArea += quadArea;
+    // convexity check
+    if (!SkScalarNearlyZero(quadArea)) {
+        if (quadArea*fLastArea < 0) {
+            ++fAreaSignFlips;
+        }
+        fLastArea = quadArea;
+    }
+
+    return true;
+}
+
+bool SkBaseShadowTessellator::checkConvexity(const SkPoint& p0,
+                                             const SkPoint& p1,
+                                             const SkPoint& p2) {
+    SkScalar cross = perp_dot(p0, p1, p2);
+    // skip collinear point
+    if (SkScalarNearlyZero(cross)) {
+        return false;
+    }
+
+    // check for convexity
+    if (fLastCross*cross < 0) {
+        fIsConvex = false;
+    }
+    fLastCross = cross;
+
+    return true;
+}
+
+void SkBaseShadowTessellator::finishPathPolygon() {
+    if (fPathPolygon.count() > 1) {
+        if (!this->accumulateCentroid(fPathPolygon[fPathPolygon.count() - 1], fPathPolygon[0])) {
+            // remove coincident point
+            fPathPolygon.pop();
+        }
+    }
+
+    if (fPathPolygon.count() > 2) {
+        if (!checkConvexity(fPathPolygon[fPathPolygon.count() - 2],
+                            fPathPolygon[fPathPolygon.count() - 1],
+                            fPathPolygon[0])) {
+            // remove collinear point
+            fPathPolygon[0] = fPathPolygon[fPathPolygon.count() - 1];
+            fPathPolygon.pop();
+        }
+    }
+
+    fCentroid *= sk_ieee_float_divide(1, 3 * fArea);
+    // It's possible to have a concave path that self-intersects but also passes the
+    // cross-product check (e.g., a star). In that case, the signed area will change signs more
+    // than twice, so we check for that here.
+    if (fAreaSignFlips > 2) {
+        fIsConvex = false;
+    }
+}
+
 // tesselation tolerance values, in device space pixels
 #if SK_SUPPORT_GPU
 static const SkScalar kQuadTolerance = 0.2f;
@@ -189,8 +271,29 @@ static const SkScalar kCubicTolerance = 0.2f;
 #endif
 static const SkScalar kConicTolerance = 0.5f;
 
+void SkBaseShadowTessellator::handleLine(const SkPoint& p) {
+    if (fPathPolygon.count() > 0) {
+        if (!this->accumulateCentroid(fPathPolygon[fPathPolygon.count() - 1], p)) {
+            // skip coincident point
+            return;
+        }
+    }
+
+    if (fPathPolygon.count() > 1) {
+        if (!checkConvexity(fPathPolygon[fPathPolygon.count() - 2],
+                            fPathPolygon[fPathPolygon.count() - 1],
+                            p)) {
+            // remove collinear point
+            fPathPolygon.pop();
+        }
+    }
+
+    *fPathPolygon.push() = p;
+}
+
 void SkBaseShadowTessellator::handleLine(const SkMatrix& m, SkPoint* p) {
     m.mapPoints(p, 1);
+
     this->handleLine(*p);
 }
 
@@ -386,7 +489,8 @@ public:
                                const SkPoint3& zPlaneParams, bool transparent);
 
 private:
-    void handleLine(const SkPoint& p) override;
+    void computePathPolygon(const SkPath& path, const SkMatrix& ctm);
+    void handlePolyPoint(const SkPoint& p);
     void addEdge(const SkVector& nextPoint, const SkVector& nextNormal);
 
     static constexpr auto kMaxEdgeLenSqr = 20 * 20;
@@ -400,7 +504,6 @@ private:
         return SkColorSetARGB(umbraAlpha * 255.9999f, 0, 0, 0);
     }
 
-    int                 fCentroidCount;
     bool                fSplitFirstEdge;
     bool                fSplitPreviousEdge;
 
@@ -438,48 +541,26 @@ SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path,
     // Middle ring: 0
     fIndices.setReserve(12 * path.countPoints());
 
-    // walk around the path, tessellate and generate outer ring
-    // if original path is transparent, will accumulate sum of points for centroid
-    SkPath::Iter iter(path, true);
-    SkPoint pts[4];
-    SkPath::Verb verb;
-    if (fTransparent) {
-        *fPositions.push() = SkPoint::Make(0, 0);
-        *fColors.push() = fUmbraColor;
-        fCentroidCount = 0;
+    this->computePathPolygon(path, ctm);
+    if (fPathPolygon.count() < 3) {
+        return;
     }
-    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
-        switch (verb) {
-            case SkPath::kLine_Verb:
-                this->INHERITED::handleLine(ctm, &pts[1]);
-                break;
-            case SkPath::kQuad_Verb:
-                this->handleQuad(ctm, pts);
-                break;
-            case SkPath::kCubic_Verb:
-                this->handleCubic(ctm, pts);
-                break;
-            case SkPath::kConic_Verb:
-                this->handleConic(ctm, pts, iter.conicWeight());
-                break;
-            case SkPath::kMove_Verb:
-            case SkPath::kClose_Verb:
-            case SkPath::kDone_Verb:
-                break;
-        }
-        // TODO: add support for concave paths
-        if (!fIsConvex) {
-            return;
-        }
+    // TODO: add support for concave paths
+    if (!fIsConvex) {
+        return;
     }
 
-    if (!this->indexCount()) {
-        return;
+    // Add center point for fan if needed
+    if (fTransparent) {
+        *fPositions.push() = fCentroid;
+        *fColors.push() = this->umbraColor(fTransformedHeightFunc(fCentroid));
     }
 
-    // final convexity check
-    // TODO: add support for concave paths
-    if (fDirection*perp_dot(fInitPoints[1], fInitPoints[2], fFirstPoint) > 0) {
+    for (int i = 0; i < fPathPolygon.count(); ++i) {
+        this->handlePolyPoint(fPathPolygon[i]);
+    }
+
+    if (!this->indexCount()) {
         return;
     }
 
@@ -531,11 +612,8 @@ SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path,
                                  fPrevUmbraIndex, fPositions.count() - 3);
             }
 
-            // if transparent, add point to first one in array and add to center fan
+            // if transparent, add to center fan
             if (fTransparent) {
-                fPositions[0] += centerPoint;
-                ++fCentroidCount;
-
                 *fIndices.push() = 0;
                 *fIndices.push() = fPrevUmbraIndex;
                 *fIndices.push() = fPositions.count() - 2;
@@ -558,11 +636,8 @@ SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path,
         fPrevOutset = normal;
     }
 
-    // finalize centroid
+    // finalize center fan
     if (fTransparent) {
-        fPositions[0] *= SkScalarFastInvert(fCentroidCount);
-        fColors[0] = this->umbraColor(fTransformedHeightFunc(fPositions[0]));
-
         this->appendTriangle(0, fPrevUmbraIndex, fFirstVertexIndex);
     }
 
@@ -582,12 +657,42 @@ SkAmbientShadowTessellator::SkAmbientShadowTessellator(const SkPath& path,
     fSucceeded = true;
 }
 
-void SkAmbientShadowTessellator::handleLine(const SkPoint& p)  {
-    // skip duplicate points
-    if (!fInitPoints.isEmpty() && duplicate_pt(p, fInitPoints[fInitPoints.count() - 1])) {
-        return;
+void SkAmbientShadowTessellator::computePathPolygon(const SkPath& path, const SkMatrix& ctm) {
+    fPathPolygon.setReserve(path.countPoints());
+
+    // walk around the path, tessellate and generate outer ring
+    // if original path is transparent, will accumulate sum of points for centroid
+    SkPath::Iter iter(path, true);
+    SkPoint pts[4];
+    SkPath::Verb verb;
+    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
+        switch (verb) {
+        case SkPath::kLine_Verb:
+            this->handleLine(ctm, &pts[1]);
+            break;
+        case SkPath::kQuad_Verb:
+            this->handleQuad(ctm, pts);
+            break;
+        case SkPath::kCubic_Verb:
+            this->handleCubic(ctm, pts);
+            break;
+        case SkPath::kConic_Verb:
+            this->handleConic(ctm, pts, iter.conicWeight());
+            break;
+        case SkPath::kMove_Verb:
+        case SkPath::kClose_Verb:
+        case SkPath::kDone_Verb:
+            break;
+        }
     }
 
+    this->finishPathPolygon();
+}
+
+void SkAmbientShadowTessellator::handlePolyPoint(const SkPoint& p)  {
+    // should have no coincident points
+    SkASSERT(fInitPoints.isEmpty() || !duplicate_pt(p, fInitPoints[fInitPoints.count() - 1]));
+
     if (fInitPoints.count() < 2) {
         *fInitPoints.push() = p;
         return;
@@ -596,11 +701,8 @@ void SkAmbientShadowTessellator::handleLine(const SkPoint& p)  {
     if (fInitPoints.count() == 2) {
         // determine if cw or ccw
         SkScalar perpDot = perp_dot(fInitPoints[0], fInitPoints[1], p);
-        if (SkScalarNearlyZero(perpDot)) {
-            // nearly parallel, just treat as straight line and continue
-            fInitPoints[1] = p;
-            return;
-        }
+        // should not be collinear
+        SkASSERT(!SkScalarNearlyZero(perpDot));
 
         // if perpDot > 0, winding is ccw
         fDirection = (perpDot > 0) ? -1 : 1;
@@ -627,10 +729,6 @@ void SkAmbientShadowTessellator::handleLine(const SkPoint& p)  {
         *fColors.push() = this->umbraColor(z);
         *fPositions.push() = fFirstPoint + fFirstOutset;
         *fColors.push() = fPenumbraColor;
-        if (fTransparent) {
-            fPositions[0] += fFirstPoint;
-            fCentroidCount = 1;
-        }
 
         // add the first quad
         z = fTransformedHeightFunc(fInitPoints[1]);
@@ -640,15 +738,6 @@ void SkAmbientShadowTessellator::handleLine(const SkPoint& p)  {
 
         // to ensure we skip this block next time
         *fInitPoints.push() = p;
-    } else {
-        // reuse fInitPoints to track last three points
-        fInitPoints[0] = fInitPoints[1];
-        fInitPoints[1] = fInitPoints[2];
-        fInitPoints[2] = p;
-        // convexity check
-        if (fDirection*perp_dot(fInitPoints[0], fInitPoints[1], p) > 0) {
-            fIsConvex = false;
-        }
     }
 
     SkVector normal;
@@ -706,11 +795,8 @@ void SkAmbientShadowTessellator::addEdge(const SkPoint& nextPoint, const SkVecto
                              fPrevUmbraIndex, fPositions.count() - 3);
         }
 
-        // if transparent, add point to first one in array and add to center fan
+        // if transparent, add to center fan
         if (fTransparent) {
-            fPositions[0] += centerPoint;
-            ++fCentroidCount;
-
             this->appendTriangle(0, fPrevUmbraIndex, fPositions.count() - 2);
         }
 
@@ -738,11 +824,8 @@ void SkAmbientShadowTessellator::addEdge(const SkPoint& nextPoint, const SkVecto
                          fPrevUmbraIndex, fPositions.count() - 3);
     }
 
-    // if transparent, add point to first one in array and add to center fan
+    // if transparent, add to center fan
     if (fTransparent) {
-        fPositions[0] += nextPoint;
-        ++fCentroidCount;
-
         this->appendTriangle(0, fPrevUmbraIndex, fPositions.count() - 2);
     }
 
@@ -769,7 +852,6 @@ private:
     bool computeConvexShadow(SkScalar radius);
     bool computeConcaveShadow(SkScalar radius);
 
-    void handleLine(const SkPoint& p) override;
     bool handlePolyPoint(const SkPoint& p);
 
     void mapPoints(SkScalar scale, const SkVector& xlate, SkPoint* pts, int count);
@@ -788,10 +870,7 @@ private:
 
     SkTDArray<SkPoint>  fClipPolygon;
     SkTDArray<SkVector> fClipVectors;
-    SkPoint             fCentroid;
-    SkScalar            fArea;
 
-    SkTDArray<SkPoint>  fPathPolygon;
     SkTDArray<SkPoint>  fUmbraPolygon;
     int                 fCurrClipPoint;
     int                 fCurrUmbraPoint;
@@ -906,14 +985,6 @@ SkSpotShadowTessellator::SkSpotShadowTessellator(const SkPath& path, const SkMat
         }
     }
 
-    if (ctm.hasPerspective()) {
-        for (int i = 0; i < fPositions.count(); ++i) {
-            SkScalar pathZ = fTransformedHeightFunc(fPositions[i]);
-            SkScalar factor = SkScalarInvert(fLightZ - pathZ);
-            fPositions[i].fX = (fPositions[i].fX*fLightZ - lightPos.fX*pathZ)*factor;
-        }
-    }
-
     if (fIsConvex) {
         if (!this->computeConvexShadow(radius)) {
             return;
@@ -977,10 +1048,6 @@ void SkSpotShadowTessellator::computeClipAndPathPolygons(const SkPath& path, con
 
     fClipPolygon.reset();
 
-    // init centroid
-    fCentroid = SkPoint::Make(0, 0);
-    fArea = 0;
-
     // coefficients to compute cubic Bezier at t = 5/16
     static constexpr SkScalar kA = 0.32495117187f;
     static constexpr SkScalar kB = 0.44311523437f;
@@ -994,7 +1061,7 @@ void SkSpotShadowTessellator::computeClipAndPathPolygons(const SkPath& path, con
             case SkPath::kLine_Verb:
                 ctm.mapPoints(&pts[1], 1);
                 this->addToClip(pts[1]);
-                this->INHERITED::handleLine(shadowTransform, &pts[1]);
+                this->handleLine(shadowTransform, &pts[1]);
                 break;
             case SkPath::kQuad_Verb:
                 ctm.mapPoints(pts, 3);
@@ -1038,17 +1105,7 @@ void SkSpotShadowTessellator::computeClipAndPathPolygons(const SkPath& path, con
         }
     }
 
-    // finish centroid
-    if (fPathPolygon.count() > 0) {
-        SkPoint currPoint = fPathPolygon[fPathPolygon.count() - 1];
-        SkPoint nextPoint = fPathPolygon[0];
-        SkScalar quadArea = currPoint.cross(nextPoint);
-        fCentroid.fX += (currPoint.fX + nextPoint.fX) * quadArea;
-        fCentroid.fY += (currPoint.fY + nextPoint.fY) * quadArea;
-        fArea += quadArea;
-        fCentroid *= sk_ieee_float_divide(1, 3 * fArea);
-    }
-
+    this->finishPathPolygon();
     fCurrClipPoint = fClipPolygon.count() - 1;
 }
 
@@ -1058,7 +1115,6 @@ void SkSpotShadowTessellator::computeClipVectorsAndTestCentroid() {
     // init clip vectors
     SkVector v0 = fClipPolygon[1] - fClipPolygon[0];
     SkVector v1 = fClipPolygon[2] - fClipPolygon[0];
-    SkScalar winding = v0.cross(v1);
     *fClipVectors.push() = v0;
 
     // init centroid check
@@ -1070,10 +1126,6 @@ void SkSpotShadowTessellator::computeClipVectorsAndTestCentroid() {
         // add to clip vectors
         v0 = fClipPolygon[(p + 1) % fClipPolygon.count()] - fClipPolygon[p];
         *fClipVectors.push() = v0;
-        v1 = fClipPolygon[(p + 2) % fClipPolygon.count()] - fClipPolygon[p];
-        if (winding*v0.cross(v1) < 0) {
-            fIsConvex = false;
-        }
         // Determine if transformed centroid is inside clipPolygon.
         v1 = fCentroid - fClipPolygon[p];
         if (initCross*v0.cross(v1) <= 0) {
@@ -1393,33 +1445,6 @@ void SkSpotShadowTessellator::mapPoints(SkScalar scale, const SkVector& xlate,
     }
 }
 
-static bool is_collinear(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
-    return (SkScalarNearlyZero(perp_dot(p0, p1, p2)));
-}
-
-void SkSpotShadowTessellator::handleLine(const SkPoint& p) {
-    // remove coincident points and add to centroid
-    if (fPathPolygon.count() > 0) {
-        const SkPoint& lastPoint = fPathPolygon[fPathPolygon.count() - 1];
-        if (duplicate_pt(p, lastPoint)) {
-            return;
-        }
-        SkScalar quadArea = lastPoint.cross(p);
-        fCentroid.fX += (p.fX + lastPoint.fX) * quadArea;
-        fCentroid.fY += (p.fY + lastPoint.fY) * quadArea;
-        fArea += quadArea;
-    }
-
-    // try to remove collinear points
-    if (fPathPolygon.count() > 1 && is_collinear(fPathPolygon[fPathPolygon.count()-2],
-                                                 fPathPolygon[fPathPolygon.count()-1],
-                                                 p)) {
-        fPathPolygon[fPathPolygon.count() - 1] = p;
-    } else {
-        *fPathPolygon.push() = p;
-    }
-}
-
 bool SkSpotShadowTessellator::handlePolyPoint(const SkPoint& p) {
     if (fInitPoints.count() < 2) {
         *fInitPoints.push() = p;
@@ -1429,11 +1454,8 @@ bool SkSpotShadowTessellator::handlePolyPoint(const SkPoint& p) {
     if (fInitPoints.count() == 2) {
         // determine if cw or ccw
         SkScalar perpDot = perp_dot(fInitPoints[0], fInitPoints[1], p);
-        if (SkScalarNearlyZero(perpDot)) {
-            // nearly parallel, just treat as straight line and continue
-            fInitPoints[1] = p;
-            return true;
-        }
+        // shouldn't be any collinear points
+        SkASSERT(!SkScalarNearlyZero(perpDot));
 
         // if perpDot > 0, winding is ccw
         fDirection = (perpDot > 0) ? -1 : 1;