| /* |
| * Copyright 2020 Google Inc. |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| |
| #include "src/gpu/GrAATriangulator.h" |
| |
| #include "src/gpu/GrEagerVertexAllocator.h" |
| #include <queue> |
| #include <vector> |
| #include <unordered_map> |
| |
| #if TRIANGULATOR_LOGGING |
| #define TESS_LOG SkDebugf |
| #define DUMP_MESH(MESH) (MESH).dump() |
| #else |
| #define TESS_LOG(...) |
| #define DUMP_MESH(MESH) |
| #endif |
| |
| constexpr static float kCosMiterAngle = 0.97f; // Corresponds to an angle of ~14 degrees. |
| |
| using EdgeType = GrTriangulator::EdgeType; |
| using Vertex = GrTriangulator::Vertex; |
| using VertexList = GrTriangulator::VertexList; |
| using Line = GrTriangulator::Line; |
| using Edge = GrTriangulator::Edge; |
| using EdgeList = GrTriangulator::EdgeList; |
| using Poly = GrTriangulator::Poly; |
| using Comparator = GrTriangulator::Comparator; |
| using SSEdge = GrAATriangulator::SSEdge; |
| using EventList = GrAATriangulator::EventList; |
| using Event = GrAATriangulator::Event; |
| using EventComparator = GrAATriangulator::EventComparator; |
| |
| struct SSVertex { |
| SSVertex(Vertex* v) : fVertex(v), fPrev(nullptr), fNext(nullptr) {} |
| Vertex* fVertex; |
| SSEdge* fPrev; |
| SSEdge* fNext; |
| }; |
| |
| struct GrAATriangulator::SSEdge { |
| SSEdge(Edge* edge, SSVertex* prev, SSVertex* next) |
| : fEdge(edge), fEvent(nullptr), fPrev(prev), fNext(next) { |
| } |
| Edge* fEdge; |
| Event* fEvent; |
| SSVertex* fPrev; |
| SSVertex* fNext; |
| }; |
| |
| typedef std::unordered_map<Vertex*, SSVertex*> SSVertexMap; |
| typedef std::vector<SSEdge*> SSEdgeList; |
| typedef std::priority_queue<Event*, std::vector<Event*>, EventComparator> EventPQ; |
| |
| struct GrAATriangulator::EventList : EventPQ { |
| EventList(EventComparator comparison) : EventPQ(comparison) { |
| } |
| }; |
| |
| 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) { |
| return; |
| } |
| Edge bisector1(prev, prev->fPartner, 1, EdgeType::kConnector); |
| Edge bisector2(next, next->fPartner, 1, EdgeType::kConnector); |
| SkPoint p; |
| uint8_t alpha; |
| if (bisector1.intersect(bisector2, &p, &alpha)) { |
| TESS_LOG("found edge event for %g, %g (original %g -> %g), " |
| "will collapse to %g,%g alpha %d\n", |
| prev->fID, next->fID, e->fEdge->fTop->fID, e->fEdge->fBottom->fID, p.fX, p.fY, |
| alpha); |
| e->fEvent = fAlloc->make<Event>(e, p, alpha); |
| events->push(e->fEvent); |
| } |
| } |
| |
| void GrAATriangulator::makeEvent(SSEdge* edge, Vertex* v, SSEdge* other, Vertex* dest, |
| EventList* events, const Comparator& c) const { |
| if (!v->fPartner) { |
| return; |
| } |
| Vertex* top = edge->fEdge->fTop; |
| Vertex* bottom = edge->fEdge->fBottom; |
| if (!top || !bottom ) { |
| return; |
| } |
| Line line = edge->fEdge->fLine; |
| line.fC = -(dest->fPoint.fX * line.fA + dest->fPoint.fY * line.fB); |
| Edge bisector(v, v->fPartner, 1, EdgeType::kConnector); |
| SkPoint p; |
| uint8_t alpha = dest->fAlpha; |
| if (line.intersect(bisector.fLine, &p) && !c.sweep_lt(p, top->fPoint) && |
| c.sweep_lt(p, bottom->fPoint)) { |
| TESS_LOG("found p edge event for %g, %g (original %g -> %g), " |
| "will collapse to %g,%g alpha %d\n", |
| dest->fID, v->fID, top->fID, bottom->fID, p.fX, p.fY, alpha); |
| edge->fEvent = fAlloc->make<Event>(edge, p, alpha); |
| events->push(edge->fEvent); |
| } |
| } |
| |
| 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); |
| inner->fPartner = outer->fPartner = nullptr; |
| } |
| } |
| } |
| } |
| |
| static void dump_skel(const SSEdgeList& ssEdges) { |
| #if TRIANGULATOR_LOGGING |
| for (SSEdge* edge : ssEdges) { |
| if (edge->fEdge) { |
| TESS_LOG("skel edge %g -> %g", |
| edge->fPrev->fVertex->fID, |
| edge->fNext->fVertex->fID); |
| if (edge->fEdge->fTop && edge->fEdge->fBottom) { |
| TESS_LOG(" (original %g -> %g)\n", |
| edge->fEdge->fTop->fID, |
| edge->fEdge->fBottom->fID); |
| } else { |
| TESS_LOG("\n"); |
| } |
| } |
| } |
| #endif |
| } |
| |
| 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) { |
| if (!v->isConnected()) { |
| continue; |
| } |
| Edge* leftEnclosingEdge; |
| Edge* rightEnclosingEdge; |
| FindEnclosingEdges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge); |
| bool prevFilled = leftEnclosingEdge && this->applyFillType(leftEnclosingEdge->fWinding); |
| for (Edge* e = v->fFirstEdgeAbove; e;) { |
| Edge* next = e->fNextEdgeAbove; |
| activeEdges.remove(e); |
| bool filled = this->applyFillType(e->fWinding); |
| if (filled == prevFilled) { |
| e->disconnect(); |
| } |
| prevFilled = filled; |
| e = next; |
| } |
| Edge* prev = leftEnclosingEdge; |
| for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { |
| if (prev) { |
| e->fWinding += prev->fWinding; |
| } |
| activeEdges.insert(e, prev); |
| prev = e; |
| } |
| } |
| } |
| |
| // Note: this is the normal to the edge, but not necessarily unit length. |
| static void get_edge_normal(const Edge* e, SkVector* normal) { |
| normal->set(SkDoubleToScalar(e->fLine.fA), |
| SkDoubleToScalar(e->fLine.fB)); |
| } |
| |
| // Stage 5c: detect and remove "pointy" vertices whose edge normals point in opposite directions |
| // 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) const { |
| Edge* prevEdge = boundary->fTail; |
| SkVector prevNormal; |
| get_edge_normal(prevEdge, &prevNormal); |
| for (Edge* e = boundary->fHead; e != nullptr;) { |
| Vertex* prev = prevEdge->fWinding == 1 ? prevEdge->fTop : prevEdge->fBottom; |
| Vertex* next = e->fWinding == 1 ? e->fBottom : e->fTop; |
| double distPrev = e->dist(prev->fPoint); |
| double distNext = prevEdge->dist(next->fPoint); |
| SkVector normal; |
| get_edge_normal(e, &normal); |
| constexpr double kQuarterPixelSq = 0.25f * 0.25f; |
| if (prev == next) { |
| boundary->remove(prevEdge); |
| boundary->remove(e); |
| prevEdge = boundary->fTail; |
| e = boundary->fHead; |
| if (prevEdge) { |
| get_edge_normal(prevEdge, &prevNormal); |
| } |
| } else if (prevNormal.dot(normal) < 0.0 && |
| (distPrev * distPrev <= kQuarterPixelSq || distNext * distNext <= kQuarterPixelSq)) { |
| Edge* join = this->makeEdge(prev, next, EdgeType::kInner, c); |
| if (prev->fPoint != next->fPoint) { |
| join->fLine.normalize(); |
| join->fLine = join->fLine * join->fWinding; |
| } |
| boundary->insert(join, e); |
| boundary->remove(prevEdge); |
| boundary->remove(e); |
| if (join->fLeft && join->fRight) { |
| prevEdge = join->fLeft; |
| e = join; |
| } else { |
| prevEdge = boundary->fTail; |
| e = boundary->fHead; // join->fLeft ? join->fLeft : join; |
| } |
| get_edge_normal(prevEdge, &prevNormal); |
| } else { |
| prevEdge = e; |
| prevNormal = normal; |
| e = e->fRight; |
| } |
| } |
| } |
| |
| 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); |
| } 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); |
| v->fPartner->fPartner = dest; |
| v->fPartner = nullptr; |
| } |
| } |
| |
| void GrAATriangulator::Event::apply(VertexList* mesh, const Comparator& c, EventList* events, |
| const GrAATriangulator* triangulator) { |
| if (!fEdge) { |
| return; |
| } |
| Vertex* prev = fEdge->fPrev->fVertex; |
| Vertex* next = fEdge->fNext->fVertex; |
| SSEdge* prevEdge = fEdge->fPrev->fPrev; |
| SSEdge* nextEdge = fEdge->fNext->fNext; |
| if (!prevEdge || !nextEdge || !prevEdge->fEdge || !nextEdge->fEdge) { |
| return; |
| } |
| Vertex* dest = triangulator->makeSortedVertex(fPoint, fAlpha, mesh, prev, c); |
| dest->fSynthetic = true; |
| SSVertex* ssv = triangulator->fAlloc->make<SSVertex>(dest); |
| TESS_LOG("collapsing %g, %g (original edge %g -> %g) to %g (%g, %g) alpha %d\n", |
| prev->fID, next->fID, fEdge->fEdge->fTop->fID, fEdge->fEdge->fBottom->fID, dest->fID, |
| fPoint.fX, fPoint.fY, fAlpha); |
| fEdge->fEdge = nullptr; |
| |
| triangulator->connectSSEdge(prev, dest, c); |
| triangulator->connectSSEdge(next, dest, c); |
| |
| prevEdge->fNext = nextEdge->fPrev = ssv; |
| ssv->fPrev = prevEdge; |
| ssv->fNext = nextEdge; |
| if (!prevEdge->fEdge || !nextEdge->fEdge) { |
| return; |
| } |
| if (prevEdge->fEvent) { |
| prevEdge->fEvent->fEdge = nullptr; |
| } |
| if (nextEdge->fEvent) { |
| nextEdge->fEvent->fEdge = nullptr; |
| } |
| if (prevEdge->fPrev == nextEdge->fNext) { |
| triangulator->connectSSEdge(prevEdge->fPrev->fVertex, dest, c); |
| prevEdge->fEdge = nextEdge->fEdge = nullptr; |
| } else { |
| triangulator->computeBisector(prevEdge->fEdge, nextEdge->fEdge, dest); |
| SkASSERT(prevEdge != fEdge && nextEdge != fEdge); |
| if (dest->fPartner) { |
| triangulator->makeEvent(prevEdge, events); |
| triangulator->makeEvent(nextEdge, events); |
| } else { |
| triangulator->makeEvent(prevEdge, prevEdge->fPrev->fVertex, nextEdge, dest, events, c); |
| triangulator->makeEvent(nextEdge, nextEdge->fNext->fVertex, prevEdge, dest, events, c); |
| } |
| } |
| } |
| |
| static bool is_overlap_edge(Edge* e) { |
| if (e->fType == EdgeType::kOuter) { |
| return e->fWinding != 0 && e->fWinding != 1; |
| } else if (e->fType == EdgeType::kInner) { |
| return e->fWinding != 0 && e->fWinding != -2; |
| } else { |
| return false; |
| } |
| } |
| |
| // 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) const { |
| TESS_LOG("\nfinding overlap regions\n"); |
| EdgeList activeEdges; |
| EventList events(comp); |
| SSVertexMap ssVertices; |
| SSEdgeList ssEdges; |
| for (Vertex* v = mesh->fHead; v != nullptr; v = v->fNext) { |
| if (!v->isConnected()) { |
| continue; |
| } |
| Edge* leftEnclosingEdge; |
| Edge* rightEnclosingEdge; |
| FindEnclosingEdges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge); |
| for (Edge* e = v->fLastEdgeAbove; e && e != leftEnclosingEdge;) { |
| Edge* prev = e->fPrevEdgeAbove ? e->fPrevEdgeAbove : leftEnclosingEdge; |
| activeEdges.remove(e); |
| bool leftOverlap = prev && is_overlap_edge(prev); |
| bool rightOverlap = is_overlap_edge(e); |
| bool isOuterBoundary = e->fType == EdgeType::kOuter && |
| (!prev || prev->fWinding == 0 || e->fWinding == 0); |
| if (prev) { |
| e->fWinding -= prev->fWinding; |
| } |
| if (leftOverlap && rightOverlap) { |
| TESS_LOG("found interior overlap edge %g -> %g, disconnecting\n", |
| e->fTop->fID, e->fBottom->fID); |
| e->disconnect(); |
| } else if (leftOverlap || rightOverlap) { |
| TESS_LOG("found overlap edge %g -> %g%s\n", |
| e->fTop->fID, e->fBottom->fID, |
| isOuterBoundary ? ", is outer boundary" : ""); |
| Vertex* prevVertex = e->fWinding < 0 ? e->fBottom : e->fTop; |
| Vertex* nextVertex = e->fWinding < 0 ? e->fTop : e->fBottom; |
| SSVertex* ssPrev = ssVertices[prevVertex]; |
| if (!ssPrev) { |
| ssPrev = ssVertices[prevVertex] = fAlloc->make<SSVertex>(prevVertex); |
| } |
| SSVertex* ssNext = ssVertices[nextVertex]; |
| if (!ssNext) { |
| ssNext = ssVertices[nextVertex] = fAlloc->make<SSVertex>(nextVertex); |
| } |
| SSEdge* ssEdge = fAlloc->make<SSEdge>(e, ssPrev, ssNext); |
| ssEdges.push_back(ssEdge); |
| // SkASSERT(!ssPrev->fNext && !ssNext->fPrev); |
| ssPrev->fNext = ssNext->fPrev = ssEdge; |
| this->makeEvent(ssEdge, &events); |
| if (!isOuterBoundary) { |
| e->disconnect(); |
| } else { |
| SkASSERT(e->fType != EdgeType::kConnector); |
| // Ensure winding values match expected scale for the edge type. During merging of |
| // collinear edges in overlap regions, windings are summed and so could exceed the |
| // expected +/-1 for outer and +/-2 for inner that is used to fill properly during |
| // subsequent polygon generation. |
| e->fWinding = SkScalarCopySign(e->fType == EdgeType::kInner ? 2 : 1, |
| e->fWinding); |
| } |
| } |
| e = prev; |
| } |
| Edge* prev = leftEnclosingEdge; |
| for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { |
| if (prev) { |
| e->fWinding += prev->fWinding; |
| } |
| activeEdges.insert(e, prev); |
| prev = e; |
| } |
| } |
| bool complex = events.size() > 0; |
| |
| TESS_LOG("\ncollapsing overlap regions\n"); |
| TESS_LOG("skeleton before:\n"); |
| dump_skel(ssEdges); |
| while (events.size() > 0) { |
| Event* event = events.top(); |
| events.pop(); |
| event->apply(mesh, c, &events, this); |
| } |
| TESS_LOG("skeleton after:\n"); |
| dump_skel(ssEdges); |
| for (SSEdge* edge : ssEdges) { |
| if (Edge* e = edge->fEdge) { |
| this->makeConnectingEdge(edge->fPrev->fVertex, edge->fNext->fVertex, e->fType, c, 0); |
| } |
| } |
| return complex; |
| } |
| |
| static bool inversion(Vertex* prev, Vertex* next, Edge* origEdge, const Comparator& c) { |
| if (!prev || !next) { |
| return true; |
| } |
| int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1; |
| return winding != origEdge->fWinding; |
| } |
| |
| // Stage 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 GrAATriangulator::strokeBoundary(EdgeList* boundary, VertexList* innerMesh, |
| 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) { |
| return; |
| } |
| Edge* prevEdge = boundary->fTail; |
| Vertex* prevV = prevEdge->fWinding > 0 ? prevEdge->fTop : prevEdge->fBottom; |
| SkVector prevNormal; |
| get_edge_normal(prevEdge, &prevNormal); |
| double radius = 0.5; |
| Line prevInner(prevEdge->fLine); |
| prevInner.fC -= radius; |
| Line prevOuter(prevEdge->fLine); |
| prevOuter.fC += radius; |
| VertexList innerVertices; |
| VertexList outerVertices; |
| bool innerInversion = true; |
| bool outerInversion = true; |
| for (Edge* e = boundary->fHead; e != nullptr; e = e->fRight) { |
| Vertex* v = e->fWinding > 0 ? e->fTop : e->fBottom; |
| SkVector normal; |
| get_edge_normal(e, &normal); |
| Line inner(e->fLine); |
| inner.fC -= radius; |
| Line outer(e->fLine); |
| outer.fC += radius; |
| SkPoint innerPoint, outerPoint; |
| TESS_LOG("stroking vertex %g (%g, %g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); |
| if (!prevEdge->fLine.nearParallel(e->fLine) && prevInner.intersect(inner, &innerPoint) && |
| prevOuter.intersect(outer, &outerPoint)) { |
| float cosAngle = normal.dot(prevNormal); |
| if (cosAngle < -kCosMiterAngle) { |
| Vertex* nextV = e->fWinding > 0 ? e->fBottom : e->fTop; |
| |
| // This is a pointy vertex whose angle is smaller than the threshold; miter it. |
| Line bisector(innerPoint, outerPoint); |
| Line tangent(v->fPoint, v->fPoint + SkPoint::Make(bisector.fA, bisector.fB)); |
| if (tangent.fA == 0 && tangent.fB == 0) { |
| continue; |
| } |
| tangent.normalize(); |
| Line innerTangent(tangent); |
| Line outerTangent(tangent); |
| innerTangent.fC -= 0.5; |
| outerTangent.fC += 0.5; |
| SkPoint innerPoint1, innerPoint2, outerPoint1, outerPoint2; |
| if (prevNormal.cross(normal) > 0) { |
| // Miter inner points |
| if (!innerTangent.intersect(prevInner, &innerPoint1) || |
| !innerTangent.intersect(inner, &innerPoint2) || |
| !outerTangent.intersect(bisector, &outerPoint)) { |
| continue; |
| } |
| Line prevTangent(prevV->fPoint, |
| prevV->fPoint + SkVector::Make(prevOuter.fA, prevOuter.fB)); |
| Line nextTangent(nextV->fPoint, |
| nextV->fPoint + SkVector::Make(outer.fA, outer.fB)); |
| if (prevTangent.dist(outerPoint) > 0) { |
| bisector.intersect(prevTangent, &outerPoint); |
| } |
| if (nextTangent.dist(outerPoint) < 0) { |
| bisector.intersect(nextTangent, &outerPoint); |
| } |
| outerPoint1 = outerPoint2 = outerPoint; |
| } else { |
| // Miter outer points |
| if (!outerTangent.intersect(prevOuter, &outerPoint1) || |
| !outerTangent.intersect(outer, &outerPoint2)) { |
| continue; |
| } |
| Line prevTangent(prevV->fPoint, |
| prevV->fPoint + SkVector::Make(prevInner.fA, prevInner.fB)); |
| Line nextTangent(nextV->fPoint, |
| nextV->fPoint + SkVector::Make(inner.fA, inner.fB)); |
| if (prevTangent.dist(innerPoint) > 0) { |
| bisector.intersect(prevTangent, &innerPoint); |
| } |
| if (nextTangent.dist(innerPoint) < 0) { |
| bisector.intersect(nextTangent, &innerPoint); |
| } |
| innerPoint1 = innerPoint2 = innerPoint; |
| } |
| if (!innerPoint1.isFinite() || !innerPoint2.isFinite() || |
| !outerPoint1.isFinite() || !outerPoint2.isFinite()) { |
| continue; |
| } |
| TESS_LOG("inner (%g, %g), (%g, %g), ", |
| innerPoint1.fX, innerPoint1.fY, innerPoint2.fX, innerPoint2.fY); |
| TESS_LOG("outer (%g, %g), (%g, %g)\n", |
| outerPoint1.fX, outerPoint1.fY, outerPoint2.fX, outerPoint2.fY); |
| Vertex* innerVertex1 = fAlloc->make<Vertex>(innerPoint1, 255); |
| Vertex* innerVertex2 = fAlloc->make<Vertex>(innerPoint2, 255); |
| Vertex* outerVertex1 = fAlloc->make<Vertex>(outerPoint1, 0); |
| Vertex* outerVertex2 = fAlloc->make<Vertex>(outerPoint2, 0); |
| innerVertex1->fPartner = outerVertex1; |
| innerVertex2->fPartner = outerVertex2; |
| outerVertex1->fPartner = innerVertex1; |
| outerVertex2->fPartner = innerVertex2; |
| if (!inversion(innerVertices.fTail, innerVertex1, prevEdge, c)) { |
| innerInversion = false; |
| } |
| if (!inversion(outerVertices.fTail, outerVertex1, prevEdge, c)) { |
| outerInversion = false; |
| } |
| innerVertices.append(innerVertex1); |
| innerVertices.append(innerVertex2); |
| outerVertices.append(outerVertex1); |
| outerVertices.append(outerVertex2); |
| } else { |
| TESS_LOG("inner (%g, %g), ", innerPoint.fX, innerPoint.fY); |
| TESS_LOG("outer (%g, %g)\n", outerPoint.fX, outerPoint.fY); |
| Vertex* innerVertex = fAlloc->make<Vertex>(innerPoint, 255); |
| Vertex* outerVertex = fAlloc->make<Vertex>(outerPoint, 0); |
| innerVertex->fPartner = outerVertex; |
| outerVertex->fPartner = innerVertex; |
| if (!inversion(innerVertices.fTail, innerVertex, prevEdge, c)) { |
| innerInversion = false; |
| } |
| if (!inversion(outerVertices.fTail, outerVertex, prevEdge, c)) { |
| outerInversion = false; |
| } |
| innerVertices.append(innerVertex); |
| outerVertices.append(outerVertex); |
| } |
| } |
| prevInner = inner; |
| prevOuter = outer; |
| prevV = v; |
| prevEdge = e; |
| prevNormal = normal; |
| } |
| if (!inversion(innerVertices.fTail, innerVertices.fHead, prevEdge, c)) { |
| innerInversion = false; |
| } |
| if (!inversion(outerVertices.fTail, outerVertices.fHead, prevEdge, c)) { |
| outerInversion = false; |
| } |
| // Outer edges get 1 winding, and inner edges get -2 winding. This ensures that the interior |
| // is always filled (1 + -2 = -1 for normal cases, 1 + 2 = 3 for thin features where the |
| // interior inverts). |
| // For total inversion cases, the shape has now reversed handedness, so invert the winding |
| // so it will be detected during collapseOverlapRegions(). |
| 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(innerVertices.fTail, innerVertices.fHead, EdgeType::kInner, c, |
| innerWinding); |
| for (Vertex* v = outerVertices.fHead; v && v->fNext; v = v->fNext) { |
| this->makeConnectingEdge(v, v->fNext, EdgeType::kOuter, c, outerWinding); |
| } |
| this->makeConnectingEdge(outerVertices.fTail, outerVertices.fHead, EdgeType::kOuter, c, |
| outerWinding); |
| innerMesh->append(innerVertices); |
| fOuterMesh.append(outerVertices); |
| } |
| |
| 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; |
| do { |
| e->fWinding = down ? 1 : -1; |
| Edge* next; |
| e->fLine.normalize(); |
| e->fLine = e->fLine * e->fWinding; |
| boundary->append(e); |
| if (down) { |
| // Find outgoing edge, in clockwise order. |
| if ((next = e->fNextEdgeAbove)) { |
| down = false; |
| } else if ((next = e->fBottom->fLastEdgeBelow)) { |
| down = true; |
| } else if ((next = e->fPrevEdgeAbove)) { |
| down = false; |
| } |
| } else { |
| // Find outgoing edge, in counter-clockwise order. |
| if ((next = e->fPrevEdgeBelow)) { |
| down = true; |
| } else if ((next = e->fTop->fFirstEdgeAbove)) { |
| down = false; |
| } else if ((next = e->fNextEdgeBelow)) { |
| down = true; |
| } |
| } |
| e->disconnect(); |
| e = next; |
| } while (e && (down ? e->fTop : e->fBottom) != start); |
| } |
| |
| // 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 { |
| this->removeNonBoundaryEdges(inMesh); |
| for (Vertex* v = inMesh.fHead; v; v = v->fNext) { |
| while (v->fFirstEdgeBelow) { |
| EdgeList boundary; |
| this->extractBoundary(&boundary, v->fFirstEdgeBelow); |
| this->simplifyBoundary(&boundary, c); |
| this->strokeBoundary(&boundary, innerVertices, 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); |
| was_complex = (SimplifyResult::kFoundSelfIntersection == result) || was_complex; |
| result = this->simplify(&fOuterMesh, c); |
| was_complex = (SimplifyResult::kFoundSelfIntersection == result) || was_complex; |
| TESS_LOG("\ninner mesh before:\n"); |
| DUMP_MESH(innerMesh); |
| TESS_LOG("\nouter mesh before:\n"); |
| DUMP_MESH(fOuterMesh); |
| EventComparator eventLT(EventComparator::Op::kLessThan); |
| EventComparator eventGT(EventComparator::Op::kGreaterThan); |
| was_complex = this->collapseOverlapRegions(&innerMesh, c, eventLT) || was_complex; |
| was_complex = this->collapseOverlapRegions(&fOuterMesh, c, eventGT) || was_complex; |
| if (was_complex) { |
| TESS_LOG("found complex mesh; taking slow path\n"); |
| VertexList aaMesh; |
| TESS_LOG("\ninner mesh after:\n"); |
| DUMP_MESH(innerMesh); |
| TESS_LOG("\nouter mesh after:\n"); |
| DUMP_MESH(fOuterMesh); |
| this->connectPartners(&fOuterMesh, c); |
| this->connectPartners(&innerMesh, c); |
| SortedMerge(&innerMesh, &fOuterMesh, &aaMesh, c); |
| TESS_LOG("\nmerged mesh:\n"); |
| DUMP_MESH(aaMesh); |
| this->mergeCoincidentVertices(&aaMesh, c); |
| result = this->simplify(&aaMesh, c); |
| TESS_LOG("combined and simplified mesh:\n"); |
| DUMP_MESH(aaMesh); |
| fOuterMesh.fHead = fOuterMesh.fTail = nullptr; |
| return this->GrTriangulator::tessellate(aaMesh, c); |
| } else { |
| TESS_LOG("no complex polygons; taking fast path\n"); |
| return this->GrTriangulator::tessellate(innerMesh, c); |
| } |
| } |
| |
| 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) { |
| for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { |
| count64 += TRIANGULATOR_WIREFRAME ? 12 : 6; |
| } |
| } |
| if (0 == count64 || count64 > SK_MaxS32) { |
| return 0; |
| } |
| int count = count64; |
| |
| size_t vertexStride = sizeof(SkPoint) + sizeof(float); |
| void* verts = vertexAllocator->lock(vertexStride, count); |
| if (!verts) { |
| SkDebugf("Could not allocate vertices\n"); |
| return 0; |
| } |
| |
| TESS_LOG("emitting %d verts\n", count); |
| void* end = this->polysToTriangles(polys, verts, 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) { |
| Vertex* v0 = e->fTop; |
| 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); |
| } |
| } |
| |
| int actualCount = static_cast<int>((static_cast<uint8_t*>(end) - static_cast<uint8_t*>(verts)) |
| / vertexStride); |
| SkASSERT(actualCount <= count); |
| vertexAllocator->unlock(actualCount); |
| return actualCount; |
| } |
