aw078: resync to DEV300m68for integration

13 files changed, 210 insertions, 21 deletions

diff --git a/basegfx/inc/basegfx/curve/b2dcubicbezier.hxx b/basegfx/inc/basegfx/curve/b2dcubicbezier.hxx
index 4dc2f45568f1..81be451499ea 100644
--- a/basegfx/inc/basegfx/curve/b2dcubicbezier.hxx
+++ b/basegfx/inc/basegfx/curve/b2dcubicbezier.hxx
@@ -203,6 +203,22 @@ namespace basegfx
             sense to use reserve(4) at the vector as preparation.
         */
         void getAllExtremumPositions(::std::vector< double >& rResults) const;
+
+        /** Get optimum-split position on this segment
+
+            This method calculates the positions of all points of the segment
+            that have the maximimum distance to the corresponding line from
+            startpoint-endpoint. This helps to approximate the bezier curve
+            with a minimum number of line segments
+
+            @param fResults
+             Result positions are in the range ]0.0 .. 1.0[
+            Cubic beziers have at most two of these positions
+
+            @return
+            Returns the number of split positions found
+        */
+        int getMaxDistancePositions( double fResults[2]) const;
     };
 } // end of namespace basegfx
 
diff --git a/basegfx/inc/basegfx/polygon/b2dpolygon.hxx b/basegfx/inc/basegfx/polygon/b2dpolygon.hxx
index ee12d55d460b..c0de4b57ced8 100644
--- a/basegfx/inc/basegfx/polygon/b2dpolygon.hxx
+++ b/basegfx/inc/basegfx/polygon/b2dpolygon.hxx
@@ -7,7 +7,6 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: b2dpolygon.hxx,v $
- * $Revision: 1.14 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -88,7 +87,9 @@ namespace basegfx
 
         /// Coordinate insert/append
         void insert(sal_uInt32 nIndex, const basegfx::B2DPoint& rPoint, sal_uInt32 nCount = 1);
-        void append(const basegfx::B2DPoint& rPoint, sal_uInt32 nCount = 1);
+        void append(const basegfx::B2DPoint& rPoint, sal_uInt32 nCount);
+        void append(const basegfx::B2DPoint& rPoint);
+        void reserve(sal_uInt32 nCount);
 
         /// Basic ControlPoint interface
         basegfx::B2DPoint getPrevControlPoint(sal_uInt32 nIndex) const;
diff --git a/basegfx/inc/basegfx/range/b1drange.hxx b/basegfx/inc/basegfx/range/b1drange.hxx
index efca06d92dfd..366431c3cd50 100644
--- a/basegfx/inc/basegfx/range/b1drange.hxx
+++ b/basegfx/inc/basegfx/range/b1drange.hxx
@@ -7,7 +7,6 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: b1drange.hxx,v $
- * $Revision: 1.15 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -131,6 +130,11 @@ namespace basegfx
             return maRange.overlaps(rRange.maRange);
         }
 
+        bool overlapsMore(const B1DRange& rRange) const
+        {
+            return maRange.overlapsMore(rRange.maRange);
+        }
+
         void expand(double fValue)
         {
             maRange.expand(fValue);
diff --git a/basegfx/inc/basegfx/range/b2drange.hxx b/basegfx/inc/basegfx/range/b2drange.hxx
index 66892865399f..8a70d4782f47 100644
--- a/basegfx/inc/basegfx/range/b2drange.hxx
+++ b/basegfx/inc/basegfx/range/b2drange.hxx
@@ -7,7 +7,6 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: b2drange.hxx,v $
- * $Revision: 1.19 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -222,6 +221,14 @@ namespace basegfx
                 );
         }
 
