SkClipStack.cpp 38 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100
  1. /*
  2. * Copyright 2011 Google Inc.
  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/SkCanvas.h"
  8. #include "include/core/SkPath.h"
  9. #include "include/pathops/SkPathOps.h"
  10. #include "src/core/SkClipOpPriv.h"
  11. #include "src/core/SkClipStack.h"
  12. #include <atomic>
  13. #include <new>
  14. #if SK_SUPPORT_GPU
  15. #include "src/gpu/GrProxyProvider.h"
  16. #endif
  17. SkClipStack::Element::Element(const Element& that) {
  18. switch (that.getDeviceSpaceType()) {
  19. case DeviceSpaceType::kEmpty:
  20. fDeviceSpaceRRect.setEmpty();
  21. fDeviceSpacePath.reset();
  22. break;
  23. case DeviceSpaceType::kRect: // Rect uses rrect
  24. case DeviceSpaceType::kRRect:
  25. fDeviceSpacePath.reset();
  26. fDeviceSpaceRRect = that.fDeviceSpaceRRect;
  27. break;
  28. case DeviceSpaceType::kPath:
  29. fDeviceSpacePath.set(that.getDeviceSpacePath());
  30. break;
  31. }
  32. fSaveCount = that.fSaveCount;
  33. fOp = that.fOp;
  34. fDeviceSpaceType = that.fDeviceSpaceType;
  35. fDoAA = that.fDoAA;
  36. fFiniteBoundType = that.fFiniteBoundType;
  37. fFiniteBound = that.fFiniteBound;
  38. fIsIntersectionOfRects = that.fIsIntersectionOfRects;
  39. fGenID = that.fGenID;
  40. }
  41. SkClipStack::Element::~Element() {
  42. #if SK_SUPPORT_GPU
  43. for (int i = 0; i < fKeysToInvalidate.count(); ++i) {
  44. fProxyProvider->processInvalidUniqueKey(fKeysToInvalidate[i], nullptr,
  45. GrProxyProvider::InvalidateGPUResource::kYes);
  46. }
  47. #endif
  48. }
  49. bool SkClipStack::Element::operator== (const Element& element) const {
  50. if (this == &element) {
  51. return true;
  52. }
  53. if (fOp != element.fOp || fDeviceSpaceType != element.fDeviceSpaceType ||
  54. fDoAA != element.fDoAA || fSaveCount != element.fSaveCount) {
  55. return false;
  56. }
  57. switch (fDeviceSpaceType) {
  58. case DeviceSpaceType::kPath:
  59. return this->getDeviceSpacePath() == element.getDeviceSpacePath();
  60. case DeviceSpaceType::kRRect:
  61. return fDeviceSpaceRRect == element.fDeviceSpaceRRect;
  62. case DeviceSpaceType::kRect:
  63. return this->getDeviceSpaceRect() == element.getDeviceSpaceRect();
  64. case DeviceSpaceType::kEmpty:
  65. return true;
  66. default:
  67. SkDEBUGFAIL("Unexpected type.");
  68. return false;
  69. }
  70. }
  71. const SkRect& SkClipStack::Element::getBounds() const {
  72. static const SkRect kEmpty = {0, 0, 0, 0};
  73. switch (fDeviceSpaceType) {
  74. case DeviceSpaceType::kRect: // fallthrough
  75. case DeviceSpaceType::kRRect:
  76. return fDeviceSpaceRRect.getBounds();
  77. case DeviceSpaceType::kPath:
  78. return fDeviceSpacePath.get()->getBounds();
  79. case DeviceSpaceType::kEmpty:
  80. return kEmpty;
  81. default:
  82. SkDEBUGFAIL("Unexpected type.");
  83. return kEmpty;
  84. }
  85. }
  86. bool SkClipStack::Element::contains(const SkRect& rect) const {
  87. switch (fDeviceSpaceType) {
  88. case DeviceSpaceType::kRect:
  89. return this->getDeviceSpaceRect().contains(rect);
  90. case DeviceSpaceType::kRRect:
  91. return fDeviceSpaceRRect.contains(rect);
  92. case DeviceSpaceType::kPath:
  93. return fDeviceSpacePath.get()->conservativelyContainsRect(rect);
  94. case DeviceSpaceType::kEmpty:
  95. return false;
  96. default:
  97. SkDEBUGFAIL("Unexpected type.");
  98. return false;
  99. }
  100. }
  101. bool SkClipStack::Element::contains(const SkRRect& rrect) const {
  102. switch (fDeviceSpaceType) {
  103. case DeviceSpaceType::kRect:
  104. return this->getDeviceSpaceRect().contains(rrect.getBounds());
  105. case DeviceSpaceType::kRRect:
  106. // We don't currently have a generalized rrect-rrect containment.
  107. return fDeviceSpaceRRect.contains(rrect.getBounds()) || rrect == fDeviceSpaceRRect;
  108. case DeviceSpaceType::kPath:
  109. return fDeviceSpacePath.get()->conservativelyContainsRect(rrect.getBounds());
  110. case DeviceSpaceType::kEmpty:
  111. return false;
  112. default:
  113. SkDEBUGFAIL("Unexpected type.");
  114. return false;
  115. }
  116. }
  117. void SkClipStack::Element::invertShapeFillType() {
  118. switch (fDeviceSpaceType) {
  119. case DeviceSpaceType::kRect:
  120. fDeviceSpacePath.init();
  121. fDeviceSpacePath.get()->addRect(this->getDeviceSpaceRect());
  122. fDeviceSpacePath.get()->setFillType(SkPath::kInverseEvenOdd_FillType);
  123. fDeviceSpaceType = DeviceSpaceType::kPath;
  124. break;
  125. case DeviceSpaceType::kRRect:
  126. fDeviceSpacePath.init();
  127. fDeviceSpacePath.get()->addRRect(fDeviceSpaceRRect);
  128. fDeviceSpacePath.get()->setFillType(SkPath::kInverseEvenOdd_FillType);
  129. fDeviceSpaceType = DeviceSpaceType::kPath;
  130. break;
  131. case DeviceSpaceType::kPath:
  132. fDeviceSpacePath.get()->toggleInverseFillType();
  133. break;
  134. case DeviceSpaceType::kEmpty:
  135. // Should this set to an empty, inverse filled path?
  136. break;
  137. }
  138. }
  139. void SkClipStack::Element::initCommon(int saveCount, SkClipOp op, bool doAA) {
  140. fSaveCount = saveCount;
  141. fOp = op;
  142. fDoAA = doAA;
  143. // A default of inside-out and empty bounds means the bounds are effectively void as it
  144. // indicates that nothing is known to be outside the clip.
  145. fFiniteBoundType = kInsideOut_BoundsType;
  146. fFiniteBound.setEmpty();
  147. fIsIntersectionOfRects = false;
  148. fGenID = kInvalidGenID;
  149. }
  150. void SkClipStack::Element::initRect(int saveCount, const SkRect& rect, const SkMatrix& m,
  151. SkClipOp op, bool doAA) {
  152. if (m.rectStaysRect()) {
  153. SkRect devRect;
  154. m.mapRect(&devRect, rect);
  155. fDeviceSpaceRRect.setRect(devRect);
  156. fDeviceSpaceType = DeviceSpaceType::kRect;
  157. this->initCommon(saveCount, op, doAA);
  158. return;
  159. }
  160. SkPath path;
  161. path.addRect(rect);
  162. path.setIsVolatile(true);
  163. this->initAsPath(saveCount, path, m, op, doAA);
  164. }
  165. void SkClipStack::Element::initRRect(int saveCount, const SkRRect& rrect, const SkMatrix& m,
  166. SkClipOp op, bool doAA) {
  167. if (rrect.transform(m, &fDeviceSpaceRRect)) {
  168. SkRRect::Type type = fDeviceSpaceRRect.getType();
  169. if (SkRRect::kRect_Type == type || SkRRect::kEmpty_Type == type) {
  170. fDeviceSpaceType = DeviceSpaceType::kRect;
  171. } else {
  172. fDeviceSpaceType = DeviceSpaceType::kRRect;
  173. }
  174. this->initCommon(saveCount, op, doAA);
  175. return;
  176. }
  177. SkPath path;
  178. path.addRRect(rrect);
  179. path.setIsVolatile(true);
  180. this->initAsPath(saveCount, path, m, op, doAA);
  181. }
  182. void SkClipStack::Element::initPath(int saveCount, const SkPath& path, const SkMatrix& m,
  183. SkClipOp op, bool doAA) {
  184. if (!path.isInverseFillType()) {
  185. SkRect r;
  186. if (path.isRect(&r)) {
  187. this->initRect(saveCount, r, m, op, doAA);
  188. return;
  189. }
  190. SkRect ovalRect;
  191. if (path.isOval(&ovalRect)) {
  192. SkRRect rrect;
  193. rrect.setOval(ovalRect);
  194. this->initRRect(saveCount, rrect, m, op, doAA);
  195. return;
  196. }
  197. }
  198. this->initAsPath(saveCount, path, m, op, doAA);
  199. }
  200. void SkClipStack::Element::initAsPath(int saveCount, const SkPath& path, const SkMatrix& m,
  201. SkClipOp op, bool doAA) {
  202. path.transform(m, fDeviceSpacePath.init());
  203. fDeviceSpacePath.get()->setIsVolatile(true);
  204. fDeviceSpaceType = DeviceSpaceType::kPath;
  205. this->initCommon(saveCount, op, doAA);
  206. }
  207. void SkClipStack::Element::asDeviceSpacePath(SkPath* path) const {
  208. switch (fDeviceSpaceType) {
  209. case DeviceSpaceType::kEmpty:
  210. path->reset();
  211. break;
  212. case DeviceSpaceType::kRect:
  213. path->reset();
  214. path->addRect(this->getDeviceSpaceRect());
  215. break;
  216. case DeviceSpaceType::kRRect:
  217. path->reset();
  218. path->addRRect(fDeviceSpaceRRect);
  219. break;
  220. case DeviceSpaceType::kPath:
  221. *path = *fDeviceSpacePath.get();
  222. break;
  223. }
  224. path->setIsVolatile(true);
  225. }
  226. void SkClipStack::Element::setEmpty() {
  227. fDeviceSpaceType = DeviceSpaceType::kEmpty;
  228. fFiniteBound.setEmpty();
  229. fFiniteBoundType = kNormal_BoundsType;
  230. fIsIntersectionOfRects = false;
  231. fDeviceSpaceRRect.setEmpty();
  232. fDeviceSpacePath.reset();
  233. fGenID = kEmptyGenID;
  234. SkDEBUGCODE(this->checkEmpty();)
  235. }
  236. void SkClipStack::Element::checkEmpty() const {
  237. SkASSERT(fFiniteBound.isEmpty());
  238. SkASSERT(kNormal_BoundsType == fFiniteBoundType);
  239. SkASSERT(!fIsIntersectionOfRects);
  240. SkASSERT(kEmptyGenID == fGenID);
  241. SkASSERT(fDeviceSpaceRRect.isEmpty());
  242. SkASSERT(!fDeviceSpacePath.isValid());
  243. }
  244. bool SkClipStack::Element::canBeIntersectedInPlace(int saveCount, SkClipOp op) const {
  245. if (DeviceSpaceType::kEmpty == fDeviceSpaceType &&
  246. (kDifference_SkClipOp == op || kIntersect_SkClipOp == op)) {
  247. return true;
  248. }
  249. // Only clips within the same save/restore frame (as captured by
  250. // the save count) can be merged
  251. return fSaveCount == saveCount &&
  252. kIntersect_SkClipOp == op &&
  253. (kIntersect_SkClipOp == fOp || kReplace_SkClipOp == fOp);
  254. }
  255. bool SkClipStack::Element::rectRectIntersectAllowed(const SkRect& newR, bool newAA) const {
  256. SkASSERT(DeviceSpaceType::kRect == fDeviceSpaceType);
  257. if (fDoAA == newAA) {
  258. // if the AA setting is the same there is no issue
  259. return true;
  260. }
  261. if (!SkRect::Intersects(this->getDeviceSpaceRect(), newR)) {
  262. // The calling code will correctly set the result to the empty clip
  263. return true;
  264. }
  265. if (this->getDeviceSpaceRect().contains(newR)) {
  266. // if the new rect carves out a portion of the old one there is no
  267. // issue
  268. return true;
  269. }
  270. // So either the two overlap in some complex manner or newR contains oldR.
  271. // In the first, case the edges will require different AA. In the second,
  272. // the AA setting that would be carried forward is incorrect (e.g., oldR
  273. // is AA while newR is BW but since newR contains oldR, oldR will be
  274. // drawn BW) since the new AA setting will predominate.
  275. return false;
  276. }
  277. // a mirror of combineBoundsRevDiff
  278. void SkClipStack::Element::combineBoundsDiff(FillCombo combination, const SkRect& prevFinite) {
  279. switch (combination) {
  280. case kInvPrev_InvCur_FillCombo:
  281. // In this case the only pixels that can remain set
  282. // are inside the current clip rect since the extensions
  283. // to infinity of both clips cancel out and whatever
  284. // is outside of the current clip is removed
  285. fFiniteBoundType = kNormal_BoundsType;
  286. break;
  287. case kInvPrev_Cur_FillCombo:
  288. // In this case the current op is finite so the only pixels
  289. // that aren't set are whatever isn't set in the previous
  290. // clip and whatever this clip carves out
  291. fFiniteBound.join(prevFinite);
  292. fFiniteBoundType = kInsideOut_BoundsType;
  293. break;
  294. case kPrev_InvCur_FillCombo:
  295. // In this case everything outside of this clip's bound
  296. // is erased, so the only pixels that can remain set
  297. // occur w/in the intersection of the two finite bounds
  298. if (!fFiniteBound.intersect(prevFinite)) {
  299. fFiniteBound.setEmpty();
  300. fGenID = kEmptyGenID;
  301. }
  302. fFiniteBoundType = kNormal_BoundsType;
  303. break;
  304. case kPrev_Cur_FillCombo:
  305. // The most conservative result bound is that of the
  306. // prior clip. This could be wildly incorrect if the
  307. // second clip either exactly matches the first clip
  308. // (which should yield the empty set) or reduces the
  309. // size of the prior bound (e.g., if the second clip
  310. // exactly matched the bottom half of the prior clip).
  311. // We ignore these two possibilities.
  312. fFiniteBound = prevFinite;
  313. break;
  314. default:
  315. SkDEBUGFAIL("SkClipStack::Element::combineBoundsDiff Invalid fill combination");
  316. break;
  317. }
  318. }
  319. void SkClipStack::Element::combineBoundsXOR(int combination, const SkRect& prevFinite) {
  320. switch (combination) {
  321. case kInvPrev_Cur_FillCombo: // fall through
  322. case kPrev_InvCur_FillCombo:
  323. // With only one of the clips inverted the result will always
  324. // extend to infinity. The only pixels that may be un-writeable
  325. // lie within the union of the two finite bounds
  326. fFiniteBound.join(prevFinite);
  327. fFiniteBoundType = kInsideOut_BoundsType;
  328. break;
  329. case kInvPrev_InvCur_FillCombo:
  330. // The only pixels that can survive are within the
  331. // union of the two bounding boxes since the extensions
  332. // to infinity of both clips cancel out
  333. // fall through!
  334. case kPrev_Cur_FillCombo:
  335. // The most conservative bound for xor is the
  336. // union of the two bounds. If the two clips exactly overlapped
  337. // the xor could yield the empty set. Similarly the xor
  338. // could reduce the size of the original clip's bound (e.g.,
  339. // if the second clip exactly matched the bottom half of the
  340. // first clip). We ignore these two cases.
  341. fFiniteBound.join(prevFinite);
  342. fFiniteBoundType = kNormal_BoundsType;
  343. break;
  344. default:
  345. SkDEBUGFAIL("SkClipStack::Element::combineBoundsXOR Invalid fill combination");
  346. break;
  347. }
  348. }
  349. // a mirror of combineBoundsIntersection
  350. void SkClipStack::Element::combineBoundsUnion(int combination, const SkRect& prevFinite) {
  351. switch (combination) {
  352. case kInvPrev_InvCur_FillCombo:
  353. if (!fFiniteBound.intersect(prevFinite)) {
  354. fFiniteBound.setEmpty();
  355. fGenID = kWideOpenGenID;
  356. }
  357. fFiniteBoundType = kInsideOut_BoundsType;
  358. break;
  359. case kInvPrev_Cur_FillCombo:
  360. // The only pixels that won't be drawable are inside
  361. // the prior clip's finite bound
  362. fFiniteBound = prevFinite;
  363. fFiniteBoundType = kInsideOut_BoundsType;
  364. break;
  365. case kPrev_InvCur_FillCombo:
  366. // The only pixels that won't be drawable are inside
  367. // this clip's finite bound
  368. break;
  369. case kPrev_Cur_FillCombo:
  370. fFiniteBound.join(prevFinite);
  371. break;
  372. default:
  373. SkDEBUGFAIL("SkClipStack::Element::combineBoundsUnion Invalid fill combination");
  374. break;
  375. }
  376. }
  377. // a mirror of combineBoundsUnion
  378. void SkClipStack::Element::combineBoundsIntersection(int combination, const SkRect& prevFinite) {
  379. switch (combination) {
  380. case kInvPrev_InvCur_FillCombo:
  381. // The only pixels that aren't writable in this case
  382. // occur in the union of the two finite bounds
  383. fFiniteBound.join(prevFinite);
  384. fFiniteBoundType = kInsideOut_BoundsType;
  385. break;
  386. case kInvPrev_Cur_FillCombo:
  387. // In this case the only pixels that will remain writeable
  388. // are within the current clip
  389. break;
  390. case kPrev_InvCur_FillCombo:
  391. // In this case the only pixels that will remain writeable
  392. // are with the previous clip
  393. fFiniteBound = prevFinite;
  394. fFiniteBoundType = kNormal_BoundsType;
  395. break;
  396. case kPrev_Cur_FillCombo:
  397. if (!fFiniteBound.intersect(prevFinite)) {
  398. this->setEmpty();
  399. }
  400. break;
  401. default:
  402. SkDEBUGFAIL("SkClipStack::Element::combineBoundsIntersection Invalid fill combination");
  403. break;
  404. }
  405. }
  406. // a mirror of combineBoundsDiff
  407. void SkClipStack::Element::combineBoundsRevDiff(int combination, const SkRect& prevFinite) {
  408. switch (combination) {
  409. case kInvPrev_InvCur_FillCombo:
  410. // The only pixels that can survive are in the
  411. // previous bound since the extensions to infinity in
  412. // both clips cancel out
  413. fFiniteBound = prevFinite;
  414. fFiniteBoundType = kNormal_BoundsType;
  415. break;
  416. case kInvPrev_Cur_FillCombo:
  417. if (!fFiniteBound.intersect(prevFinite)) {
  418. this->setEmpty();
  419. } else {
  420. fFiniteBoundType = kNormal_BoundsType;
  421. }
  422. break;
  423. case kPrev_InvCur_FillCombo:
  424. fFiniteBound.join(prevFinite);
  425. fFiniteBoundType = kInsideOut_BoundsType;
  426. break;
  427. case kPrev_Cur_FillCombo:
  428. // Fall through - as with the kDifference_Op case, the
  429. // most conservative result bound is the bound of the
  430. // current clip. The prior clip could reduce the size of this
  431. // bound (as in the kDifference_Op case) but we are ignoring
  432. // those cases.
  433. break;
  434. default:
  435. SkDEBUGFAIL("SkClipStack::Element::combineBoundsRevDiff Invalid fill combination");
  436. break;
  437. }
  438. }
  439. void SkClipStack::Element::updateBoundAndGenID(const Element* prior) {
  440. // We set this first here but we may overwrite it later if we determine that the clip is
  441. // either wide-open or empty.
  442. fGenID = GetNextGenID();
  443. // First, optimistically update the current Element's bound information
  444. // with the current clip's bound
  445. fIsIntersectionOfRects = false;
  446. switch (fDeviceSpaceType) {
  447. case DeviceSpaceType::kRect:
  448. fFiniteBound = this->getDeviceSpaceRect();
  449. fFiniteBoundType = kNormal_BoundsType;
  450. if (kReplace_SkClipOp == fOp || (kIntersect_SkClipOp == fOp && nullptr == prior) ||
  451. (kIntersect_SkClipOp == fOp && prior->fIsIntersectionOfRects &&
  452. prior->rectRectIntersectAllowed(this->getDeviceSpaceRect(), fDoAA))) {
  453. fIsIntersectionOfRects = true;
  454. }
  455. break;
  456. case DeviceSpaceType::kRRect:
  457. fFiniteBound = fDeviceSpaceRRect.getBounds();
  458. fFiniteBoundType = kNormal_BoundsType;
  459. break;
  460. case DeviceSpaceType::kPath:
  461. fFiniteBound = fDeviceSpacePath.get()->getBounds();
  462. if (fDeviceSpacePath.get()->isInverseFillType()) {
  463. fFiniteBoundType = kInsideOut_BoundsType;
  464. } else {
  465. fFiniteBoundType = kNormal_BoundsType;
  466. }
  467. break;
  468. case DeviceSpaceType::kEmpty:
  469. SkDEBUGFAIL("We shouldn't get here with an empty element.");
  470. break;
  471. }
  472. // Now determine the previous Element's bound information taking into
  473. // account that there may be no previous clip
  474. SkRect prevFinite;
  475. SkClipStack::BoundsType prevType;
  476. if (nullptr == prior) {
  477. // no prior clip means the entire plane is writable
  478. prevFinite.setEmpty(); // there are no pixels that cannot be drawn to
  479. prevType = kInsideOut_BoundsType;
  480. } else {
  481. prevFinite = prior->fFiniteBound;
  482. prevType = prior->fFiniteBoundType;
  483. }
  484. FillCombo combination = kPrev_Cur_FillCombo;
  485. if (kInsideOut_BoundsType == fFiniteBoundType) {
  486. combination = (FillCombo) (combination | 0x01);
  487. }
  488. if (kInsideOut_BoundsType == prevType) {
  489. combination = (FillCombo) (combination | 0x02);
  490. }
  491. SkASSERT(kInvPrev_InvCur_FillCombo == combination ||
  492. kInvPrev_Cur_FillCombo == combination ||
  493. kPrev_InvCur_FillCombo == combination ||
  494. kPrev_Cur_FillCombo == combination);
  495. // Now integrate with clip with the prior clips
  496. switch (fOp) {
  497. case kDifference_SkClipOp:
  498. this->combineBoundsDiff(combination, prevFinite);
  499. break;
  500. case kXOR_SkClipOp:
  501. this->combineBoundsXOR(combination, prevFinite);
  502. break;
  503. case kUnion_SkClipOp:
  504. this->combineBoundsUnion(combination, prevFinite);
  505. break;
  506. case kIntersect_SkClipOp:
  507. this->combineBoundsIntersection(combination, prevFinite);
  508. break;
  509. case kReverseDifference_SkClipOp:
  510. this->combineBoundsRevDiff(combination, prevFinite);
  511. break;
  512. case kReplace_SkClipOp:
  513. // Replace just ignores everything prior
  514. // The current clip's bound information is already filled in
  515. // so nothing to do
  516. break;
  517. default:
  518. SkDebugf("SkClipOp error\n");
  519. SkASSERT(0);
  520. break;
  521. }
  522. }
  523. // This constant determines how many Element's are allocated together as a block in
  524. // the deque. As such it needs to balance allocating too much memory vs.
  525. // incurring allocation/deallocation thrashing. It should roughly correspond to
  526. // the deepest save/restore stack we expect to see.
  527. static const int kDefaultElementAllocCnt = 8;
  528. SkClipStack::SkClipStack()
  529. : fDeque(sizeof(Element), kDefaultElementAllocCnt)
  530. , fSaveCount(0) {
  531. }
  532. SkClipStack::SkClipStack(void* storage, size_t size)
  533. : fDeque(sizeof(Element), storage, size, kDefaultElementAllocCnt)
  534. , fSaveCount(0) {
  535. }
  536. SkClipStack::SkClipStack(const SkClipStack& b)
  537. : fDeque(sizeof(Element), kDefaultElementAllocCnt) {
  538. *this = b;
  539. }
  540. SkClipStack::~SkClipStack() {
  541. reset();
  542. }
  543. SkClipStack& SkClipStack::operator=(const SkClipStack& b) {
  544. if (this == &b) {
  545. return *this;
  546. }
  547. reset();
  548. fSaveCount = b.fSaveCount;
  549. SkDeque::F2BIter recIter(b.fDeque);
  550. for (const Element* element = (const Element*)recIter.next();
  551. element != nullptr;
  552. element = (const Element*)recIter.next()) {
  553. new (fDeque.push_back()) Element(*element);
  554. }
  555. return *this;
  556. }
  557. bool SkClipStack::operator==(const SkClipStack& b) const {
  558. if (this->getTopmostGenID() == b.getTopmostGenID()) {
  559. return true;
  560. }
  561. if (fSaveCount != b.fSaveCount ||
  562. fDeque.count() != b.fDeque.count()) {
  563. return false;
  564. }
  565. SkDeque::F2BIter myIter(fDeque);
  566. SkDeque::F2BIter bIter(b.fDeque);
  567. const Element* myElement = (const Element*)myIter.next();
  568. const Element* bElement = (const Element*)bIter.next();
  569. while (myElement != nullptr && bElement != nullptr) {
  570. if (*myElement != *bElement) {
  571. return false;
  572. }
  573. myElement = (const Element*)myIter.next();
  574. bElement = (const Element*)bIter.next();
  575. }
  576. return myElement == nullptr && bElement == nullptr;
  577. }
  578. void SkClipStack::reset() {
  579. // We used a placement new for each object in fDeque, so we're responsible
  580. // for calling the destructor on each of them as well.
  581. while (!fDeque.empty()) {
  582. Element* element = (Element*)fDeque.back();
  583. element->~Element();
  584. fDeque.pop_back();
  585. }
  586. fSaveCount = 0;
  587. }
  588. void SkClipStack::save() {
  589. fSaveCount += 1;
  590. }
  591. void SkClipStack::restore() {
  592. fSaveCount -= 1;
  593. restoreTo(fSaveCount);
  594. }
  595. void SkClipStack::restoreTo(int saveCount) {
  596. while (!fDeque.empty()) {
  597. Element* element = (Element*)fDeque.back();
  598. if (element->fSaveCount <= saveCount) {
  599. break;
  600. }
  601. element->~Element();
  602. fDeque.pop_back();
  603. }
  604. }
  605. SkRect SkClipStack::bounds(const SkIRect& deviceBounds) const {
  606. // TODO: optimize this.
  607. SkRect r;
  608. SkClipStack::BoundsType bounds;
  609. this->getBounds(&r, &bounds);
  610. if (bounds == SkClipStack::kInsideOut_BoundsType) {
  611. return SkRect::Make(deviceBounds);
  612. }
  613. return r.intersect(SkRect::Make(deviceBounds)) ? r : SkRect::MakeEmpty();
  614. }
  615. // TODO: optimize this.
  616. bool SkClipStack::isEmpty(const SkIRect& r) const { return this->bounds(r).isEmpty(); }
  617. void SkClipStack::getBounds(SkRect* canvFiniteBound,
  618. BoundsType* boundType,
  619. bool* isIntersectionOfRects) const {
  620. SkASSERT(canvFiniteBound && boundType);
  621. Element* element = (Element*)fDeque.back();
  622. if (nullptr == element) {
  623. // the clip is wide open - the infinite plane w/ no pixels un-writeable
  624. canvFiniteBound->setEmpty();
  625. *boundType = kInsideOut_BoundsType;
  626. if (isIntersectionOfRects) {
  627. *isIntersectionOfRects = false;
  628. }
  629. return;
  630. }
  631. *canvFiniteBound = element->fFiniteBound;
  632. *boundType = element->fFiniteBoundType;
  633. if (isIntersectionOfRects) {
  634. *isIntersectionOfRects = element->fIsIntersectionOfRects;
  635. }
  636. }
  637. bool SkClipStack::internalQuickContains(const SkRect& rect) const {
  638. Iter iter(*this, Iter::kTop_IterStart);
  639. const Element* element = iter.prev();
  640. while (element != nullptr) {
  641. if (kIntersect_SkClipOp != element->getOp() && kReplace_SkClipOp != element->getOp())
  642. return false;
  643. if (element->isInverseFilled()) {
  644. // Part of 'rect' could be trimmed off by the inverse-filled clip element
  645. if (SkRect::Intersects(element->getBounds(), rect)) {
  646. return false;
  647. }
  648. } else {
  649. if (!element->contains(rect)) {
  650. return false;
  651. }
  652. }
  653. if (kReplace_SkClipOp == element->getOp()) {
  654. break;
  655. }
  656. element = iter.prev();
  657. }
  658. return true;
  659. }
  660. bool SkClipStack::internalQuickContains(const SkRRect& rrect) const {
  661. Iter iter(*this, Iter::kTop_IterStart);
  662. const Element* element = iter.prev();
  663. while (element != nullptr) {
  664. if (kIntersect_SkClipOp != element->getOp() && kReplace_SkClipOp != element->getOp())
  665. return false;
  666. if (element->isInverseFilled()) {
  667. // Part of 'rrect' could be trimmed off by the inverse-filled clip element
  668. if (SkRect::Intersects(element->getBounds(), rrect.getBounds())) {
  669. return false;
  670. }
  671. } else {
  672. if (!element->contains(rrect)) {
  673. return false;
  674. }
  675. }
  676. if (kReplace_SkClipOp == element->getOp()) {
  677. break;
  678. }
  679. element = iter.prev();
  680. }
  681. return true;
  682. }
  683. bool SkClipStack::asPath(SkPath *path) const {
  684. bool isAA = false;
  685. path->reset();
  686. path->setFillType(SkPath::kInverseEvenOdd_FillType);
  687. SkClipStack::Iter iter(*this, SkClipStack::Iter::kBottom_IterStart);
  688. while (const SkClipStack::Element* element = iter.next()) {
  689. SkPath operand;
  690. if (element->getDeviceSpaceType() != SkClipStack::Element::DeviceSpaceType::kEmpty) {
  691. element->asDeviceSpacePath(&operand);
  692. }
  693. SkClipOp elementOp = element->getOp();
  694. if (elementOp == kReplace_SkClipOp) {
  695. *path = operand;
  696. } else {
  697. Op(*path, operand, (SkPathOp)elementOp, path);
  698. }
  699. // if the prev and curr clips disagree about aa -vs- not, favor the aa request.
  700. // perhaps we need an API change to avoid this sort of mixed-signals about
  701. // clipping.
  702. isAA = (isAA || element->isAA());
  703. }
  704. return isAA;
  705. }
  706. void SkClipStack::pushElement(const Element& element) {
  707. // Use reverse iterator instead of back because Rect path may need previous
  708. SkDeque::Iter iter(fDeque, SkDeque::Iter::kBack_IterStart);
  709. Element* prior = (Element*) iter.prev();
  710. if (prior) {
  711. if (prior->canBeIntersectedInPlace(fSaveCount, element.getOp())) {
  712. switch (prior->fDeviceSpaceType) {
  713. case Element::DeviceSpaceType::kEmpty:
  714. SkDEBUGCODE(prior->checkEmpty();)
  715. return;
  716. case Element::DeviceSpaceType::kRect:
  717. if (Element::DeviceSpaceType::kRect == element.getDeviceSpaceType()) {
  718. if (prior->rectRectIntersectAllowed(element.getDeviceSpaceRect(),
  719. element.isAA())) {
  720. SkRect isectRect;
  721. if (!isectRect.intersect(prior->getDeviceSpaceRect(),
  722. element.getDeviceSpaceRect())) {
  723. prior->setEmpty();
  724. return;
  725. }
  726. prior->fDeviceSpaceRRect.setRect(isectRect);
  727. prior->fDoAA = element.isAA();
  728. Element* priorPrior = (Element*) iter.prev();
  729. prior->updateBoundAndGenID(priorPrior);
  730. return;
  731. }
  732. break;
  733. }
  734. // fallthrough
  735. default:
  736. if (!SkRect::Intersects(prior->getBounds(), element.getBounds())) {
  737. prior->setEmpty();
  738. return;
  739. }
  740. break;
  741. }
  742. } else if (kReplace_SkClipOp == element.getOp()) {
  743. this->restoreTo(fSaveCount - 1);
  744. prior = (Element*) fDeque.back();
  745. }
  746. }
  747. Element* newElement = new (fDeque.push_back()) Element(element);
  748. newElement->updateBoundAndGenID(prior);
  749. }
  750. void SkClipStack::clipRRect(const SkRRect& rrect, const SkMatrix& matrix, SkClipOp op,
  751. bool doAA) {
  752. Element element(fSaveCount, rrect, matrix, op, doAA);
  753. this->pushElement(element);
  754. if (this->hasClipRestriction(op)) {
  755. Element restriction(fSaveCount, fClipRestrictionRect, SkMatrix::I(), kIntersect_SkClipOp,
  756. false);
  757. this->pushElement(restriction);
  758. }
  759. }
  760. void SkClipStack::clipRect(const SkRect& rect, const SkMatrix& matrix, SkClipOp op,
  761. bool doAA) {
  762. Element element(fSaveCount, rect, matrix, op, doAA);
  763. this->pushElement(element);
  764. if (this->hasClipRestriction(op)) {
  765. Element restriction(fSaveCount, fClipRestrictionRect, SkMatrix::I(), kIntersect_SkClipOp,
  766. false);
  767. this->pushElement(restriction);
  768. }
  769. }
  770. void SkClipStack::clipPath(const SkPath& path, const SkMatrix& matrix, SkClipOp op,
  771. bool doAA) {
  772. Element element(fSaveCount, path, matrix, op, doAA);
  773. this->pushElement(element);
  774. if (this->hasClipRestriction(op)) {
  775. Element restriction(fSaveCount, fClipRestrictionRect, SkMatrix::I(), kIntersect_SkClipOp,
  776. false);
  777. this->pushElement(restriction);
  778. }
  779. }
  780. void SkClipStack::clipEmpty() {
  781. Element* element = (Element*) fDeque.back();
  782. if (element && element->canBeIntersectedInPlace(fSaveCount, kIntersect_SkClipOp)) {
  783. element->setEmpty();
  784. }
  785. new (fDeque.push_back()) Element(fSaveCount);
  786. ((Element*)fDeque.back())->fGenID = kEmptyGenID;
  787. }
  788. ///////////////////////////////////////////////////////////////////////////////
  789. SkClipStack::Iter::Iter() : fStack(nullptr) {
  790. }
  791. SkClipStack::Iter::Iter(const SkClipStack& stack, IterStart startLoc)
  792. : fStack(&stack) {
  793. this->reset(stack, startLoc);
  794. }
  795. const SkClipStack::Element* SkClipStack::Iter::next() {
  796. return (const SkClipStack::Element*)fIter.next();
  797. }
  798. const SkClipStack::Element* SkClipStack::Iter::prev() {
  799. return (const SkClipStack::Element*)fIter.prev();
  800. }
  801. const SkClipStack::Element* SkClipStack::Iter::skipToTopmost(SkClipOp op) {
  802. if (nullptr == fStack) {
  803. return nullptr;
  804. }
  805. fIter.reset(fStack->fDeque, SkDeque::Iter::kBack_IterStart);
  806. const SkClipStack::Element* element = nullptr;
  807. for (element = (const SkClipStack::Element*) fIter.prev();
  808. element;
  809. element = (const SkClipStack::Element*) fIter.prev()) {
  810. if (op == element->fOp) {
  811. // The Deque's iterator is actually one pace ahead of the
  812. // returned value. So while "element" is the element we want to
  813. // return, the iterator is actually pointing at (and will
  814. // return on the next "next" or "prev" call) the element
  815. // in front of it in the deque. Bump the iterator forward a
  816. // step so we get the expected result.
  817. if (nullptr == fIter.next()) {
  818. // The reverse iterator has run off the front of the deque
  819. // (i.e., the "op" clip is the first clip) and can't
  820. // recover. Reset the iterator to start at the front.
  821. fIter.reset(fStack->fDeque, SkDeque::Iter::kFront_IterStart);
  822. }
  823. break;
  824. }
  825. }
  826. if (nullptr == element) {
  827. // There were no "op" clips
  828. fIter.reset(fStack->fDeque, SkDeque::Iter::kFront_IterStart);
  829. }
  830. return this->next();
  831. }
  832. void SkClipStack::Iter::reset(const SkClipStack& stack, IterStart startLoc) {
  833. fStack = &stack;
  834. fIter.reset(stack.fDeque, static_cast<SkDeque::Iter::IterStart>(startLoc));
  835. }
  836. // helper method
  837. void SkClipStack::getConservativeBounds(int offsetX,
  838. int offsetY,
  839. int maxWidth,
  840. int maxHeight,
  841. SkRect* devBounds,
  842. bool* isIntersectionOfRects) const {
  843. SkASSERT(devBounds);
  844. devBounds->setLTRB(0, 0,
  845. SkIntToScalar(maxWidth), SkIntToScalar(maxHeight));
  846. SkRect temp;
  847. SkClipStack::BoundsType boundType;
  848. // temp starts off in canvas space here
  849. this->getBounds(&temp, &boundType, isIntersectionOfRects);
  850. if (SkClipStack::kInsideOut_BoundsType == boundType) {
  851. return;
  852. }
  853. // but is converted to device space here
  854. temp.offset(SkIntToScalar(offsetX), SkIntToScalar(offsetY));
  855. if (!devBounds->intersect(temp)) {
  856. devBounds->setEmpty();
  857. }
  858. }
  859. bool SkClipStack::isRRect(const SkRect& bounds, SkRRect* rrect, bool* aa) const {
  860. const Element* back = static_cast<const Element*>(fDeque.back());
  861. if (!back) {
  862. // TODO: return bounds?
  863. return false;
  864. }
  865. // First check if the entire stack is known to be a rect by the top element.
  866. if (back->fIsIntersectionOfRects && back->fFiniteBoundType == BoundsType::kNormal_BoundsType) {
  867. rrect->setRect(back->fFiniteBound);
  868. *aa = back->isAA();
  869. return true;
  870. }
  871. if (back->getDeviceSpaceType() != SkClipStack::Element::DeviceSpaceType::kRect &&
  872. back->getDeviceSpaceType() != SkClipStack::Element::DeviceSpaceType::kRRect) {
  873. return false;
  874. }
  875. if (back->getOp() == kReplace_SkClipOp) {
  876. *rrect = back->asDeviceSpaceRRect();
  877. *aa = back->isAA();
  878. return true;
  879. }
  880. if (back->getOp() == kIntersect_SkClipOp) {
  881. SkRect backBounds;
  882. if (!backBounds.intersect(bounds, back->asDeviceSpaceRRect().rect())) {
  883. return false;
  884. }
  885. // We limit to 17 elements. This means the back element will be bounds checked at most 16
  886. // times if it is an rrect.
  887. int cnt = fDeque.count();
  888. if (cnt > 17) {
  889. return false;
  890. }
  891. if (cnt > 1) {
  892. SkDeque::Iter iter(fDeque, SkDeque::Iter::kBack_IterStart);
  893. SkAssertResult(static_cast<const Element*>(iter.prev()) == back);
  894. while (const Element* prior = (const Element*)iter.prev()) {
  895. if ((prior->getOp() != kIntersect_SkClipOp &&
  896. prior->getOp() != kReplace_SkClipOp) ||
  897. !prior->contains(backBounds)) {
  898. return false;
  899. }
  900. if (prior->getOp() == kReplace_SkClipOp) {
  901. break;
  902. }
  903. }
  904. }
  905. *rrect = back->asDeviceSpaceRRect();
  906. *aa = back->isAA();
  907. return true;
  908. }
  909. return false;
  910. }
  911. uint32_t SkClipStack::GetNextGenID() {
  912. // 0-2 are reserved for invalid, empty & wide-open
  913. static const uint32_t kFirstUnreservedGenID = 3;
  914. static std::atomic<uint32_t> nextID{kFirstUnreservedGenID};
  915. uint32_t id;
  916. do {
  917. id = nextID++;
  918. } while (id < kFirstUnreservedGenID);
  919. return id;
  920. }
  921. uint32_t SkClipStack::getTopmostGenID() const {
  922. if (fDeque.empty()) {
  923. return kWideOpenGenID;
  924. }
  925. const Element* back = static_cast<const Element*>(fDeque.back());
  926. if (kInsideOut_BoundsType == back->fFiniteBoundType && back->fFiniteBound.isEmpty()) {
  927. return kWideOpenGenID;
  928. }
  929. return back->getGenID();
  930. }
  931. #ifdef SK_DEBUG
  932. void SkClipStack::Element::dump() const {
  933. static const char* kTypeStrings[] = {
  934. "empty",
  935. "rect",
  936. "rrect",
  937. "path"
  938. };
  939. static_assert(0 == static_cast<int>(DeviceSpaceType::kEmpty), "enum mismatch");
  940. static_assert(1 == static_cast<int>(DeviceSpaceType::kRect), "enum mismatch");
  941. static_assert(2 == static_cast<int>(DeviceSpaceType::kRRect), "enum mismatch");
  942. static_assert(3 == static_cast<int>(DeviceSpaceType::kPath), "enum mismatch");
  943. static_assert(SK_ARRAY_COUNT(kTypeStrings) == kTypeCnt, "enum mismatch");
  944. static const char* kOpStrings[] = {
  945. "difference",
  946. "intersect",
  947. "union",
  948. "xor",
  949. "reverse-difference",
  950. "replace",
  951. };
  952. static_assert(0 == static_cast<int>(kDifference_SkClipOp), "enum mismatch");
  953. static_assert(1 == static_cast<int>(kIntersect_SkClipOp), "enum mismatch");
  954. static_assert(2 == static_cast<int>(kUnion_SkClipOp), "enum mismatch");
  955. static_assert(3 == static_cast<int>(kXOR_SkClipOp), "enum mismatch");
  956. static_assert(4 == static_cast<int>(kReverseDifference_SkClipOp), "enum mismatch");
  957. static_assert(5 == static_cast<int>(kReplace_SkClipOp), "enum mismatch");
  958. static_assert(SK_ARRAY_COUNT(kOpStrings) == SkRegion::kOpCnt, "enum mismatch");
  959. SkDebugf("Type: %s, Op: %s, AA: %s, Save Count: %d\n", kTypeStrings[(int)fDeviceSpaceType],
  960. kOpStrings[static_cast<int>(fOp)], (fDoAA ? "yes" : "no"), fSaveCount);
  961. switch (fDeviceSpaceType) {
  962. case DeviceSpaceType::kEmpty:
  963. SkDebugf("\n");
  964. break;
  965. case DeviceSpaceType::kRect:
  966. this->getDeviceSpaceRect().dump();
  967. SkDebugf("\n");
  968. break;
  969. case DeviceSpaceType::kRRect:
  970. this->getDeviceSpaceRRect().dump();
  971. SkDebugf("\n");
  972. break;
  973. case DeviceSpaceType::kPath:
  974. this->getDeviceSpacePath().dump(nullptr, true, false);
  975. break;
  976. }
  977. }
  978. void SkClipStack::dump() const {
  979. B2TIter iter(*this);
  980. const Element* e;
  981. while ((e = iter.next())) {
  982. e->dump();
  983. SkDebugf("\n");
  984. }
  985. }
  986. #endif