michael@0: 
michael@0: /*
michael@0:  * Copyright 2011 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: #include "SkCubicInterval.h"
michael@0: 
michael@0: static SkScalar eval_cubic(SkScalar c1, SkScalar c2, SkScalar c3,
michael@0:                            SkScalar t) {
michael@0:     return SkScalarMul(SkScalarMul(SkScalarMul(c3, t) + c2, t) + c1, t);
michael@0: }
michael@0: 
michael@0: static SkScalar find_cubic_t(SkScalar c1, SkScalar c2, SkScalar c3,
michael@0:                              SkScalar targetX) {
michael@0:     SkScalar minT = 0;
michael@0:     SkScalar maxT = SK_Scalar1;
michael@0:     SkScalar t;
michael@0: 
michael@0:     for (;;) {
michael@0:         t = SkScalarAve(minT, maxT);
michael@0:         SkScalar x = eval_cubic(c1, c2, c3, t);
michael@0:         if (SkScalarNearlyZero(x - targetX)) {
michael@0:             break;
michael@0:         }
michael@0:         // subdivide the range and try again
michael@0:         if (x < targetX) {
michael@0:             minT = t;
michael@0:         } else {
michael@0:             maxT = t;
michael@0:         }
michael@0:     }
michael@0:     return t;
michael@0: }
michael@0: 
michael@0: /*
michael@0:     a(1-t)^3 + 3bt(1-t)^2 + 3ct^2(1-t) + dt^3
michael@0:     a: [0, 0]
michael@0:     d: [1, 1]
michael@0: 
michael@0:     3bt - 6bt^2 + 3bt^3 + 3ct^2 - 3ct^3 + t^3
michael@0:     C1 = t^1: 3b
michael@0:     C2 = t^2: 3c - 6b
michael@0:     C3 = t^3: 3b - 3c + 1
michael@0: 
michael@0:     ((C3*t + C2)*t + C1)*t
michael@0:  */
michael@0: SkScalar SkEvalCubicInterval(SkScalar x1, SkScalar y1,
michael@0:                              SkScalar x2, SkScalar y2,
michael@0:                              SkScalar unitX) {
michael@0:     x1 = SkScalarPin(x1, 0, SK_Scalar1);
michael@0:     x2 = SkScalarPin(x2, 0, SK_Scalar1);
michael@0:     unitX = SkScalarPin(unitX, 0, SK_Scalar1);
michael@0: 
michael@0:     // First compute our coefficients in X
michael@0:     x1 *= 3;
michael@0:     x2 *= 3;
michael@0: 
michael@0:     // now search for t given unitX
michael@0:     SkScalar t = find_cubic_t(x1, x2 - 2*x1, x1 - x2 + SK_Scalar1, unitX);
michael@0: 
michael@0:     // now evaluate the cubic in Y
michael@0:     y1 *= 3;
michael@0:     y2 *= 3;
michael@0:     return eval_cubic(y1, y2 - 2*y1, y1 - y2 + SK_Scalar1, t);
michael@0: }