chart2/source/view/main/Clipping.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 "Clipping.hxx"
  21 #include "CommonConverters.hxx"
  22 #include "BaseGFXHelper.hxx"
  23
  24 #include <osl/diagnose.h>
  25
  26 #include <com/sun/star/drawing/Position3D.hpp>
  27 #include <com/sun/star/drawing/DoubleSequence.hpp>
  28
  29 namespace chart
  30 {
  31 using namespace ::com::sun::star;
  32 using ::basegfx::B2DRectangle;
  33 using ::basegfx::B2DTuple;
  34
  35 namespace{
  36 /** @descr  This is a supporting function for lcl_clip2d.  It computes a new parametric
  37             value for an entering (dTE) or leaving (dTL) intersection point with one
  38             of the edges bounding the clipping area.
  39             For explanation of the parameters please refer to :
  40
  41             Liang-Biarsky parametric line-clipping algorithm as described in:
  42             Computer Graphics: principles and practice, 2nd ed.,
  43             James D. Foley et al.,
  44             Section 3.12.4 on page 117.
  45 */
  46 bool lcl_CLIPt(double fDenom,double fNum, double & fTE, double & fTL)
  47 {
  48     double  fT;
  49
  50     if (fDenom > 0)             //  Intersection enters: PE
  51     {
  52         fT = fNum / fDenom;     //  Parametric value at the intersection.
  53         if (fT > fTL)           //  fTE and fTL crossover
  54             return false;       //    therefore reject the line.
  55         else if (fT > fTE)      //  A new fTE has been found.
  56             fTE = fT;
  57     }
  58     else if (fDenom < 0)        //  Intersection leaves: PL
  59     {
  60         fT = fNum / fDenom;     //  Parametric Value at the intersection.
  61         if (fT < fTE)           //  fTE and fTL crossover
  62             return false;       //    therefore reject the line.
  63         else if (fT < fTL)      //  A new fTL has been found.
  64             fTL = fT;
  65     }
  66     else if (fNum > 0)
  67         return false;           //  Line lies on the outside of the edge.
  68
  69     return true;
  70 }
  71
  72 /** @descr  The line given by it's two endpoints rP0 and rP1 is clipped at the rectangle
  73             rRectangle.  If there is at least a part of it visible then sal_True is returned and
  74             the endpoints of that part are stored in rP0 and rP1.  The points rP0 and rP1
  75             may have the same coordinates.
  76         @param  rP0 Start point of the line to clip.  Modified to contain a start point inside
  77             the clipping area if possible.
  78         @param  rP1 End point of the line to clip.  Modified to contain an end point inside
  79             the clipping area if possible.
  80         @param  rRectangle Clipping area.
  81         @return If the line lies completely or partly inside the clipping area then TRUE
  82             is returned.  If the line lies completely outside then sal_False is returned and rP0 and
  83             rP1 are left unmodified.
  84 */
  85 bool lcl_clip2d(B2DTuple& rPoint0, B2DTuple& rPoint1, const B2DRectangle& rRectangle)
  86 {
  87     //Direction vector of the line.
  88     B2DTuple aDirection = rPoint1 - rPoint0;
  89
  90     if( aDirection.getX()==0 && aDirection.getY()==0 && rRectangle.isInside(rPoint0) )
  91     {
  92         //  Degenerate case of a zero length line.
  93         return true;
  94     }
  95     else
  96     {
  97         //  Values of the line parameter where the line enters resp. leaves the rectangle.
  98         double fTE = 0,
  99                fTL = 1;
 100
 101         //  Test whether at least a part lies in the four half-planes with respect to
 102         //  the rectangles four edges.
 103         if( lcl_CLIPt(aDirection.getX(), rRectangle.getMinX() - rPoint0.getX(), fTE, fTL) )
 104             if( lcl_CLIPt(-aDirection.getX(), rPoint0.getX() - rRectangle.getMaxX(), fTE, fTL) )
 105                 if( lcl_CLIPt(aDirection.getY(), rRectangle.getMinY() - rPoint0.getY(), fTE, fTL) )
 106                     if( lcl_CLIPt(-aDirection.getY(), rPoint0.getY() - rRectangle.getMaxY(), fTE, fTL) )
 107                     {
 108                         //  At least a part is visible.
 109                         if (fTL < 1)
 110                         {
 111                             //  Compute the new end point.
 112                             rPoint1.setX( rPoint0.getX() + fTL * aDirection.getX() );
 113                             rPoint1.setY( rPoint0.getY() + fTL * aDirection.getY() );
 114                         }
 115                         if (fTE > 0)
 116                         {
 117                             //  Compute the new starting point.
 118                             rPoint0.setX( rPoint0.getX() + fTE * aDirection.getX() );
 119                             rPoint0.setY( rPoint0.getY() + fTE * aDirection.getY() );
 120                         }
 121                         return true;
 122                     }
 123
 124         //  Line is not visible.
 125         return false;
 126     }
 127 }
 128
 129 bool lcl_clip2d_(drawing::Position3D& rPoint0, drawing::Position3D& rPoint1, const B2DRectangle& rRectangle)
 130 {
 131     B2DTuple aP0(rPoint0.PositionX,rPoint0.PositionY);
 132     B2DTuple aP1(rPoint1.PositionX,rPoint1.PositionY);
 133     bool bRet = lcl_clip2d( aP0, aP1, rRectangle );
 134
 135     rPoint0.PositionX = aP0.getX();
 136     rPoint0.PositionY = aP0.getY();
 137     rPoint1.PositionX = aP1.getX();
 138     rPoint1.PositionY = aP1.getY();
 139
 140     return bRet;
 141 }
 142
 143 void lcl_addPointToPoly( drawing::PolyPolygonShape3D& rPoly
 144         , const drawing::Position3D& rPos
 145         , sal_Int32 nPolygonIndex
 146         , std::vector< sal_Int32 >& rResultPointCount
 147         , sal_Int32 nReservePointCount )
 148 {
 149     if(nPolygonIndex<0)
 150     {
 151         OSL_FAIL( "The polygon index needs to be > 0");
 152         nPolygonIndex=0;
 153     }
 154
 155     //make sure that we have enough polygons
 156     if(nPolygonIndex >= rPoly.SequenceX.getLength() )
 157     {
 158         rPoly.SequenceX.realloc(nPolygonIndex+1);
 159         rPoly.SequenceY.realloc(nPolygonIndex+1);
 160         rPoly.SequenceZ.realloc(nPolygonIndex+1);
 161         rResultPointCount.resize(nPolygonIndex+1,0);
 162     }
 163
 164     drawing::DoubleSequence* pOuterSequenceX = &rPoly.SequenceX.getArray()[nPolygonIndex];
 165     drawing::DoubleSequence* pOuterSequenceY = &rPoly.SequenceY.getArray()[nPolygonIndex];
 166     drawing::DoubleSequence* pOuterSequenceZ = &rPoly.SequenceZ.getArray()[nPolygonIndex];
 167
 168     sal_Int32 nNewResultPointCount = rResultPointCount[nPolygonIndex]+1;
 169     sal_Int32 nSeqLength = pOuterSequenceX->getLength();
 170
 171     if( nSeqLength <= nNewResultPointCount )
 172     {
 173         sal_Int32 nReallocLength = nReservePointCount;
 174         if( nNewResultPointCount > nReallocLength )
 175         {
 176             nReallocLength = nNewResultPointCount;
 177             OSL_FAIL("this should not be the case to avoid performance problems");
 178         }
 179         pOuterSequenceX->realloc(nReallocLength);
 180         pOuterSequenceY->realloc(nReallocLength);
 181         pOuterSequenceZ->realloc(nReallocLength);
 182     }
 183
 184     double* pInnerSequenceX = pOuterSequenceX->getArray();
 185     double* pInnerSequenceY = pOuterSequenceY->getArray();
 186     double* pInnerSequenceZ = pOuterSequenceZ->getArray();
 187
 188     pInnerSequenceX[nNewResultPointCount-1] = rPos.PositionX;
 189     pInnerSequenceY[nNewResultPointCount-1] = rPos.PositionY;
 190     pInnerSequenceZ[nNewResultPointCount-1] = rPos.PositionZ;
 191     rResultPointCount[nPolygonIndex]=nNewResultPointCount;
 192 }
 193
 194 }//end anonymous namespace
 195
 196 void Clipping::clipPolygonAtRectangle( const drawing::PolyPolygonShape3D& rPolygon
 197                                       , const B2DRectangle& rRectangle
 198                                       , drawing::PolyPolygonShape3D& aResult
 199                                       , bool bSplitPiecesToDifferentPolygons )
 200 {
 201     aResult.SequenceX.realloc(0);
 202     aResult.SequenceY.realloc(0);
 203     aResult.SequenceZ.realloc(0);
 204
 205     if(!rPolygon.SequenceX.getLength())
 206         return;
 207
 208     //need clipping?:
 209     {
 210         ::basegfx::B3DRange a3DRange( BaseGFXHelper::getBoundVolume( rPolygon ) );
 211         ::basegfx::B2DRange a2DRange( a3DRange.getMinX(), a3DRange.getMinY(), a3DRange.getMaxX(), a3DRange.getMaxY() );
 212         if( rRectangle.isInside( a2DRange ) )
 213         {
 214             aResult = rPolygon;
 215             return;
 216         }
 217         else
 218         {
 219             a2DRange.intersect( rRectangle );
 220             if( a2DRange.isEmpty() )
 221                 return;
 222         }
 223     }
 224
 225     std::vector< sal_Int32 > aResultPointCount;//per polygon index
 226
 227     //apply clipping:
 228     drawing::Position3D aFrom;
 229     drawing::Position3D aTo;
 230
 231     sal_Int32 nNewPolyIndex = 0;
 232     sal_Int32 nOldPolyCount = rPolygon.SequenceX.getLength();
 233     for(sal_Int32 nOldPolyIndex=0; nOldPolyIndex<nOldPolyCount; nOldPolyIndex++, nNewPolyIndex++ )
 234     {
 235         sal_Int32 nOldPointCount = rPolygon.SequenceX[nOldPolyIndex].getLength();
 236
 237         // set last point to a position outside the rectangle, such that the first
 238         // time lcl_clip2d returns true, the comparison to last will always yield false
 239         drawing::Position3D aLast(rRectangle.getMinX()-1.0,rRectangle.getMinY()-1.0, 0.0 );
 240
 241         for(sal_Int32 nOldPoint=1; nOldPoint<nOldPointCount; nOldPoint++)
 242         {
 243             aFrom = getPointFromPoly(rPolygon,nOldPoint-1,nOldPolyIndex);
 244             aTo = getPointFromPoly(rPolygon,nOldPoint,nOldPolyIndex);
 245             if( lcl_clip2d_(aFrom, aTo, rRectangle) )
 246             {
 247                 // compose an Polygon of as many consecutive points as possible
 248                 if(aFrom == aLast)
 249                 {
 250                     if( !(aTo==aFrom) )
 251                     {
 252                         lcl_addPointToPoly( aResult, aTo, nNewPolyIndex, aResultPointCount, nOldPointCount );
 253                     }
 254                 }
 255                 else
 256                 {
 257                     if( bSplitPiecesToDifferentPolygons && nOldPoint!=1 )
 258                     {
 259                         if( nNewPolyIndex < aResult.SequenceX.getLength()
 260                                 && aResultPointCount[nNewPolyIndex]>0 )
 261                             nNewPolyIndex++;
 262                     }
 263                     lcl_addPointToPoly( aResult, aFrom, nNewPolyIndex, aResultPointCount, nOldPointCount );
 264                     if( !(aTo==aFrom) )
 265                         lcl_addPointToPoly( aResult, aTo, nNewPolyIndex, aResultPointCount, nOldPointCount );
 266                 }
 267                 aLast = aTo;
 268             }
 269         }
 270     }
 271     //free unused space
 272     for( sal_Int32 nPolygonIndex = aResultPointCount.size(); nPolygonIndex--; )
 273     {
 274         drawing::DoubleSequence* pOuterSequenceX = &aResult.SequenceX.getArray()[nPolygonIndex];
 275         drawing::DoubleSequence* pOuterSequenceY = &aResult.SequenceY.getArray()[nPolygonIndex];
 276         drawing::DoubleSequence* pOuterSequenceZ = &aResult.SequenceZ.getArray()[nPolygonIndex];
 277
 278         sal_Int32 nUsedPointCount = aResultPointCount[nPolygonIndex];
 279         pOuterSequenceX->realloc(nUsedPointCount);
 280         pOuterSequenceY->realloc(nUsedPointCount);
 281         pOuterSequenceZ->realloc(nUsedPointCount);
 282     }
 283 }
 284
 285 } //namespace chart
 286
 287 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */