1*09dbbe93SAndrew Rist /************************************************************** 2cdf0e10cSrcweir * 3*09dbbe93SAndrew Rist * Licensed to the Apache Software Foundation (ASF) under one 4*09dbbe93SAndrew Rist * or more contributor license agreements. See the NOTICE file 5*09dbbe93SAndrew Rist * distributed with this work for additional information 6*09dbbe93SAndrew Rist * regarding copyright ownership. The ASF licenses this file 7*09dbbe93SAndrew Rist * to you under the Apache License, Version 2.0 (the 8*09dbbe93SAndrew Rist * "License"); you may not use this file except in compliance 9*09dbbe93SAndrew Rist * with the License. You may obtain a copy of the License at 10*09dbbe93SAndrew Rist * 11*09dbbe93SAndrew Rist * http://www.apache.org/licenses/LICENSE-2.0 12*09dbbe93SAndrew Rist * 13*09dbbe93SAndrew Rist * Unless required by applicable law or agreed to in writing, 14*09dbbe93SAndrew Rist * software distributed under the License is distributed on an 15*09dbbe93SAndrew Rist * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16*09dbbe93SAndrew Rist * KIND, either express or implied. See the License for the 17*09dbbe93SAndrew Rist * specific language governing permissions and limitations 18*09dbbe93SAndrew Rist * under the License. 19*09dbbe93SAndrew Rist * 20*09dbbe93SAndrew Rist *************************************************************/ 21*09dbbe93SAndrew Rist 22*09dbbe93SAndrew Rist 23cdf0e10cSrcweir 24cdf0e10cSrcweir // MARKER(update_precomp.py): autogen include statement, do not remove 25cdf0e10cSrcweir #include "precompiled_basegfx.hxx" 26cdf0e10cSrcweir #include <basegfx/curve/b2dcubicbezier.hxx> 27cdf0e10cSrcweir #include <basegfx/vector/b2dvector.hxx> 28cdf0e10cSrcweir #include <basegfx/polygon/b2dpolygon.hxx> 29cdf0e10cSrcweir #include <basegfx/numeric/ftools.hxx> 30cdf0e10cSrcweir 31cdf0e10cSrcweir #include <limits> 32cdf0e10cSrcweir 33cdf0e10cSrcweir // #i37443# 34cdf0e10cSrcweir #define FACTOR_FOR_UNSHARPEN (1.6) 35cdf0e10cSrcweir #ifdef DBG_UTIL 36cdf0e10cSrcweir static double fMultFactUnsharpen = FACTOR_FOR_UNSHARPEN; 37cdf0e10cSrcweir #endif 38cdf0e10cSrcweir 39cdf0e10cSrcweir ////////////////////////////////////////////////////////////////////////////// 40cdf0e10cSrcweir 41cdf0e10cSrcweir namespace basegfx 42cdf0e10cSrcweir { 43cdf0e10cSrcweir namespace 44cdf0e10cSrcweir { ImpSubDivAngle(const B2DPoint & rfPA,const B2DPoint & rfEA,const B2DPoint & rfEB,const B2DPoint & rfPB,B2DPolygon & rTarget,double fAngleBound,bool bAllowUnsharpen,sal_uInt16 nMaxRecursionDepth)45cdf0e10cSrcweir void ImpSubDivAngle( 46cdf0e10cSrcweir const B2DPoint& rfPA, // start point 47cdf0e10cSrcweir const B2DPoint& rfEA, // edge on A 48cdf0e10cSrcweir const B2DPoint& rfEB, // edge on B 49cdf0e10cSrcweir const B2DPoint& rfPB, // end point 50cdf0e10cSrcweir B2DPolygon& rTarget, // target polygon 51cdf0e10cSrcweir double fAngleBound, // angle bound in [0.0 .. 2PI] 52cdf0e10cSrcweir bool bAllowUnsharpen, // #i37443# allow the criteria to get unsharp in recursions 53cdf0e10cSrcweir sal_uInt16 nMaxRecursionDepth) // endless loop protection 54cdf0e10cSrcweir { 55cdf0e10cSrcweir if(nMaxRecursionDepth) 56cdf0e10cSrcweir { 57cdf0e10cSrcweir // do angle test 58cdf0e10cSrcweir B2DVector aLeft(rfEA - rfPA); 59cdf0e10cSrcweir B2DVector aRight(rfEB - rfPB); 60cdf0e10cSrcweir 61cdf0e10cSrcweir // #i72104# 62cdf0e10cSrcweir if(aLeft.equalZero()) 63cdf0e10cSrcweir { 64cdf0e10cSrcweir aLeft = rfEB - rfPA; 65cdf0e10cSrcweir } 66cdf0e10cSrcweir 67cdf0e10cSrcweir if(aRight.equalZero()) 68cdf0e10cSrcweir { 69cdf0e10cSrcweir aRight = rfEA - rfPB; 70cdf0e10cSrcweir } 71cdf0e10cSrcweir 72cdf0e10cSrcweir const double fCurrentAngle(aLeft.angle(aRight)); 73cdf0e10cSrcweir 74cdf0e10cSrcweir if(fabs(fCurrentAngle) > (F_PI - fAngleBound)) 75cdf0e10cSrcweir { 76cdf0e10cSrcweir // end recursion 77cdf0e10cSrcweir nMaxRecursionDepth = 0; 78cdf0e10cSrcweir } 79cdf0e10cSrcweir else 80cdf0e10cSrcweir { 81cdf0e10cSrcweir if(bAllowUnsharpen) 82cdf0e10cSrcweir { 83cdf0e10cSrcweir // #i37443# unsharpen criteria 84cdf0e10cSrcweir #ifdef DBG_UTIL 85cdf0e10cSrcweir fAngleBound *= fMultFactUnsharpen; 86cdf0e10cSrcweir #else 87cdf0e10cSrcweir fAngleBound *= FACTOR_FOR_UNSHARPEN; 88cdf0e10cSrcweir #endif 89cdf0e10cSrcweir } 90cdf0e10cSrcweir } 91cdf0e10cSrcweir } 92cdf0e10cSrcweir 93cdf0e10cSrcweir if(nMaxRecursionDepth) 94cdf0e10cSrcweir { 95cdf0e10cSrcweir // divide at 0.5 96cdf0e10cSrcweir const B2DPoint aS1L(average(rfPA, rfEA)); 97cdf0e10cSrcweir const B2DPoint aS1C(average(rfEA, rfEB)); 98cdf0e10cSrcweir const B2DPoint aS1R(average(rfEB, rfPB)); 99cdf0e10cSrcweir const B2DPoint aS2L(average(aS1L, aS1C)); 100cdf0e10cSrcweir const B2DPoint aS2R(average(aS1C, aS1R)); 101cdf0e10cSrcweir const B2DPoint aS3C(average(aS2L, aS2R)); 102cdf0e10cSrcweir 103cdf0e10cSrcweir // left recursion 104cdf0e10cSrcweir ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1); 105cdf0e10cSrcweir 106cdf0e10cSrcweir // right recursion 107cdf0e10cSrcweir ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1); 108cdf0e10cSrcweir } 109cdf0e10cSrcweir else 110cdf0e10cSrcweir { 111cdf0e10cSrcweir rTarget.append(rfPB); 112cdf0e10cSrcweir } 113cdf0e10cSrcweir } 114cdf0e10cSrcweir ImpSubDivAngleStart(const B2DPoint & rfPA,const B2DPoint & rfEA,const B2DPoint & rfEB,const B2DPoint & rfPB,B2DPolygon & rTarget,const double & rfAngleBound,bool bAllowUnsharpen)115cdf0e10cSrcweir void ImpSubDivAngleStart( 116cdf0e10cSrcweir const B2DPoint& rfPA, // start point 117cdf0e10cSrcweir const B2DPoint& rfEA, // edge on A 118cdf0e10cSrcweir const B2DPoint& rfEB, // edge on B 119cdf0e10cSrcweir const B2DPoint& rfPB, // end point 120cdf0e10cSrcweir B2DPolygon& rTarget, // target polygon 121cdf0e10cSrcweir const double& rfAngleBound, // angle bound in [0.0 .. 2PI] 122cdf0e10cSrcweir bool bAllowUnsharpen) // #i37443# allow the criteria to get unsharp in recursions 123cdf0e10cSrcweir { 124cdf0e10cSrcweir sal_uInt16 nMaxRecursionDepth(8); 125cdf0e10cSrcweir const B2DVector aLeft(rfEA - rfPA); 126cdf0e10cSrcweir const B2DVector aRight(rfEB - rfPB); 127cdf0e10cSrcweir bool bLeftEqualZero(aLeft.equalZero()); 128cdf0e10cSrcweir bool bRightEqualZero(aRight.equalZero()); 129cdf0e10cSrcweir bool bAllParallel(false); 130cdf0e10cSrcweir 131cdf0e10cSrcweir if(bLeftEqualZero && bRightEqualZero) 132cdf0e10cSrcweir { 133cdf0e10cSrcweir nMaxRecursionDepth = 0; 134cdf0e10cSrcweir } 135cdf0e10cSrcweir else 136cdf0e10cSrcweir { 137cdf0e10cSrcweir const B2DVector aBase(rfPB - rfPA); 138cdf0e10cSrcweir const bool bBaseEqualZero(aBase.equalZero()); // #i72104# 139cdf0e10cSrcweir 140cdf0e10cSrcweir if(!bBaseEqualZero) 141cdf0e10cSrcweir { 142cdf0e10cSrcweir const bool bLeftParallel(bLeftEqualZero ? true : areParallel(aLeft, aBase)); 143cdf0e10cSrcweir const bool bRightParallel(bRightEqualZero ? true : areParallel(aRight, aBase)); 144cdf0e10cSrcweir 145cdf0e10cSrcweir if(bLeftParallel && bRightParallel) 146cdf0e10cSrcweir { 147cdf0e10cSrcweir bAllParallel = true; 148cdf0e10cSrcweir 149cdf0e10cSrcweir if(!bLeftEqualZero) 150cdf0e10cSrcweir { 151cdf0e10cSrcweir double fFactor; 152cdf0e10cSrcweir 153cdf0e10cSrcweir if(fabs(aBase.getX()) > fabs(aBase.getY())) 154cdf0e10cSrcweir { 155cdf0e10cSrcweir fFactor = aLeft.getX() / aBase.getX(); 156cdf0e10cSrcweir } 157cdf0e10cSrcweir else 158cdf0e10cSrcweir { 159cdf0e10cSrcweir fFactor = aLeft.getY() / aBase.getY(); 160cdf0e10cSrcweir } 161cdf0e10cSrcweir 162cdf0e10cSrcweir if(fFactor >= 0.0 && fFactor <= 1.0) 163cdf0e10cSrcweir { 164cdf0e10cSrcweir bLeftEqualZero = true; 165cdf0e10cSrcweir } 166cdf0e10cSrcweir } 167cdf0e10cSrcweir 168cdf0e10cSrcweir if(!bRightEqualZero) 169cdf0e10cSrcweir { 170cdf0e10cSrcweir double fFactor; 171cdf0e10cSrcweir 172cdf0e10cSrcweir if(fabs(aBase.getX()) > fabs(aBase.getY())) 173cdf0e10cSrcweir { 174cdf0e10cSrcweir fFactor = aRight.getX() / -aBase.getX(); 175cdf0e10cSrcweir } 176cdf0e10cSrcweir else 177cdf0e10cSrcweir { 178cdf0e10cSrcweir fFactor = aRight.getY() / -aBase.getY(); 179cdf0e10cSrcweir } 180cdf0e10cSrcweir 181cdf0e10cSrcweir if(fFactor >= 0.0 && fFactor <= 1.0) 182cdf0e10cSrcweir { 183cdf0e10cSrcweir bRightEqualZero = true; 184cdf0e10cSrcweir } 185cdf0e10cSrcweir } 186cdf0e10cSrcweir 187cdf0e10cSrcweir if(bLeftEqualZero && bRightEqualZero) 188cdf0e10cSrcweir { 189cdf0e10cSrcweir nMaxRecursionDepth = 0; 190cdf0e10cSrcweir } 191cdf0e10cSrcweir } 192cdf0e10cSrcweir } 193cdf0e10cSrcweir } 194cdf0e10cSrcweir 195cdf0e10cSrcweir if(nMaxRecursionDepth) 196cdf0e10cSrcweir { 197cdf0e10cSrcweir // divide at 0.5 ad test both edges for angle criteria 198cdf0e10cSrcweir const B2DPoint aS1L(average(rfPA, rfEA)); 199cdf0e10cSrcweir const B2DPoint aS1C(average(rfEA, rfEB)); 200cdf0e10cSrcweir const B2DPoint aS1R(average(rfEB, rfPB)); 201cdf0e10cSrcweir const B2DPoint aS2L(average(aS1L, aS1C)); 202cdf0e10cSrcweir const B2DPoint aS2R(average(aS1C, aS1R)); 203cdf0e10cSrcweir const B2DPoint aS3C(average(aS2L, aS2R)); 204cdf0e10cSrcweir 205cdf0e10cSrcweir // test left 206cdf0e10cSrcweir bool bAngleIsSmallerLeft(bAllParallel && bLeftEqualZero); 207cdf0e10cSrcweir if(!bAngleIsSmallerLeft) 208cdf0e10cSrcweir { 209cdf0e10cSrcweir const B2DVector aLeftLeft(bLeftEqualZero ? aS2L - aS1L : aS1L - rfPA); // #i72104# 210cdf0e10cSrcweir const B2DVector aRightLeft(aS2L - aS3C); 211cdf0e10cSrcweir const double fCurrentAngleLeft(aLeftLeft.angle(aRightLeft)); 212cdf0e10cSrcweir bAngleIsSmallerLeft = (fabs(fCurrentAngleLeft) > (F_PI - rfAngleBound)); 213cdf0e10cSrcweir } 214cdf0e10cSrcweir 215cdf0e10cSrcweir // test right 216cdf0e10cSrcweir bool bAngleIsSmallerRight(bAllParallel && bRightEqualZero); 217cdf0e10cSrcweir if(!bAngleIsSmallerRight) 218cdf0e10cSrcweir { 219cdf0e10cSrcweir const B2DVector aLeftRight(aS2R - aS3C); 220cdf0e10cSrcweir const B2DVector aRightRight(bRightEqualZero ? aS2R - aS1R : aS1R - rfPB); // #i72104# 221cdf0e10cSrcweir const double fCurrentAngleRight(aLeftRight.angle(aRightRight)); 222cdf0e10cSrcweir bAngleIsSmallerRight = (fabs(fCurrentAngleRight) > (F_PI - rfAngleBound)); 223cdf0e10cSrcweir } 224cdf0e10cSrcweir 225cdf0e10cSrcweir if(bAngleIsSmallerLeft && bAngleIsSmallerRight) 226cdf0e10cSrcweir { 227cdf0e10cSrcweir // no recursion necessary at all 228cdf0e10cSrcweir nMaxRecursionDepth = 0; 229cdf0e10cSrcweir } 230cdf0e10cSrcweir else 231cdf0e10cSrcweir { 232cdf0e10cSrcweir // left 233cdf0e10cSrcweir if(bAngleIsSmallerLeft) 234cdf0e10cSrcweir { 235cdf0e10cSrcweir rTarget.append(aS3C); 236cdf0e10cSrcweir } 237cdf0e10cSrcweir else 238cdf0e10cSrcweir { 239cdf0e10cSrcweir ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, rfAngleBound, bAllowUnsharpen, nMaxRecursionDepth); 240cdf0e10cSrcweir } 241cdf0e10cSrcweir 242cdf0e10cSrcweir // right 243cdf0e10cSrcweir if(bAngleIsSmallerRight) 244cdf0e10cSrcweir { 245cdf0e10cSrcweir rTarget.append(rfPB); 246cdf0e10cSrcweir } 247cdf0e10cSrcweir else 248cdf0e10cSrcweir { 249cdf0e10cSrcweir ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, rfAngleBound, bAllowUnsharpen, nMaxRecursionDepth); 250cdf0e10cSrcweir } 251cdf0e10cSrcweir } 252cdf0e10cSrcweir } 253cdf0e10cSrcweir 254cdf0e10cSrcweir if(!nMaxRecursionDepth) 255cdf0e10cSrcweir { 256cdf0e10cSrcweir rTarget.append(rfPB); 257cdf0e10cSrcweir } 258cdf0e10cSrcweir } 259cdf0e10cSrcweir ImpSubDivDistance(const B2DPoint & rfPA,const B2DPoint & rfEA,const B2DPoint & rfEB,const B2DPoint & rfPB,B2DPolygon & rTarget,double fDistanceBound2,double fLastDistanceError2,sal_uInt16 nMaxRecursionDepth)260cdf0e10cSrcweir void ImpSubDivDistance( 261cdf0e10cSrcweir const B2DPoint& rfPA, // start point 262cdf0e10cSrcweir const B2DPoint& rfEA, // edge on A 263cdf0e10cSrcweir const B2DPoint& rfEB, // edge on B 264cdf0e10cSrcweir const B2DPoint& rfPB, // end point 265cdf0e10cSrcweir B2DPolygon& rTarget, // target polygon 266cdf0e10cSrcweir double fDistanceBound2, // quadratic distance criteria 267cdf0e10cSrcweir double fLastDistanceError2, // the last quadratic distance error 268cdf0e10cSrcweir sal_uInt16 nMaxRecursionDepth) // endless loop protection 269cdf0e10cSrcweir { 270cdf0e10cSrcweir if(nMaxRecursionDepth) 271cdf0e10cSrcweir { 272cdf0e10cSrcweir // decide if another recursion is needed. If not, set 273cdf0e10cSrcweir // nMaxRecursionDepth to zero 274cdf0e10cSrcweir 275cdf0e10cSrcweir // Perform bezier flatness test (lecture notes from R. Schaback, 276cdf0e10cSrcweir // Mathematics of Computer-Aided Design, Uni Goettingen, 2000) 277cdf0e10cSrcweir // 278cdf0e10cSrcweir // ||P(t) - L(t)|| <= max ||b_j - b_0 - j/n(b_n - b_0)|| 279cdf0e10cSrcweir // 0<=j<=n 280cdf0e10cSrcweir // 281cdf0e10cSrcweir // What is calculated here is an upper bound to the distance from 282cdf0e10cSrcweir // a line through b_0 and b_3 (rfPA and P4 in our notation) and the 283cdf0e10cSrcweir // curve. We can drop 0 and n from the running indices, since the 284cdf0e10cSrcweir // argument of max becomes zero for those cases. 285cdf0e10cSrcweir const double fJ1x(rfEA.getX() - rfPA.getX() - 1.0/3.0*(rfPB.getX() - rfPA.getX())); 286cdf0e10cSrcweir const double fJ1y(rfEA.getY() - rfPA.getY() - 1.0/3.0*(rfPB.getY() - rfPA.getY())); 287cdf0e10cSrcweir const double fJ2x(rfEB.getX() - rfPA.getX() - 2.0/3.0*(rfPB.getX() - rfPA.getX())); 288cdf0e10cSrcweir const double fJ2y(rfEB.getY() - rfPA.getY() - 2.0/3.0*(rfPB.getY() - rfPA.getY())); 289cdf0e10cSrcweir const double fDistanceError2(::std::max(fJ1x*fJ1x + fJ1y*fJ1y, fJ2x*fJ2x + fJ2y*fJ2y)); 290cdf0e10cSrcweir 291cdf0e10cSrcweir // stop if error measure does not improve anymore. This is a 292cdf0e10cSrcweir // safety guard against floating point inaccuracies. 293cdf0e10cSrcweir // stop if distance from line is guaranteed to be bounded by d 294cdf0e10cSrcweir const bool bFurtherDivision(fLastDistanceError2 > fDistanceError2 && fDistanceError2 >= fDistanceBound2); 295cdf0e10cSrcweir 296cdf0e10cSrcweir if(bFurtherDivision) 297cdf0e10cSrcweir { 298cdf0e10cSrcweir // remember last error value 299cdf0e10cSrcweir fLastDistanceError2 = fDistanceError2; 300cdf0e10cSrcweir } 301cdf0e10cSrcweir else 302cdf0e10cSrcweir { 303cdf0e10cSrcweir // stop recustion 304cdf0e10cSrcweir nMaxRecursionDepth = 0; 305cdf0e10cSrcweir } 306cdf0e10cSrcweir } 307cdf0e10cSrcweir 308cdf0e10cSrcweir if(nMaxRecursionDepth) 309cdf0e10cSrcweir { 310cdf0e10cSrcweir // divide at 0.5 311cdf0e10cSrcweir const B2DPoint aS1L(average(rfPA, rfEA)); 312cdf0e10cSrcweir const B2DPoint aS1C(average(rfEA, rfEB)); 313cdf0e10cSrcweir const B2DPoint aS1R(average(rfEB, rfPB)); 314cdf0e10cSrcweir const B2DPoint aS2L(average(aS1L, aS1C)); 315cdf0e10cSrcweir const B2DPoint aS2R(average(aS1C, aS1R)); 316cdf0e10cSrcweir const B2DPoint aS3C(average(aS2L, aS2R)); 317cdf0e10cSrcweir 318cdf0e10cSrcweir // left recursion 319cdf0e10cSrcweir ImpSubDivDistance(rfPA, aS1L, aS2L, aS3C, rTarget, fDistanceBound2, fLastDistanceError2, nMaxRecursionDepth - 1); 320cdf0e10cSrcweir 321cdf0e10cSrcweir // right recursion 322cdf0e10cSrcweir ImpSubDivDistance(aS3C, aS2R, aS1R, rfPB, rTarget, fDistanceBound2, fLastDistanceError2, nMaxRecursionDepth - 1); 323cdf0e10cSrcweir } 324cdf0e10cSrcweir else 325cdf0e10cSrcweir { 326cdf0e10cSrcweir rTarget.append(rfPB); 327cdf0e10cSrcweir } 328cdf0e10cSrcweir } 329cdf0e10cSrcweir } // end of anonymous namespace 330cdf0e10cSrcweir } // end of namespace basegfx 331cdf0e10cSrcweir 332cdf0e10cSrcweir ////////////////////////////////////////////////////////////////////////////// 333cdf0e10cSrcweir 334cdf0e10cSrcweir namespace basegfx 335cdf0e10cSrcweir { B2DCubicBezier(const B2DCubicBezier & rBezier)336cdf0e10cSrcweir B2DCubicBezier::B2DCubicBezier(const B2DCubicBezier& rBezier) 337cdf0e10cSrcweir : maStartPoint(rBezier.maStartPoint), 338cdf0e10cSrcweir maEndPoint(rBezier.maEndPoint), 339cdf0e10cSrcweir maControlPointA(rBezier.maControlPointA), 340cdf0e10cSrcweir maControlPointB(rBezier.maControlPointB) 341cdf0e10cSrcweir { 342cdf0e10cSrcweir } 343cdf0e10cSrcweir B2DCubicBezier()344cdf0e10cSrcweir B2DCubicBezier::B2DCubicBezier() 345cdf0e10cSrcweir { 346cdf0e10cSrcweir } 347cdf0e10cSrcweir B2DCubicBezier(const B2DPoint & rStart,const B2DPoint & rEnd)348cdf0e10cSrcweir B2DCubicBezier::B2DCubicBezier(const B2DPoint& rStart, const B2DPoint& rEnd) 349cdf0e10cSrcweir : maStartPoint(rStart), 350cdf0e10cSrcweir maEndPoint(rEnd), 351cdf0e10cSrcweir maControlPointA(rStart), 352cdf0e10cSrcweir maControlPointB(rEnd) 353cdf0e10cSrcweir { 354cdf0e10cSrcweir } 355cdf0e10cSrcweir B2DCubicBezier(const B2DPoint & rStart,const B2DPoint & rControlPointA,const B2DPoint & rControlPointB,const B2DPoint & rEnd)356cdf0e10cSrcweir B2DCubicBezier::B2DCubicBezier(const B2DPoint& rStart, const B2DPoint& rControlPointA, const B2DPoint& rControlPointB, const B2DPoint& rEnd) 357cdf0e10cSrcweir : maStartPoint(rStart), 358cdf0e10cSrcweir maEndPoint(rEnd), 359cdf0e10cSrcweir maControlPointA(rControlPointA), 360cdf0e10cSrcweir maControlPointB(rControlPointB) 361cdf0e10cSrcweir { 362cdf0e10cSrcweir } 363cdf0e10cSrcweir ~B2DCubicBezier()364cdf0e10cSrcweir B2DCubicBezier::~B2DCubicBezier() 365cdf0e10cSrcweir { 366cdf0e10cSrcweir } 367cdf0e10cSrcweir 368cdf0e10cSrcweir // assignment operator operator =(const B2DCubicBezier & rBezier)369cdf0e10cSrcweir B2DCubicBezier& B2DCubicBezier::operator=(const B2DCubicBezier& rBezier) 370cdf0e10cSrcweir { 371cdf0e10cSrcweir maStartPoint = rBezier.maStartPoint; 372cdf0e10cSrcweir maEndPoint = rBezier.maEndPoint; 373cdf0e10cSrcweir maControlPointA = rBezier.maControlPointA; 374cdf0e10cSrcweir maControlPointB = rBezier.maControlPointB; 375cdf0e10cSrcweir 376cdf0e10cSrcweir return *this; 377cdf0e10cSrcweir } 378cdf0e10cSrcweir 379cdf0e10cSrcweir // compare operators operator ==(const B2DCubicBezier & rBezier) const380cdf0e10cSrcweir bool B2DCubicBezier::operator==(const B2DCubicBezier& rBezier) const 381cdf0e10cSrcweir { 382cdf0e10cSrcweir return ( 383cdf0e10cSrcweir maStartPoint == rBezier.maStartPoint 384cdf0e10cSrcweir && maEndPoint == rBezier.maEndPoint 385cdf0e10cSrcweir && maControlPointA == rBezier.maControlPointA 386cdf0e10cSrcweir && maControlPointB == rBezier.maControlPointB 387cdf0e10cSrcweir ); 388cdf0e10cSrcweir } 389cdf0e10cSrcweir operator !=(const B2DCubicBezier & rBezier) const390cdf0e10cSrcweir bool B2DCubicBezier::operator!=(const B2DCubicBezier& rBezier) const 391cdf0e10cSrcweir { 392cdf0e10cSrcweir return ( 393cdf0e10cSrcweir maStartPoint != rBezier.maStartPoint 394cdf0e10cSrcweir || maEndPoint != rBezier.maEndPoint 395cdf0e10cSrcweir || maControlPointA != rBezier.maControlPointA 396cdf0e10cSrcweir || maControlPointB != rBezier.maControlPointB 397cdf0e10cSrcweir ); 398cdf0e10cSrcweir } 399cdf0e10cSrcweir equal(const B2DCubicBezier & rBezier) const400cdf0e10cSrcweir bool B2DCubicBezier::equal(const B2DCubicBezier& rBezier) const 401cdf0e10cSrcweir { 402cdf0e10cSrcweir return ( 403cdf0e10cSrcweir maStartPoint.equal(rBezier.maStartPoint) 404cdf0e10cSrcweir && maEndPoint.equal(rBezier.maEndPoint) 405cdf0e10cSrcweir && maControlPointA.equal(rBezier.maControlPointA) 406cdf0e10cSrcweir && maControlPointB.equal(rBezier.maControlPointB) 407cdf0e10cSrcweir ); 408cdf0e10cSrcweir } 409cdf0e10cSrcweir 410cdf0e10cSrcweir // test if vectors are used isBezier() const411cdf0e10cSrcweir bool B2DCubicBezier::isBezier() const 412cdf0e10cSrcweir { 413cdf0e10cSrcweir if(maControlPointA != maStartPoint || maControlPointB != maEndPoint) 414cdf0e10cSrcweir { 415cdf0e10cSrcweir return true; 416cdf0e10cSrcweir } 417cdf0e10cSrcweir 418cdf0e10cSrcweir return false; 419cdf0e10cSrcweir } 420cdf0e10cSrcweir testAndSolveTrivialBezier()421cdf0e10cSrcweir void B2DCubicBezier::testAndSolveTrivialBezier() 422cdf0e10cSrcweir { 423cdf0e10cSrcweir if(maControlPointA != maStartPoint || maControlPointB != maEndPoint) 424cdf0e10cSrcweir { 425cdf0e10cSrcweir const B2DVector aEdge(maEndPoint - maStartPoint); 426cdf0e10cSrcweir 427cdf0e10cSrcweir // controls parallel to edge can be trivial. No edge -> not parallel -> control can 428cdf0e10cSrcweir // still not be trivial (e.g. ballon loop) 429cdf0e10cSrcweir if(!aEdge.equalZero()) 430cdf0e10cSrcweir { 431cdf0e10cSrcweir // get control vectors 432cdf0e10cSrcweir const B2DVector aVecA(maControlPointA - maStartPoint); 433cdf0e10cSrcweir const B2DVector aVecB(maControlPointB - maEndPoint); 434cdf0e10cSrcweir 435cdf0e10cSrcweir // check if trivial per se 436cdf0e10cSrcweir bool bAIsTrivial(aVecA.equalZero()); 437cdf0e10cSrcweir bool bBIsTrivial(aVecB.equalZero()); 438cdf0e10cSrcweir 439cdf0e10cSrcweir // #i102241# prepare inverse edge length to normalize cross values; 440cdf0e10cSrcweir // else the small compare value used in fTools::equalZero 441cdf0e10cSrcweir // will be length dependent and this detection will work as less 442cdf0e10cSrcweir // precise as longer the edge is. In principle, the length of the control 443cdf0e10cSrcweir // vector would need to be used too, but to be trivial it is assumed to 444cdf0e10cSrcweir // be of roughly equal length to the edge, so edge length can be used 445cdf0e10cSrcweir // for both. Only needed when one of both is not trivial per se. 446cdf0e10cSrcweir const double fInverseEdgeLength(bAIsTrivial && bBIsTrivial 447cdf0e10cSrcweir ? 1.0 448cdf0e10cSrcweir : 1.0 / aEdge.getLength()); 449cdf0e10cSrcweir 450cdf0e10cSrcweir // if A is not zero, check if it could be 451cdf0e10cSrcweir if(!bAIsTrivial) 452cdf0e10cSrcweir { 453cdf0e10cSrcweir // #i102241# parallel to edge? Check aVecA, aEdge. Use cross() which does what 454cdf0e10cSrcweir // we need here with the precision we need 455cdf0e10cSrcweir const double fCross(aVecA.cross(aEdge) * fInverseEdgeLength); 456cdf0e10cSrcweir 457cdf0e10cSrcweir if(fTools::equalZero(fCross)) 458cdf0e10cSrcweir { 459cdf0e10cSrcweir // get scale to edge. Use bigger distance for numeric quality 460cdf0e10cSrcweir const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY()) 461cdf0e10cSrcweir ? aVecA.getX() / aEdge.getX() 462cdf0e10cSrcweir : aVecA.getY() / aEdge.getY()); 463cdf0e10cSrcweir 464cdf0e10cSrcweir // relative end point of vector in edge range? 465cdf0e10cSrcweir if(fTools::moreOrEqual(fScale, 0.0) && fTools::lessOrEqual(fScale, 1.0)) 466cdf0e10cSrcweir { 467cdf0e10cSrcweir bAIsTrivial = true; 468cdf0e10cSrcweir } 469cdf0e10cSrcweir } 470cdf0e10cSrcweir } 471cdf0e10cSrcweir 472cdf0e10cSrcweir // if B is not zero, check if it could be, but only if A is already trivial; 473cdf0e10cSrcweir // else solve to trivial will not be possible for whole edge 474cdf0e10cSrcweir if(bAIsTrivial && !bBIsTrivial) 475cdf0e10cSrcweir { 476cdf0e10cSrcweir // parallel to edge? Check aVecB, aEdge 477cdf0e10cSrcweir const double fCross(aVecB.cross(aEdge) * fInverseEdgeLength); 478cdf0e10cSrcweir 479cdf0e10cSrcweir if(fTools::equalZero(fCross)) 480cdf0e10cSrcweir { 481cdf0e10cSrcweir // get scale to edge. Use bigger distance for numeric quality 482cdf0e10cSrcweir const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY()) 483cdf0e10cSrcweir ? aVecB.getX() / aEdge.getX() 484cdf0e10cSrcweir : aVecB.getY() / aEdge.getY()); 485cdf0e10cSrcweir 486cdf0e10cSrcweir // end point of vector in edge range? Caution: controlB is directed AGAINST edge 487cdf0e10cSrcweir if(fTools::lessOrEqual(fScale, 0.0) && fTools::moreOrEqual(fScale, -1.0)) 488cdf0e10cSrcweir { 489cdf0e10cSrcweir bBIsTrivial = true; 490cdf0e10cSrcweir } 491cdf0e10cSrcweir } 492cdf0e10cSrcweir } 493cdf0e10cSrcweir 494cdf0e10cSrcweir // if both are/can be reduced, do it. 495cdf0e10cSrcweir // Not possible if only one is/can be reduced (!) 496cdf0e10cSrcweir if(bAIsTrivial && bBIsTrivial) 497cdf0e10cSrcweir { 498cdf0e10cSrcweir maControlPointA = maStartPoint; 499cdf0e10cSrcweir maControlPointB = maEndPoint; 500cdf0e10cSrcweir } 501cdf0e10cSrcweir } 502cdf0e10cSrcweir } 503cdf0e10cSrcweir } 504cdf0e10cSrcweir 505cdf0e10cSrcweir namespace { impGetLength(const B2DCubicBezier & rEdge,double fDeviation,sal_uInt32 nRecursionWatch)506cdf0e10cSrcweir double impGetLength(const B2DCubicBezier& rEdge, double fDeviation, sal_uInt32 nRecursionWatch) 507cdf0e10cSrcweir { 508cdf0e10cSrcweir const double fEdgeLength(rEdge.getEdgeLength()); 509cdf0e10cSrcweir const double fControlPolygonLength(rEdge.getControlPolygonLength()); 510cdf0e10cSrcweir const double fCurrentDeviation(fTools::equalZero(fControlPolygonLength) ? 0.0 : 1.0 - (fEdgeLength / fControlPolygonLength)); 511cdf0e10cSrcweir 512cdf0e10cSrcweir if(!nRecursionWatch || fTools:: lessOrEqual(fCurrentDeviation, fDeviation)) 513cdf0e10cSrcweir { 514cdf0e10cSrcweir return (fEdgeLength + fControlPolygonLength) * 0.5; 515cdf0e10cSrcweir } 516cdf0e10cSrcweir else 517cdf0e10cSrcweir { 518cdf0e10cSrcweir B2DCubicBezier aLeft, aRight; 519cdf0e10cSrcweir const double fNewDeviation(fDeviation * 0.5); 520cdf0e10cSrcweir const sal_uInt32 nNewRecursionWatch(nRecursionWatch - 1); 521cdf0e10cSrcweir 522cdf0e10cSrcweir rEdge.split(0.5, &aLeft, &aRight); 523cdf0e10cSrcweir 524cdf0e10cSrcweir return impGetLength(aLeft, fNewDeviation, nNewRecursionWatch) 525cdf0e10cSrcweir + impGetLength(aRight, fNewDeviation, nNewRecursionWatch); 526cdf0e10cSrcweir } 527cdf0e10cSrcweir } 528cdf0e10cSrcweir } 529cdf0e10cSrcweir getLength(double fDeviation) const530cdf0e10cSrcweir double B2DCubicBezier::getLength(double fDeviation) const 531cdf0e10cSrcweir { 532cdf0e10cSrcweir if(isBezier()) 533cdf0e10cSrcweir { 534cdf0e10cSrcweir if(fDeviation < 0.00000001) 535cdf0e10cSrcweir { 536cdf0e10cSrcweir fDeviation = 0.00000001; 537cdf0e10cSrcweir } 538cdf0e10cSrcweir 539cdf0e10cSrcweir return impGetLength(*this, fDeviation, 6); 540cdf0e10cSrcweir } 541cdf0e10cSrcweir else 542cdf0e10cSrcweir { 543cdf0e10cSrcweir return B2DVector(getEndPoint() - getStartPoint()).getLength(); 544cdf0e10cSrcweir } 545cdf0e10cSrcweir } 546cdf0e10cSrcweir getEdgeLength() const547cdf0e10cSrcweir double B2DCubicBezier::getEdgeLength() const 548cdf0e10cSrcweir { 549cdf0e10cSrcweir const B2DVector aEdge(maEndPoint - maStartPoint); 550cdf0e10cSrcweir return aEdge.getLength(); 551cdf0e10cSrcweir } 552cdf0e10cSrcweir getControlPolygonLength() const553cdf0e10cSrcweir double B2DCubicBezier::getControlPolygonLength() const 554cdf0e10cSrcweir { 555cdf0e10cSrcweir const B2DVector aVectorA(maControlPointA - maStartPoint); 556cdf0e10cSrcweir const B2DVector aVectorB(maEndPoint - maControlPointB); 557cdf0e10cSrcweir 558cdf0e10cSrcweir if(!aVectorA.equalZero() || !aVectorB.equalZero()) 559cdf0e10cSrcweir { 560cdf0e10cSrcweir const B2DVector aTop(maControlPointB - maControlPointA); 561cdf0e10cSrcweir return (aVectorA.getLength() + aVectorB.getLength() + aTop.getLength()); 562cdf0e10cSrcweir } 563cdf0e10cSrcweir else 564cdf0e10cSrcweir { 565cdf0e10cSrcweir return getEdgeLength(); 566cdf0e10cSrcweir } 567cdf0e10cSrcweir } 568cdf0e10cSrcweir adaptiveSubdivideByAngle(B2DPolygon & rTarget,double fAngleBound,bool bAllowUnsharpen) const569cdf0e10cSrcweir void B2DCubicBezier::adaptiveSubdivideByAngle(B2DPolygon& rTarget, double fAngleBound, bool bAllowUnsharpen) const 570cdf0e10cSrcweir { 571cdf0e10cSrcweir if(isBezier()) 572cdf0e10cSrcweir { 573cdf0e10cSrcweir // use support method #i37443# and allow unsharpen the criteria 574cdf0e10cSrcweir ImpSubDivAngleStart(maStartPoint, maControlPointA, maControlPointB, maEndPoint, rTarget, fAngleBound * F_PI180, bAllowUnsharpen); 575cdf0e10cSrcweir } 576cdf0e10cSrcweir else 577cdf0e10cSrcweir { 578cdf0e10cSrcweir rTarget.append(getEndPoint()); 579cdf0e10cSrcweir } 580cdf0e10cSrcweir } 581cdf0e10cSrcweir getTangent(double t) const582cdf0e10cSrcweir B2DVector B2DCubicBezier::getTangent(double t) const 583cdf0e10cSrcweir { 584cdf0e10cSrcweir if(fTools::lessOrEqual(t, 0.0)) 585cdf0e10cSrcweir { 586cdf0e10cSrcweir // tangent in start point 587cdf0e10cSrcweir B2DVector aTangent(getControlPointA() - getStartPoint()); 588cdf0e10cSrcweir 589cdf0e10cSrcweir if(!aTangent.equalZero()) 590cdf0e10cSrcweir { 591cdf0e10cSrcweir return aTangent; 592cdf0e10cSrcweir } 593cdf0e10cSrcweir 594cdf0e10cSrcweir // start point and control vector are the same, fallback 595cdf0e10cSrcweir // to implicit start vector to control point B 596cdf0e10cSrcweir aTangent = (getControlPointB() - getStartPoint()) * 0.3; 597cdf0e10cSrcweir 598cdf0e10cSrcweir if(!aTangent.equalZero()) 599cdf0e10cSrcweir { 600cdf0e10cSrcweir return aTangent; 601cdf0e10cSrcweir } 602cdf0e10cSrcweir 603cdf0e10cSrcweir // not a bezier at all, return edge vector 604cdf0e10cSrcweir return (getEndPoint() - getStartPoint()) * 0.3; 605cdf0e10cSrcweir } 606cdf0e10cSrcweir else if(fTools::moreOrEqual(t, 1.0)) 607cdf0e10cSrcweir { 608cdf0e10cSrcweir // tangent in end point 609cdf0e10cSrcweir B2DVector aTangent(getEndPoint() - getControlPointB()); 610cdf0e10cSrcweir 611cdf0e10cSrcweir if(!aTangent.equalZero()) 612cdf0e10cSrcweir { 613cdf0e10cSrcweir return aTangent; 614cdf0e10cSrcweir } 615cdf0e10cSrcweir 616cdf0e10cSrcweir // end point and control vector are the same, fallback 617cdf0e10cSrcweir // to implicit start vector from control point A 618cdf0e10cSrcweir aTangent = (getEndPoint() - getControlPointA()) * 0.3; 619cdf0e10cSrcweir 620cdf0e10cSrcweir if(!aTangent.equalZero()) 621cdf0e10cSrcweir { 622cdf0e10cSrcweir return aTangent; 623cdf0e10cSrcweir } 624cdf0e10cSrcweir 625cdf0e10cSrcweir // not a bezier at all, return edge vector 626cdf0e10cSrcweir return (getEndPoint() - getStartPoint()) * 0.3; 627cdf0e10cSrcweir } 628cdf0e10cSrcweir else 629cdf0e10cSrcweir { 630cdf0e10cSrcweir // t is in ]0.0 .. 1.0[. Split and extract 631cdf0e10cSrcweir B2DCubicBezier aRight; 632cdf0e10cSrcweir split(t, 0, &aRight); 633cdf0e10cSrcweir 634cdf0e10cSrcweir return aRight.getControlPointA() - aRight.getStartPoint(); 635cdf0e10cSrcweir } 636cdf0e10cSrcweir } 637cdf0e10cSrcweir 638cdf0e10cSrcweir // #i37443# adaptive subdivide by nCount subdivisions adaptiveSubdivideByCount(B2DPolygon & rTarget,sal_uInt32 nCount) const639cdf0e10cSrcweir void B2DCubicBezier::adaptiveSubdivideByCount(B2DPolygon& rTarget, sal_uInt32 nCount) const 640cdf0e10cSrcweir { 641cdf0e10cSrcweir const double fLenFact(1.0 / static_cast< double >(nCount + 1)); 642cdf0e10cSrcweir 643cdf0e10cSrcweir for(sal_uInt32 a(1); a <= nCount; a++) 644cdf0e10cSrcweir { 645cdf0e10cSrcweir const double fPos(static_cast< double >(a) * fLenFact); 646cdf0e10cSrcweir rTarget.append(interpolatePoint(fPos)); 647cdf0e10cSrcweir } 648cdf0e10cSrcweir 649cdf0e10cSrcweir rTarget.append(getEndPoint()); 650cdf0e10cSrcweir } 651cdf0e10cSrcweir 652cdf0e10cSrcweir // adaptive subdivide by distance adaptiveSubdivideByDistance(B2DPolygon & rTarget,double fDistanceBound) const653cdf0e10cSrcweir void B2DCubicBezier::adaptiveSubdivideByDistance(B2DPolygon& rTarget, double fDistanceBound) const 654cdf0e10cSrcweir { 655cdf0e10cSrcweir if(isBezier()) 656cdf0e10cSrcweir { 657cdf0e10cSrcweir ImpSubDivDistance(maStartPoint, maControlPointA, maControlPointB, maEndPoint, rTarget, 658cdf0e10cSrcweir fDistanceBound * fDistanceBound, ::std::numeric_limits<double>::max(), 30); 659cdf0e10cSrcweir } 660cdf0e10cSrcweir else 661cdf0e10cSrcweir { 662cdf0e10cSrcweir rTarget.append(getEndPoint()); 663cdf0e10cSrcweir } 664cdf0e10cSrcweir } 665cdf0e10cSrcweir interpolatePoint(double t) const666cdf0e10cSrcweir B2DPoint B2DCubicBezier::interpolatePoint(double t) const 667cdf0e10cSrcweir { 668cdf0e10cSrcweir OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::interpolatePoint: Access out of range (!)"); 669cdf0e10cSrcweir 670cdf0e10cSrcweir if(isBezier()) 671cdf0e10cSrcweir { 672cdf0e10cSrcweir const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t)); 673cdf0e10cSrcweir const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t)); 674cdf0e10cSrcweir const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t)); 675cdf0e10cSrcweir const B2DPoint aS2L(interpolate(aS1L, aS1C, t)); 676cdf0e10cSrcweir const B2DPoint aS2R(interpolate(aS1C, aS1R, t)); 677cdf0e10cSrcweir 678cdf0e10cSrcweir return interpolate(aS2L, aS2R, t); 679cdf0e10cSrcweir } 680cdf0e10cSrcweir else 681cdf0e10cSrcweir { 682cdf0e10cSrcweir return interpolate(maStartPoint, maEndPoint, t); 683cdf0e10cSrcweir } 684cdf0e10cSrcweir } 685cdf0e10cSrcweir getSmallestDistancePointToBezierSegment(const B2DPoint & rTestPoint,double & rCut) const686cdf0e10cSrcweir double B2DCubicBezier::getSmallestDistancePointToBezierSegment(const B2DPoint& rTestPoint, double& rCut) const 687cdf0e10cSrcweir { 688cdf0e10cSrcweir const sal_uInt32 nInitialDivisions(3L); 689cdf0e10cSrcweir B2DPolygon aInitialPolygon; 690cdf0e10cSrcweir 691cdf0e10cSrcweir // as start make a fix division, creates nInitialDivisions + 2L points 692cdf0e10cSrcweir aInitialPolygon.append(getStartPoint()); 693cdf0e10cSrcweir adaptiveSubdivideByCount(aInitialPolygon, nInitialDivisions); 694cdf0e10cSrcweir 695cdf0e10cSrcweir // now look for the closest point 696cdf0e10cSrcweir const sal_uInt32 nPointCount(aInitialPolygon.count()); 697cdf0e10cSrcweir B2DVector aVector(rTestPoint - aInitialPolygon.getB2DPoint(0L)); 698cdf0e10cSrcweir double fQuadDist(aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY()); 699cdf0e10cSrcweir double fNewQuadDist; 700cdf0e10cSrcweir sal_uInt32 nSmallestIndex(0L); 701cdf0e10cSrcweir 702cdf0e10cSrcweir for(sal_uInt32 a(1L); a < nPointCount; a++) 703cdf0e10cSrcweir { 704cdf0e10cSrcweir aVector = B2DVector(rTestPoint - aInitialPolygon.getB2DPoint(a)); 705cdf0e10cSrcweir fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY(); 706cdf0e10cSrcweir 707cdf0e10cSrcweir if(fNewQuadDist < fQuadDist) 708cdf0e10cSrcweir { 709cdf0e10cSrcweir fQuadDist = fNewQuadDist; 710cdf0e10cSrcweir nSmallestIndex = a; 711cdf0e10cSrcweir } 712cdf0e10cSrcweir } 713cdf0e10cSrcweir 714cdf0e10cSrcweir // look right and left for even smaller distances 715cdf0e10cSrcweir double fStepValue(1.0 / (double)((nPointCount - 1L) * 2L)); // half the edge step width 716cdf0e10cSrcweir double fPosition((double)nSmallestIndex / (double)(nPointCount - 1L)); 717cdf0e10cSrcweir bool bDone(false); 718cdf0e10cSrcweir 719cdf0e10cSrcweir while(!bDone) 720cdf0e10cSrcweir { 721cdf0e10cSrcweir if(!bDone) 722cdf0e10cSrcweir { 723cdf0e10cSrcweir // test left 724cdf0e10cSrcweir double fPosLeft(fPosition - fStepValue); 725cdf0e10cSrcweir 726cdf0e10cSrcweir if(fPosLeft < 0.0) 727cdf0e10cSrcweir { 728cdf0e10cSrcweir fPosLeft = 0.0; 729cdf0e10cSrcweir aVector = B2DVector(rTestPoint - maStartPoint); 730cdf0e10cSrcweir } 731cdf0e10cSrcweir else 732cdf0e10cSrcweir { 733cdf0e10cSrcweir aVector = B2DVector(rTestPoint - interpolatePoint(fPosLeft)); 734cdf0e10cSrcweir } 735cdf0e10cSrcweir 736cdf0e10cSrcweir fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY(); 737cdf0e10cSrcweir 738cdf0e10cSrcweir if(fTools::less(fNewQuadDist, fQuadDist)) 739cdf0e10cSrcweir { 740cdf0e10cSrcweir fQuadDist = fNewQuadDist; 741cdf0e10cSrcweir fPosition = fPosLeft; 742cdf0e10cSrcweir } 743cdf0e10cSrcweir else 744cdf0e10cSrcweir { 745cdf0e10cSrcweir // test right 746cdf0e10cSrcweir double fPosRight(fPosition + fStepValue); 747cdf0e10cSrcweir 748cdf0e10cSrcweir if(fPosRight > 1.0) 749cdf0e10cSrcweir { 750cdf0e10cSrcweir fPosRight = 1.0; 751cdf0e10cSrcweir aVector = B2DVector(rTestPoint - maEndPoint); 752cdf0e10cSrcweir } 753cdf0e10cSrcweir else 754cdf0e10cSrcweir { 755cdf0e10cSrcweir aVector = B2DVector(rTestPoint - interpolatePoint(fPosRight)); 756cdf0e10cSrcweir } 757cdf0e10cSrcweir 758cdf0e10cSrcweir fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY(); 759cdf0e10cSrcweir 760cdf0e10cSrcweir if(fTools::less(fNewQuadDist, fQuadDist)) 761cdf0e10cSrcweir { 762cdf0e10cSrcweir fQuadDist = fNewQuadDist; 763cdf0e10cSrcweir fPosition = fPosRight; 764cdf0e10cSrcweir } 765cdf0e10cSrcweir else 766cdf0e10cSrcweir { 767cdf0e10cSrcweir // not less left or right, done 768cdf0e10cSrcweir bDone = true; 769cdf0e10cSrcweir } 770cdf0e10cSrcweir } 771cdf0e10cSrcweir } 772cdf0e10cSrcweir 773cdf0e10cSrcweir if(0.0 == fPosition || 1.0 == fPosition) 774cdf0e10cSrcweir { 775cdf0e10cSrcweir // if we are completely left or right, we are done 776cdf0e10cSrcweir bDone = true; 777cdf0e10cSrcweir } 778cdf0e10cSrcweir 779cdf0e10cSrcweir if(!bDone) 780cdf0e10cSrcweir { 781cdf0e10cSrcweir // prepare next step value 782cdf0e10cSrcweir fStepValue /= 2.0; 783cdf0e10cSrcweir } 784cdf0e10cSrcweir } 785cdf0e10cSrcweir 786cdf0e10cSrcweir rCut = fPosition; 787cdf0e10cSrcweir return sqrt(fQuadDist); 788cdf0e10cSrcweir } 789cdf0e10cSrcweir split(double t,B2DCubicBezier * pBezierA,B2DCubicBezier * pBezierB) const790cdf0e10cSrcweir void B2DCubicBezier::split(double t, B2DCubicBezier* pBezierA, B2DCubicBezier* pBezierB) const 791cdf0e10cSrcweir { 792cdf0e10cSrcweir OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::split: Access out of range (!)"); 793cdf0e10cSrcweir 794cdf0e10cSrcweir if(!pBezierA && !pBezierB) 795cdf0e10cSrcweir { 796cdf0e10cSrcweir return; 797cdf0e10cSrcweir } 798cdf0e10cSrcweir 799cdf0e10cSrcweir if(isBezier()) 800cdf0e10cSrcweir { 801cdf0e10cSrcweir const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t)); 802cdf0e10cSrcweir const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t)); 803cdf0e10cSrcweir const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t)); 804cdf0e10cSrcweir const B2DPoint aS2L(interpolate(aS1L, aS1C, t)); 805cdf0e10cSrcweir const B2DPoint aS2R(interpolate(aS1C, aS1R, t)); 806cdf0e10cSrcweir const B2DPoint aS3C(interpolate(aS2L, aS2R, t)); 807cdf0e10cSrcweir 808cdf0e10cSrcweir if(pBezierA) 809cdf0e10cSrcweir { 810cdf0e10cSrcweir pBezierA->setStartPoint(maStartPoint); 811cdf0e10cSrcweir pBezierA->setEndPoint(aS3C); 812cdf0e10cSrcweir pBezierA->setControlPointA(aS1L); 813cdf0e10cSrcweir pBezierA->setControlPointB(aS2L); 814cdf0e10cSrcweir } 815cdf0e10cSrcweir 816cdf0e10cSrcweir if(pBezierB) 817cdf0e10cSrcweir { 818cdf0e10cSrcweir pBezierB->setStartPoint(aS3C); 819cdf0e10cSrcweir pBezierB->setEndPoint(maEndPoint); 820cdf0e10cSrcweir pBezierB->setControlPointA(aS2R); 821cdf0e10cSrcweir pBezierB->setControlPointB(aS1R); 822cdf0e10cSrcweir } 823cdf0e10cSrcweir } 824cdf0e10cSrcweir else 825cdf0e10cSrcweir { 826cdf0e10cSrcweir const B2DPoint aSplit(interpolate(maStartPoint, maEndPoint, t)); 827cdf0e10cSrcweir 828cdf0e10cSrcweir if(pBezierA) 829cdf0e10cSrcweir { 830cdf0e10cSrcweir pBezierA->setStartPoint(maStartPoint); 831cdf0e10cSrcweir pBezierA->setEndPoint(aSplit); 832cdf0e10cSrcweir pBezierA->setControlPointA(maStartPoint); 833cdf0e10cSrcweir pBezierA->setControlPointB(aSplit); 834cdf0e10cSrcweir } 835cdf0e10cSrcweir 836cdf0e10cSrcweir if(pBezierB) 837cdf0e10cSrcweir { 838cdf0e10cSrcweir pBezierB->setStartPoint(aSplit); 839cdf0e10cSrcweir pBezierB->setEndPoint(maEndPoint); 840cdf0e10cSrcweir pBezierB->setControlPointA(aSplit); 841cdf0e10cSrcweir pBezierB->setControlPointB(maEndPoint); 842cdf0e10cSrcweir } 843cdf0e10cSrcweir } 844cdf0e10cSrcweir } 845cdf0e10cSrcweir snippet(double fStart,double fEnd) const846cdf0e10cSrcweir B2DCubicBezier B2DCubicBezier::snippet(double fStart, double fEnd) const 847cdf0e10cSrcweir { 848cdf0e10cSrcweir B2DCubicBezier aRetval; 849cdf0e10cSrcweir 850cdf0e10cSrcweir if(fTools::more(fStart, 1.0)) 851cdf0e10cSrcweir { 852cdf0e10cSrcweir fStart = 1.0; 853cdf0e10cSrcweir } 854cdf0e10cSrcweir else if(fTools::less(fStart, 0.0)) 855cdf0e10cSrcweir { 856cdf0e10cSrcweir fStart = 0.0; 857cdf0e10cSrcweir } 858cdf0e10cSrcweir 859cdf0e10cSrcweir if(fTools::more(fEnd, 1.0)) 860cdf0e10cSrcweir { 861cdf0e10cSrcweir fEnd = 1.0; 862cdf0e10cSrcweir } 863cdf0e10cSrcweir else if(fTools::less(fEnd, 0.0)) 864cdf0e10cSrcweir { 865cdf0e10cSrcweir fEnd = 0.0; 866cdf0e10cSrcweir } 867cdf0e10cSrcweir 868cdf0e10cSrcweir if(fEnd <= fStart) 869cdf0e10cSrcweir { 870cdf0e10cSrcweir // empty or NULL, create single point at center 871cdf0e10cSrcweir const double fSplit((fEnd + fStart) * 0.5); 872cdf0e10cSrcweir const B2DPoint aPoint(interpolate(getStartPoint(), getEndPoint(), fSplit)); 873cdf0e10cSrcweir aRetval.setStartPoint(aPoint); 874cdf0e10cSrcweir aRetval.setEndPoint(aPoint); 875cdf0e10cSrcweir aRetval.setControlPointA(aPoint); 876cdf0e10cSrcweir aRetval.setControlPointB(aPoint); 877cdf0e10cSrcweir } 878cdf0e10cSrcweir else 879cdf0e10cSrcweir { 880cdf0e10cSrcweir if(isBezier()) 881cdf0e10cSrcweir { 882cdf0e10cSrcweir // copy bezier; cut off right, then cut off left. Do not forget to 883cdf0e10cSrcweir // adapt cut value when both cuts happen 884cdf0e10cSrcweir const bool bEndIsOne(fTools::equal(fEnd, 1.0)); 885cdf0e10cSrcweir const bool bStartIsZero(fTools::equalZero(fStart)); 886cdf0e10cSrcweir aRetval = *this; 887cdf0e10cSrcweir 888cdf0e10cSrcweir if(!bEndIsOne) 889cdf0e10cSrcweir { 890cdf0e10cSrcweir aRetval.split(fEnd, &aRetval, 0); 891cdf0e10cSrcweir 892cdf0e10cSrcweir if(!bStartIsZero) 893cdf0e10cSrcweir { 894cdf0e10cSrcweir fStart /= fEnd; 895cdf0e10cSrcweir } 896cdf0e10cSrcweir } 897cdf0e10cSrcweir 898cdf0e10cSrcweir if(!bStartIsZero) 899cdf0e10cSrcweir { 900cdf0e10cSrcweir aRetval.split(fStart, 0, &aRetval); 901cdf0e10cSrcweir } 902cdf0e10cSrcweir } 903cdf0e10cSrcweir else 904cdf0e10cSrcweir { 905cdf0e10cSrcweir // no bezier, create simple edge 906cdf0e10cSrcweir const B2DPoint aPointA(interpolate(getStartPoint(), getEndPoint(), fStart)); 907cdf0e10cSrcweir const B2DPoint aPointB(interpolate(getStartPoint(), getEndPoint(), fEnd)); 908cdf0e10cSrcweir aRetval.setStartPoint(aPointA); 909cdf0e10cSrcweir aRetval.setEndPoint(aPointB); 910cdf0e10cSrcweir aRetval.setControlPointA(aPointA); 911cdf0e10cSrcweir aRetval.setControlPointB(aPointB); 912cdf0e10cSrcweir } 913cdf0e10cSrcweir } 914cdf0e10cSrcweir 915cdf0e10cSrcweir return aRetval; 916cdf0e10cSrcweir } 917cdf0e10cSrcweir getRange() const918cdf0e10cSrcweir B2DRange B2DCubicBezier::getRange() const 919cdf0e10cSrcweir { 920cdf0e10cSrcweir B2DRange aRetval(maStartPoint, maEndPoint); 921cdf0e10cSrcweir 922cdf0e10cSrcweir aRetval.expand(maControlPointA); 923cdf0e10cSrcweir aRetval.expand(maControlPointB); 924cdf0e10cSrcweir 925cdf0e10cSrcweir return aRetval; 926cdf0e10cSrcweir } 927cdf0e10cSrcweir getMinimumExtremumPosition(double & rfResult) const928cdf0e10cSrcweir bool B2DCubicBezier::getMinimumExtremumPosition(double& rfResult) const 929cdf0e10cSrcweir { 930cdf0e10cSrcweir ::std::vector< double > aAllResults; 931cdf0e10cSrcweir 932cdf0e10cSrcweir aAllResults.reserve(4); 933cdf0e10cSrcweir getAllExtremumPositions(aAllResults); 934cdf0e10cSrcweir 935cdf0e10cSrcweir const sal_uInt32 nCount(aAllResults.size()); 936cdf0e10cSrcweir 937cdf0e10cSrcweir if(!nCount) 938cdf0e10cSrcweir { 939cdf0e10cSrcweir return false; 940cdf0e10cSrcweir } 941cdf0e10cSrcweir else if(1 == nCount) 942cdf0e10cSrcweir { 943cdf0e10cSrcweir rfResult = aAllResults[0]; 944cdf0e10cSrcweir return true; 945cdf0e10cSrcweir } 946cdf0e10cSrcweir else 947cdf0e10cSrcweir { 948cdf0e10cSrcweir rfResult = *(::std::min_element(aAllResults.begin(), aAllResults.end())); 949cdf0e10cSrcweir return true; 950cdf0e10cSrcweir } 951cdf0e10cSrcweir } 952cdf0e10cSrcweir 953cdf0e10cSrcweir namespace 954cdf0e10cSrcweir { impCheckExtremumResult(double fCandidate,::std::vector<double> & rResult)955cdf0e10cSrcweir inline void impCheckExtremumResult(double fCandidate, ::std::vector< double >& rResult) 956cdf0e10cSrcweir { 957cdf0e10cSrcweir // check for range ]0.0 .. 1.0[ with excluding 1.0 and 0.0 clearly 958cdf0e10cSrcweir // by using the equalZero test, NOT ::more or ::less which will use the 959cdf0e10cSrcweir // ApproxEqual() which is too exact here 960cdf0e10cSrcweir if(fCandidate > 0.0 && !fTools::equalZero(fCandidate)) 961cdf0e10cSrcweir { 962cdf0e10cSrcweir if(fCandidate < 1.0 && !fTools::equalZero(fCandidate - 1.0)) 963cdf0e10cSrcweir { 964cdf0e10cSrcweir rResult.push_back(fCandidate); 965cdf0e10cSrcweir } 966cdf0e10cSrcweir } 967cdf0e10cSrcweir } 968cdf0e10cSrcweir } 969cdf0e10cSrcweir getAllExtremumPositions(::std::vector<double> & rResults) const970cdf0e10cSrcweir void B2DCubicBezier::getAllExtremumPositions(::std::vector< double >& rResults) const 971cdf0e10cSrcweir { 972cdf0e10cSrcweir rResults.clear(); 973cdf0e10cSrcweir 974cdf0e10cSrcweir // calculate the x-extrema parameters by zeroing first x-derivative 975cdf0e10cSrcweir // of the cubic bezier's parametric formula, which results in a 976cdf0e10cSrcweir // quadratic equation: dBezier/dt = t*t*fAX - 2*t*fBX + fCX 977cdf0e10cSrcweir const B2DPoint aControlDiff( maControlPointA - maControlPointB ); 978cdf0e10cSrcweir double fCX = maControlPointA.getX() - maStartPoint.getX(); 979cdf0e10cSrcweir const double fBX = fCX + aControlDiff.getX(); 980cdf0e10cSrcweir const double fAX = 3 * aControlDiff.getX() + (maEndPoint.getX() - maStartPoint.getX()); 981cdf0e10cSrcweir 982cdf0e10cSrcweir if(fTools::equalZero(fCX)) 983cdf0e10cSrcweir { 984cdf0e10cSrcweir // detect fCX equal zero and truncate to real zero value in that case 985cdf0e10cSrcweir fCX = 0.0; 986cdf0e10cSrcweir } 987cdf0e10cSrcweir 988cdf0e10cSrcweir if( !fTools::equalZero(fAX) ) 989cdf0e10cSrcweir { 990cdf0e10cSrcweir // derivative is polynomial of order 2 => use binomial formula 991cdf0e10cSrcweir const double fD = fBX*fBX - fAX*fCX; 992cdf0e10cSrcweir if( fD >= 0.0 ) 993cdf0e10cSrcweir { 994cdf0e10cSrcweir const double fS = sqrt(fD); 995cdf0e10cSrcweir // calculate both roots (avoiding a numerically unstable subtraction) 996cdf0e10cSrcweir const double fQ = fBX + ((fBX >= 0) ? +fS : -fS); 997cdf0e10cSrcweir impCheckExtremumResult(fQ / fAX, rResults); 998cdf0e10cSrcweir if( !fTools::equalZero(fS) ) // ignore root multiplicity 999cdf0e10cSrcweir impCheckExtremumResult(fCX / fQ, rResults); 1000cdf0e10cSrcweir } 1001cdf0e10cSrcweir } 1002cdf0e10cSrcweir else if( !fTools::equalZero(fBX) ) 1003cdf0e10cSrcweir { 1004cdf0e10cSrcweir // derivative is polynomial of order 1 => one extrema 1005cdf0e10cSrcweir impCheckExtremumResult(fCX / (2 * fBX), rResults); 1006cdf0e10cSrcweir } 1007cdf0e10cSrcweir 1008cdf0e10cSrcweir // calculate the y-extrema parameters by zeroing first y-derivative 1009cdf0e10cSrcweir double fCY = maControlPointA.getY() - maStartPoint.getY(); 1010cdf0e10cSrcweir const double fBY = fCY + aControlDiff.getY(); 1011cdf0e10cSrcweir const double fAY = 3 * aControlDiff.getY() + (maEndPoint.getY() - maStartPoint.getY()); 1012cdf0e10cSrcweir 1013cdf0e10cSrcweir if(fTools::equalZero(fCY)) 1014cdf0e10cSrcweir { 1015cdf0e10cSrcweir // detect fCY equal zero and truncate to real zero value in that case 1016cdf0e10cSrcweir fCY = 0.0; 1017cdf0e10cSrcweir } 1018cdf0e10cSrcweir 1019cdf0e10cSrcweir if( !fTools::equalZero(fAY) ) 1020cdf0e10cSrcweir { 1021cdf0e10cSrcweir // derivative is polynomial of order 2 => use binomial formula 1022cdf0e10cSrcweir const double fD = fBY*fBY - fAY*fCY; 1023cdf0e10cSrcweir if( fD >= 0.0 ) 1024cdf0e10cSrcweir { 1025cdf0e10cSrcweir const double fS = sqrt(fD); 1026cdf0e10cSrcweir // calculate both roots (avoiding a numerically unstable subtraction) 1027cdf0e10cSrcweir const double fQ = fBY + ((fBY >= 0) ? +fS : -fS); 1028cdf0e10cSrcweir impCheckExtremumResult(fQ / fAY, rResults); 1029cdf0e10cSrcweir if( !fTools::equalZero(fS) ) // ignore root multiplicity 1030cdf0e10cSrcweir impCheckExtremumResult(fCY / fQ, rResults); 1031cdf0e10cSrcweir } 1032cdf0e10cSrcweir } 1033cdf0e10cSrcweir else if( !fTools::equalZero(fBY) ) 1034cdf0e10cSrcweir { 1035cdf0e10cSrcweir // derivative is polynomial of order 1 => one extrema 1036cdf0e10cSrcweir impCheckExtremumResult(fCY / (2 * fBY), rResults); 1037cdf0e10cSrcweir } 1038cdf0e10cSrcweir } 1039cdf0e10cSrcweir getMaxDistancePositions(double pResult[2]) const1040cdf0e10cSrcweir int B2DCubicBezier::getMaxDistancePositions( double pResult[2]) const 1041cdf0e10cSrcweir { 1042cdf0e10cSrcweir // the distance from the bezier to a line through start and end 1043cdf0e10cSrcweir // is proportional to (ENDx-STARTx,ENDy-STARTy)*(+BEZIERy(t)-STARTy,-BEZIERx(t)-STARTx) 1044cdf0e10cSrcweir // this distance becomes zero for at least t==0 and t==1 1045cdf0e10cSrcweir // its extrema that are between 0..1 are interesting as split candidates 1046cdf0e10cSrcweir // its derived function has the form dD/dt = fA*t^2 + 2*fB*t + fC 1047cdf0e10cSrcweir const B2DPoint aRelativeEndPoint(maEndPoint-maStartPoint); 1048cdf0e10cSrcweir const double fA = (3 * (maControlPointA.getX() - maControlPointB.getX()) + aRelativeEndPoint.getX()) * aRelativeEndPoint.getY() 1049cdf0e10cSrcweir - (3 * (maControlPointA.getY() - maControlPointB.getY()) + aRelativeEndPoint.getY()) * aRelativeEndPoint.getX(); 1050cdf0e10cSrcweir const double fB = (maControlPointB.getX() - 2 * maControlPointA.getX() + maStartPoint.getX()) * aRelativeEndPoint.getY() 1051cdf0e10cSrcweir - (maControlPointB.getY() - 2 * maControlPointA.getY() + maStartPoint.getY()) * aRelativeEndPoint.getX(); 1052cdf0e10cSrcweir const double fC = (maControlPointA.getX() - maStartPoint.getX()) * aRelativeEndPoint.getY() 1053cdf0e10cSrcweir - (maControlPointA.getY() - maStartPoint.getY()) * aRelativeEndPoint.getX(); 1054cdf0e10cSrcweir 1055cdf0e10cSrcweir // test for degenerated case: order<2 1056cdf0e10cSrcweir if( fTools::equalZero(fA) ) 1057cdf0e10cSrcweir { 1058cdf0e10cSrcweir // test for degenerated case: order==0 1059cdf0e10cSrcweir if( fTools::equalZero(fB) ) 1060cdf0e10cSrcweir return 0; 1061cdf0e10cSrcweir 1062cdf0e10cSrcweir // solving the order==1 polynomial is trivial 1063cdf0e10cSrcweir pResult[0] = -fC / (2*fB); 1064cdf0e10cSrcweir 1065cdf0e10cSrcweir // test root and ignore it when it is outside the curve 1066cdf0e10cSrcweir int nCount = ((pResult[0] > 0) && (pResult[0] < 1)); 1067cdf0e10cSrcweir return nCount; 1068cdf0e10cSrcweir } 1069cdf0e10cSrcweir 1070cdf0e10cSrcweir // derivative is polynomial of order 2 1071cdf0e10cSrcweir // check if the polynomial has non-imaginary roots 1072cdf0e10cSrcweir const double fD = fB*fB - fA*fC; 1073cdf0e10cSrcweir if( fD >= 0.0 ) // TODO: is this test needed? geometrically not IMHO 1074cdf0e10cSrcweir { 1075cdf0e10cSrcweir // calculate first root (avoiding a numerically unstable subtraction) 1076cdf0e10cSrcweir const double fS = sqrt(fD); 1077cdf0e10cSrcweir const double fQ = -(fB + ((fB >= 0) ? +fS : -fS)); 1078cdf0e10cSrcweir pResult[0] = fQ / fA; 1079cdf0e10cSrcweir // ignore root when it is outside the curve 1080cdf0e10cSrcweir static const double fEps = 1e-9; 1081cdf0e10cSrcweir int nCount = ((pResult[0] > fEps) && (pResult[0] < fEps)); 1082cdf0e10cSrcweir 1083cdf0e10cSrcweir // ignore root multiplicity 1084cdf0e10cSrcweir if( !fTools::equalZero(fD) ) 1085cdf0e10cSrcweir { 1086cdf0e10cSrcweir // calculate the other root 1087cdf0e10cSrcweir const double fRoot = fC / fQ; 1088cdf0e10cSrcweir // ignore root when it is outside the curve 1089cdf0e10cSrcweir if( (fRoot > fEps) && (fRoot < 1.0-fEps) ) 1090cdf0e10cSrcweir pResult[ nCount++ ] = fRoot; 1091cdf0e10cSrcweir } 1092cdf0e10cSrcweir 1093cdf0e10cSrcweir return nCount; 1094cdf0e10cSrcweir } 1095cdf0e10cSrcweir 1096cdf0e10cSrcweir return 0; 1097cdf0e10cSrcweir } 1098cdf0e10cSrcweir 1099cdf0e10cSrcweir } // end of namespace basegfx 1100cdf0e10cSrcweir 1101cdf0e10cSrcweir // eof 1102