diff --git a/Makefile b/Makefile
index d687e15..fa88b0a 100644
--- a/Makefile
+++ b/Makefile
@@ -3,7 +3,7 @@
 # setup our defaults
 CC := gcc
 C_INCLUDES := -Iinclude/core -Iinclude/effects -Iinclude/images -Iinclude/utils
-CFLAGS := -O2 
+CFLAGS := # -O2 
 LINKER_OPTS := -lpthread
 DEFINES := -DSK_CAN_USE_FLOAT
 HIDE = @
@@ -96,7 +96,7 @@
 TESTS_SRCS := GeometryTest.cpp MathTest.cpp MatrixTest.cpp PackBitsTest.cpp \
               Sk64Test.cpp StringTest.cpp Test.cpp UtilsTest.cpp PathTest.cpp \
               ClipCubicTest.cpp SrcOverTest.cpp StreamTest.cpp SortTest.cpp \
-			  PathMeasureTest.cpp main.cpp
+			        PathMeasureTest.cpp TriangulationTest.cpp main.cpp
 
 TESTS_SRCS := $(addprefix tests/, $(TESTS_SRCS))
 
diff --git a/src/core/Makefile.am b/src/core/Makefile.am
index 96849d1..05fc9bb 100644
--- a/src/core/Makefile.am
+++ b/src/core/Makefile.am
@@ -26,6 +26,7 @@
 SkColorFilter.cpp \
 SkColorTable.cpp \
 SkComposeShader.cpp \
+SkConcaveToTriangles.cpp \
 SkCordic.cpp \
 skCubicClipper.cpp \
 SkDebug.cpp \
