added stroking support to GrAALinearizingConvexPathRenderer

src/gpu/GrAAConvexTessellator.cpp

 /*
  * Copyright 2015 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "GrAAConvexTessellator.h"
 #include "SkCanvas.h"
 #include "SkPath.h"
 #include "SkPoint.h"
 #include "SkString.h"
 #include "GrPathUtils.h"
 
 // Next steps:
-//  use in AAConvexPathRenderer
 //  add an interactive sample app slide
 //  add debug check that all points are suitably far apart
 //  test more degenerate cases
 
 // The tolerance for fusing vertices and eliminating colinear lines (It is in device space).
 static const SkScalar kClose = (SK_Scalar1 / 16);
 static const SkScalar kCloseSqd = SkScalarMul(kClose, kClose);
 

[robertphillips, 2015/06/16 13:13:01]

Expand this comment a bit - are they in device space? Are they curvature
tolerances? 

[ethannicholas, 2015/06/16 14:53:29]

Done.

+// tesselation tolerance values
+static const SkScalar kQuadTolerance = 0.2;
+static const SkScalar kCubicTolerance = 0.2;
+static const SkScalar kConicTolerance = 0.5;
+
+// dot product below which we use a round cap between curve segments
+static const SkScalar kRoundCapThreshold = 0.8;
+
 static SkScalar intersect(const SkPoint& p0, const SkPoint& n0,
                           const SkPoint& p1, const SkPoint& n1) {
     const SkPoint v = p1 - p0;
-
     SkScalar perpDot = n0.fX * n1.fY - n0.fY * n1.fX;
     return (v.fX * n1.fY - v.fY * n1.fX) / perpDot;
 }
 
 // This is a special case version of intersect where we have the vector 
 // perpendicular to the second line rather than the vector parallel to it.
 static SkScalar perp_intersect(const SkPoint& p0, const SkPoint& n0,
                                const SkPoint& p1, const SkPoint& perp) {
     const SkPoint v = p1 - p0;
     SkScalar perpDot = n0.dot(perp);
     return v.dot(perp) / perpDot;
 }
 
 static bool duplicate_pt(const SkPoint& p0, const SkPoint& p1) {
     SkScalar distSq = p0.distanceToSqd(p1);
     return distSq < kCloseSqd;
 }
 
 static SkScalar abs_dist_from_line(const SkPoint& p0, const SkVector& v, const SkPoint& test) {
     SkPoint testV = test - p0;
     SkScalar dist = testV.fX * v.fY - testV.fY * v.fX;
     return SkScalarAbs(dist);
 }
 
 int GrAAConvexTessellator::addPt(const SkPoint& pt,
                                  SkScalar depth,
+                                 SkScalar coverage,
                                  bool movable,
                                  bool isCurve) {
     this->validate();
 
     int index = fPts.count();
     *fPts.push() = pt;
-    *fDepths.push() = depth;
+    *fCoverages.push() = coverage;
     *fMovable.push() = movable;
     *fIsCurve.push() = isCurve;
 
     this->validate();
     return index;
 }
 
 void GrAAConvexTessellator::popLastPt() {
     this->validate();
 
     fPts.pop();
-    fDepths.pop();
+    fCoverages.pop();
     fMovable.pop();
 
     this->validate();
 }
 
 void GrAAConvexTessellator::popFirstPtShuffle() {
     this->validate();
 
     fPts.removeShuffle(0);
-    fDepths.removeShuffle(0);
+    fCoverages.removeShuffle(0);
     fMovable.removeShuffle(0);
 
     this->validate();
 }
 
 void GrAAConvexTessellator::updatePt(int index,
                                      const SkPoint& pt,
-                                     SkScalar depth) {
+                                     SkScalar depth,
+                                     SkScalar coverage) {
     this->validate();
     SkASSERT(fMovable[index]);
 
     fPts[index] = pt;
-    fDepths[index] = depth;
+    fCoverages[index] = coverage;
 }
 
 void GrAAConvexTessellator::addTri(int i0, int i1, int i2) {
     if (i0 == i1 || i1 == i2 || i2 == i0) {
         return;
     }
 
     *fIndices.push() = i0;
     *fIndices.push() = i1;
     *fIndices.push() = i2;
 }
 
 void GrAAConvexTessellator::rewind() {
     fPts.rewind();
-    fDepths.rewind();
+    fCoverages.rewind();
     fMovable.rewind();
     fIndices.rewind();
     fNorms.rewind();
     fInitialRing.rewind();
     fCandidateVerts.rewind();
 #if GR_AA_CONVEX_TESSELLATOR_VIZ
     fRings.rewind();        // TODO: leak in this case!
 #else
     fRings[0].rewind();
     fRings[1].rewind();
@@ skipping 14 matching lines @@
             fBisectors[cur] += other;
             SkAssertResult(fBisectors[cur].normalize());        
         } else {
             fBisectors[cur].negate();      // make the bisector face in
         }
 
         SkASSERT(SkScalarNearlyEqual(1.0f, fBisectors[cur].length()));
     }
 }
 
+// Create as many rings as we need to (up to a predefined limit) to reach the specified target
+// depth. If we are in fill mode, the final ring will automatically be fanned.
+bool GrAAConvexTessellator::createInsetRings(Ring& previousRing, SkScalar initialDepth,

[robertphillips, 2015/06/16 13:13:01]

tab this line over ?

[ethannicholas, 2015/06/16 14:53:29]

Sorry, been using "two tabs for continuations" for like twenty years now, it's a
hard habit to break :-)

+        SkScalar initialCoverage, SkScalar targetDepth, SkScalar targetCoverage, Ring** finalRing) {
+    static const int kMaxNumRings = 8;
+
+    if (previousRing.numPts() < 3) {
+        return false;
+    }
+    Ring* currentRing = &previousRing;
+    int i;
+    for (i = 0; i < kMaxNumRings; ++i) {
+        Ring* nextRing = this->getNextRing(currentRing);
+        SkASSERT(nextRing != currentRing);
+
+        bool done = this->createInsetRing(*currentRing, nextRing, initialDepth, initialCoverage, 

[robertphillips, 2015/06/16 13:13:01]

tab this line over ?

+                targetDepth, targetCoverage, i == 0);
+        currentRing = nextRing;
+        if (done) {
+            break;
+        }
+        currentRing->init(*this);
+    }
+
+    if (kMaxNumRings == i) {
+        // Bail if we've exceeded the amount of time we want to throw at this.
+        this->terminate(*currentRing);
+        return false;
+    }
+    bool done = currentRing->numPts() >= 3;
+    if (done) {
+        currentRing->init(*this);
+    }
+    *finalRing = currentRing;
+    return done;
+}
+
 // The general idea here is to, conceptually, start with the original polygon and slide
 // the vertices along the bisectors until the first intersection. At that
 // point two of the edges collapse and the process repeats on the new polygon.
 // The polygon state is captured in the Ring class while the GrAAConvexTessellator
 // controls the iteration. The CandidateVerts holds the formative points for the
 // next ring.
 bool GrAAConvexTessellator::tessellate(const SkMatrix& m, const SkPath& path) {
-    static const int kMaxNumRings = 8;
-
-    SkDEBUGCODE(fShouldCheckDepths = true;)
-
     if (!this->extractFromPath(m, path)) {
         return false;
     }
 
-    this->createOuterRing();
+    SkScalar coverage = 1.0f;
+    if (fStrokeWidth >= 0.0f) {
+        Ring outerStrokeRing;

[robertphillips, 2015/06/16 13:13:01]

What happens when fStrokeWidth is 1.00001 ?

[ethannicholas, 2015/06/16 14:53:28]

I tested it out, and it doesn't appear to cause any problems.

+        this->createOuterRing(fInitialRing, fStrokeWidth / 2 - kAntialiasingRadius, coverage,

[robertphillips, 2015/06/16 13:13:00]

tab this line over ?

+                &outerStrokeRing);
+        outerStrokeRing.init(*this);
+        Ring outerAARing;
+        this->createOuterRing(outerStrokeRing, kAntialiasingRadius * 2, 0.0f, &outerAARing);
+    } else {
+        Ring outerAARing;
+        this->createOuterRing(fInitialRing, kAntialiasingRadius, 0.0f, &outerAARing);
+    }
 
     // the bisectors are only needed for the computation of the outer ring
     fBisectors.rewind();
-
-    Ring* lastRing = &fInitialRing;
-    int i;
-    for (i = 0; i < kMaxNumRings; ++i) {
-        Ring* nextRing = this->getNextRing(lastRing);
-
-        if (this->createInsetRing(*lastRing, nextRing)) {
-            break;
+    if (fStrokeWidth >= 0.0f && fInitialRing.numPts() > 2) {

[robertphillips, 2015/06/16 13:13:01]

Do we actually need to get the Ring* back from createInsetRings ?

[ethannicholas, 2015/06/16 14:53:29]

When stroking, we call createInsetRings twice. The first call creates the inner
line of the stroke, and then the next call insets that further with zero
coverage to create the antialiased edge. Getting the ring back from the first
call allows me to use it as the basis for the second call. I'm open to other
suggestions if there is a better way to do this.

+        Ring* insetStrokeRing;
+        SkScalar strokeDepth = fStrokeWidth / 2 - kAntialiasingRadius;

[robertphillips, 2015/06/16 13:13:01]

this->createInsetRings ?

+        if (createInsetRings(fInitialRing, 0.0f, coverage, strokeDepth, coverage, 
+                             &insetStrokeRing)) {
+            Ring* insetAARing;
+            createInsetRings(*insetStrokeRing, strokeDepth, coverage, strokeDepth + 
+                             kAntialiasingRadius * 2, 0.0f, &insetAARing);
         }
-
-        nextRing->init(*this);
-        lastRing = nextRing;
+    } else {
+        Ring* insetAARing;
+        createInsetRings(fInitialRing, 0.0f, 0.5f, kAntialiasingRadius, 1.0f, &insetAARing);
     }
 
-    if (kMaxNumRings == i) {
-        // If we've exceeded the amount of time we want to throw at this, set
-        // the depth of all points in the final ring to 'fTargetDepth' and
-        // create a fan.
-        this->terminate(*lastRing);
-        SkDEBUGCODE(fShouldCheckDepths = false;)
-    }
-
-#ifdef SK_DEBUG
-    this->validate();
-    if (fShouldCheckDepths) {
-        SkDEBUGCODE(this->checkAllDepths();)
-    }
-#endif
+    SkDEBUGCODE(this->validate();)
     return true;
 }
 
 SkScalar GrAAConvexTessellator::computeDepthFromEdge(int edgeIdx, const SkPoint& p) const {
     SkASSERT(edgeIdx < fNorms.count());
 
     SkPoint v = p - fPts[edgeIdx];
     SkScalar depth = -fNorms[edgeIdx].dot(v);
-    SkASSERT(depth >= 0.0f);
     return depth;
 }
 
 // Find a point that is 'desiredDepth' away from the 'edgeIdx'-th edge and lies
 // along the 'bisector' from the 'startIdx'-th point.
 bool GrAAConvexTessellator::computePtAlongBisector(int startIdx,
                                                    const SkVector& bisector,
                                                    int edgeIdx,
                                                    SkScalar desiredDepth,
                                                    SkPoint* result) const {
     const SkPoint& norm = fNorms[edgeIdx];
 
     // First find the point where the edge and the bisector intersect
     SkPoint newP;
+
     SkScalar t = perp_intersect(fPts[startIdx], bisector, fPts[edgeIdx], norm);
     if (SkScalarNearlyEqual(t, 0.0f)) {
         // the start point was one of the original ring points
-        SkASSERT(startIdx < fNorms.count());
+        SkASSERT(startIdx < fPts.count());
         newP = fPts[startIdx];
-    } else if (t > 0.0f) {
-        SkASSERT(t < 0.0f);
+    } else if (t < 0.0f) {
         newP = bisector;
         newP.scale(t);
         newP += fPts[startIdx];
     } else {
         return false;
     }
 
     // Then offset along the bisector from that point the correct distance
-    t = -desiredDepth / bisector.dot(norm);
-    SkASSERT(t > 0.0f);
+    SkScalar dot = bisector.dot(norm);
+    t = -desiredDepth / dot;
     *result = bisector;
     result->scale(t);
     *result += newP;
 
-
     return true;
 }
 
 bool GrAAConvexTessellator::extractFromPath(const SkMatrix& m, const SkPath& path) {
     SkASSERT(SkPath::kConvex_Convexity == path.getConvexity());
 
     // Outer ring: 3*numPts
     // Middle ring: numPts
     // Presumptive inner ring: numPts
     this->reservePts(5*path.countPoints());
     // Outer ring: 12*numPts
     // Middle ring: 0
     // Presumptive inner ring: 6*numPts + 6
     fIndices.setReserve(18*path.countPoints() + 6);
 
     fNorms.setReserve(path.countPoints());
 
-    SkDEBUGCODE(fMinCross = SK_ScalarMax;)
-    SkDEBUGCODE(fMaxCross = -SK_ScalarMax;)
-
     // TODO: is there a faster way to extract the points from the path? Perhaps
     // get all the points via a new entry point, transform them all in bulk
     // and then walk them to find duplicates?
     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->lineTo(m, pts[1], false);
                 break;
             case SkPath::kQuad_Verb:
                 this->quadTo(m, pts);
                 break;
             case SkPath::kCubic_Verb:
                 this->cubicTo(m, pts);
                 break;
             case SkPath::kConic_Verb:
                 this->conicTo(m, pts, iter.conicWeight());
                 break;
             case SkPath::kMove_Verb:
             case SkPath::kClose_Verb:
             case SkPath::kDone_Verb:
                 break;
         }
     }
 
-    if (this->numPts() < 3) {
+    if (this->numPts() < 2) {
         return false;
     }
 
     // check if last point is a duplicate of the first point. If so, remove it.
     if (duplicate_pt(fPts[this->numPts()-1], fPts[0])) {
         this->popLastPt();
         fNorms.pop();
     }
 
     SkASSERT(fPts.count() == fNorms.count()+1);
-    if (this->numPts() >= 3 &&
-        abs_dist_from_line(fPts.top(), fNorms.top(), fPts[0]) < kClose) {
-        // The last point is on the line from the second to last to the first point.
-        this->popLastPt();
-        fNorms.pop();
+    if (this->numPts() >= 3) {

[robertphillips, 2015/06/16 13:13:00]

Don't we still want to remove the last point if it is on the line from the
second to last to the first point?

[ethannicholas, 2015/06/16 14:53:29]

Oops, hadn't meant to leave that commented out.

+/*        if (abs_dist_from_line(fPts.top(), fNorms.top(), fPts[0]) < kClose) {
+            // The last point is on the line from the second to last to the first point.
+            this->popLastPt();
+            fNorms.pop();
+        }*/
+
+        *fNorms.push() = fPts[0] - fPts.top();
+        SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms.top());
+        SkASSERT(len > 0.0f);
+        SkASSERT(fPts.count() == fNorms.count());
     }
 
