blob: 5e8403f5ecccac9bfe3123e32f7c445c60a7506a [file] [log] [blame]
/*
* Copyright 2006 The Android Open Source Project
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#ifndef SkAnalyticEdge_DEFINED
#define SkAnalyticEdge_DEFINED
#include "SkEdge.h"
struct SkAnalyticEdge {
// Similar to SkEdge, the conic edges will be converted to quadratic edges
enum Type {
kLine_Type,
kQuad_Type,
kCubic_Type
};
SkAnalyticEdge* fNext;
SkAnalyticEdge* fPrev;
// During aaa_walk_edges, if this edge is a left edge,
// then fRiteE is its corresponding right edge. Otherwise it's nullptr.
SkAnalyticEdge* fRiteE;
SkFixed fX;
SkFixed fDX;
SkFixed fUpperX; // The x value when y = fUpperY
SkFixed fY; // The current y
SkFixed fUpperY; // The upper bound of y (our edge is from y = fUpperY to y = fLowerY)
SkFixed fLowerY; // The lower bound of y (our edge is from y = fUpperY to y = fLowerY)
SkFixed fDY; // abs(1/fDX); may be SK_MaxS32 when fDX is close to 0.
// fDY is only used for blitting trapezoids.
SkFixed fSavedX; // For deferred blitting
SkFixed fSavedY; // For deferred blitting
SkFixed fSavedDY; // For deferred blitting
int8_t fCurveCount; // only used by kQuad(+) and kCubic(-)
uint8_t fCurveShift; // appled to all Dx/DDx/DDDx except for fCubicDShift exception
uint8_t fCubicDShift; // applied to fCDx and fCDy only in cubic
int8_t fWinding; // 1 or -1
static const int kDefaultAccuracy = 2; // default accuracy for snapping
static inline SkFixed SnapY(SkFixed y) {
const int accuracy = kDefaultAccuracy;
// This approach is safer than left shift, round, then right shift
return ((unsigned)y + (SK_Fixed1 >> (accuracy + 1))) >> (16 - accuracy) << (16 - accuracy);
}
// Update fX, fY of this edge so fY = y
inline void goY(SkFixed y) {
if (y == fY + SK_Fixed1) {
fX = fX + fDX;
fY = y;
} else if (y != fY) {
// Drop lower digits as our alpha only has 8 bits
// (fDX and y - fUpperY may be greater than SK_Fixed1)
fX = fUpperX + SkFixedMul(fDX, y - fUpperY);
fY = y;
}
}
inline void goY(SkFixed y, int yShift) {
SkASSERT(yShift >= 0 && yShift <= kDefaultAccuracy);
SkASSERT(fDX == 0 || y - fY == SK_Fixed1 >> yShift);
fY = y;
fX += fDX >> yShift;
}
inline void saveXY(SkFixed x, SkFixed y, SkFixed dY) {
fSavedX = x;
fSavedY = y;
fSavedDY = dY;
}
inline bool setLine(const SkPoint& p0, const SkPoint& p1);
inline bool updateLine(SkFixed ax, SkFixed ay, SkFixed bx, SkFixed by, SkFixed slope);
// return true if we're NOT done with this edge
bool update(SkFixed last_y, bool sortY = true);
#ifdef SK_DEBUG
void dump() const {
SkDebugf("edge: upperY:%d lowerY:%d y:%g x:%g dx:%g w:%d\n",
fUpperY, fLowerY, SkFixedToFloat(fY), SkFixedToFloat(fX),
SkFixedToFloat(fDX), fWinding);
}
void validate() const {
SkASSERT(fPrev && fNext);
SkASSERT(fPrev->fNext == this);
SkASSERT(fNext->fPrev == this);
SkASSERT(fUpperY < fLowerY);
SkASSERT(SkAbs32(fWinding) == 1);
}
#endif
};
struct SkAnalyticQuadraticEdge : public SkAnalyticEdge {
SkQuadraticEdge fQEdge;
// snap y to integer points in the middle of the curve to accelerate AAA path filling
SkFixed fSnappedX, fSnappedY;
bool setQuadratic(const SkPoint pts[3]);
bool updateQuadratic();
inline void keepContinuous() {
// We use fX as the starting x to ensure the continuouty.
// Without it, we may break the sorted edge list.
SkASSERT(SkAbs32(fX - SkFixedMul(fY - fSnappedY, fDX) - fSnappedX) < SK_Fixed1);
SkASSERT(SkAbs32(fY - fSnappedY) < SK_Fixed1); // This may differ due to smooth jump
fSnappedX = fX;
fSnappedY = fY;
}
};
struct SkAnalyticCubicEdge : public SkAnalyticEdge {
SkCubicEdge fCEdge;
SkFixed fSnappedY; // to make sure that y is increasing with smooth jump and snapping
bool setCubic(const SkPoint pts[4], bool sortY = true);
bool updateCubic(bool sortY = true);
inline void keepContinuous() {
SkASSERT(SkAbs32(fX - SkFixedMul(fDX, fY - SnapY(fCEdge.fCy)) - fCEdge.fCx) < SK_Fixed1);
fCEdge.fCx = fX;
fSnappedY = fY;
}
};
bool SkAnalyticEdge::setLine(const SkPoint& p0, const SkPoint& p1) {
fRiteE = nullptr;
// We must set X/Y using the same way (e.g., times 4, to FDot6, then to Fixed) as Quads/Cubics.
// Otherwise the order of the edge might be wrong due to precision limit.
const int accuracy = kDefaultAccuracy;
#ifdef SK_RASTERIZE_EVEN_ROUNDING
SkFixed x0 = SkFDot6ToFixed(SkScalarRoundToFDot6(p0.fX, accuracy)) >> accuracy;
SkFixed y0 = SnapY(SkFDot6ToFixed(SkScalarRoundToFDot6(p0.fY, accuracy)) >> accuracy);
SkFixed x1 = SkFDot6ToFixed(SkScalarRoundToFDot6(p1.fX, accuracy)) >> accuracy;
SkFixed y1 = SnapY(SkFDot6ToFixed(SkScalarRoundToFDot6(p1.fY, accuracy)) >> accuracy);
#else
const int multiplier = (1 << kDefaultAccuracy);
SkFixed x0 = SkFDot6ToFixed(SkScalarToFDot6(p0.fX * multiplier)) >> accuracy;
SkFixed y0 = SnapY(SkFDot6ToFixed(SkScalarToFDot6(p0.fY * multiplier)) >> accuracy);
SkFixed x1 = SkFDot6ToFixed(SkScalarToFDot6(p1.fX * multiplier)) >> accuracy;
SkFixed y1 = SnapY(SkFDot6ToFixed(SkScalarToFDot6(p1.fY * multiplier)) >> accuracy);
#endif
int winding = 1;
if (y0 > y1) {
SkTSwap(x0, x1);
SkTSwap(y0, y1);
winding = -1;
}
// are we a zero-height line?
SkFDot6 dy = SkFixedToFDot6(y1 - y0);
if (dy == 0) {
return false;
}
SkFDot6 dx = SkFixedToFDot6(x1 - x0);
SkFixed slope = QuickSkFDot6Div(dx, dy);
SkFixed absSlope = SkAbs32(slope);
fX = x0;
fDX = slope;
fUpperX = x0;
fY = y0;
fUpperY = y0;
fLowerY = y1;
fDY = dx == 0 || slope == 0 ? SK_MaxS32 : absSlope < kInverseTableSize
? QuickFDot6Inverse::Lookup(absSlope)
: SkAbs32(QuickSkFDot6Div(dy, dx));
fCurveCount = 0;
fWinding = SkToS8(winding);
fCurveShift = 0;
return true;
}
struct SkBezier {
int fCount; // 2 line, 3 quad, 4 cubic
SkPoint fP0;
SkPoint fP1;
// See if left shift, covert to SkFDot6, and round has the same top and bottom y.
// If so, the edge will be empty.
static inline bool IsEmpty(SkScalar y0, SkScalar y1, int shift = 2) {
#ifdef SK_RASTERIZE_EVEN_ROUNDING
return SkScalarRoundToFDot6(y0, shift) == SkScalarRoundToFDot6(y1, shift);
#else
SkScalar scale = (1 << (shift + 6));
return SkFDot6Round(int(y0 * scale)) == SkFDot6Round(int(y1 * scale));
#endif
}
};
struct SkLine : public SkBezier {
bool set(const SkPoint pts[2]){
if (IsEmpty(pts[0].fY, pts[1].fY)) {
return false;
}
fCount = 2;
fP0 = pts[0];
fP1 = pts[1];
return true;
}
};
struct SkQuad : public SkBezier {
SkPoint fP2;
bool set(const SkPoint pts[3]){
if (IsEmpty(pts[0].fY, pts[2].fY)) {
return false;
}
fCount = 3;
fP0 = pts[0];
fP1 = pts[1];
fP2 = pts[2];
return true;
}
};
struct SkCubic : public SkBezier {
SkPoint fP2;
SkPoint fP3;
bool set(const SkPoint pts[4]){
// We do not chop at y extrema for cubics so pts[0], pts[1], pts[2], pts[3] may not be
// monotonic. Therefore, we have to check the emptiness for all three pairs, instead of just
// checking IsEmpty(pts[0].fY, pts[3].fY).
if (IsEmpty(pts[0].fY, pts[1].fY) && IsEmpty(pts[1].fY, pts[2].fY) &&
IsEmpty(pts[2].fY, pts[3].fY)) {
return false;
}
fCount = 4;
fP0 = pts[0];
fP1 = pts[1];
fP2 = pts[2];
fP3 = pts[3];
return true;
}
};
#endif