Branch data Line data Source code
1 : : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : : /*************************************************************************
3 : : *
4 : : * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 : : *
6 : : * Copyright 2000, 2010 Oracle and/or its affiliates.
7 : : *
8 : : * OpenOffice.org - a multi-platform office productivity suite
9 : : *
10 : : * This file is part of OpenOffice.org.
11 : : *
12 : : * OpenOffice.org is free software: you can redistribute it and/or modify
13 : : * it under the terms of the GNU Lesser General Public License version 3
14 : : * only, as published by the Free Software Foundation.
15 : : *
16 : : * OpenOffice.org is distributed in the hope that it will be useful,
17 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 : : * GNU Lesser General Public License version 3 for more details
20 : : * (a copy is included in the LICENSE file that accompanied this code).
21 : : *
22 : : * You should have received a copy of the GNU Lesser General Public License
23 : : * version 3 along with OpenOffice.org. If not, see
24 : : * <http://www.openoffice.org/license.html>
25 : : * for a copy of the LGPLv3 License.
26 : : *
27 : : ************************************************************************/
28 : :
29 : : #include <basegfx/polygon/b2dpolygonclipper.hxx>
30 : : #include <osl/diagnose.h>
31 : : #include <basegfx/polygon/b2dpolygontools.hxx>
32 : : #include <basegfx/numeric/ftools.hxx>
33 : : #include <basegfx/matrix/b2dhommatrix.hxx>
34 : : #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
35 : : #include <basegfx/polygon/b2dpolygoncutandtouch.hxx>
36 : : #include <basegfx/polygon/b2dpolypolygontools.hxx>
37 : : #include <basegfx/curve/b2dcubicbezier.hxx>
38 : : #include <basegfx/tools/rectcliptools.hxx>
39 : : #include <basegfx/matrix/b2dhommatrixtools.hxx>
40 : :
41 : : //////////////////////////////////////////////////////////////////////////////
42 : :
43 : : namespace basegfx
44 : : {
45 : : namespace tools
46 : : {
47 : 0 : B2DPolyPolygon clipPolygonOnParallelAxis(const B2DPolygon& rCandidate, bool bParallelToXAxis, bool bAboveAxis, double fValueOnOtherAxis, bool bStroke)
48 : : {
49 : 0 : B2DPolyPolygon aRetval;
50 : :
51 [ # # ][ # # ]: 0 : if(rCandidate.count())
52 : : {
53 [ # # ]: 0 : const B2DRange aCandidateRange(getRange(rCandidate));
54 : :
55 [ # # ][ # # ]: 0 : if(bParallelToXAxis && fTools::moreOrEqual(aCandidateRange.getMinY(), fValueOnOtherAxis))
[ # # ][ # # ]
[ # # # # ]
56 : : {
57 : : // completely above and on the clip line. also true for curves.
58 [ # # ]: 0 : if(bAboveAxis)
59 : : {
60 : : // add completely
61 [ # # ]: 0 : aRetval.append(rCandidate);
62 : : }
63 : : }
64 [ # # ][ # # ]: 0 : else if(bParallelToXAxis && fTools::lessOrEqual(aCandidateRange.getMaxY(), fValueOnOtherAxis))
[ # # ][ # # ]
[ # # # # ]
65 : : {
66 : : // completely below and on the clip line. also true for curves.
67 [ # # ]: 0 : if(!bAboveAxis)
68 : : {
69 : : // add completely
70 [ # # ]: 0 : aRetval.append(rCandidate);
71 : : }
72 : : }
73 [ # # ][ # # ]: 0 : else if(!bParallelToXAxis && fTools::moreOrEqual(aCandidateRange.getMinX(), fValueOnOtherAxis))
[ # # ][ # # ]
[ # # # # ]
74 : : {
75 : : // completely right of and on the clip line. also true for curves.
76 [ # # ]: 0 : if(bAboveAxis)
77 : : {
78 : : // add completely
79 [ # # ]: 0 : aRetval.append(rCandidate);
80 : : }
81 : : }
82 [ # # ][ # # ]: 0 : else if(!bParallelToXAxis && fTools::lessOrEqual(aCandidateRange.getMaxX(), fValueOnOtherAxis))
[ # # ][ # # ]
[ # # # # ]
83 : : {
84 : : // completely left of and on the clip line. also true for curves.
85 [ # # ]: 0 : if(!bAboveAxis)
86 : : {
87 : : // add completely
88 [ # # ]: 0 : aRetval.append(rCandidate);
89 : : }
90 : : }
91 : : else
92 : : {
93 : : // add cuts with axis to polygon, including bezier segments
94 : : // Build edge to cut with. Make it a little big longer than needed for
95 : : // numerical stability. We want to cut against the edge seen as endless
96 : : // ray here, but addPointsAtCuts() will limit itself to the
97 : : // edge's range ]0.0 .. 1.0[.
98 [ # # ][ # # ]: 0 : const double fSmallExtension((aCandidateRange.getWidth() + aCandidateRange.getHeight()) * (0.5 * 0.1));
99 : : const B2DPoint aStart(
100 [ # # ]: 0 : bParallelToXAxis ? aCandidateRange.getMinX() - fSmallExtension : fValueOnOtherAxis,
101 [ # # ][ # # ]: 0 : bParallelToXAxis ? fValueOnOtherAxis : aCandidateRange.getMinY() - fSmallExtension);
[ # # ]
102 : : const B2DPoint aEnd(
103 [ # # ]: 0 : bParallelToXAxis ? aCandidateRange.getMaxX() + fSmallExtension : fValueOnOtherAxis,
104 [ # # ][ # # ]: 0 : bParallelToXAxis ? fValueOnOtherAxis : aCandidateRange.getMaxY() + fSmallExtension);
[ # # ]
105 [ # # ]: 0 : const B2DPolygon aCandidate(addPointsAtCuts(rCandidate, aStart, aEnd));
106 [ # # ]: 0 : const sal_uInt32 nPointCount(aCandidate.count());
107 [ # # ][ # # ]: 0 : const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L);
108 [ # # ]: 0 : B2DCubicBezier aEdge;
109 [ # # ]: 0 : B2DPolygon aRun;
110 : :
111 [ # # ]: 0 : for(sal_uInt32 a(0L); a < nEdgeCount; a++)
112 : : {
113 [ # # ]: 0 : aCandidate.getBezierSegment(a, aEdge);
114 [ # # ]: 0 : const B2DPoint aTestPoint(aEdge.interpolatePoint(0.5));
115 : : const bool bInside(bParallelToXAxis ?
116 [ # # ]: 0 : fTools::moreOrEqual(aTestPoint.getY(), fValueOnOtherAxis) == bAboveAxis :
117 [ # # ][ # # ]: 0 : fTools::moreOrEqual(aTestPoint.getX(), fValueOnOtherAxis) == bAboveAxis);
118 : :
119 [ # # ]: 0 : if(bInside)
120 : : {
121 [ # # ][ # # ]: 0 : if(!aRun.count() || !aRun.getB2DPoint(aRun.count() - 1).equal(aEdge.getStartPoint()))
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # #
# # # # ]
122 : : {
123 [ # # ]: 0 : aRun.append(aEdge.getStartPoint());
124 : : }
125 : :
126 [ # # ][ # # ]: 0 : if(aEdge.isBezier())
127 : : {
128 [ # # ]: 0 : aRun.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint());
129 : : }
130 : : else
131 : : {
132 [ # # ]: 0 : aRun.append(aEdge.getEndPoint());
133 : : }
134 : : }
135 : : else
136 : : {
137 [ # # ][ # # ]: 0 : if(bStroke && aRun.count())
[ # # ][ # # ]
138 : : {
139 [ # # ]: 0 : aRetval.append(aRun);
140 [ # # ]: 0 : aRun.clear();
141 : : }
142 : : }
143 : 0 : }
144 : :
145 [ # # ][ # # ]: 0 : if(aRun.count())
146 : : {
147 [ # # ]: 0 : if(bStroke)
148 : : {
149 : : // try to merge this last and first polygon; they may have been
150 : : // the former polygon's start/end point
151 [ # # ][ # # ]: 0 : if(aRetval.count())
152 : : {
153 [ # # ]: 0 : const B2DPolygon aStartPolygon(aRetval.getB2DPolygon(0));
154 : :
155 [ # # ][ # # ]: 0 : if(aStartPolygon.count() && aStartPolygon.getB2DPoint(0).equal(aRun.getB2DPoint(aRun.count() - 1)))
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # # #
# # ]
156 : : {
157 : : // append start polygon to aRun, remove from result set
158 [ # # ][ # # ]: 0 : aRun.append(aStartPolygon); aRun.removeDoublePoints();
159 [ # # ]: 0 : aRetval.remove(0);
160 [ # # ]: 0 : }
161 : : }
162 : :
163 [ # # ]: 0 : aRetval.append(aRun);
164 : : }
165 : : else
166 : : {
167 : : // set closed flag and correct last point (which is added double now).
168 [ # # ]: 0 : closeWithGeometryChange(aRun);
169 [ # # ]: 0 : aRetval.append(aRun);
170 : : }
171 [ # # ][ # # ]: 0 : }
[ # # ]
172 : : }
173 : : }
174 : :
175 : 0 : return aRetval;
176 : : }
177 : :
178 : 0 : B2DPolyPolygon clipPolyPolygonOnParallelAxis(const B2DPolyPolygon& rCandidate, bool bParallelToXAxis, bool bAboveAxis, double fValueOnOtherAxis, bool bStroke)
179 : : {
180 : 0 : const sal_uInt32 nPolygonCount(rCandidate.count());
181 : 0 : B2DPolyPolygon aRetval;
182 : :
183 [ # # ]: 0 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
184 : : {
185 [ # # ][ # # ]: 0 : const B2DPolyPolygon aClippedPolyPolygon(clipPolygonOnParallelAxis(rCandidate.getB2DPolygon(a), bParallelToXAxis, bAboveAxis, fValueOnOtherAxis, bStroke));
[ # # ]
186 : :
187 [ # # ][ # # ]: 0 : if(aClippedPolyPolygon.count())
188 : : {
189 [ # # ]: 0 : aRetval.append(aClippedPolyPolygon);
190 : : }
191 [ # # ]: 0 : }
192 : :
193 : 0 : return aRetval;
194 : : }
195 : :
196 : 0 : B2DPolyPolygon clipPolygonOnRange(const B2DPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke)
197 : : {
198 [ # # ]: 0 : const sal_uInt32 nCount(rCandidate.count());
199 [ # # ]: 0 : B2DPolyPolygon aRetval;
200 : :
201 [ # # ]: 0 : if(!nCount)
202 : : {
203 : : // source is empty
204 [ # # ]: 0 : return aRetval;
205 : : }
206 : :
207 [ # # ][ # # ]: 0 : if(rRange.isEmpty())
208 : : {
209 [ # # ]: 0 : if(bInside)
210 : : {
211 : : // nothing is inside an empty range
212 [ # # ]: 0 : return aRetval;
213 : : }
214 : : else
215 : : {
216 : : // everything is outside an empty range
217 [ # # ]: 0 : return B2DPolyPolygon(rCandidate);
218 : : }
219 : : }
220 : :
221 [ # # ]: 0 : const B2DRange aCandidateRange(getRange(rCandidate));
222 : :
223 [ # # ][ # # ]: 0 : if(rRange.isInside(aCandidateRange))
224 : : {
225 : : // candidate is completely inside given range
226 [ # # ]: 0 : if(bInside)
227 : : {
228 : : // nothing to do
229 [ # # ]: 0 : return B2DPolyPolygon(rCandidate);
230 : : }
231 : : else
232 : : {
233 : : // nothing is outside, then
234 [ # # ]: 0 : return aRetval;
235 : : }
236 : : }
237 : :
238 [ # # ]: 0 : if(!bInside)
239 : : {
240 : : // cutting off the outer parts of filled polygons at parallell
241 : : // lines to the axes is only possible for the inner part, not for
242 : : // the outer part which means cutting a hole into the original polygon.
243 : : // This is because the inner part is a logical AND-operation of
244 : : // the four implied half-planes, but the outer part is not.
245 : : // It is possible for strokes, but with creating unnecessary extra
246 : : // cuts, so using clipPolygonOnPolyPolygon is better there, too.
247 : : // This needs to be done with the topology knowlegde and is unfurtunately
248 : : // more expensive, too.
249 [ # # ]: 0 : const B2DPolygon aClip(createPolygonFromRect(rRange));
250 : :
251 [ # # ][ # # ]: 0 : return clipPolygonOnPolyPolygon(rCandidate, B2DPolyPolygon(aClip), bInside, bStroke);
[ # # ][ # # ]
252 : : }
253 : :
254 : : // clip against the four axes of the range
255 : : // against X-Axis, lower value
256 [ # # ][ # # ]: 0 : aRetval = clipPolygonOnParallelAxis(rCandidate, true, bInside, rRange.getMinY(), bStroke);
[ # # ][ # # ]
257 : :
258 [ # # ][ # # ]: 0 : if(aRetval.count())
259 : : {
260 : : // against Y-Axis, lower value
261 [ # # ][ # # ]: 0 : if(1L == aRetval.count())
262 : : {
263 [ # # ][ # # ]: 0 : aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), false, bInside, rRange.getMinX(), bStroke);
[ # # ][ # # ]
[ # # ][ # # ]
264 : : }
265 : : else
266 : : {
267 [ # # ][ # # ]: 0 : aRetval = clipPolyPolygonOnParallelAxis(aRetval, false, bInside, rRange.getMinX(), bStroke);
[ # # ][ # # ]
268 : : }
269 : :
270 [ # # ][ # # ]: 0 : if(aRetval.count())
271 : : {
272 : : // against X-Axis, higher value
273 [ # # ][ # # ]: 0 : if(1L == aRetval.count())
274 : : {
275 [ # # ][ # # ]: 0 : aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), true, !bInside, rRange.getMaxY(), bStroke);
[ # # ][ # # ]
[ # # ][ # # ]
276 : : }
277 : : else
278 : : {
279 [ # # ][ # # ]: 0 : aRetval = clipPolyPolygonOnParallelAxis(aRetval, true, !bInside, rRange.getMaxY(), bStroke);
[ # # ][ # # ]
280 : : }
281 : :
282 [ # # ][ # # ]: 0 : if(aRetval.count())
283 : : {
284 : : // against Y-Axis, higher value
285 [ # # ][ # # ]: 0 : if(1L == aRetval.count())
286 : : {
287 [ # # ][ # # ]: 0 : aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), false, !bInside, rRange.getMaxX(), bStroke);
[ # # ][ # # ]
[ # # ][ # # ]
288 : : }
289 : : else
290 : : {
291 [ # # ][ # # ]: 0 : aRetval = clipPolyPolygonOnParallelAxis(aRetval, false, !bInside, rRange.getMaxX(), bStroke);
[ # # ][ # # ]
292 : : }
293 : : }
294 : : }
295 : : }
296 : :
297 [ # # ][ # # ]: 0 : return aRetval;
298 : : }
299 : :
300 : 0 : B2DPolyPolygon clipPolyPolygonOnRange(const B2DPolyPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke)
301 : : {
302 [ # # ]: 0 : const sal_uInt32 nPolygonCount(rCandidate.count());
303 [ # # ]: 0 : B2DPolyPolygon aRetval;
304 : :
305 [ # # ]: 0 : if(!nPolygonCount)
306 : : {
307 : : // source is empty
308 [ # # ]: 0 : return aRetval;
309 : : }
310 : :
311 [ # # ][ # # ]: 0 : if(rRange.isEmpty())
312 : : {
313 [ # # ]: 0 : if(bInside)
314 : : {
315 : : // nothing is inside an empty range
316 [ # # ]: 0 : return aRetval;
317 : : }
318 : : else
319 : : {
320 : : // everything is outside an empty range
321 [ # # ]: 0 : return rCandidate;
322 : : }
323 : : }
324 : :
325 [ # # ]: 0 : if(bInside)
326 : : {
327 [ # # ]: 0 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
328 : : {
329 [ # # ][ # # ]: 0 : const B2DPolyPolygon aClippedPolyPolygon(clipPolygonOnRange(rCandidate.getB2DPolygon(a), rRange, bInside, bStroke));
[ # # ]
330 : :
331 [ # # ][ # # ]: 0 : if(aClippedPolyPolygon.count())
332 : : {
333 [ # # ]: 0 : aRetval.append(aClippedPolyPolygon);
334 : : }
335 [ # # ]: 0 : }
336 : : }
337 : : else
338 : : {
339 : : // for details, see comment in clipPolygonOnRange for the "cutting off
340 : : // the outer parts of filled polygons at parallell lines" explanations
341 [ # # ]: 0 : const B2DPolygon aClip(createPolygonFromRect(rRange));
342 : :
343 [ # # ][ # # ]: 0 : return clipPolyPolygonOnPolyPolygon(rCandidate, B2DPolyPolygon(aClip), bInside, bStroke);
[ # # ][ # # ]
344 : : }
345 : :
346 [ # # ][ # # ]: 0 : return aRetval;
347 : : }
348 : :
349 : : //////////////////////////////////////////////////////////////////////////////
350 : :
351 : 1032 : B2DPolyPolygon clipPolyPolygonOnPolyPolygon(const B2DPolyPolygon& rCandidate, const B2DPolyPolygon& rClip, bool bInside, bool bStroke)
352 : : {
353 : 1032 : B2DPolyPolygon aRetval;
354 : :
355 [ + - ][ + - ]: 1032 : if(rCandidate.count() && rClip.count())
[ + - ][ + - ]
[ + - ]
356 : : {
357 [ + + ]: 1032 : if(bStroke)
358 : : {
359 : : // line clipping, create line snippets by first adding all cut points and
360 : : // then marching along the edges and detecting if they are inside or outside
361 : : // the clip polygon
362 [ + - ][ + + ]: 884 : for(sal_uInt32 a(0); a < rCandidate.count(); a++)
363 : : {
364 : : // add cuts with clip to polygon, including bezier segments
365 [ + - ][ + - ]: 802 : const B2DPolygon aCandidate(addPointsAtCuts(rCandidate.getB2DPolygon(a), rClip));
[ + - ]
366 [ + - ]: 802 : const sal_uInt32 nPointCount(aCandidate.count());
367 [ + - ][ - + ]: 802 : const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L);
368 [ + - ]: 802 : B2DCubicBezier aEdge;
369 [ + - ]: 802 : B2DPolygon aRun;
370 : :
371 [ + + ]: 1742 : for(sal_uInt32 b(0); b < nEdgeCount; b++)
372 : : {
373 [ + - ]: 940 : aCandidate.getBezierSegment(b, aEdge);
374 [ + - ]: 940 : const B2DPoint aTestPoint(aEdge.interpolatePoint(0.5));
375 [ + - ]: 940 : const bool bIsInside(tools::isInside(rClip, aTestPoint) == bInside);
376 : :
377 [ + + ]: 940 : if(bIsInside)
378 : : {
379 [ + - ][ + - ]: 802 : if(!aRun.count())
380 : : {
381 [ + - ]: 802 : aRun.append(aEdge.getStartPoint());
382 : : }
383 : :
384 [ + - ][ - + ]: 802 : if(aEdge.isBezier())
385 : : {
386 [ # # ]: 0 : aRun.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint());
387 : : }
388 : : else
389 : : {
390 [ + - ]: 802 : aRun.append(aEdge.getEndPoint());
391 : : }
392 : : }
393 : : else
394 : : {
395 [ + - ][ + + ]: 138 : if(aRun.count())
396 : : {
397 [ + - ]: 46 : aRetval.append(aRun);
398 [ + - ]: 46 : aRun.clear();
399 : : }
400 : : }
401 : 940 : }
402 : :
403 [ + - ][ + + ]: 802 : if(aRun.count())
404 : : {
405 : : // try to merge this last and first polygon; they may have been
406 : : // the former polygon's start/end point
407 [ + - ][ + + ]: 756 : if(aRetval.count())
408 : : {
409 [ + - ]: 720 : const B2DPolygon aStartPolygon(aRetval.getB2DPolygon(0));
410 : :
411 [ + - ][ + - ]: 720 : if(aStartPolygon.count() && aStartPolygon.getB2DPoint(0).equal(aRun.getB2DPoint(aRun.count() - 1)))
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ - + # #
# # ]
412 : : {
413 : : // append start polygon to aRun, remove from result set
414 [ # # ][ # # ]: 0 : aRun.append(aStartPolygon); aRun.removeDoublePoints();
415 [ # # ]: 0 : aRetval.remove(0);
416 [ + - ]: 720 : }
417 : : }
418 : :
419 [ + - ]: 756 : aRetval.append(aRun);
420 : : }
421 [ + - ][ + - ]: 802 : }
[ + - ]
422 : : }
423 : : else
424 : : {
425 : : // area clipping
426 [ + - ]: 950 : B2DPolyPolygon aMergePolyPolygonA(rClip);
427 : :
428 : : // First solve all polygon-self and polygon-polygon intersections.
429 : : // Also get rid of some not-needed polygons (neutral, no area -> when
430 : : // no intersections, these are tubes).
431 : : // Now it is possible to correct the orientations in the cut-free
432 : : // polygons to values corresponding to painting the PolyPolygon with
433 : : // a XOR-WindingRule.
434 [ + - ][ + - ]: 950 : aMergePolyPolygonA = solveCrossovers(aMergePolyPolygonA);
[ + - ]
435 [ + - ][ + - ]: 950 : aMergePolyPolygonA = stripNeutralPolygons(aMergePolyPolygonA);
[ + - ]
436 [ + - ][ + - ]: 950 : aMergePolyPolygonA = correctOrientations(aMergePolyPolygonA);
[ + - ]
437 : :
438 [ - + ]: 950 : if(!bInside)
439 : : {
440 : : // if we want to get the outside of the clip polygon, make
441 : : // it a 'Hole' in topological sense
442 [ # # ]: 0 : aMergePolyPolygonA.flip();
443 : : }
444 : :
445 [ + - ]: 950 : B2DPolyPolygon aMergePolyPolygonB(rCandidate);
446 : :
447 : : // prepare 2nd source polygon in same way
448 [ + - ][ + - ]: 950 : aMergePolyPolygonB = solveCrossovers(aMergePolyPolygonB);
[ + - ]
449 [ + - ][ + - ]: 950 : aMergePolyPolygonB = stripNeutralPolygons(aMergePolyPolygonB);
[ + - ]
450 [ + - ][ + - ]: 950 : aMergePolyPolygonB = correctOrientations(aMergePolyPolygonB);
[ + - ]
451 : :
452 : : // to clip against each other, concatenate and solve all
453 : : // polygon-polygon crossovers. polygon-self do not need to
454 : : // be solved again, they were solved in the preparation.
455 [ + - ]: 950 : aRetval.append(aMergePolyPolygonA);
456 [ + - ]: 950 : aRetval.append(aMergePolyPolygonB);
457 [ + - ][ + - ]: 950 : aRetval = solveCrossovers(aRetval);
[ + - ]
458 : :
459 : : // now remove neutral polygons (closed, but no area). In a last
460 : : // step throw away all polygons which have a depth of less than 1
461 : : // which means there was no logical AND at their position. For the
462 : : // not-inside solution, the clip was flipped to define it as 'Hole',
463 : : // so the removal rule is different here; remove all with a depth
464 : : // of less than 0 (aka holes).
465 [ + - ][ + - ]: 950 : aRetval = stripNeutralPolygons(aRetval);
[ + - ]
466 [ + - ][ + - ]: 950 : aRetval = stripDispensablePolygons(aRetval, bInside);
[ + - ][ + - ]
[ + - ]
467 : : }
468 : : }
469 : :
470 : 1032 : return aRetval;
471 : : }
472 : :
473 : : //////////////////////////////////////////////////////////////////////////////
474 : :
475 : 831 : B2DPolyPolygon clipPolygonOnPolyPolygon(const B2DPolygon& rCandidate, const B2DPolyPolygon& rClip, bool bInside, bool bStroke)
476 : : {
477 : 831 : B2DPolyPolygon aRetval;
478 : :
479 [ + - ][ + - ]: 831 : if(rCandidate.count() && rClip.count())
[ + - ][ + - ]
[ + - ]
480 : : {
481 [ + - ][ + - ]: 831 : aRetval = clipPolyPolygonOnPolyPolygon(B2DPolyPolygon(rCandidate), rClip, bInside, bStroke);
[ + - ][ + - ]
[ + - ]
482 : : }
483 : :
484 : 831 : return aRetval;
485 : : }
486 : :
487 : : //////////////////////////////////////////////////////////////////////////////
488 : :
489 : : /*
490 : : * let a plane be defined as
491 : : *
492 : : * v.n+d=0
493 : : *
494 : : * and a ray be defined as
495 : : *
496 : : * a+(b-a)*t=0
497 : : *
498 : : * substitute and rearranging yields
499 : : *
500 : : * t = -(a.n+d)/(n.(b-a))
501 : : *
502 : : * if the denominator is zero, the line is either
503 : : * contained in the plane or parallel to the plane.
504 : : * in either case, there is no intersection.
505 : : * if numerator and denominator are both zero, the
506 : : * ray is contained in the plane.
507 : : *
508 : : */
509 : : struct scissor_plane {
510 : : double nx,ny; // plane normal
511 : : double d; // [-] minimum distance from origin
512 : : sal_uInt32 clipmask; // clipping mask, e.g. 1000 1000
513 : : };
514 : :
515 : : /*
516 : : *
517 : : * polygon clipping rules (straight out of Foley and Van Dam)
518 : : * ===========================================================
519 : : * current |next |emit
520 : : * ____________________________________
521 : : * inside |inside |next
522 : : * inside |outside |intersect with clip plane
523 : : * outside |outside |nothing
524 : : * outside |inside |intersect with clip plane follwed by next
525 : : *
526 : : */
527 : 0 : sal_uInt32 scissorLineSegment( ::basegfx::B2DPoint *in_vertex, // input buffer
528 : : sal_uInt32 in_count, // number of verts in input buffer
529 : : ::basegfx::B2DPoint *out_vertex, // output buffer
530 : : scissor_plane *pPlane, // scissoring plane
531 : : const ::basegfx::B2DRectangle &rR ) // clipping rectangle
532 : : {
533 : : ::basegfx::B2DPoint *curr;
534 : : ::basegfx::B2DPoint *next;
535 : :
536 : 0 : sal_uInt32 out_count=0;
537 : :
538 : : // process all the verts
539 [ # # ]: 0 : for(sal_uInt32 i=0; i<in_count; i++) {
540 : :
541 : : // vertices are relative to the coordinate
542 : : // system defined by the rectangle.
543 : 0 : curr = &in_vertex[i];
544 : 0 : next = &in_vertex[(i+1)%in_count];
545 : :
546 : : // perform clipping judgement & mask against current plane.
547 : 0 : sal_uInt32 clip = pPlane->clipmask & ((getCohenSutherlandClipFlags(*curr,rR)<<4)|getCohenSutherlandClipFlags(*next,rR));
548 : :
549 [ # # ]: 0 : if(clip==0) { // both verts are inside
550 : 0 : out_vertex[out_count++] = *next;
551 : : }
552 [ # # ][ # # ]: 0 : else if((clip&0x0f) && (clip&0xf0)) { // both verts are outside
553 : : }
554 [ # # ][ # # ]: 0 : else if((clip&0x0f) && (clip&0xf0)==0) { // curr is inside, next is outside
555 : :
556 : : // direction vector from 'current' to 'next', *not* normalized
557 : : // to bring 't' into the [0<=x<=1] intervall.
558 : 0 : ::basegfx::B2DPoint dir((*next)-(*curr));
559 : :
560 : 0 : double denominator = ( pPlane->nx*dir.getX() +
561 : 0 : pPlane->ny*dir.getY() );
562 : 0 : double numerator = ( pPlane->nx*curr->getX() +
563 : 0 : pPlane->ny*curr->getY() +
564 : 0 : pPlane->d );
565 : 0 : double t = -numerator/denominator;
566 : :
567 : : // calculate the actual point of intersection
568 : 0 : ::basegfx::B2DPoint intersection( curr->getX()+t*dir.getX(),
569 : 0 : curr->getY()+t*dir.getY() );
570 : :
571 : 0 : out_vertex[out_count++] = intersection;
572 : : }
573 [ # # ][ # # ]: 0 : else if((clip&0x0f)==0 && (clip&0xf0)) { // curr is outside, next is inside
574 : :
575 : : // direction vector from 'current' to 'next', *not* normalized
576 : : // to bring 't' into the [0<=x<=1] intervall.
577 : 0 : ::basegfx::B2DPoint dir((*next)-(*curr));
578 : :
579 : 0 : double denominator = ( pPlane->nx*dir.getX() +
580 : 0 : pPlane->ny*dir.getY() );
581 : 0 : double numerator = ( pPlane->nx*curr->getX() +
582 : 0 : pPlane->ny*curr->getY() +
583 : 0 : pPlane->d );
584 : 0 : double t = -numerator/denominator;
585 : :
586 : : // calculate the actual point of intersection
587 : 0 : ::basegfx::B2DPoint intersection( curr->getX()+t*dir.getX(),
588 : 0 : curr->getY()+t*dir.getY() );
589 : :
590 : 0 : out_vertex[out_count++] = intersection;
591 : 0 : out_vertex[out_count++] = *next;
592 : : }
593 : : }
594 : :
595 : 0 : return out_count;
596 : : }
597 : :
598 : 0 : B2DPolygon clipTriangleListOnRange( const B2DPolygon& rCandidate,
599 : : const B2DRange& rRange )
600 : : {
601 : 0 : B2DPolygon aResult;
602 : :
603 [ # # ][ # # ]: 0 : if( !(rCandidate.count()%3) )
604 : : {
605 : 0 : const int scissor_plane_count = 4;
606 : :
607 : : scissor_plane sp[scissor_plane_count];
608 : :
609 : 0 : sp[0].nx = +1.0;
610 : 0 : sp[0].ny = +0.0;
611 [ # # ]: 0 : sp[0].d = -(rRange.getMinX());
612 : 0 : sp[0].clipmask = (RectClipFlags::LEFT << 4) | RectClipFlags::LEFT; // 0001 0001
613 : 0 : sp[1].nx = -1.0;
614 : 0 : sp[1].ny = +0.0;
615 [ # # ]: 0 : sp[1].d = +(rRange.getMaxX());
616 : 0 : sp[1].clipmask = (RectClipFlags::RIGHT << 4) | RectClipFlags::RIGHT; // 0010 0010
617 : 0 : sp[2].nx = +0.0;
618 : 0 : sp[2].ny = +1.0;
619 [ # # ]: 0 : sp[2].d = -(rRange.getMinY());
620 : 0 : sp[2].clipmask = (RectClipFlags::TOP << 4) | RectClipFlags::TOP; // 0100 0100
621 : 0 : sp[3].nx = +0.0;
622 : 0 : sp[3].ny = -1.0;
623 [ # # ]: 0 : sp[3].d = +(rRange.getMaxY());
624 : 0 : sp[3].clipmask = (RectClipFlags::BOTTOM << 4) | RectClipFlags::BOTTOM; // 1000 1000
625 : :
626 : : // retrieve the number of vertices of the triangulated polygon
627 [ # # ]: 0 : const sal_uInt32 nVertexCount = rCandidate.count();
628 : :
629 [ # # ]: 0 : if(nVertexCount)
630 : : {
631 : : ////////////////////////////////////////////////////////////////////////
632 : : ////////////////////////////////////////////////////////////////////////
633 : : ////////////////////////////////////////////////////////////////////////
634 : : //
635 : : // Upper bound for the maximal number of vertices when intersecting an
636 : : // axis-aligned rectangle with a triangle in E2
637 : : //
638 : : // The rectangle and the triangle are in general position, and have 4 and 3
639 : : // vertices, respectively.
640 : : //
641 : : // Lemma: Since the rectangle is a convex polygon ( see
642 : : // http://mathworld.wolfram.com/ConvexPolygon.html for a definition), and
643 : : // has no holes, it follows that any straight line will intersect the
644 : : // rectangle's border line at utmost two times (with the usual
645 : : // tie-breaking rule, if the intersection exactly hits an already existing
646 : : // rectangle vertex, that this intersection is only attributed to one of
647 : : // the adjoining edges). Thus, having a rectangle intersected with
648 : : // a half-plane (one side of a straight line denotes 'inside', the
649 : : // other 'outside') will at utmost add _one_ vertex to the resulting
650 : : // intersection polygon (adding two intersection vertices, and removing at
651 : : // least one rectangle vertex):
652 : : //
653 : : // *
654 : : // +--+-----------------+
655 : : // | * |
656 : : // |* |
657 : : // + |
658 : : // *| |
659 : : // * | |
660 : : // +--------------------+
661 : : //
662 : : // Proof: If the straight line intersects the rectangle two
663 : : // times, it does so for distinct edges, i.e. the intersection has
664 : : // minimally one of the rectangle's vertices on either side of the straight
665 : : // line (but maybe more). Thus, the intersection with a half-plane has
666 : : // minimally _one_ rectangle vertex removed from the resulting clip
667 : : // polygon, and therefore, a clip against a half-plane has the net effect
668 : : // of adding at utmost _one_ vertex to the resulting clip polygon.
669 : : //
670 : : // Theorem: The intersection of a rectangle and a triangle results in a
671 : : // polygon with at utmost 7 vertices.
672 : : //
673 : : // Proof: The inside of the triangle can be described as the consecutive
674 : : // intersection with three half-planes. Together with the lemma above, this
675 : : // results in at utmost 3 additional vertices added to the already existing 4
676 : : // rectangle vertices.
677 : : //
678 : : // This upper bound is attained with the following example configuration:
679 : : //
680 : : // *
681 : : // ***
682 : : // ** *
683 : : // ** *
684 : : // ** *
685 : : // ** *
686 : : // ** *
687 : : // ** *
688 : : // ** *
689 : : // ** *
690 : : // ** *
691 : : // ----*2--------3 *
692 : : // | ** |*
693 : : // 1* 4
694 : : // **| *|
695 : : // ** | * |
696 : : // **| * |
697 : : // 7* * |
698 : : // --*6-----5-----
699 : : // ** *
700 : : // **
701 : : //
702 : : // As we need to scissor all triangles against the
703 : : // output rectangle we employ an output buffer for the
704 : : // resulting vertices. the question is how large this
705 : : // buffer needs to be compared to the number of
706 : : // incoming vertices. this buffer needs to hold at
707 : : // most the number of original vertices times '7'. see
708 : : // figure above for an example. scissoring triangles
709 : : // with the cohen-sutherland line clipping algorithm
710 : : // as implemented here will result in a triangle fan
711 : : // which will be rendered as separate triangles to
712 : : // avoid pipeline stalls for each scissored
713 : : // triangle. creating separate triangles from a
714 : : // triangle fan produces (n-2)*3 vertices where n is
715 : : // the number of vertices of the original triangle
716 : : // fan. for the maximum number of 7 vertices of
717 : : // resulting triangle fans we therefore need 15 times
718 : : // the number of original vertices.
719 : : //
720 : : ////////////////////////////////////////////////////////////////////////
721 : : ////////////////////////////////////////////////////////////////////////
722 : : ////////////////////////////////////////////////////////////////////////
723 : :
724 : : //const size_t nBufferSize = sizeof(vertex)*(nVertexCount*16);
725 : : //vertex *pVertices = (vertex*)alloca(nBufferSize);
726 : : //sal_uInt32 nNumOutput = 0;
727 : :
728 : : // we need to clip this triangle against the output rectangle
729 : : // to ensure that the resulting texture coordinates are in
730 : : // the valid range from [0<=st<=1]. under normal circustances
731 : : // we could use the BORDERCOLOR renderstate but some cards
732 : : // seem to ignore this feature.
733 [ # # ]: 0 : ::basegfx::B2DPoint stack[3];
734 : 0 : unsigned int clipflag = 0;
735 : :
736 [ # # ]: 0 : for(sal_uInt32 nIndex=0; nIndex<nVertexCount; ++nIndex)
737 : : {
738 : : // rotate stack
739 : 0 : stack[0] = stack[1];
740 : 0 : stack[1] = stack[2];
741 [ # # ]: 0 : stack[2] = rCandidate.getB2DPoint(nIndex);
742 : :
743 : : // clipping judgement
744 [ # # ]: 0 : clipflag |= !(rRange.isInside(stack[2]));
745 : :
746 [ # # ]: 0 : if(nIndex > 1)
747 : : {
748 : : // consume vertices until a single seperate triangle has been visited.
749 [ # # ]: 0 : if(!((nIndex+1)%3))
750 : : {
751 : : // if any of the last three vertices was outside
752 : : // we need to scissor against the destination rectangle
753 [ # # ]: 0 : if(clipflag & 7)
754 : : {
755 [ # # ]: 0 : ::basegfx::B2DPoint buf0[16];
756 [ # # ]: 0 : ::basegfx::B2DPoint buf1[16];
757 : :
758 : 0 : sal_uInt32 vertex_count = 3;
759 : :
760 : : // clip against all 4 planes passing the result of
761 : : // each plane as the input to the next using a double buffer
762 [ # # ]: 0 : vertex_count = scissorLineSegment(stack,vertex_count,buf1,&sp[0],rRange);
763 [ # # ]: 0 : vertex_count = scissorLineSegment(buf1,vertex_count,buf0,&sp[1],rRange);
764 [ # # ]: 0 : vertex_count = scissorLineSegment(buf0,vertex_count,buf1,&sp[2],rRange);
765 [ # # ]: 0 : vertex_count = scissorLineSegment(buf1,vertex_count,buf0,&sp[3],rRange);
766 : :
767 [ # # ]: 0 : if(vertex_count >= 3)
768 : : {
769 : : // convert triangle fan back to triangle list.
770 : 0 : ::basegfx::B2DPoint v0(buf0[0]);
771 : 0 : ::basegfx::B2DPoint v1(buf0[1]);
772 [ # # ]: 0 : for(sal_uInt32 i=2; i<vertex_count; ++i)
773 : : {
774 : 0 : ::basegfx::B2DPoint v2(buf0[i]);
775 [ # # ]: 0 : aResult.append(v0);
776 [ # # ]: 0 : aResult.append(v1);
777 [ # # ]: 0 : aResult.append(v2);
778 : 0 : v1 = v2;
779 : 0 : }
780 [ # # ][ # # ]: 0 : }
[ # # # # ]
781 : : }
782 : : else
783 : : {
784 : : // the last triangle has not been altered, simply copy to result
785 [ # # ]: 0 : for(sal_uInt32 i=0; i<3; ++i)
786 [ # # ]: 0 : aResult.append(stack[i]);
787 : : }
788 : : }
789 : : }
790 : :
791 : 0 : clipflag <<= 1;
792 [ # # ][ # # ]: 0 : }
793 : : }
794 : : }
795 : :
796 : 0 : return aResult;
797 : : }
798 : :
799 : : //////////////////////////////////////////////////////////////////////////////
800 : :
801 : : } // end of namespace tools
802 : : } // end of namespace basegfx
803 : :
804 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
