basegfx/source/polygon/b3dpolygonclipper.cxx

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