1 /* 2 * Copyright 2023 Google LLC 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 #ifndef SkBezierCurves_DEFINED 8 #define SkBezierCurves_DEFINED 9 10 #include "include/private/base/SkSpan_impl.h" 11 12 #include <array> 13 14 struct SkPoint; 15 16 /** 17 * Utilities for dealing with cubic Bézier curves. These have a start XY 18 * point, an end XY point, and two control XY points in between. They take 19 * a parameter t which is between 0 and 1 (inclusive) which is used to 20 * interpolate between the start and end points, via a route dictated by 21 * the control points, and return a new XY point. 22 * 23 * We store a Bézier curve as an array of 8 floats or doubles, where 24 * the even indices are the X coordinates, and the odd indices are the Y 25 * coordinates. 26 */ 27 class SkBezierCubic { 28 public: 29 30 /** 31 * Evaluates the cubic Bézier curve for a given t. It returns an X and Y coordinate 32 * following the formula, which does the interpolation mentioned above. 33 * X(t) = X_0*(1-t)^3 + 3*X_1*t(1-t)^2 + 3*X_2*t^2(1-t) + X_3*t^3 34 * Y(t) = Y_0*(1-t)^3 + 3*Y_1*t(1-t)^2 + 3*Y_2*t^2(1-t) + Y_3*t^3 35 * 36 * t is typically in the range [0, 1], but this function will not assert that, 37 * as Bézier curves are well-defined for any real number input. 38 */ 39 static std::array<double, 2> EvalAt(const double curve[8], double t); 40 41 /** 42 * Splits the provided Bézier curve at the location t, resulting in two 43 * Bézier curves that share a point (the end point from curve 1 44 * and the start point from curve 2 are the same). 45 * 46 * t must be in the interval [0, 1]. 47 * 48 * The provided twoCurves array will be filled such that indices 49 * 0-7 are the first curve (representing the interval [0, t]), and 50 * indices 6-13 are the second curve (representing [t, 1]). 51 */ 52 static void Subdivide(const double curve[8], double t, 53 double twoCurves[14]); 54 55 /** 56 * Converts the provided Bézier curve into the the equivalent cubic 57 * f(t) = A*t^3 + B*t^2 + C*t + D 58 * where f(t) will represent Y coordinates over time if yValues is 59 * true and the X coordinates if yValues is false. 60 * 61 * In effect, this turns the control points into an actual line, representing 62 * the x or y values. 63 */ 64 static std::array<double, 4> ConvertToPolynomial(const double curve[8], bool yValues); 65 66 static SkSpan<const float> IntersectWithHorizontalLine( 67 SkSpan<const SkPoint> controlPoints, float yIntercept, 68 float intersectionStorage[3]); 69 70 static SkSpan<const float> Intersect( 71 double AX, double BX, double CX, double DX, 72 double AY, double BY, double CY, double DY, 73 float toIntersect, float intersectionsStorage[3]); 74 }; 75 76 class SkBezierQuad { 77 public: 78 static SkSpan<const float> IntersectWithHorizontalLine( 79 SkSpan<const SkPoint> controlPoints, float yIntercept, 80 float intersectionStorage[2]); 81 82 /** 83 * Given 84 * AY*t^2 -2*BY*t + CY = 0 and AX*t^2 - 2*BX*t + CX = 0, 85 * 86 * Find the t where AY*t^2 - 2*BY*t + CY - y = 0, then return AX*t^2 + - 2*BX*t + CX 87 * where t is on [0, 1]. 88 * 89 * - y - is the height of the line which intersects the quadratic. 90 * - intersectionStorage - is the array to hold the return data pointed to in the span. 91 * 92 * Returns a span with the intersections of yIntercept, and the quadratic formed by A, B, 93 * and C. 94 */ 95 static SkSpan<const float> Intersect( 96 double AX, double BX, double CX, 97 double AY, double BY, double CY, 98 double yIntercept, 99 float intersectionStorage[2]); 100 }; 101 102 #endif // SkBezierCurves_DEFINED 103