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 "SkArenaAlloc.h" 12 #include "SkPath.h" 13 #include "SkPathOpsTCurve.h" 14 15 struct SkDCubicPair; 16 17 struct SkDCubic { 18 static const int kPointCount = 4; 19 static const int kPointLast = kPointCount - 1; 20 static const int kMaxIntersections = 9; 21 22 enum SearchAxis { 23 kXAxis, 24 kYAxis 25 }; 26 27 bool collapsed() const { 28 return fPts[0].approximatelyEqual(fPts[1]) && fPts[0].approximatelyEqual(fPts[2]) 29 && fPts[0].approximatelyEqual(fPts[3]); 30 } 31 32 bool controlsInside() const { 33 SkDVector v01 = fPts[0] - fPts[1]; 34 SkDVector v02 = fPts[0] - fPts[2]; 35 SkDVector v03 = fPts[0] - fPts[3]; 36 SkDVector v13 = fPts[1] - fPts[3]; 37 SkDVector v23 = fPts[2] - fPts[3]; 38 return v03.dot(v01) > 0 && v03.dot(v02) > 0 && v03.dot(v13) > 0 && v03.dot(v23) > 0; 39 } 40 41 static bool IsConic() { return false; } 42 43 const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; } 44 SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; } 45 46 void align(int endIndex, int ctrlIndex, SkDPoint* dstPt) const; 47 double binarySearch(double min, double max, double axisIntercept, SearchAxis xAxis) const; 48 double calcPrecision() const; 49 SkDCubicPair chopAt(double t) const; 50 static void Coefficients(const double* cubic, double* A, double* B, double* C, double* D); 51 static int ComplexBreak(const SkPoint pts[4], SkScalar* t); 52 int convexHull(char order[kPointCount]) const; 53 54 void debugInit() { 55 sk_bzero(fPts, sizeof(fPts)); 56 } 57 58 void debugSet(const SkDPoint* pts); 59 60 void dump() const; // callable from the debugger when the implementation code is linked in 61 void dumpID(int id) const; 62 void dumpInner() const; 63 SkDVector dxdyAtT(double t) const; 64 bool endsAreExtremaInXOrY() const; 65 static int FindExtrema(const double src[], double tValue[2]); 66 int findInflections(double tValues[2]) const; 67 68 static int FindInflections(const SkPoint a[kPointCount], double tValues[2]) { 69 SkDCubic cubic; 70 return cubic.set(a).findInflections(tValues); 71 } 72 73 int findMaxCurvature(double tValues[]) const; 74 75 #ifdef SK_DEBUG 76 SkOpGlobalState* globalState() const { return fDebugGlobalState; } 77 #endif 78 79 bool hullIntersects(const SkDCubic& c2, bool* isLinear) const; 80 bool hullIntersects(const SkDConic& c, bool* isLinear) const; 81 bool hullIntersects(const SkDQuad& c2, bool* isLinear) const; 82 bool hullIntersects(const SkDPoint* pts, int ptCount, bool* isLinear) const; 83 bool isLinear(int startIndex, int endIndex) const; 84 static int maxIntersections() { return kMaxIntersections; } 85 bool monotonicInX() const; 86 bool monotonicInY() const; 87 void otherPts(int index, const SkDPoint* o1Pts[kPointCount - 1]) const; 88 static int pointCount() { return kPointCount; } 89 static int pointLast() { return kPointLast; } 90 SkDPoint ptAtT(double t) const; 91 static int RootsReal(double A, double B, double C, double D, double t[3]); 92 static int RootsValidT(const double A, const double B, const double C, double D, double s[3]); 93 94 int searchRoots(double extremes[6], int extrema, double axisIntercept, 95 SearchAxis xAxis, double* validRoots) const; 96 97 bool toFloatPoints(SkPoint* ) const; 98 /** 99 * Return the number of valid roots (0 < root < 1) for this cubic intersecting the 100 * specified horizontal line. 101 */ 102 int horizontalIntersect(double yIntercept, double roots[3]) const; 103 /** 104 * Return the number of valid roots (0 < root < 1) for this cubic intersecting the 105 * specified vertical line. 106 */ 107 int verticalIntersect(double xIntercept, double roots[3]) const; 108 109 // add debug only global pointer so asserts can be skipped by fuzzers 110 const SkDCubic& set(const SkPoint pts[kPointCount] 111 SkDEBUGPARAMS(SkOpGlobalState* state = nullptr)) { 112 fPts[0] = pts[0]; 113 fPts[1] = pts[1]; 114 fPts[2] = pts[2]; 115 fPts[3] = pts[3]; 116 SkDEBUGCODE(fDebugGlobalState = state); 117 return *this; 118 } 119 120 SkDCubic subDivide(double t1, double t2) const; 121 void subDivide(double t1, double t2, SkDCubic* c) const { *c = this->subDivide(t1, t2); } 122 123 static SkDCubic SubDivide(const SkPoint a[kPointCount], double t1, double t2) { 124 SkDCubic cubic; 125 return cubic.set(a).subDivide(t1, t2); 126 } 127 128 void subDivide(const SkDPoint& a, const SkDPoint& d, double t1, double t2, SkDPoint p[2]) const; 129 130 static void SubDivide(const SkPoint pts[kPointCount], const SkDPoint& a, const SkDPoint& d, double t1, 131 double t2, SkDPoint p[2]) { 132 SkDCubic cubic; 133 cubic.set(pts).subDivide(a, d, t1, t2, p); 134 } 135 136 double top(const SkDCubic& dCurve, double startT, double endT, SkDPoint*topPt) const; 137 SkDQuad toQuad() const; 138 139 static const int gPrecisionUnit; 140 SkDPoint fPts[kPointCount]; 141 SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState); 142 }; 143 144 /* Given the set [0, 1, 2, 3], and two of the four members, compute an XOR mask 145 that computes the other two. Note that: 146 147 one ^ two == 3 for (0, 3), (1, 2) 148 one ^ two < 3 for (0, 1), (0, 2), (1, 3), (2, 3) 149 3 - (one ^ two) is either 0, 1, or 2 150 1 >> (3 - (one ^ two)) is either 0 or 1 151 thus: 152 returned == 2 for (0, 3), (1, 2) 153 returned == 3 for (0, 1), (0, 2), (1, 3), (2, 3) 154 given that: 155 (0, 3) ^ 2 -> (2, 1) (1, 2) ^ 2 -> (3, 0) 156 (0, 1) ^ 3 -> (3, 2) (0, 2) ^ 3 -> (3, 1) (1, 3) ^ 3 -> (2, 0) (2, 3) ^ 3 -> (1, 0) 157 */ 158 inline int other_two(int one, int two) { 159 return 1 >> (3 - (one ^ two)) ^ 3; 160 } 161 162 struct SkDCubicPair { 163 const SkDCubic first() const { 164 #ifdef SK_DEBUG 165 SkDCubic result; 166 result.debugSet(&pts[0]); 167 return result; 168 #else 169 return (const SkDCubic&) pts[0]; 170 #endif 171 } 172 const SkDCubic second() const { 173 #ifdef SK_DEBUG 174 SkDCubic result; 175 result.debugSet(&pts[3]); 176 return result; 177 #else 178 return (const SkDCubic&) pts[3]; 179 #endif 180 } 181 SkDPoint pts[7]; 182 }; 183 184 class SkTCubic : public SkTCurve { 185 public: 186 SkDCubic fCubic; 187 188 SkTCubic() {} 189 190 SkTCubic(const SkDCubic& c) 191 : fCubic(c) { 192 } 193 194 ~SkTCubic() override {} 195 196 const SkDPoint& operator[](int n) const override { return fCubic[n]; } 197 SkDPoint& operator[](int n) override { return fCubic[n]; } 198 199 bool collapsed() const override { return fCubic.collapsed(); } 200 bool controlsInside() const override { return fCubic.controlsInside(); } 201 void debugInit() override { return fCubic.debugInit(); } 202 #if DEBUG_T_SECT 203 void dumpID(int id) const override { return fCubic.dumpID(id); } 204 #endif 205 SkDVector dxdyAtT(double t) const override { return fCubic.dxdyAtT(t); } 206 #ifdef SK_DEBUG 207 SkOpGlobalState* globalState() const override { return fCubic.globalState(); } 208 #endif 209 bool hullIntersects(const SkDQuad& quad, bool* isLinear) const override; 210 bool hullIntersects(const SkDConic& conic, bool* isLinear) const override; 211 212 bool hullIntersects(const SkDCubic& cubic, bool* isLinear) const override { 213 return cubic.hullIntersects(fCubic, isLinear); 214 } 215 216 bool hullIntersects(const SkTCurve& curve, bool* isLinear) const override { 217 return curve.hullIntersects(fCubic, isLinear); 218 } 219 220 int intersectRay(SkIntersections* i, const SkDLine& line) const override; 221 bool IsConic() const override { return false; } 222 SkTCurve* make(SkArenaAlloc& heap) const override { return heap.make<SkTCubic>(); } 223 224 int maxIntersections() const override { return SkDCubic::kMaxIntersections; } 225 226 void otherPts(int oddMan, const SkDPoint* endPt[2]) const override { 227 fCubic.otherPts(oddMan, endPt); 228 } 229 230 int pointCount() const override { return SkDCubic::kPointCount; } 231 int pointLast() const override { return SkDCubic::kPointLast; } 232 SkDPoint ptAtT(double t) const override { return fCubic.ptAtT(t); } 233 void setBounds(SkDRect* ) const override; 234 235 void subDivide(double t1, double t2, SkTCurve* curve) const override { 236 ((SkTCubic*) curve)->fCubic = fCubic.subDivide(t1, t2); 237 } 238 }; 239 240 #endif 241
