summaryrefslogtreecommitdiff
path: root/basegfx/source/curve/b2dcubicbezier.cxx
diff options
context:
space:
mode:
Diffstat (limited to 'basegfx/source/curve/b2dcubicbezier.cxx')
-rw-r--r--basegfx/source/curve/b2dcubicbezier.cxx1108
1 files changed, 1108 insertions, 0 deletions
diff --git a/basegfx/source/curve/b2dcubicbezier.cxx b/basegfx/source/curve/b2dcubicbezier.cxx
new file mode 100644
index 000000000000..83c620df7870
--- /dev/null
+++ b/basegfx/source/curve/b2dcubicbezier.cxx
@@ -0,0 +1,1108 @@
+/*************************************************************************
+ *
+ * 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: b2dcubicbezier.cxx,v $
+ *
+ * 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/curve/b2dcubicbezier.hxx>
+#include <basegfx/vector/b2dvector.hxx>
+#include <basegfx/polygon/b2dpolygon.hxx>
+#include <basegfx/numeric/ftools.hxx>
+
+#include <limits>
+
+// #i37443#
+#define FACTOR_FOR_UNSHARPEN (1.6)
+#ifdef DBG_UTIL
+static double fMultFactUnsharpen = FACTOR_FOR_UNSHARPEN;
+#endif
+
+//////////////////////////////////////////////////////////////////////////////
+
+namespace basegfx
+{
+ namespace
+ {
+ 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 bAllowUnsharpen, // #i37443# allow the criteria to get unsharp in recursions
+ sal_uInt16 nMaxRecursionDepth) // endless loop protection
+ {
+ if(nMaxRecursionDepth)
+ {
+ // do angle test
+ B2DVector aLeft(rfEA - rfPA);
+ B2DVector aRight(rfEB - rfPB);
+
+ // #i72104#
+ if(aLeft.equalZero())
+ {
+ aLeft = rfEB - rfPA;
+ }
+
+ if(aRight.equalZero())
+ {
+ aRight = rfEA - rfPB;
+ }
+
+ const double fCurrentAngle(aLeft.angle(aRight));
+
+ if(fabs(fCurrentAngle) > (F_PI - fAngleBound))
+ {
+ // end recursion
+ nMaxRecursionDepth = 0;
+ }
+ else
+ {
+ if(bAllowUnsharpen)
+ {
+ // #i37443# unsharpen criteria
+#ifdef DBG_UTIL
+ fAngleBound *= fMultFactUnsharpen;
+#else
+ fAngleBound *= FACTOR_FOR_UNSHARPEN;
+#endif
+ }
+ }
+ }
+
+ 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
+ ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1);
+
+ // right recursion
+ ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1);
+ }
+ else
+ {
+ rTarget.append(rfPB);
+ }
+ }
+
+ 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 bAllowUnsharpen) // #i37443# allow the criteria to get unsharp in recursions
+ {
+ sal_uInt16 nMaxRecursionDepth(8);
+ const B2DVector aLeft(rfEA - rfPA);
+ const B2DVector aRight(rfEB - rfPB);
+ bool bLeftEqualZero(aLeft.equalZero());
+ bool bRightEqualZero(aRight.equalZero());
+ bool bAllParallel(false);
+
+ if(bLeftEqualZero && bRightEqualZero)
+ {
+ nMaxRecursionDepth = 0;
+ }
+ else
+ {
+ const B2DVector aBase(rfPB - rfPA);
+ const bool bBaseEqualZero(aBase.equalZero()); // #i72104#
+
+ if(!bBaseEqualZero)
+ {
+ const bool bLeftParallel(bLeftEqualZero ? true : areParallel(aLeft, aBase));
+ const bool bRightParallel(bRightEqualZero ? true : areParallel(aRight, aBase));
+
+ if(bLeftParallel && bRightParallel)
+ {
+ bAllParallel = true;
+
+ if(!bLeftEqualZero)
+ {
+ double fFactor;
+
+ if(fabs(aBase.getX()) > fabs(aBase.getY()))
+ {
+ fFactor = aLeft.getX() / aBase.getX();
+ }
+ else
+ {
+ fFactor = aLeft.getY() / aBase.getY();
+ }
+
+ if(fFactor >= 0.0 && fFactor <= 1.0)
+ {
+ bLeftEqualZero = true;
+ }
+ }
+
+ if(!bRightEqualZero)
+ {
+ double fFactor;
+
+ if(fabs(aBase.getX()) > fabs(aBase.getY()))
+ {
+ fFactor = aRight.getX() / -aBase.getX();
+ }
+ else
+ {
+ fFactor = aRight.getY() / -aBase.getY();
+ }
+
+ if(fFactor >= 0.0 && fFactor <= 1.0)
+ {
+ bRightEqualZero = true;
+ }
+ }
+
+ if(bLeftEqualZero && bRightEqualZero)
+ {
+ nMaxRecursionDepth = 0;
+ }
+ }
+ }
+ }
+
+ if(nMaxRecursionDepth)
+ {
+ // divide at 0.5 ad test both edges for angle criteria
+ 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));
+
+ // test left
+ bool bAngleIsSmallerLeft(bAllParallel && bLeftEqualZero);
+ if(!bAngleIsSmallerLeft)
+ {
+ const B2DVector aLeftLeft(bLeftEqualZero ? aS2L - aS1L : aS1L - rfPA); // #i72104#
+ const B2DVector aRightLeft(aS2L - aS3C);
+ const double fCurrentAngleLeft(aLeftLeft.angle(aRightLeft));
+ bAngleIsSmallerLeft = (fabs(fCurrentAngleLeft) > (F_PI - rfAngleBound));
+ }
+
+ // test right
+ bool bAngleIsSmallerRight(bAllParallel && bRightEqualZero);
+ if(!bAngleIsSmallerRight)
+ {
+ const B2DVector aLeftRight(aS2R - aS3C);
+ const B2DVector aRightRight(bRightEqualZero ? aS2R - aS1R : aS1R - rfPB); // #i72104#
+ const double fCurrentAngleRight(aLeftRight.angle(aRightRight));
+ bAngleIsSmallerRight = (fabs(fCurrentAngleRight) > (F_PI - rfAngleBound));
+ }
+
+ if(bAngleIsSmallerLeft && bAngleIsSmallerRight)
+ {
+ // no recursion necessary at all
+ nMaxRecursionDepth = 0;
+ }
+ else
+ {
+ // left
+ if(bAngleIsSmallerLeft)
+ {
+ rTarget.append(aS3C);
+ }
+ else
+ {
+ ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, rfAngleBound, bAllowUnsharpen, nMaxRecursionDepth);
+ }
+
+ // right
+ if(bAngleIsSmallerRight)
+ {
+ rTarget.append(rfPB);
+ }
+ else
+ {
+ ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, rfAngleBound, bAllowUnsharpen, nMaxRecursionDepth);
+ }
+ }
+ }
+
+ if(!nMaxRecursionDepth)
+ {
+ 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
+ {
+ // 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
+
+//////////////////////////////////////////////////////////////////////////////
+
+namespace basegfx
+{
+ B2DCubicBezier::B2DCubicBezier(const B2DCubicBezier& rBezier)
+ : maStartPoint(rBezier.maStartPoint),
+ maEndPoint(rBezier.maEndPoint),
+ maControlPointA(rBezier.maControlPointA),
+ maControlPointB(rBezier.maControlPointB)
+ {
+ }
+
+ B2DCubicBezier::B2DCubicBezier()
+ {
+ }
+
+ B2DCubicBezier::B2DCubicBezier(const B2DPoint& rStart, const B2DPoint& rEnd)
+ : maStartPoint(rStart),
+ maEndPoint(rEnd),
+ maControlPointA(rStart),
+ maControlPointB(rEnd)
+ {
+ }
+
+ B2DCubicBezier::B2DCubicBezier(const B2DPoint& rStart, const B2DPoint& rControlPointA, const B2DPoint& rControlPointB, const B2DPoint& rEnd)
+ : maStartPoint(rStart),
+ maEndPoint(rEnd),
+ maControlPointA(rControlPointA),
+ maControlPointB(rControlPointB)
+ {
+ }
+
+ B2DCubicBezier::~B2DCubicBezier()
+ {
+ }
+
+ // assignment operator
+ B2DCubicBezier& B2DCubicBezier::operator=(const B2DCubicBezier& rBezier)
+ {
+ maStartPoint = rBezier.maStartPoint;
+ maEndPoint = rBezier.maEndPoint;
+ maControlPointA = rBezier.maControlPointA;
+ maControlPointB = rBezier.maControlPointB;
+
+ return *this;
+ }
+
+ // compare operators
+ bool B2DCubicBezier::operator==(const B2DCubicBezier& rBezier) const
+ {
+ return (
+ maStartPoint == rBezier.maStartPoint
+ && maEndPoint == rBezier.maEndPoint
+ && maControlPointA == rBezier.maControlPointA
+ && maControlPointB == rBezier.maControlPointB
+ );
+ }
+
+ bool B2DCubicBezier::operator!=(const B2DCubicBezier& rBezier) const
+ {
+ return (
+ maStartPoint != rBezier.maStartPoint
+ || maEndPoint != rBezier.maEndPoint
+ || maControlPointA != rBezier.maControlPointA
+ || maControlPointB != rBezier.maControlPointB
+ );
+ }
+
+ bool B2DCubicBezier::equal(const B2DCubicBezier& rBezier) const
+ {
+ return (
+ maStartPoint.equal(rBezier.maStartPoint)
+ && maEndPoint.equal(rBezier.maEndPoint)
+ && maControlPointA.equal(rBezier.maControlPointA)
+ && maControlPointB.equal(rBezier.maControlPointB)
+ );
+ }
+
+ // test if vectors are used
+ bool B2DCubicBezier::isBezier() const
+ {
+ if(maControlPointA != maStartPoint || maControlPointB != maEndPoint)
+ {
+ return true;
+ }
+
+ return false;
+ }
+
+ void B2DCubicBezier::testAndSolveTrivialBezier()
+ {
+ if(maControlPointA != maStartPoint || maControlPointB != maEndPoint)
+ {
+ const B2DVector aEdge(maEndPoint - maStartPoint);
+
+ // controls parallel to edge can be trivial. No edge -> not parallel -> control can
+ // still not be trivial (e.g. ballon loop)
+ if(!aEdge.equalZero())
+ {
+ // get control vectors
+ const B2DVector aVecA(maControlPointA - maStartPoint);
+ const B2DVector aVecB(maControlPointB - maEndPoint);
+
+ // check if trivial per se
+ bool bAIsTrivial(aVecA.equalZero());
+ bool bBIsTrivial(aVecB.equalZero());
+
+ // #i102241# prepare inverse edge length to normalize cross values;
+ // else the small compare value used in fTools::equalZero
+ // will be length dependent and this detection will work as less
+ // precise as longer the edge is. In principle, the length of the control
+ // vector would need to be used too, but to be trivial it is assumed to
+ // be of roughly equal length to the edge, so edge length can be used
+ // for both. Only needed when one of both is not trivial per se.
+ const double fInverseEdgeLength(bAIsTrivial && bBIsTrivial
+ ? 1.0
+ : 1.0 / aEdge.getLength());
+
+ // if A is not zero, check if it could be
+ if(!bAIsTrivial)
+ {
+ // #i102241# parallel to edge? Check aVecA, aEdge. Use cross() which does what
+ // we need here with the precision we need
+ const double fCross(aVecA.cross(aEdge) * fInverseEdgeLength);
+
+ if(fTools::equalZero(fCross))
+ {
+ // get scale to edge. Use bigger distance for numeric quality
+ const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY())
+ ? aVecA.getX() / aEdge.getX()
+ : aVecA.getY() / aEdge.getY());
+
+ // relative end point of vector in edge range?
+ if(fTools::moreOrEqual(fScale, 0.0) && fTools::lessOrEqual(fScale, 1.0))
+ {
+ bAIsTrivial = true;
+ }
+ }
+ }
+
+ // if B is not zero, check if it could be, but only if A is already trivial;
+ // else solve to trivial will not be possible for whole edge
+ if(bAIsTrivial && !bBIsTrivial)
+ {
+ // parallel to edge? Check aVecB, aEdge
+ const double fCross(aVecB.cross(aEdge) * fInverseEdgeLength);
+
+ if(fTools::equalZero(fCross))
+ {
+ // get scale to edge. Use bigger distance for numeric quality
+ 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::lessOrEqual(fScale, 0.0) && fTools::moreOrEqual(fScale, -1.0))
+ {
+ bBIsTrivial = true;
+ }
+ }
+ }
+
+ // if both are/can be reduced, do it.
+ // Not possible if only one is/can be reduced (!)
+ if(bAIsTrivial && bBIsTrivial)
+ {
+ maControlPointA = maStartPoint;
+ maControlPointB = maEndPoint;
+ }
+ }
+ }
+ }
+
+ namespace {
+ double impGetLength(const B2DCubicBezier& rEdge, double fDeviation, sal_uInt32 nRecursionWatch)
+ {
+ const double fEdgeLength(rEdge.getEdgeLength());
+ const double fControlPolygonLength(rEdge.getControlPolygonLength());
+ const double fCurrentDeviation(fTools::equalZero(fControlPolygonLength) ? 0.0 : 1.0 - (fEdgeLength / fControlPolygonLength));
+
+ if(!nRecursionWatch || fTools:: lessOrEqual(fCurrentDeviation, fDeviation))
+ {
+ return (fEdgeLength + fControlPolygonLength) * 0.5;
+ }
+ else
+ {
+ B2DCubicBezier aLeft, aRight;
+ const double fNewDeviation(fDeviation * 0.5);
+ const sal_uInt32 nNewRecursionWatch(nRecursionWatch - 1);
+
+ rEdge.split(0.5, &aLeft, &aRight);
+
+ return impGetLength(aLeft, fNewDeviation, nNewRecursionWatch)
+ + impGetLength(aRight, fNewDeviation, nNewRecursionWatch);
+ }
+ }
+ }
+
+ double B2DCubicBezier::getLength(double fDeviation) const
+ {
+ if(isBezier())
+ {
+ if(fDeviation < 0.00000001)
+ {
+ fDeviation = 0.00000001;
+ }
+
+ return impGetLength(*this, fDeviation, 6);
+ }
+ else
+ {
+ return B2DVector(getEndPoint() - getStartPoint()).getLength();
+ }
+ }
+
+ double B2DCubicBezier::getEdgeLength() const
+ {
+ const B2DVector aEdge(maEndPoint - maStartPoint);
+ return aEdge.getLength();
+ }
+
+ double B2DCubicBezier::getControlPolygonLength() const
+ {
+ const B2DVector aVectorA(maControlPointA - maStartPoint);
+ const B2DVector aVectorB(maEndPoint - maControlPointB);
+
+ 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 bAllowUnsharpen) const
+ {
+ 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());
+ }
+ }
+
+ B2DVector B2DCubicBezier::getTangent(double t) const
+ {
+ if(fTools::lessOrEqual(t, 0.0))
+ {
+ // tangent in start point
+ B2DVector aTangent(getControlPointA() - getStartPoint());
+
+ if(!aTangent.equalZero())
+ {
+ return aTangent;
+ }
+
+ // start point and control vector are the same, fallback
+ // to implicit start vector to control point B
+ aTangent = (getControlPointB() - getStartPoint()) * 0.3;
+
+ if(!aTangent.equalZero())
+ {
+ return aTangent;
+ }
+
+ // not a bezier at all, return edge vector
+ return (getEndPoint() - getStartPoint()) * 0.3;
+ }
+ else if(fTools::moreOrEqual(t, 1.0))
+ {
+ // tangent in end point
+ B2DVector aTangent(getEndPoint() - getControlPointB());
+
+ if(!aTangent.equalZero())
+ {
+ return aTangent;
+ }
+
+ // end point and control vector are the same, fallback
+ // to implicit start vector from control point A
+ aTangent = (getEndPoint() - getControlPointA()) * 0.3;
+
+ if(!aTangent.equalZero())
+ {
+ return aTangent;
+ }
+
+ // not a bezier at all, return edge vector
+ return (getEndPoint() - getStartPoint()) * 0.3;
+ }
+ else
+ {
+ // t is in ]0.0 .. 1.0[. Split and extract
+ B2DCubicBezier aRight;
+ split(t, 0, &aRight);
+
+ return aRight.getControlPointA() - aRight.getStartPoint();
+ }
+ }
+
+ // #i37443# adaptive subdivide by nCount subdivisions
+ void B2DCubicBezier::adaptiveSubdivideByCount(B2DPolygon& rTarget, sal_uInt32 nCount) const
+ {
+ const double fLenFact(1.0 / static_cast< double >(nCount + 1));
+
+ for(sal_uInt32 a(1); a <= nCount; a++)
+ {
+ const double fPos(static_cast< double >(a) * fLenFact);
+ rTarget.append(interpolatePoint(fPos));
+ }
+
+ 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(getEndPoint());
+ }
+ }
+
+ B2DPoint B2DCubicBezier::interpolatePoint(double t) const
+ {
+ OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::interpolatePoint: Access out of range (!)");
+
+ 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
+ {
+ const sal_uInt32 nInitialDivisions(3L);
+ B2DPolygon aInitialPolygon;
+
+ // as start make a fix division, creates nInitialDivisions + 2L points
+ aInitialPolygon.append(getStartPoint());
+ adaptiveSubdivideByCount(aInitialPolygon, nInitialDivisions);
+
+ // now look for the closest point
+ const sal_uInt32 nPointCount(aInitialPolygon.count());
+ B2DVector aVector(rTestPoint - aInitialPolygon.getB2DPoint(0L));
+ double fQuadDist(aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY());
+ double fNewQuadDist;
+ sal_uInt32 nSmallestIndex(0L);
+
+ for(sal_uInt32 a(1L); a < nPointCount; a++)
+ {
+ aVector = B2DVector(rTestPoint - aInitialPolygon.getB2DPoint(a));
+ fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY();
+
+ if(fNewQuadDist < fQuadDist)
+ {
+ fQuadDist = fNewQuadDist;
+ nSmallestIndex = a;
+ }
+ }
+
+ // look right and left for even smaller distances
+ double fStepValue(1.0 / (double)((nPointCount - 1L) * 2L)); // half the edge step width
+ double fPosition((double)nSmallestIndex / (double)(nPointCount - 1L));
+ bool bDone(false);
+
+ while(!bDone)
+ {
+ if(!bDone)
+ {
+ // test left
+ double fPosLeft(fPosition - fStepValue);
+
+ if(fPosLeft < 0.0)
+ {
+ fPosLeft = 0.0;
+ aVector = B2DVector(rTestPoint - maStartPoint);
+ }
+ else
+ {
+ aVector = B2DVector(rTestPoint - interpolatePoint(fPosLeft));
+ }
+
+ fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY();
+
+ if(fTools::less(fNewQuadDist, fQuadDist))
+ {
+ fQuadDist = fNewQuadDist;
+ fPosition = fPosLeft;
+ }
+ else
+ {
+ // test right
+ double fPosRight(fPosition + fStepValue);
+
+ if(fPosRight > 1.0)
+ {
+ fPosRight = 1.0;
+ aVector = B2DVector(rTestPoint - maEndPoint);
+ }
+ else
+ {
+ aVector = B2DVector(rTestPoint - interpolatePoint(fPosRight));
+ }
+
+ fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY();
+
+ if(fTools::less(fNewQuadDist, fQuadDist))
+ {
+ fQuadDist = fNewQuadDist;
+ fPosition = fPosRight;
+ }
+ else
+ {
+ // not less left or right, done
+ bDone = true;
+ }
+ }
+ }
+
+ if(0.0 == fPosition || 1.0 == fPosition)
+ {
+ // if we are completely left or right, we are done
+ bDone = true;
+ }
+
+ if(!bDone)
+ {
+ // prepare next step value
+ fStepValue /= 2.0;
+ }
+ }
+
+ rCut = fPosition;
+ return sqrt(fQuadDist);
+ }
+
+ void B2DCubicBezier::split(double t, B2DCubicBezier* pBezierA, B2DCubicBezier* pBezierB) const
+ {
+ OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::split: Access out of range (!)");
+
+ if(!pBezierA && !pBezierB)
+ {
+ return;
+ }
+
+ 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));
+
+ if(pBezierA)
+ {
+ pBezierA->setStartPoint(maStartPoint);
+ pBezierA->setEndPoint(aS3C);
+ pBezierA->setControlPointA(aS1L);
+ pBezierA->setControlPointB(aS2L);
+ }
+
+ if(pBezierB)
+ {
+ pBezierB->setStartPoint(aS3C);
+ pBezierB->setEndPoint(maEndPoint);
+ pBezierB->setControlPointA(aS2R);
+ pBezierB->setControlPointB(aS1R);
+ }
+ }
+ else
+ {
+ const B2DPoint aSplit(interpolate(maStartPoint, maEndPoint, t));
+
+ if(pBezierA)
+ {
+ pBezierA->setStartPoint(maStartPoint);
+ pBezierA->setEndPoint(aSplit);
+ pBezierA->setControlPointA(maStartPoint);
+ pBezierA->setControlPointB(aSplit);
+ }
+
+ if(pBezierB)
+ {
+ pBezierB->setStartPoint(aSplit);
+ pBezierB->setEndPoint(maEndPoint);
+ pBezierB->setControlPointA(aSplit);
+ pBezierB->setControlPointB(maEndPoint);
+ }
+ }
+ }
+
+ B2DCubicBezier B2DCubicBezier::snippet(double fStart, double fEnd) const
+ {
+ B2DCubicBezier aRetval;
+
+ if(fTools::more(fStart, 1.0))
+ {
+ fStart = 1.0;
+ }
+ else if(fTools::less(fStart, 0.0))
+ {
+ fStart = 0.0;
+ }
+
+ if(fTools::more(fEnd, 1.0))
+ {
+ fEnd = 1.0;
+ }
+ else if(fTools::less(fEnd, 0.0))
+ {
+ fEnd = 0.0;
+ }
+
+ if(fEnd <= fStart)
+ {
+ // empty or NULL, create single point at center
+ const double fSplit((fEnd + fStart) * 0.5);
+ const B2DPoint aPoint(interpolate(getStartPoint(), getEndPoint(), fSplit));
+ aRetval.setStartPoint(aPoint);
+ aRetval.setEndPoint(aPoint);
+ aRetval.setControlPointA(aPoint);
+ aRetval.setControlPointB(aPoint);
+ }
+ else
+ {
+ if(isBezier())
+ {
+ // copy bezier; cut off right, then cut off left. Do not forget to
+ // adapt cut value when both cuts happen
+ const bool bEndIsOne(fTools::equal(fEnd, 1.0));
+ const bool bStartIsZero(fTools::equalZero(fStart));
+ aRetval = *this;
+
+ if(!bEndIsOne)
+ {
+ aRetval.split(fEnd, &aRetval, 0);
+
+ if(!bStartIsZero)
+ {
+ fStart /= fEnd;
+ }
+ }
+
+ if(!bStartIsZero)
+ {
+ aRetval.split(fStart, 0, &aRetval);
+ }
+ }
+ else
+ {
+ // no bezier, create simple edge
+ const B2DPoint aPointA(interpolate(getStartPoint(), getEndPoint(), fStart));
+ const B2DPoint aPointB(interpolate(getStartPoint(), getEndPoint(), fEnd));
+ aRetval.setStartPoint(aPointA);
+ aRetval.setEndPoint(aPointB);
+ aRetval.setControlPointA(aPointA);
+ aRetval.setControlPointB(aPointB);
+ }
+ }
+
+ return aRetval;
+ }
+
+ B2DRange B2DCubicBezier::getRange() const
+ {
+ B2DRange aRetval(maStartPoint, maEndPoint);
+
+ aRetval.expand(maControlPointA);
+ aRetval.expand(maControlPointB);
+
+ return aRetval;
+ }
+
+ bool B2DCubicBezier::getMinimumExtremumPosition(double& rfResult) const
+ {
+ ::std::vector< double > aAllResults;
+
+ aAllResults.reserve(4);
+ getAllExtremumPositions(aAllResults);
+
+ const sal_uInt32 nCount(aAllResults.size());
+
+ if(!nCount)
+ {
+ return false;
+ }
+ else if(1 == nCount)
+ {
+ rfResult = aAllResults[0];
+ return true;
+ }
+ else
+ {
+ rfResult = *(::std::min_element(aAllResults.begin(), aAllResults.end()));
+ return true;
+ }
+ }
+
+ namespace
+ {
+ inline void impCheckExtremumResult(double fCandidate, ::std::vector< double >& rResult)
+ {
+ // check for range ]0.0 .. 1.0[ with excluding 1.0 and 0.0 clearly
+ // by using the equalZero test, NOT ::more or ::less which will use the
+ // ApproxEqual() which is too exact here
+ if(fCandidate > 0.0 && !fTools::equalZero(fCandidate))
+ {
+ if(fCandidate < 1.0 && !fTools::equalZero(fCandidate - 1.0))
+ {
+ rResult.push_back(fCandidate);
+ }
+ }
+ }
+ }
+
+ void B2DCubicBezier::getAllExtremumPositions(::std::vector< double >& rResults) const
+ {
+ rResults.clear();
+
+ // calculate the x-extrema parameters by zeroing first x-derivative
+ // of the cubic bezier's parametric formula, which results in a
+ // quadratic equation: dBezier/dt = t*t*fAX - 2*t*fBX + fCX
+ const B2DPoint aRelativeEndPoint(maEndPoint-maStartPoint);
+ const double fAX = 3 * (maControlPointA.getX() - maControlPointB.getX()) + aRelativeEndPoint.getX();
+ const double fBX = 2 * maControlPointA.getX() - maControlPointB.getX() - maStartPoint.getX();
+ double fCX(maControlPointA.getX() - maStartPoint.getX());
+
+ if(fTools::equalZero(fCX))
+ {
+ // detect fCX equal zero and truncate to real zero value in that case
+ fCX = 0.0;
+ }
+
+ if( !fTools::equalZero(fAX) )
+ {
+ // derivative is polynomial of order 2 => use binomial formula
+ const double fD = fBX*fBX - fAX*fCX;
+ if( fD >= 0.0 )
+ {
+ const double fS = sqrt(fD);
+ // same as above but for very small fAX and/or fCX
+ // this has much better numerical stability
+ // see NRC chapter 5-6 (thanks THB!)
+ const double fQ = fBX + ((fBX >= 0) ? +fS : -fS);
+ impCheckExtremumResult(fQ / fAX, rResults);
+ impCheckExtremumResult(fCX / fQ, rResults);
+ }
+ }
+ else if( !fTools::equalZero(fBX) )
+ {
+ // derivative is polynomial of order 1 => one extrema
+ impCheckExtremumResult(fCX / (2 * fBX), rResults);
+ }
+
+ // calculate the y-extrema parameters by zeroing first y-derivative
+ const double fAY = 3 * (maControlPointA.getY() - maControlPointB.getY()) + aRelativeEndPoint.getY();
+ const double fBY = 2 * maControlPointA.getY() - maControlPointB.getY() - maStartPoint.getY();
+ double fCY(maControlPointA.getY() - maStartPoint.getY());
+
+ if(fTools::equalZero(fCY))
+ {
+ // detect fCY equal zero and truncate to real zero value in that case
+ fCY = 0.0;
+ }
+
+ if( !fTools::equalZero(fAY) )
+ {
+ // derivative is polynomial of order 2 => use binomial formula
+ const double fD = fBY*fBY - fAY*fCY;
+ if( fD >= 0 )
+ {
+ const double fS = sqrt(fD);
+ // same as above but for very small fAX and/or fCX
+ // this has much better numerical stability
+ // see NRC chapter 5-6 (thanks THB!)
+ const double fQ = fBY + ((fBY >= 0) ? +fS : -fS);
+ impCheckExtremumResult(fQ / fAY, rResults);
+ impCheckExtremumResult(fCY / fQ, rResults);
+ }
+ }
+ else if( !fTools::equalZero(fBY) )
+ {
+ // derivative is polynomial of order 1 => one extrema
+ impCheckExtremumResult(fCY / (2 * fBY), rResults);
+ }
+ }
+
+ int B2DCubicBezier::getMaxDistancePositions( double pResult[2]) const
+ {
+ // the distance from the bezier to a line through start and end
+ // is proportional to (ENDx-STARTx,ENDy-STARTy)*(+BEZIERy(t),-BEZIERx(t))
+ // this distance becomes zero for at least t==0 and t==1
+ // its extrema that are between 0..1 are interesting as split candidates
+ // its derived function has the form dD/dt = fA*t^2 + 2*fB*t + fC
+ const B2DPoint aRelativeEndPoint(maEndPoint-maStartPoint);
+ const double fA = 3 * (maEndPoint.getX() - maControlPointB.getX()) * aRelativeEndPoint.getY()
+ - 3 * (maEndPoint.getY() - maControlPointB.getY()) * aRelativeEndPoint.getX();
+ const double fB = (maControlPointB.getX() - maControlPointA.getX()) * aRelativeEndPoint.getY()
+ - (maControlPointB.getY() - maControlPointA.getY()) * aRelativeEndPoint.getX();
+ const double fC = (maControlPointA.getX() - maStartPoint.getX()) * aRelativeEndPoint.getY()
+ - (maControlPointA.getY() - maStartPoint.getY()) * aRelativeEndPoint.getX();
+
+ // test for degenerated case: non-cubic curve
+ if( fTools::equalZero(fA) )
+ {
+ // test for degenerated case: straight line
+ if( fTools::equalZero(fB) )
+ return 0;
+
+ // degenerated case: quadratic bezier
+ pResult[0] = -fC / (2*fB);
+
+ // test root: ignore it when it is outside the curve
+ int nCount = ((pResult[0] > 0) && (pResult[0] < 1));
+ return nCount;
+ }
+
+ // derivative is polynomial of order 2
+ // check if the polynomial has non-imaginary roots
+ const double fD = fB*fB - fA*fC;
+ if( fD >= 0.0 ) // TODO: is this test needed? geometrically not IMHO
+ {
+ // calculate the first root
+ const double fS = sqrt(fD);
+ const double fQ = fB + ((fB >= 0) ? +fS : -fS);
+ pResult[0] = fQ / fA;
+ // test root: ignore it when it is outside the curve
+ int nCount = ((pResult[0] > 0) && (pResult[0] < 1));
+
+ // ignore multiplicit roots
+ if( !fTools::equalZero(fD) )
+ {
+ // calculate the second root
+ const double fRoot = fC / fQ;
+ pResult[ nCount ] = fC / fQ;
+ // test root: ignore it when it is outside the curve
+ nCount += ((fRoot > 0) && (fRoot < 1));
+ }
+
+ return nCount;
+ }
+
+ return 0;
+ }
+
+} // end of namespace basegfx
+
+// eof