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 1160 : B2DPolyPolygon clipPolygonOnParallelAxis(const B2DPolygon& rCandidate, bool bParallelToXAxis, bool bAboveAxis, double fValueOnOtherAxis, bool bStroke)
37 : {
38 1160 : B2DPolyPolygon aRetval;
39 :
40 1160 : if(rCandidate.count())
41 : {
42 1160 : const B2DRange aCandidateRange(getRange(rCandidate));
43 :
44 1160 : if(bParallelToXAxis && fTools::moreOrEqual(aCandidateRange.getMinY(), fValueOnOtherAxis))
45 : {
46 : // completely above and on the clip line. also true for curves.
47 116 : if(bAboveAxis)
48 : {
49 : // add completely
50 116 : aRetval.append(rCandidate);
51 : }
52 : }
53 1044 : else if(bParallelToXAxis && fTools::lessOrEqual(aCandidateRange.getMaxY(), fValueOnOtherAxis))
54 : {
55 : // completely below and on the clip line. also true for curves.
56 114 : if(!bAboveAxis)
57 : {
58 : // add completely
59 114 : aRetval.append(rCandidate);
60 : }
61 : }
62 930 : else if(!bParallelToXAxis && fTools::moreOrEqual(aCandidateRange.getMinX(), fValueOnOtherAxis))
63 : {
64 : // completely right of and on the clip line. also true for curves.
65 84 : if(bAboveAxis)
66 : {
67 : // add completely
68 82 : aRetval.append(rCandidate);
69 : }
70 : }
71 846 : else if(!bParallelToXAxis && fTools::lessOrEqual(aCandidateRange.getMaxX(), fValueOnOtherAxis))
72 : {
73 : // completely left of and on the clip line. also true for curves.
74 80 : if(!bAboveAxis)
75 : {
76 : // add completely
77 76 : 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 766 : const double fSmallExtension((aCandidateRange.getWidth() + aCandidateRange.getHeight()) * (0.5 * 0.1));
88 : const B2DPoint aStart(
89 350 : bParallelToXAxis ? aCandidateRange.getMinX() - fSmallExtension : fValueOnOtherAxis,
90 1116 : bParallelToXAxis ? fValueOnOtherAxis : aCandidateRange.getMinY() - fSmallExtension);
91 : const B2DPoint aEnd(
92 350 : bParallelToXAxis ? aCandidateRange.getMaxX() + fSmallExtension : fValueOnOtherAxis,
93 1882 : bParallelToXAxis ? fValueOnOtherAxis : aCandidateRange.getMaxY() + fSmallExtension);
94 1532 : const B2DPolygon aCandidate(addPointsAtCuts(rCandidate, aStart, aEnd));
95 766 : const sal_uInt32 nPointCount(aCandidate.count());
96 766 : const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L);
97 1532 : B2DCubicBezier aEdge;
98 1532 : B2DPolygon aRun;
99 :
100 6592 : for(sal_uInt32 a(0L); a < nEdgeCount; a++)
101 : {
102 5826 : aCandidate.getBezierSegment(a, aEdge);
103 5826 : const B2DPoint aTestPoint(aEdge.interpolatePoint(0.5));
104 : const bool bInside(bParallelToXAxis ?
105 13866 : fTools::moreOrEqual(aTestPoint.getY(), fValueOnOtherAxis) == bAboveAxis :
106 14332 : fTools::moreOrEqual(aTestPoint.getX(), fValueOnOtherAxis) == bAboveAxis);
107 :
108 5826 : if(bInside)
109 : {
110 3230 : if(!aRun.count() || !aRun.getB2DPoint(aRun.count() - 1).equal(aEdge.getStartPoint()))
111 : {
112 982 : aRun.append(aEdge.getStartPoint());
113 : }
114 :
115 3230 : if(aEdge.isBezier())
116 : {
117 0 : aRun.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint());
118 : }
119 : else
120 : {
121 3230 : aRun.append(aEdge.getEndPoint());
122 : }
123 : }
124 : else
125 : {
126 2596 : if(bStroke && aRun.count())
127 : {
128 0 : aRetval.append(aRun);
129 0 : aRun.clear();
130 : }
131 : }
132 5826 : }
133 :
134 766 : if(aRun.count())
135 : {
136 766 : 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 766 : closeWithGeometryChange(aRun);
158 766 : aRetval.append(aRun);
159 : }
160 766 : }
161 : }
162 : }
163 :
164 1160 : 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 314 : B2DPolyPolygon clipPolygonOnRange(const B2DPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke)
186 : {
187 314 : const sal_uInt32 nCount(rCandidate.count());
188 314 : B2DPolyPolygon aRetval;
189 :
190 314 : if(!nCount)
191 : {
192 : // source is empty
193 0 : return aRetval;
194 : }
195 :
196 314 : 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 314 : const B2DRange aCandidateRange(getRange(rCandidate));
211 :
212 314 : if(rRange.isInside(aCandidateRange))
213 : {
214 : // candidate is completely inside given range
215 22 : if(bInside)
216 : {
217 : // nothing to do
218 22 : return B2DPolyPolygon(rCandidate);
219 : }
220 : else
221 : {
222 : // nothing is outside, then
223 0 : return aRetval;
224 : }
225 : }
226 :
227 292 : 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 292 : aRetval = clipPolygonOnParallelAxis(rCandidate, true, bInside, rRange.getMinY(), bStroke);
246 :
247 292 : if(aRetval.count())
248 : {
249 : // against Y-Axis, lower value
250 292 : if(1L == aRetval.count())
251 : {
252 292 : 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 292 : if(aRetval.count())
260 : {
261 : // against X-Axis, higher value
262 288 : if(1L == aRetval.count())
263 : {
264 288 : 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 288 : if(aRetval.count())
272 : {
273 : // against Y-Axis, higher value
274 288 : if(1L == aRetval.count())
275 : {
276 288 : 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 292 : return aRetval;
287 : }
288 :
289 302 : B2DPolyPolygon clipPolyPolygonOnRange(const B2DPolyPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke)
290 : {
291 302 : const sal_uInt32 nPolygonCount(rCandidate.count());
292 302 : B2DPolyPolygon aRetval;
293 :
294 302 : if(!nPolygonCount)
295 : {
296 : // source is empty
297 0 : return aRetval;
298 : }
299 :
300 302 : 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 302 : if(bInside)
315 : {
316 616 : for(sal_uInt32 a(0L); a < nPolygonCount; a++)
317 : {
318 314 : const B2DPolyPolygon aClippedPolyPolygon(clipPolygonOnRange(rCandidate.getB2DPolygon(a), rRange, bInside, bStroke));
319 :
320 314 : if(aClippedPolyPolygon.count())
321 : {
322 308 : aRetval.append(aClippedPolyPolygon);
323 : }
324 314 : }
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 302 : return aRetval;
336 : }
337 :
338 5526 : B2DPolyPolygon clipPolyPolygonOnPolyPolygon(const B2DPolyPolygon& rCandidate, const B2DPolyPolygon& rClip, bool bInside, bool bStroke)
339 : {
340 5526 : B2DPolyPolygon aRetval;
341 :
342 5526 : if(rCandidate.count() && rClip.count())
343 : {
344 : // one or both are no rectangle - go the hard way and clip PolyPolygon
345 : // against PolyPolygon...
346 5526 : 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 376 : for(sal_uInt32 a(0); a < rCandidate.count(); a++)
352 : {
353 : // add cuts with clip to polygon, including bezier segments
354 368 : const B2DPolygon aCandidate(addPointsAtCuts(rCandidate.getB2DPolygon(a), rClip));
355 368 : const sal_uInt32 nPointCount(aCandidate.count());
356 368 : const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L);
357 736 : B2DCubicBezier aEdge;
358 736 : B2DPolygon aRun;
359 :
360 1472 : for(sal_uInt32 b(0); b < nEdgeCount; b++)
361 : {
362 1104 : aCandidate.getBezierSegment(b, aEdge);
363 1104 : const B2DPoint aTestPoint(aEdge.interpolatePoint(0.5));
364 1104 : const bool bIsInside(tools::isInside(rClip, aTestPoint) == bInside);
365 :
366 1104 : if(bIsInside)
367 : {
368 368 : if(!aRun.count())
369 : {
370 368 : aRun.append(aEdge.getStartPoint());
371 : }
372 :
373 368 : if(aEdge.isBezier())
374 : {
375 0 : aRun.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint());
376 : }
377 : else
378 : {
379 368 : aRun.append(aEdge.getEndPoint());
380 : }
381 : }
382 : else
383 : {
384 736 : if(aRun.count())
385 : {
386 368 : aRetval.append(aRun);
387 368 : aRun.clear();
388 : }
389 : }
390 1104 : }
391 :
392 368 : 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 368 : }
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 5518 : if(bInside)
418 : {
419 : // #i125349# detect if both given PolyPolygons are indeed ranges
420 5470 : bool bBothRectangle(false);
421 :
422 5470 : if(basegfx::tools::isRectangle(rCandidate))
423 : {
424 5445 : if(basegfx::tools::isRectangle(rClip))
425 : {
426 : // both are ranges
427 5147 : 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 298 : return clipPolyPolygonOnRange(rClip, rCandidate.getB2DRange(), bInside, bStroke);
436 : }
437 : }
438 25 : 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 5172 : if(bBothRectangle)
454 : {
455 : // both are rectangle
456 5147 : if(rCandidate.getB2DRange().equal(rClip.getB2DRange()))
457 : {
458 : // if both are equal -> no change
459 4 : return rCandidate;
460 : }
461 : else
462 : {
463 : // not equal -> create new intersection from both ranges,
464 : // but much cheaper based on the ranges
465 5143 : basegfx::B2DRange aIntersectionRange(rCandidate.getB2DRange());
466 :
467 5143 : aIntersectionRange.intersect(rClip.getB2DRange());
468 :
469 5143 : if(aIntersectionRange.isEmpty())
470 : {
471 : // no common IntersectionRange -> the clip will be empty
472 5076 : return B2DPolyPolygon();
473 : }
474 : else
475 : {
476 : // use common aIntersectionRange as result, convert
477 : // to expected tools::PolyPolygon form
478 : return basegfx::B2DPolyPolygon(
479 67 : basegfx::tools::createPolygonFromRect(aIntersectionRange));
480 : }
481 : }
482 : }
483 : }
484 :
485 : // area clipping
486 73 : 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 73 : aMergePolyPolygonA = solveCrossovers(aMergePolyPolygonA);
495 73 : aMergePolyPolygonA = stripNeutralPolygons(aMergePolyPolygonA);
496 73 : aMergePolyPolygonA = correctOrientations(aMergePolyPolygonA);
497 :
498 73 : if(!bInside)
499 : {
500 : // if we want to get the outside of the clip polygon, make
501 : // it a 'Hole' in topological sense
502 48 : aMergePolyPolygonA.flip();
503 : }
504 :
505 146 : B2DPolyPolygon aMergePolyPolygonB(rCandidate);
506 :
507 : // prepare 2nd source polygon in same way
508 73 : aMergePolyPolygonB = solveCrossovers(aMergePolyPolygonB);
509 73 : aMergePolyPolygonB = stripNeutralPolygons(aMergePolyPolygonB);
510 73 : 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 73 : aRetval.append(aMergePolyPolygonA);
516 73 : aRetval.append(aMergePolyPolygonB);
517 73 : 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 73 : aRetval = stripNeutralPolygons(aRetval);
526 146 : aRetval = stripDispensablePolygons(aRetval, bInside);
527 : }
528 : }
529 :
530 81 : return aRetval;
531 : }
532 :
533 392 : B2DPolyPolygon clipPolygonOnPolyPolygon(const B2DPolygon& rCandidate, const B2DPolyPolygon& rClip, bool bInside, bool bStroke)
534 : {
535 392 : B2DPolyPolygon aRetval;
536 :
537 392 : if(rCandidate.count() && rClip.count())
538 : {
539 392 : aRetval = clipPolyPolygonOnPolyPolygon(B2DPolyPolygon(rCandidate), rClip, bInside, bStroke);
540 : }
541 :
542 392 : 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 : ::basegfx::B2DPoint *curr;
590 : ::basegfx::B2DPoint *next;
591 :
592 0 : sal_uInt32 out_count=0;
593 :
594 : // process all the verts
595 0 : for(sal_uInt32 i=0; i<in_count; i++) {
596 :
597 : // vertices are relative to the coordinate
598 : // system defined by the rectangle.
599 0 : curr = &in_vertex[i];
600 0 : next = &in_vertex[(i+1)%in_count];
601 :
602 : // perform clipping judgement & mask against current plane.
603 0 : sal_uInt32 clip = pPlane->clipmask & ((getCohenSutherlandClipFlags(*curr,rR)<<4)|getCohenSutherlandClipFlags(*next,rR));
604 :
605 0 : if(clip==0) { // both verts are inside
606 0 : out_vertex[out_count++] = *next;
607 : }
608 0 : else if((clip&0x0f) && (clip&0xf0)) { // both verts are outside
609 : }
610 0 : else if((clip&0x0f) && (clip&0xf0)==0) { // curr is inside, next is outside
611 :
612 : // direction vector from 'current' to 'next', *not* normalized
613 : // to bring 't' into the [0<=x<=1] intervall.
614 0 : ::basegfx::B2DPoint dir((*next)-(*curr));
615 :
616 0 : double denominator = ( pPlane->nx*dir.getX() +
617 0 : pPlane->ny*dir.getY() );
618 0 : double numerator = ( pPlane->nx*curr->getX() +
619 0 : pPlane->ny*curr->getY() +
620 0 : pPlane->d );
621 0 : double t = -numerator/denominator;
622 :
623 : // calculate the actual point of intersection
624 0 : ::basegfx::B2DPoint intersection( curr->getX()+t*dir.getX(),
625 0 : curr->getY()+t*dir.getY() );
626 :
627 0 : out_vertex[out_count++] = intersection;
628 : }
629 0 : else if((clip&0x0f)==0 && (clip&0xf0)) { // curr is outside, next is inside
630 :
631 : // direction vector from 'current' to 'next', *not* normalized
632 : // to bring 't' into the [0<=x<=1] intervall.
633 0 : ::basegfx::B2DPoint dir((*next)-(*curr));
634 :
635 0 : double denominator = ( pPlane->nx*dir.getX() +
636 0 : pPlane->ny*dir.getY() );
637 0 : double numerator = ( pPlane->nx*curr->getX() +
638 0 : pPlane->ny*curr->getY() +
639 0 : pPlane->d );
640 0 : double t = -numerator/denominator;
641 :
642 : // calculate the actual point of intersection
643 0 : ::basegfx::B2DPoint intersection( curr->getX()+t*dir.getX(),
644 0 : curr->getY()+t*dir.getY() );
645 :
646 0 : out_vertex[out_count++] = intersection;
647 0 : out_vertex[out_count++] = *next;
648 : }
649 : }
650 :
651 0 : return out_count;
652 : }
653 :
654 0 : B2DPolygon clipTriangleListOnRange( const B2DPolygon& rCandidate,
655 : const B2DRange& rRange )
656 : {
657 0 : B2DPolygon aResult;
658 :
659 0 : if( !(rCandidate.count()%3) )
660 : {
661 0 : const int scissor_plane_count = 4;
662 :
663 : scissor_plane sp[scissor_plane_count];
664 :
665 0 : sp[0].nx = +1.0;
666 0 : sp[0].ny = +0.0;
667 0 : sp[0].d = -(rRange.getMinX());
668 0 : sp[0].clipmask = (RectClipFlags::LEFT << 4) | RectClipFlags::LEFT; // 0001 0001
669 0 : sp[1].nx = -1.0;
670 0 : sp[1].ny = +0.0;
671 0 : sp[1].d = +(rRange.getMaxX());
672 0 : sp[1].clipmask = (RectClipFlags::RIGHT << 4) | RectClipFlags::RIGHT; // 0010 0010
673 0 : sp[2].nx = +0.0;
674 0 : sp[2].ny = +1.0;
675 0 : sp[2].d = -(rRange.getMinY());
676 0 : sp[2].clipmask = (RectClipFlags::TOP << 4) | RectClipFlags::TOP; // 0100 0100
677 0 : sp[3].nx = +0.0;
678 0 : sp[3].ny = -1.0;
679 0 : sp[3].d = +(rRange.getMaxY());
680 0 : sp[3].clipmask = (RectClipFlags::BOTTOM << 4) | RectClipFlags::BOTTOM; // 1000 1000
681 :
682 : // retrieve the number of vertices of the triangulated polygon
683 0 : const sal_uInt32 nVertexCount = rCandidate.count();
684 :
685 0 : if(nVertexCount)
686 : {
687 : // Upper bound for the maximal number of vertices when intersecting an
688 : // axis-aligned rectangle with a triangle in E2
689 :
690 : // The rectangle and the triangle are in general position, and have 4 and 3
691 : // vertices, respectively.
692 :
693 : // Lemma: Since the rectangle is a convex polygon ( see
694 : // http://mathworld.wolfram.com/ConvexPolygon.html for a definition), and
695 : // has no holes, it follows that any straight line will intersect the
696 : // rectangle's border line at utmost two times (with the usual
697 : // tie-breaking rule, if the intersection exactly hits an already existing
698 : // rectangle vertex, that this intersection is only attributed to one of
699 : // the adjoining edges). Thus, having a rectangle intersected with
700 : // a half-plane (one side of a straight line denotes 'inside', the
701 : // other 'outside') will at utmost add _one_ vertex to the resulting
702 : // intersection polygon (adding two intersection vertices, and removing at
703 : // least one rectangle vertex):
704 :
705 : // *
706 : // +--+-----------------+
707 : // | * |
708 : // |* |
709 : // + |
710 : // *| |
711 : // * | |
712 : // +--------------------+
713 :
714 : // Proof: If the straight line intersects the rectangle two
715 : // times, it does so for distinct edges, i.e. the intersection has
716 : // minimally one of the rectangle's vertices on either side of the straight
717 : // line (but maybe more). Thus, the intersection with a half-plane has
718 : // minimally _one_ rectangle vertex removed from the resulting clip
719 : // polygon, and therefore, a clip against a half-plane has the net effect
720 : // of adding at utmost _one_ vertex to the resulting clip polygon.
721 :
722 : // Theorem: The intersection of a rectangle and a triangle results in a
723 : // polygon with at utmost 7 vertices.
724 :
725 : // Proof: The inside of the triangle can be described as the consecutive
726 : // intersection with three half-planes. Together with the lemma above, this
727 : // results in at utmost 3 additional vertices added to the already existing 4
728 : // rectangle vertices.
729 :
730 : // This upper bound is attained with the following example configuration:
731 :
732 : // *
733 : // ***
734 : // ** *
735 : // ** *
736 : // ** *
737 : // ** *
738 : // ** *
739 : // ** *
740 : // ** *
741 : // ** *
742 : // ** *
743 : // ----*2--------3 *
744 : // | ** |*
745 : // 1* 4
746 : // **| *|
747 : // ** | * |
748 : // **| * |
749 : // 7* * |
750 : // --*6-----5-----
751 : // ** *
752 : // **
753 :
754 : // As we need to scissor all triangles against the
755 : // output rectangle we employ an output buffer for the
756 : // resulting vertices. the question is how large this
757 : // buffer needs to be compared to the number of
758 : // incoming vertices. this buffer needs to hold at
759 : // most the number of original vertices times '7'. see
760 : // figure above for an example. scissoring triangles
761 : // with the cohen-sutherland line clipping algorithm
762 : // as implemented here will result in a triangle fan
763 : // which will be rendered as separate triangles to
764 : // avoid pipeline stalls for each scissored
765 : // triangle. creating separate triangles from a
766 : // triangle fan produces (n-2)*3 vertices where n is
767 : // the number of vertices of the original triangle
768 : // fan. for the maximum number of 7 vertices of
769 : // resulting triangle fans we therefore need 15 times
770 : // the number of original vertices.
771 :
772 : //const size_t nBufferSize = sizeof(vertex)*(nVertexCount*16);
773 : //vertex *pVertices = (vertex*)alloca(nBufferSize);
774 : //sal_uInt32 nNumOutput = 0;
775 :
776 : // we need to clip this triangle against the output rectangle
777 : // to ensure that the resulting texture coordinates are in
778 : // the valid range from [0<=st<=1]. under normal circustances
779 : // we could use the BORDERCOLOR renderstate but some cards
780 : // seem to ignore this feature.
781 0 : ::basegfx::B2DPoint stack[3];
782 0 : unsigned int clipflag = 0;
783 :
784 0 : for(sal_uInt32 nIndex=0; nIndex<nVertexCount; ++nIndex)
785 : {
786 : // rotate stack
787 0 : stack[0] = stack[1];
788 0 : stack[1] = stack[2];
789 0 : stack[2] = rCandidate.getB2DPoint(nIndex);
790 :
791 : // clipping judgement
792 0 : clipflag |= unsigned(!(rRange.isInside(stack[2])));
793 :
794 0 : if(nIndex > 1)
795 : {
796 : // consume vertices until a single separate triangle has been visited.
797 0 : if(!((nIndex+1)%3))
798 : {
799 : // if any of the last three vertices was outside
800 : // we need to scissor against the destination rectangle
801 0 : if(clipflag & 7)
802 : {
803 0 : ::basegfx::B2DPoint buf0[16];
804 0 : ::basegfx::B2DPoint buf1[16];
805 :
806 0 : sal_uInt32 vertex_count = 3;
807 :
808 : // clip against all 4 planes passing the result of
809 : // each plane as the input to the next using a double buffer
810 0 : vertex_count = scissorLineSegment(stack,vertex_count,buf1,&sp[0],rRange);
811 0 : vertex_count = scissorLineSegment(buf1,vertex_count,buf0,&sp[1],rRange);
812 0 : vertex_count = scissorLineSegment(buf0,vertex_count,buf1,&sp[2],rRange);
813 0 : vertex_count = scissorLineSegment(buf1,vertex_count,buf0,&sp[3],rRange);
814 :
815 0 : if(vertex_count >= 3)
816 : {
817 : // convert triangle fan back to triangle list.
818 0 : ::basegfx::B2DPoint v0(buf0[0]);
819 0 : ::basegfx::B2DPoint v1(buf0[1]);
820 0 : for(sal_uInt32 i=2; i<vertex_count; ++i)
821 : {
822 0 : ::basegfx::B2DPoint v2(buf0[i]);
823 0 : aResult.append(v0);
824 0 : aResult.append(v1);
825 0 : aResult.append(v2);
826 0 : v1 = v2;
827 0 : }
828 0 : }
829 : }
830 : else
831 : {
832 : // the last triangle has not been altered, simply copy to result
833 0 : for(sal_uInt32 i=0; i<3; ++i)
834 0 : aResult.append(stack[i]);
835 : }
836 : }
837 : }
838 :
839 0 : clipflag <<= 1;
840 0 : }
841 : }
842 : }
843 :
844 0 : return aResult;
845 : }
846 :
847 : } // end of namespace tools
848 : } // end of namespace basegfx
849 :
850 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
