6#include <QtGui/private/qtriangulator_p.h>
7#include <QtCore/qloggingcategory.h>
8#include <QtCore/qhash.h>
34 return uvForPoint(
v1,
v2,
p - p0);
41 return { uv.x(), uv.y(), 0.0f };
43 return { uv.x(), uv.y(), e.
isConvex() ? -1.0f : 1.0f };
49 return {
v.
y(), -
v.x()};
61 return p1.x() * (
p2.y() - p3.y())
62 +
p2.x() * (p3.y() -
p1.y())
63 + p3.x() * (
p1.y() -
p2.y());
75using TrianglePoints = std::array<QVector2D, 3>;
76using LinePoints = std::array<QVector2D, 2>;
80static inline double determinant(
const TrianglePoints &
p)
82 return determinant(
p[0],
p[1],
p[2]);
86static void fixWinding(TrianglePoints &
p)
88 double det = determinant(
p);
104bool lineIntersection(
const LinePoints &l1,
const LinePoints &l2,
QList<QPair<float, float>> *solution =
nullptr)
106 constexpr double eps2 = 1e-5;
109 const float A = l1[0].x();
110 const float B = l1[1].x() - l1[0].x();
111 const float C = l2[0].x();
112 const float D = l2[1].x() - l2[0].x();
113 const float E = l1[0].y();
114 const float F = l1[1].y() - l1[0].y();
115 const float G = l2[0].y();
116 const float H = l2[1].y() - l2[0].y();
118 float det = D *
F -
B *
H;
123 float s = (
F * (
A - C) -
B * (
E -
G)) / det;
124 float t = (
H * (
A - C) - D * (
E -
G)) / det;
127 bool intersecting = (
s >= 0 &&
s <= 1. - eps2 &&
t >= 0 &&
t <= 1. - eps2);
129 if (solution && intersecting)
130 solution->append(QPair<float, float>(
t,
s));
136bool checkTriangleOverlap(TrianglePoints &triangle1, TrianglePoints &triangle2,
float epsilon = 1.0/32)
139 fixWinding(triangle1);
140 for (
int i = 0;
i < 3;
i++) {
141 int ni = (
i + 1) % 3;
142 if (checkEdge(triangle1[
i], triangle1[ni], triangle2[0],
epsilon) &&
143 checkEdge(triangle1[
i], triangle1[ni], triangle2[1],
epsilon) &&
144 checkEdge(triangle1[
i], triangle1[ni], triangle2[2],
epsilon))
149 fixWinding(triangle2);
150 for (
int i = 0;
i < 3;
i++) {
151 int ni = (
i + 1) % 3;
153 if (checkEdge(triangle2[
i], triangle2[ni], triangle1[0],
epsilon) &&
154 checkEdge(triangle2[
i], triangle2[ni], triangle1[1],
epsilon) &&
155 checkEdge(triangle2[
i], triangle2[ni], triangle1[2],
epsilon))
162bool checkLineTriangleOverlap(TrianglePoints &triangle, LinePoints &
line,
float epsilon = 1.0/32)
165 bool s1 = determinant(
line[0],
line[1], triangle[0]) < 0;
166 auto s2 = determinant(
line[0],
line[1], triangle[1]) < 0;
167 auto s3 = determinant(
line[0],
line[1], triangle[2]) < 0;
173 fixWinding(triangle);
174 for (
int i = 0;
i < 3;
i++) {
175 int ni = (
i + 1) % 3;
176 if (checkEdge(triangle[
i], triangle[ni],
line[0],
epsilon) &&
189 if (element1.isLine()) {
190 LinePoints line1{ element1.
startPoint(), element1.endPoint() };
191 if (element2.isLine()) {
192 LinePoints line2{ element2.startPoint(), element2.endPoint() };
193 return lineIntersection(line1, line2);
195 TrianglePoints
t2{ element2.startPoint(), element2.controlPoint(), element2.endPoint() };
196 return checkLineTriangleOverlap(
t2, line1);
199 TrianglePoints
t1{ element1.startPoint(), element1.controlPoint(), element1.endPoint() };
200 if (element2.isLine()) {
201 LinePoints
line{ element2.startPoint(), element2.endPoint() };
202 return checkLineTriangleOverlap(
t1,
line);
204 TrianglePoints
t2{ element2.startPoint(), element2.controlPoint(), element2.endPoint() };
205 return checkTriangleOverlap(
t1,
t2);
215 float cross =
v1.x() *
v2.y() -
v1.y() *
v2.x();
217 return atan2(cross,
dot);
220static bool isIntersecting(
const TrianglePoints &
t1,
const TrianglePoints &
t2,
QList<QPair<float, float>> *solutions =
nullptr)
222 constexpr double eps = 1e-5;
223 constexpr double eps2 = 1e-5;
224 constexpr int maxIterations = 7;
227 QPointF td1[3] = {
t1[0].toPointF(),
t1[1].toPointF(),
t1[2].toPointF() };
228 QPointF td2[3] = {
t2[0].toPointF(),
t2[1].toPointF(),
t2[2].toPointF() };
234 td1[0] * (1 -
t.x()) * (1. -
t.x()) + 2 * td1[1] * (1. -
t.x()) *
t.x() + td1[2] *
t.x() *
t.x() -
235 td2[0] * (1 -
t.y()) * (1. -
t.y()) - 2 * td2[1] * (1. -
t.y()) *
t.y() - td2[2] *
t.y() *
t.y();};
240 td1[0].
x() * (-2 * (1-
t.x())) + 2 * td1[1].x() * (1 - 2 *
t.x()) + td1[2].x() * 2 *
t.x(),
241 -td2[0].x() * (-2 * (1-
t.y())) - 2 * td2[1].x() * (1 - 2 *
t.y()) - td2[2].x() * 2 *
t.y(),
242 td1[0].y() * (-2 * (1-
t.x())) + 2 * td1[1].y() * (1 - 2 *
t.x()) + td1[2].y() * 2 *
t.x(),
243 -td2[0].y() * (-2 * (1-
t.y())) - 2 * td2[1].y() * (1 - 2 *
t.y()) - td2[2].y() * 2 *
t.y());};
248 const double det =
A.x1() *
A.y2() -
A.y1() *
A.x2();
249 QLineF Ainv(
A.y2() / det, -
A.y1() / det, -
A.x2() / det,
A.x1() / det);
251 return QPointF(Ainv.x1() *
b.x() + Ainv.y1() *
b.y(),
252 Ainv.x2() *
b.x() + Ainv.y2() *
b.y());
255#ifdef INTERSECTION_EXTRA_DEBUG
256 qCDebug(lcSGCurveIntersectionSolver) <<
"Checking" <<
t1[0] <<
t1[1] <<
t1[2];
257 qCDebug(lcSGCurveIntersectionSolver) <<
" vs" <<
t2[0] <<
t2[1] <<
t2[2];
266 for (
auto t : tref) {
272 while (err > eps &&
i < maxIterations) {
273 t =
t - solve(J(
t), fval);
275 err =
qAbs(fval.x()) +
qAbs(fval.y());
277#ifdef INTERSECTION_EXTRA_DEBUG
278 qCDebug(lcSGCurveIntersectionSolver) <<
" Newton iteration" <<
i <<
"t =" <<
t <<
"F =" << fval <<
"Error =" << err;
282 if (err < eps &&
t.x() >=0 &&
t.x() <= 1. - 10 * eps2 &&
t.y() >= 0 &&
t.y() <= 1. - 10 * eps2) {
283#ifdef INTERSECTION_EXTRA_DEBUG
284 qCDebug(lcSGCurveIntersectionSolver) <<
" Newton solution (after" <<
i <<
")=" <<
t <<
"(" <<
F(
t) <<
")";
288 for (
auto solution : *solutions) {
289 if (
qAbs(solution.first -
t.x()) < 10 * eps2 &&
qAbs(solution.second -
t.y()) < 10 * eps2) {
295 solutions->append({
t.x(),
t.y()});
302 return solutions->size() > 0;
307static bool isIntersecting(
const QQuadPath &
path,
int e1,
int e2,
QList<QPair<float, float>> *solutions =
nullptr)
313 if (elem1.isLine() && elem2.isLine()) {
314 return lineIntersection(LinePoints {elem1.startPoint(), elem1.endPoint() },
315 LinePoints {elem2.startPoint(), elem2.endPoint() },
318 return isIntersecting(TrianglePoints { elem1.startPoint(), elem1.controlPoint(), elem1.endPoint() },
319 TrianglePoints { elem2.startPoint(), elem2.controlPoint(), elem2.endPoint() },
327 int pathElementIndex;
328 TrianglePoints normals;
369QList<TriangleData> simplePointTriangulator(
const QList<QVector2D> &pts,
const QList<QVector2D> &normals,
int elementIndex)
371 int count = pts.size();
377 float det1 = determinant(pts[0], pts[1], pts[2]);
382 auto connectableInHull = [&](
int idx) -> QList<int> {
384 const int n = hull.size();
385 const auto &pt = pts[idx];
386 for (
int i = 0;
i <
n; ++
i) {
387 const auto &i1 = hull.at(
i);
388 const auto &i2 = hull.at((
i+1) %
n);
389 if (determinant(pts[i1], pts[i2], pt) < 0.0f)
395 auto visible = connectableInHull(
i);
396 if (visible.isEmpty())
398 int visCount = visible.count();
399 int hullCount = hull.count();
402 int boundaryStart = visible[0];
403 for (
int j = 0;
j < visCount - 1; ++
j) {
404 if ((visible[
j] + 1) % hullCount != visible[
j+1]) {
405 boundaryStart = visible[
j + 1];
412 int pointsToKeep = hullCount - visCount + 1;
415 for (
int j = 0;
j < pointsToKeep; ++
j) {
416 newHull << hull.at((
j + boundaryStart + visCount) % hullCount);
422 QList<TriangleData>
ret;
423 for (
int i = 1;
i < hull.size() - 1; ++
i) {
427 ret.append({{pts[i0], pts[i1], pts[i2]}, elementIndex, {normals[i0], normals[i1], normals[i2]}});
436 const auto v1 =
el.controlPoint() -
el.startPoint();
437 const auto v2 =
el.endPoint() -
el.controlPoint();
456 splitElementIfNecessary(&newPath,
index, subdivisions);
466 const bool miterJoin = !bevelJoin && !roundJoin;
473 Q_ASSERT(miterLimit > 0 || !miterJoin);
474 float inverseMiterLimit = miterJoin ? 1.0f / miterLimit : 1.0;
476 const float penFactor = penWidth / 2;
482 bool &outerBisectorWithinMiterLimit,
bool &innerIsRight,
bool &giveUp) -> std::array<QVector2D, 5>
484 outerBisectorWithinMiterLimit =
true;
490 return {
n,
n, -
n, -
n, -
n};
495 return {
n,
n, -
n, -
n, -
n};
498 Q_ASSERT(element1->endPoint() == element2->startPoint());
500 const auto p1 = element1->isLine() ? element1->startPoint() : element1->controlPoint();
501 const auto p2 = element1->endPoint();
502 const auto p3 = element2->isLine() ? element2->endPoint() : element2->controlPoint();
506 const auto b = (
v1 +
v2);
508 constexpr float epsilon = 1.0f / 32.0f;
517 return {
n,
n, -
n, -
n, -
n};
526 cos2x =
qMin(1.0f, cos2x);
527 float sine = sqrt((1.0f - cos2x) / 2);
528 innerIsRight = determinant(
p1,
p2, p3) > 0;
529 sine =
qMax(sine, 0.01f);
530 float length = penFactor / sine;
541 return projLen * 0.9f <
length && (
v -
n * projLen).
length() * 0.9 < margin;
548 giveUp = !element1->isLine() || !element2->isLine()
549 || tooLong(
p1,
p2, bisector,
length, penFactor)
550 || tooLong(p3,
p2, bisector,
length, penFactor);
551 outerBisectorWithinMiterLimit = sine >= inverseMiterLimit / 2.0f;
552 bool simpleJoin = simpleMiter && outerBisectorWithinMiterLimit && !giveUp;
556 return {bn, bn, -bn, -bn, -bn};
557 const QVector2D n1 = normalVector(*element1,
true);
558 const QVector2D n2 = normalVector(*element2);
561 return {n1, n2, -n1, -n2, -bn};
563 return {-n1, -n2, n1, n2, -bn};
567 return {bn, bn, -n1, -n2, -bn};
569 return {bn, bn, n1, n2, -bn};
573 QList<TriangleData>
ret;
578 const auto &element =
path.elementAt(idx);
584 bool controlPointOnRight = determinant(
s,
c, e) > 0;
585 QVector2D startNormal = normalVector(element);
586 QVector2D endNormal = normalVector(element,
true);
588 if (controlPointOnRight)
589 controlPointNormal = -controlPointNormal;
590 QVector2D p5 =
c + controlPointNormal * penFactor;
591 TrianglePoints
t1{
p1,
p2, p5};
592 TrianglePoints
t2{p3, p4, p5};
593 bool simpleCase = !checkTriangleOverlap(
t1,
t2);
596 ret.append({{
p1,
p2, p5}, idx, {n1, n2, controlPointNormal}});
597 ret.append({{p3, p4, p5}, idx, {n3, n4, controlPointNormal}});
598 if (controlPointOnRight) {
599 ret.append({{
p1, p3, p5}, idx, {n1, n3, controlPointNormal}});
601 ret.append({{
p2, p4, p5}, idx, {n2, n4, controlPointNormal}});
604 ret.append(simplePointTriangulator({
p1,
p2, p5, p3, p4}, {n1, n2, controlPointNormal, n3, n4}, idx));
614 while (subStart <
count) {
615 int subEnd = subStart;
616 for (
int i = subStart + 1;
i <
count; ++
i) {
617 const auto &e =
path.elementAt(
i);
627 bool closed =
path.elementAt(subStart).
startPoint() ==
path.elementAt(subEnd).endPoint();
628 const int subCount = subEnd - subStart + 1;
630 auto addIdx = [&](
int idx,
int delta) ->
int {
631 int subIdx = idx - subStart;
633 subIdx = (subIdx + subCount + delta) % subCount;
636 return subStart + subIdx;
639 int subIdx = idx - subStart;
641 subIdx = (subIdx + subCount + delta) % subCount;
642 return &
path.elementAt(subStart + subIdx);
645 if (subIdx >= 0 && subIdx < subCount)
646 return &
path.elementAt(subStart + subIdx);
650 for (
int i = subStart;
i <= subEnd; ++
i) {
651 const auto &element =
path.elementAt(
i);
652 const auto *nextElement = elementAt(
i, +1);
653 const auto *prevElement = elementAt(
i, -1);
658 bool startInnerIsRight;
659 bool startBisectorWithinMiterLimit;
660 bool giveUpOnStartJoin;
661 auto startJoin = calculateJoin(prevElement, &element,
662 startBisectorWithinMiterLimit, startInnerIsRight,
664 const QVector2D &startInner = startJoin[1];
665 const QVector2D &startOuter = startJoin[3];
667 bool endInnerIsRight;
668 bool endBisectorWithinMiterLimit;
669 bool giveUpOnEndJoin;
670 auto endJoin = calculateJoin(&element, nextElement,
671 endBisectorWithinMiterLimit, endInnerIsRight,
681 if (startInnerIsRight) {
689 p1 =
s + n1 * penFactor;
690 p2 =
s + n2 * penFactor;
693 if (endInnerIsRight) {
701 p3 = e + n3 * penFactor;
702 p4 = e + n4 * penFactor;
711 }
else if (squareCap) {
714 ret.append({{
p1,
s, c1}, -1, {}});
715 ret.append({{c1,
s,
c2}, -1, {}});
724 }
else if (squareCap) {
727 ret.append({{p3, e, c3}, -1, {}});
728 ret.append({{c3, e, c4}, -1, {}});
729 ret.append({{p4, e, c4}, -1, {}});
734 ret.append({{
p1,
p2, p3},
i, {n1, n2, n3}});
735 ret.append({{
p2, p3, p4},
i, {n2, n3, n4}});
737 triangulateCurve(
i,
p1,
p2, p3, p4, n1, n2, n3, n4);
740 bool trivialJoin = simpleMiter && endBisectorWithinMiterLimit && !giveUpOnEndJoin;
741 if (!trivialJoin && nextElement) {
744 bool innerOnRight = endInnerIsRight;
746 const auto outer1 = e + endOuter * penFactor;
747 const auto outer2 = e + nextOuter * penFactor;
750 if (bevelJoin || (miterJoin && !endBisectorWithinMiterLimit)) {
751 ret.append({{outer1, e, outer2}, -1, {}});
752 }
else if (roundJoin) {
753 ret.append({{outer1, e, outer2},
i, {}});
757 ret.append({{outer1, outer1 + nn, outer2},
i, {}});
758 ret.append({{outer1 + nn, outer2, outer2 + nn},
i, {}});
760 }
else if (miterJoin) {
761 QVector2D outer = e + outerB * penFactor;
762 ret.append({{outer1, e, outer}, -2, {}});
763 ret.append({{outer, e, outer2}, -2, {}});
766 if (!giveUpOnEndJoin) {
767 QVector2D inner = e + endInner * penFactor;
768 ret.append({{inner, e, outer1},
i, {endInner, {}, endOuter}});
770 int nextIdx = addIdx(
i, +1);
771 ret.append({{inner, e, outer2}, nextIdx, {endInner, {}, nextOuter}});
775 subStart = subEnd + 1;
783static bool handleOverlap(
QQuadPath &
path,
int e1,
int e2,
int recursionLevel = 0)
786 if (
path.elementAt(e1).isLine() &&
path.elementAt(e1).isLine())
789 if (!isOverlap(
path, e1, e2)) {
793 if (recursionLevel > 8) {
794 qCDebug(lcSGCurveProcessor) <<
"Triangle overlap: recursion level" << recursionLevel <<
"aborting!";
798 if (
path.elementAt(e1).childCount() > 1) {
799 auto e11 =
path.indexOfChildAt(e1, 0);
800 auto e12 =
path.indexOfChildAt(e1, 1);
801 handleOverlap(
path, e11, e2, recursionLevel + 1);
802 handleOverlap(
path, e12, e2, recursionLevel + 1);
803 }
else if (
path.elementAt(e2).childCount() > 1) {
804 auto e21 =
path.indexOfChildAt(e2, 0);
805 auto e22 =
path.indexOfChildAt(e2, 1);
806 handleOverlap(
path, e1, e21, recursionLevel + 1);
807 handleOverlap(
path, e1, e22, recursionLevel + 1);
809 path.splitElementAt(e1);
810 auto e11 =
path.indexOfChildAt(e1, 0);
811 auto e12 =
path.indexOfChildAt(e1, 1);
812 bool overlap1 = isOverlap(
path, e11, e2);
813 bool overlap2 = isOverlap(
path, e12, e2);
814 if (!overlap1 && !overlap2)
818 if (
path.elementAt(e2).isLine()) {
821 handleOverlap(
path, e11, e2, recursionLevel + 1);
823 handleOverlap(
path, e12, e2, recursionLevel + 1);
826 path.splitElementAt(e2);
827 auto e21 =
path.indexOfChildAt(e2, 0);
828 auto e22 =
path.indexOfChildAt(e2, 1);
830 handleOverlap(
path, e11, e21, recursionLevel + 1);
831 handleOverlap(
path, e11, e22, recursionLevel + 1);
834 handleOverlap(
path, e12, e21, recursionLevel + 1);
835 handleOverlap(
path, e12, e22, recursionLevel + 1);
846 bool changed =
false;
851 for (
auto candidate : candidates)
852 changed = handleOverlap(
path, candidate.first, candidate.second) || changed;
864 struct BRect {
float xmin;
float xmax;
float ymin;
float ymax; };
867 QVarLengthArray<int, 64> elementStarts, elementEnds;
868 QVarLengthArray<BRect, 64> boundingRects;
869 elementStarts.reserve(
path.elementCount());
870 boundingRects.reserve(
path.elementCount());
871 for (
int i = 0;
i <
path.elementCount();
i++) {
878 boundingRects.append(bR);
879 elementStarts.append(
i);
883 auto compareXmin = [&](
int i,
int j){
return boundingRects.at(
i).xmin < boundingRects.at(
j).xmin;};
884 auto compareXmax = [&](
int i,
int j){
return boundingRects.at(
i).xmax < boundingRects.at(
j).xmax;};
885 std::sort(elementStarts.begin(), elementStarts.end(), compareXmin);
886 elementEnds = elementStarts;
887 std::sort(elementEnds.begin(), elementEnds.end(), compareXmax);
890 QList<QPair<int, int>> overlappingBB;
895 int firstElementEnd = 0;
896 for (
const int addIndex : std::as_const(elementStarts)) {
897 const BRect &newR = boundingRects.at(addIndex);
900 while (bRpool.size() && firstElementEnd < elementEnds.size()) {
901 int removeIndex = elementEnds.at(firstElementEnd);
902 if (bRpool.contains(removeIndex) && newR.xmin > boundingRects.at(removeIndex).xmax) {
903 bRpool.removeOne(removeIndex);
911 for (
int j = 0;
j < bRpool.size();
j++) {
912 int i = bRpool.at(
j);
913 const BRect &
r1 = boundingRects.at(
i);
918 bool isNeighbor =
false;
919 if (
i - addIndex == 1) {
920 if (!
path.elementAt(addIndex).isSubpathEnd())
922 }
else if (addIndex -
i == 1) {
923 if (!
path.elementAt(
i).isSubpathEnd())
927 if (isNeighbor && (
r1.ymax <= newR.ymin || newR.ymax <=
r1.ymin))
930 if (!isNeighbor && (
r1.ymax < newR.ymin || newR.ymax <
r1.ymin))
933 overlappingBB.append(QPair<int, int>(
i, addIndex));
935 bRpool.append(addIndex);
937 return overlappingBB;
953 QList<int> subPathStartPoints;
954 QList<int> subPathEndPoints;
955 for (
int i = 0;
i <
path.elementCount();
i++) {
956 if (
path.elementAt(
i).isSubpathStart())
957 subPathStartPoints.append(
i);
958 if (
path.elementAt(
i).isSubpathEnd()) {
959 subPathEndPoints.append(
i);
962 const int subPathCount = subPathStartPoints.size();
965 if (subPathStartPoints.size() < 2)
969 QList<bool> isInside;
970 bool isAnyInside =
false;
971 isInside.reserve(subPathStartPoints.size() * subPathStartPoints.size());
972 for (
int i = 0;
i < subPathCount;
i++) {
973 for (
int j = 0;
j < subPathCount;
j++) {
975 isInside.append(
false);
977 isInside.append(
path.contains(
path.elementAt(subPathStartPoints.at(
i)).startPoint(),
978 subPathStartPoints.at(
j), subPathEndPoints.at(
j)));
991 QList<bool> clockwise;
992 clockwise.reserve(subPathCount);
993 for (
int i = 0;
i < subPathCount;
i++) {
994 float sumProduct = 0;
995 for (
int j = subPathStartPoints.at(
i);
j <= subPathEndPoints.at(
i);
j++) {
998 sumProduct += (endPoint.
x() - startPoint.
x()) * (endPoint.
y() + startPoint.
y());
1000 clockwise.append(sumProduct > 0);
1005 QList<bool> isFilled;
1006 isFilled.reserve(subPathStartPoints.size() );
1007 for (
int i = 0;
i < subPathCount;
i++) {
1008 int crossings = clockwise.at(
i) ? 1 : -1;
1009 for (
int j = 0;
j < subPathStartPoints.size();
j++) {
1010 if (isInside.at(
i * subPathCount +
j))
1011 crossings += clockwise.at(
j) ? 1 : -1;
1013 isFilled.append(crossings != 0);
1018 auto findClosestOuterSubpath = [&](
int subPath) {
1020 QList<int> candidates;
1021 for (
int i = 0;
i < subPathStartPoints.size();
i++) {
1022 if (isInside.at(
subPath * subPathCount +
i))
1023 candidates.append(
i);
1025 int maxNestingLevel = -1;
1026 int maxNestingLevelIndex = -1;
1027 for (
int i = 0;
i < candidates.size();
i++) {
1028 int nestingLevel = 0;
1029 for (
int j = 0;
j < candidates.size();
j++) {
1030 if (isInside.at(candidates.at(
i) * subPathCount + candidates.at(
j))) {
1034 if (nestingLevel > maxNestingLevel) {
1035 maxNestingLevel = nestingLevel;
1036 maxNestingLevelIndex = candidates.at(
i);
1039 return maxNestingLevelIndex;
1042 bool pathChanged =
false;
1048 for (
int i = 0;
i < subPathCount;
i++) {
1049 int j = findClosestOuterSubpath(
i);
1050 if (
j >= 0 && isFilled.at(
i) == isFilled.at(
j)) {
1053 for (
int k = subPathStartPoints.at(
i); k <= subPathEndPoints.at(
i); k++)
1054 fixedPath.addElement(
path.elementAt(k));
1067 if (removeNestedPaths)
1073 if (
path.elementCount() < 2) {
1078 struct IntersectionData {
int e1;
int e2;
float t1;
float t2;
bool in1 =
false, in2 =
false, out1 =
false, out2 =
false; };
1079 QList<IntersectionData> intersections;
1083 auto markIntersectionAsHandled = [=](IntersectionData *
data,
int i,
bool forward) {
1084 if (
data->e1 ==
i) {
1089 }
else if (
data->e2 ==
i){
1102 for (
const auto &candidate : candidates) {
1103 QList<QPair<float,float>>
res;
1104 int e1 = candidate.first;
1105 int e2 = candidate.second;
1106 if (isIntersecting(
path, e1, e2, &
res)) {
1107 for (
const auto &
r :
res)
1108 intersections.append({e1, e2,
r.first,
r.second});
1112 qCDebug(lcSGCurveIntersectionSolver) <<
"----- Checking for Intersections -----";
1113 qCDebug(lcSGCurveIntersectionSolver) <<
"Found" << intersections.length() <<
"intersections";
1114 if (lcSGCurveIntersectionSolver().isDebugEnabled()) {
1115 for (
const auto &
i : intersections) {
1116 auto p1 =
path.elementAt(
i.e1).pointAtFraction(
i.t1);
1117 auto p2 =
path.elementAt(
i.e2).pointAtFraction(
i.t2);
1118 qCDebug(lcSGCurveIntersectionSolver) <<
" between" <<
i.e1 <<
"and" <<
i.e2 <<
"at" <<
i.t1 <<
"/" <<
i.t2 <<
"->" <<
p1 <<
"/" <<
p2;
1122 if (intersections.isEmpty()) {
1124 if (removeNestedPaths) {
1125 qCDebug(lcSGCurveIntersectionSolver) <<
"No Intersections found. Looking for enclosed subpaths.";
1126 return removeNestedSubpaths(
path);
1128 qCDebug(lcSGCurveIntersectionSolver) <<
"Returning the path unchanged.";
1138 QList<int> subPathStartPoints;
1139 QList<int> subPathEndPoints;
1140 QList<bool> subPathHandled;
1141 for (
int i = 0;
i <
path.elementCount();
i++) {
1142 if (
path.elementAt(
i).isSubpathStart())
1143 subPathStartPoints.append(
i);
1144 if (
path.elementAt(
i).isSubpathEnd()) {
1145 subPathEndPoints.append(
i);
1146 subPathHandled.append(
false);
1151 auto subPathIndex = [&](
int index) {
1152 for (
int i = 0;
i < subPathStartPoints.size();
i++) {
1153 if (
index >= subPathStartPoints.at(
i) &&
index <= subPathEndPoints.at(
i))
1160 auto ensureInBounds = [&](
int *
i,
float *
t,
float deltaT) {
1162 if (
path.elementAt(*i).isSubpathStart())
1163 *
i = subPathEndPoints.at(subPathIndex(*
i));
1167 }
else if (*
t >= 1.f) {
1168 if (
path.elementAt(*i).isSubpathEnd())
1169 *
i = subPathStartPoints.at(subPathIndex(*
i));
1183 if (subPathStartPoints.contains(
i))
1184 adjecent = subPathEndPoints.at(subPathStartPoints.indexOf(
i));
1191 qCDebug(lcSGCurveIntersectionSolver) <<
"Element" <<
i <<
"/" << adjecent <<
"meeting point is left/right inside:" << leftInside <<
"/" << rightInside;
1196 }
else if (leftInside) {
1207 QVarLengthArray<bool> handledElements(
path.elementCount(),
false);
1209 bool regularVisit =
true;
1221 bool forward =
true;
1223 int startedAtIndex = -1;
1224 float startedAtT = -1;
1226 if (!findStart(
path, 0,
path.elementCount(), &i1, &forward)) {
1227 qCDebug(lcSGCurveIntersectionSolver) <<
"No suitable start found. This should not happen. Returning the path unchanged.";
1232 auto startNewSubPath = [&](
int i,
bool forward) {
1234 fixedPath.moveTo(
path.elementAt(
i).startPoint());
1237 fixedPath.moveTo(
path.elementAt(
i).endPoint());
1241 subPathHandled[subPathIndex(
i)] =
true;
1243 startNewSubPath(i1, forward);
1247 int totalIterations = 0;
1250 int prevIntersection = -1;
1254 if (regularVisit && (
t == 0 ||
t == 1)) {
1256 if (
t == 1 &&
path.elementAt(i1).isSubpathEnd()) {
1257 nextIndex = subPathStartPoints.at(subPathIndex(i1));
1258 }
else if (
t == 1) {
1259 nextIndex = nextIndex + 1;
1261 if (handledElements[nextIndex]) {
1262 qCDebug(lcSGCurveIntersectionSolver) <<
"Revisiting an element when trying to solve intersections. This should not happen. Returning the path unchanged.";
1265 handledElements[nextIndex] =
true;
1270 qCDebug(lcSGCurveIntersectionSolver) <<
"Checking section" << i1 <<
"from" <<
t <<
"going" << (forward ?
"forward" :
"backward");
1274 t1 = forward? 1 : -1;
1275 for (
int j = 0;
j < intersections.size();
j++) {
1276 if (
j == prevIntersection)
1278 if (i1 == intersections[
j].e1 &&
1279 intersections[
j].
t1 * (forward ? 1 : -1) >=
t * (forward ? 1 : -1) &&
1280 intersections[
j].
t1 * (forward ? 1 : -1) <
t1 * (forward ? 1 : -1)) {
1282 t1 = intersections[
j].t1;
1283 i2 = intersections[
j].e2;
1284 t2 = intersections[
j].t2;
1286 if (i1 == intersections[
j].e2 &&
1287 intersections[
j].
t2 * (forward ? 1 : -1) >=
t * (forward ? 1 : -1) &&
1288 intersections[
j].
t2 * (forward ? 1 : -1) <
t1 * (forward ? 1 : -1)) {
1290 t1 = intersections[
j].t2;
1291 i2 = intersections[
j].e1;
1292 t2 = intersections[
j].t1;
1295 prevIntersection = iC;
1298 qCDebug(lcSGCurveIntersectionSolver) <<
" No intersection found on my way. Adding the rest of the segment " << i1;
1299 regularVisit =
true;
1305 if (
path.elementAt(i1).isLine()) {
1306 fixedPath.lineTo(
path.elementAt(i1).endPoint());
1309 fixedPath.quadTo(rest.controlPoint(), rest.endPoint());
1311 if (
path.elementAt(i1).isSubpathEnd()) {
1312 int index = subPathEndPoints.indexOf(i1);
1313 qCDebug(lcSGCurveIntersectionSolver) <<
" Going back to the start of subPath" <<
index;
1314 i1 = subPathStartPoints.at(
index);
1320 if (
path.elementAt(i1).isLine()) {
1321 fixedPath.lineTo(
path.elementAt(i1).startPoint());
1324 fixedPath.quadTo(rest.controlPoint(), rest.endPoint());
1326 if (
path.elementAt(i1).isSubpathStart()) {
1327 int index = subPathStartPoints.indexOf(i1);
1328 qCDebug(lcSGCurveIntersectionSolver) <<
" Going back to the end of subPath" <<
index;
1329 i1 = subPathEndPoints.at(
index);
1336 qCDebug(lcSGCurveIntersectionSolver) <<
" Found an intersection at" <<
t1 <<
"with" << i2 <<
"at" <<
t2;
1339 subPathHandled[subPathIndex(i2)] =
true;
1343 markIntersectionAsHandled(&intersections[iC], i1, !forward);
1348 if (elem1.isLine()) {
1349 fixedPath.lineTo(elem1.pointAtFraction(
t1));
1357 fixedPath.quadTo(partUntilIntersection.controlPoint(), partUntilIntersection.endPoint());
1361 if (intersections[iC].in1 && intersections[iC].in2 && intersections[iC].out1 && !intersections[iC].out2) {
1362 i1 = intersections[iC].e2;
1363 t = intersections[iC].t2;
1365 }
else if (intersections[iC].in1 && intersections[iC].in2 && !intersections[iC].out1 && intersections[iC].out2) {
1366 i1 = intersections[iC].e1;
1367 t = intersections[iC].t1;
1369 }
else if (intersections[iC].in1 && !intersections[iC].in2 && intersections[iC].out1 && intersections[iC].out2) {
1370 i1 = intersections[iC].e2;
1371 t = intersections[iC].t2;
1373 }
else if (!intersections[iC].in1 && intersections[iC].in2 && intersections[iC].out1 && intersections[iC].out2) {
1374 i1 = intersections[iC].e1;
1375 t = intersections[iC].t1;
1382 if (
t2 != 0 &&
t2 != 1) {
1385 tangent1 = -tangent1;
1387 const QVector2D tangent2 = elem2.tangentAtFraction(
t2);
1388 const float angle = angleBetween(-tangent1, tangent2);
1389 qCDebug(lcSGCurveIntersectionSolver) <<
" Angle at intersection is" <<
angle;
1391 constexpr float deltaAngle = 1e-3f;
1396 qCDebug(lcSGCurveIntersectionSolver) <<
" Next going forward from" <<
t <<
"on" << i1;
1401 qCDebug(lcSGCurveIntersectionSolver) <<
" Next going backward from" <<
t <<
"on" << i1;
1403 qCDebug(lcSGCurveIntersectionSolver) <<
" Found tangent. Staying on element";
1410 constexpr float deltaT = 1e-4f;
1412 float t2after =
t2 + deltaT;
1413 ensureInBounds(&i2after, &t2after, deltaT);
1415 if (fillSideForwardNew == QQuadPath::Element::FillSideRight) {
1419 qCDebug(lcSGCurveIntersectionSolver) <<
" Next going forward from" <<
t <<
"on" << i1;
1422 float t2before =
t2 - deltaT;
1423 ensureInBounds(&i2before, &t2before, deltaT);
1425 if (fillSideBackwardNew == QQuadPath::Element::FillSideLeft) {
1429 qCDebug(lcSGCurveIntersectionSolver) <<
" Next going backward from" <<
t <<
"on" << i1;
1431 qCDebug(lcSGCurveIntersectionSolver) <<
" Staying on element.";
1438 if (!(i1 == startedAtIndex &&
t == startedAtT))
1439 markIntersectionAsHandled(&intersections[iC], i1, forward);
1442 if (intersections[iC].in1 && intersections[iC].in2 && intersections[iC].out1 && intersections[iC].out2) {
1443 qCDebug(lcSGCurveIntersectionSolver) <<
" This intersection was processed completely and will be removed";
1444 intersections.removeAt(iC);
1445 prevIntersection = -1;
1447 regularVisit =
false;
1450 if (i1 == startedAtIndex &&
t == startedAtT) {
1453 qCDebug(lcSGCurveIntersectionSolver) <<
"Reached my starting point and try to find a new subpath.";
1456 int nextUnhandled = -1;
1457 for (
int i = 0;
i < subPathHandled.size();
i++) {
1458 if (!subPathHandled.at(
i)) {
1462 subPathHandled[
i] =
true;
1464 if (findStart(
path, subPathStartPoints.at(
i), subPathEndPoints.at(
i), &i1, &forward)) {
1466 qCDebug(lcSGCurveIntersectionSolver) <<
"Found a new subpath" <<
i <<
"to be processed.";
1467 startNewSubPath(i1, forward);
1468 regularVisit =
true;
1475 while (nextUnhandled < 0) {
1476 qCDebug(lcSGCurveIntersectionSolver) <<
"All subpaths handled. Looking for unhandled intersections.";
1477 if (intersections.isEmpty()) {
1478 qCDebug(lcSGCurveIntersectionSolver) <<
"All intersections handled. I am done.";
1484 IntersectionData &unhandledIntersec = intersections[0];
1485 prevIntersection = 0;
1486 regularVisit =
false;
1487 qCDebug(lcSGCurveIntersectionSolver) <<
"Revisiting intersection of" << unhandledIntersec.e1 <<
"with" << unhandledIntersec.e2;
1488 qCDebug(lcSGCurveIntersectionSolver) <<
"Handled are" << unhandledIntersec.e1 <<
"in:" << unhandledIntersec.in1 <<
"out:" << unhandledIntersec.out1
1489 <<
"/" << unhandledIntersec.e2 <<
"in:" << unhandledIntersec.in2 <<
"out:" << unhandledIntersec.out2;
1494 auto lookForwardOnIntersection = [&](
bool *handledPath,
int nextE,
float nextT,
bool nextForward) {
1497 constexpr float deltaT = 1e-4f;
1498 int eForward = nextE;
1499 float tForward = nextT + (nextForward ? deltaT : -deltaT);
1500 ensureInBounds(&eForward, &tForward, deltaT);
1502 if ((nextForward && fillSide == QQuadPath::Element::FillSideRight) ||
1503 (!nextForward && fillSide == QQuadPath::Element::FillSideLeft)) {
1504 fixedPath.moveTo(
path.elementAt(nextE).pointAtFraction(nextT));
1505 i1 = startedAtIndex = nextE;
1506 t = startedAtT = nextT;
1507 forward = nextForward;
1508 *handledPath =
true;
1514 if (lookForwardOnIntersection(&unhandledIntersec.in1, unhandledIntersec.e1, unhandledIntersec.t1,
false))
1516 if (lookForwardOnIntersection(&unhandledIntersec.in2, unhandledIntersec.e2, unhandledIntersec.t2,
false))
1518 if (lookForwardOnIntersection(&unhandledIntersec.out1, unhandledIntersec.e1, unhandledIntersec.t1,
true))
1520 if (lookForwardOnIntersection(&unhandledIntersec.out2, unhandledIntersec.e2, unhandledIntersec.t2,
true))
1523 intersections.removeFirst();
1524 qCDebug(lcSGCurveIntersectionSolver) <<
"Found no way to move forward at this intersection and removed it.";
1528 }
while (totalIterations <
path.elementCount() * 50);
1531 qCDebug(lcSGCurveIntersectionSolver) <<
"Could not solve intersections of path. This should not happen. Returning the path unchanged.";
1542 addStrokeTriangleCallback addTriangle,
1545 auto thePath = subdivide(strokePath, subdivisions).flattened();
1546 auto triangles = customTriangulator2(thePath, penWidth, joinStyle, capStyle, miterLimit);
1549 addTriangle(
t.points,
1550 { element.startPoint(), element.controlPoint(), element.endPoint() },
1555 auto addBevelTriangle = [&](
const TrianglePoints &
p)
1564 if (determinant(
p) < 0)
1566 float delta = penWidth / 2;
1577 addTriangle(
p, { fp1,
QVector2D(0.0f, 0.0f), fp2 },
n,
true);
1580 for (
const auto &triangle :
triangles) {
1581 if (triangle.pathElementIndex < 0) {
1582 addBevelTriangle(triangle.points);
1585 const auto &element = thePath.elementAt(triangle.pathElementIndex);
1586 addCurveTriangle(element, triangle);
1604 addTriangleCallback addTriangle)
1609 QMultiHash<QVector2D, int> pointHash;
1619 addTriangle({
sp, cp, ep },
1621 [&element](
QVector2D v) {
return elementUvForPoint(element,
v); });
1625 const std::array<QVector2D, 3> &
v,
1626 const std::array<QVector2D, 3> &
n) {
1627 addTriangle(
v,
n, [&element](
QVector2D v) {
return elementUvForPoint(element,
v); });
1630 auto outsideNormal = [](
const QVector2D &startPoint,
1634 QVector2D baseLine = endPoint - startPoint;
1635 QVector2D insideVector = insidePoint - startPoint;
1636 QVector2D normal = normalVector(baseLine);
1640 return swap ? normal : -normal;
1647 addCurveTriangle(element,
sp, ep, cp);
1650 const QVector2D normal = outsideNormal(
sp, ep, cp);
1652 addCurveTriangleWithNormals(element, {
sp,
sp, ep}, {null, normal, null});
1653 addCurveTriangleWithNormals(element, {
sp, ep, ep}, {normal, normal, null});
1660 addTriangleForLine(element,
sp, ep, cp);
1667 addCurveTriangle(element,
sp, ep, cp);
1673 const QVector2D normal = outsideNormal(
sp, cp, ep);
1674 addCurveTriangleWithNormals(element, {
sp,
sp, cp}, {null, normal, null});
1679 const QVector2D normal = outsideNormal(ep, cp,
sp);
1680 addCurveTriangleWithNormals(element, {ep, ep, cp}, {null, normal, null});
1686 addTriangle({
p1,
p2, p3 },
1698 internalHull.moveTo(
sp.toPointF());
1700 internalHull.lineTo(ep.
toPointF());
1701 pointHash.insert(rsp,
index);
1706 internalHull.lineTo(ep.
toPointF());
1707 addTriangleForConvex(element, rsp, rep, rcp);
1708 pointHash.insert(rsp,
index);
1710 internalHull.lineTo(cp.
toPointF());
1711 internalHull.lineTo(ep.
toPointF());
1712 addTriangleForConcave(element, rsp, rep, rcp);
1713 pointHash.insert(rcp,
index);
1725 float side1 = testSideOfLineByNormal(linePoint, lineNormal,
p1);
1726 float side2 = testSideOfLineByNormal(linePoint, lineNormal,
p2);
1727 return side1 * side2 >= 0;
1740 bool safeSideOf1 = onSameSideOfLine(
p,
c,
a, n1);
1741 bool safeSideOf2 = onSameSideOfLine(
p,
c,
b, n2);
1742 return safeSideOf1 && safeSideOf2;
1747 auto handleTriangle = [&](
const QVector2D (&
p)[3]) ->
bool {
1749 bool isConcave =
false;
1750 bool isConvex =
false;
1751 int elementIndex = -1;
1753 bool foundElement =
false;
1757 for (
int i = 0;
i < 3; ++
i) {
1758 auto pointFoundRange = std::as_const(pointHash).equal_range(roundVec2D(
p[
i]));
1760 if (pointFoundRange.first == pointHash.constEnd())
1764 int testIndex = *pointFoundRange.first;
1765 bool ambiguous = std::next(pointFoundRange.first) != pointFoundRange.second;
1770 for (
auto it = pointFoundRange.first;
it != pointFoundRange.second; ++
it) {
1772 bool fillOnLeft = !
el.isFillOnRight();
1773 auto sp = roundVec2D(
el.startPoint());
1774 auto ep = roundVec2D(
el.endPoint());
1777 return p ==
sp ||
p == ep
1780 if (pointInside(
p[0]) && pointInside(
p[1]) && pointInside(
p[2])) {
1787 const auto &element = fillPath.
elementAt(testIndex);
1792 bool onElement =
false;
1793 for (
int j = 0;
j < 3; ++
j) {
1797 onElement = roundVec2D(element.
endPoint()) ==
p[
j];
1805 foundElement =
true;
1806 elementIndex = testIndex;
1809 isConcave = !
isLine && !isConvex;
1816 int ci = (6 - si - ei) % 3;
1817 addTriangleForLine(fillPath.
elementAt(elementIndex),
p[si],
p[ei],
p[ci]);
1818 }
else if (isConcave) {
1819 addCurveTriangle(fillPath.
elementAt(elementIndex),
p[0],
p[1],
p[2]);
1820 }
else if (isConvex) {
1821 int oi = (6 - si - ei) % 3;
1822 const auto &otherPoint =
p[oi];
1823 const auto &element = fillPath.
elementAt(elementIndex);
1826 bool safeSpace = pointInSafeSpace(otherPoint, element);
1828 addCurveTriangle(element,
p[0],
p[1],
p[2]);
1833 for (
int i = 0;
i < 7; ++
i) {
1834 safeSpace = pointInSafeSpace(newPoint, element);
1837 newPoint = (
p[si] +
p[ei] + newPoint) / 3;
1842 addCurveTriangle(element,
p[si],
p[ei], newPoint);
1844 addFillTriangle(
p[si],
p[oi], newPoint);
1845 addFillTriangle(
p[ei],
p[oi], newPoint);
1848 addFillTriangle(
p[0],
p[1],
p[2]);
1853 addFillTriangle(
p[0],
p[1],
p[2]);
1861 triangles.indices.setDataUint({ 0, 1, 2 });
1864 for (
int triangle = 0; triangle <
triangles.indices.size() / 3; ++triangle) {
1865 const quint32 *idx = &idxTable[triangle * 3];
1868 for (
int i = 0;
i < 3; ++
i) {
1870 float(
triangles.vertices.at(idx[
i] * 2 + 1))));
1874 bool needsSplit = !handleTriangle(
p);
1877 for (
int i = 0;
i < 3; ++
i) {
\inmodule QtCore\compares equality \compareswith equality QLine \endcompareswith
void setFillRule(Qt::FillRule fillRule)
Sets the fill rule of the painter path to the given fillRule.
\inmodule QtCore\reentrant
bool isSubpathStart() const
Element segmentFromTo(float t0, float t1) const
QVector2D startPoint() const
QVector2D endPoint() const
QVector2D referencePoint() const
QVector2D controlPoint() const
Element & elementAt(int i)
void iterateElements(Func &&lambda)
static bool isPointOnLeft(const QVector2D &p, const QVector2D &sp, const QVector2D &ep)
@ PathNonOverlappingControlPointTriangles
void setPathHints(PathHints newHints)
void setFillRule(Qt::FillRule rule)
static void processStroke(const QQuadPath &strokePath, float miterLimit, float penWidth, Qt::PenJoinStyle joinStyle, Qt::PenCapStyle capStyle, addStrokeTriangleCallback addTriangle, int subdivisions=3)
static QList< QPair< int, int > > findOverlappingCandidates(const QQuadPath &path)
static bool solveOverlaps(QQuadPath &path)
static bool solveIntersections(QQuadPath &path, bool removeNestedPaths=true)
static void processFill(const QQuadPath &path, Qt::FillRule fillRule, addTriangleCallback addTriangle)
static bool removeNestedSubpaths(QQuadPath &path)
The QVector2D class represents a vector or vertex in 2D space.
constexpr float y() const noexcept
Returns the y coordinate of this point.
QVector2D normalized() const noexcept
Returns the normalized unit vector form of this vector.
constexpr float x() const noexcept
Returns the x coordinate of this point.
static constexpr float dotProduct(QVector2D v1, QVector2D v2) noexcept
Returns the dot product of v1 and v2.
constexpr QPointF toPointF() const noexcept
Returns the QPointF form of this 2D vector.
The QVector3D class represents a vector or vertex in 3D space.
list append(new Employee("Blackpool", "Stephen"))
QSet< QString >::iterator it
Q_DECL_CONST_FUNCTION constexpr size_t hash(size_t key, size_t seed) noexcept
Combined button and popup list for selecting options.
#define Q_STATIC_ASSERT(Condition)
static const QPainterPath::ElementType * subPath(const QPainterPath::ElementType *t, const QPainterPath::ElementType *end, const qreal *points, bool *closed)
bool qFuzzyIsNull(qfloat16 f) noexcept
qint64 qRound64(qfloat16 d) noexcept
#define Q_LOGGING_CATEGORY(name,...)
#define qCDebug(category,...)
constexpr const T & qMin(const T &a, const T &b)
constexpr const T & qMax(const T &a, const T &b)
constexpr T qAbs(const T &t)
GLint GLfloat GLfloat GLfloat v2
GLboolean GLboolean GLboolean b
GLsizei const GLfloat * v
[13]
GLint GLint GLint GLint GLint x
[0]
GLenum GLuint GLint level
GLboolean GLboolean GLboolean GLboolean a
[7]
GLuint GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat s1
GLenum GLuint GLenum GLsizei length
GLenum GLenum GLsizei count
GLint GLsizei GLsizei GLenum GLenum GLsizei void * data
GLuint GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat t1
[4]
GLenum GLuint GLintptr offset
GLfixed GLfixed GLint GLint GLfixed points
GLsizei const GLchar *const * path
GLint GLenum GLboolean normalized
static qreal dot(const QPointF &a, const QPointF &b)
static bool isLine(const QBezier &bezier)
static const qreal epsilon
static Q_CONSTINIT QBasicAtomicInteger< unsigned > seed
size_t qHash(QVector2D key, size_t seed=0) noexcept
static const struct TessellationModeTab triangles[]
QT_BEGIN_NAMESPACE constexpr void qSwap(T &value1, T &value2) noexcept(std::is_nothrow_swappable_v< T >)
Q_GUI_EXPORT QTriangleSet qTriangulate(const qreal *polygon, int count, uint hint, const QTransform &matrix, bool allowUintIndices)
unsigned long long quint64