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 #include "SkAnalyticEdge.h" 10 #include "SkFDot6.h" 11 #include "SkMathPriv.h" 12 13 // This will become a bottleneck for small ovals rendering if we call SkFixedDiv twice here. 14 // Therefore, we'll let the outter function compute the slope once and send in the value. 15 // Moreover, we'll compute fDY by quickly lookup the inverse table (if possible). 16 bool SkAnalyticEdge::updateLine(SkFixed x0, SkFixed y0, SkFixed x1, SkFixed y1, SkFixed slope) { 17 // Since we send in the slope, we can no longer snap y inside this function. 18 // If we don't send in the slope, or we do some more sophisticated snapping, this function 19 // could be a performance bottleneck. 20 SkASSERT(fWinding == 1 || fWinding == -1); 21 SkASSERT(fCurveCount != 0); 22 23 // We don't chop at y extrema for cubics so the y is not guaranteed to be increasing for them. 24 // In that case, we have to swap x/y and negate the winding. 25 if (y0 > y1) { 26 SkTSwap(x0, x1); 27 SkTSwap(y0, y1); 28 fWinding = -fWinding; 29 } 30 31 SkASSERT(y0 <= y1); 32 33 SkFDot6 dx = SkFixedToFDot6(x1 - x0); 34 SkFDot6 dy = SkFixedToFDot6(y1 - y0); 35 36 // are we a zero-height line? 37 if (dy == 0) { 38 return false; 39 } 40 41 SkASSERT(slope < SK_MaxS32); 42 43 SkFDot6 absSlope = SkAbs32(SkFixedToFDot6(slope)); 44 fX = x0; 45 fDX = slope; 46 fUpperX = x0; 47 fY = y0; 48 fUpperY = y0; 49 fLowerY = y1; 50 fDY = (dx == 0 || slope == 0) 51 ? SK_MaxS32 52 : absSlope < kInverseTableSize 53 ? QuickFDot6Inverse::Lookup(absSlope) 54 : SkAbs32(QuickSkFDot6Div(dy, dx)); 55 56 return true; 57 } 58 59 bool SkAnalyticEdge::update(SkFixed last_y, bool sortY) { 60 SkASSERT(last_y >= fLowerY); // we shouldn't update edge if last_y < fLowerY 61 if (fCurveCount < 0) { 62 return static_cast<SkAnalyticCubicEdge*>(this)->updateCubic(sortY); 63 } else if (fCurveCount > 0) { 64 return static_cast<SkAnalyticQuadraticEdge*>(this)->updateQuadratic(); 65 } 66 return false; 67 } 68 69 bool SkAnalyticQuadraticEdge::setQuadratic(const SkPoint pts[3]) { 70 fRiteE = nullptr; 71 72 if (!fQEdge.setQuadraticWithoutUpdate(pts, kDefaultAccuracy)) { 73 return false; 74 } 75 fQEdge.fQx >>= kDefaultAccuracy; 76 fQEdge.fQy >>= kDefaultAccuracy; 77 fQEdge.fQDx >>= kDefaultAccuracy; 78 fQEdge.fQDy >>= kDefaultAccuracy; 79 fQEdge.fQDDx >>= kDefaultAccuracy; 80 fQEdge.fQDDy >>= kDefaultAccuracy; 81 fQEdge.fQLastX >>= kDefaultAccuracy; 82 fQEdge.fQLastY >>= kDefaultAccuracy; 83 fQEdge.fQy = SnapY(fQEdge.fQy); 84 fQEdge.fQLastY = SnapY(fQEdge.fQLastY); 85 86 fWinding = fQEdge.fWinding; 87 fCurveCount = fQEdge.fCurveCount; 88 fCurveShift = fQEdge.fCurveShift; 89 90 fSnappedX = fQEdge.fQx; 91 fSnappedY = fQEdge.fQy; 92 93 return this->updateQuadratic(); 94 } 95 96 bool SkAnalyticQuadraticEdge::updateQuadratic() { 97 int success = 0; // initialize to fail! 98 int count = fCurveCount; 99 SkFixed oldx = fQEdge.fQx; 100 SkFixed oldy = fQEdge.fQy; 101 SkFixed dx = fQEdge.fQDx; 102 SkFixed dy = fQEdge.fQDy; 103 SkFixed newx, newy, newSnappedX, newSnappedY; 104 int shift = fCurveShift; 105 106 SkASSERT(count > 0); 107 108 do { 109 SkFixed slope; 110 if (--count > 0) 111 { 112 newx = oldx + (dx >> shift); 113 newy = oldy + (dy >> shift); 114 if (SkAbs32(dy >> shift) >= SK_Fixed1 * 2) { // only snap when dy is large enough 115 SkFDot6 diffY = SkFixedToFDot6(newy - fSnappedY); 116 slope = diffY ? QuickSkFDot6Div(SkFixedToFDot6(newx - fSnappedX), diffY) 117 : SK_MaxS32; 118 newSnappedY = SkTMin<SkFixed>(fQEdge.fQLastY, SkFixedRoundToFixed(newy)); 119 newSnappedX = newx - SkFixedMul(slope, newy - newSnappedY); 120 } else { 121 newSnappedY = SkTMin(fQEdge.fQLastY, SnapY(newy)); 122 newSnappedX = newx; 123 SkFDot6 diffY = SkFixedToFDot6(newSnappedY - fSnappedY); 124 slope = diffY ? QuickSkFDot6Div(SkFixedToFDot6(newx - fSnappedX), diffY) 125 : SK_MaxS32; 126 } 127 dx += fQEdge.fQDDx; 128 dy += fQEdge.fQDDy; 129 } 130 else // last segment 131 { 132 newx = fQEdge.fQLastX; 133 newy = fQEdge.fQLastY; 134 newSnappedY = newy; 135 newSnappedX = newx; 136 SkFDot6 diffY = (newy - fSnappedY) >> 10; 137 slope = diffY ? QuickSkFDot6Div((newx - fSnappedX) >> 10, diffY) : SK_MaxS32; 138 } 139 if (slope < SK_MaxS32) { 140 success = this->updateLine(fSnappedX, fSnappedY, newSnappedX, newSnappedY, slope); 141 } 142 oldx = newx; 143 oldy = newy; 144 } while (count > 0 && !success); 145 146 SkASSERT(newSnappedY <= fQEdge.fQLastY); 147 148 fQEdge.fQx = newx; 149 fQEdge.fQy = newy; 150 fQEdge.fQDx = dx; 151 fQEdge.fQDy = dy; 152 fSnappedX = newSnappedX; 153 fSnappedY = newSnappedY; 154 fCurveCount = SkToS8(count); 155 return success; 156 } 157 158 bool SkAnalyticCubicEdge::setCubic(const SkPoint pts[4], bool sortY) { 159 fRiteE = nullptr; 160 161 if (!fCEdge.setCubicWithoutUpdate(pts, kDefaultAccuracy, sortY)) { 162 return false; 163 } 164 165 fCEdge.fCx >>= kDefaultAccuracy; 166 fCEdge.fCy >>= kDefaultAccuracy; 167 fCEdge.fCDx >>= kDefaultAccuracy; 168 fCEdge.fCDy >>= kDefaultAccuracy; 169 fCEdge.fCDDx >>= kDefaultAccuracy; 170 fCEdge.fCDDy >>= kDefaultAccuracy; 171 fCEdge.fCDDDx >>= kDefaultAccuracy; 172 fCEdge.fCDDDy >>= kDefaultAccuracy; 173 fCEdge.fCLastX >>= kDefaultAccuracy; 174 fCEdge.fCLastY >>= kDefaultAccuracy; 175 fCEdge.fCy = SnapY(fCEdge.fCy); 176 fCEdge.fCLastY = SnapY(fCEdge.fCLastY); 177 178 fWinding = fCEdge.fWinding; 179 fCurveCount = fCEdge.fCurveCount; 180 fCurveShift = fCEdge.fCurveShift; 181 fCubicDShift = fCEdge.fCubicDShift; 182 183 fSnappedY = fCEdge.fCy; 184 185 return this->updateCubic(sortY); 186 } 187 188 bool SkAnalyticCubicEdge::updateCubic(bool sortY) { 189 int success; 190 int count = fCurveCount; 191 SkFixed oldx = fCEdge.fCx; 192 SkFixed oldy = fCEdge.fCy; 193 SkFixed newx, newy; 194 const int ddshift = fCurveShift; 195 const int dshift = fCubicDShift; 196 197 SkASSERT(count < 0); 198 199 do { 200 if (++count < 0) { 201 newx = oldx + (fCEdge.fCDx >> dshift); 202 fCEdge.fCDx += fCEdge.fCDDx >> ddshift; 203 fCEdge.fCDDx += fCEdge.fCDDDx; 204 205 newy = oldy + (fCEdge.fCDy >> dshift); 206 fCEdge.fCDy += fCEdge.fCDDy >> ddshift; 207 fCEdge.fCDDy += fCEdge.fCDDDy; 208 } 209 else { // last segment 210 newx = fCEdge.fCLastX; 211 newy = fCEdge.fCLastY; 212 } 213 214 // we want to say SkASSERT(oldy <= newy), but our finite fixedpoint 215 // doesn't always achieve that, so we have to explicitly pin it here. 216 if (sortY && newy < oldy) { 217 newy = oldy; 218 } 219 220 SkFixed newSnappedY = SnapY(newy); 221 // we want to SkASSERT(snappedNewY <= fCEdge.fCLastY), but our finite fixedpoint 222 // doesn't always achieve that, so we have to explicitly pin it here. 223 if (sortY && fCEdge.fCLastY < newSnappedY) { 224 newSnappedY = fCEdge.fCLastY; 225 count = 0; 226 } 227 228 SkFixed slope = SkFixedToFDot6(newSnappedY - fSnappedY) == 0 229 ? SK_MaxS32 230 : SkFDot6Div(SkFixedToFDot6(newx - oldx), 231 SkFixedToFDot6(newSnappedY - fSnappedY)); 232 233 success = this->updateLine(oldx, fSnappedY, newx, newSnappedY, slope); 234 235 oldx = newx; 236 oldy = newy; 237 fSnappedY = newSnappedY; 238 } while (count < 0 && !success); 239 240 fCEdge.fCx = newx; 241 fCEdge.fCy = newy; 242 fCurveCount = SkToS8(count); 243 return success; 244 } 245
