1 /* 2 * Copyright 2016 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 #include "SkAnalyticEdge.h" 9 #include "SkAntiRun.h" 10 #include "SkAutoMalloc.h" 11 #include "SkBlitter.h" 12 #include "SkCoverageDelta.h" 13 #include "SkEdge.h" 14 #include "SkEdgeBuilder.h" 15 #include "SkGeometry.h" 16 #include "SkMask.h" 17 #include "SkPath.h" 18 #include "SkQuadClipper.h" 19 #include "SkRasterClip.h" 20 #include "SkRegion.h" 21 #include "SkScan.h" 22 #include "SkScanPriv.h" 23 #include "SkTSort.h" 24 #include "SkTemplates.h" 25 #include "SkUTF.h" 26 27 #if defined(SK_DISABLE_DAA) 28 void SkScan::DAAFillPath(const SkPath& path, SkBlitter* blitter, const SkIRect& ir, 29 const SkIRect& clipBounds, bool forceRLE, SkDAARecord* record) { 30 SkDEBUGFAIL("DAA Disabled"); 31 return; 32 } 33 #else 34 /////////////////////////////////////////////////////////////////////////////// 35 36 /* 37 38 DAA stands for Delta-based Anti-Aliasing. 39 40 This is an improved version of our analytic AA algorithm (in SkScan_AAAPath.cpp) 41 which first scan convert paths into coverage deltas (this step can happen out of order, 42 and we don't seem to be needed to worry about the intersection, clamping, etc.), 43 and then use a single blitter run to convert all those deltas into the final alphas. 44 45 Before we go to the final blitter run, we'll use SkFixed for all delta values so we 46 don't ever have to worry about under/overflow. 47 48 */ 49 50 /////////////////////////////////////////////////////////////////////////////// 51 52 // The following helper functions are the same as those from SkScan_AAAPath.cpp 53 // except that we use SkFixed everywhere instead of SkAlpha. 54 55 static inline SkFixed SkFixedMul_lowprec(SkFixed a, SkFixed b) { 56 return (a >> 8) * (b >> 8); 57 } 58 59 // Return the alpha of a trapezoid whose height is 1 60 static inline SkFixed trapezoidToAlpha(SkFixed l1, SkFixed l2) { 61 SkASSERT(l1 >= 0 && l2 >= 0); 62 return (l1 + l2) >> 1; 63 } 64 65 // The alpha of right-triangle (a, a*b) 66 static inline SkFixed partialTriangleToAlpha(SkFixed a, SkFixed b) { 67 SkASSERT(a <= SK_Fixed1); 68 // SkFixedMul(SkFixedMul(a, a), b) >> 1 69 // return ((((a >> 8) * (a >> 8)) >> 8) * (b >> 8)) >> 1; 70 return (a >> 11) * (a >> 11) * (b >> 11); 71 } 72 73 static inline SkFixed getPartialAlpha(SkFixed alpha, SkFixed partialMultiplier) { 74 // DAA should not be so sensitive to the precision (compared to AAA). 75 return SkFixedMul_lowprec(alpha, partialMultiplier); 76 } 77 78 /////////////////////////////////////////////////////////////////////////////// 79 80 template<bool isPartial, class Deltas> 81 static inline void add_coverage_delta_segment(int y, SkFixed rowHeight, const SkAnalyticEdge* edge, 82 SkFixed nextX, Deltas* deltas) { // rowHeight=fullAlpha 83 SkASSERT(rowHeight <= SK_Fixed1 && rowHeight >= 0); 84 85 // Let's see if multiplying sign is faster than multiplying edge->fWinding. 86 // (Compiler should be able to optimize multiplication with 1/-1?) 87 int sign = edge->fWinding == 1 ? 1 : -1; 88 89 SkFixed l = SkTMin(edge->fX, nextX); 90 SkFixed r = edge->fX + nextX - l; 91 int L = SkFixedFloorToInt(l); 92 int R = SkFixedCeilToInt(r); 93 int len = R - L; 94 95 switch (len) { 96 case 0: { 97 deltas->addDelta(L, y, rowHeight * sign); 98 return; 99 } 100 case 1: { 101 SkFixed fixedR = SkIntToFixed(R); 102 SkFixed alpha = trapezoidToAlpha(fixedR - l, fixedR - r); 103 if (isPartial) { 104 alpha = getPartialAlpha(alpha, rowHeight); 105 } 106 deltas->addDelta(L, y, alpha * sign); 107 deltas->addDelta(L + 1, y, (rowHeight - alpha) * sign); 108 return; 109 } 110 case 2: { 111 SkFixed middle = SkIntToFixed(L + 1); 112 SkFixed x1 = middle - l; 113 SkFixed x2 = r - middle; 114 SkFixed alpha1 = partialTriangleToAlpha(x1, edge->fDY); 115 SkFixed alpha2 = rowHeight - partialTriangleToAlpha(x2, edge->fDY); 116 deltas->addDelta(L, y, alpha1 * sign); 117 deltas->addDelta(L + 1, y, (alpha2 - alpha1) * sign); 118 deltas->addDelta(L + 2, y, (rowHeight - alpha2) * sign); 119 return; 120 } 121 } 122 123 // When len > 2, computations are similar to computeAlphaAboveLine in SkScan_AAAPath.cpp 124 SkFixed dY = edge->fDY; 125 SkFixed fixedL = SkIntToFixed(L); 126 SkFixed fixedR = SkIntToFixed(R); 127 SkFixed first = SK_Fixed1 + fixedL - l; // horizontal edge of the left-most triangle 128 SkFixed last = r - (fixedR - SK_Fixed1); // horizontal edge of the right-most triangle 129 SkFixed firstH = SkFixedMul_lowprec(first, dY); // vertical edge of the left-most triangle 130 131 SkFixed alpha0 = SkFixedMul_lowprec(first, firstH) >> 1; // triangle alpha 132 SkFixed alpha1 = firstH + (dY >> 1); // rectangle plus triangle 133 deltas->addDelta(L, y, alpha0 * sign); 134 deltas->addDelta(L + 1, y, (alpha1 - alpha0) * sign); 135 for(int i = 2; i < len - 1; ++i) { 136 deltas->addDelta(L + i, y, dY * sign); // the increment is always a rect of height = dY 137 } 138 139 SkFixed alphaR2 = alpha1 + dY * (len - 3); // the alpha at R - 2 140 SkFixed lastAlpha = rowHeight - partialTriangleToAlpha(last, dY); // the alpha at R - 1 141 deltas->addDelta(R - 1, y, (lastAlpha - alphaR2) * sign); 142 deltas->addDelta(R, y, (rowHeight - lastAlpha) * sign); 143 } 144 145 class XLessThan { 146 public: 147 bool operator()(const SkBezier* a, const SkBezier* b) { 148 return a->fP0.fX + a->fP1.fX < b->fP0.fX + b->fP1.fX; 149 } 150 }; 151 152 class YLessThan { 153 public: 154 bool operator()(const SkBezier* a, const SkBezier* b) { 155 return a->fP0.fY + a->fP1.fY < b->fP0.fY + b->fP1.fY; 156 } 157 }; 158 159 template<class Deltas> static SK_ALWAYS_INLINE 160 void gen_alpha_deltas(const SkPath& path, const SkIRect& clippedIR, const SkIRect& clipBounds, 161 Deltas& result, SkBlitter* blitter, bool skipRect, bool pathContainedInClip) { 162 // 1. Build edges 163 SkBezierEdgeBuilder builder; 164 // We have to use clipBounds instead of clippedIR to build edges because of "canCullToTheRight": 165 // if the builder finds a right edge past the right clip, it won't build that right edge. 166 int count = builder.buildEdges(path, pathContainedInClip ? nullptr : &clipBounds); 167 168 if (count == 0) { 169 return; 170 } 171 SkBezier** list = builder.bezierList(); 172 173 // 2. Try to find the rect part because blitAntiRect is so much faster than blitCoverageDeltas 174 int rectTop = clippedIR.fBottom; // the rect is initialized to be empty as top = bot 175 int rectBot = clippedIR.fBottom; 176 if (skipRect) { // only find that rect is skipRect == true 177 YLessThan lessThan; // sort edges in YX order 178 SkTQSort(list, list + count - 1, lessThan); 179 for(int i = 0; i < count - 1; ++i) { 180 SkBezier* lb = list[i]; 181 SkBezier* rb = list[i + 1]; 182 183 // fCount == 2 ensures that lb and rb are lines instead of quads or cubics. 184 bool lDX0 = lb->fP0.fX == lb->fP1.fX && lb->fCount == 2; 185 bool rDX0 = rb->fP0.fX == rb->fP1.fX && rb->fCount == 2; 186 if (!lDX0 || !rDX0) { // make sure that the edges are vertical 187 continue; 188 } 189 190 SkAnalyticEdge l, r; 191 if (!l.setLine(lb->fP0, lb->fP1) || !r.setLine(rb->fP0, rb->fP1)) { 192 continue; 193 } 194 195 SkFixed xorUpperY = l.fUpperY ^ r.fUpperY; 196 SkFixed xorLowerY = l.fLowerY ^ r.fLowerY; 197 if ((xorUpperY | xorLowerY) == 0) { // equal upperY and lowerY 198 rectTop = SkFixedCeilToInt(l.fUpperY); 199 rectBot = SkFixedFloorToInt(l.fLowerY); 200 if (rectBot > rectTop) { // if bot == top, the rect is too short for blitAntiRect 201 int L = SkFixedCeilToInt(l.fUpperX); 202 int R = SkFixedFloorToInt(r.fUpperX); 203 if (L <= R) { 204 SkAlpha la = (SkIntToFixed(L) - l.fUpperX) >> 8; 205 SkAlpha ra = (r.fUpperX - SkIntToFixed(R)) >> 8; 206 result.setAntiRect(L - 1, rectTop, R - L, rectBot - rectTop, la, ra); 207 } else { // too thin to use blitAntiRect; reset the rect region to be emtpy 208 rectTop = rectBot = clippedIR.fBottom; 209 } 210 } 211 break; 212 } 213 214 } 215 } 216 217 // 3. Sort edges in x so we may need less sorting for delta based on x. This only helps 218 // SkCoverageDeltaList. And we don't want to sort more than SORT_THRESHOLD edges where 219 // the log(count) factor of the quick sort may become a bottleneck; when there are so 220 // many edges, we're unlikely to make deltas sorted anyway. 221 constexpr int SORT_THRESHOLD = 256; 222 if (std::is_same<Deltas, SkCoverageDeltaList>::value && count < SORT_THRESHOLD) { 223 XLessThan lessThan; 224 SkTQSort(list, list + count - 1, lessThan); 225 } 226 227 // Future todo: parallize and SIMD the following code. 228 // 4. iterate through edges and generate deltas 229 for(int index = 0; index < count; ++index) { 230 SkAnalyticCubicEdge storage; 231 SkASSERT(sizeof(SkAnalyticQuadraticEdge) >= sizeof(SkAnalyticEdge)); 232 SkASSERT(sizeof(SkAnalyticCubicEdge) >= sizeof(SkAnalyticQuadraticEdge)); 233 234 SkBezier* bezier = list[index]; 235 SkAnalyticEdge* currE = &storage; 236 bool edgeSet = false; 237 238 int originalWinding = 1; 239 bool sortY = true; 240 switch (bezier->fCount) { 241 case 2: { 242 edgeSet = currE->setLine(bezier->fP0, bezier->fP1); 243 originalWinding = currE->fWinding; 244 break; 245 } 246 case 3: { 247 SkQuad* quad = static_cast<SkQuad*>(bezier); 248 SkPoint pts[3] = {quad->fP0, quad->fP1, quad->fP2}; 249 edgeSet = static_cast<SkAnalyticQuadraticEdge*>(currE)->setQuadratic(pts); 250 originalWinding = static_cast<SkAnalyticQuadraticEdge*>(currE)->fQEdge.fWinding; 251 break; 252 } 253 case 4: { 254 sortY = false; 255 SkCubic* cubic = static_cast<SkCubic*>(bezier); 256 SkPoint pts[4] = {cubic->fP0, cubic->fP1, cubic->fP2, cubic->fP3}; 257 edgeSet = static_cast<SkAnalyticCubicEdge*>(currE)->setCubic(pts, sortY); 258 originalWinding = static_cast<SkAnalyticCubicEdge*>(currE)->fCEdge.fWinding; 259 break; 260 } 261 } 262 263 if (!edgeSet) { 264 continue; 265 } 266 267 do { 268 currE->fX = currE->fUpperX; 269 270 SkFixed upperFloor = SkFixedFloorToFixed(currE->fUpperY); 271 SkFixed lowerCeil = SkFixedCeilToFixed(currE->fLowerY); 272 int iy = SkFixedFloorToInt(upperFloor); 273 274 if (lowerCeil <= upperFloor + SK_Fixed1) { // only one row is affected by the currE 275 SkFixed rowHeight = currE->fLowerY - currE->fUpperY; 276 SkFixed nextX = currE->fX + SkFixedMul(currE->fDX, rowHeight); 277 if (iy >= clippedIR.fTop && iy < clippedIR.fBottom) { 278 add_coverage_delta_segment<true>(iy, rowHeight, currE, nextX, &result); 279 } 280 continue; 281 } 282 283 // check first row 284 SkFixed rowHeight = upperFloor + SK_Fixed1 - currE->fUpperY; 285 SkFixed nextX; 286 if (rowHeight != SK_Fixed1) { // it's a partial row 287 nextX = currE->fX + SkFixedMul(currE->fDX, rowHeight); 288 add_coverage_delta_segment<true>(iy, rowHeight, currE, nextX, &result); 289 } else { // it's a full row so we can leave it to the while loop 290 iy--; // compensate the iy++ in the while loop 291 nextX = currE->fX; 292 } 293 294 while (true) { // process the full rows in the middle 295 iy++; 296 SkFixed y = SkIntToFixed(iy); 297 currE->fX = nextX; 298 nextX += currE->fDX; 299 300 if (y + SK_Fixed1 > currE->fLowerY) { 301 break; // no full rows left, break 302 } 303 304 // Check whether we're in the rect part that will be covered by blitAntiRect 305 if (iy >= rectTop && iy < rectBot) { 306 SkASSERT(currE->fDX == 0); // If yes, we must be on an edge with fDX = 0. 307 iy = rectBot - 1; // Skip the rect part by advancing iy to the bottom. 308 continue; 309 } 310 311 // Add current edge's coverage deltas on this full row 312 add_coverage_delta_segment<false>(iy, SK_Fixed1, currE, nextX, &result); 313 } 314 315 // last partial row 316 if (SkIntToFixed(iy) < currE->fLowerY && 317 iy >= clippedIR.fTop && iy < clippedIR.fBottom) { 318 rowHeight = currE->fLowerY - SkIntToFixed(iy); 319 nextX = currE->fX + SkFixedMul(currE->fDX, rowHeight); 320 add_coverage_delta_segment<true>(iy, rowHeight, currE, nextX, &result); 321 } 322 // Intended assignment to fWinding to restore the maybe-negated winding (during updateLine) 323 } while ((currE->fWinding = originalWinding) && currE->update(currE->fLowerY, sortY)); 324 } 325 } 326 327 void SkScan::DAAFillPath(const SkPath& path, SkBlitter* blitter, const SkIRect& ir, 328 const SkIRect& clipBounds, bool forceRLE, SkDAARecord* record) { 329 bool containedInClip = clipBounds.contains(ir); 330 bool isEvenOdd = path.getFillType() & 1; 331 bool isConvex = path.isConvex(); 332 bool isInverse = path.isInverseFillType(); 333 bool skipRect = isConvex && !isInverse; 334 bool isInitOnce = record && record->fType == SkDAARecord::Type::kToBeComputed; 335 336 SkIRect clippedIR = ir; 337 clippedIR.intersect(clipBounds); 338 339 // The overhead of even constructing SkCoverageDeltaList/Mask is too big. 340 // So TryBlitFatAntiRect and return if it's successful. 341 if (!isInverse && TryBlitFatAntiRect(blitter, path, clipBounds)) { 342 SkDAARecord::SetEmpty(record); 343 return; 344 } 345 346 #ifdef SK_BUILD_FOR_GOOGLE3 347 constexpr int STACK_SIZE = 12 << 10; // 12K stack size alloc; Google3 has 16K limit. 348 #else 349 constexpr int STACK_SIZE = 64 << 10; // 64k stack size to avoid heap allocation 350 #endif 351 SkSTArenaAlloc<STACK_SIZE> stackAlloc; // avoid heap allocation with SkSTArenaAlloc 352 353 // Set alloc to record's alloc if and only if we're in the init-once phase. We have to do that 354 // during init phase because the mask or list needs to live longer. We can't do that during blit 355 // phase because the same record could be accessed by multiple threads simultaneously. 356 SkArenaAlloc* alloc = isInitOnce ? record->fAlloc : &stackAlloc; 357 358 if (record == nullptr) { 359 record = alloc->make<SkDAARecord>(alloc); 360 } 361 362 // Only blitter->blitXXX needs to be done in order in the threaded backend. Everything else can 363 // be done out of order in the init-once phase. We do that by calling DAAFillPath twice: first 364 // with a null blitter, and then second with the real blitter and the SkMask/SkCoverageDeltaList 365 // generated in the first step. 366 if (record->fType == SkDAARecord::Type::kToBeComputed) { 367 if (!forceRLE && !isInverse && SkCoverageDeltaMask::Suitable(clippedIR)) { 368 record->fType = SkDAARecord::Type::kMask; 369 SkCoverageDeltaMask deltaMask(alloc, clippedIR); 370 gen_alpha_deltas(path, clippedIR, clipBounds, deltaMask, blitter, skipRect, 371 containedInClip); 372 deltaMask.convertCoverageToAlpha(isEvenOdd, isInverse, isConvex); 373 record->fMask = deltaMask.prepareSkMask(); 374 } else { 375 record->fType = SkDAARecord::Type::kList; 376 SkCoverageDeltaList* deltaList = alloc->make<SkCoverageDeltaList>( 377 alloc, clippedIR, forceRLE); 378 gen_alpha_deltas(path, clippedIR, clipBounds, *deltaList, blitter, skipRect, 379 containedInClip); 380 record->fList = deltaList; 381 } 382 } 383 384 if (!isInitOnce) { 385 SkASSERT(record->fType != SkDAARecord::Type::kToBeComputed); 386 if (record->fType == SkDAARecord::Type::kMask) { 387 blitter->blitMask(record->fMask, clippedIR); 388 } else { 389 blitter->blitCoverageDeltas(record->fList, clipBounds, isEvenOdd, isInverse, isConvex); 390 } 391 } 392 } 393 #endif //defined(SK_DISABLE_DAA) 394