-    if (this->numPts() < 3) {
-        return false;
-    }
-
-    *fNorms.push() = fPts[0] - fPts.top();
-    SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms.top());
-    SkASSERT(len > 0.0f);
-    SkASSERT(fPts.count() == fNorms.count());
-
-    if (abs_dist_from_line(fPts[0], fNorms.top(), fPts[1]) < kClose) {
+    if (this->numPts() >= 3 && abs_dist_from_line(fPts[0], fNorms.top(), fPts[1]) < kClose) {
         // The first point is on the line from the last to the second.
         this->popFirstPtShuffle();
         fNorms.removeShuffle(0);
         fNorms[0] = fPts[1] - fPts[0];
         SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms[0]);
         SkASSERT(len > 0.0f);
         SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[0].length()));
     }
 
-    if (this->numPts() < 3) {
+    if (this->numPts() >= 3) {
+        // Check the cross product of the final trio
+        SkScalar cross = SkPoint::CrossProduct(fNorms[0], fNorms.top());
+        if (cross > 0.0f) {
+            fSide = SkPoint::kRight_Side;
+        } else {
+            fSide = SkPoint::kLeft_Side;
+        }
+
+        // Make all the normals face outwards rather than along the edge
+        for (int cur = 0; cur < fNorms.count(); ++cur) {
+            fNorms[cur].setOrthog(fNorms[cur], fSide);
+            SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[cur].length()));
+        }
+
+        this->computeBisectors();
+    } else if (this->numPts() == 2) {
+        // We've got two points, so we're degenerate. 
+        if (fStrokeWidth < 0.0f) {
+            // it's a fill, so we don't need to worry about degenerate paths
+            return false;
+        }
+        // For stroking, we still need to process the degenerate path, so fix it up
+        fSide = SkPoint::kLeft_Side;
+
+        // Make all the normals face outwards rather than along the edge
+        for (int cur = 0; cur < fNorms.count(); ++cur) {
+            fNorms[cur].setOrthog(fNorms[cur], fSide);
+            SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[cur].length()));
+        }
+

[robertphillips, 2015/06/16 13:13:01]

SkPoint::Make ?

+        fNorms.push({ -fNorms[0].fX, -fNorms[0].fY });
+        // we won't actually use the bisectors, so just push zeroes
+        fBisectors.push({ 0, 0 });
+        fBisectors.push({ 0, 0 });
+    } else {
         return false;
     }
 
-    // Check the cross product of the final trio
-    SkScalar cross = SkPoint::CrossProduct(fNorms[0], fNorms.top());
-    SkDEBUGCODE(fMaxCross = SkTMax(fMaxCross, cross));
-    SkDEBUGCODE(fMinCross = SkTMin(fMinCross, cross));
-    SkASSERT((fMaxCross >= 0.0f) == (fMinCross >= 0.0f));
-    if (cross > 0.0f) {
-        fSide = SkPoint::kRight_Side;
-    } else {
-        fSide = SkPoint::kLeft_Side;
-    }
-
-    // Make all the normals face outwards rather than along the edge
-    for (int cur = 0; cur < fNorms.count(); ++cur) {
-        fNorms[cur].setOrthog(fNorms[cur], fSide);
-        SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[cur].length()));
-    }
-
-    this->computeBisectors();
-
     fCandidateVerts.setReserve(this->numPts());
     fInitialRing.setReserve(this->numPts());
     for (int i = 0; i < this->numPts(); ++i) {
         fInitialRing.addIdx(i, i);
     }
     fInitialRing.init(fNorms, fBisectors);
 
     this->validate();
     return true;
 }
 
 GrAAConvexTessellator::Ring* GrAAConvexTessellator::getNextRing(Ring* lastRing) {
 #if GR_AA_CONVEX_TESSELLATOR_VIZ
     Ring* ring = *fRings.push() = SkNEW(Ring);
     ring->setReserve(fInitialRing.numPts());
     ring->rewind();
     return ring;
 #else
     // Flip flop back and forth between fRings[0] & fRings[1]
     int nextRing = (lastRing == &fRings[0]) ? 1 : 0;
     fRings[nextRing].setReserve(fInitialRing.numPts());
     fRings[nextRing].rewind();
     return &fRings[nextRing];
 #endif
 }
 
 void GrAAConvexTessellator::fanRing(const Ring& ring) {
     // fan out from point 0
-    for (int cur = 1; cur < ring.numPts()-1; ++cur) {
-        this->addTri(ring.index(0), ring.index(cur), ring.index(cur+1));
+    int startIdx = ring.index(0);
+    for (int cur = ring.numPts() - 2; cur >= 0; --cur) {
+        this->addTri(startIdx, ring.index(cur), ring.index(cur + 1));
     }
 }
 
-void GrAAConvexTessellator::createOuterRing() {
-    // For now, we're only generating one outer ring (at the start). This
-    // could be relaxed for stroking use cases.
-    SkASSERT(0 == fIndices.count());  
-    SkASSERT(fPts.count() == fNorms.count());
-
-    const int numPts = fPts.count();
+void GrAAConvexTessellator::createOuterRing(const Ring& previousRing, SkScalar outset, 
+                                            SkScalar coverage, Ring* nextRing) {
+    const int numPts = previousRing.numPts();
+    if (numPts == 0) {
+        return;
+    }
 
     int prev = numPts - 1;
-    int lastPerpIdx = -1, firstPerpIdx = -1, newIdx0, newIdx1, newIdx2;
+    int lastPerpIdx = -1, firstPerpIdx = -1;
+

[robertphillips, 2015/06/16 13:13:01]

Make outsetSq const ?

+    SkScalar outsetSq = SkScalarMul(outset, outset);
+    SkScalar miterLimitSq = SkScalarMul(outset, fMiterLimit);
+    miterLimitSq = SkScalarMul(miterLimitSq, miterLimitSq);
     for (int cur = 0; cur < numPts; ++cur) {
-        if (fIsCurve[cur]) {
-            // Inside a curve, we assume that the curvature is shallow enough (due to tesselation) 
-            // that we only need one corner point. Mathematically, the distance the corner point 
-            // gets shifted out should depend on the angle between the two line segments (as in 
-            // mitering), but again due to tesselation we assume that this angle is small and 
-            // therefore the correction factor is negligible and we do not bother with it.
+        int originalIdx = previousRing.index(cur);
+        // For each vertex of the original polygon we add at least two points to the 
+        // outset polygon - one extending perpendicular to each impinging edge. Connecting these
+        // two points yields a bevel join. We need one additional point for a mitered join, and 
+        // a round join requires one or more points depending upon curvature.
 
-            // The bisector outset point
-            SkPoint temp = fBisectors[cur];
-            temp.scale(-fTargetDepth);  // the bisectors point in
-            temp += fPts[cur];
+        // The perpendicular point for the last edge
+        SkPoint normal1 = previousRing.norm(prev);
+        SkPoint perp1 = normal1;
+        perp1.scale(outset);
+        perp1 += this->point(originalIdx);
 
-            // double-check our "sufficiently flat" assumption; we want the bisector point to be
-            // close to the normal point.
-            #define kFlatnessTolerance 1.0f
-            SkDEBUGCODE(SkPoint prevNormal = fNorms[prev];)
-            SkDEBUGCODE(prevNormal.scale(fTargetDepth);)
-            SkDEBUGCODE(prevNormal += fPts[cur];)
-            SkASSERT((temp - prevNormal).length() < kFlatnessTolerance);
+        // The perpendicular point for the next edge.
+        SkPoint normal2 = previousRing.norm(cur);
+        SkPoint perp2 = normal2;
+        perp2.scale(outset);
+        perp2 += fPts[originalIdx];
 
-            newIdx1 = this->addPt(temp, -fTargetDepth, false, true);
+        bool isCurve = fIsCurve[originalIdx];
 
-            if (0 == cur) {
-                // Store the index of the first perpendicular point to finish up
-                firstPerpIdx = newIdx1;
-                SkASSERT(-1 == lastPerpIdx);
+        // We know it isn't a duplicate of the prior point (since it and this
+        // one are just perpendicular offsets from the non-merged polygon points)
+        int perp1Idx = this->addPt(perp1, -outset, coverage, false, isCurve);
+        nextRing->addIdx(perp1Idx, originalIdx);
+
+        int perp2Idx;
+        // For very shallow angles all the corner points could fuse.
+        if (duplicate_pt(perp2, this->point(perp1Idx))) {
+            perp2Idx = perp1Idx;
+        } else {
+            perp2Idx = this->addPt(perp2, -outset, coverage, false, isCurve);
+        }
+
+        if (perp2Idx != perp1Idx) {
+            if (isCurve) {
+                // bevel or round depending upon curvature
+                SkScalar dotProd = normal1.dot(normal2);
+                if (dotProd < kRoundCapThreshold) {
+                    // Currently we "round" by creating a single extra point, which produces
+                    // good results for common cases. For thick strokes with high curvature, we will
+                    // need to add more points; for the time being we simply fall back to software
+                    // rendering for thick strokes.
+                    SkPoint miter = previousRing.bisector(cur);
+                    miter.setLength(-outset);
+                    miter += fPts[originalIdx];
+
+                    // For very shallow angles all the corner points could fuse
+                    if (!duplicate_pt(miter, this->point(perp1Idx))) {
+                        int miterIdx;
+                        miterIdx = this->addPt(miter, -outset, coverage, false, false);
+                        nextRing->addIdx(miterIdx, originalIdx);
+                        // The two triangles for the corner
+                        this->addTri(originalIdx, perp1Idx, miterIdx);
+                        this->addTri(originalIdx, miterIdx, perp2Idx);
+                    }
+                } else {
+                    this->addTri(originalIdx, perp1Idx, perp2Idx);
+                }
             } else {
-                // The triangles for the previous edge
-                this->addTri(prev, newIdx1, cur);
-                this->addTri(prev, lastPerpIdx, newIdx1);
+                switch (fJoin) {
+                    case SkPaint::Join::kMiter_Join: {
+                        // The bisector outset point
+                        SkPoint miter = previousRing.bisector(cur);
+                        SkScalar dotProd = normal1.dot(normal2);
+                        SkScalar sinHalfAngleSq = SkScalarHalf(SK_Scalar1 + dotProd);
+                        SkScalar lengthSq = outsetSq / sinHalfAngleSq;
+                        if (lengthSq > miterLimitSq) {

[robertphillips, 2015/06/16 13:13:01]

Shouldn't we just cap the miter in this case - not revert to bevel ?

[ethannicholas, 2015/06/16 14:53:29]

As far as I can tell, what I am doing is visually identical to what the standard
renderer is doing.

+                            goto bevel;
+                        }
+                        miter.setLength(-SkScalarSqrt(lengthSq));
+                        miter += fPts[originalIdx];
+
+                        // For very shallow angles all the corner points could fuse
+                        if (!duplicate_pt(miter, this->point(perp1Idx))) {
+                            int miterIdx;
+                            miterIdx = this->addPt(miter, -outset, coverage, false, false);
+                            nextRing->addIdx(miterIdx, originalIdx);
+                            // The two triangles for the corner
+                            this->addTri(originalIdx, perp1Idx, miterIdx);
+                            this->addTri(originalIdx, miterIdx, perp2Idx);
+                        }
+                        break;
+                    }
+                    case SkPaint::Join::kBevel_Join:
+                        bevel:
+                        this->addTri(originalIdx, perp1Idx, perp2Idx);
+                        break;
+                    default:
+                        // kRound_Join is unsupported for now. GrAALinearizingConvexPathRenderer is 
+                        // only willing to draw mitered or beveled, so we should never get here.
+                        SkASSERT(false);
+                }
             }
 
-            prev = cur;
-            // Track the last perpendicular outset point so we can construct the
-            // trailing edge triangles.
-            lastPerpIdx = newIdx1;
+            nextRing->addIdx(perp2Idx, originalIdx);
         }
-        else {
-            // For each vertex of the original polygon we add three points to the 
-            // outset polygon - one extending perpendicular to each impinging edge
-            // and one along the bisector. Two triangles are added for each corner
-            // and two are added along each edge.
 
-            // The perpendicular point for the last edge
-            SkPoint temp = fNorms[prev];
-            temp.scale(fTargetDepth);
-            temp += fPts[cur];
+        if (0 == cur) {
+            // Store the index of the first perpendicular point to finish up
+            firstPerpIdx = perp1Idx;
+            SkASSERT(-1 == lastPerpIdx);
+        } else {
+            // The triangles for the previous edge
+            int prevIdx = previousRing.index(prev);
+            this->addTri(prevIdx, perp1Idx, originalIdx);
+            this->addTri(prevIdx, lastPerpIdx, perp1Idx);
+        }
 
-            // We know it isn't a duplicate of the prior point (since it and this
-            // one are just perpendicular offsets from the non-merged polygon points)
-            newIdx0 = this->addPt(temp, -fTargetDepth, false, false);
-
-            // The bisector outset point
-            temp = fBisectors[cur];
-            temp.scale(-fTargetDepth);  // the bisectors point in
-            temp += fPts[cur];
-
-            // For very shallow angles all the corner points could fuse
-            if (duplicate_pt(temp, this->point(newIdx0))) {
-                newIdx1 = newIdx0;
-            } else {
-                newIdx1 = this->addPt(temp, -fTargetDepth, false, false);
-            }
-
-            // The perpendicular point for the next edge.
-            temp = fNorms[cur];
-            temp.scale(fTargetDepth);
-            temp += fPts[cur];
-
-            // For very shallow angles all the corner points could fuse.
-            if (duplicate_pt(temp, this->point(newIdx1))) {
-                newIdx2 = newIdx1;
-            } else {
-                newIdx2 = this->addPt(temp, -fTargetDepth, false, false);
-            }
-
-            if (0 == cur) {
-                // Store the index of the first perpendicular point to finish up
-                firstPerpIdx = newIdx0;
-                SkASSERT(-1 == lastPerpIdx);
-            } else {
-                // The triangles for the previous edge
-                this->addTri(prev, newIdx0, cur);
-                this->addTri(prev, lastPerpIdx, newIdx0);
-            }
-
-            // The two triangles for the corner
-            this->addTri(cur, newIdx0, newIdx1);
-            this->addTri(cur, newIdx1, newIdx2);
-
-            prev = cur;
-            // Track the last perpendicular outset point so we can construct the
-            // trailing edge triangles.
-            lastPerpIdx = newIdx2;
-        }
+        // Track the last perpendicular outset point so we can construct the
+        // trailing edge triangles.
+        lastPerpIdx = perp2Idx;
+        prev = cur;
     }
 
     // pick up the final edge rect
-    this->addTri(numPts - 1, firstPerpIdx, 0);
-    this->addTri(numPts - 1, lastPerpIdx, firstPerpIdx);
+    int lastIdx = previousRing.index(numPts - 1);
+    this->addTri(lastIdx, firstPerpIdx, previousRing.index(0));
+    this->addTri(lastIdx, lastPerpIdx, firstPerpIdx);
 
     this->validate();
 }
 
-// Something went wrong in the creation of the next ring. Mark the last good
-// ring as being at the desired depth and fan it.
+// Something went wrong in the creation of the next ring. If we're filling the shape, just go ahead
+// and fan it.
 void GrAAConvexTessellator::terminate(const Ring& ring) {
-    for (int i = 0; i < ring.numPts(); ++i) {
-        fDepths[ring.index(i)] = fTargetDepth;
+    if (fStrokeWidth < 0.0f) {
+        this->fanRing(ring);
     }
+}
 

[robertphillips, 2015/06/16 13:13:01]

compute_coverage since static ?

[ethannicholas, 2015/06/16 14:53:29]

Done.

-    this->fanRing(ring);
+static SkScalar computeCoverage(SkScalar depth, SkScalar initialDepth, SkScalar initialCoverage, 

[robertphillips, 2015/06/16 13:13:01]

tab this over ?

+        SkScalar targetDepth, SkScalar targetCoverage) {
+    if (SkScalarNearlyEqual(initialDepth, targetDepth)) {
+        return targetCoverage;
+    }
+    SkScalar result = (depth - initialDepth) / (targetDepth - initialDepth) * 
+            (targetCoverage - initialCoverage) + initialCoverage;
+    SkASSERT(result >= 0.0f && result <= 1.0f);
+    return result;
 }
 
 // return true when processing is complete
-bool GrAAConvexTessellator::createInsetRing(const Ring& lastRing, Ring* nextRing) {
+bool GrAAConvexTessellator::createInsetRing(const Ring& lastRing, Ring* nextRing, 

[robertphillips, 2015/06/16 13:13:01]

tab these lines over ?

+        SkScalar initialDepth, SkScalar initialCoverage, SkScalar targetDepth, 
+        SkScalar targetCoverage, bool forceNew) {
     bool done = false;
 
     fCandidateVerts.rewind();
 
     // Loop through all the points in the ring and find the intersection with the smallest depth
     SkScalar minDist = SK_ScalarMax, minT = 0.0f;
     int minEdgeIdx = -1;
 
     for (int cur = 0; cur < lastRing.numPts(); ++cur) {
         int next = (cur + 1) % lastRing.numPts();
-
         SkScalar t = intersect(this->point(lastRing.index(cur)),  lastRing.bisector(cur),
                                this->point(lastRing.index(next)), lastRing.bisector(next));
         SkScalar dist = -t * lastRing.norm(cur).dot(lastRing.bisector(cur));
 
         if (minDist > dist) {
             minDist = dist;
             minT = t;
             minEdgeIdx = cur;
         }
     }
 
+    if (minEdgeIdx == -1) {
+        return false;
+    }
     SkPoint newPt = lastRing.bisector(minEdgeIdx);
     newPt.scale(minT);
     newPt += this->point(lastRing.index(minEdgeIdx));
 
     SkScalar depth = this->computeDepthFromEdge(lastRing.origEdgeID(minEdgeIdx), newPt);
-    if (depth >= fTargetDepth) {
+    if (depth >= targetDepth) {
         // None of the bisectors intersect before reaching the desired depth.
         // Just step them all to the desired depth
-        depth = fTargetDepth;
+        depth = targetDepth;
         done = true;
     }
 
     // 'dst' stores where each point in the last ring maps to/transforms into
     // in the next ring.
     SkTDArray<int> dst;
     dst.setCount(lastRing.numPts());
 
     // Create the first point (who compares with no one)
     if (!this->computePtAlongBisector(lastRing.index(0),
                                       lastRing.bisector(0),
                                       lastRing.origEdgeID(0),
                                       depth, &newPt)) {
         this->terminate(lastRing);
-        SkDEBUGCODE(fShouldCheckDepths = false;)
         return true;
     }
     dst[0] = fCandidateVerts.addNewPt(newPt,
                                       lastRing.index(0), lastRing.origEdgeID(0),
                                       !this->movable(lastRing.index(0)));
 
     // Handle the middle points (who only compare with the prior point)
     for (int cur = 1; cur < lastRing.numPts()-1; ++cur) {
         if (!this->computePtAlongBisector(lastRing.index(cur),
                                           lastRing.bisector(cur),
                                           lastRing.origEdgeID(cur),
                                           depth, &newPt)) {
             this->terminate(lastRing);
-            SkDEBUGCODE(fShouldCheckDepths = false;)
             return true;
         }
         if (!duplicate_pt(newPt, fCandidateVerts.lastPoint())) {
             dst[cur] = fCandidateVerts.addNewPt(newPt,
                                                 lastRing.index(cur), lastRing.origEdgeID(cur),
                                                 !this->movable(lastRing.index(cur)));
         } else {
             dst[cur] = fCandidateVerts.fuseWithPrior(lastRing.origEdgeID(cur));
         }
     }
 
     // Check on the last point (handling the wrap around)
     int cur = lastRing.numPts()-1;
     if  (!this->computePtAlongBisector(lastRing.index(cur),
                                        lastRing.bisector(cur),
                                        lastRing.origEdgeID(cur),
                                        depth, &newPt)) {
         this->terminate(lastRing);
-        SkDEBUGCODE(fShouldCheckDepths = false;)
         return true;
     }
     bool dupPrev = duplicate_pt(newPt, fCandidateVerts.lastPoint());
     bool dupNext = duplicate_pt(newPt, fCandidateVerts.firstPoint());
 
     if (!dupPrev && !dupNext) {
         dst[cur] = fCandidateVerts.addNewPt(newPt,
                                             lastRing.index(cur), lastRing.origEdgeID(cur),
                                             !this->movable(lastRing.index(cur)));
     } else if (dupPrev && !dupNext) {
         dst[cur] = fCandidateVerts.fuseWithPrior(lastRing.origEdgeID(cur));
     } else if (!dupPrev && dupNext) {
         dst[cur] = fCandidateVerts.fuseWithNext();
     } else {
         bool dupPrevVsNext = duplicate_pt(fCandidateVerts.firstPoint(), fCandidateVerts.lastPoint());
 
         if (!dupPrevVsNext) {
             dst[cur] = fCandidateVerts.fuseWithPrior(lastRing.origEdgeID(cur));
         } else {
             dst[cur] = dst[cur-1] = fCandidateVerts.fuseWithBoth();
         }
     }
 
     // Fold the new ring's points into the global pool
     for (int i = 0; i < fCandidateVerts.numPts(); ++i) {
         int newIdx;
-        if (fCandidateVerts.needsToBeNew(i)) {
+        if (fCandidateVerts.needsToBeNew(i) || forceNew) {
             // if the originating index is still valid then this point wasn't 
             // fused (and is thus movable)

[robertphillips, 2015/06/16 13:13:01]

Is there any downside to splitting this into 2 statements ?

-            newIdx = this->addPt(fCandidateVerts.point(i), depth,
+            newIdx = this->addPt(fCandidateVerts.point(i), depth, 

[robertphillips, 2015/06/16 13:13:01]

this->computeCoverage

+                                 computeCoverage(depth, initialDepth, initialCoverage, 

[robertphillips, 2015/06/16 13:13:01]

tab this line over ?

+                                        targetDepth, targetCoverage),
                                  fCandidateVerts.originatingIdx(i) != -1, false);
         } else {
             SkASSERT(fCandidateVerts.originatingIdx(i) != -1);
-            this->updatePt(fCandidateVerts.originatingIdx(i), fCandidateVerts.point(i), depth);
+            this->updatePt(fCandidateVerts.originatingIdx(i), fCandidateVerts.point(i), depth,

[robertphillips, 2015/06/16 13:13:01]

tab this over ?

+                    targetCoverage);
             newIdx = fCandidateVerts.originatingIdx(i);
         }
 
         nextRing->addIdx(newIdx, fCandidateVerts.origEdge(i));
     }
 
     // 'dst' currently has indices into the ring. Remap these to be indices
     // into the global pool since the triangulation operates in that space.
     for (int i = 0; i < dst.count(); ++i) {
         dst[i] = nextRing->index(dst[i]);
     }
 
     for (int cur = 0; cur < lastRing.numPts(); ++cur) {
         int next = (cur + 1) % lastRing.numPts();
 
         this->addTri(lastRing.index(cur), lastRing.index(next), dst[next]);
         this->addTri(lastRing.index(cur), dst[next], dst[cur]);
     }
 
-    if (done) {
+    if (done && fStrokeWidth < 0.0f) {
+        // fill
         this->fanRing(*nextRing);
     }
 
     if (nextRing->numPts() < 3) {
         done = true;
     }
-
     return done;
 }
 
 void GrAAConvexTessellator::validate() const {
-    SkASSERT(fPts.count() == fDepths.count());
     SkASSERT(fPts.count() == fMovable.count());
     SkASSERT(0 == (fIndices.count() % 3));
 }
 
 //////////////////////////////////////////////////////////////////////////////
 void GrAAConvexTessellator::Ring::init(const GrAAConvexTessellator& tess) {
     this->computeNormals(tess);
     this->computeBisectors(tess);
-    SkASSERT(this->isConvex(tess));
 }
 
 void GrAAConvexTessellator::Ring::init(const SkTDArray<SkVector>& norms,
                                        const SkTDArray<SkVector>& bisectors) {
     for (int i = 0; i < fPts.count(); ++i) {
         fPts[i].fNorm = norms[i];
         fPts[i].fBisector = bisectors[i];
     }
 }
 
 // Compute the outward facing normal at each vertex.
 void GrAAConvexTessellator::Ring::computeNormals(const GrAAConvexTessellator& tess) {
     for (int cur = 0; cur < fPts.count(); ++cur) {
         int next = (cur + 1) % fPts.count();
 
         fPts[cur].fNorm = tess.point(fPts[next].fIndex) - tess.point(fPts[cur].fIndex);
-        SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fPts[cur].fNorm);
-        SkASSERT(len > 0.0f);
+        SkPoint::Normalize(&fPts[cur].fNorm);
         fPts[cur].fNorm.setOrthog(fPts[cur].fNorm, tess.side());
-
-        SkASSERT(SkScalarNearlyEqual(1.0f, fPts[cur].fNorm.length()));
     }
 }
 
 void GrAAConvexTessellator::Ring::computeBisectors(const GrAAConvexTessellator& tess) {
     int prev = fPts.count() - 1;
     for (int cur = 0; cur < fPts.count(); prev = cur, ++cur) {
         fPts[cur].fBisector = fPts[cur].fNorm + fPts[prev].fNorm;
         if (!fPts[cur].fBisector.normalize()) {
             SkASSERT(SkPoint::kLeft_Side == tess.side() || SkPoint::kRight_Side == tess.side());
             fPts[cur].fBisector.setOrthog(fPts[cur].fNorm, (SkPoint::Side)-tess.side());
             SkVector other;
             other.setOrthog(fPts[prev].fNorm, tess.side());
             fPts[cur].fBisector += other;
             SkAssertResult(fPts[cur].fBisector.normalize());
         } else {
             fPts[cur].fBisector.negate();      // make the bisector face in
         }
-
-        SkASSERT(SkScalarNearlyEqual(1.0f, fPts[cur].fBisector.length()));
-    }    
+    }
 }
 
 //////////////////////////////////////////////////////////////////////////////
 #ifdef SK_DEBUG
 // Is this ring convex?
 bool GrAAConvexTessellator::Ring::isConvex(const GrAAConvexTessellator& tess) const {
     if (fPts.count() < 3) {
-        return false;
+        return true;
     }
 
     SkPoint prev = tess.point(fPts[0].fIndex) - tess.point(fPts.top().fIndex);
     SkPoint cur  = tess.point(fPts[1].fIndex) - tess.point(fPts[0].fIndex);
     SkScalar minDot = prev.fX * cur.fY - prev.fY * cur.fX;
     SkScalar maxDot = minDot;
 
     prev = cur;
     for (int i = 1; i < fPts.count(); ++i) {
         int next = (i + 1) % fPts.count();
 
         cur  = tess.point(fPts[next].fIndex) - tess.point(fPts[i].fIndex);
         SkScalar dot = prev.fX * cur.fY - prev.fY * cur.fX;
 
         minDot = SkMinScalar(minDot, dot);
         maxDot = SkMaxScalar(maxDot, dot);
 
         prev = cur;
     }
 
-    return (maxDot > 0.0f) == (minDot >= 0.0f);
+    if (SkScalarNearlyEqual(maxDot, 0.0f, 0.005f)) {
+        maxDot = 0;
+    }
+    if (SkScalarNearlyEqual(minDot, 0.0f, 0.005f)) {
+        minDot = 0;
+    }
+    return (maxDot >= 0.0f) == (minDot >= 0.0f);
 }
 
 static SkScalar capsule_depth(const SkPoint& p0, const SkPoint& p1,
                               const SkPoint& test, SkPoint::Side side,
                               int* sign) {
     *sign = -1;
     SkPoint edge = p1 - p0;
     SkScalar len = SkPoint::Normalize(&edge);
 
     SkPoint testVec = test - p0;
@@ skipping 30 matching lines @@
         SkASSERT(dist >= 0.0f);
 
         if (minDist > dist) {
             minDist = dist;
             closestSign = sign;
         }
     }
 
     return closestSign * minDist;
 }
-
-// Verify that the incrementally computed depths are close to the actual depths.
-void GrAAConvexTessellator::checkAllDepths() const {
-    for (int cur = 0; cur < this->numPts(); ++cur) {

[robertphillips, 2015/06/16 13:13:01]

So, can computeRealDepth go too ?

[ethannicholas, 2015/06/16 14:53:29]

Looks like it.

-        SkScalar realDepth = this->computeRealDepth(this->point(cur));
-        SkScalar computedDepth = this->depth(cur);
-        SkASSERT(SkScalarNearlyEqual(realDepth, computedDepth, 0.01f));
-    }
-}
 #endif
 
-#define kQuadTolerance 0.2f
-#define kCubicTolerance 0.2f
-#define kConicTolerance 0.5f
-
 void GrAAConvexTessellator::lineTo(const SkMatrix& m, SkPoint p, bool isCurve) {
     m.mapPoints(&p, 1);
     if (this->numPts() > 0 && duplicate_pt(p, this->lastPoint())) {
         return;
     }
 
     SkASSERT(fPts.count() <= 1 || fPts.count() == fNorms.count()+1);
     if (this->numPts() >= 2 && 
         abs_dist_from_line(fPts.top(), fNorms.top(), p) < kClose) {
         // The old last point is on the line from the second to last to the new point
         this->popLastPt();
         fNorms.pop();
         fIsCurve.pop();
     }
-    this->addPt(p, 0.0f, false, isCurve);
+    SkScalar initialRingCoverage = fStrokeWidth < 0.0f ? 0.5f : 1.0f;
+    this->addPt(p, 0.0f, initialRingCoverage, false, isCurve);
     if (this->numPts() > 1) {
         *fNorms.push() = fPts.top() - fPts[fPts.count()-2];
         SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms.top());
         SkASSERT(len > 0.0f);
         SkASSERT(SkScalarNearlyEqual(1.0f, fNorms.top().length()));
     }
-    SkDEBUGCODE(
-        if (this->numPts() >= 3) {
-            int cur = this->numPts()-1;
-            SkScalar cross = SkPoint::CrossProduct(fNorms[cur-1], fNorms[cur-2]);
-            fMaxCross = SkTMax(fMaxCross, cross);
-            fMinCross = SkTMin(fMinCross, cross);
-        }
-    )
 }
 
 void GrAAConvexTessellator::quadTo(const SkMatrix& m, SkPoint pts[3]) {
     int maxCount = GrPathUtils::quadraticPointCount(pts, kQuadTolerance);
     fPointBuffer.setReserve(maxCount);
     SkPoint* target = fPointBuffer.begin();
     int count = GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2], 
             kQuadTolerance, &target, maxCount);
     fPointBuffer.setCount(count);
     for (int i = 0; i < count; i++) {
@@ skipping 125 matching lines @@
                   SK_ColorBLACK);
     }
 
     fInitialRing.draw(canvas, *this);
     for (int i = 0; i < fRings.count(); ++i) {
         fRings[i]->draw(canvas, *this);
     }
 
     for (int i = 0; i < this->numPts(); ++i) {
         draw_point(canvas,
-                   this->point(i), 0.5f + (this->depth(i)/(2*fTargetDepth)), 
+                   this->point(i), 0.5f + (this->depth(i)/(2 * kAntialiasingRadius)), 
                    !this->movable(i));
 
         SkPaint paint;
         paint.setTextSize(kPointTextSize);
         paint.setTextAlign(SkPaint::kCenter_Align);
-        if (this->depth(i) <= -fTargetDepth) {
+        if (this->depth(i) <= -kAntialiasingRadius) {
             paint.setColor(SK_ColorWHITE);
         }
 
         SkString num;
         num.printf("%d", i);
         canvas->drawText(num.c_str(), num.size(), 
                          this->point(i).fX, this->point(i).fY+(kPointRadius/2.0f), 
                          paint);
     }
 }
 
 #endif