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
9 #include "SkAnalyticEdge.h"
10 #include "SkFDot6.h"
11 #include "SkMathPriv.h"
12
13 // This will become a bottleneck for small ovals rendering if we call SkFixedDiv twice here.
14 // Therefore, we'll let the outter function compute the slope once and send in the value.
15 // Moreover, we'll compute fDY by quickly lookup the inverse table (if possible).
updateLine(SkFixed x0,SkFixed y0,SkFixed x1,SkFixed y1,SkFixed slope)16 bool SkAnalyticEdge::updateLine(SkFixed x0, SkFixed y0, SkFixed x1, SkFixed y1, SkFixed slope) {
17 // Since we send in the slope, we can no longer snap y inside this function.
18 // If we don't send in the slope, or we do some more sophisticated snapping, this function
19 // could be a performance bottleneck.
20 SkASSERT(fWinding == 1 || fWinding == -1);
21 SkASSERT(fCurveCount != 0);
22
23 SkASSERT(y0 <= y1);
24
25 SkFDot6 dx = SkFixedToFDot6(x1 - x0);
26 SkFDot6 dy = SkFixedToFDot6(y1 - y0);
27
28 // are we a zero-height line?
29 if (dy == 0) {
30 return false;
31 }
32
33 SkASSERT(slope < SK_MaxS32);
34
35 SkFDot6 absSlope = SkAbs32(SkFixedToFDot6(slope));
36 fX = x0;
37 fDX = slope;
38 fUpperX = x0;
39 fY = y0;
40 fUpperY = y0;
41 fLowerY = y1;
42 fDY = (dx == 0 || slope == 0)
43 ? SK_MaxS32
44 : absSlope < kInverseTableSize
45 ? QuickFDot6Inverse::Lookup(absSlope)
46 : SkAbs32(QuickSkFDot6Div(dy, dx));
47
48 return true;
49 }
50
setQuadratic(const SkPoint pts[3])51 bool SkAnalyticQuadraticEdge::setQuadratic(const SkPoint pts[3]) {
52 fRiteE = nullptr;
53
54 if (!fQEdge.setQuadraticWithoutUpdate(pts, kDefaultAccuracy)) {
55 return false;
56 }
57 fQEdge.fQx >>= kDefaultAccuracy;
58 fQEdge.fQy >>= kDefaultAccuracy;
59 fQEdge.fQDx >>= kDefaultAccuracy;
60 fQEdge.fQDy >>= kDefaultAccuracy;
61 fQEdge.fQDDx >>= kDefaultAccuracy;
62 fQEdge.fQDDy >>= kDefaultAccuracy;
63 fQEdge.fQLastX >>= kDefaultAccuracy;
64 fQEdge.fQLastY >>= kDefaultAccuracy;
65 fQEdge.fQy = SnapY(fQEdge.fQy);
66 fQEdge.fQLastY = SnapY(fQEdge.fQLastY);
67
68 fWinding = fQEdge.fWinding;
69 fCurveCount = fQEdge.fCurveCount;
70 fCurveShift = fQEdge.fCurveShift;
71
72 fSnappedX = fQEdge.fQx;
73 fSnappedY = fQEdge.fQy;
74
75 return this->updateQuadratic();
76 }
77
updateQuadratic()78 bool SkAnalyticQuadraticEdge::updateQuadratic() {
79 int success = 0; // initialize to fail!
80 int count = fCurveCount;
81 SkFixed oldx = fQEdge.fQx;
82 SkFixed oldy = fQEdge.fQy;
83 SkFixed dx = fQEdge.fQDx;
84 SkFixed dy = fQEdge.fQDy;
85 SkFixed newx, newy, newSnappedX, newSnappedY;
86 int shift = fCurveShift;
87
88 SkASSERT(count > 0);
89
90 do {
91 SkFixed slope;
92 if (--count > 0)
93 {
94 newx = oldx + (dx >> shift);
95 newy = oldy + (dy >> shift);
96 if (SkAbs32(dy >> shift) >= SK_Fixed1 * 2) { // only snap when dy is large enough
97 SkFDot6 diffY = SkFixedToFDot6(newy - fSnappedY);
98 slope = diffY ? QuickSkFDot6Div(SkFixedToFDot6(newx - fSnappedX), diffY)
99 : SK_MaxS32;
100 newSnappedY = SkTMin<SkFixed>(fQEdge.fQLastY, SkFixedRoundToFixed(newy));
101 newSnappedX = newx - SkFixedMul(slope, newy - newSnappedY);
102 } else {
103 newSnappedY = SkTMin(fQEdge.fQLastY, SnapY(newy));
104 newSnappedX = newx;
105 SkFDot6 diffY = SkFixedToFDot6(newSnappedY - fSnappedY);
106 slope = diffY ? QuickSkFDot6Div(SkFixedToFDot6(newx - fSnappedX), diffY)
107 : SK_MaxS32;
108 }
109 dx += fQEdge.fQDDx;
110 dy += fQEdge.fQDDy;
111 }
112 else // last segment
113 {
114 newx = fQEdge.fQLastX;
115 newy = fQEdge.fQLastY;
116 newSnappedY = newy;
117 newSnappedX = newx;
118 SkFDot6 diffY = (newy - fSnappedY) >> 10;
119 slope = diffY ? QuickSkFDot6Div((newx - fSnappedX) >> 10, diffY) : SK_MaxS32;
120 }
121 if (slope < SK_MaxS32) {
122 success = this->updateLine(fSnappedX, fSnappedY, newSnappedX, newSnappedY, slope);
123 }
124 oldx = newx;
125 oldy = newy;
126 } while (count > 0 && !success);
127
128 SkASSERT(newSnappedY <= fQEdge.fQLastY);
129
130 fQEdge.fQx = newx;
131 fQEdge.fQy = newy;
132 fQEdge.fQDx = dx;
133 fQEdge.fQDy = dy;
134 fSnappedX = newSnappedX;
135 fSnappedY = newSnappedY;
136 fCurveCount = SkToS8(count);
137 return success;
138 }
139
setCubic(const SkPoint pts[4])140 bool SkAnalyticCubicEdge::setCubic(const SkPoint pts[4]) {
141 fRiteE = nullptr;
142
143 if (!fCEdge.setCubicWithoutUpdate(pts, kDefaultAccuracy)) {
144 return false;
145 }
146
147 fCEdge.fCx >>= kDefaultAccuracy;
148 fCEdge.fCy >>= kDefaultAccuracy;
149 fCEdge.fCDx >>= kDefaultAccuracy;
150 fCEdge.fCDy >>= kDefaultAccuracy;
151 fCEdge.fCDDx >>= kDefaultAccuracy;
152 fCEdge.fCDDy >>= kDefaultAccuracy;
153 fCEdge.fCDDDx >>= kDefaultAccuracy;
154 fCEdge.fCDDDy >>= kDefaultAccuracy;
155 fCEdge.fCLastX >>= kDefaultAccuracy;
156 fCEdge.fCLastY >>= kDefaultAccuracy;
157 fCEdge.fCy = SnapY(fCEdge.fCy);
158 fCEdge.fCLastY = SnapY(fCEdge.fCLastY);
159
160 fWinding = fCEdge.fWinding;
161 fCurveCount = fCEdge.fCurveCount;
162 fCurveShift = fCEdge.fCurveShift;
163 fCubicDShift = fCEdge.fCubicDShift;
164
165 fSnappedY = fCEdge.fCy;
166
167 return this->updateCubic();
168 }
169
updateCubic()170 bool SkAnalyticCubicEdge::updateCubic() {
171 int success;
172 int count = fCurveCount;
173 SkFixed oldx = fCEdge.fCx;
174 SkFixed oldy = fCEdge.fCy;
175 SkFixed newx, newy;
176 const int ddshift = fCurveShift;
177 const int dshift = fCubicDShift;
178
179 SkASSERT(count < 0);
180
181 do {
182 if (++count < 0) {
183 newx = oldx + (fCEdge.fCDx >> dshift);
184 fCEdge.fCDx += fCEdge.fCDDx >> ddshift;
185 fCEdge.fCDDx += fCEdge.fCDDDx;
186
187 newy = oldy + (fCEdge.fCDy >> dshift);
188 fCEdge.fCDy += fCEdge.fCDDy >> ddshift;
189 fCEdge.fCDDy += fCEdge.fCDDDy;
190 }
191 else { // last segment
192 newx = fCEdge.fCLastX;
193 newy = fCEdge.fCLastY;
194 }
195
196 // we want to say SkASSERT(oldy <= newy), but our finite fixedpoint
197 // doesn't always achieve that, so we have to explicitly pin it here.
198 if (newy < oldy) {
199 newy = oldy;
200 }
201
202 SkFixed newSnappedY = SnapY(newy);
203 // we want to SkASSERT(snappedNewY <= fCEdge.fCLastY), but our finite fixedpoint
204 // doesn't always achieve that, so we have to explicitly pin it here.
205 if (fCEdge.fCLastY < newSnappedY) {
206 newSnappedY = fCEdge.fCLastY;
207 count = 0;
208 }
209
210 SkFixed slope = SkFixedToFDot6(newSnappedY - fSnappedY) == 0
211 ? SK_MaxS32
212 : SkFDot6Div(SkFixedToFDot6(newx - oldx),
213 SkFixedToFDot6(newSnappedY - fSnappedY));
214
215 success = this->updateLine(oldx, fSnappedY, newx, newSnappedY, slope);
216
217 oldx = newx;
218 oldy = newy;
219 fSnappedY = newSnappedY;
220 } while (count < 0 && !success);
221
222 fCEdge.fCx = newx;
223 fCEdge.fCy = newy;
224 fCurveCount = SkToS8(count);
225 return success;
226 }
227