xref: /AOO41X/main/basegfx/source/polygon/b2dpolygonclipper.cxx (revision cdf0e10c4e3984b49a9502b011690b615761d4a3)

/*************************************************************************
 *
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * Copyright 2000, 2010 Oracle and/or its affiliates.
 *
 * OpenOffice.org - a multi-platform office productivity suite
 *
 * This file is part of OpenOffice.org.
 *
 * OpenOffice.org is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License version 3
 * only, as published by the Free Software Foundation.
 *
 * OpenOffice.org is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License version 3 for more details
 * (a copy is included in the LICENSE file that accompanied this code).
 *
 * You should have received a copy of the GNU Lesser General Public License
 * version 3 along with OpenOffice.org.  If not, see
 * <http://www.openoffice.org/license.html>
 * for a copy of the LGPLv3 License.
 *
 ************************************************************************/

// MARKER(update_precomp.py): autogen include statement, do not remove
#include "precompiled_basegfx.hxx"
#include <basegfx/polygon/b2dpolygonclipper.hxx>
#include <osl/diagnose.h>
#include <basegfx/polygon/b2dpolygontools.hxx>
#include <basegfx/numeric/ftools.hxx>
#include <basegfx/matrix/b2dhommatrix.hxx>
#include <basegfx/polygon/b2dpolypolygoncutter.hxx>
#include <basegfx/polygon/b2dpolygoncutandtouch.hxx>
#include <basegfx/polygon/b2dpolypolygontools.hxx>
#include <basegfx/curve/b2dcubicbezier.hxx>
#include <basegfx/tools/rectcliptools.hxx>
#include <basegfx/matrix/b2dhommatrixtools.hxx>

//////////////////////////////////////////////////////////////////////////////

namespace basegfx
{
	namespace tools
	{
		B2DPolyPolygon clipPolygonOnParallelAxis(const B2DPolygon& rCandidate, bool bParallelToXAxis, bool bAboveAxis, double fValueOnOtherAxis, bool bStroke)
		{
			B2DPolyPolygon aRetval;

			if(rCandidate.count())
			{
				const B2DRange aCandidateRange(getRange(rCandidate));

				if(bParallelToXAxis && fTools::moreOrEqual(aCandidateRange.getMinY(), fValueOnOtherAxis))
				{
					// completely above and on the clip line. also true for curves.
					if(bAboveAxis)
					{
						// add completely
						aRetval.append(rCandidate);
					}
				}
				else if(bParallelToXAxis && fTools::lessOrEqual(aCandidateRange.getMaxY(), fValueOnOtherAxis))
				{
					// completely below and on the clip line. also true for curves.
					if(!bAboveAxis)
					{
						// add completely
						aRetval.append(rCandidate);
					}
				}
				else if(!bParallelToXAxis && fTools::moreOrEqual(aCandidateRange.getMinX(), fValueOnOtherAxis))
				{
					// completely right of and on the clip line. also true for curves.
					if(bAboveAxis)
					{
						// add completely
						aRetval.append(rCandidate);
					}
				}
				else if(!bParallelToXAxis && fTools::lessOrEqual(aCandidateRange.getMaxX(), fValueOnOtherAxis))
				{
					// completely left of and on the clip line. also true for curves.
					if(!bAboveAxis)
					{
						// add completely
						aRetval.append(rCandidate);
					}
				}
				else
				{
                    // add cuts with axis to polygon, including bezier segments
                    // Build edge to cut with. Make it a little big longer than needed for
                    // numerical stability. We want to cut against the edge seen as endless
                    // ray here, but addPointsAtCuts() will limit itself to the
                    // edge's range ]0.0 .. 1.0[.
                    const double fSmallExtension((aCandidateRange.getWidth() + aCandidateRange.getHeight()) * (0.5 * 0.1));
                    const B2DPoint aStart(
                        bParallelToXAxis ? aCandidateRange.getMinX() - fSmallExtension : fValueOnOtherAxis,
                        bParallelToXAxis ? fValueOnOtherAxis : aCandidateRange.getMinY() - fSmallExtension);
                    const B2DPoint aEnd(
                        bParallelToXAxis ? aCandidateRange.getMaxX() + fSmallExtension : fValueOnOtherAxis,
                        bParallelToXAxis ? fValueOnOtherAxis : aCandidateRange.getMaxY() + fSmallExtension);
                    const B2DPolygon aCandidate(addPointsAtCuts(rCandidate, aStart, aEnd));
    			    const sal_uInt32 nPointCount(aCandidate.count());
                    const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L);
                    B2DCubicBezier aEdge;
                    B2DPolygon aRun;

                    for(sal_uInt32 a(0L); a < nEdgeCount; a++)
                    {
                        aCandidate.getBezierSegment(a, aEdge);
                        const B2DPoint aTestPoint(aEdge.interpolatePoint(0.5));
			            const bool bInside(bParallelToXAxis ?
				            fTools::moreOrEqual(aTestPoint.getY(), fValueOnOtherAxis) == bAboveAxis :
				            fTools::moreOrEqual(aTestPoint.getX(), fValueOnOtherAxis) == bAboveAxis);

						if(bInside)
						{
							if(!aRun.count() || !aRun.getB2DPoint(aRun.count() - 1).equal(aEdge.getStartPoint()))
							{
								aRun.append(aEdge.getStartPoint());
							}

							if(aEdge.isBezier())
							{
								aRun.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint());
							}
							else
							{
								aRun.append(aEdge.getEndPoint());
							}
						}
						else
						{
                            if(bStroke && aRun.count())
                            {
								aRetval.append(aRun);
								aRun.clear();
                            }
						}
                    }

                    if(aRun.count())
					{
                        if(bStroke)
                        {
                            // try to merge this last and first polygon; they may have been
                            // the former polygon's start/end point
                            if(aRetval.count())
                            {
                                const B2DPolygon aStartPolygon(aRetval.getB2DPolygon(0));

                                if(aStartPolygon.count() && aStartPolygon.getB2DPoint(0).equal(aRun.getB2DPoint(aRun.count() - 1)))
                                {
                                    // append start polygon to aRun, remove from result set
                                    aRun.append(aStartPolygon); aRun.removeDoublePoints();
                                    aRetval.remove(0);
                                }
                            }

							aRetval.append(aRun);
                        }
                        else
                        {
			                // set closed flag and correct last point (which is added double now).
			                closeWithGeometryChange(aRun);
                            aRetval.append(aRun);
                        }
					}
				}
			}

