LCOV - code coverage report
Current view: top level - basegfx/source/polygon - b2dpolygonclipper.cxx (source / functions) Hit Total Coverage
Test: commit e02a6cb2c3e2b23b203b422e4e0680877f232636 Lines: 0 254 0.0 %
Date: 2014-04-14 Functions: 0 8 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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/polygon/b2dpolygonclipper.hxx>
      21             : #include <osl/diagnose.h>
      22             : #include <basegfx/polygon/b2dpolygontools.hxx>
      23             : #include <basegfx/numeric/ftools.hxx>
      24             : #include <basegfx/matrix/b2dhommatrix.hxx>
      25             : #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
      26             : #include <basegfx/polygon/b2dpolygoncutandtouch.hxx>
      27             : #include <basegfx/polygon/b2dpolypolygontools.hxx>
      28             : #include <basegfx/curve/b2dcubicbezier.hxx>
      29             : #include <basegfx/tools/rectcliptools.hxx>
      30             : #include <basegfx/matrix/b2dhommatrixtools.hxx>
      31             : 
      32             : 
      33             : 
      34             : namespace basegfx
      35             : {
      36             :     namespace tools
      37             :     {
      38           0 :         B2DPolyPolygon clipPolygonOnParallelAxis(const B2DPolygon& rCandidate, bool bParallelToXAxis, bool bAboveAxis, double fValueOnOtherAxis, bool bStroke)
      39             :         {
      40           0 :             B2DPolyPolygon aRetval;
      41             : 
      42           0 :             if(rCandidate.count())
      43             :             {
      44           0 :                 const B2DRange aCandidateRange(getRange(rCandidate));
      45             : 
      46           0 :                 if(bParallelToXAxis && fTools::moreOrEqual(aCandidateRange.getMinY(), fValueOnOtherAxis))
      47             :                 {
      48             :                     // completely above and on the clip line. also true for curves.
      49           0 :                     if(bAboveAxis)
      50             :                     {
      51             :                         // add completely
      52           0 :                         aRetval.append(rCandidate);
      53             :                     }
      54             :                 }
      55           0 :                 else if(bParallelToXAxis && fTools::lessOrEqual(aCandidateRange.getMaxY(), fValueOnOtherAxis))
      56             :                 {
      57             :                     // completely below and on the clip line. also true for curves.
      58           0 :                     if(!bAboveAxis)
      59             :                     {
      60             :                         // add completely
      61           0 :                         aRetval.append(rCandidate);
      62             :                     }
      63             :                 }
      64           0 :                 else if(!bParallelToXAxis && fTools::moreOrEqual(aCandidateRange.getMinX(), fValueOnOtherAxis))
      65             :                 {
      66             :                     // completely right of and on the clip line. also true for curves.
      67           0 :                     if(bAboveAxis)
      68             :                     {
      69             :                         // add completely
      70           0 :                         aRetval.append(rCandidate);
      71             :                     }
      72             :                 }
      73           0 :                 else if(!bParallelToXAxis && fTools::lessOrEqual(aCandidateRange.getMaxX(), fValueOnOtherAxis))
      74             :                 {
      75             :                     // completely left of and on the clip line. also true for curves.
      76           0 :                     if(!bAboveAxis)
      77             :                     {
      78             :                         // add completely
      79           0 :                         aRetval.append(rCandidate);
      80             :                     }
      81             :                 }
      82             :                 else
      83             :                 {
      84             :                     // add cuts with axis to polygon, including bezier segments
      85             :                     // Build edge to cut with. Make it a little big longer than needed for
      86             :                     // numerical stability. We want to cut against the edge seen as endless
      87             :                     // ray here, but addPointsAtCuts() will limit itself to the
      88             :                     // edge's range ]0.0 .. 1.0[.
      89           0 :                     const double fSmallExtension((aCandidateRange.getWidth() + aCandidateRange.getHeight()) * (0.5 * 0.1));
      90             :                     const B2DPoint aStart(
      91           0 :                         bParallelToXAxis ? aCandidateRange.getMinX() - fSmallExtension : fValueOnOtherAxis,
      92           0 :                         bParallelToXAxis ? fValueOnOtherAxis : aCandidateRange.getMinY() - fSmallExtension);
      93             :                     const B2DPoint aEnd(
      94           0 :                         bParallelToXAxis ? aCandidateRange.getMaxX() + fSmallExtension : fValueOnOtherAxis,
      95           0 :                         bParallelToXAxis ? fValueOnOtherAxis : aCandidateRange.getMaxY() + fSmallExtension);
      96           0 :                     const B2DPolygon aCandidate(addPointsAtCuts(rCandidate, aStart, aEnd));
      97           0 :                     const sal_uInt32 nPointCount(aCandidate.count());
      98           0 :                     const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L);
      99           0 :                     B2DCubicBezier aEdge;
     100           0 :                     B2DPolygon aRun;
     101             : 
     102           0 :                     for(sal_uInt32 a(0L); a < nEdgeCount; a++)
     103             :                     {
     104           0 :                         aCandidate.getBezierSegment(a, aEdge);
     105           0 :                         const B2DPoint aTestPoint(aEdge.interpolatePoint(0.5));
     106             :                         const bool bInside(bParallelToXAxis ?
     107           0 :                             fTools::moreOrEqual(aTestPoint.getY(), fValueOnOtherAxis) == bAboveAxis :
     108           0 :                             fTools::moreOrEqual(aTestPoint.getX(), fValueOnOtherAxis) == bAboveAxis);
     109             : 
     110           0 :                         if(bInside)
     111             :                         {
     112           0 :                             if(!aRun.count() || !aRun.getB2DPoint(aRun.count() - 1).equal(aEdge.getStartPoint()))
     113             :                             {
     114           0 :                                 aRun.append(aEdge.getStartPoint());
     115             :                             }
     116             : 
     117           0 :                             if(aEdge.isBezier())
     118             :                             {
     119           0 :                                 aRun.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint());
     120             :                             }
     121             :                             else
     122             :                             {
     123           0 :                                 aRun.append(aEdge.getEndPoint());
     124             :                             }
     125             :                         }
     126             :                         else
     127             :                         {
     128           0 :                             if(bStroke && aRun.count())
     129             :                             {
     130           0 :                                 aRetval.append(aRun);
     131           0 :                                 aRun.clear();
     132             :                             }
     133             :                         }
     134           0 :                     }
     135             : 
     136           0 :                     if(aRun.count())
     137             :                     {
     138           0 :                         if(bStroke)
     139             :                         {
     140             :                             // try to merge this last and first polygon; they may have been
     141             :                             // the former polygon's start/end point
     142           0 :                             if(aRetval.count())
     143             :                             {
     144           0 :                                 const B2DPolygon aStartPolygon(aRetval.getB2DPolygon(0));
     145             : 
     146           0 :                                 if(aStartPolygon.count() && aStartPolygon.getB2DPoint(0).equal(aRun.getB2DPoint(aRun.count() - 1)))
     147             :                                 {
     148             :                                     // append start polygon to aRun, remove from result set
     149           0 :                                     aRun.append(aStartPolygon); aRun.removeDoublePoints();
     150           0 :                                     aRetval.remove(0);
     151           0 :                                 }
     152             :                             }
     153             : 
     154           0 :                             aRetval.append(aRun);
     155             :                         }
     156             :                         else
     157             :                         {
     158             :                             // set closed flag and correct last point (which is added double now).
     159           0 :                             closeWithGeometryChange(aRun);
     160           0 :                             aRetval.append(aRun);
     161             :                         }
     162           0 :                     }
     163             :                 }
     164             :             }
     165             : 
     166           0 :             return aRetval;
     167             :         }
     168             : 
     169           0 :         B2DPolyPolygon clipPolyPolygonOnParallelAxis(const B2DPolyPolygon& rCandidate, bool bParallelToXAxis, bool bAboveAxis, double fValueOnOtherAxis, bool bStroke)
     170             :         {
     171           0 :             const sal_uInt32 nPolygonCount(rCandidate.count());
     172           0 :             B2DPolyPolygon aRetval;
     173             : 
     174           0 :             for(sal_uInt32 a(0L); a < nPolygonCount; a++)
     175             :             {
     176           0 :                 const B2DPolyPolygon aClippedPolyPolygon(clipPolygonOnParallelAxis(rCandidate.getB2DPolygon(a), bParallelToXAxis, bAboveAxis, fValueOnOtherAxis, bStroke));
     177             : 
     178           0 :                 if(aClippedPolyPolygon.count())
     179             :                 {
     180           0 :                     aRetval.append(aClippedPolyPolygon);
     181             :                 }
     182           0 :             }
     183             : 
     184           0 :             return aRetval;
     185             :         }
     186             : 
     187           0 :         B2DPolyPolygon clipPolygonOnRange(const B2DPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke)
     188             :         {
     189           0 :             const sal_uInt32 nCount(rCandidate.count());
     190           0 :             B2DPolyPolygon aRetval;
     191             : 
     192           0 :             if(!nCount)
     193             :             {
     194             :                 // source is empty
     195           0 :                 return aRetval;
     196             :             }
     197             : 
     198           0 :             if(rRange.isEmpty())
     199             :             {
     200           0 :                 if(bInside)
     201             :                 {
     202             :                     // nothing is inside an empty range
     203           0 :                     return aRetval;
     204             :                 }
     205             :                 else
     206             :                 {
     207             :                     // everything is outside an empty range
     208           0 :                     return B2DPolyPolygon(rCandidate);
     209             :                 }
     210             :             }
     211             : 
     212           0 :             const B2DRange aCandidateRange(getRange(rCandidate));
     213             : 
     214           0 :             if(rRange.isInside(aCandidateRange))
     215             :             {
     216             :                   // candidate is completely inside given range
     217           0 :                 if(bInside)
     218             :                 {
     219             :                     // nothing to do
     220           0 :                     return B2DPolyPolygon(rCandidate);
     221             :                 }
     222             :                 else
     223             :                 {
     224             :                     // nothing is outside, then
     225           0 :                     return aRetval;
     226             :                 }
     227             :             }
     228             : 
     229           0 :             if(!bInside)
     230             :             {
     231             :                 // cutting off the outer parts of filled polygons at parallell
     232             :                 // lines to the axes is only possible for the inner part, not for
     233             :                 // the outer part which means cutting a hole into the original polygon.
     234             :                 // This is because the inner part is a logical AND-operation of
     235             :                 // the four implied half-planes, but the outer part is not.
     236             :                 // It is possible for strokes, but with creating unnecessary extra
     237             :                 // cuts, so using clipPolygonOnPolyPolygon is better there, too.
     238             :                 // This needs to be done with the topology knowlegde and is unfurtunately
     239             :                 // more expensive, too.
     240           0 :                 const B2DPolygon aClip(createPolygonFromRect(rRange));
     241             : 
     242           0 :                 return clipPolygonOnPolyPolygon(rCandidate, B2DPolyPolygon(aClip), bInside, bStroke);
     243             :             }
     244             : 
     245             :             // clip against the four axes of the range
     246             :             // against X-Axis, lower value
     247           0 :             aRetval = clipPolygonOnParallelAxis(rCandidate, true, bInside, rRange.getMinY(), bStroke);
     248             : 
     249           0 :             if(aRetval.count())
     250             :             {
     251             :                 // against Y-Axis, lower value
     252           0 :                 if(1L == aRetval.count())
     253             :                 {
     254           0 :                     aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), false, bInside, rRange.getMinX(), bStroke);
     255             :                 }
     256             :                 else
     257             :                 {
     258           0 :                     aRetval = clipPolyPolygonOnParallelAxis(aRetval, false, bInside, rRange.getMinX(), bStroke);
     259             :                 }
     260             : 
     261           0 :                 if(aRetval.count())
     262             :                 {
     263             :                     // against X-Axis, higher value
     264           0 :                     if(1L == aRetval.count())
     265             :                     {
     266           0 :                         aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), true, !bInside, rRange.getMaxY(), bStroke);
     267             :                     }
     268             :                     else
     269             :                     {
     270           0 :                         aRetval = clipPolyPolygonOnParallelAxis(aRetval, true, !bInside, rRange.getMaxY(), bStroke);
     271             :                     }
     272             : 
     273           0 :                     if(aRetval.count())
     274             :                     {
     275             :                         // against Y-Axis, higher value
     276           0 :                         if(1L == aRetval.count())
     277             :                         {
     278           0 :                             aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), false, !bInside, rRange.getMaxX(), bStroke);
     279             :                         }
     280             :                         else
     281             :                         {
     282           0 :                             aRetval = clipPolyPolygonOnParallelAxis(aRetval, false, !bInside, rRange.getMaxX(), bStroke);
     283             :                         }
     284             :                     }
     285             :                 }
     286             :             }
     287             : 
     288           0 :             return aRetval;
     289             :         }
     290             : 
     291           0 :         B2DPolyPolygon clipPolyPolygonOnRange(const B2DPolyPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke)
     292             :         {
     293           0 :             const sal_uInt32 nPolygonCount(rCandidate.count());
     294           0 :             B2DPolyPolygon aRetval;
     295             : 
     296           0 :             if(!nPolygonCount)
     297             :             {
     298             :                 // source is empty
     299           0 :                 return aRetval;
     300             :             }
     301             : 
     302           0 :             if(rRange.isEmpty())
     303             :             {
     304           0 :                 if(bInside)
     305             :                 {
     306             :                     // nothing is inside an empty range
     307           0 :                     return aRetval;
     308             :                 }
     309             :                 else
     310             :                 {
     311             :                     // everything is outside an empty range
     312           0 :                     return rCandidate;
     313             :                 }
     314             :             }
     315             : 
     316           0 :             if(bInside)
     317             :             {
     318           0 :                 for(sal_uInt32 a(0L); a < nPolygonCount; a++)
     319             :                 {
     320           0 :                     const B2DPolyPolygon aClippedPolyPolygon(clipPolygonOnRange(rCandidate.getB2DPolygon(a), rRange, bInside, bStroke));
     321             : 
     322           0 :                     if(aClippedPolyPolygon.count())
     323             :                     {
     324           0 :                         aRetval.append(aClippedPolyPolygon);
     325             :                     }
     326           0 :                 }
     327             :             }
     328             :             else
     329             :             {
     330             :                 // for details, see comment in clipPolygonOnRange for the "cutting off
     331             :                 // the outer parts of filled polygons at parallell lines" explanations
     332           0 :                 const B2DPolygon aClip(createPolygonFromRect(rRange));
     333             : 
     334           0 :                 return clipPolyPolygonOnPolyPolygon(rCandidate, B2DPolyPolygon(aClip), bInside, bStroke);
     335             :             }
     336             : 
     337           0 :             return aRetval;
     338             :         }
     339             : 
     340             : 
     341             : 
     342           0 :         B2DPolyPolygon clipPolyPolygonOnPolyPolygon(const B2DPolyPolygon& rCandidate, const B2DPolyPolygon& rClip, bool bInside, bool bStroke)
     343             :         {
     344           0 :             B2DPolyPolygon aRetval;
     345             : 
     346           0 :             if(rCandidate.count() && rClip.count())
     347             :             {
     348           0 :                 if(bStroke)
     349             :                 {
     350             :                     // line clipping, create line snippets by first adding all cut points and
     351             :                     // then marching along the edges and detecting if they are inside or outside
     352             :                     // the clip polygon
     353           0 :                     for(sal_uInt32 a(0); a < rCandidate.count(); a++)
     354             :                     {
     355             :                         // add cuts with clip to polygon, including bezier segments
     356           0 :                         const B2DPolygon aCandidate(addPointsAtCuts(rCandidate.getB2DPolygon(a), rClip));
     357           0 :                         const sal_uInt32 nPointCount(aCandidate.count());
     358           0 :                         const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L);
     359           0 :                         B2DCubicBezier aEdge;
     360           0 :                         B2DPolygon aRun;
     361             : 
     362           0 :                         for(sal_uInt32 b(0); b < nEdgeCount; b++)
     363             :                         {
     364           0 :                             aCandidate.getBezierSegment(b, aEdge);
     365           0 :                             const B2DPoint aTestPoint(aEdge.interpolatePoint(0.5));
     366           0 :                             const bool bIsInside(tools::isInside(rClip, aTestPoint) == bInside);
     367             : 
     368           0 :                             if(bIsInside)
     369             :                             {
     370           0 :                                 if(!aRun.count())
     371             :                                 {
     372           0 :                                     aRun.append(aEdge.getStartPoint());
     373             :                                 }
     374             : 
     375           0 :                                 if(aEdge.isBezier())
     376             :                                 {
     377           0 :                                     aRun.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint());
     378             :                                 }
     379             :                                 else
     380             :                                 {
     381           0 :                                     aRun.append(aEdge.getEndPoint());
     382             :                                 }
     383             :                             }
     384             :                             else
     385             :                             {
     386           0 :                                 if(aRun.count())
     387             :                                 {
     388           0 :                                     aRetval.append(aRun);
     389           0 :                                     aRun.clear();
     390             :                                 }
     391             :                             }
     392           0 :                         }
     393             : 
     394           0 :                         if(aRun.count())
     395             :                         {
     396             :                             // try to merge this last and first polygon; they may have been
     397             :                             // the former polygon's start/end point
     398           0 :                             if(aRetval.count())
     399             :                             {
     400           0 :                                 const B2DPolygon aStartPolygon(aRetval.getB2DPolygon(0));
     401             : 
     402           0 :                                 if(aStartPolygon.count() && aStartPolygon.getB2DPoint(0).equal(aRun.getB2DPoint(aRun.count() - 1)))
     403             :                                 {
     404             :                                     // append start polygon to aRun, remove from result set
     405           0 :                                     aRun.append(aStartPolygon); aRun.removeDoublePoints();
     406           0 :                                     aRetval.remove(0);
     407           0 :                                 }
     408             :                             }
     409             : 
     410           0 :                             aRetval.append(aRun);
     411             :                         }
     412           0 :                     }
     413             :                 }
     414             :                 else
     415             :                 {
     416             :                     // area clipping
     417           0 :                     B2DPolyPolygon aMergePolyPolygonA(rClip);
     418             : 
     419             :                     // First solve all polygon-self and polygon-polygon intersections.
     420             :                     // Also get rid of some not-needed polygons (neutral, no area -> when
     421             :                     // no intersections, these are tubes).
     422             :                     // Now it is possible to correct the orientations in the cut-free
     423             :                     // polygons to values corresponding to painting the PolyPolygon with
     424             :                     // a XOR-WindingRule.
     425           0 :                     aMergePolyPolygonA = solveCrossovers(aMergePolyPolygonA);
     426           0 :                     aMergePolyPolygonA = stripNeutralPolygons(aMergePolyPolygonA);
     427           0 :                     aMergePolyPolygonA = correctOrientations(aMergePolyPolygonA);
     428             : 
     429           0 :                     if(!bInside)
     430             :                     {
     431             :                         // if we want to get the outside of the clip polygon, make
     432             :                         // it a 'Hole' in topological sense
     433           0 :                         aMergePolyPolygonA.flip();
     434             :                     }
     435             : 
     436           0 :                     B2DPolyPolygon aMergePolyPolygonB(rCandidate);
     437             : 
     438             :                     // prepare 2nd source polygon in same way
     439           0 :                     aMergePolyPolygonB = solveCrossovers(aMergePolyPolygonB);
     440           0 :                     aMergePolyPolygonB = stripNeutralPolygons(aMergePolyPolygonB);
     441           0 :                     aMergePolyPolygonB = correctOrientations(aMergePolyPolygonB);
     442             : 
     443             :                     // to clip against each other, concatenate and solve all
     444             :                     // polygon-polygon crossovers. polygon-self do not need to
     445             :                     // be solved again, they were solved in the preparation.
     446           0 :                     aRetval.append(aMergePolyPolygonA);
     447           0 :                     aRetval.append(aMergePolyPolygonB);
     448           0 :                     aRetval = solveCrossovers(aRetval);
     449             : 
     450             :                     // now remove neutral polygons (closed, but no area). In a last
     451             :                     // step throw away all polygons which have a depth of less than 1
     452             :                     // which means there was no logical AND at their position. For the
     453             :                     // not-inside solution, the clip was flipped to define it as 'Hole',
     454             :                     // so the removal rule is different here; remove all with a depth
     455             :                     // of less than 0 (aka holes).
     456           0 :                     aRetval = stripNeutralPolygons(aRetval);
     457           0 :                     aRetval = stripDispensablePolygons(aRetval, bInside);
     458             :                 }
     459             :             }
     460             : 
     461           0 :             return aRetval;
     462             :         }
     463             : 
     464             : 
     465             : 
     466           0 :         B2DPolyPolygon clipPolygonOnPolyPolygon(const B2DPolygon& rCandidate, const B2DPolyPolygon& rClip, bool bInside, bool bStroke)
     467             :         {
     468           0 :             B2DPolyPolygon aRetval;
     469             : 
     470           0 :             if(rCandidate.count() && rClip.count())
     471             :             {
     472           0 :                 aRetval = clipPolyPolygonOnPolyPolygon(B2DPolyPolygon(rCandidate), rClip, bInside, bStroke);
     473             :             }
     474             : 
     475           0 :             return aRetval;
     476             :         }
     477             : 
     478             : 
     479             : 
     480             :         /*
     481             :         * let a plane be defined as
     482             :         *
     483             :         *     v.n+d=0
     484             :         *
     485             :         * and a ray be defined as
     486             :         *
     487             :         *     a+(b-a)*t=0
     488             :         *
     489             :         * substitute and rearranging yields
     490             :         *
     491             :         *     t = -(a.n+d)/(n.(b-a))
     492             :         *
     493             :         * if the denominator is zero, the line is either
     494             :         * contained in the plane or parallel to the plane.
     495             :         * in either case, there is no intersection.
     496             :         * if numerator and denominator are both zero, the
     497             :         * ray is contained in the plane.
     498             :         *
     499             :         */
     500             :         struct scissor_plane {
     501             :             double nx,ny;           // plane normal
     502             :             double d;               // [-] minimum distance from origin
     503             :             sal_uInt32 clipmask;    // clipping mask, e.g. 1000 1000
     504             :         };
     505             : 
     506             :         /*
     507             :         *
     508             :         * polygon clipping rules  (straight out of Foley and Van Dam)
     509             :         * ===========================================================
     510             :         * current   |next       |emit
     511             :         * ____________________________________
     512             :         * inside    |inside     |next
     513             :         * inside    |outside    |intersect with clip plane
     514             :         * outside   |outside    |nothing
     515             :         * outside   |inside     |intersect with clip plane follwed by next
     516             :         *
     517             :         */
     518           0 :         sal_uInt32 scissorLineSegment( ::basegfx::B2DPoint           *in_vertex,    // input buffer
     519             :                                        sal_uInt32                     in_count,     // number of verts in input buffer
     520             :                                        ::basegfx::B2DPoint           *out_vertex,   // output buffer
     521             :                                        scissor_plane                 *pPlane,       // scissoring plane
     522             :                                        const ::basegfx::B2DRectangle &rR )          // clipping rectangle
     523             :         {
     524             :             ::basegfx::B2DPoint *curr;
     525             :             ::basegfx::B2DPoint *next;
     526             : 
     527           0 :             sal_uInt32 out_count=0;
     528             : 
     529             :             // process all the verts
     530           0 :             for(sal_uInt32 i=0; i<in_count; i++) {
     531             : 
     532             :                 // vertices are relative to the coordinate
     533             :                 // system defined by the rectangle.
     534           0 :                 curr = &in_vertex[i];
     535           0 :                 next = &in_vertex[(i+1)%in_count];
     536             : 
     537             :                 // perform clipping judgement & mask against current plane.
     538           0 :                 sal_uInt32 clip = pPlane->clipmask & ((getCohenSutherlandClipFlags(*curr,rR)<<4)|getCohenSutherlandClipFlags(*next,rR));
     539             : 
     540           0 :                 if(clip==0) { // both verts are inside
     541           0 :                     out_vertex[out_count++] = *next;
     542             :                 }
     543           0 :                 else if((clip&0x0f) && (clip&0xf0)) { // both verts are outside
     544             :                 }
     545           0 :                 else if((clip&0x0f) && (clip&0xf0)==0) { // curr is inside, next is outside
     546             : 
     547             :                     // direction vector from 'current' to 'next', *not* normalized
     548             :                     // to bring 't' into the [0<=x<=1] intervall.
     549           0 :                     ::basegfx::B2DPoint dir((*next)-(*curr));
     550             : 
     551           0 :                     double denominator = ( pPlane->nx*dir.getX() +
     552           0 :                                         pPlane->ny*dir.getY() );
     553           0 :                     double numerator = ( pPlane->nx*curr->getX() +
     554           0 :                                         pPlane->ny*curr->getY() +
     555           0 :                                         pPlane->d );
     556           0 :                     double t = -numerator/denominator;
     557             : 
     558             :                     // calculate the actual point of intersection
     559           0 :                     ::basegfx::B2DPoint intersection( curr->getX()+t*dir.getX(),
     560           0 :                                                     curr->getY()+t*dir.getY() );
     561             : 
     562           0 :                     out_vertex[out_count++] = intersection;
     563             :                 }
     564           0 :                 else if((clip&0x0f)==0 && (clip&0xf0)) { // curr is outside, next is inside
     565             : 
     566             :                     // direction vector from 'current' to 'next', *not* normalized
     567             :                     // to bring 't' into the [0<=x<=1] intervall.
     568           0 :                     ::basegfx::B2DPoint dir((*next)-(*curr));
     569             : 
     570           0 :                     double denominator = ( pPlane->nx*dir.getX() +
     571           0 :                                         pPlane->ny*dir.getY() );
     572           0 :                     double numerator = ( pPlane->nx*curr->getX() +
     573           0 :                                         pPlane->ny*curr->getY() +
     574           0 :                                         pPlane->d );
     575           0 :                     double t = -numerator/denominator;
     576             : 
     577             :                     // calculate the actual point of intersection
     578           0 :                     ::basegfx::B2DPoint intersection( curr->getX()+t*dir.getX(),
     579           0 :                                                     curr->getY()+t*dir.getY() );
     580             : 
     581           0 :                     out_vertex[out_count++] = intersection;
     582           0 :                     out_vertex[out_count++] = *next;
     583             :                 }
     584             :             }
     585             : 
     586           0 :             return out_count;
     587             :         }
     588             : 
     589           0 :         B2DPolygon clipTriangleListOnRange( const B2DPolygon& rCandidate,
     590             :                                             const B2DRange&   rRange )
     591             :         {
     592           0 :             B2DPolygon aResult;
     593             : 
     594           0 :             if( !(rCandidate.count()%3) )
     595             :             {
     596           0 :                 const int scissor_plane_count = 4;
     597             : 
     598             :                 scissor_plane sp[scissor_plane_count];
     599             : 
     600           0 :                 sp[0].nx = +1.0;
     601           0 :                 sp[0].ny = +0.0;
     602           0 :                 sp[0].d = -(rRange.getMinX());
     603           0 :                 sp[0].clipmask = (RectClipFlags::LEFT << 4) | RectClipFlags::LEFT; // 0001 0001
     604           0 :                 sp[1].nx = -1.0;
     605           0 :                 sp[1].ny = +0.0;
     606           0 :                 sp[1].d = +(rRange.getMaxX());
     607           0 :                 sp[1].clipmask = (RectClipFlags::RIGHT << 4) | RectClipFlags::RIGHT; // 0010 0010
     608           0 :                 sp[2].nx = +0.0;
     609           0 :                 sp[2].ny = +1.0;
     610           0 :                 sp[2].d = -(rRange.getMinY());
     611           0 :                 sp[2].clipmask = (RectClipFlags::TOP << 4) | RectClipFlags::TOP; // 0100 0100
     612           0 :                 sp[3].nx = +0.0;
     613           0 :                 sp[3].ny = -1.0;
     614           0 :                 sp[3].d = +(rRange.getMaxY());
     615           0 :                 sp[3].clipmask = (RectClipFlags::BOTTOM << 4) | RectClipFlags::BOTTOM; // 1000 1000
     616             : 
     617             :                 // retrieve the number of vertices of the triangulated polygon
     618           0 :                 const sal_uInt32 nVertexCount = rCandidate.count();
     619             : 
     620           0 :                 if(nVertexCount)
     621             :                 {
     622             :                     // Upper bound for the maximal number of vertices when intersecting an
     623             :                     // axis-aligned rectangle with a triangle in E2
     624             : 
     625             :                     // The rectangle and the triangle are in general position, and have 4 and 3
     626             :                     // vertices, respectively.
     627             : 
     628             :                     //   Lemma: Since the rectangle is a convex polygon ( see
     629             :                     //   http://mathworld.wolfram.com/ConvexPolygon.html for a definition), and
     630             :                     //   has no holes, it follows that any straight line will intersect the
     631             :                     //   rectangle's border line at utmost two times (with the usual
     632             :                     //   tie-breaking rule, if the intersection exactly hits an already existing
     633             :                     //   rectangle vertex, that this intersection is only attributed to one of
     634             :                     //   the adjoining edges). Thus, having a rectangle intersected with
     635             :                     //   a half-plane (one side of a straight line denotes 'inside', the
     636             :                     //   other 'outside') will at utmost add _one_  vertex to the resulting
     637             :                     //   intersection polygon (adding two intersection vertices, and removing at
     638             :                     //   least one rectangle vertex):
     639             : 
     640             :                     //         *
     641             :                     //     +--+-----------------+
     642             :                     //     | *                  |
     643             :                     //     |*                   |
     644             :                     //     +                    |
     645             :                     //    *|                    |
     646             :                     //   * |                    |
     647             :                     //     +--------------------+
     648             : 
     649             :                     //   Proof: If the straight line intersects the rectangle two
     650             :                     //   times, it does so for distinct edges, i.e. the intersection has
     651             :                     //   minimally one of the rectangle's vertices on either side of the straight
     652             :                     //   line (but maybe more). Thus, the intersection with a half-plane has
     653             :                     //   minimally _one_ rectangle vertex removed from the resulting clip
     654             :                     //   polygon, and therefore, a clip against a half-plane has the net effect
     655             :                     //   of adding at utmost _one_ vertex to the resulting clip polygon.
     656             : 
     657             :                     // Theorem: The intersection of a rectangle and a triangle results in a
     658             :                     // polygon with at utmost 7 vertices.
     659             : 
     660             :                     // Proof: The inside of the triangle can be described as the consecutive
     661             :                     // intersection with three half-planes. Together with the lemma above, this
     662             :                     // results in at utmost 3 additional vertices added to the already existing 4
     663             :                     // rectangle vertices.
     664             : 
     665             :                     // This upper bound is attained with the following example configuration:
     666             : 
     667             :                     //                               *
     668             :                     //                             ***
     669             :                     //                           ** *
     670             :                     //                         **  *
     671             :                     //                       **   *
     672             :                     //                     **    *
     673             :                     //                   **     *
     674             :                     //                 **      *
     675             :                     //               **       *
     676             :                     //             **        *
     677             :                     //           **         *
     678             :                     //     ----*2--------3 *
     679             :                     //     | **          |*
     680             :                     //     1*            4
     681             :                     //   **|            *|
     682             :                     // **  |           * |
     683             :                     //   **|          *  |
     684             :                     //     7*        *   |
     685             :                     //     --*6-----5-----
     686             :                     //         **  *
     687             :                     //           **
     688             : 
     689             :                     // As we need to scissor all triangles against the
     690             :                     // output rectangle we employ an output buffer for the
     691             :                     // resulting vertices.  the question is how large this
     692             :                     // buffer needs to be compared to the number of
     693             :                     // incoming vertices.  this buffer needs to hold at
     694             :                     // most the number of original vertices times '7'. see
     695             :                     // figure above for an example.  scissoring triangles
     696             :                     // with the cohen-sutherland line clipping algorithm
     697             :                     // as implemented here will result in a triangle fan
     698             :                     // which will be rendered as separate triangles to
     699             :                     // avoid pipeline stalls for each scissored
     700             :                     // triangle. creating separate triangles from a
     701             :                     // triangle fan produces (n-2)*3 vertices where n is
     702             :                     // the number of vertices of the original triangle
     703             :                     // fan.  for the maximum number of 7 vertices of
     704             :                     // resulting triangle fans we therefore need 15 times
     705             :                     // the number of original vertices.
     706             : 
     707             :                     //const size_t nBufferSize = sizeof(vertex)*(nVertexCount*16);
     708             :                     //vertex *pVertices = (vertex*)alloca(nBufferSize);
     709             :                     //sal_uInt32 nNumOutput = 0;
     710             : 
     711             :                     // we need to clip this triangle against the output rectangle
     712             :                     // to ensure that the resulting texture coordinates are in
     713             :                     // the valid range from [0<=st<=1]. under normal circustances
     714             :                     // we could use the BORDERCOLOR renderstate but some cards
     715             :                     // seem to ignore this feature.
     716           0 :                     ::basegfx::B2DPoint stack[3];
     717           0 :                     unsigned int clipflag = 0;
     718             : 
     719           0 :                     for(sal_uInt32 nIndex=0; nIndex<nVertexCount; ++nIndex)
     720             :                     {
     721             :                         // rotate stack
     722           0 :                         stack[0] = stack[1];
     723           0 :                         stack[1] = stack[2];
     724           0 :                         stack[2] = rCandidate.getB2DPoint(nIndex);
     725             : 
     726             :                         // clipping judgement
     727           0 :                         clipflag |= unsigned(!(rRange.isInside(stack[2])));
     728             : 
     729           0 :                         if(nIndex > 1)
     730             :                         {
     731             :                             // consume vertices until a single separate triangle has been visited.
     732           0 :                             if(!((nIndex+1)%3))
     733             :                             {
     734             :                                 // if any of the last three vertices was outside
     735             :                                 // we need to scissor against the destination rectangle
     736           0 :                                 if(clipflag & 7)
     737             :                                 {
     738           0 :                                     ::basegfx::B2DPoint buf0[16];
     739           0 :                                     ::basegfx::B2DPoint buf1[16];
     740             : 
     741           0 :                                     sal_uInt32 vertex_count = 3;
     742             : 
     743             :                                     // clip against all 4 planes passing the result of
     744             :                                     // each plane as the input to the next using a double buffer
     745           0 :                                     vertex_count = scissorLineSegment(stack,vertex_count,buf1,&sp[0],rRange);
     746           0 :                                     vertex_count = scissorLineSegment(buf1,vertex_count,buf0,&sp[1],rRange);
     747           0 :                                     vertex_count = scissorLineSegment(buf0,vertex_count,buf1,&sp[2],rRange);
     748           0 :                                     vertex_count = scissorLineSegment(buf1,vertex_count,buf0,&sp[3],rRange);
     749             : 
     750           0 :                                     if(vertex_count >= 3)
     751             :                                     {
     752             :                                         // convert triangle fan back to triangle list.
     753           0 :                                         ::basegfx::B2DPoint v0(buf0[0]);
     754           0 :                                         ::basegfx::B2DPoint v1(buf0[1]);
     755           0 :                                         for(sal_uInt32 i=2; i<vertex_count; ++i)
     756             :                                         {
     757           0 :                                             ::basegfx::B2DPoint v2(buf0[i]);
     758           0 :                                             aResult.append(v0);
     759           0 :                                             aResult.append(v1);
     760           0 :                                             aResult.append(v2);
     761           0 :                                             v1 = v2;
     762           0 :                                         }
     763           0 :                                     }
     764             :                                 }
     765             :                                 else
     766             :                                 {
     767             :                                     // the last triangle has not been altered, simply copy to result
     768           0 :                                     for(sal_uInt32 i=0; i<3; ++i)
     769           0 :                                         aResult.append(stack[i]);
     770             :                                 }
     771             :                             }
     772             :                         }
     773             : 
     774           0 :                         clipflag <<= 1;
     775           0 :                     }
     776             :                 }
     777             :             }
     778             : 
     779           0 :             return aResult;
     780             :         }
     781             : 
     782             : 
     783             : 
     784             :     } // end of namespace tools
     785             : } // end of namespace basegfx
     786             : 
     787             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10