SkDLineIntersection.cpp 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339
  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/SkIntersections.h"
  8. #include "src/pathops/SkPathOpsLine.h"
  9. #include <utility>
  10. void SkIntersections::cleanUpParallelLines(bool parallel) {
  11. while (fUsed > 2) {
  12. removeOne(1);
  13. }
  14. if (fUsed == 2 && !parallel) {
  15. bool startMatch = fT[0][0] == 0 || zero_or_one(fT[1][0]);
  16. bool endMatch = fT[0][1] == 1 || zero_or_one(fT[1][1]);
  17. if ((!startMatch && !endMatch) || approximately_equal(fT[0][0], fT[0][1])) {
  18. SkASSERT(startMatch || endMatch);
  19. if (startMatch && endMatch && (fT[0][0] != 0 || !zero_or_one(fT[1][0]))
  20. && fT[0][1] == 1 && zero_or_one(fT[1][1])) {
  21. removeOne(0);
  22. } else {
  23. removeOne(endMatch);
  24. }
  25. }
  26. }
  27. if (fUsed == 2) {
  28. fIsCoincident[0] = fIsCoincident[1] = 0x03;
  29. }
  30. }
  31. void SkIntersections::computePoints(const SkDLine& line, int used) {
  32. fPt[0] = line.ptAtT(fT[0][0]);
  33. if ((fUsed = used) == 2) {
  34. fPt[1] = line.ptAtT(fT[0][1]);
  35. }
  36. }
  37. int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) {
  38. fMax = 2;
  39. SkDVector aLen = a[1] - a[0];
  40. SkDVector bLen = b[1] - b[0];
  41. /* Slopes match when denom goes to zero:
  42. axLen / ayLen == bxLen / byLen
  43. (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
  44. byLen * axLen == ayLen * bxLen
  45. byLen * axLen - ayLen * bxLen == 0 ( == denom )
  46. */
  47. double denom = bLen.fY * aLen.fX - aLen.fY * bLen.fX;
  48. int used;
  49. if (!approximately_zero(denom)) {
  50. SkDVector ab0 = a[0] - b[0];
  51. double numerA = ab0.fY * bLen.fX - bLen.fY * ab0.fX;
  52. double numerB = ab0.fY * aLen.fX - aLen.fY * ab0.fX;
  53. numerA /= denom;
  54. numerB /= denom;
  55. fT[0][0] = numerA;
  56. fT[1][0] = numerB;
  57. used = 1;
  58. } else {
  59. /* See if the axis intercepts match:
  60. ay - ax * ayLen / axLen == by - bx * ayLen / axLen
  61. axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen)
  62. axLen * ay - ax * ayLen == axLen * by - bx * ayLen
  63. */
  64. if (!AlmostEqualUlps(aLen.fX * a[0].fY - aLen.fY * a[0].fX,
  65. aLen.fX * b[0].fY - aLen.fY * b[0].fX)) {
  66. return fUsed = 0;
  67. }
  68. // there's no great answer for intersection points for coincident rays, but return something
  69. fT[0][0] = fT[1][0] = 0;
  70. fT[1][0] = fT[1][1] = 1;
  71. used = 2;
  72. }
  73. computePoints(a, used);
  74. return fUsed;
  75. }
  76. // note that this only works if both lines are neither horizontal nor vertical
  77. int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) {
  78. fMax = 3; // note that we clean up so that there is no more than two in the end
  79. // see if end points intersect the opposite line
  80. double t;
  81. for (int iA = 0; iA < 2; ++iA) {
  82. if ((t = b.exactPoint(a[iA])) >= 0) {
  83. insert(iA, t, a[iA]);
  84. }
  85. }
  86. for (int iB = 0; iB < 2; ++iB) {
  87. if ((t = a.exactPoint(b[iB])) >= 0) {
  88. insert(t, iB, b[iB]);
  89. }
  90. }
  91. /* Determine the intersection point of two line segments
  92. Return FALSE if the lines don't intersect
  93. from: http://paulbourke.net/geometry/lineline2d/ */
  94. double axLen = a[1].fX - a[0].fX;
  95. double ayLen = a[1].fY - a[0].fY;
  96. double bxLen = b[1].fX - b[0].fX;
  97. double byLen = b[1].fY - b[0].fY;
  98. /* Slopes match when denom goes to zero:
  99. axLen / ayLen == bxLen / byLen
  100. (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
  101. byLen * axLen == ayLen * bxLen
  102. byLen * axLen - ayLen * bxLen == 0 ( == denom )
  103. */
  104. double axByLen = axLen * byLen;
  105. double ayBxLen = ayLen * bxLen;
  106. // detect parallel lines the same way here and in SkOpAngle operator <
  107. // so that non-parallel means they are also sortable
  108. bool unparallel = fAllowNear ? NotAlmostEqualUlps_Pin(axByLen, ayBxLen)
  109. : NotAlmostDequalUlps(axByLen, ayBxLen);
  110. if (unparallel && fUsed == 0) {
  111. double ab0y = a[0].fY - b[0].fY;
  112. double ab0x = a[0].fX - b[0].fX;
  113. double numerA = ab0y * bxLen - byLen * ab0x;
  114. double numerB = ab0y * axLen - ayLen * ab0x;
  115. double denom = axByLen - ayBxLen;
  116. if (between(0, numerA, denom) && between(0, numerB, denom)) {
  117. fT[0][0] = numerA / denom;
  118. fT[1][0] = numerB / denom;
  119. computePoints(a, 1);
  120. }
  121. }
  122. /* Allow tracking that both sets of end points are near each other -- the lines are entirely
  123. coincident -- even when the end points are not exactly the same.
  124. Mark this as a 'wild card' for the end points, so that either point is considered totally
  125. coincident. Then, avoid folding the lines over each other, but allow either end to mate
  126. to the next set of lines.
  127. */
  128. if (fAllowNear || !unparallel) {
  129. double aNearB[2];
  130. double bNearA[2];
  131. bool aNotB[2] = {false, false};
  132. bool bNotA[2] = {false, false};
  133. int nearCount = 0;
  134. for (int index = 0; index < 2; ++index) {
  135. aNearB[index] = t = b.nearPoint(a[index], &aNotB[index]);
  136. nearCount += t >= 0;
  137. bNearA[index] = t = a.nearPoint(b[index], &bNotA[index]);
  138. nearCount += t >= 0;
  139. }
  140. if (nearCount > 0) {
  141. // Skip if each segment contributes to one end point.
  142. if (nearCount != 2 || aNotB[0] == aNotB[1]) {
  143. for (int iA = 0; iA < 2; ++iA) {
  144. if (!aNotB[iA]) {
  145. continue;
  146. }
  147. int nearer = aNearB[iA] > 0.5;
  148. if (!bNotA[nearer]) {
  149. continue;
  150. }
  151. SkASSERT(a[iA] != b[nearer]);
  152. SkOPASSERT(iA == (bNearA[nearer] > 0.5));
  153. insertNear(iA, nearer, a[iA], b[nearer]);
  154. aNearB[iA] = -1;
  155. bNearA[nearer] = -1;
  156. nearCount -= 2;
  157. }
  158. }
  159. if (nearCount > 0) {
  160. for (int iA = 0; iA < 2; ++iA) {
  161. if (aNearB[iA] >= 0) {
  162. insert(iA, aNearB[iA], a[iA]);
  163. }
  164. }
  165. for (int iB = 0; iB < 2; ++iB) {
  166. if (bNearA[iB] >= 0) {
  167. insert(bNearA[iB], iB, b[iB]);
  168. }
  169. }
  170. }
  171. }
  172. }
  173. cleanUpParallelLines(!unparallel);
  174. SkASSERT(fUsed <= 2);
  175. return fUsed;
  176. }
  177. static int horizontal_coincident(const SkDLine& line, double y) {
  178. double min = line[0].fY;
  179. double max = line[1].fY;
  180. if (min > max) {
  181. using std::swap;
  182. swap(min, max);
  183. }
  184. if (min > y || max < y) {
  185. return 0;
  186. }
  187. if (AlmostEqualUlps(min, max) && max - min < fabs(line[0].fX - line[1].fX)) {
  188. return 2;
  189. }
  190. return 1;
  191. }
  192. double SkIntersections::HorizontalIntercept(const SkDLine& line, double y) {
  193. SkASSERT(line[1].fY != line[0].fY);
  194. return SkPinT((y - line[0].fY) / (line[1].fY - line[0].fY));
  195. }
  196. int SkIntersections::horizontal(const SkDLine& line, double left, double right,
  197. double y, bool flipped) {
  198. fMax = 3; // clean up parallel at the end will limit the result to 2 at the most
  199. // see if end points intersect the opposite line
  200. double t;
  201. const SkDPoint leftPt = { left, y };
  202. if ((t = line.exactPoint(leftPt)) >= 0) {
  203. insert(t, (double) flipped, leftPt);
  204. }
  205. if (left != right) {
  206. const SkDPoint rightPt = { right, y };
  207. if ((t = line.exactPoint(rightPt)) >= 0) {
  208. insert(t, (double) !flipped, rightPt);
  209. }
  210. for (int index = 0; index < 2; ++index) {
  211. if ((t = SkDLine::ExactPointH(line[index], left, right, y)) >= 0) {
  212. insert((double) index, flipped ? 1 - t : t, line[index]);
  213. }
  214. }
  215. }
  216. int result = horizontal_coincident(line, y);
  217. if (result == 1 && fUsed == 0) {
  218. fT[0][0] = HorizontalIntercept(line, y);
  219. double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX);
  220. if (between(left, xIntercept, right)) {
  221. fT[1][0] = (xIntercept - left) / (right - left);
  222. if (flipped) {
  223. // OPTIMIZATION: ? instead of swapping, pass original line, use [1].fX - [0].fX
  224. for (int index = 0; index < result; ++index) {
  225. fT[1][index] = 1 - fT[1][index];
  226. }
  227. }
  228. fPt[0].fX = xIntercept;
  229. fPt[0].fY = y;
  230. fUsed = 1;
  231. }
  232. }
  233. if (fAllowNear || result == 2) {
  234. if ((t = line.nearPoint(leftPt, nullptr)) >= 0) {
  235. insert(t, (double) flipped, leftPt);
  236. }
  237. if (left != right) {
  238. const SkDPoint rightPt = { right, y };
  239. if ((t = line.nearPoint(rightPt, nullptr)) >= 0) {
  240. insert(t, (double) !flipped, rightPt);
  241. }
  242. for (int index = 0; index < 2; ++index) {
  243. if ((t = SkDLine::NearPointH(line[index], left, right, y)) >= 0) {
  244. insert((double) index, flipped ? 1 - t : t, line[index]);
  245. }
  246. }
  247. }
  248. }
  249. cleanUpParallelLines(result == 2);
  250. return fUsed;
  251. }
  252. static int vertical_coincident(const SkDLine& line, double x) {
  253. double min = line[0].fX;
  254. double max = line[1].fX;
  255. if (min > max) {
  256. using std::swap;
  257. swap(min, max);
  258. }
  259. if (!precisely_between(min, x, max)) {
  260. return 0;
  261. }
  262. if (AlmostEqualUlps(min, max)) {
  263. return 2;
  264. }
  265. return 1;
  266. }
  267. double SkIntersections::VerticalIntercept(const SkDLine& line, double x) {
  268. SkASSERT(line[1].fX != line[0].fX);
  269. return SkPinT((x - line[0].fX) / (line[1].fX - line[0].fX));
  270. }
  271. int SkIntersections::vertical(const SkDLine& line, double top, double bottom,
  272. double x, bool flipped) {
  273. fMax = 3; // cleanup parallel lines will bring this back line
  274. // see if end points intersect the opposite line
  275. double t;
  276. SkDPoint topPt = { x, top };
  277. if ((t = line.exactPoint(topPt)) >= 0) {
  278. insert(t, (double) flipped, topPt);
  279. }
  280. if (top != bottom) {
  281. SkDPoint bottomPt = { x, bottom };
  282. if ((t = line.exactPoint(bottomPt)) >= 0) {
  283. insert(t, (double) !flipped, bottomPt);
  284. }
  285. for (int index = 0; index < 2; ++index) {
  286. if ((t = SkDLine::ExactPointV(line[index], top, bottom, x)) >= 0) {
  287. insert((double) index, flipped ? 1 - t : t, line[index]);
  288. }
  289. }
  290. }
  291. int result = vertical_coincident(line, x);
  292. if (result == 1 && fUsed == 0) {
  293. fT[0][0] = VerticalIntercept(line, x);
  294. double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY);
  295. if (between(top, yIntercept, bottom)) {
  296. fT[1][0] = (yIntercept - top) / (bottom - top);
  297. if (flipped) {
  298. // OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [0].fY
  299. for (int index = 0; index < result; ++index) {
  300. fT[1][index] = 1 - fT[1][index];
  301. }
  302. }
  303. fPt[0].fX = x;
  304. fPt[0].fY = yIntercept;
  305. fUsed = 1;
  306. }
  307. }
  308. if (fAllowNear || result == 2) {
  309. if ((t = line.nearPoint(topPt, nullptr)) >= 0) {
  310. insert(t, (double) flipped, topPt);
  311. }
  312. if (top != bottom) {
  313. SkDPoint bottomPt = { x, bottom };
  314. if ((t = line.nearPoint(bottomPt, nullptr)) >= 0) {
  315. insert(t, (double) !flipped, bottomPt);
  316. }
  317. for (int index = 0; index < 2; ++index) {
  318. if ((t = SkDLine::NearPointV(line[index], top, bottom, x)) >= 0) {
  319. insert((double) index, flipped ? 1 - t : t, line[index]);
  320. }
  321. }
  322. }
  323. }
  324. cleanUpParallelLines(result == 2);
  325. SkASSERT(fUsed <= 2);
  326. return fUsed;
  327. }