Line data Source code
1 : /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : // vim:cindent:ts=2:et:sw=2:
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 0 : GetBezierPoint(const Bezier& aBezier, Float t)
16 : {
17 0 : Float s = 1.0f - t;
18 :
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 : }
30 :
31 : Point
32 0 : GetBezierDifferential(const Bezier& aBezier, Float t)
33 : {
34 : // Return P'(t).
35 :
36 0 : Float s = 1.0f - t;
37 :
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 : }
47 :
48 : Point
49 0 : GetBezierDifferential2(const Bezier& aBezier, Float t)
50 : {
51 : // Return P''(t).
52 :
53 0 : Float s = 1.0f - t;
54 :
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 : }
64 :
65 : Float
66 0 : GetBezierLength(const Bezier& aBezier, Float a, Float b)
67 : {
68 0 : if (a < 0.5f && b > 0.5f) {
69 : // To increase the accuracy, split into two parts.
70 0 : return GetBezierLength(aBezier, a, 0.5f) +
71 0 : GetBezierLength(aBezier, 0.5f, b);
72 : }
73 :
74 : // Calculate length of simple bezier curve with Simpson's rule.
75 : // _
76 : // / b
77 : // length = | |P'(x)| dx
78 : // _/ a
79 : //
80 : // b - a a + b
81 : // = ----- [ |P'(a)| + 4 |P'(-----)| + |P'(b)| ]
82 : // 6 2
83 :
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 :
88 0 : return (b - a) / 6.0f * (fa + 4.0f * fab + fb);
89 : }
90 :
91 : static void
92 0 : SplitBezierA(Bezier* aSubBezier, const Bezier& aBezier, Float t)
93 : {
94 : // Split bezier curve into [0,t] and [t,1] parts, and return [0,t] part.
95 :
96 0 : Float s = 1.0f - t;
97 :
98 0 : Point tmp1;
99 0 : Point tmp2;
100 :
101 0 : aSubBezier->mPoints[0] = aBezier.mPoints[0];
102 :
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 :
107 0 : aSubBezier->mPoints[2] = aSubBezier->mPoints[1] * s + tmp1 * t;
108 0 : tmp1 = tmp1 * s + tmp2 * t;
109 :
110 0 : aSubBezier->mPoints[3] = aSubBezier->mPoints[2] * s + tmp1 * t;
111 0 : }
112 :
113 : static void
114 0 : SplitBezierB(Bezier* aSubBezier, const Bezier& aBezier, Float t)
115 : {
116 : // Split bezier curve into [0,t] and [t,1] parts, and return [t,1] part.
117 :
118 0 : Float s = 1.0f - t;
119 :
120 0 : Point tmp1;
121 0 : Point tmp2;
122 :
123 0 : aSubBezier->mPoints[3] = aBezier.mPoints[3];
124 :
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 :
129 0 : aSubBezier->mPoints[1] = tmp1 * s + aSubBezier->mPoints[2] * t;
130 0 : tmp1 = tmp2 * s + tmp1 * t;
131 :
132 0 : aSubBezier->mPoints[0] = tmp1 * s + aSubBezier->mPoints[1] * t;
133 0 : }
134 :
135 : void
136 0 : GetSubBezier(Bezier* aSubBezier, const Bezier& aBezier, Float t1, Float t2)
137 : {
138 0 : Bezier tmp;
139 0 : SplitBezierB(&tmp, aBezier, t1);
140 :
141 0 : Float range = 1.0f - t1;
142 0 : if (range == 0.0f) {
143 0 : *aSubBezier = tmp;
144 : } else {
145 0 : SplitBezierA(aSubBezier, tmp, (t2 - t1) / range);
146 : }
147 0 : }
148 :
149 : static Point
150 0 : BisectBezierNearestPoint(const Bezier& aBezier, const Point& aTarget,
151 : Float* aT)
152 : {
153 : // Find a nearest point on bezier curve with Binary search.
154 : // Called from FindBezierNearestPoint.
155 :
156 0 : Float lower = 0.0f;
157 0 : Float upper = 1.0f;
158 : Float t;
159 :
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 :
169 : // Check if it converged.
170 0 : if (i > 0 && (lastP - P).LengthSquare() < DIST_MARGIN_SQUARE) {
171 0 : break;
172 : }
173 :
174 0 : Float distSquare = (P - aTarget).LengthSquare();
175 0 : if ((GetBezierPoint(aBezier, t + DIFF) - aTarget).LengthSquare() <
176 : distSquare) {
177 0 : lower = t;
178 0 : } else if ((GetBezierPoint(aBezier, t - DIFF) - aTarget).LengthSquare() <
179 : distSquare) {
180 0 : upper = t;
181 : } else {
182 0 : break;
183 : }
184 :
185 0 : lastP = P;
186 : }
187 :
188 0 : if (aT) {
189 0 : *aT = t;
190 : }
191 :
192 0 : return P;
193 : }
194 :
195 : Point
196 0 : FindBezierNearestPoint(const Bezier& aBezier, const Point& aTarget,
197 : Float aInitialT, Float* aT)
198 : {
199 : // Find a nearest point on bezier curve with Newton's method.
200 : // It converges within 4 iterations in most cases.
201 : //
202 : // f(t_n)
203 : // t_{n+1} = t_n - ---------
204 : // f'(t_n)
205 : //
206 : // d 2
207 : // f(t) = ---- | P(t) - aTarget |
208 : // dt
209 :
210 0 : Float t = aInitialT;
211 0 : Point P;
212 0 : Point lastP = GetBezierPoint(aBezier, t);
213 :
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 : }
228 0 : lastP = P;
229 :
230 0 : if (i == MAX_LOOP) {
231 : // If aInitialT is too bad, it won't converge in a few iterations,
232 : // fallback to binary search.
233 0 : return BisectBezierNearestPoint(aBezier, aTarget, aT);
234 : }
235 : }
236 :
237 0 : if (aT) {
238 0 : *aT = t;
239 : }
240 :
241 0 : return P;
242 : }
243 :
244 : void
245 0 : GetBezierPointsForCorner(Bezier* aBezier, Corner aCorner,
246 : const Point& aCornerPoint, const Size& aCornerSize)
247 : {
248 : // Calculate bezier control points for elliptic arc.
249 :
250 : const Float signsList[4][2] = {
251 : { +1.0f, +1.0f },
252 : { -1.0f, +1.0f },
253 : { -1.0f, -1.0f },
254 : { +1.0f, -1.0f }
255 0 : };
256 0 : const Float (& signs)[2] = signsList[aCorner];
257 :
258 0 : aBezier->mPoints[0] = aCornerPoint;
259 0 : aBezier->mPoints[0].x += signs[0] * aCornerSize.width;
260 :
261 0 : aBezier->mPoints[1] = aBezier->mPoints[0];
262 0 : aBezier->mPoints[1].x -= signs[0] * aCornerSize.width * kKappaFactor;
263 :
264 0 : aBezier->mPoints[3] = aCornerPoint;
265 0 : aBezier->mPoints[3].y += signs[1] * aCornerSize.height;
266 :
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 0 : GetQuarterEllipticArcLength(Float a, Float b)
273 : {
274 : // Calculate the approximate length of a quarter elliptic arc formed by radii
275 : // (a, b), by Ramanujan's approximation of the perimeter p of an ellipse.
276 : // _ _
277 : // | 2 |
278 : // | 3 * (a - b) |
279 : // p = PI | (a + b) + ------------------------------------------- |
280 : // | 2 2 |
281 : // |_ 10 * (a + b) + sqrt(a + 14 * a * b + b ) _|
282 : //
283 : // _ _
284 : // | 2 |
285 : // | 3 * (a - b) |
286 : // = PI | (a + b) + -------------------------------------------------- |
287 : // | 2 2 |
288 : // |_ 10 * (a + b) + sqrt(4 * (a + b) - 3 * (a - b) ) _|
289 : //
290 : // _ _
291 : // | 2 |
292 : // | 3 * S |
293 : // = PI | A + -------------------------------------- |
294 : // | 2 2 |
295 : // |_ 10 * A + sqrt(4 * A - 3 * S ) _|
296 : //
297 : // where A = a + b, S = a - b
298 :
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 : }
304 :
305 : Float
306 0 : CalculateDistanceToEllipticArc(const Point& P, const Point& normal,
307 : const Point& origin, Float width, Float height)
308 : {
309 : // Solve following equations with n and return smaller n.
310 : //
311 : // / (x, y) = P + n * normal
312 : // |
313 : // < _ _ 2 _ _ 2
314 : // | | x - origin.x | | y - origin.y |
315 : // | | ------------ | + | ------------ | = 1
316 : // \ |_ width _| |_ height _|
317 :
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 :
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 :
327 0 : Float S = sqrt(B * B - A * C);
328 :
329 0 : Float n1 = (- B + S) / A;
330 0 : Float n2 = (- B - S) / A;
331 :
332 0 : MOZ_ASSERT(n1 >= 0);
333 0 : MOZ_ASSERT(n2 >= 0);
334 :
335 0 : return n1 < n2 ? n1 : n2;
336 : }
337 :
338 : } // namespace gfx
339 : } // namespace mozilla
|
