basegfx/source/tools/b2dclipstate.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 <basegfx/utils/b2dclipstate.hxx>
  21
  22 #include <basegfx/range/b2drange.hxx>
  23 #include <basegfx/range/b2dpolyrange.hxx>
  24 #include <basegfx/polygon/b2dpolygon.hxx>
  25 #include <basegfx/polygon/b2dpolygontools.hxx>
  26 #include <basegfx/polygon/b2dpolypolygon.hxx>
  27 #include <basegfx/polygon/b2dpolypolygontools.hxx>
  28 #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
  29
  30
  31 namespace basegfx
  32 {
  33 namespace utils
  34 {
  35     class ImplB2DClipState
  36     {
  37     public:
  38         enum Operation {UNION, INTERSECT, XOR, SUBTRACT};
  39
  40         ImplB2DClipState() :
  41             maPendingPolygons(),
  42             maPendingRanges(),
  43             maClipPoly(),
  44             mePendingOps(UNION)
  45         {}
  46
  47         explicit ImplB2DClipState( const B2DPolyPolygon& rPoly ) :
  48             maPendingPolygons(),
  49             maPendingRanges(),
  50             maClipPoly(rPoly),
  51             mePendingOps(UNION)
  52         {}
  53
  54         bool isCleared() const
  55         {
  56             return !maClipPoly.count()
  57                 && !maPendingPolygons.count()
  58                 && !maPendingRanges.count();
  59         }
  60
  61         bool isNullClipPoly() const
  62         {
  63             return maClipPoly.count() == 1
  64                 && !maClipPoly.getB2DPolygon(0).count();
  65         }
  66
  67         bool isNull() const
  68         {
  69             return !maPendingPolygons.count()
  70                 && !maPendingRanges.count()
  71                 && isNullClipPoly();
  72         }
  73
  74         void makeNull()
  75         {
  76             maPendingPolygons.clear();
  77             maPendingRanges.clear();
  78             maClipPoly.clear();
  79             maClipPoly.append(B2DPolygon());
  80             mePendingOps = UNION;
  81         }
  82
  83         bool operator==(const ImplB2DClipState& rRHS) const
  84         {
  85             return maPendingPolygons == rRHS.maPendingPolygons
  86                 && maPendingRanges == rRHS.maPendingRanges
  87                 && maClipPoly == rRHS.maClipPoly
  88                 && mePendingOps == rRHS.mePendingOps;
  89         }
  90
  91         void addRange(const B2DRange& rRange, Operation eOp)
  92         {
  93             if( rRange.isEmpty() )
  94                 return;
  95
  96             commitPendingPolygons();
  97             if( mePendingOps != eOp )
  98                 commitPendingRanges();
  99
 100             mePendingOps = eOp;
 101             maPendingRanges.appendElement(
 102                 rRange,
 103                 B2VectorOrientation::Positive);
 104         }
 105
 106         void addPolyPolygon(const B2DPolyPolygon& aPoly, Operation eOp)
 107         {
 108             commitPendingRanges();
 109             if( mePendingOps != eOp )
 110                 commitPendingPolygons();
 111
 112             mePendingOps = eOp;
 113             maPendingPolygons.append(aPoly);
 114         }
 115
 116         void unionRange(const B2DRange& rRange)
 117         {
 118             if( isCleared() )
 119                 return;
 120
 121             addRange(rRange,UNION);
 122         }
 123
 124         void unionPolyPolygon(const B2DPolyPolygon& rPolyPoly)
 125         {
 126             if( isCleared() )
 127                 return;
 128
 129             addPolyPolygon(rPolyPoly,UNION);
 130         }
 131
 132         void intersectRange(const B2DRange& rRange)
 133         {
 134             if( isNull() )
 135                 return;
 136
 137             addRange(rRange,INTERSECT);
 138         }
 139
 140         void intersectPolyPolygon(const B2DPolyPolygon& rPolyPoly)
 141         {
 142             if( isNull() )
 143                 return;
 144
 145             addPolyPolygon(rPolyPoly,INTERSECT);
 146         }
 147
 148         void subtractRange(const B2DRange& rRange )
 149         {
 150             if( isNull() )
 151                 return;
 152
 153             addRange(rRange,SUBTRACT);
 154         }
 155
 156         void subtractPolyPolygon(const B2DPolyPolygon& rPolyPoly)
 157         {
 158             if( isNull() )
 159                 return;
 160
 161             addPolyPolygon(rPolyPoly,SUBTRACT);
 162         }
 163
 164         void xorRange(const B2DRange& rRange)
 165         {
 166             addRange(rRange,XOR);
 167         }
 168
 169         void xorPolyPolygon(const B2DPolyPolygon& rPolyPoly)
 170         {
 171             addPolyPolygon(rPolyPoly,XOR);
 172         }
 173
 174         void transform(const basegfx::B2DHomMatrix& rTranslate)
 175         {
 176             maPendingRanges.transform(rTranslate);
 177             maPendingPolygons.transform(rTranslate);
 178             maClipPoly.transform(rTranslate);
 179         }
 180
 181         B2DPolyPolygon const & getClipPoly() const
 182         {
 183             commitPendingRanges();
 184             commitPendingPolygons();
 185
 186             return maClipPoly;
 187         }
 188
 189     private:
 190         void commitPendingPolygons() const
 191         {
 192             if( !maPendingPolygons.count() )
 193                 return;
 194
 195             // assumption: maClipPoly has kept polygons prepared for
 196             // clipping; i.e. no neutral polygons & correct
 197             // orientation
 198             maPendingPolygons = utils::prepareForPolygonOperation(maPendingPolygons);
 199             const bool bIsEmpty=isNullClipPoly();
 200             const bool bIsCleared=!maClipPoly.count();
 201             switch(mePendingOps)
 202             {
 203                 case UNION:
 204                     assert( !bIsCleared );
 205
 206                     if( bIsEmpty )
 207                         maClipPoly = maPendingPolygons;
 208                     else
 209                         maClipPoly = utils::solvePolygonOperationOr(
 210                             maClipPoly,
 211                             maPendingPolygons);
 212                     break;
 213                 case INTERSECT:
 214                     assert( !bIsEmpty );
 215
 216                     if( bIsCleared )
 217                         maClipPoly = maPendingPolygons;
 218                     else
 219                         maClipPoly = utils::solvePolygonOperationAnd(
 220                             maClipPoly,
 221                             maPendingPolygons);
 222                     break;
 223                 case XOR:
 224                     if( bIsEmpty )
 225                         maClipPoly = maPendingPolygons;
 226                     else if( bIsCleared )
 227                     {
 228                         // not representable, strictly speaking,
 229                         // using polygons with the common even/odd
 230                         // or nonzero winding number fill rule. If
 231                         // we'd want to represent it, fill rule
 232                         // would need to be "non-negative winding
 233                         // number" (and we then would return
 234                         // 'holes' here)
 235
 236                         // going for an ugly hack meanwhile
 237                         maClipPoly = utils::solvePolygonOperationXor(
 238                             B2DPolyPolygon(
 239                                 utils::createPolygonFromRect(B2DRange(-1E20,-1E20,1E20,1E20))),
 240                             maPendingPolygons);
 241                     }
 242                     else
 243                         maClipPoly = utils::solvePolygonOperationXor(
 244                             maClipPoly,
 245                             maPendingPolygons);
 246                     break;
 247                 case SUBTRACT:
 248                     assert( !bIsEmpty );
 249
 250                     // first union all pending ones, subtract en bloc then
 251                     maPendingPolygons = solveCrossovers(maPendingPolygons);
 252                     maPendingPolygons = stripNeutralPolygons(maPendingPolygons);
 253                     maPendingPolygons = stripDispensablePolygons(maPendingPolygons);
 254
 255                     if( bIsCleared )
 256                     {
 257                         // not representable, strictly speaking,
 258                         // using polygons with the common even/odd
 259                         // or nonzero winding number fill rule. If
 260                         // we'd want to represent it, fill rule
 261                         // would need to be "non-negative winding
 262                         // number" (and we then would return
 263                         // 'holes' here)
 264
 265                         // going for an ugly hack meanwhile
 266                         maClipPoly = utils::solvePolygonOperationDiff(
 267                             B2DPolyPolygon(
 268                                 utils::createPolygonFromRect(B2DRange(-1E20,-1E20,1E20,1E20))),
 269                             maPendingPolygons);
 270                     }
 271                     else
 272                         maClipPoly = utils::solvePolygonOperationDiff(
 273                             maClipPoly,
 274                             maPendingPolygons);
 275                     break;
 276             }
 277
 278             maPendingPolygons.clear();
 279             mePendingOps = UNION;
 280         }
 281
 282         void commitPendingRanges() const
 283         {
 284             if( !maPendingRanges.count() )
 285                 return;
 286
 287             // use the specialized range clipper for the win
 288             B2DPolyPolygon aCollectedRanges;
 289             const bool bIsEmpty=isNullClipPoly();
 290             const bool bIsCleared=!maClipPoly.count();
 291             switch(mePendingOps)
 292             {
 293                 case UNION:
 294                     assert( !bIsCleared );
 295
 296                     aCollectedRanges = maPendingRanges.solveCrossovers();
 297                     aCollectedRanges = stripNeutralPolygons(aCollectedRanges);
 298                     aCollectedRanges = stripDispensablePolygons(aCollectedRanges);
 299                     if( bIsEmpty )
 300                         maClipPoly = aCollectedRanges;
 301                     else
 302                         maClipPoly = utils::solvePolygonOperationOr(
 303                             maClipPoly,
 304                             aCollectedRanges);
 305                     break;
 306                 case INTERSECT:
 307                     assert( !bIsEmpty );
 308
 309                     aCollectedRanges = maPendingRanges.solveCrossovers();
 310                     aCollectedRanges = stripNeutralPolygons(aCollectedRanges);
 311                     if( maPendingRanges.count() > 1 )
 312                         aCollectedRanges = stripDispensablePolygons(aCollectedRanges, true);
 313
 314                     if( bIsCleared )
 315                         maClipPoly = aCollectedRanges;
 316                     else
 317                         maClipPoly = utils::solvePolygonOperationAnd(
 318                             maClipPoly,
 319                             aCollectedRanges);
 320                     break;
 321                 case XOR:
 322                     aCollectedRanges = maPendingRanges.solveCrossovers();
 323                     aCollectedRanges = stripNeutralPolygons(aCollectedRanges);
 324                     aCollectedRanges = correctOrientations(aCollectedRanges);
 325
 326                     if( bIsEmpty )
 327                         maClipPoly = aCollectedRanges;
 328                     else if( bIsCleared )
 329                     {
 330                         // not representable, strictly speaking,
 331                         // using polygons with the common even/odd
 332                         // or nonzero winding number fill rule. If
 333                         // we'd want to represent it, fill rule
 334                         // would need to be "non-negative winding
 335                         // number" (and we then would return
 336                         // 'holes' here)
 337
 338                         // going for an ugly hack meanwhile
 339                         maClipPoly = utils::solvePolygonOperationXor(
 340                             B2DPolyPolygon(
 341                                 utils::createPolygonFromRect(B2DRange(-1E20,-1E20,1E20,1E20))),
 342                             aCollectedRanges);
 343                     }
 344                     else
 345                         maClipPoly = utils::solvePolygonOperationXor(
 346                             maClipPoly,
 347                             aCollectedRanges);
 348                     break;
 349                 case SUBTRACT:
 350                     assert( !bIsEmpty );
 351
 352                     // first union all pending ranges, subtract en bloc then
 353                     aCollectedRanges = maPendingRanges.solveCrossovers();
 354                     aCollectedRanges = stripNeutralPolygons(aCollectedRanges);
 355                     aCollectedRanges = stripDispensablePolygons(aCollectedRanges);
 356
 357                     if( bIsCleared )
 358                     {
 359                         // not representable, strictly speaking,
 360                         // using polygons with the common even/odd
 361                         // or nonzero winding number fill rule. If
 362                         // we'd want to represent it, fill rule
 363                         // would need to be "non-negative winding
 364                         // number" (and we then would return
 365                         // 'holes' here)
 366
 367                         // going for an ugly hack meanwhile
 368                         maClipPoly = utils::solvePolygonOperationDiff(
 369                             B2DPolyPolygon(
 370                                 utils::createPolygonFromRect(B2DRange(-1E20,-1E20,1E20,1E20))),
 371                             aCollectedRanges);
 372                     }
 373                     else
 374                         maClipPoly = utils::solvePolygonOperationDiff(
 375                             maClipPoly,
 376                             aCollectedRanges);
 377                     break;
 378             }
 379
 380             maPendingRanges.clear();
 381             mePendingOps = UNION;
 382         }
 383
 384         mutable B2DPolyPolygon maPendingPolygons;
 385         mutable B2DPolyRange   maPendingRanges;
 386         mutable B2DPolyPolygon maClipPoly;
 387         mutable Operation      mePendingOps;
 388     };
 389
 390     B2DClipState::B2DClipState() = default;
 391
 392     B2DClipState::~B2DClipState() = default;
 393
 394     B2DClipState::B2DClipState( const B2DClipState& ) = default;
 395
 396     B2DClipState::B2DClipState( B2DClipState&& ) = default;
 397
 398     B2DClipState::B2DClipState( const B2DPolyPolygon& rPolyPoly ) :
 399         mpImpl( ImplB2DClipState(rPolyPoly) )
 400     {}
 401
 402     B2DClipState& B2DClipState::operator=( const B2DClipState& ) = default;
 403
 404     B2DClipState& B2DClipState::operator=( B2DClipState&& ) = default;
 405
 406     void B2DClipState::makeNull()
 407     {
 408         mpImpl->makeNull();
 409     }
 410
 411     bool B2DClipState::isCleared() const
 412     {
 413         return mpImpl->isCleared();
 414     }
 415
 416     bool B2DClipState::operator==(const B2DClipState& rRHS) const
 417     {
 418         if(mpImpl.same_object(rRHS.mpImpl))
 419             return true;
 420
 421         return ((*mpImpl) == (*rRHS.mpImpl));
 422     }
 423
 424     bool B2DClipState::operator!=(const B2DClipState& rRHS) const
 425     {
 426         return !(*this == rRHS);
 427     }
 428
 429     void B2DClipState::unionRange(const B2DRange& rRange)
 430     {
 431         mpImpl->unionRange(rRange);
 432     }
 433
 434     void B2DClipState::unionPolyPolygon(const B2DPolyPolygon& rPolyPoly)
 435     {
 436         mpImpl->unionPolyPolygon(rPolyPoly);
 437     }
 438
 439     void B2DClipState::intersectRange(const B2DRange& rRange)
 440     {
 441         mpImpl->intersectRange(rRange);
 442     }
 443
 444     void B2DClipState::intersectPolyPolygon(const B2DPolyPolygon& rPolyPoly)
 445     {
 446         mpImpl->intersectPolyPolygon(rPolyPoly);
 447     }
 448
 449     void B2DClipState::subtractRange(const B2DRange& rRange)
 450     {
 451         mpImpl->subtractRange(rRange);
 452     }
 453
 454     void B2DClipState::subtractPolyPolygon(const B2DPolyPolygon& rPolyPoly)
 455     {
 456         mpImpl->subtractPolyPolygon(rPolyPoly);
 457     }
 458
 459     void B2DClipState::xorRange(const B2DRange& rRange)
 460     {
 461         mpImpl->xorRange(rRange);
 462     }
 463
 464     void B2DClipState::xorPolyPolygon(const B2DPolyPolygon& rPolyPoly)
 465     {
 466         mpImpl->xorPolyPolygon(rPolyPoly);
 467     }
 468
 469     B2DPolyPolygon const & B2DClipState::getClipPoly() const
 470     {
 471         return mpImpl->getClipPoly();
 472     }
 473
 474     void B2DClipState::transform(const basegfx::B2DHomMatrix& rTranslate)
 475     {
 476         return mpImpl->transform(rTranslate);
 477     }
 478
 479
 480 } // end of namespace utils
 481 } // end of namespace basegfx
 482
 483 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */