basegfx/source/polygon/b3dpolygontools.cxx

   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