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