basegfx/source/polygon/b3dpolygonclipper.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2000, 2010 Oracle and/or its affiliates.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * This file is part of OpenOffice.org.
  10  *
  11  * OpenOffice.org is free software: you can redistribute it and/or modify
  12  * it under the terms of the GNU Lesser General Public License version 3
  13  * only, as published by the Free Software Foundation.
  14  *
  15  * OpenOffice.org is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  * GNU Lesser General Public License version 3 for more details
  19  * (a copy is included in the LICENSE file that accompanied this code).
  20  *
  21  * You should have received a copy of the GNU Lesser General Public License
  22  * version 3 along with OpenOffice.org.  If not, see
  23  * <http://www.openoffice.org/license.html>
  24  * for a copy of the LGPLv3 License.
  25  *
  26  ************************************************************************/
  27
  28 // MARKER(update_precomp.py): autogen include statement, do not remove
  29 #include "precompiled_basegfx.hxx"
  30
  31 #include <basegfx/polygon/b3dpolygonclipper.hxx>
  32 #include <osl/diagnose.h>
  33 #include <basegfx/polygon/b3dpolygontools.hxx>
  34 #include <basegfx/numeric/ftools.hxx>
  35 #include <basegfx/matrix/b3dhommatrix.hxx>
  36 #include <basegfx/polygon/b3dpolygontools.hxx>
  37 #include <basegfx/range/b3drange.hxx>
  38 #include <basegfx/point/b2dpoint.hxx>
  39 #include <basegfx/range/b2drange.hxx>
  40 #include <basegfx/color/bcolor.hxx>
  41
  42 //////////////////////////////////////////////////////////////////////////////
  43
  44 namespace basegfx
  45 {
  46     namespace
  47     {
  48         inline bool impIsInside(const B3DPoint& rCandidate, double fPlaneOffset, tools::B3DOrientation ePlaneOrthogonal)
  49         {
  50             if(tools::B3DORIENTATION_X == ePlaneOrthogonal)
  51             {
  52                 return fTools::moreOrEqual(rCandidate.getX(), fPlaneOffset);
  53             }
  54             else if(tools::B3DORIENTATION_Y == ePlaneOrthogonal)
  55             {
  56                 return fTools::moreOrEqual(rCandidate.getY(), fPlaneOffset);
  57             }
  58             else
  59             {
  60                 return fTools::moreOrEqual(rCandidate.getZ(), fPlaneOffset);
  61             }
  62         }
  63
  64         inline double impGetCut(const B3DPoint& rCurrent, const B3DPoint& rNext, double fPlaneOffset, tools::B3DOrientation ePlaneOrthogonal)
  65         {
  66             if(tools::B3DORIENTATION_X == ePlaneOrthogonal)
  67             {
  68                 return ((fPlaneOffset - rCurrent.getX())/(rNext.getX() - rCurrent.getX()));
  69             }
  70             else if(tools::B3DORIENTATION_Y == ePlaneOrthogonal)
  71             {
  72                 return ((fPlaneOffset - rCurrent.getY())/(rNext.getY() - rCurrent.getY()));
  73             }
  74             else
  75             {
  76                 return ((fPlaneOffset - rCurrent.getZ())/(rNext.getZ() - rCurrent.getZ()));
  77             }
  78         }
  79
  80         void impAppendCopy(B3DPolygon& rDest, const B3DPolygon& rSource, sal_uInt32 nIndex)
  81         {
  82             rDest.append(rSource.getB3DPoint(nIndex));
  83
  84             if(rSource.areBColorsUsed())
  85             {
  86                 rDest.setBColor(rDest.count() - 1L, rSource.getBColor(nIndex));
  87             }
  88
  89             if(rSource.areNormalsUsed())
  90             {
  91                 rDest.setNormal(rDest.count() - 1L, rSource.getNormal(nIndex));
  92             }
  93
  94             if(rSource.areTextureCoordinatesUsed())
  95             {
  96                 rDest.setTextureCoordinate(rDest.count() - 1L, rSource.getTextureCoordinate(nIndex));
  97             }
  98         }
  99
 100         void impAppendInterpolate(B3DPolygon& rDest, const B3DPolygon& rSource, sal_uInt32 nIndA, sal_uInt32 nIndB, double fCut)
 101         {
 102             const B3DPoint aCurrPoint(rSource.getB3DPoint(nIndA));
 103             const B3DPoint aNextPoint(rSource.getB3DPoint(nIndB));
 104             rDest.append(interpolate(aCurrPoint, aNextPoint, fCut));
 105
 106             if(rSource.areBColorsUsed())
 107             {
 108                 const BColor aCurrBColor(rSource.getBColor(nIndA));
 109                 const BColor aNextBColor(rSource.getBColor(nIndB));
 110                 rDest.setBColor(rDest.count() - 1L, interpolate(aCurrBColor, aNextBColor, fCut));
 111             }
 112
 113             if(rSource.areNormalsUsed())
 114             {
 115                 const B3DVector aCurrVector(rSource.getNormal(nIndA));
 116                 const B3DVector aNextVector(rSource.getNormal(nIndB));
 117                 rDest.setNormal(rDest.count() - 1L, interpolate(aCurrVector, aNextVector, fCut));
 118             }
 119
 120             if(rSource.areTextureCoordinatesUsed())
 121             {
 122                 const B2DPoint aCurrTxCo(rSource.getTextureCoordinate(nIndA));
 123                 const B2DPoint aNextTxCo(rSource.getTextureCoordinate(nIndB));
 124                 rDest.setTextureCoordinate(rDest.count() - 1L, interpolate(aCurrTxCo, aNextTxCo, fCut));
 125             }
 126         }
 127     }
 128 } // end of namespace basegfx
 129
 130 //////////////////////////////////////////////////////////////////////////////
 131
 132 namespace basegfx
 133 {
 134     namespace tools
 135     {
 136         B3DPolyPolygon clipPolygonOnOrthogonalPlane(const B3DPolygon& rCandidate, B3DOrientation ePlaneOrthogonal, bool bClipPositive, double fPlaneOffset, bool bStroke)
 137         {
 138             B3DPolyPolygon aRetval;
 139
 140             if(rCandidate.count())
 141             {
 142                 const B3DRange aCandidateRange(getRange(rCandidate));
 143
 144                 if(B3DORIENTATION_X == ePlaneOrthogonal && fTools::moreOrEqual(aCandidateRange.getMinX(), fPlaneOffset))
 145                 {
 146                     // completely above and on the clip plane.
 147                     if(bClipPositive)
 148                     {
 149                         // add completely
 150                         aRetval.append(rCandidate);
 151                     }
 152                 }
 153                 else if(B3DORIENTATION_X == ePlaneOrthogonal && fTools::lessOrEqual(aCandidateRange.getMaxX(), fPlaneOffset))
 154                 {
 155                     // completely below and on the clip plane.
 156                     if(!bClipPositive)
 157                     {
 158                         // add completely
 159                         aRetval.append(rCandidate);
 160                     }
 161                 }
 162                 else if(B3DORIENTATION_Y == ePlaneOrthogonal && fTools::moreOrEqual(aCandidateRange.getMinY(), fPlaneOffset))
 163                 {
 164                     // completely above and on the clip plane.
 165                     if(bClipPositive)
 166                     {
 167                         // add completely
 168                         aRetval.append(rCandidate);
 169                     }
 170                 }
 171                 else if(B3DORIENTATION_Y == ePlaneOrthogonal && fTools::lessOrEqual(aCandidateRange.getMaxY(), fPlaneOffset))
 172                 {
 173                     // completely below and on the clip plane.
 174                     if(!bClipPositive)
 175                     {
 176                         // add completely
 177                         aRetval.append(rCandidate);
 178                     }
 179                 }
 180                 else if(B3DORIENTATION_Z == ePlaneOrthogonal && fTools::moreOrEqual(aCandidateRange.getMinZ(), fPlaneOffset))
 181                 {
 182                     // completely above and on the clip plane.
 183                     if(bClipPositive)
 184                     {
 185                         // add completely
 186                         aRetval.append(rCandidate);
 187                     }
 188                 }
 189                 else if(B3DORIENTATION_Z == ePlaneOrthogonal && fTools::lessOrEqual(aCandidateRange.getMaxZ(), fPlaneOffset))
 190                 {
 191                     // completely below and on the clip plane.
 192                     if(!bClipPositive)
 193                     {
 194                         // add completely
 195                         aRetval.append(rCandidate);
 196                     }
 197                 }
 198                 else
 199                 {
 200                     // prepare loop(s)
 201                     B3DPolygon aNewPolygon;
 202                     B3DPoint aCurrent(rCandidate.getB3DPoint(0L));
 203                     const sal_uInt32 nPointCount(rCandidate.count());
 204                     const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L);
 205                     bool bCurrentInside(impIsInside(aCurrent, fPlaneOffset, ePlaneOrthogonal) == bClipPositive);
 206
 207                     if(bCurrentInside)
 208                     {
 209                         impAppendCopy(aNewPolygon, rCandidate, 0L);
 210                     }
 211
 212                     if(bStroke)
 213                     {
 214                         // open polygon, create clipped line snippets.
 215                         for(sal_uInt32 a(0L); a < nEdgeCount; a++)
 216                         {
 217                             // get next point data
 218                             const sal_uInt32 nNextIndex((a + 1L == nPointCount) ? 0L : a + 1L);
 219                             const B3DPoint aNext(rCandidate.getB3DPoint(nNextIndex));
 220                             const bool bNextInside(impIsInside(aNext, fPlaneOffset, ePlaneOrthogonal) == bClipPositive);
 221
 222                             if(bCurrentInside != bNextInside)
 223                             {
 224                                 // change inside/outside
 225                                 if(bNextInside)
 226                                 {
 227                                     // entering, finish existing and start new line polygon
 228                                     if(aNewPolygon.count() > 1L)
 229                                     {
 230                                         aRetval.append(aNewPolygon);
 231                                     }
 232
 233                                     aNewPolygon.clear();
 234                                 }
 235
 236                                 // calculate and add cut point
 237                                 const double fCut(impGetCut(aCurrent, aNext, fPlaneOffset, ePlaneOrthogonal));
 238                                 impAppendInterpolate(aNewPolygon, rCandidate, a, nNextIndex, fCut);
 239
 240                                 // pepare next step
 241                                 bCurrentInside = bNextInside;
 242                             }
 243
 244                             if(bNextInside)
 245                             {
 246                                 impAppendCopy(aNewPolygon, rCandidate, nNextIndex);
 247                             }
 248
 249                             // pepare next step
 250                             aCurrent = aNext;
 251                         }
 252
 253                         if(aNewPolygon.count() > 1L)
 254                         {
 255                             aRetval.append(aNewPolygon);
 256                         }
 257                     }
 258                     else
 259                     {
 260                         // closed polygon, create single clipped closed polygon
 261                         for(sal_uInt32 a(0L); a < nEdgeCount; a++)
 262                         {
 263                             // get next point data, use offset
 264                             const sal_uInt32 nNextIndex((a + 1L == nPointCount) ? 0L : a + 1L);
 265                             const B3DPoint aNext(rCandidate.getB3DPoint(nNextIndex));
 266                             const bool bNextInside(impIsInside(aNext, fPlaneOffset, ePlaneOrthogonal) == bClipPositive);
 267
 268                             if(bCurrentInside != bNextInside)
 269                             {
 270                                 // calculate and add cut point
 271                                 const double fCut(impGetCut(aCurrent, aNext, fPlaneOffset, ePlaneOrthogonal));
 272                                 impAppendInterpolate(aNewPolygon, rCandidate, a, nNextIndex, fCut);
 273
 274                                 // pepare next step
 275                                 bCurrentInside = bNextInside;
 276                             }
 277
 278                             if(bNextInside && nNextIndex)
 279                             {
 280                                 impAppendCopy(aNewPolygon, rCandidate, nNextIndex);
 281                             }
 282
 283                             // pepare next step
 284                             aCurrent = aNext;
 285                         }
 286
 287                         if(aNewPolygon.count() > 2L)
 288                         {
 289                             aNewPolygon.setClosed(true);
 290                             aRetval.append(aNewPolygon);
 291                         }
 292                     }
 293                 }
 294             }
 295
 296             return aRetval;
 297         }
 298
 299         B3DPolyPolygon clipPolyPolygonOnOrthogonalPlane(const B3DPolyPolygon& rCandidate, B3DOrientation ePlaneOrthogonal, bool bClipPositive, double fPlaneOffset, bool bStroke)
 300         {
 301             B3DPolyPolygon aRetval;
 302
 303             for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
 304             {
 305                 aRetval.append(clipPolygonOnOrthogonalPlane(rCandidate.getB3DPolygon(a), ePlaneOrthogonal, bClipPositive, fPlaneOffset, bStroke));
 306             }
 307
 308             return aRetval;
 309         }
 310
 311         B3DPolyPolygon clipPolyPolygonOnRange(const B3DPolyPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke)
 312         {
 313             B3DPolyPolygon aRetval;
 314
 315             for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
 316             {
 317                 aRetval.append(clipPolygonOnRange(rCandidate.getB3DPolygon(a), rRange, bInside, bStroke));
 318             }
 319
 320             return aRetval;
 321         }
 322
 323         B3DPolyPolygon clipPolygonOnRange(const B3DPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke)
 324         {
 325             B3DPolyPolygon aRetval;
 326
 327             if(rRange.isEmpty())
 328             {
 329                 // clipping against an empty range. Nothing is inside an empty range, so the polygon
 330                 // is outside the range. So only return if not inside is wanted
 331                 if(!bInside && rCandidate.count())
 332                 {
 333                     aRetval.append(rCandidate);
 334                 }
 335             }
 336             else if(rCandidate.count())
 337             {
 338                 const B3DRange aCandidateRange3D(getRange(rCandidate));
 339                 const B2DRange aCandidateRange(
 340                     aCandidateRange3D.getMinX(), aCandidateRange3D.getMinY(),
 341                     aCandidateRange3D.getMaxX(), aCandidateRange3D.getMaxY());
 342
 343                 if(rRange.isInside(aCandidateRange))
 344                 {
 345                     // candidate is completely inside given range, nothing to do. Is also true with curves.
 346                     if(bInside)
 347                     {
 348                         aRetval.append(rCandidate);
 349                     }
 350                 }
 351                 else if(!rRange.overlaps(aCandidateRange))
 352                 {
 353                     // candidate is completely outside given range, nothing to do. Is also true with curves.
 354                     if(!bInside)
 355                     {
 356                         aRetval.append(rCandidate);
 357                     }
 358                 }
 359                 else
 360                 {
 361                     // clip against the six planes of the range
 362                     // against lower X
 363                     aRetval = clipPolygonOnOrthogonalPlane(rCandidate, tools::B3DORIENTATION_X, bInside, rRange.getMinX(), bStroke);
 364
 365                     if(aRetval.count())
 366                     {
 367                         // against lower Y
 368                         if(1L == aRetval.count())
 369                         {
 370                             aRetval = clipPolygonOnOrthogonalPlane(aRetval.getB3DPolygon(0L), tools::B3DORIENTATION_Y, bInside, rRange.getMinY(), bStroke);
 371                         }
 372                         else
 373                         {
 374                             aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_Y, bInside, rRange.getMinY(), bStroke);
 375                         }
 376
 377                         if(aRetval.count())
 378                         {
 379                             // against higher X
 380                             if(1L == aRetval.count())
 381                             {
 382                                 aRetval = clipPolygonOnOrthogonalPlane(aRetval.getB3DPolygon(0L), tools::B3DORIENTATION_X, !bInside, rRange.getMaxX(), bStroke);
 383                             }
 384                             else
 385                             {
 386                                 aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_X, !bInside, rRange.getMaxX(), bStroke);
 387                             }
 388
 389                             if(aRetval.count())
 390                             {
 391                                 // against higher Y
 392                                 if(1L == aRetval.count())
 393                                 {
 394                                     aRetval = clipPolygonOnOrthogonalPlane(aRetval.getB3DPolygon(0L), tools::B3DORIENTATION_Y, !bInside, rRange.getMaxY(), bStroke);
 395                                 }
 396                                 else
 397                                 {
 398                                     aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_Y, !bInside, rRange.getMaxY(), bStroke);
 399                                 }
 400                             }
 401                         }
 402                     }
 403                 }
 404             }
 405
 406             return aRetval;
 407         }
 408
 409         B3DPolyPolygon clipPolyPolygonOnRange(const B3DPolyPolygon& rCandidate, const B3DRange& rRange, bool bInside, bool bStroke)
 410         {
 411             B3DPolyPolygon aRetval;
 412
 413             for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
 414             {
 415                 aRetval.append(clipPolygonOnRange(rCandidate.getB3DPolygon(a), rRange, bInside, bStroke));
 416             }
 417
 418             return aRetval;
 419         }
 420
 421         B3DPolyPolygon clipPolygonOnRange(const B3DPolygon& rCandidate, const B3DRange& rRange, bool bInside, bool bStroke)
 422         {
 423             B3DPolyPolygon aRetval;
 424
 425             if(rRange.isEmpty())
 426             {
 427                 // clipping against an empty range. Nothing is inside an empty range, so the polygon
 428                 // is outside the range. So only return if not inside is wanted
 429                 if(!bInside && rCandidate.count())
 430                 {
 431                     aRetval.append(rCandidate);
 432                 }
 433             }
 434             else if(rCandidate.count())
 435             {
 436                 const B3DRange aCandidateRange(getRange(rCandidate));
 437
 438                 if(rRange.isInside(aCandidateRange))
 439                 {
 440                     // candidate is completely inside given range, nothing to do. Is also true with curves.
 441                     if(bInside)
 442                     {
 443                         aRetval.append(rCandidate);
 444                     }
 445                 }
 446                 else if(!rRange.overlaps(aCandidateRange))
 447                 {
 448                     // candidate is completely outside given range, nothing to do. Is also true with curves.
 449                     if(!bInside)
 450                     {
 451                         aRetval.append(rCandidate);
 452                     }
 453                 }
 454                 else
 455                 {
 456                     // clip against X,Y first and see if there's something left
 457                     const B2DRange aCandidateRange2D(rRange.getMinX(), rRange.getMinY(), rRange.getMaxX(), rRange.getMaxY());
 458                     aRetval = clipPolygonOnRange(rCandidate, aCandidateRange2D, bInside, bStroke);
 459
 460                     if(aRetval.count())
 461                     {
 462                         // against lower Z
 463                         if(1L == aRetval.count())
 464                         {
 465                             aRetval = clipPolygonOnOrthogonalPlane(aRetval.getB3DPolygon(0L), tools::B3DORIENTATION_Z, bInside, rRange.getMinZ(), bStroke);
 466                         }
 467                         else
 468                         {
 469                             aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_Z, bInside, rRange.getMinZ(), bStroke);
 470                         }
 471
 472                         if(aRetval.count())
 473                         {
 474                             // against higher Z
 475                             if(1L == aRetval.count())
 476                             {
 477                                 aRetval = clipPolygonOnOrthogonalPlane(aRetval.getB3DPolygon(0L), tools::B3DORIENTATION_Z, !bInside, rRange.getMaxZ(), bStroke);
 478                             }
 479                             else
 480                             {
 481                                 aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_Z, !bInside, rRange.getMaxZ(), bStroke);
 482                             }
 483                         }
 484                     }
 485                 }
 486             }
 487
 488             return aRetval;
 489         }
 490
 491         B3DPolyPolygon clipPolygonOnPlane(const B3DPolygon& rCandidate, const B3DPoint& rPointOnPlane, const B3DVector& rPlaneNormal, bool bClipPositive, bool bStroke)
 492         {
 493             B3DPolyPolygon aRetval;
 494
 495             if(rPlaneNormal.equalZero())
 496             {
 497                 // not really a plane definition, return polygon
 498                 aRetval.append(rCandidate);
 499             }
 500             else if(rCandidate.count())
 501             {
 502                 // build transform to project planeNormal on X-Axis and pointOnPlane to null point
 503                 B3DHomMatrix aMatrixTransform;
 504                 aMatrixTransform.translate(-rPointOnPlane.getX(), -rPointOnPlane.getY(), -rPointOnPlane.getZ());
 505                 const double fRotInXY(atan2(rPlaneNormal.getY(), rPlaneNormal.getX()));
 506                 const double fRotInXZ(atan2(-rPlaneNormal.getZ(), rPlaneNormal.getXYLength()));
 507                 if(!fTools::equalZero(fRotInXY) || !fTools::equalZero(fRotInXZ))
 508                 {
 509                     aMatrixTransform.rotate(0.0, fRotInXZ, fRotInXY);
 510                 }
 511
 512                 // transform polygon to clip scenario
 513                 B3DPolygon aCandidate(rCandidate);
 514                 aCandidate.transform(aMatrixTransform);
 515
 516                 // clip on YZ plane
 517                 aRetval = clipPolygonOnOrthogonalPlane(aCandidate, tools::B3DORIENTATION_X, bClipPositive, 0.0, bStroke);
 518
 519                 if(aRetval.count())
 520                 {
 521                     // if there is a result, it needs to be transformed back
 522                     aMatrixTransform.invert();
 523                     aRetval.transform(aMatrixTransform);
 524                 }
 525             }
 526
 527             return aRetval;
 528         }
 529
 530         B3DPolyPolygon clipPolyPolygonOnPlane(const B3DPolyPolygon& rCandidate, const B3DPoint& rPointOnPlane, const B3DVector& rPlaneNormal, bool bClipPositive, bool bStroke)
 531         {
 532             B3DPolyPolygon aRetval;
 533
 534             if(rPlaneNormal.equalZero())
 535             {
 536                 // not really a plane definition, return polygon
 537                 aRetval = rCandidate;
 538             }
 539             else if(rCandidate.count())
 540             {
 541                 // build transform to project planeNormal on X-Axis and pointOnPlane to null point
 542                 B3DHomMatrix aMatrixTransform;
 543                 aMatrixTransform.translate(-rPointOnPlane.getX(), -rPointOnPlane.getY(), -rPointOnPlane.getZ());
 544                 const double fRotInXY(atan2(rPlaneNormal.getY(), rPlaneNormal.getX()));
 545                 const double fRotInXZ(atan2(-rPlaneNormal.getZ(), rPlaneNormal.getXYLength()));
 546                 if(!fTools::equalZero(fRotInXY) || !fTools::equalZero(fRotInXZ))
 547                 {
 548                     aMatrixTransform.rotate(0.0, fRotInXZ, fRotInXY);
 549                 }
 550
 551                 // transform polygon to clip scenario
 552                 aRetval = rCandidate;
 553                 aRetval.transform(aMatrixTransform);
 554
 555                 // clip on YZ plane
 556                 aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_X, bClipPositive, 0.0, bStroke);
 557
 558                 if(aRetval.count())
 559                 {
 560                     // if there is a result, it needs to be transformed back
 561                     aMatrixTransform.invert();
 562                     aRetval.transform(aMatrixTransform);
 563                 }
 564             }
 565
 566             return aRetval;
 567         }
 568
 569     } // end of namespace tools
 570 } // end of namespace basegfx
 571
 572 //////////////////////////////////////////////////////////////////////////////
 573
 574 // eof