1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/2d/Path.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,517 @@
1.4 +/* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 2 -*-
1.5 + * This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#include "2D.h"
1.10 +#include "PathAnalysis.h"
1.11 +#include "PathHelpers.h"
1.12 +
1.13 +namespace mozilla {
1.14 +namespace gfx {
1.15 +
1.16 +static float CubicRoot(float aValue) {
1.17 + if (aValue < 0.0) {
1.18 + return -CubicRoot(-aValue);
1.19 + }
1.20 + else {
1.21 + return powf(aValue, 1.0f / 3.0f);
1.22 + }
1.23 +}
1.24 +
1.25 +struct BezierControlPoints
1.26 +{
1.27 + BezierControlPoints() {}
1.28 + BezierControlPoints(const Point &aCP1, const Point &aCP2,
1.29 + const Point &aCP3, const Point &aCP4)
1.30 + : mCP1(aCP1), mCP2(aCP2), mCP3(aCP3), mCP4(aCP4)
1.31 + {
1.32 + }
1.33 +
1.34 + Point mCP1, mCP2, mCP3, mCP4;
1.35 +};
1.36 +
1.37 +void
1.38 +FlattenBezier(const BezierControlPoints &aPoints,
1.39 + PathSink *aSink, Float aTolerance);
1.40 +
1.41 +
1.42 +Path::Path()
1.43 +{
1.44 +}
1.45 +
1.46 +Path::~Path()
1.47 +{
1.48 +}
1.49 +
1.50 +Float
1.51 +Path::ComputeLength()
1.52 +{
1.53 + EnsureFlattenedPath();
1.54 + return mFlattenedPath->ComputeLength();
1.55 +}
1.56 +
1.57 +Point
1.58 +Path::ComputePointAtLength(Float aLength, Point* aTangent)
1.59 +{
1.60 + EnsureFlattenedPath();
1.61 + return mFlattenedPath->ComputePointAtLength(aLength, aTangent);
1.62 +}
1.63 +
1.64 +void
1.65 +Path::EnsureFlattenedPath()
1.66 +{
1.67 + if (!mFlattenedPath) {
1.68 + mFlattenedPath = new FlattenedPath();
1.69 + StreamToSink(mFlattenedPath);
1.70 + }
1.71 +}
1.72 +
1.73 +// This is the maximum deviation we allow (with an additional ~20% margin of
1.74 +// error) of the approximation from the actual Bezier curve.
1.75 +const Float kFlatteningTolerance = 0.0001f;
1.76 +
1.77 +void
1.78 +FlattenedPath::MoveTo(const Point &aPoint)
1.79 +{
1.80 + MOZ_ASSERT(!mCalculatedLength);
1.81 + FlatPathOp op;
1.82 + op.mType = FlatPathOp::OP_MOVETO;
1.83 + op.mPoint = aPoint;
1.84 + mPathOps.push_back(op);
1.85 +
1.86 + mLastMove = aPoint;
1.87 +}
1.88 +
1.89 +void
1.90 +FlattenedPath::LineTo(const Point &aPoint)
1.91 +{
1.92 + MOZ_ASSERT(!mCalculatedLength);
1.93 + FlatPathOp op;
1.94 + op.mType = FlatPathOp::OP_LINETO;
1.95 + op.mPoint = aPoint;
1.96 + mPathOps.push_back(op);
1.97 +}
1.98 +
1.99 +void
1.100 +FlattenedPath::BezierTo(const Point &aCP1,
1.101 + const Point &aCP2,
1.102 + const Point &aCP3)
1.103 +{
1.104 + MOZ_ASSERT(!mCalculatedLength);
1.105 + FlattenBezier(BezierControlPoints(CurrentPoint(), aCP1, aCP2, aCP3), this, kFlatteningTolerance);
1.106 +}
1.107 +
1.108 +void
1.109 +FlattenedPath::QuadraticBezierTo(const Point &aCP1,
1.110 + const Point &aCP2)
1.111 +{
1.112 + MOZ_ASSERT(!mCalculatedLength);
1.113 + // We need to elevate the degree of this quadratic Bézier to cubic, so we're
1.114 + // going to add an intermediate control point, and recompute control point 1.
1.115 + // The first and last control points remain the same.
1.116 + // This formula can be found on http://fontforge.sourceforge.net/bezier.html
1.117 + Point CP0 = CurrentPoint();
1.118 + Point CP1 = (CP0 + aCP1 * 2.0) / 3.0;
1.119 + Point CP2 = (aCP2 + aCP1 * 2.0) / 3.0;
1.120 + Point CP3 = aCP2;
1.121 +
1.122 + BezierTo(CP1, CP2, CP3);
1.123 +}
1.124 +
1.125 +void
1.126 +FlattenedPath::Close()
1.127 +{
1.128 + MOZ_ASSERT(!mCalculatedLength);
1.129 + LineTo(mLastMove);
1.130 +}
1.131 +
1.132 +void
1.133 +FlattenedPath::Arc(const Point &aOrigin, float aRadius, float aStartAngle,
1.134 + float aEndAngle, bool aAntiClockwise)
1.135 +{
1.136 + ArcToBezier(this, aOrigin, Size(aRadius, aRadius), aStartAngle, aEndAngle, aAntiClockwise);
1.137 +}
1.138 +
1.139 +Float
1.140 +FlattenedPath::ComputeLength()
1.141 +{
1.142 + if (!mCalculatedLength) {
1.143 + Point currentPoint;
1.144 +
1.145 + for (uint32_t i = 0; i < mPathOps.size(); i++) {
1.146 + if (mPathOps[i].mType == FlatPathOp::OP_MOVETO) {
1.147 + currentPoint = mPathOps[i].mPoint;
1.148 + } else {
1.149 + mCachedLength += Distance(currentPoint, mPathOps[i].mPoint);
1.150 + currentPoint = mPathOps[i].mPoint;
1.151 + }
1.152 + }
1.153 +
1.154 + mCalculatedLength = true;
1.155 + }
1.156 +
1.157 + return mCachedLength;
1.158 +}
1.159 +
1.160 +Point
1.161 +FlattenedPath::ComputePointAtLength(Float aLength, Point *aTangent)
1.162 +{
1.163 + // We track the last point that -wasn't- in the same place as the current
1.164 + // point so if we pass the edge of the path with a bunch of zero length
1.165 + // paths we still get the correct tangent vector.
1.166 + Point lastPointSinceMove;
1.167 + Point currentPoint;
1.168 + for (uint32_t i = 0; i < mPathOps.size(); i++) {
1.169 + if (mPathOps[i].mType == FlatPathOp::OP_MOVETO) {
1.170 + if (Distance(currentPoint, mPathOps[i].mPoint)) {
1.171 + lastPointSinceMove = currentPoint;
1.172 + }
1.173 + currentPoint = mPathOps[i].mPoint;
1.174 + } else {
1.175 + Float segmentLength = Distance(currentPoint, mPathOps[i].mPoint);
1.176 +
1.177 + if (segmentLength) {
1.178 + lastPointSinceMove = currentPoint;
1.179 + if (segmentLength > aLength) {
1.180 + Point currentVector = mPathOps[i].mPoint - currentPoint;
1.181 + Point tangent = currentVector / segmentLength;
1.182 + if (aTangent) {
1.183 + *aTangent = tangent;
1.184 + }
1.185 + return currentPoint + tangent * aLength;
1.186 + }
1.187 + }
1.188 +
1.189 + aLength -= segmentLength;
1.190 + currentPoint = mPathOps[i].mPoint;
1.191 + }
1.192 + }
1.193 +
1.194 + Point currentVector = currentPoint - lastPointSinceMove;
1.195 + if (aTangent) {
1.196 + if (hypotf(currentVector.x, currentVector.y)) {
1.197 + *aTangent = currentVector / hypotf(currentVector.x, currentVector.y);
1.198 + } else {
1.199 + *aTangent = Point();
1.200 + }
1.201 + }
1.202 + return currentPoint;
1.203 +}
1.204 +
1.205 +// This function explicitly permits aControlPoints to refer to the same object
1.206 +// as either of the other arguments.
1.207 +static void
1.208 +SplitBezier(const BezierControlPoints &aControlPoints,
1.209 + BezierControlPoints *aFirstSegmentControlPoints,
1.210 + BezierControlPoints *aSecondSegmentControlPoints,
1.211 + Float t)
1.212 +{
1.213 + MOZ_ASSERT(aSecondSegmentControlPoints);
1.214 +
1.215 + *aSecondSegmentControlPoints = aControlPoints;
1.216 +
1.217 + Point cp1a = aControlPoints.mCP1 + (aControlPoints.mCP2 - aControlPoints.mCP1) * t;
1.218 + Point cp2a = aControlPoints.mCP2 + (aControlPoints.mCP3 - aControlPoints.mCP2) * t;
1.219 + Point cp1aa = cp1a + (cp2a - cp1a) * t;
1.220 + Point cp3a = aControlPoints.mCP3 + (aControlPoints.mCP4 - aControlPoints.mCP3) * t;
1.221 + Point cp2aa = cp2a + (cp3a - cp2a) * t;
1.222 + Point cp1aaa = cp1aa + (cp2aa - cp1aa) * t;
1.223 + aSecondSegmentControlPoints->mCP4 = aControlPoints.mCP4;
1.224 +
1.225 + if(aFirstSegmentControlPoints) {
1.226 + aFirstSegmentControlPoints->mCP1 = aControlPoints.mCP1;
1.227 + aFirstSegmentControlPoints->mCP2 = cp1a;
1.228 + aFirstSegmentControlPoints->mCP3 = cp1aa;
1.229 + aFirstSegmentControlPoints->mCP4 = cp1aaa;
1.230 + }
1.231 + aSecondSegmentControlPoints->mCP1 = cp1aaa;
1.232 + aSecondSegmentControlPoints->mCP2 = cp2aa;
1.233 + aSecondSegmentControlPoints->mCP3 = cp3a;
1.234 +}
1.235 +
1.236 +static void
1.237 +FlattenBezierCurveSegment(const BezierControlPoints &aControlPoints,
1.238 + PathSink *aSink,
1.239 + Float aTolerance)
1.240 +{
1.241 + /* The algorithm implemented here is based on:
1.242 + * http://cis.usouthal.edu/~hain/general/Publications/Bezier/Bezier%20Offset%20Curves.pdf
1.243 + *
1.244 + * The basic premise is that for a small t the third order term in the
1.245 + * equation of a cubic bezier curve is insignificantly small. This can
1.246 + * then be approximated by a quadratic equation for which the maximum
1.247 + * difference from a linear approximation can be much more easily determined.
1.248 + */
1.249 + BezierControlPoints currentCP = aControlPoints;
1.250 +
1.251 + Float t = 0;
1.252 + while (t < 1.0f) {
1.253 + Point cp21 = currentCP.mCP2 - currentCP.mCP3;
1.254 + Point cp31 = currentCP.mCP3 - currentCP.mCP1;
1.255 +
1.256 + Float s3 = (cp31.x * cp21.y - cp31.y * cp21.x) / hypotf(cp21.x, cp21.y);
1.257 +
1.258 + t = 2 * Float(sqrt(aTolerance / (3. * abs(s3))));
1.259 +
1.260 + if (t >= 1.0f) {
1.261 + aSink->LineTo(aControlPoints.mCP4);
1.262 + break;
1.263 + }
1.264 +
1.265 + Point prevCP2, prevCP3, nextCP1, nextCP2, nextCP3;
1.266 + SplitBezier(currentCP, nullptr, ¤tCP, t);
1.267 +
1.268 + aSink->LineTo(currentCP.mCP1);
1.269 + }
1.270 +}
1.271 +
1.272 +static inline void
1.273 +FindInflectionApproximationRange(BezierControlPoints aControlPoints,
1.274 + Float *aMin, Float *aMax, Float aT,
1.275 + Float aTolerance)
1.276 +{
1.277 + SplitBezier(aControlPoints, nullptr, &aControlPoints, aT);
1.278 +
1.279 + Point cp21 = aControlPoints.mCP2 - aControlPoints.mCP1;
1.280 + Point cp41 = aControlPoints.mCP4 - aControlPoints.mCP1;
1.281 +
1.282 + if (cp21.x == 0 && cp21.y == 0) {
1.283 + // In this case s3 becomes lim[n->0] (cp41.x * n) / n - (cp41.y * n) / n = cp41.x - cp41.y.
1.284 +
1.285 + // Use the absolute value so that Min and Max will correspond with the
1.286 + // minimum and maximum of the range.
1.287 + *aMin = aT - CubicRoot(abs(aTolerance / (cp41.x - cp41.y)));
1.288 + *aMax = aT + CubicRoot(abs(aTolerance / (cp41.x - cp41.y)));
1.289 + return;
1.290 + }
1.291 +
1.292 + Float s3 = (cp41.x * cp21.y - cp41.y * cp21.x) / hypotf(cp21.x, cp21.y);
1.293 +
1.294 + if (s3 == 0) {
1.295 + // This means within the precision we have it can be approximated
1.296 + // infinitely by a linear segment. Deal with this by specifying the
1.297 + // approximation range as extending beyond the entire curve.
1.298 + *aMin = -1.0f;
1.299 + *aMax = 2.0f;
1.300 + return;
1.301 + }
1.302 +
1.303 + Float tf = CubicRoot(abs(aTolerance / s3));
1.304 +
1.305 + *aMin = aT - tf * (1 - aT);
1.306 + *aMax = aT + tf * (1 - aT);
1.307 +}
1.308 +
1.309 +/* Find the inflection points of a bezier curve. Will return false if the
1.310 + * curve is degenerate in such a way that it is best approximated by a straight
1.311 + * line.
1.312 + *
1.313 + * The below algorithm was written by Jeff Muizelaar <jmuizelaar@mozilla.com>, explanation follows:
1.314 + *
1.315 + * The lower inflection point is returned in aT1, the higher one in aT2. In the
1.316 + * case of a single inflection point this will be in aT1.
1.317 + *
1.318 + * The method is inspired by the algorithm in "analysis of in?ection points for planar cubic bezier curve"
1.319 + *
1.320 + * Here are some differences between this algorithm and versions discussed elsewhere in the literature:
1.321 + *
1.322 + * zhang et. al compute a0, d0 and e0 incrementally using the follow formula:
1.323 + *
1.324 + * Point a0 = CP2 - CP1
1.325 + * Point a1 = CP3 - CP2
1.326 + * Point a2 = CP4 - CP1
1.327 + *
1.328 + * Point d0 = a1 - a0
1.329 + * Point d1 = a2 - a1
1.330 +
1.331 + * Point e0 = d1 - d0
1.332 + *
1.333 + * this avoids any multiplications and may or may not be faster than the approach take below.
1.334 + *
1.335 + * "fast, precise flattening of cubic bezier path and ofset curves" by hain et. al
1.336 + * Point a = CP1 + 3 * CP2 - 3 * CP3 + CP4
1.337 + * Point b = 3 * CP1 - 6 * CP2 + 3 * CP3
1.338 + * Point c = -3 * CP1 + 3 * CP2
1.339 + * Point d = CP1
1.340 + * the a, b, c, d can be expressed in terms of a0, d0 and e0 defined above as:
1.341 + * c = 3 * a0
1.342 + * b = 3 * d0
1.343 + * a = e0
1.344 + *
1.345 + *
1.346 + * a = 3a = a.y * b.x - a.x * b.y
1.347 + * b = 3b = a.y * c.x - a.x * c.y
1.348 + * c = 9c = b.y * c.x - b.x * c.y
1.349 + *
1.350 + * The additional multiples of 3 cancel each other out as show below:
1.351 + *
1.352 + * x = (-b + sqrt(b * b - 4 * a * c)) / (2 * a)
1.353 + * x = (-3 * b + sqrt(3 * b * 3 * b - 4 * a * 3 * 9 * c / 3)) / (2 * 3 * a)
1.354 + * x = 3 * (-b + sqrt(b * b - 4 * a * c)) / (2 * 3 * a)
1.355 + * x = (-b + sqrt(b * b - 4 * a * c)) / (2 * a)
1.356 + *
1.357 + * I haven't looked into whether the formulation of the quadratic formula in
1.358 + * hain has any numerical advantages over the one used below.
1.359 + */
1.360 +static inline void
1.361 +FindInflectionPoints(const BezierControlPoints &aControlPoints,
1.362 + Float *aT1, Float *aT2, uint32_t *aCount)
1.363 +{
1.364 + // Find inflection points.
1.365 + // See www.faculty.idc.ac.il/arik/quality/appendixa.html for an explanation
1.366 + // of this approach.
1.367 + Point A = aControlPoints.mCP2 - aControlPoints.mCP1;
1.368 + Point B = aControlPoints.mCP3 - (aControlPoints.mCP2 * 2) + aControlPoints.mCP1;
1.369 + Point C = aControlPoints.mCP4 - (aControlPoints.mCP3 * 3) + (aControlPoints.mCP2 * 3) - aControlPoints.mCP1;
1.370 +
1.371 + Float a = Float(B.x) * C.y - Float(B.y) * C.x;
1.372 + Float b = Float(A.x) * C.y - Float(A.y) * C.x;
1.373 + Float c = Float(A.x) * B.y - Float(A.y) * B.x;
1.374 +
1.375 + if (a == 0) {
1.376 + // Not a quadratic equation.
1.377 + if (b == 0) {
1.378 + // Instead of a linear acceleration change we have a constant
1.379 + // acceleration change. This means the equation has no solution
1.380 + // and there are no inflection points, unless the constant is 0.
1.381 + // In that case the curve is a straight line, but we'll let
1.382 + // FlattenBezierCurveSegment deal with this.
1.383 + *aCount = 0;
1.384 + return;
1.385 + }
1.386 + *aT1 = -c / b;
1.387 + *aCount = 1;
1.388 + return;
1.389 + } else {
1.390 + Float discriminant = b * b - 4 * a * c;
1.391 +
1.392 + if (discriminant < 0) {
1.393 + // No inflection points.
1.394 + *aCount = 0;
1.395 + } else if (discriminant == 0) {
1.396 + *aCount = 1;
1.397 + *aT1 = -b / (2 * a);
1.398 + } else {
1.399 + /* Use the following formula for computing the roots:
1.400 + *
1.401 + * q = -1/2 * (b + sign(b) * sqrt(b^2 - 4ac))
1.402 + * t1 = q / a
1.403 + * t2 = c / q
1.404 + */
1.405 + Float q = sqrtf(discriminant);
1.406 + if (b < 0) {
1.407 + q = b - q;
1.408 + } else {
1.409 + q = b + q;
1.410 + }
1.411 + q *= Float(-1./2);
1.412 +
1.413 + *aT1 = q / a;
1.414 + *aT2 = c / q;
1.415 + if (*aT1 > *aT2) {
1.416 + std::swap(*aT1, *aT2);
1.417 + }
1.418 + *aCount = 2;
1.419 + }
1.420 + }
1.421 +
1.422 + return;
1.423 +}
1.424 +
1.425 +void
1.426 +FlattenBezier(const BezierControlPoints &aControlPoints,
1.427 + PathSink *aSink, Float aTolerance)
1.428 +{
1.429 + Float t1;
1.430 + Float t2;
1.431 + uint32_t count;
1.432 +
1.433 + FindInflectionPoints(aControlPoints, &t1, &t2, &count);
1.434 +
1.435 + // Check that at least one of the inflection points is inside [0..1]
1.436 + if (count == 0 || ((t1 < 0 || t1 > 1.0) && ((t2 < 0 || t2 > 1.0) || count == 1)) ) {
1.437 + FlattenBezierCurveSegment(aControlPoints, aSink, aTolerance);
1.438 + return;
1.439 + }
1.440 +
1.441 + Float t1min = t1, t1max = t1, t2min = t2, t2max = t2;
1.442 +
1.443 + BezierControlPoints remainingCP = aControlPoints;
1.444 +
1.445 + // For both inflection points, calulate the range where they can be linearly
1.446 + // approximated if they are positioned within [0,1]
1.447 + if (count > 0 && t1 >= 0 && t1 < 1.0) {
1.448 + FindInflectionApproximationRange(aControlPoints, &t1min, &t1max, t1, aTolerance);
1.449 + }
1.450 + if (count > 1 && t2 >= 0 && t2 < 1.0) {
1.451 + FindInflectionApproximationRange(aControlPoints, &t2min, &t2max, t2, aTolerance);
1.452 + }
1.453 + BezierControlPoints nextCPs = aControlPoints;
1.454 + BezierControlPoints prevCPs;
1.455 +
1.456 + // Process ranges. [t1min, t1max] and [t2min, t2max] are approximated by line
1.457 + // segments.
1.458 + if (t1min > 0) {
1.459 + // Flatten the Bezier up until the first inflection point's approximation
1.460 + // point.
1.461 + SplitBezier(aControlPoints, &prevCPs,
1.462 + &remainingCP, t1min);
1.463 + FlattenBezierCurveSegment(prevCPs, aSink, aTolerance);
1.464 + }
1.465 + if (t1max >= 0 && t1max < 1.0 && (count == 1 || t2min > t1max)) {
1.466 + // The second inflection point's approximation range begins after the end
1.467 + // of the first, approximate the first inflection point by a line and
1.468 + // subsequently flatten up until the end or the next inflection point.
1.469 + SplitBezier(aControlPoints, nullptr, &nextCPs, t1max);
1.470 +
1.471 + aSink->LineTo(nextCPs.mCP1);
1.472 +
1.473 + if (count == 1 || (count > 1 && t2min >= 1.0)) {
1.474 + // No more inflection points to deal with, flatten the rest of the curve.
1.475 + FlattenBezierCurveSegment(nextCPs, aSink, aTolerance);
1.476 + }
1.477 + } else if (count > 1 && t2min > 1.0) {
1.478 + // We've already concluded t2min <= t1max, so if this is true the
1.479 + // approximation range for the first inflection point runs past the
1.480 + // end of the curve, draw a line to the end and we're done.
1.481 + aSink->LineTo(aControlPoints.mCP4);
1.482 + return;
1.483 + }
1.484 +
1.485 + if (count > 1 && t2min < 1.0 && t2max > 0) {
1.486 + if (t2min > 0 && t2min < t1max) {
1.487 + // In this case the t2 approximation range starts inside the t1
1.488 + // approximation range.
1.489 + SplitBezier(aControlPoints, nullptr, &nextCPs, t1max);
1.490 + aSink->LineTo(nextCPs.mCP1);
1.491 + } else if (t2min > 0 && t1max > 0) {
1.492 + SplitBezier(aControlPoints, nullptr, &nextCPs, t1max);
1.493 +
1.494 + // Find a control points describing the portion of the curve between t1max and t2min.
1.495 + Float t2mina = (t2min - t1max) / (1 - t1max);
1.496 + SplitBezier(nextCPs, &prevCPs, &nextCPs, t2mina);
1.497 + FlattenBezierCurveSegment(prevCPs, aSink, aTolerance);
1.498 + } else if (t2min > 0) {
1.499 + // We have nothing interesting before t2min, find that bit and flatten it.
1.500 + SplitBezier(aControlPoints, &prevCPs, &nextCPs, t2min);
1.501 + FlattenBezierCurveSegment(prevCPs, aSink, aTolerance);
1.502 + }
1.503 + if (t2max < 1.0) {
1.504 + // Flatten the portion of the curve after t2max
1.505 + SplitBezier(aControlPoints, nullptr, &nextCPs, t2max);
1.506 +
1.507 + // Draw a line to the start, this is the approximation between t2min and
1.508 + // t2max.
1.509 + aSink->LineTo(nextCPs.mCP1);
1.510 + FlattenBezierCurveSegment(nextCPs, aSink, aTolerance);
1.511 + } else {
1.512 + // Our approximation range extends beyond the end of the curve.
1.513 + aSink->LineTo(aControlPoints.mCP4);
1.514 + return;
1.515 + }
1.516 + }
1.517 +}
1.518 +
1.519 +}
1.520 +}
