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 SkPathOpsQuad_DEFINED 9 #define SkPathOpsQuad_DEFINED 10 11 #include "include/core/SkPoint.h" 12 #include "include/core/SkTypes.h" 13 #include "include/private/base/SkDebug.h" 14 #include "include/private/base/SkMalloc.h" 15 #include "src/base/SkArenaAlloc.h" 16 #include "src/pathops/SkPathOpsCubic.h" 17 #include "src/pathops/SkPathOpsDebug.h" 18 #include "src/pathops/SkPathOpsPoint.h" 19 #include "src/pathops/SkPathOpsTCurve.h" 20 21 class SkIntersections; 22 class SkOpGlobalState; 23 struct SkDConic; 24 struct SkDLine; 25 struct SkDQuad; 26 struct SkDRect; 27 28 struct SkDQuadPair { firstSkDQuadPair29 const SkDQuad& first() const { return (const SkDQuad&) pts[0]; } secondSkDQuadPair30 const SkDQuad& second() const { return (const SkDQuad&) pts[2]; } 31 SkDPoint pts[5]; 32 }; 33 34 struct SkDQuad { 35 static const int kPointCount = 3; 36 static const int kPointLast = kPointCount - 1; 37 static const int kMaxIntersections = 4; 38 39 SkDPoint fPts[kPointCount]; 40 collapsedSkDQuad41 bool collapsed() const { 42 return fPts[0].approximatelyEqual(fPts[1]) && fPts[0].approximatelyEqual(fPts[2]); 43 } 44 controlsInsideSkDQuad45 bool controlsInside() const { 46 SkDVector v01 = fPts[0] - fPts[1]; 47 SkDVector v02 = fPts[0] - fPts[2]; 48 SkDVector v12 = fPts[1] - fPts[2]; 49 return v02.dot(v01) > 0 && v02.dot(v12) > 0; 50 } 51 debugInitSkDQuad52 void debugInit() { 53 sk_bzero(fPts, sizeof(fPts)); 54 } 55 56 void debugSet(const SkDPoint* pts); 57 flipSkDQuad58 SkDQuad flip() const { 59 SkDQuad result = {{fPts[2], fPts[1], fPts[0]} SkDEBUGPARAMS(fDebugGlobalState) }; 60 return result; 61 } 62 IsConicSkDQuad63 static bool IsConic() { return false; } 64 setSkDQuad65 const SkDQuad& set(const SkPoint pts[kPointCount] 66 SkDEBUGPARAMS(SkOpGlobalState* state = nullptr)) { 67 fPts[0] = pts[0]; 68 fPts[1] = pts[1]; 69 fPts[2] = pts[2]; 70 SkDEBUGCODE(fDebugGlobalState = state); 71 return *this; 72 } 73 74 const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; } 75 SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; } 76 77 static int AddValidTs(double s[], int realRoots, double* t); 78 void align(int endIndex, SkDPoint* dstPt) const; 79 SkDQuadPair chopAt(double t) const; 80 SkDVector dxdyAtT(double t) const; 81 static int FindExtrema(const double src[], double tValue[1]); 82 83 #ifdef SK_DEBUG globalStateSkDQuad84 SkOpGlobalState* globalState() const { return fDebugGlobalState; } 85 #endif 86 87 /** 88 * Return the number of valid roots (0 < root < 1) for this cubic intersecting the 89 * specified horizontal line. 90 */ 91 int horizontalIntersect(double yIntercept, double roots[2]) const; 92 93 bool hullIntersects(const SkDQuad& , bool* isLinear) const; 94 bool hullIntersects(const SkDConic& , bool* isLinear) const; 95 bool hullIntersects(const SkDCubic& , bool* isLinear) const; 96 bool isLinear(int startIndex, int endIndex) const; maxIntersectionsSkDQuad97 static int maxIntersections() { return kMaxIntersections; } 98 bool monotonicInX() const; 99 bool monotonicInY() const; 100 void otherPts(int oddMan, const SkDPoint* endPt[2]) const; pointCountSkDQuad101 static int pointCount() { return kPointCount; } pointLastSkDQuad102 static int pointLast() { return kPointLast; } 103 SkDPoint ptAtT(double t) const; 104 static int RootsReal(double A, double B, double C, double t[2]); 105 static int RootsValidT(const double A, const double B, const double C, double s[2]); 106 static void SetABC(const double* quad, double* a, double* b, double* c); 107 SkDQuad subDivide(double t1, double t2) const; subDivideSkDQuad108 void subDivide(double t1, double t2, SkDQuad* quad) const { *quad = this->subDivide(t1, t2); } 109 SubDivideSkDQuad110 static SkDQuad SubDivide(const SkPoint a[kPointCount], double t1, double t2) { 111 SkDQuad quad; 112 quad.set(a); 113 return quad.subDivide(t1, t2); 114 } 115 SkDPoint subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2) const; SubDivideSkDQuad116 static SkDPoint SubDivide(const SkPoint pts[kPointCount], const SkDPoint& a, const SkDPoint& c, 117 double t1, double t2) { 118 SkDQuad quad; 119 quad.set(pts); 120 return quad.subDivide(a, c, t1, t2); 121 } 122 123 /** 124 * Return the number of valid roots (0 < root < 1) for this cubic intersecting the 125 * specified vertical line. 126 */ 127 int verticalIntersect(double xIntercept, double roots[2]) const; 128 129 SkDCubic debugToCubic() const; 130 // utilities callable by the user from the debugger when the implementation code is linked in 131 void dump() const; 132 void dumpID(int id) const; 133 void dumpInner() const; 134 135 SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState;) 136 }; 137 138 139 class SkTQuad : public SkTCurve { 140 public: 141 SkDQuad fQuad; 142 SkTQuad()143 SkTQuad() {} 144 SkTQuad(const SkDQuad & q)145 SkTQuad(const SkDQuad& q) 146 : fQuad(q) { 147 } 148 ~SkTQuad()149 ~SkTQuad() override {} 150 151 const SkDPoint& operator[](int n) const override { return fQuad[n]; } 152 SkDPoint& operator[](int n) override { return fQuad[n]; } 153 collapsed()154 bool collapsed() const override { return fQuad.collapsed(); } controlsInside()155 bool controlsInside() const override { return fQuad.controlsInside(); } debugInit()156 void debugInit() override { return fQuad.debugInit(); } 157 #if DEBUG_T_SECT dumpID(int id)158 void dumpID(int id) const override { return fQuad.dumpID(id); } 159 #endif dxdyAtT(double t)160 SkDVector dxdyAtT(double t) const override { return fQuad.dxdyAtT(t); } 161 #ifdef SK_DEBUG globalState()162 SkOpGlobalState* globalState() const override { return fQuad.globalState(); } 163 #endif 164 hullIntersects(const SkDQuad & quad,bool * isLinear)165 bool hullIntersects(const SkDQuad& quad, bool* isLinear) const override { 166 return quad.hullIntersects(fQuad, isLinear); 167 } 168 169 bool hullIntersects(const SkDConic& conic, bool* isLinear) const override; 170 bool hullIntersects(const SkDCubic& cubic, bool* isLinear) const override; 171 hullIntersects(const SkTCurve & curve,bool * isLinear)172 bool hullIntersects(const SkTCurve& curve, bool* isLinear) const override { 173 return curve.hullIntersects(fQuad, isLinear); 174 } 175 176 int intersectRay(SkIntersections* i, const SkDLine& line) const override; IsConic()177 bool IsConic() const override { return false; } make(SkArenaAlloc & heap)178 SkTCurve* make(SkArenaAlloc& heap) const override { return heap.make<SkTQuad>(); } 179 maxIntersections()180 int maxIntersections() const override { return SkDQuad::kMaxIntersections; } 181 otherPts(int oddMan,const SkDPoint * endPt[2])182 void otherPts(int oddMan, const SkDPoint* endPt[2]) const override { 183 fQuad.otherPts(oddMan, endPt); 184 } 185 pointCount()186 int pointCount() const override { return SkDQuad::kPointCount; } pointLast()187 int pointLast() const override { return SkDQuad::kPointLast; } ptAtT(double t)188 SkDPoint ptAtT(double t) const override { return fQuad.ptAtT(t); } 189 void setBounds(SkDRect* ) const override; 190 subDivide(double t1,double t2,SkTCurve * curve)191 void subDivide(double t1, double t2, SkTCurve* curve) const override { 192 ((SkTQuad*) curve)->fQuad = fQuad.subDivide(t1, t2); 193 } 194 }; 195 196 #endif 197