Detect and remove self intersections of QQuadPath

Currently the CurveRenderer is not working when the path is
self-intersecting.

With this patch, the self-intersections are removed before the
path is used for filling (optionally, default: on) The stroking
path is untouched.

The function findOverlappingCandidates finds candidates of elements
that might be intersecting. Its complexity is O(n log n) and can
also be used in other parts of the code where overlapping bounding
triangles need to be identified.

The function solveIntersections removes all intersections from
a QQuadPath. If intersections are solved, the path is oriented such
that the filling is on the right side of the path. If no intersections
are found, the path is returned without any changes. The optional
argument alwaysReorder can be used to force a reordering of the paths,
such that the filling of the shape is always on the right side of the
path.

Intersections are found with Newtons algorithm with 9 different
starting values. This is reliable in finding all intersections but
the starting values could be improved/reduced to improve performance.

Pick-to: 6.7
Change-Id: I088e4edfff755155521ed91114bc67f63c6e546a
Reviewed-by: Paul Olav Tvete <paul.tvete@qt.io>

6 files changed, 293 insertions, 1 deletions

diff --git a/tests/manual/painterpathquickshape/CMakeLists.txt b/tests/manual/painterpathquickshape/CMakeLists.txt
index 1f92afaba5..4677fad26c 100644
--- a/tests/manual/painterpathquickshape/CMakeLists.txt
+++ b/tests/manual/painterpathquickshape/CMakeLists.txt
@@ -36,6 +36,8 @@ set(qml_resource_files
     "SimpleShape.qml"
     "SmallPolygon.qml"
     "Squircle.qml"
+    "Intersect.qml"
+    "Intersect2.qml"
     "ControlledShape.qml"
     "Mussel.qml"
     "Graziano.ttf"
diff --git a/tests/manual/painterpathquickshape/ControlPanel.qml b/tests/manual/painterpathquickshape/ControlPanel.qml
index bb26e658f3..3fbe33968f 100644
--- a/tests/manual/painterpathquickshape/ControlPanel.qml
+++ b/tests/manual/painterpathquickshape/ControlPanel.qml
@@ -15,6 +15,7 @@ Item {
     property color outlineColor: enableOutline.checked ? Qt.rgba(outlineColor.color.r, outlineColor.color.g, outlineColor.color.b, outlineAlpha) : Qt.rgba(0,0,0,0)
     property color fillColor: Qt.rgba(fillColor.color.r, fillColor.color.g, fillColor.color.b, pathAlpha)
     property alias pathAlpha: alphaSlider.value
+    property alias fillRule: fillRule.currentValue
     property alias outlineAlpha: outlineAlphaSlider.value
     property real outlineWidth: cosmeticPen.checked ? outlineWidthEdit.text / scale : outlineWidthEdit.text
     property alias outlineStyle: outlineStyle.currentValue
@@ -46,6 +47,7 @@ Item {
         property alias cosmeticPen: cosmeticPen.checked
 
         property alias pathAlpha: alphaSlider.value
+        property alias fillRule: fillRule.currentIndex
         property alias fillColor: fillColor.color
 
         property alias setBackground: setBackground.checked
@@ -218,6 +220,25 @@ Item {
                 model: [ "NoGradient", "LinearGradient", "RadialGradient", "ConicalGradient" ]
             }
             Label {
+                text: "Fill rule:"
+                color: "white"
+            }
+            ComboBox {
+                id: fillRule
+                textRole: "text"
+                valueRole: "style"
+                model: ListModel {
+                    ListElement {
+                        text: "WindingFill"
+                        style: ShapePath.WindingFill
+                    }
+                    ListElement {
+                        text: "OddEvenFill"
+                        style: ShapePath.OddEvenFill
+                    }
+                }
+            }
+            Label {
                 text: "Fill alpha(" + Math.round(alphaSlider.value*100)/100 + "):"
                 color: "white"
             }
diff --git a/tests/manual/painterpathquickshape/ControlledShape.qml b/tests/manual/painterpathquickshape/ControlledShape.qml
index db8333c2e2..087c4084dd 100644
--- a/tests/manual/painterpathquickshape/ControlledShape.qml
+++ b/tests/manual/painterpathquickshape/ControlledShape.qml
@@ -81,7 +81,7 @@ Item {
 
             ShapePath {
                 id: shapePath
-                fillRule: ShapePath.WindingFill
+                fillRule: controlPanel.fillRule
                 fillGradient: gradients[controlPanel.gradientType]
                 strokeColor: controlPanel.outlineColor
                 fillColor: controlPanel.fillColor
diff --git a/tests/manual/painterpathquickshape/Intersect.qml b/tests/manual/painterpathquickshape/Intersect.qml
new file mode 100644
index 0000000000..ed1156f388
--- /dev/null
+++ b/tests/manual/painterpathquickshape/Intersect.qml
@@ -0,0 +1,125 @@
+// Copyright (C) 2023 The Qt Company Ltd.
+// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR BSD-3-Clause
+
+import QtQuick
+import QtQuick.Shapes
+
+ControlledShape {
+    delegate: [
+        PathMove { x: p0.cx; y: p0.cy },
+        PathQuad { x: p1.cx; y: p1.cy; controlX: c0.cx; controlY: c0.cy },
+        PathQuad { x: p2.cx; y: p2.cy; controlX: c1.cx; controlY: c1.cy },
+        PathQuad { x: p3.cx; y: p3.cy; controlX: c2.cx; controlY: c2.cy },
+        PathQuad { x: p0.cx; y: p0.cy; controlX: c3.cx; controlY: c3.cy },
+        PathMove { x: p4.cx; y: p4.cy; },
+        PathLine { x: p5.cx; y: p5.cy; },
+        PathLine { x: p6.cx; y: p6.cy; },
+        PathLine { x: p7.cx; y: p7.cy; },
+        PathLine { x: p4.cx; y: p4.cy; }
+    ]
+
+    ControlPoint {
+        id: p0
+        cx: 200
+        cy: 200
+    }
+    ControlPoint {
+        id: c0
+        color: "blue"
+        cx: 600
+        cy: 1000
+    }
+    ControlPoint {
+        id: p1
+        cx: 1000
+        cy: 200
+    }
+    ControlPoint {
+        id: c1
+        color: "blue"
+        cx: -100
+        cy: 200
+    }
+    ControlPoint {
+        id: p2
+        color: "red"
+        cx: 200
+        cy: 1000
+    }
+    ControlPoint {
+        id: c2
+        color: "blue"
+        cx: -100
+        cy: 1000
+    }
+    ControlPoint {
+        id: p3
+        color: "red"
+        cx: -100
+        cy: 500
+    }
+    ControlPoint {
+        id: c3
+        color: "blue"
+        cx: -300
+        cy: 200
+    }
+
+    ControlPoint {
+        id: p4
+        color: "green"
+        cx: 2000
+        cy: 200
+    }
+    ControlPoint {
+        id: p5
+        color: "green"
+        cx: 2500
+        cy: 700
+    }
+    ControlPoint {
+        id: p6
+        color: "green"
+        cx: 2000
+        cy: 700
+    }
+    ControlPoint {
+        id: p7
+        color: "green"
+        cx: 2500
+        cy: 200
+    }
+
+    Text {
+        anchors.centerIn: p0
+        text: "p0"
+    }
+    Text {
+        anchors.centerIn: p1
+        text: "p1"
+    }
+    Text {
+        anchors.centerIn: p2
+        text: "p2"
+    }
+    Text {
+        anchors.centerIn: p3
+        text: "p3"
+    }
+    Text {
+        anchors.centerIn: c0
+        text: "c0"
+    }
+    Text {
+        anchors.centerIn: c1
+        text: "c1"
+    }
+    Text {
+        anchors.centerIn: c2
+        text: "c2"
+    }
+    Text {
+        anchors.centerIn: c3
+        text: "c3"
+    }
+}
diff --git a/tests/manual/painterpathquickshape/Intersect2.qml b/tests/manual/painterpathquickshape/Intersect2.qml
new file mode 100644
index 0000000000..408eaa1afb
--- /dev/null
+++ b/tests/manual/painterpathquickshape/Intersect2.qml
@@ -0,0 +1,136 @@
+// Copyright (C) 2023 The Qt Company Ltd.
+// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR BSD-3-Clause
+
+import QtQuick
+import QtQuick.Shapes
+
+ControlledShape {
+    delegate: [
+        PathMove { x: p0.cx; y: p0.cy },
+        PathQuad { x: p1.cx; y: p1.cy; controlX: c0.cx; controlY: c0.cy },
+        PathQuad { x: p2.cx; y: p2.cy; controlX: c1.cx; controlY: c1.cy },
+        PathQuad { x: p0.cx; y: p0.cy; controlX: c2.cx; controlY: c2.cy },
+        PathMove { x: p3.cx; y: p3.cy },
+        PathQuad { x: p4.cx; y: p4.cy; controlX: c3.cx; controlY: c3.cy },
+        PathQuad { x: p5.cx; y: p5.cy; controlX: c4.cx; controlY: c4.cy },
+        PathQuad { x: p3.cx; y: p3.cy; controlX: c5.cx; controlY: c5.cy }
+    ]
+
+    ControlPoint {
+        id: p0
+        cx: 600
+        cy: 200
+    }
+    ControlPoint {
+        id: c0
+        color: "blue"
+        cx: 1000
+        cy: 600
+    }
+    ControlPoint {
+        id: p1
+        cx: 600
+        cy: 1000
+    }
+    ControlPoint {
+        id: c1
+        color: "blue"
+        cx: 200
+        cy: 1200
+    }
+    ControlPoint {
+        id: p2
+        cx: 200
+        cy: 600
+    }
+    ControlPoint {
+        id: c2
+        color: "blue"
+        cx: 200
+        cy: 200
+    }
+
+    ControlPoint {
+        id: p3
+        cx: 1000
+        cy: 200
+    }
+    ControlPoint {
+        id: c3
+        color: "blue"
+        cx: 1400
+        cy: 600
+    }
+    ControlPoint {
+        id: p4
+        cx: 1000
+        cy: 1000
+    }
+    ControlPoint {
+        id: c4
+        color: "blue"
+        cx: 600
+        cy: 1200
+    }
+    ControlPoint {
+        id: p5
+        cx: 600
+        cy: 600
+    }
+    ControlPoint {
+        id: c5
+        color: "blue"
+        cx: 200
+        cy: -200
+    }
+
+
+    Text {
+        anchors.centerIn: p0
+        text: "p0"
+    }
+    Text {
+        anchors.centerIn: p1
+        text: "p1"
+    }
+    Text {
+        anchors.centerIn: p2
+        text: "p2"
+    }
+    Text {
+        anchors.centerIn: p3
+        text: "p3"
+    }
+    Text {
+        anchors.centerIn: p4
+        text: "p4"
+    }
+    Text {
+        anchors.centerIn: p5
+        text: "p5"
+    }
+    Text {
+        anchors.centerIn: c0
+        text: "c0"
+    }
+    Text {
+        anchors.centerIn: c1
+        text: "c1"
+    }
+    Text {
+        anchors.centerIn: c2
+        text: "c2"
+    }
+    Text {
+        anchors.centerIn: c3
+        text: "c3"
+    }
+    Text {
+        anchors.centerIn: c4
+        text: "c4"
+    }
+    Text {
+        anchors.centerIn: c5
+        text: "c5"
+    }
+}
diff --git a/tests/manual/painterpathquickshape/main.qml b/tests/manual/painterpathquickshape/main.qml
index 36dae42639..9a5efa4ec8 100644
--- a/tests/manual/painterpathquickshape/main.qml
+++ b/tests/manual/painterpathquickshape/main.qml
@@ -40,6 +40,14 @@ Window {
             source: "Squircle.qml"
         }
         ListElement {
+            text: "Intersect"
+            source: "Intersect.qml"
+        }
+        ListElement {
+            text: "Intersect2"
+            source: "Intersect2.qml"
+        }
+        ListElement {
             text: "CubicShape"
             source: "CubicShape.qml"
         }