basegfx/source/polygon/b3dpolygontools.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  * This file incorporates work covered by the following license notice:
  10  *
  11  *   Licensed to the Apache Software Foundation (ASF) under one or more
  12  *   contributor license agreements. See the NOTICE file distributed
  13  *   with this work for additional information regarding copyright
  14  *   ownership. The ASF licenses this file to you under the Apache
  15  *   License, Version 2.0 (the "License"); you may not use this file
  16  *   except in compliance with the License. You may obtain a copy of
  17  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  18  */
  19
  20 #include <osl/diagnose.h>
  21 #include <basegfx/polygon/b3dpolygontools.hxx>
  22 #include <basegfx/polygon/b3dpolygon.hxx>
  23 #include <basegfx/numeric/ftools.hxx>
  24 #include <basegfx/range/b3drange.hxx>
  25 #include <basegfx/point/b2dpoint.hxx>
  26 #include <basegfx/matrix/b3dhommatrix.hxx>
  27 #include <basegfx/polygon/b2dpolygon.hxx>
  28 #include <basegfx/polygon/b2dpolygontools.hxx>
  29 #include <basegfx/tuple/b3ituple.hxx>
  30 #include <numeric>
  31
  32 //////////////////////////////////////////////////////////////////////////////
  33
  34 namespace basegfx
  35 {
  36     namespace tools
  37     {
  38         // B3DPolygon tools
  39         void checkClosed(B3DPolygon& rCandidate)
  40         {
  41             while(rCandidate.count() > 1L
  42                 && rCandidate.getB3DPoint(0L).equal(rCandidate.getB3DPoint(rCandidate.count() - 1L)))
  43             {
  44                 rCandidate.setClosed(true);
  45                 rCandidate.remove(rCandidate.count() - 1L);
  46             }
  47         }
  48
  49         sal_uInt32 getIndexOfSuccessor(sal_uInt32 nIndex, const B3DPolygon& rCandidate)
  50         {
  51             OSL_ENSURE(nIndex < rCandidate.count(), "getIndexOfPredecessor: Access to polygon out of range (!)");
  52
  53             if(nIndex + 1L < rCandidate.count())
  54             {
  55                 return nIndex + 1L;
  56             }
  57             else
  58             {
  59                 return 0L;
  60             }
  61         }
  62
  63         B3DRange getRange(const B3DPolygon& rCandidate)
  64         {
  65             B3DRange aRetval;
  66             const sal_uInt32 nPointCount(rCandidate.count());
  67
  68             for(sal_uInt32 a(0L); a < nPointCount; a++)
  69             {
  70                 const B3DPoint aTestPoint(rCandidate.getB3DPoint(a));
  71                 aRetval.expand(aTestPoint);
  72             }
  73
  74             return aRetval;
  75         }
  76
  77         B3DVector getNormal(const B3DPolygon& rCandidate)
  78         {
  79             return rCandidate.getNormal();
  80         }
  81
  82         double getLength(const B3DPolygon& rCandidate)
  83         {
  84             double fRetval(0.0);
  85             const sal_uInt32 nPointCount(rCandidate.count());
  86
  87             if(nPointCount > 1L)
  88             {
  89                 const sal_uInt32 nLoopCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L);
  90
  91                 for(sal_uInt32 a(0L); a < nLoopCount; a++)
  92                 {
  93                     const sal_uInt32 nNextIndex(getIndexOfSuccessor(a, rCandidate));
  94                     const B3DPoint aCurrentPoint(rCandidate.getB3DPoint(a));
  95                     const B3DPoint aNextPoint(rCandidate.getB3DPoint(nNextIndex));
  96                     const B3DVector aVector(aNextPoint - aCurrentPoint);
  97                     fRetval += aVector.getLength();
  98                 }
  99             }
 100
 101             return fRetval;
 102         }
 103
 104         void applyLineDashing(const B3DPolygon& rCandidate, const ::std::vector<double>& rDotDashArray, B3DPolyPolygon* pLineTarget, B3DPolyPolygon* pGapTarget, double fDotDashLength)
 105         {
 106             const sal_uInt32 nPointCount(rCandidate.count());
 107             const sal_uInt32 nDotDashCount(rDotDashArray.size());
 108
 109             if(fTools::lessOrEqual(fDotDashLength, 0.0))
 110             {
 111                 fDotDashLength = ::std::accumulate(rDotDashArray.begin(), rDotDashArray.end(), 0.0);
 112             }
 113
 114             if(fTools::more(fDotDashLength, 0.0) && (pLineTarget || pGapTarget) && nPointCount)
 115             {
 116                 // clear targets
 117                 if(pLineTarget)
 118                 {
 119                     pLineTarget->clear();
 120                 }
 121
 122                 if(pGapTarget)
 123                 {
 124                     pGapTarget->clear();
 125                 }
 126
 127                 // prepare current edge's start
 128                 B3DPoint aCurrentPoint(rCandidate.getB3DPoint(0));
 129                 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
 130
 131                 // prepare DotDashArray iteration and the line/gap switching bool
 132                 sal_uInt32 nDotDashIndex(0);
 133                 bool bIsLine(true);
 134                 double fDotDashMovingLength(rDotDashArray[0]);
 135                 B3DPolygon aSnippet;
 136
 137                 // iterate over all edges
 138                 for(sal_uInt32 a(0); a < nEdgeCount; a++)
 139                 {
 140                     // update current edge
 141                     double fLastDotDashMovingLength(0.0);
 142                     const sal_uInt32 nNextIndex((a + 1) % nPointCount);
 143                     const B3DPoint aNextPoint(rCandidate.getB3DPoint(nNextIndex));
 144                     const double fEdgeLength(B3DVector(aNextPoint - aCurrentPoint).getLength());
 145
 146                     if(!fTools::equalZero(fEdgeLength))
 147                     {
 148                         while(fTools::less(fDotDashMovingLength, fEdgeLength))
 149                         {
 150                             // new split is inside edge, create and append snippet [fLastDotDashMovingLength, fDotDashMovingLength]
 151                             const bool bHandleLine(bIsLine && pLineTarget);
 152                             const bool bHandleGap(!bIsLine && pGapTarget);
 153
 154                             if(bHandleLine || bHandleGap)
 155                             {
 156                                 if(!aSnippet.count())
 157                                 {
 158                                     aSnippet.append(interpolate(aCurrentPoint, aNextPoint, fLastDotDashMovingLength / fEdgeLength));
 159                                 }
 160
 161                                 aSnippet.append(interpolate(aCurrentPoint, aNextPoint, fDotDashMovingLength / fEdgeLength));
 162
 163                                 if(bHandleLine)
 164                                 {
 165                                     pLineTarget->append(aSnippet);
 166                                 }
 167                                 else
 168                                 {
 169                                     pGapTarget->append(aSnippet);
 170                                 }
 171
 172                                 aSnippet.clear();
 173                             }
 174
 175                             // prepare next DotDashArray step and flip line/gap flag
 176                             fLastDotDashMovingLength = fDotDashMovingLength;
 177                             fDotDashMovingLength += rDotDashArray[(++nDotDashIndex) % nDotDashCount];
 178                             bIsLine = !bIsLine;
 179                         }
 180
 181                         // append snippet [fLastDotDashMovingLength, fEdgeLength]
 182                         const bool bHandleLine(bIsLine && pLineTarget);
 183                         const bool bHandleGap(!bIsLine && pGapTarget);
 184
 185                         if(bHandleLine || bHandleGap)
 186                         {
 187                             if(!aSnippet.count())
 188                             {
 189                                 aSnippet.append(interpolate(aCurrentPoint, aNextPoint, fLastDotDashMovingLength / fEdgeLength));
 190                             }
 191
 192                             aSnippet.append(aNextPoint);
 193                         }
 194
 195                         // prepare move to next edge
 196                         fDotDashMovingLength -= fEdgeLength;
 197                     }
 198
 199                     // prepare next edge step (end point gets new start point)
 200                     aCurrentPoint = aNextPoint;
 201                 }
 202
 203                 // append last intermediate results (if exists)
 204                 if(aSnippet.count())
 205                 {
 206                     if(bIsLine && pLineTarget)
 207                     {
 208                         pLineTarget->append(aSnippet);
 209                     }
 210                     else if(!bIsLine && pGapTarget)
 211                     {
 212                         pGapTarget->append(aSnippet);
 213                     }
 214                 }
 215
 216                 // check if start and end polygon may be merged
 217                 if(pLineTarget)
 218                 {
 219                     const sal_uInt32 nCount(pLineTarget->count());
 220
 221                     if(nCount > 1)
 222                     {
 223                         // these polygons were created above, there exists none with less than two points,
 224                         // thus dircet point access below is allowed
 225                         const B3DPolygon aFirst(pLineTarget->getB3DPolygon(0));
 226                         B3DPolygon aLast(pLineTarget->getB3DPolygon(nCount - 1));
 227
 228                         if(aFirst.getB3DPoint(0).equal(aLast.getB3DPoint(aLast.count() - 1)))
 229                         {
 230                             // start of first and end of last are the same -> merge them
 231                             aLast.append(aFirst);
 232                             aLast.removeDoublePoints();
 233                             pLineTarget->setB3DPolygon(0, aLast);
 234                             pLineTarget->remove(nCount - 1);
 235                         }
 236                     }
 237                 }
 238
 239                 if(pGapTarget)
 240                 {
 241                     const sal_uInt32 nCount(pGapTarget->count());
 242
 243                     if(nCount > 1)
 244                     {
 245                         // these polygons were created above, there exists none with less than two points,
 246                         // thus dircet point access below is allowed
 247                         const B3DPolygon aFirst(pGapTarget->getB3DPolygon(0));
 248                         B3DPolygon aLast(pGapTarget->getB3DPolygon(nCount - 1));
 249
 250                         if(aFirst.getB3DPoint(0).equal(aLast.getB3DPoint(aLast.count() - 1)))
 251                         {
 252                             // start of first and end of last are the same -> merge them
 253                             aLast.append(aFirst);
 254                             aLast.removeDoublePoints();
 255                             pGapTarget->setB3DPolygon(0, aLast);
 256                             pGapTarget->remove(nCount - 1);
 257                         }
 258                     }
 259                 }
 260             }
 261             else
 262             {
 263                 // parameters make no sense, just add source to targets
 264                 if(pLineTarget)
 265                 {
 266                     pLineTarget->append(rCandidate);
 267                 }
 268
 269                 if(pGapTarget)
 270                 {
 271                     pGapTarget->append(rCandidate);
 272                 }
 273             }
 274         }
 275
 276         B3DPolygon applyDefaultNormalsSphere( const B3DPolygon& rCandidate, const B3DPoint& rCenter)
 277         {
 278             B3DPolygon aRetval(rCandidate);
 279
 280             for(sal_uInt32 a(0L); a < aRetval.count(); a++)
 281             {
 282                 B3DVector aVector(aRetval.getB3DPoint(a) - rCenter);
 283                 aVector.normalize();
 284                 aRetval.setNormal(a, aVector);
 285             }
 286
 287             return aRetval;
 288         }
 289
 290         B3DPolygon invertNormals( const B3DPolygon& rCandidate)
 291         {
 292             B3DPolygon aRetval(rCandidate);
 293
 294             if(aRetval.areNormalsUsed())
 295             {
 296                 for(sal_uInt32 a(0L); a < aRetval.count(); a++)
 297                 {
 298                     aRetval.setNormal(a, -aRetval.getNormal(a));
 299                 }
 300             }
 301
 302             return aRetval;
 303         }
 304
 305         B3DPolygon applyDefaultTextureCoordinatesParallel( const B3DPolygon& rCandidate, const B3DRange& rRange, bool bChangeX, bool bChangeY)
 306         {
 307             B3DPolygon aRetval(rCandidate);
 308
 309             if(bChangeX || bChangeY)
 310             {
 311                 // create projection of standard texture coordinates in (X, Y) onto
 312                 // the 3d coordinates straight
 313                 const double fWidth(rRange.getWidth());
 314                 const double fHeight(rRange.getHeight());
 315                 const bool bWidthSet(!fTools::equalZero(fWidth));
 316                 const bool bHeightSet(!fTools::equalZero(fHeight));
 317                 const double fOne(1.0);
 318
 319                 for(sal_uInt32 a(0L); a < aRetval.count(); a++)
 320                 {
 321                     const B3DPoint aPoint(aRetval.getB3DPoint(a));
 322                     B2DPoint aTextureCoordinate(aRetval.getTextureCoordinate(a));
 323
 324                     if(bChangeX)
 325                     {
 326                         if(bWidthSet)
 327                         {
 328                             aTextureCoordinate.setX((aPoint.getX() - rRange.getMinX()) / fWidth);
 329                         }
 330                         else
 331                         {
 332                             aTextureCoordinate.setX(0.0);
 333                         }
 334                     }
 335
 336                     if(bChangeY)
 337                     {
 338                         if(bHeightSet)
 339                         {
 340                             aTextureCoordinate.setY(fOne - ((aPoint.getY() - rRange.getMinY()) / fHeight));
 341                         }
 342                         else
 343                         {
 344                             aTextureCoordinate.setY(fOne);
 345                         }
 346                     }
 347
 348                     aRetval.setTextureCoordinate(a, aTextureCoordinate);
 349                 }
 350             }
 351
 352             return aRetval;
 353         }
 354
 355         B3DPolygon applyDefaultTextureCoordinatesSphere( const B3DPolygon& rCandidate, const B3DPoint& rCenter, bool bChangeX, bool bChangeY)
 356         {
 357             B3DPolygon aRetval(rCandidate);
 358
 359             if(bChangeX || bChangeY)
 360             {
 361                 // create texture coordinates using sphere projection to cartesian coordinates,
 362                 // use object's center as base
 363                 const double fOne(1.0);
 364                 const sal_uInt32 nPointCount(aRetval.count());
 365                 bool bPolarPoints(false);
 366                 sal_uInt32 a;
 367
 368                 // create center cartesian coordinates to have a possibility to decide if on boundary
 369                 // transitions which value to choose
 370                 const B3DRange aPlaneRange(getRange(rCandidate));
 371                 const B3DPoint aPlaneCenter(aPlaneRange.getCenter() - rCenter);
 372                 const double fXCenter(fOne - ((atan2(aPlaneCenter.getZ(), aPlaneCenter.getX()) + F_PI) / F_2PI));
 373
 374                 for(a = 0L; a < nPointCount; a++)
 375                 {
 376                     const B3DVector aVector(aRetval.getB3DPoint(a) - rCenter);
 377                     const double fY(fOne - ((atan2(aVector.getY(), aVector.getXZLength()) + F_PI2) / F_PI));
 378                     B2DPoint aTexCoor(aRetval.getTextureCoordinate(a));
 379
 380                     if(fTools::equalZero(fY))
 381                     {
 382                         // point is a north polar point, no useful X-coordinate can be created.
 383                         if(bChangeY)
 384                         {
 385                             aTexCoor.setY(0.0);
 386
 387                             if(bChangeX)
 388                             {
 389                                 bPolarPoints = true;
 390                             }
 391                         }
 392                     }
 393                     else if(fTools::equal(fY, fOne))
 394                     {
 395                         // point is a south polar point, no useful X-coordinate can be created. Set
 396                         // Y-coordinte, though
 397                         if(bChangeY)
 398                         {
 399                             aTexCoor.setY(fOne);
 400
 401                             if(bChangeX)
 402                             {
 403                                 bPolarPoints = true;
 404                             }
 405                         }
 406                     }
 407                     else
 408                     {
 409                         double fX(fOne - ((atan2(aVector.getZ(), aVector.getX()) + F_PI) / F_2PI));
 410
 411                         // correct cartesinan point coordiante dependent from center value
 412                         if(fX > fXCenter + 0.5)
 413                         {
 414                             fX -= fOne;
 415                         }
 416                         else if(fX < fXCenter - 0.5)
 417                         {
 418                             fX += fOne;
 419                         }
 420
 421                         if(bChangeX)
 422                         {
 423                             aTexCoor.setX(fX);
 424                         }
 425
 426                         if(bChangeY)
 427                         {
 428                             aTexCoor.setY(fY);
 429                         }
 430                     }
 431
 432                     aRetval.setTextureCoordinate(a, aTexCoor);
 433                 }
 434
 435                 if(bPolarPoints)
 436                 {
 437                     // correct X-texture coordinates if polar points are contained. Those
 438                     // coordinates cannot be correct, so use prev or next X-coordinate
 439                     for(a = 0L; a < nPointCount; a++)
 440                     {
 441                         B2DPoint aTexCoor(aRetval.getTextureCoordinate(a));
 442
 443                         if(fTools::equalZero(aTexCoor.getY()) || fTools::equal(aTexCoor.getY(), fOne))
 444                         {
 445                             // get prev, next TexCoor and test for pole
 446                             const B2DPoint aPrevTexCoor(aRetval.getTextureCoordinate(a ? a - 1L : nPointCount - 1L));
 447                             const B2DPoint aNextTexCoor(aRetval.getTextureCoordinate((a + 1L) % nPointCount));
 448                             const bool bPrevPole(fTools::equalZero(aPrevTexCoor.getY()) || fTools::equal(aPrevTexCoor.getY(), fOne));
 449                             const bool bNextPole(fTools::equalZero(aNextTexCoor.getY()) || fTools::equal(aNextTexCoor.getY(), fOne));
 450
 451                             if(!bPrevPole && !bNextPole)
 452                             {
 453                                 // both no poles, mix them
 454                                 aTexCoor.setX((aPrevTexCoor.getX() + aNextTexCoor.getX()) / 2.0);
 455                             }
 456                             else if(!bNextPole)
 457                             {
 458                                 // copy next
 459                                 aTexCoor.setX(aNextTexCoor.getX());
 460                             }
 461                             else
 462                             {
 463                                 // copy prev, even if it's a pole, hopefully it is already corrected
 464                                 aTexCoor.setX(aPrevTexCoor.getX());
 465                             }
 466
 467                             aRetval.setTextureCoordinate(a, aTexCoor);
 468                         }
 469                     }
 470                 }
 471             }
 472
 473             return aRetval;
 474         }
 475
 476         bool isInside(const B3DPolygon& rCandidate, const B3DPoint& rPoint, bool bWithBorder)
 477         {
 478             if(bWithBorder && isPointOnPolygon(rCandidate, rPoint, true))
 479             {
 480                 return true;
 481             }
 482             else
 483             {
 484                 bool bRetval(false);
 485                 const B3DVector aPlaneNormal(rCandidate.getNormal());
 486
 487                 if(!aPlaneNormal.equalZero())
 488                 {
 489                     const sal_uInt32 nPointCount(rCandidate.count());
 490
 491                     if(nPointCount)
 492                     {
 493                         B3DPoint aCurrentPoint(rCandidate.getB3DPoint(nPointCount - 1));
 494                         const double fAbsX(fabs(aPlaneNormal.getX()));
 495                         const double fAbsY(fabs(aPlaneNormal.getY()));
 496                         const double fAbsZ(fabs(aPlaneNormal.getZ()));
 497
 498                         if(fAbsX > fAbsY && fAbsX > fAbsZ)
 499                         {
 500                             // normal points mostly in X-Direction, use YZ-Polygon projection for check
 501                             // x -> y, y -> z
 502                             for(sal_uInt32 a(0); a < nPointCount; a++)
 503                             {
 504                                 const B3DPoint aPreviousPoint(aCurrentPoint);
 505                                 aCurrentPoint = rCandidate.getB3DPoint(a);
 506
 507                                 // cross-over in Z?
 508                                 const bool bCompZA(fTools::more(aPreviousPoint.getZ(), rPoint.getZ()));
 509                                 const bool bCompZB(fTools::more(aCurrentPoint.getZ(), rPoint.getZ()));
 510
 511                                 if(bCompZA != bCompZB)
 512                                 {
 513                                     // cross-over in Y?
 514                                     const bool bCompYA(fTools::more(aPreviousPoint.getY(), rPoint.getY()));
 515                                     const bool bCompYB(fTools::more(aCurrentPoint.getY(), rPoint.getY()));
 516
 517                                     if(bCompYA == bCompYB)
 518                                     {
 519                                         if(bCompYA)
 520                                         {
 521                                             bRetval = !bRetval;
 522                                         }
 523                                     }
 524                                     else
 525                                     {
 526                                         const double fCompare(
 527                                             aCurrentPoint.getY() - (aCurrentPoint.getZ() - rPoint.getZ()) *
 528                                             (aPreviousPoint.getY() - aCurrentPoint.getY()) /
 529                                             (aPreviousPoint.getZ() - aCurrentPoint.getZ()));
 530
 531                                         if(fTools::more(fCompare, rPoint.getY()))
 532                                         {
 533                                             bRetval = !bRetval;
 534                                         }
 535                                     }
 536                                 }
 537                             }
 538                         }
 539                         else if(fAbsY > fAbsX && fAbsY > fAbsZ)
 540                         {
 541                             // normal points mostly in Y-Direction, use XZ-Polygon projection for check
 542                             // x -> x, y -> z
 543                             for(sal_uInt32 a(0); a < nPointCount; a++)
 544                             {
 545                                 const B3DPoint aPreviousPoint(aCurrentPoint);
 546                                 aCurrentPoint = rCandidate.getB3DPoint(a);
 547
 548                                 // cross-over in Z?
 549                                 const bool bCompZA(fTools::more(aPreviousPoint.getZ(), rPoint.getZ()));
 550                                 const bool bCompZB(fTools::more(aCurrentPoint.getZ(), rPoint.getZ()));
 551
 552                                 if(bCompZA != bCompZB)
 553                                 {
 554                                     // cross-over in X?
 555                                     const bool bCompXA(fTools::more(aPreviousPoint.getX(), rPoint.getX()));
 556                                     const bool bCompXB(fTools::more(aCurrentPoint.getX(), rPoint.getX()));
 557
 558                                     if(bCompXA == bCompXB)
 559                                     {
 560                                         if(bCompXA)
 561                                         {
 562                                             bRetval = !bRetval;
 563                                         }
 564                                     }
 565                                     else
 566                                     {
 567                                         const double fCompare(
 568                                             aCurrentPoint.getX() - (aCurrentPoint.getZ() - rPoint.getZ()) *
 569                                             (aPreviousPoint.getX() - aCurrentPoint.getX()) /
 570                                             (aPreviousPoint.getZ() - aCurrentPoint.getZ()));
 571
 572                                         if(fTools::more(fCompare, rPoint.getX()))
 573                                         {
 574                                             bRetval = !bRetval;
 575                                         }
 576                                     }
 577                                 }
 578                             }
 579                         }
 580                         else
 581                         {
 582                             // normal points mostly in Z-Direction, use XY-Polygon projection for check
 583                             // x -> x, y -> y
 584                             for(sal_uInt32 a(0); a < nPointCount; a++)
 585                             {
 586                                 const B3DPoint aPreviousPoint(aCurrentPoint);
 587                                 aCurrentPoint = rCandidate.getB3DPoint(a);
 588
 589                                 // cross-over in Y?
 590                                 const bool bCompYA(fTools::more(aPreviousPoint.getY(), rPoint.getY()));
 591                                 const bool bCompYB(fTools::more(aCurrentPoint.getY(), rPoint.getY()));
 592
 593                                 if(bCompYA != bCompYB)
 594                                 {
 595                                     // cross-over in X?
 596                                     const bool bCompXA(fTools::more(aPreviousPoint.getX(), rPoint.getX()));
 597                                     const bool bCompXB(fTools::more(aCurrentPoint.getX(), rPoint.getX()));
 598
 599                                     if(bCompXA == bCompXB)
 600                                     {
 601                                         if(bCompXA)
 602                                         {
 603                                             bRetval = !bRetval;
 604                                         }
 605                                     }
 606                                     else
 607                                     {
 608                                         const double fCompare(
 609                                             aCurrentPoint.getX() - (aCurrentPoint.getY() - rPoint.getY()) *
 610                                             (aPreviousPoint.getX() - aCurrentPoint.getX()) /
 611                                             (aPreviousPoint.getY() - aCurrentPoint.getY()));
 612
 613                                         if(fTools::more(fCompare, rPoint.getX()))
 614                                         {
 615                                             bRetval = !bRetval;
 616                                         }
 617                                     }
 618                                 }
 619                             }
 620                         }
 621                     }
 622                 }
 623
 624                 return bRetval;
 625             }
 626         }
 627
 628         bool isPointOnLine(const B3DPoint& rStart, const B3DPoint& rEnd, const B3DPoint& rCandidate, bool bWithPoints)
 629         {
 630             if(rCandidate.equal(rStart) || rCandidate.equal(rEnd))
 631             {
 632                 // candidate is in epsilon around start or end -> inside
 633                 return bWithPoints;
 634             }
 635             else if(rStart.equal(rEnd))
 636             {
 637                 // start and end are equal, but candidate is outside their epsilon -> outside
 638                 return false;
 639             }
 640             else
 641             {
 642                 const B3DVector aEdgeVector(rEnd - rStart);
 643                 const B3DVector aTestVector(rCandidate - rStart);
 644
 645                 if(areParallel(aEdgeVector, aTestVector))
 646                 {
 647                     const double fZero(0.0);
 648                     const double fOne(1.0);
 649                     double fParamTestOnCurr(0.0);
 650
 651                     if(aEdgeVector.getX() > aEdgeVector.getY())
 652                     {
 653                         if(aEdgeVector.getX() > aEdgeVector.getZ())
 654                         {
 655                             // X is biggest
 656                             fParamTestOnCurr = aTestVector.getX() / aEdgeVector.getX();
 657                         }
 658                         else
 659                         {
 660                             // Z is biggest
 661                             fParamTestOnCurr = aTestVector.getZ() / aEdgeVector.getZ();
 662                         }
 663                     }
 664                     else
 665                     {
 666                         if(aEdgeVector.getY() > aEdgeVector.getZ())
 667                         {
 668                             // Y is biggest
 669                             fParamTestOnCurr = aTestVector.getY() / aEdgeVector.getY();
 670                         }
 671                         else
 672                         {
 673                             // Z is biggest
 674                             fParamTestOnCurr = aTestVector.getZ() / aEdgeVector.getZ();
 675                         }
 676                     }
 677
 678                     if(fTools::more(fParamTestOnCurr, fZero) && fTools::less(fParamTestOnCurr, fOne))
 679                     {
 680                         return true;
 681                     }
 682                 }
 683
 684                 return false;
 685             }
 686         }
 687
 688         bool isPointOnPolygon(const B3DPolygon& rCandidate, const B3DPoint& rPoint, bool bWithPoints)
 689         {
 690             const sal_uInt32 nPointCount(rCandidate.count());
 691
 692             if(nPointCount > 1L)
 693             {
 694                 const sal_uInt32 nLoopCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L);
 695                 B3DPoint aCurrentPoint(rCandidate.getB3DPoint(0));
 696
 697                 for(sal_uInt32 a(0); a < nLoopCount; a++)
 698                 {
 699                     const B3DPoint aNextPoint(rCandidate.getB3DPoint((a + 1) % nPointCount));
 700
 701                     if(isPointOnLine(aCurrentPoint, aNextPoint, rPoint, bWithPoints))
 702                     {
 703                         return true;
 704                     }
 705
 706                     aCurrentPoint = aNextPoint;
 707                 }
 708             }
 709             else if(nPointCount && bWithPoints)
 710             {
 711                 return rPoint.equal(rCandidate.getB3DPoint(0));
 712             }
 713
 714             return false;
 715         }
 716
 717         bool getCutBetweenLineAndPlane(const B3DVector& rPlaneNormal, const B3DPoint& rPlanePoint, const B3DPoint& rEdgeStart, const B3DPoint& rEdgeEnd, double& fCut)
 718         {
 719             if(!rPlaneNormal.equalZero() && !rEdgeStart.equal(rEdgeEnd))
 720             {
 721                 const B3DVector aTestEdge(rEdgeEnd - rEdgeStart);
 722                 const double fScalarEdge(rPlaneNormal.scalar(aTestEdge));
 723
 724                 if(!fTools::equalZero(fScalarEdge))
 725                 {
 726                     const B3DVector aCompareEdge(rPlanePoint - rEdgeStart);
 727                     const double fScalarCompare(rPlaneNormal.scalar(aCompareEdge));
 728
 729                     fCut = fScalarCompare / fScalarEdge;
 730                     return true;
 731                 }
 732             }
 733
 734             return false;
 735         }
 736
 737         //////////////////////////////////////////////////////////////////////
 738         // comparators with tolerance for 3D Polygons
 739
 740         bool equal(const B3DPolygon& rCandidateA, const B3DPolygon& rCandidateB, const double& rfSmallValue)
 741         {
 742             const sal_uInt32 nPointCount(rCandidateA.count());
 743
 744             if(nPointCount != rCandidateB.count())
 745                 return false;
 746
 747             const bool bClosed(rCandidateA.isClosed());
 748
 749             if(bClosed != rCandidateB.isClosed())
 750                 return false;
 751
 752             for(sal_uInt32 a(0); a < nPointCount; a++)
 753             {
 754                 const B3DPoint aPoint(rCandidateA.getB3DPoint(a));
 755
 756                 if(!aPoint.equal(rCandidateB.getB3DPoint(a), rfSmallValue))
 757                     return false;
 758             }
 759
 760             return true;
 761         }
 762
 763         // snap points of horizontal or vertical edges to discrete values
 764         B3DPolygon snapPointsOfHorizontalOrVerticalEdges(const B3DPolygon& rCandidate)
 765         {
 766             const sal_uInt32 nPointCount(rCandidate.count());
 767
 768             if(nPointCount > 1)
 769             {
 770                 // Start by copying the source polygon to get a writeable copy. The closed state is
 771                 // copied by aRetval's initialisation, too, so no need to copy it in this method
 772                 B3DPolygon aRetval(rCandidate);
 773
 774                 // prepare geometry data. Get rounded from original
 775                 B3ITuple aPrevTuple(basegfx::fround(rCandidate.getB3DPoint(nPointCount - 1)));
 776                 B3DPoint aCurrPoint(rCandidate.getB3DPoint(0));
 777                 B3ITuple aCurrTuple(basegfx::fround(aCurrPoint));
 778
 779                 // loop over all points. This will also snap the implicit closing edge
 780                 // even when not closed, but that's no problem here
 781                 for(sal_uInt32 a(0); a < nPointCount; a++)
 782                 {
 783                     // get next point. Get rounded from original
 784                     const bool bLastRun(a + 1 == nPointCount);
 785                     const sal_uInt32 nNextIndex(bLastRun ? 0 : a + 1);
 786                     const B3DPoint aNextPoint(rCandidate.getB3DPoint(nNextIndex));
 787                     const B3ITuple aNextTuple(basegfx::fround(aNextPoint));
 788
 789                     // get the states
 790                     const bool bPrevVertical(aPrevTuple.getX() == aCurrTuple.getX());
 791                     const bool bNextVertical(aNextTuple.getX() == aCurrTuple.getX());
 792                     const bool bPrevHorizontal(aPrevTuple.getY() == aCurrTuple.getY());
 793                     const bool bNextHorizontal(aNextTuple.getY() == aCurrTuple.getY());
 794                     const bool bSnapX(bPrevVertical || bNextVertical);
 795                     const bool bSnapY(bPrevHorizontal || bNextHorizontal);
 796
 797                     if(bSnapX || bSnapY)
 798                     {
 799                         const B3DPoint aSnappedPoint(
 800                             bSnapX ? aCurrTuple.getX() : aCurrPoint.getX(),
 801                             bSnapY ? aCurrTuple.getY() : aCurrPoint.getY(),
 802                             aCurrPoint.getZ());
 803
 804                         aRetval.setB3DPoint(a, aSnappedPoint);
 805                     }
 806
 807                     // prepare next point
 808                     if(!bLastRun)
 809                     {
 810                         aPrevTuple = aCurrTuple;
 811                         aCurrPoint = aNextPoint;
 812                         aCurrTuple = aNextTuple;
 813                     }
 814                 }
 815
 816                 return aRetval;
 817             }
 818             else
 819             {
 820                 return rCandidate;
 821             }
 822         }
 823
 824     } // end of namespace tools
 825 } // end of namespace basegfx
 826
 827 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */