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