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 "include/private/SkTo.h"
12 #include "src/core/SkEdge.h"
13 
14 #include <utility>
15 
16 struct SkAnalyticEdge {
17     // Similar to SkEdge, the conic edges will be converted to quadratic edges
18     enum Type {
19         kLine_Type,
20         kQuad_Type,
21         kCubic_Type
22     };
23 
24     SkAnalyticEdge* fNext;
25     SkAnalyticEdge* fPrev;
26 
27     // During aaa_walk_edges, if this edge is a left edge,
28     // then fRiteE is its corresponding right edge. Otherwise it's nullptr.
29     SkAnalyticEdge* fRiteE;
30 
31     SkFixed fX;
32     SkFixed fDX;
33     SkFixed fUpperX;        // The x value when y = fUpperY
34     SkFixed fY;             // The current y
35     SkFixed fUpperY;        // The upper bound of y (our edge is from y = fUpperY to y = fLowerY)
36     SkFixed fLowerY;        // The lower bound of y (our edge is from y = fUpperY to y = fLowerY)
37     SkFixed fDY;            // abs(1/fDX); may be SK_MaxS32 when fDX is close to 0.
38                             // fDY is only used for blitting trapezoids.
39 
40     SkFixed fSavedX;        // For deferred blitting
41     SkFixed fSavedY;        // For deferred blitting
42     SkFixed fSavedDY;       // For deferred blitting
43 
44     int8_t  fCurveCount;    // only used by kQuad(+) and kCubic(-)
45     uint8_t fCurveShift;    // appled to all Dx/DDx/DDDx except for fCubicDShift exception
46     uint8_t fCubicDShift;   // applied to fCDx and fCDy only in cubic
47     int8_t  fWinding;       // 1 or -1
48 
49     static const int kDefaultAccuracy = 2; // default accuracy for snapping
50 
SnapYSkAnalyticEdge51     static inline SkFixed SnapY(SkFixed y) {
52         const int accuracy = kDefaultAccuracy;
53         // This approach is safer than left shift, round, then right shift
54         return ((unsigned)y + (SK_Fixed1 >> (accuracy + 1))) >> (16 - accuracy) << (16 - accuracy);
55     }
56 
57     // Update fX, fY of this edge so fY = y
goYSkAnalyticEdge58     inline void goY(SkFixed y) {
59         if (y == fY + SK_Fixed1) {
60             fX = fX + fDX;
61             fY = y;
62         } else if (y != fY) {
63             // Drop lower digits as our alpha only has 8 bits
64             // (fDX and y - fUpperY may be greater than SK_Fixed1)
65             fX = fUpperX + SkFixedMul(fDX, y - fUpperY);
66             fY = y;
67         }
68     }
69 
goYSkAnalyticEdge70     inline void goY(SkFixed y, int yShift) {
71         SkASSERT(yShift >= 0 && yShift <= kDefaultAccuracy);
72         SkASSERT(fDX == 0 || y - fY == SK_Fixed1 >> yShift);
73         fY = y;
74         fX += fDX >> yShift;
75     }
76 
saveXYSkAnalyticEdge77     inline void saveXY(SkFixed x, SkFixed y, SkFixed dY) {
78         fSavedX = x;
79         fSavedY = y;
80         fSavedDY = dY;
81     }
82 
83     bool setLine(const SkPoint& p0, const SkPoint& p1);
84     bool updateLine(SkFixed ax, SkFixed ay, SkFixed bx, SkFixed by, SkFixed slope);
85 
86     // return true if we're NOT done with this edge
87     bool update(SkFixed last_y, bool sortY = true);
88 
89 #ifdef SK_DEBUG
dumpSkAnalyticEdge90     void dump() const {
91         SkDebugf("edge: upperY:%d lowerY:%d y:%g x:%g dx:%g w:%d\n",
92                  fUpperY, fLowerY, SkFixedToFloat(fY), SkFixedToFloat(fX),
93                  SkFixedToFloat(fDX), fWinding);
94     }
95 
validateSkAnalyticEdge96     void validate() const {
97          SkASSERT(fPrev && fNext);
98          SkASSERT(fPrev->fNext == this);
99          SkASSERT(fNext->fPrev == this);
100 
101          SkASSERT(fUpperY < fLowerY);
102          SkASSERT(SkAbs32(fWinding) == 1);
103     }
104 #endif
105 };
106 
107 struct SkAnalyticQuadraticEdge : public SkAnalyticEdge {
108     SkQuadraticEdge fQEdge;
109 
110     // snap y to integer points in the middle of the curve to accelerate AAA path filling
111     SkFixed fSnappedX, fSnappedY;
112 
113     bool setQuadratic(const SkPoint pts[3]);
114     bool updateQuadratic();
keepContinuousSkAnalyticQuadraticEdge115     inline void keepContinuous() {
116         // We use fX as the starting x to ensure the continuouty.
117         // Without it, we may break the sorted edge list.
118         SkASSERT(SkAbs32(fX - SkFixedMul(fY - fSnappedY, fDX) - fSnappedX) < SK_Fixed1);
119         SkASSERT(SkAbs32(fY - fSnappedY) < SK_Fixed1); // This may differ due to smooth jump
120         fSnappedX = fX;
121         fSnappedY = fY;
122     }
123 };
124 
125 struct SkAnalyticCubicEdge : public SkAnalyticEdge {
126     SkCubicEdge fCEdge;
127 
128     SkFixed fSnappedY; // to make sure that y is increasing with smooth jump and snapping
129 
130     bool setCubic(const SkPoint pts[4], bool sortY = true);
131     bool updateCubic(bool sortY = true);
keepContinuousSkAnalyticCubicEdge132     inline void keepContinuous() {
133         SkASSERT(SkAbs32(fX - SkFixedMul(fDX, fY - SnapY(fCEdge.fCy)) - fCEdge.fCx) < SK_Fixed1);
134         fCEdge.fCx = fX;
135         fSnappedY = fY;
136     }
137 };
138 
139 struct SkBezier {
140     int fCount; // 2 line, 3 quad, 4 cubic
141     SkPoint fP0;
142     SkPoint fP1;
143 
144     // See if left shift, covert to SkFDot6, and round has the same top and bottom y.
145     // If so, the edge will be empty.
146     static inline bool IsEmpty(SkScalar y0, SkScalar y1, int shift = 2) {
147 #ifdef SK_RASTERIZE_EVEN_ROUNDING
148         return SkScalarRoundToFDot6(y0, shift) == SkScalarRoundToFDot6(y1, shift);
149 #else
150         SkScalar scale = (1 << (shift + 6));
151         return SkFDot6Round(int(y0 * scale)) == SkFDot6Round(int(y1 * scale));
152 #endif
153     }
154 };
155 
156 struct SkLine : public SkBezier {
setSkLine157     bool set(const SkPoint pts[2]){
158         if (IsEmpty(pts[0].fY, pts[1].fY)) {
159             return false;
160         }
161         fCount = 2;
162         fP0 = pts[0];
163         fP1 = pts[1];
164         return true;
165     }
166 };
167 
168 struct SkQuad : public SkBezier {
169     SkPoint fP2;
170 
setSkQuad171     bool set(const SkPoint pts[3]){
172         if (IsEmpty(pts[0].fY, pts[2].fY)) {
173             return false;
174         }
175         fCount = 3;
176         fP0 = pts[0];
177         fP1 = pts[1];
178         fP2 = pts[2];
179         return true;
180     }
181 };
182 
183 struct SkCubic : public SkBezier {
184     SkPoint fP2;
185     SkPoint fP3;
186 
setSkCubic187     bool set(const SkPoint pts[4]){
188         // We do not chop at y extrema for cubics so pts[0], pts[1], pts[2], pts[3] may not be
189         // monotonic. Therefore, we have to check the emptiness for all three pairs, instead of just
190         // checking IsEmpty(pts[0].fY, pts[3].fY).
191         if (IsEmpty(pts[0].fY, pts[1].fY) && IsEmpty(pts[1].fY, pts[2].fY) &&
192                 IsEmpty(pts[2].fY, pts[3].fY)) {
193             return false;
194         }
195         fCount = 4;
196         fP0 = pts[0];
197         fP1 = pts[1];
198         fP2 = pts[2];
199         fP3 = pts[3];
200         return true;
201     }
202 };
203 
204 #endif
205