aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/quick/scenegraph/qsgcurveprocessor.cpp640
-rw-r--r--src/quick/scenegraph/qsgcurveprocessor_p.h3
-rw-r--r--src/quick/scenegraph/util/qquadpath.cpp123
-rw-r--r--src/quick/scenegraph/util/qquadpath_p.h33
-rw-r--r--src/quickshapes/qquickshapecurverenderer.cpp3
-rw-r--r--src/quickshapes/qquickshapecurverenderer_p.h1
-rw-r--r--tests/baseline/scenegraph/data/shape/shape_intersecting1.qml72
-rw-r--r--tests/baseline/scenegraph/data/shape/shape_intersecting2.qml73
-rw-r--r--tests/manual/painterpathquickshape/CMakeLists.txt2
-rw-r--r--tests/manual/painterpathquickshape/ControlPanel.qml21
-rw-r--r--tests/manual/painterpathquickshape/ControlledShape.qml2
-rw-r--r--tests/manual/painterpathquickshape/Intersect.qml125
-rw-r--r--tests/manual/painterpathquickshape/Intersect2.qml136
-rw-r--r--tests/manual/painterpathquickshape/main.qml8
14 files changed, 1227 insertions, 15 deletions
diff --git a/src/quick/scenegraph/qsgcurveprocessor.cpp b/src/quick/scenegraph/qsgcurveprocessor.cpp
index 427a344413..6fe9b56855 100644
--- a/src/quick/scenegraph/qsgcurveprocessor.cpp
+++ b/src/quick/scenegraph/qsgcurveprocessor.cpp
@@ -10,6 +10,7 @@
QT_BEGIN_NAMESPACE
Q_LOGGING_CATEGORY(lcSGCurveProcessor, "qt.quick.curveprocessor");
+Q_LOGGING_CATEGORY(lcSGCurveIntersectionSolver, "qt.quick.curveprocessor.intersections");
namespace {
// Input coordinate space is pre-mapped so that (0, 0) maps to [0, 0] in uv space.
@@ -110,6 +111,38 @@ bool checkEdge(QVector2D &p1, QVector2D &p2, QVector2D &p, float epsilon)
return determinant(p1, p2, p) <= epsilon;
}
+// Check if lines l1 and l2 are intersecting and return the respective value. Solutions are stored to
+// the optional pointer solution.
+bool lineIntersection(const LinePoints &l1, const LinePoints &l2, QList<QPair<float, float>> *solution = nullptr)
+{
+ constexpr double eps2 = 1e-5; // Epsilon for parameter space t1-t2
+
+ // see https://www.wolframalpha.com/input?i=solve%28A+%2B+t+*+B+%3D+C+%2B+s*D%3B+E+%2B+t+*+F+%3D+G+%2B+s+*+H+for+s+and+t%29
+ const float A = l1[0].x();
+ const float B = l1[1].x() - l1[0].x();
+ const float C = l2[0].x();
+ const float D = l2[1].x() - l2[0].x();
+ const float E = l1[0].y();
+ const float F = l1[1].y() - l1[0].y();
+ const float G = l2[0].y();
+ const float H = l2[1].y() - l2[0].y();
+
+ float det = D * F - B * H;
+
+ if (det == 0)
+ return false;
+
+ float s = (F * (A - C) - B * (E - G)) / det;
+ float t = (H * (A - C) - D * (E - G)) / det;
+
+ bool intersecting = (s >= eps2 && s <= 1. - eps2 && t >= eps2 && t <= 1. - eps2);
+
+ if (solution && intersecting)
+ solution->append(QPair<float, float>(t, s));
+
+ return intersecting;
+}
+
bool checkTriangleOverlap(TrianglePoints &triangle1, TrianglePoints &triangle2, float epsilon = 1.0/32)
{
@@ -173,26 +206,142 @@ bool checkTriangleContains (QVector2D pt, QVector2D v1, QVector2D v2, QVector2D
return allNegative || allPositive;
}
-// e1 is always a concave curve. e2 can be curve or line
static bool isOverlap(const QQuadPath &path, int e1, int e2)
{
const QQuadPath::Element &element1 = path.elementAt(e1);
const QQuadPath::Element &element2 = path.elementAt(e2);
- Q_ASSERT(!element1.isLine());
- TrianglePoints t1{ element1.startPoint(), element1.controlPoint(), element1.endPoint() };
-
- if (element2.isLine()) {
- LinePoints line{ element2.startPoint(), element2.endPoint() };
- return checkLineTriangleOverlap(t1, line);
+ if (element1.isLine()) {
+ LinePoints line1{ element1.startPoint(), element1.endPoint() };
+ if (element2.isLine()) {
+ LinePoints line2{ element2.startPoint(), element2.endPoint() };
+ return lineIntersection(line1, line2);
+ } else {
+ TrianglePoints t2{ element2.startPoint(), element2.controlPoint(), element2.endPoint() };
+ return checkLineTriangleOverlap(t2, line1);
+ }
} else {
- TrianglePoints t2{ element2.startPoint(), element2.controlPoint(), element2.endPoint() };
- return checkTriangleOverlap(t1, t2);
+ TrianglePoints t1{ element1.startPoint(), element1.controlPoint(), element1.endPoint() };
+ if (element2.isLine()) {
+ LinePoints line{ element2.startPoint(), element2.endPoint() };
+ return checkLineTriangleOverlap(t1, line);
+ } else {
+ TrianglePoints t2{ element2.startPoint(), element2.controlPoint(), element2.endPoint() };
+ return checkTriangleOverlap(t1, t2);
+ }
}
return false;
}
+static float angleBetween(const QVector2D v1, const QVector2D v2)
+{
+ float dot = v1.x() * v2.x() + v1.y() * v2.y();
+ float cross = v1.x() * v2.y() - v1.y() * v2.x();
+ //TODO: Optimization: Maybe we don't need the atan2 here.
+ return atan2(cross, dot);
+}
+
+static bool isIntersecting(const TrianglePoints &t1, const TrianglePoints &t2, QList<QPair<float, float>> *solutions = nullptr)
+{
+ constexpr double eps = 1e-5; // Epsilon for coordinate space x-y
+ constexpr double eps2 = 1e-5; // Epsilon for parameter space t1-t2
+ constexpr int maxIterations = 7; // Maximum iterations allowed for Newton
+
+ // Convert to double to get better accuracy.
+ QPointF td1[3] = {QPointF(t1[0].x(), t1[0].y()), QPointF(t1[1].x(), t1[1].y()), QPointF(t1[2].x(), t1[2].y())};
+ QPointF td2[3] = {QPointF(t2[0].x(), t2[0].y()), QPointF(t2[1].x(), t2[1].y()), QPointF(t2[2].x(), t2[2].y())};
+
+ // F = P1(t1) - P2(t2) where P1 and P2 are bezier curve functions.
+ // F = (0, 0) at the intersection.
+ // t is the vector of bezier curve parameters for curves P1 and P2
+ auto F = [=](QPointF t) { return
+ td1[0] * (1 - t.x()) * (1. - t.x()) + 2 * td1[1] * (1. - t.x()) * t.x() + td1[2] * t.x() * t.x() -
+ td2[0] * (1 - t.y()) * (1. - t.y()) - 2 * td2[1] * (1. - t.y()) * t.y() - td2[2] * t.y() * t.y();};
+
+ // J is the Jacobi Matrix dF/dt where F and t are both vectors of dimension 2.
+ // Storing in a QLineF for simplicity.
+ auto J = [=](QPointF t) { return QLineF(
+ td1[0].x() * (-2 * (1-t.x())) + 2 * td1[1].x() * (1 - 2 * t.x()) + td1[2].x() * 2 * t.x(),
+ -td2[0].x() * (-2 * (1-t.y())) - 2 * td2[1].x() * (1 - 2 * t.y()) - td2[2].x() * 2 * t.y(),
+ td1[0].y() * (-2 * (1-t.x())) + 2 * td1[1].y() * (1 - 2 * t.x()) + td1[2].y() * 2 * t.x(),
+ -td2[0].y() * (-2 * (1-t.y())) - 2 * td2[1].y() * (1 - 2 * t.y()) - td2[2].y() * 2 * t.y());};
+
+ // solve the equation A(as 2x2 matrix)*x = b. Returns x.
+ auto solve = [](QLineF A, QPointF b) {
+ // invert A
+ const double det = A.x1() * A.y2() - A.y1() * A.x2();
+ QLineF Ainv(A.y2() / det, -A.y1() / det, -A.x2() / det, A.x1() / det);
+ // return A^-1 * b
+ return QPointF(Ainv.x1() * b.x() + Ainv.y1() * b.y(),
+ Ainv.x2() * b.x() + Ainv.y2() * b.y());
+ };
+
+#ifdef INTERSECTION_EXTRA_DEBUG
+ qCDebug(lcSGCurveIntersectionSolver) << "Checking" << t1[0] << t1[1] << t1[2];
+ qCDebug(lcSGCurveIntersectionSolver) << " vs" << t2[0] << t2[1] << t2[2];
+#endif
+
+ // TODO: Try to figure out reasonable starting points to reach all 4 possible intersections.
+ // This works but is kinda brute forcing it.
+ const QList<QPointF> tref {{0., 0.}, {0.5, 0.}, {1., 0.}, {0., 0.5}, {0.5, 0.5}, {1., 0.5}, {0., 1.}, {0.5, 1.}, {1., 1.}};
+
+ for (auto t0 : tref) {
+ QPointF t = t0;
+ double err = 1;
+ QPointF fval = F(t);
+ int i = 0;
+
+ // TODO: Try to abort sooner, e.g. when falling out of the interval [0-1]?
+ while (err > eps && i < maxIterations) { // && t.x() >= 0 && t.x() <= 1 && t.y() >= 0 && t.y() <= 1) {
+ t = t - solve(J(t), fval);
+ fval = F(t);
+ err = qAbs(fval.x()) + qAbs(fval.y()); // Using the Manhatten length as an error indicator.
+ i++;
+#ifdef INTERSECTION_EXTRA_DEBUG
+ qCDebug(lcSGCurveIntersectionSolver) << " Newton iteration" << i << "t =" << t << "F =" << fval << "Error =" << err;
+#endif
+ }
+ if (err < eps && t.x() > 10 * eps2 && t.x() < 1. - 10 * eps2 && t.y() > 10 * eps2 && t.y() < 1. - 10 * eps2) {
+#ifdef INTERSECTION_EXTRA_DEBUG
+ qCDebug(lcSGCurveIntersectionSolver) << " Newton solution (after" << i << ")=" << t << "(" << F(t) << ")";
+#endif
+ if (solutions) {
+ bool append = true;
+ for (auto solution : *solutions) {
+ if (qAbs(solution.first - t.x()) < 10 * eps2 && qAbs(solution.second - t.y()) < 10 * eps2)
+ append = false;
+ }
+ if (append)
+ solutions->append({t.x(), t.y()});
+ }
+ else
+ return true;
+ }
+ }
+ if (solutions)
+ return solutions->size() > 0;
+ else
+ return false;
+}
+
+static bool isIntersecting(const QQuadPath &path, int e1, int e2, QList<QPair<float, float>> *solutions = nullptr)
+{
+
+ const QQuadPath::Element &elem1 = path.elementAt(e1);
+ const QQuadPath::Element &elem2 = path.elementAt(e2);
+
+ if (elem1.isLine() && elem2.isLine()) {
+ return lineIntersection(LinePoints {elem1.startPoint(), elem1.endPoint() },
+ LinePoints {elem2.startPoint(), elem2.endPoint() },
+ solutions);
+ } else {
+ return isIntersecting(TrianglePoints { elem1.startPoint(), elem1.controlPoint(), elem1.endPoint() },
+ TrianglePoints { elem2.startPoint(), elem2.controlPoint(), elem2.endPoint() },
+ solutions);
+ }
+}
+
static bool isOverlap(const QQuadPath &path, int index, const QVector2D &vertex)
{
const QQuadPath::Element &elem = path.elementAt(index);
@@ -721,7 +870,7 @@ static void handleOverlap(QQuadPath &path, int e1, const QVector2D vertex, int r
if (vertex == path.elementAt(e1).endPoint() || !isOverlap(path, e1, vertex))
return;
if (recursionLevel > 8) {
- qDebug() << "Vertex overlap: recursion level" << recursionLevel << "aborting!";
+ qCDebug(lcSGCurveIntersectionSolver) << "Vertex overlap: recursion level" << recursionLevel << "aborting!";
return;
}
@@ -779,6 +928,477 @@ void QSGCurveProcessor::solveOverlaps(QQuadPath &path)
}
}
+// A fast algorithm to find path elements that might overlap. We will only check the overlap of the
+// triangles that define the elements.
+// We will order the elements first and then pool them depending on their x-values. This should
+// reduce the complexity to O(n log n), where n is the number of elements in the path.
+QList<QPair<int, int>> QSGCurveProcessor::findOverlappingCandidates(const QQuadPath &path)
+{
+ struct bRect { float xmin; float xmax; float ymin; float ymax; };
+
+ // Calculate all bounding rectanlges
+ QList<int> elementStarts;
+ QVarLengthArray<bRect, 32> boundingRects;
+ boundingRects.reserve(path.elementCount());
+ for (int i = 0; i < path.elementCount(); i++) {
+ QQuadPath::Element e = path.elementAt(i);
+
+ bRect bR{qMin(qMin(e.startPoint().x(), e.controlPoint().x()), e.endPoint().x()),
+ qMax(qMax(e.startPoint().x(), e.controlPoint().x()), e.endPoint().x()),
+ qMin(qMin(e.startPoint().y(), e.controlPoint().y()), e.endPoint().y()),
+ qMax(qMax(e.startPoint().y(), e.controlPoint().y()), e.endPoint().y())};
+ boundingRects.append(bR);
+ elementStarts.append(i);
+ }
+
+ // Sort the bounding rectangles by x-startpoint and x-endpoint
+ auto compareXmin = [&](int i, int j){return boundingRects.at(i).xmin < boundingRects.at(j).xmin;};
+ auto compareXmax = [&](int i, int j){return boundingRects.at(i).xmax < boundingRects.at(j).xmax;};
+ std::sort(elementStarts.begin(), elementStarts.end(), compareXmin);
+ QList<int> elementEnds = elementStarts;
+ std::sort(elementEnds.begin(), elementEnds.end(), compareXmax);
+
+ QList<int> bRpool;
+ QList<QPair<int, int>> overlappingBB;
+
+ // Start from x = xmin and move towards xmax. Add a rectangle to the pool and check for
+ // intersections with all other rectangles in the pool. If a rectangles xmax is smaller
+ // than the new xmin, it can be removed from the pool.
+ while (!elementStarts.isEmpty()) {
+ int addIndex = elementStarts.takeFirst();
+ const bRect &newR = boundingRects.at(addIndex);
+
+ // First remove elements from the pool that cannot touch the new one
+ // because xmax is too small
+ while (bRpool.size() && elementEnds.size() && newR.xmin >= boundingRects.at(elementEnds.first()).xmax) {
+ int removeIndex = elementEnds.takeFirst();
+ bRpool.removeOne(removeIndex);
+ }
+
+ // Now compare the new element with all elements in the pool.
+ for (int j = 0; j < bRpool.size(); j++) {
+ int i = bRpool.at(j);
+ const bRect &r1 = boundingRects.at(i);
+ // We don't have to check for x because the pooling takes care of it.
+ //if (r1.xmax <= newR.xmin || newR.xmax <= r1.xmin)
+ // continue;
+ if (r1.ymax <= newR.ymin || newR.ymax <= r1.ymin)
+ continue;
+ // If the bounding boxes are overlapping it is a candidate for an intersection.
+ if (isOverlap(path, i, addIndex)) // Another test to see if the triangles overlap
+ overlappingBB.append(QPair<int, int>(i, addIndex));
+ }
+ bRpool.append(addIndex); //Add the new element to the pool.
+ }
+ return overlappingBB;
+}
+
+void QSGCurveProcessor::solveIntersections(QQuadPath &path, bool alwaysReorder)
+{
+ struct IntersectionData { int e1; int e2; float t1; float t2; bool in1 = false, in2 = false, out1 = false, out2 = false; };
+ QList<IntersectionData> intersections;
+
+ // Helper function to mark an intersection as handled when the
+ // path i is processed moving forward/backward
+ auto markIntersectionAsHandled = [=](IntersectionData *data, int i, bool forward) {
+ if (data->e1 == i) {
+ if (forward)
+ data->out1 = true;
+ else
+ data->in1 = true;
+ } else if (data->e2 == i){
+ if (forward)
+ data->out2 = true;
+ else
+ data->in2 = true;
+ } else {
+ Q_UNREACHABLE();
+ }
+ };
+
+ // First make a O(n log n) search for candidates.
+ const QList<QPair<int, int>> candidates = findOverlappingCandidates(path);
+
+ // Then check the candidates for actual intersections.
+ for (const auto &candidate : candidates) {
+ QList<QPair<float,float>> res;
+ int e1 = candidate.first;
+ int e2 = candidate.second;
+ if (isIntersecting(path, e1, e2, &res)) {
+ for (const auto &r : res)
+ intersections.append({e1, e2, r.first, r.second});
+ }
+ }
+
+ qCDebug(lcSGCurveIntersectionSolver) << "----- Checking for Intersections -----";
+ qCDebug(lcSGCurveIntersectionSolver) << "Found" << intersections.length() << "intersections";
+ for (const auto &i : intersections) {
+ auto p1 = path.elementAt(i.e1).pointAtFraction(i.t1);
+ auto p2 = path.elementAt(i.e2).pointAtFraction(i.t2);
+ qCDebug(lcSGCurveIntersectionSolver) << " between" << i.e1 << "and" << i.e2 << "at" << i.t1 << "/" << i.t2 << "->" << p1 << "/" << p2;
+ }
+
+ if (intersections.isEmpty() && !alwaysReorder) {
+ qCDebug(lcSGCurveIntersectionSolver) << "Returning the path unchanged.";
+ return;
+ }
+
+ // Store the starting and end elements of the subpaths to be able
+ // to jump quickly between them. Also keep a list of handled paths,
+ // so we know if we need to come back to a subpath or if it
+ // was already united with another subpath due to an intersection.
+ QList<int> subPathStartPoints;
+ QList<int> subPathEndPoints;
+ QList<bool> subPathHandled;
+ for (int i = 0; i < path.elementCount(); i++) {
+ if (path.elementAt(i).isSubpathStart())
+ subPathStartPoints.append(i);
+ if (path.elementAt(i).isSubpathEnd()) {
+ subPathEndPoints.append(i);
+ subPathHandled.append(false);
+ }
+ }
+
+ // A small helper to find the subPath of an element with index
+ auto subPathIndex = [&](int index) {
+ for (int i = 0; i < subPathStartPoints.size(); i++) {
+ if (index >= subPathStartPoints.at(i) && index <= subPathEndPoints.at(i))
+ return i;
+ }
+ return -1;
+ };
+
+ // Helper function to find a siutable starting point between start and end.
+ // A suitable starting point is where right is inside and left is outside
+ // If left is inside and right is outside it works too, just move in the
+ // other direction (forward = false).
+ auto findStart = [=](QQuadPath &path, int start, int end, int *result, bool *forward) {
+ for (int i = start; i < end; i++) {
+ int adjecent;
+ if (subPathStartPoints.contains(i))
+ adjecent = subPathEndPoints.at(subPathStartPoints.indexOf(i));
+ else
+ adjecent = i - 1;
+
+ QQuadPath::Element::FillSide fillSide = path.fillSideOf(i, 1e-4f);
+ const bool leftInside = fillSide == QQuadPath::Element::FillSideLeft;
+ const bool rightInside = fillSide == QQuadPath::Element::FillSideRight;
+ qCDebug(lcSGCurveIntersectionSolver) << "Element" << i << "/" << adjecent << "meeting point is left/right inside:" << leftInside << "/" << rightInside;
+ if (rightInside) {
+ *result = i;
+ *forward = true;
+ return true;
+ } else if (leftInside) {
+ *result = adjecent;
+ *forward = false;
+ return true;
+ }
+ }
+ return false;
+ };
+
+ // Also store handledElements. This is used to identify and abort
+ // on errors.
+ QVarLengthArray<bool> handledElements(path.elementCount(), false);
+
+ QQuadPath fixedPath;
+ fixedPath.setFillRule(path.fillRule());
+
+ int i1 = 0;
+ float t1 = 0;
+
+ int i2 = 0;
+ float t2 = 0;
+
+ float t = 0;
+ bool forward = true;
+
+ int startedAtIndex = -1;
+ float startedAtT = -1;
+
+ if (!findStart(path, 0, path.elementCount(), &i1, &forward)) {
+ qWarning() << "No suitable start found. This should not happen. Returning the path unchanged.";
+ return;
+ }
+
+ // Helper function to start a new subpath and update temporary variables.
+ auto startNewSubPath = [&](int i, bool forward) {
+ if (forward) {
+ fixedPath.moveTo(path.elementAt(i).startPoint());
+ t = startedAtT = 0;
+ } else {
+ fixedPath.moveTo(path.elementAt(i).endPoint());
+ t = startedAtT = 1;
+ }
+ startedAtIndex = i;
+ subPathHandled[subPathIndex(i)] = true;
+ };
+ startNewSubPath(i1, forward);
+
+ // If not all interactions where found correctly, we might end up in an infinite loop.
+ // Therefore we count the total number of iterations and bail out at some point.
+ int totalIterations = 0;
+
+ do {
+ // Sanity check: Make sure that we do not process the same corner point more than once.
+ if (t == 0 || t == 1) {
+ int nextIndex = i1;
+
+ if (t == 1 && path.elementAt(i1).isSubpathEnd()) {
+ nextIndex = subPathStartPoints.at(subPathIndex(i1));
+ } else if (t == 1) {
+ nextIndex = nextIndex + 1;
+ }
+ if (handledElements[nextIndex]) {
+ qWarning() << "Revisiting an element when trying to solve intersections. This should not happen. Returning the path unchanged.";
+ return;
+ }
+ handledElements[nextIndex] = true;
+ }
+ // Sanity check: Keep an eye on total iterations
+ totalIterations++;
+
+ qCDebug(lcSGCurveIntersectionSolver) << "Checking section" << i1 << "from" << t << "going" << (forward ? "forward" : "backward");
+
+ // Find the next intersection that is as close as possible to t but in direction of processing (forward or !forward).
+ int iC = -1; //intersection candidate
+ t1 = forward? +1 : -1; //intersection candidate t-value
+ for (int j = 0; j < intersections.size(); j++) {
+ if (i1 == intersections[j].e1 &&
+ intersections[j].t1 * (forward? 1 : -1) > t * (forward? 1 : -1) &&
+ intersections[j].t1 * (forward? 1 : -1) < t1 * (forward? 1 : -1)) {
+ iC = j;
+ t1 = intersections[j].t1;
+ i2 = intersections[j].e2;
+ t2 = intersections[j].t2;
+ }
+ if (i1 == intersections[j].e2 &&
+ intersections[j].t2 * (forward?1 : -1) > t * (forward? 1 : -1) &&
+ intersections[j].t2 * (forward?1 : -1) < t1 * (forward?1 : -1)) {
+ iC = j;
+ t1 = intersections[j].t2;
+ i2 = intersections[j].e1;
+ t2 = intersections[j].t1;
+ }
+ }
+
+ if (iC < 0) {
+ qCDebug(lcSGCurveIntersectionSolver) << " No intersection found on my way. Adding the rest of the segment " << i1;
+ // If no intersection with the current element was found, just add the rest of the element
+ // to the fixed path and go on.
+ // If we reached the end (going forward) or start (going backward) of a subpath, we have
+ // to wrap aroud. Abort condition for the loop comes separately later.
+ if (forward) {
+ if (path.elementAt(i1).isLine()) {
+ fixedPath.lineTo(path.elementAt(i1).endPoint());
+ } else {
+ const QQuadPath::Element rest = path.elementAt(i1).segmentFromTo(t, 1);
+ fixedPath.quadTo(rest.controlPoint(), rest.endPoint());
+ }
+ if (path.elementAt(i1).isSubpathEnd()) {
+ int index = subPathEndPoints.indexOf(i1);
+ qCDebug(lcSGCurveIntersectionSolver) << " Going back to the start of subPath" << index;
+ i1 = subPathStartPoints.at(index);
+ } else {
+ i1++;
+ }
+ t = 0;
+ } else {
+ if (path.elementAt(i1).isLine()) {
+ fixedPath.lineTo(path.elementAt(i1).startPoint());
+ } else {
+ const QQuadPath::Element rest = path.elementAt(i1).segmentFromTo(0, t).reversed();
+ fixedPath.quadTo(rest.controlPoint(), rest.endPoint());
+ }
+ if (path.elementAt(i1).isSubpathStart()) {
+ int index = subPathStartPoints.indexOf(i1);
+ qCDebug(lcSGCurveIntersectionSolver) << " Going back to the end of subPath" << index;
+ i1 = subPathEndPoints.at(index);
+ } else {
+ i1--;
+ }
+ t = 1;
+ }
+ } else { // Here comes the part where we actually handle intersections.
+ qCDebug(lcSGCurveIntersectionSolver) << " Found an intersection at" << t1 << "with" << i2 << "at" << t2;
+
+ // Mark the subpath we intersected with as visisted. We do not have to come here explicitly again.
+ subPathHandled[subPathIndex(i2)] = true;
+
+ // Mark the path that lead us to this intersection as handled on the intersection level.
+ // Note the ! in front of forward. This is required because we move towards the intersection.
+ markIntersectionAsHandled(&intersections[iC], i1, !forward);
+
+ // Split the path from the last point to the newly found intersection.
+ // Add the part of the current segment to the fixedPath.
+ const QQuadPath::Element &elem1 = path.elementAt(i1);
+ if (elem1.isLine()) {
+ fixedPath.lineTo(elem1.pointAtFraction(t1));
+ } else {
+ QQuadPath::Element partUntilIntersection;
+ if (forward) {
+ partUntilIntersection = elem1.segmentFromTo(t, t1);
+ } else {
+ partUntilIntersection = elem1.segmentFromTo(t1, t).reversed();
+ }
+ fixedPath.quadTo(partUntilIntersection.controlPoint(), partUntilIntersection.endPoint());
+ }
+
+ // If only one unhandled path is left the decision how to proceed is trivial
+ if (intersections[iC].in1 && intersections[iC].in2 && intersections[iC].out1 && !intersections[iC].out2) {
+ i1 = intersections[iC].e2;
+ t = intersections[iC].t2;
+ forward = true;
+ } else if (intersections[iC].in1 && intersections[iC].in2 && !intersections[iC].out1 && intersections[iC].out2) {
+ i1 = intersections[iC].e1;
+ t = intersections[iC].t1;
+ forward = true;
+ } else if (intersections[iC].in1 && !intersections[iC].in2 && intersections[iC].out1 && intersections[iC].out2) {
+ i1 = intersections[iC].e2;
+ t = intersections[iC].t2;
+ forward = false;
+ } else if (!intersections[iC].in1 && intersections[iC].in2 && intersections[iC].out1 && intersections[iC].out2) {
+ i1 = intersections[iC].e1;
+ t = intersections[iC].t1;
+ forward = false;
+ } else {
+ // If no trivial path is left, calculate the intersection angle to decide which path to move forward.
+ // For winding fill we take the left most path forward, so the inside stays on the right side
+ // For odd even fill we take the right most path forward so we cut of the smallest area.
+ // We come back at the intersection and add the missing pieces as subpaths later on.
+ QVector2D tangent1 = elem1.tangentAtFraction(t1);
+ if (!forward)
+ tangent1 = -tangent1;
+ const QQuadPath::Element &elem2 = path.elementAt(i2);
+ const QVector2D tangent2 = elem2.tangentAtFraction(t2);
+ const float angle = angleBetween(-tangent1, tangent2);
+ qCDebug(lcSGCurveIntersectionSolver) << " Angle at intersection is" << angle;
+ // A small angle. Everything smaller is interpreted as tangent
+ constexpr float deltaAngle = 1e-3f;
+ if ((angle > deltaAngle && path.fillRule() == Qt::WindingFill) || (angle < -deltaAngle && path.fillRule() == Qt::OddEvenFill)) {
+ forward = true;
+ i1 = i2;
+ t = t2;
+ qCDebug(lcSGCurveIntersectionSolver) << " Next going forward from" << t2 << "on" << i2;
+ } else if ((angle < -deltaAngle && path.fillRule() == Qt::WindingFill) || (angle > deltaAngle && path.fillRule() == Qt::OddEvenFill)) {
+ forward = false;
+ i1 = i2;
+ t = t2;
+ qCDebug(lcSGCurveIntersectionSolver) << " Next going backward from" << t2 << "on" << i2;
+ } else { // this is basically a tangential touch and and no crossing. So stay on the current path, keep direction
+ qCDebug(lcSGCurveIntersectionSolver) << " Found tangent. Staying on element";
+ }
+ }
+
+ // Mark the path that takes us away from this intersection as handled on the intersection level.
+ if (!(i1 == startedAtIndex && t == startedAtT))
+ markIntersectionAsHandled(&intersections[iC], i1, forward);
+
+ // If we took all paths from an intersection it can be deleted.
+ if (intersections[iC].in1 && intersections[iC].in2 && intersections[iC].out1 && intersections[iC].out2) {
+ qCDebug(lcSGCurveIntersectionSolver) << " This intersection was processed completely and will be removed";
+ intersections.removeAt(iC);
+ }
+ }
+
+ if (i1 == startedAtIndex && t == startedAtT) {
+ // We reached the point on the subpath where we started. This subpath is done.
+ // We have to find an unhandled subpath or a new subpath that was generated by cuts/intersections.
+ qCDebug(lcSGCurveIntersectionSolver) << "Reached my starting point and try to find a new subpath.";
+
+ // Search for the next subpath to handle.
+ int nextUnhandled = -1;
+ for (int i = 0; i < subPathHandled.size(); i++) {
+ if (!subPathHandled.at(i)) {
+
+ // Not nesesarrily handled (if findStart return false) but if we find no starting
+ // point, we cannot/don't need to handle it anyway. So just mark it as handled.
+ subPathHandled[i] = true;
+
+ if (findStart(path, subPathStartPoints.at(i), subPathEndPoints.at(i), &i1, &forward)) {
+ nextUnhandled = i;
+ qCDebug(lcSGCurveIntersectionSolver) << "Found a new subpath" << i << "to be processed.";
+ startNewSubPath(i1, forward);
+ break;
+ }
+ }
+ }
+
+ // If no valid subpath is left, we have to go back to the unhandled intersections.
+ while (nextUnhandled < 0) {
+ qCDebug(lcSGCurveIntersectionSolver) << "All subpaths handled. Looking for unhandled intersections.";
+ if (intersections.isEmpty()) {
+ qCDebug(lcSGCurveIntersectionSolver) << "All intersections handled. I am done.";
+ path = fixedPath;
+ return;
+ }
+
+ IntersectionData &unhandledIntersec = intersections[0];
+ qCDebug(lcSGCurveIntersectionSolver) << "Revisiting intersection of" << unhandledIntersec.e1 << "with" << unhandledIntersec.e2;
+ qCDebug(lcSGCurveIntersectionSolver) << "Handled are" << unhandledIntersec.e1 << "in:" << unhandledIntersec.in1 << "out:" << unhandledIntersec.out1
+ << "/" << unhandledIntersec.e2 << "in:" << unhandledIntersec.in2 << "out:" << unhandledIntersec.out2;
+
+ // Searching for the correct direction to go forward.
+ // That requires that the intersection + small delta (here 1e-4)
+ // is a valid starting point (filling only on one side)
+ constexpr float deltaT = 1e-4f;
+ if (!unhandledIntersec.in1) {
+ QQuadPath::Element::FillSide fillSide = path.fillSideOf(unhandledIntersec.e1, unhandledIntersec.t1 - deltaT);
+ if (fillSide == QQuadPath::Element::FillSideLeft) {
+ fixedPath.moveTo(path.elementAt(unhandledIntersec.e1).pointAtFraction(unhandledIntersec.t1));
+ i1 = startedAtIndex = unhandledIntersec.e1;
+ t = startedAtT = unhandledIntersec.t1;
+ forward = false;
+ unhandledIntersec.in1 = true;
+ break;
+ }
+ }
+ if (!unhandledIntersec.in2) {
+ QQuadPath::Element::FillSide fillSide = path.fillSideOf(unhandledIntersec.e2, unhandledIntersec.t2 - deltaT);
+ if (fillSide == QQuadPath::Element::FillSideLeft) {
+ fixedPath.moveTo(path.elementAt(unhandledIntersec.e1).pointAtFraction(unhandledIntersec.t1));
+ i1 = startedAtIndex = unhandledIntersec.e2;
+ t = startedAtT = unhandledIntersec.t2;
+ forward = false;
+ unhandledIntersec.in2 = true;
+ break;
+ }
+ }
+ if (!unhandledIntersec.out1) {
+ QQuadPath::Element::FillSide fillSide = path.fillSideOf(unhandledIntersec.e1, unhandledIntersec.t1 + deltaT);
+ if (fillSide == QQuadPath::Element::FillSideRight) {
+ fixedPath.moveTo(path.elementAt(unhandledIntersec.e1).pointAtFraction(unhandledIntersec.t1));
+ i1 = startedAtIndex = unhandledIntersec.e1;
+ t = startedAtT = unhandledIntersec.t1;
+ forward = true;
+ unhandledIntersec.out1 = true;
+ break;
+ }
+ }
+ if (!unhandledIntersec.out2) {
+ QQuadPath::Element::FillSide fillSide = path.fillSideOf(unhandledIntersec.e2, unhandledIntersec.t2 + deltaT);
+ if (fillSide == QQuadPath::Element::FillSideRight) {
+ fixedPath.moveTo(path.elementAt(unhandledIntersec.e1).pointAtFraction(unhandledIntersec.t1));
+ i1 = startedAtIndex = unhandledIntersec.e2;
+ t = startedAtT = unhandledIntersec.t2;
+ forward = true;
+ unhandledIntersec.out2 = true;
+ break;
+ }
+ }
+ intersections.removeFirst();
+ qCDebug(lcSGCurveIntersectionSolver) << "Found no way to move forward at this intersection and removed it.";
+ }
+ }
+
+ } while (totalIterations < path.elementCount() * 50);
+ // Check the totalIterations as a sanity check. Should never be triggered.
+
+ qWarning() << "Could not solve intersections of path. This should not happen. Returning the path unchanged.";
+
+}
+
+
void QSGCurveProcessor::processStroke(const QQuadPath &strokePath,
float miterLimit,
float penWidth,
diff --git a/src/quick/scenegraph/qsgcurveprocessor_p.h b/src/quick/scenegraph/qsgcurveprocessor_p.h
index 271f15207c..442c319d01 100644
--- a/src/quick/scenegraph/qsgcurveprocessor_p.h
+++ b/src/quick/scenegraph/qsgcurveprocessor_p.h
@@ -44,6 +44,9 @@ public:
addStrokeTriangleCallback addTriangle,
int subdivisions = 3);
static void solveOverlaps(QQuadPath &path);
+ static QList<QPair<int, int>> findOverlappingCandidates(const QQuadPath &path);
+ static void solveIntersections(QQuadPath &path, bool alwaysReorder = true);
+
};
QT_END_NAMESPACE
diff --git a/src/quick/scenegraph/util/qquadpath.cpp b/src/quick/scenegraph/util/qquadpath.cpp
index 8ce818ae1f..70fca33e1c 100644
--- a/src/quick/scenegraph/util/qquadpath.cpp
+++ b/src/quick/scenegraph/util/qquadpath.cpp
@@ -203,6 +203,37 @@ QVector2D QQuadPath::Element::pointAtFraction(float t) const
}
}
+QQuadPath::Element QQuadPath::Element::segmentFromTo(float t0, float t1) const
+{
+ if (t0 <= 0 && t1 >= 1)
+ return *this;
+
+ Element part;
+ part.sp = pointAtFraction(t0);
+ part.ep = pointAtFraction(t1);
+
+ if (isLine()) {
+ part.cp = 0.5f * (part.sp + part.ep);
+ part.m_isLine = true;
+ } else {
+ // Split curve right at t0, yields { t0, rcp, endPoint } quad segment
+ const QVector2D rcp = (1 - t0) * controlPoint() + t0 * endPoint();
+ // Split that left at t1, yields { t0, lcp, t1 } quad segment
+ float segmentT = (t1 - t0) / (1 - t0);
+ part.cp = (1 - segmentT) * part.sp + segmentT * rcp;
+ }
+ return part;
+}
+
+QQuadPath::Element QQuadPath::Element::reversed() const {
+ Element swappedElement;
+ swappedElement.ep = sp;
+ swappedElement.cp = cp;
+ swappedElement.sp = ep;
+ swappedElement.m_isLine = m_isLine;
+ return swappedElement;
+}
+
float QQuadPath::Element::extent() const
{
// TBD: cache this value if we start using it a lot
@@ -333,6 +364,82 @@ bool QQuadPath::contains(const QVector2D &point) const
return (fillRule() == Qt::WindingFill ? (winding_number != 0) : ((winding_number % 2) != 0));
}
+// similar as contains. But we treat the element with the index elementIdx in a special way
+// that should be numerically more stable. The result is a contains for a point on the left
+// and for the right side of the element.
+QQuadPath::Element::FillSide QQuadPath::fillSideOf(int elementIdx, float elementT) const
+{
+ constexpr float toleranceT = 1e-3f;
+ const QVector2D point = m_elements.at(elementIdx).pointAtFraction(elementT);
+
+ int winding_number = 0;
+ for (int i = 0; i < elementCount(); i++) {
+ const Element &e = m_elements.at(i);
+ int dir = 1;
+ float y1 = e.startPoint().y();
+ float y2 = e.endPoint().y();
+ if (y2 < y1) {
+ qSwap(y1, y2);
+ dir = -1;
+ }
+ if (e.m_isLine) {
+ if (point.y() < y1 || point.y() >= y2 || y1 == y2)
+ continue;
+ const float t = (point.y() - e.startPoint().y()) / (e.endPoint().y() - e.startPoint().y());
+ const float x = e.startPoint().x() + t * (e.endPoint().x() - e.startPoint().x());
+ if ((elementIdx != i && x <= point.x()) ||
+ (elementIdx == i && x <= point.x() && qAbs(t - elementT) > toleranceT)) {
+ winding_number += dir;
+ }
+ } else {
+ y1 = qMin(y1, e.controlPoint().y());
+ y2 = qMax(y2, e.controlPoint().y());
+ if (point.y() < y1 || point.y() >= y2)
+ continue;
+ float ts[2];
+ const int numRoots = e.intersectionsAtY(point.y(), ts);
+ // Count if there is exactly one intersection to the left
+ bool oneHit = false;
+ float tForHit = -1;
+ for (int j = 0; j < numRoots; j++) {
+ const float x = e.pointAtFraction(ts[j]).x();
+ if ((elementIdx != i && x <= point.x()) ||
+ (elementIdx == i && x <= point.x() && qAbs(ts[j] - elementT) > toleranceT)) {
+ oneHit = !oneHit;
+ tForHit = ts[j];
+ }
+ }
+ if (oneHit) {
+ dir = e.tangentAtFraction(tForHit).y() < 0 ? -1 : 1;
+ winding_number += dir;
+ }
+ }
+ };
+
+ int left_winding_number = winding_number;
+ int right_winding_number = winding_number;
+
+ int dir = m_elements.at(elementIdx).tangentAtFraction(elementT).y() < 0 ? -1 : 1;
+
+ if (dir > 0) {
+ left_winding_number += dir;
+ } else {
+ right_winding_number += dir;
+ }
+
+ bool leftInside = (fillRule() == Qt::WindingFill ? (left_winding_number != 0) : ((left_winding_number % 2) != 0));
+ bool rightInside = (fillRule() == Qt::WindingFill ? (right_winding_number != 0) : ((right_winding_number % 2) != 0));
+
+ if (leftInside && rightInside)
+ return QQuadPath::Element::FillSideBoth;
+ else if (leftInside)
+ return QQuadPath::Element::FillSideLeft;
+ else if (rightInside)
+ return QQuadPath::Element::FillSideRight;
+ else
+ return QQuadPath::Element::FillSideUndetermined; //should not happen except for numerical error.
+}
+
void QQuadPath::addElement(const QVector2D &control, const QVector2D &endPoint, bool isLine)
{
if (qFuzzyCompare(currentPoint, endPoint))
@@ -494,6 +601,22 @@ QPainterPath QQuadPath::toPainterPath() const
return res;
}
+QString QQuadPath::asSvgString() const
+{
+ QString res;
+ QTextStream str(&res);
+ for (const Element &element : m_elements) {
+ if (element.isSubpathStart())
+ str << "M " << element.startPoint().x() << " " << element.startPoint().y() << " ";
+ if (element.isLine())
+ str << "L " << element.endPoint().x() << " " << element.endPoint().y() << " ";
+ else
+ str << "Q " << element.controlPoint().x() << " " << element.controlPoint().y() << " "
+ << element.endPoint().x() << " " << element.endPoint().y() << " ";
+ }
+ return res;
+}
+
// Returns a new path since doing it inline would probably be less efficient
// (technically changing it from O(n) to O(n^2))
// Note that this function should be called before splitting any elements,
diff --git a/src/quick/scenegraph/util/qquadpath_p.h b/src/quick/scenegraph/util/qquadpath_p.h
index d1d8f32eb1..7540f277a0 100644
--- a/src/quick/scenegraph/util/qquadpath_p.h
+++ b/src/quick/scenegraph/util/qquadpath_p.h
@@ -35,6 +35,11 @@ public:
{
}
+ Element (QVector2D s, QVector2D c, QVector2D e)
+ : sp(s), cp(c), ep(e), m_isSubpathStart(false), m_isSubpathEnd(false), m_isLine(false)
+ {
+ }
+
bool isSubpathStart() const
{
return m_isSubpathStart;
@@ -89,6 +94,10 @@ public:
}
}
+ Element segmentFromTo(float t0, float t1) const;
+
+ Element reversed() const;
+
int childCount() const { return m_numChildren; }
int indexOfChild(int childNumber) const
@@ -120,20 +129,35 @@ public:
m_curvatureFlags = Element::CurvatureFlags(m_curvatureFlags & ~Element::Convex);
}
+ void setFillOnRight(bool isFillOnRight)
+ {
+ if (isFillOnRight)
+ m_curvatureFlags = Element::CurvatureFlags(m_curvatureFlags | Element::FillOnRight);
+ else
+ m_curvatureFlags = Element::CurvatureFlags(m_curvatureFlags & ~Element::FillOnRight);
+ }
+
bool isControlPointOnLeft() const
{
return isPointOnLeft(cp, sp, ep);
}
- private:
- int intersectionsAtY(float y, float *fractions) const;
-
enum CurvatureFlags : quint8 {
CurvatureUndetermined = 0,
FillOnRight = 1,
Convex = 2
};
+ enum FillSide : quint8 {
+ FillSideUndetermined = 0,
+ FillSideRight = 1,
+ FillSideLeft = 2,
+ FillSideBoth = 3
+ };
+
+ private:
+ int intersectionsAtY(float y, float *fractions) const;
+
QVector2D sp;
QVector2D cp;
QVector2D ep;
@@ -190,6 +214,7 @@ public:
static QQuadPath fromPainterPath(const QPainterPath &path);
QPainterPath toPainterPath() const;
+ QString asSvgString() const;
QQuadPath subPathsClosed() const;
void addCurvatureData();
@@ -197,6 +222,7 @@ public:
QQuadPath dashed(qreal lineWidth, const QList<qreal> &dashPattern, qreal dashOffset = 0) const;
void splitElementAt(int index);
bool contains(const QVector2D &point) const;
+ Element::FillSide fillSideOf(int elementIdx, float elementT) const;
template<typename Func>
void iterateChildrenOf(Element &e, Func &&lambda)
@@ -256,7 +282,6 @@ private:
Element::CurvatureFlags coordinateOrderOfElement(const Element &element) const;
friend QDebug operator<<(QDebug, const QQuadPath &);
-
bool subPathToStart = true;
Qt::FillRule m_fillRule = Qt::OddEvenFill;
QVector2D currentPoint;
diff --git a/src/quickshapes/qquickshapecurverenderer.cpp b/src/quickshapes/qquickshapecurverenderer.cpp
index e78b9a8a40..d4bd4ea96c 100644
--- a/src/quickshapes/qquickshapecurverenderer.cpp
+++ b/src/quickshapes/qquickshapecurverenderer.cpp
@@ -417,6 +417,7 @@ void QQuickShapeCurveRenderer::updateNode()
void QQuickShapeCurveRenderer::processPath(PathData *pathData)
{
static const bool doOverlapSolving = !qEnvironmentVariableIntValue("QT_QUICKSHAPES_DISABLE_OVERLAP_SOLVER");
+ static const bool doIntersetionSolving = !qEnvironmentVariableIntValue("QT_QUICKSHAPES_DISABLE_INTERSECTION_SOLVER");
static const bool useTriangulatingStroker = qEnvironmentVariableIntValue("QT_QUICKSHAPES_TRIANGULATING_STROKER");
static const bool simplifyPath = qEnvironmentVariableIntValue("QT_QUICKSHAPES_SIMPLIFY_PATHS");
@@ -436,6 +437,8 @@ void QQuickShapeCurveRenderer::processPath(PathData *pathData)
if (pathData->isFillVisible()) {
if (pathData->fillPath.isEmpty()) {
pathData->fillPath = pathData->path.subPathsClosed();
+ if (doIntersetionSolving)
+ QSGCurveProcessor::solveIntersections(pathData->fillPath);
pathData->fillPath.addCurvatureData();
if (doOverlapSolving)
QSGCurveProcessor::solveOverlaps(pathData->fillPath);
diff --git a/src/quickshapes/qquickshapecurverenderer_p.h b/src/quickshapes/qquickshapecurverenderer_p.h
index d86cf65960..12d147d80a 100644
--- a/src/quickshapes/qquickshapecurverenderer_p.h
+++ b/src/quickshapes/qquickshapecurverenderer_p.h
@@ -118,6 +118,7 @@ private:
static NodeList addTriangulatingStrokerNodes(const PathData &pathData);
static NodeList addCurveStrokeNodes(const PathData &pathData);
+ void solveIntersections(QQuadPath &path);
QQuickItem *m_item;
QSGNode *m_rootNode = nullptr;
QVector<PathData> m_paths;
diff --git a/tests/baseline/scenegraph/data/shape/shape_intersecting1.qml b/tests/baseline/scenegraph/data/shape/shape_intersecting1.qml
new file mode 100644
index 0000000000..1501a8e1c7
--- /dev/null
+++ b/tests/baseline/scenegraph/data/shape/shape_intersecting1.qml
@@ -0,0 +1,72 @@
+// Copyright (C) 2023 The Qt Company Ltd.
+// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
+
+import QtQuick
+import QtQuick.Shapes
+
+Item {
+ width: 1200
+ height: 600
+
+ ListModel {
+ id: fillRules
+ ListElement { fillrule: ShapePath.WindingFill }
+ ListElement { fillrule: ShapePath.OddEvenFill }
+ }
+
+ ListModel {
+ id: renderers
+ ListElement { renderer: Shape.GeometryRenderer }
+ ListElement { renderer: Shape.CurveRenderer }
+ }
+
+ ListModel {
+ id: svgstrings
+ ListElement { scaleToFit: 0.11; offsetX: 20; offsetY: 20; pathString: "M 885.276 1047.5 Q 1310 -265 722.654 1071.85 Q 1100 1100 636.857 929.582 Q 100 1100 322.456 883.006 L 1003.49 134.715 Q 944.382 591.106 0 0 L 885.276 1047.5"}
+ ListElement { scaleToFit: 0.035; offsetX: -60; offsetY: 0; pathString: "M 5000 3475 Q 5600 825 2290 245 Q 3635 -30 5360 3885 Q 730 2990 4685 390 L 2445 1435 L 5000 3475" }
+ ListElement { scaleToFit: 0.11; offsetX: 10; offsetY: 10; pathString: "M 600 200 Q 1000 600 600 1000 Q 200 1200 200 600 Q 200 200 600 200 M 1000 200 Q 1400 600 1000 1000 Q 600 1200 600 600 Q 200 -200 1000 200" }
+ ListElement { scaleToFit: 0.11; offsetX: -10; offsetY: 10; pathString: "M 865 270 Q 1000 600 955 820 Q 675 690 775 525 Q 200 200 865 270 M 1000 200 Q 1400 600 1000 1000 Q 600 1200 590 635 Q 200 -200 1000 200" }
+ ListElement { scaleToFit: 0.11; offsetX: -10; offsetY: 10; pathString: "M 568.243 506.927 Q 1000 600 955 820 Q 675 690 1007.14 396.964 Q 616.417 79.1432 568.243 506.927 M 1000 200 Q 1400 600 1000 1000 Q 600 1200 590 635 Q 200 -200 1000 200" }
+ ListElement { scaleToFit: 0.11; offsetX: -10; offsetY: 10; pathString: "M 562.26 285.556 Q 728.371 717.267 955 820 Q 1037.57 642.136 1007.14 396.964 Q 616.417 79.1432 562.26 285.556 M 1000 200 Q 1400 600 1000 1000 Q 600 1200 590 635 Q 200 -200 1000 200" }
+ ListElement { scaleToFit: 0.09; offsetX: -10; offsetY: 10; pathString: "M 550.789, 661.103 Q 1435.03, -8.14249 1668.28, 799.321 Q 1100, 1100 593.639, 527.481 Q 593.639 527.481 100 1100 100 600 Q 100 600 1208.1 876.376 2316.21, 1152.75 Q 2316.21 1152.75 1433.5 906.927 550.789 661.103" }
+ ListElement { scaleToFit: 0.04; offsetX: 35; offsetY: 10; pathString: "M 846.361 1397.06 Q 2485 -660 2485 1015 Q 1598.13 4529.81 975 290 Q -69.0821 3853.43 -568.237 1473.61 L 2515.73 2262.31 L 846.361 1397.06" }
+ }
+
+ Column {
+ Repeater {
+ model: renderers
+ Column {
+ Repeater {
+ model: fillRules
+ Row {
+ Repeater {
+ model: svgstrings
+ Rectangle {
+ width: 150
+ height: 150
+ border.color: "black"
+
+ Shape {
+ preferredRendererType: renderer
+ ShapePath {
+ fillColor: renderer == Shape.CurveRenderer ? "#99483d8b" : "#99dc143c"
+ fillRule: fillrule
+ strokeWidth: 0
+ PathSvg { path: pathString }
+ }
+
+ transform: Matrix4x4 {
+ matrix: Qt.matrix4x4(scaleToFit, 0, 0, offsetX,
+ 0, scaleToFit, 0, offsetY,
+ 0, 0, 1, 0,
+ 0, 0, 0, 1)
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+}
diff --git a/tests/baseline/scenegraph/data/shape/shape_intersecting2.qml b/tests/baseline/scenegraph/data/shape/shape_intersecting2.qml
new file mode 100644
index 0000000000..df303d97bf
--- /dev/null
+++ b/tests/baseline/scenegraph/data/shape/shape_intersecting2.qml
@@ -0,0 +1,73 @@
+// Copyright (C) 2023 The Qt Company Ltd.
+// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
+
+import QtQuick
+import QtQuick.Shapes
+
+Item {
+ width: 1200
+ height: 600
+
+ ListModel {
+ id: fillRules
+ ListElement { fillrule: ShapePath.WindingFill }
+ ListElement { fillrule: ShapePath.OddEvenFill }
+ }
+
+ ListModel {
+ id: renderers
+ ListElement { renderer: Shape.GeometryRenderer }
+ ListElement { renderer: Shape.CurveRenderer }
+ }
+
+ // The last two paths don't work yet
+ ListModel {
+ id: svgstrings
+ ListElement { scaleToFit: 0.11; offsetX: 20; offsetY: 20; pathString: "M 200 200 Q 600 1000 1000 200 Q -100 200 200 1000 Q -100 1000 -100 500 Q -300 200 200 200 M 300 200 L 800 700 L 300 700 L 800 200 L 300 200"}
+ ListElement { scaleToFit: 0.11; offsetX: 20; offsetY: 20; pathString: "M 200 200 Q 600 1000 1000 200 Q -100 200 200 1000 Q -100 1000 -100 500 Q -300 200 200 200 M 300 200 L 300 700 L 800 200 L 800 700 L 300 200"}
+ ListElement { scaleToFit: 1; offsetX: 0; offsetY: 0; pathString: "M 128.84 103.6 L 112.71 68.78 L 64.32 19.15 L 144.33 94.34 L 47.33 98.82 Q 37.0 60.87 39.01 12.06 L 51.92 72.5 L 19.87 130.09 L 139.11 47.81 Q 110.47 70.31 113.71 87.09 "}
+ ListElement { scaleToFit: 1; offsetX: 0; offsetY: 0; pathString: "M 85.23 92.08 Q 126.6 2.98 23.72 51.94 Z M 103.97 123.27 L 145.32 76.51 Z M 134.57 28.24 L 41.44 8.54 Z M 43.48 123.1 Q 58.58 39.75 92.72 144.17 Z M 23.86 116.3 Q 5.82 83.87 84.11 130.88"}
+ ListElement { scaleToFit: 1; offsetX: 0; offsetY: 0; pathString: "M 64.9 142.96 Q 4.68 9.31 7.25 121.42 Z M 5.3 86.37 Q 31.57 11.81 34.04 5.0 Q 25.26 47.39 31.31 87.97 Z M 4.2 17.35 L 33.27 124.0 Q 111.36 33.37 8.23 118.77 L 65.78 27.48 Q 139.84 87.06 96.03 23.08"}
+ ListElement { scaleToFit: 1; offsetX: 0; offsetY: 0; pathString: "M 88.78 105.24 L 69.72 114.27 L 26.94 71.0 Q 62.05 122.52 83.1 22.44 Q 105.46 40.25 108.12 54.23 L 103.51 40.41 Q 70.16 41.09 29.88 96.16 Z M 60.49 96.92 L 14.58 112.34 Q 1.76 12.05 106.52 128.97"}
+ ListElement { scaleToFit: 1; offsetX: 0; offsetY: 0; pathString: "M 70.21 146.61 L 54.01 6.38 Z M 52.51 5.75 L 70.75 44.78 L 81.98 128.43 Z M 2.71 72.51 L 96.86 4.48 L 136.96 83.88 Z M 25.32 52.79 Q 3.59 111.11 125.15 137.23"}
+ ListElement { scaleToFit: 1; offsetX: 0; offsetY: 0; pathString: "M 131.61 147.43 L 4.5 6.5 L 110.44 40.71 Q 128.69 39.15 136.85 6.84 Q 8.9 139.71 76.35 103.86 L 77.47 43.63 L 127.06 97.65 L 14.97 66.38 Z M 47.53 0.08 L 42.02 33.25"}
+ }
+
+ Column {
+ Repeater {
+ model: renderers
+ Column {
+ Repeater {
+ model: fillRules
+ Row {
+ Repeater {
+ model: svgstrings
+ Rectangle {
+ width: 150
+ height: 150
+ border.color: "black"
+
+ Shape {
+ preferredRendererType: renderer
+ ShapePath {
+ fillColor: renderer == Shape.CurveRenderer ? "#99483d8b" : "#99dc143c"
+ fillRule: fillrule
+ strokeWidth: 0
+ PathSvg { path: pathString }
+ }
+
+ transform: Matrix4x4 {
+ matrix: Qt.matrix4x4(scaleToFit, 0, 0, offsetX,
+ 0, scaleToFit, 0, offsetY,
+ 0, 0, 1, 0,
+ 0, 0, 0, 1)
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+}
diff --git a/tests/manual/painterpathquickshape/CMakeLists.txt b/tests/manual/painterpathquickshape/CMakeLists.txt
index 1f92afaba5..4677fad26c 100644
--- a/tests/manual/painterpathquickshape/CMakeLists.txt
+++ b/tests/manual/painterpathquickshape/CMakeLists.txt
@@ -36,6 +36,8 @@ set(qml_resource_files
"SimpleShape.qml"
"SmallPolygon.qml"
"Squircle.qml"
+ "Intersect.qml"
+ "Intersect2.qml"
"ControlledShape.qml"
"Mussel.qml"
"Graziano.ttf"
diff --git a/tests/manual/painterpathquickshape/ControlPanel.qml b/tests/manual/painterpathquickshape/ControlPanel.qml
index bb26e658f3..3fbe33968f 100644
--- a/tests/manual/painterpathquickshape/ControlPanel.qml
+++ b/tests/manual/painterpathquickshape/ControlPanel.qml
@@ -15,6 +15,7 @@ Item {
property color outlineColor: enableOutline.checked ? Qt.rgba(outlineColor.color.r, outlineColor.color.g, outlineColor.color.b, outlineAlpha) : Qt.rgba(0,0,0,0)
property color fillColor: Qt.rgba(fillColor.color.r, fillColor.color.g, fillColor.color.b, pathAlpha)
property alias pathAlpha: alphaSlider.value
+ property alias fillRule: fillRule.currentValue
property alias outlineAlpha: outlineAlphaSlider.value
property real outlineWidth: cosmeticPen.checked ? outlineWidthEdit.text / scale : outlineWidthEdit.text
property alias outlineStyle: outlineStyle.currentValue
@@ -46,6 +47,7 @@ Item {
property alias cosmeticPen: cosmeticPen.checked
property alias pathAlpha: alphaSlider.value
+ property alias fillRule: fillRule.currentIndex
property alias fillColor: fillColor.color
property alias setBackground: setBackground.checked
@@ -218,6 +220,25 @@ Item {
model: [ "NoGradient", "LinearGradient", "RadialGradient", "ConicalGradient" ]
}
Label {
+ text: "Fill rule:"
+ color: "white"
+ }
+ ComboBox {
+ id: fillRule
+ textRole: "text"
+ valueRole: "style"
+ model: ListModel {
+ ListElement {
+ text: "WindingFill"
+ style: ShapePath.WindingFill
+ }
+ ListElement {
+ text: "OddEvenFill"
+ style: ShapePath.OddEvenFill
+ }
+ }
+ }
+ Label {
text: "Fill alpha(" + Math.round(alphaSlider.value*100)/100 + "):"
color: "white"
}
diff --git a/tests/manual/painterpathquickshape/ControlledShape.qml b/tests/manual/painterpathquickshape/ControlledShape.qml
index db8333c2e2..087c4084dd 100644
--- a/tests/manual/painterpathquickshape/ControlledShape.qml
+++ b/tests/manual/painterpathquickshape/ControlledShape.qml
@@ -81,7 +81,7 @@ Item {
ShapePath {
id: shapePath
- fillRule: ShapePath.WindingFill
+ fillRule: controlPanel.fillRule
fillGradient: gradients[controlPanel.gradientType]
strokeColor: controlPanel.outlineColor
fillColor: controlPanel.fillColor
diff --git a/tests/manual/painterpathquickshape/Intersect.qml b/tests/manual/painterpathquickshape/Intersect.qml
new file mode 100644
index 0000000000..ed1156f388
--- /dev/null
+++ b/tests/manual/painterpathquickshape/Intersect.qml
@@ -0,0 +1,125 @@
+// Copyright (C) 2023 The Qt Company Ltd.
+// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR BSD-3-Clause
+
+import QtQuick
+import QtQuick.Shapes
+
+ControlledShape {
+ delegate: [
+ PathMove { x: p0.cx; y: p0.cy },
+ PathQuad { x: p1.cx; y: p1.cy; controlX: c0.cx; controlY: c0.cy },
+ PathQuad { x: p2.cx; y: p2.cy; controlX: c1.cx; controlY: c1.cy },
+ PathQuad { x: p3.cx; y: p3.cy; controlX: c2.cx; controlY: c2.cy },
+ PathQuad { x: p0.cx; y: p0.cy; controlX: c3.cx; controlY: c3.cy },
+ PathMove { x: p4.cx; y: p4.cy; },
+ PathLine { x: p5.cx; y: p5.cy; },
+ PathLine { x: p6.cx; y: p6.cy; },
+ PathLine { x: p7.cx; y: p7.cy; },
+ PathLine { x: p4.cx; y: p4.cy; }
+ ]
+
+ ControlPoint {
+ id: p0
+ cx: 200
+ cy: 200
+ }
+ ControlPoint {
+ id: c0
+ color: "blue"
+ cx: 600
+ cy: 1000
+ }
+ ControlPoint {
+ id: p1
+ cx: 1000
+ cy: 200
+ }
+ ControlPoint {
+ id: c1
+ color: "blue"
+ cx: -100
+ cy: 200
+ }
+ ControlPoint {
+ id: p2
+ color: "red"
+ cx: 200
+ cy: 1000
+ }
+ ControlPoint {
+ id: c2
+ color: "blue"
+ cx: -100
+ cy: 1000
+ }
+ ControlPoint {
+ id: p3
+ color: "red"
+ cx: -100
+ cy: 500
+ }
+ ControlPoint {
+ id: c3
+ color: "blue"
+ cx: -300
+ cy: 200
+ }
+
+ ControlPoint {
+ id: p4
+ color: "green"
+ cx: 2000
+ cy: 200
+ }
+ ControlPoint {
+ id: p5
+ color: "green"
+ cx: 2500
+ cy: 700
+ }
+ ControlPoint {
+ id: p6
+ color: "green"
+ cx: 2000
+ cy: 700
+ }
+ ControlPoint {
+ id: p7
+ color: "green"
+ cx: 2500
+ cy: 200
+ }
+
+ Text {
+ anchors.centerIn: p0
+ text: "p0"
+ }
+ Text {
+ anchors.centerIn: p1
+ text: "p1"
+ }
+ Text {
+ anchors.centerIn: p2
+ text: "p2"
+ }
+ Text {
+ anchors.centerIn: p3
+ text: "p3"
+ }
+ Text {
+ anchors.centerIn: c0
+ text: "c0"
+ }
+ Text {
+ anchors.centerIn: c1
+ text: "c1"
+ }
+ Text {
+ anchors.centerIn: c2
+ text: "c2"
+ }
+ Text {
+ anchors.centerIn: c3
+ text: "c3"
+ }
+}
diff --git a/tests/manual/painterpathquickshape/Intersect2.qml b/tests/manual/painterpathquickshape/Intersect2.qml
new file mode 100644
index 0000000000..408eaa1afb
--- /dev/null
+++ b/tests/manual/painterpathquickshape/Intersect2.qml
@@ -0,0 +1,136 @@
+// Copyright (C) 2023 The Qt Company Ltd.
+// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR BSD-3-Clause
+
+import QtQuick
+import QtQuick.Shapes
+
+ControlledShape {
+ delegate: [
+ PathMove { x: p0.cx; y: p0.cy },
+ PathQuad { x: p1.cx; y: p1.cy; controlX: c0.cx; controlY: c0.cy },
+ PathQuad { x: p2.cx; y: p2.cy; controlX: c1.cx; controlY: c1.cy },
+ PathQuad { x: p0.cx; y: p0.cy; controlX: c2.cx; controlY: c2.cy },
+ PathMove { x: p3.cx; y: p3.cy },
+ PathQuad { x: p4.cx; y: p4.cy; controlX: c3.cx; controlY: c3.cy },
+ PathQuad { x: p5.cx; y: p5.cy; controlX: c4.cx; controlY: c4.cy },
+ PathQuad { x: p3.cx; y: p3.cy; controlX: c5.cx; controlY: c5.cy }
+ ]
+
+ ControlPoint {
+ id: p0
+ cx: 600
+ cy: 200
+ }
+ ControlPoint {
+ id: c0
+ color: "blue"
+ cx: 1000
+ cy: 600
+ }
+ ControlPoint {
+ id: p1
+ cx: 600
+ cy: 1000
+ }
+ ControlPoint {
+ id: c1
+ color: "blue"
+ cx: 200
+ cy: 1200
+ }
+ ControlPoint {
+ id: p2
+ cx: 200
+ cy: 600
+ }
+ ControlPoint {
+ id: c2
+ color: "blue"
+ cx: 200
+ cy: 200
+ }
+
+ ControlPoint {
+ id: p3
+ cx: 1000
+ cy: 200
+ }
+ ControlPoint {
+ id: c3
+ color: "blue"
+ cx: 1400
+ cy: 600
+ }
+ ControlPoint {
+ id: p4
+ cx: 1000
+ cy: 1000
+ }
+ ControlPoint {
+ id: c4
+ color: "blue"
+ cx: 600
+ cy: 1200
+ }
+ ControlPoint {
+ id: p5
+ cx: 600
+ cy: 600
+ }
+ ControlPoint {
+ id: c5
+ color: "blue"
+ cx: 200
+ cy: -200
+ }
+
+
+ Text {
+ anchors.centerIn: p0
+ text: "p0"
+ }
+ Text {
+ anchors.centerIn: p1
+ text: "p1"
+ }
+ Text {
+ anchors.centerIn: p2
+ text: "p2"
+ }
+ Text {
+ anchors.centerIn: p3
+ text: "p3"
+ }
+ Text {
+ anchors.centerIn: p4
+ text: "p4"
+ }
+ Text {
+ anchors.centerIn: p5
+ text: "p5"
+ }
+ Text {
+ anchors.centerIn: c0
+ text: "c0"
+ }
+ Text {
+ anchors.centerIn: c1
+ text: "c1"
+ }
+ Text {
+ anchors.centerIn: c2
+ text: "c2"
+ }
+ Text {
+ anchors.centerIn: c3
+ text: "c3"
+ }
+ Text {
+ anchors.centerIn: c4
+ text: "c4"
+ }
+ Text {
+ anchors.centerIn: c5
+ text: "c5"
+ }
+}
diff --git a/tests/manual/painterpathquickshape/main.qml b/tests/manual/painterpathquickshape/main.qml
index 36dae42639..9a5efa4ec8 100644
--- a/tests/manual/painterpathquickshape/main.qml
+++ b/tests/manual/painterpathquickshape/main.qml
@@ -40,6 +40,14 @@ Window {
source: "Squircle.qml"
}
ListElement {
+ text: "Intersect"
+ source: "Intersect.qml"
+ }
+ ListElement {
+ text: "Intersect2"
+ source: "Intersect2.qml"
+ }
+ ListElement {
text: "CubicShape"
source: "CubicShape.qml"
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-07 07:13:59 +0000