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

src/gpu/GrAAConvexTessellator.h

Index: src/gpu/GrAAConvexTessellator.h
diff --git a/src/gpu/GrAAConvexTessellator.h b/src/gpu/GrAAConvexTessellator.h
new file mode 100644
index 0000000000000000000000000000000000000000..ddfd7c7145196091e3195e70b78027f5286ecbef
--- /dev/null
+++ b/src/gpu/GrAAConvexTessellator.h
@@ -0,0 +1,222 @@
+/*
+ * Copyright 2015 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef GrAAConvexTessellator_DEFINED
+#define GrAAConvexTessellator_DEFINED
+
+#include "SkColor.h"
+#include "SkPoint.h"
+#include "SkScalar.h"
+#include "SkTDArray.h"
+#include "SkTDPQueue.h"
+
+class SkCanvas;
+class SkMatrix;
+class SkPath;
+
+#define GR_AA_CONVEX_TESSELLATOR_VIZ 1
+
+class GrAAConvexTessellator;
+class GrVertInfo;
+
+class GrCandidateVert {
+public:
+    void setPt(const SkPoint& pt) { fPt = pt; }
+    const SkPoint& pt() { return fPt; }
+
+    void setBisector(const SkVector& bisector) { fBisector = bisector; }
+    const SkVector& bisector() const { return fBisector; }
+
+    void setDepth(SkScalar depth) { fDepth = depth; }
+    SkScalar depth() const { return fDepth; }
+
+    void setOriginatingPt(int idx) { fOriginatingPt = idx; }
+    int originatingPt() const { return fOriginatingPt;}
+
+    void setPrevSubsumed(GrVertInfo* prevSubsumed) { fPrevSubsumed = prevSubsumed; }
+    GrVertInfo* prevSubsumed() { return fPrevSubsumed; }
+
+    void setNextSubsumed(GrVertInfo* nextSubsumed) { fNextSubsumed = nextSubsumed; }
+    GrVertInfo* nextSubsumed() { return fNextSubsumed; }
+
+    void setPrev(GrCandidateVert* prev) { fPrev = prev; }
+    GrCandidateVert* prev() { return fPrev; }
+
+    void setNext(GrCandidateVert* next) { fNext = next; }
+    GrCandidateVert* next() { return fNext; }
+
+    static bool Less(GrCandidateVert*const& a, GrCandidateVert*const& b) {
+        return a->fDepth < b->fDepth;
+    }
+    static int* AccessIndex(GrCandidateVert* const& a) {
+        return &a->fQueueIndex;
+    }
+
+    void computeIntersection();
+
+    void recomputeBi();
+
+protected:
+
+private:
+    SkPoint          fPt;
+    SkVector         fBisector;
+    SkScalar         fDepth;
+    int              fOriginatingPt;
+    int              fEdgeId;
+
+    // segment subsumed
+    GrVertInfo*      fPrevSubsumed;
+    GrVertInfo*      fNextSubsumed;
+
+    // DLL
+    GrCandidateVert* fPrev;
+    GrCandidateVert* fNext;
+
+    int              fQueueIndex;
+};
+
+class GrVertInfo {
+public:
+    void setOriginatingPt(int index) { fIndex1 = index; }
+    int originatingPt() const { return fIndex1; }
+
+    void setBisector(const SkVector& bisector) { fBisector = bisector; }
+    const SkVector& bisector() const { return fBisector; }
+
+    void setEdgeId(int edgeId) { fEdgeId = edgeId; }
+    int edgeId() const { return fEdgeId; }
+
+    void setPrev(GrVertInfo* prev) { fPrev = prev; }
+    void setNext(GrVertInfo* next) { fNext = next; }
+
+
+    GrVertInfo* prev() { return fPrev; }
+    GrVertInfo* next() { return fNext; }
+
+    void updateGeometry(const GrAAConvexTessellator& tess);
+//    void computeIntersection(const GrAAConvexTessellator& tess);
+
+private:
+    int         fIndex1;
+    SkVector    fBisector;
+    int         fEdgeId;
+
+    GrVertInfo* fPrev;
+    GrVertInfo* fNext;
+
+};
+
+// The GrAAConvexTessellator holds:
+//      the global pool of vertices 
+//      the triangle indices
+class GrAAConvexTessellator {
+public:
+    GrAAConvexTessellator(SkScalar targetDepth = 0.5f) : fTargetDepth(targetDepth), fFree(NULL) { }
+
+    void setTargetDepth(SkScalar targetDepth) { fTargetDepth = targetDepth; }
+    SkScalar targetDepth() const { return fTargetDepth; }
+
+    bool tessellate(const SkMatrix& m, const SkPath& path);
+
+    // The next seven should only be called after tessellate
+    int numPts() const { return fPts.count(); }
+    int numIndices() const { return fIndices.count(); }
+
+    const SkPoint& point(int index) const { return fPts[index]; }
+    int index(int index) const { return fIndices[index]; }
+    SkScalar depth(int index) const {return fDepths[index]; }
+
+    SkScalar computeDepthFromEdge(int edgeIdx, const SkPoint& p) const;
+
+#if GR_AA_CONVEX_TESSELLATOR_VIZ
+    void draw(SkCanvas* canvas) const;
+#endif
+
+    void rewind();
+
+private:
+    int addPt(const SkPoint& pt, SkScalar depth);
+    void popLastPt();
+    void popFirstPtShuffle();
+
+    void addTri(int i0, int i1, int i2);
+
+    void reservePts(int count) {
+        fPts.setReserve(count);
+        fDepths.setReserve(count);  
+    }
+
+
+    SkPoint computePtAlongBisector(int startIdx, const SkPoint& bisector,
+                                   int edgeIdx, SkScalar desiredDepth) const;
+
+    // return false on failure/degenerate path
+    bool extractFromPath(const SkMatrix& m, const SkPath& path);
+    void computeNormals();
+    void computeBisectors();
+    void initPQueue();
+    void createOuterRing();
+    void stepAllIn();
+    void removeDups(GrVertInfo* start, int* trailingIdx);
+    void removeDups2(GrVertInfo* start, int* trailingIdx);
+    void createInsetRing();
+
+    void createCandidate(GrVertInfo* v, GrCandidateVert** prev,
+                         GrCandidateVert* next, bool checkNext);
+    void recompute(GrCandidateVert* v);
+
+    void validate() const;
+
+#if GR_AA_CONVEX_TESSELLATOR_VIZ
+    void drawInitialPoly(SkCanvas* canvas) const;
+#endif
+
+#ifdef SK_DEBUG
+    SkScalar computeRealDepth(const SkPoint& p) const;
+    void checkAllDepths() const;
+#endif
+
+    // fPts, fWeights & fMovable should always have the same # of elements
+    SkTDArray<SkPoint>    fPts;
+    SkTDArray<SkScalar>   fDepths;
+
+    // The triangle indices
+    SkTDArray<int>        fIndices;
+
+    // The outward facing normals for the original polygon
+    SkTDArray<SkVector>   fNorms;
+    // The inward facing bisector at each point in the original polygon
+    SkTDArray<SkVector>   fBisectors;
+    SkPoint::Side         fSide;    // winding of the original polygon
+
+    typedef SkTDPQueue<GrCandidateVert*, GrCandidateVert::Less, GrCandidateVert::AccessIndex> VertPQueue;
+
+    VertPQueue            fPQueue;  // pointers to GrVertInfos
+    SkTDArray<GrCandidateVert> fCandidates1;
+    GrCandidateVert*      fFree;
+
+    GrCandidateVert* get() {
+        SkASSERT(fFree);
+        GrCandidateVert* tmp = fFree;
+        fFree = fFree->next();
+        return tmp;
+    }
+
+    void release(GrCandidateVert* v) {
+        v->setNext(fFree);
+        fFree = v;
+    }
+
+    SkTDArray<GrVertInfo> fVerts1;   // the actual verts
+
+    SkScalar              fTargetDepth;
+};
+
+
+#endif
+