Add GrAAConvexTessellator class

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"
+
+// Next steps:
+//  use in AAConvexPathRenderer
+//  add an interactive sample app slide
+//  add a combo gm/bench
+//  add debug check that all points are suitably far apart
+//  test more degenerate cases
+
+// Add swap & converted flag to ring
+
+// 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);
+
+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;
+}
+
+static SkScalar perp_intersect(const SkPoint& p0, const SkPoint& n0,

[bsalomon, 2015/04/24 15:44:44]

could use a tiny comment here

[robertphillips, 2015/05/05 15:21:32]

Done.

+                               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 SkPoint& p1, const SkPoint& test) {

[bsalomon, 2015/04/24 15:44:44]

Wondering if we could use SkPoint::distanceToLineBetweenSqd here and skip the
sqrt (with a sqd kClose value)?

[robertphillips, 2015/05/05 15:21:33]

Done. The new version uses the vector computed for the normals.

+    // TODO: update this to use the normals computed for a ring rather than recomputing
+    SkPoint v = p1 - p0;
+    v.normalize();
+
+    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,
+                                 bool movable) {
+    this->validate();
+
+    int index = fPts.count();
+    *fPts.push() = pt;
+    *fDepths.push() = depth;
+    *fMovable.push() = movable;
+
+    this->validate();
+    return index;
+}
+
+void GrAAConvexTessellator::popLastPt() {
+    this->validate();
+
+    fPts.pop();
+    fDepths.pop();
+    fMovable.pop();
+
+    this->validate();
+}
+
+void GrAAConvexTessellator::popFirstPtShuffle() {
+    this->validate();
+
+    fPts.removeShuffle(0);
+    fDepths.removeShuffle(0);
+    fMovable.removeShuffle(0);
+
+    this->validate();
+}
+
+void GrAAConvexTessellator::updatePt(int index,
+                                     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) {
+    if (i0 == i1 || i1 == i2 || i2 == i0) {
+        return;
+    }
+
+    *fIndices.push() = i0;
+    *fIndices.push() = i1;
+    *fIndices.push() = i2;
+}
+
+// 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 GrRing class while the GrAAConvexTessellator
+// controls the iteration.
+bool GrAAConvexTessellator::tessellate(const SkMatrix& m, const SkPath& path) {
+    static const int kMaxNumRings = 7;
+
+    if (!this->extractFromPath(m, path)) {
+        return false;
+    }
+
+    this->createOuterRing(fInitialRing);
+
+    GrRing* lastRing = &fInitialRing;
+    int i;
+    for (i = 0; i < kMaxNumRings; ++i) {
+        GrRing* nextRing = this->getNextRing(lastRing);
+
+        if (this->createInsetRing(*lastRing, nextRing)) {
+            break;
+        }
+
+        if (nextRing->numPts0() < 3) {
+            break;
+        }
+
+        nextRing->init(*this);
+        lastRing = nextRing;
+    }
+
+    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.
+        for (int i = 0; i < lastRing->numPts0(); ++i) {
+            this->fDepths[lastRing->index(i)] = fTargetDepth;
+        }
+        this->fanRing(*lastRing);
+    }
+
+    this->validate();
+    SkDEBUGCODE(this->checkAllDepths();)
+    return true;
+}
+
+// Find a point that is 'desiredDepth' away from the 'edgeIdx'-th edge and lies
+// along the 'bisector' from the 'startIdx'-th point.
+SkPoint GrAAConvexTessellator::computePtAlongBisector(int startIdx,
+                                                      const SkVector& bisector,
+                                                      int edgeIdx,
+                                                      SkScalar desiredDepth) const {
+    const SkPoint& norm = fInitialRing.norm1(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 < fInitialRing.numPts0());
+        newP = fPts[startIdx];
+    } else {
+        SkASSERT(t < 0.0f);
+        newP = bisector;
+        newP.scale(t);
+        newP += fPts[startIdx];
+    }
+
+    // Then offset along the bisector from that point the correct distance
+    t = -desiredDepth / bisector.dot(norm);
+    SkASSERT(t > 0.0f);
+    SkPoint result = bisector;
+    result.scale(t);
+    result += newP;
+
+    return result;
+}
+
+bool GrAAConvexTessellator::extractFromPath(const SkMatrix& m, const SkPath& path) {
+    SkASSERT(SkPath::kLine_SegmentMask == path.getSegmentMasks());
+    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);
+
+    SkScalar minCross = SK_ScalarMax, maxCross = -SK_ScalarMax;
+
+    // TODO: can we reuse the GrRing structure in this process?
+    SkPath::Iter iter(path, true);
+    SkPoint pts[4];
+    SkPath::Verb verb;
+    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {

[bsalomon, 2015/04/24 15:44:44]

Do we really need to iterate here?

We know all the points in the path are a convex polygon. Can't we just get the
point array out of the path, transform it in bulk, and then walk it again
removing degeneracies?

[robertphillips, 2015/05/05 15:21:33]

I've added a TODO. I think we would need a new entry point on path.

+        switch (verb) {
+            case SkPath::kLine_Verb:
+                m.mapPoints(&pts[1], 1);
+                if (this->numPts() > 0 && duplicate_pt(pts[1], this->lastPoint())) {
+                    continue;
+                }
+
+                if (this->numPts() >= 2 && 
+                    abs_dist_from_line(fPts[this->numPts()-1], fPts[this->numPts()-2], pts[1]) < 
+                    kClose) {
+                    // The old last point is on the line from the second to last to the new point
+                    this->popLastPt();
+                }
+
+                this->addPt(pts[1], 0.0f, false);
+
+                if (this->numPts() >= 3) {
+                    int cur = this->numPts()-1;
+
+                    SkScalar cross = SkPoint::CrossProduct(fPts[cur] - fPts[cur-1],
+                                                           fPts[cur-1] - fPts[cur-2]);
+                    if (maxCross < cross) {

[bsalomon, 2015/04/24 15:44:44]

maxCross = SkTMax(maxCross, cross);
minCross = SkTMin(minCross, cross);
?

[robertphillips, 2015/05/05 15:21:32]

Done.

+                        maxCross = cross;
+                    }
+                    if (minCross > cross) {
+                        minCross = cross;
+                    }
+                }
+                break;
+            case SkPath::kQuad_Verb:
+            case SkPath::kConic_Verb:
+            case SkPath::kCubic_Verb:
+                SkASSERT(false);
+                break;
+            case SkPath::kMove_Verb:
+            case SkPath::kClose_Verb:
+            case SkPath::kDone_Verb:
+                break;
+        }
+    }
+
+    // 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();
+    }
+
+    if (this->numPts() >= 3 &&
+        abs_dist_from_line(fPts[this->numPts()-1], fPts[this->numPts()-2], fPts[0]) < kClose) {
+        // The last point is on the line from the second to last to the first point.
+        this->popLastPt();
+    }
+
+    if (this->numPts() >= 3 &&
+        abs_dist_from_line(fPts[0], fPts[this->numPts()-1], fPts[1]) < kClose) {
+        // The first point is on the line from the last to the second.
+        this->popFirstPtShuffle();
+        SkASSERT(0);
+    }
+
+    if (this->numPts() < 3) {
+        return false;
+    }
+
+    // Check the cross produce of the final trio
+    SkScalar cross = SkPoint::CrossProduct(fPts[1] - fPts[0], fPts[0] - fPts[fPts.count()-1]);
+    if (maxCross < cross) {
+        maxCross = cross;
+    }
+    if (minCross > cross) {
+        minCross = cross;
+    }
+
+    SkPoint::Side side;

