SkPathOpsQuad.h 6.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184
  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 SkPathOpsQuad_DEFINED
  8. #define SkPathOpsQuad_DEFINED
  9. #include "src/core/SkArenaAlloc.h"
  10. #include "src/pathops/SkPathOpsTCurve.h"
  11. struct SkOpCurve;
  12. struct SkDQuadPair {
  13. const SkDQuad& first() const { return (const SkDQuad&) pts[0]; }
  14. const SkDQuad& second() const { return (const SkDQuad&) pts[2]; }
  15. SkDPoint pts[5];
  16. };
  17. struct SkDQuad {
  18. static const int kPointCount = 3;
  19. static const int kPointLast = kPointCount - 1;
  20. static const int kMaxIntersections = 4;
  21. SkDPoint fPts[kPointCount];
  22. bool collapsed() const {
  23. return fPts[0].approximatelyEqual(fPts[1]) && fPts[0].approximatelyEqual(fPts[2]);
  24. }
  25. bool controlsInside() const {
  26. SkDVector v01 = fPts[0] - fPts[1];
  27. SkDVector v02 = fPts[0] - fPts[2];
  28. SkDVector v12 = fPts[1] - fPts[2];
  29. return v02.dot(v01) > 0 && v02.dot(v12) > 0;
  30. }
  31. void debugInit() {
  32. sk_bzero(fPts, sizeof(fPts));
  33. }
  34. void debugSet(const SkDPoint* pts);
  35. SkDQuad flip() const {
  36. SkDQuad result = {{fPts[2], fPts[1], fPts[0]} SkDEBUGPARAMS(fDebugGlobalState) };
  37. return result;
  38. }
  39. static bool IsConic() { return false; }
  40. const SkDQuad& set(const SkPoint pts[kPointCount]
  41. SkDEBUGPARAMS(SkOpGlobalState* state = nullptr)) {
  42. fPts[0] = pts[0];
  43. fPts[1] = pts[1];
  44. fPts[2] = pts[2];
  45. SkDEBUGCODE(fDebugGlobalState = state);
  46. return *this;
  47. }
  48. const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; }
  49. SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; }
  50. static int AddValidTs(double s[], int realRoots, double* t);
  51. void align(int endIndex, SkDPoint* dstPt) const;
  52. SkDQuadPair chopAt(double t) const;
  53. SkDVector dxdyAtT(double t) const;
  54. static int FindExtrema(const double src[], double tValue[1]);
  55. #ifdef SK_DEBUG
  56. SkOpGlobalState* globalState() const { return fDebugGlobalState; }
  57. #endif
  58. /**
  59. * Return the number of valid roots (0 < root < 1) for this cubic intersecting the
  60. * specified horizontal line.
  61. */
  62. int horizontalIntersect(double yIntercept, double roots[2]) const;
  63. bool hullIntersects(const SkDQuad& , bool* isLinear) const;
  64. bool hullIntersects(const SkDConic& , bool* isLinear) const;
  65. bool hullIntersects(const SkDCubic& , 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 oddMan, const SkDPoint* endPt[2]) 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 t[2]);
  75. static int RootsValidT(const double A, const double B, const double C, double s[2]);
  76. static void SetABC(const double* quad, double* a, double* b, double* c);
  77. SkDQuad subDivide(double t1, double t2) const;
  78. void subDivide(double t1, double t2, SkDQuad* quad) const { *quad = this->subDivide(t1, t2); }
  79. static SkDQuad SubDivide(const SkPoint a[kPointCount], double t1, double t2) {
  80. SkDQuad quad;
  81. quad.set(a);
  82. return quad.subDivide(t1, t2);
  83. }
  84. SkDPoint subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2) const;
  85. static SkDPoint SubDivide(const SkPoint pts[kPointCount], const SkDPoint& a, const SkDPoint& c,
  86. double t1, double t2) {
  87. SkDQuad quad;
  88. quad.set(pts);
  89. return quad.subDivide(a, c, t1, t2);
  90. }
  91. /**
  92. * Return the number of valid roots (0 < root < 1) for this cubic intersecting the
  93. * specified vertical line.
  94. */
  95. int verticalIntersect(double xIntercept, double roots[2]) const;
  96. SkDCubic debugToCubic() const;
  97. // utilities callable by the user from the debugger when the implementation code is linked in
  98. void dump() const;
  99. void dumpID(int id) const;
  100. void dumpInner() const;
  101. SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState);
  102. };
  103. class SkTQuad : public SkTCurve {
  104. public:
  105. SkDQuad fQuad;
  106. SkTQuad() {}
  107. SkTQuad(const SkDQuad& q)
  108. : fQuad(q) {
  109. }
  110. ~SkTQuad() override {}
  111. const SkDPoint& operator[](int n) const override { return fQuad[n]; }
  112. SkDPoint& operator[](int n) override { return fQuad[n]; }
  113. bool collapsed() const override { return fQuad.collapsed(); }
  114. bool controlsInside() const override { return fQuad.controlsInside(); }
  115. void debugInit() override { return fQuad.debugInit(); }
  116. #if DEBUG_T_SECT
  117. void dumpID(int id) const override { return fQuad.dumpID(id); }
  118. #endif
  119. SkDVector dxdyAtT(double t) const override { return fQuad.dxdyAtT(t); }
  120. #ifdef SK_DEBUG
  121. SkOpGlobalState* globalState() const override { return fQuad.globalState(); }
  122. #endif
  123. bool hullIntersects(const SkDQuad& quad, bool* isLinear) const override {
  124. return quad.hullIntersects(fQuad, isLinear);
  125. }
  126. bool hullIntersects(const SkDConic& conic, bool* isLinear) const override;
  127. bool hullIntersects(const SkDCubic& cubic, bool* isLinear) const override;
  128. bool hullIntersects(const SkTCurve& curve, bool* isLinear) const override {
  129. return curve.hullIntersects(fQuad, isLinear);
  130. }
  131. int intersectRay(SkIntersections* i, const SkDLine& line) const override;
  132. bool IsConic() const override { return false; }
  133. SkTCurve* make(SkArenaAlloc& heap) const override { return heap.make<SkTQuad>(); }
  134. int maxIntersections() const override { return SkDQuad::kMaxIntersections; }
  135. void otherPts(int oddMan, const SkDPoint* endPt[2]) const override {
  136. fQuad.otherPts(oddMan, endPt);
  137. }
  138. int pointCount() const override { return SkDQuad::kPointCount; }
  139. int pointLast() const override { return SkDQuad::kPointLast; }
  140. SkDPoint ptAtT(double t) const override { return fQuad.ptAtT(t); }
  141. void setBounds(SkDRect* ) const override;
  142. void subDivide(double t1, double t2, SkTCurve* curve) const override {
  143. ((SkTQuad*) curve)->fQuad = fQuad.subDivide(t1, t2);
  144. }
  145. };
  146. #endif