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