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 <osl/diagnose.h> 31 #include <basegfx/polygon/b3dpolygontools.hxx> 32 #include <basegfx/polygon/b3dpolygon.hxx> 33 #include <basegfx/numeric/ftools.hxx> 34 #include <basegfx/range/b3drange.hxx> 35 #include <basegfx/point/b2dpoint.hxx> 36 #include <basegfx/matrix/b3dhommatrix.hxx> 37 #include <basegfx/polygon/b2dpolygon.hxx> 38 #include <basegfx/polygon/b2dpolygontools.hxx> 39 #include <basegfx/tuple/b3ituple.hxx> 40 #include <numeric> 41 42 ////////////////////////////////////////////////////////////////////////////// 43 44 namespace basegfx 45 { 46 namespace tools 47 { 48 // B3DPolygon tools 49 void checkClosed(B3DPolygon& rCandidate) 50 { 51 while(rCandidate.count() > 1L 52 && rCandidate.getB3DPoint(0L).equal(rCandidate.getB3DPoint(rCandidate.count() - 1L))) 53 { 54 rCandidate.setClosed(true); 55 rCandidate.remove(rCandidate.count() - 1L); 56 } 57 } 58 59 // Get successor and predecessor indices. Returning the same index means there 60 // is none. Same for successor. 61 sal_uInt32 getIndexOfPredecessor(sal_uInt32 nIndex, const B3DPolygon& rCandidate) 62 { 63 OSL_ENSURE(nIndex < rCandidate.count(), "getIndexOfPredecessor: Access to polygon out of range (!)"); 64 65 if(nIndex) 66 { 67 return nIndex - 1L; 68 } 69 else if(rCandidate.count()) 70 { 71 return rCandidate.count() - 1L; 72 } 73 else 74 { 75 return nIndex; 76 } 77 } 78 79 sal_uInt32 getIndexOfSuccessor(sal_uInt32 nIndex, const B3DPolygon& rCandidate) 80 { 81 OSL_ENSURE(nIndex < rCandidate.count(), "getIndexOfPredecessor: Access to polygon out of range (!)"); 82 83 if(nIndex + 1L < rCandidate.count()) 84 { 85 return nIndex + 1L; 86 } 87 else 88 { 89 return 0L; 90 } 91 } 92 93 B3DRange getRange(const B3DPolygon& rCandidate) 94 { 95 B3DRange aRetval; 96 const sal_uInt32 nPointCount(rCandidate.count()); 97 98 for(sal_uInt32 a(0L); a < nPointCount; a++) 99 { 100 const B3DPoint aTestPoint(rCandidate.getB3DPoint(a)); 101 aRetval.expand(aTestPoint); 102 } 103 104 return aRetval; 105 } 106 107 B3DVector getNormal(const B3DPolygon& rCandidate) 108 { 109 return rCandidate.getNormal(); 110 } 111 112 B3DVector getPositiveOrientedNormal(const B3DPolygon& rCandidate) 113 { 114 B3DVector aRetval(rCandidate.getNormal()); 115 116 if(ORIENTATION_NEGATIVE == getOrientation(rCandidate)) 117 { 118 aRetval = -aRetval; 119 } 120 121 return aRetval; 122 } 123 124 B2VectorOrientation getOrientation(const B3DPolygon& rCandidate) 125 { 126 B2VectorOrientation eRetval(ORIENTATION_NEUTRAL); 127 128 if(rCandidate.count() > 2L) 129 { 130 const double fSignedArea(getSignedArea(rCandidate)); 131 132 if(fSignedArea > 0.0) 133 { 134 eRetval = ORIENTATION_POSITIVE; 135 } 136 else if(fSignedArea < 0.0) 137 { 138 eRetval = ORIENTATION_NEGATIVE; 139 } 140 } 141 142 return eRetval; 143 } 144 145 double getSignedArea(const B3DPolygon& rCandidate) 146 { 147 double fRetval(0.0); 148 const sal_uInt32 nPointCount(rCandidate.count()); 149 150 if(nPointCount > 2) 151 { 152 const B3DVector aAbsNormal(absolute(getNormal(rCandidate))); 153 sal_uInt16 nCase(3); // default: ignore z 154 155 if(aAbsNormal.getX() > aAbsNormal.getY()) 156 { 157 if(aAbsNormal.getX() > aAbsNormal.getZ()) 158 { 159 nCase = 1; // ignore x 160 } 161 } 162 else if(aAbsNormal.getY() > aAbsNormal.getZ()) 163 { 164 nCase = 2; // ignore y 165 } 166 167 B3DPoint aPreviousPoint(rCandidate.getB3DPoint(nPointCount - 1L)); 168 169 for(sal_uInt32 a(0L); a < nPointCount; a++) 170 { 171 const B3DPoint aCurrentPoint(rCandidate.getB3DPoint(a)); 172 173 switch(nCase) 174 { 175 case 1: // ignore x 176 fRetval += aPreviousPoint.getZ() * aCurrentPoint.getY(); 177 fRetval -= aPreviousPoint.getY() * aCurrentPoint.getZ(); 178 break; 179 case 2: // ignore y 180 fRetval += aPreviousPoint.getX() * aCurrentPoint.getZ(); 181 fRetval -= aPreviousPoint.getZ() * aCurrentPoint.getX(); 182 break; 183 case 3: // ignore z 184 fRetval += aPreviousPoint.getX() * aCurrentPoint.getY(); 185 fRetval -= aPreviousPoint.getY() * aCurrentPoint.getX(); 186 break; 187 } 188 189 // prepare next step 190 aPreviousPoint = aCurrentPoint; 191 } 192 193 switch(nCase) 194 { 195 case 1: // ignore x 196 fRetval /= 2.0 * aAbsNormal.getX(); 197 break; 198 case 2: // ignore y 199 fRetval /= 2.0 * aAbsNormal.getY(); 200 break; 201 case 3: // ignore z 202 fRetval /= 2.0 * aAbsNormal.getZ(); 203 break; 204 } 205 } 206 207 return fRetval; 208 } 209 210 double getArea(const B3DPolygon& rCandidate) 211 { 212 double fRetval(0.0); 213 214 if(rCandidate.count() > 2) 215 { 216 fRetval = getSignedArea(rCandidate); 217 const double fZero(0.0); 218 219 if(fTools::less(fRetval, fZero)) 220 { 221 fRetval = -fRetval; 222 } 223 } 224 225 return fRetval; 226 } 227 228 double getEdgeLength(const B3DPolygon& rCandidate, sal_uInt32 nIndex) 229 { 230 OSL_ENSURE(nIndex < rCandidate.count(), "getEdgeLength: Access to polygon out of range (!)"); 231 double fRetval(0.0); 232 const sal_uInt32 nPointCount(rCandidate.count()); 233 234 if(nIndex < nPointCount) 235 { 236 if(rCandidate.isClosed() || ((nIndex + 1L) != nPointCount)) 237 { 238 const sal_uInt32 nNextIndex(getIndexOfSuccessor(nIndex, rCandidate)); 239 const B3DPoint aCurrentPoint(rCandidate.getB3DPoint(nIndex)); 240 const B3DPoint aNextPoint(rCandidate.getB3DPoint(nNextIndex)); 241 const B3DVector aVector(aNextPoint - aCurrentPoint); 242 fRetval = aVector.getLength(); 243 } 244 } 245 246 return fRetval; 247 } 248 249 double getLength(const B3DPolygon& rCandidate) 250 { 251 double fRetval(0.0); 252 const sal_uInt32 nPointCount(rCandidate.count()); 253 254 if(nPointCount > 1L) 255 { 256 const sal_uInt32 nLoopCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); 257 258 for(sal_uInt32 a(0L); a < nLoopCount; a++) 259 { 260 const sal_uInt32 nNextIndex(getIndexOfSuccessor(a, rCandidate)); 261 const B3DPoint aCurrentPoint(rCandidate.getB3DPoint(a)); 262 const B3DPoint aNextPoint(rCandidate.getB3DPoint(nNextIndex)); 263 const B3DVector aVector(aNextPoint - aCurrentPoint); 264 fRetval += aVector.getLength(); 265 } 266 } 267 268 return fRetval; 269 } 270 271 B3DPoint getPositionAbsolute(const B3DPolygon& rCandidate, double fDistance, double fLength) 272 { 273 B3DPoint aRetval; 274 const sal_uInt32 nPointCount(rCandidate.count()); 275 276 if(nPointCount > 1L) 277 { 278 sal_uInt32 nIndex(0L); 279 bool bIndexDone(false); 280 const double fZero(0.0); 281 double fEdgeLength(fZero); 282 283 // get length if not given 284 if(fTools::equalZero(fLength)) 285 { 286 fLength = getLength(rCandidate); 287 } 288 289 // handle fDistance < 0.0 290 if(fTools::less(fDistance, fZero)) 291 { 292 if(rCandidate.isClosed()) 293 { 294 // if fDistance < 0.0 increment with multiple of fLength 295 sal_uInt32 nCount(sal_uInt32(-fDistance / fLength)); 296 fDistance += double(nCount + 1L) * fLength; 297 } 298 else 299 { 300 // crop to polygon start 301 fDistance = fZero; 302 bIndexDone = true; 303 } 304 } 305 306 // handle fDistance >= fLength 307 if(fTools::moreOrEqual(fDistance, fLength)) 308 { 309 if(rCandidate.isClosed()) 310 { 311 // if fDistance >= fLength decrement with multiple of fLength 312 sal_uInt32 nCount(sal_uInt32(fDistance / fLength)); 313 fDistance -= (double)(nCount) * fLength; 314 } 315 else 316 { 317 // crop to polygon end 318 fDistance = fZero; 319 nIndex = nPointCount - 1L; 320 bIndexDone = true; 321 } 322 } 323 324 // look for correct index. fDistance is now [0.0 .. fLength[ 325 if(!bIndexDone) 326 { 327 do 328 { 329 // get length of next edge 330 fEdgeLength = getEdgeLength(rCandidate, nIndex); 331 332 if(fTools::moreOrEqual(fDistance, fEdgeLength)) 333 { 334 // go to next edge 335 fDistance -= fEdgeLength; 336 nIndex++; 337 } 338 else 339 { 340 // it's on this edge, stop 341 bIndexDone = true; 342 } 343 } while (!bIndexDone); 344 } 345 346 // get the point using nIndex 347 aRetval = rCandidate.getB3DPoint(nIndex); 348 349 // if fDistance != 0.0, move that length on the edge. The edge 350 // length is in fEdgeLength. 351 if(!fTools::equalZero(fDistance)) 352 { 353 sal_uInt32 nNextIndex(getIndexOfSuccessor(nIndex, rCandidate)); 354 const B3DPoint aNextPoint(rCandidate.getB3DPoint(nNextIndex)); 355 double fRelative(fZero); 356 357 if(!fTools::equalZero(fEdgeLength)) 358 { 359 fRelative = fDistance / fEdgeLength; 360 } 361 362 // add calculated average value to the return value 363 aRetval += interpolate(aRetval, aNextPoint, fRelative); 364 } 365 } 366 367 return aRetval; 368 } 369 370 B3DPoint getPositionRelative(const B3DPolygon& rCandidate, double fDistance, double fLength) 371 { 372 // get length if not given 373 if(fTools::equalZero(fLength)) 374 { 375 fLength = getLength(rCandidate); 376 } 377 378 // multiply fDistance with real length to get absolute position and 379 // use getPositionAbsolute 380 return getPositionAbsolute(rCandidate, fDistance * fLength, fLength); 381 } 382 383 void applyLineDashing(const B3DPolygon& rCandidate, const ::std::vector<double>& rDotDashArray, B3DPolyPolygon* pLineTarget, B3DPolyPolygon* pGapTarget, double fDotDashLength) 384 { 385 const sal_uInt32 nPointCount(rCandidate.count()); 386 const sal_uInt32 nDotDashCount(rDotDashArray.size()); 387 388 if(fTools::lessOrEqual(fDotDashLength, 0.0)) 389 { 390 fDotDashLength = ::std::accumulate(rDotDashArray.begin(), rDotDashArray.end(), 0.0); 391 } 392 393 if(fTools::more(fDotDashLength, 0.0) && (pLineTarget || pGapTarget) && nPointCount) 394 { 395 // clear targets 396 if(pLineTarget) 397 { 398 pLineTarget->clear(); 399 } 400 401 if(pGapTarget) 402 { 403 pGapTarget->clear(); 404 } 405 406 // prepare current edge's start 407 B3DPoint aCurrentPoint(rCandidate.getB3DPoint(0)); 408 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); 409 410 // prepare DotDashArray iteration and the line/gap switching bool 411 sal_uInt32 nDotDashIndex(0); 412 bool bIsLine(true); 413 double fDotDashMovingLength(rDotDashArray[0]); 414 B3DPolygon aSnippet; 415 416 // iterate over all edges 417 for(sal_uInt32 a(0); a < nEdgeCount; a++) 418 { 419 // update current edge 420 double fLastDotDashMovingLength(0.0); 421 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 422 const B3DPoint aNextPoint(rCandidate.getB3DPoint(nNextIndex)); 423 const double fEdgeLength(B3DVector(aNextPoint - aCurrentPoint).getLength()); 424 425 while(fTools::less(fDotDashMovingLength, fEdgeLength)) 426 { 427 // new split is inside edge, create and append snippet [fLastDotDashMovingLength, fDotDashMovingLength] 428 const bool bHandleLine(bIsLine && pLineTarget); 429 const bool bHandleGap(!bIsLine && pGapTarget); 430 431 if(bHandleLine || bHandleGap) 432 { 433 if(!aSnippet.count()) 434 { 435 aSnippet.append(interpolate(aCurrentPoint, aNextPoint, fLastDotDashMovingLength / fEdgeLength)); 436 } 437 438 aSnippet.append(interpolate(aCurrentPoint, aNextPoint, fDotDashMovingLength / fEdgeLength)); 439 440 if(bHandleLine) 441 { 442 pLineTarget->append(aSnippet); 443 } 444 else 445 { 446 pGapTarget->append(aSnippet); 447 } 448 449 aSnippet.clear(); 450 } 451 452 // prepare next DotDashArray step and flip line/gap flag 453 fLastDotDashMovingLength = fDotDashMovingLength; 454 fDotDashMovingLength += rDotDashArray[(++nDotDashIndex) % nDotDashCount]; 455 bIsLine = !bIsLine; 456 } 457 458 // append snippet [fLastDotDashMovingLength, fEdgeLength] 459 const bool bHandleLine(bIsLine && pLineTarget); 460 const bool bHandleGap(!bIsLine && pGapTarget); 461 462 if(bHandleLine || bHandleGap) 463 { 464 if(!aSnippet.count()) 465 { 466 aSnippet.append(interpolate(aCurrentPoint, aNextPoint, fLastDotDashMovingLength / fEdgeLength)); 467 } 468 469 aSnippet.append(aNextPoint); 470 } 471 472 // prepare move to next edge 473 fDotDashMovingLength -= fEdgeLength; 474 475 // prepare next edge step (end point gets new start point) 476 aCurrentPoint = aNextPoint; 477 } 478 479 // append last intermediate results (if exists) 480 if(aSnippet.count()) 481 { 482 if(bIsLine && pLineTarget) 483 { 484 pLineTarget->append(aSnippet); 485 } 486 else if(!bIsLine && pGapTarget) 487 { 488 pGapTarget->append(aSnippet); 489 } 490 } 491 492 // check if start and end polygon may be merged 493 if(pLineTarget) 494 { 495 const sal_uInt32 nCount(pLineTarget->count()); 496 497 if(nCount > 1) 498 { 499 // these polygons were created above, there exists none with less than two points, 500 // thus dircet point access below is allowed 501 const B3DPolygon aFirst(pLineTarget->getB3DPolygon(0)); 502 B3DPolygon aLast(pLineTarget->getB3DPolygon(nCount - 1)); 503 504 if(aFirst.getB3DPoint(0).equal(aLast.getB3DPoint(aLast.count() - 1))) 505 { 506 // start of first and end of last are the same -> merge them 507 aLast.append(aFirst); 508 aLast.removeDoublePoints(); 509 pLineTarget->setB3DPolygon(0, aLast); 510 pLineTarget->remove(nCount - 1); 511 } 512 } 513 } 514 515 if(pGapTarget) 516 { 517 const sal_uInt32 nCount(pGapTarget->count()); 518 519 if(nCount > 1) 520 { 521 // these polygons were created above, there exists none with less than two points, 522 // thus dircet point access below is allowed 523 const B3DPolygon aFirst(pGapTarget->getB3DPolygon(0)); 524 B3DPolygon aLast(pGapTarget->getB3DPolygon(nCount - 1)); 525 526 if(aFirst.getB3DPoint(0).equal(aLast.getB3DPoint(aLast.count() - 1))) 527 { 528 // start of first and end of last are the same -> merge them 529 aLast.append(aFirst); 530 aLast.removeDoublePoints(); 531 pGapTarget->setB3DPolygon(0, aLast); 532 pGapTarget->remove(nCount - 1); 533 } 534 } 535 } 536 } 537 else 538 { 539 // parameters make no sense, just add source to targets 540 if(pLineTarget) 541 { 542 pLineTarget->append(rCandidate); 543 } 544 545 if(pGapTarget) 546 { 547 pGapTarget->append(rCandidate); 548 } 549 } 550 } 551 552 B3DPolygon applyDefaultNormalsSphere( const B3DPolygon& rCandidate, const B3DPoint& rCenter) 553 { 554 B3DPolygon aRetval(rCandidate); 555 556 for(sal_uInt32 a(0L); a < aRetval.count(); a++) 557 { 558 B3DVector aVector(aRetval.getB3DPoint(a) - rCenter); 559 aVector.normalize(); 560 aRetval.setNormal(a, aVector); 561 } 562 563 return aRetval; 564 } 565 566 B3DPolygon invertNormals( const B3DPolygon& rCandidate) 567 { 568 B3DPolygon aRetval(rCandidate); 569 570 if(aRetval.areNormalsUsed()) 571 { 572 for(sal_uInt32 a(0L); a < aRetval.count(); a++) 573 { 574 aRetval.setNormal(a, -aRetval.getNormal(a)); 575 } 576 } 577 578 return aRetval; 579 } 580 581 B3DPolygon applyDefaultTextureCoordinatesParallel( const B3DPolygon& rCandidate, const B3DRange& rRange, bool bChangeX, bool bChangeY) 582 { 583 B3DPolygon aRetval(rCandidate); 584 585 if(bChangeX || bChangeY) 586 { 587 // create projection of standard texture coordinates in (X, Y) onto 588 // the 3d coordinates straight 589 const double fWidth(rRange.getWidth()); 590 const double fHeight(rRange.getHeight()); 591 const bool bWidthSet(!fTools::equalZero(fWidth)); 592 const bool bHeightSet(!fTools::equalZero(fHeight)); 593 const double fOne(1.0); 594 595 for(sal_uInt32 a(0L); a < aRetval.count(); a++) 596 { 597 const B3DPoint aPoint(aRetval.getB3DPoint(a)); 598 B2DPoint aTextureCoordinate(aRetval.getTextureCoordinate(a)); 599 600 if(bChangeX) 601 { 602 if(bWidthSet) 603 { 604 aTextureCoordinate.setX((aPoint.getX() - rRange.getMinX()) / fWidth); 605 } 606 else 607 { 608 aTextureCoordinate.setX(0.0); 609 } 610 } 611 612 if(bChangeY) 613 { 614 if(bHeightSet) 615 { 616 aTextureCoordinate.setY(fOne - ((aPoint.getY() - rRange.getMinY()) / fHeight)); 617 } 618 else 619 { 620 aTextureCoordinate.setY(fOne); 621 } 622 } 623 624 aRetval.setTextureCoordinate(a, aTextureCoordinate); 625 } 626 } 627 628 return aRetval; 629 } 630 631 B3DPolygon applyDefaultTextureCoordinatesSphere( const B3DPolygon& rCandidate, const B3DPoint& rCenter, bool bChangeX, bool bChangeY) 632 { 633 B3DPolygon aRetval(rCandidate); 634 635 if(bChangeX || bChangeY) 636 { 637 // create texture coordinates using sphere projection to cartesian coordinates, 638 // use object's center as base 639 const double fOne(1.0); 640 const sal_uInt32 nPointCount(aRetval.count()); 641 bool bPolarPoints(false); 642 sal_uInt32 a; 643 644 // create center cartesian coordinates to have a possibility to decide if on boundary 645 // transitions which value to choose 646 const B3DRange aPlaneRange(getRange(rCandidate)); 647 const B3DPoint aPlaneCenter(aPlaneRange.getCenter() - rCenter); 648 const double fXCenter(fOne - ((atan2(aPlaneCenter.getZ(), aPlaneCenter.getX()) + F_PI) / F_2PI)); 649 650 for(a = 0L; a < nPointCount; a++) 651 { 652 const B3DVector aVector(aRetval.getB3DPoint(a) - rCenter); 653 const double fY(fOne - ((atan2(aVector.getY(), aVector.getXZLength()) + F_PI2) / F_PI)); 654 B2DPoint aTexCoor(aRetval.getTextureCoordinate(a)); 655 656 if(fTools::equalZero(fY)) 657 { 658 // point is a north polar point, no useful X-coordinate can be created. 659 if(bChangeY) 660 { 661 aTexCoor.setY(0.0); 662 663 if(bChangeX) 664 { 665 bPolarPoints = true; 666 } 667 } 668 } 669 else if(fTools::equal(fY, fOne)) 670 { 671 // point is a south polar point, no useful X-coordinate can be created. Set 672 // Y-coordinte, though 673 if(bChangeY) 674 { 675 aTexCoor.setY(fOne); 676 677 if(bChangeX) 678 { 679 bPolarPoints = true; 680 } 681 } 682 } 683 else 684 { 685 double fX(fOne - ((atan2(aVector.getZ(), aVector.getX()) + F_PI) / F_2PI)); 686 687 // correct cartesinan point coordiante dependent from center value 688 if(fX > fXCenter + 0.5) 689 { 690 fX -= fOne; 691 } 692 else if(fX < fXCenter - 0.5) 693 { 694 fX += fOne; 695 } 696 697 if(bChangeX) 698 { 699 aTexCoor.setX(fX); 700 } 701 702 if(bChangeY) 703 { 704 aTexCoor.setY(fY); 705 } 706 } 707 708 aRetval.setTextureCoordinate(a, aTexCoor); 709 } 710 711 if(bPolarPoints) 712 { 713 // correct X-texture coordinates if polar points are contained. Those 714 // coordinates cannot be correct, so use prev or next X-coordinate 715 for(a = 0L; a < nPointCount; a++) 716 { 717 B2DPoint aTexCoor(aRetval.getTextureCoordinate(a)); 718 719 if(fTools::equalZero(aTexCoor.getY()) || fTools::equal(aTexCoor.getY(), fOne)) 720 { 721 // get prev, next TexCoor and test for pole 722 const B2DPoint aPrevTexCoor(aRetval.getTextureCoordinate(a ? a - 1L : nPointCount - 1L)); 723 const B2DPoint aNextTexCoor(aRetval.getTextureCoordinate((a + 1L) % nPointCount)); 724 const bool bPrevPole(fTools::equalZero(aPrevTexCoor.getY()) || fTools::equal(aPrevTexCoor.getY(), fOne)); 725 const bool bNextPole(fTools::equalZero(aNextTexCoor.getY()) || fTools::equal(aNextTexCoor.getY(), fOne)); 726 727 if(!bPrevPole && !bNextPole) 728 { 729 // both no poles, mix them 730 aTexCoor.setX((aPrevTexCoor.getX() + aNextTexCoor.getX()) / 2.0); 731 } 732 else if(!bNextPole) 733 { 734 // copy next 735 aTexCoor.setX(aNextTexCoor.getX()); 736 } 737 else 738 { 739 // copy prev, even if it's a pole, hopefully it is already corrected 740 aTexCoor.setX(aPrevTexCoor.getX()); 741 } 742 743 aRetval.setTextureCoordinate(a, aTexCoor); 744 } 745 } 746 } 747 } 748 749 return aRetval; 750 } 751 752 bool isInEpsilonRange(const B3DPoint& rEdgeStart, const B3DPoint& rEdgeEnd, const B3DPoint& rTestPosition, double fDistance) 753 { 754 // build edge vector 755 const B3DVector aEdge(rEdgeEnd - rEdgeStart); 756 bool bDoDistanceTestStart(false); 757 bool bDoDistanceTestEnd(false); 758 759 if(aEdge.equalZero()) 760 { 761 // no edge, just a point. Do one of the distance tests. 762 bDoDistanceTestStart = true; 763 } 764 else 765 { 766 // calculate fCut in aEdge 767 const B3DVector aTestEdge(rTestPosition - rEdgeStart); 768 const double fScalarTestEdge(aEdge.scalar(aTestEdge)); 769 const double fScalarStartEdge(aEdge.scalar(rEdgeStart)); 770 const double fScalarEdge(aEdge.scalar(aEdge)); 771 const double fCut((fScalarTestEdge - fScalarStartEdge) / fScalarEdge); 772 const double fZero(0.0); 773 const double fOne(1.0); 774 775 if(fTools::less(fCut, fZero)) 776 { 777 // left of rEdgeStart 778 bDoDistanceTestStart = true; 779 } 780 else if(fTools::more(fCut, fOne)) 781 { 782 // right of rEdgeEnd 783 bDoDistanceTestEnd = true; 784 } 785 else 786 { 787 // inside line [0.0 .. 1.0] 788 const B3DPoint aCutPoint(interpolate(rEdgeStart, rEdgeEnd, fCut)); 789 const B3DVector aDelta(rTestPosition - aCutPoint); 790 const double fDistanceSquare(aDelta.scalar(aDelta)); 791 792 if(fDistanceSquare <= fDistance * fDistance * fDistance) 793 { 794 return true; 795 } 796 else 797 { 798 return false; 799 } 800 } 801 } 802 803 if(bDoDistanceTestStart) 804 { 805 const B3DVector aDelta(rTestPosition - rEdgeStart); 806 const double fDistanceSquare(aDelta.scalar(aDelta)); 807 808 if(fDistanceSquare <= fDistance * fDistance * fDistance) 809 { 810 return true; 811 } 812 } 813 else if(bDoDistanceTestEnd) 814 { 815 const B3DVector aDelta(rTestPosition - rEdgeEnd); 816 const double fDistanceSquare(aDelta.scalar(aDelta)); 817 818 if(fDistanceSquare <= fDistance * fDistance * fDistance) 819 { 820 return true; 821 } 822 } 823 824 return false; 825 } 826 827 bool isInEpsilonRange(const B3DPolygon& rCandidate, const B3DPoint& rTestPosition, double fDistance) 828 { 829 const sal_uInt32 nPointCount(rCandidate.count()); 830 831 if(nPointCount) 832 { 833 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); 834 B3DPoint aCurrent(rCandidate.getB3DPoint(0)); 835 836 if(nEdgeCount) 837 { 838 // edges 839 for(sal_uInt32 a(0); a < nEdgeCount; a++) 840 { 841 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 842 const B3DPoint aNext(rCandidate.getB3DPoint(nNextIndex)); 843 844 if(isInEpsilonRange(aCurrent, aNext, rTestPosition, fDistance)) 845 { 846 return true; 847 } 848 849 // prepare next step 850 aCurrent = aNext; 851 } 852 } 853 else 854 { 855 // no edges, but points -> not closed. Check single point. Just 856 // use isInEpsilonRange with twice the same point, it handles those well 857 if(isInEpsilonRange(aCurrent, aCurrent, rTestPosition, fDistance)) 858 { 859 return true; 860 } 861 } 862 } 863 864 return false; 865 } 866 867 bool isInside(const B3DPolygon& rCandidate, const B3DPoint& rPoint, bool bWithBorder) 868 { 869 if(bWithBorder && isPointOnPolygon(rCandidate, rPoint, true)) 870 { 871 return true; 872 } 873 else 874 { 875 bool bRetval(false); 876 const B3DVector aPlaneNormal(rCandidate.getNormal()); 877 878 if(!aPlaneNormal.equalZero()) 879 { 880 const sal_uInt32 nPointCount(rCandidate.count()); 881 882 if(nPointCount) 883 { 884 B3DPoint aCurrentPoint(rCandidate.getB3DPoint(nPointCount - 1)); 885 const double fAbsX(fabs(aPlaneNormal.getX())); 886 const double fAbsY(fabs(aPlaneNormal.getY())); 887 const double fAbsZ(fabs(aPlaneNormal.getZ())); 888 889 if(fAbsX > fAbsY && fAbsX > fAbsZ) 890 { 891 // normal points mostly in X-Direction, use YZ-Polygon projection for check 892 // x -> y, y -> z 893 for(sal_uInt32 a(0); a < nPointCount; a++) 894 { 895 const B3DPoint aPreviousPoint(aCurrentPoint); 896 aCurrentPoint = rCandidate.getB3DPoint(a); 897 898 // cross-over in Z? 899 const bool bCompZA(fTools::more(aPreviousPoint.getZ(), rPoint.getZ())); 900 const bool bCompZB(fTools::more(aCurrentPoint.getZ(), rPoint.getZ())); 901 902 if(bCompZA != bCompZB) 903 { 904 // cross-over in Y? 905 const bool bCompYA(fTools::more(aPreviousPoint.getY(), rPoint.getY())); 906 const bool bCompYB(fTools::more(aCurrentPoint.getY(), rPoint.getY())); 907 908 if(bCompYA == bCompYB) 909 { 910 if(bCompYA) 911 { 912 bRetval = !bRetval; 913 } 914 } 915 else 916 { 917 const double fCompare( 918 aCurrentPoint.getY() - (aCurrentPoint.getZ() - rPoint.getZ()) * 919 (aPreviousPoint.getY() - aCurrentPoint.getY()) / 920 (aPreviousPoint.getZ() - aCurrentPoint.getZ())); 921 922 if(fTools::more(fCompare, rPoint.getY())) 923 { 924 bRetval = !bRetval; 925 } 926 } 927 } 928 } 929 } 930 else if(fAbsY > fAbsX && fAbsY > fAbsZ) 931 { 932 // normal points mostly in Y-Direction, use XZ-Polygon projection for check 933 // x -> x, y -> z 934 for(sal_uInt32 a(0); a < nPointCount; a++) 935 { 936 const B3DPoint aPreviousPoint(aCurrentPoint); 937 aCurrentPoint = rCandidate.getB3DPoint(a); 938 939 // cross-over in Z? 940 const bool bCompZA(fTools::more(aPreviousPoint.getZ(), rPoint.getZ())); 941 const bool bCompZB(fTools::more(aCurrentPoint.getZ(), rPoint.getZ())); 942 943 if(bCompZA != bCompZB) 944 { 945 // cross-over in X? 946 const bool bCompXA(fTools::more(aPreviousPoint.getX(), rPoint.getX())); 947 const bool bCompXB(fTools::more(aCurrentPoint.getX(), rPoint.getX())); 948 949 if(bCompXA == bCompXB) 950 { 951 if(bCompXA) 952 { 953 bRetval = !bRetval; 954 } 955 } 956 else 957 { 958 const double fCompare( 959 aCurrentPoint.getX() - (aCurrentPoint.getZ() - rPoint.getZ()) * 960 (aPreviousPoint.getX() - aCurrentPoint.getX()) / 961 (aPreviousPoint.getZ() - aCurrentPoint.getZ())); 962 963 if(fTools::more(fCompare, rPoint.getX())) 964 { 965 bRetval = !bRetval; 966 } 967 } 968 } 969 } 970 } 971 else 972 { 973 // normal points mostly in Z-Direction, use XY-Polygon projection for check 974 // x -> x, y -> y 975 for(sal_uInt32 a(0); a < nPointCount; a++) 976 { 977 const B3DPoint aPreviousPoint(aCurrentPoint); 978 aCurrentPoint = rCandidate.getB3DPoint(a); 979 980 // cross-over in Y? 981 const bool bCompYA(fTools::more(aPreviousPoint.getY(), rPoint.getY())); 982 const bool bCompYB(fTools::more(aCurrentPoint.getY(), rPoint.getY())); 983 984 if(bCompYA != bCompYB) 985 { 986 // cross-over in X? 987 const bool bCompXA(fTools::more(aPreviousPoint.getX(), rPoint.getX())); 988 const bool bCompXB(fTools::more(aCurrentPoint.getX(), rPoint.getX())); 989 990 if(bCompXA == bCompXB) 991 { 992 if(bCompXA) 993 { 994 bRetval = !bRetval; 995 } 996 } 997 else 998 { 999 const double fCompare( 1000 aCurrentPoint.getX() - (aCurrentPoint.getY() - rPoint.getY()) * 1001 (aPreviousPoint.getX() - aCurrentPoint.getX()) / 1002 (aPreviousPoint.getY() - aCurrentPoint.getY())); 1003 1004 if(fTools::more(fCompare, rPoint.getX())) 1005 { 1006 bRetval = !bRetval; 1007 } 1008 } 1009 } 1010 } 1011 } 1012 } 1013 } 1014 1015 return bRetval; 1016 } 1017 } 1018 1019 bool isInside(const B3DPolygon& rCandidate, const B3DPolygon& rPolygon, bool bWithBorder) 1020 { 1021 const sal_uInt32 nPointCount(rPolygon.count()); 1022 1023 for(sal_uInt32 a(0L); a < nPointCount; a++) 1024 { 1025 const B3DPoint aTestPoint(rPolygon.getB3DPoint(a)); 1026 1027 if(!isInside(rCandidate, aTestPoint, bWithBorder)) 1028 { 1029 return false; 1030 } 1031 } 1032 1033 return true; 1034 } 1035 1036 bool isPointOnLine(const B3DPoint& rStart, const B3DPoint& rEnd, const B3DPoint& rCandidate, bool bWithPoints) 1037 { 1038 if(rCandidate.equal(rStart) || rCandidate.equal(rEnd)) 1039 { 1040 // candidate is in epsilon around start or end -> inside 1041 return bWithPoints; 1042 } 1043 else if(rStart.equal(rEnd)) 1044 { 1045 // start and end are equal, but candidate is outside their epsilon -> outside 1046 return false; 1047 } 1048 else 1049 { 1050 const B3DVector aEdgeVector(rEnd - rStart); 1051 const B3DVector aTestVector(rCandidate - rStart); 1052 1053 if(areParallel(aEdgeVector, aTestVector)) 1054 { 1055 const double fZero(0.0); 1056 const double fOne(1.0); 1057 double fParamTestOnCurr(0.0); 1058 1059 if(aEdgeVector.getX() > aEdgeVector.getY()) 1060 { 1061 if(aEdgeVector.getX() > aEdgeVector.getZ()) 1062 { 1063 // X is biggest 1064 fParamTestOnCurr = aTestVector.getX() / aEdgeVector.getX(); 1065 } 1066 else 1067 { 1068 // Z is biggest 1069 fParamTestOnCurr = aTestVector.getZ() / aEdgeVector.getZ(); 1070 } 1071 } 1072 else 1073 { 1074 if(aEdgeVector.getY() > aEdgeVector.getZ()) 1075 { 1076 // Y is biggest 1077 fParamTestOnCurr = aTestVector.getY() / aEdgeVector.getY(); 1078 } 1079 else 1080 { 1081 // Z is biggest 1082 fParamTestOnCurr = aTestVector.getZ() / aEdgeVector.getZ(); 1083 } 1084 } 1085 1086 if(fTools::more(fParamTestOnCurr, fZero) && fTools::less(fParamTestOnCurr, fOne)) 1087 { 1088 return true; 1089 } 1090 } 1091 1092 return false; 1093 } 1094 } 1095 1096 bool isPointOnPolygon(const B3DPolygon& rCandidate, const B3DPoint& rPoint, bool bWithPoints) 1097 { 1098 const sal_uInt32 nPointCount(rCandidate.count()); 1099 1100 if(nPointCount > 1L) 1101 { 1102 const sal_uInt32 nLoopCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); 1103 B3DPoint aCurrentPoint(rCandidate.getB3DPoint(0)); 1104 1105 for(sal_uInt32 a(0); a < nLoopCount; a++) 1106 { 1107 const B3DPoint aNextPoint(rCandidate.getB3DPoint((a + 1) % nPointCount)); 1108 1109 if(isPointOnLine(aCurrentPoint, aNextPoint, rPoint, bWithPoints)) 1110 { 1111 return true; 1112 } 1113 1114 aCurrentPoint = aNextPoint; 1115 } 1116 } 1117 else if(nPointCount && bWithPoints) 1118 { 1119 return rPoint.equal(rCandidate.getB3DPoint(0)); 1120 } 1121 1122 return false; 1123 } 1124 1125 bool getCutBetweenLineAndPlane(const B3DVector& rPlaneNormal, const B3DPoint& rPlanePoint, const B3DPoint& rEdgeStart, const B3DPoint& rEdgeEnd, double& fCut) 1126 { 1127 if(!rPlaneNormal.equalZero() && !rEdgeStart.equal(rEdgeEnd)) 1128 { 1129 const B3DVector aTestEdge(rEdgeEnd - rEdgeStart); 1130 const double fScalarEdge(rPlaneNormal.scalar(aTestEdge)); 1131 1132 if(!fTools::equalZero(fScalarEdge)) 1133 { 1134 const B3DVector aCompareEdge(rPlanePoint - rEdgeStart); 1135 const double fScalarCompare(rPlaneNormal.scalar(aCompareEdge)); 1136 1137 fCut = fScalarCompare / fScalarEdge; 1138 return true; 1139 } 1140 } 1141 1142 return false; 1143 } 1144 1145 bool getCutBetweenLineAndPolygon(const B3DPolygon& rCandidate, const B3DPoint& rEdgeStart, const B3DPoint& rEdgeEnd, double& fCut) 1146 { 1147 const sal_uInt32 nPointCount(rCandidate.count()); 1148 1149 if(nPointCount > 2 && !rEdgeStart.equal(rEdgeEnd)) 1150 { 1151 const B3DVector aPlaneNormal(rCandidate.getNormal()); 1152 1153 if(!aPlaneNormal.equalZero()) 1154 { 1155 const B3DPoint aPointOnPlane(rCandidate.getB3DPoint(0)); 1156 1157 return getCutBetweenLineAndPlane(aPlaneNormal, aPointOnPlane, rEdgeStart, rEdgeEnd, fCut); 1158 } 1159 } 1160 1161 return false; 1162 } 1163 1164 ////////////////////////////////////////////////////////////////////// 1165 // comparators with tolerance for 3D Polygons 1166 1167 bool equal(const B3DPolygon& rCandidateA, const B3DPolygon& rCandidateB, const double& rfSmallValue) 1168 { 1169 const sal_uInt32 nPointCount(rCandidateA.count()); 1170 1171 if(nPointCount != rCandidateB.count()) 1172 return false; 1173 1174 const bool bClosed(rCandidateA.isClosed()); 1175 1176 if(bClosed != rCandidateB.isClosed()) 1177 return false; 1178 1179 for(sal_uInt32 a(0); a < nPointCount; a++) 1180 { 1181 const B3DPoint aPoint(rCandidateA.getB3DPoint(a)); 1182 1183 if(!aPoint.equal(rCandidateB.getB3DPoint(a), rfSmallValue)) 1184 return false; 1185 } 1186 1187 return true; 1188 } 1189 1190 bool equal(const B3DPolygon& rCandidateA, const B3DPolygon& rCandidateB) 1191 { 1192 const double fSmallValue(fTools::getSmallValue()); 1193 1194 return equal(rCandidateA, rCandidateB, fSmallValue); 1195 } 1196 1197 // snap points of horizontal or vertical edges to discrete values 1198 B3DPolygon snapPointsOfHorizontalOrVerticalEdges(const B3DPolygon& rCandidate) 1199 { 1200 const sal_uInt32 nPointCount(rCandidate.count()); 1201 1202 if(nPointCount > 1) 1203 { 1204 // Start by copying the source polygon to get a writeable copy. The closed state is 1205 // copied by aRetval's initialisation, too, so no need to copy it in this method 1206 B3DPolygon aRetval(rCandidate); 1207 1208 // prepare geometry data. Get rounded from original 1209 B3ITuple aPrevTuple(basegfx::fround(rCandidate.getB3DPoint(nPointCount - 1))); 1210 B3DPoint aCurrPoint(rCandidate.getB3DPoint(0)); 1211 B3ITuple aCurrTuple(basegfx::fround(aCurrPoint)); 1212 1213 // loop over all points. This will also snap the implicit closing edge 1214 // even when not closed, but that's no problem here 1215 for(sal_uInt32 a(0); a < nPointCount; a++) 1216 { 1217 // get next point. Get rounded from original 1218 const bool bLastRun(a + 1 == nPointCount); 1219 const sal_uInt32 nNextIndex(bLastRun ? 0 : a + 1); 1220 const B3DPoint aNextPoint(rCandidate.getB3DPoint(nNextIndex)); 1221 const B3ITuple aNextTuple(basegfx::fround(aNextPoint)); 1222 1223 // get the states 1224 const bool bPrevVertical(aPrevTuple.getX() == aCurrTuple.getX()); 1225 const bool bNextVertical(aNextTuple.getX() == aCurrTuple.getX()); 1226 const bool bPrevHorizontal(aPrevTuple.getY() == aCurrTuple.getY()); 1227 const bool bNextHorizontal(aNextTuple.getY() == aCurrTuple.getY()); 1228 const bool bSnapX(bPrevVertical || bNextVertical); 1229 const bool bSnapY(bPrevHorizontal || bNextHorizontal); 1230 1231 if(bSnapX || bSnapY) 1232 { 1233 const B3DPoint aSnappedPoint( 1234 bSnapX ? aCurrTuple.getX() : aCurrPoint.getX(), 1235 bSnapY ? aCurrTuple.getY() : aCurrPoint.getY(), 1236 aCurrPoint.getZ()); 1237 1238 aRetval.setB3DPoint(a, aSnappedPoint); 1239 } 1240 1241 // prepare next point 1242 if(!bLastRun) 1243 { 1244 aPrevTuple = aCurrTuple; 1245 aCurrPoint = aNextPoint; 1246 aCurrTuple = aNextTuple; 1247 } 1248 } 1249 1250 return aRetval; 1251 } 1252 else 1253 { 1254 return rCandidate; 1255 } 1256 } 1257 1258 } // end of namespace tools 1259 } // end of namespace basegfx 1260 1261 ////////////////////////////////////////////////////////////////////////////// 1262 1263 // eof 1264