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
16struct 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
51 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
58 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
70 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
77 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
90 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
96 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
107struct 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();
115 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
125struct 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);
132 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
139struct 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
156struct SkLine : public SkBezier {
157 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
168struct SkQuad : public SkBezier {
169 SkPoint fP2;
170
171 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
183struct SkCubic : public SkBezier {
184 SkPoint fP2;
185 SkPoint fP3;
186
187 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