Support buffering SystemDependent GraphicData (III)

This change is for speedup of fat line drawing when using
X11. This is a long-term problem which never really progressed,
but is avoided using Cairo in the future. Still - if used,
speedup using current state and buffering possibilities.

Two speedup steps will be used:
(1) The tesselation is no longer done using trapezoids. That
works (but was done wrong leaving artifacts) but is not fast
and done every time. It is even not done with FatLines and
more than 1000 points.
New version will use triangulation. Dspite using the existing
triangulator (that works but is slow) extend the FatLine
geometry creator to directly create triangles.
This is also necessary since for buffering that data a
transformation-invariant version is needed (in device coordinates
the data changes all the time when scrolling). Trapezoids are
by definition *not* transformation-invariant (e.g. rotation)

(2) Buffer that triangulation - with the needed care and watch.
It is e.g. necessary to react on 'hairlines' since these change
their logical LineWidth view-dependent (zoom). In those cases, the
buffered data *has* to be removed due to the base for buffering is
the created FatLine geometry based on one stable logical LineWidth

Also took the time to adapt B2DPolygonTriangulator to use an
own data type (B2DTriangle) and a vector of these for better
understandability and security. Adapted all usages as needed.

Change-Id: Iedb2932b094a8786fd9c32d0d0ab1ca603a1a7b2
Reviewed-on: https://gerrit.libreoffice.org/60818
Tested-by: Jenkins
Reviewed-by: Armin Le Grand <Armin.Le.Grand@cib.de>

3 files changed, 129 insertions, 37 deletions

diff --git a/basegfx/source/polygon/b2dlinegeometry.cxx b/basegfx/source/polygon/b2dlinegeometry.cxx
index ca4b88238383..78f569970df3 100644
--- a/basegfx/source/polygon/b2dlinegeometry.cxx
+++ b/basegfx/source/polygon/b2dlinegeometry.cxx
@@ -30,6 +30,7 @@
 #include <basegfx/matrix/b2dhommatrixtools.hxx>
 #include <com/sun/star/drawing/LineCap.hpp>
 #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
+#include <basegfx/polygon/b2dpolygontriangulator.hxx>
 
 namespace basegfx
 {
@@ -337,7 +338,8 @@ namespace basegfx
             bool bStartRound,
             bool bEndRound,
             bool bStartSquare,
-            bool bEndSquare)
+            bool bEndSquare,
+            basegfx::triangulator::B2DTriangleVector* pTriangles)
         {
             // create polygon for edge
             // Unfortunately, while it would be geometrically correct to not add
@@ -566,6 +568,15 @@ namespace basegfx
                     }
                 }
 
+                if(nullptr != pTriangles)
+                {
+                    const basegfx::triangulator::B2DTriangleVector aResult(
+                        basegfx::triangulator::triangulate(
+                            aBezierPolygon));
+                    pTriangles->insert(pTriangles->end(), aResult.begin(), aResult.end());
+                    aBezierPolygon.clear();
+                }
+
                 // return
                 return aBezierPolygon;
             }
@@ -664,6 +675,15 @@ namespace basegfx
                 // close and return
                 aEdgePolygon.setClosed(true);
 
+                if(nullptr != pTriangles)
+                {
+                    const basegfx::triangulator::B2DTriangleVector aResult(
+                        basegfx::triangulator::triangulate(
+                            aEdgePolygon));
+                    pTriangles->insert(pTriangles->end(), aResult.begin(), aResult.end());
+                    aEdgePolygon.clear();
+                }
+
                 return aEdgePolygon;
             }
         }
@@ -676,7 +696,8 @@ namespace basegfx
             const B2DPoint& rPoint,
             double fHalfLineWidth,
             B2DLineJoin eJoin,
