31#if !defined(SK_ENABLE_OPTIMIZE_SIZE)
33#if TRIANGULATOR_LOGGING
34#define TESS_LOG printf
35#define DUMP_MESH(M) (M).dump()
51template <
class T, T* T::*Prev, T* T::*Next>
67template <
class T, T* T::*Prev, T* T::*Next>
70 t->*Prev->*Next = t->*Next;
75 t->*Next->*Prev = t->*Prev;
79 t->*Prev = t->*Next =
nullptr;
85 return a.fX <
b.fX || (
a.fX ==
b.fX &&
a.fY >
b.fY);
89 return a.fY <
b.fY || (
a.fY ==
b.fY &&
a.fX <
b.fX);
110 TESS_LOG(
"emit_triangle %g (%g, %g) %d\n", v0->fID, v0->fPoint.
fX, v0->fPoint.
fY, v0->fAlpha);
111 TESS_LOG(
" %g (%g, %g) %d\n", v1->fID, v1->fPoint.
fX, v1->fPoint.
fY, v1->fAlpha);
112 TESS_LOG(
" %g (%g, %g) %d\n",
v2->fID,
v2->fPoint.fX,
v2->fPoint.fY,
v2->fAlpha);
113#if TRIANGULATOR_WIREFRAME
114 data =
emit_vertex(v0, emitCoverage, std::move(data));
115 data =
emit_vertex(v1, emitCoverage, std::move(data));
116 data =
emit_vertex(v1, emitCoverage, std::move(data));
119 data =
emit_vertex(v0, emitCoverage, std::move(data));
121 data =
emit_vertex(v0, emitCoverage, std::move(data));
122 data =
emit_vertex(v1, emitCoverage, std::move(data));
129 list_insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v,
prev,
next, &fHead, &fTail);
133 list_remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, &fHead, &fTail);
148 static const double kNearZeroLimit = 16 * (double) std::numeric_limits<float>::min();
149 if (std::abs(
d) < kNearZeroLimit) {
156 double denom = fA * other.
fB - fB * other.
fA;
160 double scale = 1.0 / denom;
174 int expDiffX = std::abs((std::abs(p0.
fX) < 1.f ? 0 : std::ilogbf(p0.
fX)) -
175 (std::abs(p1.
fX) < 1.f ? 0 : std::ilogbf(p1.
fX)));
176 int expDiffY = std::abs((std::abs(p0.
fY) < 1.f ? 0 : std::ilogbf(p0.
fY)) -
177 (std::abs(p1.
fY) < 1.f ? 0 : std::ilogbf(p1.
fY)));
179 return expDiffX > 20 || expDiffY > 20;
189 if (std::min(u0.
fX, u1.
fX) > std::max(v0.
fX, v1.
fX) ||
190 std::max(u0.
fX, u1.
fX) < std::min(v0.
fX, v1.
fX) ||
191 std::min(u0.
fY, u1.
fY) > std::max(v0.
fY, v1.
fY) ||
192 std::max(u0.
fY, u1.
fY) < std::min(v0.
fY, v1.
fY)) {
200 double denom = u.
fA * v.
fB - u.
fB * v.
fA;
204 double dx =
static_cast<double>(v0.
fX) - u0.
fX;
205 double dy =
static_cast<double>(v0.
fY) - u0.
fY;
206 double sNumer = dy * v.
fB + dx * v.
fA;
207 double tNumer = dy * u.
fB + dx * u.
fA;
210 if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNumer > denom)
211 : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNumer < denom)) {
217 SkASSERT(*
s >= 0.0 && *s <= 1.0 && *t >= 0.0 && *t <= 1.0);
221 if (!uNeedsSplit && !vNeedsSplit) {
226 double sScale = 1.0, sShift = 0.0;
227 double tScale = 1.0, tShift = 0.0;
231 (float) (0.5 * u0.
fY + 0.5 * u1.
fY)};
242 (float) (0.5 * v0.
fY + 0.5 * v1.
fY)};
253 if (
recursive_edge_intersect(
Line(u0, u1), u0, u1,
Line(v0, v1), v0, v1, p,
s, t)) {
255 *
s = sScale * (*s) + sShift;
256 *t = tScale * (*t) + tShift;
266 TESS_LOG(
"intersecting %g -> %g with %g -> %g\n",
267 fTop->fID, fBottom->fID, other.
fTop->fID, other.
fBottom->fID);
268 if (fTop == other.
fTop || fBottom == other.
fBottom ||
277 fLine, fTop->fPoint, fBottom->fPoint,
285 if (fType == EdgeType::kInner || other.
fType == EdgeType::kInner) {
289 }
else if (fType == EdgeType::kOuter && other.
fType == EdgeType::kOuter) {
296 SkASSERT(fType == EdgeType::kConnector || other.
fType == EdgeType::kConnector);
297 *alpha = std::max((1.0 -
s) * fTop->fAlpha +
s * fBottom->fAlpha,
305 list_insert<Edge, &Edge::fLeft, &Edge::fRight>(edge,
prev,
next, &fHead, &fTail);
314 list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &fHead, &fTail);
321 list_insert<Edge, &Edge::fRightPolyPrev, &Edge::fRightPolyNext>(
322 edge, fLastEdge,
nullptr, &fFirstEdge, &fLastEdge);
326 list_insert<Edge, &Edge::fLeftPolyPrev, &Edge::fLeftPolyNext>(
327 edge, fLastEdge,
nullptr, &fFirstEdge, &fLastEdge);
339 while (e !=
nullptr) {
341 vertices.
append(e->fBottom);
342 e = e->fRightPolyNext;
345 e = e->fLeftPolyNext;
351 while (v != vertices.
fTail) {
359 double ax =
static_cast<double>(curr->
fPoint.
fX) -
prev->fPoint.fX;
360 double ay =
static_cast<double>(curr->
fPoint.
fY) -
prev->fPoint.fY;
361 double bx =
static_cast<double>(
next->fPoint.fX) - curr->
fPoint.
fX;
362 double by =
static_cast<double>(
next->fPoint.fY) - curr->
fPoint.
fY;
363 if (
ax * by - ay * bx >= 0.0) {
368 if (v->
fPrev == first) {
405#if TRIANGULATOR_LOGGING
408 TESS_LOG(
"*** created Poly %d\n", fID);
413 TESS_LOG(
"addEdge (%g -> %g) to poly %d, %s side\n",
414 e->fTop->fID, e->fBottom->fID, fID,
side ==
kLeft_Side ?
"left" :
"right");
415 Poly* partner = fPartner;
418 if (e->fUsedInRightPoly) {
422 if (e->fUsedInLeftPoly) {
427 fPartner = partner->
fPartner =
nullptr;
432 }
else if (e->fBottom == fTail->fLastEdge->fBottom) {
434 }
else if (
side == fTail->fSide) {
438 e = tri->
allocateEdge(fTail->fLastEdge->fBottom, e->fBottom, 1, EdgeType::kInner);
442 partner->addEdge(e,
side, tri);
477#if TRIANGULATOR_LOGGING
478 static float gID = 0.0f;
485 SkQuadCoeff quad(pts);
497 SkQuadCoeff quad(pts);
499 SkScalar denom = 2.0f * (aa[0] + aa[1]);
513 for (
int j = 1; j <= nPoints; j++) {
520 int pointsLeft)
const {
523 if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) || !
SkIsFinite(d1, d2)) {
546 SkScalar toleranceSqd = tolerance * tolerance;
554 for (
int i = 3; i >= 0; i--) {
565 if (toleranceSqd == 0) {
570 const SkPoint* quadPts = converter.computeQuads(pts, weight, toleranceSqd);
571 for (
int i = 0; i < converter.countQuads(); ++i) {
589 if (toleranceSqd == 0) {
598 if (toleranceSqd == 0) {
619 return (winding & 1) != 0;
623 return (winding & 1) == 1;
679 if (
prev->isLeftOf(v)) {
689 if (fTop->fPoint == fBottom->fPoint ||
690 c.
sweep_lt(fBottom->fPoint, fTop->fPoint)) {
693 TESS_LOG(
"insert edge (%g -> %g) above vertex %g\n", fTop->fID, fBottom->fID, v->fID);
697 if (
next->isRightOf(*fTop)) {
702 list_insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
707 if (fTop->fPoint == fBottom->fPoint ||
708 c.
sweep_lt(fBottom->fPoint, fTop->fPoint)) {
711 TESS_LOG(
"insert edge (%g -> %g) below vertex %g\n", fTop->fID, fBottom->fID, v->fID);
715 if (
next->isRightOf(*fBottom)) {
720 list_insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
725 SkASSERT(edge->fTop && edge->fBottom);
726 TESS_LOG(
"removing edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
728 list_remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
729 edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove);
733 SkASSERT(edge->fTop && edge->fBottom);
734 TESS_LOG(
"removing edge (%g -> %g) below vertex %g\n",
735 edge->fTop->fID, edge->fBottom->fID, edge->fTop->fID);
736 list_remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
737 edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);
746 if (!current || *current == dst || c.
sweep_lt((*current)->fPoint, dst->fPoint)) {
750 TESS_LOG(
"rewinding active edges from vertex %g to vertex %g\n", v->fID, dst->fID);
753 for (
Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
754 if (!activeEdges->
remove(e)) {
758 Edge* leftEdge = v->fLeftEnclosingEdge;
759 for (
Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
760 if (!activeEdges->
insert(e, leftEdge)) {
765 if (c.
sweep_lt(top->fPoint, dst->fPoint) &&
766 ((top->fLeftEnclosingEdge && !top->fLeftEnclosingEdge->isLeftOf(*e->fTop)) ||
767 (top->fRightEnclosingEdge && !top->fRightEnclosingEdge->isRightOf(*e->fTop)))) {
778 if (!activeEdges || !current) {
785 Vertex* bottom = edge->fBottom;
787 Vertex* leftTop = edge->fLeft->fTop;
788 Vertex* leftBottom = edge->fLeft->fBottom;
789 if (leftTop && leftBottom) {
790 if (c.
sweep_lt(leftTop->fPoint, top->fPoint) && !edge->fLeft->isLeftOf(*top)) {
791 if (!
rewind(activeEdges, current, leftTop, c)) {
794 }
else if (c.
sweep_lt(top->fPoint, leftTop->fPoint) && !edge->isRightOf(*leftTop)) {
795 if (!
rewind(activeEdges, current, top, c)) {
798 }
else if (c.
sweep_lt(bottom->fPoint, leftBottom->fPoint) &&
799 !edge->fLeft->isLeftOf(*bottom)) {
800 if (!
rewind(activeEdges, current, leftTop, c)) {
803 }
else if (c.
sweep_lt(leftBottom->fPoint, bottom->fPoint) &&
804 !edge->isRightOf(*leftBottom)) {
805 if (!
rewind(activeEdges, current, top, c)) {
812 Vertex* rightTop = edge->fRight->fTop;
813 Vertex* rightBottom = edge->fRight->fBottom;
814 if (rightTop && rightBottom) {
815 if (c.
sweep_lt(rightTop->fPoint, top->fPoint) && !edge->fRight->isRightOf(*top)) {
816 if (!
rewind(activeEdges, current, rightTop, c)) {
819 }
else if (c.
sweep_lt(top->fPoint, rightTop->fPoint) && !edge->isLeftOf(*rightTop)) {
820 if (!
rewind(activeEdges, current, top, c)) {
823 }
else if (c.
sweep_lt(bottom->fPoint, rightBottom->fPoint) &&
824 !edge->fRight->isRightOf(*bottom)) {
825 if (!
rewind(activeEdges, current, rightTop, c)) {
828 }
else if (c.
sweep_lt(rightBottom->fPoint, bottom->fPoint) &&
829 !edge->isLeftOf(*rightBottom)) {
830 if (!
rewind(activeEdges, current, top, c)) {
873 if (!edge || !other) {
877 TESS_LOG(
"merging coincident above edges (%g, %g) -> (%g, %g)\n",
880 if (!
rewind(activeEdges, current, edge->
fTop, c)) {
887 if (!
rewind(activeEdges, current, edge->
fTop, c)) {
891 if (!this->
setBottom(edge, other->
fTop, activeEdges, current, c)) {
895 if (!
rewind(activeEdges, current, other->
fTop, c)) {
899 if (!this->
setBottom(other, edge->
fTop, activeEdges, current, c)) {
908 if (!edge || !other) {
912 TESS_LOG(
"merging coincident below edges (%g, %g) -> (%g, %g)\n",
915 if (!
rewind(activeEdges, current, edge->
fTop, c)) {
922 if (!
rewind(activeEdges, current, other->
fTop, c)) {
926 if (!this->
setTop(other, edge->
fBottom, activeEdges, current, c)) {
930 if (!
rewind(activeEdges, current, edge->
fTop, c)) {
934 if (!this->
setTop(edge, other->
fBottom, activeEdges, current, c)) {
945 return left->fTop->fPoint ==
right->fTop->fPoint ||
953 return left->fBottom->fPoint ==
right->fBottom->fPoint ||
992 TESS_LOG(
"splitting edge (%g -> %g) at vertex %g (%g, %g)\n",
1004 bottom = edge->
fTop;
1006 if (!this->
setTop(edge, v, activeEdges, current, c)) {
1015 if (!this->
setBottom(edge, v, activeEdges, current, c)) {
1023 if (!this->
setBottom(edge, v, activeEdges, current, c)) {
1049 Edge* split =
nullptr;
1050 Vertex* splitAt =
nullptr;
1054 splitAt =
right->fTop;
1059 splitAt =
left->fTop;
1065 splitAt =
right->fBottom;
1068 if (!
right->isRightOf(*
left->fBottom)) {
1070 splitAt =
left->fBottom;
1080 if (!
rewind(activeEdges, current, split->
fTop, c)) {
1083 return this->
splitEdge(split, splitAt, activeEdges, current, c);
1101 TESS_LOG(
"found coincident verts at %g, %g; merging %g into %g\n",
1102 src->fPoint.fX, src->fPoint.fY, src->fID, dst->fID);
1103 dst->fAlpha = std::max(src->fAlpha, dst->fAlpha);
1104 if (src->fPartner) {
1105 src->fPartner->fPartner = dst;
1107 while (
Edge* edge = src->fFirstEdgeAbove) {
1108 std::ignore = this->
setBottom(edge, dst,
nullptr,
nullptr, c);
1110 while (
Edge* edge = src->fFirstEdgeBelow) {
1111 std::ignore = this->
setTop(edge, dst,
nullptr,
nullptr, c);
1114 dst->fSynthetic =
true;
1119 Vertex* prevV = reference;
1121 prevV = prevV->
fPrev;
1123 Vertex* nextV = prevV ? prevV->
fNext : mesh->fHead;
1126 nextV = nextV->
fNext;
1135#if TRIANGULATOR_LOGGING
1137 v->fID = mesh->fHead->fID - 1.0f;
1138 }
else if (!nextV) {
1139 v->fID = mesh->fTail->fID + 1.0f;
1141 v->fID = (prevV->fID + nextV->fID) * 0.5f;
1144 mesh->insert(v, prevV, nextV);
1173 double cosAngle = line1.
fA * line2.
fA + line1.
fB * line2.
fB;
1174 if (cosAngle > 0.999) {
1181 uint8_t alpha = edge1->
fType == EdgeType::kOuter ? 255 : 0;
1183 TESS_LOG(
"computed bisector (%g,%g) alpha %d for vertex %g\n", p.fX, p.fY, alpha, v->fID);
1200 if (
left->intersect(*
right, &p, &alpha) && p.isFinite()) {
1202 TESS_LOG(
"found intersection, pt is %g, %g\n", p.fX, p.fY);
1226 if (
left->fTop->fPartner) {
1232 if (!
rewind(activeEdges, current, top ? top : v, c)) {
1265 TESS_LOG(
"vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoint.fY);
1267 }
else if (!v->fPoint.isFinite()) {
1268 TESS_LOG(
"vertex %g,%g non-finite; removing\n", v->fPoint.fX, v->fPoint.fY);
1272 TESS_LOG(
"vertex %g,%g collinear; removing\n", v->fPoint.fX, v->fPoint.fY);
1286 bool merged =
false;
1287 for (
Vertex* v = mesh->fHead->fNext; v;) {
1289 if (c.
sweep_lt(v->fPoint, v->fPrev->fPoint)) {
1290 v->
fPoint = v->fPrev->fPoint;
1292 if (
coincident(v->fPrev->fPoint, v->fPoint)) {
1317template <CompareFunc sweep_lt>
1322 if (sweep_lt(
a->fPoint,
b->fPoint)) {
1339 sorted_merge<sweep_lt_horiz>(front, back,
result);
1341 sorted_merge<sweep_lt_vert>(front, back,
result);
1343#if TRIANGULATOR_LOGGING
1353template <CompareFunc sweep_lt>
1359 Vertex* fast = slow->fNext;
1374 merge_sort<sweep_lt>(&front);
1375 merge_sort<sweep_lt>(&back);
1378 sorted_merge<sweep_lt>(&front, &back, vertices);
1381#if TRIANGULATOR_LOGGING
1382void VertexList::dump()
const {
1384 TESS_LOG(
"vertex %g (%g, %g) alpha %d", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
1385 if (
Vertex* p = v->fPartner) {
1386 TESS_LOG(
", partner %g (%g, %g) alpha %d\n",
1387 p->fID,
p->fPoint.fX,
p->fPoint.fY,
p->fAlpha);
1391 for (
Edge* e = v->fFirstEdgeAbove;
e;
e =
e->fNextEdgeAbove) {
1392 TESS_LOG(
" edge %g -> %g, winding %d\n",
e->fTop->fID,
e->fBottom->fID,
e->fWinding);
1394 for (
Edge* e = v->fFirstEdgeBelow;
e;
e =
e->fNextEdgeBelow) {
1395 TESS_LOG(
" edge %g -> %g, winding %d\n",
e->fTop->fID,
e->fBottom->fID,
e->fWinding);
1440 TESS_LOG(
"simplifying complex polygons\n");
1446 for (
Vertex* v = mesh->fHead; v !=
nullptr; v = v->fNext) {
1447 if (!v->isConnected()) {
1458 Edge* leftEnclosingEdge;
1459 Edge* rightEnclosingEdge;
1462 TESS_LOG(
"\nvertex %g: (%g,%g), alpha %d\n",
1463 v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
1464 restartChecks =
false;
1466 v->fLeftEnclosingEdge = leftEnclosingEdge;
1467 v->fRightEnclosingEdge = rightEnclosingEdge;
1468 if (v->fFirstEdgeBelow) {
1469 for (
Edge* edge = v->fFirstEdgeBelow; edge; edge = edge->fNextEdgeBelow) {
1471 leftEnclosingEdge, edge, &activeEdges, &v, mesh, c);
1476 edge, rightEnclosingEdge, &activeEdges, &v, mesh, c);
1487 restartChecks =
true;
1492 leftEnclosingEdge, rightEnclosingEdge, &activeEdges, &v, mesh, c);
1498 restartChecks =
true;
1502 }
while (restartChecks);
1504 validate_edge_list(&activeEdges, c);
1506 for (
Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1507 if (!activeEdges.
remove(e)) {
1511 Edge* leftEdge = leftEnclosingEdge;
1512 for (
Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1513 activeEdges.
insert(e, leftEdge);
1524 TESS_LOG(
"\ntessellating simple polygons\n");
1526 Poly* polys =
nullptr;
1527 for (
Vertex* v = vertices.
fHead; v !=
nullptr; v = v->fNext) {
1528 if (!v->isConnected()) {
1531#if TRIANGULATOR_LOGGING
1532 TESS_LOG(
"\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
1534 Edge* leftEnclosingEdge;
1535 Edge* rightEnclosingEdge;
1539 if (v->fFirstEdgeAbove) {
1540 leftPoly = v->fFirstEdgeAbove->fLeftPoly;
1541 rightPoly = v->fLastEdgeAbove->fRightPoly;
1543 leftPoly = leftEnclosingEdge ? leftEnclosingEdge->
fRightPoly :
nullptr;
1544 rightPoly = rightEnclosingEdge ? rightEnclosingEdge->
fLeftPoly :
nullptr;
1546#if TRIANGULATOR_LOGGING
1548 for (
Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1549 TESS_LOG(
"%g -> %g, lpoly %d, rpoly %d\n",
1550 e->fTop->fID, e->fBottom->fID,
1551 e->fLeftPoly ? e->fLeftPoly->fID : -1,
1552 e->fRightPoly ? e->fRightPoly->fID : -1);
1555 for (
Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1556 TESS_LOG(
"%g -> %g, lpoly %d, rpoly %d\n",
1557 e->fTop->fID, e->fBottom->fID,
1558 e->fLeftPoly ? e->fLeftPoly->fID : -1,
1559 e->fRightPoly ? e->fRightPoly->fID : -1);
1562 if (v->fFirstEdgeAbove) {
1569 for (
Edge* e = v->fFirstEdgeAbove; e != v->fLastEdgeAbove; e = e->fNextEdgeAbove) {
1570 Edge* rightEdge = e->fNextEdgeAbove;
1572 if (e->fRightPoly) {
1579 activeEdges.
remove(v->fLastEdgeAbove);
1580 if (!v->fFirstEdgeBelow) {
1581 if (leftPoly && rightPoly && leftPoly != rightPoly) {
1588 if (v->fFirstEdgeBelow) {
1589 if (!v->fFirstEdgeAbove) {
1590 if (leftPoly && rightPoly) {
1591 if (leftPoly == rightPoly) {
1599 rightEnclosingEdge->
fLeftPoly = rightPoly;
1607 Edge* leftEdge = v->fFirstEdgeBelow;
1609 activeEdges.
insert(leftEdge, leftEnclosingEdge);
1611 rightEdge = rightEdge->fNextEdgeBelow) {
1612 activeEdges.
insert(rightEdge, leftEdge);
1617 leftEdge->
fRightPoly = rightEdge->fLeftPoly = poly;
1619 leftEdge = rightEdge;
1623#if TRIANGULATOR_LOGGING
1625 for (
Edge* e = activeEdges.
fHead; e !=
nullptr; e = e->fRight) {
1626 TESS_LOG(
"%g -> %g, lpoly %d, rpoly %d\n",
1627 e->fTop->fID, e->fBottom->fID,
1628 e->fLeftPoly ? e->fLeftPoly->fID : -1,
1629 e->fRightPoly ? e->fRightPoly->fID : -1);
1633 return { polys,
true };
1640#if TRIANGULATOR_LOGGING
1641 for (
int i = 0; i < contourCnt; ++i) {
1651 this->
buildEdges(contours, contourCnt, mesh, c);
1655 if (!vertices || !vertices->
fHead) {
1661 merge_sort<sweep_lt_horiz>(vertices);
1663 merge_sort<sweep_lt_vert>(vertices);
1665#if TRIANGULATOR_LOGGING
1666 for (
Vertex* v = vertices->
fHead; v !=
nullptr; v = v->fNext) {
1667 static float gID = 0.0f;
1685 TESS_LOG(
"\nsorted+merged mesh:\n");
1689 return {
nullptr,
false };
1700 for (
Poly* poly = polys; poly; poly = poly->
fNext) {
1702 data = this->
emitPoly(poly, std::move(data));
1712 bool hasPoints =
false;
1744 if (contourCnt <= 0) {
1746 return {
nullptr,
true };
1752 std::unique_ptr<VertexList[]> contours(
new VertexList[contourCnt]);
1754 this->
pathToContours(tolerance, clipBounds, contours.get(), isLinear);
1760 for (
Poly* poly = polys; poly; poly = poly->
fNext) {
1772 if (0 == count64 || count64 >
SK_MaxS32) {
1775 int count = count64;
1777 size_t vertexStride =
sizeof(
SkPoint);
1779 vertexStride +=
sizeof(float);
1783 SkDebugf(
"Could not allocate vertices\n");
1792 int actualCount =
static_cast<int>((verts.
mark() -
start) / vertexStride);
1794 vertexAllocator->
unlock(actualCount);
static float GrNormalizeByteToFloat(uint8_t value)
static bool rewind_if_necessary(Edge *edge, EdgeList *activeEdges, Vertex **current, const Comparator &c)
static void list_insert(T *t, T *prev, T *next, T **head, T **tail)
static int get_contour_count(const SkPath &path, SkScalar tolerance)
static bool rewind(EdgeList *activeEdges, Vertex **current, Vertex *dst, const Comparator &c)
static bool bottom_collinear(Edge *left, Edge *right)
static SkScalar quad_error_at(const SkPoint pts[3], SkScalar t, SkScalar u)
bool(* CompareFunc)(const SkPoint &a, const SkPoint &b)
static bool recursive_edge_intersect(const Line &u, SkPoint u0, SkPoint u1, const Line &v, SkPoint v0, SkPoint v1, SkPoint *p, double *s, double *t)
static void remove_edge_above(Edge *edge)
static bool coincident(const SkPoint &a, const SkPoint &b)
static void list_remove(T *t, T **head, T **tail)
static bool edge_line_needs_recursion(const SkPoint &p0, const SkPoint &p1)
static bool top_collinear(Edge *left, Edge *right)
static void merge_sort(VertexList *vertices)
static void round(SkPoint *p)
static skgpu::VertexWriter emit_vertex(Vertex *v, bool emitCoverage, skgpu::VertexWriter data)
static skgpu::VertexWriter emit_triangle(Vertex *v0, Vertex *v1, Vertex *v2, bool emitCoverage, skgpu::VertexWriter data)
static void sorted_merge(VertexList *front, VertexList *back, VertexList *result)
static SkScalar double_to_clamped_scalar(double d)
static void remove_edge_below(Edge *edge)
static bool sweep_lt_horiz(const SkPoint &a, const SkPoint &b)
static bool apply_fill_type(SkPathFillType fillType, int winding)
static bool sweep_lt_vert(const SkPoint &a, const SkPoint &b)
#define TRIANGULATOR_WIREFRAME
static float next(float f)
static float prev(float f)
static unsigned clamp(SkFixed fx, int max)
void SK_SPI SkDebugf(const char format[],...) SK_PRINTF_LIKE(1
static bool SkIsFinite(T x, Pack... values)
static constexpr int32_t SK_MaxS32
static int side(double x)
static bool contains(const SkRect &r, SkPoint p)
static bool SkPathFillType_IsInverse(SkPathFillType ft)
static bool left(const SkPoint &p0, const SkPoint &p1)
static bool right(const SkPoint &p0, const SkPoint &p1)
#define SkScalarAve(a, b)
#define SkDoubleToScalar(x)
#define SkScalarRoundToScalar(x)
static constexpr const T & SkTPin(const T &x, const T &lo, const T &hi)
skgpu::VertexWriter lockWriter(size_t stride, int eagerCount)
virtual void unlock(int actualCount)=0
void append(SkArenaAlloc *alloc, SkPoint a, SkPoint b, SkPoint c, int winding)
void contoursToMesh(VertexList *contours, int contourCnt, VertexList *mesh, const Comparator &)
std::tuple< Poly *, bool > pathToPolys(float tolerance, const SkRect &clipBounds, bool *isLinear)
skgpu::VertexWriter emitMonotonePoly(const MonotonePoly *, skgpu::VertexWriter data) const
static int64_t CountPoints(Poly *polys, SkPathFillType overrideFillType)
static void SortMesh(VertexList *vertices, const Comparator &)
bool mergeCollinearEdges(Edge *edge, EdgeList *activeEdges, Vertex **current, const Comparator &) const
Edge * allocateEdge(Vertex *top, Vertex *bottom, int winding, EdgeType type)
bool setTop(Edge *edge, Vertex *v, EdgeList *activeEdges, Vertex **current, const Comparator &) const
bool fPreserveCollinearVertices
Edge * makeEdge(Vertex *prev, Vertex *next, EdgeType type, const Comparator &)
SkArenaAlloc *const fAlloc
void buildEdges(VertexList *contours, int contourCnt, VertexList *mesh, const Comparator &)
bool fCollectBreadcrumbTriangles
BreadcrumbTriangleList fBreadcrumbList
bool applyFillType(int winding) const
MonotonePoly * allocateMonotonePoly(Edge *edge, Side side, int winding)
SimplifyResult simplify(VertexList *mesh, const Comparator &)
virtual std::tuple< Poly *, bool > tessellate(const VertexList &vertices, const Comparator &)
Poly * makePoly(Poly **head, Vertex *v, int winding) const
skgpu::VertexWriter polysToTriangles(Poly *polys, SkPathFillType overrideFillType, skgpu::VertexWriter data) const
static void SortedMerge(VertexList *front, VertexList *back, VertexList *result, const Comparator &)
bool setBottom(Edge *edge, Vertex *v, EdgeList *activeEdges, Vertex **current, const Comparator &) const
bool fRoundVerticesToQuarterPixel
void pathToContours(float tolerance, const SkRect &clipBounds, VertexList *contours, bool *isLinear) const
Edge * makeConnectingEdge(Vertex *prev, Vertex *next, EdgeType, const Comparator &, int windingScale=1)
void mergeVertices(Vertex *src, Vertex *dst, VertexList *mesh, const Comparator &) const
Vertex * makeSortedVertex(const SkPoint &, uint8_t alpha, VertexList *mesh, Vertex *reference, const Comparator &) const
skgpu::VertexWriter emitPoly(const Poly *, skgpu::VertexWriter data) const
bool mergeEdgesAbove(Edge *edge, Edge *other, EdgeList *activeEdges, Vertex **current, const Comparator &) const
void generateCubicPoints(const SkPoint &, const SkPoint &, const SkPoint &, const SkPoint &, SkScalar tolSqd, VertexList *contour, int pointsLeft) const
static void FindEnclosingEdges(const Vertex &v, const EdgeList &edges, Edge **left, Edge **right)
std::tuple< Poly *, bool > contoursToPolys(VertexList *contours, int contourCnt)
skgpu::VertexWriter emitTriangle(Vertex *prev, Vertex *curr, Vertex *next, int winding, skgpu::VertexWriter data) const
bool mergeCoincidentVertices(VertexList *mesh, const Comparator &) const
bool mergeEdgesBelow(Edge *edge, Edge *other, EdgeList *activeEdges, Vertex **current, const Comparator &) const
void sanitizeContours(VertexList *contours, int contourCnt) const
void appendQuadraticToContour(const SkPoint[3], SkScalar toleranceSqd, VertexList *contour) const
BoolFail intersectEdgePair(Edge *left, Edge *right, EdgeList *activeEdges, Vertex **current, const Comparator &)
BoolFail checkForIntersection(Edge *left, Edge *right, EdgeList *activeEdges, Vertex **current, VertexList *mesh, const Comparator &)
void appendPointToContour(const SkPoint &p, VertexList *contour) const
BoolFail splitEdge(Edge *edge, Vertex *v, EdgeList *activeEdges, Vertex **current, const Comparator &)
void computeBisector(Edge *edge1, Edge *edge2, Vertex *) const
auto make(Ctor &&ctor) -> decltype(ctor(nullptr))
Verb next(SkPoint pts[4])
SkScalar conicWeight() const
bool isInverseFillType() const
SkPathFillType getFillType() const
const SkRect & getBounds() const
static SkScalar DistanceToLineSegmentBetweenSqd(const SkPoint &pt, const SkPoint &a, const SkPoint &b)
static SkPoint to_point(SkIPoint p)
VULKAN_HPP_DEFAULT_DISPATCH_LOADER_DYNAMIC_STORAGE auto & d
static float max(float r, float g, float b)
static float min(float r, float g, float b)
uint32_t cubicPointCount(const SkPoint points[], SkScalar tol)
static const int kMaxPointsPerCurve
bool sweep_lt(const SkPoint &a, const SkPoint &b) const
void insert(Edge *edge, Edge *prev, Edge *next)
bool contains(Edge *edge) const
void insertBelow(Vertex *, const Comparator &)
void insertAbove(Vertex *, const Comparator &)
bool intersect(const Edge &other, SkPoint *p, uint8_t *alpha=nullptr) const
double dist(const SkPoint &p) const
bool intersect(const Line &other, SkPoint *point) const
Poly(Vertex *v, int winding)
Vertex * lastVertex() const
Poly * addEdge(Edge *e, Side side, GrTriangulator *)
void insert(Vertex *v, Vertex *prev, Vertex *next)
void toQuad(SkPoint quad[4]) const
constexpr float height() const
constexpr float width() const
Mark mark(size_t offset=0) const