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 SkEdge_DEFINED
9 #define SkEdge_DEFINED
10
11 #include "include/core/SkPoint.h"
12 #include "include/core/SkRect.h"
13 #include "include/private/base/SkAssert.h"
14 #include "include/private/base/SkDebug.h"
15 #include "include/private/base/SkFixed.h"
16 #include "include/private/base/SkMath.h"
17 #include "include/private/base/SkSafe32.h"
18 #include "include/private/base/SkTo.h"
19 #include "src/core/SkFDot6.h"
20
21 #include <cstdint>
22 #include <utility>
23
24 // This correctly favors the lower-pixel when y0 is on a 1/2 pixel boundary
25 #define SkEdge_Compute_DY(top, y0) (SkLeftShift(top, 6) + 32 - (y0))
26
27 struct SkEdge {
28 enum Type {
29 kLine_Type,
30 kQuad_Type,
31 kCubic_Type
32 };
33
34 SkEdge* fNext;
35 SkEdge* fPrev;
36
37 SkFixed fX;
38 SkFixed fDX;
39 int32_t fFirstY;
40 int32_t fLastY;
41 Type fEdgeType; // Remembers the *initial* edge type
42 int8_t fCurveCount; // only used by kQuad(+) and kCubic(-)
43 uint8_t fCurveShift; // appled to all Dx/DDx/DDDx except for fCubicDShift exception
44 uint8_t fCubicDShift; // applied to fCDx and fCDy only in cubic
45 int8_t fWinding; // 1 or -1
46
47 int setLine(const SkPoint& p0, const SkPoint& p1, const SkIRect* clip, int shiftUp);
48 // call this version if you know you don't have a clip
49 inline int setLine(const SkPoint& p0, const SkPoint& p1, int shiftUp);
50 inline int updateLine(SkFixed ax, SkFixed ay, SkFixed bx, SkFixed by);
51 void chopLineWithClip(const SkIRect& clip);
52
intersectsClipSkEdge53 inline bool intersectsClip(const SkIRect& clip) const {
54 SkASSERT(fFirstY < clip.fBottom);
55 return fLastY >= clip.fTop;
56 }
57
58 #ifdef SK_DEBUG
59 void dump() const;
validateSkEdge60 void validate() const {
61 SkASSERT(fPrev && fNext);
62 SkASSERT(fPrev->fNext == this);
63 SkASSERT(fNext->fPrev == this);
64
65 SkASSERT(fFirstY <= fLastY);
66 SkASSERT(SkAbs32(fWinding) == 1);
67 }
68 #endif
69 };
70
71 struct SkQuadraticEdge : public SkEdge {
72 SkFixed fQx, fQy;
73 SkFixed fQDx, fQDy;
74 SkFixed fQDDx, fQDDy;
75 SkFixed fQLastX, fQLastY;
76
77 bool setQuadraticWithoutUpdate(const SkPoint pts[3], int shiftUp);
78 int setQuadratic(const SkPoint pts[3], int shiftUp);
79 int updateQuadratic();
80 };
81
82 struct SkCubicEdge : public SkEdge {
83 SkFixed fCx, fCy;
84 SkFixed fCDx, fCDy;
85 SkFixed fCDDx, fCDDy;
86 SkFixed fCDDDx, fCDDDy;
87 SkFixed fCLastX, fCLastY;
88
89 bool setCubicWithoutUpdate(const SkPoint pts[4], int shiftUp, bool sortY = true);
90 int setCubic(const SkPoint pts[4], int shiftUp);
91 int updateCubic();
92 };
93
setLine(const SkPoint & p0,const SkPoint & p1,int shift)94 int SkEdge::setLine(const SkPoint& p0, const SkPoint& p1, int shift) {
95 SkFDot6 x0, y0, x1, y1;
96
97 {
98 #ifdef SK_RASTERIZE_EVEN_ROUNDING
99 x0 = SkScalarRoundToFDot6(p0.fX, shift);
100 y0 = SkScalarRoundToFDot6(p0.fY, shift);
101 x1 = SkScalarRoundToFDot6(p1.fX, shift);
102 y1 = SkScalarRoundToFDot6(p1.fY, shift);
103 #else
104 float scale = float(1 << (shift + 6));
105 x0 = int(p0.fX * scale);
106 y0 = int(p0.fY * scale);
107 x1 = int(p1.fX * scale);
108 y1 = int(p1.fY * scale);
109 #endif
110 }
111
112 int winding = 1;
113
114 if (y0 > y1) {
115 using std::swap;
116 swap(x0, x1);
117 swap(y0, y1);
118 winding = -1;
119 }
120
121 int top = SkFDot6Round(y0);
122 int bot = SkFDot6Round(y1);
123
124 // are we a zero-height line?
125 if (top == bot) {
126 return 0;
127 }
128
129 SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0);
130 const SkFDot6 dy = SkEdge_Compute_DY(top, y0);
131
132 fX = SkFDot6ToFixed(x0 + SkFixedMul(slope, dy)); // + SK_Fixed1/2
133 fDX = slope;
134 fFirstY = top;
135 fLastY = bot - 1;
136 fEdgeType = kLine_Type;
137 fCurveCount = 0;
138 fWinding = SkToS8(winding);
139 fCurveShift = 0;
140 return 1;
141 }
142
143 #endif
144