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
19struct 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
44    inline bool intersectsClip(const SkIRect& clip) const {
45        SkASSERT(fFirstY < clip.fBottom);
46        return fLastY >= clip.fTop;
47    }
48
49#ifdef SK_DEBUG
50    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
54    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
65struct 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
76struct 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);
84    int setCubic(const SkPoint pts[4], int shiftUp);
85    int updateCubic();
86};
87
88int 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