diff --git a/src/core/SkConcaveToTriangles.cpp b/src/core/SkConcaveToTriangles.cpp
new file mode 100644
index 0000000..28d8a51
--- /dev/null
+++ b/src/core/SkConcaveToTriangles.cpp
@@ -0,0 +1,964 @@
+/*
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+////////////////////////////////////////////////////////////////////////////////
+// This is an implementation of the triangulation algorithm described by Alain
+// Fournier and Delfin Montuno, in "Triangulating Simple Polygons and Equivalent
+// Problems", in the ACM Transactions on Graphics, vol. 3, no. 2, April 1984,
+// pp. 153-174.
+//
+// No new vertices are created in the triangulation: triangles are constructed
+// only from the points in the original polygon, so there is no possibility for
+// cracks to develop from finite precision arithmetic.
+////////////////////////////////////////////////////////////////////////////////
+
+// TODO:
+// - RemoveDegenerateTrapezoids() was added to make the code robust, but it
+//   unfortunately introduces T-vertices. Make it robust without T-vertices.
+// - It should be easy enough to detect whether the outer contour is right- or
+//   left-handed by looking at the top vertex, which is available in the
+//   pre-sort during trapezoidization. Use this information in angleIsConvex()
+//   to allowed either handedness outer contour. In either case, though, holes
+//   need to have the opposite orientation.
+// - SkTHeapSort was broken, so I wrote a bubble sort so that I could make other
+//   things work. Use SkQSort() instead.
+// - The ActiveTrapezoid array does a linear search which is O(n) inefficient.
+//   Use SkSearch to implement O(log n) binary search and insertion sort.
+// - There is no need to use SkTDArray for everything. Use SkAutoTMalloc for
+//   everything else.
+
+#include "SkTDArray.h"
+#include "SkGeometry.h"
+#include "SkTSort.h"
+
+// This is used to prevent runaway code bugs, and can probably be removed after
+// the code has been proven robust.
+#define kMaxCount 1000
+
+#define DEBUG
+#ifdef DEBUG
+//------------------------------------------------------------------------------
+// Debugging support
+//------------------------------------------------------------------------------
+
+#include <cstdio>
+#include <stdarg.h>
+
+static int gDebugLevel = 0;   // This enables debug reporting.
+
+static void DebugPrintf(const char *format, ...) {
+    if (gDebugLevel > 0) {
+        va_list ap;
+        va_start(ap, format);
+        vprintf(format, ap);
+        va_end(ap);
+    }
+}
+
+static void FailureMessage(const char *format, ...) {
+    if (1) {
+        printf("FAILURE: ");
+        va_list ap;
+        va_start(ap, format);
+        vprintf(format, ap);
+        va_end(ap);
+    }
+}
+#else  // !DEBUG
+inline void DebugPrintf(const char *format, ...) {}
+inline void FailureMessage(const char *format, ...) {}
+#endif  // DEBUG
+
+
+// Forward declaration.
+class Vertex;
+
+
+//------------------------------------------------------------------------------
+// The Trapezoid (actually, up to two of them) is embedded into a Vertex, whose
+// point() provides the top of the Trapezoid, whereas the bottom, and the left
+// and right edges, are stored in the Trapezoid. The edges are represented by
+// their tail point; the head is the successive point modulo the number of
+// points in the polygon. Only the Y coordinate of the top and bottom are
+// relevant.
+//------------------------------------------------------------------------------
+class Trapezoid {
+public:
+    const Vertex* left()   const    { return fLeft;   }
+    const Vertex* right()  const    { return fRight;  }
+    const Vertex* bottom() const    { return fBottom; }
+    Vertex* left()                  { return fLeft;   }
+    Vertex* right()                 { return fRight;  }
+    Vertex* bottom()                { return fBottom; }
+    void   setLeft(Vertex *left)    { fLeft   = left;   }
+    void  setRight(Vertex *right)   { fRight  = right;  }
+    void setBottom(Vertex *bottom)  { fBottom = bottom; }
+    void nullify()                  { setBottom(NULL); }
+
+    bool operator<(Trapezoid &t1)   { return compare(t1) < 0; }
+    bool operator>(Trapezoid &t1)   { return compare(t1) > 0; }
+
+private:
+    Vertex *fLeft, *fRight, *fBottom;
+
+    // These return a number that is less than, equal to, or greater than zero
+    // depending on whether the trapezoid or point is to the left, on, or to the
+    // right.
+    SkScalar compare(const Trapezoid &t1) const;
+    SkScalar compare(const SkPoint &p) const;
+};
+
+
+//------------------------------------------------------------------------------
+// The ActiveTrapezoids are a sorted list containing the currently active
+// trapezoids, i.e. those that have the top, left, and right, but still need the
+// bottom. This could use some optimization, to reduce search time from O(n) to
+// O(log n).
+//------------------------------------------------------------------------------
+class ActiveTrapezoids {
+public:
+    ActiveTrapezoids() { fTrapezoids.setCount(0); }
+
+    size_t count() const { return fTrapezoids.count(); }
+
+    // Select an unused trapezoid from the Vertex vt, initialize it with the
+    // left and right edges, and insert it into the sorted list.
+    bool insertNewTrapezoid(Vertex *vt, Vertex *left, Vertex *right);
+
+    // Remove the specified Trapezoids from the active list.
+    void remove(Trapezoid *t);
+
+    // Determine whether the given point lies within any active trapezoid, and
+    // return a pointer to that Trapezoid.
+    bool withinActiveTrapezoid(const SkPoint &pt, Trapezoid **tp);
+
+    // Find an active trapezoid that contains the given edge.
+    Trapezoid* getTrapezoidWithEdge(const Vertex *edge);
+
+private:
+    // Insert the specified Trapezoid into the sorted list.
+    void insert(Trapezoid *t);
+
+    // The sorted list of active trapezoids. This is O(n), and would benefit
+    // a 2-3 tree o achieve O(log n).
+    SkTDArray<Trapezoid*> fTrapezoids;  // Fournier suggests a 2-3 tree instead.
+};
+
+
+//------------------------------------------------------------------------------
+// The Vertex is used to communicate information between the various phases of
+// triangulation.
+//------------------------------------------------------------------------------
+class Vertex {
+public:
+    enum VertexType { MONOTONE, CONVEX, CONCAVE };
+
+    Trapezoid fTrap0;
+    Trapezoid fTrap1;
+
+    const SkPoint &point() const        { return fPoint; }
+    void setPoint(const SkPoint &point) { fPoint = point; }
+
+    // The next and previous vertices around the polygon.
+    Vertex *next()                      { return fNext; }
+    Vertex *prev()                      { return fPrev; }
+    const Vertex *next() const          { return fNext; }
+    const Vertex *prev() const          { return fPrev; }
+    void setNext(Vertex *next)          { fNext = next; }
+    void setPrev(Vertex *prev)          { fPrev = prev; }
+
+    void setDone(bool done)             { fDone = done; }
+    bool done() const                   { return fDone; }
+
+    // Trapezoid accessors return non-null for any complete trapezoids.
+    void trapezoids(Trapezoid **trap0, Trapezoid **trap1) {
+        *trap0 = (fTrap0.bottom() != NULL) ? &fTrap0 : NULL;
+        *trap1 = (fTrap1.bottom() != NULL) ? &fTrap1 : NULL;
+    }
+
+    // Eliminate a trapezoid.
+    void nullifyTrapezoid() {
+        if (fTrap1.bottom() != NULL) {
+            DebugPrintf("Unexpected non-null second trapezoid.\n");
+            fTrap1.nullify();
+            return;
+        }
+        fTrap0.nullify();
+    }
+
+    // Determine whether the edge specified by this Vertex shares the given top
+    // and bottom.
+    bool shareEdge(Vertex *top, Vertex *bottom);
+
+    // Determines whether the angle specified by { prev, this, next } is convex.
+    // Note that collinear is considered to be convex.
+    bool angleIsConvex();
+
+    // Remove this Vertex from the { prev, next } linked list.
+    void delink() {
+        Vertex *p = prev(),
+               *n = next();
+        p->setNext(n);
+        n->setPrev(p);
+    }
+
+    // Return a number that is less than, equal to, or greater than zero
+    // depending on whether the point is to the left, on, or to the right of the
+    // edge that has this Vertex as a base.
+    SkScalar compare(const SkPoint &pt) const;
+
+    // Classify the vertex, and return its sorted edges.
+    VertexType classify(Vertex **e0, Vertex **e1);
+
+    // This helps determine unimonotonicity.
+    Vertex *diagonal();
+
+private:
+    SkPoint fPoint;
+    Vertex *fNext;
+    Vertex *fPrev;
+    bool fDone;
+};
+
+
+bool Vertex::angleIsConvex() {
+    SkPoint vPrev = prev()->point() - point(),
+            vNext = next()->point() - point();
+    // TODO(turk): There might be overflow in fixed-point.
+    return SkPoint::CrossProduct(vNext, vPrev) >= 0;
+}
+
+
+bool Vertex::shareEdge(Vertex *top, Vertex *bottom) {
+    return (((this == top)    && (this->next() == bottom)) ||
+            ((this == bottom) && (this->next() == top)));
+}
+
+
+SkScalar Vertex::compare(const SkPoint &pt) const  {
+    SkPoint ve = next()->point() - point(),
+            vp = pt              - point();
+    SkScalar d;
+    if (ve.fY == 0) {
+        // Return twice the distance to the center of the horizontal edge.
+        d = ve.fX + pt.fX - next()->point().fX;
+    } else {
+        // Return the distance to the edge, scaled by the edge length.
+        d = SkPoint::CrossProduct(ve, vp);
+        if (ve.fY > 0) d = -d;
+    }
+    return d;
+}
+
+
+SkScalar Trapezoid::compare(const SkPoint &pt) const {
+    SkScalar d = left()->compare(pt);
+    if (d <= 0)
+        return d;   // Left of the left edge.
+    d = right()->compare(pt);
+    if (d >= 0)
+        return d;   // Right of the right edge.
+    return 0;       // Somewhere between the left and the right edges.
+}
+
+
+
+SkScalar Trapezoid::compare(const Trapezoid &t1) const {
+#if 1
+    SkScalar d = left()->compare(t1.left()->point());
+    if (d == 0)
+        d = right()->compare(t1.right()->point());
+    return d;
+#else
+    SkScalar dl =  left()->compare( t1.left()->point()),
+             dr = right()->compare(t1.right()->point());
+    if (dl < 0 && dr < 0)
+        return dr;
+    if (dl > 0 && dr > 0)
+        return dl;
+    return 0;
+#endif
+}
+
+
+Trapezoid* ActiveTrapezoids::getTrapezoidWithEdge(const Vertex *edge) {
+    DebugPrintf("Entering getTrapezoidWithEdge(): looking through %d\n",
+           fTrapezoids.count());
+    DebugPrintf("trying to find %p: ", edge);
+    Trapezoid **tp;
+    for (tp = fTrapezoids.begin(); tp < fTrapezoids.end(); ++tp) {
+        SkASSERT(tp != NULL);
+        SkASSERT(*tp != NULL);
+        DebugPrintf("%p and %p, ", (**tp).left(), (**tp).right());
+        if ((**tp).left() == edge || (**tp).right() == edge) {
+            DebugPrintf("\ngetTrapezoidWithEdge found the trapezoid\n");
+            return *tp;
+        }
+    }
+    DebugPrintf("getTrapezoidWithEdge found no trapezoid\n");
+    return NULL;
+}
+
+
+bool ActiveTrapezoids::insertNewTrapezoid(Vertex *vt,
+                                          Vertex *left,
+                                          Vertex *right) {
+    DebugPrintf("Inserting a trapezoid...");
+    if (vt->fTrap0.left() == NULL && vt->fTrap0.right() == NULL) {
+        vt->fTrap0.setLeft(left);
+        vt->fTrap0.setRight(right);
+        insert(&vt->fTrap0);
+    } else if (vt->fTrap1.left() == NULL && vt->fTrap1.right() == NULL) {
+        DebugPrintf("a second one...");
+        vt->fTrap1.setLeft(left);
+        vt->fTrap1.setRight(right);
+        if (vt->fTrap1 < vt->fTrap0) {  // Keep trapezoids sorted.
+            remove(&vt->fTrap0);
+            Trapezoid t = vt->fTrap0;
+            vt->fTrap0 = vt->fTrap1;
+            vt->fTrap1 = t;
+            insert(&vt->fTrap0);
+        }
+        insert(&vt->fTrap1);
+    } else {
+        FailureMessage("More than 2 trapezoids requested for a vertex\n");
+        return false;
+    }
+    DebugPrintf(" done. %d incomplete trapezoids\n", fTrapezoids.count());
+    return true;
+}
+
+
+void ActiveTrapezoids::insert(Trapezoid *t) {
+    Trapezoid **tp;
+    for (tp = fTrapezoids.begin(); tp < fTrapezoids.end(); ++tp)
+        if (**tp > *t)
+            break;
+    fTrapezoids.insert(tp - fTrapezoids.begin(), 1, &t);
+    // SHOULD VERIFY THAT ALL TRAPEZOIDS ARE PROPERLY SORTED
+}
+
+
+void ActiveTrapezoids::remove(Trapezoid *t) {
+    DebugPrintf("Removing a trapezoid...");
+    for (Trapezoid **tp = fTrapezoids.begin(); tp < fTrapezoids.end(); ++tp) {
+        if (*tp == t) {
+            fTrapezoids.remove(tp - fTrapezoids.begin());
+            DebugPrintf(" done.\n");
+            return;
+        }
+    }
+    DebugPrintf(" Arghh! Panic!\n");
+    SkASSERT(t == 0);   // Cannot find t in active trapezoid list.
+}
+
+
+bool ActiveTrapezoids::withinActiveTrapezoid(const SkPoint &pt,
+                                             Trapezoid **trap) {
+    DebugPrintf("Entering withinActiveTrapezoid()\n");
+    // This is where a good search data structure would be helpful.
+    Trapezoid **t;
+    for (t = fTrapezoids.begin(); t < fTrapezoids.end(); ++t) {
+        if ((**t).left()->compare(pt) <= 0) {
+            // The point is to the left of the left edge of this trapezoid.
+            DebugPrintf("withinActiveTrapezoid: Before a trapezoid\n");
+            *trap = *t;     // Return the place where a new trapezoid would go.
+// We have a bug with the sorting -- look through everything.
+            continue;
+//             return false;   // Outside all trapezoids, since they are sorted.
+        }
+        // The point is to the right of the left edge of this trapezoid.
+
+        if ((**t).right()->compare(pt) < 0) {
+            // The point is to the left of the right edge.
+            DebugPrintf("withinActiveTrapezoid: Within an Active Trapezoid\n");
+            *trap = *t;
+            return true;
+        }
+    }
+
+    // The point is to the right of all trapezoids.
+    DebugPrintf("withinActiveTrapezoid: After all trapezoids\n");
+    *trap = NULL;
+    return false;
+}
+
+
+Vertex* Vertex::diagonal() {
+    Vertex *diag = NULL;
+    if (fTrap0.bottom() != NULL) {
+        if (!fTrap0.left() ->shareEdge(this, fTrap0.bottom()) &&
+            !fTrap0.right()->shareEdge(this, fTrap0.bottom())
+        ) {
+            diag = fTrap0.bottom();
+            fTrap0 = fTrap1;
+            fTrap1.nullify();
+        } else if (fTrap1.bottom() != NULL &&
+                  !fTrap1.left() ->shareEdge(this, fTrap1.bottom()) &&
+                  !fTrap1.right()->shareEdge(this, fTrap1.bottom())
+        ) {
+            diag = fTrap1.bottom();
+            fTrap1.nullify();
+        }
+    }
+    return diag;
+}
+
+
+// We use this to sort the edges vertically for a scan-conversion type of
+// operation.
+class VertexPtr {
+public:
+    Vertex *vt;
+};
+
+
+bool operator<(VertexPtr &v0, VertexPtr &v1) {
+    // DebugPrintf("< %p %p\n", &v0, &v1);
+    if (v0.vt->point().fY < v1.vt->point().fY)  return true;
+    if (v0.vt->point().fY > v1.vt->point().fY)  return false;
+    if (v0.vt->point().fX < v1.vt->point().fX)  return true;
+    else                                        return false;
+}
+
+
+bool operator>(VertexPtr &v0, VertexPtr &v1) {
+    // DebugPrintf("> %p %p\n", &v0, &v1);
+    if (v0.vt->point().fY > v1.vt->point().fY)  return true;
+    if (v0.vt->point().fY < v1.vt->point().fY)  return false;
+    if (v0.vt->point().fX > v1.vt->point().fX)  return true;
+    else                                        return false;
+}
+
+
+static void SetVertexPoints(size_t numPts, const SkPoint *pt, Vertex *vt) {
+    for (; numPts-- != 0; ++pt, ++vt)
+        vt->setPoint(*pt);
+}
+
+
+static void InitializeVertexTopology(size_t numPts, Vertex *v1) {
+    Vertex *v0 = v1 + numPts - 1, *v_1 = v0 - 1;
+    for (; numPts-- != 0; v_1 = v0, v0 = v1++) {
+        v0->setPrev(v_1);
+        v0->setNext(v1);
+    }
+}
+
+Vertex::VertexType Vertex::classify(Vertex **e0, Vertex **e1) {
+    VertexType type;
+    SkPoint vPrev, vNext;
+    vPrev.fX = prev()->point().fX - point().fX;
+    vPrev.fY = prev()->point().fY - point().fY;
+    vNext.fX = next()->point().fX - point().fX;
+    vNext.fY = next()->point().fY - point().fY;
+
+    // This can probably be simplified, but there are enough potential bugs,
+    // we will leave it expanded until all cases are tested appropriately.
+    if (vPrev.fY < 0) {
+        if (vNext.fY > 0) {
+            // Prev comes from above, Next goes below.
+            type = MONOTONE;
+            *e0 = prev();
+            *e1 = this;
+        } else if (vNext.fY < 0) {
+            // The are both above: sort so that e0 is on the left.
+            type = CONCAVE;
+            if (SkPoint::CrossProduct(vPrev, vNext) <= 0) {
+                *e0 = this;
+                *e1 = prev();
+            } else {
+                *e0 = prev();
+                *e1 = this;
+            }
+        } else {
+            DebugPrintf("### py < 0, ny = 0\n");
+            if (vNext.fX < 0) {
+                type = CONCAVE;
+                *e0 = this;     // flat to the left
+                *e1 = prev();   // concave on the right
+            } else {
+                type = CONCAVE;
+                *e0 = prev();   // concave to the left
+                *e1 = this;     // flat to the right
+            }
+        }
+    } else if (vPrev.fY > 0) {
+        if (vNext.fY < 0) {
+            // Next comes from above, Prev goes below.
+            type = MONOTONE;
+            *e0 = this;
+            *e1 = prev();
+        } else if (vNext.fY > 0) {
+            // They are both below: sort so that e0 is on the left.
+            type = CONVEX;
+            if (SkPoint::CrossProduct(vPrev, vNext) <= 0) {
+                *e0 = prev();
+                *e1 = this;
+            } else {
+                *e0 = this;
+                *e1 = prev();
+            }
+        } else {
+            DebugPrintf("### py > 0, ny = 0\n");
+            if (vNext.fX < 0) {
+                type = MONOTONE;
+                *e0 = this;     // flat to the left
+                *e1 = prev();   // convex on the right - try monotone first
+            } else {
+                type = MONOTONE;
+                *e0 = prev();   // convex to the left - try monotone first
+                *e1 = this;     // flat to the right
+            }
+        }
+    } else {  // vPrev.fY == 0
+        if (vNext.fY < 0) {
+            DebugPrintf("### py = 0, ny < 0\n");
+            if (vPrev.fX < 0) {
+                type = CONCAVE;
+                *e0 = prev();   // flat to the left
+                *e1 = this;     // concave on the right
+            } else {
+                type = CONCAVE;
+                *e0 = this;     // concave on the left - defer
+                *e1 = prev();   // flat to the right
+            }
+        } else if (vNext.fY > 0) {
+            DebugPrintf("### py = 0, ny > 0\n");
+            if (vPrev.fX < 0) {
+                type = MONOTONE;
+                *e0 = prev();   // flat to the left
+                *e1 = this;     // convex on the right - try monotone first
+            } else {
+                type = MONOTONE;
+                *e0 = this;     // convex to the left - try monotone first
+                *e1 = prev();   // flat to the right
+            }
+        } else {
+            DebugPrintf("### py = 0, ny = 0\n");
+            // First we try concave, then monotone, then convex.
+            if (vPrev.fX <= vNext.fX) {
+                type = CONCAVE;
+                *e0 = prev();   // flat to the left
+                *e1 = this;     // flat to the right
+            } else {
+                type = CONCAVE;
+                *e0 = this;     // flat to the left
+                *e1 = prev();   // flat to the right
+            }
+        }
+    }
+    return type;
+}
+
+
+#ifdef DEBUG
+static const char* GetVertexTypeString(Vertex::VertexType type) {
+    const char *typeStr = NULL;
+    switch (type) {
+        case Vertex::MONOTONE:
+            typeStr = "MONOTONE";
+            break;
+        case Vertex::CONCAVE:
+            typeStr = "CONCAVE";
+            break;
+        case Vertex::CONVEX:
+            typeStr = "CONVEX";
+            break;
+    }
+    return typeStr;
+}
+
+
+static void PrintVertices(size_t numPts, Vertex *vt) {
+    DebugPrintf("\nVertices:\n");
+    for (int i = 0; i < numPts; i++) {
+        Vertex *e0, *e1;
+        Vertex::VertexType type = vt[i].classify(&e0, &e1);
+        DebugPrintf("%2d: (%.7g, %.7g), prev(%d), next(%d), "
+                    "type(%s), left(%d), right(%d)",
+                    i, vt[i].point().fX, vt[i].point().fY,
+                    vt[i].prev() - vt, vt[i].next() - vt,
+                    GetVertexTypeString(type), e0 - vt, e1 - vt);
+        Trapezoid *trap[2];
+        vt[i].trapezoids(trap, trap+1);
+        for (int i = 0; i < 2; ++i)
+            if (trap[i] != NULL)
+                DebugPrintf(", trap(L=%d, R=%d, B=%d)",
+                            trap[i]->left()   - vt,
+                            trap[i]->right()  - vt,
+                            trap[i]->bottom() - vt);
+        DebugPrintf("\n");
+    }
+}
+
+
+static void PrintVertexPtrs(size_t numPts, VertexPtr *vp, Vertex *vtBase) {
+    DebugPrintf("\nSorted Vertices:\n");
+    for (int i = 0; i < numPts; i++) {
+        Vertex *e0, *e1;
+        Vertex *vt = vp[i].vt;
+        Vertex::VertexType type = vt->classify(&e0, &e1);
+        DebugPrintf("%2d: %2d: (%.7g, %.7g), prev(%d), next(%d), "
+                    "type(%s), left(%d), right(%d)",
+                    i, vt - vtBase, vt->point().fX, vt->point().fY,
+                    vt->prev() - vtBase, vt->next() - vtBase,
+                    GetVertexTypeString(type), e0 - vtBase, e1 - vtBase);
+        Trapezoid *trap[2];
+        vt->trapezoids(trap, trap+1);
+        for (int i = 0; i < 2; ++i)
+            if (trap[i] != NULL)
+                DebugPrintf(", trap(L=%d, R=%d, B=%d)",
+                            trap[i]->left()   - vtBase,
+                            trap[i]->right()  - vtBase,
+                            trap[i]->bottom() - vtBase);
+        DebugPrintf("\n");
+    }
+}
+#else  // !DEBUG
+inline void PrintVertices(size_t numPts, Vertex *vt) {}
+inline void PrintVertexPtrs(size_t numPts, VertexPtr *vp, Vertex *vtBase) {}
+#endif  // !DEBUG
+
+
+// SkTHeapSort is broken, so we use a bubble sort in the meantime.
+template <typename T>
+void BubbleSort(T *array, size_t count) {
+    bool sorted;
+    size_t count_1 = count - 1;
+    do {
+        sorted = true;
+        for (int i = 0; i < count_1; ++i) {
+            if (array[i + 1] < array[i]) {
+                T t = array[i];
+                array[i] = array[i + 1];
+                array[i + 1] = t;
+                sorted = false;
+            }
+        }
+    } while (!sorted);
+}
+
+
+// Remove zero-height trapezoids.
+static void RemoveDegenerateTrapezoids(size_t numVt, Vertex *vt) {
+    for (; numVt-- != 0; vt++) {
+        Trapezoid *traps[2];
+        vt->trapezoids(traps, traps+1);
+        if (traps[1] != NULL &&
+                vt->point().fY >= traps[1]->bottom()->point().fY) {
+            traps[1]->nullify();
+            traps[1] = NULL;
+        }
+        if (traps[0] != NULL &&
+                vt->point().fY >= traps[0]->bottom()->point().fY) {
+            if (traps[1] != NULL) {
+                *traps[0] = *traps[1];
+                traps[1]->nullify();
+            } else {
+                traps[0]->nullify();
+            }
+        }
+    }
+}
+
+
+// Enhance the polygon with trapezoids.
+bool ConvertPointsToVertices(size_t numPts, const SkPoint *pts, Vertex *vta) {
+    DebugPrintf("ConvertPointsToVertices()\n");
+
+    // Clear everything.
+    DebugPrintf("Zeroing vertices\n");
+    bzero(vta, numPts * sizeof(*vta));
+
+    // Initialize vertices.
+    DebugPrintf("Initializing vertices\n");
+    SetVertexPoints(numPts, pts, vta);
+    InitializeVertexTopology(numPts, vta);
+
+    PrintVertices(numPts, vta);
+
+    SkTDArray<VertexPtr> vtptr;
+    vtptr.setCount(numPts);
+    for (int i = numPts; i-- != 0;)
+        vtptr[i].vt = vta + i;
+    PrintVertexPtrs(vtptr.count(), vtptr.begin(), vta);
+    DebugPrintf("Sorting vertrap ptr array [%d] %p %p\n", vtptr.count(),
+        &vtptr[0], &vtptr[vtptr.count() - 1]
+    );
+//  SkTHeapSort(vtptr.begin(), vtptr.count());
+    BubbleSort(vtptr.begin(), vtptr.count());
+    DebugPrintf("Done sorting\n");
+    PrintVertexPtrs(vtptr.count(), vtptr.begin(), vta);
+
+    DebugPrintf("Traversing sorted vertrap ptrs\n");
+    ActiveTrapezoids incompleteTrapezoids;
+    for (VertexPtr *vtpp = vtptr.begin(); vtpp < vtptr.end(); ++vtpp) {
+        DebugPrintf("%d: sorted vertrap %d\n",
+                    vtpp - vtptr.begin(), vtpp->vt - vta);
+        Vertex *vt = vtpp->vt;
+        Vertex *e0, *e1;
+        Trapezoid *t;
+        switch (vt->classify(&e0, &e1)) {
+            case Vertex::MONOTONE:
+            monotone:
+                DebugPrintf("MONOTONE %d %d\n", e0 - vta, e1 - vta);
+                // We should find one edge.
+                t = incompleteTrapezoids.getTrapezoidWithEdge(e0);
+                if (t == NULL) {      // One of the edges is flat.
+                    DebugPrintf("Monotone: cannot find a trapezoid with e0: "
+                                "trying convex\n");
+                    goto convex;
+                }
+                t->setBottom(vt);     // This trapezoid is now complete.
+                incompleteTrapezoids.remove(t);
+
+                if (e0 == t->left())  // Replace the left edge.
+                    incompleteTrapezoids.insertNewTrapezoid(vt, e1, t->right());
+                else                  // Replace the right edge.
+                    incompleteTrapezoids.insertNewTrapezoid(vt, t->left(), e1);
+                break;
+
+            case Vertex::CONVEX:      // Start of a new trapezoid.
+            convex:
+                // We don't expect to find any edges.
+                DebugPrintf("CONVEX %d %d\n", e0 - vta, e1 - vta);
+                if (incompleteTrapezoids.withinActiveTrapezoid(
+                        vt->point(), &t)) {
+                    // Complete trapezoid.
+                    SkASSERT(t != NULL);
+                    t->setBottom(vt);
+                    incompleteTrapezoids.remove(t);
+                    // Introduce two new trapezoids.
+                    incompleteTrapezoids.insertNewTrapezoid(vt, t->left(), e0);
+                    incompleteTrapezoids.insertNewTrapezoid(vt, e1, t->right());
+                } else {
+                    // Insert a new trapezoid.
+                    incompleteTrapezoids.insertNewTrapezoid(vt, e0, e1);
+                }
+                break;
+
+            case Vertex::CONCAVE:   // End of a trapezoid.
+                DebugPrintf("CONCAVE %d %d\n", e0 - vta, e1 - vta);
+                // We should find two edges.
+                t = incompleteTrapezoids.getTrapezoidWithEdge(e0);
+                if (t == NULL) {
+                    DebugPrintf("Concave: cannot find a trapezoid with e0: "
+                                " trying monotone\n");
+                    goto monotone;
+                }
+                SkASSERT(t != NULL);
+                if (e0 == t->left() && e1 == t->right()) {
+                    DebugPrintf(
+                            "Concave edges belong to the same trapezoid.\n");
+                    // Edges belong to the same trapezoid.
+                    // Complete trapezoid & transfer it from the active list.
+                    t->setBottom(vt);
+                    incompleteTrapezoids.remove(t);
+                } else {  // Edges belong to different trapezoids
+                    DebugPrintf(
+                            "Concave edges belong to different trapezoids.\n");
+                    // Complete left and right trapezoids.
+                    Trapezoid *s = incompleteTrapezoids.getTrapezoidWithEdge(
+                                                                            e1);
+                    if (s == NULL) {
+                        DebugPrintf(
+                                "Concave: cannot find a trapezoid with e1: "
+                                " trying monotone\n");
+                        goto monotone;
+                    }
+                    t->setBottom(vt);
+                    s->setBottom(vt);
+                    incompleteTrapezoids.remove(t);
+                    incompleteTrapezoids.remove(s);
+
+                    // Merge the two trapezoids into one below this vertex.
+                    incompleteTrapezoids.insertNewTrapezoid(vt, t->left(),
+                                                                s->right());
+                }
+                break;
+        }
+    }
+
+    RemoveDegenerateTrapezoids(numPts, vta);
+
+    DebugPrintf("Done making trapezoids\n");
+    PrintVertexPtrs(vtptr.count(), vtptr.begin(), vta);
+
+    size_t k = incompleteTrapezoids.count();
+    if (k > 0) {
+        FailureMessage("%d incomplete trapezoids\n", k);
+        return false;
+    }
+    return true;
+}
+
+
+inline void appendTriangleAtVertex(const Vertex *v,
+                                   SkTDArray<SkPoint> *triangles) {
+    SkPoint *p = triangles->append(3);
+    p[0] = v->prev()->point();
+    p[1] = v->point();
+    p[2] = v->next()->point();
+    DebugPrintf(
+          "Appending triangle: { (%.7g, %.7g), (%.7g, %.7g), (%.7g, %.7g) }\n",
+          p[0].fX, p[0].fY,
+          p[1].fX, p[1].fY,
+          p[2].fX, p[2].fY
+    );
+}
+
+
+static size_t CountVertices(const Vertex *first, const Vertex *last) {
+    DebugPrintf("Counting vertices: ");
+    size_t count = 1;
+    for (; first != last; first = first->next()) {
+        ++count;
+        SkASSERT(count <= kMaxCount);
+        if (count >= kMaxCount) {
+            FailureMessage("Vertices do not seem to be in a linked chain\n");
+            break;
+        }
+    }
+    return count;
+}
+
+
+bool operator<(const SkPoint &p0, const SkPoint &p1) {
+    if (p0.fY < p1.fY)  return true;
+    if (p0.fY > p1.fY)  return false;
+    if (p0.fX < p1.fX)  return true;
+    else                return false;
+}
+
+
+static void PrintLinkedVertices(size_t n, Vertex *vertices) {
+    DebugPrintf("%d vertices:\n", n);
+    Vertex *v;
+    for (v = vertices; n-- != 0; v = v->next())
+        DebugPrintf("   (%.7g, %.7g)\n", v->point().fX, v->point().fY);
+    if (v != vertices)
+        FailureMessage("Vertices are not in a linked chain\n");
+}
+
+
+// Triangulate an unimonotone chain.
+bool TriangulateMonotone(Vertex *first, Vertex *last,
+                         SkTDArray<SkPoint> *triangles) {
+    bool success = true;
+    DebugPrintf("TriangulateMonotone()\n");
+
+    size_t numVertices = CountVertices(first, last);
+    if (numVertices == kMaxCount) {
+        FailureMessage("Way too many vertices: %d:\n", numVertices);
+        PrintLinkedVertices(numVertices, first);
+        return false;
+    }
+
+    Vertex *start = first;
+    // First find the point with the smallest Y.
+    DebugPrintf("TriangulateMonotone: finding bottom\n");
+    int count = kMaxCount;    // Maximum number of vertices.
+    for (Vertex *v = first->next(); v != first && count-- > 0; v = v->next())
+        if (v->point() < start->point())
+            start = v;
+    if (count <= 0) {
+        FailureMessage("TriangulateMonotone() was given disjoint chain\n");
+        return false;   // Something went wrong.
+    }
+
+    // Start at the far end of the long edge.
+    if (start->prev()->point() < start->next()->point())
+        start = start->next();
+
+    Vertex *current = start->next();
+    while (numVertices >= 3) {
+        if (current->angleIsConvex()) {
+            DebugPrintf("Angle %p is convex\n", current);
+            // Print the vertices
+            PrintLinkedVertices(numVertices, start);
+
+            appendTriangleAtVertex(current, triangles);
+            if (triangles->count() > kMaxCount * 3) {
+                FailureMessage("An extraordinarily large number of triangles "
+                               "were generated\n");
+                return false;
+            }
+            Vertex *save = current->prev();
+            current->delink();
+            current = (save == start || save == start->prev()) ? start->next()
+                                                               : save;
+            --numVertices;
+        } else {
+            if (numVertices == 3) {
+                FailureMessage("Convexity error in TriangulateMonotone()\n");
+                appendTriangleAtVertex(current, triangles);
+                return false;
+            }
+            DebugPrintf("Angle %p is concave\n", current);
+            current = current->next();
+        }
+    }
+    return true;
+}
+
+
+// Split the polygon into sets of unimonotone chains, and eventually call
+// TriangulateMonotone() to convert them into triangles.
+bool Triangulate(Vertex *first, Vertex *last, SkTDArray<SkPoint> *triangles) {
+    DebugPrintf("Triangulate()\n");
+    Vertex *currentVertex = first;
+    while (!currentVertex->done()) {
+        currentVertex->setDone(true);
+        Vertex *bottomVertex = currentVertex->diagonal();
+        if (bottomVertex != NULL) {
+            Vertex *saveNext = currentVertex->next();
+            Vertex *savePrev = bottomVertex->prev();
+            currentVertex->setNext(bottomVertex);
+            bottomVertex->setPrev(currentVertex);
+            currentVertex->nullifyTrapezoid();
+            bool success = Triangulate(bottomVertex, currentVertex, triangles);
+            currentVertex->setDone(false);
+            bottomVertex->setDone(false);
+            currentVertex->setNext(saveNext);
+            bottomVertex->setPrev(savePrev);
+            bottomVertex->setNext(currentVertex);
+            currentVertex->setPrev(bottomVertex);
+            return Triangulate(currentVertex, bottomVertex, triangles)
+                   && success;
+        } else {
+            currentVertex = currentVertex->next();
+        }
+    }
+    return TriangulateMonotone(first, last, triangles);
+}
+
+
+bool SkConcaveToTriangles(size_t numPts,
+                          const SkPoint pts[],
+                          SkTDArray<SkPoint> *triangles) {
+    DebugPrintf("SkConcaveToTriangles()\n");
+
+    SkTDArray<Vertex> vertices;
+    vertices.setCount(numPts);
+    if (!ConvertPointsToVertices(numPts, pts, vertices.begin()))
+        return false;
+
+    triangles->setReserve(numPts);
+    triangles->setCount(0);
+    return Triangulate(vertices.begin(), vertices.end() - 1, triangles);
+}
diff --git a/src/core/core_files.mk b/src/core/core_files.mk
index 3b94149..37c55e1 100644
--- a/src/core/core_files.mk
+++ b/src/core/core_files.mk
@@ -22,6 +22,7 @@
     SkColor.cpp \
     SkColorFilter.cpp \
     SkColorTable.cpp \
+    SkConcaveToTriangles.cpp \
     SkComposeShader.cpp \
     SkCordic.cpp \
     SkCubicClipper.cpp \
diff --git a/tests/TriangulationTest.cpp b/tests/TriangulationTest.cpp
new file mode 100644
index 0000000..869e739
--- /dev/null
+++ b/tests/TriangulationTest.cpp
@@ -0,0 +1,292 @@
+#include "Test.h"
+#include "../../src/core/SkConcaveToTriangles.h"
+#include "SkGeometry.h"
+
+static int GetIndexFromPoint(const SkPoint &pt,
+                             int numPts, const SkPoint *pts) {
+    for (int i = 0; i < numPts; ++i)
+        if (pt.fX == pts[i].fX && pt.fY == pts[i].fY)
+            return i;
+    return -1;
+}
+
+
+bool gPrintTriangles = false;   // Can we set this on the command line?
+
+static void PrintTriangles(const SkTDArray<SkPoint> &triangles,
+                           int numPts, const SkPoint *pts,
+                           skiatest::Reporter* reporter) {
+    if (gPrintTriangles) {
+        SkPoint *p = triangles.begin();
+        int n = triangles.count();
+        REPORTER_ASSERT(reporter, n % 3 == 0);
+        n /= 3;
+        printf("%d Triangles:\n{\n", n);
+        for (; n-- != 0; p += 3)
+            printf("    { {%.7g, %.7g}, {%.7g, %.7g}, {%.7g, %.7g} },  "
+                   "// { %2d, %2d, %2d }\n",
+                p[0].fX, p[0].fY,
+                p[1].fX, p[1].fY,
+                p[2].fX, p[2].fY,
+                GetIndexFromPoint(p[0], numPts, pts),
+                GetIndexFromPoint(p[1], numPts, pts),
+                GetIndexFromPoint(p[2], numPts, pts));
+        printf("}\n");
+    }
+}
+
+
+static bool CompareTriangleList(size_t numTriangles,
+                                const float refTriangles[][3][2],
+                                const SkTDArray<SkPoint> &triangles) {
+    if (triangles.count() != numTriangles * 3) {
+        printf("Expected %d triangles, not %d\n",
+               numTriangles, triangles.count() / 3);
+        return false;
+    }
+    size_t numErrors = 0;
+    for (size_t i = 0; i < numTriangles; ++i) {
+        const float *r = &refTriangles[i][0][0];
+        const SkScalar *t = &triangles[i * 3].fX;
+        bool equalTriangle = true;
+        for (int j = 6; j-- != 0; r++, t++)
+            if (SkFloatToScalar(*r) != *t)
+                equalTriangle = false;
+        if (equalTriangle == false) {
+            ++numErrors;
+            printf("Triangle %d differs\n", i);
+        }
+    }
+    if (numErrors > 0)
+        printf("%d triangles differ\n", numErrors);
+    return numErrors == 0;
+}
+
+
+#ifndef LEFT_HANDED_POLYGONS
+static const SkPoint star[] = {
+    // Outer contour is clockwise if Y is down, counterclockwise if Y is up.
+    { SkFloatToScalar(110), SkFloatToScalar( 20)  },
+    { SkFloatToScalar(100), SkFloatToScalar( 50)  },
+    { SkFloatToScalar(130), SkFloatToScalar( 80)  },
+    { SkFloatToScalar( 90), SkFloatToScalar( 80)  },
+    { SkFloatToScalar( 70), SkFloatToScalar(120)  },
+    { SkFloatToScalar( 50), SkFloatToScalar( 80)  },
+    { SkFloatToScalar( 10), SkFloatToScalar( 80)  },
+    { SkFloatToScalar( 40), SkFloatToScalar( 50)  },
+    { SkFloatToScalar( 30), SkFloatToScalar( 20)  },
+    { SkFloatToScalar( 70), SkFloatToScalar( 40)  },
+    // Inner contour is counterclockwise if Y is down, clockwise if Y is up.
+    { SkFloatToScalar(110), SkFloatToScalar( 20)  },
+    { SkFloatToScalar( 70), SkFloatToScalar( 50)  },
+    { SkFloatToScalar( 60), SkFloatToScalar( 60)  },
+    { SkFloatToScalar( 60), SkFloatToScalar( 70)  },
+    { SkFloatToScalar( 80), SkFloatToScalar( 70)  },
+    { SkFloatToScalar( 80), SkFloatToScalar( 60)  },
+    { SkFloatToScalar( 70), SkFloatToScalar( 50)  }
+};
+static const SkPoint plus[] = {
+    { SkFloatToScalar( 70), SkFloatToScalar( 10)  },
+    { SkFloatToScalar( 70), SkFloatToScalar( 50)  },
+    { SkFloatToScalar(110), SkFloatToScalar( 50)  },
+    { SkFloatToScalar(110), SkFloatToScalar( 70)  },
+    { SkFloatToScalar( 70), SkFloatToScalar( 70)  },
+    { SkFloatToScalar( 70), SkFloatToScalar(110)  },
+    { SkFloatToScalar( 50), SkFloatToScalar(110)  },
+    { SkFloatToScalar( 50), SkFloatToScalar( 70)  },
+    { SkFloatToScalar( 10), SkFloatToScalar( 70)  },
+    { SkFloatToScalar( 10), SkFloatToScalar( 50)  },
+    { SkFloatToScalar( 50), SkFloatToScalar( 50)  },
+    { SkFloatToScalar( 50), SkFloatToScalar( 10)  }
+};
+static const SkPoint zipper[] = {
+    { SkFloatToScalar( 10), SkFloatToScalar( 60)  },
+    { SkFloatToScalar( 10), SkFloatToScalar( 10)  },
+    { SkFloatToScalar( 20), SkFloatToScalar( 10)  },
+    { SkFloatToScalar( 20), SkFloatToScalar( 50)  },
+    { SkFloatToScalar( 30), SkFloatToScalar( 50)  },
+    { SkFloatToScalar( 30), SkFloatToScalar( 10)  },
+    { SkFloatToScalar( 60), SkFloatToScalar( 10)  },
+    { SkFloatToScalar( 60), SkFloatToScalar( 50)  },
+    { SkFloatToScalar( 70), SkFloatToScalar( 50)  },
+    { SkFloatToScalar( 70), SkFloatToScalar( 10)  },
+    { SkFloatToScalar(100), SkFloatToScalar( 10)  },
+    { SkFloatToScalar(100), SkFloatToScalar( 50)  },
+    { SkFloatToScalar(110), SkFloatToScalar( 50)  },
+    { SkFloatToScalar(110), SkFloatToScalar( 10)  },
+    { SkFloatToScalar(140), SkFloatToScalar( 10)  },
+    { SkFloatToScalar(140), SkFloatToScalar( 60)  },
+    { SkFloatToScalar(130), SkFloatToScalar( 60)  },
+    { SkFloatToScalar(130), SkFloatToScalar( 20)  },
+    { SkFloatToScalar(120), SkFloatToScalar( 20)  },
+    { SkFloatToScalar(120), SkFloatToScalar( 60)  },
+    { SkFloatToScalar( 90), SkFloatToScalar( 60)  },
+    { SkFloatToScalar( 90), SkFloatToScalar( 20)  },
+    { SkFloatToScalar( 80), SkFloatToScalar( 20)  },
+    { SkFloatToScalar( 80), SkFloatToScalar( 60)  },
+    { SkFloatToScalar( 50), SkFloatToScalar( 60)  },
+    { SkFloatToScalar( 50), SkFloatToScalar( 20)  },
+    { SkFloatToScalar( 40), SkFloatToScalar( 20)  },
+    { SkFloatToScalar( 40), SkFloatToScalar( 60)  }
+};
+#else  // LEFT_HANDED_POLYGONS
+static const SkPoint star[] = {
+    // Outer contour is counterclockwise if Y is down, clockwise if Y is up.
+    { SkFloatToScalar(110), SkFloatToScalar( 20)  },
+    { SkFloatToScalar( 70), SkFloatToScalar( 40)  },
+    { SkFloatToScalar( 30), SkFloatToScalar( 20)  },
+    { SkFloatToScalar( 40), SkFloatToScalar( 50)  },
+    { SkFloatToScalar( 10), SkFloatToScalar( 80)  },
+    { SkFloatToScalar( 50), SkFloatToScalar( 80)  },
+    { SkFloatToScalar( 70), SkFloatToScalar(120)  },
+    { SkFloatToScalar( 90), SkFloatToScalar( 80)  },
+    { SkFloatToScalar(130), SkFloatToScalar( 80)  },
+    { SkFloatToScalar(100), SkFloatToScalar( 50)  },
+    // Inner contour is clockwise if Y is down, counterclockwise if Y is up.
+    { SkFloatToScalar(110), SkFloatToScalar( 20)  },
+    { SkFloatToScalar( 70), SkFloatToScalar( 50)  },
+    { SkFloatToScalar( 80), SkFloatToScalar( 60)  },
+    { SkFloatToScalar( 80), SkFloatToScalar( 70)  },
+    { SkFloatToScalar( 60), SkFloatToScalar( 70)  },
+    { SkFloatToScalar( 60), SkFloatToScalar( 60)  },
+    { SkFloatToScalar( 70), SkFloatToScalar( 50)  }
+};
+#endif  // LEFT_HANDED_POLYGONS
+#define kNumStarVertices 10
+#define kNumStarHoleVertices (sizeof(star) / sizeof(star[0]))
+
+
+// Star test
+static void TestStarTriangulation(skiatest::Reporter* reporter) {
+    static const float refTriangles[][3][2] = {
+        { { 30,  20}, { 70,  40}, { 40,  50} },  // { 8, 9, 7 }
+        { {100,  50}, { 10,  80}, { 40,  50} },  // { 1, 6, 7 }
+        { {100,  50}, { 40,  50}, { 70,  40} },  // { 1, 7, 9 }
+        { {100,  50}, { 70,  40}, {110,  20} },  // { 1, 9, 0 }
+        { { 90,  80}, { 70, 120}, { 50,  80} },  // { 3, 4, 5 }
+        { {130,  80}, { 90,  80}, { 50,  80} },  // { 2, 3, 5 } degen
+        { {130,  80}, { 50,  80}, { 10,  80} },  // { 2, 5, 6 } degen
+        { {130,  80}, { 10,  80}, {100,  50} }   // { 2, 6, 1 }
+    };
+    const size_t numRefTriangles = sizeof(refTriangles)
+                                 / (6 * sizeof(refTriangles[0][0][0]));
+    SkTDArray<SkPoint> triangles;
+    bool success = SkConcaveToTriangles(kNumStarVertices, star, &triangles);
+    PrintTriangles(triangles, kNumStarVertices, star, reporter);
+    success = CompareTriangleList(numRefTriangles, refTriangles, triangles)
+            && success;
+    reporter->report("Triangulate Star", success ? reporter->kPassed
+                                                 : reporter->kFailed);
+}
+
+
+// Star with hole test
+static void TestStarHoleTriangulation(skiatest::Reporter* reporter) {
+    static const float refTriangles[][3][2] = {
+        { {100,  50}, { 80,  60}, { 70,  50} },  // {  1, 15, 16 }
+        { {100,  50}, { 70,  50}, {110,  20} },  // {  1, 16,  0 }
+        { { 30,  20}, { 70,  40}, { 40,  50} },  // {  8,  9,  7 }
+        { { 60,  70}, { 80,  70}, { 10,  80} },  // { 13, 14,  6 }
+        { { 60,  60}, { 60,  70}, { 10,  80} },  // { 12, 13,  6 }
+        { { 70,  50}, { 60,  60}, { 10,  80} },  // { 11, 12,  6 }
+        { { 70,  50}, { 10,  80}, { 40,  50} },  // { 11,  6,  7 }
+        { { 70,  50}, { 40,  50}, { 70,  40} },  // { 11,  7,  9 }
+        { { 70,  50}, { 70,  40}, {110,  20} },  // { 11,  9, 10 }
+        { { 90,  80}, { 70, 120}, { 50,  80} },  // {  3,  4,  5 }
+        { {130,  80}, { 90,  80}, { 50,  80} },  // {  2,  3,  5 } degen
+        { {130,  80}, { 50,  80}, { 10,  80} },  // {  2,  5,  6 } degen
+        { {130,  80}, { 10,  80}, { 80,  70} },  // {  2,  6, 14 }
+        { {130,  80}, { 80,  70}, { 80,  60} },  // {  2, 14, 15 }
+        { {130,  80}, { 80,  60}, {100,  50} }   // {  2, 15,  1 }
+    };
+    const size_t numRefTriangles = sizeof(refTriangles)
+                                 / (6 * sizeof(refTriangles[0][0][0]));
+    SkTDArray<SkPoint> triangles;
+    bool success = SkConcaveToTriangles(kNumStarHoleVertices, star, &triangles);
+    PrintTriangles(triangles, kNumStarHoleVertices, star, reporter);
+    success = CompareTriangleList(numRefTriangles, refTriangles, triangles)
+            && success;
+    reporter->report("Triangulate Star With Hole", success ? reporter->kPassed
+                                                           : reporter->kFailed);
+}
+
+
+// Plus test
+static void TestPlusTriangulation(skiatest::Reporter* reporter) {
+    static const float refTriangles[][3][2] = {
+        { { 50,  10}, { 70,  10}, { 50, 50} },  // { 11,  0, 10 }
+        { { 70,  50}, {110,  50}, { 10, 70} },  // {  1,  2,  8 }
+        { { 70,  50}, { 10,  70}, { 10, 50} },  // {  1,  8,  9 }
+        { { 70,  50}, { 10,  50}, { 50, 50} },  // {  1,  9, 10 }
+        { { 70,  50}, { 50,  50}, { 70, 10} },  // {  1, 10,  0 }
+        { { 70,  70}, { 50, 110}, { 50, 70} },  // {  4,  6,  7 }
+        { {110,  70}, { 70,  70}, { 50, 70} },  // {  3,  4,  7 }
+        { {110,  70}, { 50,  70}, { 10, 70} },  // {  3,  7,  8 }
+        { {110,  70}, { 10,  70}, {110, 50} },  // {  3,  8,  2 }
+        { { 70, 110}, { 50, 110}, { 70, 70} },  // {  5,  6,  4 }
+    };
+    const size_t numRefTriangles = sizeof(refTriangles)
+                                 / (6 * sizeof(refTriangles[0][0][0]));
+    SkTDArray<SkPoint> triangles;
+    const size_t numVertices = sizeof(plus) / sizeof(SkPoint);
+    bool success = SkConcaveToTriangles(numVertices, plus, &triangles);
+    PrintTriangles(triangles, numVertices, plus, reporter);
+    success = CompareTriangleList(numRefTriangles, refTriangles, triangles)
+            && success;
+    reporter->report("Triangulate Plus", success ? reporter->kPassed
+                                                 : reporter->kFailed);
+}
+
+
+// Zipper test
+static void TestZipperTriangulation(skiatest::Reporter* reporter) {
+    static const float refTriangles[][3][2] = {
+        { { 10, 10}, { 20, 10}, { 20, 50} },  // {  1,  2,  3 }
+        { { 20, 50}, { 30, 50}, { 10, 60} },  // {  3,  4,  0 }
+        { { 10, 10}, { 20, 50}, { 10, 60} },  // {  1,  3,  0 }
+        { { 30, 10}, { 60, 10}, { 40, 20} },  // {  5,  6, 26 }
+        { { 30, 10}, { 40, 20}, { 30, 50} },  // {  5, 26,  4 }
+        { { 40, 60}, { 10, 60}, { 30, 50} },  // { 27,  0,  4 }
+        { { 40, 60}, { 30, 50}, { 40, 20} },  // { 27,  4, 26 }
+        { { 60, 50}, { 70, 50}, { 50, 60} },  // {  7,  8, 24 }
+        { { 50, 20}, { 60, 50}, { 50, 60} },  // { 25,  7, 24 }
+        { { 50, 20}, { 40, 20}, { 60, 10} },  // { 25, 26,  6 }
+        { { 60, 50}, { 50, 20}, { 60, 10} },  // {  7, 25,  6 }
+        { { 70, 10}, {100, 10}, { 80, 20} },  // {  9, 10, 22 }
+        { { 70, 10}, { 80, 20}, { 70, 50} },  // {  9, 22,  8 }
+        { { 80, 60}, { 50, 60}, { 70, 50} },  // { 23, 24,  8 }
+        { { 80, 60}, { 70, 50}, { 80, 20} },  // { 23,  8, 22 }
+        { {100, 50}, {110, 50}, { 90, 60} },  // { 11, 12, 20 }
+        { { 90, 20}, {100, 50}, { 90, 60} },  // { 21, 11, 20 }
+        { { 90, 20}, { 80, 20}, {100, 10} },  // { 21, 22, 10 }
+        { {100, 50}, { 90, 20}, {100, 10} },  // { 11, 21, 10 }
+        { {110, 10}, {140, 10}, {120, 20} },  // { 13, 14, 18 }
+        { {110, 10}, {120, 20}, {110, 50} },  // { 13, 18, 12 }
+        { {120, 60}, { 90, 60}, {110, 50} },  // { 19, 20, 12 }
+        { {120, 60}, {110, 50}, {120, 20} },  // { 19, 12, 18 }
+        { {140, 60}, {130, 60}, {130, 20} },  // { 15, 16, 17 }
+        { {130, 20}, {120, 20}, {140, 10} },  // { 17, 18, 14 }
+        { {140, 60}, {130, 20}, {140, 10} },  // { 15, 17, 14 }
+    };
+    const size_t numRefTriangles = sizeof(refTriangles)
+                                 / (6 * sizeof(refTriangles[0][0][0]));
+    SkTDArray<SkPoint> triangles;
+    const size_t numVertices = sizeof(zipper) / sizeof(SkPoint);
+    bool success = SkConcaveToTriangles(numVertices, zipper, &triangles);
+    PrintTriangles(triangles, numVertices, zipper, reporter);
+    success = CompareTriangleList(numRefTriangles, refTriangles, triangles)
+            && success;
+    reporter->report("Triangulate Zipper", success ? reporter->kPassed
+                                                   : reporter->kFailed);
+}
+
+
+static void TestTriangulation(skiatest::Reporter* reporter) {
+    TestStarTriangulation(reporter);
+    TestStarHoleTriangulation(reporter);
+    TestPlusTriangulation(reporter);
+    TestZipperTriangulation(reporter);
+}
+
+#include "TestClassDef.h"
+DEFINE_TESTCLASS("Triangulation", TriangulationTestClass, TestTriangulation)