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