SkScan_AAAPath.cpp 80 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011
  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. #include "include/core/SkPath.h"
  8. #include "include/core/SkRegion.h"
  9. #include "include/private/SkTemplates.h"
  10. #include "include/private/SkTo.h"
  11. #include "src/core/SkAnalyticEdge.h"
  12. #include "src/core/SkAntiRun.h"
  13. #include "src/core/SkAutoMalloc.h"
  14. #include "src/core/SkBlitter.h"
  15. #include "src/core/SkEdge.h"
  16. #include "src/core/SkEdgeBuilder.h"
  17. #include "src/core/SkGeometry.h"
  18. #include "src/core/SkQuadClipper.h"
  19. #include "src/core/SkRasterClip.h"
  20. #include "src/core/SkScan.h"
  21. #include "src/core/SkScanPriv.h"
  22. #include "src/core/SkTSort.h"
  23. #include "src/utils/SkUTF.h"
  24. #include <utility>
  25. #if defined(SK_DISABLE_AAA)
  26. void SkScan::AAAFillPath(const SkPath&, SkBlitter*, const SkIRect&, const SkIRect&, bool) {
  27. SkDEBUGFAIL("AAA Disabled");
  28. return;
  29. }
  30. #else
  31. /*
  32. The following is a high-level overview of our analytic anti-aliasing
  33. algorithm. We consider a path as a collection of line segments, as
  34. quadratic/cubic curves are converted to small line segments. Without loss of
  35. generality, let's assume that the draw region is [0, W] x [0, H].
  36. Our algorithm is based on horizontal scan lines (y = c_i) as the previous
  37. sampling-based algorithm did. However, our algorithm uses non-equal-spaced
  38. scan lines, while the previous method always uses equal-spaced scan lines,
  39. such as (y = 1/2 + 0, 1/2 + 1, 1/2 + 2, ...) in the previous non-AA algorithm,
  40. and (y = 1/8 + 1/4, 1/8 + 2/4, 1/8 + 3/4, ...) in the previous
  41. 16-supersampling AA algorithm.
  42. Our algorithm contains scan lines y = c_i for c_i that is either:
  43. 1. an integer between [0, H]
  44. 2. the y value of a line segment endpoint
  45. 3. the y value of an intersection of two line segments
  46. For two consecutive scan lines y = c_i, y = c_{i+1}, we analytically computes
  47. the coverage of this horizontal strip of our path on each pixel. This can be
  48. done very efficiently because the strip of our path now only consists of
  49. trapezoids whose top and bottom edges are y = c_i, y = c_{i+1} (this includes
  50. rectangles and triangles as special cases).
  51. We now describe how the coverage of single pixel is computed against such a
  52. trapezoid. That coverage is essentially the intersection area of a rectangle
  53. (e.g., [0, 1] x [c_i, c_{i+1}]) and our trapezoid. However, that intersection
  54. could be complicated, as shown in the example region A below:
  55. +-----------\----+
  56. | \ C|
  57. | \ |
  58. \ \ |
  59. |\ A \|
  60. | \ \
  61. | \ |
  62. | B \ |
  63. +----\-----------+
  64. However, we don't have to compute the area of A directly. Instead, we can
  65. compute the excluded area, which are B and C, quite easily, because they're
  66. just triangles. In fact, we can prove that an excluded region (take B as an
  67. example) is either itself a simple trapezoid (including rectangles, triangles,
  68. and empty regions), or its opposite (the opposite of B is A + C) is a simple
  69. trapezoid. In any case, we can compute its area efficiently.
  70. In summary, our algorithm has a higher quality because it generates ground-
  71. truth coverages analytically. It is also faster because it has much fewer
  72. unnessasary horizontal scan lines. For example, given a triangle path, the
  73. number of scan lines in our algorithm is only about 3 + H while the
  74. 16-supersampling algorithm has about 4H scan lines.
  75. */
  76. static void add_alpha(SkAlpha* alpha, SkAlpha delta) {
  77. SkASSERT(*alpha + delta <= 256);
  78. *alpha = SkAlphaRuns::CatchOverflow(*alpha + delta);
  79. }
  80. static void safely_add_alpha(SkAlpha* alpha, SkAlpha delta) {
  81. *alpha = SkTMin(0xFF, *alpha + delta);
  82. }
  83. class AdditiveBlitter : public SkBlitter {
  84. public:
  85. ~AdditiveBlitter() override {}
  86. virtual SkBlitter* getRealBlitter(bool forceRealBlitter = false) = 0;
  87. virtual void blitAntiH(int x, int y, const SkAlpha antialias[], int len) = 0;
  88. virtual void blitAntiH(int x, int y, const SkAlpha alpha) = 0;
  89. virtual void blitAntiH(int x, int y, int width, const SkAlpha alpha) = 0;
  90. void blitAntiH(int x, int y, const SkAlpha antialias[], const int16_t runs[]) override {
  91. SkDEBUGFAIL("Please call real blitter's blitAntiH instead.");
  92. }
  93. void blitV(int x, int y, int height, SkAlpha alpha) override {
  94. SkDEBUGFAIL("Please call real blitter's blitV instead.");
  95. }
  96. void blitH(int x, int y, int width) override {
  97. SkDEBUGFAIL("Please call real blitter's blitH instead.");
  98. }
  99. void blitRect(int x, int y, int width, int height) override {
  100. SkDEBUGFAIL("Please call real blitter's blitRect instead.");
  101. }
  102. void blitAntiRect(int x, int y, int width, int height, SkAlpha leftAlpha, SkAlpha rightAlpha)
  103. override {
  104. SkDEBUGFAIL("Please call real blitter's blitAntiRect instead.");
  105. }
  106. virtual int getWidth() = 0;
  107. // Flush the additive alpha cache if floor(y) and floor(nextY) is different
  108. // (i.e., we'll start working on a new pixel row).
  109. virtual void flush_if_y_changed(SkFixed y, SkFixed nextY) = 0;
  110. };
  111. // We need this mask blitter because it significantly accelerates small path filling.
  112. class MaskAdditiveBlitter : public AdditiveBlitter {
  113. public:
  114. MaskAdditiveBlitter(SkBlitter* realBlitter,
  115. const SkIRect& ir,
  116. const SkIRect& clipBounds,
  117. bool isInverse);
  118. ~MaskAdditiveBlitter() override { fRealBlitter->blitMask(fMask, fClipRect); }
  119. // Most of the time, we still consider this mask blitter as the real blitter
  120. // so we can accelerate blitRect and others. But sometimes we want to return
  121. // the absolute real blitter (e.g., when we fall back to the old code path).
  122. SkBlitter* getRealBlitter(bool forceRealBlitter) override {
  123. return forceRealBlitter ? fRealBlitter : this;
  124. }
  125. // Virtual function is slow. So don't use this. Directly add alpha to the mask instead.
  126. void blitAntiH(int x, int y, const SkAlpha antialias[], int len) override;
  127. // Allowing following methods are used to blit rectangles during aaa_walk_convex_edges
  128. // Since there aren't many rectangles, we can still bear the slow speed of virtual functions.
  129. void blitAntiH(int x, int y, const SkAlpha alpha) override;
  130. void blitAntiH(int x, int y, int width, const SkAlpha alpha) override;
  131. void blitV(int x, int y, int height, SkAlpha alpha) override;
  132. void blitRect(int x, int y, int width, int height) override;
  133. void blitAntiRect(int x, int y, int width, int height, SkAlpha leftAlpha, SkAlpha rightAlpha)
  134. override;
  135. // The flush is only needed for RLE (RunBasedAdditiveBlitter)
  136. void flush_if_y_changed(SkFixed y, SkFixed nextY) override {}
  137. int getWidth() override { return fClipRect.width(); }
  138. static bool CanHandleRect(const SkIRect& bounds) {
  139. int width = bounds.width();
  140. if (width > MaskAdditiveBlitter::kMAX_WIDTH) {
  141. return false;
  142. }
  143. int64_t rb = SkAlign4(width);
  144. // use 64bits to detect overflow
  145. int64_t storage = rb * bounds.height();
  146. return (width <= MaskAdditiveBlitter::kMAX_WIDTH) &&
  147. (storage <= MaskAdditiveBlitter::kMAX_STORAGE);
  148. }
  149. // Return a pointer where pointer[x] corresonds to the alpha of (x, y)
  150. uint8_t* getRow(int y) {
  151. if (y != fY) {
  152. fY = y;
  153. fRow = fMask.fImage + (y - fMask.fBounds.fTop) * fMask.fRowBytes - fMask.fBounds.fLeft;
  154. }
  155. return fRow;
  156. }
  157. private:
  158. // so we don't try to do very wide things, where the RLE blitter would be faster
  159. static const int kMAX_WIDTH = 32;
  160. static const int kMAX_STORAGE = 1024;
  161. SkBlitter* fRealBlitter;
  162. SkMask fMask;
  163. SkIRect fClipRect;
  164. // we add 2 because we can write 1 extra byte at either end due to precision error
  165. uint32_t fStorage[(kMAX_STORAGE >> 2) + 2];
  166. uint8_t* fRow;
  167. int fY;
  168. };
  169. MaskAdditiveBlitter::MaskAdditiveBlitter(SkBlitter* realBlitter,
  170. const SkIRect& ir,
  171. const SkIRect& clipBounds,
  172. bool isInverse) {
  173. SkASSERT(CanHandleRect(ir));
  174. SkASSERT(!isInverse);
  175. fRealBlitter = realBlitter;
  176. fMask.fImage = (uint8_t*)fStorage + 1; // There's 1 extra byte at either end of fStorage
  177. fMask.fBounds = ir;
  178. fMask.fRowBytes = ir.width();
  179. fMask.fFormat = SkMask::kA8_Format;
  180. fY = ir.fTop - 1;
  181. fRow = nullptr;
  182. fClipRect = ir;
  183. if (!fClipRect.intersect(clipBounds)) {
  184. SkASSERT(0);
  185. fClipRect.setEmpty();
  186. }
  187. memset(fStorage, 0, fMask.fBounds.height() * fMask.fRowBytes + 2);
  188. }
  189. void MaskAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha antialias[], int len) {
  190. SK_ABORT("Don't use this; directly add alphas to the mask.");
  191. }
  192. void MaskAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha alpha) {
  193. SkASSERT(x >= fMask.fBounds.fLeft - 1);
  194. add_alpha(&this->getRow(y)[x], alpha);
  195. }
  196. void MaskAdditiveBlitter::blitAntiH(int x, int y, int width, const SkAlpha alpha) {
  197. SkASSERT(x >= fMask.fBounds.fLeft - 1);
  198. uint8_t* row = this->getRow(y);
  199. for (int i = 0; i < width; ++i) {
  200. add_alpha(&row[x + i], alpha);
  201. }
  202. }
  203. void MaskAdditiveBlitter::blitV(int x, int y, int height, SkAlpha alpha) {
  204. if (alpha == 0) {
  205. return;
  206. }
  207. SkASSERT(x >= fMask.fBounds.fLeft - 1);
  208. // This must be called as if this is a real blitter.
  209. // So we directly set alpha rather than adding it.
  210. uint8_t* row = this->getRow(y);
  211. for (int i = 0; i < height; ++i) {
  212. row[x] = alpha;
  213. row += fMask.fRowBytes;
  214. }
  215. }
  216. void MaskAdditiveBlitter::blitRect(int x, int y, int width, int height) {
  217. SkASSERT(x >= fMask.fBounds.fLeft - 1);
  218. // This must be called as if this is a real blitter.
  219. // So we directly set alpha rather than adding it.
  220. uint8_t* row = this->getRow(y);
  221. for (int i = 0; i < height; ++i) {
  222. memset(row + x, 0xFF, width);
  223. row += fMask.fRowBytes;
  224. }
  225. }
  226. void MaskAdditiveBlitter::blitAntiRect(int x,
  227. int y,
  228. int width,
  229. int height,
  230. SkAlpha leftAlpha,
  231. SkAlpha rightAlpha) {
  232. blitV(x, y, height, leftAlpha);
  233. blitV(x + 1 + width, y, height, rightAlpha);
  234. blitRect(x + 1, y, width, height);
  235. }
  236. class RunBasedAdditiveBlitter : public AdditiveBlitter {
  237. public:
  238. RunBasedAdditiveBlitter(SkBlitter* realBlitter,
  239. const SkIRect& ir,
  240. const SkIRect& clipBounds,
  241. bool isInverse);
  242. ~RunBasedAdditiveBlitter() override { this->flush(); }
  243. SkBlitter* getRealBlitter(bool forceRealBlitter) override { return fRealBlitter; }
  244. void blitAntiH(int x, int y, const SkAlpha antialias[], int len) override;
  245. void blitAntiH(int x, int y, const SkAlpha alpha) override;
  246. void blitAntiH(int x, int y, int width, const SkAlpha alpha) override;
  247. int getWidth() override { return fWidth; }
  248. void flush_if_y_changed(SkFixed y, SkFixed nextY) override {
  249. if (SkFixedFloorToInt(y) != SkFixedFloorToInt(nextY)) {
  250. this->flush();
  251. }
  252. }
  253. protected:
  254. SkBlitter* fRealBlitter;
  255. int fCurrY; // Current y coordinate.
  256. int fWidth; // Widest row of region to be blitted
  257. int fLeft; // Leftmost x coordinate in any row
  258. int fTop; // Initial y coordinate (top of bounds)
  259. // The next three variables are used to track a circular buffer that
  260. // contains the values used in SkAlphaRuns. These variables should only
  261. // ever be updated in advanceRuns(), and fRuns should always point to
  262. // a valid SkAlphaRuns...
  263. int fRunsToBuffer;
  264. void* fRunsBuffer;
  265. int fCurrentRun;
  266. SkAlphaRuns fRuns;
  267. int fOffsetX;
  268. bool check(int x, int width) const { return x >= 0 && x + width <= fWidth; }
  269. // extra one to store the zero at the end
  270. int getRunsSz() const { return (fWidth + 1 + (fWidth + 2) / 2) * sizeof(int16_t); }
  271. // This function updates the fRuns variable to point to the next buffer space
  272. // with adequate storage for a SkAlphaRuns. It mostly just advances fCurrentRun
  273. // and resets fRuns to point to an empty scanline.
  274. void advanceRuns() {
  275. const size_t kRunsSz = this->getRunsSz();
  276. fCurrentRun = (fCurrentRun + 1) % fRunsToBuffer;
  277. fRuns.fRuns = reinterpret_cast<int16_t*>(reinterpret_cast<uint8_t*>(fRunsBuffer) +
  278. fCurrentRun * kRunsSz);
  279. fRuns.fAlpha = reinterpret_cast<SkAlpha*>(fRuns.fRuns + fWidth + 1);
  280. fRuns.reset(fWidth);
  281. }
  282. // Blitting 0xFF and 0 is much faster so we snap alphas close to them
  283. SkAlpha snapAlpha(SkAlpha alpha) { return alpha > 247 ? 0xFF : alpha < 8 ? 0x00 : alpha; }
  284. void flush() {
  285. if (fCurrY >= fTop) {
  286. SkASSERT(fCurrentRun < fRunsToBuffer);
  287. for (int x = 0; fRuns.fRuns[x]; x += fRuns.fRuns[x]) {
  288. // It seems that blitting 255 or 0 is much faster than blitting 254 or 1
  289. fRuns.fAlpha[x] = snapAlpha(fRuns.fAlpha[x]);
  290. }
  291. if (!fRuns.empty()) {
  292. // SkDEBUGCODE(fRuns.dump();)
  293. fRealBlitter->blitAntiH(fLeft, fCurrY, fRuns.fAlpha, fRuns.fRuns);
  294. this->advanceRuns();
  295. fOffsetX = 0;
  296. }
  297. fCurrY = fTop - 1;
  298. }
  299. }
  300. void checkY(int y) {
  301. if (y != fCurrY) {
  302. this->flush();
  303. fCurrY = y;
  304. }
  305. }
  306. };
  307. RunBasedAdditiveBlitter::RunBasedAdditiveBlitter(SkBlitter* realBlitter,
  308. const SkIRect& ir,
  309. const SkIRect& clipBounds,
  310. bool isInverse) {
  311. fRealBlitter = realBlitter;
  312. SkIRect sectBounds;
  313. if (isInverse) {
  314. // We use the clip bounds instead of the ir, since we may be asked to
  315. // draw outside of the rect when we're a inverse filltype
  316. sectBounds = clipBounds;
  317. } else {
  318. if (!sectBounds.intersect(ir, clipBounds)) {
  319. sectBounds.setEmpty();
  320. }
  321. }
  322. const int left = sectBounds.left();
  323. const int right = sectBounds.right();
  324. fLeft = left;
  325. fWidth = right - left;
  326. fTop = sectBounds.top();
  327. fCurrY = fTop - 1;
  328. fRunsToBuffer = realBlitter->requestRowsPreserved();
  329. fRunsBuffer = realBlitter->allocBlitMemory(fRunsToBuffer * this->getRunsSz());
  330. fCurrentRun = -1;
  331. this->advanceRuns();
  332. fOffsetX = 0;
  333. }
  334. void RunBasedAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha antialias[], int len) {
  335. checkY(y);
  336. x -= fLeft;
  337. if (x < 0) {
  338. len += x;
  339. antialias -= x;
  340. x = 0;
  341. }
  342. len = SkTMin(len, fWidth - x);
  343. SkASSERT(check(x, len));
  344. if (x < fOffsetX) {
  345. fOffsetX = 0;
  346. }
  347. fOffsetX = fRuns.add(x, 0, len, 0, 0, fOffsetX); // Break the run
  348. for (int i = 0; i < len; i += fRuns.fRuns[x + i]) {
  349. for (int j = 1; j < fRuns.fRuns[x + i]; j++) {
  350. fRuns.fRuns[x + i + j] = 1;
  351. fRuns.fAlpha[x + i + j] = fRuns.fAlpha[x + i];
  352. }
  353. fRuns.fRuns[x + i] = 1;
  354. }
  355. for (int i = 0; i < len; ++i) {
  356. add_alpha(&fRuns.fAlpha[x + i], antialias[i]);
  357. }
  358. }
  359. void RunBasedAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha alpha) {
  360. checkY(y);
  361. x -= fLeft;
  362. if (x < fOffsetX) {
  363. fOffsetX = 0;
  364. }
  365. if (this->check(x, 1)) {
  366. fOffsetX = fRuns.add(x, 0, 1, 0, alpha, fOffsetX);
  367. }
  368. }
  369. void RunBasedAdditiveBlitter::blitAntiH(int x, int y, int width, const SkAlpha alpha) {
  370. checkY(y);
  371. x -= fLeft;
  372. if (x < fOffsetX) {
  373. fOffsetX = 0;
  374. }
  375. if (this->check(x, width)) {
  376. fOffsetX = fRuns.add(x, 0, width, 0, alpha, fOffsetX);
  377. }
  378. }
  379. // This exists specifically for concave path filling.
  380. // In those cases, we can easily accumulate alpha greater than 0xFF.
  381. class SafeRLEAdditiveBlitter : public RunBasedAdditiveBlitter {
  382. public:
  383. SafeRLEAdditiveBlitter(SkBlitter* realBlitter,
  384. const SkIRect& ir,
  385. const SkIRect& clipBounds,
  386. bool isInverse)
  387. : RunBasedAdditiveBlitter(realBlitter, ir, clipBounds, isInverse) {}
  388. void blitAntiH(int x, int y, const SkAlpha antialias[], int len) override;
  389. void blitAntiH(int x, int y, const SkAlpha alpha) override;
  390. void blitAntiH(int x, int y, int width, const SkAlpha alpha) override;
  391. };
  392. void SafeRLEAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha antialias[], int len) {
  393. checkY(y);
  394. x -= fLeft;
  395. if (x < 0) {
  396. len += x;
  397. antialias -= x;
  398. x = 0;
  399. }
  400. len = SkTMin(len, fWidth - x);
  401. SkASSERT(check(x, len));
  402. if (x < fOffsetX) {
  403. fOffsetX = 0;
  404. }
  405. fOffsetX = fRuns.add(x, 0, len, 0, 0, fOffsetX); // Break the run
  406. for (int i = 0; i < len; i += fRuns.fRuns[x + i]) {
  407. for (int j = 1; j < fRuns.fRuns[x + i]; j++) {
  408. fRuns.fRuns[x + i + j] = 1;
  409. fRuns.fAlpha[x + i + j] = fRuns.fAlpha[x + i];
  410. }
  411. fRuns.fRuns[x + i] = 1;
  412. }
  413. for (int i = 0; i < len; ++i) {
  414. safely_add_alpha(&fRuns.fAlpha[x + i], antialias[i]);
  415. }
  416. }
  417. void SafeRLEAdditiveBlitter::blitAntiH(int x, int y, const SkAlpha alpha) {
  418. checkY(y);
  419. x -= fLeft;
  420. if (x < fOffsetX) {
  421. fOffsetX = 0;
  422. }
  423. if (check(x, 1)) {
  424. // Break the run
  425. fOffsetX = fRuns.add(x, 0, 1, 0, 0, fOffsetX);
  426. safely_add_alpha(&fRuns.fAlpha[x], alpha);
  427. }
  428. }
  429. void SafeRLEAdditiveBlitter::blitAntiH(int x, int y, int width, const SkAlpha alpha) {
  430. checkY(y);
  431. x -= fLeft;
  432. if (x < fOffsetX) {
  433. fOffsetX = 0;
  434. }
  435. if (check(x, width)) {
  436. // Break the run
  437. fOffsetX = fRuns.add(x, 0, width, 0, 0, fOffsetX);
  438. for (int i = x; i < x + width; i += fRuns.fRuns[i]) {
  439. safely_add_alpha(&fRuns.fAlpha[i], alpha);
  440. }
  441. }
  442. }
  443. // Return the alpha of a trapezoid whose height is 1
  444. static SkAlpha trapezoid_to_alpha(SkFixed l1, SkFixed l2) {
  445. SkASSERT(l1 >= 0 && l2 >= 0);
  446. SkFixed area = (l1 + l2) / 2;
  447. return SkTo<SkAlpha>(area >> 8);
  448. }
  449. // The alpha of right-triangle (a, a*b)
  450. static SkAlpha partial_triangle_to_alpha(SkFixed a, SkFixed b) {
  451. SkASSERT(a <= SK_Fixed1);
  452. #if 0
  453. // TODO(mtklein): skia:8877
  454. SkASSERT(b <= SK_Fixed1);
  455. #endif
  456. // Approximating...
  457. // SkFixed area = SkFixedMul(a, SkFixedMul(a,b)) / 2;
  458. SkFixed area = (a >> 11) * (a >> 11) * (b >> 11);
  459. #if 0
  460. // TODO(mtklein): skia:8877
  461. return SkTo<SkAlpha>(area >> 8);
  462. #else
  463. return SkTo<SkAlpha>((area >> 8) & 0xFF);
  464. #endif
  465. }
  466. static SkAlpha get_partial_alpha(SkAlpha alpha, SkFixed partialHeight) {
  467. return SkToU8(SkFixedRoundToInt(alpha * partialHeight));
  468. }
  469. static SkAlpha get_partial_alpha(SkAlpha alpha, SkAlpha fullAlpha) {
  470. return (alpha * fullAlpha) >> 8;
  471. }
  472. // For SkFixed that's close to SK_Fixed1, we can't convert it to alpha by just shifting right.
  473. // For example, when f = SK_Fixed1, right shifting 8 will get 256, but we need 255.
  474. // This is rarely the problem so we'll only use this for blitting rectangles.
  475. static SkAlpha fixed_to_alpha(SkFixed f) {
  476. SkASSERT(f <= SK_Fixed1);
  477. return get_partial_alpha(0xFF, f);
  478. }
  479. // Suppose that line (l1, y)-(r1, y+1) intersects with (l2, y)-(r2, y+1),
  480. // approximate (very coarsely) the x coordinate of the intersection.
  481. static SkFixed approximate_intersection(SkFixed l1, SkFixed r1, SkFixed l2, SkFixed r2) {
  482. if (l1 > r1) {
  483. std::swap(l1, r1);
  484. }
  485. if (l2 > r2) {
  486. std::swap(l2, r2);
  487. }
  488. return (SkTMax(l1, l2) + SkTMin(r1, r2)) / 2;
  489. }
  490. // Here we always send in l < SK_Fixed1, and the first alpha we want to compute is alphas[0]
  491. static void compute_alpha_above_line(SkAlpha* alphas,
  492. SkFixed l,
  493. SkFixed r,
  494. SkFixed dY,
  495. SkAlpha fullAlpha) {
  496. SkASSERT(l <= r);
  497. SkASSERT(l >> 16 == 0);
  498. int R = SkFixedCeilToInt(r);
  499. if (R == 0) {
  500. return;
  501. } else if (R == 1) {
  502. alphas[0] = get_partial_alpha(((R << 17) - l - r) >> 9, fullAlpha);
  503. } else {
  504. SkFixed first = SK_Fixed1 - l; // horizontal edge length of the left-most triangle
  505. SkFixed last = r - ((R - 1) << 16); // horizontal edge length of the right-most triangle
  506. SkFixed firstH = SkFixedMul(first, dY); // vertical edge of the left-most triangle
  507. alphas[0] = SkFixedMul(first, firstH) >> 9; // triangle alpha
  508. SkFixed alpha16 = firstH + (dY >> 1); // rectangle plus triangle
  509. for (int i = 1; i < R - 1; ++i) {
  510. alphas[i] = alpha16 >> 8;
  511. alpha16 += dY;
  512. }
  513. alphas[R - 1] = fullAlpha - partial_triangle_to_alpha(last, dY);
  514. }
  515. }
  516. // Here we always send in l < SK_Fixed1, and the first alpha we want to compute is alphas[0]
  517. static void compute_alpha_below_line(SkAlpha* alphas,
  518. SkFixed l,
  519. SkFixed r,
  520. SkFixed dY,
  521. SkAlpha fullAlpha) {
  522. SkASSERT(l <= r);
  523. SkASSERT(l >> 16 == 0);
  524. int R = SkFixedCeilToInt(r);
  525. if (R == 0) {
  526. return;
  527. } else if (R == 1) {
  528. alphas[0] = get_partial_alpha(trapezoid_to_alpha(l, r), fullAlpha);
  529. } else {
  530. SkFixed first = SK_Fixed1 - l; // horizontal edge length of the left-most triangle
  531. SkFixed last = r - ((R - 1) << 16); // horizontal edge length of the right-most triangle
  532. SkFixed lastH = SkFixedMul(last, dY); // vertical edge of the right-most triangle
  533. alphas[R - 1] = SkFixedMul(last, lastH) >> 9; // triangle alpha
  534. SkFixed alpha16 = lastH + (dY >> 1); // rectangle plus triangle
  535. for (int i = R - 2; i > 0; i--) {
  536. alphas[i] = (alpha16 >> 8) & 0xFF;
  537. alpha16 += dY;
  538. }
  539. alphas[0] = fullAlpha - partial_triangle_to_alpha(first, dY);
  540. }
  541. }
  542. // Note that if fullAlpha != 0xFF, we'll multiply alpha by fullAlpha
  543. static SK_ALWAYS_INLINE void blit_single_alpha(AdditiveBlitter* blitter,
  544. int y,
  545. int x,
  546. SkAlpha alpha,
  547. SkAlpha fullAlpha,
  548. SkAlpha* maskRow,
  549. bool isUsingMask,
  550. bool noRealBlitter,
  551. bool needSafeCheck) {
  552. if (isUsingMask) {
  553. if (fullAlpha == 0xFF && !noRealBlitter) { // noRealBlitter is needed for concave paths
  554. maskRow[x] = alpha;
  555. } else if (needSafeCheck) {
  556. safely_add_alpha(&maskRow[x], get_partial_alpha(alpha, fullAlpha));
  557. } else {
  558. add_alpha(&maskRow[x], get_partial_alpha(alpha, fullAlpha));
  559. }
  560. } else {
  561. if (fullAlpha == 0xFF && !noRealBlitter) {
  562. blitter->getRealBlitter()->blitV(x, y, 1, alpha);
  563. } else {
  564. blitter->blitAntiH(x, y, get_partial_alpha(alpha, fullAlpha));
  565. }
  566. }
  567. }
  568. static SK_ALWAYS_INLINE void blit_two_alphas(AdditiveBlitter* blitter,
  569. int y,
  570. int x,
  571. SkAlpha a1,
  572. SkAlpha a2,
  573. SkAlpha fullAlpha,
  574. SkAlpha* maskRow,
  575. bool isUsingMask,
  576. bool noRealBlitter,
  577. bool needSafeCheck) {
  578. if (isUsingMask) {
  579. if (needSafeCheck) {
  580. safely_add_alpha(&maskRow[x], a1);
  581. safely_add_alpha(&maskRow[x + 1], a2);
  582. } else {
  583. add_alpha(&maskRow[x], a1);
  584. add_alpha(&maskRow[x + 1], a2);
  585. }
  586. } else {
  587. if (fullAlpha == 0xFF && !noRealBlitter) {
  588. blitter->getRealBlitter()->blitAntiH2(x, y, a1, a2);
  589. } else {
  590. blitter->blitAntiH(x, y, a1);
  591. blitter->blitAntiH(x + 1, y, a2);
  592. }
  593. }
  594. }
  595. static SK_ALWAYS_INLINE void blit_full_alpha(AdditiveBlitter* blitter,
  596. int y,
  597. int x,
  598. int len,
  599. SkAlpha fullAlpha,
  600. SkAlpha* maskRow,
  601. bool isUsingMask,
  602. bool noRealBlitter,
  603. bool needSafeCheck) {
  604. if (isUsingMask) {
  605. for (int i = 0; i < len; ++i) {
  606. if (needSafeCheck) {
  607. safely_add_alpha(&maskRow[x + i], fullAlpha);
  608. } else {
  609. add_alpha(&maskRow[x + i], fullAlpha);
  610. }
  611. }
  612. } else {
  613. if (fullAlpha == 0xFF && !noRealBlitter) {
  614. blitter->getRealBlitter()->blitH(x, y, len);
  615. } else {
  616. blitter->blitAntiH(x, y, len, fullAlpha);
  617. }
  618. }
  619. }
  620. static void blit_aaa_trapezoid_row(AdditiveBlitter* blitter,
  621. int y,
  622. SkFixed ul,
  623. SkFixed ur,
  624. SkFixed ll,
  625. SkFixed lr,
  626. SkFixed lDY,
  627. SkFixed rDY,
  628. SkAlpha fullAlpha,
  629. SkAlpha* maskRow,
  630. bool isUsingMask,
  631. bool noRealBlitter,
  632. bool needSafeCheck) {
  633. int L = SkFixedFloorToInt(ul), R = SkFixedCeilToInt(lr);
  634. int len = R - L;
  635. if (len == 1) {
  636. SkAlpha alpha = trapezoid_to_alpha(ur - ul, lr - ll);
  637. blit_single_alpha(blitter,
  638. y,
  639. L,
  640. alpha,
  641. fullAlpha,
  642. maskRow,
  643. isUsingMask,
  644. noRealBlitter,
  645. needSafeCheck);
  646. return;
  647. }
  648. const int kQuickLen = 31;
  649. char quickMemory[(sizeof(SkAlpha) * 2 + sizeof(int16_t)) * (kQuickLen + 1)];
  650. SkAlpha* alphas;
  651. if (len <= kQuickLen) {
  652. alphas = (SkAlpha*)quickMemory;
  653. } else {
  654. alphas = new SkAlpha[(len + 1) * (sizeof(SkAlpha) * 2 + sizeof(int16_t))];
  655. }
  656. SkAlpha* tempAlphas = alphas + len + 1;
  657. int16_t* runs = (int16_t*)(alphas + (len + 1) * 2);
  658. for (int i = 0; i < len; ++i) {
  659. runs[i] = 1;
  660. alphas[i] = fullAlpha;
  661. }
  662. runs[len] = 0;
  663. int uL = SkFixedFloorToInt(ul);
  664. int lL = SkFixedCeilToInt(ll);
  665. if (uL + 2 == lL) { // We only need to compute two triangles, accelerate this special case
  666. SkFixed first = SkIntToFixed(uL) + SK_Fixed1 - ul;
  667. SkFixed second = ll - ul - first;
  668. SkAlpha a1 = fullAlpha - partial_triangle_to_alpha(first, lDY);
  669. SkAlpha a2 = partial_triangle_to_alpha(second, lDY);
  670. alphas[0] = alphas[0] > a1 ? alphas[0] - a1 : 0;
  671. alphas[1] = alphas[1] > a2 ? alphas[1] - a2 : 0;
  672. } else {
  673. compute_alpha_below_line(
  674. tempAlphas + uL - L, ul - SkIntToFixed(uL), ll - SkIntToFixed(uL), lDY, fullAlpha);
  675. for (int i = uL; i < lL; ++i) {
  676. if (alphas[i - L] > tempAlphas[i - L]) {
  677. alphas[i - L] -= tempAlphas[i - L];
  678. } else {
  679. alphas[i - L] = 0;
  680. }
  681. }
  682. }
  683. int uR = SkFixedFloorToInt(ur);
  684. int lR = SkFixedCeilToInt(lr);
  685. if (uR + 2 == lR) { // We only need to compute two triangles, accelerate this special case
  686. SkFixed first = SkIntToFixed(uR) + SK_Fixed1 - ur;
  687. SkFixed second = lr - ur - first;
  688. SkAlpha a1 = partial_triangle_to_alpha(first, rDY);
  689. SkAlpha a2 = fullAlpha - partial_triangle_to_alpha(second, rDY);
  690. alphas[len - 2] = alphas[len - 2] > a1 ? alphas[len - 2] - a1 : 0;
  691. alphas[len - 1] = alphas[len - 1] > a2 ? alphas[len - 1] - a2 : 0;
  692. } else {
  693. compute_alpha_above_line(
  694. tempAlphas + uR - L, ur - SkIntToFixed(uR), lr - SkIntToFixed(uR), rDY, fullAlpha);
  695. for (int i = uR; i < lR; ++i) {
  696. if (alphas[i - L] > tempAlphas[i - L]) {
  697. alphas[i - L] -= tempAlphas[i - L];
  698. } else {
  699. alphas[i - L] = 0;
  700. }
  701. }
  702. }
  703. if (isUsingMask) {
  704. for (int i = 0; i < len; ++i) {
  705. if (needSafeCheck) {
  706. safely_add_alpha(&maskRow[L + i], alphas[i]);
  707. } else {
  708. add_alpha(&maskRow[L + i], alphas[i]);
  709. }
  710. }
  711. } else {
  712. if (fullAlpha == 0xFF && !noRealBlitter) {
  713. // Real blitter is faster than RunBasedAdditiveBlitter
  714. blitter->getRealBlitter()->blitAntiH(L, y, alphas, runs);
  715. } else {
  716. blitter->blitAntiH(L, y, alphas, len);
  717. }
  718. }
  719. if (len > kQuickLen) {
  720. delete[] alphas;
  721. }
  722. }
  723. static SK_ALWAYS_INLINE void blit_trapezoid_row(AdditiveBlitter* blitter,
  724. int y,
  725. SkFixed ul,
  726. SkFixed ur,
  727. SkFixed ll,
  728. SkFixed lr,
  729. SkFixed lDY,
  730. SkFixed rDY,
  731. SkAlpha fullAlpha,
  732. SkAlpha* maskRow,
  733. bool isUsingMask,
  734. bool noRealBlitter = false,
  735. bool needSafeCheck = false) {
  736. SkASSERT(lDY >= 0 && rDY >= 0); // We should only send in the absolte value
  737. if (ul > ur) {
  738. return;
  739. }
  740. // Edge crosses. Approximate it. This should only happend due to precision limit,
  741. // so the approximation could be very coarse.
  742. if (ll > lr) {
  743. ll = lr = approximate_intersection(ul, ll, ur, lr);
  744. }
  745. if (ul == ur && ll == lr) {
  746. return; // empty trapzoid
  747. }
  748. // We're going to use the left line ul-ll and the rite line ur-lr
  749. // to exclude the area that's not covered by the path.
  750. // Swapping (ul, ll) or (ur, lr) won't affect that exclusion
  751. // so we'll do that for simplicity.
  752. if (ul > ll) {
  753. std::swap(ul, ll);
  754. }
  755. if (ur > lr) {
  756. std::swap(ur, lr);
  757. }
  758. SkFixed joinLeft = SkFixedCeilToFixed(ll);
  759. SkFixed joinRite = SkFixedFloorToFixed(ur);
  760. if (joinLeft <= joinRite) { // There's a rect from joinLeft to joinRite that we can blit
  761. if (ul < joinLeft) {
  762. int len = SkFixedCeilToInt(joinLeft - ul);
  763. if (len == 1) {
  764. SkAlpha alpha = trapezoid_to_alpha(joinLeft - ul, joinLeft - ll);
  765. blit_single_alpha(blitter,
  766. y,
  767. ul >> 16,
  768. alpha,
  769. fullAlpha,
  770. maskRow,
  771. isUsingMask,
  772. noRealBlitter,
  773. needSafeCheck);
  774. } else if (len == 2) {
  775. SkFixed first = joinLeft - SK_Fixed1 - ul;
  776. SkFixed second = ll - ul - first;
  777. SkAlpha a1 = partial_triangle_to_alpha(first, lDY);
  778. SkAlpha a2 = fullAlpha - partial_triangle_to_alpha(second, lDY);
  779. blit_two_alphas(blitter,
  780. y,
  781. ul >> 16,
  782. a1,
  783. a2,
  784. fullAlpha,
  785. maskRow,
  786. isUsingMask,
  787. noRealBlitter,
  788. needSafeCheck);
  789. } else {
  790. blit_aaa_trapezoid_row(blitter,
  791. y,
  792. ul,
  793. joinLeft,
  794. ll,
  795. joinLeft,
  796. lDY,
  797. SK_MaxS32,
  798. fullAlpha,
  799. maskRow,
  800. isUsingMask,
  801. noRealBlitter,
  802. needSafeCheck);
  803. }
  804. }
  805. // SkAAClip requires that we blit from left to right.
  806. // Hence we must blit [ul, joinLeft] before blitting [joinLeft, joinRite]
  807. if (joinLeft < joinRite) {
  808. blit_full_alpha(blitter,
  809. y,
  810. SkFixedFloorToInt(joinLeft),
  811. SkFixedFloorToInt(joinRite - joinLeft),
  812. fullAlpha,
  813. maskRow,
  814. isUsingMask,
  815. noRealBlitter,
  816. needSafeCheck);
  817. }
  818. if (lr > joinRite) {
  819. int len = SkFixedCeilToInt(lr - joinRite);
  820. if (len == 1) {
  821. SkAlpha alpha = trapezoid_to_alpha(ur - joinRite, lr - joinRite);
  822. blit_single_alpha(blitter,
  823. y,
  824. joinRite >> 16,
  825. alpha,
  826. fullAlpha,
  827. maskRow,
  828. isUsingMask,
  829. noRealBlitter,
  830. needSafeCheck);
  831. } else if (len == 2) {
  832. SkFixed first = joinRite + SK_Fixed1 - ur;
  833. SkFixed second = lr - ur - first;
  834. SkAlpha a1 = fullAlpha - partial_triangle_to_alpha(first, rDY);
  835. SkAlpha a2 = partial_triangle_to_alpha(second, rDY);
  836. blit_two_alphas(blitter,
  837. y,
  838. joinRite >> 16,
  839. a1,
  840. a2,
  841. fullAlpha,
  842. maskRow,
  843. isUsingMask,
  844. noRealBlitter,
  845. needSafeCheck);
  846. } else {
  847. blit_aaa_trapezoid_row(blitter,
  848. y,
  849. joinRite,
  850. ur,
  851. joinRite,
  852. lr,
  853. SK_MaxS32,
  854. rDY,
  855. fullAlpha,
  856. maskRow,
  857. isUsingMask,
  858. noRealBlitter,
  859. needSafeCheck);
  860. }
  861. }
  862. } else {
  863. blit_aaa_trapezoid_row(blitter,
  864. y,
  865. ul,
  866. ur,
  867. ll,
  868. lr,
  869. lDY,
  870. rDY,
  871. fullAlpha,
  872. maskRow,
  873. isUsingMask,
  874. noRealBlitter,
  875. needSafeCheck);
  876. }
  877. }
  878. static bool operator<(const SkAnalyticEdge& a, const SkAnalyticEdge& b) {
  879. int valuea = a.fUpperY;
  880. int valueb = b.fUpperY;
  881. if (valuea == valueb) {
  882. valuea = a.fX;
  883. valueb = b.fX;
  884. }
  885. if (valuea == valueb) {
  886. valuea = a.fDX;
  887. valueb = b.fDX;
  888. }
  889. return valuea < valueb;
  890. }
  891. static SkAnalyticEdge* sort_edges(SkAnalyticEdge* list[], int count, SkAnalyticEdge** last) {
  892. SkTQSort(list, list + count - 1);
  893. // now make the edges linked in sorted order
  894. for (int i = 1; i < count; ++i) {
  895. list[i - 1]->fNext = list[i];
  896. list[i]->fPrev = list[i - 1];
  897. }
  898. *last = list[count - 1];
  899. return list[0];
  900. }
  901. static void validate_sort(const SkAnalyticEdge* edge) {
  902. #ifdef SK_DEBUG
  903. SkFixed y = SkIntToFixed(-32768);
  904. while (edge->fUpperY != SK_MaxS32) {
  905. edge->validate();
  906. SkASSERT(y <= edge->fUpperY);
  907. y = edge->fUpperY;
  908. edge = (SkAnalyticEdge*)edge->fNext;
  909. }
  910. #endif
  911. }
  912. // For an edge, we consider it smooth if the Dx doesn't change much, and Dy is large enough
  913. // For curves that are updating, the Dx is not changing much if fQDx/fCDx and fQDy/fCDy are
  914. // relatively large compared to fQDDx/QCDDx and fQDDy/fCDDy
  915. static bool is_smooth_enough(SkAnalyticEdge* thisEdge, SkAnalyticEdge* nextEdge, int stop_y) {
  916. if (thisEdge->fCurveCount < 0) {
  917. const SkCubicEdge& cEdge = static_cast<SkAnalyticCubicEdge*>(thisEdge)->fCEdge;
  918. int ddshift = cEdge.fCurveShift;
  919. return SkAbs32(cEdge.fCDx) >> 1 >= SkAbs32(cEdge.fCDDx) >> ddshift &&
  920. SkAbs32(cEdge.fCDy) >> 1 >= SkAbs32(cEdge.fCDDy) >> ddshift &&
  921. // current Dy is (fCDy - (fCDDy >> ddshift)) >> dshift
  922. (cEdge.fCDy - (cEdge.fCDDy >> ddshift)) >> cEdge.fCubicDShift >= SK_Fixed1;
  923. } else if (thisEdge->fCurveCount > 0) {
  924. const SkQuadraticEdge& qEdge = static_cast<SkAnalyticQuadraticEdge*>(thisEdge)->fQEdge;
  925. return SkAbs32(qEdge.fQDx) >> 1 >= SkAbs32(qEdge.fQDDx) &&
  926. SkAbs32(qEdge.fQDy) >> 1 >= SkAbs32(qEdge.fQDDy) &&
  927. // current Dy is (fQDy - fQDDy) >> shift
  928. (qEdge.fQDy - qEdge.fQDDy) >> qEdge.fCurveShift >= SK_Fixed1;
  929. }
  930. return SkAbs32(nextEdge->fDX - thisEdge->fDX) <= SK_Fixed1 && // DDx should be small
  931. nextEdge->fLowerY - nextEdge->fUpperY >= SK_Fixed1; // Dy should be large
  932. }
  933. // Check if the leftE and riteE are changing smoothly in terms of fDX.
  934. // If yes, we can later skip the fractional y and directly jump to integer y.
  935. static bool is_smooth_enough(SkAnalyticEdge* leftE,
  936. SkAnalyticEdge* riteE,
  937. SkAnalyticEdge* currE,
  938. int stop_y) {
  939. if (currE->fUpperY >= SkLeftShift(stop_y, 16)) {
  940. return false; // We're at the end so we won't skip anything
  941. }
  942. if (leftE->fLowerY + SK_Fixed1 < riteE->fLowerY) {
  943. return is_smooth_enough(leftE, currE, stop_y); // Only leftE is changing
  944. } else if (leftE->fLowerY > riteE->fLowerY + SK_Fixed1) {
  945. return is_smooth_enough(riteE, currE, stop_y); // Only riteE is changing
  946. }
  947. // Now both edges are changing, find the second next edge
  948. SkAnalyticEdge* nextCurrE = currE->fNext;
  949. if (nextCurrE->fUpperY >= stop_y << 16) { // Check if we're at the end
  950. return false;
  951. }
  952. // Ensure that currE is the next left edge and nextCurrE is the next right edge. Swap if not.
  953. if (nextCurrE->fUpperX < currE->fUpperX) {
  954. std::swap(currE, nextCurrE);
  955. }
  956. return is_smooth_enough(leftE, currE, stop_y) && is_smooth_enough(riteE, nextCurrE, stop_y);
  957. }
  958. static void aaa_walk_convex_edges(SkAnalyticEdge* prevHead,
  959. AdditiveBlitter* blitter,
  960. int start_y,
  961. int stop_y,
  962. SkFixed leftBound,
  963. SkFixed riteBound,
  964. bool isUsingMask) {
  965. validate_sort((SkAnalyticEdge*)prevHead->fNext);
  966. SkAnalyticEdge* leftE = (SkAnalyticEdge*)prevHead->fNext;
  967. SkAnalyticEdge* riteE = (SkAnalyticEdge*)leftE->fNext;
  968. SkAnalyticEdge* currE = (SkAnalyticEdge*)riteE->fNext;
  969. SkFixed y = SkTMax(leftE->fUpperY, riteE->fUpperY);
  970. for (;;) {
  971. // We have to check fLowerY first because some edges might be alone (e.g., there's only
  972. // a left edge but no right edge in a given y scan line) due to precision limit.
  973. while (leftE->fLowerY <= y) { // Due to smooth jump, we may pass multiple short edges
  974. if (!leftE->update(y)) {
  975. if (SkFixedFloorToInt(currE->fUpperY) >= stop_y) {
  976. goto END_WALK;
  977. }
  978. leftE = currE;
  979. currE = (SkAnalyticEdge*)currE->fNext;
  980. }
  981. }
  982. while (riteE->fLowerY <= y) { // Due to smooth jump, we may pass multiple short edges
  983. if (!riteE->update(y)) {
  984. if (SkFixedFloorToInt(currE->fUpperY) >= stop_y) {
  985. goto END_WALK;
  986. }
  987. riteE = currE;
  988. currE = (SkAnalyticEdge*)currE->fNext;
  989. }
  990. }
  991. SkASSERT(leftE);
  992. SkASSERT(riteE);
  993. // check our bottom clip
  994. if (SkFixedFloorToInt(y) >= stop_y) {
  995. break;
  996. }
  997. SkASSERT(SkFixedFloorToInt(leftE->fUpperY) <= stop_y);
  998. SkASSERT(SkFixedFloorToInt(riteE->fUpperY) <= stop_y);
  999. leftE->goY(y);
  1000. riteE->goY(y);
  1001. if (leftE->fX > riteE->fX || (leftE->fX == riteE->fX && leftE->fDX > riteE->fDX)) {
  1002. std::swap(leftE, riteE);
  1003. }
  1004. SkFixed local_bot_fixed = SkMin32(leftE->fLowerY, riteE->fLowerY);
  1005. if (is_smooth_enough(leftE, riteE, currE, stop_y)) {
  1006. local_bot_fixed = SkFixedCeilToFixed(local_bot_fixed);
  1007. }
  1008. local_bot_fixed = SkMin32(local_bot_fixed, SkIntToFixed(stop_y));
  1009. SkFixed left = SkTMax(leftBound, leftE->fX);
  1010. SkFixed dLeft = leftE->fDX;
  1011. SkFixed rite = SkTMin(riteBound, riteE->fX);
  1012. SkFixed dRite = riteE->fDX;
  1013. if (0 == (dLeft | dRite)) {
  1014. int fullLeft = SkFixedCeilToInt(left);
  1015. int fullRite = SkFixedFloorToInt(rite);
  1016. SkFixed partialLeft = SkIntToFixed(fullLeft) - left;
  1017. SkFixed partialRite = rite - SkIntToFixed(fullRite);
  1018. int fullTop = SkFixedCeilToInt(y);
  1019. int fullBot = SkFixedFloorToInt(local_bot_fixed);
  1020. SkFixed partialTop = SkIntToFixed(fullTop) - y;
  1021. SkFixed partialBot = local_bot_fixed - SkIntToFixed(fullBot);
  1022. if (fullTop > fullBot) { // The rectangle is within one pixel height...
  1023. partialTop -= (SK_Fixed1 - partialBot);
  1024. partialBot = 0;
  1025. }
  1026. if (fullRite >= fullLeft) {
  1027. if (partialTop > 0) { // blit first partial row
  1028. if (partialLeft > 0) {
  1029. blitter->blitAntiH(fullLeft - 1,
  1030. fullTop - 1,
  1031. fixed_to_alpha(SkFixedMul(partialTop, partialLeft)));
  1032. }
  1033. blitter->blitAntiH(
  1034. fullLeft, fullTop - 1, fullRite - fullLeft, fixed_to_alpha(partialTop));
  1035. if (partialRite > 0) {
  1036. blitter->blitAntiH(fullRite,
  1037. fullTop - 1,
  1038. fixed_to_alpha(SkFixedMul(partialTop, partialRite)));
  1039. }
  1040. blitter->flush_if_y_changed(y, y + partialTop);
  1041. }
  1042. // Blit all full-height rows from fullTop to fullBot
  1043. if (fullBot > fullTop &&
  1044. // SkAAClip cannot handle the empty rect so check the non-emptiness here
  1045. // (bug chromium:662800)
  1046. (fullRite > fullLeft || fixed_to_alpha(partialLeft) > 0 ||
  1047. fixed_to_alpha(partialRite) > 0)) {
  1048. blitter->getRealBlitter()->blitAntiRect(fullLeft - 1,
  1049. fullTop,
  1050. fullRite - fullLeft,
  1051. fullBot - fullTop,
  1052. fixed_to_alpha(partialLeft),
  1053. fixed_to_alpha(partialRite));
  1054. }
  1055. if (partialBot > 0) { // blit last partial row
  1056. if (partialLeft > 0) {
  1057. blitter->blitAntiH(fullLeft - 1,
  1058. fullBot,
  1059. fixed_to_alpha(SkFixedMul(partialBot, partialLeft)));
  1060. }
  1061. blitter->blitAntiH(
  1062. fullLeft, fullBot, fullRite - fullLeft, fixed_to_alpha(partialBot));
  1063. if (partialRite > 0) {
  1064. blitter->blitAntiH(fullRite,
  1065. fullBot,
  1066. fixed_to_alpha(SkFixedMul(partialBot, partialRite)));
  1067. }
  1068. }
  1069. } else { // left and rite are within the same pixel
  1070. if (partialTop > 0) {
  1071. blitter->blitAntiH(fullLeft - 1,
  1072. fullTop - 1,
  1073. 1,
  1074. fixed_to_alpha(SkFixedMul(partialTop, rite - left)));
  1075. blitter->flush_if_y_changed(y, y + partialTop);
  1076. }
  1077. if (fullBot > fullTop) {
  1078. blitter->getRealBlitter()->blitV(
  1079. fullLeft - 1, fullTop, fullBot - fullTop, fixed_to_alpha(rite - left));
  1080. }
  1081. if (partialBot > 0) {
  1082. blitter->blitAntiH(fullLeft - 1,
  1083. fullBot,
  1084. 1,
  1085. fixed_to_alpha(SkFixedMul(partialBot, rite - left)));
  1086. }
  1087. }
  1088. y = local_bot_fixed;
  1089. } else {
  1090. // The following constant are used to snap X
  1091. // We snap X mainly for speedup (no tiny triangle) and
  1092. // avoiding edge cases caused by precision errors
  1093. const SkFixed kSnapDigit = SK_Fixed1 >> 4;
  1094. const SkFixed kSnapHalf = kSnapDigit >> 1;
  1095. const SkFixed kSnapMask = (-1 ^ (kSnapDigit - 1));
  1096. left += kSnapHalf;
  1097. rite += kSnapHalf; // For fast rounding
  1098. // Number of blit_trapezoid_row calls we'll have
  1099. int count = SkFixedCeilToInt(local_bot_fixed) - SkFixedFloorToInt(y);
  1100. // If we're using mask blitter, we advance the mask row in this function
  1101. // to save some "if" condition checks.
  1102. SkAlpha* maskRow = nullptr;
  1103. if (isUsingMask) {
  1104. maskRow = static_cast<MaskAdditiveBlitter*>(blitter)->getRow(y >> 16);
  1105. }
  1106. // Instead of writing one loop that handles both partial-row blit_trapezoid_row
  1107. // and full-row trapezoid_row together, we use the following 3-stage flow to
  1108. // handle partial-row blit and full-row blit separately. It will save us much time
  1109. // on changing y, left, and rite.
  1110. if (count > 1) {
  1111. if ((int)(y & 0xFFFF0000) != y) { // There's a partial-row on the top
  1112. count--;
  1113. SkFixed nextY = SkFixedCeilToFixed(y + 1);
  1114. SkFixed dY = nextY - y;
  1115. SkFixed nextLeft = left + SkFixedMul(dLeft, dY);
  1116. SkFixed nextRite = rite + SkFixedMul(dRite, dY);
  1117. SkASSERT((left & kSnapMask) >= leftBound && (rite & kSnapMask) <= riteBound &&
  1118. (nextLeft & kSnapMask) >= leftBound &&
  1119. (nextRite & kSnapMask) <= riteBound);
  1120. blit_trapezoid_row(blitter,
  1121. y >> 16,
  1122. left & kSnapMask,
  1123. rite & kSnapMask,
  1124. nextLeft & kSnapMask,
  1125. nextRite & kSnapMask,
  1126. leftE->fDY,
  1127. riteE->fDY,
  1128. get_partial_alpha(0xFF, dY),
  1129. maskRow,
  1130. isUsingMask);
  1131. blitter->flush_if_y_changed(y, nextY);
  1132. left = nextLeft;
  1133. rite = nextRite;
  1134. y = nextY;
  1135. }
  1136. while (count > 1) { // Full rows in the middle
  1137. count--;
  1138. if (isUsingMask) {
  1139. maskRow = static_cast<MaskAdditiveBlitter*>(blitter)->getRow(y >> 16);
  1140. }
  1141. SkFixed nextY = y + SK_Fixed1, nextLeft = left + dLeft, nextRite = rite + dRite;
  1142. SkASSERT((left & kSnapMask) >= leftBound && (rite & kSnapMask) <= riteBound &&
  1143. (nextLeft & kSnapMask) >= leftBound &&
  1144. (nextRite & kSnapMask) <= riteBound);
  1145. blit_trapezoid_row(blitter,
  1146. y >> 16,
  1147. left & kSnapMask,
  1148. rite & kSnapMask,
  1149. nextLeft & kSnapMask,
  1150. nextRite & kSnapMask,
  1151. leftE->fDY,
  1152. riteE->fDY,
  1153. 0xFF,
  1154. maskRow,
  1155. isUsingMask);
  1156. blitter->flush_if_y_changed(y, nextY);
  1157. left = nextLeft;
  1158. rite = nextRite;
  1159. y = nextY;
  1160. }
  1161. }
  1162. if (isUsingMask) {
  1163. maskRow = static_cast<MaskAdditiveBlitter*>(blitter)->getRow(y >> 16);
  1164. }
  1165. SkFixed dY = local_bot_fixed - y; // partial-row on the bottom
  1166. SkASSERT(dY <= SK_Fixed1);
  1167. // Smooth jumping to integer y may make the last nextLeft/nextRite out of bound.
  1168. // Take them back into the bound here.
  1169. // Note that we substract kSnapHalf later so we have to add them to leftBound/riteBound
  1170. SkFixed nextLeft = SkTMax(left + SkFixedMul(dLeft, dY), leftBound + kSnapHalf);
  1171. SkFixed nextRite = SkTMin(rite + SkFixedMul(dRite, dY), riteBound + kSnapHalf);
  1172. SkASSERT((left & kSnapMask) >= leftBound && (rite & kSnapMask) <= riteBound &&
  1173. (nextLeft & kSnapMask) >= leftBound && (nextRite & kSnapMask) <= riteBound);
  1174. blit_trapezoid_row(blitter,
  1175. y >> 16,
  1176. left & kSnapMask,
  1177. rite & kSnapMask,
  1178. nextLeft & kSnapMask,
  1179. nextRite & kSnapMask,
  1180. leftE->fDY,
  1181. riteE->fDY,
  1182. get_partial_alpha(0xFF, dY),
  1183. maskRow,
  1184. isUsingMask);
  1185. blitter->flush_if_y_changed(y, local_bot_fixed);
  1186. left = nextLeft;
  1187. rite = nextRite;
  1188. y = local_bot_fixed;
  1189. left -= kSnapHalf;
  1190. rite -= kSnapHalf;
  1191. }
  1192. leftE->fX = left;
  1193. riteE->fX = rite;
  1194. leftE->fY = riteE->fY = y;
  1195. }
  1196. END_WALK:;
  1197. }
  1198. static void update_next_next_y(SkFixed y, SkFixed nextY, SkFixed* nextNextY) {
  1199. *nextNextY = y > nextY && y < *nextNextY ? y : *nextNextY;
  1200. }
  1201. static void check_intersection(const SkAnalyticEdge* edge, SkFixed nextY, SkFixed* nextNextY) {
  1202. if (edge->fPrev->fPrev && edge->fPrev->fX + edge->fPrev->fDX > edge->fX + edge->fDX) {
  1203. *nextNextY = nextY + (SK_Fixed1 >> SkAnalyticEdge::kDefaultAccuracy);
  1204. }
  1205. }
  1206. static void insert_new_edges(SkAnalyticEdge* newEdge, SkFixed y, SkFixed* nextNextY) {
  1207. if (newEdge->fUpperY > y) {
  1208. update_next_next_y(newEdge->fUpperY, y, nextNextY);
  1209. return;
  1210. }
  1211. SkAnalyticEdge* prev = newEdge->fPrev;
  1212. if (prev->fX <= newEdge->fX) {
  1213. while (newEdge->fUpperY <= y) {
  1214. check_intersection(newEdge, y, nextNextY);
  1215. update_next_next_y(newEdge->fLowerY, y, nextNextY);
  1216. newEdge = newEdge->fNext;
  1217. }
  1218. update_next_next_y(newEdge->fUpperY, y, nextNextY);
  1219. return;
  1220. }
  1221. // find first x pos to insert
  1222. SkAnalyticEdge* start = backward_insert_start(prev, newEdge->fX);
  1223. // insert the lot, fixing up the links as we go
  1224. do {
  1225. SkAnalyticEdge* next = newEdge->fNext;
  1226. do {
  1227. if (start->fNext == newEdge) {
  1228. goto nextEdge;
  1229. }
  1230. SkAnalyticEdge* after = start->fNext;
  1231. if (after->fX >= newEdge->fX) {
  1232. break;
  1233. }
  1234. SkASSERT(start != after);
  1235. start = after;
  1236. } while (true);
  1237. remove_edge(newEdge);
  1238. insert_edge_after(newEdge, start);
  1239. nextEdge:
  1240. check_intersection(newEdge, y, nextNextY);
  1241. update_next_next_y(newEdge->fLowerY, y, nextNextY);
  1242. start = newEdge;
  1243. newEdge = next;
  1244. } while (newEdge->fUpperY <= y);
  1245. update_next_next_y(newEdge->fUpperY, y, nextNextY);
  1246. }
  1247. static void validate_edges_for_y(const SkAnalyticEdge* edge, SkFixed y) {
  1248. #ifdef SK_DEBUG
  1249. while (edge->fUpperY <= y) {
  1250. SkASSERT(edge->fPrev && edge->fNext);
  1251. SkASSERT(edge->fPrev->fNext == edge);
  1252. SkASSERT(edge->fNext->fPrev == edge);
  1253. SkASSERT(edge->fUpperY <= edge->fLowerY);
  1254. SkASSERT(edge->fPrev->fPrev == nullptr || edge->fPrev->fX <= edge->fX);
  1255. edge = edge->fNext;
  1256. }
  1257. #endif
  1258. }
  1259. // Return true if prev->fX, next->fX are too close in the current pixel row.
  1260. static bool edges_too_close(SkAnalyticEdge* prev, SkAnalyticEdge* next, SkFixed lowerY) {
  1261. // When next->fDX == 0, prev->fX >= next->fX - SkAbs32(next->fDX) would be false
  1262. // even if prev->fX and next->fX are close and within one pixel (e.g., prev->fX == 0.1,
  1263. // next->fX == 0.9). Adding SLACK = 1 to the formula would guarantee it to be true if two
  1264. // edges prev and next are within one pixel.
  1265. constexpr SkFixed SLACK = SK_Fixed1;
  1266. // Note that even if the following test failed, the edges might still be very close to each
  1267. // other at some point within the current pixel row because of prev->fDX and next->fDX.
  1268. // However, to handle that case, we have to sacrafice more performance.
  1269. // I think the current quality is good enough (mainly by looking at Nebraska-StateSeal.svg)
  1270. // so I'll ignore fDX for performance tradeoff.
  1271. return next && prev && next->fUpperY < lowerY &&
  1272. prev->fX + SLACK >= next->fX - SkAbs32(next->fDX);
  1273. // The following is more accurate but also slower.
  1274. // return (prev && prev->fPrev && next && next->fNext != nullptr && next->fUpperY < lowerY &&
  1275. // prev->fX + SkAbs32(prev->fDX) + SLACK >= next->fX - SkAbs32(next->fDX));
  1276. }
  1277. // This function exists for the case where the previous rite edge is removed because
  1278. // its fLowerY <= nextY
  1279. static bool edges_too_close(int prevRite, SkFixed ul, SkFixed ll) {
  1280. return prevRite > SkFixedFloorToInt(ul) || prevRite > SkFixedFloorToInt(ll);
  1281. }
  1282. static void blit_saved_trapezoid(SkAnalyticEdge* leftE,
  1283. SkFixed lowerY,
  1284. SkFixed lowerLeft,
  1285. SkFixed lowerRite,
  1286. AdditiveBlitter* blitter,
  1287. SkAlpha* maskRow,
  1288. bool isUsingMask,
  1289. bool noRealBlitter,
  1290. SkFixed leftClip,
  1291. SkFixed rightClip) {
  1292. SkAnalyticEdge* riteE = leftE->fRiteE;
  1293. SkASSERT(riteE);
  1294. SkASSERT(riteE->fNext == nullptr || leftE->fSavedY == riteE->fSavedY);
  1295. SkASSERT(SkFixedFloorToInt(lowerY - 1) == SkFixedFloorToInt(leftE->fSavedY));
  1296. int y = SkFixedFloorToInt(leftE->fSavedY);
  1297. // Instead of using fixed_to_alpha(lowerY - leftE->fSavedY), we use the following fullAlpha
  1298. // to elimiate cumulative error: if there are many fractional y scan lines within the
  1299. // same row, the former may accumulate the rounding error while the later won't.
  1300. SkAlpha fullAlpha = fixed_to_alpha(lowerY - SkIntToFixed(y)) -
  1301. fixed_to_alpha(leftE->fSavedY - SkIntToFixed(y));
  1302. // We need fSavedDY because the (quad or cubic) edge might be updated
  1303. blit_trapezoid_row(
  1304. blitter,
  1305. y,
  1306. SkTMax(leftE->fSavedX, leftClip),
  1307. SkTMin(riteE->fSavedX, rightClip),
  1308. SkTMax(lowerLeft, leftClip),
  1309. SkTMin(lowerRite, rightClip),
  1310. leftE->fSavedDY,
  1311. riteE->fSavedDY,
  1312. fullAlpha,
  1313. maskRow,
  1314. isUsingMask,
  1315. noRealBlitter || (fullAlpha == 0xFF && (edges_too_close(leftE->fPrev, leftE, lowerY) ||
  1316. edges_too_close(riteE, riteE->fNext, lowerY))),
  1317. true);
  1318. leftE->fRiteE = nullptr;
  1319. }
  1320. static void deferred_blit(SkAnalyticEdge* leftE,
  1321. SkAnalyticEdge* riteE,
  1322. SkFixed left,
  1323. SkFixed leftDY, // don't save leftE->fX/fDY as they may have been updated
  1324. SkFixed y,
  1325. SkFixed nextY,
  1326. bool isIntegralNextY,
  1327. bool leftEnds,
  1328. bool riteEnds,
  1329. AdditiveBlitter* blitter,
  1330. SkAlpha* maskRow,
  1331. bool isUsingMask,
  1332. bool noRealBlitter,
  1333. SkFixed leftClip,
  1334. SkFixed rightClip,
  1335. int yShift) {
  1336. if (leftE->fRiteE && leftE->fRiteE != riteE) {
  1337. // leftE's right edge changed. Blit the saved trapezoid.
  1338. SkASSERT(leftE->fRiteE->fNext == nullptr || leftE->fRiteE->fY == y);
  1339. blit_saved_trapezoid(leftE,
  1340. y,
  1341. left,
  1342. leftE->fRiteE->fX,
  1343. blitter,
  1344. maskRow,
  1345. isUsingMask,
  1346. noRealBlitter,
  1347. leftClip,
  1348. rightClip);
  1349. }
  1350. if (!leftE->fRiteE) {
  1351. // Save and defer blitting the trapezoid
  1352. SkASSERT(riteE->fRiteE == nullptr);
  1353. SkASSERT(leftE->fPrev == nullptr || leftE->fY == nextY);
  1354. SkASSERT(riteE->fNext == nullptr || riteE->fY == y);
  1355. leftE->saveXY(left, y, leftDY);
  1356. riteE->saveXY(riteE->fX, y, riteE->fDY);
  1357. leftE->fRiteE = riteE;
  1358. }
  1359. SkASSERT(leftE->fPrev == nullptr || leftE->fY == nextY);
  1360. riteE->goY(nextY, yShift);
  1361. // Always blit when edges end or nextY is integral
  1362. if (isIntegralNextY || leftEnds || riteEnds) {
  1363. blit_saved_trapezoid(leftE,
  1364. nextY,
  1365. leftE->fX,
  1366. riteE->fX,
  1367. blitter,
  1368. maskRow,
  1369. isUsingMask,
  1370. noRealBlitter,
  1371. leftClip,
  1372. rightClip);
  1373. }
  1374. }
  1375. static void aaa_walk_edges(SkAnalyticEdge* prevHead,
  1376. SkAnalyticEdge* nextTail,
  1377. SkPath::FillType fillType,
  1378. AdditiveBlitter* blitter,
  1379. int start_y,
  1380. int stop_y,
  1381. SkFixed leftClip,
  1382. SkFixed rightClip,
  1383. bool isUsingMask,
  1384. bool forceRLE,
  1385. bool useDeferred,
  1386. bool skipIntersect) {
  1387. prevHead->fX = prevHead->fUpperX = leftClip;
  1388. nextTail->fX = nextTail->fUpperX = rightClip;
  1389. SkFixed y = SkTMax(prevHead->fNext->fUpperY, SkIntToFixed(start_y));
  1390. SkFixed nextNextY = SK_MaxS32;
  1391. {
  1392. SkAnalyticEdge* edge;
  1393. for (edge = prevHead->fNext; edge->fUpperY <= y; edge = edge->fNext) {
  1394. edge->goY(y);
  1395. update_next_next_y(edge->fLowerY, y, &nextNextY);
  1396. }
  1397. update_next_next_y(edge->fUpperY, y, &nextNextY);
  1398. }
  1399. // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
  1400. int windingMask = (fillType & 1) ? 1 : -1;
  1401. bool isInverse = SkPath::IsInverseFillType(fillType);
  1402. if (isInverse && SkIntToFixed(start_y) != y) {
  1403. int width = SkFixedFloorToInt(rightClip - leftClip);
  1404. if (SkFixedFloorToInt(y) != start_y) {
  1405. blitter->getRealBlitter()->blitRect(
  1406. SkFixedFloorToInt(leftClip), start_y, width, SkFixedFloorToInt(y) - start_y);
  1407. start_y = SkFixedFloorToInt(y);
  1408. }
  1409. SkAlpha* maskRow =
  1410. isUsingMask ? static_cast<MaskAdditiveBlitter*>(blitter)->getRow(start_y) : nullptr;
  1411. blit_full_alpha(blitter,
  1412. start_y,
  1413. SkFixedFloorToInt(leftClip),
  1414. width,
  1415. fixed_to_alpha(y - SkIntToFixed(start_y)),
  1416. maskRow,
  1417. isUsingMask,
  1418. false,
  1419. false);
  1420. }
  1421. while (true) {
  1422. int w = 0;
  1423. bool in_interval = isInverse;
  1424. SkFixed prevX = prevHead->fX;
  1425. SkFixed nextY = SkTMin(nextNextY, SkFixedCeilToFixed(y + 1));
  1426. bool isIntegralNextY = (nextY & (SK_Fixed1 - 1)) == 0;
  1427. SkAnalyticEdge* currE = prevHead->fNext;
  1428. SkAnalyticEdge* leftE = prevHead;
  1429. SkFixed left = leftClip;
  1430. SkFixed leftDY = 0;
  1431. bool leftEnds = false;
  1432. int prevRite = SkFixedFloorToInt(leftClip);
  1433. nextNextY = SK_MaxS32;
  1434. SkASSERT((nextY & ((SK_Fixed1 >> 2) - 1)) == 0);
  1435. int yShift = 0;
  1436. if ((nextY - y) & (SK_Fixed1 >> 2)) {
  1437. yShift = 2;
  1438. nextY = y + (SK_Fixed1 >> 2);
  1439. } else if ((nextY - y) & (SK_Fixed1 >> 1)) {
  1440. yShift = 1;
  1441. SkASSERT(nextY == y + (SK_Fixed1 >> 1));
  1442. }
  1443. SkAlpha fullAlpha = fixed_to_alpha(nextY - y);
  1444. // If we're using mask blitter, we advance the mask row in this function
  1445. // to save some "if" condition checks.
  1446. SkAlpha* maskRow = nullptr;
  1447. if (isUsingMask) {
  1448. maskRow = static_cast<MaskAdditiveBlitter*>(blitter)->getRow(SkFixedFloorToInt(y));
  1449. }
  1450. SkASSERT(currE->fPrev == prevHead);
  1451. validate_edges_for_y(currE, y);
  1452. // Even if next - y == SK_Fixed1, we can still break the left-to-right order requirement
  1453. // of the SKAAClip: |\| (two trapezoids with overlapping middle wedges)
  1454. bool noRealBlitter = forceRLE; // forceRLE && (nextY - y != SK_Fixed1);
  1455. while (currE->fUpperY <= y) {
  1456. SkASSERT(currE->fLowerY >= nextY);
  1457. SkASSERT(currE->fY == y);
  1458. w += currE->fWinding;
  1459. bool prev_in_interval = in_interval;
  1460. in_interval = !(w & windingMask) == isInverse;
  1461. bool isLeft = in_interval && !prev_in_interval;
  1462. bool isRite = !in_interval && prev_in_interval;
  1463. bool currEnds = currE->fLowerY == nextY;
  1464. if (useDeferred) {
  1465. if (currE->fRiteE && !isLeft) {
  1466. // currE is a left edge previously, but now it's not.
  1467. // Blit the trapezoid between fSavedY and y.
  1468. SkASSERT(currE->fRiteE->fY == y);
  1469. blit_saved_trapezoid(currE,
  1470. y,
  1471. currE->fX,
  1472. currE->fRiteE->fX,
  1473. blitter,
  1474. maskRow,
  1475. isUsingMask,
  1476. noRealBlitter,
  1477. leftClip,
  1478. rightClip);
  1479. }
  1480. if (leftE->fRiteE == currE && !isRite) {
  1481. // currE is a right edge previously, but now it's not.
  1482. // Moreover, its corresponding leftE doesn't change (otherwise we'll handle it
  1483. // in the previous if clause). Hence we blit the trapezoid.
  1484. blit_saved_trapezoid(leftE,
  1485. y,
  1486. left,
  1487. currE->fX,
  1488. blitter,
  1489. maskRow,
  1490. isUsingMask,
  1491. noRealBlitter,
  1492. leftClip,
  1493. rightClip);
  1494. }
  1495. }
  1496. if (isRite) {
  1497. if (useDeferred) {
  1498. deferred_blit(leftE,
  1499. currE,
  1500. left,
  1501. leftDY,
  1502. y,
  1503. nextY,
  1504. isIntegralNextY,
  1505. leftEnds,
  1506. currEnds,
  1507. blitter,
  1508. maskRow,
  1509. isUsingMask,
  1510. noRealBlitter,
  1511. leftClip,
  1512. rightClip,
  1513. yShift);
  1514. } else {
  1515. SkFixed rite = currE->fX;
  1516. currE->goY(nextY, yShift);
  1517. SkFixed nextLeft = SkTMax(leftClip, leftE->fX);
  1518. rite = SkTMin(rightClip, rite);
  1519. SkFixed nextRite = SkTMin(rightClip, currE->fX);
  1520. blit_trapezoid_row(
  1521. blitter,
  1522. y >> 16,
  1523. left,
  1524. rite,
  1525. nextLeft,
  1526. nextRite,
  1527. leftDY,
  1528. currE->fDY,
  1529. fullAlpha,
  1530. maskRow,
  1531. isUsingMask,
  1532. noRealBlitter || (fullAlpha == 0xFF &&
  1533. (edges_too_close(prevRite, left, leftE->fX) ||
  1534. edges_too_close(currE, currE->fNext, nextY))),
  1535. true);
  1536. prevRite = SkFixedCeilToInt(SkTMax(rite, currE->fX));
  1537. }
  1538. } else {
  1539. if (isLeft) {
  1540. left = SkTMax(currE->fX, leftClip);
  1541. leftDY = currE->fDY;
  1542. leftE = currE;
  1543. leftEnds = leftE->fLowerY == nextY;
  1544. }
  1545. currE->goY(nextY, yShift);
  1546. }
  1547. SkAnalyticEdge* next = currE->fNext;
  1548. SkFixed newX;
  1549. while (currE->fLowerY <= nextY) {
  1550. if (currE->fCurveCount < 0) {
  1551. SkAnalyticCubicEdge* cubicEdge = (SkAnalyticCubicEdge*)currE;
  1552. cubicEdge->keepContinuous();
  1553. if (!cubicEdge->updateCubic()) {
  1554. break;
  1555. }
  1556. } else if (currE->fCurveCount > 0) {
  1557. SkAnalyticQuadraticEdge* quadEdge = (SkAnalyticQuadraticEdge*)currE;
  1558. quadEdge->keepContinuous();
  1559. if (!quadEdge->updateQuadratic()) {
  1560. break;
  1561. }
  1562. } else {
  1563. break;
  1564. }
  1565. }
  1566. SkASSERT(currE->fY == nextY);
  1567. if (currE->fLowerY <= nextY) {
  1568. remove_edge(currE);
  1569. } else {
  1570. update_next_next_y(currE->fLowerY, nextY, &nextNextY);
  1571. newX = currE->fX;
  1572. SkASSERT(currE->fLowerY > nextY);
  1573. if (newX < prevX) { // ripple currE backwards until it is x-sorted
  1574. // If the crossing edge is a right edge, blit the saved trapezoid.
  1575. if (leftE->fRiteE == currE && useDeferred) {
  1576. SkASSERT(leftE->fY == nextY && currE->fY == nextY);
  1577. blit_saved_trapezoid(leftE,
  1578. nextY,
  1579. leftE->fX,
  1580. currE->fX,
  1581. blitter,
  1582. maskRow,
  1583. isUsingMask,
  1584. noRealBlitter,
  1585. leftClip,
  1586. rightClip);
  1587. }
  1588. backward_insert_edge_based_on_x(currE);
  1589. } else {
  1590. prevX = newX;
  1591. }
  1592. if (!skipIntersect) {
  1593. check_intersection(currE, nextY, &nextNextY);
  1594. }
  1595. }
  1596. currE = next;
  1597. SkASSERT(currE);
  1598. }
  1599. // was our right-edge culled away?
  1600. if (in_interval) {
  1601. if (useDeferred) {
  1602. deferred_blit(leftE,
  1603. nextTail,
  1604. left,
  1605. leftDY,
  1606. y,
  1607. nextY,
  1608. isIntegralNextY,
  1609. leftEnds,
  1610. false,
  1611. blitter,
  1612. maskRow,
  1613. isUsingMask,
  1614. noRealBlitter,
  1615. leftClip,
  1616. rightClip,
  1617. yShift);
  1618. } else {
  1619. blit_trapezoid_row(blitter,
  1620. y >> 16,
  1621. left,
  1622. rightClip,
  1623. SkTMax(leftClip, leftE->fX),
  1624. rightClip,
  1625. leftDY,
  1626. 0,
  1627. fullAlpha,
  1628. maskRow,
  1629. isUsingMask,
  1630. noRealBlitter || (fullAlpha == 0xFF &&
  1631. edges_too_close(leftE->fPrev, leftE, nextY)),
  1632. true);
  1633. }
  1634. }
  1635. if (forceRLE) {
  1636. ((RunBasedAdditiveBlitter*)blitter)->flush_if_y_changed(y, nextY);
  1637. }
  1638. y = nextY;
  1639. if (y >= SkIntToFixed(stop_y)) {
  1640. break;
  1641. }
  1642. // now currE points to the first edge with a fUpperY larger than the previous y
  1643. insert_new_edges(currE, y, &nextNextY);
  1644. }
  1645. }
  1646. static SK_ALWAYS_INLINE void aaa_fill_path(
  1647. const SkPath& path,
  1648. const SkIRect& clipRect,
  1649. AdditiveBlitter* blitter,
  1650. int start_y,
  1651. int stop_y,
  1652. bool pathContainedInClip,
  1653. bool isUsingMask,
  1654. bool forceRLE) { // forceRLE implies that SkAAClip is calling us
  1655. SkASSERT(blitter);
  1656. SkAnalyticEdgeBuilder builder;
  1657. int count = builder.buildEdges(path, pathContainedInClip ? nullptr : &clipRect);
  1658. SkAnalyticEdge** list = builder.analyticEdgeList();
  1659. SkIRect rect = clipRect;
  1660. if (0 == count) {
  1661. if (path.isInverseFillType()) {
  1662. /*
  1663. * Since we are in inverse-fill, our caller has already drawn above
  1664. * our top (start_y) and will draw below our bottom (stop_y). Thus
  1665. * we need to restrict our drawing to the intersection of the clip
  1666. * and those two limits.
  1667. */
  1668. if (rect.fTop < start_y) {
  1669. rect.fTop = start_y;
  1670. }
  1671. if (rect.fBottom > stop_y) {
  1672. rect.fBottom = stop_y;
  1673. }
  1674. if (!rect.isEmpty()) {
  1675. blitter->getRealBlitter()->blitRect(
  1676. rect.fLeft, rect.fTop, rect.width(), rect.height());
  1677. }
  1678. }
  1679. return;
  1680. }
  1681. SkAnalyticEdge headEdge, tailEdge, *last;
  1682. // this returns the first and last edge after they're sorted into a dlink list
  1683. SkAnalyticEdge* edge = sort_edges(list, count, &last);
  1684. headEdge.fRiteE = nullptr;
  1685. headEdge.fPrev = nullptr;
  1686. headEdge.fNext = edge;
  1687. headEdge.fUpperY = headEdge.fLowerY = SK_MinS32;
  1688. headEdge.fX = SK_MinS32;
  1689. headEdge.fDX = 0;
  1690. headEdge.fDY = SK_MaxS32;
  1691. headEdge.fUpperX = SK_MinS32;
  1692. edge->fPrev = &headEdge;
  1693. tailEdge.fRiteE = nullptr;
  1694. tailEdge.fPrev = last;
  1695. tailEdge.fNext = nullptr;
  1696. tailEdge.fUpperY = tailEdge.fLowerY = SK_MaxS32;
  1697. tailEdge.fX = SK_MaxS32;
  1698. tailEdge.fDX = 0;
  1699. tailEdge.fDY = SK_MaxS32;
  1700. tailEdge.fUpperX = SK_MaxS32;
  1701. last->fNext = &tailEdge;
  1702. // now edge is the head of the sorted linklist
  1703. if (!pathContainedInClip && start_y < clipRect.fTop) {
  1704. start_y = clipRect.fTop;
  1705. }
  1706. if (!pathContainedInClip && stop_y > clipRect.fBottom) {
  1707. stop_y = clipRect.fBottom;
  1708. }
  1709. SkFixed leftBound = SkIntToFixed(rect.fLeft);
  1710. SkFixed rightBound = SkIntToFixed(rect.fRight);
  1711. if (isUsingMask) {
  1712. // If we're using mask, then we have to limit the bound within the path bounds.
  1713. // Otherwise, the edge drift may access an invalid address inside the mask.
  1714. SkIRect ir;
  1715. path.getBounds().roundOut(&ir);
  1716. leftBound = SkTMax(leftBound, SkIntToFixed(ir.fLeft));
  1717. rightBound = SkTMin(rightBound, SkIntToFixed(ir.fRight));
  1718. }
  1719. if (!path.isInverseFillType() && path.isConvex() && count >= 2) {
  1720. aaa_walk_convex_edges(
  1721. &headEdge, blitter, start_y, stop_y, leftBound, rightBound, isUsingMask);
  1722. } else {
  1723. // Only use deferred blitting if there are many edges.
  1724. bool useDeferred =
  1725. count >
  1726. (SkFixedFloorToInt(tailEdge.fPrev->fLowerY - headEdge.fNext->fUpperY) + 1) * 4;
  1727. // We skip intersection computation if there are many points which probably already
  1728. // give us enough fractional scan lines.
  1729. bool skipIntersect = path.countPoints() > (stop_y - start_y) * 2;
  1730. aaa_walk_edges(&headEdge,
  1731. &tailEdge,
  1732. path.getFillType(),
  1733. blitter,
  1734. start_y,
  1735. stop_y,
  1736. leftBound,
  1737. rightBound,
  1738. isUsingMask,
  1739. forceRLE,
  1740. useDeferred,
  1741. skipIntersect);
  1742. }
  1743. }
  1744. void SkScan::AAAFillPath(const SkPath& path,
  1745. SkBlitter* blitter,
  1746. const SkIRect& ir,
  1747. const SkIRect& clipBounds,
  1748. bool forceRLE) {
  1749. bool containedInClip = clipBounds.contains(ir);
  1750. bool isInverse = path.isInverseFillType();
  1751. // The mask blitter (where we store intermediate alpha values directly in a mask, and then call
  1752. // the real blitter once in the end to blit the whole mask) is faster than the RLE blitter when
  1753. // the blit region is small enough (i.e., CanHandleRect(ir)). When isInverse is true, the blit
  1754. // region is no longer the rectangle ir so we won't use the mask blitter. The caller may also
  1755. // use the forceRLE flag to force not using the mask blitter. Also, when the path is a simple
  1756. // rect, preparing a mask and blitting it might have too much overhead. Hence we'll use
  1757. // blitFatAntiRect to avoid the mask and its overhead.
  1758. if (MaskAdditiveBlitter::CanHandleRect(ir) && !isInverse && !forceRLE) {
  1759. // blitFatAntiRect is slower than the normal AAA flow without MaskAdditiveBlitter.
  1760. // Hence only tryBlitFatAntiRect when MaskAdditiveBlitter would have been used.
  1761. if (!TryBlitFatAntiRect(blitter, path, clipBounds)) {
  1762. MaskAdditiveBlitter additiveBlitter(blitter, ir, clipBounds, isInverse);
  1763. aaa_fill_path(path,
  1764. clipBounds,
  1765. &additiveBlitter,
  1766. ir.fTop,
  1767. ir.fBottom,
  1768. containedInClip,
  1769. true,
  1770. forceRLE);
  1771. }
  1772. } else if (!isInverse && path.isConvex()) {
  1773. // If the filling area is convex (i.e., path.isConvex && !isInverse), our simpler
  1774. // aaa_walk_convex_edges won't generate alphas above 255. Hence we don't need
  1775. // SafeRLEAdditiveBlitter (which is slow due to clamping). The basic RLE blitter
  1776. // RunBasedAdditiveBlitter would suffice.
  1777. RunBasedAdditiveBlitter additiveBlitter(blitter, ir, clipBounds, isInverse);
  1778. aaa_fill_path(path,
  1779. clipBounds,
  1780. &additiveBlitter,
  1781. ir.fTop,
  1782. ir.fBottom,
  1783. containedInClip,
  1784. false,
  1785. forceRLE);
  1786. } else {
  1787. // If the filling area might not be convex, the more involved aaa_walk_edges would
  1788. // be called and we have to clamp the alpha downto 255. The SafeRLEAdditiveBlitter
  1789. // does that at a cost of performance.
  1790. SafeRLEAdditiveBlitter additiveBlitter(blitter, ir, clipBounds, isInverse);
  1791. aaa_fill_path(path,
  1792. clipBounds,
  1793. &additiveBlitter,
  1794. ir.fTop,
  1795. ir.fBottom,
  1796. containedInClip,
  1797. false,
  1798. forceRLE);
  1799. }
  1800. }
  1801. #endif // defined(SK_DISABLE_AAA)