Add m-esr52 at 52.6.0

1 files changed, 339 insertions, 0 deletions

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