chart2/source/view/main/Clipping.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: Clipping.cxx,v $
  10  * $Revision: 1.9 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31
  32 // MARKER(update_precomp.py): autogen include statement, do not remove
  33 #include "precompiled_chart2.hxx"
  34
  35 #include "Clipping.hxx"
  36 #include "CommonConverters.hxx"
  37 #include "BaseGFXHelper.hxx"
  38
  39 #include <com/sun/star/drawing/Position3D.hpp>
  40 #include <com/sun/star/drawing/DoubleSequence.hpp>
  41
  42 //.............................................................................
  43 namespace chart
  44 {
  45 //.............................................................................
  46 using namespace ::com::sun::star;
  47 using ::basegfx::B2DRectangle;
  48 using ::basegfx::B2DTuple;
  49
  50 //-----------------------------------------------------------------------------
  51 //-----------------------------------------------------------------------------
  52 //-----------------------------------------------------------------------------
  53
  54 namespace{
  55 /**     @descr  This is a supporting function for lcl_clip2d.  It computes a new parametric
  56             value for an entering (dTE) or leaving (dTL) intersection point with one
  57             of the edges bounding the clipping area.
  58             For explanation of the parameters please refer to :
  59
  60             Liang-Biarsky parametric line-clipping algorithm as described in:
  61             Computer Graphics: principles and practice, 2nd ed.,
  62             James D. Foley et al.,
  63             Section 3.12.4 on page 117.
  64 */
  65 bool lcl_CLIPt(double fDenom,double fNum, double & fTE, double & fTL)
  66 {
  67     double      fT;
  68
  69     if (fDenom > 0)                             //      Intersection enters: PE
  70     {
  71         fT = fNum / fDenom;             //      Parametric value at the intersection.
  72         if (fT > fTL)                   //      fTE and fTL crossover
  73             return false;               //        therefore reject the line.
  74         else if (fT > fTE)              //      A new fTE has been found.
  75             fTE = fT;
  76     }
  77     else if (fDenom < 0)                //      Intersection leaves: PL
  78     {
  79         fT = fNum / fDenom;             //      Parametric Value at the intersection.
  80         if (fT < fTE)                   //      fTE and fTL crossover
  81             return false;               //        therefore reject the line.
  82         else if (fT < fTL)              //      A new fTL has been found.
  83             fTL = fT;
  84     }
  85     else if (fNum > 0)
  86         return false;                   //      Line lies on the outside of the edge.
  87
  88     return true;
  89 }
  90
  91 /**     @descr  The line given by it's two endpoints rP0 and rP1 is clipped at the rectangle
  92             rRectangle.  If there is at least a part of it visible then TRUE is returned and
  93             the endpoints of that part are stored in rP0 and rP1.  The points rP0 and rP1
  94             may have the same coordinates.
  95         @param  rP0 Start point of the line to clip.  Modified to contain a start point inside
  96             the clipping area if possible.
  97         @param  rP1 End point of the line to clip.  Modified to contain an end point inside
  98             the clipping area if possible.
  99         @param  rRectangle Clipping area.
 100         @return If the line lies completely or partly inside the clipping area then TRUE
 101             is returned.  If the line lies completely outside then FALSE is returned and rP0 and
 102             rP1 are left unmodified.
 103 */
 104 bool lcl_clip2d(B2DTuple& rPoint0, B2DTuple& rPoint1, const B2DRectangle& rRectangle)
 105 {
 106     //Direction vector of the line.
 107     B2DTuple aDirection = rPoint1 - rPoint0;
 108
 109     if( aDirection.getX()==0 && aDirection.getY()==0 && rRectangle.isInside(rPoint0) )
 110     {
 111         //      Degenerate case of a zero length line.
 112         return true;
 113     }
 114     else
 115     {
 116         //      Values of the line parameter where the line enters resp. leaves the rectangle.
 117         double fTE = 0,
 118                fTL = 1;
 119
 120         //      Test wether at least a part lies in the four half-planes with respect to
 121         //      the rectangles four edges.
 122         if( lcl_CLIPt(aDirection.getX(), rRectangle.getMinX() - rPoint0.getX(), fTE, fTL) )
 123             if( lcl_CLIPt(-aDirection.getX(), rPoint0.getX() - rRectangle.getMaxX(), fTE, fTL) )
 124                 if( lcl_CLIPt(aDirection.getY(), rRectangle.getMinY() - rPoint0.getY(), fTE, fTL) )
 125                     if( lcl_CLIPt(-aDirection.getY(), rPoint0.getY() - rRectangle.getMaxY(), fTE, fTL) )
 126                     {
 127                         //      At least a part is visible.
 128                         if (fTL < 1)
 129                         {
 130                             //  Compute the new end point.
 131                             rPoint1.setX( rPoint0.getX() + fTL * aDirection.getX() );
 132                             rPoint1.setY( rPoint0.getY() + fTL * aDirection.getY() );
 133                         }
 134                         if (fTE > 0)
 135                         {
 136                             //  Compute the new starting point.
 137                             rPoint0.setX( rPoint0.getX() + fTE * aDirection.getX() );
 138                             rPoint0.setY( rPoint0.getY() + fTE * aDirection.getY() );
 139                         }
 140                         return true;
 141                     }
 142
 143         //      Line is not visible.
 144         return false;
 145     }
 146 }
 147
 148 bool lcl_clip2d_(drawing::Position3D& rPoint0, drawing::Position3D& rPoint1, const B2DRectangle& rRectangle)
 149 {
 150     B2DTuple aP0(rPoint0.PositionX,rPoint0.PositionY);
 151     B2DTuple aP1(rPoint1.PositionX,rPoint1.PositionY);
 152     bool bRet = lcl_clip2d( aP0, aP1, rRectangle );
 153
 154     rPoint0.PositionX = aP0.getX();
 155     rPoint0.PositionY = aP0.getY();
 156     rPoint1.PositionX = aP1.getX();
 157     rPoint1.PositionY = aP1.getY();
 158
 159     return bRet;
 160 }
 161
 162 void lcl_addPointToPoly( drawing::PolyPolygonShape3D& rPoly
 163         , const drawing::Position3D& rPos
 164         , sal_Int32 nPolygonIndex
 165         , std::vector< sal_Int32 >& rResultPointCount
 166         , sal_Int32 nReservePointCount )
 167 {
 168     if(nPolygonIndex<0)
 169     {
 170         OSL_ENSURE( false, "The polygon index needs to be > 0");
 171         nPolygonIndex=0;
 172     }
 173
 174     //make sure that we have enough polygons
 175     if(nPolygonIndex >= rPoly.SequenceX.getLength() )
 176     {
 177         rPoly.SequenceX.realloc(nPolygonIndex+1);
 178         rPoly.SequenceY.realloc(nPolygonIndex+1);
 179         rPoly.SequenceZ.realloc(nPolygonIndex+1);
 180         rResultPointCount.resize(nPolygonIndex+1,0);
 181     }
 182
 183     drawing::DoubleSequence* pOuterSequenceX = &rPoly.SequenceX.getArray()[nPolygonIndex];
 184     drawing::DoubleSequence* pOuterSequenceY = &rPoly.SequenceY.getArray()[nPolygonIndex];
 185     drawing::DoubleSequence* pOuterSequenceZ = &rPoly.SequenceZ.getArray()[nPolygonIndex];
 186
 187     sal_Int32 nNewResultPointCount = rResultPointCount[nPolygonIndex]+1;
 188     sal_Int32 nSeqLength = pOuterSequenceX->getLength();
 189
 190     if( nSeqLength <= nNewResultPointCount )
 191     {
 192         sal_Int32 nReallocLength = nReservePointCount;
 193         if( nNewResultPointCount > nReallocLength )
 194         {
 195             nReallocLength = nNewResultPointCount;
 196             DBG_ERROR("this should not be the case to avoid performance problems");
 197         }
 198         pOuterSequenceX->realloc(nReallocLength);
 199         pOuterSequenceY->realloc(nReallocLength);
 200         pOuterSequenceZ->realloc(nReallocLength);
 201     }
 202
 203     double* pInnerSequenceX = pOuterSequenceX->getArray();
 204     double* pInnerSequenceY = pOuterSequenceY->getArray();
 205     double* pInnerSequenceZ = pOuterSequenceZ->getArray();
 206
 207     pInnerSequenceX[nNewResultPointCount-1] = rPos.PositionX;
 208     pInnerSequenceY[nNewResultPointCount-1] = rPos.PositionY;
 209     pInnerSequenceZ[nNewResultPointCount-1] = rPos.PositionZ;
 210     rResultPointCount[nPolygonIndex]=nNewResultPointCount;
 211 }
 212
 213 }//end anonymous namespace
 214
 215 void Clipping::clipPolygonAtRectangle( const drawing::PolyPolygonShape3D& rPolygon
 216                                       , const B2DRectangle& rRectangle
 217                                       , drawing::PolyPolygonShape3D& aResult
 218                                       , bool bSplitPiecesToDifferentPolygons )
 219 {
 220     aResult.SequenceX.realloc(0);
 221     aResult.SequenceY.realloc(0);
 222     aResult.SequenceZ.realloc(0);
 223
 224     if(!rPolygon.SequenceX.getLength())
 225         return;
 226
 227     //need clipping?:
 228     {
 229         ::basegfx::B3DRange a3DRange( BaseGFXHelper::getBoundVolume( rPolygon ) );
 230         ::basegfx::B2DRange a2DRange( a3DRange.getMinX(), a3DRange.getMinY(), a3DRange.getMaxX(), a3DRange.getMaxY() );
 231         if( rRectangle.isInside( a2DRange ) )
 232         {
 233             aResult = rPolygon;
 234             return;
 235         }
 236         else
 237         {
 238             a2DRange.intersect( rRectangle );
 239             if( a2DRange.isEmpty() )
 240                 return;
 241         }
 242     }
 243
 244     //
 245     std::vector< sal_Int32 > aResultPointCount;//per polygon index
 246
 247     //apply clipping:
 248     drawing::Position3D aFrom;
 249     drawing::Position3D aTo;
 250
 251     sal_Int32 nNewPolyIndex = 0;
 252     sal_Int32 nOldPolyCount = rPolygon.SequenceX.getLength();
 253     for(sal_Int32 nOldPolyIndex=0; nOldPolyIndex<nOldPolyCount; nOldPolyIndex++, nNewPolyIndex++ )
 254     {
 255         sal_Int32 nOldPointCount = rPolygon.SequenceX[nOldPolyIndex].getLength();
 256
 257         // set last point to a position outside the rectangle, such that the first
 258         // time lcl_clip2d returns true, the comparison to last will always yield false
 259         drawing::Position3D aLast(rRectangle.getMinX()-1.0,rRectangle.getMinY()-1.0, 0.0 );
 260
 261         for(sal_Int32 nOldPoint=1; nOldPoint<nOldPointCount; nOldPoint++)
 262         {
 263             aFrom = getPointFromPoly(rPolygon,nOldPoint-1,nOldPolyIndex);
 264             aTo = getPointFromPoly(rPolygon,nOldPoint,nOldPolyIndex);
 265             if( lcl_clip2d_(aFrom, aTo, rRectangle) )
 266             {
 267                 // compose an Polygon of as many consecutive points as possible
 268                 if(aFrom == aLast)
 269                 {
 270                     if( !(aTo==aFrom) )
 271                     {
 272                         lcl_addPointToPoly( aResult, aTo, nNewPolyIndex, aResultPointCount, nOldPointCount );
 273                     }
 274                 }
 275                 else
 276                 {
 277                     if( bSplitPiecesToDifferentPolygons && nOldPoint!=1 )
 278                     {
 279                         if( nNewPolyIndex < aResult.SequenceX.getLength()
 280                                 && aResultPointCount[nNewPolyIndex]>0 )
 281                             nNewPolyIndex++;
 282                     }
 283                     lcl_addPointToPoly( aResult, aFrom, nNewPolyIndex, aResultPointCount, nOldPointCount );
 284                     if( !(aTo==aFrom) )
 285                         lcl_addPointToPoly( aResult, aTo, nNewPolyIndex, aResultPointCount, nOldPointCount );
 286                 }
 287                 aLast = aTo;
 288             }
 289         }
 290     }
 291     //free unused space
 292     for( sal_Int32 nPolygonIndex = aResultPointCount.size(); nPolygonIndex--; )
 293     {
 294         drawing::DoubleSequence* pOuterSequenceX = &aResult.SequenceX.getArray()[nPolygonIndex];
 295         drawing::DoubleSequence* pOuterSequenceY = &aResult.SequenceY.getArray()[nPolygonIndex];
 296         drawing::DoubleSequence* pOuterSequenceZ = &aResult.SequenceZ.getArray()[nPolygonIndex];
 297
 298         sal_Int32 nUsedPointCount = aResultPointCount[nPolygonIndex];
 299         pOuterSequenceX->realloc(nUsedPointCount);
 300         pOuterSequenceY->realloc(nUsedPointCount);
 301         pOuterSequenceZ->realloc(nUsedPointCount);
 302     }
 303 }
 304
 305 //.............................................................................
 306 } //namespace chart
 307 //.............................................................................