			return aRetval;
		}

		B2DPolyPolygon clipPolyPolygonOnParallelAxis(const B2DPolyPolygon& rCandidate, bool bParallelToXAxis, bool bAboveAxis, double fValueOnOtherAxis, bool bStroke)
		{
			const sal_uInt32 nPolygonCount(rCandidate.count());
			B2DPolyPolygon aRetval;

			for(sal_uInt32 a(0L); a < nPolygonCount; a++)
			{
				const B2DPolyPolygon aClippedPolyPolygon(clipPolygonOnParallelAxis(rCandidate.getB2DPolygon(a), bParallelToXAxis, bAboveAxis, fValueOnOtherAxis, bStroke));

                if(aClippedPolyPolygon.count())
                {
    				aRetval.append(aClippedPolyPolygon);
                }
			}

			return aRetval;
		}

		B2DPolyPolygon clipPolygonOnRange(const B2DPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke)
		{
            const sal_uInt32 nCount(rCandidate.count());
			B2DPolyPolygon aRetval;

            if(!nCount)
            {
                // source is empty
                return aRetval;
            }

            if(rRange.isEmpty())
            {
                if(bInside)
                {
                    // nothing is inside an empty range
                    return aRetval;
                }
                else
                {
                    // everything is outside an empty range
                    return B2DPolyPolygon(rCandidate);
                }
            }

			const B2DRange aCandidateRange(getRange(rCandidate));

			if(rRange.isInside(aCandidateRange))
			{
  				// candidate is completely inside given range
				if(bInside)
				{
    				// nothing to do
					return B2DPolyPolygon(rCandidate);
				}
                else
                {
                    // nothing is outside, then
                    return aRetval;
                }
			}

            if(!bInside)
            {
                // cutting off the outer parts of filled polygons at parallell
                // lines to the axes is only possible for the inner part, not for
                // the outer part which means cutting a hole into the original polygon.
                // This is because the inner part is a logical AND-operation of
                // the four implied half-planes, but the outer part is not.
                // It is possible for strokes, but with creating unnecessary extra
                // cuts, so using clipPolygonOnPolyPolygon is better there, too.
                // This needs to be done with the topology knowlegde and is unfurtunately
                // more expensive, too.
        		const B2DPolygon aClip(createPolygonFromRect(rRange));

                return clipPolygonOnPolyPolygon(rCandidate, B2DPolyPolygon(aClip), bInside, bStroke);
            }

			// clip against the four axes of the range
			// against X-Axis, lower value
			aRetval = clipPolygonOnParallelAxis(rCandidate, true, bInside, rRange.getMinY(), bStroke);

			if(aRetval.count())
			{
				// against Y-Axis, lower value
				if(1L == aRetval.count())
				{
					aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), false, bInside, rRange.getMinX(), bStroke);
				}
				else
				{
					aRetval = clipPolyPolygonOnParallelAxis(aRetval, false, bInside, rRange.getMinX(), bStroke);
				}

				if(aRetval.count())
				{
					// against X-Axis, higher value
					if(1L == aRetval.count())
					{
						aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), true, !bInside, rRange.getMaxY(), bStroke);
					}
					else
					{
						aRetval = clipPolyPolygonOnParallelAxis(aRetval, true, !bInside, rRange.getMaxY(), bStroke);
					}

					if(aRetval.count())
					{
						// against Y-Axis, higher value
						if(1L == aRetval.count())
						{
							aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), false, !bInside, rRange.getMaxX(), bStroke);
						}
						else
						{
							aRetval = clipPolyPolygonOnParallelAxis(aRetval, false, !bInside, rRange.getMaxX(), bStroke);
						}
					}
				}
			}

			return aRetval;
		}

		B2DPolyPolygon clipPolyPolygonOnRange(const B2DPolyPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke)
		{
			const sal_uInt32 nPolygonCount(rCandidate.count());
			B2DPolyPolygon aRetval;

            if(!nPolygonCount)
            {
                // source is empty
                return aRetval;
            }

            if(rRange.isEmpty())
            {
                if(bInside)
                {
                    // nothing is inside an empty range
                    return aRetval;
                }
                else
                {
                    // everything is outside an empty range
                    return rCandidate;
                }
            }

            if(bInside)
            {
			    for(sal_uInt32 a(0L); a < nPolygonCount; a++)
			    {
				    const B2DPolyPolygon aClippedPolyPolygon(clipPolygonOnRange(rCandidate.getB2DPolygon(a), rRange, bInside, bStroke));

                    if(aClippedPolyPolygon.count())
                    {
    				    aRetval.append(aClippedPolyPolygon);
                    }
			    }
            }
            else
            {
                // for details, see comment in clipPolygonOnRange for the "cutting off
                // the outer parts of filled polygons at parallell lines" explanations
        		const B2DPolygon aClip(createPolygonFromRect(rRange));

                return clipPolyPolygonOnPolyPolygon(rCandidate, B2DPolyPolygon(aClip), bInside, bStroke);
            }

			return aRetval;
		}

		B2DPolyPolygon clipPolygonOnEdge(const B2DPolygon& rCandidate, const B2DPoint& rPointA, const B2DPoint& rPointB, bool bAbove, bool bStroke)
		{
			B2DPolyPolygon aRetval;

			if(rPointA.equal(rPointB))
			{
				// edge has no length, return polygon
				aRetval.append(rCandidate);
			}
			else if(rCandidate.count())
			{
				const B2DVector aEdge(rPointB - rPointA);
				B2DPolygon aCandidate(rCandidate);

				// translate and rotate polygon so that given edge is on x axis
                B2DHomMatrix aMatrixTransform(basegfx::tools::createTranslateB2DHomMatrix(-rPointA.getX(), -rPointA.getY()));
				aMatrixTransform.rotate(-atan2(aEdge.getY(), aEdge.getX()));
				aCandidate.transform(aMatrixTransform);

				// call clip method on X-Axis
				aRetval = clipPolygonOnParallelAxis(aCandidate, true, bAbove, 0.0, bStroke);

				if(aRetval.count())
				{
					// if there is a result, it needs to be transformed back
					aMatrixTransform.invert();
					aRetval.transform(aMatrixTransform);
				}
			}

			return aRetval;
		}

		B2DPolyPolygon clipPolyPolygonOnEdge(const B2DPolyPolygon& rCandidate, const B2DPoint& rPointA, const B2DPoint& rPointB, bool bAbove, bool bStroke)
		{
			B2DPolyPolygon aRetval;

			if(rPointA.equal(rPointB))
			{
				// edge has no length, return polygon
				aRetval = rCandidate;
			}
			else if(rCandidate.count())
			{
				const B2DVector aEdge(rPointB - rPointA);
				B2DPolyPolygon aCandidate(rCandidate);

				// translate and rotate polygon so that given edge is on x axis
                B2DHomMatrix aMatrixTransform(basegfx::tools::createTranslateB2DHomMatrix(-rPointA.getX(), -rPointA.getY()));
				aMatrixTransform.rotate(-atan2(aEdge.getY(), aEdge.getX()));
				aCandidate.transform(aMatrixTransform);

				// call clip method on X-Axis
				aRetval = clipPolyPolygonOnParallelAxis(aCandidate, true, bAbove, 0.0, bStroke);

				if(aRetval.count())
				{
					// if there is a result, it needs to be transformed back
					aMatrixTransform.invert();
					aRetval.transform(aMatrixTransform);
				}
			}

			return aRetval;
		}

		//////////////////////////////////////////////////////////////////////////////

		B2DPolyPolygon clipPolyPolygonOnPolyPolygon(const B2DPolyPolygon& rCandidate, const B2DPolyPolygon& rClip, bool bInside, bool bStroke)
		{
			B2DPolyPolygon aRetval;

			if(rCandidate.count() && rClip.count())
			{
				if(bStroke)
				{
					// line clipping, create line snippets by first adding all cut points and
                    // then marching along the edges and detecting if they are inside or outside
                    // the clip polygon
					for(sal_uInt32 a(0); a < rCandidate.count(); a++)
					{
                        // add cuts with clip to polygon, including bezier segments
                        const B2DPolygon aCandidate(addPointsAtCuts(rCandidate.getB2DPolygon(a), rClip));
    			        const sal_uInt32 nPointCount(aCandidate.count());
                        const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L);
                        B2DCubicBezier aEdge;
                        B2DPolygon aRun;

                        for(sal_uInt32 b(0); b < nEdgeCount; b++)
                        {
                            aCandidate.getBezierSegment(b, aEdge);
                            const B2DPoint aTestPoint(aEdge.interpolatePoint(0.5));
                            const bool bIsInside(tools::isInside(rClip, aTestPoint) == bInside);

						    if(bIsInside)
						    {
							    if(!aRun.count())
							    {
								    aRun.append(aEdge.getStartPoint());
							    }

							    if(aEdge.isBezier())
							    {
								    aRun.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint());
							    }
							    else
							    {
								    aRun.append(aEdge.getEndPoint());
							    }
						    }
						    else
						    {
                                if(aRun.count())
                                {
								    aRetval.append(aRun);
								    aRun.clear();
                                }
						    }
                        }

                        if(aRun.count())
					    {
                            // try to merge this last and first polygon; they may have been
                            // the former polygon's start/end point
                            if(aRetval.count())
                            {
                                const B2DPolygon aStartPolygon(aRetval.getB2DPolygon(0));

                                if(aStartPolygon.count() && aStartPolygon.getB2DPoint(0).equal(aRun.getB2DPoint(aRun.count() - 1)))
                                {
                                    // append start polygon to aRun, remove from result set
                                    aRun.append(aStartPolygon); aRun.removeDoublePoints();
                                    aRetval.remove(0);
                                }
                            }

						    aRetval.append(aRun);
					    }
					}
				}
				else
				{
					// area clipping
					B2DPolyPolygon aMergePolyPolygonA(rClip);

                    // First solve all polygon-self and polygon-polygon intersections.
                    // Also get rid of some not-needed polygons (neutral, no area -> when
                    // no intersections, these are tubes).
                    // Now it is possible to correct the orientations in the cut-free
                    // polygons to values corresponding to painting the PolyPolygon with
                    // a XOR-WindingRule.
                    aMergePolyPolygonA = solveCrossovers(aMergePolyPolygonA);
					aMergePolyPolygonA = stripNeutralPolygons(aMergePolyPolygonA);
                    aMergePolyPolygonA = correctOrientations(aMergePolyPolygonA);

					if(!bInside)
					{
                        // if we want to get the outside of the clip polygon, make
                        // it a 'Hole' in topological sense
						aMergePolyPolygonA.flip();
					}

					B2DPolyPolygon aMergePolyPolygonB(rCandidate);

                    // prepare 2nd source polygon in same way
                    aMergePolyPolygonB = solveCrossovers(aMergePolyPolygonB);
					aMergePolyPolygonB = stripNeutralPolygons(aMergePolyPolygonB);
                    aMergePolyPolygonB = correctOrientations(aMergePolyPolygonB);

                    // to clip against each other, concatenate and solve all
                    // polygon-polygon crossovers. polygon-self do not need to
                    // be solved again, they were solved in the preparation.
					aRetval.append(aMergePolyPolygonA);
					aRetval.append(aMergePolyPolygonB);
					aRetval = solveCrossovers(aRetval);

                    // now remove neutral polygons (closed, but no area). In a last
                    // step throw away all polygons which have a depth of less than 1
                    // which means there was no logical AND at their position. For the
                    // not-inside solution, the clip was flipped to define it as 'Hole',
                    // so the removal rule is different here; remove all with a depth
                    // of less than 0 (aka holes).
					aRetval = stripNeutralPolygons(aRetval);
					aRetval = stripDispensablePolygons(aRetval, bInside);
				}
			}

			return aRetval;
		}

		//////////////////////////////////////////////////////////////////////////////

		B2DPolyPolygon clipPolygonOnPolyPolygon(const B2DPolygon& rCandidate, const B2DPolyPolygon& rClip, bool bInside, bool bStroke)
		{
			B2DPolyPolygon aRetval;

			if(rCandidate.count() && rClip.count())
			{
				aRetval = clipPolyPolygonOnPolyPolygon(B2DPolyPolygon(rCandidate), rClip, bInside, bStroke);
			}

			return aRetval;
		}

		//////////////////////////////////////////////////////////////////////////////

		/*
		* let a plane be defined as
		*
		*     v.n+d=0
		*
		* and a ray be defined as
		*
		*     a+(b-a)*t=0
		*
		* substitute and rearranging yields
		*
		*     t = -(a.n+d)/(n.(b-a))
		*
		* if the denominator is zero, the line is either
		* contained in the plane or parallel to the plane.
		* in either case, there is no intersection.
		* if numerator and denominator are both zero, the
		* ray is contained in the plane.
		*
		*/
		struct scissor_plane {
			double nx,ny;			// plane normal
			double d;				// [-] minimum distance from origin
			sal_uInt32 clipmask;	// clipping mask, e.g. 1000 1000
		};

		/*
		*
		* polygon clipping rules  (straight out of Foley and Van Dam)
		* ===========================================================
		* current	|next		|emit
		* ____________________________________
		* inside	|inside		|next
		* inside	|outside	|intersect with clip plane
		* outside	|outside	|nothing
		* outside	|inside		|intersect with clip plane follwed by next
		*
		*/
		sal_uInt32 scissorLineSegment( ::basegfx::B2DPoint			 *in_vertex,	// input buffer
                                       sal_uInt32					  in_count,		// number of verts in input buffer
                                       ::basegfx::B2DPoint			 *out_vertex,	// output buffer
                                       scissor_plane				 *pPlane,		// scissoring plane
                                       const ::basegfx::B2DRectangle &rR )			// clipping rectangle
		{
			::basegfx::B2DPoint *curr;
			::basegfx::B2DPoint *next;

			sal_uInt32 out_count=0;

			// process all the verts
			for(sal_uInt32 i=0; i<in_count; i++) {

				// vertices are relative to the coordinate
				// system defined by the rectangle.
				curr = &in_vertex[i];
				next = &in_vertex[(i+1)%in_count];

				// perform clipping judgement & mask against current plane.
				sal_uInt32 clip = pPlane->clipmask & ((getCohenSutherlandClipFlags(*curr,rR)<<4)|getCohenSutherlandClipFlags(*next,rR));

				if(clip==0) { // both verts are inside
					out_vertex[out_count++] = *next;
				}
				else if((clip&0x0f) && (clip&0xf0)) { // both verts are outside
				}
				else if((clip&0x0f) && (clip&0xf0)==0) { // curr is inside, next is outside

					// direction vector from 'current' to 'next', *not* normalized
					// to bring 't' into the [0<=x<=1] intervall.
					::basegfx::B2DPoint dir((*next)-(*curr));

					double denominator = ( pPlane->nx*dir.getX() +
										pPlane->ny*dir.getY() );
					double numerator = ( pPlane->nx*curr->getX() +
										pPlane->ny*curr->getY() +
										pPlane->d );
					double t = -numerator/denominator;

					// calculate the actual point of intersection
					::basegfx::B2DPoint intersection( curr->getX()+t*dir.getX(),
													curr->getY()+t*dir.getY() );

					out_vertex[out_count++] = intersection;
				}
				else if((clip&0x0f)==0 && (clip&0xf0)) { // curr is outside, next is inside

					// direction vector from 'current' to 'next', *not* normalized
					// to bring 't' into the [0<=x<=1] intervall.
					::basegfx::B2DPoint dir((*next)-(*curr));

					double denominator = ( pPlane->nx*dir.getX() +
										pPlane->ny*dir.getY() );
					double numerator = ( pPlane->nx*curr->getX() +
										pPlane->ny*curr->getY() +
										pPlane->d );
					double t = -numerator/denominator;

					// calculate the actual point of intersection
					::basegfx::B2DPoint intersection( curr->getX()+t*dir.getX(),
													curr->getY()+t*dir.getY() );

					out_vertex[out_count++] = intersection;
					out_vertex[out_count++] = *next;
				}
			}

			return out_count;
		}

		B2DPolygon clipTriangleListOnRange( const B2DPolygon& rCandidate,
                                            const B2DRange&   rRange )
		{
			B2DPolygon aResult;

			if( !(rCandidate.count()%3) )
			{
				const int scissor_plane_count = 4;

				scissor_plane sp[scissor_plane_count];

				sp[0].nx = +1.0;
				sp[0].ny = +0.0;
				sp[0].d = -(rRange.getMinX());
				sp[0].clipmask = (RectClipFlags::LEFT << 4) | RectClipFlags::LEFT; // 0001 0001
				sp[1].nx = -1.0;
				sp[1].ny = +0.0;
				sp[1].d = +(rRange.getMaxX());
				sp[1].clipmask = (RectClipFlags::RIGHT << 4) | RectClipFlags::RIGHT; // 0010 0010
				sp[2].nx = +0.0;
				sp[2].ny = +1.0;
				sp[2].d = -(rRange.getMinY());
				sp[2].clipmask = (RectClipFlags::TOP << 4) | RectClipFlags::TOP; // 0100 0100
				sp[3].nx = +0.0;
				sp[3].ny = -1.0;
				sp[3].d = +(rRange.getMaxY());
				sp[3].clipmask = (RectClipFlags::BOTTOM << 4) | RectClipFlags::BOTTOM; // 1000 1000

				// retrieve the number of vertices of the triangulated polygon
				const sal_uInt32 nVertexCount = rCandidate.count();

				if(nVertexCount)
				{
					////////////////////////////////////////////////////////////////////////
					////////////////////////////////////////////////////////////////////////
					////////////////////////////////////////////////////////////////////////
					//
					// Upper bound for the maximal number of vertices when intersecting an
					// axis-aligned rectangle with a triangle in E2
					//
					// The rectangle and the triangle are in general position, and have 4 and 3
					// vertices, respectively.
					//
					//   Lemma: Since the rectangle is a convex polygon ( see
					//   http://mathworld.wolfram.com/ConvexPolygon.html for a definition), and
					//   has no holes, it follows that any straight line will intersect the
					//   rectangle's border line at utmost two times (with the usual
					//   tie-breaking rule, if the intersection exactly hits an already existing
					//   rectangle vertex, that this intersection is only attributed to one of
					//   the adjoining edges). Thus, having a rectangle intersected with
					//   a half-plane (one side of a straight line denotes 'inside', the
					//   other 'outside') will at utmost add _one_  vertex to the resulting
					//   intersection polygon (adding two intersection vertices, and removing at
					//   least one rectangle vertex):
					//
					//         *
					//     +--+-----------------+
					//     | *                  |
					//     |*                   |
					//     +                    |
					//    *|                    |
					//   * |                    |
					//     +--------------------+
					//
					//   Proof: If the straight line intersects the rectangle two
					//   times, it does so for distinct edges, i.e. the intersection has
					//   minimally one of the rectangle's vertices on either side of the straight
					//   line (but maybe more). Thus, the intersection with a half-plane has
					//   minimally _one_ rectangle vertex removed from the resulting clip
					//   polygon, and therefore, a clip against a half-plane has the net effect
					//   of adding at utmost _one_ vertex to the resulting clip polygon.
					//
					// Theorem: The intersection of a rectangle and a triangle results in a
					// polygon with at utmost 7 vertices.
					//
					// Proof: The inside of the triangle can be described as the consecutive
					// intersection with three half-planes. Together with the lemma above, this
					// results in at utmost 3 additional vertices added to the already existing 4
					// rectangle vertices.
					//
					// This upper bound is attained with the following example configuration:
					//
					//                               *
					//                             ***
					//                           ** *
					//                         **  *
					//                       **   *
					//                     **    *
					//                   **     *
					//                 **      *
					//               **       *
					//             **        *
					//           **         *
					//     ----*2--------3 *
					//     | **          |*
					//     1*            4
					//   **|            *|
					// **  |           * |
					//   **|          *  |
					//     7*        *   |
					//     --*6-----5-----
					//         **  *
					//           **
					//
					// As we need to scissor all triangles against the
					// output rectangle we employ an output buffer for the
					// resulting vertices.  the question is how large this
					// buffer needs to be compared to the number of
					// incoming vertices.  this buffer needs to hold at
					// most the number of original vertices times '7'. see
					// figure above for an example.  scissoring triangles
					// with the cohen-sutherland line clipping algorithm
					// as implemented here will result in a triangle fan
					// which will be rendered as separate triangles to
					// avoid pipeline stalls for each scissored
					// triangle. creating separate triangles from a
					// triangle fan produces (n-2)*3 vertices where n is
					// the number of vertices of the original triangle
					// fan.  for the maximum number of 7 vertices of
					// resulting triangle fans we therefore need 15 times
					// the number of original vertices.
					//
					////////////////////////////////////////////////////////////////////////
					////////////////////////////////////////////////////////////////////////
					////////////////////////////////////////////////////////////////////////

					//const size_t nBufferSize = sizeof(vertex)*(nVertexCount*16);
					//vertex *pVertices = (vertex*)alloca(nBufferSize);
					//sal_uInt32 nNumOutput = 0;

					// we need to clip this triangle against the output rectangle
					// to ensure that the resulting texture coordinates are in
					// the valid range from [0<=st<=1]. under normal circustances
					// we could use the BORDERCOLOR renderstate but some cards
					// seem to ignore this feature.
					::basegfx::B2DPoint stack[3];
					unsigned int clipflag = 0;

					for(sal_uInt32 nIndex=0; nIndex<nVertexCount; ++nIndex)
					{
						// rotate stack
						stack[0] = stack[1];
						stack[1] = stack[2];
						stack[2] = rCandidate.getB2DPoint(nIndex);

						// clipping judgement
						clipflag |= !(rRange.isInside(stack[2]));

						if(nIndex > 1)
						{
							// consume vertices until a single seperate triangle has been visited.
							if(!((nIndex+1)%3))
							{
								// if any of the last three vertices was outside
								// we need to scissor against the destination rectangle
								if(clipflag & 7)
								{
									::basegfx::B2DPoint buf0[16];
									::basegfx::B2DPoint buf1[16];

									sal_uInt32 vertex_count = 3;

									// clip against all 4 planes passing the result of
									// each plane as the input to the next using a double buffer
									vertex_count = scissorLineSegment(stack,vertex_count,buf1,&sp[0],rRange);
									vertex_count = scissorLineSegment(buf1,vertex_count,buf0,&sp[1],rRange);
									vertex_count = scissorLineSegment(buf0,vertex_count,buf1,&sp[2],rRange);
									vertex_count = scissorLineSegment(buf1,vertex_count,buf0,&sp[3],rRange);

									if(vertex_count >= 3)
									{
										// convert triangle fan back to triangle list.
										::basegfx::B2DPoint v0(buf0[0]);
										::basegfx::B2DPoint v1(buf0[1]);
										for(sal_uInt32 i=2; i<vertex_count; ++i)
										{
											::basegfx::B2DPoint v2(buf0[i]);
											aResult.append(v0);
											aResult.append(v1);
											aResult.append(v2);
											v1 = v2;
										}
									}
								}
								else
								{
									// the last triangle has not been altered, simply copy to result
									for(sal_uInt32 i=0; i<3; ++i)
										aResult.append(stack[i]);
								}
							}
						}

						clipflag <<= 1;
					}
				}
			}

			return aResult;
		}

		//////////////////////////////////////////////////////////////////////////////

	} // end of namespace tools
} // end of namespace basegfx

//////////////////////////////////////////////////////////////////////////////

// eof