SkDConicLineIntersection.cpp 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384
  1. /*
  2. * Copyright 2015 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/SkPathOpsConic.h"
  9. #include "src/pathops/SkPathOpsCurve.h"
  10. #include "src/pathops/SkPathOpsLine.h"
  11. class LineConicIntersections {
  12. public:
  13. enum PinTPoint {
  14. kPointUninitialized,
  15. kPointInitialized
  16. };
  17. LineConicIntersections(const SkDConic& c, const SkDLine& l, SkIntersections* i)
  18. : fConic(c)
  19. , fLine(&l)
  20. , fIntersections(i)
  21. , fAllowNear(true) {
  22. i->setMax(4); // allow short partial coincidence plus discrete intersection
  23. }
  24. LineConicIntersections(const SkDConic& c)
  25. : fConic(c)
  26. SkDEBUGPARAMS(fLine(nullptr))
  27. SkDEBUGPARAMS(fIntersections(nullptr))
  28. SkDEBUGPARAMS(fAllowNear(false)) {
  29. }
  30. void allowNear(bool allow) {
  31. fAllowNear = allow;
  32. }
  33. void checkCoincident() {
  34. int last = fIntersections->used() - 1;
  35. for (int index = 0; index < last; ) {
  36. double conicMidT = ((*fIntersections)[0][index] + (*fIntersections)[0][index + 1]) / 2;
  37. SkDPoint conicMidPt = fConic.ptAtT(conicMidT);
  38. double t = fLine->nearPoint(conicMidPt, nullptr);
  39. if (t < 0) {
  40. ++index;
  41. continue;
  42. }
  43. if (fIntersections->isCoincident(index)) {
  44. fIntersections->removeOne(index);
  45. --last;
  46. } else if (fIntersections->isCoincident(index + 1)) {
  47. fIntersections->removeOne(index + 1);
  48. --last;
  49. } else {
  50. fIntersections->setCoincident(index++);
  51. }
  52. fIntersections->setCoincident(index);
  53. }
  54. }
  55. #ifdef SK_DEBUG
  56. static bool close_to(double a, double b, const double c[3]) {
  57. double max = SkTMax(-SkTMin(SkTMin(c[0], c[1]), c[2]), SkTMax(SkTMax(c[0], c[1]), c[2]));
  58. return approximately_zero_when_compared_to(a - b, max);
  59. }
  60. #endif
  61. int horizontalIntersect(double axisIntercept, double roots[2]) {
  62. double conicVals[] = { fConic[0].fY, fConic[1].fY, fConic[2].fY };
  63. return this->validT(conicVals, axisIntercept, roots);
  64. }
  65. int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) {
  66. this->addExactHorizontalEndPoints(left, right, axisIntercept);
  67. if (fAllowNear) {
  68. this->addNearHorizontalEndPoints(left, right, axisIntercept);
  69. }
  70. double roots[2];
  71. int count = this->horizontalIntersect(axisIntercept, roots);
  72. for (int index = 0; index < count; ++index) {
  73. double conicT = roots[index];
  74. SkDPoint pt = fConic.ptAtT(conicT);
  75. SkDEBUGCODE(double conicVals[] = { fConic[0].fY, fConic[1].fY, fConic[2].fY });
  76. SkOPOBJASSERT(fIntersections, close_to(pt.fY, axisIntercept, conicVals));
  77. double lineT = (pt.fX - left) / (right - left);
  78. if (this->pinTs(&conicT, &lineT, &pt, kPointInitialized)
  79. && this->uniqueAnswer(conicT, pt)) {
  80. fIntersections->insert(conicT, lineT, pt);
  81. }
  82. }
  83. if (flipped) {
  84. fIntersections->flip();
  85. }
  86. this->checkCoincident();
  87. return fIntersections->used();
  88. }
  89. int intersect() {
  90. this->addExactEndPoints();
  91. if (fAllowNear) {
  92. this->addNearEndPoints();
  93. }
  94. double rootVals[2];
  95. int roots = this->intersectRay(rootVals);
  96. for (int index = 0; index < roots; ++index) {
  97. double conicT = rootVals[index];
  98. double lineT = this->findLineT(conicT);
  99. #ifdef SK_DEBUG
  100. if (!fIntersections->globalState()
  101. || !fIntersections->globalState()->debugSkipAssert()) {
  102. SkDEBUGCODE(SkDPoint conicPt = fConic.ptAtT(conicT));
  103. SkDEBUGCODE(SkDPoint linePt = fLine->ptAtT(lineT));
  104. SkASSERT(conicPt.approximatelyDEqual(linePt));
  105. }
  106. #endif
  107. SkDPoint pt;
  108. if (this->pinTs(&conicT, &lineT, &pt, kPointUninitialized)
  109. && this->uniqueAnswer(conicT, pt)) {
  110. fIntersections->insert(conicT, lineT, pt);
  111. }
  112. }
  113. this->checkCoincident();
  114. return fIntersections->used();
  115. }
  116. int intersectRay(double roots[2]) {
  117. double adj = (*fLine)[1].fX - (*fLine)[0].fX;
  118. double opp = (*fLine)[1].fY - (*fLine)[0].fY;
  119. double r[3];
  120. for (int n = 0; n < 3; ++n) {
  121. r[n] = (fConic[n].fY - (*fLine)[0].fY) * adj - (fConic[n].fX - (*fLine)[0].fX) * opp;
  122. }
  123. return this->validT(r, 0, roots);
  124. }
  125. int validT(double r[3], double axisIntercept, double roots[2]) {
  126. double A = r[2];
  127. double B = r[1] * fConic.fWeight - axisIntercept * fConic.fWeight + axisIntercept;
  128. double C = r[0];
  129. A += C - 2 * B; // A = a + c - 2*(b*w - xCept*w + xCept)
  130. B -= C; // B = b*w - w * xCept + xCept - a
  131. C -= axisIntercept;
  132. return SkDQuad::RootsValidT(A, 2 * B, C, roots);
  133. }
  134. int verticalIntersect(double axisIntercept, double roots[2]) {
  135. double conicVals[] = { fConic[0].fX, fConic[1].fX, fConic[2].fX };
  136. return this->validT(conicVals, axisIntercept, roots);
  137. }
  138. int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) {
  139. this->addExactVerticalEndPoints(top, bottom, axisIntercept);
  140. if (fAllowNear) {
  141. this->addNearVerticalEndPoints(top, bottom, axisIntercept);
  142. }
  143. double roots[2];
  144. int count = this->verticalIntersect(axisIntercept, roots);
  145. for (int index = 0; index < count; ++index) {
  146. double conicT = roots[index];
  147. SkDPoint pt = fConic.ptAtT(conicT);
  148. SkDEBUGCODE(double conicVals[] = { fConic[0].fX, fConic[1].fX, fConic[2].fX });
  149. SkOPOBJASSERT(fIntersections, close_to(pt.fX, axisIntercept, conicVals));
  150. double lineT = (pt.fY - top) / (bottom - top);
  151. if (this->pinTs(&conicT, &lineT, &pt, kPointInitialized)
  152. && this->uniqueAnswer(conicT, pt)) {
  153. fIntersections->insert(conicT, lineT, pt);
  154. }
  155. }
  156. if (flipped) {
  157. fIntersections->flip();
  158. }
  159. this->checkCoincident();
  160. return fIntersections->used();
  161. }
  162. protected:
  163. // OPTIMIZE: Functions of the form add .. points are indentical to the conic routines.
  164. // add endpoints first to get zero and one t values exactly
  165. void addExactEndPoints() {
  166. for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
  167. double lineT = fLine->exactPoint(fConic[cIndex]);
  168. if (lineT < 0) {
  169. continue;
  170. }
  171. double conicT = (double) (cIndex >> 1);
  172. fIntersections->insert(conicT, lineT, fConic[cIndex]);
  173. }
  174. }
  175. void addNearEndPoints() {
  176. for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
  177. double conicT = (double) (cIndex >> 1);
  178. if (fIntersections->hasT(conicT)) {
  179. continue;
  180. }
  181. double lineT = fLine->nearPoint(fConic[cIndex], nullptr);
  182. if (lineT < 0) {
  183. continue;
  184. }
  185. fIntersections->insert(conicT, lineT, fConic[cIndex]);
  186. }
  187. this->addLineNearEndPoints();
  188. }
  189. void addLineNearEndPoints() {
  190. for (int lIndex = 0; lIndex < 2; ++lIndex) {
  191. double lineT = (double) lIndex;
  192. if (fIntersections->hasOppT(lineT)) {
  193. continue;
  194. }
  195. double conicT = ((SkDCurve*) &fConic)->nearPoint(SkPath::kConic_Verb,
  196. (*fLine)[lIndex], (*fLine)[!lIndex]);
  197. if (conicT < 0) {
  198. continue;
  199. }
  200. fIntersections->insert(conicT, lineT, (*fLine)[lIndex]);
  201. }
  202. }
  203. void addExactHorizontalEndPoints(double left, double right, double y) {
  204. for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
  205. double lineT = SkDLine::ExactPointH(fConic[cIndex], left, right, y);
  206. if (lineT < 0) {
  207. continue;
  208. }
  209. double conicT = (double) (cIndex >> 1);
  210. fIntersections->insert(conicT, lineT, fConic[cIndex]);
  211. }
  212. }
  213. void addNearHorizontalEndPoints(double left, double right, double y) {
  214. for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
  215. double conicT = (double) (cIndex >> 1);
  216. if (fIntersections->hasT(conicT)) {
  217. continue;
  218. }
  219. double lineT = SkDLine::NearPointH(fConic[cIndex], left, right, y);
  220. if (lineT < 0) {
  221. continue;
  222. }
  223. fIntersections->insert(conicT, lineT, fConic[cIndex]);
  224. }
  225. this->addLineNearEndPoints();
  226. }
  227. void addExactVerticalEndPoints(double top, double bottom, double x) {
  228. for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
  229. double lineT = SkDLine::ExactPointV(fConic[cIndex], top, bottom, x);
  230. if (lineT < 0) {
  231. continue;
  232. }
  233. double conicT = (double) (cIndex >> 1);
  234. fIntersections->insert(conicT, lineT, fConic[cIndex]);
  235. }
  236. }
  237. void addNearVerticalEndPoints(double top, double bottom, double x) {
  238. for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
  239. double conicT = (double) (cIndex >> 1);
  240. if (fIntersections->hasT(conicT)) {
  241. continue;
  242. }
  243. double lineT = SkDLine::NearPointV(fConic[cIndex], top, bottom, x);
  244. if (lineT < 0) {
  245. continue;
  246. }
  247. fIntersections->insert(conicT, lineT, fConic[cIndex]);
  248. }
  249. this->addLineNearEndPoints();
  250. }
  251. double findLineT(double t) {
  252. SkDPoint xy = fConic.ptAtT(t);
  253. double dx = (*fLine)[1].fX - (*fLine)[0].fX;
  254. double dy = (*fLine)[1].fY - (*fLine)[0].fY;
  255. if (fabs(dx) > fabs(dy)) {
  256. return (xy.fX - (*fLine)[0].fX) / dx;
  257. }
  258. return (xy.fY - (*fLine)[0].fY) / dy;
  259. }
  260. bool pinTs(double* conicT, double* lineT, SkDPoint* pt, PinTPoint ptSet) {
  261. if (!approximately_one_or_less_double(*lineT)) {
  262. return false;
  263. }
  264. if (!approximately_zero_or_more_double(*lineT)) {
  265. return false;
  266. }
  267. double qT = *conicT = SkPinT(*conicT);
  268. double lT = *lineT = SkPinT(*lineT);
  269. if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && qT != 0 && qT != 1)) {
  270. *pt = (*fLine).ptAtT(lT);
  271. } else if (ptSet == kPointUninitialized) {
  272. *pt = fConic.ptAtT(qT);
  273. }
  274. SkPoint gridPt = pt->asSkPoint();
  275. if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[0].asSkPoint())) {
  276. *pt = (*fLine)[0];
  277. *lineT = 0;
  278. } else if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[1].asSkPoint())) {
  279. *pt = (*fLine)[1];
  280. *lineT = 1;
  281. }
  282. if (fIntersections->used() > 0 && approximately_equal((*fIntersections)[1][0], *lineT)) {
  283. return false;
  284. }
  285. if (gridPt == fConic[0].asSkPoint()) {
  286. *pt = fConic[0];
  287. *conicT = 0;
  288. } else if (gridPt == fConic[2].asSkPoint()) {
  289. *pt = fConic[2];
  290. *conicT = 1;
  291. }
  292. return true;
  293. }
  294. bool uniqueAnswer(double conicT, const SkDPoint& pt) {
  295. for (int inner = 0; inner < fIntersections->used(); ++inner) {
  296. if (fIntersections->pt(inner) != pt) {
  297. continue;
  298. }
  299. double existingConicT = (*fIntersections)[0][inner];
  300. if (conicT == existingConicT) {
  301. return false;
  302. }
  303. // check if midway on conic is also same point. If so, discard this
  304. double conicMidT = (existingConicT + conicT) / 2;
  305. SkDPoint conicMidPt = fConic.ptAtT(conicMidT);
  306. if (conicMidPt.approximatelyEqual(pt)) {
  307. return false;
  308. }
  309. }
  310. #if ONE_OFF_DEBUG
  311. SkDPoint qPt = fConic.ptAtT(conicT);
  312. SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY,
  313. qPt.fX, qPt.fY);
  314. #endif
  315. return true;
  316. }
  317. private:
  318. const SkDConic& fConic;
  319. const SkDLine* fLine;
  320. SkIntersections* fIntersections;
  321. bool fAllowNear;
  322. };
  323. int SkIntersections::horizontal(const SkDConic& conic, double left, double right, double y,
  324. bool flipped) {
  325. SkDLine line = {{{ left, y }, { right, y }}};
  326. LineConicIntersections c(conic, line, this);
  327. return c.horizontalIntersect(y, left, right, flipped);
  328. }
  329. int SkIntersections::vertical(const SkDConic& conic, double top, double bottom, double x,
  330. bool flipped) {
  331. SkDLine line = {{{ x, top }, { x, bottom }}};
  332. LineConicIntersections c(conic, line, this);
  333. return c.verticalIntersect(x, top, bottom, flipped);
  334. }
  335. int SkIntersections::intersect(const SkDConic& conic, const SkDLine& line) {
  336. LineConicIntersections c(conic, line, this);
  337. c.allowNear(fAllowNear);
  338. return c.intersect();
  339. }
  340. int SkIntersections::intersectRay(const SkDConic& conic, const SkDLine& line) {
  341. LineConicIntersections c(conic, line, this);
  342. fUsed = c.intersectRay(fT[0]);
  343. for (int index = 0; index < fUsed; ++index) {
  344. fPt[index] = conic.ptAtT(fT[0][index]);
  345. }
  346. return fUsed;
  347. }
  348. int SkIntersections::HorizontalIntercept(const SkDConic& conic, SkScalar y, double* roots) {
  349. LineConicIntersections c(conic);
  350. return c.horizontalIntersect(y, roots);
  351. }
  352. int SkIntersections::VerticalIntercept(const SkDConic& conic, SkScalar x, double* roots) {
  353. LineConicIntersections c(conic);
  354. return c.verticalIntersect(x, roots);
  355. }