[bsalomon, 2015/04/24 15:44:44]

It wouldn't surprise me much if the asserts here were hit. I think the convexity
checker has some tolerance. Might wind up taking the larger abs value of
min/maxCross to decide the side and assert that the other isn't "too big."

[robertphillips, 2015/05/05 15:21:32]

I think the colinear cleanup pass should remove the slightly small concavities
so I would like to keep this hard for now.

+    if (maxCross > 0.0f) {
+        SkASSERT(minCross >= 0.0f);
+        side = SkPoint::kRight_Side;
+    } else {
+        SkASSERT(minCross <= 0.0f);
+        side = SkPoint::kLeft_Side;
+    }
+
+    fInitialRing.setReserve(this->numPts());
+    fInitialRing.setSide(side);
+    for (int i = 0; i < this->numPts(); ++i) {
+        fInitialRing.addIdx1(i, i);
+    }
+    fInitialRing.init(*this);
+
+    this->validate();
+    return true;
+}
+
+GrRing* GrAAConvexTessellator::getNextRing(GrRing* lastRing) {
+#if GR_AA_CONVEX_TESSELLATOR_VIZ
+    GrRing* ring = *fRings.push() = SkNEW(GrRing);
+    ring->setReserve(fInitialRing.numPts0());
+    ring->setSide(fInitialRing.side());
+    ring->rewind();
+    return ring;
+#else
+    // Flip flop back and forth between fRings[0] & fRings[1]

[bsalomon, 2015/04/24 15:44:44]

Is this different than

int nextRing = lastRing == &fRings[0] ? 1 : 0;
fRings[nextRing].setReserve(fInitialRing.numPts0());
fRings[nextRing].setSide(fInitialRing.side());
fRings[nextRing].rewind();
return &fRings[nextRing];

?

[robertphillips, 2015/05/05 15:21:32]

Done.

+    if (lastRing == &fInitialRing) {
+        fRings[0].setReserve(fInitialRing.numPts0());
+        fRings[0].setSide(fInitialRing.side());
+        fRings[0].rewind();
+        return &fRings[0];
+    } else if (lastRing == &fRings[0]) {
+        fRings[1].setReserve(fInitialRing.numPts0());
+        fRings[1].setSide(fInitialRing.side());
+        fRings[1].rewind();
+        return &fRings[1];
+    } else {
+        SkASSERT(lastRing == &fRings[1]);
+        fRings[0].setReserve(fInitialRing.numPts0());
+        fRings[0].setSide(fInitialRing.side());
+        fRings[0].rewind();
+        return &fRings[0];
+    }
+#endif
+}
+
+void GrAAConvexTessellator::fanRing(const GrRing& ring) {
+    // fan out from point 0
+    for (int cur = 1; cur < ring.numPts2()-1; ++cur) {
+        this->addTri(ring.index(0), ring.index(cur), ring.index(cur+1));
+    }
+}
+
+void GrAAConvexTessellator::createOuterRing(const GrRing& ring) {
+    // For now, we're only generating one outer ring (at the start). This
+    // could be relaxed for stroking use cases.
+    SkASSERT(0 == fIndices.count());  
+
+    const int numPts = ring.numPts0();
+
+    int prev = numPts - 1;
+    int lastOut = -1, firstOut, newIdx0, newIdx1, newIdx2;
+    for (int cur = 0; cur < numPts; ++cur) {

[bsalomon, 2015/04/24 15:44:44]

Maybe an explanation somewhere that what we're doing here is adding three points
to the outset polygon at each vertex of the original polygon, one for each edge
normal and one along the bisector. Triangles are added...

[robertphillips, 2015/05/05 15:21:33]

Done.

+        SkPoint temp = ring.norm1(prev);
+        temp.scale(fTargetDepth);
+        temp += this->point(ring.index(cur));
+
+        if (lastOut > -1 && duplicate_pt(temp, this->point(lastOut))) {

[bsalomon, 2015/04/24 15:44:44]

"With a very shallow angle between two edges, the outset points may be very
close and should fuse"?

As discussed, can probably remove the lastOut tracking and just compare
norm-outsets vs bisector outsets within an iteration.

[robertphillips, 2015/05/05 15:21:32]

Done-ish. I think it is still useful to track the last perpendicular point in
order to create the trailing edge triangles but I have removed the comparison of
the last perpendicular outset pt of the last point with the first perpendicular
outset pt of the current point.

+            SkASSERT(lastOut == this->numPts()-1);
+            newIdx0 = this->numPts()-1;
+        } else {
+            newIdx0 = this->addPt(temp, -fTargetDepth, false);
+        }
+
+        temp = ring.bisector(cur);
+        temp.scale(-fTargetDepth);  // the bisectors point in
+        temp +=  this->point(ring.index(cur)); 
+
+        if (duplicate_pt(temp, this->point(newIdx0))) {
+            newIdx1 = newIdx0;
+        } else {
+            newIdx1 = this->addPt(temp, -fTargetDepth, false);
+        }
+
+        temp = ring.norm1(cur);
+        temp.scale(fTargetDepth);
+        temp +=  this->point(ring.index(cur)); 
+
+        if (duplicate_pt(temp, this->point(newIdx1))) {
+            newIdx2 = newIdx1;
+        } else {
+            newIdx2 = this->addPt(temp, -fTargetDepth, false);
+        }
+
+        // The previous edge
+        if (lastOut != -1) {
+            this->addTri(ring.index(prev), newIdx0, ring.index(cur));
+            this->addTri(ring.index(prev), lastOut, newIdx0);
+        } else {
+            firstOut = newIdx0;
+        }
+
+        // The cap around the corner
+        this->addTri(ring.index(cur), newIdx0, newIdx1);
+        this->addTri(ring.index(cur), newIdx1, newIdx2);
+
+        prev = cur;
+        lastOut = newIdx2;
+    }
+
+    // pick up the final edge rect
+    this->addTri(ring.index(numPts-1), firstOut, ring.index(0));
+    this->addTri(ring.index(numPts-1), lastOut, firstOut);
+
+    this->validate();
+}
+
+// return true when processing is complete
+bool GrAAConvexTessellator::createInsetRing(const GrRing& lastRing, GrRing* nextRing) {
+    bool done = false;
+
+    // Loop through all the points in the ring and find the intersection with the smallest depth
+    SkScalar minDist = SK_ScalarMax, minT;
+    int minEdgeIdx;
+
+    for (int cur = 0; cur < lastRing.numPts0(); ++cur) {
+        int next = (cur + 1) % lastRing.numPts0();

[bsalomon, 2015/04/24 15:44:44]

wonder if we can avoid int mod.

+
+        SkScalar t = intersect(this->point(lastRing.index(cur)),  lastRing.bisector(cur),
+                               this->point(lastRing.index(next)), lastRing.bisector(next));
+        SkScalar dist = -t * lastRing.norm1(cur).dot(lastRing.bisector(cur));
+
+        if (minDist > dist) {
+            minDist = dist;
+            minT = t;
+            minEdgeIdx = cur;
+        }
+    }
+
+    SkPoint newPt = lastRing.bisector(minEdgeIdx);
+    newPt.scale(minT);
+    newPt += this->point(lastRing.index(minEdgeIdx));
+
+    SkScalar depth = fInitialRing.computeDepthFromEdge(*this,
+                                                       lastRing.origEdgeID(minEdgeIdx), 
+                                                       newPt);
+    // TODO: if this assert consistently holds we don't need the above computeDepthFromEdge
+    SkASSERT(SkScalarNearlyEqual(depth, minDist + this->depth(lastRing.index(minEdgeIdx))));
+
+    if (depth >= fTargetDepth) {
+        // None of the bisectors intersect before reaching the desired depth.
+        // Just step them all to the desired depth
+        depth = fTargetDepth;
+        done = true;
+    }
+
+    // 'dst' is the index into the vertex array each point in the current poly maps to/

[bsalomon, 2015/04/24 15:44:44]

maybe say "... in the last ring maps to/transforms into in the next ring."?

[robertphillips, 2015/05/05 15:21:32]

Done.

+    // transforms into
+    // TODO: can/should 'dst' be moved into the GrRing?
+    SkTDArray<int> dst;
+    dst.setCount(lastRing.numPts0());
+
+    // Check on the first point (who compares with no one)
+    newPt = this->computePtAlongBisector(lastRing.index(0),
+                                         lastRing.bisector(0),
+                                         lastRing.origEdgeID(0),
+                                         depth);
+    dst[0] = nextRing->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.numPts0()-1; ++cur) {
+        newPt = this->computePtAlongBisector(lastRing.index(cur),
+                                             lastRing.bisector(cur),
+                                             lastRing.origEdgeID(cur),
+                                             depth);
+        if (!duplicate_pt(newPt, nextRing->lastPoint())) {
+            dst[cur] = nextRing->addNewPt(newPt,
+                                          lastRing.index(cur), lastRing.origEdgeID(cur),
+                                          !this->movable(lastRing.index(cur)));
+        } else {
+            dst[cur] = nextRing->fuseWithPrior(lastRing.origEdgeID(cur));
+        }
+    }
+
+    // Check on the last point (handling the wrap around)
+    int cur = lastRing.numPts0()-1;
+    newPt = this->computePtAlongBisector(lastRing.index(cur),
+                                         lastRing.bisector(cur),
+                                         lastRing.origEdgeID(cur),
+                                         depth);
+    bool dupPrev = duplicate_pt(newPt, nextRing->lastPoint());
+    bool dupNext = duplicate_pt(newPt, nextRing->firstPoint());
+
+    if (!dupPrev && !dupNext) {
+        dst[cur] = nextRing->addNewPt(newPt,
+                                      lastRing.index(cur), lastRing.origEdgeID(cur),
+                                      !this->movable(lastRing.index(cur)));
+    } else if (dupPrev && !dupNext) {
+        dst[cur] = nextRing->fuseWithPrior(lastRing.origEdgeID(cur));
+    } else if (!dupPrev && dupNext) {
+        dst[cur] = nextRing->fuseWithNext();
+    } else {
+        bool dupPrevVsNext = duplicate_pt(nextRing->firstPoint(), nextRing->lastPoint());
+
+        if (!dupPrevVsNext) {
+            dst[cur] = nextRing->fuseWithPrior(lastRing.origEdgeID(cur));
+        } else {
+            dst[cur] = dst[cur-1] = nextRing->fuseWithBoth();
+        }
+    }
+
+    // Fold the new ring's points into the global pool
+    for (int i = 0; i < nextRing->numPts2(); ++i) {
+        int newIdx;
+        if (nextRing->needsToBeNew(i)) {
+            // if the originating index is still valid then this point wasn't 
+            // fused (and is thus movable)
+            newIdx = this->addPt(nextRing->point(i), depth,
+                                 nextRing->originatingIdx(i) != -1);
+        } else {
+            SkASSERT(nextRing->originatingIdx(i) != -1);
+            this->updatePt(nextRing->originatingIdx(i), nextRing->point(i), depth);
+            newIdx = nextRing->originatingIdx(i);
+        }
+
+        nextRing->addIdx1(newIdx, nextRing->origEdge2(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.numPts0(); ++cur) {
+        int next = (cur + 1) % lastRing.numPts0();
+
+        this->addTri(lastRing.index(cur), lastRing.index(next), dst[next]);
+        this->addTri(lastRing.index(cur), dst[next], dst[cur]);
+    }
+
+    if (done) {
+        this->fanRing(*nextRing);
+    }
+
+    return done;
+}
+
+void GrAAConvexTessellator::validate() const {
+    SkASSERT(fPts.count() == fDepths.count());
+    SkASSERT(fPts.count() == fMovable.count());
+    SkASSERT(0 == (fIndices.count() % 3));
+}
+
+//////////////////////////////////////////////////////////////////////////////
+void GrRing::setReserve(int numPts) {
+    fIndices.setReserve(numPts);
+    fNorms.setReserve(numPts);
+    fBisectors.setReserve(numPts);
+    fOrigEdgeIds.setReserve(numPts);
+
+    fPts2.setReserve(numPts);
+    fOrigEdgeIds2.setReserve(numPts);
+    fOriginatingIdx2.setReserve(numPts);
+    fNeedsToBeNew2.setReserve(numPts);
+}
+
+void GrRing::rewind() {
+    fIndices.rewind();
+    fNorms.rewind();
+    fBisectors.rewind();
+    fOrigEdgeIds.rewind();
+
+    fPts2.rewind();
+    fOrigEdgeIds2.rewind();
+    fOriginatingIdx2.rewind();
+    fNeedsToBeNew2.rewind();
+}
+
+void GrRing::init(const GrAAConvexTessellator& tess) {
+    this->computeNormals(tess);
+    this->computeBisectors();
+    SkASSERT(this->isConvex(tess));
+}
+
+SkScalar GrRing::computeDepthFromEdge(GrAAConvexTessellator& tess,
+                                      int edgeIdx,
+                                      const SkPoint& p) const {
+    SkASSERT(edgeIdx < this->numPts0());
+
+    SkPoint v = p - tess.point(fIndices[edgeIdx]);
+    SkScalar depth = -fNorms[edgeIdx].dot(v);
+    SkASSERT(depth >= 0.0f);
+    return depth;
+}
+
+// Compute the outward facing normal at each vertex.
+void GrRing::computeNormals(const GrAAConvexTessellator& tess) {
+    fNorms.setCount(fIndices.count());
+
+    for (int cur = 0; cur < fIndices.count(); ++cur) {
+        int next = (cur + 1) % fIndices.count();
+
+        fNorms[cur] = tess.point(fIndices[next]) - tess.point(fIndices[cur]);
+        SkScalar len = SkPoint::Normalize(&fNorms[cur]);
+        SkASSERT(len > 0.0f);
+        fNorms[cur].setOrthog(fNorms[cur], fSide);
+
+        SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[cur].length()));
+    }
+}
+
+void GrRing::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];
+        fBisectors[cur].normalize();
+        fBisectors[cur].negate();      // make the bisector face in
+
+        SkASSERT(SkScalarNearlyEqual(1.0f, fBisectors[cur].length()));
+    }    
+}
+
+void GrRing::validate() const {
+    SkASSERT(fPts2.count() == fOriginatingIdx2.count());
+    SkASSERT(fPts2.count() == fOrigEdgeIds2.count());
+    SkASSERT(fPts2.count() == fNeedsToBeNew2.count());
+}
+
+//////////////////////////////////////////////////////////////////////////////
+#ifdef SK_DEBUG
+// Is this ring convex?
+bool GrRing::isConvex(const GrAAConvexTessellator& tess) const {
+    if (fIndices.count() < 3) {
+        return false;
+    }
+
+    SkPoint prev = tess.point(fIndices[0]) - tess.point(fIndices[fIndices.count()-1]);
+    SkPoint cur  = tess.point(fIndices[1]) - tess.point(fIndices[0]);
+    SkScalar minDot = prev.fX * cur.fY - prev.fY * cur.fX;
+    SkScalar maxDot = minDot;
+
+    prev = cur;
+    for (int i = 1; i < fIndices.count(); ++i) {
+        int next = (i + 1) % fIndices.count();
+
+        cur  = tess.point(fIndices[next]) - tess.point(fIndices[i]);
+        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);
+}
+
+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;
+
+    SkScalar d0 = edge.dot(testVec);
+    if (d0 < 0.0f) {
+        return SkPoint::Distance(p0, test);
+    }
+    if (d0 > len) {
+        return SkPoint::Distance(p1, test);
+    }
+
+    SkScalar perpDist = testVec.fY * edge.fX - testVec.fX * edge.fY;
+    if (SkPoint::kRight_Side == side) {
+        perpDist = -perpDist;
+    }
+
+    if (perpDist < 0.0f) {
+        perpDist = -perpDist;
+    } else {
+        *sign = 1;
+    }
+    return perpDist;
+}
+
+SkScalar GrAAConvexTessellator::computeRealDepth(const SkPoint& p) const {
+    SkScalar minDist = SK_ScalarMax;
+    int closestEdge, closestSign, sign;
+
+    for (int edge = 0; edge < fInitialRing.numPts0(); ++edge) {
+        SkScalar dist = capsule_depth(this->point(edge),
+                                      this->point((edge+1) % fInitialRing.numPts0()),
+                                      p, fInitialRing.side(), &sign);
+        SkASSERT(dist >= 0.0f);
+
+        if (minDist > dist) {
+            minDist = dist;
+            closestEdge = edge;
+            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) {
+        SkScalar realDepth = this->computeRealDepth(this->point(cur));
+        SkASSERT(SkScalarNearlyEqual(realDepth, this->depth(cur)));
+    }
+}
+#endif
+
+//////////////////////////////////////////////////////////////////////////////
+#if GR_AA_CONVEX_TESSELLATOR_VIZ
+static const SkScalar kPointRadius = 3.0f;
+static const SkScalar kArrowStrokeWidth = 0.75f;
+static const SkScalar kArrowLength = 10.0f;
+static const SkScalar kEdgeTextSize = 6.0f;
+static const SkScalar kPointTextSize = 4.0f;
+
+static void draw_point(SkCanvas* canvas, const SkPoint& p, SkScalar paramValue, bool stroke) {
+    SkPaint paint;
+    SkASSERT(paramValue <= 1.0f);
+    int gs = int(255*paramValue);
+    paint.setARGB(255, gs, gs, gs);
+
+    canvas->drawCircle(p.fX, p.fY, kPointRadius, paint);
+
+    if (stroke) {
+        SkPaint stroke;
+        stroke.setColor(SK_ColorYELLOW);
+        stroke.setStyle(SkPaint::kStroke_Style);
+        stroke.setStrokeWidth(kPointRadius/3.0f);
+        canvas->drawCircle(p.fX, p.fY, kPointRadius, stroke); 
+    }
+}
+
+static void draw_line(SkCanvas* canvas, const SkPoint& p0, const SkPoint& p1, SkColor color) {
+    SkPaint p;
+    p.setColor(color);
+
+    canvas->drawLine(p0.fX, p0.fY, p1.fX, p1.fY, p);
+}
+
+static void draw_arrow(SkCanvas*canvas, const SkPoint& p, const SkPoint &n,
+                       SkScalar len, SkColor color) {
+    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 GrRing::draw(SkCanvas* canvas, const GrAAConvexTessellator& tess) const {
+    SkPaint paint;
+    paint.setTextSize(kEdgeTextSize);
+
+    for (int cur = 0; cur < fIndices.count(); ++cur) {
+        int next = (cur + 1) % fIndices.count();
+
+        draw_line(canvas,
+                  tess.point(fIndices[cur]),
+                  tess.point(fIndices[next]),
+                  SK_ColorGREEN);
+
+        SkPoint mid = tess.point(fIndices[cur]) + tess.point(fIndices[next]);
+        mid.scale(0.5f);
+
+        if (fNorms.count()) {
+            draw_arrow(canvas, mid, fNorms[cur], kArrowLength, SK_ColorRED);
+            mid.fX += (kArrowLength/2) * fNorms[cur].fX;
+            mid.fY += (kArrowLength/2) * fNorms[cur].fY;
+        }
+
+        SkString num;
+        num.printf("%d", this->origEdgeID(cur));
+        canvas->drawText(num.c_str(), num.size(), mid.fX, mid.fY, paint);
+
+        if (fBisectors.count()) {
+            draw_arrow(canvas, tess.point(fIndices[cur]), fBisectors[cur],
+                       kArrowLength, SK_ColorBLUE);
+        }
+    }    
+}
+
+void GrAAConvexTessellator::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]),
+                  SK_ColorBLACK);
+        draw_line(canvas,
+                  this->point(this->fIndices[i+2]), this->point(this->fIndices[i]),
+                  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->movable(i));
+
+        SkPaint paint;
+        paint.setTextSize(kPointTextSize);
+        paint.setTextAlign(SkPaint::kCenter_Align);
+        if (this->depth(i) <= -fTargetDepth) {
+            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
+