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