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