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