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 #ifdef SK_DEBUG
dumpSkAnalyticEdge84 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
validateSkAnalyticEdge90 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();
keepContinuousSkAnalyticQuadraticEdge109 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();
keepContinuousSkAnalyticCubicEdge126 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
setLine(const SkPoint & p0,const SkPoint & p1)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