Make GrTriangulator immutable
Marks its methods const and lifts the breadcrumb list out into
function arguments. This is one more step toward the final vision
where GrTriangulator just has an allocator and control knobs, and
everything else is functional.
Bug: skia:10419
Change-Id: I77341c045d481da49ebfee06de5dfc7a2a8a07be
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/360956
Reviewed-by: Brian Salomon <bsalomon@google.com>
Commit-Queue: Chris Dalton <csmartdalton@google.com>
diff --git a/bench/TriangulatorBench.cpp b/bench/TriangulatorBench.cpp
index 4326077..50097ec 100644
--- a/bench/TriangulatorBench.cpp
+++ b/bench/TriangulatorBench.cpp
@@ -23,10 +23,7 @@
extern int kNumTigerPaths;
constexpr float kTigerTolerance = 0.728769f;
-class TriangulatorBenchmark
- : public Benchmark
- , public GrEagerVertexAllocator
- , public GrInnerFanTriangulator::BreadcrumbTriangleCollector {
+class TriangulatorBenchmark : public Benchmark, public GrEagerVertexAllocator {
public:
TriangulatorBenchmark(const char* name) {
fName.printf("triangulator_%s", name);
@@ -85,9 +82,6 @@
void unlock(int) override {}
- // GrInnerFanTriangulator::BreadcrumbTriangleCollector.
- void onPush(SkPoint, SkPoint, SkPoint, int) override {}
-
virtual void doLoop() = 0;
SkString fName;
@@ -119,7 +113,8 @@
void doLoop() override {
bool isLinear;
for (const SkPath& path : fPaths) {
- GrInnerFanTriangulator(path, &fArena, this).pathToTriangles(this, &isLinear);
+ GrInnerFanTriangulator::BreadcrumbTriangleList breadcrumbList;
+ GrInnerFanTriangulator(path, &fArena).pathToTriangles(this, &breadcrumbList, &isLinear);
}
fArena.reset();
}
diff --git a/src/gpu/GrAATriangulator.cpp b/src/gpu/GrAATriangulator.cpp
index 0b7723d..a058fad 100644
--- a/src/gpu/GrAATriangulator.cpp
+++ b/src/gpu/GrAATriangulator.cpp
@@ -61,7 +61,7 @@
}
};
-void GrAATriangulator::makeEvent(SSEdge* e, EventList* events) {
+void GrAATriangulator::makeEvent(SSEdge* e, EventList* events) const {
Vertex* prev = e->fPrev->fVertex;
Vertex* next = e->fNext->fVertex;
if (prev == next || !prev->fPartner || !next->fPartner) {
@@ -82,7 +82,7 @@
}
void GrAATriangulator::makeEvent(SSEdge* edge, Vertex* v, SSEdge* other, Vertex* dest,
- EventList* events, const Comparator& c) {
+ EventList* events, const Comparator& c) const {
if (!v->fPartner) {
return;
}
@@ -106,14 +106,14 @@
}
}
-void GrAATriangulator::connectPartners(VertexList* mesh, const Comparator& c) {
+void GrAATriangulator::connectPartners(VertexList* mesh, const Comparator& c) const {
for (Vertex* outer = mesh->fHead; outer; outer = outer->fNext) {
if (Vertex* inner = outer->fPartner) {
if ((inner->fPrev || inner->fNext) && (outer->fPrev || outer->fNext)) {
// Connector edges get zero winding, since they're only structural (i.e., to ensure
// no 0-0-0 alpha triangles are produced), and shouldn't affect the poly winding
// number.
- this->makeConnectingEdge(outer, inner, EdgeType::kConnector, c, 0);
+ this->makeConnectingEdge(outer, inner, EdgeType::kConnector, c, nullptr, 0);
inner->fPartner = outer->fPartner = nullptr;
}
}
@@ -139,7 +139,7 @@
#endif
}
-void GrAATriangulator::removeNonBoundaryEdges(const VertexList& mesh) {
+void GrAATriangulator::removeNonBoundaryEdges(const VertexList& mesh) const {
TESS_LOG("removing non-boundary edges\n");
EdgeList activeEdges;
for (Vertex* v = mesh.fHead; v != nullptr; v = v->fNext) {
@@ -181,7 +181,7 @@
// and whose adjacent vertices are less than a quarter pixel from an edge. These are guaranteed to
// invert on stroking.
-void GrAATriangulator::simplifyBoundary(EdgeList* boundary, const Comparator& c) {
+void GrAATriangulator::simplifyBoundary(EdgeList* boundary, const Comparator& c) const {
Edge* prevEdge = boundary->fTail;
SkVector prevNormal;
get_edge_normal(prevEdge, &prevNormal);
@@ -227,13 +227,13 @@
}
}
-void GrAATriangulator::connectSSEdge(Vertex* v, Vertex* dest, const Comparator& c) {
+void GrAATriangulator::connectSSEdge(Vertex* v, Vertex* dest, const Comparator& c) const {
if (v == dest) {
return;
}
TESS_LOG("ss_connecting vertex %g to vertex %g\n", v->fID, dest->fID);
if (v->fSynthetic) {
- this->makeConnectingEdge(v, dest, EdgeType::kConnector, c, 0);
+ this->makeConnectingEdge(v, dest, EdgeType::kConnector, c, nullptr, 0);
} else if (v->fPartner) {
TESS_LOG("setting %g's partner to %g ", v->fPartner->fID, dest->fID);
TESS_LOG("and %g's partner to null\n", v->fID);
@@ -243,7 +243,7 @@
}
void GrAATriangulator::Event::apply(VertexList* mesh, const Comparator& c, EventList* events,
- GrAATriangulator* triangulator) {
+ const GrAATriangulator* triangulator) {
if (!fEdge) {
return;
}
@@ -306,7 +306,7 @@
// This is a stripped-down version of tessellate() which computes edges which
// join two filled regions, which represent overlap regions, and collapses them.
bool GrAATriangulator::collapseOverlapRegions(VertexList* mesh, const Comparator& c,
- EventComparator comp) {
+ EventComparator comp) const {
TESS_LOG("\nfinding overlap regions\n");
EdgeList activeEdges;
EventList events(comp);
@@ -381,7 +381,8 @@
dump_skel(ssEdges);
for (SSEdge* edge : ssEdges) {
if (Edge* e = edge->fEdge) {
- this->makeConnectingEdge(edge->fPrev->fVertex, edge->fNext->fVertex, e->fType, c, 0);
+ this->makeConnectingEdge(edge->fPrev->fVertex, edge->fNext->fVertex, e->fType, c,
+ nullptr, 0);
}
}
return complex;
@@ -400,7 +401,7 @@
// new antialiased mesh from those vertices.
void GrAATriangulator::strokeBoundary(EdgeList* boundary, VertexList* innerMesh,
- const Comparator& c) {
+ const Comparator& c) const {
TESS_LOG("\nstroking boundary\n");
// A boundary with fewer than 3 edges is degenerate.
if (!boundary->fHead || !boundary->fHead->fRight || !boundary->fHead->fRight->fRight) {
@@ -546,20 +547,20 @@
int innerWinding = innerInversion ? 2 : -2;
int outerWinding = outerInversion ? -1 : 1;
for (Vertex* v = innerVertices.fHead; v && v->fNext; v = v->fNext) {
- this->makeConnectingEdge(v, v->fNext, EdgeType::kInner, c, innerWinding);
+ this->makeConnectingEdge(v, v->fNext, EdgeType::kInner, c, nullptr, innerWinding);
}
- this->makeConnectingEdge(innerVertices.fTail, innerVertices.fHead, EdgeType::kInner, c,
+ this->makeConnectingEdge(innerVertices.fTail, innerVertices.fHead, EdgeType::kInner, c, nullptr,
innerWinding);
for (Vertex* v = outerVertices.fHead; v && v->fNext; v = v->fNext) {
- this->makeConnectingEdge(v, v->fNext, EdgeType::kOuter, c, outerWinding);
+ this->makeConnectingEdge(v, v->fNext, EdgeType::kOuter, c, nullptr, outerWinding);
}
this->makeConnectingEdge(outerVertices.fTail, outerVertices.fHead, EdgeType::kOuter, c,
- outerWinding);
+ nullptr, outerWinding);
innerMesh->append(innerVertices);
fOuterMesh.append(outerVertices);
}
-void GrAATriangulator::extractBoundary(EdgeList* boundary, Edge* e) {
+void GrAATriangulator::extractBoundary(EdgeList* boundary, Edge* e) const {
TESS_LOG("\nextracting boundary\n");
bool down = this->applyFillType(e->fWinding);
Vertex* start = down ? e->fTop : e->fBottom;
@@ -596,7 +597,7 @@
// Stage 5b: Extract boundaries from mesh, simplify and stroke them into a new mesh.
void GrAATriangulator::extractBoundaries(const VertexList& inMesh, VertexList* innerVertices,
- const Comparator& c) {
+ const Comparator& c) const {
this->removeNonBoundaryEdges(inMesh);
for (Vertex* v = inMesh.fHead; v; v = v->fNext) {
while (v->fFirstEdgeBelow) {
@@ -608,17 +609,17 @@
}
}
-Poly* GrAATriangulator::tessellate(const VertexList& mesh, const Comparator& c) {
+Poly* GrAATriangulator::tessellate(const VertexList& mesh, const Comparator& c) const {
VertexList innerMesh;
this->extractBoundaries(mesh, &innerMesh, c);
SortMesh(&innerMesh, c);
SortMesh(&fOuterMesh, c);
- this->mergeCoincidentVertices(&innerMesh, c);
- bool was_complex = this->mergeCoincidentVertices(&fOuterMesh, c);
- auto result = this->simplify(&innerMesh, c);
+ this->mergeCoincidentVertices(&innerMesh, c, nullptr);
+ bool was_complex = this->mergeCoincidentVertices(&fOuterMesh, c, nullptr);
+ auto result = this->simplify(&innerMesh, c, nullptr);
SkASSERT(SimplifyResult::kAbort != result);
was_complex = (SimplifyResult::kFoundSelfIntersection == result) || was_complex;
- result = this->simplify(&fOuterMesh, c);
+ result = this->simplify(&fOuterMesh, c, nullptr);
SkASSERT(SimplifyResult::kAbort != result);
was_complex = (SimplifyResult::kFoundSelfIntersection == result) || was_complex;
TESS_LOG("\ninner mesh before:\n");
@@ -639,8 +640,8 @@
this->connectPartners(&fOuterMesh, c);
this->connectPartners(&innerMesh, c);
SortedMerge(&innerMesh, &fOuterMesh, &aaMesh, c);
- this->mergeCoincidentVertices(&aaMesh, c);
- result = this->simplify(&aaMesh, c);
+ this->mergeCoincidentVertices(&aaMesh, c, nullptr);
+ result = this->simplify(&aaMesh, c, nullptr);
SkASSERT(SimplifyResult::kAbort != result);
TESS_LOG("combined and simplified mesh:\n");
DUMP_MESH(aaMesh);
@@ -652,7 +653,8 @@
}
}
-int GrAATriangulator::polysToAATriangles(Poly* polys, GrEagerVertexAllocator* vertexAllocator) {
+int GrAATriangulator::polysToAATriangles(Poly* polys,
+ GrEagerVertexAllocator* vertexAllocator) const {
int64_t count64 = CountPoints(polys, SkPathFillType::kWinding);
// Count the points from the outer mesh.
for (Vertex* v = fOuterMesh.fHead; v; v = v->fNext) {
@@ -673,7 +675,7 @@
}
TESS_LOG("emitting %d verts\n", count);
- void* end = this->polysToTriangles(polys, verts, SkPathFillType::kWinding);
+ void* end = this->polysToTriangles(polys, verts, nullptr, SkPathFillType::kWinding);
// Emit the triangles from the outer mesh.
for (Vertex* v = fOuterMesh.fHead; v; v = v->fNext) {
for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
@@ -681,8 +683,8 @@
Vertex* v1 = e->fBottom;
Vertex* v2 = e->fBottom->fPartner;
Vertex* v3 = e->fTop->fPartner;
- end = this->emitTriangle(v0, v1, v2, 0/*winding*/, end);
- end = this->emitTriangle(v0, v2, v3, 0/*winding*/, end);
+ end = this->emitTriangle(v0, v1, v2, 0/*winding*/, end, nullptr);
+ end = this->emitTriangle(v0, v2, v3, 0/*winding*/, end, nullptr);
}
}
diff --git a/src/gpu/GrAATriangulator.h b/src/gpu/GrAATriangulator.h
index 05246ee..a11e23b 100644
--- a/src/gpu/GrAATriangulator.h
+++ b/src/gpu/GrAATriangulator.h
@@ -20,7 +20,7 @@
aaTriangulator.fRoundVerticesToQuarterPixel = true;
aaTriangulator.fEmitCoverage = true;
bool isLinear;
- Poly* polys = aaTriangulator.pathToPolys(tolerance, clipBounds, &isLinear);
+ Poly* polys = aaTriangulator.pathToPolys(tolerance, clipBounds, nullptr, &isLinear);
return aaTriangulator.polysToAATriangles(polys, vertexAllocator);
}
@@ -33,7 +33,7 @@
SSEdge* fEdge;
SkPoint fPoint;
uint8_t fAlpha;
- void apply(VertexList* mesh, const Comparator&, EventList* events, GrAATriangulator*);
+ void apply(VertexList* mesh, const Comparator&, EventList* events, const GrAATriangulator*);
};
struct EventComparator {
enum class Op { kLessThan, kGreaterThan };
@@ -52,31 +52,33 @@
//
// Run steps 1-5 above to produce polygons.
// 5b) Apply fill rules to extract boundary contours from the polygons:
- void extractBoundary(EdgeList* boundary, Edge* e);
- void extractBoundaries(const VertexList& inMesh, VertexList* innerVertices, const Comparator&);
+ void extractBoundary(EdgeList* boundary, Edge* e) const;
+ void extractBoundaries(const VertexList& inMesh, VertexList* innerVertices,
+ const Comparator&) const;
// 5c) Simplify boundaries to remove "pointy" vertices that cause inversions:
- void simplifyBoundary(EdgeList* boundary, const Comparator&);
+ void simplifyBoundary(EdgeList* boundary, const Comparator&) const;
// 5d) Displace edges by half a pixel inward and outward along their normals. Intersect to find
// new vertices, and set zero alpha on the exterior and one alpha on the interior. Build a
// new antialiased mesh from those vertices:
- void strokeBoundary(EdgeList* boundary, VertexList* innerMesh, const Comparator&);
+ void strokeBoundary(EdgeList* boundary, VertexList* innerMesh, const Comparator&) const;
// Run steps 3-6 above on the new mesh, and produce antialiased triangles.
- Poly* tessellate(const VertexList& mesh, const Comparator&) override;
- int polysToAATriangles(Poly*, GrEagerVertexAllocator*);
+ Poly* tessellate(const VertexList& mesh, const Comparator&) const override;
+ int polysToAATriangles(Poly*, GrEagerVertexAllocator*) const;
// Additional helpers and driver functions.
- void makeEvent(SSEdge*, EventList* events);
+ void makeEvent(SSEdge*, EventList* events) const;
void makeEvent(SSEdge*, Vertex* v, SSEdge* other, Vertex* dest, EventList* events,
- const Comparator&);
- void connectPartners(VertexList* mesh, const Comparator&);
- void removeNonBoundaryEdges(const VertexList& mesh);
- void connectSSEdge(Vertex* v, Vertex* dest, const Comparator&);
- bool collapseOverlapRegions(VertexList* mesh, const Comparator&, EventComparator comp);
+ const Comparator&) const;
+ void connectPartners(VertexList* mesh, const Comparator&) const;
+ void removeNonBoundaryEdges(const VertexList& mesh) const;
+ void connectSSEdge(Vertex* v, Vertex* dest, const Comparator&) const;
+ bool collapseOverlapRegions(VertexList* mesh, const Comparator&, EventComparator comp) const;
- VertexList fOuterMesh;
+ // FIXME: fOuterMesh should be plumbed through function parameters instead.
+ mutable VertexList fOuterMesh;
};
#endif
diff --git a/src/gpu/GrInnerFanTriangulator.h b/src/gpu/GrInnerFanTriangulator.h
index f37a6d5..2f98a87 100644
--- a/src/gpu/GrInnerFanTriangulator.h
+++ b/src/gpu/GrInnerFanTriangulator.h
@@ -15,26 +15,28 @@
// path. If a breadcrumbCollector is not provided, pathToPolys fails upon self intersection.
class GrInnerFanTriangulator : private GrTriangulator {
public:
- using GrTriangulator::BreadcrumbTriangleCollector;
+ using GrTriangulator::BreadcrumbTriangleList;
GrInnerFanTriangulator(const SkPath& path, SkArenaAlloc* alloc,
- BreadcrumbTriangleCollector* breadcrumbCollector)
+ bool disallowSelfIntersection = false)
: GrTriangulator(path, alloc) {
+ fDisallowSelfIntersection = disallowSelfIntersection;
fCullCollinearVertices = false;
- fDisallowSelfIntersection = !breadcrumbCollector;
- fBreadcrumbTriangles = breadcrumbCollector;
}
- int pathToTriangles(GrEagerVertexAllocator* vertexAlloc, bool* isLinear) {
- return this->polysToTriangles(this->pathToPolys(isLinear), vertexAlloc);
+ int pathToTriangles(GrEagerVertexAllocator* vertexAlloc, BreadcrumbTriangleList* breadcrumbList,
+ bool* isLinear) const {
+ Poly* polys = this->pathToPolys(breadcrumbList, isLinear);
+ return this->polysToTriangles(polys, vertexAlloc, breadcrumbList);
}
- Poly* pathToPolys(bool* isLinear) {
- return this->GrTriangulator::pathToPolys(0, SkRect::MakeEmpty(), isLinear);
+ Poly* pathToPolys(BreadcrumbTriangleList* breadcrumbList, bool* isLinear) const {
+ return this->GrTriangulator::pathToPolys(0, SkRect::MakeEmpty(), breadcrumbList, isLinear);
}
- int polysToTriangles(Poly* polys, GrEagerVertexAllocator* vertexAlloc) {
- return this->GrTriangulator::polysToTriangles(polys, vertexAlloc);
+ int polysToTriangles(Poly* polys, GrEagerVertexAllocator* vertexAlloc,
+ BreadcrumbTriangleList* breadcrumbList) const {
+ return this->GrTriangulator::polysToTriangles(polys, vertexAlloc, breadcrumbList);
}
};
diff --git a/src/gpu/GrTriangulator.cpp b/src/gpu/GrTriangulator.cpp
index 94a1eac..00f275d 100644
--- a/src/gpu/GrTriangulator.cpp
+++ b/src/gpu/GrTriangulator.cpp
@@ -204,7 +204,8 @@
}
}
-void* GrTriangulator::emitMonotonePoly(const MonotonePoly* monotonePoly, void* data) {
+void* GrTriangulator::emitMonotonePoly(const MonotonePoly* monotonePoly, void* data,
+ BreadcrumbTriangleList* breadcrumbList) const {
SkASSERT(monotonePoly->fWinding != 0);
Edge* e = monotonePoly->fFirstEdge;
VertexList vertices;
@@ -228,14 +229,16 @@
Vertex* curr = v;
Vertex* next = v->fNext;
if (count == 3) {
- return this->emitTriangle(prev, curr, next, monotonePoly->fWinding, data);
+ return this->emitTriangle(prev, curr, next, monotonePoly->fWinding, data,
+ breadcrumbList);
}
double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint.fX;
double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint.fY;
double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint.fX;
double by = static_cast<double>(next->fPoint.fY) - curr->fPoint.fY;
if (ax * by - ay * bx >= 0.0) {
- data = this->emitTriangle(prev, curr, next, monotonePoly->fWinding, data);
+ data = this->emitTriangle(prev, curr, next, monotonePoly->fWinding, data,
+ breadcrumbList);
v->fPrev->fNext = v->fNext;
v->fNext->fPrev = v->fPrev;
count--;
@@ -252,17 +255,17 @@
}
void* GrTriangulator::emitTriangle(Vertex* prev, Vertex* curr, Vertex* next, int winding,
- void* data) const {
+ void* data, BreadcrumbTriangleList* breadcrumbList) const {
if (winding > 0) {
// Ensure our triangles always wind in the same direction as if the path had been
// triangulated as a simple fan (a la red book).
std::swap(prev, next);
}
- if (fBreadcrumbTriangles && abs(winding) > 1 &&
+ if (breadcrumbList && abs(winding) > 1 &&
fPath.getFillType() == SkPathFillType::kWinding) {
// The first winding count will come from the actual triangle we emit. The remaining counts
// come from the breadcrumb triangle.
- fBreadcrumbTriangles->push(prev->fPoint, curr->fPoint, next->fPoint, abs(winding) - 1);
+ breadcrumbList->prepend(fAlloc, prev->fPoint, curr->fPoint, next->fPoint, abs(winding) - 1);
}
return emit_triangle(prev, curr, next, fEmitCoverage, data);
}
@@ -308,13 +311,14 @@
}
return poly;
}
-void* GrTriangulator::emitPoly(const Poly* poly, void *data) {
+void* GrTriangulator::emitPoly(const Poly* poly, void *data,
+ BreadcrumbTriangleList* breadcrumbList) const {
if (poly->fCount < 3) {
return data;
}
TESS_LOG("emit() %d, size %d\n", fID, fCount);
for (MonotonePoly* m = poly->fHead; m != nullptr; m = m->fNext) {
- data = this->emitMonotonePoly(m, data);
+ data = this->emitMonotonePoly(m, data, breadcrumbList);
}
return data;
}
@@ -323,14 +327,14 @@
return a == b;
}
-Poly* GrTriangulator::makePoly(Poly** head, Vertex* v, int winding) {
+Poly* GrTriangulator::makePoly(Poly** head, Vertex* v, int winding) const {
Poly* poly = fAlloc->make<Poly>(v, winding);
poly->fNext = *head;
*head = poly;
return poly;
}
-void GrTriangulator::appendPointToContour(const SkPoint& p, VertexList* contour) {
+void GrTriangulator::appendPointToContour(const SkPoint& p, VertexList* contour) const {
Vertex* v = fAlloc->make<Vertex>(p, 255);
#if TRIANGULATOR_LOGGING
static float gID = 0.0f;
@@ -351,7 +355,7 @@
}
void GrTriangulator::appendQuadraticToContour(const SkPoint pts[3], SkScalar toleranceSqd,
- VertexList* contour) {
+ VertexList* contour) const {
SkQuadCoeff quad(pts);
Sk2s aa = quad.fA * quad.fA;
SkScalar denom = 2.0f * (aa[0] + aa[1]);
@@ -375,7 +379,7 @@
void GrTriangulator::generateCubicPoints(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
const SkPoint& p3, SkScalar tolSqd, VertexList* contour,
- int pointsLeft) {
+ int pointsLeft) const {
SkScalar d1 = SkPointPriv::DistanceToLineSegmentBetweenSqd(p1, p0, p3);
SkScalar d2 = SkPointPriv::DistanceToLineSegmentBetweenSqd(p2, p0, p3);
if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) ||
@@ -401,7 +405,7 @@
// Stage 1: convert the input path to a set of linear contours (linked list of Vertices).
void GrTriangulator::pathToContours(float tolerance, const SkRect& clipBounds,
- VertexList* contours, bool* isLinear) {
+ VertexList* contours, bool* isLinear) const {
SkScalar toleranceSqd = tolerance * tolerance;
SkPoint pts[4];
*isLinear = true;
@@ -486,7 +490,7 @@
}
}
-bool GrTriangulator::applyFillType(int winding) {
+bool GrTriangulator::applyFillType(int winding) const {
return apply_fill_type(fPath.getFillType(), winding);
}
@@ -494,7 +498,8 @@
return poly && apply_fill_type(fillType, poly->fWinding);
}
-Edge* GrTriangulator::makeEdge(Vertex* prev, Vertex* next, EdgeType type, const Comparator& c) {
+Edge* GrTriangulator::makeEdge(Vertex* prev, Vertex* next, EdgeType type,
+ const Comparator& c) const {
SkASSERT(prev->fPoint != next->fPoint);
int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1;
Vertex* top = winding < 0 ? next : prev;
@@ -649,35 +654,36 @@
}
void GrTriangulator::setTop(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
- const Comparator& c) {
+ const Comparator& c, BreadcrumbTriangleList* breadcrumbList) const {
remove_edge_below(edge);
- if (fBreadcrumbTriangles) {
- fBreadcrumbTriangles->push(edge->fTop->fPoint, edge->fBottom->fPoint, v->fPoint,
- edge->fWinding);
+ if (breadcrumbList) {
+ breadcrumbList->prepend(fAlloc, edge->fTop->fPoint, edge->fBottom->fPoint, v->fPoint,
+ edge->fWinding);
}
edge->fTop = v;
edge->recompute();
edge->insertBelow(v, c);
rewind_if_necessary(edge, activeEdges, current, c);
- this->mergeCollinearEdges(edge, activeEdges, current, c);
+ this->mergeCollinearEdges(edge, activeEdges, current, c, breadcrumbList);
}
void GrTriangulator::setBottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
- const Comparator& c) {
+ const Comparator& c, BreadcrumbTriangleList* breadcrumbList) const {
remove_edge_above(edge);
- if (fBreadcrumbTriangles) {
- fBreadcrumbTriangles->push(edge->fTop->fPoint, edge->fBottom->fPoint, v->fPoint,
- edge->fWinding);
+ if (breadcrumbList) {
+ breadcrumbList->prepend(fAlloc, edge->fTop->fPoint, edge->fBottom->fPoint, v->fPoint,
+ edge->fWinding);
}
edge->fBottom = v;
edge->recompute();
edge->insertAbove(v, c);
rewind_if_necessary(edge, activeEdges, current, c);
- this->mergeCollinearEdges(edge, activeEdges, current, c);
+ this->mergeCollinearEdges(edge, activeEdges, current, c, breadcrumbList);
}
void GrTriangulator::mergeEdgesAbove(Edge* edge, Edge* other, EdgeList* activeEdges,
- Vertex** current, const Comparator& c) {
+ Vertex** current, const Comparator& c,
+ BreadcrumbTriangleList* breadcrumbList) const {
if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) {
TESS_LOG("merging coincident above edges (%g, %g) -> (%g, %g)\n",
edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
@@ -689,16 +695,17 @@
} else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) {
rewind(activeEdges, current, edge->fTop, c);
other->fWinding += edge->fWinding;
- this->setBottom(edge, other->fTop, activeEdges, current, c);
+ this->setBottom(edge, other->fTop, activeEdges, current, c, breadcrumbList);
} else {
rewind(activeEdges, current, other->fTop, c);
edge->fWinding += other->fWinding;
- this->setBottom(other, edge->fTop, activeEdges, current, c);
+ this->setBottom(other, edge->fTop, activeEdges, current, c, breadcrumbList);
}
}
void GrTriangulator::mergeEdgesBelow(Edge* edge, Edge* other, EdgeList* activeEdges,
- Vertex** current, const Comparator& c) {
+ Vertex** current, const Comparator& c,
+ BreadcrumbTriangleList* breadcrumbList) const {
if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) {
TESS_LOG("merging coincident below edges (%g, %g) -> (%g, %g)\n",
edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
@@ -710,11 +717,11 @@
} else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) {
rewind(activeEdges, current, other->fTop, c);
edge->fWinding += other->fWinding;
- this->setTop(other, edge->fBottom, activeEdges, current, c);
+ this->setTop(other, edge->fBottom, activeEdges, current, c, breadcrumbList);
} else {
rewind(activeEdges, current, edge->fTop, c);
other->fWinding += edge->fWinding;
- this->setTop(edge, other->fBottom, activeEdges, current, c);
+ this->setTop(edge, other->fBottom, activeEdges, current, c, breadcrumbList);
}
}
@@ -735,16 +742,21 @@
}
void GrTriangulator::mergeCollinearEdges(Edge* edge, EdgeList* activeEdges, Vertex** current,
- const Comparator& c) {
+ const Comparator& c,
+ BreadcrumbTriangleList* breadcrumbList) const {
for (;;) {
if (top_collinear(edge->fPrevEdgeAbove, edge)) {
- this->mergeEdgesAbove(edge->fPrevEdgeAbove, edge, activeEdges, current, c);
+ this->mergeEdgesAbove(edge->fPrevEdgeAbove, edge, activeEdges, current, c,
+ breadcrumbList);
} else if (top_collinear(edge, edge->fNextEdgeAbove)) {
- this->mergeEdgesAbove(edge->fNextEdgeAbove, edge, activeEdges, current, c);
+ this->mergeEdgesAbove(edge->fNextEdgeAbove, edge, activeEdges, current, c,
+ breadcrumbList);
} else if (bottom_collinear(edge->fPrevEdgeBelow, edge)) {
- this->mergeEdgesBelow(edge->fPrevEdgeBelow, edge, activeEdges, current, c);
+ this->mergeEdgesBelow(edge->fPrevEdgeBelow, edge, activeEdges, current, c,
+ breadcrumbList);
} else if (bottom_collinear(edge, edge->fNextEdgeBelow)) {
- this->mergeEdgesBelow(edge->fNextEdgeBelow, edge, activeEdges, current, c);
+ this->mergeEdgesBelow(edge->fNextEdgeBelow, edge, activeEdges, current, c,
+ breadcrumbList);
} else {
break;
}
@@ -756,7 +768,7 @@
}
bool GrTriangulator::splitEdge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
- const Comparator& c) {
+ const Comparator& c, BreadcrumbTriangleList* breadcrumbList) const {
if (!edge->fTop || !edge->fBottom || v == edge->fTop || v == edge->fBottom) {
return false;
}
@@ -768,25 +780,26 @@
if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) {
top = v;
bottom = edge->fTop;
- this->setTop(edge, v, activeEdges, current, c);
+ this->setTop(edge, v, activeEdges, current, c, breadcrumbList);
} else if (c.sweep_lt(edge->fBottom->fPoint, v->fPoint)) {
top = edge->fBottom;
bottom = v;
- this->setBottom(edge, v, activeEdges, current, c);
+ this->setBottom(edge, v, activeEdges, current, c, breadcrumbList);
} else {
top = v;
bottom = edge->fBottom;
- this->setBottom(edge, v, activeEdges, current, c);
+ this->setBottom(edge, v, activeEdges, current, c, breadcrumbList);
}
Edge* newEdge = fAlloc->make<Edge>(top, bottom, winding, edge->fType);
newEdge->insertBelow(top, c);
newEdge->insertAbove(bottom, c);
- this->mergeCollinearEdges(newEdge, activeEdges, current, c);
+ this->mergeCollinearEdges(newEdge, activeEdges, current, c, breadcrumbList);
return true;
}
bool GrTriangulator::intersectEdgePair(Edge* left, Edge* right, EdgeList* activeEdges,
- Vertex** current, const Comparator& c) {
+ Vertex** current, const Comparator& c,
+ BreadcrumbTriangleList* breadcrumbList) const {
if (!left->fTop || !left->fBottom || !right->fTop || !right->fBottom) {
return false;
}
@@ -796,30 +809,32 @@
if (c.sweep_lt(left->fTop->fPoint, right->fTop->fPoint)) {
if (!left->isLeftOf(right->fTop)) {
rewind(activeEdges, current, right->fTop, c);
- return this->splitEdge(left, right->fTop, activeEdges, current, c);
+ return this->splitEdge(left, right->fTop, activeEdges, current, c, breadcrumbList);
}
} else {
if (!right->isRightOf(left->fTop)) {
rewind(activeEdges, current, left->fTop, c);
- return this->splitEdge(right, left->fTop, activeEdges, current, c);
+ return this->splitEdge(right, left->fTop, activeEdges, current, c, breadcrumbList);
}
}
if (c.sweep_lt(right->fBottom->fPoint, left->fBottom->fPoint)) {
if (!left->isLeftOf(right->fBottom)) {
rewind(activeEdges, current, right->fBottom, c);
- return this->splitEdge(left, right->fBottom, activeEdges, current, c);
+ return this->splitEdge(left, right->fBottom, activeEdges, current, c, breadcrumbList);
}
} else {
if (!right->isRightOf(left->fBottom)) {
rewind(activeEdges, current, left->fBottom, c);
- return this->splitEdge(right, left->fBottom, activeEdges, current, c);
+ return this->splitEdge(right, left->fBottom, activeEdges, current, c, breadcrumbList);
}
}
return false;
}
Edge* GrTriangulator::makeConnectingEdge(Vertex* prev, Vertex* next, EdgeType type,
- const Comparator& c, int windingScale) {
+ const Comparator& c,
+ BreadcrumbTriangleList* breadcrumbList,
+ int windingScale) const {
if (!prev || !next || prev->fPoint == next->fPoint) {
return nullptr;
}
@@ -827,12 +842,13 @@
edge->insertBelow(edge->fTop, c);
edge->insertAbove(edge->fBottom, c);
edge->fWinding *= windingScale;
- this->mergeCollinearEdges(edge, nullptr, nullptr, c);
+ this->mergeCollinearEdges(edge, nullptr, nullptr, c, breadcrumbList);
return edge;
}
void GrTriangulator::mergeVertices(Vertex* src, Vertex* dst, VertexList* mesh,
- const Comparator& c) {
+ const Comparator& c,
+ BreadcrumbTriangleList* breadcrumbList) const {
TESS_LOG("found coincident verts at %g, %g; merging %g into %g\n",
src->fPoint.fX, src->fPoint.fY, src->fID, dst->fID);
dst->fAlpha = std::max(src->fAlpha, dst->fAlpha);
@@ -840,17 +856,17 @@
src->fPartner->fPartner = dst;
}
while (Edge* edge = src->fFirstEdgeAbove) {
- this->setBottom(edge, dst, nullptr, nullptr, c);
+ this->setBottom(edge, dst, nullptr, nullptr, c, breadcrumbList);
}
while (Edge* edge = src->fFirstEdgeBelow) {
- this->setTop(edge, dst, nullptr, nullptr, c);
+ this->setTop(edge, dst, nullptr, nullptr, c, breadcrumbList);
}
mesh->remove(src);
dst->fSynthetic = true;
}
Vertex* GrTriangulator::makeSortedVertex(const SkPoint& p, uint8_t alpha, VertexList* mesh,
- Vertex* reference, const Comparator& c) {
+ Vertex* reference, const Comparator& c) const {
Vertex* prevV = reference;
while (prevV && c.sweep_lt(p, prevV->fPoint)) {
prevV = prevV->fPrev;
@@ -900,7 +916,7 @@
}
}
-void GrTriangulator::computeBisector(Edge* edge1, Edge* edge2, Vertex* v) {
+void GrTriangulator::computeBisector(Edge* edge1, Edge* edge2, Vertex* v) const {
SkASSERT(fEmitCoverage); // Edge-AA only!
Line line1 = edge1->fLine;
Line line2 = edge2->fLine;
@@ -921,7 +937,8 @@
}
bool GrTriangulator::checkForIntersection(Edge* left, Edge* right, EdgeList* activeEdges,
- Vertex** current, VertexList* mesh, const Comparator& c) {
+ Vertex** current, VertexList* mesh, const Comparator& c,
+ BreadcrumbTriangleList* breadcrumbList) const {
if (!left || !right) {
return false;
}
@@ -959,15 +976,15 @@
}
}
rewind(activeEdges, current, top ? top : v, c);
- this->splitEdge(left, v, activeEdges, current, c);
- this->splitEdge(right, v, activeEdges, current, c);
+ this->splitEdge(left, v, activeEdges, current, c, breadcrumbList);
+ this->splitEdge(right, v, activeEdges, current, c, breadcrumbList);
v->fAlpha = std::max(v->fAlpha, alpha);
return true;
}
- return this->intersectEdgePair(left, right, activeEdges, current, c);
+ return this->intersectEdgePair(left, right, activeEdges, current, c, breadcrumbList);
}
-void GrTriangulator::sanitizeContours(VertexList* contours, int contourCnt) {
+void GrTriangulator::sanitizeContours(VertexList* contours, int contourCnt) const {
for (VertexList* contour = contours; contourCnt > 0; --contourCnt, ++contour) {
SkASSERT(contour->fHead);
Vertex* prev = contour->fTail;
@@ -998,7 +1015,8 @@
}
}
-bool GrTriangulator::mergeCoincidentVertices(VertexList* mesh, const Comparator& c) {
+bool GrTriangulator::mergeCoincidentVertices(VertexList* mesh, const Comparator& c,
+ BreadcrumbTriangleList* breadcrumbList) const {
if (!mesh->fHead) {
return false;
}
@@ -1009,7 +1027,7 @@
v->fPoint = v->fPrev->fPoint;
}
if (coincident(v->fPrev->fPoint, v->fPoint)) {
- this->mergeVertices(v, v->fPrev, mesh, c);
+ this->mergeVertices(v, v->fPrev, mesh, c, breadcrumbList);
merged = true;
}
v = next;
@@ -1020,12 +1038,12 @@
// Stage 2: convert the contours to a mesh of edges connecting the vertices.
void GrTriangulator::buildEdges(VertexList* contours, int contourCnt, VertexList* mesh,
- const Comparator& c) {
+ const Comparator& c, BreadcrumbTriangleList* breadcrumbList) const {
for (VertexList* contour = contours; contourCnt > 0; --contourCnt, ++contour) {
Vertex* prev = contour->fTail;
for (Vertex* v = contour->fHead; v;) {
Vertex* next = v->fNext;
- this->makeConnectingEdge(prev, v, EdgeType::kInner, c);
+ this->makeConnectingEdge(prev, v, EdgeType::kInner, c, breadcrumbList);
mesh->append(v);
prev = v;
v = next;
@@ -1098,7 +1116,7 @@
}
#if TRIANGULATOR_LOGGING
-void VertexList::dump() {
+void VertexList::dump() const {
for (Vertex* v = fHead; v; v = v->fNext) {
TESS_LOG("vertex %g (%g, %g) alpha %d", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
if (Vertex* p = v->fPartner) {
@@ -1154,7 +1172,8 @@
// Stage 4: Simplify the mesh by inserting new vertices at intersecting edges.
-GrTriangulator::SimplifyResult GrTriangulator::simplify(VertexList* mesh, const Comparator& c) {
+GrTriangulator::SimplifyResult GrTriangulator::simplify(
+ VertexList* mesh, const Comparator& c, BreadcrumbTriangleList* breadcrumbList) const {
TESS_LOG("simplifying complex polygons\n");
EdgeList activeEdges;
auto result = SimplifyResult::kAlreadySimple;
@@ -1175,9 +1194,9 @@
if (v->fFirstEdgeBelow) {
for (Edge* edge = v->fFirstEdgeBelow; edge; edge = edge->fNextEdgeBelow) {
if (this->checkForIntersection(
- leftEnclosingEdge, edge, &activeEdges, &v, mesh, c) ||
+ leftEnclosingEdge, edge, &activeEdges, &v, mesh, c, breadcrumbList) ||
this->checkForIntersection(
- edge, rightEnclosingEdge, &activeEdges, &v, mesh, c)) {
+ edge, rightEnclosingEdge, &activeEdges, &v, mesh, c, breadcrumbList)) {
if (fDisallowSelfIntersection) {
return SimplifyResult::kAbort;
}
@@ -1188,7 +1207,7 @@
}
} else {
if (this->checkForIntersection(leftEnclosingEdge, rightEnclosingEdge, &activeEdges,
- &v, mesh, c)) {
+ &v, mesh, c, breadcrumbList)) {
if (fDisallowSelfIntersection) {
return SimplifyResult::kAbort;
}
@@ -1216,7 +1235,7 @@
// Stage 5: Tessellate the simplified mesh into monotone polygons.
-Poly* GrTriangulator::tessellate(const VertexList& vertices, const Comparator&) {
+Poly* GrTriangulator::tessellate(const VertexList& vertices, const Comparator&) const {
TESS_LOG("\ntessellating simple polygons\n");
int maxWindMagnitude = std::numeric_limits<int>::max();
if (fDisallowSelfIntersection && !SkPathFillType_IsEvenOdd(fPath.getFillType())) {
@@ -1340,7 +1359,8 @@
// This is a driver function that calls stages 2-5 in turn.
void GrTriangulator::contoursToMesh(VertexList* contours, int contourCnt, VertexList* mesh,
- const Comparator& c) {
+ const Comparator& c,
+ BreadcrumbTriangleList* breadcrumbList) const {
#if TRIANGULATOR_LOGGING
for (int i = 0; i < contourCnt; ++i) {
Vertex* v = contours[i].fHead;
@@ -1352,7 +1372,7 @@
}
#endif
this->sanitizeContours(contours, contourCnt);
- this->buildEdges(contours, contourCnt, mesh, c);
+ this->buildEdges(contours, contourCnt, mesh, c, breadcrumbList);
}
void GrTriangulator::SortMesh(VertexList* vertices, const Comparator& c) {
@@ -1374,15 +1394,16 @@
#endif
}
-Poly* GrTriangulator::contoursToPolys(VertexList* contours, int contourCnt) {
+Poly* GrTriangulator::contoursToPolys(VertexList* contours, int contourCnt,
+ BreadcrumbTriangleList* breadcrumbList) const {
const SkRect& pathBounds = fPath.getBounds();
Comparator c(pathBounds.width() > pathBounds.height() ? Comparator::Direction::kHorizontal
: Comparator::Direction::kVertical);
VertexList mesh;
- this->contoursToMesh(contours, contourCnt, &mesh, c);
+ this->contoursToMesh(contours, contourCnt, &mesh, c, breadcrumbList);
SortMesh(&mesh, c);
- this->mergeCoincidentVertices(&mesh, c);
- if (SimplifyResult::kAbort == this->simplify(&mesh, c)) {
+ this->mergeCoincidentVertices(&mesh, c, breadcrumbList);
+ if (SimplifyResult::kAbort == this->simplify(&mesh, c, breadcrumbList)) {
return nullptr;
}
TESS_LOG("\nsimplified mesh:\n");
@@ -1391,10 +1412,12 @@
}
// Stage 6: Triangulate the monotone polygons into a vertex buffer.
-void* GrTriangulator::polysToTriangles(Poly* polys, void* data, SkPathFillType overrideFillType) {
+void* GrTriangulator::polysToTriangles(Poly* polys, void* data,
+ BreadcrumbTriangleList* breadcrumbList,
+ SkPathFillType overrideFillType) const {
for (Poly* poly = polys; poly; poly = poly->fNext) {
if (apply_fill_type(overrideFillType, poly)) {
- data = this->emitPoly(poly, data);
+ data = this->emitPoly(poly, data, breadcrumbList);
}
}
return data;
@@ -1434,7 +1457,8 @@
return contourCnt;
}
-Poly* GrTriangulator::pathToPolys(float tolerance, const SkRect& clipBounds, bool* isLinear) {
+Poly* GrTriangulator::pathToPolys(float tolerance, const SkRect& clipBounds,
+ BreadcrumbTriangleList* breadcrumbList, bool* isLinear) const {
int contourCnt = get_contour_count(fPath, tolerance);
if (contourCnt <= 0) {
*isLinear = true;
@@ -1447,7 +1471,7 @@
std::unique_ptr<VertexList[]> contours(new VertexList[contourCnt]);
this->pathToContours(tolerance, clipBounds, contours.get(), isLinear);
- return this->contoursToPolys(contours.get(), contourCnt);
+ return this->contoursToPolys(contours.get(), contourCnt, breadcrumbList);
}
int64_t GrTriangulator::CountPoints(Poly* polys, SkPathFillType overrideFillType) {
@@ -1462,7 +1486,8 @@
// Stage 6: Triangulate the monotone polygons into a vertex buffer.
-int GrTriangulator::polysToTriangles(Poly* polys, GrEagerVertexAllocator* vertexAllocator) {
+int GrTriangulator::polysToTriangles(Poly* polys, GrEagerVertexAllocator* vertexAllocator,
+ BreadcrumbTriangleList* breadcrumbList) const {
int64_t count64 = CountPoints(polys, fPath.getFillType());
if (0 == count64 || count64 > SK_MaxS32) {
return 0;
@@ -1480,7 +1505,7 @@
}
TESS_LOG("emitting %d verts\n", count);
- void* end = this->polysToTriangles(polys, verts, fPath.getFillType());
+ void* end = this->polysToTriangles(polys, verts, breadcrumbList, fPath.getFillType());
int actualCount = static_cast<int>((static_cast<uint8_t*>(end) - static_cast<uint8_t*>(verts))
/ vertexStride);
@@ -1494,7 +1519,7 @@
SkArenaAlloc alloc(kArenaDefaultChunkSize);
GrTriangulator triangulator(path, &alloc);
bool isLinear;
- Poly* polys = triangulator.pathToPolys(tolerance, clipBounds, &isLinear);
+ Poly* polys = triangulator.pathToPolys(tolerance, clipBounds, nullptr, &isLinear);
int64_t count64 = CountPoints(polys, path.getFillType());
if (0 == count64 || count64 > SK_MaxS32) {
*verts = nullptr;
@@ -1509,7 +1534,7 @@
for (Poly* poly = polys; poly; poly = poly->fNext) {
if (apply_fill_type(path.getFillType(), poly)) {
SkPoint* start = pointsEnd;
- pointsEnd = static_cast<SkPoint*>(triangulator.emitPoly(poly, pointsEnd));
+ pointsEnd = static_cast<SkPoint*>(triangulator.emitPoly(poly, pointsEnd, nullptr));
while (start != pointsEnd) {
vertsEnd->fPos = *start;
vertsEnd->fWinding = poly->fWinding;
diff --git a/src/gpu/GrTriangulator.h b/src/gpu/GrTriangulator.h
index 9704246..33f30657 100644
--- a/src/gpu/GrTriangulator.h
+++ b/src/gpu/GrTriangulator.h
@@ -31,8 +31,8 @@
GrEagerVertexAllocator* vertexAllocator, bool* isLinear) {
SkArenaAlloc alloc(kArenaDefaultChunkSize);
GrTriangulator triangulator(path, &alloc);
- Poly* polys = triangulator.pathToPolys(tolerance, clipBounds, isLinear);
- int count = triangulator.polysToTriangles(polys, vertexAllocator);
+ Poly* polys = triangulator.pathToPolys(tolerance, clipBounds, nullptr, isLinear);
+ int count = triangulator.polysToTriangles(polys, vertexAllocator, nullptr);
return count;
}
@@ -69,14 +69,65 @@
GrTriangulator(const SkPath& path, SkArenaAlloc* alloc) : fPath(path), fAlloc(alloc) {}
virtual ~GrTriangulator() {}
+ // The breadcrumb triangles serve as a glue that erases T-junctions between a path's outer
+ // curves and its inner polygon triangulation. Drawing a path's outer curves, breadcrumb
+ // triangles, and inner polygon triangulation all together into the stencil buffer has the same
+ // identical rasterized effect as stenciling a classic Redbook fan.
+ //
+ // The breadcrumb triangles track all the edge splits that led from the original inner polygon
+ // edges to the final triangulation. Every time an edge splits, we emit a razor-thin breadcrumb
+ // triangle consisting of the edge's original endpoints and the split point. (We also add
+ // supplemental breadcrumb triangles to areas where abs(winding) > 1.)
+ //
+ // a
+ // /
+ // /
+ // /
+ // x <- Edge splits at x. New breadcrumb triangle is: [a, b, x].
+ // /
+ // /
+ // b
+ //
+ // The opposite-direction shared edges between the triangulation and breadcrumb triangles should
+ // all cancel out, leaving just the set of edges from the original polygon.
+ class BreadcrumbTriangleList {
+ public:
+ void prepend(SkArenaAlloc* alloc, SkPoint a, SkPoint b, SkPoint c, int winding) {
+ if (a == b || a == c || b == c || winding == 0) {
+ return;
+ }
+ if (winding < 0) {
+ std::swap(a, b);
+ winding = -winding;
+ }
+ for (int i = 0; i < winding; ++i) {
+ fHead = alloc->make<Node>(a, b, c, fHead);
+ }
+ fCount += winding;
+ }
+
+ struct Node {
+ Node(SkPoint a, SkPoint b, SkPoint c, const Node* next) : fPts{a, b, c}, fNext(next) {}
+ SkPoint fPts[3];
+ const Node* fNext;
+ };
+ const Node* head() const { return fHead; }
+ int count() const { return fCount; }
+
+ private:
+ const Node* fHead = nullptr;
+ int fCount = 0;
+ };
+
// There are six stages to the basic algorithm:
//
// 1) Linearize the path contours into piecewise linear segments:
void pathToContours(float tolerance, const SkRect& clipBounds, VertexList* contours,
- bool* isLinear);
+ bool* isLinear) const;
// 2) Build a mesh of edges connecting the vertices:
- void contoursToMesh(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&);
+ void contoursToMesh(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&,
+ BreadcrumbTriangleList*) const;
// 3) Sort the vertices in Y (and secondarily in X):
static void SortedMerge(VertexList* front, VertexList* back, VertexList* result,
@@ -90,13 +141,14 @@
kAbort
};
- SimplifyResult simplify(VertexList* mesh, const Comparator&);
+ SimplifyResult simplify(VertexList* mesh, const Comparator&, BreadcrumbTriangleList*) const;
// 5) Tessellate the simplified mesh into monotone polygons:
- virtual Poly* tessellate(const VertexList& vertices, const Comparator&);
+ virtual Poly* tessellate(const VertexList& vertices, const Comparator&) const;
// 6) Triangulate the monotone polygons directly into a vertex buffer:
- void* polysToTriangles(Poly* polys, void* data, SkPathFillType overrideFillType);
+ void* polysToTriangles(Poly* polys, void* data, BreadcrumbTriangleList*,
+ SkPathFillType overrideFillType) const;
// The vertex sorting in step (3) is a merge sort, since it plays well with the linked list
// of vertices (and the necessity of inserting new vertices on intersection).
@@ -142,46 +194,54 @@
// setting rotates 90 degrees counterclockwise, rather that transposing.
// Additional helpers and driver functions.
- void* emitMonotonePoly(const MonotonePoly*, void* data);
- void* emitTriangle(Vertex* prev, Vertex* curr, Vertex* next, int winding, void* data) const;
- void* emitPoly(const Poly*, void *data);
- Poly* makePoly(Poly** head, Vertex* v, int winding);
- void appendPointToContour(const SkPoint& p, VertexList* contour);
- void appendQuadraticToContour(const SkPoint[3], SkScalar toleranceSqd, VertexList* contour);
+ void* emitMonotonePoly(const MonotonePoly*, void* data, BreadcrumbTriangleList*) const;
+ void* emitTriangle(Vertex* prev, Vertex* curr, Vertex* next, int winding, void* data,
+ BreadcrumbTriangleList*) const;
+ void* emitPoly(const Poly*, void *data, BreadcrumbTriangleList*) const;
+ Poly* makePoly(Poly** head, Vertex* v, int winding) const;
+ void appendPointToContour(const SkPoint& p, VertexList* contour) const;
+ void appendQuadraticToContour(const SkPoint[3], SkScalar toleranceSqd,
+ VertexList* contour) const;
void generateCubicPoints(const SkPoint&, const SkPoint&, const SkPoint&, const SkPoint&,
- SkScalar tolSqd, VertexList* contour, int pointsLeft);
- bool applyFillType(int winding);
- Edge* makeEdge(Vertex* prev, Vertex* next, EdgeType type, const Comparator&);
- void setTop(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, const Comparator&);
+ SkScalar tolSqd, VertexList* contour, int pointsLeft) const;
+ bool applyFillType(int winding) const;
+ Edge* makeEdge(Vertex* prev, Vertex* next, EdgeType type, const Comparator&) const;
+ void setTop(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, const Comparator&,
+ BreadcrumbTriangleList*) const;
void setBottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
- const Comparator&);
+ const Comparator&, BreadcrumbTriangleList*) const;
void mergeEdgesAbove(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
- const Comparator&);
+ const Comparator&, BreadcrumbTriangleList*) const;
void mergeEdgesBelow(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
- const Comparator&);
+ const Comparator&, BreadcrumbTriangleList*) const;
Edge* makeConnectingEdge(Vertex* prev, Vertex* next, EdgeType, const Comparator&,
- int windingScale = 1);
- void mergeVertices(Vertex* src, Vertex* dst, VertexList* mesh, const Comparator&);
+ BreadcrumbTriangleList*, int windingScale = 1) const;
+ void mergeVertices(Vertex* src, Vertex* dst, VertexList* mesh, const Comparator&,
+ BreadcrumbTriangleList*) const;
static void FindEnclosingEdges(Vertex* v, EdgeList* edges, Edge** left, Edge** right);
void mergeCollinearEdges(Edge* edge, EdgeList* activeEdges, Vertex** current,
- const Comparator&);
+ const Comparator&, BreadcrumbTriangleList*) const;
bool splitEdge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
- const Comparator&);
+ const Comparator&, BreadcrumbTriangleList*) const;
bool intersectEdgePair(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current,
- const Comparator&);
+ const Comparator&, BreadcrumbTriangleList*) const;
Vertex* makeSortedVertex(const SkPoint&, uint8_t alpha, VertexList* mesh, Vertex* reference,
- const Comparator&);
- void computeBisector(Edge* edge1, Edge* edge2, Vertex*);
+ const Comparator&) const;
+ void computeBisector(Edge* edge1, Edge* edge2, Vertex*) const;
bool checkForIntersection(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current,
- VertexList* mesh, const Comparator&);
- void sanitizeContours(VertexList* contours, int contourCnt);
- bool mergeCoincidentVertices(VertexList* mesh, const Comparator&);
- void buildEdges(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&);
- Poly* contoursToPolys(VertexList* contours, int contourCnt);
- Poly* pathToPolys(float tolerance, const SkRect& clipBounds, bool* isLinear);
+ VertexList* mesh, const Comparator&, BreadcrumbTriangleList*) const;
+ void sanitizeContours(VertexList* contours, int contourCnt) const;
+ bool mergeCoincidentVertices(VertexList* mesh, const Comparator&,
+ BreadcrumbTriangleList*) const;
+ void buildEdges(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&,
+ BreadcrumbTriangleList*) const;
+ Poly* contoursToPolys(VertexList* contours, int contourCnt, BreadcrumbTriangleList*) const;
+ Poly* pathToPolys(float tolerance, const SkRect& clipBounds, BreadcrumbTriangleList*,
+ bool* isLinear) const;
static int64_t CountPoints(Poly* polys, SkPathFillType overrideFillType);
- int polysToTriangles(Poly*, GrEagerVertexAllocator*);
+ int polysToTriangles(Poly*, GrEagerVertexAllocator*, BreadcrumbTriangleList*) const;
+ // FIXME: fPath should be plumbed through function parameters instead.
const SkPath fPath;
SkArenaAlloc* const fAlloc;
@@ -190,45 +250,6 @@
bool fEmitCoverage = false;
bool fCullCollinearVertices = true;
bool fDisallowSelfIntersection = false;
-
- // The breadcrumb triangles serve as a glue that erases T-junctions between a path's outer
- // curves and its inner polygon triangulation. Drawing a path's outer curves, breadcrumb
- // triangles, and inner polygon triangulation all together into the stencil buffer has the same
- // identical rasterized effect as stenciling a classic Redbook fan.
- //
- // The breadcrumb triangles track all the edge splits that led from the original inner polygon
- // edges to the final triangulation. Every time an edge splits, we emit a razor-thin breadcrumb
- // triangle consisting of the edge's original endpoints and the split point. (We also add
- // supplemental breadcrumb triangles to areas where abs(winding) > 1.)
- //
- // a
- // /
- // /
- // /
- // x <- Edge splits at x. New breadcrumb triangle is: [a, b, x].
- // /
- // /
- // b
- //
- // The opposite-direction shared edges between the triangulation and breadcrumb triangles should
- // all cancel out, leaving just the set of edges from the original polygon.
- class BreadcrumbTriangleCollector {
- public:
- void push(SkPoint a, SkPoint b, SkPoint c, int winding) {
- if (a != b && a != c && b != c) {
- if (winding > 0) {
- this->onPush(a, b, c, winding);
- } else if (winding < 0) {
- this->onPush(b, a, c, -winding);
- }
- }
- }
- virtual ~BreadcrumbTriangleCollector() {}
- private:
- virtual void onPush(SkPoint, SkPoint, SkPoint, int winding) = 0;
- };
-
- BreadcrumbTriangleCollector* fBreadcrumbTriangles = nullptr;
};
/**
@@ -301,7 +322,7 @@
}
}
#if TRIANGULATOR_LOGGING
- void dump();
+ void dump() const;
#endif
};
@@ -444,9 +465,6 @@
MonotonePoly* fNext;
int fWinding;
void addEdge(Edge*);
- void* emit(bool emitCoverage, void* data);
- void* emitTriangle(Vertex* prev, Vertex* curr, Vertex* next, bool emitCoverage,
- void* data) const;
};
struct GrTriangulator::Poly {
@@ -466,7 +484,6 @@
#endif
}
Poly* addEdge(Edge* e, Side side, SkArenaAlloc* alloc);
- void* emit(bool emitCoverage, void *data);
Vertex* lastVertex() const { return fTail ? fTail->fLastEdge->fBottom : fFirstVertex; }
Vertex* fFirstVertex;
int fWinding;
diff --git a/src/gpu/tessellate/GrPathTessellateOp.cpp b/src/gpu/tessellate/GrPathTessellateOp.cpp
index 62b9853..ce449ea 100644
--- a/src/gpu/tessellate/GrPathTessellateOp.cpp
+++ b/src/gpu/tessellate/GrPathTessellateOp.cpp
@@ -143,8 +143,8 @@
SkASSERT(fTriangleVertexCount == 0);
SkASSERT(!fStencilTrianglesProgram);
SkASSERT(!fFillTrianglesProgram);
- fInnerFanTriangulator = args.fArena->make<GrInnerFanTriangulator>(fPath, args.fArena, nullptr);
- fInnerFanPolys = fInnerFanTriangulator->pathToPolys(isLinear);
+ fInnerFanTriangulator = args.fArena->make<GrInnerFanTriangulator>(fPath, args.fArena, true);
+ fInnerFanPolys = fInnerFanTriangulator->pathToPolys(nullptr, isLinear);
if (!fInnerFanPolys) {
// pathToPolys will fail if the inner polygon(s) are not simple.
return false;
@@ -385,7 +385,8 @@
// either fOffThreadInnerTriangulation or fTriangleBuffer exclusively.
SkASSERT(fInnerFanTriangulator);
GrEagerDynamicVertexAllocator alloc(flushState, &fTriangleBuffer, &fBaseTriangleVertex);
- fTriangleVertexCount = fInnerFanTriangulator->polysToTriangles(fInnerFanPolys, &alloc);
+ fTriangleVertexCount = fInnerFanTriangulator->polysToTriangles(fInnerFanPolys, &alloc,
+ nullptr);
} else if (fStencilTrianglesProgram) {
// The inner fan isn't built into the tessellator. Generate a standard Redbook fan with a
// middle-out topology.
diff --git a/tests/TriangulatingPathRendererTests.cpp b/tests/TriangulatingPathRendererTests.cpp
index 1271a33..679696d 100644
--- a/tests/TriangulatingPathRendererTests.cpp
+++ b/tests/TriangulatingPathRendererTests.cpp
@@ -790,18 +790,6 @@
SkAutoTMalloc<SkPoint> fPoints;
};
-class SimpleBreadcrumbCollector
- : public GrInnerFanTriangulator::BreadcrumbTriangleCollector, public SkTArray<SkPoint> {
- void onPush(SkPoint p0, SkPoint p1, SkPoint p2, int winding) override {
- SkASSERT(winding > 0);
- for (int i = 0; i < winding; ++i) {
- this->push_back(p0);
- this->push_back(p1);
- this->push_back(p2);
- }
- }
-};
-
} // namespace
struct Edge {
@@ -869,14 +857,14 @@
SkPath path) {
for (auto fillType : {SkPathFillType::kWinding}) {
path.setFillType(fillType);
- SimpleBreadcrumbCollector breadcrumbs;
+ SkArenaAlloc arena(GrTriangulator::kArenaDefaultChunkSize);
+ GrInnerFanTriangulator::BreadcrumbTriangleList breadcrumbs;
SimpleVertexAllocator vertexAlloc;
int vertexCount;
{
bool isLinear;
- SkArenaAlloc arena(GrTriangulator::kArenaDefaultChunkSize);
- GrInnerFanTriangulator triangulator(path, &arena, &breadcrumbs);
- vertexCount = triangulator.pathToTriangles(&vertexAlloc, &isLinear);
+ GrInnerFanTriangulator triangulator(path, &arena);
+ vertexCount = triangulator.pathToTriangles(&vertexAlloc, &breadcrumbs, &isLinear);
}
// Count up all the triangulated edges.
@@ -885,9 +873,12 @@
add_tri_edges(r, trianglePlusBreadcrumbEdges, vertexAlloc.fPoints.data() + i);
}
// Count up all the breadcrumb edges.
- for (int i = 0; i < breadcrumbs.count(); i += 3) {
- add_tri_edges(r, trianglePlusBreadcrumbEdges, breadcrumbs.data() + i);
+ int breadcrumbCount = 0;
+ for (const auto* node = breadcrumbs.head(); node; node = node->fNext) {
+ add_tri_edges(r, trianglePlusBreadcrumbEdges, node->fPts);
+ ++breadcrumbCount;
}
+ REPORTER_ASSERT(r, breadcrumbCount == breadcrumbs.count());
// The triangulated + breadcrumb edges should cancel out to the inner polygon edges.
trianglePlusBreadcrumbEdges = simplify(trianglePlusBreadcrumbEdges, path.getFillType());