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