From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- gfx/2d/BezierUtils.cpp | 326 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 326 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 0000000000..8c80d1c43f --- /dev/null +++ b/gfx/2d/BezierUtils.cpp @@ -0,0 +1,326 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* 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, 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; + // In the quadratic formulat B would be 2*(a*b+c*d), however we factor the 2 + // out Here which cancels out later. + Float B = a * b + c * d; + Float C = a * a + c * c - 1.0; + + Float signB = 1.0; + if (B < 0.0) { + signB = -1.0; + } + + // 2nd degree polynomials are typically computed using the formulae + // r1 = -(B - sqrt(delta)) / (2 * A) + // r2 = -(B + sqrt(delta)) / (2 * A) + // However B - sqrt(delta) can be an inportant source of precision loss for + // one of the roots when computing the difference between two similar and + // large numbers. To avoid that we pick the root with no precision loss in r1 + // and compute r2 using the Citardauq formula. + // Factoring out 2 from B earlier let + Float S = B + signB * sqrt(B * B - A * C); + Float r1 = -S / A; + Float r2 = -C / S; + +#ifdef DEBUG + Float epsilon = (Float)0.001; + MOZ_ASSERT(r1 >= -epsilon); + MOZ_ASSERT(r2 >= -epsilon); +#endif + + return std::max((r1 < r2 ? r1 : r2), (Float)0.0); +} + +} // namespace gfx +} // namespace mozilla -- cgit v1.2.3