1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2011 Google Inc. 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 8161b00bae2c759b157bb5f1141f497f706443902reed@android.com#include "SkCubicInterval.h" 9161b00bae2c759b157bb5f1141f497f706443902reed@android.com 10161b00bae2c759b157bb5f1141f497f706443902reed@android.comstatic SkScalar eval_cubic(SkScalar c1, SkScalar c2, SkScalar c3, 11161b00bae2c759b157bb5f1141f497f706443902reed@android.com SkScalar t) { 12161b00bae2c759b157bb5f1141f497f706443902reed@android.com return SkScalarMul(SkScalarMul(SkScalarMul(c3, t) + c2, t) + c1, t); 13161b00bae2c759b157bb5f1141f497f706443902reed@android.com} 14161b00bae2c759b157bb5f1141f497f706443902reed@android.com 15161b00bae2c759b157bb5f1141f497f706443902reed@android.comstatic SkScalar find_cubic_t(SkScalar c1, SkScalar c2, SkScalar c3, 16161b00bae2c759b157bb5f1141f497f706443902reed@android.com SkScalar targetX) { 17161b00bae2c759b157bb5f1141f497f706443902reed@android.com SkScalar minT = 0; 18161b00bae2c759b157bb5f1141f497f706443902reed@android.com SkScalar maxT = SK_Scalar1; 19161b00bae2c759b157bb5f1141f497f706443902reed@android.com SkScalar t; 20161b00bae2c759b157bb5f1141f497f706443902reed@android.com 21161b00bae2c759b157bb5f1141f497f706443902reed@android.com for (;;) { 22161b00bae2c759b157bb5f1141f497f706443902reed@android.com t = SkScalarAve(minT, maxT); 23161b00bae2c759b157bb5f1141f497f706443902reed@android.com SkScalar x = eval_cubic(c1, c2, c3, t); 24161b00bae2c759b157bb5f1141f497f706443902reed@android.com if (SkScalarNearlyZero(x - targetX)) { 25161b00bae2c759b157bb5f1141f497f706443902reed@android.com break; 26161b00bae2c759b157bb5f1141f497f706443902reed@android.com } 27161b00bae2c759b157bb5f1141f497f706443902reed@android.com // subdivide the range and try again 28161b00bae2c759b157bb5f1141f497f706443902reed@android.com if (x < targetX) { 29161b00bae2c759b157bb5f1141f497f706443902reed@android.com minT = t; 30161b00bae2c759b157bb5f1141f497f706443902reed@android.com } else { 31161b00bae2c759b157bb5f1141f497f706443902reed@android.com maxT = t; 32161b00bae2c759b157bb5f1141f497f706443902reed@android.com } 33161b00bae2c759b157bb5f1141f497f706443902reed@android.com } 34161b00bae2c759b157bb5f1141f497f706443902reed@android.com return t; 35161b00bae2c759b157bb5f1141f497f706443902reed@android.com} 36161b00bae2c759b157bb5f1141f497f706443902reed@android.com 37161b00bae2c759b157bb5f1141f497f706443902reed@android.com/* 38161b00bae2c759b157bb5f1141f497f706443902reed@android.com a(1-t)^3 + 3bt(1-t)^2 + 3ct^2(1-t) + dt^3 39161b00bae2c759b157bb5f1141f497f706443902reed@android.com a: [0, 0] 40161b00bae2c759b157bb5f1141f497f706443902reed@android.com d: [1, 1] 41161b00bae2c759b157bb5f1141f497f706443902reed@android.com 42161b00bae2c759b157bb5f1141f497f706443902reed@android.com 3bt - 6bt^2 + 3bt^3 + 3ct^2 - 3ct^3 + t^3 43161b00bae2c759b157bb5f1141f497f706443902reed@android.com C1 = t^1: 3b 44161b00bae2c759b157bb5f1141f497f706443902reed@android.com C2 = t^2: 3c - 6b 45161b00bae2c759b157bb5f1141f497f706443902reed@android.com C3 = t^3: 3b - 3c + 1 46161b00bae2c759b157bb5f1141f497f706443902reed@android.com 47161b00bae2c759b157bb5f1141f497f706443902reed@android.com ((C3*t + C2)*t + C1)*t 48161b00bae2c759b157bb5f1141f497f706443902reed@android.com */ 49161b00bae2c759b157bb5f1141f497f706443902reed@android.comSkScalar SkEvalCubicInterval(SkScalar x1, SkScalar y1, 50161b00bae2c759b157bb5f1141f497f706443902reed@android.com SkScalar x2, SkScalar y2, 51161b00bae2c759b157bb5f1141f497f706443902reed@android.com SkScalar unitX) { 52161b00bae2c759b157bb5f1141f497f706443902reed@android.com x1 = SkScalarPin(x1, 0, SK_Scalar1); 53161b00bae2c759b157bb5f1141f497f706443902reed@android.com x2 = SkScalarPin(x2, 0, SK_Scalar1); 54161b00bae2c759b157bb5f1141f497f706443902reed@android.com unitX = SkScalarPin(unitX, 0, SK_Scalar1); 55161b00bae2c759b157bb5f1141f497f706443902reed@android.com 56161b00bae2c759b157bb5f1141f497f706443902reed@android.com // First compute our coefficients in X 57161b00bae2c759b157bb5f1141f497f706443902reed@android.com x1 *= 3; 58161b00bae2c759b157bb5f1141f497f706443902reed@android.com x2 *= 3; 59161b00bae2c759b157bb5f1141f497f706443902reed@android.com 60161b00bae2c759b157bb5f1141f497f706443902reed@android.com // now search for t given unitX 61161b00bae2c759b157bb5f1141f497f706443902reed@android.com SkScalar t = find_cubic_t(x1, x2 - 2*x1, x1 - x2 + SK_Scalar1, unitX); 62d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 63161b00bae2c759b157bb5f1141f497f706443902reed@android.com // now evaluate the cubic in Y 64161b00bae2c759b157bb5f1141f497f706443902reed@android.com y1 *= 3; 65161b00bae2c759b157bb5f1141f497f706443902reed@android.com y2 *= 3; 66161b00bae2c759b157bb5f1141f497f706443902reed@android.com return eval_cubic(y1, y2 - 2*y1, y1 - y2 + SK_Scalar1, t); 67161b00bae2c759b157bb5f1141f497f706443902reed@android.com} 68