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
};
342

343