-            double fMiterMinimumAngle)
+            double fMiterMinimumAngle,
+            basegfx::triangulator::B2DTriangleVector* pTriangles)
         {
             OSL_ENSURE(fHalfLineWidth > 0.0, "createAreaGeometryForJoin: LineWidth too small (!)");
             OSL_ENSURE(eJoin != B2DLineJoin::NONE, "createAreaGeometryForJoin: B2DLineJoin::NONE not allowed (!)");
@@ -703,9 +724,19 @@ namespace basegfx
             {
                 case B2DLineJoin::Miter :
                 {
-                    aEdgePolygon.append(aEndPoint);
-                    aEdgePolygon.append(rPoint);
-                    aEdgePolygon.append(aStartPoint);
+                    if(nullptr != pTriangles)
+                    {
+                        pTriangles->emplace_back(
+                            aEndPoint,
+                            rPoint,
+                            aStartPoint);
+                    }
+                    else
+                    {
+                        aEdgePolygon.append(aEndPoint);
+                        aEdgePolygon.append(rPoint);
+                        aEdgePolygon.append(aStartPoint);
+                    }
 
                     // Look for the cut point between start point along rTangentPrev and
                     // end point along rTangentEdge. -rTangentEdge should be used, but since
@@ -718,7 +749,18 @@ namespace basegfx
                     if(fCutPos != 0.0)
                     {
                         const B2DPoint aCutPoint(aStartPoint + (rTangentPrev * fCutPos));
-                        aEdgePolygon.append(aCutPoint);
+
+                        if(nullptr != pTriangles)
+                        {
+                            pTriangles->emplace_back(
+                                aStartPoint,
+                                aCutPoint,
+                                aEndPoint);
+                        }
+                        else
+                        {
+                            aEdgePolygon.append(aCutPoint);
+                        }
                     }
 
                     break;
@@ -744,14 +786,27 @@ namespace basegfx
 
                     if(aBow.count() > 1)
                     {
-                        // #i101491#
-                        // use the original start/end positions; the ones from bow creation may be numerically
-                        // different due to their different creation. To guarantee good merging quality with edges
-                        // and edge roundings (and to reduce point count)
-                        aEdgePolygon = aBow;
-                        aEdgePolygon.setB2DPoint(0, aStartPoint);
-                        aEdgePolygon.setB2DPoint(aEdgePolygon.count() - 1, aEndPoint);
-                        aEdgePolygon.append(rPoint);
+                        if(nullptr != pTriangles)
+                        {
+                            for(sal_uInt32 a(0); a < aBow.count() - 1; a++)
+                            {
+                                pTriangles->emplace_back(
+                                    0 == a ? aStartPoint : aBow.getB2DPoint(a),
+                                    rPoint,
+                                    aBow.count() - 1 == a + 1 ? aEndPoint : aBow.getB2DPoint(a + 1));
+                            }
+                        }
+                        else
+                        {
+                            // #i101491#
+                            // use the original start/end positions; the ones from bow creation may be numerically
+                            // different due to their different creation. To guarantee good merging quality with edges
+                            // and edge roundings (and to reduce point count)
+                            aEdgePolygon = aBow;
+                            aEdgePolygon.setB2DPoint(0, aStartPoint);
+                            aEdgePolygon.setB2DPoint(aEdgePolygon.count() - 1, aEndPoint);
+                            aEdgePolygon.append(rPoint);
+                        }
 
                         break;
                     }
@@ -762,9 +817,19 @@ namespace basegfx
                 }
                 default: // B2DLineJoin::Bevel
                 {
-                    aEdgePolygon.append(aEndPoint);
-                    aEdgePolygon.append(rPoint);
-                    aEdgePolygon.append(aStartPoint);
+                    if(nullptr != pTriangles)
+                    {
+                        pTriangles->emplace_back(
+                            aEndPoint,
+                            rPoint,
+                            aStartPoint);
+                    }
+                    else
+                    {
+                        aEdgePolygon.append(aEndPoint);
+                        aEdgePolygon.append(rPoint);
+                        aEdgePolygon.append(aStartPoint);
+                    }
 
                     break;
                 }
@@ -786,7 +851,8 @@ namespace basegfx
             css::drawing::LineCap eCap,
             double fMaxAllowedAngle,
             double fMaxPartOfEdge,
-            double fMiterMinimumAngle)
+            double fMiterMinimumAngle,
+            basegfx::triangulator::B2DTriangleVector* pTriangles)
         {
             if(fMaxAllowedAngle > F_PI2)
             {
@@ -895,7 +961,8 @@ namespace basegfx
                                         aEdge.getStartPoint(),
                                         fHalfLineWidth,
                                         eJoin,
-                                        fMiterMinimumAngle));
+                                        fMiterMinimumAngle,
+                                        pTriangles));
                             }
                             else if(aOrientation == B2VectorOrientation::Negative)
                             {
@@ -911,7 +978,8 @@ namespace basegfx
                                         aEdge.getStartPoint(),
                                         fHalfLineWidth,
                                         eJoin,
-                                        fMiterMinimumAngle));
+                                        fMiterMinimumAngle,
+                                        pTriangles));
                             }
                         }
 
