SkAddIntersections.cpp 27 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579
  1. /*
  2. * Copyright 2012 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 "src/pathops/SkAddIntersections.h"
  8. #include "src/pathops/SkOpCoincidence.h"
  9. #include "src/pathops/SkPathOpsBounds.h"
  10. #include <utility>
  11. #if DEBUG_ADD_INTERSECTING_TS
  12. static void debugShowLineIntersection(int pts, const SkIntersectionHelper& wt,
  13. const SkIntersectionHelper& wn, const SkIntersections& i) {
  14. SkASSERT(i.used() == pts);
  15. if (!pts) {
  16. SkDebugf("%s no intersect " LINE_DEBUG_STR " " LINE_DEBUG_STR "\n",
  17. __FUNCTION__, LINE_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
  18. return;
  19. }
  20. SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " LINE_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
  21. i[0][0], LINE_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
  22. if (pts == 2) {
  23. SkDebugf(" " T_DEBUG_STR(wtTs, 1) " " PT_DEBUG_STR, i[0][1], PT_DEBUG_DATA(i, 1));
  24. }
  25. SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts()));
  26. if (pts == 2) {
  27. SkDebugf(" " T_DEBUG_STR(wnTs, 1), i[1][1]);
  28. }
  29. SkDebugf("\n");
  30. }
  31. static void debugShowQuadLineIntersection(int pts, const SkIntersectionHelper& wt,
  32. const SkIntersectionHelper& wn,
  33. const SkIntersections& i) {
  34. SkASSERT(i.used() == pts);
  35. if (!pts) {
  36. SkDebugf("%s no intersect " QUAD_DEBUG_STR " " LINE_DEBUG_STR "\n",
  37. __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
  38. return;
  39. }
  40. SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
  41. i[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
  42. for (int n = 1; n < pts; ++n) {
  43. SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
  44. }
  45. SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts()));
  46. for (int n = 1; n < pts; ++n) {
  47. SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
  48. }
  49. SkDebugf("\n");
  50. }
  51. static void debugShowQuadIntersection(int pts, const SkIntersectionHelper& wt,
  52. const SkIntersectionHelper& wn, const SkIntersections& i) {
  53. SkASSERT(i.used() == pts);
  54. if (!pts) {
  55. SkDebugf("%s no intersect " QUAD_DEBUG_STR " " QUAD_DEBUG_STR "\n",
  56. __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts()));
  57. return;
  58. }
  59. SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
  60. i[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
  61. for (int n = 1; n < pts; ++n) {
  62. SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
  63. }
  64. SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i[1][0], QUAD_DEBUG_DATA(wn.pts()));
  65. for (int n = 1; n < pts; ++n) {
  66. SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
  67. }
  68. SkDebugf("\n");
  69. }
  70. static void debugShowConicLineIntersection(int pts, const SkIntersectionHelper& wt,
  71. const SkIntersectionHelper& wn, const SkIntersections& i) {
  72. SkASSERT(i.used() == pts);
  73. if (!pts) {
  74. SkDebugf("%s no intersect " CONIC_DEBUG_STR " " LINE_DEBUG_STR "\n",
  75. __FUNCTION__, CONIC_DEBUG_DATA(wt.pts(), wt.weight()), LINE_DEBUG_DATA(wn.pts()));
  76. return;
  77. }
  78. SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CONIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
  79. i[0][0], CONIC_DEBUG_DATA(wt.pts(), wt.weight()), PT_DEBUG_DATA(i, 0));
  80. for (int n = 1; n < pts; ++n) {
  81. SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
  82. }
  83. SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts()));
  84. for (int n = 1; n < pts; ++n) {
  85. SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
  86. }
  87. SkDebugf("\n");
  88. }
  89. static void debugShowConicQuadIntersection(int pts, const SkIntersectionHelper& wt,
  90. const SkIntersectionHelper& wn, const SkIntersections& i) {
  91. SkASSERT(i.used() == pts);
  92. if (!pts) {
  93. SkDebugf("%s no intersect " CONIC_DEBUG_STR " " QUAD_DEBUG_STR "\n",
  94. __FUNCTION__, CONIC_DEBUG_DATA(wt.pts(), wt.weight()), QUAD_DEBUG_DATA(wn.pts()));
  95. return;
  96. }
  97. SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CONIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
  98. i[0][0], CONIC_DEBUG_DATA(wt.pts(), wt.weight()), PT_DEBUG_DATA(i, 0));
  99. for (int n = 1; n < pts; ++n) {
  100. SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
  101. }
  102. SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i[1][0], QUAD_DEBUG_DATA(wn.pts()));
  103. for (int n = 1; n < pts; ++n) {
  104. SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
  105. }
  106. SkDebugf("\n");
  107. }
  108. static void debugShowConicIntersection(int pts, const SkIntersectionHelper& wt,
  109. const SkIntersectionHelper& wn, const SkIntersections& i) {
  110. SkASSERT(i.used() == pts);
  111. if (!pts) {
  112. SkDebugf("%s no intersect " CONIC_DEBUG_STR " " CONIC_DEBUG_STR "\n",
  113. __FUNCTION__, CONIC_DEBUG_DATA(wt.pts(), wt.weight()),
  114. CONIC_DEBUG_DATA(wn.pts(), wn.weight()));
  115. return;
  116. }
  117. SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CONIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
  118. i[0][0], CONIC_DEBUG_DATA(wt.pts(), wt.weight()), PT_DEBUG_DATA(i, 0));
  119. for (int n = 1; n < pts; ++n) {
  120. SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
  121. }
  122. SkDebugf(" wnTs[0]=%g " CONIC_DEBUG_STR, i[1][0], CONIC_DEBUG_DATA(wn.pts(), wn.weight()));
  123. for (int n = 1; n < pts; ++n) {
  124. SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
  125. }
  126. SkDebugf("\n");
  127. }
  128. static void debugShowCubicLineIntersection(int pts, const SkIntersectionHelper& wt,
  129. const SkIntersectionHelper& wn, const SkIntersections& i) {
  130. SkASSERT(i.used() == pts);
  131. if (!pts) {
  132. SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " LINE_DEBUG_STR "\n",
  133. __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
  134. return;
  135. }
  136. SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
  137. i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
  138. for (int n = 1; n < pts; ++n) {
  139. SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
  140. }
  141. SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts()));
  142. for (int n = 1; n < pts; ++n) {
  143. SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
  144. }
  145. SkDebugf("\n");
  146. }
  147. static void debugShowCubicQuadIntersection(int pts, const SkIntersectionHelper& wt,
  148. const SkIntersectionHelper& wn, const SkIntersections& i) {
  149. SkASSERT(i.used() == pts);
  150. if (!pts) {
  151. SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " QUAD_DEBUG_STR "\n",
  152. __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts()));
  153. return;
  154. }
  155. SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
  156. i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
  157. for (int n = 1; n < pts; ++n) {
  158. SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
  159. }
  160. SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i[1][0], QUAD_DEBUG_DATA(wn.pts()));
  161. for (int n = 1; n < pts; ++n) {
  162. SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
  163. }
  164. SkDebugf("\n");
  165. }
  166. static void debugShowCubicConicIntersection(int pts, const SkIntersectionHelper& wt,
  167. const SkIntersectionHelper& wn, const SkIntersections& i) {
  168. SkASSERT(i.used() == pts);
  169. if (!pts) {
  170. SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " CONIC_DEBUG_STR "\n",
  171. __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), CONIC_DEBUG_DATA(wn.pts(), wn.weight()));
  172. return;
  173. }
  174. SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
  175. i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
  176. for (int n = 1; n < pts; ++n) {
  177. SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
  178. }
  179. SkDebugf(" wnTs[0]=%g " CONIC_DEBUG_STR, i[1][0], CONIC_DEBUG_DATA(wn.pts(), wn.weight()));
  180. for (int n = 1; n < pts; ++n) {
  181. SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
  182. }
  183. SkDebugf("\n");
  184. }
  185. static void debugShowCubicIntersection(int pts, const SkIntersectionHelper& wt,
  186. const SkIntersectionHelper& wn, const SkIntersections& i) {
  187. SkASSERT(i.used() == pts);
  188. if (!pts) {
  189. SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " CUBIC_DEBUG_STR "\n",
  190. __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), CUBIC_DEBUG_DATA(wn.pts()));
  191. return;
  192. }
  193. SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
  194. i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
  195. for (int n = 1; n < pts; ++n) {
  196. SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
  197. }
  198. SkDebugf(" wnTs[0]=%g " CUBIC_DEBUG_STR, i[1][0], CUBIC_DEBUG_DATA(wn.pts()));
  199. for (int n = 1; n < pts; ++n) {
  200. SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
  201. }
  202. SkDebugf("\n");
  203. }
  204. #else
  205. static void debugShowLineIntersection(int , const SkIntersectionHelper& ,
  206. const SkIntersectionHelper& , const SkIntersections& ) {
  207. }
  208. static void debugShowQuadLineIntersection(int , const SkIntersectionHelper& ,
  209. const SkIntersectionHelper& , const SkIntersections& ) {
  210. }
  211. static void debugShowQuadIntersection(int , const SkIntersectionHelper& ,
  212. const SkIntersectionHelper& , const SkIntersections& ) {
  213. }
  214. static void debugShowConicLineIntersection(int , const SkIntersectionHelper& ,
  215. const SkIntersectionHelper& , const SkIntersections& ) {
  216. }
  217. static void debugShowConicQuadIntersection(int , const SkIntersectionHelper& ,
  218. const SkIntersectionHelper& , const SkIntersections& ) {
  219. }
  220. static void debugShowConicIntersection(int , const SkIntersectionHelper& ,
  221. const SkIntersectionHelper& , const SkIntersections& ) {
  222. }
  223. static void debugShowCubicLineIntersection(int , const SkIntersectionHelper& ,
  224. const SkIntersectionHelper& , const SkIntersections& ) {
  225. }
  226. static void debugShowCubicQuadIntersection(int , const SkIntersectionHelper& ,
  227. const SkIntersectionHelper& , const SkIntersections& ) {
  228. }
  229. static void debugShowCubicConicIntersection(int , const SkIntersectionHelper& ,
  230. const SkIntersectionHelper& , const SkIntersections& ) {
  231. }
  232. static void debugShowCubicIntersection(int , const SkIntersectionHelper& ,
  233. const SkIntersectionHelper& , const SkIntersections& ) {
  234. }
  235. #endif
  236. bool AddIntersectTs(SkOpContour* test, SkOpContour* next, SkOpCoincidence* coincidence) {
  237. if (test != next) {
  238. if (AlmostLessUlps(test->bounds().fBottom, next->bounds().fTop)) {
  239. return false;
  240. }
  241. // OPTIMIZATION: outset contour bounds a smidgen instead?
  242. if (!SkPathOpsBounds::Intersects(test->bounds(), next->bounds())) {
  243. return true;
  244. }
  245. }
  246. SkIntersectionHelper wt;
  247. wt.init(test);
  248. do {
  249. SkIntersectionHelper wn;
  250. wn.init(next);
  251. test->debugValidate();
  252. next->debugValidate();
  253. if (test == next && !wn.startAfter(wt)) {
  254. continue;
  255. }
  256. do {
  257. if (!SkPathOpsBounds::Intersects(wt.bounds(), wn.bounds())) {
  258. continue;
  259. }
  260. int pts = 0;
  261. SkIntersections ts { SkDEBUGCODE(test->globalState()) };
  262. bool swap = false;
  263. SkDQuad quad1, quad2;
  264. SkDConic conic1, conic2;
  265. SkDCubic cubic1, cubic2;
  266. switch (wt.segmentType()) {
  267. case SkIntersectionHelper::kHorizontalLine_Segment:
  268. swap = true;
  269. switch (wn.segmentType()) {
  270. case SkIntersectionHelper::kHorizontalLine_Segment:
  271. case SkIntersectionHelper::kVerticalLine_Segment:
  272. case SkIntersectionHelper::kLine_Segment:
  273. pts = ts.lineHorizontal(wn.pts(), wt.left(),
  274. wt.right(), wt.y(), wt.xFlipped());
  275. debugShowLineIntersection(pts, wn, wt, ts);
  276. break;
  277. case SkIntersectionHelper::kQuad_Segment:
  278. pts = ts.quadHorizontal(wn.pts(), wt.left(),
  279. wt.right(), wt.y(), wt.xFlipped());
  280. debugShowQuadLineIntersection(pts, wn, wt, ts);
  281. break;
  282. case SkIntersectionHelper::kConic_Segment:
  283. pts = ts.conicHorizontal(wn.pts(), wn.weight(), wt.left(),
  284. wt.right(), wt.y(), wt.xFlipped());
  285. debugShowConicLineIntersection(pts, wn, wt, ts);
  286. break;
  287. case SkIntersectionHelper::kCubic_Segment:
  288. pts = ts.cubicHorizontal(wn.pts(), wt.left(),
  289. wt.right(), wt.y(), wt.xFlipped());
  290. debugShowCubicLineIntersection(pts, wn, wt, ts);
  291. break;
  292. default:
  293. SkASSERT(0);
  294. }
  295. break;
  296. case SkIntersectionHelper::kVerticalLine_Segment:
  297. swap = true;
  298. switch (wn.segmentType()) {
  299. case SkIntersectionHelper::kHorizontalLine_Segment:
  300. case SkIntersectionHelper::kVerticalLine_Segment:
  301. case SkIntersectionHelper::kLine_Segment: {
  302. pts = ts.lineVertical(wn.pts(), wt.top(),
  303. wt.bottom(), wt.x(), wt.yFlipped());
  304. debugShowLineIntersection(pts, wn, wt, ts);
  305. break;
  306. }
  307. case SkIntersectionHelper::kQuad_Segment: {
  308. pts = ts.quadVertical(wn.pts(), wt.top(),
  309. wt.bottom(), wt.x(), wt.yFlipped());
  310. debugShowQuadLineIntersection(pts, wn, wt, ts);
  311. break;
  312. }
  313. case SkIntersectionHelper::kConic_Segment: {
  314. pts = ts.conicVertical(wn.pts(), wn.weight(), wt.top(),
  315. wt.bottom(), wt.x(), wt.yFlipped());
  316. debugShowConicLineIntersection(pts, wn, wt, ts);
  317. break;
  318. }
  319. case SkIntersectionHelper::kCubic_Segment: {
  320. pts = ts.cubicVertical(wn.pts(), wt.top(),
  321. wt.bottom(), wt.x(), wt.yFlipped());
  322. debugShowCubicLineIntersection(pts, wn, wt, ts);
  323. break;
  324. }
  325. default:
  326. SkASSERT(0);
  327. }
  328. break;
  329. case SkIntersectionHelper::kLine_Segment:
  330. switch (wn.segmentType()) {
  331. case SkIntersectionHelper::kHorizontalLine_Segment:
  332. pts = ts.lineHorizontal(wt.pts(), wn.left(),
  333. wn.right(), wn.y(), wn.xFlipped());
  334. debugShowLineIntersection(pts, wt, wn, ts);
  335. break;
  336. case SkIntersectionHelper::kVerticalLine_Segment:
  337. pts = ts.lineVertical(wt.pts(), wn.top(),
  338. wn.bottom(), wn.x(), wn.yFlipped());
  339. debugShowLineIntersection(pts, wt, wn, ts);
  340. break;
  341. case SkIntersectionHelper::kLine_Segment:
  342. pts = ts.lineLine(wt.pts(), wn.pts());
  343. debugShowLineIntersection(pts, wt, wn, ts);
  344. break;
  345. case SkIntersectionHelper::kQuad_Segment:
  346. swap = true;
  347. pts = ts.quadLine(wn.pts(), wt.pts());
  348. debugShowQuadLineIntersection(pts, wn, wt, ts);
  349. break;
  350. case SkIntersectionHelper::kConic_Segment:
  351. swap = true;
  352. pts = ts.conicLine(wn.pts(), wn.weight(), wt.pts());
  353. debugShowConicLineIntersection(pts, wn, wt, ts);
  354. break;
  355. case SkIntersectionHelper::kCubic_Segment:
  356. swap = true;
  357. pts = ts.cubicLine(wn.pts(), wt.pts());
  358. debugShowCubicLineIntersection(pts, wn, wt, ts);
  359. break;
  360. default:
  361. SkASSERT(0);
  362. }
  363. break;
  364. case SkIntersectionHelper::kQuad_Segment:
  365. switch (wn.segmentType()) {
  366. case SkIntersectionHelper::kHorizontalLine_Segment:
  367. pts = ts.quadHorizontal(wt.pts(), wn.left(),
  368. wn.right(), wn.y(), wn.xFlipped());
  369. debugShowQuadLineIntersection(pts, wt, wn, ts);
  370. break;
  371. case SkIntersectionHelper::kVerticalLine_Segment:
  372. pts = ts.quadVertical(wt.pts(), wn.top(),
  373. wn.bottom(), wn.x(), wn.yFlipped());
  374. debugShowQuadLineIntersection(pts, wt, wn, ts);
  375. break;
  376. case SkIntersectionHelper::kLine_Segment:
  377. pts = ts.quadLine(wt.pts(), wn.pts());
  378. debugShowQuadLineIntersection(pts, wt, wn, ts);
  379. break;
  380. case SkIntersectionHelper::kQuad_Segment: {
  381. pts = ts.intersect(quad1.set(wt.pts()), quad2.set(wn.pts()));
  382. debugShowQuadIntersection(pts, wt, wn, ts);
  383. break;
  384. }
  385. case SkIntersectionHelper::kConic_Segment: {
  386. swap = true;
  387. pts = ts.intersect(conic2.set(wn.pts(), wn.weight()),
  388. quad1.set(wt.pts()));
  389. debugShowConicQuadIntersection(pts, wn, wt, ts);
  390. break;
  391. }
  392. case SkIntersectionHelper::kCubic_Segment: {
  393. swap = true;
  394. pts = ts.intersect(cubic2.set(wn.pts()), quad1.set(wt.pts()));
  395. debugShowCubicQuadIntersection(pts, wn, wt, ts);
  396. break;
  397. }
  398. default:
  399. SkASSERT(0);
  400. }
  401. break;
  402. case SkIntersectionHelper::kConic_Segment:
  403. switch (wn.segmentType()) {
  404. case SkIntersectionHelper::kHorizontalLine_Segment:
  405. pts = ts.conicHorizontal(wt.pts(), wt.weight(), wn.left(),
  406. wn.right(), wn.y(), wn.xFlipped());
  407. debugShowConicLineIntersection(pts, wt, wn, ts);
  408. break;
  409. case SkIntersectionHelper::kVerticalLine_Segment:
  410. pts = ts.conicVertical(wt.pts(), wt.weight(), wn.top(),
  411. wn.bottom(), wn.x(), wn.yFlipped());
  412. debugShowConicLineIntersection(pts, wt, wn, ts);
  413. break;
  414. case SkIntersectionHelper::kLine_Segment:
  415. pts = ts.conicLine(wt.pts(), wt.weight(), wn.pts());
  416. debugShowConicLineIntersection(pts, wt, wn, ts);
  417. break;
  418. case SkIntersectionHelper::kQuad_Segment: {
  419. pts = ts.intersect(conic1.set(wt.pts(), wt.weight()),
  420. quad2.set(wn.pts()));
  421. debugShowConicQuadIntersection(pts, wt, wn, ts);
  422. break;
  423. }
  424. case SkIntersectionHelper::kConic_Segment: {
  425. pts = ts.intersect(conic1.set(wt.pts(), wt.weight()),
  426. conic2.set(wn.pts(), wn.weight()));
  427. debugShowConicIntersection(pts, wt, wn, ts);
  428. break;
  429. }
  430. case SkIntersectionHelper::kCubic_Segment: {
  431. swap = true;
  432. pts = ts.intersect(cubic2.set(wn.pts()
  433. SkDEBUGPARAMS(ts.globalState())),
  434. conic1.set(wt.pts(), wt.weight()
  435. SkDEBUGPARAMS(ts.globalState())));
  436. debugShowCubicConicIntersection(pts, wn, wt, ts);
  437. break;
  438. }
  439. }
  440. break;
  441. case SkIntersectionHelper::kCubic_Segment:
  442. switch (wn.segmentType()) {
  443. case SkIntersectionHelper::kHorizontalLine_Segment:
  444. pts = ts.cubicHorizontal(wt.pts(), wn.left(),
  445. wn.right(), wn.y(), wn.xFlipped());
  446. debugShowCubicLineIntersection(pts, wt, wn, ts);
  447. break;
  448. case SkIntersectionHelper::kVerticalLine_Segment:
  449. pts = ts.cubicVertical(wt.pts(), wn.top(),
  450. wn.bottom(), wn.x(), wn.yFlipped());
  451. debugShowCubicLineIntersection(pts, wt, wn, ts);
  452. break;
  453. case SkIntersectionHelper::kLine_Segment:
  454. pts = ts.cubicLine(wt.pts(), wn.pts());
  455. debugShowCubicLineIntersection(pts, wt, wn, ts);
  456. break;
  457. case SkIntersectionHelper::kQuad_Segment: {
  458. pts = ts.intersect(cubic1.set(wt.pts()), quad2.set(wn.pts()));
  459. debugShowCubicQuadIntersection(pts, wt, wn, ts);
  460. break;
  461. }
  462. case SkIntersectionHelper::kConic_Segment: {
  463. pts = ts.intersect(cubic1.set(wt.pts()
  464. SkDEBUGPARAMS(ts.globalState())),
  465. conic2.set(wn.pts(), wn.weight()
  466. SkDEBUGPARAMS(ts.globalState())));
  467. debugShowCubicConicIntersection(pts, wt, wn, ts);
  468. break;
  469. }
  470. case SkIntersectionHelper::kCubic_Segment: {
  471. pts = ts.intersect(cubic1.set(wt.pts()), cubic2.set(wn.pts()));
  472. debugShowCubicIntersection(pts, wt, wn, ts);
  473. break;
  474. }
  475. default:
  476. SkASSERT(0);
  477. }
  478. break;
  479. default:
  480. SkASSERT(0);
  481. }
  482. #if DEBUG_T_SECT_LOOP_COUNT
  483. test->globalState()->debugAddLoopCount(&ts, wt, wn);
  484. #endif
  485. int coinIndex = -1;
  486. SkOpPtT* coinPtT[2];
  487. for (int pt = 0; pt < pts; ++pt) {
  488. SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1);
  489. SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1);
  490. wt.segment()->debugValidate();
  491. // if t value is used to compute pt in addT, error may creep in and
  492. // rect intersections may result in non-rects. if pt value from intersection
  493. // is passed in, current tests break. As a workaround, pass in pt
  494. // value from intersection only if pt.x and pt.y is integral
  495. SkPoint iPt = ts.pt(pt).asSkPoint();
  496. bool iPtIsIntegral = iPt.fX == floor(iPt.fX) && iPt.fY == floor(iPt.fY);
  497. SkOpPtT* testTAt = iPtIsIntegral ? wt.segment()->addT(ts[swap][pt], iPt)
  498. : wt.segment()->addT(ts[swap][pt]);
  499. wn.segment()->debugValidate();
  500. SkOpPtT* nextTAt = iPtIsIntegral ? wn.segment()->addT(ts[!swap][pt], iPt)
  501. : wn.segment()->addT(ts[!swap][pt]);
  502. if (!testTAt->contains(nextTAt)) {
  503. SkOpPtT* oppPrev = testTAt->oppPrev(nextTAt); // Returns nullptr if pair
  504. if (oppPrev) { // already share a pt-t loop.
  505. testTAt->span()->mergeMatches(nextTAt->span());
  506. testTAt->addOpp(nextTAt, oppPrev);
  507. }
  508. if (testTAt->fPt != nextTAt->fPt) {
  509. testTAt->span()->unaligned();
  510. nextTAt->span()->unaligned();
  511. }
  512. wt.segment()->debugValidate();
  513. wn.segment()->debugValidate();
  514. }
  515. if (!ts.isCoincident(pt)) {
  516. continue;
  517. }
  518. if (coinIndex < 0) {
  519. coinPtT[0] = testTAt;
  520. coinPtT[1] = nextTAt;
  521. coinIndex = pt;
  522. continue;
  523. }
  524. if (coinPtT[0]->span() == testTAt->span()) {
  525. coinIndex = -1;
  526. continue;
  527. }
  528. if (coinPtT[1]->span() == nextTAt->span()) {
  529. coinIndex = -1; // coincidence span collapsed
  530. continue;
  531. }
  532. if (swap) {
  533. using std::swap;
  534. swap(coinPtT[0], coinPtT[1]);
  535. swap(testTAt, nextTAt);
  536. }
  537. SkASSERT(coincidence->globalState()->debugSkipAssert()
  538. || coinPtT[0]->span()->t() < testTAt->span()->t());
  539. if (coinPtT[0]->span()->deleted()) {
  540. coinIndex = -1;
  541. continue;
  542. }
  543. if (testTAt->span()->deleted()) {
  544. coinIndex = -1;
  545. continue;
  546. }
  547. coincidence->add(coinPtT[0], testTAt, coinPtT[1], nextTAt);
  548. wt.segment()->debugValidate();
  549. wn.segment()->debugValidate();
  550. coinIndex = -1;
  551. }
  552. SkOPOBJASSERT(coincidence, coinIndex < 0); // expect coincidence to be paired
  553. } while (wn.advance());
  554. } while (wt.advance());
  555. return true;
  556. }