/src/mozilla-central/gfx/2d/BezierUtils.cpp

Source (jump to first uncovered line)
/* -*- 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;
  Float B = a * b + c * d;
  Float C = a * a + c * c - 1;

  Float S = sqrt(B * B - A * C);

  Float n1 = - B + S;
  Float n2 = - B - S;

#ifdef DEBUG
  Float epsilon = (Float) 0.001;
  MOZ_ASSERT(n1 >= -epsilon);
  MOZ_ASSERT(n2 >= -epsilon);
#endif

  return std::max((n1 < n2 ? n1 : n2) / A, (Float) 0.0);
}

} // namespace gfx
} // namespace mozilla

Coverage Report

Created: 2018-09-25 14:53

Line	Count	Source (jump to first uncovered line)
1		/* -- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -- */
2		/* vim: set ts=8 sts=2 et sw=2 tw=80: */
3		/* This Source Code Form is subject to the terms of the Mozilla Public
4		* License, v. 2.0. If a copy of the MPL was not distributed with this
5		* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7		#include "BezierUtils.h"
8
9		#include "PathHelpers.h"
10
11		namespace mozilla {
12		namespace gfx {
13
14		Point
15		GetBezierPoint(const Bezier& aBezier, Float t)
16	0	{
17	0	Float s = 1.0f - t;
18	0
19	0	return Point(
20	0	aBezier.mPoints[0].x * s * s * s +
21	0	3.0f * aBezier.mPoints[1].x * t * s * s +
22	0	3.0f * aBezier.mPoints[2].x * t * t * s +
23	0	aBezier.mPoints[3].x * t * t * t,
24	0	aBezier.mPoints[0].y * s * s * s +
25	0	3.0f * aBezier.mPoints[1].y * t * s * s +
26	0	3.0f * aBezier.mPoints[2].y * t * t * s +
27	0	aBezier.mPoints[3].y * t * t * t
28	0	);
29	0	}
30
31		Point
32		GetBezierDifferential(const Bezier& aBezier, Float t)
33	0	{
34	0	// Return P'(t).
35	0
36	0	Float s = 1.0f - t;
37	0
38	0	return Point(
39	0	-3.0f * ((aBezier.mPoints[0].x - aBezier.mPoints[1].x) * s * s +
40	0	2.0f * (aBezier.mPoints[1].x - aBezier.mPoints[2].x) * t * s +
41	0	(aBezier.mPoints[2].x - aBezier.mPoints[3].x) * t * t),
42	0	-3.0f * ((aBezier.mPoints[0].y - aBezier.mPoints[1].y) * s * s +
43	0	2.0f * (aBezier.mPoints[1].y - aBezier.mPoints[2].y) * t * s+
44	0	(aBezier.mPoints[2].y - aBezier.mPoints[3].y) * t * t)
45	0	);
46	0	}
47
48		Point
49		GetBezierDifferential2(const Bezier& aBezier, Float t)
50	0	{
51	0	// Return P''(t).
52	0
53	0	Float s = 1.0f - t;
54	0
55	0	return Point(
56	0	6.0f * ((aBezier.mPoints[0].x - aBezier.mPoints[1].x) * s -
57	0	(aBezier.mPoints[1].x - aBezier.mPoints[2].x) * (s - t) -
58	0	(aBezier.mPoints[2].x - aBezier.mPoints[3].x) * t),
59	0	6.0f * ((aBezier.mPoints[0].y - aBezier.mPoints[1].y) * s -
60	0	(aBezier.mPoints[1].y - aBezier.mPoints[2].y) * (s - t) -
61	0	(aBezier.mPoints[2].y - aBezier.mPoints[3].y) * t)
62	0	);
63	0	}
64
65		Float
66		GetBezierLength(const Bezier& aBezier, Float a, Float b)
67	0	{
68	0	if (a < 0.5f && b > 0.5f) {
69	0	// To increase the accuracy, split into two parts.
70	0	return GetBezierLength(aBezier, a, 0.5f) +
71	0	GetBezierLength(aBezier, 0.5f, b);
72	0	}
73	0
74	0	// Calculate length of simple bezier curve with Simpson's rule.
75	0	// _
76	0	// / b
77	0	// length = \| \|P'(x)\| dx
78	0	// _/ a
79	0	//
80	0	// b - a a + b
81	0	// = ----- [ \|P'(a)\| + 4 \|P'(-----)\| + \|P'(b)\| ]
82	0	// 6 2
83	0
84	0	Float fa = GetBezierDifferential(aBezier, a).Length();
85	0	Float fab = GetBezierDifferential(aBezier, (a + b) / 2.0f).Length();
86	0	Float fb = GetBezierDifferential(aBezier, b).Length();
87	0
88	0	return (b - a) / 6.0f * (fa + 4.0f * fab + fb);
89	0	}
90
91		static void
92		SplitBezierA(Bezier* aSubBezier, const Bezier& aBezier, Float t)
93	0	{
94	0	// Split bezier curve into [0,t] and [t,1] parts, and return [0,t] part.
95	0
96	0	Float s = 1.0f - t;
97	0
98	0	Point tmp1;
99	0	Point tmp2;
100	0
101	0	aSubBezier->mPoints[0] = aBezier.mPoints[0];
102	0
103	0	aSubBezier->mPoints[1] = aBezier.mPoints[0] * s + aBezier.mPoints[1] * t;
104	0	tmp1 = aBezier.mPoints[1] * s + aBezier.mPoints[2] * t;
105	0	tmp2 = aBezier.mPoints[2] * s + aBezier.mPoints[3] * t;
106	0
107	0	aSubBezier->mPoints[2] = aSubBezier->mPoints[1] * s + tmp1 * t;
108	0	tmp1 = tmp1 * s + tmp2 * t;
109	0
110	0	aSubBezier->mPoints[3] = aSubBezier->mPoints[2] * s + tmp1 * t;
111	0	}
112
113		static void
114		SplitBezierB(Bezier* aSubBezier, const Bezier& aBezier, Float t)
115	0	{
116	0	// Split bezier curve into [0,t] and [t,1] parts, and return [t,1] part.
117	0
118	0	Float s = 1.0f - t;
119	0
120	0	Point tmp1;
121	0	Point tmp2;
122	0
123	0	aSubBezier->mPoints[3] = aBezier.mPoints[3];
124	0
125	0	aSubBezier->mPoints[2] = aBezier.mPoints[2] * s + aBezier.mPoints[3] * t;
126	0	tmp1 = aBezier.mPoints[1] * s + aBezier.mPoints[2] * t;
127	0	tmp2 = aBezier.mPoints[0] * s + aBezier.mPoints[1] * t;
128	0
129	0	aSubBezier->mPoints[1] = tmp1 * s + aSubBezier->mPoints[2] * t;
130	0	tmp1 = tmp2 * s + tmp1 * t;
131	0
132	0	aSubBezier->mPoints[0] = tmp1 * s + aSubBezier->mPoints[1] * t;
133	0	}
134
135		void
136		GetSubBezier(Bezier* aSubBezier, const Bezier& aBezier, Float t1, Float t2)
137	0	{
138	0	Bezier tmp;
139	0	SplitBezierB(&tmp, aBezier, t1);
140	0
141	0	Float range = 1.0f - t1;
142	0	if (range == 0.0f) {
143	0	*aSubBezier = tmp;
144	0	} else {
145	0	SplitBezierA(aSubBezier, tmp, (t2 - t1) / range);
146	0	}
147	0	}
148
149		static Point
150		BisectBezierNearestPoint(const Bezier& aBezier, const Point& aTarget,
151		Float* aT)
152	0	{
153	0	// Find a nearest point on bezier curve with Binary search.
154	0	// Called from FindBezierNearestPoint.
155	0
156	0	Float lower = 0.0f;
157	0	Float upper = 1.0f;
158	0	Float t;
159	0
160	0	Point P, lastP;
161	0	const size_t MAX_LOOP = 32;
162	0	const Float DIST_MARGIN = 0.1f;
163	0	const Float DIST_MARGIN_SQUARE = DIST_MARGIN * DIST_MARGIN;
164	0	const Float DIFF = 0.0001f;
165	0	for (size_t i = 0; i < MAX_LOOP; i++) {
166	0	t = (upper + lower) / 2.0f;
167	0	P = GetBezierPoint(aBezier, t);
168	0
169	0	// Check if it converged.
170	0	if (i > 0 && (lastP - P).LengthSquare() < DIST_MARGIN_SQUARE) {
171	0	break;
172	0	}
173	0
174	0	Float distSquare = (P - aTarget).LengthSquare();
175	0	if ((GetBezierPoint(aBezier, t + DIFF) - aTarget).LengthSquare() <
176	0	distSquare) {
177	0	lower = t;
178	0	} else if ((GetBezierPoint(aBezier, t - DIFF) - aTarget).LengthSquare() <
179	0	distSquare) {
180	0	upper = t;
181	0	} else {
182	0	break;
183	0	}
184	0
185	0	lastP = P;
186	0	}
187	0
188	0	if (aT) {
189	0	*aT = t;
190	0	}
191	0
192	0	return P;
193	0	}
194
195		Point
196		FindBezierNearestPoint(const Bezier& aBezier, const Point& aTarget,
197		Float aInitialT, Float* aT)
198	0	{
199	0	// Find a nearest point on bezier curve with Newton's method.
200	0	// It converges within 4 iterations in most cases.
201	0	//
202	0	// f(t_n)
203	0	// t_{n+1} = t_n - ---------
204	0	// f'(t_n)
205	0	//
206	0	// d 2
207	0	// f(t) = ---- \| P(t) - aTarget \|
208	0	// dt
209	0
210	0	Float t = aInitialT;
211	0	Point P;
212	0	Point lastP = GetBezierPoint(aBezier, t);
213	0
214	0	const size_t MAX_LOOP = 4;
215	0	const Float DIST_MARGIN = 0.1f;
216	0	const Float DIST_MARGIN_SQUARE = DIST_MARGIN * DIST_MARGIN;
217	0	for (size_t i = 0; i <= MAX_LOOP; i++) {
218	0	Point dP = GetBezierDifferential(aBezier, t);
219	0	Point ddP = GetBezierDifferential2(aBezier, t);
220	0	Float f = 2.0f * (lastP.DotProduct(dP) - aTarget.DotProduct(dP));
221	0	Float df = 2.0f * (dP.DotProduct(dP) + lastP.DotProduct(ddP) -
222	0	aTarget.DotProduct(ddP));
223	0	t = t - f / df;
224	0	P = GetBezierPoint(aBezier, t);
225	0	if ((P - lastP).LengthSquare() < DIST_MARGIN_SQUARE) {
226	0	break;
227	0	}
228	0	lastP = P;
229	0
230	0	if (i == MAX_LOOP) {
231	0	// If aInitialT is too bad, it won't converge in a few iterations,
232	0	// fallback to binary search.
233	0	return BisectBezierNearestPoint(aBezier, aTarget, aT);
234	0	}
235	0	}
236	0
237	0	if (aT) {
238	0	*aT = t;
239	0	}
240	0
241	0	return P;
242	0	}
243
244		void
245		GetBezierPointsForCorner(Bezier* aBezier, Corner aCorner,
246		const Point& aCornerPoint, const Size& aCornerSize)
247	0	{
248	0	// Calculate bezier control points for elliptic arc.
249	0
250	0	const Float signsList[4][2] = {
251	0	{ +1.0f, +1.0f },
252	0	{ -1.0f, +1.0f },
253	0	{ -1.0f, -1.0f },
254	0	{ +1.0f, -1.0f }
255	0	};
256	0	const Float (& signs)[2] = signsList[aCorner];
257	0
258	0	aBezier->mPoints[0] = aCornerPoint;
259	0	aBezier->mPoints[0].x += signs[0] * aCornerSize.width;
260	0
261	0	aBezier->mPoints[1] = aBezier->mPoints[0];
262	0	aBezier->mPoints[1].x -= signs[0] * aCornerSize.width * kKappaFactor;
263	0
264	0	aBezier->mPoints[3] = aCornerPoint;
265	0	aBezier->mPoints[3].y += signs[1] * aCornerSize.height;
266	0
267	0	aBezier->mPoints[2] = aBezier->mPoints[3];
268	0	aBezier->mPoints[2].y -= signs[1] * aCornerSize.height * kKappaFactor;
269	0	}
270
271		Float
272		GetQuarterEllipticArcLength(Float a, Float b)
273	0	{
274	0	// Calculate the approximate length of a quarter elliptic arc formed by radii
275	0	// (a, b), by Ramanujan's approximation of the perimeter p of an ellipse.
276	0	// _ _
277	0	// \| 2 \|
278	0	// \| 3 * (a - b) \|
279	0	// p = PI \| (a + b) + ------------------------------------------- \|
280	0	// \| 2 2 \|
281	0	// \|_ 10 * (a + b) + sqrt(a + 14 * a * b + b ) _\|
282	0	//
283	0	// _ _
284	0	// \| 2 \|
285	0	// \| 3 * (a - b) \|
286	0	// = PI \| (a + b) + -------------------------------------------------- \|
287	0	// \| 2 2 \|
288	0	// \|_ 10 * (a + b) + sqrt(4 * (a + b) - 3 * (a - b) ) _\|
289	0	//
290	0	// _ _
291	0	// \| 2 \|
292	0	// \| 3 * S \|
293	0	// = PI \| A + -------------------------------------- \|
294	0	// \| 2 2 \|
295	0	// \|_ 10 * A + sqrt(4 * A - 3 * S ) _\|
296	0	//
297	0	// where A = a + b, S = a - b
298	0
299	0	Float A = a + b, S = a - b;
300	0	Float A2 = A * A, S2 = S * S;
301	0	Float p = M_PI * (A + 3.0f * S2 / (10.0f * A + sqrt(4.0f * A2 - 3.0f * S2)));
302	0	return p / 4.0f;
303	0	}
304
305		Float
306		CalculateDistanceToEllipticArc(const Point& P, const Point& normal,
307		const Point& origin, Float width, Float height)
308	0	{
309	0	// Solve following equations with n and return smaller n.
310	0	//
311	0	// / (x, y) = P + n * normal
312	0	// \|
313	0	// < _ _ 2 _ _ 2
314	0	// \| \| x - origin.x \| \| y - origin.y \|
315	0	// \| \| ------------ \| + \| ------------ \| = 1
316	0	// \ \|_ width _\| \|_ height _\|
317	0
318	0	Float a = (P.x - origin.x) / width;
319	0	Float b = normal.x / width;
320	0	Float c = (P.y - origin.y) / height;
321	0	Float d = normal.y / height;
322	0
323	0	Float A = b * b + d * d;
324	0	Float B = a * b + c * d;
325	0	Float C = a * a + c * c - 1;
326	0
327	0	Float S = sqrt(B * B - A * C);
328	0
329	0	Float n1 = - B + S;
330	0	Float n2 = - B - S;
331	0
332		#ifdef DEBUG
333		Float epsilon = (Float) 0.001;
334		MOZ_ASSERT(n1 >= -epsilon);
335		MOZ_ASSERT(n2 >= -epsilon);
336		#endif
337
338	0	return std::max((n1 < n2 ? n1 : n2) / A, (Float) 0.0);
339	0	}
340
341		} // namespace gfx
342		} // namespace mozilla