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