diff options
Diffstat (limited to 'basegfx/source/curve/b2dcubicbezier.cxx')
| -rw-r--r-- | basegfx/source/curve/b2dcubicbezier.cxx | 307 |
1 files changed, 229 insertions, 78 deletions
diff --git a/basegfx/source/curve/b2dcubicbezier.cxx b/basegfx/source/curve/b2dcubicbezier.cxx index dff487b521e0..ec70a91c5cf3 100644 --- a/basegfx/source/curve/b2dcubicbezier.cxx +++ b/basegfx/source/curve/b2dcubicbezier.cxx @@ -4,9 +4,9 @@ * * $RCSfile: b2dcubicbezier.cxx,v $ * - * $Revision: 1.13 $ + * $Revision: 1.14 $ * - * last change: $Author: obo $ $Date: 2007-01-25 11:03:02 $ + * last change: $Author: obo $ $Date: 2007-07-18 11:05:19 $ * * The Contents of this file are made available subject to * the terms of GNU Lesser General Public License Version 2.1. @@ -52,6 +52,8 @@ #include <basegfx/numeric/ftools.hxx> #endif +#include <limits> + // #i37443# #define FACTOR_FOR_UNSHARPEN (1.6) #ifdef DBG_UTIL @@ -64,14 +66,13 @@ namespace basegfx { namespace { - void ImpSubDiv( + void ImpSubDivAngle( const B2DPoint& rfPA, // start point const B2DPoint& rfEA, // edge on A const B2DPoint& rfEB, // edge on B const B2DPoint& rfPB, // end point B2DPolygon& rTarget, // target polygon double fAngleBound, // angle bound in [0.0 .. 2PI] - bool bAddLastPoint, // should last point be added? bool bAllowUnsharpen, // #i37443# allow the criteria to get unsharp in recursions sal_uInt16 nMaxRecursionDepth) // endless loop protection { @@ -124,33 +125,24 @@ namespace basegfx const B2DPoint aS3C(average(aS2L, aS2R)); // left recursion - ImpSubDiv(rfPA, aS1L, aS2L, aS3C, rTarget, fAngleBound, - bAddLastPoint, bAllowUnsharpen, nMaxRecursionDepth - 1); + ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1); // right recursion - ImpSubDiv(aS3C, aS2R, aS1R, rfPB, rTarget, fAngleBound, - bAddLastPoint, bAllowUnsharpen, nMaxRecursionDepth - 1); + ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1); } else { - // add points - rTarget.append(rfPA); - - if(bAddLastPoint) - { - rTarget.append(rfPB); - } + rTarget.append(rfPB); } } - void ImpSubDivStart( + void ImpSubDivAngleStart( const B2DPoint& rfPA, // start point const B2DPoint& rfEA, // edge on A const B2DPoint& rfEB, // edge on B const B2DPoint& rfPB, // end point B2DPolygon& rTarget, // target polygon const double& rfAngleBound, // angle bound in [0.0 .. 2PI] - bool bAddLastPoint, // should last point be added? bool bAllowUnsharpen) // #i37443# allow the criteria to get unsharp in recursions { sal_uInt16 nMaxRecursionDepth(8); @@ -264,43 +256,99 @@ namespace basegfx // left if(bAngleIsSmallerLeft) { - rTarget.append(rfPA); - if(bAddLastPoint) - { - rTarget.append(aS3C); - } + rTarget.append(aS3C); } else { - ImpSubDiv(rfPA, aS1L, aS2L, aS3C, rTarget, rfAngleBound, - bAddLastPoint, bAllowUnsharpen, nMaxRecursionDepth); + ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, rfAngleBound, bAllowUnsharpen, nMaxRecursionDepth); } // right if(bAngleIsSmallerRight) { - rTarget.append(aS3C); - if(bAddLastPoint) - { - rTarget.append(rfPB); - } + rTarget.append(rfPB); } else { - ImpSubDiv(aS3C, aS2R, aS1R, rfPB, rTarget, rfAngleBound, - bAddLastPoint, bAllowUnsharpen, nMaxRecursionDepth); + ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, rfAngleBound, bAllowUnsharpen, nMaxRecursionDepth); } } } if(!nMaxRecursionDepth) { - rTarget.append(rfPA); - if(bAddLastPoint) + rTarget.append(rfPB); + } + } + + void ImpSubDivDistance( + const B2DPoint& rfPA, // start point + const B2DPoint& rfEA, // edge on A + const B2DPoint& rfEB, // edge on B + const B2DPoint& rfPB, // end point + B2DPolygon& rTarget, // target polygon + double fDistanceBound2, // quadratic distance criteria + double fLastDistanceError2, // the last quadratic distance error + sal_uInt16 nMaxRecursionDepth) // endless loop protection + { + if(nMaxRecursionDepth) + { + // decide if another recursion is needed. If not, set + // nMaxRecursionDepth to zero + + // Perform bezier flatness test (lecture notes from R. Schaback, + // Mathematics of Computer-Aided Design, Uni Goettingen, 2000) + // + // ||P(t) - L(t)|| <= max ||b_j - b_0 - j/n(b_n - b_0)|| + // 0<=j<=n + // + // What is calculated here is an upper bound to the distance from + // a line through b_0 and b_3 (rfPA and P4 in our notation) and the + // curve. We can drop 0 and n from the running indices, since the + // argument of max becomes zero for those cases. + const double fJ1x(rfEA.getX() - rfPA.getX() - 1.0/3.0*(rfPB.getX() - rfPA.getX())); + const double fJ1y(rfEA.getY() - rfPA.getY() - 1.0/3.0*(rfPB.getY() - rfPA.getY())); + const double fJ2x(rfEB.getX() - rfPA.getX() - 2.0/3.0*(rfPB.getX() - rfPA.getX())); + const double fJ2y(rfEB.getY() - rfPA.getY() - 2.0/3.0*(rfPB.getY() - rfPA.getY())); + const double fDistanceError2(::std::max(fJ1x*fJ1x + fJ1y*fJ1y, fJ2x*fJ2x + fJ2y*fJ2y)); + + // stop if error measure does not improve anymore. This is a + // safety guard against floating point inaccuracies. + // stop if distance from line is guaranteed to be bounded by d + const bool bFurtherDivision(fLastDistanceError2 > fDistanceError2 && fDistanceError2 >= fDistanceBound2); + + if(bFurtherDivision) + { + // remember last error value + fLastDistanceError2 = fDistanceError2; + } + else { - rTarget.append(rfPB); + // stop recustion + nMaxRecursionDepth = 0; } } + + if(nMaxRecursionDepth) + { + // divide at 0.5 + const B2DPoint aS1L(average(rfPA, rfEA)); + const B2DPoint aS1C(average(rfEA, rfEB)); + const B2DPoint aS1R(average(rfEB, rfPB)); + const B2DPoint aS2L(average(aS1L, aS1C)); + const B2DPoint aS2R(average(aS1C, aS1R)); + const B2DPoint aS3C(average(aS2L, aS2R)); + + // left recursion + ImpSubDivDistance(rfPA, aS1L, aS2L, aS3C, rTarget, fDistanceBound2, fLastDistanceError2, nMaxRecursionDepth - 1); + + // right recursion + ImpSubDivDistance(aS3C, aS2R, aS1R, rfPB, rTarget, fDistanceBound2, fLastDistanceError2, nMaxRecursionDepth - 1); + } + else + { + rTarget.append(rfPB); + } } } // end of anonymous namespace } // end of namespace basegfx @@ -337,14 +385,6 @@ namespace basegfx { } - B2DCubicBezier::B2DCubicBezier(const B2DPoint& rStart, const B2DVector& rControlVectorA, const B2DVector& rControlVectorB, const B2DPoint& rEnd) - : maStartPoint(rStart), - maEndPoint(rEnd), - maControlPointA(rStart + rControlVectorA), - maControlPointB(rStart + rControlVectorB) - { - } - B2DCubicBezier::~B2DCubicBezier() { } @@ -394,7 +434,68 @@ namespace basegfx void B2DCubicBezier::testAndSolveTrivialBezier() { - // TODO + if(maControlPointA != maStartPoint || maControlPointB != maEndPoint) + { + const B2DVector aEdge(maEndPoint - maStartPoint); + + // controls parallel to edge can be trivial. No edge -> not parallel -> control can not be trivial + if(!aEdge.equalZero()) + { + const B2DVector aVecA(maControlPointA - maStartPoint); + const B2DVector aVecB(maControlPointB - maEndPoint); + const bool bAIsZero(aVecA.equalZero()); + const bool bBIsZero(aVecB.equalZero()); + bool bACanBeZero(false); + bool bBCanBeZero(false); + + if(!bAIsZero) + { + // parallel to edge? + if(areParallel(aVecA, aEdge)) + { + // get scale to edge + const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY()) ? aVecA.getX() / aEdge.getX() : aVecA.getY() / aEdge.getY()); + + // end point of vector in edge range? + if(fTools::more(fScale, 0.0) && fTools::lessOrEqual(fScale, 1.0)) + { + bACanBeZero = true; + } + } + } + + if(!bBIsZero) + { + // parallel to edge? + if(areParallel(aVecB, aEdge)) + { + // get scale to edge + const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY()) ? aVecB.getX() / aEdge.getX() : aVecB.getY() / aEdge.getY()); + + // end point of vector in edge range? Caution: controlB is directed AGAINST edge + if(fTools::less(fScale, 0.0) && fTools::moreOrEqual(fScale, -1.0)) + { + bBCanBeZero = true; + } + } + } + + // if both are/can be reduced, do it. + // Not possible if only one is/can be reduced (!) + if((bAIsZero || bACanBeZero) && (bBIsZero || bBCanBeZero)) + { + if(!bAIsZero) + { + maControlPointA = maStartPoint; + } + + if(!bBIsZero) + { + maControlPointB = maEndPoint; + } + } + } + } } double B2DCubicBezier::getEdgeLength() const @@ -407,44 +508,75 @@ namespace basegfx { const B2DVector aVectorA(maControlPointA - maStartPoint); const B2DVector aVectorB(maEndPoint - maControlPointB); - const B2DVector aTop(maControlPointB - maControlPointA); - return (aVectorA.getLength() + aVectorB.getLength() + aTop.getLength()); + + if(!aVectorA.equalZero() || !aVectorB.equalZero()) + { + const B2DVector aTop(maControlPointB - maControlPointA); + return (aVectorA.getLength() + aVectorB.getLength() + aTop.getLength()); + } + else + { + return getEdgeLength(); + } } - void B2DCubicBezier::adaptiveSubdivideByAngle(B2DPolygon& rTarget, double fAngleBound, - bool bAddLastPoint, bool bAllowUnsharpen) const + void B2DCubicBezier::adaptiveSubdivideByAngle(B2DPolygon& rTarget, double fAngleBound, bool bAllowUnsharpen) const { - // use support method #i37443# and allow unsharpen the criteria - ImpSubDivStart(maStartPoint, maControlPointA, maControlPointB, maEndPoint, - rTarget, fAngleBound * F_PI180, bAddLastPoint, bAllowUnsharpen); + if(isBezier()) + { + // use support method #i37443# and allow unsharpen the criteria + ImpSubDivAngleStart(maStartPoint, maControlPointA, maControlPointB, maEndPoint, rTarget, fAngleBound * F_PI180, bAllowUnsharpen); + } + else + { + rTarget.append(getEndPoint()); + } } // #i37443# adaptive subdivide by nCount subdivisions - void B2DCubicBezier::adaptiveSubdivideByCount(B2DPolygon& rTarget, sal_uInt32 nCount, bool bAddLastPoint) const + void B2DCubicBezier::adaptiveSubdivideByCount(B2DPolygon& rTarget, sal_uInt32 nCount) const { - rTarget.append(maStartPoint); - for(sal_uInt32 a(0L); a < nCount; a++) { const double fPos(double(a + 1L) / double(nCount + 1L)); rTarget.append(interpolatePoint(fPos)); } - if(bAddLastPoint) + rTarget.append(getEndPoint()); + } + + // adaptive subdivide by distance + void B2DCubicBezier::adaptiveSubdivideByDistance(B2DPolygon& rTarget, double fDistanceBound) const + { + if(isBezier()) + { + ImpSubDivDistance(maStartPoint, maControlPointA, maControlPointB, maEndPoint, rTarget, + fDistanceBound * fDistanceBound, ::std::numeric_limits<double>::max(), 30); + } + else { - rTarget.append(maEndPoint); + rTarget.append(getEndPoint()); } } B2DPoint B2DCubicBezier::interpolatePoint(double t) const { OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::interpolatePoint: Access out of range (!)"); - const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t)); - const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t)); - const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t)); - const B2DPoint aS2L(interpolate(aS1L, aS1C, t)); - const B2DPoint aS2R(interpolate(aS1C, aS1R, t)); - return interpolate(aS2L, aS2R, t); + + if(isBezier()) + { + const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t)); + const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t)); + const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t)); + const B2DPoint aS2L(interpolate(aS1L, aS1C, t)); + const B2DPoint aS2R(interpolate(aS1C, aS1R, t)); + + return interpolate(aS2L, aS2R, t); + } + else + { + return interpolate(maStartPoint, maEndPoint, t); + } } double B2DCubicBezier::getSmallestDistancePointToBezierSegment(const B2DPoint& rTestPoint, double& rCut) const @@ -453,7 +585,8 @@ namespace basegfx B2DPolygon aInitialPolygon; // as start make a fix division, creates nInitialDivisions + 2L points - adaptiveSubdivideByCount(aInitialPolygon, nInitialDivisions, true); + aInitialPolygon.append(getStartPoint()); + adaptiveSubdivideByCount(aInitialPolygon, nInitialDivisions); // now look for the closest point const sal_uInt32 nPointCount(aInitialPolygon.count()); @@ -553,22 +686,40 @@ namespace basegfx void B2DCubicBezier::split(double t, B2DCubicBezier& rBezierA, B2DCubicBezier& rBezierB) const { OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::split: Access out of range (!)"); - const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t)); - const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t)); - const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t)); - const B2DPoint aS2L(interpolate(aS1L, aS1C, t)); - const B2DPoint aS2R(interpolate(aS1C, aS1R, t)); - const B2DPoint aS3C(interpolate(aS2L, aS2R, t)); - - rBezierA.setStartPoint(maStartPoint); - rBezierA.setEndPoint(aS3C); - rBezierA.setControlPointA(aS1L); - rBezierA.setControlPointB(aS2L); - - rBezierB.setStartPoint(aS3C); - rBezierB.setEndPoint(maEndPoint); - rBezierB.setControlPointA(aS2R); - rBezierB.setControlPointB(aS1R); + + if(isBezier()) + { + const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t)); + const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t)); + const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t)); + const B2DPoint aS2L(interpolate(aS1L, aS1C, t)); + const B2DPoint aS2R(interpolate(aS1C, aS1R, t)); + const B2DPoint aS3C(interpolate(aS2L, aS2R, t)); + + rBezierA.setStartPoint(maStartPoint); + rBezierA.setEndPoint(aS3C); + rBezierA.setControlPointA(aS1L); + rBezierA.setControlPointB(aS2L); + + rBezierB.setStartPoint(aS3C); + rBezierB.setEndPoint(maEndPoint); + rBezierB.setControlPointA(aS2R); + rBezierB.setControlPointB(aS1R); + } + else + { + const B2DPoint aSplit(interpolate(maStartPoint, maEndPoint, t)); + + rBezierA.setStartPoint(maStartPoint); + rBezierA.setEndPoint(aSplit); + rBezierA.setControlPointA(maStartPoint); + rBezierA.setControlPointB(aSplit); + + rBezierB.setStartPoint(aSplit); + rBezierB.setEndPoint(maEndPoint); + rBezierB.setControlPointA(aSplit); + rBezierB.setControlPointB(maEndPoint); + } } B2DRange B2DCubicBezier::getRange() const |