basegfx/source/polygon/b3dpolygontools.cxx

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