SkAnalyticEdge.h 6.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204
  1. /*
  2. * Copyright 2006 The Android Open Source Project
  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 SkAnalyticEdge_DEFINED
  8. #define SkAnalyticEdge_DEFINED
  9. #include "include/private/SkTo.h"
  10. #include "src/core/SkEdge.h"
  11. #include <utility>
  12. struct SkAnalyticEdge {
  13. // Similar to SkEdge, the conic edges will be converted to quadratic edges
  14. enum Type {
  15. kLine_Type,
  16. kQuad_Type,
  17. kCubic_Type
  18. };
  19. SkAnalyticEdge* fNext;
  20. SkAnalyticEdge* fPrev;
  21. // During aaa_walk_edges, if this edge is a left edge,
  22. // then fRiteE is its corresponding right edge. Otherwise it's nullptr.
  23. SkAnalyticEdge* fRiteE;
  24. SkFixed fX;
  25. SkFixed fDX;
  26. SkFixed fUpperX; // The x value when y = fUpperY
  27. SkFixed fY; // The current y
  28. SkFixed fUpperY; // The upper bound of y (our edge is from y = fUpperY to y = fLowerY)
  29. SkFixed fLowerY; // The lower bound of y (our edge is from y = fUpperY to y = fLowerY)
  30. SkFixed fDY; // abs(1/fDX); may be SK_MaxS32 when fDX is close to 0.
  31. // fDY is only used for blitting trapezoids.
  32. SkFixed fSavedX; // For deferred blitting
  33. SkFixed fSavedY; // For deferred blitting
  34. SkFixed fSavedDY; // For deferred blitting
  35. int8_t fCurveCount; // only used by kQuad(+) and kCubic(-)
  36. uint8_t fCurveShift; // appled to all Dx/DDx/DDDx except for fCubicDShift exception
  37. uint8_t fCubicDShift; // applied to fCDx and fCDy only in cubic
  38. int8_t fWinding; // 1 or -1
  39. static const int kDefaultAccuracy = 2; // default accuracy for snapping
  40. static inline SkFixed SnapY(SkFixed y) {
  41. const int accuracy = kDefaultAccuracy;
  42. // This approach is safer than left shift, round, then right shift
  43. return ((unsigned)y + (SK_Fixed1 >> (accuracy + 1))) >> (16 - accuracy) << (16 - accuracy);
  44. }
  45. // Update fX, fY of this edge so fY = y
  46. inline void goY(SkFixed y) {
  47. if (y == fY + SK_Fixed1) {
  48. fX = fX + fDX;
  49. fY = y;
  50. } else if (y != fY) {
  51. // Drop lower digits as our alpha only has 8 bits
  52. // (fDX and y - fUpperY may be greater than SK_Fixed1)
  53. fX = fUpperX + SkFixedMul(fDX, y - fUpperY);
  54. fY = y;
  55. }
  56. }
  57. inline void goY(SkFixed y, int yShift) {
  58. SkASSERT(yShift >= 0 && yShift <= kDefaultAccuracy);
  59. SkASSERT(fDX == 0 || y - fY == SK_Fixed1 >> yShift);
  60. fY = y;
  61. fX += fDX >> yShift;
  62. }
  63. inline void saveXY(SkFixed x, SkFixed y, SkFixed dY) {
  64. fSavedX = x;
  65. fSavedY = y;
  66. fSavedDY = dY;
  67. }
  68. bool setLine(const SkPoint& p0, const SkPoint& p1);
  69. bool updateLine(SkFixed ax, SkFixed ay, SkFixed bx, SkFixed by, SkFixed slope);
  70. // return true if we're NOT done with this edge
  71. bool update(SkFixed last_y, bool sortY = true);
  72. #ifdef SK_DEBUG
  73. void dump() const {
  74. SkDebugf("edge: upperY:%d lowerY:%d y:%g x:%g dx:%g w:%d\n",
  75. fUpperY, fLowerY, SkFixedToFloat(fY), SkFixedToFloat(fX),
  76. SkFixedToFloat(fDX), fWinding);
  77. }
  78. void validate() const {
  79. SkASSERT(fPrev && fNext);
  80. SkASSERT(fPrev->fNext == this);
  81. SkASSERT(fNext->fPrev == this);
  82. SkASSERT(fUpperY < fLowerY);
  83. SkASSERT(SkAbs32(fWinding) == 1);
  84. }
  85. #endif
  86. };
  87. struct SkAnalyticQuadraticEdge : public SkAnalyticEdge {
  88. SkQuadraticEdge fQEdge;
  89. // snap y to integer points in the middle of the curve to accelerate AAA path filling
  90. SkFixed fSnappedX, fSnappedY;
  91. bool setQuadratic(const SkPoint pts[3]);
  92. bool updateQuadratic();
  93. inline void keepContinuous() {
  94. // We use fX as the starting x to ensure the continuouty.
  95. // Without it, we may break the sorted edge list.
  96. SkASSERT(SkAbs32(fX - SkFixedMul(fY - fSnappedY, fDX) - fSnappedX) < SK_Fixed1);
  97. SkASSERT(SkAbs32(fY - fSnappedY) < SK_Fixed1); // This may differ due to smooth jump
  98. fSnappedX = fX;
  99. fSnappedY = fY;
  100. }
  101. };
  102. struct SkAnalyticCubicEdge : public SkAnalyticEdge {
  103. SkCubicEdge fCEdge;
  104. SkFixed fSnappedY; // to make sure that y is increasing with smooth jump and snapping
  105. bool setCubic(const SkPoint pts[4], bool sortY = true);
  106. bool updateCubic(bool sortY = true);
  107. inline void keepContinuous() {
  108. SkASSERT(SkAbs32(fX - SkFixedMul(fDX, fY - SnapY(fCEdge.fCy)) - fCEdge.fCx) < SK_Fixed1);
  109. fCEdge.fCx = fX;
  110. fSnappedY = fY;
  111. }
  112. };
  113. struct SkBezier {
  114. int fCount; // 2 line, 3 quad, 4 cubic
  115. SkPoint fP0;
  116. SkPoint fP1;
  117. // See if left shift, covert to SkFDot6, and round has the same top and bottom y.
  118. // If so, the edge will be empty.
  119. static inline bool IsEmpty(SkScalar y0, SkScalar y1, int shift = 2) {
  120. #ifdef SK_RASTERIZE_EVEN_ROUNDING
  121. return SkScalarRoundToFDot6(y0, shift) == SkScalarRoundToFDot6(y1, shift);
  122. #else
  123. SkScalar scale = (1 << (shift + 6));
  124. return SkFDot6Round(int(y0 * scale)) == SkFDot6Round(int(y1 * scale));
  125. #endif
  126. }
  127. };
  128. struct SkLine : public SkBezier {
  129. bool set(const SkPoint pts[2]){
  130. if (IsEmpty(pts[0].fY, pts[1].fY)) {
  131. return false;
  132. }
  133. fCount = 2;
  134. fP0 = pts[0];
  135. fP1 = pts[1];
  136. return true;
  137. }
  138. };
  139. struct SkQuad : public SkBezier {
  140. SkPoint fP2;
  141. bool set(const SkPoint pts[3]){
  142. if (IsEmpty(pts[0].fY, pts[2].fY)) {
  143. return false;
  144. }
  145. fCount = 3;
  146. fP0 = pts[0];
  147. fP1 = pts[1];
  148. fP2 = pts[2];
  149. return true;
  150. }
  151. };
  152. struct SkCubic : public SkBezier {
  153. SkPoint fP2;
  154. SkPoint fP3;
  155. bool set(const SkPoint pts[4]){
  156. // We do not chop at y extrema for cubics so pts[0], pts[1], pts[2], pts[3] may not be
  157. // monotonic. Therefore, we have to check the emptiness for all three pairs, instead of just
  158. // checking IsEmpty(pts[0].fY, pts[3].fY).
  159. if (IsEmpty(pts[0].fY, pts[1].fY) && IsEmpty(pts[1].fY, pts[2].fY) &&
  160. IsEmpty(pts[2].fY, pts[3].fY)) {
  161. return false;
  162. }
  163. fCount = 4;
  164. fP0 = pts[0];
  165. fP1 = pts[1];
  166. fP2 = pts[2];
  167. fP3 = pts[3];
  168. return true;
  169. }
  170. };
  171. #endif