diff options
| -rw-r--r-- | src/quickshapes/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/quickshapes/qquickshapecurverenderer.cpp | 1369 | ||||
| -rw-r--r-- | src/quickshapes/qquickshapecurverenderer_p.h | 9 | ||||
| -rw-r--r-- | src/quickshapes/qquickshapecurverenderer_p_p.h | 47 | ||||
| -rw-r--r-- | src/quickshapes/qt_delaunay_triangulator.cpp | 1439 | ||||
| -rw-r--r-- | src/quickshapes/qt_quadratic_bezier.cpp | 184 | ||||
| -rw-r--r-- | tests/manual/painterpathquickshape/CMakeLists.txt | 2 | ||||
| -rw-r--r-- | tests/manual/painterpathquickshape/ControlPanel.qml | 69 | ||||
| -rw-r--r-- | tests/manual/painterpathquickshape/ControlPoint.qml | 18 | ||||
| -rw-r--r-- | tests/manual/painterpathquickshape/ControlledShape.qml | 73 | ||||
| -rw-r--r-- | tests/manual/painterpathquickshape/Mussel.qml | 42 | ||||
| -rw-r--r-- | tests/manual/painterpathquickshape/SvgShape.qml | 24 | ||||
| -rw-r--r-- | tests/manual/painterpathquickshape/main.qml | 24 | ||||
| -rw-r--r-- | tests/manual/painterpathquickshape/svgpathloader.cpp | 67 | ||||
| -rw-r--r-- | tests/manual/painterpathquickshape/svgpathloader.h | 7 |
15 files changed, 1530 insertions, 1845 deletions
diff --git a/src/quickshapes/CMakeLists.txt b/src/quickshapes/CMakeLists.txt index 99e5704b39..f5697f974b 100644 --- a/src/quickshapes/CMakeLists.txt +++ b/src/quickshapes/CMakeLists.txt @@ -21,7 +21,6 @@ qt_internal_add_qml_module(QuickShapesPrivate qquickshapegenericrenderer.cpp qquickshapegenericrenderer_p.h qquickshapesglobal.h qquickshapesglobal_p.h qquickshapecurverenderer.cpp qquickshapecurverenderer_p.h qquickshapecurverenderer_p_p.h - qt_delaunay_triangulator.cpp qt_quadratic_bezier.cpp qquickshapesoftwarerenderer.cpp qquickshapesoftwarerenderer_p.h PUBLIC_LIBRARIES diff --git a/src/quickshapes/qquickshapecurverenderer.cpp b/src/quickshapes/qquickshapecurverenderer.cpp index 036a6a01cb..2ab282c6af 100644 --- a/src/quickshapes/qquickshapecurverenderer.cpp +++ b/src/quickshapes/qquickshapecurverenderer.cpp @@ -7,6 +7,7 @@ #include <QtGui/qvector2d.h> #include <QtGui/private/qtriangulator_p.h> +#include <QtGui/private/qtriangulatingstroker_p.h> #include <QtGui/private/qrhi_p.h> #include <QtQuick/qsgmaterial.h> @@ -489,6 +490,18 @@ QVector2D QuadPath::Element::pointAtFraction(float t) const } } +float QuadPath::Element::extent() const +{ + // TBD: cache this value if we start using it a lot + QVector2D min(qMin(sp.x(), ep.x()), qMin(sp.y(), ep.y())); + QVector2D max(qMax(sp.x(), ep.x()), qMax(sp.y(), ep.y())); + if (!isLine()) { + min = QVector2D(qMin(min.x(), cp.x()), qMin(min.y(), cp.y())); + max = QVector2D(qMax(max.x(), cp.x()), qMax(max.y(), cp.y())); + } + return (max - min).length(); +} + // Returns the number of intersections between element and a horizontal line at y. // The t values of max 2 intersection(s) are stored in the fractions array int QuadPath::Element::intersectionsAtY(float y, float *fractions) const @@ -620,7 +633,8 @@ QuadPath::Element::CurvatureFlags QuadPath::coordinateOrderOfElement(const QuadP QVector2D midPoint = element.midPoint(); // At the midpoint, the tangent of a quad is parallel to the baseline QVector2D normal = QVector2D(-baseLine.y(), baseLine.x()).normalized(); - QVector2D justRightOfMid = midPoint + normal * QQUICKSHAPECURVERENDERER_CONVEX_CHECK_ERROR_MARGIN; + float delta = qMin(element.extent() / 100, QQUICKSHAPECURVERENDERER_CONVEX_CHECK_ERROR_MARGIN); + QVector2D justRightOfMid = midPoint + (normal * delta); bool pathContainsPoint = contains(justRightOfMid); return pathContainsPoint ? Element::FillOnRight : Element::CurvatureFlags(0); } @@ -640,6 +654,7 @@ QuadPath QuadPath::fromPainterPath(const QPainterPath &path) res.reserve(path.elementCount()); res.setFillRule(path.fillRule()); + QPolygonF quads; QPointF sp; for (int i = 0; i < path.elementCount(); ++i) { QPainterPath::Element element = path.elementAt(i); @@ -658,9 +673,9 @@ QuadPath QuadPath::fromPainterPath(const QPainterPath &path) ep = path.elementAt(++i); QBezier b = QBezier::fromPoints(sp, cp1, cp2, ep); #ifndef USE_TOQUADRATICS_IN_QBEZIER - const QPolygonF quads = qt_toQuadratics(b); + qt_toQuadratics(b, &quads); #else - const QPolygonF quads = b.toQuadratics(); + quads = b.toQuadratics(); #endif for (int i = 1; i < quads.size(); i += 2) { QVector2D cp(quads[i]); @@ -812,6 +827,22 @@ QuadPath QuadPath::subPathsClosed() const endElement.m_isSubpathEnd = true; endElement.ep = m_elements[subStart].sp; } + + // ### Workaround for triangulator issue: Avoid 3-element paths + if (res.elementCount() == 3) { + res.splitElementAt(2); + res = res.flattened(); + Q_ASSERT(res.elementCount() == 4); + } + + return res; +} + +QuadPath QuadPath::flattened() const +{ + QuadPath res; + res.reserve(elementCountRecursive()); + iterateElements([&](const QuadPath::Element &element) { res.m_elements.append(element); }); return res; } @@ -831,7 +862,7 @@ void QuadPath::splitElementAt(qsizetype index) quad1.m_isSubpathStart = parent.m_isSubpathStart; quad1.m_isSubpathEnd = false; quad1.m_curvatureFlags = parent.m_curvatureFlags; - quad1.m_isLine = parent.m_isLine || isPointNearLine(quad1.cp, quad1.sp, quad1.ep); + quad1.m_isLine = parent.m_isLine; //### || isPointNearLine(quad1.cp, quad1.sp, quad1.ep); Element &quad2 = m_childElements[newChildIndex + 1]; quad2.sp = mp; @@ -840,7 +871,7 @@ void QuadPath::splitElementAt(qsizetype index) quad2.m_isSubpathStart = false; quad2.m_isSubpathEnd = parent.m_isSubpathEnd; quad2.m_curvatureFlags = parent.m_curvatureFlags; - quad2.m_isLine = parent.m_isLine || isPointNearLine(quad2.cp, quad2.sp, quad2.ep); + quad2.m_isLine = parent.m_isLine; //### || isPointNearLine(quad2.cp, quad2.sp, quad2.ep); #ifndef QT_NO_DEBUG if (qFuzzyCompare(quad1.sp, quad1.ep) || qFuzzyCompare(quad2.sp, quad2.ep)) @@ -1040,12 +1071,13 @@ void QQuickShapeCurveRenderer::updateNode() return; static const int codePath = qEnvironmentVariableIntValue("QT_QUICKSHAPES_ALTERNATIVE_CODE_PATH"); static const int overlapSolving = !qEnvironmentVariableIntValue("QT_QUICKSHAPES_DISABLE_OVERLAP_SOLVER"); + static bool newStrokeShader = qEnvironmentVariableIntValue("QT_QUICKSHAPES_EXPERIMENTAL_STROKER"); auto addNodes = [&](const PathData &pathData, NodeList *debugNodes) { - if (codePath == 42) - return addPathNodesDelaunayTest(pathData, debugNodes); - else + if (codePath == 1) return addPathNodesBasic(pathData, debugNodes); + else + return addPathNodesLineShader(pathData, debugNodes); }; for (PathData &pathData : m_paths) { @@ -1054,14 +1086,20 @@ void QQuickShapeCurveRenderer::updateNode() deleteAndClear(&pathData.fillNodes); deleteAndClear(&pathData.debugNodes); + static bool useTriangulatingStroker = !qEnvironmentVariableIntValue("QT_QUICKSHAPES_PAINTERPATH_STROKER"); bool createStrokePath = pathData.isStrokeVisible() && !pathData.useFragmentShaderStroker(); static bool simplifyPath = qEnvironmentVariableIntValue("QT_QUICKSHAPES_SIMPLIFY_PATHS") != 0; pathData.path = simplifyPath ? QuadPath::fromPainterPath(pathData.originalPath.simplified()) : QuadPath::fromPainterPath(pathData.originalPath); pathData.path.setFillRule(pathData.fillRule); - if (createStrokePath) + bool solidStroke = pathData.pen.style() == Qt::SolidLine && pathData.pen.isSolid(); + if (newStrokeShader && solidStroke) { + pathData.qPath = pathData.path; + pathData.qPath.addCurvatureData(); // ### Can we unify with fill below? + } else if (createStrokePath) { pathData.fillPath = pathData.path.toPainterPath(); // Without subpath closing etc. + } if (pathData.isFillVisible()) { pathData.path = pathData.path.subPathsClosed(); @@ -1072,27 +1110,33 @@ void QQuickShapeCurveRenderer::updateNode() } if (createStrokePath) { - QPainterPathStroker stroker(pathData.pen); - QPainterPath strokePath = stroker.createStroke(pathData.fillPath); - - // Solid strokes are sometimes created with self-overlaps in the joins, - // causing the overlap detection to freak out. So while this is expensive - // we have to make sure the overlaps are removed first. - static bool simplifyStroke = qEnvironmentVariableIntValue("QT_QUICKSHAPES_DISABLE_SIMPLIFY_STROKE") == 0; - if (pathData.pen.isSolid() && simplifyStroke) - strokePath = strokePath.simplified(); - QuadPath strokeQuadPath = QuadPath::fromPainterPath(strokePath); - strokeQuadPath.addCurvatureData(); - strokePath = strokeQuadPath.toPainterPath(); - if (overlapSolving) - solveOverlaps(strokeQuadPath); - - PathData strokeData = pathData; - strokeData.path = strokeQuadPath; - strokeData.fillPath = strokePath; - strokeData.gradientType = NoGradient; - strokeData.fillColor = pathData.pen.color(); - pathData.strokeNodes = addNodes(strokeData, &pathData.debugNodes); + if (newStrokeShader && solidStroke) { + pathData.strokeNodes = addNodesStrokeShader(pathData, &pathData.debugNodes); + } else if (useTriangulatingStroker && solidStroke) { + pathData.strokeNodes = addStrokeNodes(pathData, &pathData.debugNodes); + } else { + QPainterPathStroker stroker(pathData.pen); + QPainterPath strokePath = stroker.createStroke(pathData.fillPath); + + // Solid strokes are sometimes created with self-overlaps in the joins, + // causing the overlap detection to freak out. So while this is expensive + // we have to make sure the overlaps are removed first. + static bool simplifyStroke = qEnvironmentVariableIntValue("QT_QUICKSHAPES_DISABLE_SIMPLIFY_STROKE") == 0; + if (pathData.pen.style() == Qt::SolidLine && simplifyStroke) + strokePath = strokePath.simplified(); + QuadPath strokeQuadPath = QuadPath::fromPainterPath(strokePath); + strokeQuadPath.addCurvatureData(); + strokePath = strokeQuadPath.toPainterPath(); + if (overlapSolving) + solveOverlaps(strokeQuadPath); + + PathData strokeData = pathData; + strokeData.path = strokeQuadPath; + strokeData.fillPath = strokePath; + strokeData.gradientType = NoGradient; + strokeData.fillColor = pathData.pen.color(); + pathData.strokeNodes = addNodes(strokeData, &pathData.debugNodes); + } } } else if (pathData.m_dirty & UniformsDirty) { for (auto &pathNode : std::as_const(pathData.fillNodes)) @@ -1100,7 +1144,10 @@ void QQuickShapeCurveRenderer::updateNode() if (pathData.pen.style() != Qt::NoPen && pathData.pen.color().alpha() > 0) { for (auto &strokeNode : std::as_const(pathData.strokeNodes)) - static_cast<QQuickShapeLoopBlinnNode *>(strokeNode)->color = pathData.pen.color(); + if (newStrokeShader) // #### Remove this when we have a dedicated stroke shader + static_cast<QQuickShapeLoopBlinnNode *>(strokeNode)->strokeColor = pathData.pen.color(); + else + static_cast<QQuickShapeLoopBlinnNode *>(strokeNode)->color = pathData.pen.color(); } } pathData.m_dirty &= ~(GeometryDirty | UniformsDirty); @@ -1320,34 +1367,562 @@ QSGGeometryNode *QQuickShapeCurveRenderer::addLoopBlinnNodes(const QTriangleSet return node; } -static bool testTriangulation(const QList<QtPathVertex> &vertices, const QList<QtPathEdge> &edges, const QList<QtPathTriangle> &triangles) +// Input coordinate space is pre-mapped so that (0, 0) maps to [0, 0] in uv space. +// v1 maps to [1,0], v2 maps to [0,1]. p is the point to be mapped to uv in this space (i.e. vector from p0) +static inline QVector2D uvForPoint(QVector2D v1, QVector2D v2, QVector2D p) +{ + double divisor = v1.x() * v2.y() - v2.x() * v1.y(); + + float u = (p.x() * v2.y() - p.y() * v2.x()) / divisor; + float v = (p.y() * v1.x() - p.x() * v1.y()) / divisor; + + return {u, v}; +} + +// Find uv coordinates for the point p, for a quadratic curve from p0 to p2 with control point p1 +// also works for a line from p0 to p2, where p1 is on the inside of the path relative to the line +static inline QVector2D curveUv(QVector2D p0, QVector2D p1, QVector2D p2, QVector2D p) +{ + QVector2D v1 = 2 * (p1 - p0); + QVector2D v2 = p2 - v1 - p0; + return uvForPoint(v1, v2, p - p0); +} + +QVector3D QuadPath::Element::uvForPoint(QVector2D p) const +{ + auto uv = curveUv(sp, cp, ep, p); + if (m_isLine) + return { uv.x(), uv.y(), 0.0f }; + else + return { uv.x(), uv.y(), (m_curvatureFlags & Convex) ? -1.0f : 1.0f }; +} + +static inline QVector2D calcNormalVector(QVector2D a, QVector2D b) +{ + auto v = b - a; + return {v.y(), -v.x()}; +} + +// The sign of the return value indicates which side of the line defined by a and n the point p falls +static inline float testSideOfLineByNormal(QVector2D a, QVector2D n, QVector2D p) +{ + float dot = QVector2D::dotProduct(p - a, n); + return dot; +}; + +template<typename Func> +void iteratePath(const QuadPath &path, int index, Func &&lambda) { - // Verify that all our edges are part of a triangle: - bool ok = true; - auto edgeMatch = [](const QtPathEdge &edge, quint32 v1Index, quint32 v2Index) -> bool { - return (edge.startIndex == v1Index && edge.endIndex == v2Index) - || (edge.startIndex == v2Index && edge.endIndex == v1Index); + const auto &element = path.elementAt(index); + if (element.childCount() == 0) { + lambda(element, index); + } else { + for (int i = 0; i < element.childCount(); ++i) + iteratePath(path, element.indexOfChild(i), lambda); + } +} +QVector<QSGGeometryNode *> QQuickShapeCurveRenderer::addPathNodesLineShader(const PathData &pathData, NodeList *debugNodes) +{ + //qDebug() << "========= STARTING ===========" << pathData.path; + + + QVector<QSGGeometryNode *> ret; + const QColor &color = pathData.fillColor; + QPainterPath internalHull; + internalHull.setFillRule(pathData.path.fillRule()); + + + QVector<QQuickShapeLoopBlinnNode::LoopBlinnVertex> vertexBuffer; + QVector<quint32> indices; + bool visualizeDebug = debugVisualization() & DebugCurves; + const float dbg = visualizeDebug ? 0.5f : 0.0f; + QVector<QQuickShapeWireFrameNode::WireFrameVertex> wfVertices; + + QHash<QPair<float, float>, int> linePointHash; + QHash<QPair<float, float>, int> concaveControlPointHash; + QHash<QPair<float, float>, int> convexPointHash; + + + auto toRoundedPair = [](const QPointF &p) -> QPair<float, float> { + return qMakePair(qRound(p.x() * 32.0f) / 32.0f, qRound(p.y() * 32.0f) / 32.0f); + }; + + auto toRoundedVec2D = [](const QPointF &p) -> QVector2D { + return { qRound(p.x() * 32.0f) / 32.0f, qRound(p.y() * 32.0f) / 32.0f }; + }; + + auto roundVec2D = [](const QVector2D &p) -> QVector2D { + return { qRound(p.x() * 32.0f) / 32.0f, qRound(p.y() * 32.0f) / 32.0f }; + }; + + auto addVertexDataForPoint = [&vertexBuffer, dbg](const QuadPath::Element &element, const QVector2D &p) { + auto uv = element.uvForPoint(p); + + float r = 0.0f, g = 0.0f, b = 0.0f; + if (element.isLine()) { + g = b = 1.0f; + } else if (element.isConvex()) { + r = 1.0; + } else { // concave + b = 1.0; + } + + vertexBuffer.append({p.x(), p.y(), uv.x(), uv.y(), uv.z(), r, g, b, dbg}); + }; + + auto addCurveTriangle = [&](const QuadPath::Element &element, const QVector2D &sp, const QVector2D &ep, const QVector2D &cp){ + int currentVertex = vertexBuffer.count(); + addVertexDataForPoint(element, sp); + addVertexDataForPoint(element, cp); + addVertexDataForPoint(element, ep); + indices << currentVertex << currentVertex + 1 << currentVertex + 2; + wfVertices.append({sp.x(), sp.y(), 1.0f, 0.0f, 0.0f}); // 0 + wfVertices.append({cp.x(), cp.y(), 0.0f, 1.0f, 0.0f}); // 1 + wfVertices.append({ep.x(), ep.y(), 0.0f, 0.0f, 1.0f}); // 2 + }; + + // Find a point on the other side of the line + auto findPointOtherSide = [](const QVector2D &startPoint, const QVector2D &endPoint, const QVector2D &referencePoint){ + + QVector2D baseLine = endPoint - startPoint; + QVector2D insideVector = referencePoint - startPoint; + //QVector2D midPoint = (endPoint + startPoint) / 2; // ??? Should we use midPoint instead of startPoint?? + QVector2D normal = QVector2D(-baseLine.y(), baseLine.x()); // TODO: limit size of triangle + + bool swap = QVector2D::dotProduct(insideVector, normal) < 0; + + return swap ? startPoint + normal : startPoint - normal; + }; + + auto addLineTriangle = [&](const QuadPath::Element &element, const QVector2D &sp, const QVector2D &ep, const QVector2D &cp){ + int currentVertex = vertexBuffer.count(); + addCurveTriangle(element, sp, ep, cp); + // Add a triangle on the outer side of the line to get some more AA + // The new point replaces cp (currentVertex+1) + QVector2D op = findPointOtherSide(sp, ep, cp); //sp - (cp - ep); + wfVertices.append({op.x(), op.y(), 0.0f, 1.0f, 0.0f}); // replacing cp (1) + auto uv = element.uvForPoint(op); + vertexBuffer.append({op.x(), op.y(), uv.x(), uv.y(), uv.z(), 0.0f, 1.0f, 1.0f, dbg}); + indices << currentVertex << currentVertex + 3 << currentVertex + 2; + }; + + auto addConvexTriangle = [&](const QuadPath::Element &element, const QVector2D &sp, const QVector2D &ep, const QVector2D &cp){ + int currentVertex = vertexBuffer.count(); + addCurveTriangle(element, sp, ep, cp); + // Add two triangles on the outer side to get some more AA + + // First triangle on the line sp-cp, replacing ep (currentVertex+2) + { + QVector2D op = findPointOtherSide(sp, cp, ep); //sp - (ep - cp); + wfVertices.append({op.x(), op.y(), 0.0f, 0.0f, 1.0f}); // replacing ep (2) + auto uv = element.uvForPoint(op); + vertexBuffer.append({op.x(), op.y(), uv.x(), uv.y(), uv.z(), 0.0f, 1.0f, 1.0f, dbg}); + indices << currentVertex << currentVertex + 1 << currentVertex + 3; + } + + // Second triangle on the line ep-cp, replacing sp (currentVertex+0) + { + QVector2D op = findPointOtherSide(ep, cp, sp); //ep - (sp - cp); + wfVertices.append({op.x(), op.y(), 1.0f, 0.0f, 0.0f}); // replacing sp (0) + auto uv = element.uvForPoint(op); + vertexBuffer.append({op.x(), op.y(), uv.x(), uv.y(), uv.z(), 0.0f, 1.0f, 1.0f, dbg}); + indices << currentVertex + 4 << currentVertex + 1 << currentVertex + 2; + } + + }; + + + // This is guaranteed to be in safe space (the curve will never enter the triangle) + // ### This is the opposite of what we really want: it's going to be extremely thin when we need it, + // and big when it's completely pointless, but a thicker triangle could be going into negative space + auto oppositePoint = [](const QVector2D &startPoint, const QVector2D &endPoint, const QVector2D &controlPoint) -> QVector2D { + return startPoint + 2 * (endPoint - controlPoint); + }; + + // Identical to addLineTriangle, except for how op is calculated + auto addConcaveTriangle = [&](const QuadPath::Element &element, const QVector2D &sp, const QVector2D &ep, const QVector2D &cp){ + int currentVertex = vertexBuffer.count(); + addCurveTriangle(element, sp, ep, cp); + // Add an outer triangle to give extra AA for very flat curves + QVector2D op = oppositePoint(sp, ep, cp); + // The new point replaces cp (currentVertex+1) + wfVertices.append({op.x(), op.y(), 0.0f, 1.0f, 0.0f}); // replacing cp (1) + auto uv = element.uvForPoint(op); + vertexBuffer.append({op.x(), op.y(), uv.x(), uv.y(), uv.z(), 0.0f, 1.0f, 1.0f, dbg}); + indices << currentVertex << currentVertex + 3 << currentVertex + 2; + }; + + auto addFillTriangle = [&](const QVector2D &p1, const QVector2D &p2, const QVector2D &p3){ + int currentVertex = vertexBuffer.count(); + constexpr QVector3D uv(0.0, 1.0, -1.0); + vertexBuffer.append({p1.x(), p1.y(), uv.x(), uv.y(), uv.z(), 0.0f, 1.0f, 0.0f, dbg}); + vertexBuffer.append({p2.x(), p2.y(), uv.x(), uv.y(), uv.z(), 0.0f, 1.0f, 0.0f, dbg}); + vertexBuffer.append({p3.x(), p3.y(), uv.x(), uv.y(), uv.z(), 0.0f, 1.0f, 0.0f, dbg}); + indices << currentVertex << currentVertex + 1 << currentVertex + 2; + wfVertices.append({p1.x(), p1.y(), 1.0f, 0.0f, 0.0f}); // 0 + wfVertices.append({p3.x(), p3.y(), 0.0f, 1.0f, 0.0f}); // 1 + wfVertices.append({p2.x(), p2.y(), 0.0f, 0.0f, 1.0f}); // 2 + }; + + + + for (int i = 0; i < pathData.path.elementCount(); ++i) + iteratePath(pathData.path, i, [&](const QuadPath::Element &element, int index){ + QPointF sp(element.startPoint().toPointF()); //### to much conversion to and from pointF + QPointF cp(element.controlPoint().toPointF()); + QPointF ep(element.endPoint().toPointF()); + if (element.isSubpathStart()) + internalHull.moveTo(sp); + if (element.isLine()) { + internalHull.lineTo(ep); + //lineSegments.append(QLineF(sp, ep)); + linePointHash.insert(toRoundedPair(sp), index); + } else { + if (element.isConvex()) { + internalHull.lineTo(ep); + addConvexTriangle(element, toRoundedVec2D(sp), toRoundedVec2D(ep), toRoundedVec2D(cp)); + convexPointHash.insert(toRoundedPair(sp), index); + } else { + internalHull.lineTo(cp); + internalHull.lineTo(ep); + addConcaveTriangle(element, toRoundedVec2D(sp), toRoundedVec2D(ep), toRoundedVec2D(cp)); + concaveControlPointHash.insert(toRoundedPair(cp), index); + } + } + }); + //qDebug() << "Curves: i" << indices.size() << "v" << vertexBuffer.size() << "w" << wfVertices.size(); + + auto makeHashable = [](const QVector2D &p) -> QPair<float, float> { + return qMakePair(qRound(p.x() * 32.0f) / 32.0f, qRound(p.y() * 32.0f) / 32.0f); + }; + // Points in p are already rounded do 1/32 + // Returns false if the triangle needs to be split. Adds the triangle to the graphics buffers and returns true otherwise. + + // TODO: Does not handle ambiguous vertices that are on multiple unrelated lines/curves + + auto onSameSideOfLine = [](const QVector2D &p1, const QVector2D &p2, const QVector2D &linePoint, const QVector2D &lineNormal) { + float side1 = testSideOfLineByNormal(linePoint, lineNormal, p1); + float side2 = testSideOfLineByNormal(linePoint, lineNormal, p2); + return side1 * side2 >= 0; + }; + + auto pointInSafeSpace = [&](const QVector2D &p, const QuadPath::Element &element) -> bool { + const QVector2D a = element.startPoint(); + const QVector2D b = element.endPoint(); + const QVector2D c = element.controlPoint(); + // There are "safe" areas of the curve also across the baseline: the curve can never cross: + // line1: the line through A and B' + // line2: the line through B and A' + // Where A' = A "mirrored" through C and B' = B "mirrored" through C + const QVector2D n1 = calcNormalVector(a, c + (c - b)); + const QVector2D n2 = calcNormalVector(b, c + (c - a)); + bool safeSideOf1 = onSameSideOfLine(p, c, a, n1); + bool safeSideOf2 = onSameSideOfLine(p, c, b, n2); + return safeSideOf1 && safeSideOf2; + }; + + auto handleTriangle = [&](const QVector2D (&p)[3]) -> bool { + int lineElementIndex = -1; + int concaveElementIndex = -1; + int convexElementIndex = -1; + + bool foundElement = false; + int si = -1; + int ei = -1; + for (int i = 0; i < 3; ++i) { + if (auto found = linePointHash.constFind(makeHashable(p[i])); found != linePointHash.constEnd()) { + // check if this triangle is on a line, i.e. if one point is the sp and another is the ep of the same path element + const auto &element = pathData.path.elementAt(*found); + //qDebug() << " " << element; + for (int j = 0; j < 3; ++j) { + if (i != j && roundVec2D(element.endPoint()) == p[j]) { + if (foundElement) + return false; // More than one edge on path: must split + lineElementIndex = *found; + si = i; + ei = j; + //qDebug() << "FOUND IT!!!!" << p[i] << p[j] << lineElementIndex; + foundElement = true; + } + } + } else if (auto found = concaveControlPointHash.constFind(makeHashable(p[i])); found != concaveControlPointHash.constEnd()) { + // check if this triangle is on the tangent line of a concave curve, + // i.e if one point is the cp, and the other is sp or ep + // TODO: clean up duplicated code (almost the same as the lineElement path above) + const auto &element = pathData.path.elementAt(*found); + for (int j = 0; j < 3; ++j) { + if (i == j) + continue; + if (roundVec2D(element.startPoint()) == p[j] || roundVec2D(element.endPoint()) == p[j]) { + if (foundElement) + return false; // More than one edge on path: must split + concaveElementIndex = *found; + // The tangent line is p[i] - p[j] + si = i; // we may not need these + ei = j; + //qDebug() << "FOUND IT!!!!" << p[i] << p[j] << lineElementIndex; + foundElement = true; + } + } + } else if (auto found = convexPointHash.constFind(makeHashable(p[i])); found != convexPointHash.constEnd()) { + // check if this triangle is on a curve, i.e. if one point is the sp and another is the ep of the same path element + const auto &element = pathData.path.elementAt(*found); + for (int j = 0; j < 3; ++j) { + if (i != j && roundVec2D(element.endPoint()) == p[j]) { + if (foundElement) + return false; // More than one edge on path: must split + convexElementIndex = *found; + si = i; + ei = j; + //qDebug() << "FOUND IT!!!!" << p[i] << p[j] << convexElementIndex; + foundElement = true; + } + } + } + } + if (lineElementIndex != -1) { + int ci = (6 - si - ei) % 3; // 1+2+3 is 6, so missing number is 6-n1-n2 + addLineTriangle(pathData.path.elementAt(lineElementIndex), p[si], p[ei], p[ci]); + } else if (concaveElementIndex != -1) { + addCurveTriangle(pathData.path.elementAt(concaveElementIndex), p[0], p[1], p[2]); + } else if (convexElementIndex != -1) { + int oi = (6 - si - ei) % 3; + const auto &otherPoint = p[oi]; + const auto &element = pathData.path.elementAt(convexElementIndex); + // We have to test whether the triangle can cross the line TODO: use the toplevel element's safe space + bool safeSpace = pointInSafeSpace(otherPoint, element); + if (safeSpace) { + addCurveTriangle(element, p[0], p[1], p[2]); + } else { + //qDebug() << "Point" << otherPoint << "element" << element << "safe" << safeSpace; + // Find a point inside the triangle that's also in the safe space + QVector2D newPoint = (p[0] + p[1] + p[2]) / 3; + // We should calculate the point directly, but just do a lazy implementation for now: + for (int i = 0; i < 7; ++i) { + safeSpace = pointInSafeSpace(newPoint, element); + //qDebug() << "UNSAFE space round" << i << "checking" << newPoint << safeSpace; + if (safeSpace) + break; + newPoint = (p[si] + p[ei] + newPoint) / 3; + } + if (safeSpace) { + // Split triangle. We know the original triangle is only on one path element, so the other triangles are both fill. + // Curve triangle is (sp, ep, np) + addCurveTriangle(element, p[si], p[ei], newPoint); + // The other two are (sp, op, np) and (ep, op, np) + addFillTriangle(p[si], p[oi], newPoint); + addFillTriangle(p[ei], p[oi], newPoint); + } else { + // fallback to fill if we can't find a point in safe space + addFillTriangle(p[0], p[1], p[2]); + } + } + + } else { + addFillTriangle(p[0], p[1], p[2]); + } + return true; }; + QTriangleSet triangles = qTriangulate(internalHull); + + const quint32 *idxTable = static_cast<const quint32 *>(triangles.indices.data()); + for (int triangle = 0; triangle < triangles.indices.size() / 3; ++triangle) { + const quint32 *idx = &idxTable[triangle * 3]; - for (const auto &edge : edges) { - // Just do it the simplest way possible, and O(n^2) be damned - bool found = false; - for (const auto &triangle : triangles) { - if (edgeMatch(edge, triangle.v1Index, triangle.v2Index) - || edgeMatch(edge, triangle.v2Index, triangle.v3Index) - || edgeMatch(edge, triangle.v3Index, triangle.v1Index)) { - found = true; - break; + QVector2D p[3]; + for (int i = 0; i < 3; ++i) { + p[i] = toRoundedVec2D(QPointF(triangles.vertices.at(idx[i]*2), triangles.vertices.at(idx[i]*2 + 1))); + } + bool needsSplit = !handleTriangle(p); + if (needsSplit) { + QVector2D c = (p[0] + p[1] + p[2]) / 3; + //qDebug() << "Split!!! New point" << c; + for (int i = 0; i < 3; ++i) { + qSwap(c, p[i]); + //qDebug() << "Adding split triangle" << p[0] << p[1] << p[2]; + handleTriangle(p); + qSwap(c, p[i]); } } - if (!found) { - qDebug() << "*** MISSING LINK ***" << edge.startIndex << edge.endIndex - << vertices[edge.startIndex].point << vertices[edge.endIndex].point; - ok = false; + } + + if (indices.size() > 0) { + auto *node = new QQuickShapeLoopBlinnNode(pathData.gradientType); + node->color = color; + node->fillGradient = pathData.gradient; + + if (pathData.useFragmentShaderStroker() && pathData.isStrokeVisible() && pathData.pen.isSolid()) { + node->strokeColor = pathData.pen.color(); + node->strokeWidth = pathData.pen.widthF(); } + + QSGGeometry *g = new QSGGeometry(QQuickShapeLoopBlinnNode::attributes(), + vertexBuffer.size(), indices.size(), QSGGeometry::UnsignedIntType); + node->setGeometry(g); + g->setDrawingMode(QSGGeometry::DrawTriangles); + + //qDebug() << "gvc" << g->vertexCount(); + + memcpy(g->vertexData(), + vertexBuffer.data(), + g->vertexCount() * g->sizeOfVertex()); + memcpy(g->indexData(), + indices.data(), + indices.size() * g->sizeOfIndex()); + + m_rootNode->appendChildNode(node); + ret.append(node); + } + const bool wireFrame = debugVisualization() & DebugWireframe; + if (wireFrame) { + QQuickShapeWireFrameNode *wfNode = new QQuickShapeWireFrameNode; + + //QVarLengthArray<quint32> indices; + + QSGGeometry *wfg = new QSGGeometry(QQuickShapeWireFrameNode::attributes(), + wfVertices.size(), + indices.size(), + QSGGeometry::UnsignedIntType); + wfNode->setGeometry(wfg); + + wfg->setDrawingMode(QSGGeometry::DrawTriangles); + memcpy(wfg->indexData(), + indices.data(), + indices.size() * wfg->sizeOfIndex()); + memcpy(wfg->vertexData(), + wfVertices.data(), + wfg->vertexCount() * wfg->sizeOfVertex()); + + m_rootNode->appendChildNode(wfNode); + debugNodes->append(wfNode); } - return ok; + + return ret; +} + +QVector<QSGGeometryNode *> QQuickShapeCurveRenderer::addStrokeNodes(const PathData &pathData, NodeList *debugNodes) +{ + QVector<QSGGeometryNode *> ret; + const QColor &color = pathData.pen.color(); + + QVector<QQuickShapeLoopBlinnNode::LoopBlinnVertex> vertexBuffer; + QVector<quint32> indices; + bool visualizeDebug = debugVisualization() & DebugCurves; + const float dbg = visualizeDebug ? 0.5f : 0.0f; + QVector<QQuickShapeWireFrameNode::WireFrameVertex> wfVertices; + + QTriangulatingStroker stroker; + const QVectorPath &vp = qtVectorPathForPath(pathData.fillPath); + QPen pen = pathData.pen; + stroker.process(vp, pen, {}, {}); + + auto findPointOtherSide = [](const QVector2D &startPoint, const QVector2D &endPoint, const QVector2D &referencePoint){ + + QVector2D baseLine = endPoint - startPoint; + QVector2D insideVector = referencePoint - startPoint; + //QVector2D midPoint = (endPoint + startPoint) / 2; // ??? Should we use midPoint instead of startPoint?? + QVector2D normal = QVector2D(-baseLine.y(), baseLine.x()); // TODO: limit size of triangle + + bool swap = QVector2D::dotProduct(insideVector, normal) < 0; + + return swap ? startPoint + normal : startPoint - normal; + }; + + static bool disableExtraTriangles = qEnvironmentVariableIntValue("QT_QUICKSHAPES_WIP_DISABLE_EXTRA_STROKE_TRIANGLES"); + + auto addStrokeTriangle = [&](const QVector2D &p1, const QVector2D &p2, const QVector2D &p3, bool){ + int currentVertex = vertexBuffer.count(); + //constexpr QVector3D uv(0.0, 1.0, -1.0); + + + if (p1 == p2 || p2 == p3) { + //qDebug() << "Skipping triangle" << p1 << p2 << p3; + return; + } + + + vertexBuffer.append({p1.x(), p1.y(), 0.0f, 0.0f, 0.0f, 1.0f, 0.0f, 0.0f, dbg}); // edge start + vertexBuffer.append({p2.x(), p2.y(), 1.0f, 0.0f, 0.0f, 0.0f, 1.0f, 0.0f, dbg}); // inner + vertexBuffer.append({p3.x(), p3.y(), 1.0f, 1.0f, 0.0f, 0.0f, 0.0f, 1.0f, dbg}); // edge end + indices << currentVertex << currentVertex + 1 << currentVertex + 2; + wfVertices.append({p1.x(), p1.y(), 1.0f, 0.0f, 0.0f}); // 0 + wfVertices.append({p2.x(), p2.y(), 0.0f, 0.1f, 0.0f}); // 1 + wfVertices.append({p3.x(), p3.y(), 0.0f, 0.0f, 1.0f}); // 2 + + if (!disableExtraTriangles) { + // Add a triangle on the outer side of the line to get some more AA + // The new point replaces p2 (currentVertex+1) + QVector2D op = findPointOtherSide(p1, p3, p2); + wfVertices.append({op.x(), op.y(), 0.0f, 1.0f, 0.0f}); // replacing p2 + vertexBuffer.append({op.x(), op.y(), 0.0f, 1.0f, 0.0f, 0.0f, 1.0f, 1.0f, dbg}); + indices << currentVertex << currentVertex + 3 << currentVertex + 2; + } + }; + + const int vertCount = stroker.vertexCount() / 2; + const float *verts = stroker.vertices(); + for (int i = 0; i < vertCount - 2; ++i) { + QVector2D p[3]; + for (int j = 0; j < 3; ++j) { + p[j] = QVector2D(verts[(i+j)*2], verts[(i+j)*2 + 1]); + } + bool isOdd = i % 2; + addStrokeTriangle(p[0], p[1], p[2], isOdd); + } + + if (indices.size() > 0) { + auto *node = new QQuickShapeLoopBlinnNode(pathData.gradientType); + node->color = color; + node->fillGradient = pathData.gradient; + + if (pathData.useFragmentShaderStroker() && pathData.isStrokeVisible() && pathData.pen.isSolid()) { + node->strokeColor = pathData.pen.color(); + node->strokeWidth = pathData.pen.widthF(); + } + + QSGGeometry *g = new QSGGeometry(QQuickShapeLoopBlinnNode::attributes(), + vertexBuffer.size(), indices.size(), QSGGeometry::UnsignedIntType); + node->setGeometry(g); + g->setDrawingMode(QSGGeometry::DrawTriangles); + + //qDebug() << "gvc" << g->vertexCount(); + + memcpy(g->vertexData(), + vertexBuffer.data(), + g->vertexCount() * g->sizeOfVertex()); + memcpy(g->indexData(), + indices.data(), + indices.size() * g->sizeOfIndex()); + + m_rootNode->appendChildNode(node); + ret.append(node); + } + const bool wireFrame = debugVisualization() & DebugWireframe; + if (wireFrame) { + QQuickShapeWireFrameNode *wfNode = new QQuickShapeWireFrameNode; + + //QVarLengthArray<quint32> indices; + + QSGGeometry *wfg = new QSGGeometry(QQuickShapeWireFrameNode::attributes(), + wfVertices.size(), + indices.size(), + QSGGeometry::UnsignedIntType); + wfNode->setGeometry(wfg); + + wfg->setDrawingMode(QSGGeometry::DrawTriangles); + memcpy(wfg->indexData(), + indices.data(), + indices.size() * wfg->sizeOfIndex()); + memcpy(wfg->vertexData(), + wfVertices.data(), + wfg->vertexCount() * wfg->sizeOfVertex()); + + m_rootNode->appendChildNode(wfNode); + debugNodes->append(wfNode); + } + + return ret; } void QQuickShapeCurveRenderer::setRootNode(QQuickShapeCurveNode *node) @@ -1377,6 +1952,8 @@ void QQuickShapeCurveRenderer::deleteAndClear(NodeList *nodeList) nodeList->clear(); } +namespace { + /* Clever triangle overlap algorithm. Stack Overflow says: @@ -1388,11 +1965,11 @@ void QQuickShapeCurveRenderer::deleteAndClear(NodeList *nodeList) */ // The sign of the determinant tells the winding order -static inline double determinant(QVector2D &p1, QVector2D &p2, QVector2D &p3) +static inline double determinant(const QVector2D &p1, const QVector2D &p2, const QVector2D &p3) { return p1.x() * (p2.y() - p3.y()) - + p2.x() * (p3.y() - p1.y()) - + p3.x() * (p1.y() - p2.y()); + + p2.x() * (p3.y() - p1.y()) + + p3.x() * (p1.y() - p2.y()); } // Fix the triangle so that the determinant is positive @@ -1499,6 +2076,522 @@ static bool isOverlap(const QuadPath &path, qsizetype index, const QVector2D &ve return checkTriangleContains(vertex, elem.startPoint(), elem.controlPoint(), elem.endPoint()); } +struct TriangleData +{ + QVector2D points[3]; + int pathElementIndex; + QVector3D debugColor; + bool specialDebug = false; +}; + +QVector2D normalVector(QVector2D baseLine) +{ + QVector2D normal = QVector2D(-baseLine.y(), baseLine.x()).normalized(); + return normal; +} + +QVector2D normalVector(const QuadPath::Element &element, bool endSide = false) +{ + if (element.isLine()) + return normalVector(element.endPoint() - element.startPoint()); + else if (!endSide) + return normalVector(element.controlPoint() - element.startPoint()); + else + return normalVector(element.endPoint() - element.controlPoint()); +} + +QVector2D angleBisector(const QuadPath::Element &element1, const QuadPath::Element &element2, float strokeMargin) +{ + Q_ASSERT(element1.endPoint() == element2.startPoint()); + + + const auto p1 = element1.isLine() ? element1.startPoint() : element1.controlPoint(); + const auto p2 = element1.endPoint(); + const auto p3 = element2.isLine() ? element2.endPoint() : element2.controlPoint(); + + const auto v1 = (p1 - p2).normalized(); + const auto v2 = (p3 - p2).normalized(); + const auto bisector = v1 + v2; + + if (qFuzzyIsNull(bisector.x()) && qFuzzyIsNull(bisector.y())) { + // v1 and v2 are almost parallel, and pointing in opposite directions + // angle bisector formula will give an almost null vector: use normal of bisector of normals instead + QVector2D n1(-v1.y(), v1.x()); + QVector2D n2(-v2.y(), v2.x()); + return (n2 - n1).normalized() * strokeMargin; + } else { + // We need to increase the length, so that the result covers the whole miter + // Using the identity sin(x/2) == sqrt((1 - cos(x)) / 2), and the fact that the + // dot product of two unit vectors is the cosine of the angle between them + // The length of the miter is w/sin(x/2) where x is the angle between the two elements + + float cos2x = QVector2D::dotProduct(v1, v2); + cos2x = qMin(1.0f, cos2x); // Allow for float inaccuracy + float sine = sqrt((1.0f - cos2x) / 2); + sine = qMax(sine, 0.1f); // Avoid divide by zero + + return bisector.normalized() * strokeMargin / sine; + // TODO: Make a proper bevel at that point + // ### This is *not* the right place to do a miter limit: The inner join needs to be as long as + // it needs to be, independent of the miter on the other side. (We still need to avoid a divide + // by zero, of course.) + } +} + +// Returns true if p and q are on the same side of the line AB +bool onSameSideOfLine(const QVector2D &a, const QVector2D &b, const QVector2D &p, const QVector2D &q) +{ + auto baseLine = a - b; + QVector2D n(-baseLine.y(), baseLine.x()); + float pSide = testSideOfLineByNormal(a, n, p); + float qSide = testSideOfLineByNormal(a, n, q); + return pSide * qSide >= 0; +} + +// Returns true if the entire curve triangle is on the same side of the line p1-p2 +bool controlPointInsideLine(const QuadPath::Element &element, const QVector2D &p1, const QVector2D &p2) +{ + bool s1 = determinant(p1, p2, element.startPoint()) < 0; + auto s2 = determinant(p1, p2, element.endPoint()) < 0; + auto s3 = determinant(p1, p2, element.controlPoint()) < 0; + // If all determinants have the same sign, all the points are on the same side + return (s1 == s2 && s2 == s3); +} + +inline bool lineIntersects(const QVector2D &v1_, const QVector2D &v2_, + const QVector2D &u1_, const QVector2D &u2_) +{ +#if 1 + QPointF v1 = v1_.toPointF(); + QPointF v2 = v2_.toPointF(); + QPointF u1 = u1_.toPointF(); + QPointF u2 = u2_.toPointF(); + + if ( (v1.x() < u1.x() && v1.x() < u2.x() && v2.x() < u1.x() && v2.x() < u2.x()) + || (v1.x() > u1.x() && v1.x() > u2.x() && v2.x() > u1.x() && v2.x() > u2.x()) + || (v1.y() < u1.y() && v1.y() < u2.y() && v2.y() < u1.y() && v2.y() < u2.y()) + || (v1.y() > u1.y() && v1.y() > u2.y() && v2.y() > u1.y() && v2.y() > u2.y())) { + return false; + } + + // Copied from QLineF::intersects() with some changes to ordering to speed + // up for our use case + const QPointF a = v2 - v1; + const QPointF b = u1 - u2; + const QPointF c = v1 - u1; + + const qreal denominator = a.y() * b.x() - a.x() * b.y(); + if (denominator == 0.0 || !qt_is_finite(denominator)) + return false; + + const qreal reciprocal = 1.0 / denominator; + qreal na = (b.y() * c.x() - b.x() * c.y()) * reciprocal; + if (na < 0.0 || na > 1.0) + return false; + + qreal nb = (a.x() * c.y() - a.y() * c.x()) * reciprocal; + if (nb < 0.0 || nb > 1.0) + return false; + + const QPointF intersectionPoint = v1 + a * na; + return intersectionPoint != v1 && intersectionPoint != v2 && intersectionPoint != u1 && intersectionPoint != u2; + return true; +#else + QLineF v(v1.toPointF(), v2.toPointF()); + QLineF u(u1.toPointF(), u2.toPointF()); + + QPointF intersectionPoint; + if (v.intersects(u, &intersectionPoint) == QLineF::BoundedIntersection) { + return (intersectionPoint != v.p1() && intersectionPoint != v.p2() + && intersectionPoint != u.p1() && intersectionPoint != u.p2()); + } + + return false; +#endif +} + + +static QList<TriangleData> customTriangulator(const QuadPath &path, float margin, bool miterJoin) +{ + QList<TriangleData> ret; + + // TODO: We repeat the same calculations for each side of each join: try to remember the values from the previous + // element. (The difficult part is path closures) + + auto handleElement = [&ret, margin, miterJoin](const QuadPath::Element *prev, const QuadPath::Element *current, const QuadPath::Element *next, const int elementIndex) { + QVector2D p1, p2, p3, p4; + + + auto startNormal = normalVector(*current) * margin; + auto endNormal = normalVector(*current, true) * margin; + auto startBisector = prev ? angleBisector(*prev, *current, margin) : startNormal; + auto endBisector = next ? angleBisector(*current, *next, margin) : endNormal; + + const auto &sp = current->startPoint(); + const auto &ep = current->endPoint(); + + // p1: bisect on the "inside" of the join, p2: normal on the "outside" + // guess which side is which: (TODO: we should be able to know this) + bool bevelPointReversed = false; + + if (prev) { + const auto &prevPoint = prev->isLine() ? prev->startPoint() : prev->controlPoint(); + const auto &lineStart = current->startPoint(); + const auto &lineEnd = current->isLine() ? current->endPoint() : current->controlPoint(); + if (miterJoin) { + p1 = sp + startBisector; + p2 = sp - startBisector; + } else { + p1 = sp - startBisector; + p2 = sp - startNormal; + // p1 should be on the same side as the start point of the previous element + if (!onSameSideOfLine(lineStart, lineEnd, p1, prevPoint)) { + p1 = sp + startBisector; + } + // p2 should be on the opposite side ### TODO: optimize test, reusing intermediates from test above + if (onSameSideOfLine(lineStart, lineEnd, p2, prevPoint)) { + p2 = sp + startNormal; + bevelPointReversed = true; + } + } + } else { + p1 = sp + startNormal; + p2 = sp - startNormal; + } + auto bevelPoint = p2; // This is one corner of the "gap" triangle + + // p3: bisect on the "inside" of the join, p4: normal on the "outside" + // For curves, we use the tangent line of the next element + if (next) { + const auto &lineStart = current->isLine() ? current->startPoint() : current->controlPoint(); + const auto &lineEnd = current->endPoint(); + const auto &nextPoint = next->isLine() ? next->endPoint() : next->controlPoint(); + if (miterJoin) { + p3 = ep + endBisector; + p4 = ep - endBisector; + } else { + p3 = ep - endBisector; + p4 = ep - endNormal; + // p3 should be on the same side of our line as the end point of the next element + if (!onSameSideOfLine(lineStart, lineEnd, p3, nextPoint)) { + p3 = ep + endBisector; + } + // p4 should be on the opposite side ### TODO: optimize test, reusing intermediates from test above + if (onSameSideOfLine(lineStart, lineEnd, p4, nextPoint)) { + p4 = ep + endNormal; + } + } + } else { + p3 = ep + endNormal; + p4 = ep - endNormal; + } + + //bool intersect = lineIntersects(p1, p2, p3, p4); // Check if our quadrilateral is self-intersecting + //### Not enough! It's also wrong if p1-p2 is completely on the wrong side of p3-p4 + //bool ok = onSameSideOfLine(p1, p2, p3, p4) && onSameSideOfLine(p1, p2, p3, current->endPoint()); + //### And that's still not enough, since the line can turn almost 180 degrees + + // New attempt: see if the bisector intersects the normal... + bool notOK = lineIntersects(sp + startNormal, sp - startNormal, ep + endBisector, ep - endBisector) + || lineIntersects(sp + startBisector, sp - startBisector, ep + endNormal, ep - endNormal); + + // TESTING: Avoid the inner bisector extending past the stroke. We need to move the points around, + // but for now, just accept overpainting. Only implemented for BevelJoin + if (notOK && !miterJoin) { + p1 = current->startPoint() + startNormal; + p2 = current->startPoint() - startNormal; + p3 = current->endPoint() + endNormal; + p4 = current->endPoint() - endNormal; + } + + if (current->isLine()) { + // Rearrange so p1, p3 is on the same side of the path, and p2, p4 is on the other side + if (!onSameSideOfLine(current->startPoint(), current->endPoint(), p1, p3)) + qSwap(p3, p4); + } else { + // Rearrange so that p1 and p3 are on the outside of the curve triangle, i.e. p2 and p4 are on the same side + // of the respective tangent line as the path + + + // p1 should be on the outside of sp-cp + if (onSameSideOfLine(current->startPoint(), current->controlPoint(), p1, current->endPoint())) + qSwap(p1, p2); + // p3 should be on the outside of ep-cp + if (onSameSideOfLine(current->endPoint(), current->controlPoint(), p3, current->startPoint())) + qSwap(p3, p4); + } + + + bool special = notOK; + + /* + p + p1 p3 + + sp ep + + p2 p4 + + */ + + //Note: p1-sp-p2 is no longer guaranteed to be on a line, so we need to add extra triangles + + if (current->isLine() || controlPointInsideLine(*current, p1, p3)) { + float r = current->isLine() ? 0.0f : 0.5f; + ret.append({{p1, p2, p3}, elementIndex, {r, 1.0f, 0.0f}, special}); + ret.append({{p2, p3, p4}, elementIndex, {r, 0.0f, 1.0f}, special}); + if (!miterJoin) { // TODO: handle bevel for overlong miter + ret.append({{p1, sp, p2}, elementIndex, {r, 0.5f, 1.0f}, special}); + ret.append({{p3, ep, p4}, elementIndex, {r, 0.5f, 1.0f}, special}); + } + //qDebug() << "adding triangles" << p1 << p2 << p3 << "and" << p2 << p3 << p4; + } else { + + const auto &p = current->controlPoint(); + ret.append({{p1, p2, p}, elementIndex, {1.0f, 0.0f, 0.0f}, special}); + ret.append({{p, p2, p4}, elementIndex, {1.0f, 1.0f, 0.0f}, special}); + ret.append({{p, p3, p4}, elementIndex, {1.0f, 0.0f, 1.0f}, special}); + if (!miterJoin) { // TODO: handle bevel for overlong miter + ret.append({{p1, sp, p2}, elementIndex, {0.5f, 1.0f, 0.0f}, special}); + ret.append({{p3, ep, p4}, elementIndex, {0.5f, 1.0f, 0.0f}, special}); + } + //qDebug() << "adding triangle1" << p1 << p2 << p << "triangle2" << p << p2 << p4 << "triangle3" << p << p3 << p4 ; + + + // qDebug() << "Curve element" << p1 << p2 << p << p3 << p4; + } + + if (prev && !miterJoin) { + // Try to do the bevel triangle: prev bevelpoint - sp - bevelPoint + auto prevNormal = normalVector(*prev, true) * margin; // Do we have normals in different directions??? + auto pbp = bevelPointReversed ? sp + prevNormal : sp - prevNormal; + //qDebug() << "bevel triangle" << pbp << sp << bevelPoint; + ret.append({{pbp, sp, bevelPoint}, -1, {}, true}); + } + }; + + + /* + Iterate through the path. Each start element has to be postponed until the end of the sub-path. + At that point, we have to process both the start and the end elements. + + If the end element's end point is equal to the start element's start point, we treat them as connected, + otherwise we add null pointers + */ + + const QuadPath::Element *startElement = nullptr; + int startElementIndex = -1; + const QuadPath::Element *prevElement = nullptr; + //### For now, we know that this path has not been split + for (int i = 0; i < path.elementCount(); ++i) { + const auto *element = &path.elementAt(i); + // ### isSubPathEnd() doesn't work unless subPathsClosed() has been called + bool isSubPathEnd = i == path.elementCount() - 1 || path.elementAt(i + 1).isSubpathStart(); + bool isSubPathStart = element->isSubpathStart() || i == 0; // 0 should always be subPathStart, but just to be sure + if (isSubPathStart) { + if (isSubPathEnd) { + // If the element is both start and end, it's a standalone + handleElement(nullptr, element, nullptr, i); + startElement = nullptr; // These should be ignored, but reset just in case + prevElement = nullptr; + } else { + // this element will be handled later, when we know whether the sub-path is closed + startElement = element; + startElementIndex = i; + prevElement = element; + } + continue; + } + + const QuadPath::Element *nextElement = nullptr; + if (i != 0 && !element->isSubpathStart()) + prevElement = &path.elementAt(i - 1); + + if (isSubPathEnd) { + //handle the previous start element: check if it is connected to this element + Q_ASSERT(startElement); + bool subPathClosed = element->endPoint() == startElement->startPoint(); + handleElement(subPathClosed ? element : nullptr, startElement, &path.elementAt(startElementIndex + 1), startElementIndex); + if (subPathClosed) + nextElement = startElement; + startElement = nullptr; + } else { + nextElement = &path.elementAt(i + 1); + } + handleElement(prevElement, element, nextElement, i); + prevElement = isSubPathEnd ? nullptr : element; + } + Q_ASSERT(!startElement); // Should have been handled in the loop + + return ret; +} + +}; + +QVector<QSGGeometryNode *> QQuickShapeCurveRenderer::addNodesStrokeShader(const PathData &pathData, NodeList *debugNodes) +{ + QVector<QSGGeometryNode *> ret; + + Q_UNUSED(debugNodes); + + const QColor &color = pathData.pen.color(); + Q_UNUSED(color) + + QVector<QQuickShapeLoopBlinnNode::LoopBlinnVertex> vertexBuffer; + QVector<quint32> indices; + bool visualizeDebug = debugVisualization() & DebugCurves; + const float dbg = visualizeDebug ? 0.5f : 0.0f; + QVector<QQuickShapeWireFrameNode::WireFrameVertex> wfVertices; + + const auto &thePath = pathData.qPath; + + // qDebug() << "Stroking" << thePath; + + + // TODO: calculate margin correctly for narrow angles. If it's too big we'll get into unsafe space more often + auto triangles = customTriangulator(thePath, float(pathData.pen.widthF()) * 1, pathData.pen.joinStyle() == Qt::MiterJoin); //### SvgMiterJoin ??? + + //### TODO: reduce code duplication + auto addVertexDataForPoint = [&vertexBuffer, &wfVertices, dbg](const QuadPath::Element &element, const QVector2D &p, const QVector3D &color, int wfIndex) { + auto uv = element.uvForPoint(p); + + float r = color.x(), g = color.y(), b = color.z(); + + vertexBuffer.append({p.x(), p.y(), uv.x(), uv.y(), uv.z(), r, g, b, dbg}); + switch (wfIndex % 3) { + case 0: + wfVertices.append({p.x(), p.y(), 1.0f, 0.0f, 0.0f}); + break; + case 1: + wfVertices.append({p.x(), p.y(), 0.0f, 1.0f, 0.0f}); + break; + case 2: + wfVertices.append({p.x(), p.y(), 0.0f, 0.0f, 1.0f}); + break; + } + }; + + auto addCurveTriangle = [&](const QuadPath::Element &element, const QVector2D &sp, const QVector2D &ep, const QVector2D &cp, const QVector3D &color){ + int currentVertex = vertexBuffer.count(); + addVertexDataForPoint(element, sp, color, 0); + addVertexDataForPoint(element, cp, color, 1); + addVertexDataForPoint(element, ep, color, 2); + indices << currentVertex << currentVertex + 1 << currentVertex + 2; + }; + + // TESTING + auto addBevelTriangle = [&](const QVector2D &p1, const QVector2D &p2, const QVector2D &p3) + { + float r = 0.0f; + float g = 1.0f; + float b = 0.5f; + + + // MEGA HACK!!! Invent a curve based on the triangle, since we know that: + // p2 is the path join point + // the stroke passes through the mid points of p2-p1 and p2-p3 + + // we have static inline QVector2D curveUv(QVector2D p0, QVector2D p1, QVector2D p2, QVector2D p) + // which finds uv coordinates for the point p, for a quadratic curve from p0 to p2 with control point p1 + + QVector2D fp1 = p2 + (p3 - p1); + QVector2D fp2 = p2 - (p3 - p1); + QVector2D fcp = (p1 + 3 * p2 + p3) / 5; // does not matter for line + + // The bevel is not strokeWidth/2 wide, it's half this triangle's height + // We need to shift everything down by the difference (definitely hackish) + + QVector2D vh = ((p1 - p2) + (p3 - p2)) / 2; + float triangleHeight = vh.length(); + float delta = (pathData.pen.widthF() - triangleHeight) / 2; + + QVector2D offset = vh.normalized() * delta; + fp1 -= offset; + fp2 -= offset; + fcp -= offset; + + + const auto uv1 = curveUv(fp1, fcp, fp2, p1); + const auto uv2 = curveUv(fp1, fcp, fp2, p2); + const auto uv3 = curveUv(fp1, fcp, fp2, p3); + + const int currentVertex = vertexBuffer.count(); + vertexBuffer.append({p1.x(), p1.y(), uv1.x(), uv1.y(), 0.0f, r, g, b, dbg}); + vertexBuffer.append({p2.x(), p2.y(), uv2.x(), uv2.y(), 0.0f, r, g, b, dbg}); + vertexBuffer.append({p3.x(), p3.y(), uv3.x(), uv3.y(), 0.0f, r, g, b, dbg}); + indices << currentVertex << currentVertex + 1 << currentVertex + 2; + wfVertices.append({p1.x(), p1.y(), 1.0f, 0.0f, 0.0f}); + wfVertices.append({p2.x(), p2.y(), 0.0f, 1.0f, 0.0f}); + wfVertices.append({p3.x(), p3.y(), 0.0f, 0.0f, 1.0f}); + //qDebug() << "bev" << p1 << p2 << p3; + }; + + static constexpr QVector3D specialDebug{0.0f, 1.0f, 1.0f}; + + for (const auto &triangle : triangles) { + if (triangle.pathElementIndex < 0) { + //TESTING + addBevelTriangle(triangle.points[0], triangle.points[1], triangle.points[2]); + continue; + } + const auto &element = thePath.elementAt(triangle.pathElementIndex); + addCurveTriangle(element, triangle.points[0], triangle.points[1], triangle.points[2], + triangle.specialDebug ? specialDebug : triangle.debugColor); + } + + + + if (indices.size() > 0) { + auto *node = new QQuickShapeLoopBlinnNode(NoGradient); // TODO: dedicated node + node->color = Qt::transparent; + //node->fillGradient = pathData.gradient; + + node->strokeColor = pathData.pen.color(); // this is all you need to use the stroke shader + node->strokeWidth = pathData.pen.widthF(); + + QSGGeometry *g = new QSGGeometry(QQuickShapeLoopBlinnNode::attributes(), + vertexBuffer.size(), indices.size(), QSGGeometry::UnsignedIntType); + node->setGeometry(g); + g->setDrawingMode(QSGGeometry::DrawTriangles); + + //qDebug() << "gvc" << g->vertexCount(); + + memcpy(g->vertexData(), + vertexBuffer.data(), + g->vertexCount() * g->sizeOfVertex()); + memcpy(g->indexData(), + indices.data(), + indices.size() * g->sizeOfIndex()); + + m_rootNode->appendChildNode(node); + ret.append(node); + } + const bool wireFrame = debugVisualization() & DebugWireframe; + if (wireFrame) { + QQuickShapeWireFrameNode *wfNode = new QQuickShapeWireFrameNode; + + //QVarLengthArray<quint32> indices; + + QSGGeometry *wfg = new QSGGeometry(QQuickShapeWireFrameNode::attributes(), + wfVertices.size(), + indices.size(), + QSGGeometry::UnsignedIntType); + wfNode->setGeometry(wfg); + + wfg->setDrawingMode(QSGGeometry::DrawTriangles); + memcpy(wfg->indexData(), + indices.data(), + indices.size() * wfg->sizeOfIndex()); + memcpy(wfg->vertexData(), + wfVertices.data(), + wfg->vertexCount() * wfg->sizeOfVertex()); + + m_rootNode->appendChildNode(wfNode); + debugNodes->append(wfNode); + } + return ret; +} + //TODO: we could optimize by preprocessing e1, since we call this function multiple times on the same // elements static void handleOverlap(QuadPath &path, qsizetype e1, qsizetype e2, int recursionLevel = 0) @@ -1624,172 +2717,4 @@ void QQuickShapeCurveRenderer::solveOverlaps(QuadPath &path) } } -//#define ROUNDING -QVector<QSGGeometryNode *> QQuickShapeCurveRenderer::addPathNodesDelaunayTest(const PathData &pathData, NodeList *debugNodes) -{ - const QuadPath &thePath = pathData.path; - if (thePath.elementCount() == 0) - return QVector<QSGGeometryNode *>{}; - - QList<QtPathVertex> vertices; - QList<QtPathEdge> edges; - - // Generate the graph for the triangulator - // Start with adding an external bounding box - - auto boundingRect = pathData.path.controlPointRect(); - float extraBorder = qMax(boundingRect.width(), boundingRect.height()) * 0.10; // 10% extra - boundingRect.adjust(-extraBorder, -extraBorder, extraBorder, extraBorder); - - vertices << QtPathVertex{ QVector2D(boundingRect.topLeft()), 1 }; - vertices << QtPathVertex{ QVector2D(boundingRect.topRight()), 2 }; - vertices << QtPathVertex{ QVector2D(boundingRect.bottomRight()), 3 }; - vertices << QtPathVertex{ QVector2D(boundingRect.bottomLeft()), 4 }; - edges.append({ 0, 1, 1 }); - edges.append({ 1, 2, 2 }); - edges.append({ 2, 3, 3 }); - edges.append({ 3, 0, 4 }); - - // Then add all the edges that we want to have - // TODO: We ought actually have an index-based structure in QuadPath. - // For now, just duplicate points - -#if !defined(ROUNDING) - QHash<QPair<qreal, qreal>, int> pointHash; -#else - QHash<QPair<int, int>, int> pointHash; -#endif - thePath.iterateElements([&](const QuadPath::Element &element) { - auto findOrInsert = [&pointHash, &vertices](const QVector2D &p) { -#if defined(ROUNDING) - auto key = qMakePair(QFixed::fromReal(qRound(p.x() * 32.0) / 32.0).value(), - QFixed::fromReal(qRound(p.y() * 32.0) / 32.0).value()); -#else - auto key = qMakePair(p.x(), p.y()); -#endif - - auto it = pointHash.find(key); - if (it != pointHash.end()) { - return it.value(); - } else { - vertices << QtPathVertex{ p, 42}; - pointHash.insert(key, int(vertices.size() - 1)); - return int(vertices.size() - 1); - } - }; - - - quint32 startIdx = findOrInsert(element.startPoint()); - quint32 endIdx = findOrInsert(element.endPoint()); - - edges.append({ startIdx, endIdx, 42 }); - if (!element.isLine()) { - quint32 controlIdx = findOrInsert(element.controlPoint()); - edges.append({ startIdx, controlIdx, 42 }); - edges.append({ endIdx, controlIdx, 42 }); - } - }); - - //Add a "super triangle" for the Delauney algorithm - -{ - // Calculate the dimensions and center of the bounding box - float width = boundingRect.width(); - float height = boundingRect.height(); - float centerX = boundingRect.center().x(); - float centerY = boundingRect.center().y(); - - // Create a super-triangle with vertices outside the bounding box - int l = vertices.length(); - QtPathVertex v1 = {QVector2D(centerX, centerY - 3 * height), l++}; // Top vertex - QtPathVertex v2 = {QVector2D(centerX - 3 * width, centerY + 3 * height), l++}; // Bottom-left vertex - QtPathVertex v3 = {QVector2D(centerX + 3 * width, centerY + 3 * height), l}; // Bottom-right vertex - - vertices << v1 << v2 << v3; - -} - - QList<QtPathTriangle> triangles = qtDelaunayTriangulator(vertices, edges, pathData.originalPath); - - if (!triangles.isEmpty()) - testTriangulation(vertices, edges, triangles); - - // Quick-and-dirty triangle visualisation: - - // Semi-transparent triangle fill to debug coverage and overlap - auto *fillNode = new QQuickShapeLoopBlinnNode(QQuickAbstractPathRenderer::NoGradient); - - QSGGeometry *g = new QSGGeometry(QQuickShapeLoopBlinnNode::attributes(), - vertices.size(), triangles.size() * 3, QSGGeometry::UnsignedIntType); - - fillNode->setGeometry(g); - g->setDrawingMode(QSGGeometry::DrawTriangles); - m_rootNode->appendChildNode(fillNode); - - QVector<QQuickShapeLoopBlinnNode::LoopBlinnVertex> vertexData; - vertexData.reserve(vertices.size()); - QVector<quint32> indexData; - indexData.reserve(triangles.size() * 3); - - fillNode->color = QColor(0x7f, 0xff, 0, 0x7f); - for (const auto &v : std::as_const(vertices)) - vertexData.append({ v.point.x(), v.point.y(), 0.0f, 1.0f, -1.0f, 0.0f, 0.0f, 0.0f, 0.0f }); - for (const auto &t : std::as_const(triangles)) - indexData << t.v1Index << t.v2Index << t.v3Index; - - memcpy(g->vertexData(), - vertexData.data(), - g->vertexCount() * g->sizeOfVertex()); - memcpy(g->indexData(), - indexData.data(), - indexData.size() * g->sizeOfIndex()); - - - // A wireframe node to show the edges - QQuickShapeWireFrameNode *wfNode = new QQuickShapeWireFrameNode; - QSGGeometry *wfg = wfNode->geometry(); - - QVarLengthArray<quint32> indices; - int iidx = 0; - QVarLengthArray<QQuickShapeWireFrameNode::WireFrameVertex> wfVertices; - - auto addWireframeVertex = [&](int vertexIndex, int index){ - float u = index % 3 == 0 ? 1.0f : 0.0f; - float v = index % 3 == 1 ? 1.0f : 0.0f; - float w = index % 3 == 2 ? 1.0f : 0.0f; - - auto pt = vertices[vertexIndex].point; - indices.append(iidx++); - wfVertices.append({ pt.x(), pt.y(), u, v, w }); - }; - - for (const auto &t : std::as_const(triangles)) { - addWireframeVertex(t.v1Index, 0); - addWireframeVertex(t.v2Index, 1); - addWireframeVertex(t.v3Index, 2); - } - - if (wfg->indexType() != QSGGeometry::UnsignedIntType) { - wfg = new QSGGeometry(QQuickShapeWireFrameNode::attributes(), - wfVertices.size(), - indices.size(), - QSGGeometry::UnsignedIntType); - wfNode->setGeometry(wfg); - } else { - wfg->allocate(wfVertices.size(), indices.size()); - } - - wfg->setDrawingMode(QSGGeometry::DrawTriangles); - memcpy(wfg->indexData(), - indices.data(), - indices.size() * wfg->sizeOfIndex()); - memcpy(wfg->vertexData(), - wfVertices.data(), - wfg->vertexCount() * wfg->sizeOfVertex()); - - m_rootNode->appendChildNode(wfNode); - debugNodes->append(wfNode); - return { fillNode }; -} - QT_END_NAMESPACE diff --git a/src/quickshapes/qquickshapecurverenderer_p.h b/src/quickshapes/qquickshapecurverenderer_p.h index 6916de018e..859ff000c8 100644 --- a/src/quickshapes/qquickshapecurverenderer_p.h +++ b/src/quickshapes/qquickshapecurverenderer_p.h @@ -59,6 +59,7 @@ public: static QuadPath fromPainterPath(const QPainterPath &path); QPainterPath toPainterPath() const; QuadPath subPathsClosed() const; + QuadPath flattened() const; class Element { @@ -131,6 +132,8 @@ public: return QVector2D(-tan.y(), tan.x()); } + float extent() const; + private: int intersectionsAtY(float y, float *fractions) const; @@ -306,6 +309,7 @@ private: QPainterPath fillPath; QPainterPath originalPath; QuadPath path; + QuadPath qPath; // TODO: better name QColor fillColor; Qt::FillRule fillRule = Qt::OddEvenFill; QPen pen; @@ -321,8 +325,9 @@ private: void deleteAndClear(NodeList *nodeList); QVector<QSGGeometryNode *> addPathNodesBasic(const PathData &pathData, NodeList *debugNodes); - - QVector<QSGGeometryNode *> addPathNodesDelaunayTest(const PathData &pathData, NodeList *debugNodes); + QVector<QSGGeometryNode *> addPathNodesLineShader(const PathData &pathData, NodeList *debugNodes); + QVector<QSGGeometryNode *> addStrokeNodes(const PathData &pathData, NodeList *debugNodes); + QVector<QSGGeometryNode *> addNodesStrokeShader(const PathData &pathData, NodeList *debugNodes); QSGGeometryNode *addLoopBlinnNodes(const QTriangleSet &triangles, const QVarLengthArray<quint32> &extraIndices, diff --git a/src/quickshapes/qquickshapecurverenderer_p_p.h b/src/quickshapes/qquickshapecurverenderer_p_p.h index 4904cbc2b9..40d0f3beb4 100644 --- a/src/quickshapes/qquickshapecurverenderer_p_p.h +++ b/src/quickshapes/qquickshapecurverenderer_p_p.h @@ -25,52 +25,9 @@ QT_BEGIN_NAMESPACE Q_DECLARE_LOGGING_CATEGORY(lcShapeCurveRenderer); -struct QtPathVertex -{ - QVector2D point; - int id; - quint32 binX = 0; - quint32 binY = 0; -}; - -struct QtPathEdge -{ - quint32 startIndex; - quint32 endIndex; - int id; -}; - -struct QtPathTriangle -{ - QtPathTriangle(quint32 i1, quint32 i2, quint32 i3, int d) : v1Index(i1), v2Index(i2), v3Index(i3), id(d) {} - quint32 v1Index; - quint32 v2Index; - quint32 v3Index; - - quint32 adjacentTriangle1 = quint32(-1); // Adjacent to v1-v2 - quint32 adjacentTriangle2 = quint32(-1); // Adjacent to v2-v3 - quint32 adjacentTriangle3 = quint32(-1); // Adjacent to v3-v1 - - // Used by triangulator - quint32 lastSeenVertex = quint32(-1); - - // Should this triangle be rendered? Set to false for triangles connecting to super-triangle - bool isValid = true; - - int id; -}; - -constexpr bool operator==(const QtPathTriangle& lhs, const QtPathTriangle& rhs) -{ - return lhs.id == rhs.id - && lhs.v1Index == rhs.v1Index - && lhs.v2Index == rhs.v2Index - && lhs.v3Index == rhs.v3Index; -} - class QBezier; -Q_QUICKSHAPES_PRIVATE_EXPORT QPolygonF qt_toQuadratics(const QBezier &b, qreal errorLimit = 0.2); -Q_QUICKSHAPES_PRIVATE_EXPORT QList<QtPathTriangle> qtDelaunayTriangulator(const QList<QtPathVertex> &vertices, const QList<QtPathEdge> &edges, const QPainterPath &path); +Q_QUICKSHAPES_PRIVATE_EXPORT void qt_toQuadratics(const QBezier &b, QPolygonF *out, + qreal errorLimit = 0.01); QT_END_NAMESPACE diff --git a/src/quickshapes/qt_delaunay_triangulator.cpp b/src/quickshapes/qt_delaunay_triangulator.cpp deleted file mode 100644 index 0f52477476..0000000000 --- a/src/quickshapes/qt_delaunay_triangulator.cpp +++ /dev/null @@ -1,1439 +0,0 @@ -// 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 - -#include "qquickshapecurverenderer_p_p.h" -#include <QtGui/qvector2d.h> -#include <QtGui/private/qtriangulator_p.h> -#include <QtCore/QHash> -#include <QtCore/QSet> -#include <QtCore/QPair> -#include <QtCore/QStack> -#include <QtCore/QElapsedTimer> - -// #define QQUICKSHAPES_DEBUG_IMAGE 1 - -QT_BEGIN_NAMESPACE - -Q_LOGGING_CATEGORY(lcShapeTiming, "qt.shape.timing"); - -// Check if a point is inside the circumcircle of a triangle defined by three vertices (v1, v2, v3). -// It uses the determinant of a matrix formed from the coordinates of the point and the vertices -// to determine if the point is inside the circumcircle. -// If the determinant is > 0, the point is inside the circumcircle. -inline bool isPointInCircumcircle(const QVector2D &point, - const QVector2D &v1_, const QVector2D &v2_, const QVector2D &v3_) -{ - QVector2D v1 = v1_; - QVector2D v2 = v2_; - QVector2D v3 = v3_; - - // Vertices must be in ccw order - if ( ( ( (v2.x() - v1.x()) * (v3.y() - v1.y()) ) - ( (v3.x() - v1.x()) * (v2.y() - v1.y()) ) ) <= 0.0f) { - qSwap(v2, v3); - } - -#if 1 - float x13 = v1.x() - v3.x(); - float y13 = v1.y() - v3.y(); - float x23 = v2.x() - v3.x(); - float y23 = v2.y() - v3.y(); - float x1p = v1.x() - point.x(); - float y1p = v1.y() - point.y(); - float x2p = v2.x() - point.x(); - float y2p = v2.y() - point.y(); - - return (x13*x23 + y13*y23) * (x2p*y1p - x1p*y2p) < (x23*y13 - x13*y23) * (x2p*x1p + y1p*y2p); - -#else - float ax = v1.x() - point.x(); - float ay = v1.y() - point.y(); - float bx = v2.x() - point.x(); - float by = v2.y() - point.y(); - float cx = v3.x() - point.x(); - float cy = v3.y() - point.y(); - - float det = (ax * ax + ay * ay) * (bx * cy - cx * by) - - (bx * bx + by * by) * (ax * cy - cx * ay) + - (cx * cx + cy * cy) * (ax * by - bx * ay); - - return det > 0.0f; -#endif -} - -// Retrieves quad corresponding to t1 and t2 (assuming that they share one edge) -// In the end, the new diagonal is (i1, i3) and (i1, i2, i3, i4) is the ordered vertices -// in the quad. -inline void findQuad(const QtPathTriangle &t1, const QtPathTriangle &t2, - quint32 *i1, quint32 *i2, quint32 *i3, quint32 *i4) -{ - // First find index in t1 which is not in t2 and call this i1 (with i2, and i4 completing t1) - if (t1.v1Index != t2.v1Index && t1.v1Index != t2.v2Index && t1.v1Index != t2.v3Index) { - (*i1) = t1.v1Index; - (*i2) = t1.v2Index; - (*i4) = t1.v3Index; - } else if (t1.v2Index != t2.v1Index && t1.v2Index != t2.v2Index && t1.v2Index != t2.v3Index) { - (*i1) = t1.v2Index; - (*i2) = t1.v3Index; - (*i4) = t1.v1Index; - } else { - Q_ASSERT(t1.v3Index != t2.v1Index && t1.v3Index != t2.v2Index && t1.v3Index != t2.v3Index); - (*i1) = t1.v3Index; - (*i2) = t1.v1Index; - (*i4) = t1.v2Index; - } - - // Then find (*i3) as index in t2 which is not in t1 - if (t2.v1Index != t1.v1Index && t2.v1Index != t1.v2Index && t2.v1Index != t1.v3Index) { - (*i3) = t2.v1Index; - } else if (t2.v2Index != t1.v1Index && t2.v2Index != t1.v2Index && t2.v2Index != t1.v3Index) { - (*i3) = t2.v2Index; - } else { - Q_ASSERT(t2.v3Index != t1.v1Index && t2.v3Index != t1.v2Index && t2.v3Index != t1.v3Index); - (*i3) = t2.v3Index; - } -} - -inline void swapDiagonal(QtPathTriangle *t1, - QtPathTriangle *t2, - quint32 idx = quint32(-1)) -{ - quint32 i1, i2, i3, i4; - findQuad(*t1, *t2, &i1, &i2, &i3, &i4); - Q_ASSERT(idx == quint32(-1) || t2->v1Index == idx || t2->v2Index == idx || t2->v3Index == idx); - - t2->v1Index = i1; - t2->v2Index = i3; - t2->v3Index = i2; - - t1->v1Index = i1; - t1->v2Index = i3; - t1->v3Index = i4; -} - -inline bool isPointInTriangle(const QVector2D &v, - const QVector2D &v1, - const QVector2D &v2, - const QVector2D &v3) -{ -#if 0 - QPolygonF p; - p.append(v1.toPointF()); - p.append(v2.toPointF()); - p.append(v3.toPointF()); - return p.containsPoint(v.toPointF(), Qt::OddEvenFill); -#else - if ( (v1.x() > v.x() && v2.x() > v.x() && v3.x() > v.x()) - || (v1.x() < v.x() && v2.x() < v.x() && v3.x() < v.x()) - || (v1.y() > v.y() && v2.y() > v.y() && v3.y() > v.y()) - || (v1.y() < v.y() && v2.y() < v.y() && v3.y() < v.y())) { - return false; - } - - // Barycentric scalars - double denom = (v2.y() - v3.y()) * (v1.x() - v3.x()) - + (v3.x() - v2.x()) * (v1.y() - v3.y()); - double a = ((v2.y() - v3.y()) * (v.x() - v3.x()) - + (v3.x() - v2.x()) * (v.y() - v3.y())) - / denom; - double b = ((v3.y() - v1.y()) * (v.x() - v3.x()) - + (v1.x() - v3.x()) * (v.y() - v3.y())) - / denom; - double c = 1.0 - a - b; - - if (qFuzzyIsNull(a)) - a = 0.0; - if (qFuzzyIsNull(b)) - b = 0.0; - if (qFuzzyIsNull(c)) - c = 0.0; - - if (qFuzzyCompare(a, 1.0)) - a = 1.0; - if (qFuzzyCompare(b, 1.0)) - b = 1.0; - if (qFuzzyCompare(c, 1.0)) - c = 1.0; - - return a >= 0.0 && a <= 1.0 - && b >= 0.0 && b <= 1.0 - && c >= 0.0 && c <= 1.0; -#endif -} - -inline void saveDebugImage(bool shouldDraw, - const QPainterPath &path, - const QString &label, - const QList<QtPathTriangle> &triangles, - const QList<QtPathVertex> &vertices, - const QList<quint32> &highlightedPoints = QList<quint32>{}, - const QList<quint32> &highlightedTriangles = QList<quint32>{}, - const QList<QPair<quint32, quint32> > &highlightedEdges = QList<QPair<quint32, quint32> >{}) -{ -#if defined(QQUICKSHAPES_DEBUG_IMAGE) - shouldDraw = true; -#endif - - static bool zoom = qEnvironmentVariableIntValue("QT_QUICKSHAPES_ZOOM_DEBUG_IMAGE"); - - if (!shouldDraw) - return; - - static int counter = 0; - - int size = 3000; - QImage image(size, size, QImage::Format_ARGB32); - image.fill(Qt::black); - - QList<QVector2D> vs; - - if (zoom) { - for (auto it : highlightedPoints) - vs.append(vertices.at(it).point); - - for (auto it : highlightedEdges) { - vs.append(vertices.at(it.first).point); - vs.append(vertices.at(it.second).point); - } - - for (auto it : highlightedTriangles) { - vs.append(vertices.at(triangles.at(it).v1Index).point); - vs.append(vertices.at(triangles.at(it).v2Index).point); - vs.append(vertices.at(triangles.at(it).v3Index).point); - } - } else { - for (int i = 0; i < vertices.size() - 3; ++i) - vs.append(vertices.at(i).point); - } - - float minX = 0.0f; - float maxX = 0.0f; - float minY = 0.0f; - float maxY = 0.0f; - for (int i = 0; i < vs.size(); ++i) { - QVector2D p = vs.at(i); - if (i == 0 || minX > p.x()) - minX = p.x(); - if (i == 0 || maxX < p.x()) - maxX = p.x(); - if (i == 0 || minY > p.y()) - minY = p.y(); - if (i == 0 || maxY < p.y()) - maxY = p.y(); - } - - minX -= (maxX - minX) * 0.05f; - minY -= (maxY - minY) * 0.05f; - maxX += (maxX - minX) * 0.05f; - maxY += (maxY - minY) * 0.05f; - - { - QPainter painter(&image); - - float w = maxX - minX; - float h = maxY - minY; - - float max = qMax(w, h); - - painter.save(); - painter.scale(size / max, size / max); - painter.translate(-QPointF(minX, minY)); - - float fontSize = 18 * max / size; - - QFont font = painter.font(); - font.setPixelSize(qCeil(fontSize)); - - painter.setFont(font); - - if (!path.isEmpty()) { - painter.save(); - painter.setBrush(Qt::darkGray); - painter.drawPath(path); - painter.setOpacity(1); - painter.restore(); - } - - for (int i = 0; i < triangles.size(); ++i) { - QtPathTriangle triangle = triangles.at(i); - QPolygonF polygon; - polygon.append(vertices.at(triangle.v1Index).point.toPointF()); - polygon.append(vertices.at(triangle.v2Index).point.toPointF()); - polygon.append(vertices.at(triangle.v3Index).point.toPointF()); - - QPen pen(Qt::red, 3); - pen.setCosmetic(true); - - painter.setPen(pen); - painter.drawPolygon(polygon); - - painter.setPen(Qt::white); - painter.drawText(vertices.at(triangle.v1Index).point.toPointF(), - QString::number(triangle.v1Index)); - painter.drawText(vertices.at(triangle.v2Index).point.toPointF(), - QString::number(triangle.v2Index)); - painter.drawText(vertices.at(triangle.v3Index).point.toPointF(), - QString::number(triangle.v3Index)); - } - - for (int i = 0; i < highlightedTriangles.size(); ++i) { - int highlightedTriangle = highlightedTriangles.at(i); - QColor color = i > 0 ? Qt::magenta : Qt::green; - - QtPathTriangle triangle = triangles.at(highlightedTriangle); - QPolygonF polygon; - polygon.append(vertices.at(triangle.v1Index).point.toPointF()); - polygon.append(vertices.at(triangle.v2Index).point.toPointF()); - polygon.append(vertices.at(triangle.v3Index).point.toPointF()); - - QPen pen(color, 3); - pen.setCosmetic(true); - - painter.setPen(pen); - painter.drawPolygon(polygon); - - } - - for (int i = 0; i < highlightedPoints.size(); ++i) { - int highlightedPoint = highlightedPoints.at(i); - QPointF point = vertices.at(highlightedPoint).point.toPointF(); - - painter.setBrush(Qt::yellow); - - QPen pen(Qt::yellow, 3); - pen.setCosmetic(true); - painter.setPen(pen); - painter.drawEllipse(point, 5 * max / size, 5 * max / size); - } - - for (int i = 0; i < highlightedEdges.size(); ++i) { - auto highlightedEdge = highlightedEdges.at(i); - QLineF line(vertices.at(highlightedEdge.first).point.toPointF(), - vertices.at(highlightedEdge.second).point.toPointF()); - - QColor color = i == 0 ? Qt::yellow : Qt::cyan; - QPen pen(color, 3); - pen.setCosmetic(true); - painter.setPen(pen); - - painter.drawLine(line); - - } - - painter.setPen(Qt::white); - painter.setBrush(Qt::white); - - painter.restore(); - - QFont f = painter.font(); - f.setPixelSize(18); - painter.setFont(f); - QFontMetricsF fm(f); - - painter.fillRect(QRectF(0, size - fm.height() * 3, size, fm.height() * 3), Qt::red); - painter.drawText(QRectF(0, size - fm.height() * 3, size, fm.height() * 3), - Qt::AlignCenter, - QStringLiteral("%1, %2 triangles").arg(label).arg(triangles.size())); - } - - image.save(QStringLiteral("delaunay%1.png").arg(counter++)); -} - -// Checks if the quadrilateral made up of triangle1 and triangle2 is strictly convex -inline bool isConvexQuadrilateral(const QList<QtPathVertex> &vertices, - const QtPathTriangle &triangle1, - const QtPathTriangle &triangle2) -{ - quint32 quad[4]; - - findQuad(triangle1, triangle2, &quad[0], &quad[1], &quad[2], &quad[3]); - - int mask = 0; - // Check if the cross product of all adjacent lines points the same way - for (int i = 0; i < 4 && mask <= 2; ++i) { - quint32 p1 = quad[i]; - quint32 p2 = quad[(i + 1) % 4]; - quint32 p3 = quad[(i + 2) % 4]; - - QVector2D v1 = vertices.at(p2).point - vertices.at(p1).point; - QVector2D v2 = vertices.at(p3).point - vertices.at(p2).point; - - // Parallel lines - if ((qFuzzyIsNull(v1.x()) && qFuzzyIsNull(v2.x())) - || (qFuzzyIsNull(v1.y()) && qFuzzyIsNull(v2.y()))) { - mask = 3; - } - - if (!qFuzzyIsNull(v1.x()) && qFuzzyIsNull(v2.x()) && qFuzzyIsNull(v1.y()) && qFuzzyIsNull(v2.y())) { - float v1Slope = v1.y() / v1.x(); - float v2Slope = v2.y() / v2.x(); - - if (mask <= 2 && (qFuzzyCompare(v1Slope, v2Slope) || qFuzzyCompare(v1Slope, -v2Slope))) - mask = 3; - } - -// if (mask <= 2 && (v1.normalized() == v2.normalized() || v1.normalized() == -v2.normalized())) -// mask |= 3; - - if (mask <= 2) { - float c = v1.x() * v2.y() - v1.y() * v2.x(); - if (c >= 0.0f) - mask |= 1; - else - mask |= 2; - } - - - } - return mask <= 2; -} - -inline bool lineIntersects(const QVector2D &v1_, const QVector2D &v2_, - const QVector2D &u1_, const QVector2D &u2_) -{ -#if 1 - QPointF v1 = v1_.toPointF(); - QPointF v2 = v2_.toPointF(); - QPointF u1 = u1_.toPointF(); - QPointF u2 = u2_.toPointF(); - - if ( (v1.x() < u1.x() && v1.x() < u2.x() && v2.x() < u1.x() && v2.x() < u2.x()) - || (v1.x() > u1.x() && v1.x() > u2.x() && v2.x() > u1.x() && v2.x() > u2.x()) - || (v1.y() < u1.y() && v1.y() < u2.y() && v2.y() < u1.y() && v2.y() < u2.y()) - || (v1.y() > u1.y() && v1.y() > u2.y() && v2.y() > u1.y() && v2.y() > u2.y())) { - return false; - } - - // Copied from QLineF::intersects() with some changes to ordering to speed - // up for our use case - const QPointF a = v2 - v1; - const QPointF b = u1 - u2; - const QPointF c = v1 - u1; - - const qreal denominator = a.y() * b.x() - a.x() * b.y(); - if (denominator == 0.0 || !qt_is_finite(denominator)) - return false; - - const qreal reciprocal = 1.0 / denominator; - qreal na = (b.y() * c.x() - b.x() * c.y()) * reciprocal; - if (na < 0.0 || na > 1.0) - return false; - - qreal nb = (a.x() * c.y() - a.y() * c.x()) * reciprocal; - if (nb < 0.0 || nb > 1.0) - return false; - - const QPointF intersectionPoint = v1 + a * na; - return intersectionPoint != v1 && intersectionPoint != v2 && intersectionPoint != u1 && intersectionPoint != u2; - return true; -#else - QLineF v(v1.toPointF(), v2.toPointF()); - QLineF u(u1.toPointF(), u2.toPointF()); - - QPointF intersectionPoint; - if (v.intersects(u, &intersectionPoint) == QLineF::BoundedIntersection) { - return (intersectionPoint != v.p1() && intersectionPoint != v.p2() - && intersectionPoint != u.p1() && intersectionPoint != u.p2()); - } - - return false; -#endif -} - -// Returns edges (and the adjacent triangles corresponding to them) which have visibility -// to the vertex -static void findAdjacentTrianglesOnSameSide(const QList<QtPathVertex> &vertices, - quint32 vertexIdx, - const QtPathTriangle &triangle, - QVarLengthArray<quint32, 2> *possibleTriangles, - QVarLengthArray<QPair<quint32, quint32>, 2> *edges = nullptr) -{ - Q_ASSERT(possibleTriangles != nullptr); - QVector2D v = vertices.at(vertexIdx).point; - QVector2D v1 = vertices.at(triangle.v1Index).point; - QVector2D v2 = vertices.at(triangle.v2Index).point; - QVector2D v3 = vertices.at(triangle.v3Index).point; - - bool d = ( ( ( (v2.x() - v1.x()) * (v3.y() - v1.y()) ) - ( (v3.x() - v1.x()) * (v2.y() - v1.y()) ) )) <= 0.0f; - - // Check v1 - v2 - if (triangle.adjacentTriangle1 != quint32(-1)) { - bool d1 = ((v.x() - v1.x()) * (v2.y() - v1.y()) - (v.y() - v1.y()) * (v2.x() - v1.x())) <= 0.0f; - if (d1 == d) { - possibleTriangles->append(triangle.adjacentTriangle1); - if (edges != nullptr) { - if (triangle.v1Index < triangle.v2Index) - edges->append(qMakePair(triangle.v1Index, triangle.v2Index)); - else - edges->append(qMakePair(triangle.v2Index, triangle.v1Index)); - } - } - } - - // Check v2 - v3 - if (triangle.adjacentTriangle2 != quint32(-1)) { - bool d2 = ((v.x() - v2.x()) * (v3.y() - v2.y()) - (v.y() - v2.y()) * (v3.x() - v2.x())) <= 0.0f; - if (d2 == d) { - possibleTriangles->append(triangle.adjacentTriangle2); - if (edges != nullptr) { - if (triangle.v2Index < triangle.v3Index) - edges->append(qMakePair(triangle.v2Index, triangle.v3Index)); - else - edges->append(qMakePair(triangle.v3Index, triangle.v2Index)); - } - } - } - - // Check v3 - v1 - if (triangle.adjacentTriangle3 != quint32(-1)) { - bool d3 = ((v.x() - v3.x()) * (v1.y() - v3.y()) - (v.y() - v3.y()) * (v1.x() - v3.x())) <= 0.0f; - if (d3 == d) { - possibleTriangles->append(triangle.adjacentTriangle3); - if (edges != nullptr) { - if (triangle.v3Index < triangle.v1Index) - edges->append(qMakePair(triangle.v3Index, triangle.v1Index)); - else - edges->append(qMakePair(triangle.v1Index, triangle.v3Index)); - } - } - } -} - -static quint32 findAdjacentTriangleOnSameSide(const QList<QtPathVertex> &vertices, - quint32 vertexIdx, - const QtPathTriangle &triangle) -{ - QVarLengthArray<quint32, 2> possibleTriangles; - findAdjacentTrianglesOnSameSide(vertices, vertexIdx, triangle, &possibleTriangles); - - if (possibleTriangles.size() == 0) { - qCWarning(lcShapeCurveRenderer) << "Point" << vertexIdx - << "is not on the outside of any edge of triangle" - << triangle.v1Index << triangle.v2Index << triangle.v3Index; - return quint32(-1); - } - - return possibleTriangles.at(0); -} - -// CDT using Incremental Algorithm approach. -// the algorithm first inserts the edge's endpoints into the triangulation. -// Then, it finds the sequence of triangles intersected by the constraint -// edge and modifies them to include the edge. -QList<QtPathTriangle> qtDelaunayTriangulator(const QList<QtPathVertex> &_vertices, - const QList<QtPathEdge> &edges, - const QPainterPath &path) -{ - static bool saveImageOnError = qEnvironmentVariableIntValue("QT_QUICKSHAPES_SAVE_IMAGE_ON_ERROR") != 0; - static bool drawAllImages = qEnvironmentVariableIntValue("QT_QUICKSHAPES_SAVE_DEBUG_IMAGE") != 0; - static bool normalizeCoordinates = qEnvironmentVariableIntValue("QT_QUICKSHAPES_NORMALIZE_COORDINATES") != 0; - static bool validateResults = qEnvironmentVariableIntValue("QT_QUICKSHAPES_VALIDATE_RESULTS"); - - if (_vertices.isEmpty()) - return {}; - - QList<QtPathVertex> vertices; - if (Q_UNLIKELY(normalizeCoordinates)) { - vertices.reserve(_vertices.size()); - - qreal minX, minY, maxX, maxY; - for (int i = 0; i < _vertices.size(); ++i) { - const QtPathVertex &v = _vertices.at(i); - if (i == 0 || v.point.x() < minX) - minX = v.point.x(); - if (i == 0 || v.point.x() > maxX) - maxX = v.point.x(); - if (i == 0 || v.point.y() < minY) - minY = v.point.y(); - if (i == 0 || v.point.y() > maxY) - maxY = v.point.y(); - } - - for (int i = 0; i < _vertices.size(); ++i) { - QtPathVertex v = _vertices.at(i); - v.point -= QVector2D(minX, minY); - v.point /= QVector2D(maxX - minX, maxY - minY); - vertices.append(v); - } - } else { - vertices = _vertices; - } - - QList<QtPathTriangle> triangulation; - triangulation.reserve(2 * vertices.size() + 1); - - // Create a super-triangle - const quint32 l = int(vertices.size()); - QtPathTriangle superTriangle = { l - 3, l - 2, l - 1, 0}; - triangulation.append(superTriangle); - - QElapsedTimer t; - t.start(); - - typedef QPair<quint32, quint32> Pair; - - QHash<Pair, Pair> existingEdges; - QSet<Pair> constrainedEdges; - existingEdges.reserve(3 * (2 * vertices.size() + 1)); - - auto registerAdjacency = [&triangulation](quint32 a, quint32 b, quint32 triangleIdx1, quint32 triangleIdx2) { - Q_ASSERT(triangleIdx1 < triangulation.size()); - Q_ASSERT(triangleIdx2 < triangulation.size()); - - QtPathTriangle &t1 = triangulation[triangleIdx1]; - QtPathTriangle &t2 = triangulation[triangleIdx2]; - - if ((t1.v1Index == a && t1.v2Index == b) || (t1.v1Index == b && t1.v2Index == a)) { - t1.adjacentTriangle1 = triangleIdx2; - } else if ((t1.v2Index == a && t1.v3Index == b) || (t1.v2Index == b && t1.v3Index == a)) { - t1.adjacentTriangle2 = triangleIdx2; - } else { - Q_ASSERT(((t1.v3Index == a && t1.v1Index == b) || (t1.v3Index == b && t1.v1Index == a))); - t1.adjacentTriangle3 = triangleIdx2; - } - - if ((t2.v1Index == a && t2.v2Index == b) || (t2.v1Index == b && t2.v2Index == a)) { - t2.adjacentTriangle1 = triangleIdx1; - } else if ((t2.v2Index == a && t2.v3Index == b) || (t2.v2Index == b && t2.v3Index == a)) { - t2.adjacentTriangle2 = triangleIdx1; - } else { - Q_ASSERT((t2.v3Index == a && t2.v1Index == b) || (t2.v3Index == b && t2.v1Index == a)); - t2.adjacentTriangle3 = triangleIdx1; - } - }; - - auto unregisterAdjacency = [&triangulation](quint32 triangleIdx1, quint32 triangleIdx2) { - Q_ASSERT(triangleIdx1 < triangulation.size()); - Q_ASSERT(triangleIdx2 < triangulation.size()); - - QtPathTriangle &t1 = triangulation[triangleIdx1]; - QtPathTriangle &t2 = triangulation[triangleIdx2]; - - if (t1.adjacentTriangle1 == triangleIdx2) { - t1.adjacentTriangle1 = quint32(-1); - } else if (t1.adjacentTriangle2 == triangleIdx2) { - t1.adjacentTriangle2 = quint32(-1); - } else { - Q_ASSERT(t1.adjacentTriangle3 == triangleIdx2); - t1.adjacentTriangle3 = quint32(-1); - } - - if (t2.adjacentTriangle1 == triangleIdx1) { - t2.adjacentTriangle1 = quint32(-1); - } else if (t2.adjacentTriangle2 == triangleIdx1) { - t2.adjacentTriangle2 = quint32(-1); - } else { - Q_ASSERT(t2.adjacentTriangle3 == triangleIdx1); - t2.adjacentTriangle3 = quint32(-1); - } - }; - - auto insertOrdered = [&existingEdges, ®isterAdjacency](quint32 a, quint32 b, quint32 triangleIdx) { - if (a > b) - qSwap(a, b); - - Pair edge = qMakePair(a, b); - auto it = existingEdges.find(edge); - if (it == existingEdges.end()) { - existingEdges.insert(edge, qMakePair(triangleIdx, quint32(-1))); - } else { - if (it.value().first == quint32(-1)) { - Q_ASSERT(triangleIdx != it.value().second); - it.value().first = triangleIdx; - } else { - Q_ASSERT(it.value().second == quint32(-1)); - Q_ASSERT(triangleIdx != it.value().first); - it.value().second = triangleIdx; - } - - if (it.value().first != quint32(-1) && it.value().second != quint32(-1)) - registerAdjacency(a, b, it.value().first, it.value().second); - } - }; - - auto removeTriangleEdge = [&existingEdges, &unregisterAdjacency](quint32 a, quint32 b, quint32 triangleIdx) { - if (a > b) - qSwap(a, b); - - Pair edge = qMakePair(a, b); - auto it = existingEdges.find(edge); - Q_ASSERT(it != existingEdges.end()); - - if (it.value().first != quint32(-1) && it.value().second != quint32(-1)) - unregisterAdjacency(it.value().first, it.value().second); - - // Mark that triangleIdx no longer shares the edge - if (it.value().first == triangleIdx) - it.value().first = quint32(-1); - else - it.value().second = quint32(-1); - - - // No more triangles refer to this (== it was the old diagonal), so we - // remove it from the existing edges list - if (it.value().first == quint32(-1) && it.value().second == quint32(-1)) - it = existingEdges.erase(it); - }; - - insertOrdered(superTriangle.v1Index, superTriangle.v2Index, 0); - insertOrdered(superTriangle.v2Index, superTriangle.v3Index, 0); - insertOrdered(superTriangle.v3Index, superTriangle.v1Index, 0); - - // Insert vertices one by one - // For each vertex, we search for the triangle that contains it and then split this at the - // point. We then check the Delaunay property of the new triangles and their neighbours, and - // swap diagonals to restore Delaunayness when needed. - quint32 lastFormedTriangle = 0; - for (quint32 vertexIdx = 0; vertexIdx < l - 3; ++vertexIdx) { - const QtPathVertex &vertex = vertices.at(vertexIdx); - - if (Q_UNLIKELY(drawAllImages)) { - saveDebugImage(true, - path, - QStringLiteral("Adding vertex %1: %2, %3").arg(vertexIdx).arg(vertex.point.x()).arg(vertex.point.y()), - triangulation, - vertices, - QList<quint32>{} << vertexIdx); - } - - QStack<QPair<quint32, quint32> > adjacentTriangles; - auto findAdjacent = [&existingEdges, &vertexIdx, &adjacentTriangles](quint32 i1, quint32 i2, quint32 triangleIdx) { - if (i1 != vertexIdx && i2 != vertexIdx) { - - if (i1 > i2) - qSwap(i1, i2); - Pair key = qMakePair(i1, i2); - auto it = existingEdges.find(key); - Q_ASSERT(it.value().first == triangleIdx || it.value().second == triangleIdx); - - if (it.value().first != quint32(-1) && it.value().second != quint32(-1)) { - if (it.value().first == triangleIdx) - adjacentTriangles.append(qMakePair(it.value().second, triangleIdx)); - else - adjacentTriangles.append(qMakePair(it.value().first, triangleIdx)); - } - } - }; - - { - quint32 triangleIdx1 = quint32(-1); - - // Start with the last formed triangle (or the super triangle on the first run) - // Use Lawson's visibility walk to find the triangle containing the point: - // First check the current triangle (starting with the last formed). If it does not - // contain the point, the next triangle to check is the one of the adjacent triangles - // in the direction of the point. This is done using a "visibility" check, i.e. whether - // the point is on the exterior half-plane of the shared edge.) - triangleIdx1 = lastFormedTriangle; - while (triangleIdx1 != quint32(-1) - && !isPointInTriangle(vertex.point, - vertices[triangulation.at(triangleIdx1).v1Index].point, - vertices[triangulation.at(triangleIdx1).v2Index].point, - vertices[triangulation.at(triangleIdx1).v3Index].point)) { - QtPathTriangle &triangle = triangulation[triangleIdx1]; - if (triangle.lastSeenVertex != quint32(-1) && triangle.lastSeenVertex == vertexIdx) { - qCWarning(lcShapeCurveRenderer) << "Revisiting triangle which has previously been checked"; - triangleIdx1 = quint32(-1); - break; - } - - triangle.lastSeenVertex = vertexIdx; - - // If the point is not in the current triangle, we find the edge(s) where the - // point is on the outside of the triangle. The adjacent triangle to this edge - // is the next in the search. If there are two such edges we pick the first. - // As long as the triangulation is a Delaunay triangulation, this should always - // find the triangle, but we keep a fail safe in case of bugs. - quint32 nextTriangle = findAdjacentTriangleOnSameSide(vertices, - vertexIdx, - triangle); - if (Q_UNLIKELY(drawAllImages)) { - saveDebugImage(true, - path, - QStringLiteral("Marching from %1 to %2 (%3, %4, %5)").arg(triangleIdx1).arg(nextTriangle), - triangulation, - vertices, - QList<quint32>{} << vertexIdx, - QList<quint32>{} << (nextTriangle != quint32(-1) ? nextTriangle : 0) << triangleIdx1, - QList<Pair>{}); - } - - triangleIdx1 = nextTriangle; - } - - // Fail safe, if we failed to find the triangle using the optimized step, we do a brute - // force search. - if (validateResults || triangleIdx1 == quint32(-1)) { - if (triangleIdx1 == quint32(-1)) - qCWarning(lcShapeCurveRenderer) << "Can't find triangle using Lawson. Falling back to brute force"; - quint32 otherTriangle = triangleIdx1; - triangleIdx1 = 0; - for (; triangleIdx1 < triangulation.size(); ++triangleIdx1) { - const QtPathTriangle &triangle = triangulation.at(triangleIdx1); - if (isPointInTriangle(vertex.point, vertices[triangle.v1Index].point, - vertices[triangle.v2Index].point, - vertices[triangle.v3Index].point)) { - break; - } - } - - if (validateResults && otherTriangle != triangleIdx1 && triangleIdx1 != quint32(-1) && otherTriangle != quint32(-1)) { - qCWarning(lcShapeCurveRenderer) << "Lawson matched" << otherTriangle - << "whereas brute force matched" << triangleIdx1 - << "Lawson:" << vertices.at(triangulation.at(otherTriangle).v1Index).point - << vertices.at(triangulation.at(otherTriangle).v2Index).point - << vertices.at(triangulation.at(otherTriangle).v3Index).point - << "Brute:" << vertices.at(triangulation.at(triangleIdx1).v1Index).point - << vertices.at(triangulation.at(triangleIdx1).v2Index).point - << vertices.at(triangulation.at(triangleIdx1).v3Index).point - << "Testing point:" << vertices.at(vertexIdx).point; - - saveDebugImage(saveImageOnError, - path, - QStringLiteral("Two triangles containing the same point"), - triangulation, - vertices, - QList<quint32>{} << vertexIdx, - QList<quint32>{} << triangleIdx1 << otherTriangle); - } - } - - if (Q_UNLIKELY(drawAllImages)) { - saveDebugImage(true, - path, - QStringLiteral("Splitting triangle"), - triangulation, - vertices, - QList<quint32>{} << vertexIdx, - QList<quint32>{} << triangleIdx1); - } - - if (triangleIdx1 >= triangulation.size()) { - qCWarning(lcShapeCurveRenderer) << "Unable to find any triangle containing point" - << vertex.point - << ". Aborting."; - return QList<QtPathTriangle>{}; - } - - // Split triangle into three, connecting to the new vertex - quint32 t1v1Index; - quint32 t1v2Index; - quint32 t1v3Index; - { - QtPathTriangle &t1 = triangulation[triangleIdx1]; - t1v1Index = t1.v1Index; - t1v2Index = t1.v2Index; - t1v3Index = t1.v3Index; - t1.v3Index = vertexIdx; - - removeTriangleEdge(t1v2Index, t1v3Index, triangleIdx1); - removeTriangleEdge(t1v3Index, t1v1Index, triangleIdx1); - } - - - quint32 triangleIdx2 = triangulation.size(); - triangulation.append(QtPathTriangle(t1v2Index, t1v3Index, vertexIdx, triangulation.count())); - quint32 triangleIdx3 = triangulation.size(); - triangulation.append(QtPathTriangle(t1v3Index, t1v1Index, vertexIdx, triangulation.count())); - const QtPathTriangle &t2 = triangulation.at(triangleIdx2); - const QtPathTriangle &t3 = triangulation.at(triangleIdx3); - - lastFormedTriangle = triangleIdx3; - - t1v3Index = vertexIdx; - - insertOrdered(t1v2Index, t1v3Index, triangleIdx1); - insertOrdered(t1v3Index, t1v1Index, triangleIdx1); - - insertOrdered(t2.v1Index, t2.v2Index, triangleIdx2); - insertOrdered(t2.v2Index, t2.v3Index, triangleIdx2); - insertOrdered(t2.v3Index, t2.v1Index, triangleIdx2); - - insertOrdered(t3.v1Index, t3.v2Index, triangleIdx3); - insertOrdered(t3.v2Index, t3.v3Index, triangleIdx3); - insertOrdered(t3.v3Index, t3.v1Index, triangleIdx3); - - // Find triangles sharing edges with new triangles and push to stack - findAdjacent(t1v1Index, t1v2Index, triangleIdx1); - findAdjacent(t2.v1Index, t2.v2Index, triangleIdx2); - findAdjacent(t3.v1Index, t3.v2Index, triangleIdx3); - } - - // Check adjacent triangles to see that they do not contain the introduced vertex in their - // circumcircle. In cases where this happens, we take the quadrilateral consisting of the - // new triangle and its neighbour and turn it into two new triangles by swapping to the - // other diagonal. - while (!adjacentTriangles.isEmpty()) { - QPair<quint32, quint32> pair = adjacentTriangles.pop(); - quint32 triangleIdx1 = pair.first; - quint32 triangleIdx2 = pair.second; - - // If opposing triangle circumcircle contains the vertex we are adding, we swap - // the diagonal of the quad made of the two opposing triangles - QtPathTriangle &triangle1 = triangulation[triangleIdx1]; - QtPathTriangle &triangle2 = triangulation[triangleIdx2]; - if (isPointInCircumcircle(vertex.point, vertices[triangle1.v1Index].point, - vertices[triangle1.v2Index].point, - vertices[triangle1.v3Index].point)) { - if (Q_UNLIKELY(drawAllImages)) { - saveDebugImage(true, - path, - QStringLiteral("About to swap diagonal"), - triangulation, - vertices, - QList<quint32>{} << vertexIdx, - QList<quint32>{} << triangleIdx1 << triangleIdx2); - } - - removeTriangleEdge(triangle1.v1Index, triangle1.v2Index, triangleIdx1); - removeTriangleEdge(triangle1.v2Index, triangle1.v3Index, triangleIdx1); - removeTriangleEdge(triangle1.v3Index, triangle1.v1Index, triangleIdx1); - - removeTriangleEdge(triangle2.v1Index, triangle2.v2Index, triangleIdx2); - removeTriangleEdge(triangle2.v2Index, triangle2.v3Index, triangleIdx2); - removeTriangleEdge(triangle2.v3Index, triangle2.v1Index, triangleIdx2); - - swapDiagonal(&triangle1, &triangle2, vertexIdx); - - if (Q_UNLIKELY(drawAllImages)) { - saveDebugImage(true, - path, - QStringLiteral("Has swapped diagonal"), - triangulation, - vertices, - QList<quint32>{} << vertexIdx, - QList<quint32>{} << triangleIdx1 << triangleIdx2); - } - - // Add back triangles sharing edges - insertOrdered(triangle1.v1Index, triangle1.v2Index, triangleIdx1); - insertOrdered(triangle1.v2Index, triangle1.v3Index, triangleIdx1); - insertOrdered(triangle1.v3Index, triangle1.v1Index, triangleIdx1); - - insertOrdered(triangle2.v1Index, triangle2.v2Index, triangleIdx2); - insertOrdered(triangle2.v2Index, triangle2.v3Index, triangleIdx2); - insertOrdered(triangle2.v3Index, triangle2.v1Index, triangleIdx2); - - findAdjacent(triangle1.v1Index, triangle1.v2Index, triangleIdx1); - findAdjacent(triangle1.v2Index, triangle1.v3Index, triangleIdx1); - findAdjacent(triangle1.v3Index, triangle1.v1Index, triangleIdx1); - - findAdjacent(triangle2.v1Index, triangle2.v2Index, triangleIdx2); - findAdjacent(triangle2.v2Index, triangle2.v3Index, triangleIdx2); - findAdjacent(triangle2.v3Index, triangle2.v1Index, triangleIdx2); - } - } - } - - qCDebug(lcShapeTiming) << "qtDelaunayTriangulator: Inserting vertices in" << t.elapsed() << "ms"; - - // Make a look-up for constrained edges to check self-intersections - for (const QtPathEdge &constraintEdge : edges) { - quint32 a = constraintEdge.startIndex; - quint32 b = constraintEdge.endIndex; - if (a > b) - qSwap(a, b); - constrainedEdges.insert(qMakePair(a, b)); - } - - // Insert constraint edges: - // For each constrained edge, we make sure it is in the triangulation: We first check if it - // already happens to be, and if so we do nothing. If it is not, we check which edges in the - // current graph it intersects, and remove these by swapping diagonals. We then go through - // newly created edges (except the constrained edge) and swap them for the other diagonals in - // cases where this is needed to satisfy Delaunay property. - for (const QtPathEdge &constraintEdge : edges) { - quint32 a = constraintEdge.startIndex; - quint32 b = constraintEdge.endIndex; - if (a > b) - qSwap(a, b); - - // If edge already exists, we continue - if (!existingEdges.contains(qMakePair(a, b))) { - const QVector2D &newEdgeP1 = vertices.at(a).point; - const QVector2D &newEdgeP2 = vertices.at(b).point; - - // Find all edges that intersect with [a, b] - QList<Pair> intersectingEdges; - static bool permitSelfIntersections = qEnvironmentVariableIntValue("QT_QUICKSHAPES_PERMIT_SELF_INTERSECTIONS") != 0; - - // We start search with any triangle containing 'a' as a vertex - // ### Could we keep track of this as well in the vertex info? - quint32 triangleIdx = 0; - while (triangleIdx != quint32(-1) - && triangulation.at(triangleIdx).v1Index != a - && triangulation.at(triangleIdx).v2Index != a - && triangulation.at(triangleIdx).v3Index != a) { - const QtPathTriangle &triangle = triangulation.at(triangleIdx); - triangleIdx = findAdjacentTriangleOnSameSide(vertices, - a, - triangle); - } - - if (triangleIdx >= triangulation.size()) { - qCWarning(lcShapeCurveRenderer) - << "qtDelaunayTriangulator: Unable to find any triangle containing vertex" - << a << vertices.at(a).point - << ". Constrained edge will be missing from triangulation"; - continue; - } - - // We now circle 'a' by looking at adjacent triangles on edges containing 'a' (making - // sure we do not go backwards) until we find one which intersects [a, b]. We then - // use the visibility walk to check triangles in the direction of 'b', recording - // intersections as we go and moving via intersecting edges. We stop when there are no - // more intersections. - quint32 previousTriangleIdx = quint32(-1); - quint32 startingTriangleIdx = triangleIdx; - while (triangleIdx != quint32(-1)) { - quint32 nextTriangle = quint32(-1); - const QtPathTriangle &triangle = triangulation.at(triangleIdx); - - if (Q_UNLIKELY(drawAllImages)) { - saveDebugImage(true, - path, - QStringLiteral("Circling %1 to find first intersection (triangle: %2, %3, %4)").arg(a).arg(triangle.v1Index).arg(triangle.v2Index).arg(triangle.v3Index), - triangulation, - vertices, - QList<quint32>{} << a, - QList<quint32>{} << triangleIdx, - QList<Pair>{} << qMakePair(a, b)); - } - - Pair existingEdge; - quint32 adjacentTriangle; - if (triangle.v1Index == a) { - existingEdge = qMakePair(triangle.v2Index, triangle.v3Index); - adjacentTriangle = triangle.adjacentTriangle2; - - if (triangle.adjacentTriangle1 != previousTriangleIdx - && triangle.adjacentTriangle1 != quint32(-1)) { - nextTriangle = triangle.adjacentTriangle1; // v1-v2 - } else { - nextTriangle = triangle.adjacentTriangle3; // v3-v1 - } - } else if (triangle.v2Index == a) { - existingEdge = qMakePair(triangle.v3Index, triangle.v1Index); - adjacentTriangle = triangle.adjacentTriangle3; - - if (triangle.adjacentTriangle1 != previousTriangleIdx - && triangle.adjacentTriangle1 != quint32(-1)) { - nextTriangle = triangle.adjacentTriangle1; // v1-v2 - } else { - nextTriangle = triangle.adjacentTriangle2; // v2-v3 - } - } else { // a == triangle.v3Index - Q_ASSERT(a == triangle.v3Index); - existingEdge = qMakePair(triangle.v1Index, triangle.v2Index); - adjacentTriangle = triangle.adjacentTriangle1; - - if (triangle.adjacentTriangle3 != previousTriangleIdx - && triangle.adjacentTriangle3 != quint32(-1)) { - nextTriangle = triangle.adjacentTriangle3; // v3-v1 - } else { - nextTriangle = triangle.adjacentTriangle2; // v2-v3 - } - } - - const QVector2D &existingEdgeP1 = vertices.at(existingEdge.first).point; - const QVector2D &existingEdgeP2 = vertices.at(existingEdge.second).point; - - if (lineIntersects(newEdgeP1, newEdgeP2, existingEdgeP1, existingEdgeP2)) { - // Go to next phase of search, where the intersections are recorded. - triangleIdx = adjacentTriangle; - if (existingEdge.first > existingEdge.second) - qSwap(existingEdge.first, existingEdge.second); - intersectingEdges.append(existingEdge); - - if (!permitSelfIntersections && constrainedEdges.contains(existingEdge)) { - qCWarning(lcShapeCurveRenderer) - << "qtDelaunayTriangulator: Exiting early due to self-intersection." - << "Edge 1:" << a << b << "(" << newEdgeP1 << newEdgeP2 << ")" - << "Edge 2:" << existingEdge.first << existingEdge.second << "(" << existingEdgeP1 << existingEdgeP2 << ")"; - saveDebugImage(saveImageOnError, - path, - QStringLiteral("Found intersection of two constrained edges. No solution."), - triangulation, - vertices, - QList<quint32>{}, - QList<quint32>{}, - QList<QPair<quint32, quint32> >{} - << qMakePair(a, b) - << qMakePair(existingEdge.first, existingEdge.second)); - return QList<QtPathTriangle>{}; - } - - break; - } - - previousTriangleIdx = triangleIdx; - triangleIdx = nextTriangle; - - // No intersection found - if (triangleIdx == startingTriangleIdx) - triangleIdx = quint32(-1); - } - - // Now we march towards 'b' and record all intersections - while (triangleIdx != quint32(-1)) { - const QtPathTriangle &triangle = triangulation.at(triangleIdx); - - QVarLengthArray<quint32, 2> possibleTriangles; - QVarLengthArray<Pair, 2> edges; - - findAdjacentTrianglesOnSameSide(vertices, b, triangle, &possibleTriangles, &edges); - - // Check edge(s) which can see 'b' for intersections - triangleIdx = quint32(-1); - for (int i = 0; i < edges.size(); ++i) { - const Pair &existingEdge = edges.at(i); - - const QVector2D &existingEdgeP1 = vertices.at(existingEdge.first).point; - const QVector2D &existingEdgeP2 = vertices.at(existingEdge.second).point; - - if (existingEdge.first != a - && existingEdge.second != a - && lineIntersects(newEdgeP1, newEdgeP2, existingEdgeP1, existingEdgeP2)) { - if (!permitSelfIntersections && constrainedEdges.contains(existingEdge)) { - qCWarning(lcShapeCurveRenderer) - << "qtDelaunayTriangulator: Exiting early due to self-intersection." - << "Edge 1:" << a << b << "(" << newEdgeP1 << newEdgeP2 << ")" - << "Edge 2:" << existingEdge.first << existingEdge.second << "(" << existingEdgeP1 << existingEdgeP2 << ")"; - saveDebugImage(saveImageOnError, - path, - QStringLiteral("Found intersection of two constrained edges. No solution."), - triangulation, - vertices, - QList<quint32>{}, - QList<quint32>{}, - QList<QPair<quint32, quint32> >{} - << qMakePair(a, b) - << qMakePair(existingEdge.first, existingEdge.second)); - return QList<QtPathTriangle>{}; - } - - intersectingEdges.append(existingEdge); - triangleIdx = possibleTriangles[i]; - - if (Q_UNLIKELY(drawAllImages)) { - saveDebugImage(true, - path, - QStringLiteral("Marching to %1 (triangle: %2, %3, %4)") - .arg(b) - .arg(triangulation.at(possibleTriangles.first()).v1Index) - .arg(triangulation.at(possibleTriangles.first()).v2Index) - .arg(triangulation.at(possibleTriangles.first()).v3Index), - triangulation, - vertices, - QList<quint32>{} << b, - QList<quint32>{} << triangleIdx << possibleTriangles.first(), - QList<Pair>{} << qMakePair(a, b) << existingEdge); - } - } - } - } - - if (Q_UNLIKELY(validateResults)) { - QList<Pair> intersectingEdgesFound = intersectingEdges; - intersectingEdges.clear(); - for (auto it = existingEdges.constBegin(); it != existingEdges.constEnd(); ++it) { - const Pair &existingEdge = it.key(); - - const QVector2D &existingEdgeP1 = vertices.at(existingEdge.first).point; - const QVector2D &existingEdgeP2 = vertices.at(existingEdge.second).point; - - if (existingEdge.first != a && existingEdge.second != a - && existingEdge.first != b && existingEdge.second != b - && lineIntersects(newEdgeP1, newEdgeP2, existingEdgeP1, existingEdgeP2)) { - if (!permitSelfIntersections && constrainedEdges.contains(existingEdge)) { - qCWarning(lcShapeCurveRenderer) - << "qtDelaunayTriangulator: Exiting early due to self-intersection." - << "Edge 1:" << a << b << "(" << newEdgeP1 << newEdgeP2 << ")" - << "Edge 2:" << existingEdge.first << existingEdge.second << "(" << existingEdgeP1 << existingEdgeP2 << ")"; - saveDebugImage(saveImageOnError, - path, - QStringLiteral("Found intersection of two constrained edges. No solution."), - triangulation, - vertices, - QList<quint32>{}, - QList<quint32>{}, - QList<QPair<quint32, quint32> >{} << qMakePair(a, b) << qMakePair(existingEdge.first, existingEdge.second)); - return QList<QtPathTriangle>{}; - } - - intersectingEdges.append(existingEdge); - - if (Q_UNLIKELY(drawAllImages)) { - saveDebugImage(true, - path, - QStringLiteral("Found intersection of constrained edge (%1 so far)").arg(intersectingEdges.size()), - triangulation, - vertices, - QList<quint32>{}, - QList<quint32>{}, - QList<QPair<quint32, quint32> >{} << qMakePair(a, b) << qMakePair(existingEdge.first, existingEdge.second)); - } - } - } - - for (const Pair &intersectingEdge : intersectingEdges) { - bool found = false; - for (const Pair &otherIntersectingEdge : intersectingEdgesFound) { - if (otherIntersectingEdge == intersectingEdge || qMakePair(otherIntersectingEdge.second, otherIntersectingEdge.first) == intersectingEdge) { - found = true; - break; - } - } - - if (!found) { - qCWarning(lcShapeCurveRenderer) << "Intersecting edge" << intersectingEdge.first << intersectingEdge.second << "not found with smart algorithm. Constrained edge:" << a << b; - - saveDebugImage(saveImageOnError, - path, - QStringLiteral("Intersecting edge not found"), - triangulation, - vertices, - QList<quint32>{}, - QList<quint32>{}, - QList<QPair<quint32, quint32> >{} << qMakePair(a, b) << qMakePair(intersectingEdge.first, intersectingEdge.second)); - - return QList<QtPathTriangle>{}; - } - } - - for (const Pair &intersectingEdge : intersectingEdgesFound) { - bool found = false; - for (const Pair &otherIntersectingEdge : intersectingEdges) { - if (otherIntersectingEdge == intersectingEdge || qMakePair(otherIntersectingEdge.second, otherIntersectingEdge.first) == intersectingEdge) { - found = true; - break; - } - } - - if (!found) { - qCWarning(lcShapeCurveRenderer) << "Intersecting edge" << intersectingEdge.first << intersectingEdge.second << "not found with dumb algorithm. Constrained edge:" << a << b; - - saveDebugImage(saveImageOnError, - path, - QStringLiteral("Intersecting edge not found"), - triangulation, - vertices, - QList<quint32>{}, - QList<quint32>{}, - QList<QPair<quint32, quint32> >{} << qMakePair(a, b) << qMakePair(intersectingEdge.first, intersectingEdge.second)); - - return QList<QtPathTriangle>{}; - } - } - } - - bool somethingChanged = false; - auto it = intersectingEdges.begin(); - QSet<Pair> newlyCreatedEdges; - while (!intersectingEdges.isEmpty()) { - Q_ASSERT(it != intersectingEdges.end()); - - Pair existingEdge = *it; - - Q_ASSERT(existingEdges.contains(existingEdge)); - - // ### Since we are now finding edges via triangles, this information can be - // included in the intersecting edges list and we do not need the extra lookup. - Pair triangles = existingEdges.value(existingEdge); - - QtPathTriangle &triangle1 = triangulation[triangles.first]; - QtPathTriangle &triangle2 = triangulation[triangles.second]; - - // If the triangles do not together make a convex polygon, we skip this for now - // Otherwise, swap the diagonal - if (isConvexQuadrilateral(vertices, triangle1, triangle2)) { - somethingChanged = true; - - if (Q_UNLIKELY(drawAllImages)) { - saveDebugImage(true, - path, - QStringLiteral("About to swap diagonal"), - triangulation, - vertices, - QList<quint32>{}, - QList<quint32>{} << triangles.first << triangles.second, - QList<QPair<quint32, quint32> >{} << qMakePair(existingEdge.first, existingEdge.second)); - } - - // The triangles are being altered, so we have to remove them from the edge - // list first - removeTriangleEdge(triangle1.v1Index, triangle1.v2Index, triangles.first); - removeTriangleEdge(triangle1.v2Index, triangle1.v3Index, triangles.first); - removeTriangleEdge(triangle1.v3Index, triangle1.v1Index, triangles.first); - - removeTriangleEdge(triangle2.v1Index, triangle2.v2Index, triangles.second); - removeTriangleEdge(triangle2.v2Index, triangle2.v3Index, triangles.second); - removeTriangleEdge(triangle2.v3Index, triangle2.v1Index, triangles.second); - - // If not, we swap the diagonal of the two triangles - swapDiagonal(&triangle1, &triangle2); - it = intersectingEdges.erase(it); - if (it == intersectingEdges.end()) { // Wrap over end of list - it = intersectingEdges.begin(); - somethingChanged = false; - } - - // Add back triangles sharing edges - insertOrdered(triangle1.v1Index, triangle1.v2Index, triangles.first); - insertOrdered(triangle1.v2Index, triangle1.v3Index, triangles.first); - insertOrdered(triangle1.v3Index, triangle1.v1Index, triangles.first); - - insertOrdered(triangle2.v1Index, triangle2.v2Index, triangles.second); - insertOrdered(triangle2.v2Index, triangle2.v3Index, triangles.second); - insertOrdered(triangle2.v3Index, triangle2.v1Index, triangles.second); - - Pair newDiagonal = triangle1.v1Index < triangle1.v2Index - ? qMakePair(triangle1.v1Index, triangle1.v2Index) - : qMakePair(triangle1.v2Index, triangle1.v1Index); - - if (Q_UNLIKELY(drawAllImages)) { - saveDebugImage(true, - path, - QStringLiteral("Swapped diagonal"), - triangulation, - vertices, - QList<quint32>{}, - QList<quint32>{} << triangles.first << triangles.second, - QList<QPair<quint32, quint32> >{} << qMakePair(newDiagonal.first, newDiagonal.second)); - } - - // By convention, the new diagonal is now the two first vertices in the triangles - const QVector2D &newDiagonalP1 = vertices[triangle1.v1Index].point; - const QVector2D &newDiagonalP2 = vertices[triangle1.v2Index].point; - - if (newDiagonal.first != a - && newDiagonal.second != a - && newDiagonal.first != b - && newDiagonal.second != b - && lineIntersects(newEdgeP1, newEdgeP2, newDiagonalP1, newDiagonalP2)) { - it = intersectingEdges.insert(it, newDiagonal); - } else { - if (newDiagonal != qMakePair(a, b) && newDiagonal != qMakePair(b, a)) - newlyCreatedEdges.insert(newDiagonal); - - continue; // No need to increase iterator, since we erased - } - } else { - if (Q_UNLIKELY(drawAllImages)) { - saveDebugImage(true, - path, - QStringLiteral("Skipping non-convex quad"), - triangulation, - vertices, - QList<quint32>{}, - QList<quint32>{} << triangles.first << triangles.second, - QList<QPair<quint32, quint32> >{} << qMakePair(existingEdge.first, existingEdge.second)); - } - } - - if (++it == intersectingEdges.end()) { // Wrap over end of list - if (!somethingChanged && !intersectingEdges.isEmpty()) { - intersectingEdges.prepend(qMakePair(a, b)); // Just for visuals - saveDebugImage(saveImageOnError, - path, - QStringLiteral("Looped through all edges with no changes. No solution."), - triangulation, - vertices, - QList<quint32>{}, - QList<quint32>{}, - intersectingEdges); - qCWarning(lcShapeCurveRenderer) << "Detected infinite loop. Exiting early."; - break; - } - - it = intersectingEdges.begin(); - somethingChanged = false; - } - } - - // Restore the delaunay properties - for (const Pair &newlyCreatedEdge : newlyCreatedEdges) { - auto it = existingEdges.find(newlyCreatedEdge); - Q_ASSERT(it != existingEdges.end()); - - Pair triangles = it.value(); - - QtPathTriangle &triangle1 = triangulation[triangles.first]; - QtPathTriangle &triangle2 = triangulation[triangles.second]; - - bool delaunaySatisfied = - !isPointInCircumcircle(vertices.at(triangle1.v1Index).point, - vertices.at(triangle2.v1Index).point, - vertices.at(triangle2.v2Index).point, - vertices.at(triangle2.v3Index).point) - && !isPointInCircumcircle(vertices.at(triangle1.v2Index).point, - vertices.at(triangle2.v1Index).point, - vertices.at(triangle2.v2Index).point, - vertices.at(triangle2.v3Index).point) - && !isPointInCircumcircle(vertices.at(triangle1.v3Index).point, - vertices.at(triangle2.v1Index).point, - vertices.at(triangle2.v2Index).point, - vertices.at(triangle2.v3Index).point) - && !isPointInCircumcircle(vertices.at(triangle2.v1Index).point, - vertices.at(triangle1.v1Index).point, - vertices.at(triangle1.v2Index).point, - vertices.at(triangle1.v3Index).point) - && !isPointInCircumcircle(vertices.at(triangle2.v2Index).point, - vertices.at(triangle1.v1Index).point, - vertices.at(triangle1.v2Index).point, - vertices.at(triangle1.v3Index).point) - && !isPointInCircumcircle(vertices.at(triangle2.v3Index).point, - vertices.at(triangle1.v1Index).point, - vertices.at(triangle1.v2Index).point, - vertices.at(triangle1.v3Index).point); - if (!delaunaySatisfied) { - removeTriangleEdge(triangle1.v1Index, triangle1.v2Index, triangles.first); - removeTriangleEdge(triangle1.v2Index, triangle1.v3Index, triangles.first); - removeTriangleEdge(triangle1.v3Index, triangle1.v1Index, triangles.first); - - removeTriangleEdge(triangle2.v1Index, triangle2.v2Index, triangles.second); - removeTriangleEdge(triangle2.v2Index, triangle2.v3Index, triangles.second); - removeTriangleEdge(triangle2.v3Index, triangle2.v1Index, triangles.second); - - // If not, we swap the diagonal of the two triangles - swapDiagonal(&triangle1, &triangle2); - - // Add back triangles sharing edges - insertOrdered(triangle1.v1Index, triangle1.v2Index, triangles.first); - insertOrdered(triangle1.v2Index, triangle1.v3Index, triangles.first); - insertOrdered(triangle1.v3Index, triangle1.v1Index, triangles.first); - - insertOrdered(triangle2.v1Index, triangle2.v2Index, triangles.second); - insertOrdered(triangle2.v2Index, triangle2.v3Index, triangles.second); - insertOrdered(triangle2.v3Index, triangle2.v1Index, triangles.second); - } - } - - if (Q_UNLIKELY(validateResults)) { - if (!existingEdges.contains(qMakePair(a, b))) { - qCWarning(lcShapeCurveRenderer) - << "Unable to produce triangulation with edge" << a << b; - saveDebugImage(saveImageOnError, - path, - QStringLiteral("Triangulation missing [%1, %2]").arg(a).arg(b), - triangulation, - vertices, - QList<quint32>{}, - QList<quint32>{}, - QList<Pair>{} << qMakePair(a, b)); - } - } - } - } - - qCDebug(lcShapeTiming) << "qtDelaunayTriangulator: Inserting edges in" << t.elapsed() << "ms"; - - for (auto it = triangulation.begin(); it != triangulation.end(); ++it) { - QtPathTriangle &triangle = *it; - if (triangle.v1Index >= l - 3 || triangle.v2Index >= l - 3 || triangle.v3Index >= l - 3) - triangle.isValid = false; - } - - return triangulation; -} - -QT_END_NAMESPACE diff --git a/src/quickshapes/qt_quadratic_bezier.cpp b/src/quickshapes/qt_quadratic_bezier.cpp index 93158010a1..6a41a67872 100644 --- a/src/quickshapes/qt_quadratic_bezier.cpp +++ b/src/quickshapes/qt_quadratic_bezier.cpp @@ -8,38 +8,81 @@ QT_BEGIN_NAMESPACE -#if 0 -static bool qt_isQuadratic(const QBezier &b) -{ - const qreal f = 3.0 / 2.0; - const QPointF c1 = b.pt1() + f * (b.pt2() - b.pt1()); - const QPointF c2 = b.pt4() + f * (b.pt3() - b.pt4()); - return c1 == c2; -} -#endif - static qreal qt_scoreQuadratic(const QBezier &b, QPointF qcp) { - // Construct a cubic from the quadratic, and compare its control points to the originals' - const QRectF bounds = b.bounds(); - qreal dim = QLineF(bounds.topLeft(), bounds.bottomRight()).length(); - if (qFuzzyIsNull(dim)) - return 0; - const qreal f = 2.0 / 3; - const QPointF cp1 = b.pt1() + f * (qcp - b.pt1()); - const QPointF cp2 = b.pt4() + f * (qcp - b.pt4()); - const QLineF d1(b.pt2(), cp1); - const QLineF d2(b.pt3(), cp2); - return qMax(d1.length(), d2.length()) / dim; + static bool init = false; + const int numSteps = 21; + Q_STATIC_ASSERT(numSteps % 2 == 1); // numTries must be odd + static qreal t2s[numSteps]; + static qreal tmts[numSteps]; + if (!init) { + // Precompute bezier factors + qreal t = 0.20; + const qreal step = (1 - (2 * t)) / (numSteps - 1); + for (int i = 0; i < numSteps; i++) { + t2s[i] = t * t; + tmts[i] = 2 * t * (1 - t); + t += step; + } + init = true; + } + + const QPointF midPoint = b.midPoint(); + auto distForIndex = [&](int i) -> qreal { + QPointF qp = (t2s[numSteps - 1 - i] * b.pt1()) + (tmts[i] * qcp) + (t2s[i] * b.pt4()); + QPointF d = midPoint - qp; + return QPointF::dotProduct(d, d); + }; + + const int halfSteps = (numSteps - 1) / 2; + bool foundIt = false; + const qreal centerDist = distForIndex(halfSteps); + qreal minDist = centerDist; + // Search for the minimum in right half + for (int i = 0; i < halfSteps; i++) { + qreal tDist = distForIndex(halfSteps + 1 + i); + if (tDist < minDist) { + minDist = tDist; + } else { + foundIt = (i > 0); + break; + } + } + if (!foundIt) { + // Search in left half + minDist = centerDist; + for (int i = 0; i < halfSteps; i++) { + qreal tDist = distForIndex(halfSteps - 1 - i); + if (tDist < minDist) { + minDist = tDist; + } else { + foundIt = (i > 0); + break; + } + } + } + return foundIt ? minDist : centerDist; } -static qreal qt_quadraticForCubic(const QBezier &b, QPointF *qcp) +static QPointF qt_quadraticForCubic(const QBezier &b) { const QLineF st = b.startTangent(); const QLineF et = b.endTangent(); - if (st.intersects(et, qcp) == QLineF::NoIntersection) - *qcp = b.midPoint(); - return qt_scoreQuadratic(b, *qcp); + const QPointF midPoint = b.midPoint(); + bool valid = true; + QPointF quadControlPoint; + if (st.intersects(et, &quadControlPoint) == QLineF::NoIntersection) { + valid = false; + } else { + // Check if intersection is on wrong side + const QPointF bl = b.pt4() - b.pt1(); + const QPointF ml = midPoint - b.pt1(); + const QPointF ql = quadControlPoint - b.pt1(); + qreal cx1 = (ml.x() * bl.y()) - (ml.y() * bl.x()); + qreal cx2 = (ql.x() * bl.y()) - (ql.y() * bl.x()); + valid = (std::signbit(cx1) == std::signbit(cx2)); + } + return valid ? quadControlPoint : midPoint; } static int qt_getInflectionPoints(const QBezier &orig, qreal *tpoints) @@ -57,22 +100,34 @@ static int qt_getInflectionPoints(const QBezier &orig, qreal *tpoints) const QBezier n = orig.mapBy(xf); Q_ASSERT(n.pt1() == QPoint() && qFuzzyIsNull(float(n.pt4().y()))); - const qreal p = n.pt3().x() * n.pt2().y(); - const qreal q = n.pt4().x() * n.pt2().y(); - const qreal r = n.pt2().x() * n.pt3().y(); - const qreal s = n.pt4().x() * n.pt3().y(); - - const qreal a = 36 * ((-3 * p) + (2 * q) + (3 * r) - s); - if (!a) - return 0; - const qreal b = -18 * (((3 * p) - q) - (3 * r)); + const qreal x2 = n.pt2().x(); + const qreal x3 = n.pt3().x(); + const qreal x4 = n.pt4().x(); + const qreal y2 = n.pt2().y(); + const qreal y3 = n.pt3().y(); + + const qreal p = x3 * y2; + const qreal q = x4 * y2; + const qreal r = x2 * y3; + const qreal s = x4 * y3; + + const qreal a = 18 * ((-3 * p) + (2 * q) + (3 * r) - s); + if (qFuzzyIsNull(float(a))) { + if (std::signbit(y2) != std::signbit(y3) && qFuzzyCompare(float(x4 - x3), float(x2))) { + tpoints[0] = 0.5; // approx + return 1; + } else if (!a) { + return 0; + } + } + const qreal b = 18 * (((3 * p) - q) - (3 * r)); const qreal c = 18 * (r - p); - const qreal rad = (b * b) - (2 * a * c); + const qreal rad = (b * b) - (4 * a * c); if (rad < 0) return 0; const qreal sqr = qSqrt(rad); - const qreal root1 = (b + sqr) / a; - const qreal root2 = (b - sqr) / a; + const qreal root1 = (-b + sqr) / (2 * a); + const qreal root2 = (-b - sqr) / (2 * a); int res = 0; if (isValidRoot(root1)) @@ -86,54 +141,53 @@ static int qt_getInflectionPoints(const QBezier &orig, qreal *tpoints) return res; } -static void qt_addToQuadratics(const QBezier &b, QPolygonF *p, qreal spanlength, qreal errorLimit) +static void qt_addToQuadratics(const QBezier &b, QPolygonF *p, int maxSplits, qreal maxDiff) { - Q_ASSERT((spanlength > 0) && !(spanlength > 1)); - - QPointF qcp; - bool isOk = (qt_quadraticForCubic(b, &qcp) < errorLimit); // error limit, careful - if (isOk || spanlength < 0.1) { + QPointF qcp = qt_quadraticForCubic(b); + if (maxSplits <= 0 || qt_scoreQuadratic(b, qcp) < maxDiff) { p->append(qcp); p->append(b.pt4()); } else { QBezier rhs = b; QBezier lhs; rhs.parameterSplitLeft(0.5, &lhs); - qt_addToQuadratics(lhs, p, spanlength / 2, errorLimit); - qt_addToQuadratics(rhs, p, spanlength / 2, errorLimit); + qt_addToQuadratics(lhs, p, maxSplits - 1, maxDiff); + qt_addToQuadratics(rhs, p, maxSplits - 1, maxDiff); } } -QPolygonF qt_toQuadratics(const QBezier &b, qreal errorLimit) +void qt_toQuadratics(const QBezier &b, QPolygonF *out, qreal errorLimit) { + out->resize(0); + out->append(b.pt1()); + + { + // Shortcut if the cubic is really a quadratic + const qreal f = 3.0 / 2.0; + const QPointF c1 = b.pt1() + f * (b.pt2() - b.pt1()); + const QPointF c2 = b.pt4() + f * (b.pt3() - b.pt4()); + if (c1 == c2) { + out->append(c1); + out->append(b.pt4()); + return; + } + } - QPolygonF res; - res.reserve(16); - res.append(b.pt1()); const QRectF cpr = b.bounds(); - qreal epsilon = QLineF(cpr.topLeft(), cpr.bottomRight()).length() * 0.5 * errorLimit; - bool degenerate = false; - if (QLineF(b.pt2(), b.pt1()).length() < epsilon) { - res.append(b.pt3()); - degenerate = true; - } else if (QLineF(b.pt4(), b.pt3()).length() < epsilon) { - res.append(b.pt2()); - degenerate = true; - } - if (degenerate) { - res.append(b.pt4()); - return res; - } + const QPointF dim = cpr.bottomRight() - cpr.topLeft(); + qreal maxDiff = QPointF::dotProduct(dim, dim) * errorLimit * errorLimit; // maxdistance^2 + qreal infPoints[2]; int numInfPoints = qt_getInflectionPoints(b, infPoints); + const int maxSubSplits = numInfPoints > 0 ? 2 : 3; qreal t0 = 0; - for (int i = 0; i < numInfPoints + 1; i++) { // #segments == #inflectionpoints + 1 + // number of main segments == #inflectionpoints + 1 + for (int i = 0; i < numInfPoints + 1; i++) { qreal t1 = (i < numInfPoints) ? infPoints[i] : 1; QBezier segment = b.bezierOnInterval(t0, t1); - qt_addToQuadratics(segment, &res, t1 - t0, errorLimit); + qt_addToQuadratics(segment, out, maxSubSplits, maxDiff); t0 = t1; } - return res; } QT_END_NAMESPACE diff --git a/tests/manual/painterpathquickshape/CMakeLists.txt b/tests/manual/painterpathquickshape/CMakeLists.txt index a9616564a3..67f5b142ef 100644 --- a/tests/manual/painterpathquickshape/CMakeLists.txt +++ b/tests/manual/painterpathquickshape/CMakeLists.txt @@ -14,7 +14,6 @@ qt_internal_add_manual_test(painterPathQuickShape Qt::Quick Qt::QuickPrivate Qt::QuickShapesPrivate - Qt::SvgPrivate ) @@ -29,6 +28,7 @@ set(qml_resource_files "SmallPolygon.qml" "Squircle.qml" "ControlledShape.qml" + "Mussel.qml" "Graziano.ttf" "CubicShape.qml" "hand-print.svg" diff --git a/tests/manual/painterpathquickshape/ControlPanel.qml b/tests/manual/painterpathquickshape/ControlPanel.qml index 5276ec3a2d..1b34bb6eab 100644 --- a/tests/manual/painterpathquickshape/ControlPanel.qml +++ b/tests/manual/painterpathquickshape/ControlPanel.qml @@ -9,10 +9,13 @@ import QtQuick.Dialogs Item { property real scale: +scaleSlider.value.toFixed(4) - property color outlineColor: enableOutline.checked ? Qt.rgba(outlineColor.color.r, outlineColor.color.g, outlineColor.color.b, pathAlpha) : Qt.rgba(0,0,0,0) + property color backgroundColor: setBackground.checked ? Qt.rgba(bgColor.color.r, bgColor.color.g, bgColor.color.b, 1.0) : Qt.rgba(0,0,0,0) + + 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 outlineWidth: outlineWidth.value + property alias outlineAlpha: outlineAlphaSlider.value + property real outlineWidth: cosmeticPen.checked ? outlineWidth.value / scale : outlineWidth.value ** 2 property alias outlineStyle: outlineStyle.currentValue property alias capStyle: capStyle.currentValue property alias joinStyle: joinStyle.currentValue @@ -27,6 +30,7 @@ Item { property alias preferCurve: rendererLabel.preferCurve property int subShape: pickSubShape.checked ? subShapeSelector.value : -1 + property bool subShapeGreaterThan : pickSubShapeGreaterThan.checked property real pathMargin: marginEdit.text @@ -100,10 +104,10 @@ Item { text: "Alpha" color: "white" } - CheckBox { id: pickSubShape } - Label { + CheckBox { text: "Pick SVG sub-shape" - color: "white" + id: pickSubShape + palette.windowText: "white" } SpinBox { id: subShapeSelector @@ -112,6 +116,35 @@ Item { to: 999 editable: true } + CheckBox { + id: pickSubShapeGreaterThan + visible: pickSubShape.checked + text: "show greater than" + palette.windowText: "white" + } + CheckBox { + id: setBackground + text: "Solid background" + palette.windowText: "white" + } + RowLayout { + visible: setBackground.checked + Rectangle { + id: bgColor + property color selectedColor: "#a9a9a9" + color: selectedColor + border.color: "black" + border.width: 2 + width: 21 + height: 21 + MouseArea { + anchors.fill: parent + onClicked: { + bgColorDialog.open() + } + } + } + } } RowLayout { Label { @@ -256,7 +289,6 @@ Item { } } } - Label { text: "Outline width" color: "white" @@ -265,14 +297,35 @@ Item { id: outlineWidth Layout.fillWidth: true from: 0.0 - to: 100.0 - value: 10.0 + to: 10.0 + value: Math.sqrt(10) + } + CheckBox { + id: cosmeticPen + text: "Cosmetic pen" + palette.windowText: "white" + } + Label { + text: "Outline alpha" + color: "white" + } + Slider { + id: outlineAlphaSlider + Layout.fillWidth: true + from: 0.0 + to: 1.0 + value: 1.0 } } } } ColorDialog { + id: bgColorDialog + selectedColor: bgColor.selectedColor + onAccepted: bgColor.selectedColor = selectedColor + } + ColorDialog { id: outlineColorDialog selectedColor: outlineColor.selectedColor onAccepted: outlineColor.selectedColor = selectedColor diff --git a/tests/manual/painterpathquickshape/ControlPoint.qml b/tests/manual/painterpathquickshape/ControlPoint.qml index 190d759392..77e7e4fbff 100644 --- a/tests/manual/painterpathquickshape/ControlPoint.qml +++ b/tests/manual/painterpathquickshape/ControlPoint.qml @@ -19,16 +19,17 @@ Rectangle { property point pt: Qt.point(cx, cy) DragHandler { + id: handler xAxis.minimum: -controlPanel.pathMargin yAxis.minimum: -controlPanel.pathMargin - } - onXChanged: { - cx = (x + width/2) / controlPanel.scale - controlPanel.updatePath() - } - onYChanged: { - cy = (y + height/2) / controlPanel.scale - controlPanel.updatePath() + xAxis.onActiveValueChanged: { + cx = (x + width/2) / controlPanel.scale + controlPanel.updatePath() + } + yAxis.onActiveValueChanged: { + cy = (y + height/2) / controlPanel.scale + controlPanel.updatePath() + } } Component.onCompleted: { @@ -43,5 +44,4 @@ Rectangle { y = cy * controlPanel.scale - height/2 } } - } diff --git a/tests/manual/painterpathquickshape/ControlledShape.qml b/tests/manual/painterpathquickshape/ControlledShape.qml index 7cdc866fd3..cf9cbaa5d8 100644 --- a/tests/manual/painterpathquickshape/ControlledShape.qml +++ b/tests/manual/painterpathquickshape/ControlledShape.qml @@ -13,6 +13,7 @@ Item { property alias strokeColor: shapePath.strokeColor property alias strokeWidth: shapePath.strokeWidth property alias fillRule: shapePath.fillRule + property alias shapeTransform: shape.transform property alias startX: shapePath.startX property alias startY: shapePath.startY @@ -58,48 +59,48 @@ Item { property var gradients: [ null, linearGradient, radialGradient, conicalGradient ] - Shape { - id: shape - x: 0 - y: 0 - preferredRendererType: controlPanel.preferCurve ? Shape.CurveRenderer : Shape.UnknownRenderer - onRendererTypeChanged: { - controlPanel.rendererName = rendererType == Shape.SoftwareRenderer ? "Software" : - rendererType == Shape.GeometryRenderer ? "Geometry" : - rendererType == Shape.CurveRenderer ? "Curve" : "Unknown"; - } - + Item { transform: [ Scale { - xScale: controlPanel.scale - yScale: controlPanel.scale - origin.x: shape.implicitWidth / 2 - origin.y: shape.implicitHeight / 2 - } - ] - - ShapePath { - id: shapePath - fillRule: ShapePath.WindingFill - fillGradient: gradients[controlPanel.gradientType] - strokeColor: controlPanel.outlineColor - fillColor: controlPanel.fillColor - strokeWidth: controlPanel.outlineWidth - strokeStyle: controlPanel.outlineStyle - joinStyle: controlPanel.joinStyle - capStyle: controlPanel.capStyle - } + xScale: controlPanel.scale + yScale: controlPanel.scale + origin.x: shape.implicitWidth / 2 + origin.y: shape.implicitHeight / 2 + } + ] + Shape { + id: shape + x: 0 + y: 0 + preferredRendererType: controlPanel.preferCurve ? Shape.CurveRenderer : Shape.UnknownRenderer + onRendererTypeChanged: { + controlPanel.rendererName = rendererType == Shape.SoftwareRenderer ? "Software" : + rendererType == Shape.GeometryRenderer ? "Geometry" : + rendererType == Shape.CurveRenderer ? "Curve" : "Unknown"; + } + + ShapePath { + id: shapePath + fillRule: ShapePath.WindingFill + fillGradient: gradients[controlPanel.gradientType] + strokeColor: controlPanel.outlineColor + fillColor: controlPanel.fillColor + strokeWidth: controlPanel.outlineWidth + strokeStyle: controlPanel.outlineStyle + joinStyle: controlPanel.joinStyle + capStyle: controlPanel.capStyle + } - Repeater { - model: topLevel.delegate - onModelChanged: { - shapePath.pathElements = [] - for (var i = 0; i < model.length; ++i) - shapePath.pathElements.push(model[i]) + Repeater { + model: topLevel.delegate + onModelChanged: { + shapePath.pathElements = [] + for (var i = 0; i < model.length; ++i) + shapePath.pathElements.push(model[i]) + } } } } - Connections { target: controlPanel function onPathChanged() { diff --git a/tests/manual/painterpathquickshape/Mussel.qml b/tests/manual/painterpathquickshape/Mussel.qml new file mode 100644 index 0000000000..5b72d1054d --- /dev/null +++ b/tests/manual/painterpathquickshape/Mussel.qml @@ -0,0 +1,42 @@ +// 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: p1.cx; y: p1.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 }, + PathLine { x: p1.cx; y: p1.cy } + ] + + ControlPoint { + id: p1 + cx: 200 + cy: 200 + } + ControlPoint { + id: c1 + color: "blue" + cx: 600 + cy: 0 + } + ControlPoint { + id: p2 + cx: 1000 + cy: 200 + } + ControlPoint { + id: c2 + color: "blue" + cx: 1000 + cy: 1000 + } + ControlPoint { + id: p3 + cx: 200 + cy: 1000 + } +} diff --git a/tests/manual/painterpathquickshape/SvgShape.qml b/tests/manual/painterpathquickshape/SvgShape.qml index cf27706e88..697ede2524 100644 --- a/tests/manual/painterpathquickshape/SvgShape.qml +++ b/tests/manual/painterpathquickshape/SvgShape.qml @@ -40,19 +40,24 @@ Item { children = [] let first = true - let pickOne = controlPanel.subShape - if (pickOne < 0) - console.debug("Creating " + pathLoader.paths.length + " SVG items") + let pickShape = controlPanel.subShape + let pickOne = pickShape >= 0 && !controlPanel.subShapeGreaterThan + let pickGreater = pickShape >= 0 && controlPanel.subShapeGreaterThan + if (pickOne) + console.log("Creating SVG item", pickShape, "out of", pathLoader.paths.length) + else if (pickGreater) + console.debug("Creating " + (pathLoader.paths.length - pickShape) + " SVG items") else - console.log("Creating SVG item", pickOne, "out of", pathLoader.paths.length) + console.debug("Creating " + pathLoader.paths.length + " SVG items") for (var i = 0; i < pathLoader.paths.length; ++i) { - if (pickOne >= 0 && pickOne !== i) + if ((pickOne && pickShape !== i ) || (pickGreater && i < pickShape)) continue var s = pathLoader.paths[i] var fillColor = pathLoader.fillColors[i] let strokeText = ""; let strokeColor = pathLoader.strokeColors[i] let strokeWidth = pathLoader.strokeWidths[i] + let transform = pathLoader.transforms[i] if (strokeColor) { if (!strokeWidth) strokeWidth = "1.0" // default value defined by SVG standard @@ -62,10 +67,11 @@ Item { fillColor = "#00000000" } - var obj = Qt.createQmlObject("import QtQuick\nimport QtQuick.Shapes\n ControlledShape { " - + "fillColor: \"" + fillColor + "\";" - + strokeText - + "fillRule: ShapePath.WindingFill; delegate: [ PathSvg { path: \"" + s + "\"; } ] }", + var obj = Qt.createQmlObject("import QtQuick\nimport QtQuick.Shapes\n ControlledShape { \n" + + "fillColor: \"" + fillColor + "\";\n" + + "shapeTransform: Matrix4x4 { matrix: Qt.matrix4x4(" + transform + "); }\n" + + strokeText + "\n" + + "fillRule: ShapePath.WindingFill; delegate: [ PathSvg { path: \"" + s + "\"; } ] }\n", topLevel, "SvgPathComponent_" + i) diff --git a/tests/manual/painterpathquickshape/main.qml b/tests/manual/painterpathquickshape/main.qml index 45651f870f..9ad5d1f1a4 100644 --- a/tests/manual/painterpathquickshape/main.qml +++ b/tests/manual/painterpathquickshape/main.qml @@ -42,6 +42,10 @@ Window { source: "CubicShape.qml" } ListElement { + text: "Mussel" + source: "Mussel.qml" + } + ListElement { text: "Arc Direction" source: "arcDirection.qml" } @@ -138,6 +142,11 @@ Window { source: "qrc:/background.png" smooth: true } + Rectangle { + id: solidBackground + anchors.fill: flickable + color: controlPanel.backgroundColor + } Flickable { id: flickable @@ -152,10 +161,9 @@ Window { WheelHandler { onWheel: (event)=> { let scale = controlPanel.scale - let posX = event.x - let posY = event.y - let xOff = posX - flickable.contentX - let yOff = posY - flickable.contentY + // position in scaled path: + let posX = event.x - controlPanel.pathMargin + let posY = event.y - controlPanel.pathMargin let pathX = posX / scale let pathY = posY / scale @@ -166,8 +174,12 @@ Window { scale = scale / 1.1 controlPanel.setScale(scale) - flickable.contentX = pathX * controlPanel.scale - xOff - flickable.contentY = pathY * controlPanel.scale - yOff + scale = controlPanel.scale + let scaledPosX = pathX * scale + let scaledPosY = pathY * scale + + flickable.contentX += scaledPosX - posX + flickable.contentY += scaledPosY - posY flickable.returnToBounds() } } diff --git a/tests/manual/painterpathquickshape/svgpathloader.cpp b/tests/manual/painterpathquickshape/svgpathloader.cpp index 22dfbfba1b..612d00e7d2 100644 --- a/tests/manual/painterpathquickshape/svgpathloader.cpp +++ b/tests/manual/painterpathquickshape/svgpathloader.cpp @@ -5,8 +5,11 @@ #include <QFile> #include <QPainterPath> -#include <QtSvg/private/qsvgtinydocument_p.h> -#include <QtSvg/private/qsvggraphics_p.h> +#include <QXmlStreamReader> +#include <QXmlStreamAttributes> +#include <QStack> +#include <QLocale> +#include <QMatrix4x4> SvgPathLoader::SvgPathLoader() { @@ -20,6 +23,7 @@ struct SvgState QString fillColor = {}; QString strokeColor = {}; QString strokeWidth = {}; + QMatrix4x4 transform; }; void SvgPathLoader::loadPaths() @@ -28,6 +32,7 @@ void SvgPathLoader::loadPaths() m_fillColors.clear(); m_strokeColors.clear(); m_strokeWidths.clear(); + m_transforms.clear(); if (m_source.isEmpty()) return; @@ -49,8 +54,50 @@ void SvgPathLoader::loadPaths() QXmlStreamAttributes attrs = reader.attributes(); if (reader.isStartElement()) states.push(currentState); + + if (attrs.hasAttribute(QStringLiteral("transform"))) { + QString t = attrs.value(QStringLiteral("transform")).toString(); + const bool isTranslate = t.startsWith(QStringLiteral("translate")); + const bool isScale = t.startsWith(QStringLiteral("scale")); + const bool isMatrix = t.startsWith(QStringLiteral("matrix")); + if (isTranslate || isScale || isMatrix) { + int pStart = t.indexOf(QLatin1Char('(')); + int pEnd = t.indexOf(QLatin1Char(')')); + if (pStart >= 0 && pEnd > pStart + 1) { + t = t.mid(pStart + 1, pEnd - pStart - 1); + QStringList coords = t.split(QLatin1Char(',')); + if (isMatrix && coords.size() == 6) { + QMatrix3x3 m; + m(0, 0) = coords.at(0).toDouble(); + m(1, 0) = coords.at(1).toDouble(); + m(2, 0) = 0.0f; + + m(0, 1) = coords.at(2).toDouble(); + m(1, 1) = coords.at(3).toDouble(); + m(2, 1) = 0.0f; + + m(0, 2) = coords.at(4).toDouble(); + m(1, 2) = coords.at(5).toDouble(); + m(2, 2) = 1.0f; + + currentState.transform *= QMatrix4x4(m); + } else if (coords.size() == 2) { + qreal c1 = coords.first().toDouble(); + qreal c2 = coords.last().toDouble(); + + if (isTranslate) + currentState.transform.translate(c1, c2); + else if (isScale) + currentState.transform.scale(c1, c2); + } + } + } + } + if (attrs.hasAttribute(QStringLiteral("fill"))) { currentState.fillColor = attrs.value(QStringLiteral("fill")).toString(); + if (!currentState.fillColor.startsWith("#")) + currentState.fillColor = ""; } else if (attrs.hasAttribute(QStringLiteral("style"))) { QString s = attrs.value(QStringLiteral("style")).toString(); int idx = s.indexOf(QStringLiteral("fill:")); @@ -73,6 +120,22 @@ void SvgPathLoader::loadPaths() m_fillColors.append(currentState.fillColor); m_strokeColors.append(currentState.strokeColor); m_strokeWidths.append(currentState.strokeWidth); + + QString t; + for (int i = 0; i < 4; ++i) { + if (i > 0) + t += QLatin1Char(','); + QVector4D row = currentState.transform.row(i); + + QLocale c(QLocale::C); + t += QStringLiteral("%1, %2, %3, %4") + .arg(c.toString(row.x())) + .arg(c.toString(row.y())) + .arg(c.toString(row.z())) + .arg(c.toString(row.w())); + } + + m_transforms.append(t); if (attrs.hasAttribute(QStringLiteral("d"))) { m_paths.append(attrs.value(QStringLiteral("d")).toString()); } diff --git a/tests/manual/painterpathquickshape/svgpathloader.h b/tests/manual/painterpathquickshape/svgpathloader.h index 28cd1b76bd..5fd444da2f 100644 --- a/tests/manual/painterpathquickshape/svgpathloader.h +++ b/tests/manual/painterpathquickshape/svgpathloader.h @@ -17,6 +17,7 @@ class SvgPathLoader : public QObject Q_PROPERTY(QStringList fillColors READ fillColors NOTIFY pathsChanged) Q_PROPERTY(QStringList strokeColors READ strokeColors NOTIFY pathsChanged) Q_PROPERTY(QStringList strokeWidths READ strokeWidths NOTIFY pathsChanged) + Q_PROPERTY(QStringList transforms READ transforms NOTIFY pathsChanged) public: SvgPathLoader(); @@ -53,6 +54,11 @@ public: return m_strokeWidths; } + QStringList transforms() const + { + return m_transforms; + } + private slots: void loadPaths(); @@ -66,6 +72,7 @@ private: QStringList m_fillColors; QStringList m_strokeColors; QStringList m_strokeWidths; + QStringList m_transforms; }; #endif // SVGPATHLOADER_H |