1/* 2 * Copyright (C) 2014 Apple Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' 14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS 17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 23 * THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26WebInspector.UnitBezier = function(x1, y1, x2, y2) 27{ 28 WebInspector.Object.call(this); 29 30 // Calculate the polynomial coefficients, implicit first and last control points are (0,0) and (1,1). 31 this._cx = 3.0 * x1; 32 this._bx = 3.0 * (x2 - x1) - this._cx; 33 this._ax = 1.0 - this._cx - this._bx; 34 35 this._cy = 3.0 * y1; 36 this._by = 3.0 * (y2 - y1) - this._cy; 37 this._ay = 1.0 - this._cy - this._by; 38}; 39 40WebInspector.UnitBezier.prototype = { 41 constructor: WebInspector.UnitBezier, 42 43 // Public 44 45 solve: function(x, epsilon) 46 { 47 return this._sampleCurveY(this._solveCurveX(x, epsilon)); 48 }, 49 50 // Private 51 52 _sampleCurveX: function(t) 53 { 54 // `ax t^3 + bx t^2 + cx t' expanded using Horner's rule. 55 return ((this._ax * t + this._bx) * t + this._cx) * t; 56 }, 57 58 _sampleCurveY: function(t) 59 { 60 return ((this._ay * t + this._by) * t + this._cy) * t; 61 }, 62 63 _sampleCurveDerivativeX: function(t) 64 { 65 return (3.0 * this._ax * t + 2.0 * this._bx) * t + this._cx; 66 }, 67 68 // Given an x value, find a parametric value it came from. 69 _solveCurveX: function(x, epsilon) 70 { 71 var t0, t1, t2, x2, d2, i; 72 73 // First try a few iterations of Newton's method -- normally very fast. 74 for (t2 = x, i = 0; i < 8; i++) { 75 x2 = this._sampleCurveX(t2) - x; 76 if (Math.abs(x2) < epsilon) 77 return t2; 78 d2 = this._sampleCurveDerivativeX(t2); 79 if (Math.abs(d2) < 1e-6) 80 break; 81 t2 = t2 - x2 / d2; 82 } 83 84 // Fall back to the bisection method for reliability. 85 t0 = 0.0; 86 t1 = 1.0; 87 t2 = x; 88 89 if (t2 < t0) 90 return t0; 91 if (t2 > t1) 92 return t1; 93 94 while (t0 < t1) { 95 x2 = this._sampleCurveX(t2); 96 if (Math.abs(x2 - x) < epsilon) 97 return t2; 98 if (x > x2) 99 t0 = t2; 100 else 101 t1 = t2; 102 t2 = (t1 - t0) * 0.5 + t0; 103 } 104 105 // Failure. 106 return t2; 107 } 108}; 109