summaryrefslogtreecommitdiff
path: root/basegfx/source/curve
diff options
context:
space:
mode:
authorOliver Bolte <obo@openoffice.org>2007-07-18 10:05:19 +0000
committerOliver Bolte <obo@openoffice.org>2007-07-18 10:05:19 +0000
commita45464095be4abcb229509e2233473dcd13d6e1f (patch)
tree6095c8276c85250ac44a40be7d9651d403bd094d /basegfx/source/curve
parent7a9f4ed48a1cd3fd088722d69de2f7f6ea40a0ae (diff)
INTEGRATION: CWS aw051 (1.13.14); FILE MERGED
2007/06/11 14:41:47 aw 1.13.14.3: #i77162# 2nd adaptions to new bezier handling 2007/06/06 15:49:41 aw 1.13.14.2: #i77162# B2DPolygin control point interface changes 2007/05/10 09:48:51 aw 1.13.14.1: #i76891#
Diffstat (limited to 'basegfx/source/curve')
-rw-r--r--basegfx/source/curve/b2dcubicbezier.cxx307
1 files changed, 229 insertions, 78 deletions
diff --git a/basegfx/source/curve/b2dcubicbezier.cxx b/basegfx/source/curve/b2dcubicbezier.cxx
index dff487b521e0..ec70a91c5cf3 100644
--- a/basegfx/source/curve/b2dcubicbezier.cxx
+++ b/basegfx/source/curve/b2dcubicbezier.cxx
@@ -4,9 +4,9 @@
*
* $RCSfile: b2dcubicbezier.cxx,v $
*
- * $Revision: 1.13 $
+ * $Revision: 1.14 $
*
- * last change: $Author: obo $ $Date: 2007-01-25 11:03:02 $
+ * last change: $Author: obo $ $Date: 2007-07-18 11:05:19 $
*
* The Contents of this file are made available subject to
* the terms of GNU Lesser General Public License Version 2.1.
@@ -52,6 +52,8 @@
#include <basegfx/numeric/ftools.hxx>
#endif
+#include <limits>
+
// #i37443#
#define FACTOR_FOR_UNSHARPEN (1.6)
#ifdef DBG_UTIL
@@ -64,14 +66,13 @@ namespace basegfx
{
namespace
{
- void ImpSubDiv(
+ void ImpSubDivAngle(
const B2DPoint& rfPA, // start point
const B2DPoint& rfEA, // edge on A
const B2DPoint& rfEB, // edge on B
const B2DPoint& rfPB, // end point
B2DPolygon& rTarget, // target polygon
double fAngleBound, // angle bound in [0.0 .. 2PI]
- bool bAddLastPoint, // should last point be added?
bool bAllowUnsharpen, // #i37443# allow the criteria to get unsharp in recursions
sal_uInt16 nMaxRecursionDepth) // endless loop protection
{
@@ -124,33 +125,24 @@ namespace basegfx
const B2DPoint aS3C(average(aS2L, aS2R));
// left recursion
- ImpSubDiv(rfPA, aS1L, aS2L, aS3C, rTarget, fAngleBound,
- bAddLastPoint, bAllowUnsharpen, nMaxRecursionDepth - 1);
+ ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1);
// right recursion
- ImpSubDiv(aS3C, aS2R, aS1R, rfPB, rTarget, fAngleBound,
- bAddLastPoint, bAllowUnsharpen, nMaxRecursionDepth - 1);
+ ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1);
}
else
{
- // add points
- rTarget.append(rfPA);
-
- if(bAddLastPoint)
- {
- rTarget.append(rfPB);
- }
+ rTarget.append(rfPB);
}
}
- void ImpSubDivStart(
+ void ImpSubDivAngleStart(
const B2DPoint& rfPA, // start point
const B2DPoint& rfEA, // edge on A
const B2DPoint& rfEB, // edge on B
const B2DPoint& rfPB, // end point
B2DPolygon& rTarget, // target polygon
const double& rfAngleBound, // angle bound in [0.0 .. 2PI]
- bool bAddLastPoint, // should last point be added?
bool bAllowUnsharpen) // #i37443# allow the criteria to get unsharp in recursions
{
sal_uInt16 nMaxRecursionDepth(8);
@@ -264,43 +256,99 @@ namespace basegfx
// left
if(bAngleIsSmallerLeft)
{
- rTarget.append(rfPA);
- if(bAddLastPoint)
- {
- rTarget.append(aS3C);
- }
+ rTarget.append(aS3C);
}
else
{
- ImpSubDiv(rfPA, aS1L, aS2L, aS3C, rTarget, rfAngleBound,
- bAddLastPoint, bAllowUnsharpen, nMaxRecursionDepth);
+ ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, rfAngleBound, bAllowUnsharpen, nMaxRecursionDepth);
}
// right
if(bAngleIsSmallerRight)
{
- rTarget.append(aS3C);
- if(bAddLastPoint)
- {
- rTarget.append(rfPB);
- }
+ rTarget.append(rfPB);
}
else
{
- ImpSubDiv(aS3C, aS2R, aS1R, rfPB, rTarget, rfAngleBound,
- bAddLastPoint, bAllowUnsharpen, nMaxRecursionDepth);
+ ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, rfAngleBound, bAllowUnsharpen, nMaxRecursionDepth);
}
}
}
if(!nMaxRecursionDepth)
{
- rTarget.append(rfPA);
- if(bAddLastPoint)
+ rTarget.append(rfPB);
+ }
+ }
+
+ void ImpSubDivDistance(
+ const B2DPoint& rfPA, // start point
+ const B2DPoint& rfEA, // edge on A
+ const B2DPoint& rfEB, // edge on B
+ const B2DPoint& rfPB, // end point
+ B2DPolygon& rTarget, // target polygon
+ double fDistanceBound2, // quadratic distance criteria
+ double fLastDistanceError2, // the last quadratic distance error
+ sal_uInt16 nMaxRecursionDepth) // endless loop protection
+ {
+ if(nMaxRecursionDepth)
+ {
+ // decide if another recursion is needed. If not, set
+ // nMaxRecursionDepth to zero
+
+ // Perform bezier flatness test (lecture notes from R. Schaback,
+ // Mathematics of Computer-Aided Design, Uni Goettingen, 2000)
+ //
+ // ||P(t) - L(t)|| <= max ||b_j - b_0 - j/n(b_n - b_0)||
+ // 0<=j<=n
+ //
+ // What is calculated here is an upper bound to the distance from
+ // a line through b_0 and b_3 (rfPA and P4 in our notation) and the
+ // curve. We can drop 0 and n from the running indices, since the
+ // argument of max becomes zero for those cases.
+ const double fJ1x(rfEA.getX() - rfPA.getX() - 1.0/3.0*(rfPB.getX() - rfPA.getX()));
+ const double fJ1y(rfEA.getY() - rfPA.getY() - 1.0/3.0*(rfPB.getY() - rfPA.getY()));
+ const double fJ2x(rfEB.getX() - rfPA.getX() - 2.0/3.0*(rfPB.getX() - rfPA.getX()));
+ const double fJ2y(rfEB.getY() - rfPA.getY() - 2.0/3.0*(rfPB.getY() - rfPA.getY()));
+ const double fDistanceError2(::std::max(fJ1x*fJ1x + fJ1y*fJ1y, fJ2x*fJ2x + fJ2y*fJ2y));
+
+ // stop if error measure does not improve anymore. This is a
+ // safety guard against floating point inaccuracies.
+ // stop if distance from line is guaranteed to be bounded by d
+ const bool bFurtherDivision(fLastDistanceError2 > fDistanceError2 && fDistanceError2 >= fDistanceBound2);
+
+ if(bFurtherDivision)
+ {
+ // remember last error value
+ fLastDistanceError2 = fDistanceError2;
+ }
+ else
{
- rTarget.append(rfPB);
+ // stop recustion
+ nMaxRecursionDepth = 0;
}
}
+
+ if(nMaxRecursionDepth)
+ {
+ // divide at 0.5
+ const B2DPoint aS1L(average(rfPA, rfEA));
+ const B2DPoint aS1C(average(rfEA, rfEB));
+ const B2DPoint aS1R(average(rfEB, rfPB));
+ const B2DPoint aS2L(average(aS1L, aS1C));
+ const B2DPoint aS2R(average(aS1C, aS1R));
+ const B2DPoint aS3C(average(aS2L, aS2R));
+
+ // left recursion
+ ImpSubDivDistance(rfPA, aS1L, aS2L, aS3C, rTarget, fDistanceBound2, fLastDistanceError2, nMaxRecursionDepth - 1);
+
+ // right recursion
+ ImpSubDivDistance(aS3C, aS2R, aS1R, rfPB, rTarget, fDistanceBound2, fLastDistanceError2, nMaxRecursionDepth - 1);
+ }
+ else
+ {
+ rTarget.append(rfPB);
+ }
}
} // end of anonymous namespace
} // end of namespace basegfx
@@ -337,14 +385,6 @@ namespace basegfx
{
}
- B2DCubicBezier::B2DCubicBezier(const B2DPoint& rStart, const B2DVector& rControlVectorA, const B2DVector& rControlVectorB, const B2DPoint& rEnd)
- : maStartPoint(rStart),
- maEndPoint(rEnd),
- maControlPointA(rStart + rControlVectorA),
- maControlPointB(rStart + rControlVectorB)
- {
- }
-
B2DCubicBezier::~B2DCubicBezier()
{
}
@@ -394,7 +434,68 @@ namespace basegfx
void B2DCubicBezier::testAndSolveTrivialBezier()
{
- // TODO
+ if(maControlPointA != maStartPoint || maControlPointB != maEndPoint)
+ {
+ const B2DVector aEdge(maEndPoint - maStartPoint);
+
+ // controls parallel to edge can be trivial. No edge -> not parallel -> control can not be trivial
+ if(!aEdge.equalZero())
+ {
+ const B2DVector aVecA(maControlPointA - maStartPoint);
+ const B2DVector aVecB(maControlPointB - maEndPoint);
+ const bool bAIsZero(aVecA.equalZero());
+ const bool bBIsZero(aVecB.equalZero());
+ bool bACanBeZero(false);
+ bool bBCanBeZero(false);
+
+ if(!bAIsZero)
+ {
+ // parallel to edge?
+ if(areParallel(aVecA, aEdge))
+ {
+ // get scale to edge
+ const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY()) ? aVecA.getX() / aEdge.getX() : aVecA.getY() / aEdge.getY());
+
+ // end point of vector in edge range?
+ if(fTools::more(fScale, 0.0) && fTools::lessOrEqual(fScale, 1.0))
+ {
+ bACanBeZero = true;
+ }
+ }
+ }
+
+ if(!bBIsZero)
+ {
+ // parallel to edge?
+ if(areParallel(aVecB, aEdge))
+ {
+ // get scale to edge
+ const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY()) ? aVecB.getX() / aEdge.getX() : aVecB.getY() / aEdge.getY());
+
+ // end point of vector in edge range? Caution: controlB is directed AGAINST edge
+ if(fTools::less(fScale, 0.0) && fTools::moreOrEqual(fScale, -1.0))
+ {
+ bBCanBeZero = true;
+ }
+ }
+ }
+
+ // if both are/can be reduced, do it.
+ // Not possible if only one is/can be reduced (!)
+ if((bAIsZero || bACanBeZero) && (bBIsZero || bBCanBeZero))
+ {
+ if(!bAIsZero)
+ {
+ maControlPointA = maStartPoint;
+ }
+
+ if(!bBIsZero)
+ {
+ maControlPointB = maEndPoint;
+ }
+ }
+ }
+ }
}
double B2DCubicBezier::getEdgeLength() const
@@ -407,44 +508,75 @@ namespace basegfx
{
const B2DVector aVectorA(maControlPointA - maStartPoint);
const B2DVector aVectorB(maEndPoint - maControlPointB);
- const B2DVector aTop(maControlPointB - maControlPointA);
- return (aVectorA.getLength() + aVectorB.getLength() + aTop.getLength());
+
+ if(!aVectorA.equalZero() || !aVectorB.equalZero())
+ {
+ const B2DVector aTop(maControlPointB - maControlPointA);
+ return (aVectorA.getLength() + aVectorB.getLength() + aTop.getLength());
+ }
+ else
+ {
+ return getEdgeLength();
+ }
}
- void B2DCubicBezier::adaptiveSubdivideByAngle(B2DPolygon& rTarget, double fAngleBound,
- bool bAddLastPoint, bool bAllowUnsharpen) const
+ void B2DCubicBezier::adaptiveSubdivideByAngle(B2DPolygon& rTarget, double fAngleBound, bool bAllowUnsharpen) const
{
- // use support method #i37443# and allow unsharpen the criteria
- ImpSubDivStart(maStartPoint, maControlPointA, maControlPointB, maEndPoint,
- rTarget, fAngleBound * F_PI180, bAddLastPoint, bAllowUnsharpen);
+ if(isBezier())
+ {
+ // use support method #i37443# and allow unsharpen the criteria
+ ImpSubDivAngleStart(maStartPoint, maControlPointA, maControlPointB, maEndPoint, rTarget, fAngleBound * F_PI180, bAllowUnsharpen);
+ }
+ else
+ {
+ rTarget.append(getEndPoint());
+ }
}
// #i37443# adaptive subdivide by nCount subdivisions
- void B2DCubicBezier::adaptiveSubdivideByCount(B2DPolygon& rTarget, sal_uInt32 nCount, bool bAddLastPoint) const
+ void B2DCubicBezier::adaptiveSubdivideByCount(B2DPolygon& rTarget, sal_uInt32 nCount) const
{
- rTarget.append(maStartPoint);
-
for(sal_uInt32 a(0L); a < nCount; a++)
{
const double fPos(double(a + 1L) / double(nCount + 1L));
rTarget.append(interpolatePoint(fPos));
}
- if(bAddLastPoint)
+ rTarget.append(getEndPoint());
+ }
+
+ // adaptive subdivide by distance
+ void B2DCubicBezier::adaptiveSubdivideByDistance(B2DPolygon& rTarget, double fDistanceBound) const
+ {
+ if(isBezier())
+ {
+ ImpSubDivDistance(maStartPoint, maControlPointA, maControlPointB, maEndPoint, rTarget,
+ fDistanceBound * fDistanceBound, ::std::numeric_limits<double>::max(), 30);
+ }
+ else
{
- rTarget.append(maEndPoint);
+ rTarget.append(getEndPoint());
}
}
B2DPoint B2DCubicBezier::interpolatePoint(double t) const
{
OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::interpolatePoint: Access out of range (!)");
- const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t));
- const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t));
- const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t));
- const B2DPoint aS2L(interpolate(aS1L, aS1C, t));
- const B2DPoint aS2R(interpolate(aS1C, aS1R, t));
- return interpolate(aS2L, aS2R, t);
+
+ if(isBezier())
+ {
+ const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t));
+ const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t));
+ const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t));
+ const B2DPoint aS2L(interpolate(aS1L, aS1C, t));
+ const B2DPoint aS2R(interpolate(aS1C, aS1R, t));
+
+ return interpolate(aS2L, aS2R, t);
+ }
+ else
+ {
+ return interpolate(maStartPoint, maEndPoint, t);
+ }
}
double B2DCubicBezier::getSmallestDistancePointToBezierSegment(const B2DPoint& rTestPoint, double& rCut) const
@@ -453,7 +585,8 @@ namespace basegfx
B2DPolygon aInitialPolygon;
// as start make a fix division, creates nInitialDivisions + 2L points
- adaptiveSubdivideByCount(aInitialPolygon, nInitialDivisions, true);
+ aInitialPolygon.append(getStartPoint());
+ adaptiveSubdivideByCount(aInitialPolygon, nInitialDivisions);
// now look for the closest point
const sal_uInt32 nPointCount(aInitialPolygon.count());
@@ -553,22 +686,40 @@ namespace basegfx
void B2DCubicBezier::split(double t, B2DCubicBezier& rBezierA, B2DCubicBezier& rBezierB) const
{
OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::split: Access out of range (!)");
- const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t));
- const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t));
- const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t));
- const B2DPoint aS2L(interpolate(aS1L, aS1C, t));
- const B2DPoint aS2R(interpolate(aS1C, aS1R, t));
- const B2DPoint aS3C(interpolate(aS2L, aS2R, t));
-
- rBezierA.setStartPoint(maStartPoint);
- rBezierA.setEndPoint(aS3C);
- rBezierA.setControlPointA(aS1L);
- rBezierA.setControlPointB(aS2L);
-
- rBezierB.setStartPoint(aS3C);
- rBezierB.setEndPoint(maEndPoint);
- rBezierB.setControlPointA(aS2R);
- rBezierB.setControlPointB(aS1R);
+
+ if(isBezier())
+ {
+ const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t));
+ const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t));
+ const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t));
+ const B2DPoint aS2L(interpolate(aS1L, aS1C, t));
+ const B2DPoint aS2R(interpolate(aS1C, aS1R, t));
+ const B2DPoint aS3C(interpolate(aS2L, aS2R, t));
+
+ rBezierA.setStartPoint(maStartPoint);
+ rBezierA.setEndPoint(aS3C);
+ rBezierA.setControlPointA(aS1L);
+ rBezierA.setControlPointB(aS2L);
+
+ rBezierB.setStartPoint(aS3C);
+ rBezierB.setEndPoint(maEndPoint);
+ rBezierB.setControlPointA(aS2R);
+ rBezierB.setControlPointB(aS1R);
+ }
+ else
+ {
+ const B2DPoint aSplit(interpolate(maStartPoint, maEndPoint, t));
+
+ rBezierA.setStartPoint(maStartPoint);
+ rBezierA.setEndPoint(aSplit);
+ rBezierA.setControlPointA(maStartPoint);
+ rBezierA.setControlPointB(aSplit);
+
+ rBezierB.setStartPoint(aSplit);
+ rBezierB.setEndPoint(maEndPoint);
+ rBezierB.setControlPointA(aSplit);
+ rBezierB.setControlPointB(maEndPoint);
+ }
}
B2DRange B2DCubicBezier::getRange() const