Update GrTriangulator to skia:c2a399a74da523ec445f1202367764d04b5df2ec Diffs= c83e2f1bc Update GrTriangulator to skia:c2a399a74da523ec445f1202367764d04b5df2ec (#7238) Co-authored-by: Chris Dalton <99840794+csmartdalton@users.noreply.github.com>
diff --git a/.rive_head b/.rive_head index 89189b0..16595e9 100644 --- a/.rive_head +++ b/.rive_head
@@ -1 +1 @@ -3191f5e384df0016a4e82bf113b70b253a06ec35 +c83e2f1bcaa345aa04f719271cab63dfed3466ba
diff --git a/renderer/gr_inner_fan_triangulator.hpp b/renderer/gr_inner_fan_triangulator.hpp index a9b4466..8ec0ba9 100644 --- a/renderer/gr_inner_fan_triangulator.hpp +++ b/renderer/gr_inner_fan_triangulator.hpp
@@ -20,7 +20,7 @@ class GrInnerFanTriangulator : private GrTriangulator { public: - using GrTriangulator::GroutTriangleList; + using GroutTriangleList = GrTriangulator::BreadcrumbTriangleList; GrInnerFanTriangulator(const RawPath& path, const Mat2D& viewMatrix, @@ -31,7 +31,7 @@ m_shouldReverseTriangles(viewMatrix[0] * viewMatrix[3] - viewMatrix[2] * viewMatrix[1] < 0) { fPreserveCollinearVertices = true; - fCollectGroutTriangles = true; + fCollectBreadcrumbTriangles = true; bool isLinear; auto [polys, success] = GrTriangulator::pathToPolys(path, 0, AABB{}, &isLinear); if (success) @@ -60,7 +60,7 @@ bufferRing); } - const GroutTriangleList& groutList() const { return fGroutList; } + const GroutTriangleList& groutList() const { return fBreadcrumbList; } private: // We reverse triangles whe using a left-handed view matrix, in order to ensure we always emit
diff --git a/renderer/gr_triangulator.cpp b/renderer/gr_triangulator.cpp index 45931f9..d282d2f 100644 --- a/renderer/gr_triangulator.cpp +++ b/renderer/gr_triangulator.cpp
@@ -4,13 +4,13 @@ * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. * - * Initial import from skia:src/gpu/ganesh/geometry/GrTriangulator.cpp + * Initial import from + * skia:c2a399a74da523ec445f1202367764d04b5df2ec@src/gpu/ganesh/geometry/GrTriangulator.h * * Copyright 2023 Rive */ #include "gr_triangulator.hpp" -#include "path_utils.hpp" #include <algorithm> @@ -160,8 +160,8 @@ #if 0 static inline void round(Vec2D* p) { - p->x = SkScalarRoundToScalar(p->x * SkFloatToScalar(4.0f)) * SkFloatToScalar(0.25f); - p->y = SkScalarRoundToScalar(p->y * SkFloatToScalar(4.0f)) * SkFloatToScalar(0.25f); + p->x = SkScalarRoundToScalar(p->x * 4.0f) * 0.25f; + p->y = SkScalarRoundToScalar(p->y * 4.0f) * 0.25f; } #endif @@ -376,11 +376,16 @@ list_insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &fHead, &fTail); } -void GrTriangulator::EdgeList::remove(Edge* edge) +bool GrTriangulator::EdgeList::remove(Edge* edge) { TESS_LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); - assert(this->contains(edge)); + // assert(this->contains(edge)); // Leave this here for future debugging. + if (!this->contains(edge)) + { + return false; + } list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &fHead, &fTail); + return true; } void GrTriangulator::MonotonePoly::addEdge(Edge* edge) @@ -575,7 +580,6 @@ } return poly; } - void GrTriangulator::emitPoly(const Poly* poly, uint16_t pathID, bool reverseTriangles, @@ -589,6 +593,7 @@ for (MonotonePoly* m = poly->fHead; m != nullptr; m = m->fNext) { emitMonotonePoly(m, pathID, reverseTriangles, mappedMemory); + ; } } @@ -664,17 +669,16 @@ { float d1 = SkPointPriv::DistanceToLineSegmentBetweenSqd(p1, p0, p3); float d2 = SkPointPriv::DistanceToLineSegmentBetweenSqd(p2, p0, p3); - if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) || !SkScalarIsFinite(d1) || - !SkScalarIsFinite(d2)) + if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) || !SkIsFinite(d1, d2)) { this->appendPointToContour(p3, contour); return; } const Vec2D q[] = {{SkScalarAve(p0.x, p1.x), SkScalarAve(p0.y, p1.y)}, - {SkScalarAve(p1.x, p2.x), SkScalarAve(p1.y, p2.y)}, - {SkScalarAve(p2.x, p3.x), SkScalarAve(p2.y, p3.y)}}; + {SkScalarAve(p1.x, p2.x), SkScalarAve(p1.y, p2.y)}, + {SkScalarAve(p2.x, p3.x), SkScalarAve(p2.y, p3.y)}}; const Vec2D r[] = {{SkScalarAve(q[0].x, q[1].x), SkScalarAve(q[0].y, q[1].y)}, - {SkScalarAve(q[1].x, q[2].x), SkScalarAve(q[1].y, q[2].y)}}; + {SkScalarAve(q[1].x, q[2].x), SkScalarAve(q[1].y, q[2].y)}}; const Vec2D s = {SkScalarAve(r[0].x, r[1].x), SkScalarAve(r[0].y, r[1].y)}; pointsLeft >>= 1; this->generateCubicPoints(p0, q[0], r[0], s, tolSqd, contour, pointsLeft); @@ -692,12 +696,13 @@ { #if 0 float toleranceSqd = tolerance * tolerance; + Vec2D pts[4]; #endif *isLinear = true; VertexList* contour = contours; #if 0 RawPath::Iter iter(fPath, false); - if (fPath.isInverseFillType()) + if (path.isInverseFillType()) { Vec2D quad[4]; clipBounds.toQuad(quad); @@ -714,7 +719,7 @@ switch (verb) { #if 0 - case PathVerb::conic + case SkPath::kConic_Verb: { *isLinear = false; if (toleranceSqd == 0) @@ -831,12 +836,17 @@ return this->allocateEdge(top, bottom, winding, type); } -void EdgeList::insert(Edge* edge, Edge* prev) +bool EdgeList::insert(Edge* edge, Edge* prev) { TESS_LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); - assert(!this->contains(edge)); + // assert(!this->contains(edge)); // Leave this here for debugging. + if (this->contains(edge)) + { + return false; + } Edge* next = prev ? prev->fRight : fHead; this->insert(edge, prev, next); + return true; } void GrTriangulator::FindEnclosingEdges(const Vertex& v, @@ -942,11 +952,11 @@ remove_edge_below(this); } -static void rewind(EdgeList* activeEdges, Vertex** current, Vertex* dst, const Comparator& c) +static bool rewind(EdgeList* activeEdges, Vertex** current, Vertex* dst, const Comparator& c) { if (!current || *current == dst || c.sweep_lt((*current)->fPoint, dst->fPoint)) { - return; + return true; } Vertex* v = *current; TESS_LOG("rewinding active edges from vertex %g to vertex %g\n", v->fID, dst->fID); @@ -955,12 +965,18 @@ v = v->fPrev; for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { - activeEdges->remove(e); + if (!activeEdges->remove(e)) + { + return false; + } } Edge* leftEdge = v->fLeftEnclosingEdge; for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { - activeEdges->insert(e, leftEdge); + if (!activeEdges->insert(e, leftEdge)) + { + return false; + } leftEdge = e; Vertex* top = e->fTop; if (c.sweep_lt(top->fPoint, dst->fPoint) && @@ -972,16 +988,21 @@ } } *current = v; + return true; } -static void rewind_if_necessary(Edge* edge, +static bool rewind_if_necessary(Edge* edge, EdgeList* activeEdges, Vertex** current, const Comparator& c) { if (!activeEdges || !current) { - return; + return true; + } + if (!edge) + { + return false; } Vertex* top = edge->fTop; Vertex* bottom = edge->fBottom; @@ -989,97 +1010,141 @@ { Vertex* leftTop = edge->fLeft->fTop; Vertex* leftBottom = edge->fLeft->fBottom; - if (c.sweep_lt(leftTop->fPoint, top->fPoint) && !edge->fLeft->isLeftOf(*top)) + if (leftTop && leftBottom) { - rewind(activeEdges, current, leftTop, c); - } - else if (c.sweep_lt(top->fPoint, leftTop->fPoint) && !edge->isRightOf(*leftTop)) - { - rewind(activeEdges, current, top, c); - } - else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) && !edge->fLeft->isLeftOf(*bottom)) - { - rewind(activeEdges, current, leftTop, c); - } - else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRightOf(*leftBottom)) - { - rewind(activeEdges, current, top, c); + if (c.sweep_lt(leftTop->fPoint, top->fPoint) && !edge->fLeft->isLeftOf(*top)) + { + if (!rewind(activeEdges, current, leftTop, c)) + { + return false; + } + } + else if (c.sweep_lt(top->fPoint, leftTop->fPoint) && !edge->isRightOf(*leftTop)) + { + if (!rewind(activeEdges, current, top, c)) + { + return false; + } + } + else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) && + !edge->fLeft->isLeftOf(*bottom)) + { + if (!rewind(activeEdges, current, leftTop, c)) + { + return false; + } + } + else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && + !edge->isRightOf(*leftBottom)) + { + if (!rewind(activeEdges, current, top, c)) + { + return false; + } + } } } if (edge->fRight) { Vertex* rightTop = edge->fRight->fTop; Vertex* rightBottom = edge->fRight->fBottom; - if (c.sweep_lt(rightTop->fPoint, top->fPoint) && !edge->fRight->isRightOf(*top)) + if (rightTop && rightBottom) { - rewind(activeEdges, current, rightTop, c); - } - else if (c.sweep_lt(top->fPoint, rightTop->fPoint) && !edge->isLeftOf(*rightTop)) - { - rewind(activeEdges, current, top, c); - } - else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) && - !edge->fRight->isRightOf(*bottom)) - { - rewind(activeEdges, current, rightTop, c); - } - else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) && !edge->isLeftOf(*rightBottom)) - { - rewind(activeEdges, current, top, c); + if (c.sweep_lt(rightTop->fPoint, top->fPoint) && !edge->fRight->isRightOf(*top)) + { + if (!rewind(activeEdges, current, rightTop, c)) + { + return false; + } + } + else if (c.sweep_lt(top->fPoint, rightTop->fPoint) && !edge->isLeftOf(*rightTop)) + { + if (!rewind(activeEdges, current, top, c)) + { + return false; + } + } + else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) && + !edge->fRight->isRightOf(*bottom)) + { + if (!rewind(activeEdges, current, rightTop, c)) + { + return false; + } + } + else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) && + !edge->isLeftOf(*rightBottom)) + { + if (!rewind(activeEdges, current, top, c)) + { + return false; + } + } } } + return true; } -void GrTriangulator::setTop(Edge* edge, +bool GrTriangulator::setTop(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, const Comparator& c) const { remove_edge_below(edge); - if (fCollectGroutTriangles) + if (fCollectBreadcrumbTriangles) { - fGroutList.append(fAlloc, - edge->fTop->fPoint, - edge->fBottom->fPoint, - v->fPoint, - edge->fWinding); + fBreadcrumbList.append(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); + if (!rewind_if_necessary(edge, activeEdges, current, c)) + { + return false; + } + return this->mergeCollinearEdges(edge, activeEdges, current, c); } -void GrTriangulator::setBottom(Edge* edge, +bool GrTriangulator::setBottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, const Comparator& c) const { remove_edge_above(edge); - if (fCollectGroutTriangles) + if (fCollectBreadcrumbTriangles) { - fGroutList.append(fAlloc, - edge->fTop->fPoint, - edge->fBottom->fPoint, - v->fPoint, - edge->fWinding); + fBreadcrumbList.append(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); + if (!rewind_if_necessary(edge, activeEdges, current, c)) + { + return false; + } + return this->mergeCollinearEdges(edge, activeEdges, current, c); } -void GrTriangulator::mergeEdgesAbove(Edge* edge, +bool GrTriangulator::mergeEdgesAbove(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current, const Comparator& c) const { + if (!edge || !other) + { + return false; + } if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) { TESS_LOG("merging coincident above edges (%g, %g) -> (%g, %g)\n", @@ -1087,31 +1152,51 @@ edge->fTop->fPoint.y, edge->fBottom->fPoint.x, edge->fBottom->fPoint.y); - rewind(activeEdges, current, edge->fTop, c); + if (!rewind(activeEdges, current, edge->fTop, c)) + { + return false; + } other->fWinding += edge->fWinding; edge->disconnect(); edge->fTop = edge->fBottom = nullptr; } else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) { - rewind(activeEdges, current, edge->fTop, c); + if (!rewind(activeEdges, current, edge->fTop, c)) + { + return false; + } other->fWinding += edge->fWinding; - this->setBottom(edge, other->fTop, activeEdges, current, c); + if (!this->setBottom(edge, other->fTop, activeEdges, current, c)) + { + return false; + } } else { - rewind(activeEdges, current, other->fTop, c); + if (!rewind(activeEdges, current, other->fTop, c)) + { + return false; + } edge->fWinding += other->fWinding; - this->setBottom(other, edge->fTop, activeEdges, current, c); + if (!this->setBottom(other, edge->fTop, activeEdges, current, c)) + { + return false; + } } + return true; } -void GrTriangulator::mergeEdgesBelow(Edge* edge, +bool GrTriangulator::mergeEdgesBelow(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current, const Comparator& c) const { + if (!edge || !other) + { + return false; + } if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) { TESS_LOG("merging coincident below edges (%g, %g) -> (%g, %g)\n", @@ -1119,23 +1204,39 @@ edge->fTop->fPoint.y, edge->fBottom->fPoint.x, edge->fBottom->fPoint.y); - rewind(activeEdges, current, edge->fTop, c); + if (!rewind(activeEdges, current, edge->fTop, c)) + { + return false; + } other->fWinding += edge->fWinding; edge->disconnect(); edge->fTop = edge->fBottom = nullptr; } else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) { - rewind(activeEdges, current, other->fTop, c); + if (!rewind(activeEdges, current, other->fTop, c)) + { + return false; + } edge->fWinding += other->fWinding; - this->setTop(other, edge->fBottom, activeEdges, current, c); + if (!this->setTop(other, edge->fBottom, activeEdges, current, c)) + { + return false; + } } else { - rewind(activeEdges, current, edge->fTop, c); + if (!rewind(activeEdges, current, edge->fTop, c)) + { + return false; + } other->fWinding += edge->fWinding; - this->setTop(edge, other->fBottom, activeEdges, current, c); + if (!this->setTop(edge, other->fBottom, activeEdges, current, c)) + { + return false; + } } + return true; } static bool top_collinear(Edge* left, Edge* right) @@ -1158,7 +1259,7 @@ !right->isRightOf(*left->fBottom); } -void GrTriangulator::mergeCollinearEdges(Edge* edge, +bool GrTriangulator::mergeCollinearEdges(Edge* edge, EdgeList* activeEdges, Vertex** current, const Comparator& c) const @@ -1167,19 +1268,31 @@ { if (top_collinear(edge->fPrevEdgeAbove, edge)) { - this->mergeEdgesAbove(edge->fPrevEdgeAbove, edge, activeEdges, current, c); + if (!this->mergeEdgesAbove(edge->fPrevEdgeAbove, edge, activeEdges, current, c)) + { + return false; + } } else if (top_collinear(edge, edge->fNextEdgeAbove)) { - this->mergeEdgesAbove(edge->fNextEdgeAbove, edge, activeEdges, current, c); + if (!this->mergeEdgesAbove(edge->fNextEdgeAbove, edge, activeEdges, current, c)) + { + return false; + } } else if (bottom_collinear(edge->fPrevEdgeBelow, edge)) { - this->mergeEdgesBelow(edge->fPrevEdgeBelow, edge, activeEdges, current, c); + if (!this->mergeEdgesBelow(edge->fPrevEdgeBelow, edge, activeEdges, current, c)) + { + return false; + } } else if (bottom_collinear(edge, edge->fNextEdgeBelow)) { - this->mergeEdgesBelow(edge->fNextEdgeBelow, edge, activeEdges, current, c); + if (!this->mergeEdgesBelow(edge->fNextEdgeBelow, edge, activeEdges, current, c)) + { + return false; + } } else { @@ -1190,17 +1303,18 @@ assert(!top_collinear(edge, edge->fNextEdgeAbove)); assert(!bottom_collinear(edge->fPrevEdgeBelow, edge)); assert(!bottom_collinear(edge, edge->fNextEdgeBelow)); + return true; } -bool GrTriangulator::splitEdge(Edge* edge, - Vertex* v, - EdgeList* activeEdges, - Vertex** current, - const Comparator& c) +GrTriangulator::BoolFail GrTriangulator::splitEdge(Edge* edge, + Vertex* v, + EdgeList* activeEdges, + Vertex** current, + const Comparator& c) { if (!edge->fTop || !edge->fBottom || v == edge->fTop || v == edge->fBottom) { - return false; + return BoolFail::kFalse; } TESS_LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n", edge->fTop->fID, @@ -1221,7 +1335,10 @@ top = v; bottom = edge->fTop; winding *= -1; - this->setTop(edge, v, activeEdges, current, c); + if (!this->setTop(edge, v, activeEdges, current, c)) + { + return BoolFail::kFail; + } } else if (c.sweep_lt(edge->fBottom->fPoint, v->fPoint)) { @@ -1230,7 +1347,10 @@ top = edge->fBottom; bottom = v; winding *= -1; - this->setBottom(edge, v, activeEdges, current, c); + if (!this->setBottom(edge, v, activeEdges, current, c)) + { + return BoolFail::kFail; + } } else { @@ -1238,28 +1358,34 @@ // is valid for both edges. top = v; bottom = edge->fBottom; - this->setBottom(edge, v, activeEdges, current, c); + if (!this->setBottom(edge, v, activeEdges, current, c)) + { + return BoolFail::kFail; + } } Edge* newEdge = this->allocateEdge(top, bottom, winding, edge->fType); newEdge->insertBelow(top, c); newEdge->insertAbove(bottom, c); - this->mergeCollinearEdges(newEdge, activeEdges, current, c); - return true; + if (!this->mergeCollinearEdges(newEdge, activeEdges, current, c)) + { + return BoolFail::kFail; + } + return BoolFail::kTrue; } -bool GrTriangulator::intersectEdgePair(Edge* left, - Edge* right, - EdgeList* activeEdges, - Vertex** current, - const Comparator& c) +GrTriangulator::BoolFail GrTriangulator::intersectEdgePair(Edge* left, + Edge* right, + EdgeList* activeEdges, + Vertex** current, + const Comparator& c) { if (!left->fTop || !left->fBottom || !right->fTop || !right->fBottom) { - return false; + return BoolFail::kFalse; } if (left->fTop == right->fTop || left->fBottom == right->fBottom) { - return false; + return BoolFail::kFalse; } // Check if the lines intersect as determined by isLeftOf and isRightOf, since that is the @@ -1303,12 +1429,15 @@ if (!split) { - return false; + return BoolFail::kFalse; } // Rewind to the top of the edge that is "moving" since this topology correction can change the // geometry of the split edge. - rewind(activeEdges, current, split->fTop, c); + if (!rewind(activeEdges, current, split->fTop, c)) + { + return BoolFail::kFail; + } return this->splitEdge(split, splitAt, activeEdges, current, c); } @@ -1347,11 +1476,11 @@ } while (Edge* edge = src->fFirstEdgeAbove) { - this->setBottom(edge, dst, nullptr, nullptr, c); + std::ignore = this->setBottom(edge, dst, nullptr, nullptr, c); } while (Edge* edge = src->fFirstEdgeBelow) { - this->setTop(edge, dst, nullptr, nullptr, c); + std::ignore = this->setTop(edge, dst, nullptr, nullptr, c); } mesh->remove(src); dst->fSynthetic = true; @@ -1450,19 +1579,24 @@ } #endif -bool GrTriangulator::checkForIntersection(Edge* left, - Edge* right, - EdgeList* activeEdges, - Vertex** current, - VertexList* mesh, - const Comparator& c) +GrTriangulator::BoolFail GrTriangulator::checkForIntersection(Edge* left, + Edge* right, + EdgeList* activeEdges, + Vertex** current, + VertexList* mesh, + const Comparator& c) { if (!left || !right) { - return false; + return BoolFail::kFalse; } Vec2D p; uint8_t alpha; + // If we are going to call intersect, then there must be tops and bottoms. + if (!left->fTop || !left->fBottom || !right->fTop || !right->fBottom) + { + return BoolFail::kFail; + } if (left->intersect(*right, &p, &alpha) && is_finite(p)) { Vertex* v; @@ -1509,11 +1643,20 @@ } #endif } - rewind(activeEdges, current, top ? top : v, c); - this->splitEdge(left, v, activeEdges, current, c); - this->splitEdge(right, v, activeEdges, current, c); + if (!rewind(activeEdges, current, top ? top : v, c)) + { + return BoolFail::kFail; + } + if (this->splitEdge(left, v, activeEdges, current, c) == BoolFail::kFail) + { + return BoolFail::kFail; + } + if (this->splitEdge(right, v, activeEdges, current, c) == BoolFail::kFail) + { + return BoolFail::kFail; + } v->fAlpha = std::max(v->fAlpha, alpha); - return true; + return BoolFail::kTrue; } return this->intersectEdgePair(left, right, activeEdges, current, c); } @@ -1781,6 +1924,7 @@ TESS_LOG("simplifying complex polygons\n"); int initialNumEdges = fNumEdges; + int numSelfIntersections = 0; EdgeList activeEdges; auto result = SimplifyResult::kAlreadySimple; @@ -1799,6 +1943,13 @@ return SimplifyResult::kFailed; } + // In pathological cases, a path can intersect itself millions of times. After 500,000 + // self-intersections are found, reject the path. + if (numSelfIntersections > 500000) + { + return SimplifyResult::kFailed; + } + Edge* leftEnclosingEdge; Edge* rightEnclosingEdge; bool restartChecks; @@ -1817,36 +1968,59 @@ { for (Edge* edge = v->fFirstEdgeBelow; edge; edge = edge->fNextEdgeBelow) { - if (this->checkForIntersection(leftEnclosingEdge, - edge, - &activeEdges, - &v, - mesh, - c) || - this->checkForIntersection(edge, - rightEnclosingEdge, - &activeEdges, - &v, - mesh, - c)) + BoolFail l = this->checkForIntersection(leftEnclosingEdge, + edge, + &activeEdges, + &v, + mesh, + c); + if (l == BoolFail::kFail) { - result = SimplifyResult::kFoundSelfIntersection; - restartChecks = true; - break; + return SimplifyResult::kFailed; } - } + if (l == BoolFail::kFalse) + { + BoolFail r = this->checkForIntersection(edge, + rightEnclosingEdge, + &activeEdges, + &v, + mesh, + c); + if (r == BoolFail::kFail) + { + return SimplifyResult::kFailed; + } + if (r == BoolFail::kFalse) + { + // Neither l and r are both false. + continue; + } + } + + // Either l or r are true. + result = SimplifyResult::kFoundSelfIntersection; + restartChecks = true; + ++numSelfIntersections; + break; + } // for } else { - if (this->checkForIntersection(leftEnclosingEdge, - rightEnclosingEdge, - &activeEdges, - &v, - mesh, - c)) + BoolFail bf = this->checkForIntersection(leftEnclosingEdge, + rightEnclosingEdge, + &activeEdges, + &v, + mesh, + c); + if (bf == BoolFail::kFail) + { + return SimplifyResult::kFailed; + } + if (bf == BoolFail::kTrue) { result = SimplifyResult::kFoundSelfIntersection; restartChecks = true; + ++numSelfIntersections; } } } while (restartChecks); @@ -1855,7 +2029,10 @@ #endif for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { - activeEdges.remove(e); + if (!activeEdges.remove(e)) + { + return SimplifyResult::kFailed; + } } Edge* leftEdge = leftEnclosingEdge; for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) @@ -2086,13 +2263,13 @@ // Stage 6: Triangulate the monotone polygons into a vertex buffer. void GrTriangulator::polysToTriangles( - const Poly* polys, + Poly* polys, FillRule overrideFillType, uint16_t pathID, bool reverseTriangles, pls::WriteOnlyMappedMemory<pls::TriangleVertex>* mappedMemory) const { - for (const Poly* poly = polys; poly; poly = poly->fNext) + for (Poly* poly = polys; poly; poly = poly->fNext) { if (apply_fill_type(overrideFillType, poly)) { @@ -2160,10 +2337,10 @@ return this->contoursToPolys(contours.get(), contourCnt); } -int64_t GrTriangulator::CountPoints(const Poly* polys, FillRule overrideFillType) +int64_t GrTriangulator::CountPoints(Poly* polys, FillRule overrideFillType) { int64_t count = 0; - for (const Poly* poly = polys; poly; poly = poly->fNext) + for (Poly* poly = polys; poly; poly = poly->fNext) { if (apply_fill_type(overrideFillType, poly) && poly->fCount >= 3) { @@ -2175,13 +2352,13 @@ // Stage 6: Triangulate the monotone polygons into a vertex buffer. -size_t GrTriangulator::countMaxTriangleVertices(const Poly* polys) const +size_t GrTriangulator::countMaxTriangleVertices(Poly* polys) const { return CountPoints(polys, fFillRule); } size_t GrTriangulator::polysToTriangles( - const Poly* polys, + Poly* polys, uint64_t maxVertexCount, uint16_t pathID, bool reverseTriangles, @@ -2192,8 +2369,6 @@ return 0; } - TESS_LOG("emitting %d verts\n", count); - size_t vertexStride = sizeof(pls::TriangleVertex); #if 0 if (fEmitCoverage)
diff --git a/renderer/gr_triangulator.hpp b/renderer/gr_triangulator.hpp index 635d301..dad30cf 100644 --- a/renderer/gr_triangulator.hpp +++ b/renderer/gr_triangulator.hpp
@@ -4,7 +4,8 @@ * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. * - * Initial import from skia:src/gpu/ganesh/geometry/GrTriangulator.h + * Initial import from + * skia:c2a399a74da523ec445f1202367764d04b5df2ec@src/gpu/ganesh/geometry/GrTriangulator.h * * Copyright 2023 Rive */ @@ -33,18 +34,6 @@ public: constexpr static int kArenaDefaultChunkSize = 16 * 1024; - struct Comparator - { - enum class Direction - { - kVertical, - kHorizontal - }; - Comparator(Direction direction) : fDirection(direction) {} - bool sweep_lt(const Vec2D& a, const Vec2D& b) const; - Direction fDirection; - }; - // Enums used by GrTriangulator internals. typedef enum { @@ -67,6 +56,18 @@ struct MonotonePoly; struct Poly; + struct Comparator + { + enum class Direction + { + kVertical, + kHorizontal + }; + Comparator(Direction direction) : fDirection(direction) {} + bool sweep_lt(const Vec2D& a, const Vec2D& b) const; + Direction fDirection; + }; + protected: GrTriangulator(Comparator::Direction direction, FillRule fillRule, @@ -101,13 +102,20 @@ kFoundSelfIntersection }; + enum class BoolFail + { + kFalse, + kTrue, + kFail + }; + [[nodiscard]] SimplifyResult simplify(VertexList* mesh, const Comparator&); // 5) Tessellate the simplified mesh into monotone polygons: virtual std::tuple<Poly*, bool> tessellate(const VertexList& vertices, const Comparator&); // 6) Triangulate the monotone polygons directly into a vertex buffer: - void polysToTriangles(const Poly* polys, + void polysToTriangles(Poly* polys, FillRule overrideFillRule, uint16_t pathID, bool reverseTriangles, @@ -187,26 +195,26 @@ MonotonePoly* allocateMonotonePoly(Edge* edge, Side side, int winding); Edge* allocateEdge(Vertex* top, Vertex* bottom, int winding, EdgeType type); Edge* makeEdge(Vertex* prev, Vertex* next, EdgeType type, const Comparator&); - void setTop(Edge* edge, - Vertex* v, - EdgeList* activeEdges, - Vertex** current, - const Comparator&) const; - void setBottom(Edge* edge, - Vertex* v, - EdgeList* activeEdges, - Vertex** current, - const Comparator&) const; - void mergeEdgesAbove(Edge* edge, - Edge* other, - EdgeList* activeEdges, - Vertex** current, - const Comparator&) const; - void mergeEdgesBelow(Edge* edge, - Edge* other, - EdgeList* activeEdges, - Vertex** current, - const Comparator&) const; + [[nodiscard]] bool setTop(Edge* edge, + Vertex* v, + EdgeList* activeEdges, + Vertex** current, + const Comparator&) const; + [[nodiscard]] bool setBottom(Edge* edge, + Vertex* v, + EdgeList* activeEdges, + Vertex** current, + const Comparator&) const; + [[nodiscard]] bool mergeEdgesAbove(Edge* edge, + Edge* other, + EdgeList* activeEdges, + Vertex** current, + const Comparator&) const; + [[nodiscard]] bool mergeEdgesBelow(Edge* edge, + Edge* other, + EdgeList* activeEdges, + Vertex** current, + const Comparator&) const; Edge* makeConnectingEdge(Vertex* prev, Vertex* next, EdgeType, @@ -217,34 +225,32 @@ const EdgeList& edges, Edge** left, Edge** right); - void mergeCollinearEdges(Edge* edge, + bool mergeCollinearEdges(Edge* edge, EdgeList* activeEdges, Vertex** current, const Comparator&) const; - bool splitEdge(Edge* edge, - Vertex* v, - EdgeList* activeEdges, - Vertex** current, - const Comparator&); - bool intersectEdgePair(Edge* left, - Edge* right, - EdgeList* activeEdges, - Vertex** current, - const Comparator&); + BoolFail splitEdge(Edge* edge, + Vertex* v, + EdgeList* activeEdges, + Vertex** current, + const Comparator&); + BoolFail intersectEdgePair(Edge* left, + Edge* right, + EdgeList* activeEdges, + Vertex** current, + const Comparator&); Vertex* makeSortedVertex(const Vec2D&, uint8_t alpha, VertexList* mesh, Vertex* reference, const Comparator&) const; -#if 0 void computeBisector(Edge* edge1, Edge* edge2, Vertex*) const; -#endif - bool checkForIntersection(Edge* left, - Edge* right, - EdgeList* activeEdges, - Vertex** current, - VertexList* mesh, - const Comparator&); + BoolFail checkForIntersection(Edge* left, + Edge* right, + EdgeList* activeEdges, + Vertex** current, + VertexList* mesh, + const Comparator&); void sanitizeContours(VertexList* contours, int contourCnt) const; bool mergeCoincidentVertices(VertexList* mesh, const Comparator&) const; void buildEdges(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&); @@ -253,9 +259,9 @@ float tolerance, const AABB& clipBounds, bool* isLinear); - static int64_t CountPoints(const Poly* polys, FillRule overrideFillRule); - size_t countMaxTriangleVertices(const Poly*) const; - size_t polysToTriangles(const Poly*, + static int64_t CountPoints(Poly* polys, FillRule overrideFillRule); + size_t countMaxTriangleVertices(Poly*) const; + size_t polysToTriangles(Poly*, uint64_t maxVertexCount, uint16_t pathID, bool reverseTriangles, @@ -263,7 +269,7 @@ Comparator::Direction fDirection; FillRule fFillRule; - TrivialBlockAllocator* fAlloc; + TrivialBlockAllocator* const fAlloc; int fNumMonotonePolys = 0; int fNumEdges = 0; @@ -273,30 +279,30 @@ bool fEmitCoverage = false; #endif bool fPreserveCollinearVertices = false; - bool fCollectGroutTriangles = false; + bool fCollectBreadcrumbTriangles = false; - // The grout 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, grout + // 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 grout 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 grout + // 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 grout triangles to areas where abs(winding) > 1.) + // supplemental breadcrumb triangles to areas where abs(winding) > 1.) // // a // / // / // / - // x <- Edge splits at x. New grout triangle is: [a, b, x]. + // x <- Edge splits at x. New breadcrumb triangle is: [a, b, x]. // / // / // b // - // The opposite-direction shared edges between the triangulation and grout triangles should + // 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 GroutTriangleList + class BreadcrumbTriangleList { public: struct Node @@ -328,7 +334,7 @@ fCount += winding; } - void concat(GroutTriangleList&& list) + void concat(BreadcrumbTriangleList&& list) { assert(fTail && !(*fTail)); if (list.fHead) @@ -348,7 +354,7 @@ int fCount = 0; }; - mutable GroutTriangleList fGroutList; + mutable BreadcrumbTriangleList fBreadcrumbList; }; /** @@ -473,10 +479,8 @@ return fabs(o.fA - fA) < 0.00001 && fabs(o.fB - fB) < 0.00001; } -#if 0 // Compute the intersection of two (infinite) Lines. bool intersect(const Line& other, Vec2D* point) const; -#endif double fA, fB, fC; }; @@ -563,9 +567,9 @@ Edge* fHead; Edge* fTail; void insert(Edge* edge, Edge* prev, Edge* next); - void insert(Edge* edge, Edge* prev); + bool insert(Edge* edge, Edge* prev); void append(Edge* e) { insert(e, fTail, nullptr); } - void remove(Edge* edge); + bool remove(Edge* edge); void removeAll() { while (fHead)