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