1 /*************************************************************************
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 * Copyright 2008 by Sun Microsystems, Inc.
7 * OpenOffice.org - a multi-platform office productivity suite
9 * $RCSfile: b2dpolygonclipper.cxx,v $
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 //////////////////////////////////////////////////////////////////////////////
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.
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.
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.
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.
91 aRetval
.append(rCandidate
);
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
);
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
;
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
);
124 if(!aRun
.count() || !aRun
.getB2DPoint(aRun
.count() - 1).equal(aEdge
.getStartPoint()))
126 aRun
.append(aEdge
.getStartPoint());
131 aRun
.appendBezierSegment(aEdge
.getControlPointA(), aEdge
.getControlPointB(), aEdge
.getEndPoint());
135 aRun
.append(aEdge
.getEndPoint());
140 if(bStroke
&& aRun
.count())
142 aRetval
.append(aRun
);
152 // try to merge this last and first polygon; they may have been
153 // the former polygon's start/end point
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();
166 aRetval
.append(aRun
);
170 // set closed flag and correct last point (which is added double now).
171 closeWithGeometryChange(aRun
);
172 aRetval
.append(aRun
);
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
);
199 B2DPolyPolygon
clipPolygonOnRange(const B2DPolygon
& rCandidate
, const B2DRange
& rRange
, bool bInside
, bool bStroke
)
201 const sal_uInt32
nCount(rCandidate
.count());
202 B2DPolyPolygon aRetval
;
214 // nothing is inside an empty range
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
232 return B2DPolyPolygon(rCandidate
);
236 // nothing is outside, then
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
);
263 // against Y-Axis, lower value
264 if(1L == aRetval
.count())
266 aRetval
= clipPolygonOnParallelAxis(aRetval
.getB2DPolygon(0L), false, bInside
, rRange
.getMinX(), bStroke
);
270 aRetval
= clipPolyPolygonOnParallelAxis(aRetval
, false, bInside
, rRange
.getMinX(), bStroke
);
275 // against X-Axis, higher value
276 if(1L == aRetval
.count())
278 aRetval
= clipPolygonOnParallelAxis(aRetval
.getB2DPolygon(0L), true, !bInside
, rRange
.getMaxY(), bStroke
);
282 aRetval
= clipPolyPolygonOnParallelAxis(aRetval
, true, !bInside
, rRange
.getMaxY(), bStroke
);
287 // against Y-Axis, higher value
288 if(1L == aRetval
.count())
290 aRetval
= clipPolygonOnParallelAxis(aRetval
.getB2DPolygon(0L), false, !bInside
, rRange
.getMaxX(), bStroke
);
294 aRetval
= clipPolyPolygonOnParallelAxis(aRetval
, false, !bInside
, rRange
.getMaxX(), bStroke
);
303 B2DPolyPolygon
clipPolyPolygonOnRange(const B2DPolyPolygon
& rCandidate
, const B2DRange
& rRange
, bool bInside
, bool bStroke
)
305 const sal_uInt32
nPolygonCount(rCandidate
.count());
306 B2DPolyPolygon aRetval
;
318 // nothing is inside an empty range
323 // everything is outside an empty range
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
);
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
);
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
);
377 // if there is a result, it needs to be transformed back
378 aMatrixTransform
.invert();
379 aRetval
.transform(aMatrixTransform
);
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
);
411 // if there is a result, it needs to be transformed back
412 aMatrixTransform
.invert();
413 aRetval
.transform(aMatrixTransform
);
420 //////////////////////////////////////////////////////////////////////////////
422 B2DPolyPolygon
clipPolyPolygonOnPolyPolygon(const B2DPolyPolygon
& rCandidate
, const B2DPolyPolygon
& rClip
, bool bInside
, bool bStroke
)
424 B2DPolyPolygon aRetval
;
426 if(rCandidate
.count() && rClip
.count())
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
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
;
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
);
452 aRun
.append(aEdge
.getStartPoint());
457 aRun
.appendBezierSegment(aEdge
.getControlPointA(), aEdge
.getControlPointB(), aEdge
.getEndPoint());
461 aRun
.append(aEdge
.getEndPoint());
468 aRetval
.append(aRun
);
476 // try to merge this last and first polygon; they may have been
477 // the former polygon's start/end point
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();
490 aRetval
.append(aRun
);
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
);
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
);
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
);
558 //////////////////////////////////////////////////////////////////////////////
561 * let a plane be defined as
565 * and a ray be defined as
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() +
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() +
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
;
669 B2DPolygon
clipTriangleListOnRange( const B2DPolygon
& rCandidate
,
670 const B2DRange
& rRange
)
674 if( !(rCandidate
.count()%3) )
676 const int scissor_plane_count
= 4;
678 scissor_plane sp
[scissor_plane_count
];
682 sp
[0].d
= -(rRange
.getMinX());
683 sp
[0].clipmask
= (RectClipFlags::LEFT
<< 4) | RectClipFlags::LEFT
; // 0001 0001
686 sp
[1].d
= +(rRange
.getMaxX());
687 sp
[1].clipmask
= (RectClipFlags::RIGHT
<< 4) | RectClipFlags::RIGHT
; // 0010 0010
690 sp
[2].d
= -(rRange
.getMinY());
691 sp
[2].clipmask
= (RectClipFlags::TOP
<< 4) | RectClipFlags::TOP
; // 0100 0100
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();
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):
725 // +--+-----------------+
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:
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
)
812 stack
[2] = rCandidate
.getB2DPoint(nIndex
);
814 // clipping judgement
815 clipflag
|= !(rRange
.isInside(stack
[2]));
819 // consume vertices until a single seperate triangle has been visited.
822 // if any of the last three vertices was outside
823 // we need to scissor against the destination rectangle
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
]);
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
]);
870 //////////////////////////////////////////////////////////////////////////////
872 } // end of namespace tools
873 } // end of namespace basegfx
875 //////////////////////////////////////////////////////////////////////////////