SkAnalyticEdge.h revision 197bde9c606dbd22eafa02509bf4ea3ce7a0c69b 
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 "SkEdge.h"
12
13// Use this to check that we successfully guard the change against Chromium layout tests
14#ifndef  SK_SUPPORT_LEGACY_AAA
15# define SK_SUPPORT_LEGACY_AAA
16#endif
17
18struct SkAnalyticEdge {
19    // Similar to SkEdge, the conic edges will be converted to quadratic edges
20    enum Type {
21        kLine_Type,
22        kQuad_Type,
23        kCubic_Type
24    };
25
26    SkAnalyticEdge* fNext;
27    SkAnalyticEdge* fPrev;
28
29    // During aaa_walk_edges, if this edge is a left edge,
30    // then fRiteE is its corresponding right edge. Otherwise it's nullptr.
31    SkAnalyticEdge* fRiteE;
32
33    SkFixed fX;
34    SkFixed fDX;
35    SkFixed fUpperX;        // The x value when y = fUpperY
36    SkFixed fY;             // The current y
37    SkFixed fUpperY;        // The upper bound of y (our edge is from y = fUpperY to y = fLowerY)
38    SkFixed fLowerY;        // The lower bound of y (our edge is from y = fUpperY to y = fLowerY)
39    SkFixed fDY;            // abs(1/fDX); may be SK_MaxS32 when fDX is close to 0.
40                            // fDY is only used for blitting trapezoids.
41
42    SkFixed fSavedX;        // For deferred blitting
43    SkFixed fSavedY;        // For deferred blitting
44    SkFixed fSavedDY;       // For deferred blitting
45
46    int8_t  fCurveCount;    // only used by kQuad(+) and kCubic(-)
47    uint8_t fCurveShift;    // appled to all Dx/DDx/DDDx except for fCubicDShift exception
48    uint8_t fCubicDShift;   // applied to fCDx and fCDy only in cubic
49    int8_t  fWinding;       // 1 or -1
50
51    static const int kDefaultAccuracy = 2; // default accuracy for snapping
52
53    static inline SkFixed SnapY(SkFixed y) {
54        const int accuracy = kDefaultAccuracy;
55        // This approach is safer than left shift, round, then right shift
56        return ((unsigned)y + (SK_Fixed1 >> (accuracy + 1))) >> (16 - accuracy) << (16 - accuracy);
57    }
58
59    // Update fX, fY of this edge so fY = y
60    inline void goY(SkFixed y) {
61        if (y == fY + SK_Fixed1) {
62            fX = fX + fDX;
63            fY = y;
64        } else if (y != fY) {
65            // Drop lower digits as our alpha only has 8 bits
66            // (fDX and y - fUpperY may be greater than SK_Fixed1)
67            fX = fUpperX + SkFixedMul(fDX, y - fUpperY);
68            fY = y;
69        }
70    }
71
72    inline void goY(SkFixed y, int yShift) {
73        SkASSERT(yShift >= 0 && yShift <= kDefaultAccuracy);
74        SkASSERT(fDX == 0 || y - fY == SK_Fixed1 >> yShift);
75        fY = y;
76        fX += fDX >> yShift;
77    }
78
79    inline void saveXY(SkFixed x, SkFixed y, SkFixed dY) {
80        fSavedX = x;
81        fSavedY = y;
82        fSavedDY = dY;
83    }
84
85    inline bool setLine(const SkPoint& p0, const SkPoint& p1);
86    inline bool updateLine(SkFixed ax, SkFixed ay, SkFixed bx, SkFixed by, SkFixed slope);
87
88#ifdef SK_DEBUG
89    void dump() const {
90        SkDebugf("edge: upperY:%d lowerY:%d y:%g x:%g dx:%g w:%d\n",
91                 fUpperY, fLowerY, SkFixedToFloat(fY), SkFixedToFloat(fX),
92                 SkFixedToFloat(fDX), fWinding);
93    }
94
95    void validate() const {
96         SkASSERT(fPrev && fNext);
97         SkASSERT(fPrev->fNext == this);
98         SkASSERT(fNext->fPrev == this);
99
100         SkASSERT(fUpperY < fLowerY);
101         SkASSERT(SkAbs32(fWinding) == 1);
102    }
103#endif
104};
105
106struct SkAnalyticQuadraticEdge : public SkAnalyticEdge {
107    SkQuadraticEdge fQEdge;
108
109    // snap y to integer points in the middle of the curve to accelerate AAA path filling
110    SkFixed fSnappedX, fSnappedY;
111
112    bool setQuadratic(const SkPoint pts[3]);
113    bool updateQuadratic();
114    inline void keepContinuous() {
115        // We use fX as the starting x to ensure the continuouty.
116        // Without it, we may break the sorted edge list.
117        SkASSERT(SkAbs32(fX - SkFixedMul(fY - fSnappedY, fDX) - fSnappedX) < SK_Fixed1);
118        SkASSERT(SkAbs32(fY - fSnappedY) < SK_Fixed1); // This may differ due to smooth jump
119        fSnappedX = fX;
120        fSnappedY = fY;
121    }
122};
123
124struct SkAnalyticCubicEdge : public SkAnalyticEdge {
125    SkCubicEdge fCEdge;
126
127    SkFixed fSnappedY; // to make sure that y is increasing with smooth jump and snapping
128
129    bool setCubic(const SkPoint pts[4]);
130    bool updateCubic();
131    inline void keepContinuous() {
132        SkASSERT(SkAbs32(fX - SkFixedMul(fDX, fY - SnapY(fCEdge.fCy)) - fCEdge.fCx) < SK_Fixed1);
133        fCEdge.fCx = fX;
134        fSnappedY = fY;
135    }
136};
137
138bool SkAnalyticEdge::setLine(const SkPoint& p0, const SkPoint& p1) {
139    fRiteE = nullptr;
140
141    // We must set X/Y using the same way (e.g., times 4, to FDot6, then to Fixed) as Quads/Cubics.
142    // Otherwise the order of the edge might be wrong due to precision limit.
143    const int accuracy = kDefaultAccuracy;
144    const int multiplier = (1 << kDefaultAccuracy);
145    SkFixed x0 = SkFDot6ToFixed(SkScalarToFDot6(p0.fX * multiplier)) >> accuracy;
146    SkFixed y0 = SnapY(SkFDot6ToFixed(SkScalarToFDot6(p0.fY * multiplier)) >> accuracy);
147    SkFixed x1 = SkFDot6ToFixed(SkScalarToFDot6(p1.fX * multiplier)) >> accuracy;
148    SkFixed y1 = SnapY(SkFDot6ToFixed(SkScalarToFDot6(p1.fY * multiplier)) >> accuracy);
149
150    // are we a zero-height line?
151    if (y0 == y1) {
152        return false;
153    }
154
155    int winding = 1;
156
157    if (y0 > y1) {
158        SkTSwap(x0, x1);
159        SkTSwap(y0, y1);
160        winding = -1;
161    }
162
163#ifdef SK_SUPPORT_LEGACY_AAA
164    SkFixed slope = SkFixedDiv(x1 - x0, y1 - y0);
165#else
166    SkFDot6 dy = SkFixedToFDot6(y1 - y0);
167    SkFDot6 dx = SkFixedToFDot6(x1 - x0);
168    SkFixed slope = dy ? QuickSkFDot6Div(dx, dy) : SK_MaxS32;
169    SkASSERT(dx == 0 || slope != 0);
170    SkFixed absSlope = SkAbs32(slope);
171#endif
172
173    fX          = x0;
174    fDX         = slope;
175    fUpperX     = x0;
176    fY          = y0;
177    fUpperY     = y0;
178    fLowerY     = y1;
179#ifdef SK_SUPPORT_LEGACY_AAA
180    fDY         = x1 != x0 ? SkAbs32(SkFixedDiv(y1 - y0, x1 - x0)) : SK_MaxS32;
181#else
182    fDY         = dx == 0 ? SK_MaxS32 : absSlope < kInverseTableSize
183                                                 ? QuickFDot6Inverse::Lookup(absSlope)
184                                                 : SkAbs32(QuickSkFDot6Div(dy, dx));
185#endif
186    fCurveCount = 0;
187    fWinding    = SkToS8(winding);
188    fCurveShift = 0;
189
190    return true;
191}
192
193#endif
194