1 /* 2 * Copyright 2012 Google Inc. 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 8 #ifndef SkPathOpsCubic_DEFINED 9 #define SkPathOpsCubic_DEFINED 10 11 #include "SkPath.h" 12 #include "SkPathOpsPoint.h" 13 14 struct SkDCubicPair; 15 16 struct SkDCubic { 17 static const int kPointCount = 4; 18 static const int kPointLast = kPointCount - 1; 19 static const int kMaxIntersections = 9; 20 21 enum SearchAxis { 22 kXAxis, 23 kYAxis 24 }; 25 26 bool collapsed() const { 27 return fPts[0].approximatelyEqual(fPts[1]) && fPts[0].approximatelyEqual(fPts[2]) 28 && fPts[0].approximatelyEqual(fPts[3]); 29 } 30 31 bool controlsInside() const { 32 SkDVector v01 = fPts[0] - fPts[1]; 33 SkDVector v02 = fPts[0] - fPts[2]; 34 SkDVector v03 = fPts[0] - fPts[3]; 35 SkDVector v13 = fPts[1] - fPts[3]; 36 SkDVector v23 = fPts[2] - fPts[3]; 37 return v03.dot(v01) > 0 && v03.dot(v02) > 0 && v03.dot(v13) > 0 && v03.dot(v23) > 0; 38 } 39 40 static bool IsConic() { return false; } 41 42 const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; } 43 SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; } 44 45 void align(int endIndex, int ctrlIndex, SkDPoint* dstPt) const; 46 double binarySearch(double min, double max, double axisIntercept, SearchAxis xAxis) const; 47 double calcPrecision() const; 48 SkDCubicPair chopAt(double t) const; 49 static void Coefficients(const double* cubic, double* A, double* B, double* C, double* D); 50 static int ComplexBreak(const SkPoint pts[4], SkScalar* t); 51 int convexHull(char order[kPointCount]) const; 52 53 void debugInit() { 54 sk_bzero(fPts, sizeof(fPts)); 55 } 56 57 void debugSet(const SkDPoint* pts); 58 59 void dump() const; // callable from the debugger when the implementation code is linked in 60 void dumpID(int id) const; 61 void dumpInner() const; 62 SkDVector dxdyAtT(double t) const; 63 bool endsAreExtremaInXOrY() const; 64 static int FindExtrema(const double src[], double tValue[2]); 65 int findInflections(double tValues[2]) const; 66 67 static int FindInflections(const SkPoint a[kPointCount], double tValues[2]) { 68 SkDCubic cubic; 69 return cubic.set(a).findInflections(tValues); 70 } 71 72 int findMaxCurvature(double tValues[]) const; 73 74 #ifdef SK_DEBUG 75 SkOpGlobalState* globalState() const { return fDebugGlobalState; } 76 #endif 77 78 bool hullIntersects(const SkDCubic& c2, bool* isLinear) const; 79 bool hullIntersects(const SkDConic& c, bool* isLinear) const; 80 bool hullIntersects(const SkDQuad& c2, bool* isLinear) const; 81 bool hullIntersects(const SkDPoint* pts, int ptCount, bool* isLinear) const; 82 bool isLinear(int startIndex, int endIndex) const; 83 bool monotonicInX() const; 84 bool monotonicInY() const; 85 void otherPts(int index, const SkDPoint* o1Pts[kPointCount - 1]) const; 86 SkDPoint ptAtT(double t) const; 87 static int RootsReal(double A, double B, double C, double D, double t[3]); 88 static int RootsValidT(const double A, const double B, const double C, double D, double s[3]); 89 90 int searchRoots(double extremes[6], int extrema, double axisIntercept, 91 SearchAxis xAxis, double* validRoots) const; 92 93 bool toFloatPoints(SkPoint* ) const; 94 /** 95 * Return the number of valid roots (0 < root < 1) for this cubic intersecting the 96 * specified horizontal line. 97 */ 98 int horizontalIntersect(double yIntercept, double roots[3]) const; 99 /** 100 * Return the number of valid roots (0 < root < 1) for this cubic intersecting the 101 * specified vertical line. 102 */ 103 int verticalIntersect(double xIntercept, double roots[3]) const; 104 105 // add debug only global pointer so asserts can be skipped by fuzzers 106 const SkDCubic& set(const SkPoint pts[kPointCount] 107 SkDEBUGPARAMS(SkOpGlobalState* state = nullptr)) { 108 fPts[0] = pts[0]; 109 fPts[1] = pts[1]; 110 fPts[2] = pts[2]; 111 fPts[3] = pts[3]; 112 SkDEBUGCODE(fDebugGlobalState = state); 113 return *this; 114 } 115 116 SkDCubic subDivide(double t1, double t2) const; 117 118 static SkDCubic SubDivide(const SkPoint a[kPointCount], double t1, double t2) { 119 SkDCubic cubic; 120 return cubic.set(a).subDivide(t1, t2); 121 } 122 123 void subDivide(const SkDPoint& a, const SkDPoint& d, double t1, double t2, SkDPoint p[2]) const; 124 125 static void SubDivide(const SkPoint pts[kPointCount], const SkDPoint& a, const SkDPoint& d, double t1, 126 double t2, SkDPoint p[2]) { 127 SkDCubic cubic; 128 cubic.set(pts).subDivide(a, d, t1, t2, p); 129 } 130 131 double top(const SkDCubic& dCurve, double startT, double endT, SkDPoint*topPt) const; 132 SkDQuad toQuad() const; 133 134 static const int gPrecisionUnit; 135 SkDPoint fPts[kPointCount]; 136 SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState); 137 }; 138 139 /* Given the set [0, 1, 2, 3], and two of the four members, compute an XOR mask 140 that computes the other two. Note that: 141 142 one ^ two == 3 for (0, 3), (1, 2) 143 one ^ two < 3 for (0, 1), (0, 2), (1, 3), (2, 3) 144 3 - (one ^ two) is either 0, 1, or 2 145 1 >> (3 - (one ^ two)) is either 0 or 1 146 thus: 147 returned == 2 for (0, 3), (1, 2) 148 returned == 3 for (0, 1), (0, 2), (1, 3), (2, 3) 149 given that: 150 (0, 3) ^ 2 -> (2, 1) (1, 2) ^ 2 -> (3, 0) 151 (0, 1) ^ 3 -> (3, 2) (0, 2) ^ 3 -> (3, 1) (1, 3) ^ 3 -> (2, 0) (2, 3) ^ 3 -> (1, 0) 152 */ 153 inline int other_two(int one, int two) { 154 return 1 >> (3 - (one ^ two)) ^ 3; 155 } 156 157 struct SkDCubicPair { 158 const SkDCubic first() const { 159 #ifdef SK_DEBUG 160 SkDCubic result; 161 result.debugSet(&pts[0]); 162 return result; 163 #else 164 return (const SkDCubic&) pts[0]; 165 #endif 166 } 167 const SkDCubic second() const { 168 #ifdef SK_DEBUG 169 SkDCubic result; 170 result.debugSet(&pts[3]); 171 return result; 172 #else 173 return (const SkDCubic&) pts[3]; 174 #endif 175 } 176 SkDPoint pts[7]; 177 }; 178 179 #endif 180