SkRegion_path.cpp 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549
  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/private/SkTDArray.h"
  9. #include "include/private/SkTo.h"
  10. #include "src/core/SkBlitter.h"
  11. #include "src/core/SkRegionPriv.h"
  12. #include "src/core/SkSafeMath.h"
  13. #include "src/core/SkScan.h"
  14. #include "src/core/SkTSort.h"
  15. // The rgnbuilder caller *seems* to pass short counts, possible often seens early failure, so
  16. // we may not want to promote this to a "std" routine just yet.
  17. static bool sk_memeq32(const int32_t* SK_RESTRICT a, const int32_t* SK_RESTRICT b, int count) {
  18. for (int i = 0; i < count; ++i) {
  19. if (a[i] != b[i]) {
  20. return false;
  21. }
  22. }
  23. return true;
  24. }
  25. class SkRgnBuilder : public SkBlitter {
  26. public:
  27. SkRgnBuilder();
  28. ~SkRgnBuilder() override;
  29. // returns true if it could allocate the working storage needed
  30. bool init(int maxHeight, int maxTransitions, bool pathIsInverse);
  31. void done() {
  32. if (fCurrScanline != nullptr) {
  33. fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
  34. if (!this->collapsWithPrev()) { // flush the last line
  35. fCurrScanline = fCurrScanline->nextScanline();
  36. }
  37. }
  38. }
  39. int computeRunCount() const;
  40. void copyToRect(SkIRect*) const;
  41. void copyToRgn(SkRegion::RunType runs[]) const;
  42. void blitH(int x, int y, int width) override;
  43. void blitAntiH(int x, int y, const SkAlpha antialias[], const int16_t runs[]) override {
  44. SkDEBUGFAIL("blitAntiH not implemented");
  45. }
  46. #ifdef SK_DEBUG
  47. void dump() const {
  48. SkDebugf("SkRgnBuilder: Top = %d\n", fTop);
  49. const Scanline* line = (Scanline*)fStorage;
  50. while (line < fCurrScanline) {
  51. SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount);
  52. for (int i = 0; i < line->fXCount; i++) {
  53. SkDebugf(" %d", line->firstX()[i]);
  54. }
  55. SkDebugf("\n");
  56. line = line->nextScanline();
  57. }
  58. }
  59. #endif
  60. private:
  61. /*
  62. * Scanline mimics a row in the region, nearly. A row in a region is:
  63. * [Bottom IntervalCount [L R]... Sentinel]
  64. * while a Scanline is
  65. * [LastY XCount [L R]... uninitialized]
  66. * The two are the same length (which is good), but we have to transmute
  67. * the scanline a little when we convert it to a region-row.
  68. *
  69. * Potentially we could recode this to exactly match the row format, in
  70. * which case copyToRgn() could be a single memcpy. Not sure that is worth
  71. * the effort.
  72. */
  73. struct Scanline {
  74. SkRegion::RunType fLastY;
  75. SkRegion::RunType fXCount;
  76. SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); }
  77. Scanline* nextScanline() const {
  78. // add final +1 for the x-sentinel
  79. return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount + 1);
  80. }
  81. };
  82. SkRegion::RunType* fStorage;
  83. Scanline* fCurrScanline;
  84. Scanline* fPrevScanline;
  85. // points at next avialable x[] in fCurrScanline
  86. SkRegion::RunType* fCurrXPtr;
  87. SkRegion::RunType fTop; // first Y value
  88. int fStorageCount;
  89. bool collapsWithPrev() {
  90. if (fPrevScanline != nullptr &&
  91. fPrevScanline->fLastY + 1 == fCurrScanline->fLastY &&
  92. fPrevScanline->fXCount == fCurrScanline->fXCount &&
  93. sk_memeq32(fPrevScanline->firstX(), fCurrScanline->firstX(), fCurrScanline->fXCount))
  94. {
  95. // update the height of fPrevScanline
  96. fPrevScanline->fLastY = fCurrScanline->fLastY;
  97. return true;
  98. }
  99. return false;
  100. }
  101. };
  102. SkRgnBuilder::SkRgnBuilder()
  103. : fStorage(nullptr) {
  104. }
  105. SkRgnBuilder::~SkRgnBuilder() {
  106. sk_free(fStorage);
  107. }
  108. bool SkRgnBuilder::init(int maxHeight, int maxTransitions, bool pathIsInverse) {
  109. if ((maxHeight | maxTransitions) < 0) {
  110. return false;
  111. }
  112. SkSafeMath safe;
  113. if (pathIsInverse) {
  114. // allow for additional X transitions to "invert" each scanline
  115. // [ L' ... normal transitions ... R' ]
  116. //
  117. maxTransitions = safe.addInt(maxTransitions, 2);
  118. }
  119. // compute the count with +1 and +3 slop for the working buffer
  120. size_t count = safe.mul(safe.addInt(maxHeight, 1), safe.addInt(3, maxTransitions));
  121. if (pathIsInverse) {
  122. // allow for two "empty" rows for the top and bottom
  123. // [ Y, 1, L, R, S] == 5 (*2 for top and bottom)
  124. count = safe.add(count, 10);
  125. }
  126. if (!safe || !SkTFitsIn<int32_t>(count)) {
  127. return false;
  128. }
  129. fStorageCount = SkToS32(count);
  130. fStorage = (SkRegion::RunType*)sk_malloc_canfail(fStorageCount, sizeof(SkRegion::RunType));
  131. if (nullptr == fStorage) {
  132. return false;
  133. }
  134. fCurrScanline = nullptr; // signal empty collection
  135. fPrevScanline = nullptr; // signal first scanline
  136. return true;
  137. }
  138. void SkRgnBuilder::blitH(int x, int y, int width) {
  139. if (fCurrScanline == nullptr) { // first time
  140. fTop = (SkRegion::RunType)(y);
  141. fCurrScanline = (Scanline*)fStorage;
  142. fCurrScanline->fLastY = (SkRegion::RunType)(y);
  143. fCurrXPtr = fCurrScanline->firstX();
  144. } else {
  145. SkASSERT(y >= fCurrScanline->fLastY);
  146. if (y > fCurrScanline->fLastY) {
  147. // if we get here, we're done with fCurrScanline
  148. fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
  149. int prevLastY = fCurrScanline->fLastY;
  150. if (!this->collapsWithPrev()) {
  151. fPrevScanline = fCurrScanline;
  152. fCurrScanline = fCurrScanline->nextScanline();
  153. }
  154. if (y - 1 > prevLastY) { // insert empty run
  155. fCurrScanline->fLastY = (SkRegion::RunType)(y - 1);
  156. fCurrScanline->fXCount = 0;
  157. fCurrScanline = fCurrScanline->nextScanline();
  158. }
  159. // setup for the new curr line
  160. fCurrScanline->fLastY = (SkRegion::RunType)(y);
  161. fCurrXPtr = fCurrScanline->firstX();
  162. }
  163. }
  164. // check if we should extend the current run, or add a new one
  165. if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) {
  166. fCurrXPtr[-1] = (SkRegion::RunType)(x + width);
  167. } else {
  168. fCurrXPtr[0] = (SkRegion::RunType)(x);
  169. fCurrXPtr[1] = (SkRegion::RunType)(x + width);
  170. fCurrXPtr += 2;
  171. }
  172. SkASSERT(fCurrXPtr - fStorage < fStorageCount);
  173. }
  174. int SkRgnBuilder::computeRunCount() const {
  175. if (fCurrScanline == nullptr) {
  176. return 0;
  177. }
  178. const SkRegion::RunType* line = fStorage;
  179. const SkRegion::RunType* stop = (const SkRegion::RunType*)fCurrScanline;
  180. return 2 + (int)(stop - line);
  181. }
  182. void SkRgnBuilder::copyToRect(SkIRect* r) const {
  183. SkASSERT(fCurrScanline != nullptr);
  184. // A rect's scanline is [bottom intervals left right sentinel] == 5
  185. SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 5);
  186. const Scanline* line = (const Scanline*)fStorage;
  187. SkASSERT(line->fXCount == 2);
  188. r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1);
  189. }
  190. void SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const {
  191. SkASSERT(fCurrScanline != nullptr);
  192. SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4);
  193. const Scanline* line = (const Scanline*)fStorage;
  194. const Scanline* stop = fCurrScanline;
  195. *runs++ = fTop;
  196. do {
  197. *runs++ = (SkRegion::RunType)(line->fLastY + 1);
  198. int count = line->fXCount;
  199. *runs++ = count >> 1; // intervalCount
  200. if (count) {
  201. memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType));
  202. runs += count;
  203. }
  204. *runs++ = SkRegion_kRunTypeSentinel;
  205. line = line->nextScanline();
  206. } while (line < stop);
  207. SkASSERT(line == stop);
  208. *runs = SkRegion_kRunTypeSentinel;
  209. }
  210. static unsigned verb_to_initial_last_index(unsigned verb) {
  211. static const uint8_t gPathVerbToInitialLastIndex[] = {
  212. 0, // kMove_Verb
  213. 1, // kLine_Verb
  214. 2, // kQuad_Verb
  215. 2, // kConic_Verb
  216. 3, // kCubic_Verb
  217. 0, // kClose_Verb
  218. 0 // kDone_Verb
  219. };
  220. SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToInitialLastIndex));
  221. return gPathVerbToInitialLastIndex[verb];
  222. }
  223. static unsigned verb_to_max_edges(unsigned verb) {
  224. static const uint8_t gPathVerbToMaxEdges[] = {
  225. 0, // kMove_Verb
  226. 1, // kLine_Verb
  227. 2, // kQuad_VerbB
  228. 2, // kConic_VerbB
  229. 3, // kCubic_Verb
  230. 0, // kClose_Verb
  231. 0 // kDone_Verb
  232. };
  233. SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToMaxEdges));
  234. return gPathVerbToMaxEdges[verb];
  235. }
  236. // If returns 0, ignore itop and ibot
  237. static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) {
  238. SkPath::Iter iter(path, true);
  239. SkPoint pts[4];
  240. SkPath::Verb verb;
  241. int maxEdges = 0;
  242. SkScalar top = SkIntToScalar(SK_MaxS16);
  243. SkScalar bot = SkIntToScalar(SK_MinS16);
  244. while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
  245. maxEdges += verb_to_max_edges(verb);
  246. int lastIndex = verb_to_initial_last_index(verb);
  247. if (lastIndex > 0) {
  248. for (int i = 1; i <= lastIndex; i++) {
  249. if (top > pts[i].fY) {
  250. top = pts[i].fY;
  251. } else if (bot < pts[i].fY) {
  252. bot = pts[i].fY;
  253. }
  254. }
  255. } else if (SkPath::kMove_Verb == verb) {
  256. if (top > pts[0].fY) {
  257. top = pts[0].fY;
  258. } else if (bot < pts[0].fY) {
  259. bot = pts[0].fY;
  260. }
  261. }
  262. }
  263. if (0 == maxEdges) {
  264. return 0; // we have only moves+closes
  265. }
  266. SkASSERT(top <= bot);
  267. *itop = SkScalarRoundToInt(top);
  268. *ibot = SkScalarRoundToInt(bot);
  269. return maxEdges;
  270. }
  271. static bool check_inverse_on_empty_return(SkRegion* dst, const SkPath& path, const SkRegion& clip) {
  272. if (path.isInverseFillType()) {
  273. return dst->set(clip);
  274. } else {
  275. return dst->setEmpty();
  276. }
  277. }
  278. bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) {
  279. SkDEBUGCODE(SkRegionPriv::Validate(*this));
  280. if (clip.isEmpty() || !path.isFinite()) {
  281. return this->setEmpty();
  282. }
  283. if (path.isEmpty()) {
  284. return check_inverse_on_empty_return(this, path, clip);
  285. }
  286. // Our builder is very fragile, and can't be called with spans/rects out of Y->X order.
  287. // To ensure this, we only "fill" clipped to a rect (the clip's bounds), and if the
  288. // clip is more complex than that, we just post-intersect the result with the clip.
  289. if (clip.isComplex()) {
  290. if (!this->setPath(path, SkRegion(clip.getBounds()))) {
  291. return false;
  292. }
  293. return this->op(clip, kIntersect_Op);
  294. }
  295. // compute worst-case rgn-size for the path
  296. int pathTop, pathBot;
  297. int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot);
  298. if (0 == pathTransitions) {
  299. return check_inverse_on_empty_return(this, path, clip);
  300. }
  301. int clipTop, clipBot;
  302. int clipTransitions = clip.count_runtype_values(&clipTop, &clipBot);
  303. int top = SkMax32(pathTop, clipTop);
  304. int bot = SkMin32(pathBot, clipBot);
  305. if (top >= bot) {
  306. return check_inverse_on_empty_return(this, path, clip);
  307. }
  308. SkRgnBuilder builder;
  309. if (!builder.init(bot - top,
  310. SkMax32(pathTransitions, clipTransitions),
  311. path.isInverseFillType())) {
  312. // can't allocate working space, so return false
  313. return this->setEmpty();
  314. }
  315. SkScan::FillPath(path, clip, &builder);
  316. builder.done();
  317. int count = builder.computeRunCount();
  318. if (count == 0) {
  319. return this->setEmpty();
  320. } else if (count == kRectRegionRuns) {
  321. builder.copyToRect(&fBounds);
  322. this->setRect(fBounds);
  323. } else {
  324. SkRegion tmp;
  325. tmp.fRunHead = RunHead::Alloc(count);
  326. builder.copyToRgn(tmp.fRunHead->writable_runs());
  327. tmp.fRunHead->computeRunBounds(&tmp.fBounds);
  328. this->swap(tmp);
  329. }
  330. SkDEBUGCODE(SkRegionPriv::Validate(*this));
  331. return true;
  332. }
  333. /////////////////////////////////////////////////////////////////////////////////////////////////
  334. /////////////////////////////////////////////////////////////////////////////////////////////////
  335. struct Edge {
  336. enum {
  337. kY0Link = 0x01,
  338. kY1Link = 0x02,
  339. kCompleteLink = (kY0Link | kY1Link)
  340. };
  341. SkRegionPriv::RunType fX;
  342. SkRegionPriv::RunType fY0, fY1;
  343. uint8_t fFlags;
  344. Edge* fNext;
  345. void set(int x, int y0, int y1) {
  346. SkASSERT(y0 != y1);
  347. fX = (SkRegionPriv::RunType)(x);
  348. fY0 = (SkRegionPriv::RunType)(y0);
  349. fY1 = (SkRegionPriv::RunType)(y1);
  350. fFlags = 0;
  351. SkDEBUGCODE(fNext = nullptr;)
  352. }
  353. int top() const {
  354. return SkMin32(fY0, fY1);
  355. }
  356. };
  357. static void find_link(Edge* base, Edge* stop) {
  358. SkASSERT(base < stop);
  359. if (base->fFlags == Edge::kCompleteLink) {
  360. SkASSERT(base->fNext);
  361. return;
  362. }
  363. SkASSERT(base + 1 < stop);
  364. int y0 = base->fY0;
  365. int y1 = base->fY1;
  366. Edge* e = base;
  367. if ((base->fFlags & Edge::kY0Link) == 0) {
  368. for (;;) {
  369. e += 1;
  370. if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) {
  371. SkASSERT(nullptr == e->fNext);
  372. e->fNext = base;
  373. e->fFlags = SkToU8(e->fFlags | Edge::kY1Link);
  374. break;
  375. }
  376. }
  377. }
  378. e = base;
  379. if ((base->fFlags & Edge::kY1Link) == 0) {
  380. for (;;) {
  381. e += 1;
  382. if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) {
  383. SkASSERT(nullptr == base->fNext);
  384. base->fNext = e;
  385. e->fFlags = SkToU8(e->fFlags | Edge::kY0Link);
  386. break;
  387. }
  388. }
  389. }
  390. base->fFlags = Edge::kCompleteLink;
  391. }
  392. static int extract_path(Edge* edge, Edge* stop, SkPath* path) {
  393. while (0 == edge->fFlags) {
  394. edge++; // skip over "used" edges
  395. }
  396. SkASSERT(edge < stop);
  397. Edge* base = edge;
  398. Edge* prev = edge;
  399. edge = edge->fNext;
  400. SkASSERT(edge != base);
  401. int count = 1;
  402. path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0));
  403. prev->fFlags = 0;
  404. do {
  405. if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear
  406. path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
  407. path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0)); // H
  408. }
  409. prev = edge;
  410. edge = edge->fNext;
  411. count += 1;
  412. prev->fFlags = 0;
  413. } while (edge != base);
  414. path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
  415. path->close();
  416. return count;
  417. }
  418. struct EdgeLT {
  419. bool operator()(const Edge& a, const Edge& b) const {
  420. return (a.fX == b.fX) ? a.top() < b.top() : a.fX < b.fX;
  421. }
  422. };
  423. bool SkRegion::getBoundaryPath(SkPath* path) const {
  424. // path could safely be nullptr if we're empty, but the caller shouldn't
  425. // *know* that
  426. SkASSERT(path);
  427. if (this->isEmpty()) {
  428. return false;
  429. }
  430. const SkIRect& bounds = this->getBounds();
  431. if (this->isRect()) {
  432. SkRect r;
  433. r.set(bounds); // this converts the ints to scalars
  434. path->addRect(r);
  435. return true;
  436. }
  437. SkRegion::Iterator iter(*this);
  438. SkTDArray<Edge> edges;
  439. for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) {
  440. Edge* edge = edges.append(2);
  441. edge[0].set(r.fLeft, r.fBottom, r.fTop);
  442. edge[1].set(r.fRight, r.fTop, r.fBottom);
  443. }
  444. int count = edges.count();
  445. Edge* start = edges.begin();
  446. Edge* stop = start + count;
  447. SkTQSort<Edge>(start, stop - 1, EdgeLT());
  448. Edge* e;
  449. for (e = start; e != stop; e++) {
  450. find_link(e, stop);
  451. }
  452. #ifdef SK_DEBUG
  453. for (e = start; e != stop; e++) {
  454. SkASSERT(e->fNext != nullptr);
  455. SkASSERT(e->fFlags == Edge::kCompleteLink);
  456. }
  457. #endif
  458. path->incReserve(count << 1);
  459. do {
  460. SkASSERT(count > 1);
  461. count -= extract_path(start, stop, path);
  462. } while (count > 0);
  463. return true;
  464. }