merge the formfield patch from ooo-build
[ooovba.git] / basegfx / source / polygon / b2dpolygonclipper.cxx
blob9505cb983c302049981737634225ea6b70cabfe3
1 /*************************************************************************
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * Copyright 2008 by Sun Microsystems, Inc.
7 * OpenOffice.org - a multi-platform office productivity suite
9 * $RCSfile: b2dpolygonclipper.cxx,v $
10 * $Revision: 1.7 $
12 * This file is part of OpenOffice.org.
14 * OpenOffice.org is free software: you can redistribute it and/or modify
15 * it under the terms of the GNU Lesser General Public License version 3
16 * only, as published by the Free Software Foundation.
18 * OpenOffice.org is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 * GNU Lesser General Public License version 3 for more details
22 * (a copy is included in the LICENSE file that accompanied this code).
24 * You should have received a copy of the GNU Lesser General Public License
25 * version 3 along with OpenOffice.org. If not, see
26 * <http://www.openoffice.org/license.html>
27 * for a copy of the LGPLv3 License.
29 ************************************************************************/
31 // MARKER(update_precomp.py): autogen include statement, do not remove
32 #include "precompiled_basegfx.hxx"
33 #include <basegfx/polygon/b2dpolygonclipper.hxx>
34 #include <osl/diagnose.h>
35 #include <basegfx/polygon/b2dpolygontools.hxx>
36 #include <basegfx/numeric/ftools.hxx>
37 #include <basegfx/matrix/b2dhommatrix.hxx>
38 #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
39 #include <basegfx/polygon/b2dpolygoncutandtouch.hxx>
40 #include <basegfx/polygon/b2dpolypolygontools.hxx>
41 #include <basegfx/curve/b2dcubicbezier.hxx>
42 #include <basegfx/tools/rectcliptools.hxx>
44 //////////////////////////////////////////////////////////////////////////////
46 namespace basegfx
48 namespace tools
50 B2DPolyPolygon clipPolygonOnParallelAxis(const B2DPolygon& rCandidate, bool bParallelToXAxis, bool bAboveAxis, double fValueOnOtherAxis, bool bStroke)
52 B2DPolyPolygon aRetval;
54 if(rCandidate.count())
56 const B2DRange aCandidateRange(getRange(rCandidate));
58 if(bParallelToXAxis && fTools::moreOrEqual(aCandidateRange.getMinY(), fValueOnOtherAxis))
60 // completely above and on the clip line. also true for curves.
61 if(bAboveAxis)
63 // add completely
64 aRetval.append(rCandidate);
67 else if(bParallelToXAxis && fTools::lessOrEqual(aCandidateRange.getMaxY(), fValueOnOtherAxis))
69 // completely below and on the clip line. also true for curves.
70 if(!bAboveAxis)
72 // add completely
73 aRetval.append(rCandidate);
76 else if(!bParallelToXAxis && fTools::moreOrEqual(aCandidateRange.getMinX(), fValueOnOtherAxis))
78 // completely right of and on the clip line. also true for curves.
79 if(bAboveAxis)
81 // add completely
82 aRetval.append(rCandidate);
85 else if(!bParallelToXAxis && fTools::lessOrEqual(aCandidateRange.getMaxX(), fValueOnOtherAxis))
87 // completely left of and on the clip line. also true for curves.
88 if(!bAboveAxis)
90 // add completely
91 aRetval.append(rCandidate);
94 else
96 // add cuts with axis to polygon, including bezier segments
97 // Build edge to cut with. Make it a little big longer than needed for
98 // numerical stability. We want to cut against the edge seen as endless
99 // ray here, but addPointsAtCuts() will limit itself to the
100 // edge's range ]0.0 .. 1.0[.
101 const double fSmallExtension((aCandidateRange.getWidth() + aCandidateRange.getHeight()) * (0.5 * 0.1));
102 const B2DPoint aStart(
103 bParallelToXAxis ? aCandidateRange.getMinX() - fSmallExtension : fValueOnOtherAxis,
104 bParallelToXAxis ? fValueOnOtherAxis : aCandidateRange.getMinY() - fSmallExtension);
105 const B2DPoint aEnd(
106 bParallelToXAxis ? aCandidateRange.getMaxX() + fSmallExtension : fValueOnOtherAxis,
107 bParallelToXAxis ? fValueOnOtherAxis : aCandidateRange.getMaxY() + fSmallExtension);
108 const B2DPolygon aCandidate(addPointsAtCuts(rCandidate, aStart, aEnd));
109 const sal_uInt32 nPointCount(aCandidate.count());
110 const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L);
111 B2DCubicBezier aEdge;
112 B2DPolygon aRun;
114 for(sal_uInt32 a(0L); a < nEdgeCount; a++)
116 aCandidate.getBezierSegment(a, aEdge);
117 const B2DPoint aTestPoint(aEdge.interpolatePoint(0.5));
118 const bool bInside(bParallelToXAxis ?
119 fTools::moreOrEqual(aTestPoint.getY(), fValueOnOtherAxis) == bAboveAxis :
120 fTools::moreOrEqual(aTestPoint.getX(), fValueOnOtherAxis) == bAboveAxis);
122 if(bInside)
124 if(!aRun.count() || !aRun.getB2DPoint(aRun.count() - 1).equal(aEdge.getStartPoint()))
126 aRun.append(aEdge.getStartPoint());
129 if(aEdge.isBezier())
131 aRun.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint());
133 else
135 aRun.append(aEdge.getEndPoint());
138 else
140 if(bStroke && aRun.count())
142 aRetval.append(aRun);
143 aRun.clear();
148 if(aRun.count())
150 if(bStroke)
152 // try to merge this last and first polygon; they may have been
153 // the former polygon's start/end point
154 if(aRetval.count())
156 const B2DPolygon aStartPolygon(aRetval.getB2DPolygon(0));
158 if(aStartPolygon.count() && aStartPolygon.getB2DPoint(0).equal(aRun.getB2DPoint(aRun.count() - 1)))
160 // append start polygon to aRun, remove from result set
161 aRun.append(aStartPolygon); aRun.removeDoublePoints();
162 aRetval.remove(0);
166 aRetval.append(aRun);
168 else
170 // set closed flag and correct last point (which is added double now).
171 closeWithGeometryChange(aRun);
172 aRetval.append(aRun);
178 return aRetval;
181 B2DPolyPolygon clipPolyPolygonOnParallelAxis(const B2DPolyPolygon& rCandidate, bool bParallelToXAxis, bool bAboveAxis, double fValueOnOtherAxis, bool bStroke)
183 const sal_uInt32 nPolygonCount(rCandidate.count());
184 B2DPolyPolygon aRetval;
186 for(sal_uInt32 a(0L); a < nPolygonCount; a++)
188 const B2DPolyPolygon aClippedPolyPolygon(clipPolygonOnParallelAxis(rCandidate.getB2DPolygon(a), bParallelToXAxis, bAboveAxis, fValueOnOtherAxis, bStroke));
190 if(aClippedPolyPolygon.count())
192 aRetval.append(aClippedPolyPolygon);
196 return aRetval;
199 B2DPolyPolygon clipPolygonOnRange(const B2DPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke)
201 const sal_uInt32 nCount(rCandidate.count());
202 B2DPolyPolygon aRetval;
204 if(!nCount)
206 // source is empty
207 return aRetval;
210 if(rRange.isEmpty())
212 if(bInside)
214 // nothing is inside an empty range
215 return aRetval;
217 else
219 // everything is outside an empty range
220 return B2DPolyPolygon(rCandidate);
224 const B2DRange aCandidateRange(getRange(rCandidate));
226 if(rRange.isInside(aCandidateRange))
228 // candidate is completely inside given range
229 if(bInside)
231 // nothing to do
232 return B2DPolyPolygon(rCandidate);
234 else
236 // nothing is outside, then
237 return aRetval;
241 if(!bInside)
243 // cutting off the outer parts of filled polygons at parallell
244 // lines to the axes is only possible for the inner part, not for
245 // the outer part which means cutting a hole into the original polygon.
246 // This is because the inner part is a logical AND-operation of
247 // the four implied half-planes, but the outer part is not.
248 // It is possible for strokes, but with creating unnecessary extra
249 // cuts, so using clipPolygonOnPolyPolygon is better there, too.
250 // This needs to be done with the topology knowlegde and is unfurtunately
251 // more expensive, too.
252 const B2DPolygon aClip(createPolygonFromRect(rRange));
254 return clipPolygonOnPolyPolygon(rCandidate, B2DPolyPolygon(aClip), bInside, bStroke);
257 // clip against the four axes of the range
258 // against X-Axis, lower value
259 aRetval = clipPolygonOnParallelAxis(rCandidate, true, bInside, rRange.getMinY(), bStroke);
261 if(aRetval.count())
263 // against Y-Axis, lower value
264 if(1L == aRetval.count())
266 aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), false, bInside, rRange.getMinX(), bStroke);
268 else
270 aRetval = clipPolyPolygonOnParallelAxis(aRetval, false, bInside, rRange.getMinX(), bStroke);
273 if(aRetval.count())
275 // against X-Axis, higher value
276 if(1L == aRetval.count())
278 aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), true, !bInside, rRange.getMaxY(), bStroke);
280 else
282 aRetval = clipPolyPolygonOnParallelAxis(aRetval, true, !bInside, rRange.getMaxY(), bStroke);
285 if(aRetval.count())
287 // against Y-Axis, higher value
288 if(1L == aRetval.count())
290 aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), false, !bInside, rRange.getMaxX(), bStroke);
292 else
294 aRetval = clipPolyPolygonOnParallelAxis(aRetval, false, !bInside, rRange.getMaxX(), bStroke);
300 return aRetval;
303 B2DPolyPolygon clipPolyPolygonOnRange(const B2DPolyPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke)
305 const sal_uInt32 nPolygonCount(rCandidate.count());
306 B2DPolyPolygon aRetval;
308 if(!nPolygonCount)
310 // source is empty
311 return aRetval;
314 if(rRange.isEmpty())
316 if(bInside)
318 // nothing is inside an empty range
319 return aRetval;
321 else
323 // everything is outside an empty range
324 return rCandidate;
328 if(bInside)
330 for(sal_uInt32 a(0L); a < nPolygonCount; a++)
332 const B2DPolyPolygon aClippedPolyPolygon(clipPolygonOnRange(rCandidate.getB2DPolygon(a), rRange, bInside, bStroke));
334 if(aClippedPolyPolygon.count())
336 aRetval.append(aClippedPolyPolygon);
340 else
342 // for details, see comment in clipPolygonOnRange for the "cutting off
343 // the outer parts of filled polygons at parallell lines" explanations
344 const B2DPolygon aClip(createPolygonFromRect(rRange));
346 return clipPolyPolygonOnPolyPolygon(rCandidate, B2DPolyPolygon(aClip), bInside, bStroke);
349 return aRetval;
352 B2DPolyPolygon clipPolygonOnEdge(const B2DPolygon& rCandidate, const B2DPoint& rPointA, const B2DPoint& rPointB, bool bAbove, bool bStroke)
354 B2DPolyPolygon aRetval;
356 if(rPointA.equal(rPointB))
358 // edge has no length, return polygon
359 aRetval.append(rCandidate);
361 else if(rCandidate.count())
363 const B2DVector aEdge(rPointB - rPointA);
364 B2DHomMatrix aMatrixTransform;
365 B2DPolygon aCandidate(rCandidate);
367 // translate and rotate polygon so that given edge is on x axis
368 aMatrixTransform.translate(-rPointA.getX(), -rPointA.getY());
369 aMatrixTransform.rotate(-atan2(aEdge.getY(), aEdge.getX()));
370 aCandidate.transform(aMatrixTransform);
372 // call clip method on X-Axis
373 aRetval = clipPolygonOnParallelAxis(aCandidate, true, bAbove, 0.0, bStroke);
375 if(aRetval.count())
377 // if there is a result, it needs to be transformed back
378 aMatrixTransform.invert();
379 aRetval.transform(aMatrixTransform);
383 return aRetval;
386 B2DPolyPolygon clipPolyPolygonOnEdge(const B2DPolyPolygon& rCandidate, const B2DPoint& rPointA, const B2DPoint& rPointB, bool bAbove, bool bStroke)
388 B2DPolyPolygon aRetval;
390 if(rPointA.equal(rPointB))
392 // edge has no length, return polygon
393 aRetval = rCandidate;
395 else if(rCandidate.count())
397 const B2DVector aEdge(rPointB - rPointA);
398 B2DHomMatrix aMatrixTransform;
399 B2DPolyPolygon aCandidate(rCandidate);
401 // translate and rotate polygon so that given edge is on x axis
402 aMatrixTransform.translate(-rPointA.getX(), -rPointA.getY());
403 aMatrixTransform.rotate(-atan2(aEdge.getY(), aEdge.getX()));
404 aCandidate.transform(aMatrixTransform);
406 // call clip method on X-Axis
407 aRetval = clipPolyPolygonOnParallelAxis(aCandidate, true, bAbove, 0.0, bStroke);
409 if(aRetval.count())
411 // if there is a result, it needs to be transformed back
412 aMatrixTransform.invert();
413 aRetval.transform(aMatrixTransform);
417 return aRetval;
420 //////////////////////////////////////////////////////////////////////////////
422 B2DPolyPolygon clipPolyPolygonOnPolyPolygon(const B2DPolyPolygon& rCandidate, const B2DPolyPolygon& rClip, bool bInside, bool bStroke)
424 B2DPolyPolygon aRetval;
426 if(rCandidate.count() && rClip.count())
428 if(bStroke)
430 // line clipping, create line snippets by first adding all cut points and
431 // then marching along the edges and detecting if they are inside or outside
432 // the clip polygon
433 for(sal_uInt32 a(0); a < rCandidate.count(); a++)
435 // add cuts with clip to polygon, including bezier segments
436 const B2DPolygon aCandidate(addPointsAtCuts(rCandidate.getB2DPolygon(a), rClip));
437 const sal_uInt32 nPointCount(aCandidate.count());
438 const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L);
439 B2DCubicBezier aEdge;
440 B2DPolygon aRun;
442 for(sal_uInt32 b(0); b < nEdgeCount; b++)
444 aCandidate.getBezierSegment(b, aEdge);
445 const B2DPoint aTestPoint(aEdge.interpolatePoint(0.5));
446 const bool bIsInside(tools::isInside(rClip, aTestPoint) == bInside);
448 if(bIsInside)
450 if(!aRun.count())
452 aRun.append(aEdge.getStartPoint());
455 if(aEdge.isBezier())
457 aRun.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint());
459 else
461 aRun.append(aEdge.getEndPoint());
464 else
466 if(aRun.count())
468 aRetval.append(aRun);
469 aRun.clear();
474 if(aRun.count())
476 // try to merge this last and first polygon; they may have been
477 // the former polygon's start/end point
478 if(aRetval.count())
480 const B2DPolygon aStartPolygon(aRetval.getB2DPolygon(0));
482 if(aStartPolygon.count() && aStartPolygon.getB2DPoint(0).equal(aRun.getB2DPoint(aRun.count() - 1)))
484 // append start polygon to aRun, remove from result set
485 aRun.append(aStartPolygon); aRun.removeDoublePoints();
486 aRetval.remove(0);
490 aRetval.append(aRun);
494 else
496 // area clipping
497 B2DPolyPolygon aMergePolyPolygonA(rClip);
499 // First solve all polygon-self and polygon-polygon intersections.
500 // Also get rid of some not-needed polygons (neutral, no area -> when
501 // no intersections, these are tubes).
502 // Now it is possible to correct the orientations in the cut-free
503 // polygons to values corresponding to painting the PolyPolygon with
504 // a XOR-WindingRule.
505 aMergePolyPolygonA = solveCrossovers(aMergePolyPolygonA);
506 aMergePolyPolygonA = stripNeutralPolygons(aMergePolyPolygonA);
507 aMergePolyPolygonA = correctOrientations(aMergePolyPolygonA);
509 if(!bInside)
511 // if we want to get the outside of the clip polygon, make
512 // it a 'Hole' in topological sense
513 aMergePolyPolygonA.flip();
516 B2DPolyPolygon aMergePolyPolygonB(rCandidate);
518 // prepare 2nd source polygon in same way
519 aMergePolyPolygonB = solveCrossovers(aMergePolyPolygonB);
520 aMergePolyPolygonB = stripNeutralPolygons(aMergePolyPolygonB);
521 aMergePolyPolygonB = correctOrientations(aMergePolyPolygonB);
523 // to clip against each other, concatenate and solve all
524 // polygon-polygon crossovers. polygon-self do not need to
525 // be solved again, they were solved in the preparation.
526 aRetval.append(aMergePolyPolygonA);
527 aRetval.append(aMergePolyPolygonB);
528 aRetval = solveCrossovers(aRetval);
530 // now remove neutral polygons (closed, but no area). In a last
531 // step throw away all polygons which have a depth of less than 1
532 // which means there was no logical AND at their position. For the
533 // not-inside solution, the clip was flipped to define it as 'Hole',
534 // so the removal rule is different here; remove all with a depth
535 // of less than 0 (aka holes).
536 aRetval = stripNeutralPolygons(aRetval);
537 aRetval = stripDispensablePolygons(aRetval, bInside);
541 return aRetval;
544 //////////////////////////////////////////////////////////////////////////////
546 B2DPolyPolygon clipPolygonOnPolyPolygon(const B2DPolygon& rCandidate, const B2DPolyPolygon& rClip, bool bInside, bool bStroke)
548 B2DPolyPolygon aRetval;
550 if(rCandidate.count() && rClip.count())
552 aRetval = clipPolyPolygonOnPolyPolygon(B2DPolyPolygon(rCandidate), rClip, bInside, bStroke);
555 return aRetval;
558 //////////////////////////////////////////////////////////////////////////////
561 * let a plane be defined as
563 * v.n+d=0
565 * and a ray be defined as
567 * a+(b-a)*t=0
569 * substitute and rearranging yields
571 * t = -(a.n+d)/(n.(b-a))
573 * if the denominator is zero, the line is either
574 * contained in the plane or parallel to the plane.
575 * in either case, there is no intersection.
576 * if numerator and denominator are both zero, the
577 * ray is contained in the plane.
580 struct scissor_plane {
581 double nx,ny; // plane normal
582 double d; // [-] minimum distance from origin
583 sal_uInt32 clipmask; // clipping mask, e.g. 1000 1000
588 * polygon clipping rules (straight out of Foley and Van Dam)
589 * ===========================================================
590 * current |next |emit
591 * ____________________________________
592 * inside |inside |next
593 * inside |outside |intersect with clip plane
594 * outside |outside |nothing
595 * outside |inside |intersect with clip plane follwed by next
598 sal_uInt32 scissorLineSegment( ::basegfx::B2DPoint *in_vertex, // input buffer
599 sal_uInt32 in_count, // number of verts in input buffer
600 ::basegfx::B2DPoint *out_vertex, // output buffer
601 scissor_plane *pPlane, // scissoring plane
602 const ::basegfx::B2DRectangle &rR ) // clipping rectangle
604 ::basegfx::B2DPoint *curr;
605 ::basegfx::B2DPoint *next;
607 sal_uInt32 out_count=0;
609 // process all the verts
610 for(sal_uInt32 i=0; i<in_count; i++) {
612 // vertices are relative to the coordinate
613 // system defined by the rectangle.
614 curr = &in_vertex[i];
615 next = &in_vertex[(i+1)%in_count];
617 // perform clipping judgement & mask against current plane.
618 sal_uInt32 clip = pPlane->clipmask & ((getCohenSutherlandClipFlags(*curr,rR)<<4)|getCohenSutherlandClipFlags(*next,rR));
620 if(clip==0) { // both verts are inside
621 out_vertex[out_count++] = *next;
623 else if((clip&0x0f) && (clip&0xf0)) { // both verts are outside
625 else if((clip&0x0f) && (clip&0xf0)==0) { // curr is inside, next is outside
627 // direction vector from 'current' to 'next', *not* normalized
628 // to bring 't' into the [0<=x<=1] intervall.
629 ::basegfx::B2DPoint dir((*next)-(*curr));
631 double denominator = ( pPlane->nx*dir.getX() +
632 pPlane->ny*dir.getY() );
633 double numerator = ( pPlane->nx*curr->getX() +
634 pPlane->ny*curr->getY() +
635 pPlane->d );
636 double t = -numerator/denominator;
638 // calculate the actual point of intersection
639 ::basegfx::B2DPoint intersection( curr->getX()+t*dir.getX(),
640 curr->getY()+t*dir.getY() );
642 out_vertex[out_count++] = intersection;
644 else if((clip&0x0f)==0 && (clip&0xf0)) { // curr is outside, next is inside
646 // direction vector from 'current' to 'next', *not* normalized
647 // to bring 't' into the [0<=x<=1] intervall.
648 ::basegfx::B2DPoint dir((*next)-(*curr));
650 double denominator = ( pPlane->nx*dir.getX() +
651 pPlane->ny*dir.getY() );
652 double numerator = ( pPlane->nx*curr->getX() +
653 pPlane->ny*curr->getY() +
654 pPlane->d );
655 double t = -numerator/denominator;
657 // calculate the actual point of intersection
658 ::basegfx::B2DPoint intersection( curr->getX()+t*dir.getX(),
659 curr->getY()+t*dir.getY() );
661 out_vertex[out_count++] = intersection;
662 out_vertex[out_count++] = *next;
666 return out_count;
669 B2DPolygon clipTriangleListOnRange( const B2DPolygon& rCandidate,
670 const B2DRange& rRange )
672 B2DPolygon aResult;
674 if( !(rCandidate.count()%3) )
676 const int scissor_plane_count = 4;
678 scissor_plane sp[scissor_plane_count];
680 sp[0].nx = +1.0;
681 sp[0].ny = +0.0;
682 sp[0].d = -(rRange.getMinX());
683 sp[0].clipmask = (RectClipFlags::LEFT << 4) | RectClipFlags::LEFT; // 0001 0001
684 sp[1].nx = -1.0;
685 sp[1].ny = +0.0;
686 sp[1].d = +(rRange.getMaxX());
687 sp[1].clipmask = (RectClipFlags::RIGHT << 4) | RectClipFlags::RIGHT; // 0010 0010
688 sp[2].nx = +0.0;
689 sp[2].ny = +1.0;
690 sp[2].d = -(rRange.getMinY());
691 sp[2].clipmask = (RectClipFlags::TOP << 4) | RectClipFlags::TOP; // 0100 0100
692 sp[3].nx = +0.0;
693 sp[3].ny = -1.0;
694 sp[3].d = +(rRange.getMaxY());
695 sp[3].clipmask = (RectClipFlags::BOTTOM << 4) | RectClipFlags::BOTTOM; // 1000 1000
697 // retrieve the number of vertices of the triangulated polygon
698 const sal_uInt32 nVertexCount = rCandidate.count();
700 if(nVertexCount)
702 ////////////////////////////////////////////////////////////////////////
703 ////////////////////////////////////////////////////////////////////////
704 ////////////////////////////////////////////////////////////////////////
706 // Upper bound for the maximal number of vertices when intersecting an
707 // axis-aligned rectangle with a triangle in E2
709 // The rectangle and the triangle are in general position, and have 4 and 3
710 // vertices, respectively.
712 // Lemma: Since the rectangle is a convex polygon ( see
713 // http://mathworld.wolfram.com/ConvexPolygon.html for a definition), and
714 // has no holes, it follows that any straight line will intersect the
715 // rectangle's border line at utmost two times (with the usual
716 // tie-breaking rule, if the intersection exactly hits an already existing
717 // rectangle vertex, that this intersection is only attributed to one of
718 // the adjoining edges). Thus, having a rectangle intersected with
719 // a half-plane (one side of a straight line denotes 'inside', the
720 // other 'outside') will at utmost add _one_ vertex to the resulting
721 // intersection polygon (adding two intersection vertices, and removing at
722 // least one rectangle vertex):
724 // *
725 // +--+-----------------+
726 // | * |
727 // |* |
728 // + |
729 // *| |
730 // * | |
731 // +--------------------+
733 // Proof: If the straight line intersects the rectangle two
734 // times, it does so for distinct edges, i.e. the intersection has
735 // minimally one of the rectangle's vertices on either side of the straight
736 // line (but maybe more). Thus, the intersection with a half-plane has
737 // minimally _one_ rectangle vertex removed from the resulting clip
738 // polygon, and therefore, a clip against a half-plane has the net effect
739 // of adding at utmost _one_ vertex to the resulting clip polygon.
741 // Theorem: The intersection of a rectangle and a triangle results in a
742 // polygon with at utmost 7 vertices.
744 // Proof: The inside of the triangle can be described as the consecutive
745 // intersection with three half-planes. Together with the lemma above, this
746 // results in at utmost 3 additional vertices added to the already existing 4
747 // rectangle vertices.
749 // This upper bound is attained with the following example configuration:
751 // *
752 // ***
753 // ** *
754 // ** *
755 // ** *
756 // ** *
757 // ** *
758 // ** *
759 // ** *
760 // ** *
761 // ** *
762 // ----*2--------3 *
763 // | ** |*
764 // 1* 4
765 // **| *|
766 // ** | * |
767 // **| * |
768 // 7* * |
769 // --*6-----5-----
770 // ** *
771 // **
773 // As we need to scissor all triangles against the
774 // output rectangle we employ an output buffer for the
775 // resulting vertices. the question is how large this
776 // buffer needs to be compared to the number of
777 // incoming vertices. this buffer needs to hold at
778 // most the number of original vertices times '7'. see
779 // figure above for an example. scissoring triangles
780 // with the cohen-sutherland line clipping algorithm
781 // as implemented here will result in a triangle fan
782 // which will be rendered as separate triangles to
783 // avoid pipeline stalls for each scissored
784 // triangle. creating separate triangles from a
785 // triangle fan produces (n-2)*3 vertices where n is
786 // the number of vertices of the original triangle
787 // fan. for the maximum number of 7 vertices of
788 // resulting triangle fans we therefore need 15 times
789 // the number of original vertices.
791 ////////////////////////////////////////////////////////////////////////
792 ////////////////////////////////////////////////////////////////////////
793 ////////////////////////////////////////////////////////////////////////
795 //const size_t nBufferSize = sizeof(vertex)*(nVertexCount*16);
796 //vertex *pVertices = (vertex*)alloca(nBufferSize);
797 //sal_uInt32 nNumOutput = 0;
799 // we need to clip this triangle against the output rectangle
800 // to ensure that the resulting texture coordinates are in
801 // the valid range from [0<=st<=1]. under normal circustances
802 // we could use the BORDERCOLOR renderstate but some cards
803 // seem to ignore this feature.
804 ::basegfx::B2DPoint stack[3];
805 unsigned int clipflag = 0;
807 for(sal_uInt32 nIndex=0; nIndex<nVertexCount; ++nIndex)
809 // rotate stack
810 stack[0] = stack[1];
811 stack[1] = stack[2];
812 stack[2] = rCandidate.getB2DPoint(nIndex);
814 // clipping judgement
815 clipflag |= !(rRange.isInside(stack[2]));
817 if(nIndex > 1)
819 // consume vertices until a single seperate triangle has been visited.
820 if(!((nIndex+1)%3))
822 // if any of the last three vertices was outside
823 // we need to scissor against the destination rectangle
824 if(clipflag & 7)
826 ::basegfx::B2DPoint buf0[16];
827 ::basegfx::B2DPoint buf1[16];
829 sal_uInt32 vertex_count = 3;
831 // clip against all 4 planes passing the result of
832 // each plane as the input to the next using a double buffer
833 vertex_count = scissorLineSegment(stack,vertex_count,buf1,&sp[0],rRange);
834 vertex_count = scissorLineSegment(buf1,vertex_count,buf0,&sp[1],rRange);
835 vertex_count = scissorLineSegment(buf0,vertex_count,buf1,&sp[2],rRange);
836 vertex_count = scissorLineSegment(buf1,vertex_count,buf0,&sp[3],rRange);
838 if(vertex_count >= 3)
840 // convert triangle fan back to triangle list.
841 ::basegfx::B2DPoint v0(buf0[0]);
842 ::basegfx::B2DPoint v1(buf0[1]);
843 for(sal_uInt32 i=2; i<vertex_count; ++i)
845 ::basegfx::B2DPoint v2(buf0[i]);
846 aResult.append(v0);
847 aResult.append(v1);
848 aResult.append(v2);
849 v1 = v2;
853 else
855 // the last triangle has not been altered, simply copy to result
856 for(sal_uInt32 i=0; i<3; ++i)
857 aResult.append(stack[i]);
862 clipflag <<= 1;
867 return aResult;
870 //////////////////////////////////////////////////////////////////////////////
872 } // end of namespace tools
873 } // end of namespace basegfx
875 //////////////////////////////////////////////////////////////////////////////
877 // eof