SkScan_Path.cpp 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780
  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 "include/core/SkPath.h"
  8. #include "include/core/SkRegion.h"
  9. #include "include/private/SkMacros.h"
  10. #include "include/private/SkSafe32.h"
  11. #include "include/private/SkTemplates.h"
  12. #include "src/core/SkBlitter.h"
  13. #include "src/core/SkEdge.h"
  14. #include "src/core/SkEdgeBuilder.h"
  15. #include "src/core/SkGeometry.h"
  16. #include "src/core/SkQuadClipper.h"
  17. #include "src/core/SkRasterClip.h"
  18. #include "src/core/SkRectPriv.h"
  19. #include "src/core/SkScanPriv.h"
  20. #include "src/core/SkTSort.h"
  21. #include <utility>
  22. #define kEDGE_HEAD_Y SK_MinS32
  23. #define kEDGE_TAIL_Y SK_MaxS32
  24. #ifdef SK_DEBUG
  25. static void validate_sort(const SkEdge* edge) {
  26. int y = kEDGE_HEAD_Y;
  27. while (edge->fFirstY != SK_MaxS32) {
  28. edge->validate();
  29. SkASSERT(y <= edge->fFirstY);
  30. y = edge->fFirstY;
  31. edge = edge->fNext;
  32. }
  33. }
  34. #else
  35. #define validate_sort(edge)
  36. #endif
  37. static void insert_new_edges(SkEdge* newEdge, int curr_y) {
  38. if (newEdge->fFirstY != curr_y) {
  39. return;
  40. }
  41. SkEdge* prev = newEdge->fPrev;
  42. if (prev->fX <= newEdge->fX) {
  43. return;
  44. }
  45. // find first x pos to insert
  46. SkEdge* start = backward_insert_start(prev, newEdge->fX);
  47. // insert the lot, fixing up the links as we go
  48. do {
  49. SkEdge* next = newEdge->fNext;
  50. do {
  51. if (start->fNext == newEdge) {
  52. goto nextEdge;
  53. }
  54. SkEdge* after = start->fNext;
  55. if (after->fX >= newEdge->fX) {
  56. break;
  57. }
  58. start = after;
  59. } while (true);
  60. remove_edge(newEdge);
  61. insert_edge_after(newEdge, start);
  62. nextEdge:
  63. start = newEdge;
  64. newEdge = next;
  65. } while (newEdge->fFirstY == curr_y);
  66. }
  67. #ifdef SK_DEBUG
  68. static void validate_edges_for_y(const SkEdge* edge, int curr_y) {
  69. while (edge->fFirstY <= curr_y) {
  70. SkASSERT(edge->fPrev && edge->fNext);
  71. SkASSERT(edge->fPrev->fNext == edge);
  72. SkASSERT(edge->fNext->fPrev == edge);
  73. SkASSERT(edge->fFirstY <= edge->fLastY);
  74. SkASSERT(edge->fPrev->fX <= edge->fX);
  75. edge = edge->fNext;
  76. }
  77. }
  78. #else
  79. #define validate_edges_for_y(edge, curr_y)
  80. #endif
  81. #if defined _WIN32 // disable warning : local variable used without having been initialized
  82. #pragma warning ( push )
  83. #pragma warning ( disable : 4701 )
  84. #endif
  85. typedef void (*PrePostProc)(SkBlitter* blitter, int y, bool isStartOfScanline);
  86. #define PREPOST_START true
  87. #define PREPOST_END false
  88. static void walk_edges(SkEdge* prevHead, SkPath::FillType fillType,
  89. SkBlitter* blitter, int start_y, int stop_y,
  90. PrePostProc proc, int rightClip) {
  91. validate_sort(prevHead->fNext);
  92. int curr_y = start_y;
  93. // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
  94. int windingMask = (fillType & 1) ? 1 : -1;
  95. for (;;) {
  96. int w = 0;
  97. int left SK_INIT_TO_AVOID_WARNING;
  98. SkEdge* currE = prevHead->fNext;
  99. SkFixed prevX = prevHead->fX;
  100. validate_edges_for_y(currE, curr_y);
  101. if (proc) {
  102. proc(blitter, curr_y, PREPOST_START); // pre-proc
  103. }
  104. while (currE->fFirstY <= curr_y) {
  105. SkASSERT(currE->fLastY >= curr_y);
  106. int x = SkFixedRoundToInt(currE->fX);
  107. if ((w & windingMask) == 0) { // we're starting interval
  108. left = x;
  109. }
  110. w += currE->fWinding;
  111. if ((w & windingMask) == 0) { // we finished an interval
  112. int width = x - left;
  113. SkASSERT(width >= 0);
  114. if (width > 0) {
  115. blitter->blitH(left, curr_y, width);
  116. }
  117. }
  118. SkEdge* next = currE->fNext;
  119. SkFixed newX;
  120. if (currE->fLastY == curr_y) { // are we done with this edge?
  121. if (currE->fCurveCount > 0) {
  122. if (((SkQuadraticEdge*)currE)->updateQuadratic()) {
  123. newX = currE->fX;
  124. goto NEXT_X;
  125. }
  126. } else if (currE->fCurveCount < 0) {
  127. if (((SkCubicEdge*)currE)->updateCubic()) {
  128. SkASSERT(currE->fFirstY == curr_y + 1);
  129. newX = currE->fX;
  130. goto NEXT_X;
  131. }
  132. }
  133. remove_edge(currE);
  134. } else {
  135. SkASSERT(currE->fLastY > curr_y);
  136. newX = currE->fX + currE->fDX;
  137. currE->fX = newX;
  138. NEXT_X:
  139. if (newX < prevX) { // ripple currE backwards until it is x-sorted
  140. backward_insert_edge_based_on_x(currE);
  141. } else {
  142. prevX = newX;
  143. }
  144. }
  145. currE = next;
  146. SkASSERT(currE);
  147. }
  148. if ((w & windingMask) != 0) { // was our right-edge culled away?
  149. int width = rightClip - left;
  150. if (width > 0) {
  151. blitter->blitH(left, curr_y, width);
  152. }
  153. }
  154. if (proc) {
  155. proc(blitter, curr_y, PREPOST_END); // post-proc
  156. }
  157. curr_y += 1;
  158. if (curr_y >= stop_y) {
  159. break;
  160. }
  161. // now currE points to the first edge with a Yint larger than curr_y
  162. insert_new_edges(currE, curr_y);
  163. }
  164. }
  165. // return true if we're NOT done with this edge
  166. static bool update_edge(SkEdge* edge, int last_y) {
  167. SkASSERT(edge->fLastY >= last_y);
  168. if (last_y == edge->fLastY) {
  169. if (edge->fCurveCount < 0) {
  170. if (((SkCubicEdge*)edge)->updateCubic()) {
  171. SkASSERT(edge->fFirstY == last_y + 1);
  172. return true;
  173. }
  174. } else if (edge->fCurveCount > 0) {
  175. if (((SkQuadraticEdge*)edge)->updateQuadratic()) {
  176. SkASSERT(edge->fFirstY == last_y + 1);
  177. return true;
  178. }
  179. }
  180. return false;
  181. }
  182. return true;
  183. }
  184. // Unexpected conditions for which we need to return
  185. #define ASSERT_RETURN(cond) \
  186. do { \
  187. if (!(cond)) { \
  188. SkASSERT(false); \
  189. return; \
  190. } \
  191. } while (0)
  192. // Needs Y to only change once (looser than convex in X)
  193. static void walk_simple_edges(SkEdge* prevHead, SkBlitter* blitter, int start_y, int stop_y) {
  194. validate_sort(prevHead->fNext);
  195. SkEdge* leftE = prevHead->fNext;
  196. SkEdge* riteE = leftE->fNext;
  197. SkEdge* currE = riteE->fNext;
  198. // our edge choppers for curves can result in the initial edges
  199. // not lining up, so we take the max.
  200. int local_top = SkMax32(leftE->fFirstY, riteE->fFirstY);
  201. ASSERT_RETURN(local_top >= start_y);
  202. while (local_top < stop_y) {
  203. SkASSERT(leftE->fFirstY <= stop_y);
  204. SkASSERT(riteE->fFirstY <= stop_y);
  205. int local_bot = SkMin32(leftE->fLastY, riteE->fLastY);
  206. local_bot = SkMin32(local_bot, stop_y - 1);
  207. ASSERT_RETURN(local_top <= local_bot);
  208. SkFixed left = leftE->fX;
  209. SkFixed dLeft = leftE->fDX;
  210. SkFixed rite = riteE->fX;
  211. SkFixed dRite = riteE->fDX;
  212. int count = local_bot - local_top;
  213. ASSERT_RETURN(count >= 0);
  214. if (0 == (dLeft | dRite)) {
  215. int L = SkFixedRoundToInt(left);
  216. int R = SkFixedRoundToInt(rite);
  217. if (L > R) {
  218. std::swap(L, R);
  219. }
  220. if (L < R) {
  221. count += 1;
  222. blitter->blitRect(L, local_top, R - L, count);
  223. }
  224. local_top = local_bot + 1;
  225. } else {
  226. do {
  227. int L = SkFixedRoundToInt(left);
  228. int R = SkFixedRoundToInt(rite);
  229. if (L > R) {
  230. std::swap(L, R);
  231. }
  232. if (L < R) {
  233. blitter->blitH(L, local_top, R - L);
  234. }
  235. // Either/both of these might overflow, since we perform this step even if
  236. // (later) we determine that we are done with the edge, and so the computed
  237. // left or rite edge will not be used (see update_edge). Use this helper to
  238. // silence UBSAN when we perform the add.
  239. left = Sk32_can_overflow_add(left, dLeft);
  240. rite = Sk32_can_overflow_add(rite, dRite);
  241. local_top += 1;
  242. } while (--count >= 0);
  243. }
  244. leftE->fX = left;
  245. riteE->fX = rite;
  246. if (!update_edge(leftE, local_bot)) {
  247. if (currE->fFirstY >= stop_y) {
  248. return; // we're done
  249. }
  250. leftE = currE;
  251. currE = currE->fNext;
  252. ASSERT_RETURN(leftE->fFirstY == local_top);
  253. }
  254. if (!update_edge(riteE, local_bot)) {
  255. if (currE->fFirstY >= stop_y) {
  256. return; // we're done
  257. }
  258. riteE = currE;
  259. currE = currE->fNext;
  260. ASSERT_RETURN(riteE->fFirstY == local_top);
  261. }
  262. }
  263. }
  264. ///////////////////////////////////////////////////////////////////////////////
  265. // this guy overrides blitH, and will call its proxy blitter with the inverse
  266. // of the spans it is given (clipped to the left/right of the cliprect)
  267. //
  268. // used to implement inverse filltypes on paths
  269. //
  270. class InverseBlitter : public SkBlitter {
  271. public:
  272. void setBlitter(SkBlitter* blitter, const SkIRect& clip, int shift) {
  273. fBlitter = blitter;
  274. fFirstX = clip.fLeft << shift;
  275. fLastX = clip.fRight << shift;
  276. }
  277. void prepost(int y, bool isStart) {
  278. if (isStart) {
  279. fPrevX = fFirstX;
  280. } else {
  281. int invWidth = fLastX - fPrevX;
  282. if (invWidth > 0) {
  283. fBlitter->blitH(fPrevX, y, invWidth);
  284. }
  285. }
  286. }
  287. // overrides
  288. void blitH(int x, int y, int width) override {
  289. int invWidth = x - fPrevX;
  290. if (invWidth > 0) {
  291. fBlitter->blitH(fPrevX, y, invWidth);
  292. }
  293. fPrevX = x + width;
  294. }
  295. // we do not expect to get called with these entrypoints
  296. void blitAntiH(int, int, const SkAlpha[], const int16_t runs[]) override {
  297. SkDEBUGFAIL("blitAntiH unexpected");
  298. }
  299. void blitV(int x, int y, int height, SkAlpha alpha) override {
  300. SkDEBUGFAIL("blitV unexpected");
  301. }
  302. void blitRect(int x, int y, int width, int height) override {
  303. SkDEBUGFAIL("blitRect unexpected");
  304. }
  305. void blitMask(const SkMask&, const SkIRect& clip) override {
  306. SkDEBUGFAIL("blitMask unexpected");
  307. }
  308. const SkPixmap* justAnOpaqueColor(uint32_t* value) override {
  309. SkDEBUGFAIL("justAnOpaqueColor unexpected");
  310. return nullptr;
  311. }
  312. private:
  313. SkBlitter* fBlitter;
  314. int fFirstX, fLastX, fPrevX;
  315. };
  316. static void PrePostInverseBlitterProc(SkBlitter* blitter, int y, bool isStart) {
  317. ((InverseBlitter*)blitter)->prepost(y, isStart);
  318. }
  319. ///////////////////////////////////////////////////////////////////////////////
  320. #if defined _WIN32
  321. #pragma warning ( pop )
  322. #endif
  323. static bool operator<(const SkEdge& a, const SkEdge& b) {
  324. int valuea = a.fFirstY;
  325. int valueb = b.fFirstY;
  326. if (valuea == valueb) {
  327. valuea = a.fX;
  328. valueb = b.fX;
  329. }
  330. return valuea < valueb;
  331. }
  332. static SkEdge* sort_edges(SkEdge* list[], int count, SkEdge** last) {
  333. SkTQSort(list, list + count - 1);
  334. // now make the edges linked in sorted order
  335. for (int i = 1; i < count; i++) {
  336. list[i - 1]->fNext = list[i];
  337. list[i]->fPrev = list[i - 1];
  338. }
  339. *last = list[count - 1];
  340. return list[0];
  341. }
  342. // clipRect has not been shifted up
  343. void sk_fill_path(const SkPath& path, const SkIRect& clipRect, SkBlitter* blitter,
  344. int start_y, int stop_y, int shiftEdgesUp, bool pathContainedInClip) {
  345. SkASSERT(blitter);
  346. SkIRect shiftedClip = clipRect;
  347. shiftedClip.fLeft = SkLeftShift(shiftedClip.fLeft, shiftEdgesUp);
  348. shiftedClip.fRight = SkLeftShift(shiftedClip.fRight, shiftEdgesUp);
  349. shiftedClip.fTop = SkLeftShift(shiftedClip.fTop, shiftEdgesUp);
  350. shiftedClip.fBottom = SkLeftShift(shiftedClip.fBottom, shiftEdgesUp);
  351. SkBasicEdgeBuilder builder(shiftEdgesUp);
  352. int count = builder.buildEdges(path, pathContainedInClip ? nullptr : &shiftedClip);
  353. SkEdge** list = builder.edgeList();
  354. if (0 == count) {
  355. if (path.isInverseFillType()) {
  356. /*
  357. * Since we are in inverse-fill, our caller has already drawn above
  358. * our top (start_y) and will draw below our bottom (stop_y). Thus
  359. * we need to restrict our drawing to the intersection of the clip
  360. * and those two limits.
  361. */
  362. SkIRect rect = clipRect;
  363. if (rect.fTop < start_y) {
  364. rect.fTop = start_y;
  365. }
  366. if (rect.fBottom > stop_y) {
  367. rect.fBottom = stop_y;
  368. }
  369. if (!rect.isEmpty()) {
  370. blitter->blitRect(rect.fLeft << shiftEdgesUp,
  371. rect.fTop << shiftEdgesUp,
  372. rect.width() << shiftEdgesUp,
  373. rect.height() << shiftEdgesUp);
  374. }
  375. }
  376. return;
  377. }
  378. SkEdge headEdge, tailEdge, *last;
  379. // this returns the first and last edge after they're sorted into a dlink list
  380. SkEdge* edge = sort_edges(list, count, &last);
  381. headEdge.fPrev = nullptr;
  382. headEdge.fNext = edge;
  383. headEdge.fFirstY = kEDGE_HEAD_Y;
  384. headEdge.fX = SK_MinS32;
  385. edge->fPrev = &headEdge;
  386. tailEdge.fPrev = last;
  387. tailEdge.fNext = nullptr;
  388. tailEdge.fFirstY = kEDGE_TAIL_Y;
  389. last->fNext = &tailEdge;
  390. // now edge is the head of the sorted linklist
  391. start_y = SkLeftShift(start_y, shiftEdgesUp);
  392. stop_y = SkLeftShift(stop_y, shiftEdgesUp);
  393. if (!pathContainedInClip && start_y < shiftedClip.fTop) {
  394. start_y = shiftedClip.fTop;
  395. }
  396. if (!pathContainedInClip && stop_y > shiftedClip.fBottom) {
  397. stop_y = shiftedClip.fBottom;
  398. }
  399. InverseBlitter ib;
  400. PrePostProc proc = nullptr;
  401. if (path.isInverseFillType()) {
  402. ib.setBlitter(blitter, clipRect, shiftEdgesUp);
  403. blitter = &ib;
  404. proc = PrePostInverseBlitterProc;
  405. }
  406. // count >= 2 is required as the convex walker does not handle missing right edges
  407. if (path.isConvex() && (nullptr == proc) && count >= 2) {
  408. walk_simple_edges(&headEdge, blitter, start_y, stop_y);
  409. } else {
  410. walk_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, proc,
  411. shiftedClip.right());
  412. }
  413. }
  414. void sk_blit_above(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) {
  415. const SkIRect& cr = clip.getBounds();
  416. SkIRect tmp;
  417. tmp.fLeft = cr.fLeft;
  418. tmp.fRight = cr.fRight;
  419. tmp.fTop = cr.fTop;
  420. tmp.fBottom = ir.fTop;
  421. if (!tmp.isEmpty()) {
  422. blitter->blitRectRegion(tmp, clip);
  423. }
  424. }
  425. void sk_blit_below(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) {
  426. const SkIRect& cr = clip.getBounds();
  427. SkIRect tmp;
  428. tmp.fLeft = cr.fLeft;
  429. tmp.fRight = cr.fRight;
  430. tmp.fTop = ir.fBottom;
  431. tmp.fBottom = cr.fBottom;
  432. if (!tmp.isEmpty()) {
  433. blitter->blitRectRegion(tmp, clip);
  434. }
  435. }
  436. ///////////////////////////////////////////////////////////////////////////////
  437. /**
  438. * If the caller is drawing an inverse-fill path, then it pass true for
  439. * skipRejectTest, so we don't abort drawing just because the src bounds (ir)
  440. * is outside of the clip.
  441. */
  442. SkScanClipper::SkScanClipper(SkBlitter* blitter, const SkRegion* clip,
  443. const SkIRect& ir, bool skipRejectTest, bool irPreClipped) {
  444. fBlitter = nullptr; // null means blit nothing
  445. fClipRect = nullptr;
  446. if (clip) {
  447. fClipRect = &clip->getBounds();
  448. if (!skipRejectTest && !SkIRect::Intersects(*fClipRect, ir)) { // completely clipped out
  449. return;
  450. }
  451. if (clip->isRect()) {
  452. if (!irPreClipped && fClipRect->contains(ir)) {
  453. #ifdef SK_DEBUG
  454. fRectClipCheckBlitter.init(blitter, *fClipRect);
  455. blitter = &fRectClipCheckBlitter;
  456. #endif
  457. fClipRect = nullptr;
  458. } else {
  459. // only need a wrapper blitter if we're horizontally clipped
  460. if (irPreClipped ||
  461. fClipRect->fLeft > ir.fLeft || fClipRect->fRight < ir.fRight) {
  462. fRectBlitter.init(blitter, *fClipRect);
  463. blitter = &fRectBlitter;
  464. } else {
  465. #ifdef SK_DEBUG
  466. fRectClipCheckBlitter.init(blitter, *fClipRect);
  467. blitter = &fRectClipCheckBlitter;
  468. #endif
  469. }
  470. }
  471. } else {
  472. fRgnBlitter.init(blitter, clip);
  473. blitter = &fRgnBlitter;
  474. }
  475. }
  476. fBlitter = blitter;
  477. }
  478. ///////////////////////////////////////////////////////////////////////////////
  479. static bool clip_to_limit(const SkRegion& orig, SkRegion* reduced) {
  480. // need to limit coordinates such that the width/height of our rect can be represented
  481. // in SkFixed (16.16). See skbug.com/7998
  482. const int32_t limit = 32767 >> 1;
  483. SkIRect limitR;
  484. limitR.set(-limit, -limit, limit, limit);
  485. if (limitR.contains(orig.getBounds())) {
  486. return false;
  487. }
  488. reduced->op(orig, limitR, SkRegion::kIntersect_Op);
  489. return true;
  490. }
  491. // Bias used for conservative rounding of float rects to int rects, to nudge the irects a little
  492. // larger, so we don't "think" a path's bounds are inside a clip, when (due to numeric drift in
  493. // the scan-converter) we might walk beyond the predicted limits.
  494. //
  495. // This value has been determined trial and error: pick the smallest value (after the 0.5) that
  496. // fixes any problematic cases (e.g. crbug.com/844457)
  497. // NOTE: cubics appear to be the main reason for needing this slop. If we could (perhaps) have a
  498. // more accurate walker for cubics, we may be able to reduce this fudge factor.
  499. static const double kConservativeRoundBias = 0.5 + 1.5 / SK_FDot6One;
  500. /**
  501. * Round the value down. This is used to round the top and left of a rectangle,
  502. * and corresponds to the way the scan converter treats the top and left edges.
  503. * It has a slight bias to make the "rounded" int smaller than a normal round, to create a more
  504. * conservative int-bounds (larger) from a float rect.
  505. */
  506. static inline int round_down_to_int(SkScalar x) {
  507. double xx = x;
  508. xx -= kConservativeRoundBias;
  509. return sk_double_saturate2int(ceil(xx));
  510. }
  511. /**
  512. * Round the value up. This is used to round the right and bottom of a rectangle.
  513. * It has a slight bias to make the "rounded" int smaller than a normal round, to create a more
  514. * conservative int-bounds (larger) from a float rect.
  515. */
  516. static inline int round_up_to_int(SkScalar x) {
  517. double xx = x;
  518. xx += kConservativeRoundBias;
  519. return sk_double_saturate2int(floor(xx));
  520. }
  521. /*
  522. * Conservative rounding function, which effectively nudges the int-rect to be slightly larger
  523. * than SkRect::round() might have produced. This is a safety-net for the scan-converter, which
  524. * inspects the returned int-rect, and may disable clipping (for speed) if it thinks all of the
  525. * edges will fit inside the clip's bounds. The scan-converter introduces slight numeric errors
  526. * due to accumulated += of the slope, so this function is used to return a conservatively large
  527. * int-bounds, and thus we will only disable clipping if we're sure the edges will stay in-bounds.
  528. */
  529. static SkIRect conservative_round_to_int(const SkRect& src) {
  530. return {
  531. round_down_to_int(src.fLeft),
  532. round_down_to_int(src.fTop),
  533. round_up_to_int(src.fRight),
  534. round_up_to_int(src.fBottom),
  535. };
  536. }
  537. void SkScan::FillPath(const SkPath& path, const SkRegion& origClip,
  538. SkBlitter* blitter) {
  539. if (origClip.isEmpty()) {
  540. return;
  541. }
  542. // Our edges are fixed-point, and don't like the bounds of the clip to
  543. // exceed that. Here we trim the clip just so we don't overflow later on
  544. const SkRegion* clipPtr = &origClip;
  545. SkRegion finiteClip;
  546. if (clip_to_limit(origClip, &finiteClip)) {
  547. if (finiteClip.isEmpty()) {
  548. return;
  549. }
  550. clipPtr = &finiteClip;
  551. }
  552. // don't reference "origClip" any more, just use clipPtr
  553. SkRect bounds = path.getBounds();
  554. bool irPreClipped = false;
  555. if (!SkRectPriv::MakeLargeS32().contains(bounds)) {
  556. if (!bounds.intersect(SkRectPriv::MakeLargeS32())) {
  557. bounds.setEmpty();
  558. }
  559. irPreClipped = true;
  560. }
  561. SkIRect ir = conservative_round_to_int(bounds);
  562. if (ir.isEmpty()) {
  563. if (path.isInverseFillType()) {
  564. blitter->blitRegion(*clipPtr);
  565. }
  566. return;
  567. }
  568. SkScanClipper clipper(blitter, clipPtr, ir, path.isInverseFillType(), irPreClipped);
  569. blitter = clipper.getBlitter();
  570. if (blitter) {
  571. // we have to keep our calls to blitter in sorted order, so we
  572. // must blit the above section first, then the middle, then the bottom.
  573. if (path.isInverseFillType()) {
  574. sk_blit_above(blitter, ir, *clipPtr);
  575. }
  576. SkASSERT(clipper.getClipRect() == nullptr ||
  577. *clipper.getClipRect() == clipPtr->getBounds());
  578. sk_fill_path(path, clipPtr->getBounds(), blitter, ir.fTop, ir.fBottom,
  579. 0, clipper.getClipRect() == nullptr);
  580. if (path.isInverseFillType()) {
  581. sk_blit_below(blitter, ir, *clipPtr);
  582. }
  583. } else {
  584. // what does it mean to not have a blitter if path.isInverseFillType???
  585. }
  586. }
  587. void SkScan::FillPath(const SkPath& path, const SkIRect& ir,
  588. SkBlitter* blitter) {
  589. SkRegion rgn(ir);
  590. FillPath(path, rgn, blitter);
  591. }
  592. ///////////////////////////////////////////////////////////////////////////////
  593. static int build_tri_edges(SkEdge edge[], const SkPoint pts[],
  594. const SkIRect* clipRect, SkEdge* list[]) {
  595. SkEdge** start = list;
  596. if (edge->setLine(pts[0], pts[1], clipRect, 0)) {
  597. *list++ = edge;
  598. edge = (SkEdge*)((char*)edge + sizeof(SkEdge));
  599. }
  600. if (edge->setLine(pts[1], pts[2], clipRect, 0)) {
  601. *list++ = edge;
  602. edge = (SkEdge*)((char*)edge + sizeof(SkEdge));
  603. }
  604. if (edge->setLine(pts[2], pts[0], clipRect, 0)) {
  605. *list++ = edge;
  606. }
  607. return (int)(list - start);
  608. }
  609. static void sk_fill_triangle(const SkPoint pts[], const SkIRect* clipRect,
  610. SkBlitter* blitter, const SkIRect& ir) {
  611. SkASSERT(pts && blitter);
  612. SkEdge edgeStorage[3];
  613. SkEdge* list[3];
  614. int count = build_tri_edges(edgeStorage, pts, clipRect, list);
  615. if (count < 2) {
  616. return;
  617. }
  618. SkEdge headEdge, tailEdge, *last;
  619. // this returns the first and last edge after they're sorted into a dlink list
  620. SkEdge* edge = sort_edges(list, count, &last);
  621. headEdge.fPrev = nullptr;
  622. headEdge.fNext = edge;
  623. headEdge.fFirstY = kEDGE_HEAD_Y;
  624. headEdge.fX = SK_MinS32;
  625. edge->fPrev = &headEdge;
  626. tailEdge.fPrev = last;
  627. tailEdge.fNext = nullptr;
  628. tailEdge.fFirstY = kEDGE_TAIL_Y;
  629. last->fNext = &tailEdge;
  630. // now edge is the head of the sorted linklist
  631. int stop_y = ir.fBottom;
  632. if (clipRect && stop_y > clipRect->fBottom) {
  633. stop_y = clipRect->fBottom;
  634. }
  635. int start_y = ir.fTop;
  636. if (clipRect && start_y < clipRect->fTop) {
  637. start_y = clipRect->fTop;
  638. }
  639. walk_simple_edges(&headEdge, blitter, start_y, stop_y);
  640. }
  641. void SkScan::FillTriangle(const SkPoint pts[], const SkRasterClip& clip,
  642. SkBlitter* blitter) {
  643. if (clip.isEmpty()) {
  644. return;
  645. }
  646. SkRect r;
  647. r.set(pts, 3);
  648. // If r is too large (larger than can easily fit in SkFixed) then we need perform geometric
  649. // clipping. This is a bit of work, so we just call the general FillPath() to handle it.
  650. // Use FixedMax/2 as the limit so we can subtract two edges and still store that in Fixed.
  651. const SkScalar limit = SK_MaxS16 >> 1;
  652. if (!SkRect::MakeLTRB(-limit, -limit, limit, limit).contains(r)) {
  653. SkPath path;
  654. path.addPoly(pts, 3, false);
  655. FillPath(path, clip, blitter);
  656. return;
  657. }
  658. SkIRect ir = conservative_round_to_int(r);
  659. if (ir.isEmpty() || !SkIRect::Intersects(ir, clip.getBounds())) {
  660. return;
  661. }
  662. SkAAClipBlitterWrapper wrap;
  663. const SkRegion* clipRgn;
  664. if (clip.isBW()) {
  665. clipRgn = &clip.bwRgn();
  666. } else {
  667. wrap.init(clip, blitter);
  668. clipRgn = &wrap.getRgn();
  669. blitter = wrap.getBlitter();
  670. }
  671. SkScanClipper clipper(blitter, clipRgn, ir);
  672. blitter = clipper.getBlitter();
  673. if (blitter) {
  674. sk_fill_triangle(pts, clipper.getClipRect(), blitter, ir);
  675. }
  676. }