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