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 <o3tl/safeint.hxx>
  25 #include <osl/diagnose.h>
  26
  27 #include <com/sun/star/drawing/Position3D.hpp>
  28 #include <com/sun/star/drawing/DoubleSequence.hpp>
  29
  30 namespace chart
  31 {
  32 using namespace ::com::sun::star;
  33 using ::basegfx::B2DRectangle;
  34 using ::basegfx::B2DTuple;
  35
  36 namespace{
  37 /** @descr  This is a supporting function for lcl_clip2d.  It computes a new parametric
  38             value for an entering (dTE) or leaving (dTL) intersection point with one
  39             of the edges bounding the clipping area.
  40             For explanation of the parameters please refer to :
  41
  42             Liang-Biarsky parametric line-clipping algorithm as described in:
  43             Computer Graphics: principles and practice, 2nd ed.,
  44             James D. Foley et al.,
  45             Section 3.12.4 on page 117.
  46 */
  47 bool lcl_CLIPt(double fDenom,double fNum, double & fTE, double & fTL)
  48 {
  49     double  fT;
  50
  51     if (fDenom > 0)             //  Intersection enters: PE
  52     {
  53         fT = fNum / fDenom;     //  Parametric value at the intersection.
  54         if (fT > fTL)           //  fTE and fTL crossover
  55             return false;       //    therefore reject the line.
  56         else if (fT > fTE)      //  A new fTE has been found.
  57             fTE = fT;
  58     }
  59     else if (fDenom < 0)        //  Intersection leaves: PL
  60     {
  61         fT = fNum / fDenom;     //  Parametric Value at the intersection.
  62         if (fT < fTE)           //  fTE and fTL crossover
  63             return false;       //    therefore reject the line.
  64         else if (fT < fTL)      //  A new fTL has been found.
  65             fTL = fT;
  66     }
  67     else if (fNum > 0)
  68         return false;           //  Line lies on the outside of the edge.
  69
  70     return true;
  71 }
  72
  73 /** @descr  The line given by its two endpoints rP0 and rP1 is clipped at the rectangle
  74             rRectangle.  If there is at least a part of it visible then sal_True is returned and
  75             the endpoints of that part are stored in rP0 and rP1.  The points rP0 and rP1
  76             may have the same coordinates.
  77         @param  rP0 Start point of the line to clip.  Modified to contain a start point inside
  78             the clipping area if possible.
  79         @param  rP1 End point of the line to clip.  Modified to contain an end point inside
  80             the clipping area if possible.
  81         @param  rRectangle Clipping area.
  82         @return If the line lies completely or partly inside the clipping area then TRUE
  83             is returned.  If the line lies completely outside then sal_False is returned and rP0 and
  84             rP1 are left unmodified.
  85 */
  86 bool lcl_clip2d(B2DTuple& rPoint0, B2DTuple& rPoint1, const B2DRectangle& rRectangle)
  87 {
  88     //Direction vector of the line.
  89     B2DTuple aDirection = rPoint1 - rPoint0;
  90
  91     if( aDirection.getX()==0 && aDirection.getY()==0 && rRectangle.isInside(rPoint0) )
  92     {
  93         //  Degenerate case of a zero length line.
  94         return true;
  95     }
  96     else
  97     {
  98         //  Values of the line parameter where the line enters resp. leaves the rectangle.
  99         double fTE = 0,
 100                fTL = 1;
 101
 102         //  Test whether at least a part lies in the four half-planes with respect to
 103         //  the rectangles four edges.
 104         if( lcl_CLIPt(aDirection.getX(), rRectangle.getMinX() - rPoint0.getX(), fTE, fTL) )
 105             if( lcl_CLIPt(-aDirection.getX(), rPoint0.getX() - rRectangle.getMaxX(), fTE, fTL) )
 106                 if( lcl_CLIPt(aDirection.getY(), rRectangle.getMinY() - rPoint0.getY(), fTE, fTL) )
 107                     if( lcl_CLIPt(-aDirection.getY(), rPoint0.getY() - rRectangle.getMaxY(), fTE, fTL) )
 108                     {
 109                         //  At least a part is visible.
 110                         if (fTL < 1)
 111                         {
 112                             //  Compute the new end point.
 113                             rPoint1.setX( rPoint0.getX() + fTL * aDirection.getX() );
 114                             rPoint1.setY( rPoint0.getY() + fTL * aDirection.getY() );
 115                         }
 116                         if (fTE > 0)
 117                         {
 118                             //  Compute the new starting point.
 119                             rPoint0.setX( rPoint0.getX() + fTE * aDirection.getX() );
 120                             rPoint0.setY( rPoint0.getY() + fTE * aDirection.getY() );
 121                         }
 122                         return true;
 123                     }
 124
 125         //  Line is not visible.
 126         return false;
 127     }
 128 }
 129
 130 bool lcl_clip2d_(drawing::Position3D& rPoint0, drawing::Position3D& rPoint1, const B2DRectangle& rRectangle)
 131 {
 132     B2DTuple aP0(rPoint0.PositionX,rPoint0.PositionY);
 133     B2DTuple aP1(rPoint1.PositionX,rPoint1.PositionY);
 134     bool bRet = lcl_clip2d( aP0, aP1, rRectangle );
 135
 136     rPoint0.PositionX = aP0.getX();
 137     rPoint0.PositionY = aP0.getY();
 138     rPoint1.PositionX = aP1.getX();
 139     rPoint1.PositionY = aP1.getY();
 140
 141     return bRet;
 142 }
 143
 144 unsigned int round_up_nearest_pow2(unsigned int v)
 145 {
 146     // compute the next highest power of 2 of 32-bit v
 147     --v;
 148     v |= v >> 1;
 149     v |= v >> 2;
 150     v |= v >> 4;
 151     v |= v >> 8;
 152     v |= v >> 16;
 153     ++v;
 154     return v;
 155 }
 156
 157 void lcl_addPointToPoly( drawing::PolyPolygonShape3D& rPoly
 158         , const drawing::Position3D& rPos
 159         , sal_Int32 nPolygonIndex
 160         , std::vector< sal_Int32 >& rResultPointCount
 161         , sal_Int32 nReservePointCount )
 162 {
 163     if(nPolygonIndex<0)
 164     {
 165         OSL_FAIL( "The polygon index needs to be > 0");
 166         nPolygonIndex=0;
 167     }
 168
 169     //make sure that we have enough polygons
 170     if(nPolygonIndex >= rPoly.SequenceX.getLength() )
 171     {
 172         rPoly.SequenceX.realloc(nPolygonIndex+1);
 173         rPoly.SequenceY.realloc(nPolygonIndex+1);
 174         rPoly.SequenceZ.realloc(nPolygonIndex+1);
 175         rResultPointCount.resize(nPolygonIndex+1,0);
 176     }
 177
 178     drawing::DoubleSequence* pOuterSequenceX = &rPoly.SequenceX.getArray()[nPolygonIndex];
 179     drawing::DoubleSequence* pOuterSequenceY = &rPoly.SequenceY.getArray()[nPolygonIndex];
 180     drawing::DoubleSequence* pOuterSequenceZ = &rPoly.SequenceZ.getArray()[nPolygonIndex];
 181
 182     sal_Int32 nNewResultPointCount = rResultPointCount[nPolygonIndex]+1;
 183     sal_Int32 nSeqLength = pOuterSequenceX->getLength();
 184
 185     if( nSeqLength <= nNewResultPointCount )
 186     {
 187         sal_Int32 nReallocLength = nReservePointCount > SAL_MAX_INT16 ? round_up_nearest_pow2(nNewResultPointCount) * 2 : nReservePointCount;
 188         if( nNewResultPointCount > nReallocLength )
 189         {
 190             nReallocLength = nNewResultPointCount;
 191             OSL_FAIL("this should not be the case to avoid performance problems");
 192         }
 193         pOuterSequenceX->realloc(nReallocLength);
 194         pOuterSequenceY->realloc(nReallocLength);
 195         pOuterSequenceZ->realloc(nReallocLength);
 196     }
 197
 198     double* pInnerSequenceX = pOuterSequenceX->getArray();
 199     double* pInnerSequenceY = pOuterSequenceY->getArray();
 200     double* pInnerSequenceZ = pOuterSequenceZ->getArray();
 201
 202     pInnerSequenceX[nNewResultPointCount-1] = rPos.PositionX;
 203     pInnerSequenceY[nNewResultPointCount-1] = rPos.PositionY;
 204     pInnerSequenceZ[nNewResultPointCount-1] = rPos.PositionZ;
 205     rResultPointCount[nPolygonIndex]=nNewResultPointCount;
 206 }
 207
 208 void lcl_addPointToPoly( std::vector<std::vector<css::drawing::Position3D>>& rPoly
 209         , const drawing::Position3D& rPos
 210         , sal_Int32 nPolygonIndex
 211         , std::vector< sal_Int32 >& rResultPointCount
 212         , sal_Int32 nReservePointCount )
 213 {
 214     if(nPolygonIndex<0)
 215     {
 216         OSL_FAIL( "The polygon index needs to be > 0");
 217         nPolygonIndex=0;
 218     }
 219
 220     //make sure that we have enough polygons
 221     if(o3tl::make_unsigned(nPolygonIndex) >= rPoly.size() )
 222     {
 223         rPoly.resize(nPolygonIndex+1);
 224         rResultPointCount.resize(nPolygonIndex+1,0);
 225     }
 226
 227     std::vector<css::drawing::Position3D>* pOuterSequence = &rPoly[nPolygonIndex];
 228
 229     sal_Int32 nNewResultPointCount = rResultPointCount[nPolygonIndex]+1;
 230     sal_Int32 nSeqLength = pOuterSequence->size();
 231
 232     if( nSeqLength <= nNewResultPointCount )
 233     {
 234         sal_Int32 nReallocLength = nReservePointCount > SAL_MAX_INT16 ? round_up_nearest_pow2(nNewResultPointCount) * 2 : nReservePointCount;
 235         if( nNewResultPointCount > nReallocLength )
 236         {
 237             nReallocLength = nNewResultPointCount;
 238             OSL_FAIL("this should not be the case to avoid performance problems");
 239         }
 240         pOuterSequence->resize(nReallocLength);
 241     }
 242
 243     css::drawing::Position3D* pInnerSequence = pOuterSequence->data();
 244
 245     pInnerSequence[nNewResultPointCount-1] = rPos;
 246     rResultPointCount[nPolygonIndex]=nNewResultPointCount;
 247 }
 248
 249 }//end anonymous namespace
 250
 251 void Clipping::clipPolygonAtRectangle( const drawing::PolyPolygonShape3D& rPolygon
 252                                       , const B2DRectangle& rRectangle
 253                                       , drawing::PolyPolygonShape3D& aResult
 254                                       , bool bSplitPiecesToDifferentPolygons )
 255 {
 256     aResult.SequenceX.realloc(0);
 257     aResult.SequenceY.realloc(0);
 258     aResult.SequenceZ.realloc(0);
 259
 260     if(!rPolygon.SequenceX.hasElements())
 261         return;
 262
 263     //need clipping?:
 264     {
 265         ::basegfx::B3DRange a3DRange( BaseGFXHelper::getBoundVolume( rPolygon ) );
 266         ::basegfx::B2DRange a2DRange( a3DRange.getMinX(), a3DRange.getMinY(), a3DRange.getMaxX(), a3DRange.getMaxY() );
 267         if( rRectangle.isInside( a2DRange ) )
 268         {
 269             aResult = rPolygon;
 270             return;
 271         }
 272         else
 273         {
 274             a2DRange.intersect( rRectangle );
 275             if( a2DRange.isEmpty() )
 276                 return;
 277         }
 278     }
 279
 280     std::vector< sal_Int32 > aResultPointCount;//per polygon index
 281
 282     //apply clipping:
 283     drawing::Position3D aFrom;
 284     drawing::Position3D aTo;
 285
 286     sal_Int32 nNewPolyIndex = 0;
 287     sal_Int32 nOldPolyCount = rPolygon.SequenceX.getLength();
 288     for(sal_Int32 nOldPolyIndex=0; nOldPolyIndex<nOldPolyCount; nOldPolyIndex++, nNewPolyIndex++ )
 289     {
 290         sal_Int32 nOldPointCount = rPolygon.SequenceX[nOldPolyIndex].getLength();
 291
 292         // set last point to a position outside the rectangle, such that the first
 293         // time lcl_clip2d returns true, the comparison to last will always yield false
 294         drawing::Position3D aLast(rRectangle.getMinX()-1.0,rRectangle.getMinY()-1.0, 0.0 );
 295
 296         for(sal_Int32 nOldPoint=1; nOldPoint<nOldPointCount; nOldPoint++)
 297         {
 298             aFrom = getPointFromPoly(rPolygon,nOldPoint-1,nOldPolyIndex);
 299             aTo = getPointFromPoly(rPolygon,nOldPoint,nOldPolyIndex);
 300             if( lcl_clip2d_(aFrom, aTo, rRectangle) )
 301             {
 302                 // compose a Polygon of as many consecutive points as possible
 303                 if(aFrom == aLast)
 304                 {
 305                     if( aTo != aFrom )
 306                     {
 307                         lcl_addPointToPoly( aResult, aTo, nNewPolyIndex, aResultPointCount, nOldPointCount );
 308                     }
 309                 }
 310                 else
 311                 {
 312                     if( bSplitPiecesToDifferentPolygons && nOldPoint!=1 )
 313                     {
 314                         if( nNewPolyIndex < aResult.SequenceX.getLength()
 315                                 && aResultPointCount[nNewPolyIndex]>0 )
 316                             nNewPolyIndex++;
 317                     }
 318                     lcl_addPointToPoly( aResult, aFrom, nNewPolyIndex, aResultPointCount, nOldPointCount );
 319                     if( aTo != aFrom )
 320                         lcl_addPointToPoly( aResult, aTo, nNewPolyIndex, aResultPointCount, nOldPointCount );
 321                 }
 322                 aLast = aTo;
 323             }
 324         }
 325     }
 326     //free unused space
 327     for( sal_Int32 nPolygonIndex = aResultPointCount.size(); nPolygonIndex--; )
 328     {
 329         drawing::DoubleSequence* pOuterSequenceX = &aResult.SequenceX.getArray()[nPolygonIndex];
 330         drawing::DoubleSequence* pOuterSequenceY = &aResult.SequenceY.getArray()[nPolygonIndex];
 331         drawing::DoubleSequence* pOuterSequenceZ = &aResult.SequenceZ.getArray()[nPolygonIndex];
 332
 333         sal_Int32 nUsedPointCount = aResultPointCount[nPolygonIndex];
 334         pOuterSequenceX->realloc(nUsedPointCount);
 335         pOuterSequenceY->realloc(nUsedPointCount);
 336         pOuterSequenceZ->realloc(nUsedPointCount);
 337     }
 338 }
 339
 340 void Clipping::clipPolygonAtRectangle( const std::vector<std::vector<css::drawing::Position3D>>& rPolygon
 341                                       , const B2DRectangle& rRectangle
 342                                       , std::vector<std::vector<css::drawing::Position3D>>& aResult
 343                                       , bool bSplitPiecesToDifferentPolygons )
 344 {
 345     aResult.clear();
 346
 347     if(rPolygon.empty())
 348         return;
 349
 350     //need clipping?:
 351     {
 352         ::basegfx::B3DRange a3DRange( BaseGFXHelper::getBoundVolume( rPolygon ) );
 353         ::basegfx::B2DRange a2DRange( a3DRange.getMinX(), a3DRange.getMinY(), a3DRange.getMaxX(), a3DRange.getMaxY() );
 354         if( rRectangle.isInside( a2DRange ) )
 355         {
 356             aResult = rPolygon;
 357             return;
 358         }
 359         else
 360         {
 361             a2DRange.intersect( rRectangle );
 362             if( a2DRange.isEmpty() )
 363                 return;
 364         }
 365     }
 366
 367     std::vector< sal_Int32 > aResultPointCount;//per polygon index
 368
 369     //apply clipping:
 370     drawing::Position3D aFrom;
 371     drawing::Position3D aTo;
 372
 373     sal_Int32 nNewPolyIndex = 0;
 374     sal_Int32 nOldPolyCount = rPolygon.size();
 375     for(sal_Int32 nOldPolyIndex=0; nOldPolyIndex<nOldPolyCount; nOldPolyIndex++, nNewPolyIndex++ )
 376     {
 377         sal_Int32 nOldPointCount = rPolygon[nOldPolyIndex].size();
 378
 379         // set last point to a position outside the rectangle, such that the first
 380         // time lcl_clip2d returns true, the comparison to last will always yield false
 381         drawing::Position3D aLast(rRectangle.getMinX()-1.0,rRectangle.getMinY()-1.0, 0.0 );
 382
 383         for(sal_Int32 nOldPoint=1; nOldPoint<nOldPointCount; nOldPoint++)
 384         {
 385             aFrom = getPointFromPoly(rPolygon,nOldPoint-1,nOldPolyIndex);
 386             aTo = getPointFromPoly(rPolygon,nOldPoint,nOldPolyIndex);
 387             if( lcl_clip2d_(aFrom, aTo, rRectangle) )
 388             {
 389                 // compose a Polygon of as many consecutive points as possible
 390                 if(aFrom == aLast)
 391                 {
 392                     if( aTo != aFrom )
 393                     {
 394                         lcl_addPointToPoly( aResult, aTo, nNewPolyIndex, aResultPointCount, nOldPointCount );
 395                     }
 396                 }
 397                 else
 398                 {
 399                     if( bSplitPiecesToDifferentPolygons && nOldPoint!=1 )
 400                     {
 401                         if( nNewPolyIndex < static_cast<sal_Int32>(aResult.size())
 402                                 && aResultPointCount[nNewPolyIndex]>0 )
 403                             nNewPolyIndex++;
 404                     }
 405                     lcl_addPointToPoly( aResult, aFrom, nNewPolyIndex, aResultPointCount, nOldPointCount );
 406                     if( aTo != aFrom )
 407                         lcl_addPointToPoly( aResult, aTo, nNewPolyIndex, aResultPointCount, nOldPointCount );
 408                 }
 409                 aLast = aTo;
 410             }
 411         }
 412     }
 413     //free unused space
 414     for( sal_Int32 nPolygonIndex = aResultPointCount.size(); nPolygonIndex--; )
 415     {
 416         std::vector<css::drawing::Position3D>* pOuterSequence = &aResult[nPolygonIndex];
 417
 418         sal_Int32 nUsedPointCount = aResultPointCount[nPolygonIndex];
 419         pOuterSequence->resize(nUsedPointCount);
 420     }
 421 }
 422
 423 } //namespace chart
 424
 425 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */