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
SnapYSkAnalyticEdge48 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
goYSkAnalyticEdge55 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
goYSkAnalyticEdge67 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
saveXYSkAnalyticEdge74 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
dumpSkAnalyticEdge87 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
validateSkAnalyticEdge93 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();
keepContinuousSkAnalyticQuadraticEdge112 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);
keepContinuousSkAnalyticCubicEdge129 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
setLine(const SkPoint & p0,const SkPoint & p1)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 {
setSkLine206 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
setSkQuad220 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
setSkCubic236 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