From 6152b5efa3490cc8f09f269dc7542ffe3833358c Mon Sep 17 00:00:00 2001 From: Mathias Bauer Date: Mon, 14 Sep 2009 19:06:55 +0200 Subject: #i103496#: split cppunit in a pure external lib and a lib depending on sal -> testshl2 --- basegfx/test/basegfx1d.cxx | 2 +- basegfx/test/basegfx2d.cxx | 2 +- basegfx/test/basegfx3d.cxx | 2 +- basegfx/test/makefile.mk | 11 ++++++----- 4 files changed, 9 insertions(+), 8 deletions(-) (limited to 'basegfx') 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 +#include namespace basegfx1d { diff --git a/basegfx/test/basegfx2d.cxx b/basegfx/test/basegfx2d.cxx index 8b732e465a51..8f3e340729a2 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 +#include #include #include 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 +#include namespace basegfx3d { diff --git a/basegfx/test/makefile.mk b/basegfx/test/makefile.mk index 8e47a13defdd..d21093f4e08a 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=\ @@ -65,23 +65,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 ------------------------ -- cgit From c17a26a1df43233008981c7aebd4f504a6b532ff Mon Sep 17 00:00:00 2001 From: Armin Weiss Date: Tue, 20 Oct 2009 15:36:14 +0000 Subject: #i105065# speedup 3D/FontWork --- basegfx/source/polygon/b3dpolygontools.cxx | 167 ++++++++++++++++++++++------- 1 file changed, 131 insertions(+), 36 deletions(-) (limited to 'basegfx') diff --git a/basegfx/source/polygon/b3dpolygontools.cxx b/basegfx/source/polygon/b3dpolygontools.cxx index ea303886dd88..52e0f0fcc36f 100644 --- a/basegfx/source/polygon/b3dpolygontools.cxx +++ b/basegfx/source/polygon/b3dpolygontools.cxx @@ -875,52 +875,147 @@ namespace basegfx } else { + bool bRetval(false); const B3DVector aPlaneNormal(rCandidate.getNormal()); if(!aPlaneNormal.equalZero()) { - const double fAbsX(fabs(aPlaneNormal.getX())); - const double fAbsY(fabs(aPlaneNormal.getY())); - const double fAbsZ(fabs(aPlaneNormal.getZ())); + const sal_uInt32 nPointCount(rCandidate.count()); - if(fAbsX > fAbsY && fAbsX > fAbsZ) + if(nPointCount) { - // normal points mostly in X-Direction, use YZ-Polygon projection for check - B3DHomMatrix aTrans; + B3DPoint aCurrentPoint(rCandidate.getB3DPoint(nPointCount - 1)); + const double fAbsX(fabs(aPlaneNormal.getX())); + const double fAbsY(fabs(aPlaneNormal.getY())); + const double fAbsZ(fabs(aPlaneNormal.getZ())); - aTrans.set(0, 0, 0.0); - aTrans.set(0, 1, 1.0); - aTrans.set(1, 1, 0.0); - aTrans.set(1, 2, 1.0); - - const B2DPolygon aYZ(createB2DPolygonFromB3DPolygon(rCandidate, aTrans)); - - return isInside(aYZ, B2DPoint(rPoint.getY(), rPoint.getZ()), bWithBorder); - } - else if(fAbsY > fAbsX && fAbsY > fAbsZ) - { - // normal points mostly in Y-Direction, use XZ-Polygon projection for check - B3DHomMatrix aTrans; - - aTrans.set(1, 1, 0.0); - aTrans.set(1, 2, 1.0); - - const B2DPolygon aXZ(createB2DPolygonFromB3DPolygon(rCandidate, aTrans)); - - return isInside(aXZ, B2DPoint(rPoint.getX(), rPoint.getZ()), bWithBorder); - } - else - { - // normal points mostly in Z-Direction, use XY-Polygon projection for check - B3DHomMatrix aTrans; - - const B2DPolygon aXY(createB2DPolygonFromB3DPolygon(rCandidate, aTrans)); - - return isInside(aXY, B2DPoint(rPoint.getX(), rPoint.getY()), bWithBorder); + if(fAbsX > fAbsY && fAbsX > fAbsZ) + { + // normal points mostly in X-Direction, use YZ-Polygon projection for check + // x -> y, y -> z + for(sal_uInt32 a(0); a < nPointCount; a++) + { + const B3DPoint aPreviousPoint(aCurrentPoint); + aCurrentPoint = rCandidate.getB3DPoint(a); + + // cross-over in Z? + const bool bCompZA(fTools::more(aPreviousPoint.getZ(), rPoint.getZ())); + const bool bCompZB(fTools::more(aCurrentPoint.getZ(), rPoint.getZ())); + + if(bCompZA != bCompZB) + { + // cross-over in Y? + const bool bCompYA(fTools::more(aPreviousPoint.getY(), rPoint.getY())); + const bool bCompYB(fTools::more(aCurrentPoint.getY(), rPoint.getY())); + + if(bCompYA == bCompYB) + { + if(bCompYA) + { + bRetval = !bRetval; + } + } + else + { + const double fCompare( + aCurrentPoint.getY() - (aCurrentPoint.getZ() - rPoint.getZ()) * + (aPreviousPoint.getY() - aCurrentPoint.getY()) / + (aPreviousPoint.getZ() - aCurrentPoint.getZ())); + + if(fTools::more(fCompare, rPoint.getY())) + { + bRetval = !bRetval; + } + } + } + } + } + else if(fAbsY > fAbsX && fAbsY > fAbsZ) + { + // normal points mostly in Y-Direction, use XZ-Polygon projection for check + // x -> x, y -> z + for(sal_uInt32 a(0); a < nPointCount; a++) + { + const B3DPoint aPreviousPoint(aCurrentPoint); + aCurrentPoint = rCandidate.getB3DPoint(a); + + // cross-over in Z? + const bool bCompZA(fTools::more(aPreviousPoint.getZ(), rPoint.getZ())); + const bool bCompZB(fTools::more(aCurrentPoint.getZ(), rPoint.getZ())); + + if(bCompZA != bCompZB) + { + // cross-over in X? + const bool bCompXA(fTools::more(aPreviousPoint.getX(), rPoint.getX())); + const bool bCompXB(fTools::more(aCurrentPoint.getX(), rPoint.getX())); + + if(bCompXA == bCompXB) + { + if(bCompXA) + { + bRetval = !bRetval; + } + } + else + { + const double fCompare( + aCurrentPoint.getX() - (aCurrentPoint.getZ() - rPoint.getZ()) * + (aPreviousPoint.getX() - aCurrentPoint.getX()) / + (aPreviousPoint.getZ() - aCurrentPoint.getZ())); + + if(fTools::more(fCompare, rPoint.getX())) + { + bRetval = !bRetval; + } + } + } + } + } + else + { + // normal points mostly in Z-Direction, use XY-Polygon projection for check + // x -> x, y -> y + for(sal_uInt32 a(0); a < nPointCount; a++) + { + const B3DPoint aPreviousPoint(aCurrentPoint); + aCurrentPoint = rCandidate.getB3DPoint(a); + + // cross-over in Y? + const bool bCompYA(fTools::more(aPreviousPoint.getY(), rPoint.getY())); + const bool bCompYB(fTools::more(aCurrentPoint.getY(), rPoint.getY())); + + if(bCompYA != bCompYB) + { + // cross-over in X? + const bool bCompXA(fTools::more(aPreviousPoint.getX(), rPoint.getX())); + const bool bCompXB(fTools::more(aCurrentPoint.getX(), rPoint.getX())); + + if(bCompXA == bCompXB) + { + if(bCompXA) + { + bRetval = !bRetval; + } + } + else + { + const double fCompare( + aCurrentPoint.getX() - (aCurrentPoint.getY() - rPoint.getY()) * + (aPreviousPoint.getX() - aCurrentPoint.getX()) / + (aPreviousPoint.getY() - aCurrentPoint.getY())); + + if(fTools::more(fCompare, rPoint.getX())) + { + bRetval = !bRetval; + } + } + } + } + } } } - return false; + return bRetval; } } -- cgit From b1419a4de2ff47d32cd7d93b4042727b05435fad Mon Sep 17 00:00:00 2001 From: hdu Date: Wed, 21 Oct 2009 11:06:38 +0200 Subject: #i106127# perf: add and use B2DPolygon::reserve() to prevent many reallocations --- basegfx/inc/basegfx/polygon/b2dpolygon.hxx | 1 + basegfx/source/polygon/b2dpolygon.cxx | 15 +++++++++++++++ basegfx/source/polygon/b2dpolygontools.cxx | 9 +++++++++ 3 files changed, 25 insertions(+) (limited to 'basegfx') diff --git a/basegfx/inc/basegfx/polygon/b2dpolygon.hxx b/basegfx/inc/basegfx/polygon/b2dpolygon.hxx index ee12d55d460b..1d5f8aaa4356 100644 --- a/basegfx/inc/basegfx/polygon/b2dpolygon.hxx +++ b/basegfx/inc/basegfx/polygon/b2dpolygon.hxx @@ -89,6 +89,7 @@ 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 reserve(sal_uInt32 nCount); /// Basic ControlPoint interface basegfx::B2DPoint getPrevControlPoint(sal_uInt32 nIndex) const; diff --git a/basegfx/source/polygon/b2dpolygon.cxx b/basegfx/source/polygon/b2dpolygon.cxx index 467a4b90f516..d44599e0f49e 100644 --- a/basegfx/source/polygon/b2dpolygon.cxx +++ b/basegfx/source/polygon/b2dpolygon.cxx @@ -123,6 +123,11 @@ public: maVector[nIndex].setCoordinate(rValue); } + void reserve(sal_uInt32 nCount) + { + maVector.reserve(nCount); + } + void insert(sal_uInt32 nIndex, const CoordinateData2D& rValue, sal_uInt32 nCount) { if(nCount) @@ -741,6 +746,11 @@ public: maPoints.setCoordinate(nIndex, rValue); } + void reserve(sal_uInt32 nCount) + { + maPoints.reserve(nCount); + } + void insert(sal_uInt32 nIndex, const basegfx::B2DPoint& rPoint, sal_uInt32 nCount) { if(nCount) @@ -1190,6 +1200,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 (!)"); diff --git a/basegfx/source/polygon/b2dpolygontools.cxx b/basegfx/source/polygon/b2dpolygontools.cxx index c1e5dc80d8c4..038ad0b35300 100644 --- a/basegfx/source/polygon/b2dpolygontools.cxx +++ b/basegfx/source/polygon/b2dpolygontools.cxx @@ -192,6 +192,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()); @@ -272,6 +275,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()); @@ -342,6 +348,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()); -- cgit From c94382c18059ecf000d1becbffa5425812dcc3f6 Mon Sep 17 00:00:00 2001 From: hdu Date: Wed, 21 Oct 2009 15:43:13 +0200 Subject: #i106127# perf: make self-intersection-test of bezier curve much cheaper --- basegfx/source/polygon/b2dpolygoncutandtouch.cxx | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'basegfx') diff --git a/basegfx/source/polygon/b2dpolygoncutandtouch.cxx b/basegfx/source/polygon/b2dpolygoncutandtouch.cxx index 26016942717d..9d40acc0dcab 100644 --- a/basegfx/source/polygon/b2dpolygoncutandtouch.cxx +++ b/basegfx/source/polygon/b2dpolygoncutandtouch.cxx @@ -497,6 +497,11 @@ namespace basegfx const B2DCubicBezier& rCubicA, sal_uInt32 nInd, temporaryPointVector& rTempPoints) { + 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. -- cgit From 61b3bb859f1f9150a68edd307c0367bb89ab69c5 Mon Sep 17 00:00:00 2001 From: hdu Date: Wed, 21 Oct 2009 18:16:37 +0200 Subject: #i106127# perf: add B2DCubicBezier::getMaxDistancePositions ( ) to allow better bezier-subdivisions --- basegfx/inc/basegfx/curve/b2dcubicbezier.hxx | 16 ++++++++++ basegfx/source/curve/b2dcubicbezier.cxx | 48 ++++++++++++++++++++++++++++ 2 files changed, 64 insertions(+) (limited to 'basegfx') 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/source/curve/b2dcubicbezier.cxx b/basegfx/source/curve/b2dcubicbezier.cxx index e7247a95333b..f0a1a0b54e90 100644 --- a/basegfx/source/curve/b2dcubicbezier.cxx +++ b/basegfx/source/curve/b2dcubicbezier.cxx @@ -1045,6 +1045,54 @@ 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(); + + 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); + if( pResult[0] < 0 || pResult[0]>1) + return 0; + return 1; + } + + // derivative is polynomial of order 2 => use binomial formula + const double fD = fB*fB - fA*fC; + if( fD >= 0.0 ) + { + const double fS = sqrt(fD); + const double fQ = fB + ((fB >= 0) ? +fS : -fS); + pResult[0] = fQ / fA; + pResult[1] = fC / fQ; + int nCount = 2; + if( pResult[1] < 0 || pResult[1]>1) + --nCount; + if( pResult[0] < 0 || pResult[0]>1) + { --nCount; pResult[0] = pResult[0]; } + return nCount; + } + + return 0; + } + } // end of namespace basegfx // eof -- cgit From 10235e9e83bd48e47e07486a5542b4e1b9299e90 Mon Sep 17 00:00:00 2001 From: hdu Date: Thu, 22 Oct 2009 09:19:00 +0200 Subject: #i106127# perf: free roaming curve-subdivision also benefit from pre-allocation --- basegfx/source/polygon/b2dpolygoncutandtouch.cxx | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) (limited to 'basegfx') diff --git a/basegfx/source/polygon/b2dpolygoncutandtouch.cxx b/basegfx/source/polygon/b2dpolygoncutandtouch.cxx index 9d40acc0dcab..7597bf1ed11b 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,8 @@ 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 ) @@ -510,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); -- cgit From 350ea0397036814992d47c7b836ef6f5005c6e98 Mon Sep 17 00:00:00 2001 From: hdu Date: Thu, 22 Oct 2009 09:35:47 +0200 Subject: #i106127# fix typo in new method getMaxDistancePositions() --- basegfx/source/curve/b2dcubicbezier.cxx | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'basegfx') diff --git a/basegfx/source/curve/b2dcubicbezier.cxx b/basegfx/source/curve/b2dcubicbezier.cxx index f0a1a0b54e90..38d783e9651d 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. * @@ -1086,7 +1085,8 @@ namespace basegfx if( pResult[1] < 0 || pResult[1]>1) --nCount; if( pResult[0] < 0 || pResult[0]>1) - { --nCount; pResult[0] = pResult[0]; } + if( --nCount) + pResult[0] = pResult[1]; return nCount; } -- cgit From ab818b36b52e646b43e390d1b6c0140b91a92523 Mon Sep 17 00:00:00 2001 From: hdu Date: Thu, 22 Oct 2009 11:39:42 +0200 Subject: #i106127# perf: consecutive polygon segments always touch so costly decisions based only on the touch-criterion should be avoided for this case --- basegfx/inc/basegfx/range/b1drange.hxx | 6 ++++- basegfx/inc/basegfx/range/b2drange.hxx | 9 ++++++- basegfx/inc/basegfx/range/basicrange.hxx | 9 ++++++- basegfx/source/polygon/b2dpolygoncutandtouch.cxx | 33 +++++++++++++++++++++--- 4 files changed, 50 insertions(+), 7 deletions(-) (limited to 'basegfx') 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/polygon/b2dpolygoncutandtouch.cxx b/basegfx/source/polygon/b2dpolygoncutandtouch.cxx index 7597bf1ed11b..e35e22ae3a04 100644 --- a/basegfx/source/polygon/b2dpolygoncutandtouch.cxx +++ b/basegfx/source/polygon/b2dpolygoncutandtouch.cxx @@ -567,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) { @@ -609,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); } @@ -806,7 +819,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) { @@ -848,7 +867,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); -- cgit From aa99d186de8cd2841cd7aabc371f68f1e05bae1f Mon Sep 17 00:00:00 2001 From: hdu Date: Thu, 22 Oct 2009 15:55:15 +0200 Subject: #i106127# more pre-allocations to prevent reallocations --- basegfx/source/polygon/b2dpolygoncutandtouch.cxx | 1 + basegfx/source/polygon/b2dpolygontools.cxx | 4 +++- 2 files changed, 4 insertions(+), 1 deletion(-) (limited to 'basegfx') diff --git a/basegfx/source/polygon/b2dpolygoncutandtouch.cxx b/basegfx/source/polygon/b2dpolygoncutandtouch.cxx index e35e22ae3a04..da6ff8904725 100644 --- a/basegfx/source/polygon/b2dpolygoncutandtouch.cxx +++ b/basegfx/source/polygon/b2dpolygoncutandtouch.cxx @@ -711,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); diff --git a/basegfx/source/polygon/b2dpolygontools.cxx b/basegfx/source/polygon/b2dpolygontools.cxx index 038ad0b35300..7485387c6cb9 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. * @@ -3278,6 +3277,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()); -- cgit From 406092f60abbb258bbd1fc6f2d09e7a669af943b Mon Sep 17 00:00:00 2001 From: hdu Date: Thu, 22 Oct 2009 16:54:19 +0200 Subject: #i106127# perf: using vector.push_back() instead of the generic vector.insertAtWithCount() is worth it when it gets called a gazillion times --- basegfx/inc/basegfx/polygon/b2dpolygon.hxx | 4 ++-- basegfx/source/polygon/b2dpolygon.cxx | 35 +++++++++++++++++++++++++++++- 2 files changed, 36 insertions(+), 3 deletions(-) (limited to 'basegfx') diff --git a/basegfx/inc/basegfx/polygon/b2dpolygon.hxx b/basegfx/inc/basegfx/polygon/b2dpolygon.hxx index 1d5f8aaa4356..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,8 @@ 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 diff --git a/basegfx/source/polygon/b2dpolygon.cxx b/basegfx/source/polygon/b2dpolygon.cxx index d44599e0f49e..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. * @@ -128,6 +127,11 @@ public: 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) @@ -385,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) @@ -751,6 +766,19 @@ public: 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) @@ -1223,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 (!)"); -- cgit From f4b316f0117ef507758dfa5c5a1038e0870eded6 Mon Sep 17 00:00:00 2001 From: hdu Date: Fri, 23 Oct 2009 11:02:48 +0200 Subject: #i106127# perf: ignore multiplicit solutions in maxdist calculation --- basegfx/source/curve/b2dcubicbezier.cxx | 34 +++++++++++++++++++++------------ 1 file changed, 22 insertions(+), 12 deletions(-) (limited to 'basegfx') diff --git a/basegfx/source/curve/b2dcubicbezier.cxx b/basegfx/source/curve/b2dcubicbezier.cxx index 38d783e9651d..83c620df7870 100644 --- a/basegfx/source/curve/b2dcubicbezier.cxx +++ b/basegfx/source/curve/b2dcubicbezier.cxx @@ -1060,6 +1060,7 @@ namespace basegfx 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 @@ -1068,25 +1069,34 @@ namespace basegfx // degenerated case: quadratic bezier pResult[0] = -fC / (2*fB); - if( pResult[0] < 0 || pResult[0]>1) - return 0; - return 1; + + // 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 => use binomial formula + // 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 ) + 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; - pResult[1] = fC / fQ; - int nCount = 2; - if( pResult[1] < 0 || pResult[1]>1) - --nCount; - if( pResult[0] < 0 || pResult[0]>1) - if( --nCount) - pResult[0] = pResult[1]; + // 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; } -- cgit