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 its 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 unsigned int round_up_nearest_pow2(unsigned int v)
 144 {
 145     // compute the next highest power of 2 of 32-bit v
 146     --v;
 147     v |= v >> 1;
 148     v |= v >> 2;
 149     v |= v >> 4;
 150     v |= v >> 8;
 151     v |= v >> 16;
 152     ++v;
 153     return v;
 154 }
 155
 156 void lcl_addPointToPoly( drawing::PolyPolygonShape3D& rPoly
 157         , const drawing::Position3D& rPos
 158         , sal_Int32 nPolygonIndex
 159         , std::vector< sal_Int32 >& rResultPointCount
 160         , sal_Int32 nReservePointCount )
 161 {
 162     if(nPolygonIndex<0)
 163     {
 164         OSL_FAIL( "The polygon index needs to be > 0");
 165         nPolygonIndex=0;
 166     }
 167
 168     //make sure that we have enough polygons
 169     if(nPolygonIndex >= rPoly.SequenceX.getLength() )
 170     {
 171         rPoly.SequenceX.realloc(nPolygonIndex+1);
 172         rPoly.SequenceY.realloc(nPolygonIndex+1);
 173         rPoly.SequenceZ.realloc(nPolygonIndex+1);
 174         rResultPointCount.resize(nPolygonIndex+1,0);
 175     }
 176
 177     drawing::DoubleSequence* pOuterSequenceX = &rPoly.SequenceX.getArray()[nPolygonIndex];
 178     drawing::DoubleSequence* pOuterSequenceY = &rPoly.SequenceY.getArray()[nPolygonIndex];
 179     drawing::DoubleSequence* pOuterSequenceZ = &rPoly.SequenceZ.getArray()[nPolygonIndex];
 180
 181     sal_Int32 nNewResultPointCount = rResultPointCount[nPolygonIndex]+1;
 182     sal_Int32 nSeqLength = pOuterSequenceX->getLength();
 183
 184     if( nSeqLength <= nNewResultPointCount )
 185     {
 186         sal_Int32 nReallocLength = nReservePointCount > SAL_MAX_INT16 ? round_up_nearest_pow2(nNewResultPointCount) * 2 : nReservePointCount;
 187         if( nNewResultPointCount > nReallocLength )
 188         {
 189             nReallocLength = nNewResultPointCount;
 190             OSL_FAIL("this should not be the case to avoid performance problems");
 191         }
 192         pOuterSequenceX->realloc(nReallocLength);
 193         pOuterSequenceY->realloc(nReallocLength);
 194         pOuterSequenceZ->realloc(nReallocLength);
 195     }
 196
 197     double* pInnerSequenceX = pOuterSequenceX->getArray();
 198     double* pInnerSequenceY = pOuterSequenceY->getArray();
 199     double* pInnerSequenceZ = pOuterSequenceZ->getArray();
 200
 201     pInnerSequenceX[nNewResultPointCount-1] = rPos.PositionX;
 202     pInnerSequenceY[nNewResultPointCount-1] = rPos.PositionY;
 203     pInnerSequenceZ[nNewResultPointCount-1] = rPos.PositionZ;
 204     rResultPointCount[nPolygonIndex]=nNewResultPointCount;
 205 }
 206
 207 }//end anonymous namespace
 208
 209 void Clipping::clipPolygonAtRectangle( const drawing::PolyPolygonShape3D& rPolygon
 210                                       , const B2DRectangle& rRectangle
 211                                       , drawing::PolyPolygonShape3D& aResult
 212                                       , bool bSplitPiecesToDifferentPolygons )
 213 {
 214     aResult.SequenceX.realloc(0);
 215     aResult.SequenceY.realloc(0);
 216     aResult.SequenceZ.realloc(0);
 217
 218     if(!rPolygon.SequenceX.hasElements())
 219         return;
 220
 221     //need clipping?:
 222     {
 223         ::basegfx::B3DRange a3DRange( BaseGFXHelper::getBoundVolume( rPolygon ) );
 224         ::basegfx::B2DRange a2DRange( a3DRange.getMinX(), a3DRange.getMinY(), a3DRange.getMaxX(), a3DRange.getMaxY() );
 225         if( rRectangle.isInside( a2DRange ) )
 226         {
 227             aResult = rPolygon;
 228             return;
 229         }
 230         else
 231         {
 232             a2DRange.intersect( rRectangle );
 233             if( a2DRange.isEmpty() )
 234                 return;
 235         }
 236     }
 237
 238     std::vector< sal_Int32 > aResultPointCount;//per polygon index
 239
 240     //apply clipping:
 241     drawing::Position3D aFrom;
 242     drawing::Position3D aTo;
 243
 244     sal_Int32 nNewPolyIndex = 0;
 245     sal_Int32 nOldPolyCount = rPolygon.SequenceX.getLength();
 246     for(sal_Int32 nOldPolyIndex=0; nOldPolyIndex<nOldPolyCount; nOldPolyIndex++, nNewPolyIndex++ )
 247     {
 248         sal_Int32 nOldPointCount = rPolygon.SequenceX[nOldPolyIndex].getLength();
 249
 250         // set last point to a position outside the rectangle, such that the first
 251         // time lcl_clip2d returns true, the comparison to last will always yield false
 252         drawing::Position3D aLast(rRectangle.getMinX()-1.0,rRectangle.getMinY()-1.0, 0.0 );
 253
 254         for(sal_Int32 nOldPoint=1; nOldPoint<nOldPointCount; nOldPoint++)
 255         {
 256             aFrom = getPointFromPoly(rPolygon,nOldPoint-1,nOldPolyIndex);
 257             aTo = getPointFromPoly(rPolygon,nOldPoint,nOldPolyIndex);
 258             if( lcl_clip2d_(aFrom, aTo, rRectangle) )
 259             {
 260                 // compose a Polygon of as many consecutive points as possible
 261                 if(aFrom == aLast)
 262                 {
 263                     if( aTo != aFrom )
 264                     {
 265                         lcl_addPointToPoly( aResult, aTo, nNewPolyIndex, aResultPointCount, nOldPointCount );
 266                     }
 267                 }
 268                 else
 269                 {
 270                     if( bSplitPiecesToDifferentPolygons && nOldPoint!=1 )
 271                     {
 272                         if( nNewPolyIndex < aResult.SequenceX.getLength()
 273                                 && aResultPointCount[nNewPolyIndex]>0 )
 274                             nNewPolyIndex++;
 275                     }
 276                     lcl_addPointToPoly( aResult, aFrom, nNewPolyIndex, aResultPointCount, nOldPointCount );
 277                     if( aTo != aFrom )
 278                         lcl_addPointToPoly( aResult, aTo, nNewPolyIndex, aResultPointCount, nOldPointCount );
 279                 }
 280                 aLast = aTo;
 281             }
 282         }
 283     }
 284     //free unused space
 285     for( sal_Int32 nPolygonIndex = aResultPointCount.size(); nPolygonIndex--; )
 286     {
 287         drawing::DoubleSequence* pOuterSequenceX = &aResult.SequenceX.getArray()[nPolygonIndex];
 288         drawing::DoubleSequence* pOuterSequenceY = &aResult.SequenceY.getArray()[nPolygonIndex];
 289         drawing::DoubleSequence* pOuterSequenceZ = &aResult.SequenceZ.getArray()[nPolygonIndex];
 290
 291         sal_Int32 nUsedPointCount = aResultPointCount[nPolygonIndex];
 292         pOuterSequenceX->realloc(nUsedPointCount);
 293         pOuterSequenceY->realloc(nUsedPointCount);
 294         pOuterSequenceZ->realloc(nUsedPointCount);
 295     }
 296 }
 297
 298 } //namespace chart
 299
 300 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */