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 // We don't chop at y extrema for cubics so the y is not guaranteed to be increasing for them.
24 // In that case, we have to swap x/y and negate the winding.
25 if (y0 > y1) {
26 SkTSwap(x0, x1);
27 SkTSwap(y0, y1);
28 fWinding = -fWinding;
29 }
30
31 SkASSERT(y0 <= y1);
32
33 SkFDot6 dx = SkFixedToFDot6(x1 - x0);
34 SkFDot6 dy = SkFixedToFDot6(y1 - y0);
35
36 // are we a zero-height line?
37 if (dy == 0) {
38 return false;
39 }
40
41 SkASSERT(slope < SK_MaxS32);
42
43 SkFDot6 absSlope = SkAbs32(SkFixedToFDot6(slope));
44 fX = x0;
45 fDX = slope;
46 fUpperX = x0;
47 fY = y0;
48 fUpperY = y0;
49 fLowerY = y1;
50 fDY = (dx == 0 || slope == 0)
51 ? SK_MaxS32
52 : absSlope < kInverseTableSize
53 ? QuickFDot6Inverse::Lookup(absSlope)
54 : SkAbs32(QuickSkFDot6Div(dy, dx));
55
56 return true;
57 }
58
update(SkFixed last_y,bool sortY)59 bool SkAnalyticEdge::update(SkFixed last_y, bool sortY) {
60 SkASSERT(last_y >= fLowerY); // we shouldn't update edge if last_y < fLowerY
61 if (fCurveCount < 0) {
62 return static_cast<SkAnalyticCubicEdge*>(this)->updateCubic(sortY);
63 } else if (fCurveCount > 0) {
64 return static_cast<SkAnalyticQuadraticEdge*>(this)->updateQuadratic();
65 }
66 return false;
67 }
68
setQuadratic(const SkPoint pts[3])69 bool SkAnalyticQuadraticEdge::setQuadratic(const SkPoint pts[3]) {
70 fRiteE = nullptr;
71
72 if (!fQEdge.setQuadraticWithoutUpdate(pts, kDefaultAccuracy)) {
73 return false;
74 }
75 fQEdge.fQx >>= kDefaultAccuracy;
76 fQEdge.fQy >>= kDefaultAccuracy;
77 fQEdge.fQDx >>= kDefaultAccuracy;
78 fQEdge.fQDy >>= kDefaultAccuracy;
79 fQEdge.fQDDx >>= kDefaultAccuracy;
80 fQEdge.fQDDy >>= kDefaultAccuracy;
81 fQEdge.fQLastX >>= kDefaultAccuracy;
82 fQEdge.fQLastY >>= kDefaultAccuracy;
83 fQEdge.fQy = SnapY(fQEdge.fQy);
84 fQEdge.fQLastY = SnapY(fQEdge.fQLastY);
85
86 fWinding = fQEdge.fWinding;
87 fCurveCount = fQEdge.fCurveCount;
88 fCurveShift = fQEdge.fCurveShift;
89
90 fSnappedX = fQEdge.fQx;
91 fSnappedY = fQEdge.fQy;
92
93 return this->updateQuadratic();
94 }
95
updateQuadratic()96 bool SkAnalyticQuadraticEdge::updateQuadratic() {
97 int success = 0; // initialize to fail!
98 int count = fCurveCount;
99 SkFixed oldx = fQEdge.fQx;
100 SkFixed oldy = fQEdge.fQy;
101 SkFixed dx = fQEdge.fQDx;
102 SkFixed dy = fQEdge.fQDy;
103 SkFixed newx, newy, newSnappedX, newSnappedY;
104 int shift = fCurveShift;
105
106 SkASSERT(count > 0);
107
108 do {
109 SkFixed slope;
110 if (--count > 0)
111 {
112 newx = oldx + (dx >> shift);
113 newy = oldy + (dy >> shift);
114 if (SkAbs32(dy >> shift) >= SK_Fixed1 * 2) { // only snap when dy is large enough
115 SkFDot6 diffY = SkFixedToFDot6(newy - fSnappedY);
116 slope = diffY ? QuickSkFDot6Div(SkFixedToFDot6(newx - fSnappedX), diffY)
117 : SK_MaxS32;
118 newSnappedY = SkTMin<SkFixed>(fQEdge.fQLastY, SkFixedRoundToFixed(newy));
119 newSnappedX = newx - SkFixedMul(slope, newy - newSnappedY);
120 } else {
121 newSnappedY = SkTMin(fQEdge.fQLastY, SnapY(newy));
122 newSnappedX = newx;
123 SkFDot6 diffY = SkFixedToFDot6(newSnappedY - fSnappedY);
124 slope = diffY ? QuickSkFDot6Div(SkFixedToFDot6(newx - fSnappedX), diffY)
125 : SK_MaxS32;
126 }
127 dx += fQEdge.fQDDx;
128 dy += fQEdge.fQDDy;
129 }
130 else // last segment
131 {
132 newx = fQEdge.fQLastX;
133 newy = fQEdge.fQLastY;
134 newSnappedY = newy;
135 newSnappedX = newx;
136 SkFDot6 diffY = (newy - fSnappedY) >> 10;
137 slope = diffY ? QuickSkFDot6Div((newx - fSnappedX) >> 10, diffY) : SK_MaxS32;
138 }
139 if (slope < SK_MaxS32) {
140 success = this->updateLine(fSnappedX, fSnappedY, newSnappedX, newSnappedY, slope);
141 }
142 oldx = newx;
143 oldy = newy;
144 } while (count > 0 && !success);
145
146 SkASSERT(newSnappedY <= fQEdge.fQLastY);
147
148 fQEdge.fQx = newx;
149 fQEdge.fQy = newy;
150 fQEdge.fQDx = dx;
151 fQEdge.fQDy = dy;
152 fSnappedX = newSnappedX;
153 fSnappedY = newSnappedY;
154 fCurveCount = SkToS8(count);
155 return success;
156 }
157
setCubic(const SkPoint pts[4],bool sortY)158 bool SkAnalyticCubicEdge::setCubic(const SkPoint pts[4], bool sortY) {
159 fRiteE = nullptr;
160
161 if (!fCEdge.setCubicWithoutUpdate(pts, kDefaultAccuracy, sortY)) {
162 return false;
163 }
164
165 fCEdge.fCx >>= kDefaultAccuracy;
166 fCEdge.fCy >>= kDefaultAccuracy;
167 fCEdge.fCDx >>= kDefaultAccuracy;
168 fCEdge.fCDy >>= kDefaultAccuracy;
169 fCEdge.fCDDx >>= kDefaultAccuracy;
170 fCEdge.fCDDy >>= kDefaultAccuracy;
171 fCEdge.fCDDDx >>= kDefaultAccuracy;
172 fCEdge.fCDDDy >>= kDefaultAccuracy;
173 fCEdge.fCLastX >>= kDefaultAccuracy;
174 fCEdge.fCLastY >>= kDefaultAccuracy;
175 fCEdge.fCy = SnapY(fCEdge.fCy);
176 fCEdge.fCLastY = SnapY(fCEdge.fCLastY);
177
178 fWinding = fCEdge.fWinding;
179 fCurveCount = fCEdge.fCurveCount;
180 fCurveShift = fCEdge.fCurveShift;
181 fCubicDShift = fCEdge.fCubicDShift;
182
183 fSnappedY = fCEdge.fCy;
184
185 return this->updateCubic(sortY);
186 }
187
updateCubic(bool sortY)188 bool SkAnalyticCubicEdge::updateCubic(bool sortY) {
189 int success;
190 int count = fCurveCount;
191 SkFixed oldx = fCEdge.fCx;
192 SkFixed oldy = fCEdge.fCy;
193 SkFixed newx, newy;
194 const int ddshift = fCurveShift;
195 const int dshift = fCubicDShift;
196
197 SkASSERT(count < 0);
198
199 do {
200 if (++count < 0) {
201 newx = oldx + (fCEdge.fCDx >> dshift);
202 fCEdge.fCDx += fCEdge.fCDDx >> ddshift;
203 fCEdge.fCDDx += fCEdge.fCDDDx;
204
205 newy = oldy + (fCEdge.fCDy >> dshift);
206 fCEdge.fCDy += fCEdge.fCDDy >> ddshift;
207 fCEdge.fCDDy += fCEdge.fCDDDy;
208 }
209 else { // last segment
210 newx = fCEdge.fCLastX;
211 newy = fCEdge.fCLastY;
212 }
213
214 // we want to say SkASSERT(oldy <= newy), but our finite fixedpoint
215 // doesn't always achieve that, so we have to explicitly pin it here.
216 if (sortY && newy < oldy) {
217 newy = oldy;
218 }
219
220 SkFixed newSnappedY = SnapY(newy);
221 // we want to SkASSERT(snappedNewY <= fCEdge.fCLastY), but our finite fixedpoint
222 // doesn't always achieve that, so we have to explicitly pin it here.
223 if (sortY && fCEdge.fCLastY < newSnappedY) {
224 newSnappedY = fCEdge.fCLastY;
225 count = 0;
226 }
227
228 SkFixed slope = SkFixedToFDot6(newSnappedY - fSnappedY) == 0
229 ? SK_MaxS32
230 : SkFDot6Div(SkFixedToFDot6(newx - oldx),
231 SkFixedToFDot6(newSnappedY - fSnappedY));
232
233 success = this->updateLine(oldx, fSnappedY, newx, newSnappedY, slope);
234
235 oldx = newx;
236 oldy = newy;
237 fSnappedY = newSnappedY;
238 } while (count < 0 && !success);
239
240 fCEdge.fCx = newx;
241 fCEdge.fCy = newy;
242 fCurveCount = SkToS8(count);
243 return success;
244 }
245