/************************************************************** * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. * *************************************************************/ // MARKER(update_precomp.py): autogen include statement, do not remove #include "precompiled_basegfx.hxx" #include #include #include #include #include #include #include #include #include #include #include ////////////////////////////////////////////////////////////////////////////// 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; iclipmask & ((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 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