+        bool overlapsMore(const B2DRange& rRange) const
+        {
+            return (
+                maRangeX.overlapsMore(rRange.maRangeX)
+                && maRangeY.overlapsMore(rRange.maRangeY)
+                );
+        }
+
         void expand(const B2DTuple& rTuple)
         {
             maRangeX.expand(rTuple.getX());
diff --git a/basegfx/inc/basegfx/range/basicrange.hxx b/basegfx/inc/basegfx/range/basicrange.hxx
index a7c402c905c8..59d13cf530c0 100644
--- a/basegfx/inc/basegfx/range/basicrange.hxx
+++ b/basegfx/inc/basegfx/range/basicrange.hxx
@@ -7,7 +7,6 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: basicrange.hxx,v $
- * $Revision: 1.15 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -142,6 +141,14 @@ namespace basegfx
             }
         }
 
+        bool overlapsMore(const BasicRange& rRange) const
+        {
+            if(isEmpty() || rRange.isEmpty())
+                return false;
+            // returns true if the overlap is more than just a touching at the limits
+            return ((rRange.mnMaximum > mnMinimum) && (rRange.mnMinimum < mnMaximum));
+        }
+
         bool operator==( const BasicRange& rRange ) const
         {
             return (mnMinimum == rRange.mnMinimum && mnMaximum == rRange.mnMaximum);
diff --git a/basegfx/source/curve/b2dcubicbezier.cxx b/basegfx/source/curve/b2dcubicbezier.cxx
index e7247a95333b..83c620df7870 100644
--- a/basegfx/source/curve/b2dcubicbezier.cxx
+++ b/basegfx/source/curve/b2dcubicbezier.cxx
@@ -7,7 +7,6 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: b2dcubicbezier.cxx,v $
- * $Revision: 1.16 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -1045,6 +1044,65 @@ namespace basegfx
             impCheckExtremumResult(fCY / (2 * fBY), rResults);
         }
     }
+
+    int B2DCubicBezier::getMaxDistancePositions( double pResult[2]) const
+    {
+        // the distance from the bezier to a line through start and end
+        // is proportional to (ENDx-STARTx,ENDy-STARTy)*(+BEZIERy(t),-BEZIERx(t))
+        // this distance becomes zero for at least t==0 and t==1
+        // its extrema that are between 0..1 are interesting as split candidates
+        // its derived function has the form dD/dt = fA*t^2 + 2*fB*t + fC
+        const B2DPoint aRelativeEndPoint(maEndPoint-maStartPoint);
+        const double fA = 3 * (maEndPoint.getX() - maControlPointB.getX()) * aRelativeEndPoint.getY()
+                - 3 * (maEndPoint.getY() - maControlPointB.getY()) * aRelativeEndPoint.getX();
+        const double fB = (maControlPointB.getX() - maControlPointA.getX()) * aRelativeEndPoint.getY()
+                - (maControlPointB.getY() - maControlPointA.getY()) * aRelativeEndPoint.getX();
+        const double fC = (maControlPointA.getX() - maStartPoint.getX()) * aRelativeEndPoint.getY()
+                - (maControlPointA.getY() - maStartPoint.getY()) * aRelativeEndPoint.getX();
+
+        // test for degenerated case: non-cubic curve
+        if( fTools::equalZero(fA) )
+        {
+            // test for degenerated case: straight line
+            if( fTools::equalZero(fB) )
+                return 0;
+
+            // degenerated case: quadratic bezier
+            pResult[0] = -fC / (2*fB);
+
+            // test root: ignore it when it is outside the curve
+            int nCount = ((pResult[0] > 0) && (pResult[0] < 1));
+            return nCount;
+        }
+
+        // derivative is polynomial of order 2
+        // check if the polynomial has non-imaginary roots
+        const double fD = fB*fB - fA*fC;
+        if( fD >= 0.0 ) // TODO: is this test needed? geometrically not IMHO
+        {
+            // calculate the first root
+            const double fS = sqrt(fD);
+            const double fQ = fB + ((fB >= 0) ? +fS : -fS);
+            pResult[0] = fQ / fA;
+            // test root: ignore it when it is outside the curve
+            int nCount = ((pResult[0] > 0) && (pResult[0] < 1));
+
+            // ignore multiplicit roots
+            if( !fTools::equalZero(fD) )
+            {
+                 // calculate the second root
+                const double fRoot = fC / fQ;
+                pResult[ nCount ] = fC / fQ;
+                // test root: ignore it when it is outside the curve
+                nCount += ((fRoot > 0) && (fRoot < 1));
+            }
+
+            return nCount;
+        }
+
+        return 0;
+    }
+
 } // end of namespace basegfx
 
 // eof
diff --git a/basegfx/source/polygon/b2dpolygon.cxx b/basegfx/source/polygon/b2dpolygon.cxx
index 467a4b90f516..48d00ddcec7d 100644
--- a/basegfx/source/polygon/b2dpolygon.cxx
+++ b/basegfx/source/polygon/b2dpolygon.cxx
@@ -7,7 +7,6 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: b2dpolygon.cxx,v $
- * $Revision: 1.22 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -123,6 +122,16 @@ public:
         maVector[nIndex].setCoordinate(rValue);
     }
 
+    void reserve(sal_uInt32 nCount)
+    {
+        maVector.reserve(nCount);
+    }
+
+    void append(const CoordinateData2D& rValue)
+    {
+        maVector.push_back(rValue);
+    }
+
     void insert(sal_uInt32 nIndex, const CoordinateData2D& rValue, sal_uInt32 nCount)
     {
         if(nCount)
@@ -380,6 +389,17 @@ public:
         }
     }
 
+    void append(const ControlVectorPair2D& rValue)
+    {
+        maVector.push_back(rValue);
+
+        if(!rValue.getPrevVector().equalZero())
+            mnUsedVectors += 1;
+
+        if(!rValue.getNextVector().equalZero())
+            mnUsedVectors += 1;
+    }
+
     void insert(sal_uInt32 nIndex, const ControlVectorPair2D& rValue, sal_uInt32 nCount)
     {
         if(nCount)
@@ -741,6 +761,24 @@ public:
         maPoints.setCoordinate(nIndex, rValue);
     }
 
+    void reserve(sal_uInt32 nCount)
+    {
+        maPoints.reserve(nCount);
+    }
+
+    void append(const basegfx::B2DPoint& rPoint)
+    {
+        mpBufferedData.reset(); // TODO: is this needed?
+        const CoordinateData2D aCoordinate(rPoint);
+        maPoints.append(aCoordinate);
+
+        if(mpControlVector)
+        {
+            const ControlVectorPair2D aVectorPair;
+            mpControlVector->append(aVectorPair);
+        }
+    }
+
     void insert(sal_uInt32 nIndex, const basegfx::B2DPoint& rPoint, sal_uInt32 nCount)
     {
         if(nCount)
@@ -1190,6 +1228,11 @@ namespace basegfx
         }
     }
 
+    void B2DPolygon::reserve(sal_uInt32 nCount)
+    {
+        mpPolygon->reserve(nCount);
+    }
+
     void B2DPolygon::insert(sal_uInt32 nIndex, const B2DPoint& rPoint, sal_uInt32 nCount)
     {
         OSL_ENSURE(nIndex <= mpPolygon->count(), "B2DPolygon Insert outside range (!)");
@@ -1208,6 +1251,11 @@ namespace basegfx
         }
     }
 
+    void B2DPolygon::append(const B2DPoint& rPoint)
+    {
+        mpPolygon->append(rPoint);
+    }
+
     B2DPoint B2DPolygon::getPrevControlPoint(sal_uInt32 nIndex) const
     {
         OSL_ENSURE(nIndex < mpPolygon->count(), "B2DPolygon access outside range (!)");
diff --git a/basegfx/source/polygon/b2dpolygoncutandtouch.cxx b/basegfx/source/polygon/b2dpolygoncutandtouch.cxx
index 26016942717d..da6ff8904725 100644
--- a/basegfx/source/polygon/b2dpolygoncutandtouch.cxx
+++ b/basegfx/source/polygon/b2dpolygoncutandtouch.cxx
@@ -7,7 +7,6 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: b2dpolygoncutandtouch.cxx,v $
- * $Revision: 1.8 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -430,6 +429,7 @@ namespace basegfx
 
             // create subdivided polygons and find cuts between them
             // Keep adaptiveSubdivideByCount due to needed quality
+            aTempPolygonA.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
             aTempPolygonA.append(rCubicA.getStartPoint());
             rCubicA.adaptiveSubdivideByCount(aTempPolygonA, SUBDIVIDE_FOR_CUT_TEST_COUNT);
             aTempPolygonEdge.append(rCurrB);
@@ -470,8 +470,10 @@ namespace basegfx
 
             // create subdivided polygons and find cuts between them
             // Keep adaptiveSubdivideByCount due to needed quality
+            aTempPolygonA.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
             aTempPolygonA.append(rCubicA.getStartPoint());
             rCubicA.adaptiveSubdivideByCount(aTempPolygonA, SUBDIVIDE_FOR_CUT_TEST_COUNT);
+            aTempPolygonB.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
             aTempPolygonB.append(rCubicB.getStartPoint());
             rCubicB.adaptiveSubdivideByCount(aTempPolygonB, SUBDIVIDE_FOR_CUT_TEST_COUNT);
 
@@ -497,6 +499,13 @@ namespace basegfx
             const B2DCubicBezier& rCubicA,
             sal_uInt32 nInd, temporaryPointVector& rTempPoints)
         {
+            // avoid expensive part of this method if possible
+            // TODO: use hasAnyExtremum() method instead when it becomes available
+            double fDummy;
+            const bool bHasAnyExtremum = rCubicA.getMinimumExtremumPosition( fDummy );
+            if( !bHasAnyExtremum )
+                return;
+
             // find all self-intersections on the given bezier segment. Add an entry to the tempPoints
             // for each self intersection point with the cut value describing the relative position on given
             // bezier segment.
@@ -505,6 +514,7 @@ namespace basegfx
 
             // create subdivided polygon and find cuts on it
             // Keep adaptiveSubdivideByCount due to needed quality
+            aTempPolygon.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
             aTempPolygon.append(rCubicA.getStartPoint());
             rCubicA.adaptiveSubdivideByCount(aTempPolygon, SUBDIVIDE_FOR_CUT_TEST_COUNT);
             findCuts(aTempPolygon, aTempPointVector);
@@ -557,7 +567,14 @@ namespace basegfx
                                 const bool bEdgeBIsCurve(aCubicB.isBezier());
                                 const B2DRange aRangeB(aCubicB.getRange());
 
-                                if(aRangeA.overlaps(aRangeB))
+                                // only overlapping segments need to be tested
+                                // consecutive segments touch of course
+                                bool bOverlap = false;
+                                if( b > a+1)
+                                    bOverlap = aRangeA.overlaps(aRangeB);
+                                else
+                                    bOverlap = aRangeA.overlapsMore(aRangeB);
+                                if( bOverlap)
                                 {
                                     if(bEdgeAIsCurve && bEdgeBIsCurve)
                                     {
@@ -599,7 +616,13 @@ namespace basegfx
                                 const B2DPoint aNextB(rCandidate.getB2DPoint(b + 1L == nPointCount ? 0L : b + 1L));
                                 const B2DRange aRangeB(aCurrB, aNextB);
 
-                                if(aRangeA.overlaps(aRangeB))
+                                // consecutive segments touch of course
+                                bool bOverlap = false;
+                                if( b > a+1)
+                                    bOverlap = aRangeA.overlaps(aRangeB);
+                                else
+                                    bOverlap = aRangeA.overlapsMore(aRangeB);
+                                if( bOverlap)
                                 {
                                     findEdgeCutsTwoEdges(aCurrA, aNextA, aCurrB, aNextB, a, b, rTempPoints, rTempPoints);
                                 }
@@ -688,6 +711,7 @@ namespace basegfx
 
             // create subdivided polygon and find cuts on it
             // Keep adaptiveSubdivideByCount due to needed quality
+            aTempPolygon.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
             aTempPolygon.append(rCubicA.getStartPoint());
             rCubicA.adaptiveSubdivideByCount(aTempPolygon, SUBDIVIDE_FOR_CUT_TEST_COUNT);
             findTouches(aTempPolygon, rPointPolygon, aTempPointVector);
@@ -796,7 +820,13 @@ namespace basegfx
                                 const bool bEdgeBIsCurve(aCubicB.isBezier());
                                 const B2DRange aRangeB(aCubicB.getRange());
 
-                                if(aRangeA.overlaps(aRangeB))
+                                // consecutive segments touch of course
+                                bool bOverlap = false;
+                                if( b > a+1)
+                                    bOverlap = aRangeA.overlaps(aRangeB);
+                                else
+                                    bOverlap = aRangeA.overlapsMore(aRangeB);
+                                if( bOverlap)
                                 {
                                     if(bEdgeAIsCurve && bEdgeBIsCurve)
                                     {
@@ -838,7 +868,13 @@ namespace basegfx
                                 const B2DPoint aNextB(rCandidateB.getB2DPoint(b + 1L == nPointCountB ? 0L : b + 1L));
                                 const B2DRange aRangeB(aCurrB, aNextB);
 
-                                if(aRangeA.overlaps(aRangeB))
+                                // consecutive segments touch of course
+                                bool bOverlap = false;
+                                if( b > a+1)
+                                    bOverlap = aRangeA.overlaps(aRangeB);
+                                else
+                                    bOverlap = aRangeA.overlapsMore(aRangeB);
+                                if( bOverlap)
                                 {
                                     // test for simple edge-edge cuts
                                     findEdgeCutsTwoEdges(aCurrA, aNextA, aCurrB, aNextB, a, b, rTempPointsA, rTempPointsB);
diff --git a/basegfx/source/polygon/b2dpolygontools.cxx b/basegfx/source/polygon/b2dpolygontools.cxx
index da3fa202c2a4..d62462b8c097 100644
--- a/basegfx/source/polygon/b2dpolygontools.cxx
+++ b/basegfx/source/polygon/b2dpolygontools.cxx
@@ -7,7 +7,6 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: b2dpolygontools.cxx,v $
- * $Revision: 1.29.4.1 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -194,6 +193,9 @@ namespace basegfx
                     B2DCubicBezier aBezier;
                     aBezier.setStartPoint(rCandidate.getB2DPoint(0));
 
+                    // perf: try to avoid too many realloctions by guessing the result's pointcount
+                    aRetval.reserve(nPointCount*4);
+
                     // add start point (always)
                     aRetval.append(aBezier.getStartPoint());
 
@@ -274,6 +276,9 @@ namespace basegfx
                     B2DCubicBezier aBezier;
                     aBezier.setStartPoint(rCandidate.getB2DPoint(0));
 
+                    // perf: try to avoid too many realloctions by guessing the result's pointcount
+                    aRetval.reserve(nPointCount*4);
+
                     // add start point (always)
                     aRetval.append(aBezier.getStartPoint());
 
@@ -344,6 +349,9 @@ namespace basegfx
                     B2DCubicBezier aBezier;
                     aBezier.setStartPoint(rCandidate.getB2DPoint(0));
 
+                    // perf: try to avoid too many realloctions by guessing the result's pointcount
+                    aRetval.reserve(nPointCount*4);
+
                     // add start point (always)
                     aRetval.append(aBezier.getStartPoint());
 
@@ -3234,6 +3242,9 @@ namespace basegfx
                 B2DCubicBezier aBezier;
                 aBezier.setStartPoint(rCandidate.getB2DPoint(0));
 
+                // try to avoid costly reallocations
+                aRetval.reserve( nEdgeCount+1);
+
                 // add start point
                 aRetval.append(aBezier.getStartPoint());
 
diff --git a/basegfx/test/basegfx1d.cxx b/basegfx/test/basegfx1d.cxx
index f058b0034fa7..454ed23289b2 100644
--- a/basegfx/test/basegfx1d.cxx
+++ b/basegfx/test/basegfx1d.cxx
@@ -33,7 +33,7 @@
 #include "precompiled_basegfx.hxx"
 // autogenerated file with codegen.pl
 
-#include <cppunit/simpleheader.hxx>
+#include <testshl/simpleheader.hxx>
 
 namespace basegfx1d
 {
diff --git a/basegfx/test/basegfx2d.cxx b/basegfx/test/basegfx2d.cxx
index 639933ace1e6..1bd15702e143 100644
--- a/basegfx/test/basegfx2d.cxx
+++ b/basegfx/test/basegfx2d.cxx
@@ -33,7 +33,7 @@
 #include "precompiled_basegfx.hxx"
 // autogenerated file with codegen.pl
 
-#include <cppunit/simpleheader.hxx>
+#include <testshl/simpleheader.hxx>
 
 #include <basegfx/matrix/b2dhommatrix.hxx>
 #include <basegfx/polygon/b2dpolygon.hxx>
diff --git a/basegfx/test/basegfx3d.cxx b/basegfx/test/basegfx3d.cxx
index fc59ffbced4e..f0fe463ce23d 100644
--- a/basegfx/test/basegfx3d.cxx
+++ b/basegfx/test/basegfx3d.cxx
@@ -33,7 +33,7 @@
 #include "precompiled_basegfx.hxx"
 // autogenerated file with codegen.pl
 
-#include <cppunit/simpleheader.hxx>
+#include <testshl/simpleheader.hxx>
 
 namespace basegfx3d
 {
diff --git a/basegfx/test/makefile.mk b/basegfx/test/makefile.mk
index 1bd4d59b98d5..da61c60f9308 100644
--- a/basegfx/test/makefile.mk
+++ b/basegfx/test/makefile.mk
@@ -1,7 +1,7 @@
 #*************************************************************************
 #
 # DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
-# 
+#
 # Copyright 2008 by Sun Microsystems, Inc.
 #
 # OpenOffice.org - a multi-platform office productivity suite
@@ -46,7 +46,7 @@ SHL1OBJS=  \
     $(SLO)$/basegfx1d.obj \
     $(SLO)$/basegfx2d.obj \
     $(SLO)$/basegfx3d.obj \
-    $(SLO)$/testtools.obj	
+    $(SLO)$/testtools.obj
 
 # linking statically against basegfx parts
 SHL1LIBS=\
@@ -66,23 +66,24 @@ SHL1STDLIBS= \
                 $(SALLIB)        \
                 $(CPPUHELPERLIB) \
                         $(CPPULIB)       \
+                                $(TESTSHL2LIB) \
                 $(CPPUNITLIB)
 
 SHL1IMPLIB= i$(SHL1TARGET)
 
 DEF1NAME    =$(SHL1TARGET)
-SHL1VERSIONMAP = export.map 
+SHL1VERSIONMAP = export.map
 
 # END ------------------------------------------------------------------
 
 #------------------------------- All object files -------------------------------
 # do this here, so we get right dependencies
-SLOFILES=$(SHL1OBJS) 
+SLOFILES=$(SHL1OBJS)
 
 # --- Targets ------------------------------------------------------
 
 .INCLUDE : target.mk
-.INCLUDE : _cppunit.mk 
+.INCLUDE : _cppunit.mk
 
 # --- Enable testshl2 execution in normal build ------------------------