/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ /* * This file is part of the LibreOffice project. * * This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. * * This file incorporates work covered by the following license notice: * * 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 .
*/
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);
}
} elseif(bParallelToXAxis && fTools::lessOrEqual(aCandidateRange.getMaxY(), fValueOnOtherAxis))
{ // completely below and on the clip line. also true for curves. if(!bAboveAxis)
{ // add completely
aRetval.append(rCandidate);
}
} elseif(!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);
}
} elseif(!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[. constdouble 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 - 1);
B2DCubicBezier aEdge;
B2DPolygon aRun;
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);
}
}
}
}
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);
}
}
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 parallel // 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 knowledge and is unfortunately // more expensive, too. const B2DPolygon aClip(createPolygonFromRect(rRange));
// clip against the four axes of the range // against X-Axis, lower value
aRetval = clipPolygonOnParallelAxis(rCandidate, true, bInside, rRange.getMinY(), bStroke);
if(!rCandidate.count())
{ // 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(aClippedPolyPolygon.count())
{
aRetval.append(aClippedPolyPolygon);
}
}
} else
{ // for details, see comment in clipPolygonOnRange for the "cutting off // the outer parts of filled polygons at parallel lines" explanations const B2DPolygon aClip(createPolygonFromRect(rRange));
if(rCandidate.count() && rClip.count())
{ // one or both are no rectangle - go the hard way and clip PolyPolygon // against PolyPolygon... 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(constauto& rPolygon : rCandidate)
{ // add cuts with clip to polygon, including bezier segments const B2DPolygon aCandidate(addPointsAtCuts(rPolygon, rClip)); const sal_uInt32 nPointCount(aCandidate.count()); const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1);
B2DCubicBezier aEdge;
B2DPolygon aRun;
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
{ // check for simplification with ranges if !bStroke (handling as stroke is more simple), // but also only when bInside, else the simplification may lead to recursive calls (see // calls to clipPolyPolygonOnPolyPolygon in clipPolyPolygonOnRange and clipPolygonOnRange) if (bInside && basegfx::utils::isRectangle(rClip))
{ // #i125349# detect if both given PolyPolygons are indeed ranges if (basegfx::utils::isRectangle(rCandidate))
{ // both are rectangle if(rCandidate.getB2DRange().equal(rClip.getB2DRange()))
{ // if both are equal -> no change return rCandidate;
} else
{ // not equal -> create new intersection from both ranges, // but much cheaper based on the ranges
basegfx::B2DRange aIntersectionRange(rCandidate.getB2DRange());
if(aIntersectionRange.isEmpty())
{ // no common IntersectionRange -> the clip will be empty return B2DPolyPolygon();
} else
{ // use common aIntersectionRange as result, convert // to expected utils::PolyPolygon form return basegfx::B2DPolyPolygon(
basegfx::utils::createPolygonFromRect(aIntersectionRange));
}
}
} else
{ // rClip is rectangle -> clip rCandidate on rRectangle, use the much // cheaper and numerically more stable clipping against a range return clipPolyPolygonOnRange(rCandidate, rClip.getB2DRange(), bInside, bStroke);
}
}
// area clipping
// 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 utils::PolyPolygon with // a XOR-WindingRule.
B2DPolyPolygon aMergePolyPolygonA = solveCrossovers(rClip);
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();
}
// prepare 2nd source polygon in same way
B2DPolyPolygon aMergePolyPolygonB = solveCrossovers(rCandidate, pPointLimit);
if (pPointLimit && !*pPointLimit)
{
SAL_WARN("basegfx", "clipPolyPolygonOnPolyPolygon hit point limit"); return aRetval;
}
// 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, pPointLimit);
// 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);
}
}
/* * 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 followed by next *
*/ static 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 const *pPlane, // scissoring plane const ::basegfx::B2DRectangle &rR ) // clipping rectangle
{
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.
::basegfx::B2DPoint *curr = &in_vertex[i];
::basegfx::B2DPoint *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;
} elseif((clip&0x0f) && (clip&0xf0)) { // both verts are outside
} elseif((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] interval.
::basegfx::B2DPoint dir((*next)-(*curr));
// 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:
// 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.
// 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 circumstances // we could use the BORDERCOLOR renderstate but some cards // seem to ignore this feature.
::basegfx::B2DPoint stack[3]; unsignedint clipflag = 0;
if(nIndex > 1)
{ // consume vertices until a single separate 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(const basegfx::B2DPoint & i : stack)
aResult.append(i);
}
}
}
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
