/*
* 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 (size_t 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 j = 0; j < 2; ++j) {
if (trap[j] != NULL) {
DebugPrintf(", trap(L=%d, R=%d, B=%d)",
trap[j]->left() - vt,
trap[j]->right() - vt,
trap[j]->bottom() - vt);
}
}
DebugPrintf("\n");
}
}
static void PrintVertexPtrs(size_t numPts, VertexPtr *vp, Vertex *vtBase) {
DebugPrintf("\nSorted Vertices:\n");
for (size_t 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 j = 0; j < 2; ++j) {
if (trap[j] != NULL) {
DebugPrintf(", trap(L=%d, R=%d, B=%d)",
trap[j]->left() - vtBase,
trap[j]->right() - vtBase,
trap[j]->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 (size_t 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");
sk_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) {
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);
}