Refugee from Dead Machine 13: New version of the convex AA tessellator

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 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);
+
+static void intersect2(const SkPoint& p0, const SkPoint& n0,
+                       const SkPoint& p1, const SkPoint& n1,
+                       SkScalar* t0) {
+    SkASSERT(SkScalarNearlyEqual(n0.lengthSqd(), 1.0f));
+    SkASSERT(SkScalarNearlyEqual(n1.lengthSqd(), 1.0f));
+
+    const SkPoint v = p1 - p0;
+
+    SkScalar perpDot = n0.fX * n1.fY - n0.fY * n1.fX;
+    *t0 = (v.fX * n1.fY - v.fY * n1.fX) / perpDot;
+
+    if (*t0 < 0.0f) {
+        *t0 = 100000;
+    }
+//    SkASSERT(*t0 >= 0.0f);
+}
+
+static void intersect(const SkPoint& p0, const SkPoint& n0,
+                      const SkPoint& p1, const SkPoint& n1,
+                      SkScalar* t0, SkScalar* t1) {
+    SkASSERT(SkScalarNearlyEqual(n0.lengthSqd(), 1.0f));
+    SkASSERT(SkScalarNearlyEqual(n1.lengthSqd(), 1.0f));
+
+    const SkPoint v = p1 - p0;
+
+    SkScalar perpDot = n0.fX * n1.fY - n0.fY * n1.fX;
+    *t0 = (v.fX * n1.fY - v.fY * n1.fX) / perpDot;
+    *t1 = (v.fX * n0.fY - v.fY * n0.fX) / perpDot;
+
+    SkASSERT(*t0 >= 0.0f && *t1 >= 0.0f);
+}
+
+// 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) {
+    SkASSERT(SkScalarNearlyEqual(n0.lengthSqd(), 1.0f));
+    SkASSERT(SkScalarNearlyEqual(perp.lengthSqd(), 1.0f));
+
+    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) {
+    // 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) {
+    this->validate();
+
+    int index = fPts.count();
+    *fPts.push() = pt;
+    *fDepths.push() = depth;
+
+    this->validate();
+    return index;
+}
+
+void GrAAConvexTessellator::popLastPt() {
+    this->validate();
+
+    fPts.pop();
+    fDepths.pop();
+
+    this->validate();
+}
+
+void GrAAConvexTessellator::popFirstPtShuffle() {
+    this->validate();
+
+    fPts.removeShuffle(0);
+    fDepths.removeShuffle(0);
+
+    this->validate();
+}
+
+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();
+    fIndices.rewind();
+    fNorms.rewind();
+    fBisectors.rewind();
+
+    fPQueue.rewind();
+    fVerts1.rewind();
+}
+
+void GrAAConvexTessellator::computeNormals() {
+    int numPts = this->numPts();
+
+    fNorms.setCount(numPts);
+
+    for (int cur = 0; cur < numPts; ++cur) {
+        int next = (cur + 1) % numPts;
+
+        fNorms[cur] = fPts[next] - fPts[cur];
+        SkDEBUGCODE(SkScalar len =) SkPoint::Normalize(&fNorms[cur]);
+        SkASSERT(len > 0.0f);
+        fNorms[cur].setOrthog(fNorms[cur], fSide);
+
+        SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[cur].length()));
+    }
+}
+
+void GrAAConvexTessellator::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()));
+    }    
+}
+
+// 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.
+bool GrAAConvexTessellator::tessellate(const SkMatrix& m, const SkPath& path) {
+    if (!this->extractFromPath(m, path)) {
+        return false;
+    }
+
+    this->computeNormals();
+    this->computeBisectors();
+    this->initPQueue();
+
+    this->createOuterRing();
+    this->createInsetRing();
+
+    this->validate();
+    SkDEBUGCODE(this->checkAllDepths();)
+    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.
+SkPoint GrAAConvexTessellator::computePtAlongBisector(int startIdx,
+                                                      const SkVector& bisector,
+                                                      int edgeIdx,
+                                                      SkScalar desiredDepth) 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());
+        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;
+
+    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], fPts.top())) {
+                    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);
+
+                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) {
+                        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;
+        }
+    }
+
+    if (!this->numPts()) {
+        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();
+    }
+
+    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();
+    }
+
+    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;
+    }
+
+    if (maxCross > 0.0f) {
+        SkASSERT(minCross >= 0.0f);
+        fSide = SkPoint::kRight_Side;
+    } else {
+        SkASSERT(minCross <= 0.0f);
+        fSide = SkPoint::kLeft_Side;
+    }
+
+    this->validate();
+    return true;
+}
+
+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();
+
+    // 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, 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];
+
+        // 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);
+
+        // 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, fPts[newIdx0])) {
+            newIdx1 = newIdx0;
+        } else {
+            newIdx1 = this->addPt(temp, -fTargetDepth);
+        }
+
+        // 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, fPts[newIdx1])) {
+            newIdx2 = newIdx1;
+        } else {
+            newIdx2 = this->addPt(temp, -fTargetDepth);
+        }
+
+        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->validate();
+}
+
+
+void GrAAConvexTessellator::stepAllIn() {
+#if 1
+    //SkASSERT(fPQueue.count() >= 3);
+
+    // 'dst' is the index into the vertex array each point in the last ring
+    // maps to/transforms into in the next ring.
+    SkTDArray<int> dst;
+    dst.setCount(fVerts1.count());
+    SkTDArray<SkPoint> pts;
+    pts.setReserve(fVerts1.count());
+
+    GrVertInfo* first = &fVerts1[0];
+
+    // Check on the first point (who compares with no one)
+    SkPoint newPt = this->computePtAlongBisector(first->originatingPt(),
+                                                 first->bisector(),
+                                                 first->edgeId(),
+                                                 fTargetDepth);
+    dst[0] = 0;
+    *pts.push() = newPt;
+
+    GrVertInfo* cur;
+    int i;
+    // Handle the middle points (who only compare with the prior point)
+    for (i = 1, cur = first->next(); cur != first->prev(); ++i, cur=cur->next()) {
+        newPt = this->computePtAlongBisector(cur->originatingPt(),
+                                             cur->bisector(),
+                                             cur->edgeId(),
+                                             fTargetDepth);
+        if (!duplicate_pt(newPt, pts.top())) {
+            dst[i] = pts.count();
+            *pts.push() = newPt;
+        } else {
+            dst[i] = pts.count()-1;
+        }    
+    }
+    SkASSERT(i == fVerts1.count()-1);
+
+    // Check on the last point (handling the wrap around)
+    newPt = this->computePtAlongBisector(first->prev()->originatingPt(),
+                                         first->prev()->bisector(),
+                                         first->prev()->edgeId(),
+                                         fTargetDepth);
+    bool dupPrev = duplicate_pt(newPt, pts.top());
+    bool dupNext = duplicate_pt(newPt, pts[0]);
+
+    if (!dupPrev && !dupNext) {
+        dst.top() = pts.count();
+        *pts.push() = newPt;
+    } else if (dupPrev && !dupNext) {
+        dst.top() = pts.count()-1;
+    } else if (!dupPrev && dupNext) {
+        dst.top() = 0;
+    } else {
+        bool dupPrevVsNext = duplicate_pt(pts[0], pts.top());
+
+        if (!dupPrevVsNext) {
+            dst.top() = pts.count()-1;
+        } else {
+            if (pts.count() > 1) {
+                pts.pop();
+            }
+
+            dst.top() = 0;
+            dst[dst.count()-2] = 0;
+        }
+    }
+
+    SkTDArray<int> remap;  // yuck
+    remap.setCount(pts.count());
+
+    // Fold the new ring's points into the global pool
+    for (int i = 0; i < pts.count(); ++i) {
+        remap[i] = this->addPt(pts[i], fTargetDepth);
+    }
+
+    // '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] = remap[dst[i]];
+    }
+
+    this->addTri(first->originatingPt(), first->next()->originatingPt(), dst[0]);
+    this->addTri(dst[0], first->next()->originatingPt(), dst[1]);
+
+    for (i = 1, cur = first->next(); cur != first; ++i, cur=cur->next()) {
+        this->addTri(cur->originatingPt(), cur->next()->originatingPt(), dst[i]);
+        this->addTri(dst[i], cur->next()->originatingPt(), dst[(i+1)%dst.count()]); 
+    }
+
+    // fan out from point 0
+    for (int cur = 1; cur < remap.count()-1; ++cur) {
+        this->addTri(remap[0], remap[cur], remap[cur+1]);
+    }
+#endif
+}
+
+static void add_to_dll(GrCandidateVert* prev, GrCandidateVert* newV, GrCandidateVert* next) {
+    SkASSERT(newV);
+
+    newV->setPrev(prev);
+    newV->setNext(next);
+
+    if (prev) {
+        prev->setNext(newV);
+    }
+    if (next) {
+        next->setPrev(newV);
+    }
+}
+
+static void rm_from_dll(GrCandidateVert* v) {
+    if (v->prev()) {
+        v->prev()->setNext(v->next());
+    }
+    if (v->next()) {
+        v->next()->setPrev(v->prev());
+    }
+}
+
+void GrAAConvexTessellator::createCandidate(GrVertInfo* v, GrCandidateVert** prev,
+                                            GrCandidateVert* next, bool checkNext){
+    SkScalar tPrev, tNext;
+    intersect2(this->point(v->originatingPt()), v->bisector(),
+                this->point(v->prev()->originatingPt()), v->prev()->bisector(),
+                &tPrev);
+    intersect2(this->point(v->originatingPt()), v->bisector(),
+                this->point(v->next()->originatingPt()), v->next()->bisector(),
+                &tNext);
+
+    SkScalar t;
+    GrVertInfo* prevSubsumed, *nextSubsumed;
+    if (tPrev < tNext) {
+        t = tPrev;
+        prevSubsumed = v->prev();
+        nextSubsumed = v;
+    } else {
+        t = tNext;
+        prevSubsumed = v;
+        nextSubsumed = v->next();
+    }
+
+    SkPoint newPt = v->bisector();
+    newPt.scale(t);
+    newPt += this->point(v->originatingPt());
+
+    SkScalar depth = this->computeDepthFromEdge(v->edgeId(), newPt);
+
+    if (SkScalarNearlyEqual(depth, (*prev)->depth(), kClose) &&
+        duplicate_pt((*prev)->pt(), newPt)) {
+        (*prev)->setNextSubsumed(v);
+        (*prev)->recomputeBi();
+        return;
+    }
+
+    if (checkNext && SkScalarNearlyEqual(depth, next->depth(), kClose) &&
+        duplicate_pt(next->pt(), newPt)) {
+        next->setPrevSubsumed(v);
+        next->recomputeBi();
+        return;
+    }
+
+    GrCandidateVert* newI = this->get();
+
+    newI->setPt(newPt);
+    newI->setBisector(v->bisector());
+    newI->setDepth(depth);
+    newI->setOriginatingPt(v->originatingPt());
+    newI->setPrevSubsumed(prevSubsumed);
+    newI->setNextSubsumed(nextSubsumed);
+    add_to_dll(*prev, newI, next);
+
+    fPQueue.insert(newI);
+    *prev = newI;
+}
+
+void GrAAConvexTessellator::recompute(GrCandidateVert* v) {
+
+    GrVertInfo* from = v->prevSubsumed();
+    GrVertInfo* to = v->nextSubsumed();
+
+    GrCandidateVert* trailing = v->prev();
+    GrCandidateVert* leading = v->next();
+
+    // First retract 'v'
+    rm_from_dll(v);
+    fPQueue.remove(v);
+    this->release(v);
+
+    for (GrVertInfo* cur = from; cur != to; cur = cur->next()) {
+        this->createCandidate(cur, &trailing, leading, false);
+    }
+
+    this->createCandidate(to, &trailing, leading, true);
+}
+
+void GrAAConvexTessellator::initPQueue() {
+
+    fVerts1.setCount(fPts.count());
+    fCandidates1.setCount(fPts.count());
+    for (int i = fPts.count()-1; i >= 0; --i) {
+        fCandidates1[i].setOriginatingPt(i);
+        this->release(&fCandidates1[i]);
+    }
+    fPQueue.setReserve(fPts.count());
+
+    int prev = fPts.count()-1;
+    for (int cur = 0; cur < fPts.count(); prev = cur, ++cur) {
+        int next = (cur + 1) % fPts.count();
+
+        fVerts1[cur].setOriginatingPt(cur);
+        fVerts1[cur].setPrev(&fVerts1[prev]);
+        fVerts1[cur].setNext(&fVerts1[next]);
+
+        fVerts1[cur].setBisector(fBisectors[cur]);
+        fVerts1[cur].setEdgeId(cur);
+    }
+
+    SkScalar tTemp, tPrev, tNext;
+    intersect(fPts.top(), fBisectors.top(),
+              fPts[0],    fBisectors[0],
+              &tTemp, &tPrev);
+
+    GrCandidateVert* prevI = NULL;
+
+    // Add all the candidate points to a priority queue sorted by the depth of the first
+    // intersection between the bisector of its originating point and its two neighbor's bisectors
+    for (int cur = 0; cur < fPts.count(); ++cur) {
+        int next = (cur + 1) % fPts.count();
+
+        intersect(fPts[cur],  fBisectors[cur],
+                  fPts[next], fBisectors[next],
+                  &tNext, &tTemp);
+
+        SkScalar t;
+        GrVertInfo* prevSubsumed, *nextSubsumed;
+        if (tPrev < tNext) {
+            t = tPrev;
+            prevSubsumed = fVerts1[cur].prev();
+            nextSubsumed = &fVerts1[cur];
+        } else {
+            t = tNext;
+            prevSubsumed = &fVerts1[cur];
+            nextSubsumed = fVerts1[cur].next();
+        }
+
+        SkPoint newPt = fBisectors[cur];
+        newPt.scale(t);
+        newPt += fPts[cur];
+
+        SkScalar depth = this->computeDepthFromEdge(cur, newPt);
+
+        if (prevI && duplicate_pt(prevI->pt(), newPt)) {
+            SkASSERT(SkScalarNearlyEqual(prevI->depth(), depth));
+            // fuse with prior
+            prevI->setNextSubsumed(nextSubsumed);
+            SkVector newBi = prevI->prevSubsumed()->bisector();
+            newBi += prevI->nextSubsumed()->bisector();
+            newBi.normalize();
+            prevI->setBisector(newBi);
+            tPrev = tTemp;
+            continue;
+        }
+
+        GrCandidateVert* newI = this->get();
+
+        newI->setPt(newPt);
+        newI->setBisector(fBisectors[cur]);
+        newI->setDepth(depth);
+        newI->setOriginatingPt(cur);
+        newI->setPrevSubsumed(prevSubsumed);
+        newI->setNextSubsumed(nextSubsumed);
+        add_to_dll(prevI, newI, NULL);
+
+        fPQueue.insert(newI);
+
+        prevI = newI;
+        tPrev = tTemp;
+    }
+
+    prevI->setNext(&fCandidates1[0]);
+    fCandidates1[0].setPrev(prevI);
+
+    if (fCandidates1.count() > 1) {
+        if (duplicate_pt(prevI->pt(), fCandidates1[0].pt())) {
+            SkASSERT(SkScalarNearlyEqual(prevI->depth(), fCandidates1[0].depth()));
+
+            fCandidates1[0].setPrevSubsumed(prevI->prevSubsumed());
+            SkVector newBi = fCandidates1[0].prevSubsumed()->bisector();
+            newBi += fCandidates1[0].nextSubsumed()->bisector();
+            newBi.normalize();
+            fCandidates1[0].setBisector(newBi);
+            rm_from_dll(prevI);
+            fPQueue.remove(prevI);
+            this->release(prevI);
+        }
+    }
+}
+
+static void rm_from_dllV(GrVertInfo* v) {
+    v->prev()->setNext(v->next());
+    v->next()->setPrev(v->prev());
+    v->setNext(NULL);
+    v->setPrev(NULL);
+}
+
+static void add_to_dllV(GrVertInfo* v, GrVertInfo* prev, GrVertInfo* next) {
+    v->setPrev(prev);
+    v->setNext(next);
+
+    prev->setNext(v);
+    next->setPrev(v);
+}
+
+void GrAAConvexTessellator::removeDups(GrVertInfo* start, int* trailingIdx) {
+#if 0    
+    GrVertInfo* next;
+    for (GrVertInfo* cur = start->next(); cur != start; cur = next) {
+        next = cur->next();
+
+        if (!duplicate_pt(start->newPt(), cur->newPt())) {
+            return;  // found a non-duplicate
+        }
+
+        SkASSERT(SkScalarNearlyEqual(start->depth(), cur->depth(), kClose));
+        this->addTri(*trailingIdx, cur->index1(), start->index1());
+        fPQueue.remove(cur);
+        *trailingIdx = cur->index1();
+        rm_from_dll(cur);
+    }
+#endif
+}
+
+void GrAAConvexTessellator::removeDups2(GrVertInfo* start, int* trailingIdx) {
+#if 0
+    GrVertInfo* prev;
+    for (GrVertInfo* cur = start->next(); cur != start; cur = prev) {
+        prev = cur->prev();
+
+        if (!duplicate_pt(start->newPt(), cur->newPt())) {
+            return;  // found a non-duplicate
+        }
+
+        SkASSERT(SkScalarNearlyEqual(start->depth(), cur->depth()));
+        this->addTri(*trailingIdx, cur->index1(), start->index1());
+        fPQueue.remove(cur);
+        *trailingIdx = cur->index1();
+        rm_from_dll(cur);
+    }
+#endif
+}
+
+void GrAAConvexTessellator::createInsetRing() {
+
+#if 0
+    while (fPQueue.count()) {
+        GrCandidateVert* curI = fPQueue.peek();
+
+        int newIdx = this->addPt(curI->pt(), curI->depth());
+        SkDebugf("newIdx %d\n", newIdx);
+
+        fPQueue.pop();
+    }
+
+    return;
+#endif
+
+    int floob = 0;
+    while (fPQueue.count() && floob < 4) {
+        floob++;
+
+        GrCandidateVert* curI = fPQueue.peek();
+        fPQueue.pop();
+        rm_from_dll(curI);
+
+        if (curI->depth() >= fTargetDepth) {
+            // None of the bisectors intersect before reaching the desired depth.
+            // Just step them all to the desired depth
+            this->stepAllIn();
+            return;
+        }
+
+
+        int newIdx = this->addPt(curI->pt(), curI->depth());
+
+        GrVertInfo* prev = curI->prevSubsumed();
+        GrVertInfo* next = curI->nextSubsumed();
+        int newEdgeId = next->edgeId();
+        GrVertInfo* pp = prev->prev();
+        GrVertInfo* nn = next->next();
+
+#if 0
+        SkVector newBisector = prev->bisector();
+        newBisector += next->bisector();
+        newBisector.normalize();
+#endif
+
+        if (!fPQueue.count()) {
+            GrVertInfo* foo = prev; 
+            do {
+                this->addTri(foo->originatingPt(), foo->next()->originatingPt(), newIdx);
+                foo = foo->next();
+            } while (foo != next);
+            return;
+        }
+
+        bool nextNeedsRecompute = false, prevNeedsRecompute = false;
+        if (curI->next()->prevSubsumed() == next) {
+            curI->next()->setPrevSubsumed(nn);
+            nextNeedsRecompute = true;
+        }
+        if (curI->prev()->nextSubsumed() == prev) {
+            curI->prev()->setNextSubsumed(pp);
+            prevNeedsRecompute = true;
+        }
+
+        this->addTri(pp->originatingPt(), pp->next()->originatingPt(), newIdx);
+        this->addTri(nn->prev()->originatingPt(), nn->originatingPt(), newIdx);
+
+        GrVertInfo *cur = prev, *next2;
+        do {
+            next2 = cur->next();
+            this->addTri(cur->originatingPt(), next2->originatingPt(), newIdx);
+            rm_from_dllV(cur);
+            cur = next2;
+        } while (cur != nn);
+
+        GrVertInfo* newV = prev; // recycle prev - let next and all the ones in between lie fallow
+        newV->setOriginatingPt(newIdx);
+        newV->setBisector(curI->bisector());
+        newV->setEdgeId(newEdgeId);
+        add_to_dllV(newV, pp, nn);
+
+        {
+            SkScalar tPrev, tNext;
+            intersect2(curI->pt(), curI->bisector(),
+                       this->point(pp->originatingPt()), pp->bisector(),
+                       &tPrev);
+            intersect2(curI->pt(), curI->bisector(),
+                       this->point(nn->originatingPt()), nn->bisector(),
+                       &tNext);
+
+            SkScalar t;
+            GrVertInfo* prevSubsumed, *nextSubsumed;
+            if (tPrev < tNext) {
+                t = tPrev;
+                prevSubsumed = pp;
+                nextSubsumed = newV;
+            } else {
+                t = tNext;
+                prevSubsumed = newV;
+                nextSubsumed = nn;
+            }
+
+            SkPoint newPt = newV->bisector();
+            newPt.scale(t);
+            newPt += this->point(newV->originatingPt());
+
+            SkScalar depth = this->computeDepthFromEdge(newV->edgeId(), newPt);
+
+            if (!prevNeedsRecompute && 
+                SkScalarNearlyEqual(depth, curI->prev()->depth(), kClose) &&
+                duplicate_pt(curI->prev()->pt(), newPt)) {
+                curI->prev()->setNextSubsumed(newV);
+                curI->prev()->recomputeBi();
+                continue;
+            }
+
+            if (!nextNeedsRecompute && 
+                SkScalarNearlyEqual(depth, curI->next()->depth(), kClose) &&
+                duplicate_pt(curI->next()->pt(), newPt)) {
+                curI->next()->setPrevSubsumed(newV);
+                curI->next()->recomputeBi();
+                continue;
+            }
+
+            GrCandidateVert* newI = curI; // recycle curI
+
+            newI->setPt(newPt);
+            newI->setBisector(newV->bisector());
+            newI->setDepth(depth);
+            newI->setOriginatingPt(newIdx);
+            newI->setPrevSubsumed(prevSubsumed);
+            newI->setNextSubsumed(nextSubsumed);
+            add_to_dll(newI->prev(), newI, newI->next());
+
+            fPQueue.insert(newI);
+
+            if (nextNeedsRecompute) {
+                this->recompute(newI->next());
+            }
+            if (prevNeedsRecompute) {
+                this->recompute(newI->prev());
+            }
+        }
+
+#if 0
+        fPQueue.remove(curVert);
+        fPQueue.remove(otherVert);
+        rm_from_dll(otherVert);
+#endif
+
+#if 0
+        int dyingCurIdx = curVert->index1();
+        int newIdx = this->addPt(curVert->newPt(), curVert->depth());
+
+        if (curVert->wasNext()) {
+            this->addTri(dyingCurIdx, otherVert->index1(), newIdx); // tri for the dying edge
+        } else {
+            this->addTri(otherVert->index1(), dyingCurIdx, newIdx); // tri for the dying edge
+        }
+
+        curVert->setIndex(newIdx);
+
+        int trailingIdx = curVert->prev()->index1();
+        int leadingIdx = curVert->next()->index1();
+
+        this->removeDups(curVert, &leadingIdx);
+        this->removeDups2(curVert, &trailingIdx);
+
+        if (curVert->wasNext()) {
+            this->addTri(trailingIdx, dyingCurIdx, newIdx);
+            this->addTri(newIdx, otherVert->index1(), leadingIdx);
+        } else {
+            this->addTri(trailingIdx, otherVert->index1(), newIdx);
+            this->addTri(newIdx, dyingCurIdx, leadingIdx);
+        }
+
+        if (fPQueue.count() < 2) {
+            break;
+        }
+
+        curVert->setBisector(newBisector);
+        curVert->setEdgeId(newEdgeId);
+        curVert->computeIntersection(*this);
+
+        fPQueue.insert(curVert);
+#endif
+    }
+
+    while (fPQueue.count()) {
+        GrCandidateVert* curI = fPQueue.peek();
+
+        int newIdx = this->addPt(curI->pt(), curI->depth());
+        SkDebugf("newIdx %d\n", newIdx);
+
+        fPQueue.pop();
+    }
+
+}
+
+void GrAAConvexTessellator::validate() const {
+    SkASSERT(fPts.count() == fDepths.count());
+    SkASSERT(0 == (fIndices.count() % 3));
+}
+
+//////////////////////////////////////////////////////////////////////////////
+void GrVertInfo::updateGeometry(const GrAAConvexTessellator& tess) {
+    SkVector prevV = tess.point(fPrev->originatingPt()) - tess.point(fIndex1);
+    SkVector nextV = tess.point(fNext->originatingPt()) - tess.point(fIndex1);
+
+    nextV.normalize();
+    prevV.normalize();
+    prevV += nextV;
+    fBisector = prevV;
+    fBisector.normalize();
+}
+
+
+void GrCandidateVert::recomputeBi() {
+    SkVector newBi = this->prevSubsumed()->bisector();
+    newBi += this->nextSubsumed()->bisector();
+    newBi.normalize();
+    this->setBisector(newBi);    
+}
+
+void GrCandidateVert::computeIntersection() {
+#if 0
+    SkScalar tPrev, tNext;
+    intersect2(fPt,        fBisector,
+               fPrev->fPt, fPrev->fBisector,
+               &tPrev);
+    intersect2(fPt,        fBisector,
+               fNext->fPt, fNext->fBisector,
+               &tNext);
+    SkScalar t = SkMinScalar(tPrev, tNext);
+    if (tPrev < tNext) {
+        fWasNext = false;
+    } else {
+        fWasNext = true;
+    }
+
+    fNewPt = fBisector;
+    fNewPt.scale(t);
+    fNewPt += tess.point(fIndex1);
+
+    fDepth = tess.computeDepthFromEdge(fEdgeId, fNewPt);
+#endif
+}
+
+#if 0
+void GrVertInfo::computeIntersection(const GrAAConvexTessellator& tess) {
+    SkScalar tPrev, tNext;
+    intersect2(tess.point(fIndex1),         fBisector,
+               tess.point(fPrev->index1()), fPrev->bisector(),
+               &tPrev);
+    intersect2(tess.point(fIndex1),         fBisector,
+               tess.point(fNext->index1()), fNext->bisector(),
+               &tNext);
+    SkScalar t = SkMinScalar(tPrev, tNext);
+    if (tPrev < tNext) {
+        fWasNext = false;
+    } else {
+        fWasNext = true;
+    }
+
+    fNewPt = fBisector;
+    fNewPt.scale(t);
+    fNewPt += tess.point(fIndex1);
+
+    fDepth = tess.computeDepthFromEdge(fEdgeId, fNewPt);
+}
+#endif
+
+//////////////////////////////////////////////////////////////////////////////
+#ifdef SK_DEBUG
+#if 0
+// 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);
+}
+#endif
+
+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 < fNorms.count(); ++edge) {
+        SkScalar dist = capsule_depth(fPts[edge],
+                                      fPts[(edge+1) % fNorms.count()],
+                                      p, fSide, &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));
+        realDepth++;
+//        SkASSERT(SkScalarNearlyEqual(realDepth, this->depth(cur)));
+    }
+}
+#endif
+
+//////////////////////////////////////////////////////////////////////////////
+#if GR_AA_CONVEX_TESSELLATOR_VIZ
+static const SkScalar kPointRadius = 0.02f;
+static const SkScalar kArrowStrokeWidth = 0.0f;
+static const SkScalar kArrowLength = 0.1f;
+static const SkScalar kEdgeTextSize = 0.2f;
+static const SkScalar kPointTextSize = 0.02f;
+
+static void draw_point(SkCanvas* canvas, const SkPoint& p, SkScalar paramValue) {
+    SkPaint paint;
+    if (paramValue > 1.0f) {
+        //SkASSERT(0);
+        paramValue = 1.0f;
+    }
+    int gs = int(255*paramValue);
+    paint.setARGB(255, gs, gs, gs);
+
+    canvas->drawCircle(p.fX, p.fY, kPointRadius, paint);
+}
+
+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 GrAAConvexTessellator::drawInitialPoly(SkCanvas* canvas) const {
+    SkPaint paint;
+    paint.setTextSize(kEdgeTextSize);
+
+    for (int cur = 0; cur < fNorms.count(); ++cur) {
+        int next = (cur + 1) % fNorms.count();
+
+        draw_line(canvas, this->point(cur), this->point(next), SK_ColorGREEN);
+
+        SkPoint mid = this->point(cur) + this->point(next);
+        mid.scale(0.5f);
+
+        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", cur);
+        canvas->drawText(num.c_str(), num.size(), mid.fX, mid.fY, paint);
+
+        draw_arrow(canvas, this->point(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);
+    }
+
+    this->drawInitialPoly(canvas);
+
+    for (int i = 0; i < this->numPts(); ++i) {
+        draw_point(canvas,
+                   this->point(i), 0.5f + (this->depth(i)/(2*fTargetDepth)));
+
+        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
+