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