Debian Codegraph @

closure-library/closure/goog/math/bezier.js

raw
1 // Copyright 2007 The Closure Library Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15
16 /**
17 * @fileoverview Represents a cubic Bezier curve.
18 *
19 * Uses the deCasteljau algorithm to compute points on the curve.
20 * http://en.wikipedia.org/wiki/De_Casteljau's_algorithm
21 *
22 * Currently it uses an unrolled version of the algorithm for speed. Eventually
23 * it may be useful to use the loop form of the algorithm in order to support
24 * curves of arbitrary degree.
25 *
26 * @author [email protected] (Robby Walker)
27 */
28
29 goog.provide('goog.math.Bezier');
30
31 goog.require('goog.math');
32 goog.require('goog.math.Coordinate');
33
34
35
36 /**
37 * Object representing a cubic bezier curve.
38 * @param {number} x0 X coordinate of the start point.
39 * @param {number} y0 Y coordinate of the start point.
40 * @param {number} x1 X coordinate of the first control point.
41 * @param {number} y1 Y coordinate of the first control point.
42 * @param {number} x2 X coordinate of the second control point.
43 * @param {number} y2 Y coordinate of the second control point.
44 * @param {number} x3 X coordinate of the end point.
45 * @param {number} y3 Y coordinate of the end point.
46 * @struct
47 * @constructor
48 * @final
49 */
50 goog.math.Bezier = function(x0, y0, x1, y1, x2, y2, x3, y3) {
51 /**
52 * X coordinate of the first point.
53 * @type {number}
54 */
55 this.x0 = x0;
56
57 /**
58 * Y coordinate of the first point.
59 * @type {number}
60 */
61 this.y0 = y0;
62
63 /**
64 * X coordinate of the first control point.
65 * @type {number}
66 */
67 this.x1 = x1;
68
69 /**
70 * Y coordinate of the first control point.
71 * @type {number}
72 */
73 this.y1 = y1;
74
75 /**
76 * X coordinate of the second control point.
77 * @type {number}
78 */
79 this.x2 = x2;
80
81 /**
82 * Y coordinate of the second control point.
83 * @type {number}
84 */
85 this.y2 = y2;
86
87 /**
88 * X coordinate of the end point.
89 * @type {number}
90 */
91 this.x3 = x3;
92
93 /**
94 * Y coordinate of the end point.
95 * @type {number}
96 */
97 this.y3 = y3;
98 };
99
100
101 /**
102 * Constant used to approximate ellipses.
103 * See: http://canvaspaint.org/blog/2006/12/ellipse/
104 * @type {number}
105 */
106 goog.math.Bezier.KAPPA = 4 * (Math.sqrt(2) - 1) / 3;
107
108
109 /**
110 * @return {!goog.math.Bezier} A copy of this curve.
111 */
112 goog.math.Bezier.prototype.clone = function() {
113 return new goog.math.Bezier(
114 this.x0, this.y0, this.x1, this.y1, this.x2, this.y2, this.x3, this.y3);
115 };
116
117
118 /**
119 * Test if the given curve is exactly the same as this one.
120 * @param {goog.math.Bezier} other The other curve.
121 * @return {boolean} Whether the given curve is the same as this one.
122 */
123 goog.math.Bezier.prototype.equals = function(other) {
124 return this.x0 == other.x0 && this.y0 == other.y0 && this.x1 == other.x1 &&
125 this.y1 == other.y1 && this.x2 == other.x2 && this.y2 == other.y2 &&
126 this.x3 == other.x3 && this.y3 == other.y3;
127 };
128
129
130 /**
131 * Modifies the curve in place to progress in the opposite direction.
132 */
133 goog.math.Bezier.prototype.flip = function() {
134 var temp = this.x0;
135 this.x0 = this.x3;
136 this.x3 = temp;
137 temp = this.y0;
138 this.y0 = this.y3;
139 this.y3 = temp;
140
141 temp = this.x1;
142 this.x1 = this.x2;
143 this.x2 = temp;
144 temp = this.y1;
145 this.y1 = this.y2;
146 this.y2 = temp;
147 };
148
149
150 /**
151 * Computes the curve's X coordinate at a point between 0 and 1.
152 * @param {number} t The point on the curve to find.
153 * @return {number} The computed coordinate.
154 */
155 goog.math.Bezier.prototype.getPointX = function(t) {
156 // Special case start and end.
157 if (t == 0) {
158 return this.x0;
159 } else if (t == 1) {
160 return this.x3;
161 }
162
163 // Step one - from 4 points to 3
164 var ix0 = goog.math.lerp(this.x0, this.x1, t);
165 var ix1 = goog.math.lerp(this.x1, this.x2, t);
166 var ix2 = goog.math.lerp(this.x2, this.x3, t);
167
168 // Step two - from 3 points to 2
169 ix0 = goog.math.lerp(ix0, ix1, t);
170 ix1 = goog.math.lerp(ix1, ix2, t);
171
172 // Final step - last point
173 return goog.math.lerp(ix0, ix1, t);
174 };
175
176
177 /**
178 * Computes the curve's Y coordinate at a point between 0 and 1.
179 * @param {number} t The point on the curve to find.
180 * @return {number} The computed coordinate.
181 */
182 goog.math.Bezier.prototype.getPointY = function(t) {
183 // Special case start and end.
184 if (t == 0) {
185 return this.y0;
186 } else if (t == 1) {
187 return this.y3;
188 }
189
190 // Step one - from 4 points to 3
191 var iy0 = goog.math.lerp(this.y0, this.y1, t);
192 var iy1 = goog.math.lerp(this.y1, this.y2, t);
193 var iy2 = goog.math.lerp(this.y2, this.y3, t);
194
195 // Step two - from 3 points to 2
196 iy0 = goog.math.lerp(iy0, iy1, t);
197 iy1 = goog.math.lerp(iy1, iy2, t);
198
199 // Final step - last point
200 return goog.math.lerp(iy0, iy1, t);
201 };
202
203
204 /**
205 * Computes the curve at a point between 0 and 1.
206 * @param {number} t The point on the curve to find.
207 * @return {!goog.math.Coordinate} The computed coordinate.
208 */
209 goog.math.Bezier.prototype.getPoint = function(t) {
210 return new goog.math.Coordinate(this.getPointX(t), this.getPointY(t));
211 };
212
213
214 /**
215 * Changes this curve in place to be the portion of itself from [t, 1].
216 * @param {number} t The start of the desired portion of the curve.
217 */
218 goog.math.Bezier.prototype.subdivideLeft = function(t) {
219 if (t == 1) {
220 return;
221 }
222
223 // Step one - from 4 points to 3
224 var ix0 = goog.math.lerp(this.x0, this.x1, t);
225 var iy0 = goog.math.lerp(this.y0, this.y1, t);
226
227 var ix1 = goog.math.lerp(this.x1, this.x2, t);
228 var iy1 = goog.math.lerp(this.y1, this.y2, t);
229
230 var ix2 = goog.math.lerp(this.x2, this.x3, t);
231 var iy2 = goog.math.lerp(this.y2, this.y3, t);
232
233 // Collect our new x1 and y1
234 this.x1 = ix0;
235 this.y1 = iy0;
236
237 // Step two - from 3 points to 2
238 ix0 = goog.math.lerp(ix0, ix1, t);
239 iy0 = goog.math.lerp(iy0, iy1, t);
240
241 ix1 = goog.math.lerp(ix1, ix2, t);
242 iy1 = goog.math.lerp(iy1, iy2, t);
243
244 // Collect our new x2 and y2
245 this.x2 = ix0;
246 this.y2 = iy0;
247
248 // Final step - last point
249 this.x3 = goog.math.lerp(ix0, ix1, t);
250 this.y3 = goog.math.lerp(iy0, iy1, t);
251 };
252
253
254 /**
255 * Changes this curve in place to be the portion of itself from [0, t].
256 * @param {number} t The end of the desired portion of the curve.
257 */
258 goog.math.Bezier.prototype.subdivideRight = function(t) {
259 this.flip();
260 this.subdivideLeft(1 - t);
261 this.flip();
262 };
263
264
265 /**
266 * Changes this curve in place to be the portion of itself from [s, t].
267 * @param {number} s The start of the desired portion of the curve.
268 * @param {number} t The end of the desired portion of the curve.
269 */
270 goog.math.Bezier.prototype.subdivide = function(s, t) {
271 this.subdivideRight(s);
272 this.subdivideLeft((t - s) / (1 - s));
273 };
274
275
276 /**
277 * Computes the position t of a point on the curve given its x coordinate.
278 * That is, for an input xVal, finds t s.t. getPointX(t) = xVal.
279 * As such, the following should always be true up to some small epsilon:
280 * t ~ solvePositionFromXValue(getPointX(t)) for t in [0, 1].
281 * @param {number} xVal The x coordinate of the point to find on the curve.
282 * @return {number} The position t.
283 */
284 goog.math.Bezier.prototype.solvePositionFromXValue = function(xVal) {
285 // Desired precision on the computation.
286 var epsilon = 1e-6;
287
288 // Initial estimate of t using linear interpolation.
289 var t = (xVal - this.x0) / (this.x3 - this.x0);
290 if (t <= 0) {
291 return 0;
292 } else if (t >= 1) {
293 return 1;
294 }
295
296 // Try gradient descent to solve for t. If it works, it is very fast.
297 var tMin = 0;
298 var tMax = 1;
299 var value = 0;
300 for (var i = 0; i < 8; i++) {
301 value = this.getPointX(t);
302 var derivative = (this.getPointX(t + epsilon) - value) / epsilon;
303 if (Math.abs(value - xVal) < epsilon) {
304 return t;
305 } else if (Math.abs(derivative) < epsilon) {
306 break;
307 } else {
308 if (value < xVal) {
309 tMin = t;
310 } else {
311 tMax = t;
312 }
313 t -= (value - xVal) / derivative;
314 }
315 }
316
317 // If the gradient descent got stuck in a local minimum, e.g. because
318 // the derivative was close to 0, use a Dichotomy refinement instead.
319 // We limit the number of interations to 8.
320 for (var i = 0; Math.abs(value - xVal) > epsilon && i < 8; i++) {
321 if (value < xVal) {
322 tMin = t;
323 t = (t + tMax) / 2;
324 } else {
325 tMax = t;
326 t = (t + tMin) / 2;
327 }
328 value = this.getPointX(t);
329 }
330 return t;
331 };
332
333
334 /**
335 * Computes the y coordinate of a point on the curve given its x coordinate.
336 * @param {number} xVal The x coordinate of the point on the curve.
337 * @return {number} The y coordinate of the point on the curve.
338 */
339 goog.math.Bezier.prototype.solveYValueFromXValue = function(xVal) {
340 return this.getPointY(this.solvePositionFromXValue(xVal));
341 };