@@ -929,7 +997,8 @@ namespace basegfx
                                     bFirst && eCap == css::drawing::LineCap_ROUND,
                                     bLast && eCap == css::drawing::LineCap_ROUND,
                                     bFirst && eCap == css::drawing::LineCap_SQUARE,
-                                    bLast && eCap == css::drawing::LineCap_SQUARE));
+                                    bLast && eCap == css::drawing::LineCap_SQUARE,
+                                    pTriangles));
                         }
                         else
                         {
@@ -940,7 +1009,8 @@ namespace basegfx
                                     false,
                                     false,
                                     false,
-                                    false));
+                                    false,
+                                    pTriangles));
                         }
 
                         // prepare next step
@@ -958,10 +1028,22 @@ namespace basegfx
                 else
                 {
                     // point count, but no edge count -> single point
-                    aRetval.append(
+                    const basegfx::B2DPolygon aCircle(
                         createPolygonFromCircle(
                             aCandidate.getB2DPoint(0),
                             fHalfLineWidth));
+
+                    if(nullptr != pTriangles)
+                    {
+                        const basegfx::triangulator::B2DTriangleVector aResult(
+                            basegfx::triangulator::triangulate(
+                                aCircle));
+                        pTriangles->insert(pTriangles->end(), aResult.begin(), aResult.end());
+                    }
+                    else
+                    {
+                        aRetval.append(aCircle);
+                    }
                 }
 
                 return aRetval;
diff --git a/basegfx/source/polygon/b2dpolygontools.cxx b/basegfx/source/polygon/b2dpolygontools.cxx
index b5d2abf7e4be..27bfa56d8ced 100644
--- a/basegfx/source/polygon/b2dpolygontools.cxx
+++ b/basegfx/source/polygon/b2dpolygontools.cxx
@@ -2133,7 +2133,9 @@ namespace basegfx
             return ((fCrossA > 0.0) == (fCrossB > 0.0));
         }
 
