1
2/*
3 * Copyright 2011 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8#include "SkCubicInterval.h"
9
10static SkScalar eval_cubic(SkScalar c1, SkScalar c2, SkScalar c3,
11                           SkScalar t) {
12    return SkScalarMul(SkScalarMul(SkScalarMul(c3, t) + c2, t) + c1, t);
13}
14
15static SkScalar find_cubic_t(SkScalar c1, SkScalar c2, SkScalar c3,
16                             SkScalar targetX) {
17    SkScalar minT = 0;
18    SkScalar maxT = SK_Scalar1;
19    SkScalar t;
20
21    for (;;) {
22        t = SkScalarAve(minT, maxT);
23        SkScalar x = eval_cubic(c1, c2, c3, t);
24        if (SkScalarNearlyZero(x - targetX)) {
25            break;
26        }
27        // subdivide the range and try again
28        if (x < targetX) {
29            minT = t;
30        } else {
31            maxT = t;
32        }
33    }
34    return t;
35}
36
37/*
38    a(1-t)^3 + 3bt(1-t)^2 + 3ct^2(1-t) + dt^3
39    a: [0, 0]
40    d: [1, 1]
41
42    3bt - 6bt^2 + 3bt^3 + 3ct^2 - 3ct^3 + t^3
43    C1 = t^1: 3b
44    C2 = t^2: 3c - 6b
45    C3 = t^3: 3b - 3c + 1
46
47    ((C3*t + C2)*t + C1)*t
48 */
49SkScalar SkEvalCubicInterval(SkScalar x1, SkScalar y1,
50                             SkScalar x2, SkScalar y2,
51                             SkScalar unitX) {
52    x1 = SkScalarPin(x1, 0, SK_Scalar1);
53    x2 = SkScalarPin(x2, 0, SK_Scalar1);
54    unitX = SkScalarPin(unitX, 0, SK_Scalar1);
55
56    // First compute our coefficients in X
57    x1 *= 3;
58    x2 *= 3;
59
60    // now search for t given unitX
61    SkScalar t = find_cubic_t(x1, x2 - 2*x1, x1 - x2 + SK_Scalar1, unitX);
62
63    // now evaluate the cubic in Y
64    y1 *= 3;
65    y2 *= 3;
66    return eval_cubic(y1, y2 - 2*y1, y1 - y2 + SK_Scalar1, t);
67}
68