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 "SkEdge.h" 12 13 struct SkAnalyticEdge { 14 // Similar to SkEdge, the conic edges will be converted to quadratic edges 15 enum Type { 16 kLine_Type, 17 kQuad_Type, 18 kCubic_Type 19 }; 20 21 SkAnalyticEdge* fNext; 22 SkAnalyticEdge* fPrev; 23 24 // During aaa_walk_edges, if this edge is a left edge, 25 // then fRiteE is its corresponding right edge. Otherwise it's nullptr. 26 SkAnalyticEdge* fRiteE; 27 28 SkFixed fX; 29 SkFixed fDX; 30 SkFixed fUpperX; // The x value when y = fUpperY 31 SkFixed fY; // The current y 32 SkFixed fUpperY; // The upper bound of y (our edge is from y = fUpperY to y = fLowerY) 33 SkFixed fLowerY; // The lower bound of y (our edge is from y = fUpperY to y = fLowerY) 34 SkFixed fDY; // abs(1/fDX); may be SK_MaxS32 when fDX is close to 0. 35 // fDY is only used for blitting trapezoids. 36 37 SkFixed fSavedX; // For deferred blitting 38 SkFixed fSavedY; // For deferred blitting 39 SkFixed fSavedDY; // For deferred blitting 40 41 int8_t fCurveCount; // only used by kQuad(+) and kCubic(-) 42 uint8_t fCurveShift; // appled to all Dx/DDx/DDDx except for fCubicDShift exception 43 uint8_t fCubicDShift; // applied to fCDx and fCDy only in cubic 44 int8_t fWinding; // 1 or -1 45 46 static const int kDefaultAccuracy = 2; // default accuracy for snapping 47 48 static inline SkFixed SnapY(SkFixed y) { 49 const int accuracy = kDefaultAccuracy; 50 // This approach is safer than left shift, round, then right shift 51 return ((unsigned)y + (SK_Fixed1 >> (accuracy + 1))) >> (16 - accuracy) << (16 - accuracy); 52 } 53 54 // Update fX, fY of this edge so fY = y 55 inline void goY(SkFixed y) { 56 if (y == fY + SK_Fixed1) { 57 fX = fX + fDX; 58 fY = y; 59 } else if (y != fY) { 60 // Drop lower digits as our alpha only has 8 bits 61 // (fDX and y - fUpperY may be greater than SK_Fixed1) 62 fX = fUpperX + SkFixedMul(fDX, y - fUpperY); 63 fY = y; 64 } 65 } 66 67 inline void goY(SkFixed y, int yShift) { 68 SkASSERT(yShift >= 0 && yShift <= kDefaultAccuracy); 69 SkASSERT(fDX == 0 || y - fY == SK_Fixed1 >> yShift); 70 fY = y; 71 fX += fDX >> yShift; 72 } 73 74 inline void saveXY(SkFixed x, SkFixed y, SkFixed dY) { 75 fSavedX = x; 76 fSavedY = y; 77 fSavedDY = dY; 78 } 79 80 inline bool setLine(const SkPoint& p0, const SkPoint& p1); 81 inline bool updateLine(SkFixed ax, SkFixed ay, SkFixed bx, SkFixed by, SkFixed slope); 82 83 // return true if we're NOT done with this edge 84 bool update(SkFixed last_y, bool sortY = true); 85 86 #ifdef SK_DEBUG 87 void dump() const { 88 SkDebugf("edge: upperY:%d lowerY:%d y:%g x:%g dx:%g w:%d\n", 89 fUpperY, fLowerY, SkFixedToFloat(fY), SkFixedToFloat(fX), 90 SkFixedToFloat(fDX), fWinding); 91 } 92 93 void validate() const { 94 SkASSERT(fPrev && fNext); 95 SkASSERT(fPrev->fNext == this); 96 SkASSERT(fNext->fPrev == this); 97 98 SkASSERT(fUpperY < fLowerY); 99 SkASSERT(SkAbs32(fWinding) == 1); 100 } 101 #endif 102 }; 103 104 struct SkAnalyticQuadraticEdge : public SkAnalyticEdge { 105 SkQuadraticEdge fQEdge; 106 107 // snap y to integer points in the middle of the curve to accelerate AAA path filling 108 SkFixed fSnappedX, fSnappedY; 109 110 bool setQuadratic(const SkPoint pts[3]); 111 bool updateQuadratic(); 112 inline void keepContinuous() { 113 // We use fX as the starting x to ensure the continuouty. 114 // Without it, we may break the sorted edge list. 115 SkASSERT(SkAbs32(fX - SkFixedMul(fY - fSnappedY, fDX) - fSnappedX) < SK_Fixed1); 116 SkASSERT(SkAbs32(fY - fSnappedY) < SK_Fixed1); // This may differ due to smooth jump 117 fSnappedX = fX; 118 fSnappedY = fY; 119 } 120 }; 121 122 struct SkAnalyticCubicEdge : public SkAnalyticEdge { 123 SkCubicEdge fCEdge; 124 125 SkFixed fSnappedY; // to make sure that y is increasing with smooth jump and snapping 126 127 bool setCubic(const SkPoint pts[4], bool sortY = true); 128 bool updateCubic(bool sortY = true); 129 inline void keepContinuous() { 130 SkASSERT(SkAbs32(fX - SkFixedMul(fDX, fY - SnapY(fCEdge.fCy)) - fCEdge.fCx) < SK_Fixed1); 131 fCEdge.fCx = fX; 132 fSnappedY = fY; 133 } 134 }; 135 136 bool SkAnalyticEdge::setLine(const SkPoint& p0, const SkPoint& p1) { 137 fRiteE = nullptr; 138 139 // We must set X/Y using the same way (e.g., times 4, to FDot6, then to Fixed) as Quads/Cubics. 140 // Otherwise the order of the edge might be wrong due to precision limit. 141 const int accuracy = kDefaultAccuracy; 142 #ifdef SK_RASTERIZE_EVEN_ROUNDING 143 SkFixed x0 = SkFDot6ToFixed(SkScalarRoundToFDot6(p0.fX, accuracy)) >> accuracy; 144 SkFixed y0 = SnapY(SkFDot6ToFixed(SkScalarRoundToFDot6(p0.fY, accuracy)) >> accuracy); 145 SkFixed x1 = SkFDot6ToFixed(SkScalarRoundToFDot6(p1.fX, accuracy)) >> accuracy; 146 SkFixed y1 = SnapY(SkFDot6ToFixed(SkScalarRoundToFDot6(p1.fY, accuracy)) >> accuracy); 147 #else 148 const int multiplier = (1 << kDefaultAccuracy); 149 SkFixed x0 = SkFDot6ToFixed(SkScalarToFDot6(p0.fX * multiplier)) >> accuracy; 150 SkFixed y0 = SnapY(SkFDot6ToFixed(SkScalarToFDot6(p0.fY * multiplier)) >> accuracy); 151 SkFixed x1 = SkFDot6ToFixed(SkScalarToFDot6(p1.fX * multiplier)) >> accuracy; 152 SkFixed y1 = SnapY(SkFDot6ToFixed(SkScalarToFDot6(p1.fY * multiplier)) >> accuracy); 153 #endif 154 155 int winding = 1; 156 157 if (y0 > y1) { 158 SkTSwap(x0, x1); 159 SkTSwap(y0, y1); 160 winding = -1; 161 } 162 163 // are we a zero-height line? 164 SkFDot6 dy = SkFixedToFDot6(y1 - y0); 165 if (dy == 0) { 166 return false; 167 } 168 SkFDot6 dx = SkFixedToFDot6(x1 - x0); 169 SkFixed slope = QuickSkFDot6Div(dx, dy); 170 SkFixed absSlope = SkAbs32(slope); 171 172 fX = x0; 173 fDX = slope; 174 fUpperX = x0; 175 fY = y0; 176 fUpperY = y0; 177 fLowerY = y1; 178 fDY = dx == 0 || slope == 0 ? SK_MaxS32 : absSlope < kInverseTableSize 179 ? QuickFDot6Inverse::Lookup(absSlope) 180 : SkAbs32(QuickSkFDot6Div(dy, dx)); 181 fCurveCount = 0; 182 fWinding = SkToS8(winding); 183 fCurveShift = 0; 184 185 return true; 186 } 187 188 struct SkBezier { 189 int fCount; // 2 line, 3 quad, 4 cubic 190 SkPoint fP0; 191 SkPoint fP1; 192 193 // See if left shift, covert to SkFDot6, and round has the same top and bottom y. 194 // If so, the edge will be empty. 195 static inline bool IsEmpty(SkScalar y0, SkScalar y1, int shift = 2) { 196 #ifdef SK_RASTERIZE_EVEN_ROUNDING 197 return SkScalarRoundToFDot6(y0, shift) == SkScalarRoundToFDot6(y1, shift); 198 #else 199 SkScalar scale = (1 << (shift + 6)); 200 return SkFDot6Round(int(y0 * scale)) == SkFDot6Round(int(y1 * scale)); 201 #endif 202 } 203 }; 204 205 struct SkLine : public SkBezier { 206 bool set(const SkPoint pts[2]){ 207 if (IsEmpty(pts[0].fY, pts[1].fY)) { 208 return false; 209 } 210 fCount = 2; 211 fP0 = pts[0]; 212 fP1 = pts[1]; 213 return true; 214 } 215 }; 216 217 struct SkQuad : public SkBezier { 218 SkPoint fP2; 219 220 bool set(const SkPoint pts[3]){ 221 if (IsEmpty(pts[0].fY, pts[2].fY)) { 222 return false; 223 } 224 fCount = 3; 225 fP0 = pts[0]; 226 fP1 = pts[1]; 227 fP2 = pts[2]; 228 return true; 229 } 230 }; 231 232 struct SkCubic : public SkBezier { 233 SkPoint fP2; 234 SkPoint fP3; 235 236 bool set(const SkPoint pts[4]){ 237 // We do not chop at y extrema for cubics so pts[0], pts[1], pts[2], pts[3] may not be 238 // monotonic. Therefore, we have to check the emptiness for all three pairs, instead of just 239 // checking IsEmpty(pts[0].fY, pts[3].fY). 240 if (IsEmpty(pts[0].fY, pts[1].fY) && IsEmpty(pts[1].fY, pts[2].fY) && 241 IsEmpty(pts[2].fY, pts[3].fY)) { 242 return false; 243 } 244 fCount = 4; 245 fP0 = pts[0]; 246 fP1 = pts[1]; 247 fP2 = pts[2]; 248 fP3 = pts[3]; 249 return true; 250 } 251 }; 252 253 #endif 254