-        void addTriangleFan(const B2DPolygon& rCandidate, B2DPolygon& rTarget)
+        void addTriangleFan(
+            const B2DPolygon& rCandidate,
+            triangulator::B2DTriangleVector& rTarget)
         {
             const sal_uInt32 nCount(rCandidate.count());
 
@@ -2145,9 +2147,10 @@ namespace basegfx
                 for(sal_uInt32 a(2); a < nCount; a++)
                 {
                     const B2DPoint aCurrent(rCandidate.getB2DPoint(a));
-                    rTarget.append(aStart);
-                    rTarget.append(aLast);
-                    rTarget.append(aCurrent);
+                    rTarget.emplace_back(
+                        aStart,
+                        aLast,
+                        aCurrent);
 
                     // prepare next
                     aLast = aCurrent;
diff --git a/basegfx/source/polygon/b2dpolygontriangulator.cxx b/basegfx/source/polygon/b2dpolygontriangulator.cxx
index ab97419144d4..c24a78f579b8 100644
--- a/basegfx/source/polygon/b2dpolygontriangulator.cxx
+++ b/basegfx/source/polygon/b2dpolygontriangulator.cxx
@@ -110,7 +110,7 @@ namespace basegfx
             EdgeEntry*                                      mpList;
             EdgeEntries                                     maStartEntries;
             std::vector< std::unique_ptr<EdgeEntry> >       maNewEdgeEntries;
-            B2DPolygon                                      maResult;
+            triangulator::B2DTriangleVector                 maResult;
 
             void handleClosingEdge(const B2DPoint& rStart, const B2DPoint& rEnd);
             bool CheckPointInTriangle(EdgeEntry* pEdgeA, EdgeEntry const * pEdgeB, const B2DPoint& rTestPoint);
@@ -119,7 +119,7 @@ namespace basegfx
         public:
             explicit Triangulator(const B2DPolyPolygon& rCandidate);
 
-            const B2DPolygon& getResult() const { return maResult; }
+            const triangulator::B2DTriangleVector& getResult() const { return maResult; }
         };
 
         void Triangulator::handleClosingEdge(const B2DPoint& rStart, const B2DPoint& rEnd)
@@ -203,9 +203,10 @@ namespace basegfx
 
         void Triangulator::createTriangle(const B2DPoint& rA, const B2DPoint& rB, const B2DPoint& rC)
         {
-            maResult.append(rA);
-            maResult.append(rB);
-            maResult.append(rC);
+            maResult.emplace_back(
+                rA,
+                rB,
+                rC);
         }
 
         // consume as long as there are edges
@@ -370,9 +371,9 @@ namespace basegfx
 {
     namespace triangulator
     {
-        B2DPolygon triangulate(const B2DPolygon& rCandidate)
+        B2DTriangleVector triangulate(const B2DPolygon& rCandidate)
         {
-            B2DPolygon aRetval;
+            B2DTriangleVector aRetval;
 
             // subdivide locally (triangulate does not work with beziers), remove double and neutral points
             B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? utils::adaptiveSubdivideByAngle(rCandidate) : rCandidate);
@@ -382,7 +383,10 @@ namespace basegfx
             if(aCandidate.count() == 2)
             {
                 // candidate IS a triangle, just append
-                aRetval.append(aCandidate);
+                aRetval.emplace_back(
+                    aCandidate.getB2DPoint(0),
+                    aCandidate.getB2DPoint(1),
+                    aCandidate.getB2DPoint(2));
             }
             else if(aCandidate.count() > 2)
             {
@@ -396,6 +400,7 @@ namespace basegfx
                     // polygon is concave.
                     const B2DPolyPolygon aCandPolyPoly(aCandidate);
                     Triangulator aTriangulator(aCandPolyPoly);
+
                     aRetval = aTriangulator.getResult();
                 }
             }
@@ -403,9 +408,9 @@ namespace basegfx
             return aRetval;
         }
 
-        B2DPolygon triangulate(const B2DPolyPolygon& rCandidate)
+        B2DTriangleVector triangulate(const B2DPolyPolygon& rCandidate)
         {
-            B2DPolygon aRetval;
+            B2DTriangleVector aRetval;
 
             // subdivide locally (triangulate does not work with beziers)
             B2DPolyPolygon aCandidate(rCandidate.areControlPointsUsed() ? utils::adaptiveSubdivideByAngle(rCandidate) : rCandidate);
@@ -414,11 +419,13 @@ namespace basegfx
             {
                 // single polygon -> single polygon triangulation
                 const B2DPolygon aSinglePolygon(aCandidate.getB2DPolygon(0));
+
                 aRetval = triangulate(aSinglePolygon);
             }
             else
             {
                 Triangulator aTriangulator(aCandidate);
+
                 aRetval = aTriangulator.getResult();
             }