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