15d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Copyright 2014 The Chromium Authors. All rights reserved. 25d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// found in the LICENSE file. 45d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 55d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "ui/gfx/geometry/cubic_bezier.h" 65d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 75d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include <algorithm> 85d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include <cmath> 95d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "base/logging.h" 115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)namespace gfx { 135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)namespace { 155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)static const double kBezierEpsilon = 1e-7; 175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)static const int MAX_STEPS = 30; 185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 195f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)static double eval_bezier(double p1, double p2, double t) { 205f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const double p1_times_3 = 3.0 * p1; 215f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const double p2_times_3 = 3.0 * p2; 225f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const double h3 = p1_times_3; 235f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const double h1 = p1_times_3 - p2_times_3 + 1.0; 245f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const double h2 = p2_times_3 - 6.0 * p1; 255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return t * (t * (t * h1 + h2) + h3); 265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 285f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)static double eval_bezier_derivative(double p1, double p2, double t) { 295f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const double h1 = 9.0 * p1 - 9.0 * p2 + 3.0; 305f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const double h2 = 6.0 * p2 - 12.0 * p1; 315f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) const double h3 = 3.0 * p1; 325f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return t * (t * h1 + h2) + h3; 335f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)} 345f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 355f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// Finds t such that eval_bezier(x1, x2, t) = x. 365f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// There is a unique solution if x1 and x2 lie within (0, 1). 375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)static double bezier_interp(double x1, 385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) double x2, 395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) double x) { 405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_GE(1.0, x1); 415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_LE(0.0, x1); 425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_GE(1.0, x2); 435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_LE(0.0, x2); 445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) x1 = std::min(std::max(x1, 0.0), 1.0); 465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) x2 = std::min(std::max(x2, 0.0), 1.0); 475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) x = std::min(std::max(x, 0.0), 1.0); 485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // We're just going to do bisection for now (for simplicity), but we could 505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // easily do some newton steps if this turns out to be a bottleneck. 515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) double t = 0.0; 525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) double step = 1.0; 535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) for (int i = 0; i < MAX_STEPS; ++i, step *= 0.5) { 545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) const double error = eval_bezier(x1, x2, t) - x; 555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (std::abs(error) < kBezierEpsilon) 565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) break; 575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) t += error > 0.0 ? -step : step; 585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // We should have terminated the above loop because we got close to x, not 615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // because we exceeded MAX_STEPS. Do a DCHECK here to confirm. 625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) DCHECK_GT(kBezierEpsilon, std::abs(eval_bezier(x1, x2, t) - x)); 635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 645f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return t; 655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} // namespace 685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)CubicBezier::CubicBezier(double x1, double y1, double x2, double y2) 705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) : x1_(x1), 715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) y1_(y1), 725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) x2_(x2), 735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) y2_(y2) { 745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)CubicBezier::~CubicBezier() { 775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)double CubicBezier::Solve(double x) const { 805f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return eval_bezier(y1_, y2_, bezier_interp(x1_, x2_, x)); 815f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)} 825f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 835f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)double CubicBezier::Slope(double x) const { 845f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) double t = bezier_interp(x1_, x2_, x); 855f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) double dx_dt = eval_bezier_derivative(x1_, x2_, t); 865f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) double dy_dt = eval_bezier_derivative(y1_, y2_, t); 875f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return dy_dt / dx_dt; 885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 895d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)void CubicBezier::Range(double* min, double* max) const { 915d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) *min = 0; 925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) *max = 1; 935d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (0 <= y1_ && y1_ < 1 && 0 <= y2_ && y2_ <= 1) 945d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return; 955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 965d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Represent the function's derivative in the form at^2 + bt + c. 975f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // (Technically this is (dy/dt)*(1/3), which is suitable for finding zeros 985f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) // but does not actually give the slope of the curve.) 995d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) double a = 3 * (y1_ - y2_) + 1; 1005d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) double b = 2 * (y2_ - 2 * y1_); 1015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) double c = y1_; 1025d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Check if the derivative is constant. 1045d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (std::abs(a) < kBezierEpsilon && 1055d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::abs(b) < kBezierEpsilon) 1065d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return; 1075d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1085d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // Zeros of the function's derivative. 1095d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) double t_1 = 0; 1105d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) double t_2 = 0; 1115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1125d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (std::abs(a) < kBezierEpsilon) { 1135d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // The function's derivative is linear. 1145d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) t_1 = -c / b; 1155d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } else { 1165d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // The function's derivative is a quadratic. We find the zeros of this 1175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) // quadratic using the quadratic formula. 1185d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) double discriminant = b * b - 4 * a * c; 1195d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (discriminant < 0) 1205d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) return; 1215d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) double discriminant_sqrt = sqrt(discriminant); 1225d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) t_1 = (-b + discriminant_sqrt) / (2 * a); 1235d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) t_2 = (-b - discriminant_sqrt) / (2 * a); 1245d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 1255d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1265d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) double sol_1 = 0; 1275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) double sol_2 = 0; 1285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (0 < t_1 && t_1 < 1) 1305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) sol_1 = eval_bezier(y1_, y2_, t_1); 1315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) if (0 < t_2 && t_2 < 1) 1335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) sol_2 = eval_bezier(y1_, y2_, t_2); 1345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) *min = std::min(std::min(*min, sol_1), sol_2); 1365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) *max = std::max(std::max(*max, sol_1), sol_2); 1375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} 1385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 1395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)} // namespace gfx 140