summaryrefslogtreecommitdiffstats
path: root/chart2/source/view/main/Clipping.cxx
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 09:06:44 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 09:06:44 +0000
commited5640d8b587fbcfed7dd7967f3de04b37a76f26 (patch)
tree7a5f7c6c9d02226d7471cb3cc8fbbf631b415303 /chart2/source/view/main/Clipping.cxx
parentInitial commit. (diff)
downloadlibreoffice-upstream.tar.xz
libreoffice-upstream.zip
Adding upstream version 4:7.4.7.upstream/4%7.4.7upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'chart2/source/view/main/Clipping.cxx')
-rw-r--r--chart2/source/view/main/Clipping.cxx425
1 files changed, 425 insertions, 0 deletions
diff --git a/chart2/source/view/main/Clipping.cxx b/chart2/source/view/main/Clipping.cxx
new file mode 100644
index 000000000..713e88c26
--- /dev/null
+++ b/chart2/source/view/main/Clipping.cxx
@@ -0,0 +1,425 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed
+ * with this work for additional information regarding copyright
+ * ownership. The ASF licenses this file to you under the Apache
+ * License, Version 2.0 (the "License"); you may not use this file
+ * except in compliance with the License. You may obtain a copy of
+ * the License at http://www.apache.org/licenses/LICENSE-2.0 .
+ */
+
+#include <Clipping.hxx>
+#include <CommonConverters.hxx>
+#include <BaseGFXHelper.hxx>
+
+#include <o3tl/safeint.hxx>
+#include <osl/diagnose.h>
+
+#include <com/sun/star/drawing/Position3D.hpp>
+#include <com/sun/star/drawing/DoubleSequence.hpp>
+
+namespace chart
+{
+using namespace ::com::sun::star;
+using ::basegfx::B2DRectangle;
+using ::basegfx::B2DTuple;
+
+namespace{
+/** @descr This is a supporting function for lcl_clip2d. It computes a new parametric
+ value for an entering (dTE) or leaving (dTL) intersection point with one
+ of the edges bounding the clipping area.
+ For explanation of the parameters please refer to :
+
+ Liang-Biarsky parametric line-clipping algorithm as described in:
+ Computer Graphics: principles and practice, 2nd ed.,
+ James D. Foley et al.,
+ Section 3.12.4 on page 117.
+*/
+bool lcl_CLIPt(double fDenom,double fNum, double & fTE, double & fTL)
+{
+ double fT;
+
+ if (fDenom > 0) // Intersection enters: PE
+ {
+ fT = fNum / fDenom; // Parametric value at the intersection.
+ if (fT > fTL) // fTE and fTL crossover
+ return false; // therefore reject the line.
+ else if (fT > fTE) // A new fTE has been found.
+ fTE = fT;
+ }
+ else if (fDenom < 0) // Intersection leaves: PL
+ {
+ fT = fNum / fDenom; // Parametric Value at the intersection.
+ if (fT < fTE) // fTE and fTL crossover
+ return false; // therefore reject the line.
+ else if (fT < fTL) // A new fTL has been found.
+ fTL = fT;
+ }
+ else if (fNum > 0)
+ return false; // Line lies on the outside of the edge.
+
+ return true;
+}
+
+/** @descr The line given by its two endpoints rP0 and rP1 is clipped at the rectangle
+ rRectangle. If there is at least a part of it visible then sal_True is returned and
+ the endpoints of that part are stored in rP0 and rP1. The points rP0 and rP1
+ may have the same coordinates.
+ @param rP0 Start point of the line to clip. Modified to contain a start point inside
+ the clipping area if possible.
+ @param rP1 End point of the line to clip. Modified to contain an end point inside
+ the clipping area if possible.
+ @param rRectangle Clipping area.
+ @return If the line lies completely or partly inside the clipping area then TRUE
+ is returned. If the line lies completely outside then sal_False is returned and rP0 and
+ rP1 are left unmodified.
+*/
+bool lcl_clip2d(B2DTuple& rPoint0, B2DTuple& rPoint1, const B2DRectangle& rRectangle)
+{
+ //Direction vector of the line.
+ B2DTuple aDirection = rPoint1 - rPoint0;
+
+ if( aDirection.getX()==0 && aDirection.getY()==0 && rRectangle.isInside(rPoint0) )
+ {
+ // Degenerate case of a zero length line.
+ return true;
+ }
+ else
+ {
+ // Values of the line parameter where the line enters resp. leaves the rectangle.
+ double fTE = 0,
+ fTL = 1;
+
+ // Test whether at least a part lies in the four half-planes with respect to
+ // the rectangles four edges.
+ if( lcl_CLIPt(aDirection.getX(), rRectangle.getMinX() - rPoint0.getX(), fTE, fTL) )
+ if( lcl_CLIPt(-aDirection.getX(), rPoint0.getX() - rRectangle.getMaxX(), fTE, fTL) )
+ if( lcl_CLIPt(aDirection.getY(), rRectangle.getMinY() - rPoint0.getY(), fTE, fTL) )
+ if( lcl_CLIPt(-aDirection.getY(), rPoint0.getY() - rRectangle.getMaxY(), fTE, fTL) )
+ {
+ // At least a part is visible.
+ if (fTL < 1)
+ {
+ // Compute the new end point.
+ rPoint1.setX( rPoint0.getX() + fTL * aDirection.getX() );
+ rPoint1.setY( rPoint0.getY() + fTL * aDirection.getY() );
+ }
+ if (fTE > 0)
+ {
+ // Compute the new starting point.
+ rPoint0.setX( rPoint0.getX() + fTE * aDirection.getX() );
+ rPoint0.setY( rPoint0.getY() + fTE * aDirection.getY() );
+ }
+ return true;
+ }
+
+ // Line is not visible.
+ return false;
+ }
+}
+
+bool lcl_clip2d_(drawing::Position3D& rPoint0, drawing::Position3D& rPoint1, const B2DRectangle& rRectangle)
+{
+ B2DTuple aP0(rPoint0.PositionX,rPoint0.PositionY);
+ B2DTuple aP1(rPoint1.PositionX,rPoint1.PositionY);
+ bool bRet = lcl_clip2d( aP0, aP1, rRectangle );
+
+ rPoint0.PositionX = aP0.getX();
+ rPoint0.PositionY = aP0.getY();
+ rPoint1.PositionX = aP1.getX();
+ rPoint1.PositionY = aP1.getY();
+
+ return bRet;
+}
+
+unsigned int round_up_nearest_pow2(unsigned int v)
+{
+ // compute the next highest power of 2 of 32-bit v
+ --v;
+ v |= v >> 1;
+ v |= v >> 2;
+ v |= v >> 4;
+ v |= v >> 8;
+ v |= v >> 16;
+ ++v;
+ return v;
+}
+
+void lcl_addPointToPoly( drawing::PolyPolygonShape3D& rPoly
+ , const drawing::Position3D& rPos
+ , sal_Int32 nPolygonIndex
+ , std::vector< sal_Int32 >& rResultPointCount
+ , sal_Int32 nReservePointCount )
+{
+ if(nPolygonIndex<0)
+ {
+ OSL_FAIL( "The polygon index needs to be > 0");
+ nPolygonIndex=0;
+ }
+
+ //make sure that we have enough polygons
+ if(nPolygonIndex >= rPoly.SequenceX.getLength() )
+ {
+ rPoly.SequenceX.realloc(nPolygonIndex+1);
+ rPoly.SequenceY.realloc(nPolygonIndex+1);
+ rPoly.SequenceZ.realloc(nPolygonIndex+1);
+ rResultPointCount.resize(nPolygonIndex+1,0);
+ }
+
+ drawing::DoubleSequence* pOuterSequenceX = &rPoly.SequenceX.getArray()[nPolygonIndex];
+ drawing::DoubleSequence* pOuterSequenceY = &rPoly.SequenceY.getArray()[nPolygonIndex];
+ drawing::DoubleSequence* pOuterSequenceZ = &rPoly.SequenceZ.getArray()[nPolygonIndex];
+
+ sal_Int32 nNewResultPointCount = rResultPointCount[nPolygonIndex]+1;
+ sal_Int32 nSeqLength = pOuterSequenceX->getLength();
+
+ if( nSeqLength <= nNewResultPointCount )
+ {
+ sal_Int32 nReallocLength = nReservePointCount > SAL_MAX_INT16 ? round_up_nearest_pow2(nNewResultPointCount) * 2 : nReservePointCount;
+ if( nNewResultPointCount > nReallocLength )
+ {
+ nReallocLength = nNewResultPointCount;
+ OSL_FAIL("this should not be the case to avoid performance problems");
+ }
+ pOuterSequenceX->realloc(nReallocLength);
+ pOuterSequenceY->realloc(nReallocLength);
+ pOuterSequenceZ->realloc(nReallocLength);
+ }
+
+ double* pInnerSequenceX = pOuterSequenceX->getArray();
+ double* pInnerSequenceY = pOuterSequenceY->getArray();
+ double* pInnerSequenceZ = pOuterSequenceZ->getArray();
+
+ pInnerSequenceX[nNewResultPointCount-1] = rPos.PositionX;
+ pInnerSequenceY[nNewResultPointCount-1] = rPos.PositionY;
+ pInnerSequenceZ[nNewResultPointCount-1] = rPos.PositionZ;
+ rResultPointCount[nPolygonIndex]=nNewResultPointCount;
+}
+
+void lcl_addPointToPoly( std::vector<std::vector<css::drawing::Position3D>>& rPoly
+ , const drawing::Position3D& rPos
+ , sal_Int32 nPolygonIndex
+ , std::vector< sal_Int32 >& rResultPointCount
+ , sal_Int32 nReservePointCount )
+{
+ if(nPolygonIndex<0)
+ {
+ OSL_FAIL( "The polygon index needs to be > 0");
+ nPolygonIndex=0;
+ }
+
+ //make sure that we have enough polygons
+ if(o3tl::make_unsigned(nPolygonIndex) >= rPoly.size() )
+ {
+ rPoly.resize(nPolygonIndex+1);
+ rResultPointCount.resize(nPolygonIndex+1,0);
+ }
+
+ std::vector<css::drawing::Position3D>* pOuterSequence = &rPoly[nPolygonIndex];
+
+ sal_Int32 nNewResultPointCount = rResultPointCount[nPolygonIndex]+1;
+ sal_Int32 nSeqLength = pOuterSequence->size();
+
+ if( nSeqLength <= nNewResultPointCount )
+ {
+ sal_Int32 nReallocLength = nReservePointCount > SAL_MAX_INT16 ? round_up_nearest_pow2(nNewResultPointCount) * 2 : nReservePointCount;
+ if( nNewResultPointCount > nReallocLength )
+ {
+ nReallocLength = nNewResultPointCount;
+ OSL_FAIL("this should not be the case to avoid performance problems");
+ }
+ pOuterSequence->resize(nReallocLength);
+ }
+
+ css::drawing::Position3D* pInnerSequence = pOuterSequence->data();
+
+ pInnerSequence[nNewResultPointCount-1] = rPos;
+ rResultPointCount[nPolygonIndex]=nNewResultPointCount;
+}
+
+}//end anonymous namespace
+
+void Clipping::clipPolygonAtRectangle( const drawing::PolyPolygonShape3D& rPolygon
+ , const B2DRectangle& rRectangle
+ , drawing::PolyPolygonShape3D& aResult
+ , bool bSplitPiecesToDifferentPolygons )
+{
+ aResult.SequenceX.realloc(0);
+ aResult.SequenceY.realloc(0);
+ aResult.SequenceZ.realloc(0);
+
+ if(!rPolygon.SequenceX.hasElements())
+ return;
+
+ //need clipping?:
+ {
+ ::basegfx::B3DRange a3DRange( BaseGFXHelper::getBoundVolume( rPolygon ) );
+ ::basegfx::B2DRange a2DRange( a3DRange.getMinX(), a3DRange.getMinY(), a3DRange.getMaxX(), a3DRange.getMaxY() );
+ if( rRectangle.isInside( a2DRange ) )
+ {
+ aResult = rPolygon;
+ return;
+ }
+ else
+ {
+ a2DRange.intersect( rRectangle );
+ if( a2DRange.isEmpty() )
+ return;
+ }
+ }
+
+ std::vector< sal_Int32 > aResultPointCount;//per polygon index
+
+ //apply clipping:
+ drawing::Position3D aFrom;
+ drawing::Position3D aTo;
+
+ sal_Int32 nNewPolyIndex = 0;
+ sal_Int32 nOldPolyCount = rPolygon.SequenceX.getLength();
+ for(sal_Int32 nOldPolyIndex=0; nOldPolyIndex<nOldPolyCount; nOldPolyIndex++, nNewPolyIndex++ )
+ {
+ sal_Int32 nOldPointCount = rPolygon.SequenceX[nOldPolyIndex].getLength();
+
+ // set last point to a position outside the rectangle, such that the first
+ // time lcl_clip2d returns true, the comparison to last will always yield false
+ drawing::Position3D aLast(rRectangle.getMinX()-1.0,rRectangle.getMinY()-1.0, 0.0 );
+
+ for(sal_Int32 nOldPoint=1; nOldPoint<nOldPointCount; nOldPoint++)
+ {
+ aFrom = getPointFromPoly(rPolygon,nOldPoint-1,nOldPolyIndex);
+ aTo = getPointFromPoly(rPolygon,nOldPoint,nOldPolyIndex);
+ if( lcl_clip2d_(aFrom, aTo, rRectangle) )
+ {
+ // compose a Polygon of as many consecutive points as possible
+ if(aFrom == aLast)
+ {
+ if( aTo != aFrom )
+ {
+ lcl_addPointToPoly( aResult, aTo, nNewPolyIndex, aResultPointCount, nOldPointCount );
+ }
+ }
+ else
+ {
+ if( bSplitPiecesToDifferentPolygons && nOldPoint!=1 )
+ {
+ if( nNewPolyIndex < aResult.SequenceX.getLength()
+ && aResultPointCount[nNewPolyIndex]>0 )
+ nNewPolyIndex++;
+ }
+ lcl_addPointToPoly( aResult, aFrom, nNewPolyIndex, aResultPointCount, nOldPointCount );
+ if( aTo != aFrom )
+ lcl_addPointToPoly( aResult, aTo, nNewPolyIndex, aResultPointCount, nOldPointCount );
+ }
+ aLast = aTo;
+ }
+ }
+ }
+ //free unused space
+ for( sal_Int32 nPolygonIndex = aResultPointCount.size(); nPolygonIndex--; )
+ {
+ drawing::DoubleSequence* pOuterSequenceX = &aResult.SequenceX.getArray()[nPolygonIndex];
+ drawing::DoubleSequence* pOuterSequenceY = &aResult.SequenceY.getArray()[nPolygonIndex];
+ drawing::DoubleSequence* pOuterSequenceZ = &aResult.SequenceZ.getArray()[nPolygonIndex];
+
+ sal_Int32 nUsedPointCount = aResultPointCount[nPolygonIndex];
+ pOuterSequenceX->realloc(nUsedPointCount);
+ pOuterSequenceY->realloc(nUsedPointCount);
+ pOuterSequenceZ->realloc(nUsedPointCount);
+ }
+}
+
+void Clipping::clipPolygonAtRectangle( const std::vector<std::vector<css::drawing::Position3D>>& rPolygon
+ , const B2DRectangle& rRectangle
+ , std::vector<std::vector<css::drawing::Position3D>>& aResult
+ , bool bSplitPiecesToDifferentPolygons )
+{
+ aResult.clear();
+
+ if(rPolygon.empty())
+ return;
+
+ //need clipping?:
+ {
+ ::basegfx::B3DRange a3DRange( BaseGFXHelper::getBoundVolume( rPolygon ) );
+ ::basegfx::B2DRange a2DRange( a3DRange.getMinX(), a3DRange.getMinY(), a3DRange.getMaxX(), a3DRange.getMaxY() );
+ if( rRectangle.isInside( a2DRange ) )
+ {
+ aResult = rPolygon;
+ return;
+ }
+ else
+ {
+ a2DRange.intersect( rRectangle );
+ if( a2DRange.isEmpty() )
+ return;
+ }
+ }
+
+ std::vector< sal_Int32 > aResultPointCount;//per polygon index
+
+ //apply clipping:
+ drawing::Position3D aFrom;
+ drawing::Position3D aTo;
+
+ sal_Int32 nNewPolyIndex = 0;
+ sal_Int32 nOldPolyCount = rPolygon.size();
+ for(sal_Int32 nOldPolyIndex=0; nOldPolyIndex<nOldPolyCount; nOldPolyIndex++, nNewPolyIndex++ )
+ {
+ sal_Int32 nOldPointCount = rPolygon[nOldPolyIndex].size();
+
+ // set last point to a position outside the rectangle, such that the first
+ // time lcl_clip2d returns true, the comparison to last will always yield false
+ drawing::Position3D aLast(rRectangle.getMinX()-1.0,rRectangle.getMinY()-1.0, 0.0 );
+
+ for(sal_Int32 nOldPoint=1; nOldPoint<nOldPointCount; nOldPoint++)
+ {
+ aFrom = getPointFromPoly(rPolygon,nOldPoint-1,nOldPolyIndex);
+ aTo = getPointFromPoly(rPolygon,nOldPoint,nOldPolyIndex);
+ if( lcl_clip2d_(aFrom, aTo, rRectangle) )
+ {
+ // compose a Polygon of as many consecutive points as possible
+ if(aFrom == aLast)
+ {
+ if( aTo != aFrom )
+ {
+ lcl_addPointToPoly( aResult, aTo, nNewPolyIndex, aResultPointCount, nOldPointCount );
+ }
+ }
+ else
+ {
+ if( bSplitPiecesToDifferentPolygons && nOldPoint!=1 )
+ {
+ if( nNewPolyIndex < static_cast<sal_Int32>(aResult.size())
+ && aResultPointCount[nNewPolyIndex]>0 )
+ nNewPolyIndex++;
+ }
+ lcl_addPointToPoly( aResult, aFrom, nNewPolyIndex, aResultPointCount, nOldPointCount );
+ if( aTo != aFrom )
+ lcl_addPointToPoly( aResult, aTo, nNewPolyIndex, aResultPointCount, nOldPointCount );
+ }
+ aLast = aTo;
+ }
+ }
+ }
+ //free unused space
+ for( sal_Int32 nPolygonIndex = aResultPointCount.size(); nPolygonIndex--; )
+ {
+ std::vector<css::drawing::Position3D>* pOuterSequence = &aResult[nPolygonIndex];
+
+ sal_Int32 nUsedPointCount = aResultPointCount[nPolygonIndex];
+ pOuterSequence->resize(nUsedPointCount);
+ }
+}
+
+} //namespace chart
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */