diff options
Diffstat (limited to 'basegfx')
-rw-r--r-- | basegfx/inc/basegfx/curve/b2dcubicbezier.hxx | 16 | ||||
-rw-r--r-- | basegfx/inc/basegfx/polygon/b2dpolygon.hxx | 5 | ||||
-rw-r--r-- | basegfx/inc/basegfx/range/b1drange.hxx | 6 | ||||
-rw-r--r-- | basegfx/inc/basegfx/range/b2drange.hxx | 9 | ||||
-rw-r--r-- | basegfx/inc/basegfx/range/basicrange.hxx | 9 | ||||
-rw-r--r-- | basegfx/source/curve/b2dcubicbezier.cxx | 60 | ||||
-rw-r--r-- | basegfx/source/polygon/b2dpolygon.cxx | 50 | ||||
-rw-r--r-- | basegfx/source/polygon/b2dpolygoncutandtouch.cxx | 46 | ||||
-rw-r--r-- | basegfx/source/polygon/b2dpolygontools.cxx | 13 | ||||
-rw-r--r-- | basegfx/test/basegfx1d.cxx | 2 | ||||
-rw-r--r-- | basegfx/test/basegfx2d.cxx | 2 | ||||
-rw-r--r-- | basegfx/test/basegfx3d.cxx | 2 | ||||
-rw-r--r-- | basegfx/test/makefile.mk | 11 |
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 ------------------------ |