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 "include/private/SkTo.h" 12#include "src/core/SkEdge.h" 13 14#include <utility> 15 16struct SkAnalyticEdge { 17 // Similar to SkEdge, the conic edges will be converted to quadratic edges 18 enum Type { 19 kLine_Type, 20 kQuad_Type, 21 kCubic_Type 22 }; 23 24 SkAnalyticEdge* fNext; 25 SkAnalyticEdge* fPrev; 26 27 // During aaa_walk_edges, if this edge is a left edge, 28 // then fRiteE is its corresponding right edge. Otherwise it's nullptr. 29 SkAnalyticEdge* fRiteE; 30 31 SkFixed fX; 32 SkFixed fDX; 33 SkFixed fUpperX; // The x value when y = fUpperY 34 SkFixed fY; // The current y 35 SkFixed fUpperY; // The upper bound of y (our edge is from y = fUpperY to y = fLowerY) 36 SkFixed fLowerY; // The lower bound of y (our edge is from y = fUpperY to y = fLowerY) 37 SkFixed fDY; // abs(1/fDX); may be SK_MaxS32 when fDX is close to 0. 38 // fDY is only used for blitting trapezoids. 39 40 SkFixed fSavedX; // For deferred blitting 41 SkFixed fSavedY; // For deferred blitting 42 SkFixed fSavedDY; // For deferred blitting 43 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 int8_t fWinding; // 1 or -1 48 49 static const int kDefaultAccuracy = 2; // default accuracy for snapping 50 51 static inline SkFixed SnapY(SkFixed y) { 52 const int accuracy = kDefaultAccuracy; 53 // This approach is safer than left shift, round, then right shift 54 return ((unsigned)y + (SK_Fixed1 >> (accuracy + 1))) >> (16 - accuracy) << (16 - accuracy); 55 } 56 57 // Update fX, fY of this edge so fY = y 58 inline void goY(SkFixed y) { 59 if (y == fY + SK_Fixed1) { 60 fX = fX + fDX; 61 fY = y; 62 } else if (y != fY) { 63 // Drop lower digits as our alpha only has 8 bits 64 // (fDX and y - fUpperY may be greater than SK_Fixed1) 65 fX = fUpperX + SkFixedMul(fDX, y - fUpperY); 66 fY = y; 67 } 68 } 69 70 inline void goY(SkFixed y, int yShift) { 71 SkASSERT(yShift >= 0 && yShift <= kDefaultAccuracy); 72 SkASSERT(fDX == 0 || y - fY == SK_Fixed1 >> yShift); 73 fY = y; 74 fX += fDX >> yShift; 75 } 76 77 inline void saveXY(SkFixed x, SkFixed y, SkFixed dY) { 78 fSavedX = x; 79 fSavedY = y; 80 fSavedDY = dY; 81 } 82 83 bool setLine(const SkPoint& p0, const SkPoint& p1); 84 bool updateLine(SkFixed ax, SkFixed ay, SkFixed bx, SkFixed by, SkFixed slope); 85 86 // return true if we're NOT done with this edge 87 bool update(SkFixed last_y, bool sortY = true); 88 89#ifdef SK_DEBUG 90 void dump() const { 91 SkDebugf("edge: upperY:%d lowerY:%d y:%g x:%g dx:%g w:%d\n", 92 fUpperY, fLowerY, SkFixedToFloat(fY), SkFixedToFloat(fX), 93 SkFixedToFloat(fDX), fWinding); 94 } 95 96 void validate() const { 97 SkASSERT(fPrev && fNext); 98 SkASSERT(fPrev->fNext == this); 99 SkASSERT(fNext->fPrev == this); 100 101 SkASSERT(fUpperY < fLowerY); 102 SkASSERT(SkAbs32(fWinding) == 1); 103 } 104#endif 105}; 106 107struct SkAnalyticQuadraticEdge : public SkAnalyticEdge { 108 SkQuadraticEdge fQEdge; 109 110 // snap y to integer points in the middle of the curve to accelerate AAA path filling 111 SkFixed fSnappedX, fSnappedY; 112 113 bool setQuadratic(const SkPoint pts[3]); 114 bool updateQuadratic(); 115 inline void keepContinuous() { 116 // We use fX as the starting x to ensure the continuouty. 117 // Without it, we may break the sorted edge list. 118 SkASSERT(SkAbs32(fX - SkFixedMul(fY - fSnappedY, fDX) - fSnappedX) < SK_Fixed1); 119 SkASSERT(SkAbs32(fY - fSnappedY) < SK_Fixed1); // This may differ due to smooth jump 120 fSnappedX = fX; 121 fSnappedY = fY; 122 } 123}; 124 125struct SkAnalyticCubicEdge : public SkAnalyticEdge { 126 SkCubicEdge fCEdge; 127 128 SkFixed fSnappedY; // to make sure that y is increasing with smooth jump and snapping 129 130 bool setCubic(const SkPoint pts[4], bool sortY = true); 131 bool updateCubic(bool sortY = true); 132 inline void keepContinuous() { 133 SkASSERT(SkAbs32(fX - SkFixedMul(fDX, fY - SnapY(fCEdge.fCy)) - fCEdge.fCx) < SK_Fixed1); 134 fCEdge.fCx = fX; 135 fSnappedY = fY; 136 } 137}; 138 139struct SkBezier { 140 int fCount; // 2 line, 3 quad, 4 cubic 141 SkPoint fP0; 142 SkPoint fP1; 143 144 // See if left shift, covert to SkFDot6, and round has the same top and bottom y. 145 // If so, the edge will be empty. 146 static inline bool IsEmpty(SkScalar y0, SkScalar y1, int shift = 2) { 147#ifdef SK_RASTERIZE_EVEN_ROUNDING 148 return SkScalarRoundToFDot6(y0, shift) == SkScalarRoundToFDot6(y1, shift); 149#else 150 SkScalar scale = (1 << (shift + 6)); 151 return SkFDot6Round(int(y0 * scale)) == SkFDot6Round(int(y1 * scale)); 152#endif 153 } 154}; 155 156struct SkLine : public SkBezier { 157 bool set(const SkPoint pts[2]){ 158 if (IsEmpty(pts[0].fY, pts[1].fY)) { 159 return false; 160 } 161 fCount = 2; 162 fP0 = pts[0]; 163 fP1 = pts[1]; 164 return true; 165 } 166}; 167 168struct SkQuad : public SkBezier { 169 SkPoint fP2; 170 171 bool set(const SkPoint pts[3]){ 172 if (IsEmpty(pts[0].fY, pts[2].fY)) { 173 return false; 174 } 175 fCount = 3; 176 fP0 = pts[0]; 177 fP1 = pts[1]; 178 fP2 = pts[2]; 179 return true; 180 } 181}; 182 183struct SkCubic : public SkBezier { 184 SkPoint fP2; 185 SkPoint fP3; 186 187 bool set(const SkPoint pts[4]){ 188 // We do not chop at y extrema for cubics so pts[0], pts[1], pts[2], pts[3] may not be 189 // monotonic. Therefore, we have to check the emptiness for all three pairs, instead of just 190 // checking IsEmpty(pts[0].fY, pts[3].fY). 191 if (IsEmpty(pts[0].fY, pts[1].fY) && IsEmpty(pts[1].fY, pts[2].fY) && 192 IsEmpty(pts[2].fY, pts[3].fY)) { 193 return false; 194 } 195 fCount = 4; 196 fP0 = pts[0]; 197 fP1 = pts[1]; 198 fP2 = pts[2]; 199 fP3 = pts[3]; 200 return true; 201 } 202}; 203 204#endif 205