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 #ifdef SK_DEBUG 84 void dump() const { 85 SkDebugf("edge: upperY:%d lowerY:%d y:%g x:%g dx:%g w:%d\n", 86 fUpperY, fLowerY, SkFixedToFloat(fY), SkFixedToFloat(fX), 87 SkFixedToFloat(fDX), fWinding); 88 } 89 90 void validate() const { 91 SkASSERT(fPrev && fNext); 92 SkASSERT(fPrev->fNext == this); 93 SkASSERT(fNext->fPrev == this); 94 95 SkASSERT(fUpperY < fLowerY); 96 SkASSERT(SkAbs32(fWinding) == 1); 97 } 98 #endif 99 }; 100 101 struct SkAnalyticQuadraticEdge : public SkAnalyticEdge { 102 SkQuadraticEdge fQEdge; 103 104 // snap y to integer points in the middle of the curve to accelerate AAA path filling 105 SkFixed fSnappedX, fSnappedY; 106 107 bool setQuadratic(const SkPoint pts[3]); 108 bool updateQuadratic(); 109 inline void keepContinuous() { 110 // We use fX as the starting x to ensure the continuouty. 111 // Without it, we may break the sorted edge list. 112 SkASSERT(SkAbs32(fX - SkFixedMul(fY - fSnappedY, fDX) - fSnappedX) < SK_Fixed1); 113 SkASSERT(SkAbs32(fY - fSnappedY) < SK_Fixed1); // This may differ due to smooth jump 114 fSnappedX = fX; 115 fSnappedY = fY; 116 } 117 }; 118 119 struct SkAnalyticCubicEdge : public SkAnalyticEdge { 120 SkCubicEdge fCEdge; 121 122 SkFixed fSnappedY; // to make sure that y is increasing with smooth jump and snapping 123 124 bool setCubic(const SkPoint pts[4]); 125 bool updateCubic(); 126 inline void keepContinuous() { 127 SkASSERT(SkAbs32(fX - SkFixedMul(fDX, fY - SnapY(fCEdge.fCy)) - fCEdge.fCx) < SK_Fixed1); 128 fCEdge.fCx = fX; 129 fSnappedY = fY; 130 } 131 }; 132 133 bool SkAnalyticEdge::setLine(const SkPoint& p0, const SkPoint& p1) { 134 fRiteE = nullptr; 135 136 // We must set X/Y using the same way (e.g., times 4, to FDot6, then to Fixed) as Quads/Cubics. 137 // Otherwise the order of the edge might be wrong due to precision limit. 138 const int accuracy = kDefaultAccuracy; 139 const int multiplier = (1 << kDefaultAccuracy); 140 SkFixed x0 = SkFDot6ToFixed(SkScalarToFDot6(p0.fX * multiplier)) >> accuracy; 141 SkFixed y0 = SnapY(SkFDot6ToFixed(SkScalarToFDot6(p0.fY * multiplier)) >> accuracy); 142 SkFixed x1 = SkFDot6ToFixed(SkScalarToFDot6(p1.fX * multiplier)) >> accuracy; 143 SkFixed y1 = SnapY(SkFDot6ToFixed(SkScalarToFDot6(p1.fY * multiplier)) >> accuracy); 144 145 int winding = 1; 146 147 if (y0 > y1) { 148 SkTSwap(x0, x1); 149 SkTSwap(y0, y1); 150 winding = -1; 151 } 152 153 // are we a zero-height line? 154 SkFDot6 dy = SkFixedToFDot6(y1 - y0); 155 if (dy == 0) { 156 return false; 157 } 158 SkFDot6 dx = SkFixedToFDot6(x1 - x0); 159 SkFixed slope = QuickSkFDot6Div(dx, dy); 160 SkFixed absSlope = SkAbs32(slope); 161 162 fX = x0; 163 fDX = slope; 164 fUpperX = x0; 165 fY = y0; 166 fUpperY = y0; 167 fLowerY = y1; 168 fDY = dx == 0 || slope == 0 ? SK_MaxS32 : absSlope < kInverseTableSize 169 ? QuickFDot6Inverse::Lookup(absSlope) 170 : SkAbs32(QuickSkFDot6Div(dy, dx)); 171 fCurveCount = 0; 172 fWinding = SkToS8(winding); 173 fCurveShift = 0; 174 175 return true; 176 } 177 178 #endif 179
