SkScan_AntiPath.cpp 26 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838
  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. #include "src/core/SkScanPriv.h"
  8. #include "include/core/SkMatrix.h"
  9. #include "include/core/SkPath.h"
  10. #include "include/core/SkRegion.h"
  11. #include "include/private/SkTo.h"
  12. #include "src/core/SkAntiRun.h"
  13. #include "src/core/SkBlitter.h"
  14. #include "src/core/SkPathPriv.h"
  15. #define SHIFT SK_SUPERSAMPLE_SHIFT
  16. #define SCALE (1 << SHIFT)
  17. #define MASK (SCALE - 1)
  18. /** @file
  19. We have two techniques for capturing the output of the supersampler:
  20. - SUPERMASK, which records a large mask-bitmap
  21. this is often faster for small, complex objects
  22. - RLE, which records a rle-encoded scanline
  23. this is often faster for large objects with big spans
  24. These blitters use two coordinate systems:
  25. - destination coordinates, scale equal to the output - often
  26. abbreviated with 'i' or 'I' in variable names
  27. - supersampled coordinates, scale equal to the output * SCALE
  28. */
  29. //#define FORCE_SUPERMASK
  30. //#define FORCE_RLE
  31. ///////////////////////////////////////////////////////////////////////////////
  32. /// Base class for a single-pass supersampled blitter.
  33. class BaseSuperBlitter : public SkBlitter {
  34. public:
  35. BaseSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir,
  36. const SkIRect& clipBounds, bool isInverse);
  37. /// Must be explicitly defined on subclasses.
  38. virtual void blitAntiH(int x, int y, const SkAlpha antialias[],
  39. const int16_t runs[]) override {
  40. SkDEBUGFAIL("How did I get here?");
  41. }
  42. /// May not be called on BaseSuperBlitter because it blits out of order.
  43. void blitV(int x, int y, int height, SkAlpha alpha) override {
  44. SkDEBUGFAIL("How did I get here?");
  45. }
  46. protected:
  47. SkBlitter* fRealBlitter;
  48. /// Current y coordinate, in destination coordinates.
  49. int fCurrIY;
  50. /// Widest row of region to be blitted, in destination coordinates.
  51. int fWidth;
  52. /// Leftmost x coordinate in any row, in destination coordinates.
  53. int fLeft;
  54. /// Leftmost x coordinate in any row, in supersampled coordinates.
  55. int fSuperLeft;
  56. SkDEBUGCODE(int fCurrX;)
  57. /// Current y coordinate in supersampled coordinates.
  58. int fCurrY;
  59. /// Initial y coordinate (top of bounds).
  60. int fTop;
  61. SkIRect fSectBounds;
  62. };
  63. BaseSuperBlitter::BaseSuperBlitter(SkBlitter* realBlit, const SkIRect& ir,
  64. const SkIRect& clipBounds, bool isInverse) {
  65. fRealBlitter = realBlit;
  66. SkIRect sectBounds;
  67. if (isInverse) {
  68. // We use the clip bounds instead of the ir, since we may be asked to
  69. //draw outside of the rect when we're a inverse filltype
  70. sectBounds = clipBounds;
  71. } else {
  72. if (!sectBounds.intersect(ir, clipBounds)) {
  73. sectBounds.setEmpty();
  74. }
  75. }
  76. const int left = sectBounds.left();
  77. const int right = sectBounds.right();
  78. fLeft = left;
  79. fSuperLeft = SkLeftShift(left, SHIFT);
  80. fWidth = right - left;
  81. fTop = sectBounds.top();
  82. fCurrIY = fTop - 1;
  83. fCurrY = SkLeftShift(fTop, SHIFT) - 1;
  84. SkDEBUGCODE(fCurrX = -1;)
  85. }
  86. /// Run-length-encoded supersampling antialiased blitter.
  87. class SuperBlitter : public BaseSuperBlitter {
  88. public:
  89. SuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, const SkIRect& clipBounds,
  90. bool isInverse);
  91. ~SuperBlitter() override {
  92. this->flush();
  93. }
  94. /// Once fRuns contains a complete supersampled row, flush() blits
  95. /// it out through the wrapped blitter.
  96. void flush();
  97. /// Blits a row of pixels, with location and width specified
  98. /// in supersampled coordinates.
  99. void blitH(int x, int y, int width) override;
  100. /// Blits a rectangle of pixels, with location and size specified
  101. /// in supersampled coordinates.
  102. void blitRect(int x, int y, int width, int height) override;
  103. private:
  104. // The next three variables are used to track a circular buffer that
  105. // contains the values used in SkAlphaRuns. These variables should only
  106. // ever be updated in advanceRuns(), and fRuns should always point to
  107. // a valid SkAlphaRuns...
  108. int fRunsToBuffer;
  109. void* fRunsBuffer;
  110. int fCurrentRun;
  111. SkAlphaRuns fRuns;
  112. // extra one to store the zero at the end
  113. int getRunsSz() const { return (fWidth + 1 + (fWidth + 2)/2) * sizeof(int16_t); }
  114. // This function updates the fRuns variable to point to the next buffer space
  115. // with adequate storage for a SkAlphaRuns. It mostly just advances fCurrentRun
  116. // and resets fRuns to point to an empty scanline.
  117. void advanceRuns() {
  118. const size_t kRunsSz = this->getRunsSz();
  119. fCurrentRun = (fCurrentRun + 1) % fRunsToBuffer;
  120. fRuns.fRuns = reinterpret_cast<int16_t*>(
  121. reinterpret_cast<uint8_t*>(fRunsBuffer) + fCurrentRun * kRunsSz);
  122. fRuns.fAlpha = reinterpret_cast<SkAlpha*>(fRuns.fRuns + fWidth + 1);
  123. fRuns.reset(fWidth);
  124. }
  125. int fOffsetX;
  126. };
  127. SuperBlitter::SuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, const SkIRect& clipBounds,
  128. bool isInverse)
  129. : BaseSuperBlitter(realBlitter, ir, clipBounds, isInverse)
  130. {
  131. fRunsToBuffer = realBlitter->requestRowsPreserved();
  132. fRunsBuffer = realBlitter->allocBlitMemory(fRunsToBuffer * this->getRunsSz());
  133. fCurrentRun = -1;
  134. this->advanceRuns();
  135. fOffsetX = 0;
  136. }
  137. void SuperBlitter::flush() {
  138. if (fCurrIY >= fTop) {
  139. SkASSERT(fCurrentRun < fRunsToBuffer);
  140. if (!fRuns.empty()) {
  141. // SkDEBUGCODE(fRuns.dump();)
  142. fRealBlitter->blitAntiH(fLeft, fCurrIY, fRuns.fAlpha, fRuns.fRuns);
  143. this->advanceRuns();
  144. fOffsetX = 0;
  145. }
  146. fCurrIY = fTop - 1;
  147. SkDEBUGCODE(fCurrX = -1;)
  148. }
  149. }
  150. /** coverage_to_partial_alpha() is being used by SkAlphaRuns, which
  151. *accumulates* SCALE pixels worth of "alpha" in [0,(256/SCALE)]
  152. to produce a final value in [0, 255] and handles clamping 256->255
  153. itself, with the same (alpha - (alpha >> 8)) correction as
  154. coverage_to_exact_alpha().
  155. */
  156. static inline int coverage_to_partial_alpha(int aa) {
  157. aa <<= 8 - 2*SHIFT;
  158. return aa;
  159. }
  160. /** coverage_to_exact_alpha() is being used by our blitter, which wants
  161. a final value in [0, 255].
  162. */
  163. static inline int coverage_to_exact_alpha(int aa) {
  164. int alpha = (256 >> SHIFT) * aa;
  165. // clamp 256->255
  166. return alpha - (alpha >> 8);
  167. }
  168. void SuperBlitter::blitH(int x, int y, int width) {
  169. SkASSERT(width > 0);
  170. int iy = y >> SHIFT;
  171. SkASSERT(iy >= fCurrIY);
  172. x -= fSuperLeft;
  173. // hack, until I figure out why my cubics (I think) go beyond the bounds
  174. if (x < 0) {
  175. width += x;
  176. x = 0;
  177. }
  178. #ifdef SK_DEBUG
  179. SkASSERT(y != fCurrY || x >= fCurrX);
  180. #endif
  181. SkASSERT(y >= fCurrY);
  182. if (fCurrY != y) {
  183. fOffsetX = 0;
  184. fCurrY = y;
  185. }
  186. if (iy != fCurrIY) { // new scanline
  187. this->flush();
  188. fCurrIY = iy;
  189. }
  190. int start = x;
  191. int stop = x + width;
  192. SkASSERT(start >= 0 && stop > start);
  193. // integer-pixel-aligned ends of blit, rounded out
  194. int fb = start & MASK;
  195. int fe = stop & MASK;
  196. int n = (stop >> SHIFT) - (start >> SHIFT) - 1;
  197. if (n < 0) {
  198. fb = fe - fb;
  199. n = 0;
  200. fe = 0;
  201. } else {
  202. if (fb == 0) {
  203. n += 1;
  204. } else {
  205. fb = SCALE - fb;
  206. }
  207. }
  208. fOffsetX = fRuns.add(x >> SHIFT, coverage_to_partial_alpha(fb),
  209. n, coverage_to_partial_alpha(fe),
  210. (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT),
  211. fOffsetX);
  212. #ifdef SK_DEBUG
  213. fRuns.assertValid(y & MASK, (1 << (8 - SHIFT)));
  214. fCurrX = x + width;
  215. #endif
  216. }
  217. #if 0 // UNUSED
  218. static void set_left_rite_runs(SkAlphaRuns& runs, int ileft, U8CPU leftA,
  219. int n, U8CPU riteA) {
  220. SkASSERT(leftA <= 0xFF);
  221. SkASSERT(riteA <= 0xFF);
  222. int16_t* run = runs.fRuns;
  223. uint8_t* aa = runs.fAlpha;
  224. if (ileft > 0) {
  225. run[0] = ileft;
  226. aa[0] = 0;
  227. run += ileft;
  228. aa += ileft;
  229. }
  230. SkASSERT(leftA < 0xFF);
  231. if (leftA > 0) {
  232. *run++ = 1;
  233. *aa++ = leftA;
  234. }
  235. if (n > 0) {
  236. run[0] = n;
  237. aa[0] = 0xFF;
  238. run += n;
  239. aa += n;
  240. }
  241. SkASSERT(riteA < 0xFF);
  242. if (riteA > 0) {
  243. *run++ = 1;
  244. *aa++ = riteA;
  245. }
  246. run[0] = 0;
  247. }
  248. #endif
  249. void SuperBlitter::blitRect(int x, int y, int width, int height) {
  250. SkASSERT(width > 0);
  251. SkASSERT(height > 0);
  252. // blit leading rows
  253. while ((y & MASK)) {
  254. this->blitH(x, y++, width);
  255. if (--height <= 0) {
  256. return;
  257. }
  258. }
  259. SkASSERT(height > 0);
  260. // Since this is a rect, instead of blitting supersampled rows one at a
  261. // time and then resolving to the destination canvas, we can blit
  262. // directly to the destintion canvas one row per SCALE supersampled rows.
  263. int start_y = y >> SHIFT;
  264. int stop_y = (y + height) >> SHIFT;
  265. int count = stop_y - start_y;
  266. if (count > 0) {
  267. y += count << SHIFT;
  268. height -= count << SHIFT;
  269. // save original X for our tail blitH() loop at the bottom
  270. int origX = x;
  271. x -= fSuperLeft;
  272. // hack, until I figure out why my cubics (I think) go beyond the bounds
  273. if (x < 0) {
  274. width += x;
  275. x = 0;
  276. }
  277. // There is always a left column, a middle, and a right column.
  278. // ileft is the destination x of the first pixel of the entire rect.
  279. // xleft is (SCALE - # of covered supersampled pixels) in that
  280. // destination pixel.
  281. int ileft = x >> SHIFT;
  282. int xleft = x & MASK;
  283. // irite is the destination x of the last pixel of the OPAQUE section.
  284. // xrite is the number of supersampled pixels extending beyond irite;
  285. // xrite/SCALE should give us alpha.
  286. int irite = (x + width) >> SHIFT;
  287. int xrite = (x + width) & MASK;
  288. if (!xrite) {
  289. xrite = SCALE;
  290. irite--;
  291. }
  292. // Need to call flush() to clean up pending draws before we
  293. // even consider blitV(), since otherwise it can look nonmonotonic.
  294. SkASSERT(start_y > fCurrIY);
  295. this->flush();
  296. int n = irite - ileft - 1;
  297. if (n < 0) {
  298. // If n < 0, we'll only have a single partially-transparent column
  299. // of pixels to render.
  300. xleft = xrite - xleft;
  301. SkASSERT(xleft <= SCALE);
  302. SkASSERT(xleft > 0);
  303. fRealBlitter->blitV(ileft + fLeft, start_y, count,
  304. coverage_to_exact_alpha(xleft));
  305. } else {
  306. // With n = 0, we have two possibly-transparent columns of pixels
  307. // to render; with n > 0, we have opaque columns between them.
  308. xleft = SCALE - xleft;
  309. // Using coverage_to_exact_alpha is not consistent with blitH()
  310. const int coverageL = coverage_to_exact_alpha(xleft);
  311. const int coverageR = coverage_to_exact_alpha(xrite);
  312. SkASSERT(coverageL > 0 || n > 0 || coverageR > 0);
  313. SkASSERT((coverageL != 0) + n + (coverageR != 0) <= fWidth);
  314. fRealBlitter->blitAntiRect(ileft + fLeft, start_y, n, count,
  315. coverageL, coverageR);
  316. }
  317. // preamble for our next call to blitH()
  318. fCurrIY = stop_y - 1;
  319. fOffsetX = 0;
  320. fCurrY = y - 1;
  321. fRuns.reset(fWidth);
  322. x = origX;
  323. }
  324. // catch any remaining few rows
  325. SkASSERT(height <= MASK);
  326. while (--height >= 0) {
  327. this->blitH(x, y++, width);
  328. }
  329. }
  330. ///////////////////////////////////////////////////////////////////////////////
  331. /// Masked supersampling antialiased blitter.
  332. class MaskSuperBlitter : public BaseSuperBlitter {
  333. public:
  334. MaskSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, const SkIRect&, bool isInverse);
  335. ~MaskSuperBlitter() override {
  336. fRealBlitter->blitMask(fMask, fClipRect);
  337. }
  338. void blitH(int x, int y, int width) override;
  339. static bool CanHandleRect(const SkIRect& bounds) {
  340. #ifdef FORCE_RLE
  341. return false;
  342. #endif
  343. int width = bounds.width();
  344. int64_t rb = SkAlign4(width);
  345. // use 64bits to detect overflow
  346. int64_t storage = rb * bounds.height();
  347. return (width <= MaskSuperBlitter::kMAX_WIDTH) &&
  348. (storage <= MaskSuperBlitter::kMAX_STORAGE);
  349. }
  350. private:
  351. enum {
  352. #ifdef FORCE_SUPERMASK
  353. kMAX_WIDTH = 2048,
  354. kMAX_STORAGE = 1024 * 1024 * 2
  355. #else
  356. kMAX_WIDTH = 32, // so we don't try to do very wide things, where the RLE blitter would be faster
  357. kMAX_STORAGE = 1024
  358. #endif
  359. };
  360. SkMask fMask;
  361. SkIRect fClipRect;
  362. // we add 1 because add_aa_span can write (unchanged) 1 extra byte at the end, rather than
  363. // perform a test to see if stopAlpha != 0
  364. uint32_t fStorage[(kMAX_STORAGE >> 2) + 1];
  365. };
  366. MaskSuperBlitter::MaskSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir,
  367. const SkIRect& clipBounds, bool isInverse)
  368. : BaseSuperBlitter(realBlitter, ir, clipBounds, isInverse)
  369. {
  370. SkASSERT(CanHandleRect(ir));
  371. SkASSERT(!isInverse);
  372. fMask.fImage = (uint8_t*)fStorage;
  373. fMask.fBounds = ir;
  374. fMask.fRowBytes = ir.width();
  375. fMask.fFormat = SkMask::kA8_Format;
  376. fClipRect = ir;
  377. if (!fClipRect.intersect(clipBounds)) {
  378. SkASSERT(0);
  379. fClipRect.setEmpty();
  380. }
  381. // For valgrind, write 1 extra byte at the end so we don't read
  382. // uninitialized memory. See comment in add_aa_span and fStorage[].
  383. memset(fStorage, 0, fMask.fBounds.height() * fMask.fRowBytes + 1);
  384. }
  385. static void add_aa_span(uint8_t* alpha, U8CPU startAlpha) {
  386. /* I should be able to just add alpha[x] + startAlpha.
  387. However, if the trailing edge of the previous span and the leading
  388. edge of the current span round to the same super-sampled x value,
  389. I might overflow to 256 with this add, hence the funny subtract.
  390. */
  391. unsigned tmp = *alpha + startAlpha;
  392. SkASSERT(tmp <= 256);
  393. *alpha = SkToU8(tmp - (tmp >> 8));
  394. }
  395. static inline uint32_t quadplicate_byte(U8CPU value) {
  396. uint32_t pair = (value << 8) | value;
  397. return (pair << 16) | pair;
  398. }
  399. // Perform this tricky subtract, to avoid overflowing to 256. Our caller should
  400. // only ever call us with at most enough to hit 256 (never larger), so it is
  401. // enough to just subtract the high-bit. Actually clamping with a branch would
  402. // be slower (e.g. if (tmp > 255) tmp = 255;)
  403. //
  404. static inline void saturated_add(uint8_t* ptr, U8CPU add) {
  405. unsigned tmp = *ptr + add;
  406. SkASSERT(tmp <= 256);
  407. *ptr = SkToU8(tmp - (tmp >> 8));
  408. }
  409. // minimum count before we want to setup an inner loop, adding 4-at-a-time
  410. #define MIN_COUNT_FOR_QUAD_LOOP 16
  411. static void add_aa_span(uint8_t* alpha, U8CPU startAlpha, int middleCount,
  412. U8CPU stopAlpha, U8CPU maxValue) {
  413. SkASSERT(middleCount >= 0);
  414. saturated_add(alpha, startAlpha);
  415. alpha += 1;
  416. if (middleCount >= MIN_COUNT_FOR_QUAD_LOOP) {
  417. // loop until we're quad-byte aligned
  418. while (reinterpret_cast<intptr_t>(alpha) & 0x3) {
  419. alpha[0] = SkToU8(alpha[0] + maxValue);
  420. alpha += 1;
  421. middleCount -= 1;
  422. }
  423. int bigCount = middleCount >> 2;
  424. uint32_t* qptr = reinterpret_cast<uint32_t*>(alpha);
  425. uint32_t qval = quadplicate_byte(maxValue);
  426. do {
  427. *qptr++ += qval;
  428. } while (--bigCount > 0);
  429. middleCount &= 3;
  430. alpha = reinterpret_cast<uint8_t*> (qptr);
  431. // fall through to the following while-loop
  432. }
  433. while (--middleCount >= 0) {
  434. alpha[0] = SkToU8(alpha[0] + maxValue);
  435. alpha += 1;
  436. }
  437. // potentially this can be off the end of our "legal" alpha values, but that
  438. // only happens if stopAlpha is also 0. Rather than test for stopAlpha != 0
  439. // every time (slow), we just do it, and ensure that we've allocated extra space
  440. // (see the + 1 comment in fStorage[]
  441. saturated_add(alpha, stopAlpha);
  442. }
  443. void MaskSuperBlitter::blitH(int x, int y, int width) {
  444. int iy = (y >> SHIFT);
  445. SkASSERT(iy >= fMask.fBounds.fTop && iy < fMask.fBounds.fBottom);
  446. iy -= fMask.fBounds.fTop; // make it relative to 0
  447. // This should never happen, but it does. Until the true cause is
  448. // discovered, let's skip this span instead of crashing.
  449. // See http://crbug.com/17569.
  450. if (iy < 0) {
  451. return;
  452. }
  453. #ifdef SK_DEBUG
  454. {
  455. int ix = x >> SHIFT;
  456. SkASSERT(ix >= fMask.fBounds.fLeft && ix < fMask.fBounds.fRight);
  457. }
  458. #endif
  459. x -= SkLeftShift(fMask.fBounds.fLeft, SHIFT);
  460. // hack, until I figure out why my cubics (I think) go beyond the bounds
  461. if (x < 0) {
  462. width += x;
  463. x = 0;
  464. }
  465. uint8_t* row = fMask.fImage + iy * fMask.fRowBytes + (x >> SHIFT);
  466. int start = x;
  467. int stop = x + width;
  468. SkASSERT(start >= 0 && stop > start);
  469. int fb = start & MASK;
  470. int fe = stop & MASK;
  471. int n = (stop >> SHIFT) - (start >> SHIFT) - 1;
  472. if (n < 0) {
  473. SkASSERT(row >= fMask.fImage);
  474. SkASSERT(row < fMask.fImage + kMAX_STORAGE + 1);
  475. add_aa_span(row, coverage_to_partial_alpha(fe - fb));
  476. } else {
  477. fb = SCALE - fb;
  478. SkASSERT(row >= fMask.fImage);
  479. SkASSERT(row + n + 1 < fMask.fImage + kMAX_STORAGE + 1);
  480. add_aa_span(row, coverage_to_partial_alpha(fb),
  481. n, coverage_to_partial_alpha(fe),
  482. (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT));
  483. }
  484. #ifdef SK_DEBUG
  485. fCurrX = x + width;
  486. #endif
  487. }
  488. ///////////////////////////////////////////////////////////////////////////////
  489. static SkIRect safeRoundOut(const SkRect& src) {
  490. // roundOut will pin huge floats to max/min int
  491. SkIRect dst = src.roundOut();
  492. // intersect with a smaller huge rect, so the rect will not be considered empty for being
  493. // too large. e.g. { -SK_MaxS32 ... SK_MaxS32 } is considered empty because its width
  494. // exceeds signed 32bit.
  495. const int32_t limit = SK_MaxS32 >> SK_SUPERSAMPLE_SHIFT;
  496. (void)dst.intersect({ -limit, -limit, limit, limit});
  497. return dst;
  498. }
  499. constexpr int kSampleSize = 8;
  500. #if !defined(SK_DISABLE_AAA)
  501. constexpr SkScalar kComplexityThreshold = 0.25;
  502. #endif
  503. static void compute_complexity(const SkPath& path, SkScalar& avgLength, SkScalar& complexity) {
  504. int n = path.countPoints();
  505. if (n < kSampleSize || path.getBounds().isEmpty()) {
  506. // set to invalid value to indicate that we failed to compute
  507. avgLength = complexity = -1;
  508. return;
  509. }
  510. SkScalar sumLength = 0;
  511. SkPoint lastPoint = path.getPoint(0);
  512. for(int i = 1; i < kSampleSize; ++i) {
  513. SkPoint point = path.getPoint(i);
  514. sumLength += SkPoint::Distance(lastPoint, point);
  515. lastPoint = point;
  516. }
  517. avgLength = sumLength / (kSampleSize - 1);
  518. auto sqr = [](SkScalar x) { return x*x; };
  519. SkScalar diagonalSqr = sqr(path.getBounds().width()) + sqr(path.getBounds().height());
  520. // If the path consists of random line segments, the number of intersections should be
  521. // proportional to this.
  522. SkScalar intersections = sk_ieee_float_divide(sqr(n) * sqr(avgLength), diagonalSqr);
  523. // The number of intersections per scanline should be proportional to this number.
  524. complexity = sk_ieee_float_divide(intersections, path.getBounds().height());
  525. if (sk_float_isnan(complexity)) { // it may be possible to have 0.0 / 0.0; inf is fine for us.
  526. complexity = -1;
  527. }
  528. }
  529. static bool ShouldUseAAA(const SkPath& path, SkScalar avgLength, SkScalar complexity) {
  530. #if defined(SK_DISABLE_AAA)
  531. return false;
  532. #else
  533. if (gSkForceAnalyticAA) {
  534. return true;
  535. }
  536. if (!gSkUseAnalyticAA) {
  537. return false;
  538. }
  539. if (path.isRect(nullptr)) {
  540. return true;
  541. }
  542. #ifdef SK_SUPPORT_LEGACY_AAA_CHOICE
  543. const SkRect& bounds = path.getBounds();
  544. // When the path have so many points compared to the size of its
  545. // bounds/resolution, it indicates that the path is not quite smooth in
  546. // the current resolution: the expected number of turning points in
  547. // every pixel row/column is significantly greater than zero. Hence
  548. // Aanlytic AA is not likely to produce visible quality improvements,
  549. // and Analytic AA might be slower than supersampling.
  550. return path.countPoints() < SkTMax(bounds.width(), bounds.height()) / 2 - 10;
  551. #else
  552. if (path.countPoints() >= path.getBounds().height()) {
  553. // SAA is faster than AAA in this case even if there are no
  554. // intersections because AAA will have too many scan lines. See
  555. // skbug.com/8272
  556. return false;
  557. }
  558. // We will use AAA if the number of verbs < kSampleSize and therefore complexity < 0
  559. return complexity < kComplexityThreshold;
  560. #endif
  561. #endif
  562. }
  563. void SkScan::SAAFillPath(const SkPath& path, SkBlitter* blitter, const SkIRect& ir,
  564. const SkIRect& clipBounds, bool forceRLE) {
  565. bool containedInClip = clipBounds.contains(ir);
  566. bool isInverse = path.isInverseFillType();
  567. // MaskSuperBlitter can't handle drawing outside of ir, so we can't use it
  568. // if we're an inverse filltype
  569. if (!isInverse && MaskSuperBlitter::CanHandleRect(ir) && !forceRLE) {
  570. MaskSuperBlitter superBlit(blitter, ir, clipBounds, isInverse);
  571. SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop);
  572. sk_fill_path(path, clipBounds, &superBlit, ir.fTop, ir.fBottom, SHIFT, containedInClip);
  573. } else {
  574. SuperBlitter superBlit(blitter, ir, clipBounds, isInverse);
  575. sk_fill_path(path, clipBounds, &superBlit, ir.fTop, ir.fBottom, SHIFT, containedInClip);
  576. }
  577. }
  578. static int overflows_short_shift(int value, int shift) {
  579. const int s = 16 + shift;
  580. return (SkLeftShift(value, s) >> s) - value;
  581. }
  582. /**
  583. Would any of the coordinates of this rectangle not fit in a short,
  584. when left-shifted by shift?
  585. */
  586. static int rect_overflows_short_shift(SkIRect rect, int shift) {
  587. SkASSERT(!overflows_short_shift(8191, shift));
  588. SkASSERT(overflows_short_shift(8192, shift));
  589. SkASSERT(!overflows_short_shift(32767, 0));
  590. SkASSERT(overflows_short_shift(32768, 0));
  591. // Since we expect these to succeed, we bit-or together
  592. // for a tiny extra bit of speed.
  593. return overflows_short_shift(rect.fLeft, shift) |
  594. overflows_short_shift(rect.fRight, shift) |
  595. overflows_short_shift(rect.fTop, shift) |
  596. overflows_short_shift(rect.fBottom, shift);
  597. }
  598. void SkScan::AntiFillPath(const SkPath& path, const SkRegion& origClip,
  599. SkBlitter* blitter, bool forceRLE) {
  600. if (origClip.isEmpty()) {
  601. return;
  602. }
  603. const bool isInverse = path.isInverseFillType();
  604. SkIRect ir = safeRoundOut(path.getBounds());
  605. if (ir.isEmpty()) {
  606. if (isInverse) {
  607. blitter->blitRegion(origClip);
  608. }
  609. return;
  610. }
  611. // If the intersection of the path bounds and the clip bounds
  612. // will overflow 32767 when << by SHIFT, we can't supersample,
  613. // so draw without antialiasing.
  614. SkIRect clippedIR;
  615. if (isInverse) {
  616. // If the path is an inverse fill, it's going to fill the entire
  617. // clip, and we care whether the entire clip exceeds our limits.
  618. clippedIR = origClip.getBounds();
  619. } else {
  620. if (!clippedIR.intersect(ir, origClip.getBounds())) {
  621. return;
  622. }
  623. }
  624. if (rect_overflows_short_shift(clippedIR, SHIFT)) {
  625. SkScan::FillPath(path, origClip, blitter);
  626. return;
  627. }
  628. // Our antialiasing can't handle a clip larger than 32767, so we restrict
  629. // the clip to that limit here. (the runs[] uses int16_t for its index).
  630. //
  631. // A more general solution (one that could also eliminate the need to
  632. // disable aa based on ir bounds (see overflows_short_shift) would be
  633. // to tile the clip/target...
  634. SkRegion tmpClipStorage;
  635. const SkRegion* clipRgn = &origClip;
  636. {
  637. static const int32_t kMaxClipCoord = 32767;
  638. const SkIRect& bounds = origClip.getBounds();
  639. if (bounds.fRight > kMaxClipCoord || bounds.fBottom > kMaxClipCoord) {
  640. SkIRect limit = { 0, 0, kMaxClipCoord, kMaxClipCoord };
  641. tmpClipStorage.op(origClip, limit, SkRegion::kIntersect_Op);
  642. clipRgn = &tmpClipStorage;
  643. }
  644. }
  645. // for here down, use clipRgn, not origClip
  646. SkScanClipper clipper(blitter, clipRgn, ir);
  647. if (clipper.getBlitter() == nullptr) { // clipped out
  648. if (isInverse) {
  649. blitter->blitRegion(*clipRgn);
  650. }
  651. return;
  652. }
  653. SkASSERT(clipper.getClipRect() == nullptr ||
  654. *clipper.getClipRect() == clipRgn->getBounds());
  655. // now use the (possibly wrapped) blitter
  656. blitter = clipper.getBlitter();
  657. if (isInverse) {
  658. sk_blit_above(blitter, ir, *clipRgn);
  659. }
  660. SkScalar avgLength, complexity;
  661. compute_complexity(path, avgLength, complexity);
  662. if (ShouldUseAAA(path, avgLength, complexity)) {
  663. // Do not use AAA if path is too complicated:
  664. // there won't be any speedup or significant visual improvement.
  665. SkScan::AAAFillPath(path, blitter, ir, clipRgn->getBounds(), forceRLE);
  666. } else {
  667. SkScan::SAAFillPath(path, blitter, ir, clipRgn->getBounds(), forceRLE);
  668. }
  669. if (isInverse) {
  670. sk_blit_below(blitter, ir, *clipRgn);
  671. }
  672. }
  673. ///////////////////////////////////////////////////////////////////////////////
  674. #include "src/core/SkRasterClip.h"
  675. void SkScan::FillPath(const SkPath& path, const SkRasterClip& clip, SkBlitter* blitter) {
  676. if (clip.isEmpty() || !path.isFinite()) {
  677. return;
  678. }
  679. if (clip.isBW()) {
  680. FillPath(path, clip.bwRgn(), blitter);
  681. } else {
  682. SkRegion tmp;
  683. SkAAClipBlitter aaBlitter;
  684. tmp.setRect(clip.getBounds());
  685. aaBlitter.init(blitter, &clip.aaRgn());
  686. SkScan::FillPath(path, tmp, &aaBlitter);
  687. }
  688. }
  689. void SkScan::AntiFillPath(const SkPath& path, const SkRasterClip& clip, SkBlitter* blitter) {
  690. if (clip.isEmpty() || !path.isFinite()) {
  691. return;
  692. }
  693. if (clip.isBW()) {
  694. AntiFillPath(path, clip.bwRgn(), blitter, false);
  695. } else {
  696. SkRegion tmp;
  697. SkAAClipBlitter aaBlitter;
  698. tmp.setRect(clip.getBounds());
  699. aaBlitter.init(blitter, &clip.aaRgn());
  700. AntiFillPath(path, tmp, &aaBlitter, true); // SkAAClipBlitter can blitMask, why forceRLE?
  701. }
  702. }