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