Flutter Engine
The Flutter Engine
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
Static Public Member Functions | List of all members
SkCubics Class Reference

#include <SkCubics.h>

Static Public Member Functions

static int RootsReal (double A, double B, double C, double D, double solution[3])
 
static int RootsValidT (double A, double B, double C, double D, double solution[3])
 
static int BinarySearchRootsValidT (double A, double B, double C, double D, double solution[3])
 
static double EvalAt (double A, double B, double C, double D, double t)
 
static double EvalAt (double coefficients[4], double t)
 

Detailed Description

Utilities for dealing with cubic formulas with one variable: f(t) = A*t^3 + B*t^2 + C*t + d

Definition at line 16 of file SkCubics.h.

Member Function Documentation

◆ BinarySearchRootsValidT()

int SkCubics::BinarySearchRootsValidT ( double  A,
double  B,
double  C,
double  D,
double  solution[3] 
)
static

Puts up to 3 real solutions to the equation A*t^3 + B*t^2 + C*t + D = 0 in the provided array, with the constraint that t is in the range [0.0, 1.0], and returns how many roots that was. This is a slower method than RootsValidT, but more accurate in circumstances where floating point error gets too big.

Definition at line 208 of file SkCubics.cpp.

209 {
210 if (!SkIsFinite(A, B, C, D)) {
211 return 0;
212 }
213 double regions[4] = {0, 0, 0, 1};
214 // Find local minima and maxima
215 double minMax[2] = {0, 0};
216 int extremaCount = find_extrema_valid_t(A, B, C, minMax);
217 int startIndex = 2 - extremaCount;
218 if (extremaCount == 1) {
219 regions[startIndex + 1] = minMax[0];
220 }
221 if (extremaCount == 2) {
222 // While the roots will be in the range 0 to 1 inclusive, they might not be sorted.
223 regions[startIndex + 1] = std::min(minMax[0], minMax[1]);
224 regions[startIndex + 2] = std::max(minMax[0], minMax[1]);
225 }
226 // Starting at regions[startIndex] and going up through regions[3], we have
227 // an ascending list of numbers in the range 0 to 1.0, between which are the possible
228 // locations of a root.
229 int foundRoots = 0;
230 for (;startIndex < 3; startIndex++) {
231 double root = binary_search(A, B, C, D, regions[startIndex], regions[startIndex + 1]);
232 if (root >= 0) {
233 // Check for duplicates
234 if ((foundRoots < 1 || !approximately_zero(solution[0] - root)) &&
235 (foundRoots < 2 || !approximately_zero(solution[1] - root))) {
236 solution[foundRoots++] = root;
237 }
238 }
239 }
240 return foundRoots;
241}
static double binary_search(double A, double B, double C, double D, double start, double stop)
Definition: SkCubics.cpp:176
static bool approximately_zero(double x)
Definition: SkCubics.cpp:153
static int find_extrema_valid_t(double A, double B, double C, double t[2])
Definition: SkCubics.cpp:159
static bool SkIsFinite(T x, Pack... values)
static float max(float r, float g, float b)
Definition: hsl.cpp:49
static float min(float r, float g, float b)
Definition: hsl.cpp:48
string root
Definition: scale_cpu.py:20

◆ EvalAt() [1/2]

static double SkCubics::EvalAt ( double  A,
double  B,
double  C,
double  D,
double  t 
)
inlinestatic

Evaluates the cubic function with the 4 provided coefficients and the provided variable.

Definition at line 51 of file SkCubics.h.

51 {
52 return std::fma(t, std::fma(t, std::fma(t, A, B), C), D);
53 }
static skvx::float4 fma(const skvx::float4 &f, float m, const skvx::float4 &a)
Definition: SkGeometry.cpp:597

◆ EvalAt() [2/2]

static double SkCubics::EvalAt ( double  coefficients[4],
double  t 
)
inlinestatic

Definition at line 55 of file SkCubics.h.

55 {
56 return EvalAt(coefficients[0], coefficients[1], coefficients[2], coefficients[3], t);
57 }
static double EvalAt(double A, double B, double C, double D, double t)
Definition: SkCubics.h:51

◆ RootsReal()

int SkCubics::RootsReal ( double  A,
double  B,
double  C,
double  D,
double  solution[3] 
)
static

Puts up to 3 real solutions to the equation A*t^3 + B*t^2 + C*t + d = 0 in the provided array and returns how many roots that was.

Definition at line 38 of file SkCubics.cpp.

38 {
39 if (close_to_a_quadratic(A, B)) {
40 return SkQuads::RootsReal(B, C, D, solution);
41 }
42 if (sk_double_nearly_zero(D)) { // 0 is one root
43 int num = SkQuads::RootsReal(A, B, C, solution);
44 for (int i = 0; i < num; ++i) {
45 if (sk_double_nearly_zero(solution[i])) {
46 return num;
47 }
48 }
49 solution[num++] = 0;
50 return num;
51 }
52 if (sk_double_nearly_zero(A + B + C + D)) { // 1 is one root
53 int num = SkQuads::RootsReal(A, A + B, -D, solution);
54 for (int i = 0; i < num; ++i) {
55 if (sk_doubles_nearly_equal_ulps(solution[i], 1)) {
56 return num;
57 }
58 }
59 solution[num++] = 1;
60 return num;
61 }
62 double a, b, c;
63 {
64 // If A is zero (e.g. B was nan and thus close_to_a_quadratic was false), we will
65 // temporarily have infinities rolling about, but will catch that when checking
66 // R2MinusQ3.
67 double invA = sk_ieee_double_divide(1, A);
68 a = B * invA;
69 b = C * invA;
70 c = D * invA;
71 }
72 double a2 = a * a;
73 double Q = (a2 - b * 3) / 9;
74 double R = (2 * a2 * a - 9 * a * b + 27 * c) / 54;
75 double R2 = R * R;
76 double Q3 = Q * Q * Q;
77 double R2MinusQ3 = R2 - Q3;
78 // If one of R2 Q3 is infinite or nan, subtracting them will also be infinite/nan.
79 // If both are infinite or nan, the subtraction will be nan.
80 // In either case, we have no finite roots.
81 if (!SkIsFinite(R2MinusQ3)) {
82 return 0;
83 }
84 double adiv3 = a / 3;
85 double r;
86 double* roots = solution;
87 if (R2MinusQ3 < 0) { // we have 3 real roots
88 // the divide/root can, due to finite precisions, be slightly outside of -1...1
89 const double theta = acos(SkTPin(R / std::sqrt(Q3), -1., 1.));
90 const double neg2RootQ = -2 * std::sqrt(Q);
91
92 r = neg2RootQ * cos(theta / 3) - adiv3;
93 *roots++ = r;
94
95 r = neg2RootQ * cos((theta + 2 * PI) / 3) - adiv3;
96 if (!nearly_equal(solution[0], r)) {
97 *roots++ = r;
98 }
99 r = neg2RootQ * cos((theta - 2 * PI) / 3) - adiv3;
100 if (!nearly_equal(solution[0], r) &&
101 (roots - solution == 1 || !nearly_equal(solution[1], r))) {
102 *roots++ = r;
103 }
104 } else { // we have 1 real root
105 const double sqrtR2MinusQ3 = std::sqrt(R2MinusQ3);
106 A = fabs(R) + sqrtR2MinusQ3;
107 A = std::cbrt(A); // cube root
108 if (R > 0) {
109 A = -A;
110 }
111 if (!sk_double_nearly_zero(A)) {
112 A += Q / A;
113 }
114 r = A - adiv3;
115 *roots++ = r;
118 r = -A / 2 - adiv3;
119 if (!nearly_equal(solution[0], r)) {
120 *roots++ = r;
121 }
122 }
123 }
124 return static_cast<int>(roots - solution);
125}
static constexpr double PI
Definition: SkCubics.cpp:18
static bool close_to_a_quadratic(double A, double B)
Definition: SkCubics.cpp:31
static bool nearly_equal(double x, double y)
Definition: SkCubics.cpp:20
bool sk_double_nearly_zero(double a)
static constexpr double sk_ieee_double_divide(double numer, double denom)
bool sk_doubles_nearly_equal_ulps(double a, double b, uint8_t maxUlpsDiff=16)
static constexpr const T & SkTPin(const T &x, const T &lo, const T &hi)
Definition: SkTPin.h:19
static int RootsReal(double A, double B, double C, double solution[2])
Definition: SkQuads.cpp:135
static bool b
struct MyStruct a[10]
#define R(r)
SIN Vec< N, float > sqrt(const Vec< N, float > &x)
Definition: SkVx.h:706

◆ RootsValidT()

int SkCubics::RootsValidT ( double  A,
double  B,
double  C,
double  D,
double  solution[3] 
)
static

Puts up to 3 real solutions to the equation A*t^3 + B*t^2 + C*t + D = 0 in the provided array, with the constraint that t is in the range [0.0, 1.0], and returns how many roots that was.

Definition at line 127 of file SkCubics.cpp.

128 {
129 double allRoots[3] = {0, 0, 0};
130 int realRoots = SkCubics::RootsReal(A, B, C, D, allRoots);
131 int foundRoots = 0;
132 for (int index = 0; index < realRoots; ++index) {
133 double tValue = allRoots[index];
134 if (tValue >= 1.0 && tValue <= 1.00005) {
135 // Make sure we do not already have 1 (or something very close) in the list of roots.
136 if ((foundRoots < 1 || !sk_doubles_nearly_equal_ulps(solution[0], 1)) &&
137 (foundRoots < 2 || !sk_doubles_nearly_equal_ulps(solution[1], 1))) {
138 solution[foundRoots++] = 1;
139 }
140 } else if (tValue >= -0.00005 && (tValue <= 0.0 || sk_double_nearly_zero(tValue))) {
141 // Make sure we do not already have 0 (or something very close) in the list of roots.
142 if ((foundRoots < 1 || !sk_double_nearly_zero(solution[0])) &&
143 (foundRoots < 2 || !sk_double_nearly_zero(solution[1]))) {
144 solution[foundRoots++] = 0;
145 }
146 } else if (tValue > 0.0 && tValue < 1.0) {
147 solution[foundRoots++] = tValue;
148 }
149 }
150 return foundRoots;
151}
static int RootsReal(double A, double B, double C, double D, double solution[3])
Definition: SkCubics.cpp:38

The documentation for this class was generated from the following files: