Add GrAAConvexTessellator class

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..b888d6d142b83c99132fd8d5e603db582ad98806
--- /dev/null
+++ b/src/gpu/GrAAConvexTessellator.h
@@ -0,0 +1,258 @@
+/*
+ * 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"
+
+class SkCanvas;
+class SkMatrix;
+class SkPath;
+
+#define GR_AA_CONVEX_TESSELLATOR_VIZ 1
+
+class GrAAConvexTessellator;
+
+// The GrAAConvexTessellator holds the global pool of vertices. The GrRing
+// holds a set of indices into that global pool that together define a
+// single polygon inset.
+class GrRing {

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

Seems like Ring should be a nested class of GrAACT and could be forward decl in
the .h and defined in the .cpp?

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

Done. The GrAACT does need to know the size but I have nested it inside.

+public:
+    GrRing() : fSide(SkPoint::kOn_Side) {}
+
+    void setSide(SkPoint::Side side) { fSide = side; }
+    SkPoint::Side side() const { return fSide; }
+
+    void setReserve(int numPts);
+    void rewind();
+
+    int numPts0() const { return fIndices.count(); }
+
+    void addIdx1(int index, int origEdgeId) {
+        *fIndices.push() = index;
+        *fOrigEdgeIds.push() = origEdgeId;
+    }
+
+    // init should be called after all the indices have been added (via addIdx)
+    void init(const GrAAConvexTessellator& tess);
+
+    const SkPoint& norm1(int index) const { return fNorms[index]; }
+    const SkPoint& bisector(int index) const { return fBisectors[index]; }
+    int index(int index) const { return fIndices[index]; }
+    int origEdgeID(int index) const { return fOrigEdgeIds[index]; }
+
+    // only call after 'init'
+    SkScalar computeDepthFromEdge(GrAAConvexTessellator& tess,
+                                    int edgeIdx, const SkPoint& p) const;
+
+#if GR_AA_CONVEX_TESSELLATOR_VIZ
+    void draw(SkCanvas* canvas, const GrAAConvexTessellator& tess) const;
+#endif
+
+    int numPts2() const { return fPts2.count(); }
+
+    const SkPoint& lastPoint() const { return fPts2[fPts2.count()-1];}
+    const SkPoint& firstPoint() const { return fPts2[0]; }
+    const SkPoint& point(int index) const { return fPts2[index]; }
+
+    int originatingIdx(int index) const {
+        return fOriginatingIdx2[index];
+    }
+
+    int origEdge2(int index) const {
+        return fOrigEdgeIds2[index];
+    }
+
+    bool needsToBeNew(int index) const {
+        return fNeedsToBeNew2[index];
+    }
+
+    int addNewPt(const SkPoint& newPt, int originatingIdx, int origEdge, bool needsToBeNew) {
+        *fPts2.push() = newPt;
+        *fOrigEdgeIds2.push() = origEdge;
+        *fOriginatingIdx2.push() = originatingIdx;
+        *fNeedsToBeNew2.push() = needsToBeNew;
+        return fPts2.count() - 1;
+    }
+
+    int fuseWithPrior(int origEdgeId) {
+        this->validate();
+
+        fOrigEdgeIds2[fOrigEdgeIds2.count()-1] = origEdgeId;
+        fOriginatingIdx2[fOriginatingIdx2.count()-1] = -1;
+        fNeedsToBeNew2[fNeedsToBeNew2.count()-1] = true;
+        return fPts2.count() - 1;
+    }
+
+    int fuseWithNext() {
+        this->validate();
+
+        fOriginatingIdx2[0] = -1;
+        fNeedsToBeNew2[0] = true;
+        return 0;
+    }
+
+    int fuseWithBoth() {
+        this->validate();
+
+        if (fPts2.count() > 1) {
+            fPts2.pop();
+            fOriginatingIdx2.pop();
+            fOrigEdgeIds2.pop();
+            fNeedsToBeNew2.pop();
+        }
+
+        this->validate();
+
+        fOriginatingIdx2[0] = -1;
+        fNeedsToBeNew2[0] = true;
+        return 0;
+    }
+
+private:
+    void validate() const;
+    void computeNormals(const GrAAConvexTessellator& result);
+    void computeBisectors();
+
+    bool isConvex(const GrAAConvexTessellator& tess) const;
+
+    // TODO: the ring operates in two modes: a construction phase and
+    // an information phase. The data used by the two phases is almost completely
+    // disjoint but of equal size. We could reuse the memory between the
+    // two phases.
+#if 0
+    enum RingMode {
+        InProgress_RingMode,
+        Finished_RingMode,
+        FinishedWithInfo_RingMode
+    };
+
+    typedef struct {
+        SkPoint fPt;                // new ring point not yet in the global pool
+        int     fOriginatingIdx;    // Index of the vert that was slid along the bisector for this
+                                    // point. Set to -1 if this point was fused with another.
+        int     fOrigEdgeId;        // The closest edge in fInitialRing
+        bool    fNeedsToBeNew;
+    } InProgressInfo;
+
+    typedef struct {
+        SkPoint fNorm;
+        SkPoint fBisector;
+        int     fIndex;              // index of the point in the global pool
+        int     fOrigEdgeId;         // The closest edge in fInitialRing
+    } FinishedInfo;
+
+    RingMode           fMode;
+
+    typedef union {
+        InProgressInfo fIPI;
+        FinishedInfo   fFI;
+    } SingleEntry;
+
+    SkTDArray<SingleEntry> fVertInfo;
+#endif
+
+    SkPoint::Side      fSide;
+
+    SkTDArray<SkPoint> fPts2;
+    SkTDArray<int>     fOriginatingIdx2;
+    SkTDArray<int>     fOrigEdgeIds2;
+    SkTDArray<bool>    fNeedsToBeNew2;
+
+    SkTDArray<SkPoint> fNorms;
+    SkTDArray<SkPoint> fBisectors;
+    SkTDArray<int>     fIndices;
+    SkTDArray<int>     fOrigEdgeIds;
+
+};
+
+
+class GrAAConvexTessellator {
+public:
+    GrAAConvexTessellator(SkScalar targetDepth = 0.5f) : fTargetDepth(targetDepth) { }
+
+    void setTargetDepth(SkScalar targetDepth) { fTargetDepth = targetDepth; }
+    SkScalar targetDepth() const { return fTargetDepth; }
+
+    bool tessellate(const SkMatrix& m, const SkPath& path);
+
+    // The next five 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]; }
+
+#if GR_AA_CONVEX_TESSELLATOR_VIZ
+    void draw(SkCanvas* canvas) const;
+#endif
+
+private:
+    const SkPoint& lastPoint() const { return fPts.top(); }
+    SkScalar depth(int index) const { return fDepths[index]; }
+    bool movable(int index) const { return fMovable[index]; }
+
+    int addPt(const SkPoint& pt, SkScalar depth, bool movable);

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

comment about what movable means?

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

Done.

+    void popLastPt();
+    void popFirstPtShuffle();
+
+    void updatePt(int index, const SkPoint& pt, SkScalar depth);
+
+    void addTri(int i0, int i1, int i2);
+
+    void reservePts(int count) {
+        fPts.setReserve(count);
+        fDepths.setReserve(count);  
+        fMovable.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 fanRing(const GrRing& ring);
+    void createOuterRing(const GrRing& ring);
+
+    GrRing* getNextRing(GrRing* lastRing);
+
+    bool createInsetRing(const GrRing& lastRing, GrRing* nextRing);
+
+    void validate() const;
+
+#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;
+    // movable points are those that can be slid further along their bisector
+    SkTDArray<bool>     fMovable;
+
+    SkTDArray<int>      fIndices;
+
+    GrRing              fInitialRing;
+#if GR_AA_CONVEX_TESSELLATOR_VIZ
+    // When visualizing save all the rings
+    SkTDArray<GrRing*>  fRings;
+#else
+    GrRing              fRings[2];
+#endif
+
+    SkScalar            fTargetDepth;
+};
+
+
+#endif
+