diff options
Diffstat (limited to 'basegfx/source/polygon/b2dpolygonclipper.cxx')
-rw-r--r-- | basegfx/source/polygon/b2dpolygonclipper.cxx | 877 |
1 files changed, 877 insertions, 0 deletions
diff --git a/basegfx/source/polygon/b2dpolygonclipper.cxx b/basegfx/source/polygon/b2dpolygonclipper.cxx new file mode 100644 index 000000000000..f0d325942c07 --- /dev/null +++ b/basegfx/source/polygon/b2dpolygonclipper.cxx @@ -0,0 +1,877 @@ +/************************************************************************* + * + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * Copyright 2008 by Sun Microsystems, Inc. + * + * OpenOffice.org - a multi-platform office productivity suite + * + * $RCSfile: b2dpolygonclipper.cxx,v $ + * $Revision: 1.7 $ + * + * 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> + +////////////////////////////////////////////////////////////////////////////// + +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); + B2DHomMatrix aMatrixTransform; + B2DPolygon aCandidate(rCandidate); + + // translate and rotate polygon so that given edge is on x axis + aMatrixTransform.translate(-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); + B2DHomMatrix aMatrixTransform; + B2DPolyPolygon aCandidate(rCandidate); + + // translate and rotate polygon so that given edge is on x axis + aMatrixTransform.translate(-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 |