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 <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 690 : bool lcl_CLIPt(double fDenom,double fNum, double & fTE, double & fTL)
47 : {
48 : double fT;
49 :
50 690 : if (fDenom > 0) // Intersection enters: PE
51 : {
52 343 : fT = fNum / fDenom; // Parametric value at the intersection.
53 343 : if (fT > fTL) // fTE and fTL crossover
54 9 : return false; // therefore reject the line.
55 334 : else if (fT > fTE) // A new fTE has been found.
56 5 : fTE = fT;
57 : }
58 347 : else if (fDenom < 0) // Intersection leaves: PL
59 : {
60 344 : fT = fNum / fDenom; // Parametric Value at the intersection.
61 344 : if (fT < fTE) // fTE and fTL crossover
62 10 : return false; // therefore reject the line.
63 334 : else if (fT < fTL) // A new fTL has been found.
64 2 : fTL = fT;
65 : }
66 3 : else if (fNum > 0)
67 3 : return false; // Line lies on the outside of the edge.
68 :
69 668 : return true;
70 : }
71 :
72 : /** @descr The line given by it's 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 178 : bool lcl_clip2d(B2DTuple& rPoint0, B2DTuple& rPoint1, const B2DRectangle& rRectangle)
86 : {
87 : //Direction vector of the line.
88 178 : B2DTuple aDirection = rPoint1 - rPoint0;
89 :
90 178 : if( aDirection.getX()==0 && aDirection.getY()==0 && rRectangle.isInside(rPoint0) )
91 : {
92 : // Degenerate case of a zero length line.
93 0 : return true;
94 : }
95 : else
96 : {
97 : // Values of the line parameter where the line enters resp. leaves the rectangle.
98 178 : double fTE = 0,
99 178 : 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 178 : if( lcl_CLIPt(aDirection.getX(), rRectangle.getMinX() - rPoint0.getX(), fTE, fTL) )
104 178 : if( lcl_CLIPt(-aDirection.getX(), rPoint0.getX() - rRectangle.getMaxX(), fTE, fTL) )
105 178 : if( lcl_CLIPt(aDirection.getY(), rRectangle.getMinY() - rPoint0.getY(), fTE, fTL) )
106 156 : if( lcl_CLIPt(-aDirection.getY(), rPoint0.getY() - rRectangle.getMaxY(), fTE, fTL) )
107 : {
108 : // At least a part is visible.
109 156 : if (fTL < 1)
110 : {
111 : // Compute the new end point.
112 2 : rPoint1.setX( rPoint0.getX() + fTL * aDirection.getX() );
113 2 : rPoint1.setY( rPoint0.getY() + fTL * aDirection.getY() );
114 : }
115 156 : if (fTE > 0)
116 : {
117 : // Compute the new starting point.
118 5 : rPoint0.setX( rPoint0.getX() + fTE * aDirection.getX() );
119 5 : rPoint0.setY( rPoint0.getY() + fTE * aDirection.getY() );
120 : }
121 156 : return true;
122 : }
123 :
124 : // Line is not visible.
125 22 : return false;
126 178 : }
127 : }
128 :
129 178 : bool lcl_clip2d_(drawing::Position3D& rPoint0, drawing::Position3D& rPoint1, const B2DRectangle& rRectangle)
130 : {
131 178 : B2DTuple aP0(rPoint0.PositionX,rPoint0.PositionY);
132 356 : B2DTuple aP1(rPoint1.PositionX,rPoint1.PositionY);
133 178 : bool bRet = lcl_clip2d( aP0, aP1, rRectangle );
134 :
135 178 : rPoint0.PositionX = aP0.getX();
136 178 : rPoint0.PositionY = aP0.getY();
137 178 : rPoint1.PositionX = aP1.getX();
138 178 : rPoint1.PositionY = aP1.getY();
139 :
140 356 : return bRet;
141 : }
142 :
143 161 : void lcl_addPointToPoly( drawing::PolyPolygonShape3D& rPoly
144 : , const drawing::Position3D& rPos
145 : , sal_Int32 nPolygonIndex
146 : , std::vector< sal_Int32 >& rResultPointCount
147 : , sal_Int32 nReservePointCount )
148 : {
149 161 : if(nPolygonIndex<0)
150 : {
151 : OSL_FAIL( "The polygon index needs to be > 0");
152 0 : nPolygonIndex=0;
153 : }
154 :
155 : //make sure that we have enough polygons
156 161 : if(nPolygonIndex >= rPoly.SequenceX.getLength() )
157 : {
158 7 : rPoly.SequenceX.realloc(nPolygonIndex+1);
159 7 : rPoly.SequenceY.realloc(nPolygonIndex+1);
160 7 : rPoly.SequenceZ.realloc(nPolygonIndex+1);
161 7 : rResultPointCount.resize(nPolygonIndex+1,0);
162 : }
163 :
164 161 : drawing::DoubleSequence* pOuterSequenceX = &rPoly.SequenceX.getArray()[nPolygonIndex];
165 161 : drawing::DoubleSequence* pOuterSequenceY = &rPoly.SequenceY.getArray()[nPolygonIndex];
166 161 : drawing::DoubleSequence* pOuterSequenceZ = &rPoly.SequenceZ.getArray()[nPolygonIndex];
167 :
168 161 : sal_Int32 nNewResultPointCount = rResultPointCount[nPolygonIndex]+1;
169 161 : sal_Int32 nSeqLength = pOuterSequenceX->getLength();
170 :
171 161 : if( nSeqLength <= nNewResultPointCount )
172 : {
173 7 : sal_Int32 nReallocLength = nReservePointCount;
174 7 : if( nNewResultPointCount > nReallocLength )
175 : {
176 0 : nReallocLength = nNewResultPointCount;
177 : OSL_FAIL("this should not be the case to avoid performance problems");
178 : }
179 7 : pOuterSequenceX->realloc(nReallocLength);
180 7 : pOuterSequenceY->realloc(nReallocLength);
181 7 : pOuterSequenceZ->realloc(nReallocLength);
182 : }
183 :
184 161 : double* pInnerSequenceX = pOuterSequenceX->getArray();
185 161 : double* pInnerSequenceY = pOuterSequenceY->getArray();
186 161 : double* pInnerSequenceZ = pOuterSequenceZ->getArray();
187 :
188 161 : pInnerSequenceX[nNewResultPointCount-1] = rPos.PositionX;
189 161 : pInnerSequenceY[nNewResultPointCount-1] = rPos.PositionY;
190 161 : pInnerSequenceZ[nNewResultPointCount-1] = rPos.PositionZ;
191 161 : rResultPointCount[nPolygonIndex]=nNewResultPointCount;
192 161 : }
193 :
194 : }//end anonymous namespace
195 :
196 388 : void Clipping::clipPolygonAtRectangle( const drawing::PolyPolygonShape3D& rPolygon
197 : , const B2DRectangle& rRectangle
198 : , drawing::PolyPolygonShape3D& aResult
199 : , bool bSplitPiecesToDifferentPolygons )
200 : {
201 388 : aResult.SequenceX.realloc(0);
202 388 : aResult.SequenceY.realloc(0);
203 388 : aResult.SequenceZ.realloc(0);
204 :
205 388 : if(!rPolygon.SequenceX.getLength())
206 385 : return;
207 :
208 : //need clipping?:
209 : {
210 386 : ::basegfx::B3DRange a3DRange( BaseGFXHelper::getBoundVolume( rPolygon ) );
211 386 : ::basegfx::B2DRange a2DRange( a3DRange.getMinX(), a3DRange.getMinY(), a3DRange.getMaxX(), a3DRange.getMaxY() );
212 386 : if( rRectangle.isInside( a2DRange ) )
213 : {
214 375 : aResult = rPolygon;
215 756 : return;
216 : }
217 : else
218 : {
219 11 : a2DRange.intersect( rRectangle );
220 11 : if( a2DRange.isEmpty() )
221 6 : return;
222 : }
223 : }
224 :
225 5 : std::vector< sal_Int32 > aResultPointCount;//per polygon index
226 :
227 : //apply clipping:
228 5 : drawing::Position3D aFrom;
229 5 : drawing::Position3D aTo;
230 :
231 5 : sal_Int32 nNewPolyIndex = 0;
232 5 : sal_Int32 nOldPolyCount = rPolygon.SequenceX.getLength();
233 10 : for(sal_Int32 nOldPolyIndex=0; nOldPolyIndex<nOldPolyCount; nOldPolyIndex++, nNewPolyIndex++ )
234 : {
235 5 : sal_Int32 nOldPointCount = rPolygon.SequenceX[nOldPolyIndex].getLength();
236 :
237 : // set last point to a position outside the rectangle, such that the first
238 : // time lcl_clip2d returns true, the comparison to last will always yield false
239 5 : drawing::Position3D aLast(rRectangle.getMinX()-1.0,rRectangle.getMinY()-1.0, 0.0 );
240 :
241 183 : for(sal_Int32 nOldPoint=1; nOldPoint<nOldPointCount; nOldPoint++)
242 : {
243 178 : aFrom = getPointFromPoly(rPolygon,nOldPoint-1,nOldPolyIndex);
244 178 : aTo = getPointFromPoly(rPolygon,nOldPoint,nOldPolyIndex);
245 178 : if( lcl_clip2d_(aFrom, aTo, rRectangle) )
246 : {
247 : // compose an Polygon of as many consecutive points as possible
248 156 : if(aFrom == aLast)
249 : {
250 149 : if( !(aTo==aFrom) )
251 : {
252 149 : lcl_addPointToPoly( aResult, aTo, nNewPolyIndex, aResultPointCount, nOldPointCount );
253 : }
254 : }
255 : else
256 : {
257 7 : if( bSplitPiecesToDifferentPolygons && nOldPoint!=1 )
258 : {
259 10 : if( nNewPolyIndex < aResult.SequenceX.getLength()
260 5 : && aResultPointCount[nNewPolyIndex]>0 )
261 2 : nNewPolyIndex++;
262 : }
263 7 : lcl_addPointToPoly( aResult, aFrom, nNewPolyIndex, aResultPointCount, nOldPointCount );
264 7 : if( !(aTo==aFrom) )
265 5 : lcl_addPointToPoly( aResult, aTo, nNewPolyIndex, aResultPointCount, nOldPointCount );
266 : }
267 156 : aLast = aTo;
268 : }
269 : }
270 : }
271 : //free unused space
272 17 : for( sal_Int32 nPolygonIndex = aResultPointCount.size(); nPolygonIndex--; )
273 : {
274 7 : drawing::DoubleSequence* pOuterSequenceX = &aResult.SequenceX.getArray()[nPolygonIndex];
275 7 : drawing::DoubleSequence* pOuterSequenceY = &aResult.SequenceY.getArray()[nPolygonIndex];
276 7 : drawing::DoubleSequence* pOuterSequenceZ = &aResult.SequenceZ.getArray()[nPolygonIndex];
277 :
278 7 : sal_Int32 nUsedPointCount = aResultPointCount[nPolygonIndex];
279 7 : pOuterSequenceX->realloc(nUsedPointCount);
280 7 : pOuterSequenceY->realloc(nUsedPointCount);
281 7 : pOuterSequenceZ->realloc(nUsedPointCount);
282 5 : }
283 : }
284 :
285 : } //namespace chart
286 :
287 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
