Added GrAAFlatteningConvexPathRenderer

src/gpu/GrAAFlatteningConvexTessellator.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 "GrAAFlatteningConvexTessellator.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);
@@ skipping 19 matching lines @@
     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,
+int GrAAFlatteningConvexTessellator::addPt(const SkPoint& pt,

[robertphillips, 2015/05/27 18:10:54]

line these guys up ?

                                  SkScalar depth,
-                                 bool movable) {
+                                 bool movable,
+                                 bool isCurve) {
     this->validate();
 
     int index = fPts.count();
     *fPts.push() = pt;
     *fDepths.push() = depth;
     *fMovable.push() = movable;
+    *fIsCurve.push() = isCurve;
 
     this->validate();
     return index;
 }
 
-void GrAAConvexTessellator::popLastPt() {
+void GrAAFlatteningConvexTessellator::popLastPt() {
     this->validate();
 
     fPts.pop();
     fDepths.pop();
     fMovable.pop();
 
     this->validate();
 }
 
-void GrAAConvexTessellator::popFirstPtShuffle() {
+void GrAAFlatteningConvexTessellator::popFirstPtShuffle() {
     this->validate();
 
     fPts.removeShuffle(0);
     fDepths.removeShuffle(0);
     fMovable.removeShuffle(0);
 
     this->validate();
 }
 
-void GrAAConvexTessellator::updatePt(int index,
+void GrAAFlatteningConvexTessellator::updatePt(int index,

[robertphillips, 2015/05/27 18:10:54]

line up ?

                                      const SkPoint& pt,
                                      SkScalar depth) {
     this->validate();
     SkASSERT(fMovable[index]);
 
     fPts[index] = pt;
     fDepths[index] = depth;
 }
 
-void GrAAConvexTessellator::addTri(int i0, int i1, int i2) {
+void GrAAFlatteningConvexTessellator::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() {
+void GrAAFlatteningConvexTessellator::rewind() {
     fPts.rewind();
     fDepths.rewind();
     fMovable.rewind();
     fIndices.rewind();
     fNorms.rewind();
     fInitialRing.rewind();
     fCandidateVerts.rewind();
-#if GR_AA_CONVEX_TESSELLATOR_VIZ
+#if GR_AA_FLATTENING_CONVEX_TESSELLATOR_VIZ
     fRings.rewind();        // TODO: leak in this case!
 #else
     fRings[0].rewind();
     fRings[1].rewind();
 #endif
 }
 
-void GrAAConvexTessellator::computeBisectors() {
+void GrAAFlatteningConvexTessellator::computeBisectors() {
     fBisectors.setCount(fNorms.count());
 
     int prev = fBisectors.count() - 1;
     for (int cur = 0; cur < fBisectors.count(); prev = cur, ++cur) {
         fBisectors[cur] = fNorms[cur] + fNorms[prev];
         if (!fBisectors[cur].normalize()) {
             SkASSERT(SkPoint::kLeft_Side == fSide || SkPoint::kRight_Side == fSide);
             fBisectors[cur].setOrthog(fNorms[cur], (SkPoint::Side)-fSide);
             SkVector other;
             other.setOrthog(fNorms[prev], fSide);
             fBisectors[cur] += other;
             SkAssertResult(fBisectors[cur].normalize());        
         } else {
             fBisectors[cur].negate();      // make the bisector face in
         }
 
         SkASSERT(SkScalarNearlyEqual(1.0f, fBisectors[cur].length()));
     }
 }
 
 // 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
+// The polygon state is captured in the Ring class while the GrAAFlatteningConvexTessellator
 // 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;
+bool GrAAFlatteningConvexTessellator::tessellate(const SkMatrix& m, const SkPath& path) {
+    static const int kMaxNumRings = 1;
 
     SkDEBUGCODE(fShouldCheckDepths = true;)
 
     if (!this->extractFromPath(m, path)) {
         return false;
     }
 
     this->createOuterRing();
 
     // the bisectors are only needed for the computation of the outer ring
@@ skipping 22 matching lines @@
 
 #ifdef SK_DEBUG
     this->validate();
     if (fShouldCheckDepths) {
         SkDEBUGCODE(this->checkAllDepths();)
     }
 #endif
     return true;
 }
 
-SkScalar GrAAConvexTessellator::computeDepthFromEdge(int edgeIdx, const SkPoint& p) const {
+SkScalar GrAAFlatteningConvexTessellator::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,
+bool GrAAFlatteningConvexTessellator::computePtAlongBisector(int startIdx,

[robertphillips, 2015/05/27 18:10:54]

line up ?

                                                    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)) {
@@ skipping 13 matching lines @@
     t = -desiredDepth / bisector.dot(norm);
     SkASSERT(t > 0.0f);
     *result = bisector;
     result->scale(t);
     *result += newP;
 
 
     return true;
 }
 
-bool GrAAConvexTessellator::extractFromPath(const SkMatrix& m, const SkPath& path) {
-    SkASSERT(SkPath::kLine_SegmentMask == path.getSegmentMasks());
+bool GrAAFlatteningConvexTessellator::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());
 
-    SkScalar minCross = SK_ScalarMax, maxCross = -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:
-                m.mapPoints(&pts[1], 1);
-                if (this->numPts() > 0 && duplicate_pt(pts[1], this->lastPoint())) {
-                    continue;
-                }
-
-                SkASSERT(fPts.count() <= 1 || fPts.count() == fNorms.count()+1);
-                if (this->numPts() >= 2 && 
-                    abs_dist_from_line(fPts.top(), fNorms.top(), pts[1]) < kClose) {
-                    // The old last point is on the line from the second to last to the new point
-                    this->popLastPt();
-                    fNorms.pop();
-                }
-
-                this->addPt(pts[1], 0.0f, false);
-                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()));
-                }
-
-                if (this->numPts() >= 3) {
-                    int cur = this->numPts()-1;
-                    SkScalar cross = SkPoint::CrossProduct(fNorms[cur-1], fNorms[cur-2]);
-                    maxCross = SkTMax(maxCross, cross);
-                    minCross = SkTMin(minCross, cross);
-                }
+                lineTo(m, pts[1], false);

[bsalomon, 2015/05/27 17:11:07]

style nit, for (non-static) method calls we prefix them with "this->"

e.g. this->lineTo(m, pts[1], false);

[ethannicholas, 2015/05/27 19:22:30]

Done.

                 break;
             case SkPath::kQuad_Verb:
+                quadTo(m, pts);
+                break;
+            case SkPath::kCubic_Verb:
+                cubicTo(m, pts);
+                break;
             case SkPath::kConic_Verb:
-            case SkPath::kCubic_Verb:
-                SkASSERT(false);
+                conicTo(m, pts, iter.conicWeight());
                 break;
             case SkPath::kMove_Verb:
             case SkPath::kClose_Verb:
             case SkPath::kDone_Verb:
                 break;
         }
     }
 
     if (this->numPts() < 3) {
         return false;
@@ skipping 30 matching lines @@
         SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms[0]);
         SkASSERT(len > 0.0f);
         SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[0].length()));
     }
 
     if (this->numPts() < 3) {
         return false;
     }
 
     // Check the cross produce of the final trio
     SkScalar cross = SkPoint::CrossProduct(fNorms[0], fNorms.top());

[robertphillips, 2015/05/27 18:10:54]

Hmmm ...

[ethannicholas, 2015/05/27 19:22:30]

The work to compute the min & max cross products showed up in profiling as
taking a significant amount of time, and as far as I could tell was solely used
in assertions that would have failed if the path were not convex. Since the path
has already been verified to be convex, I did not see this work as being worth
the effort.

-    maxCross = SkTMax(maxCross, cross);
-    minCross = SkTMin(minCross, cross);
-
-    if (maxCross > 0.0f) {
-        SkASSERT(minCross >= 0.0f);
+    if (cross > 0.0f) {
         fSide = SkPoint::kRight_Side;
     } else {
-        SkASSERT(minCross <= 0.0f);
         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
+GrAAFlatteningConvexTessellator::Ring* GrAAFlatteningConvexTessellator::getNextRing(Ring* lastRing) {
+#if GR_AA_FLATTENING_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) {
+void GrAAFlatteningConvexTessellator::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));
     }
 }
 
-void GrAAConvexTessellator::createOuterRing() {
+void GrAAFlatteningConvexTessellator::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();
 
-    // 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.
     int prev = numPts - 1;
     int lastPerpIdx = -1, firstPerpIdx = -1, newIdx0, newIdx1, newIdx2;
     for (int cur = 0; cur < numPts; ++cur) {
-        // The perpendicular point for the last edge
-        SkPoint temp = fNorms[prev];
-        temp.scale(fTargetDepth);
-        temp += fPts[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.

[bsalomon, 2015/05/27 17:11:07]

Is it reasonable to have an assert that verifies the assumption?

[ethannicholas, 2015/05/27 19:22:30]

Done.

 
-        // 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);
+            // The bisector outset point
+            SkPoint temp = fBisectors[cur];
+            temp.scale(-fTargetDepth);  // the bisectors point in
+            temp += fPts[cur];
 
-        // The bisector outset point
-        temp = fBisectors[cur];
-        temp.scale(-fTargetDepth);  // the bisectors point in
-        temp += fPts[cur];
+            newIdx1 = this->addPt(temp, -fTargetDepth, false, true);
 
-        // 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);
+            if (0 == cur) {
+                // Store the index of the first perpendicular point to finish up
+                firstPerpIdx = newIdx1;
+                SkASSERT(-1 == lastPerpIdx);
+            } else {
+                // The triangles for the previous edge
+                this->addTri(prev, newIdx1, cur);
+                this->addTri(prev, lastPerpIdx, newIdx1);
+            }
+
+            prev = cur;
+            // Track the last perpendicular outset point so we can construct the
+            // trailing edge triangles.
+            lastPerpIdx = newIdx1;
         }
+        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 next edge.
-        temp = fNorms[cur];
-        temp.scale(fTargetDepth);
-        temp += fPts[cur];
+            // The perpendicular point for the last edge
+            SkPoint temp = fNorms[prev];
+            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);
+            // 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;
         }
-
-        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;
     }
 
     // pick up the final edge rect
-    this->addTri(numPts-1, firstPerpIdx, 0);
-    this->addTri(numPts-1, lastPerpIdx, firstPerpIdx);
+    this->addTri(numPts - 1, firstPerpIdx, 0);
+    this->addTri(numPts - 1, 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.
-void GrAAConvexTessellator::terminate(const Ring& ring) {
+void GrAAFlatteningConvexTessellator::terminate(const Ring& ring) {
     for (int i = 0; i < ring.numPts(); ++i) {
         fDepths[ring.index(i)] = fTargetDepth;
     }
 
     this->fanRing(ring);
 }
 
 // return true when processing is complete
-bool GrAAConvexTessellator::createInsetRing(const Ring& lastRing, Ring* nextRing) {
+bool GrAAFlatteningConvexTessellator::createInsetRing(const Ring& lastRing, Ring* nextRing) {
     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();
@@ skipping 89 matching lines @@
         }
     }
 
     // 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 the originating index is still valid then this point wasn't 
             // fused (and is thus movable)
             newIdx = this->addPt(fCandidateVerts.point(i), depth,
-                                 fCandidateVerts.originatingIdx(i) != -1);
+                                 fCandidateVerts.originatingIdx(i) != -1, false);
         } else {
             SkASSERT(fCandidateVerts.originatingIdx(i) != -1);
             this->updatePt(fCandidateVerts.originatingIdx(i), fCandidateVerts.point(i), depth);
             newIdx = fCandidateVerts.originatingIdx(i);
         }
 
         nextRing->addIdx(newIdx, fCandidateVerts.origEdge(i));
     }
 
     // 'dst' currently has indices into the ring. Remap these to be indices
@@ skipping 13 matching lines @@
         this->fanRing(*nextRing);
     }
 
     if (nextRing->numPts() < 3) {
         done = true;
     }
 
     return done;
 }
 
-void GrAAConvexTessellator::validate() const {
+void GrAAFlatteningConvexTessellator::validate() const {
     SkASSERT(fPts.count() == fDepths.count());
     SkASSERT(fPts.count() == fMovable.count());
     SkASSERT(0 == (fIndices.count() % 3));
 }
 
 //////////////////////////////////////////////////////////////////////////////
-void GrAAConvexTessellator::Ring::init(const GrAAConvexTessellator& tess) {
+void GrAAFlatteningConvexTessellator::Ring::init(const GrAAFlatteningConvexTessellator& tess) {
     this->computeNormals(tess);
     this->computeBisectors(tess);
     SkASSERT(this->isConvex(tess));
 }
 
-void GrAAConvexTessellator::Ring::init(const SkTDArray<SkVector>& norms,
+void GrAAFlatteningConvexTessellator::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) {
+void GrAAFlatteningConvexTessellator::Ring::computeNormals(const GrAAFlatteningConvexTessellator& 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);
         fPts[cur].fNorm.setOrthog(fPts[cur].fNorm, tess.side());
 
         SkASSERT(SkScalarNearlyEqual(1.0f, fPts[cur].fNorm.length()));
     }
 }
 
-void GrAAConvexTessellator::Ring::computeBisectors(const GrAAConvexTessellator& tess) {
+void GrAAFlatteningConvexTessellator::Ring::computeBisectors(const GrAAFlatteningConvexTessellator& 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 {
+bool GrAAFlatteningConvexTessellator::Ring::isConvex(const GrAAFlatteningConvexTessellator& tess) const {
     if (fPts.count() < 3) {
         return false;
     }
 
     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;
@@ skipping 35 matching lines @@
     }
 
     if (perpDist < 0.0f) {
         perpDist = -perpDist;
     } else {
         *sign = 1;
     }
     return perpDist;
 }
 
-SkScalar GrAAConvexTessellator::computeRealDepth(const SkPoint& p) const {
+SkScalar GrAAFlatteningConvexTessellator::computeRealDepth(const SkPoint& p) const {
     SkScalar minDist = SK_ScalarMax;
     int closestSign, sign;
 
     for (int edge = 0; edge < fNorms.count(); ++edge) {
         SkScalar dist = capsule_depth(this->point(edge),
                                       this->point((edge+1) % fNorms.count()),
                                       p, fSide, &sign);
         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 {
+void GrAAFlatteningConvexTessellator::checkAllDepths() const {
     for (int cur = 0; cur < this->numPts(); ++cur) {
         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 GrAAFlatteningConvexTessellator::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);
+    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()));
+    }
+}
+
+void GrAAFlatteningConvexTessellator::quadTo(const SkMatrix& m, SkPoint* pts) {
+    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++) {
+        lineTo(m, fPointBuffer[i], true);
+    }
+}
+
+void GrAAFlatteningConvexTessellator::cubicTo(const SkMatrix& m, SkPoint* pts) {
+    int maxCount = GrPathUtils::cubicPointCount(pts, kCubicTolerance);
+    fPointBuffer.setReserve(maxCount);
+    SkPoint* target = fPointBuffer.begin();
+    int count = GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3], 
+            kCubicTolerance, &target, maxCount);
+    fPointBuffer.setCount(count);
+    for (int i = 0; i < count; i++) {
+        lineTo(m, fPointBuffer[i], true);
+    }
+}
+
+// include down here to avoid compilation errors caused by "-" overload in SkGeometry.h

[bsalomon, 2015/05/27 17:11:07]

What's the error?

[ethannicholas, 2015/05/27 19:22:30]

In file included from ../../src/gpu/GrAAFlatteningConvexTessellator.cpp:14:
In file included from ../../src/core/SkGeometry.h:12:
../../src/core/SkNx.h:264:58: error: cannot initialize return object of type
'SkPoint::Side' with an rvalue of type 'int'
template <typename T> T operator - (const T& l) { return T(0) - l; }
                                                         ^~~~~~~~
../../src/gpu/GrAAFlatteningConvexTessellator.cpp:134:67: note: in instantiation
of function template specialization 'operator-<SkPoint::Side>' requested here
            fBisectors[cur].setOrthog(fNorms[cur], (SkPoint::Side)-fSide);

+#include "SkGeometry.h"
+
+void GrAAFlatteningConvexTessellator::conicTo(const SkMatrix& m, SkPoint* pts, SkScalar w) {
+    SkAutoConicToQuads quadder;
+    const SkPoint* quads = quadder.computeQuads(pts, w, kConicTolerance);
+    SkPoint lastPoint = *(quads++);
+    int count = quadder.countQuads();
+    for (int i = 0; i < count; ++i) {
+        SkPoint quadPts[3];
+        quadPts[0] = lastPoint;
+        quadPts[1] = quads[0];
+        quadPts[2] = i == count - 1 ? pts[2] : quads[1];
+        quadTo(m, quadPts);
+        lastPoint = quadPts[2];
+        quads += 2;
+    }
+}
+
 //////////////////////////////////////////////////////////////////////////////
-#if GR_AA_CONVEX_TESSELLATOR_VIZ
+#if GR_AA_FLATTENING_CONVEX_TESSELLATOR_VIZ
 static const SkScalar kPointRadius = 0.02f;
 static const SkScalar kArrowStrokeWidth = 0.0f;
 static const SkScalar kArrowLength = 0.2f;
 static const SkScalar kEdgeTextSize = 0.1f;
 static const SkScalar kPointTextSize = 0.02f;
 
 static void draw_point(SkCanvas* canvas, const SkPoint& p, SkScalar paramValue, bool stroke) {
     SkPaint paint;
     SkASSERT(paramValue <= 1.0f);
     int gs = int(255*paramValue);
@@ skipping 22 matching lines @@
     SkPaint paint;
     paint.setColor(color);
     paint.setStrokeWidth(kArrowStrokeWidth);
     paint.setStyle(SkPaint::kStroke_Style);
 
     canvas->drawLine(p.fX, p.fY,
                      p.fX + len * n.fX, p.fY + len * n.fY,
                      paint);
 }
 
-void GrAAConvexTessellator::Ring::draw(SkCanvas* canvas, const GrAAConvexTessellator& tess) const {
+void GrAAFlatteningConvexTessellator::Ring::draw(SkCanvas* canvas, const GrAAFlatteningConvexTessellator& tess) const {

[bsalomon, 2015/05/27 17:11:07]

nit, 100 col wrap

[ethannicholas, 2015/05/27 19:22:30]

Done.

     SkPaint paint;
     paint.setTextSize(kEdgeTextSize);
 
     for (int cur = 0; cur < fPts.count(); ++cur) {
         int next = (cur + 1) % fPts.count();
 
         draw_line(canvas,
                   tess.point(fPts[cur].fIndex),
                   tess.point(fPts[next].fIndex),
                   SK_ColorGREEN);
@@ skipping 11 matching lines @@
         num.printf("%d", this->origEdgeID(cur));
         canvas->drawText(num.c_str(), num.size(), mid.fX, mid.fY, paint);
 
         if (fPts.count()) {
             draw_arrow(canvas, tess.point(fPts[cur].fIndex), fPts[cur].fBisector,
                        kArrowLength, SK_ColorBLUE);
         }
     }    
 }
 
-void GrAAConvexTessellator::draw(SkCanvas* canvas) const {
+void GrAAFlatteningConvexTessellator::draw(SkCanvas* canvas) const {
     for (int i = 0; i < fIndices.count(); i += 3) {
         SkASSERT(fIndices[i] < this->numPts()) ;
         SkASSERT(fIndices[i+1] < this->numPts()) ;
         SkASSERT(fIndices[i+2] < this->numPts()) ;
 
         draw_line(canvas,
                   this->point(this->fIndices[i]), this->point(this->fIndices[i+1]),
                   SK_ColorBLACK);
         draw_line(canvas,
                   this->point(this->fIndices[i+1]), this->point(this->fIndices[i+2]),
@@ skipping 23 matching lines @@
         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