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 SkASSERT(y0 <= y1); 24 25 SkFDot6 dx = SkFixedToFDot6(x1 - x0); 26 SkFDot6 dy = SkFixedToFDot6(y1 - y0); 27 28 // are we a zero-height line? 29 if (dy == 0) { 30 return false; 31 } 32 33 SkASSERT(slope < SK_MaxS32); 34 35 SkFDot6 absSlope = SkAbs32(SkFixedToFDot6(slope)); 36 fX = x0; 37 fDX = slope; 38 fUpperX = x0; 39 fY = y0; 40 fUpperY = y0; 41 fLowerY = y1; 42 fDY = (dx == 0 || slope == 0) 43 ? SK_MaxS32 44 : absSlope < kInverseTableSize 45 ? QuickFDot6Inverse::Lookup(absSlope) 46 : SkAbs32(QuickSkFDot6Div(dy, dx)); 47 48 return true; 49 } 50 51 bool SkAnalyticQuadraticEdge::setQuadratic(const SkPoint pts[3]) { 52 fRiteE = nullptr; 53 54 if (!fQEdge.setQuadraticWithoutUpdate(pts, kDefaultAccuracy)) { 55 return false; 56 } 57 fQEdge.fQx >>= kDefaultAccuracy; 58 fQEdge.fQy >>= kDefaultAccuracy; 59 fQEdge.fQDx >>= kDefaultAccuracy; 60 fQEdge.fQDy >>= kDefaultAccuracy; 61 fQEdge.fQDDx >>= kDefaultAccuracy; 62 fQEdge.fQDDy >>= kDefaultAccuracy; 63 fQEdge.fQLastX >>= kDefaultAccuracy; 64 fQEdge.fQLastY >>= kDefaultAccuracy; 65 fQEdge.fQy = SnapY(fQEdge.fQy); 66 fQEdge.fQLastY = SnapY(fQEdge.fQLastY); 67 68 fWinding = fQEdge.fWinding; 69 fCurveCount = fQEdge.fCurveCount; 70 fCurveShift = fQEdge.fCurveShift; 71 72 fSnappedX = fQEdge.fQx; 73 fSnappedY = fQEdge.fQy; 74 75 return this->updateQuadratic(); 76 } 77 78 bool SkAnalyticQuadraticEdge::updateQuadratic() { 79 int success = 0; // initialize to fail! 80 int count = fCurveCount; 81 SkFixed oldx = fQEdge.fQx; 82 SkFixed oldy = fQEdge.fQy; 83 SkFixed dx = fQEdge.fQDx; 84 SkFixed dy = fQEdge.fQDy; 85 SkFixed newx, newy, newSnappedX, newSnappedY; 86 int shift = fCurveShift; 87 88 SkASSERT(count > 0); 89 90 do { 91 SkFixed slope; 92 if (--count > 0) 93 { 94 newx = oldx + (dx >> shift); 95 newy = oldy + (dy >> shift); 96 if (SkAbs32(dy >> shift) >= SK_Fixed1 * 2) { // only snap when dy is large enough 97 SkFDot6 diffY = SkFixedToFDot6(newy - fSnappedY); 98 slope = diffY ? QuickSkFDot6Div(SkFixedToFDot6(newx - fSnappedX), diffY) 99 : SK_MaxS32; 100 newSnappedY = SkTMin<SkFixed>(fQEdge.fQLastY, SkFixedRoundToFixed(newy)); 101 newSnappedX = newx - SkFixedMul(slope, newy - newSnappedY); 102 } else { 103 newSnappedY = SkTMin(fQEdge.fQLastY, SnapY(newy)); 104 newSnappedX = newx; 105 SkFDot6 diffY = SkFixedToFDot6(newSnappedY - fSnappedY); 106 slope = diffY ? QuickSkFDot6Div(SkFixedToFDot6(newx - fSnappedX), diffY) 107 : SK_MaxS32; 108 } 109 dx += fQEdge.fQDDx; 110 dy += fQEdge.fQDDy; 111 } 112 else // last segment 113 { 114 newx = fQEdge.fQLastX; 115 newy = fQEdge.fQLastY; 116 newSnappedY = newy; 117 newSnappedX = newx; 118 SkFDot6 diffY = (newy - fSnappedY) >> 10; 119 slope = diffY ? QuickSkFDot6Div((newx - fSnappedX) >> 10, diffY) : SK_MaxS32; 120 } 121 if (slope < SK_MaxS32) { 122 success = this->updateLine(fSnappedX, fSnappedY, newSnappedX, newSnappedY, slope); 123 } 124 oldx = newx; 125 oldy = newy; 126 } while (count > 0 && !success); 127 128 SkASSERT(newSnappedY <= fQEdge.fQLastY); 129 130 fQEdge.fQx = newx; 131 fQEdge.fQy = newy; 132 fQEdge.fQDx = dx; 133 fQEdge.fQDy = dy; 134 fSnappedX = newSnappedX; 135 fSnappedY = newSnappedY; 136 fCurveCount = SkToS8(count); 137 return success; 138 } 139 140 bool SkAnalyticCubicEdge::setCubic(const SkPoint pts[4]) { 141 fRiteE = nullptr; 142 143 if (!fCEdge.setCubicWithoutUpdate(pts, kDefaultAccuracy)) { 144 return false; 145 } 146 147 fCEdge.fCx >>= kDefaultAccuracy; 148 fCEdge.fCy >>= kDefaultAccuracy; 149 fCEdge.fCDx >>= kDefaultAccuracy; 150 fCEdge.fCDy >>= kDefaultAccuracy; 151 fCEdge.fCDDx >>= kDefaultAccuracy; 152 fCEdge.fCDDy >>= kDefaultAccuracy; 153 fCEdge.fCDDDx >>= kDefaultAccuracy; 154 fCEdge.fCDDDy >>= kDefaultAccuracy; 155 fCEdge.fCLastX >>= kDefaultAccuracy; 156 fCEdge.fCLastY >>= kDefaultAccuracy; 157 fCEdge.fCy = SnapY(fCEdge.fCy); 158 fCEdge.fCLastY = SnapY(fCEdge.fCLastY); 159 160 fWinding = fCEdge.fWinding; 161 fCurveCount = fCEdge.fCurveCount; 162 fCurveShift = fCEdge.fCurveShift; 163 fCubicDShift = fCEdge.fCubicDShift; 164 165 fSnappedY = fCEdge.fCy; 166 167 return this->updateCubic(); 168 } 169 170 bool SkAnalyticCubicEdge::updateCubic() { 171 int success; 172 int count = fCurveCount; 173 SkFixed oldx = fCEdge.fCx; 174 SkFixed oldy = fCEdge.fCy; 175 SkFixed newx, newy; 176 const int ddshift = fCurveShift; 177 const int dshift = fCubicDShift; 178 179 SkASSERT(count < 0); 180 181 do { 182 if (++count < 0) { 183 newx = oldx + (fCEdge.fCDx >> dshift); 184 fCEdge.fCDx += fCEdge.fCDDx >> ddshift; 185 fCEdge.fCDDx += fCEdge.fCDDDx; 186 187 newy = oldy + (fCEdge.fCDy >> dshift); 188 fCEdge.fCDy += fCEdge.fCDDy >> ddshift; 189 fCEdge.fCDDy += fCEdge.fCDDDy; 190 } 191 else { // last segment 192 newx = fCEdge.fCLastX; 193 newy = fCEdge.fCLastY; 194 } 195 196 // we want to say SkASSERT(oldy <= newy), but our finite fixedpoint 197 // doesn't always achieve that, so we have to explicitly pin it here. 198 if (newy < oldy) { 199 newy = oldy; 200 } 201 202 SkFixed newSnappedY = SnapY(newy); 203 // we want to SkASSERT(snappedNewY <= fCEdge.fCLastY), but our finite fixedpoint 204 // doesn't always achieve that, so we have to explicitly pin it here. 205 if (fCEdge.fCLastY < newSnappedY) { 206 newSnappedY = fCEdge.fCLastY; 207 count = 0; 208 } 209 210 SkFixed slope = SkFixedToFDot6(newSnappedY - fSnappedY) == 0 211 ? SK_MaxS32 212 : SkFDot6Div(SkFixedToFDot6(newx - oldx), 213 SkFixedToFDot6(newSnappedY - fSnappedY)); 214 215 success = this->updateLine(oldx, fSnappedY, newx, newSnappedY, slope); 216 217 oldx = newx; 218 oldy = newy; 219 fSnappedY = newSnappedY; 220 } while (count < 0 && !success); 221 222 fCEdge.fCx = newx; 223 fCEdge.fCy = newy; 224 fCurveCount = SkToS8(count); 225 return success; 226 } 227
