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