SkPathOpsCubic.h 8.2 KB

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