From 5f8de423f190bbb79a62f804151bc24824fa32d8 Mon Sep 17 00:00:00 2001 From: "Matt A. Tobin" Date: Fri, 2 Feb 2018 04:16:08 -0500 Subject: Add m-esr52 at 52.6.0 --- gfx/2d/BezierUtils.cpp | 339 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 339 insertions(+) create mode 100644 gfx/2d/BezierUtils.cpp (limited to 'gfx/2d/BezierUtils.cpp') diff --git a/gfx/2d/BezierUtils.cpp b/gfx/2d/BezierUtils.cpp new file mode 100644 index 000000000..292c6356b --- /dev/null +++ b/gfx/2d/BezierUtils.cpp @@ -0,0 +1,339 @@ +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +// vim:cindent:ts=2:et:sw=2: +/* 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/. */ + +#include "BezierUtils.h" + +#include "PathHelpers.h" + +namespace mozilla { +namespace gfx { + +Point +GetBezierPoint(const Bezier& aBezier, Float t) +{ + Float s = 1.0f - t; + + return Point( + aBezier.mPoints[0].x * s * s * s + + 3.0f * aBezier.mPoints[1].x * t * s * s + + 3.0f * aBezier.mPoints[2].x * t * t * s + + aBezier.mPoints[3].x * t * t * t, + aBezier.mPoints[0].y * s * s * s + + 3.0f * aBezier.mPoints[1].y * t * s * s + + 3.0f * aBezier.mPoints[2].y * t * t * s + + aBezier.mPoints[3].y * t * t * t + ); +} + +Point +GetBezierDifferential(const Bezier& aBezier, Float t) +{ + // Return P'(t). + + Float s = 1.0f - t; + + return Point( + -3.0f * ((aBezier.mPoints[0].x - aBezier.mPoints[1].x) * s * s + + 2.0f * (aBezier.mPoints[1].x - aBezier.mPoints[2].x) * t * s + + (aBezier.mPoints[2].x - aBezier.mPoints[3].x) * t * t), + -3.0f * ((aBezier.mPoints[0].y - aBezier.mPoints[1].y) * s * s + + 2.0f * (aBezier.mPoints[1].y - aBezier.mPoints[2].y) * t * s+ + (aBezier.mPoints[2].y - aBezier.mPoints[3].y) * t * t) + ); +} + +Point +GetBezierDifferential2(const Bezier& aBezier, Float t) +{ + // Return P''(t). + + Float s = 1.0f - t; + + return Point( + 6.0f * ((aBezier.mPoints[0].x - aBezier.mPoints[1].x) * s - + (aBezier.mPoints[1].x - aBezier.mPoints[2].x) * (s - t) - + (aBezier.mPoints[2].x - aBezier.mPoints[3].x) * t), + 6.0f * ((aBezier.mPoints[0].y - aBezier.mPoints[1].y) * s - + (aBezier.mPoints[1].y - aBezier.mPoints[2].y) * (s - t) - + (aBezier.mPoints[2].y - aBezier.mPoints[3].y) * t) + ); +} + +Float +GetBezierLength(const Bezier& aBezier, Float a, Float b) +{ + if (a < 0.5f && b > 0.5f) { + // To increase the accuracy, split into two parts. + return GetBezierLength(aBezier, a, 0.5f) + + GetBezierLength(aBezier, 0.5f, b); + } + + // Calculate length of simple bezier curve with Simpson's rule. + // _ + // / b + // length = | |P'(x)| dx + // _/ a + // + // b - a a + b + // = ----- [ |P'(a)| + 4 |P'(-----)| + |P'(b)| ] + // 6 2 + + Float fa = GetBezierDifferential(aBezier, a).Length(); + Float fab = GetBezierDifferential(aBezier, (a + b) / 2.0f).Length(); + Float fb = GetBezierDifferential(aBezier, b).Length(); + + return (b - a) / 6.0f * (fa + 4.0f * fab + fb); +} + +static void +SplitBezierA(Bezier* aSubBezier, const Bezier& aBezier, Float t) +{ + // Split bezier curve into [0,t] and [t,1] parts, and return [0,t] part. + + Float s = 1.0f - t; + + Point tmp1; + Point tmp2; + + aSubBezier->mPoints[0] = aBezier.mPoints[0]; + + aSubBezier->mPoints[1] = aBezier.mPoints[0] * s + aBezier.mPoints[1] * t; + tmp1 = aBezier.mPoints[1] * s + aBezier.mPoints[2] * t; + tmp2 = aBezier.mPoints[2] * s + aBezier.mPoints[3] * t; + + aSubBezier->mPoints[2] = aSubBezier->mPoints[1] * s + tmp1 * t; + tmp1 = tmp1 * s + tmp2 * t; + + aSubBezier->mPoints[3] = aSubBezier->mPoints[2] * s + tmp1 * t; +} + +static void +SplitBezierB(Bezier* aSubBezier, const Bezier& aBezier, Float t) +{ + // Split bezier curve into [0,t] and [t,1] parts, and return [t,1] part. + + Float s = 1.0f - t; + + Point tmp1; + Point tmp2; + + aSubBezier->mPoints[3] = aBezier.mPoints[3]; + + aSubBezier->mPoints[2] = aBezier.mPoints[2] * s + aBezier.mPoints[3] * t; + tmp1 = aBezier.mPoints[1] * s + aBezier.mPoints[2] * t; + tmp2 = aBezier.mPoints[0] * s + aBezier.mPoints[1] * t; + + aSubBezier->mPoints[1] = tmp1 * s + aSubBezier->mPoints[2] * t; + tmp1 = tmp2 * s + tmp1 * t; + + aSubBezier->mPoints[0] = tmp1 * s + aSubBezier->mPoints[1] * t; +} + +void +GetSubBezier(Bezier* aSubBezier, const Bezier& aBezier, Float t1, Float t2) +{ + Bezier tmp; + SplitBezierB(&tmp, aBezier, t1); + + Float range = 1.0f - t1; + if (range == 0.0f) { + *aSubBezier = tmp; + } else { + SplitBezierA(aSubBezier, tmp, (t2 - t1) / range); + } +} + +static Point +BisectBezierNearestPoint(const Bezier& aBezier, const Point& aTarget, + Float* aT) +{ + // Find a nearest point on bezier curve with Binary search. + // Called from FindBezierNearestPoint. + + Float lower = 0.0f; + Float upper = 1.0f; + Float t; + + Point P, lastP; + const size_t MAX_LOOP = 32; + const Float DIST_MARGIN = 0.1f; + const Float DIST_MARGIN_SQUARE = DIST_MARGIN * DIST_MARGIN; + const Float DIFF = 0.0001f; + for (size_t i = 0; i < MAX_LOOP; i++) { + t = (upper + lower) / 2.0f; + P = GetBezierPoint(aBezier, t); + + // Check if it converged. + if (i > 0 && (lastP - P).LengthSquare() < DIST_MARGIN_SQUARE) { + break; + } + + Float distSquare = (P - aTarget).LengthSquare(); + if ((GetBezierPoint(aBezier, t + DIFF) - aTarget).LengthSquare() < + distSquare) { + lower = t; + } else if ((GetBezierPoint(aBezier, t - DIFF) - aTarget).LengthSquare() < + distSquare) { + upper = t; + } else { + break; + } + + lastP = P; + } + + if (aT) { + *aT = t; + } + + return P; +} + +Point +FindBezierNearestPoint(const Bezier& aBezier, const Point& aTarget, + Float aInitialT, Float* aT) +{ + // Find a nearest point on bezier curve with Newton's method. + // It converges within 4 iterations in most cases. + // + // f(t_n) + // t_{n+1} = t_n - --------- + // f'(t_n) + // + // d 2 + // f(t) = ---- | P(t) - aTarget | + // dt + + Float t = aInitialT; + Point P; + Point lastP = GetBezierPoint(aBezier, t); + + const size_t MAX_LOOP = 4; + const Float DIST_MARGIN = 0.1f; + const Float DIST_MARGIN_SQUARE = DIST_MARGIN * DIST_MARGIN; + for (size_t i = 0; i <= MAX_LOOP; i++) { + Point dP = GetBezierDifferential(aBezier, t); + Point ddP = GetBezierDifferential2(aBezier, t); + Float f = 2.0f * (lastP.DotProduct(dP) - aTarget.DotProduct(dP)); + Float df = 2.0f * (dP.DotProduct(dP) + lastP.DotProduct(ddP) - + aTarget.DotProduct(ddP)); + t = t - f / df; + P = GetBezierPoint(aBezier, t); + if ((P - lastP).LengthSquare() < DIST_MARGIN_SQUARE) { + break; + } + lastP = P; + + if (i == MAX_LOOP) { + // If aInitialT is too bad, it won't converge in a few iterations, + // fallback to binary search. + return BisectBezierNearestPoint(aBezier, aTarget, aT); + } + } + + if (aT) { + *aT = t; + } + + return P; +} + +void +GetBezierPointsForCorner(Bezier* aBezier, mozilla::css::Corner aCorner, + const Point& aCornerPoint, const Size& aCornerSize) +{ + // Calculate bezier control points for elliptic arc. + + const Float signsList[4][2] = { + { +1.0f, +1.0f }, + { -1.0f, +1.0f }, + { -1.0f, -1.0f }, + { +1.0f, -1.0f } + }; + const Float (& signs)[2] = signsList[aCorner]; + + aBezier->mPoints[0] = aCornerPoint; + aBezier->mPoints[0].x += signs[0] * aCornerSize.width; + + aBezier->mPoints[1] = aBezier->mPoints[0]; + aBezier->mPoints[1].x -= signs[0] * aCornerSize.width * kKappaFactor; + + aBezier->mPoints[3] = aCornerPoint; + aBezier->mPoints[3].y += signs[1] * aCornerSize.height; + + aBezier->mPoints[2] = aBezier->mPoints[3]; + aBezier->mPoints[2].y -= signs[1] * aCornerSize.height * kKappaFactor; +} + +Float +GetQuarterEllipticArcLength(Float a, Float b) +{ + // Calculate the approximate length of a quarter elliptic arc formed by radii + // (a, b), by Ramanujan's approximation of the perimeter p of an ellipse. + // _ _ + // | 2 | + // | 3 * (a - b) | + // p = PI | (a + b) + ------------------------------------------- | + // | 2 2 | + // |_ 10 * (a + b) + sqrt(a + 14 * a * b + b ) _| + // + // _ _ + // | 2 | + // | 3 * (a - b) | + // = PI | (a + b) + -------------------------------------------------- | + // | 2 2 | + // |_ 10 * (a + b) + sqrt(4 * (a + b) - 3 * (a - b) ) _| + // + // _ _ + // | 2 | + // | 3 * S | + // = PI | A + -------------------------------------- | + // | 2 2 | + // |_ 10 * A + sqrt(4 * A - 3 * S ) _| + // + // where A = a + b, S = a - b + + Float A = a + b, S = a - b; + Float A2 = A * A, S2 = S * S; + Float p = M_PI * (A + 3.0f * S2 / (10.0f * A + sqrt(4.0f * A2 - 3.0f * S2))); + return p / 4.0f; +} + +Float +CalculateDistanceToEllipticArc(const Point& P, const Point& normal, + const Point& origin, Float width, Float height) +{ + // Solve following equations with n and return smaller n. + // + // / (x, y) = P + n * normal + // | + // < _ _ 2 _ _ 2 + // | | x - origin.x | | y - origin.y | + // | | ------------ | + | ------------ | = 1 + // \ |_ width _| |_ height _| + + Float a = (P.x - origin.x) / width; + Float b = normal.x / width; + Float c = (P.y - origin.y) / height; + Float d = normal.y / height; + + Float A = b * b + d * d; + Float B = a * b + c * d; + Float C = a * a + c * c - 1; + + Float S = sqrt(B * B - A * C); + + Float n1 = (- B + S) / A; + Float n2 = (- B - S) / A; + + MOZ_ASSERT(n1 >= 0); + MOZ_ASSERT(n2 >= 0); + + return n1 < n2 ? n1 : n2; +} + +} // namespace gfx +} // namespace mozilla -- cgit v1.2.3