SkPathOpsQuad.cpp 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416
  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/SkLineParameters.h"
  9. #include "src/pathops/SkPathOpsCubic.h"
  10. #include "src/pathops/SkPathOpsCurve.h"
  11. #include "src/pathops/SkPathOpsQuad.h"
  12. #include "src/pathops/SkPathOpsRect.h"
  13. // from blackpawn.com/texts/pointinpoly
  14. static bool pointInTriangle(const SkDPoint fPts[3], const SkDPoint& test) {
  15. SkDVector v0 = fPts[2] - fPts[0];
  16. SkDVector v1 = fPts[1] - fPts[0];
  17. SkDVector v2 = test - fPts[0];
  18. double dot00 = v0.dot(v0);
  19. double dot01 = v0.dot(v1);
  20. double dot02 = v0.dot(v2);
  21. double dot11 = v1.dot(v1);
  22. double dot12 = v1.dot(v2);
  23. // Compute barycentric coordinates
  24. double denom = dot00 * dot11 - dot01 * dot01;
  25. double u = dot11 * dot02 - dot01 * dot12;
  26. double v = dot00 * dot12 - dot01 * dot02;
  27. // Check if point is in triangle
  28. if (denom >= 0) {
  29. return u >= 0 && v >= 0 && u + v < denom;
  30. }
  31. return u <= 0 && v <= 0 && u + v > denom;
  32. }
  33. static bool matchesEnd(const SkDPoint fPts[3], const SkDPoint& test) {
  34. return fPts[0] == test || fPts[2] == test;
  35. }
  36. /* started with at_most_end_pts_in_common from SkDQuadIntersection.cpp */
  37. // Do a quick reject by rotating all points relative to a line formed by
  38. // a pair of one quad's points. If the 2nd quad's points
  39. // are on the line or on the opposite side from the 1st quad's 'odd man', the
  40. // curves at most intersect at the endpoints.
  41. /* if returning true, check contains true if quad's hull collapsed, making the cubic linear
  42. if returning false, check contains true if the the quad pair have only the end point in common
  43. */
  44. bool SkDQuad::hullIntersects(const SkDQuad& q2, bool* isLinear) const {
  45. bool linear = true;
  46. for (int oddMan = 0; oddMan < kPointCount; ++oddMan) {
  47. const SkDPoint* endPt[2];
  48. this->otherPts(oddMan, endPt);
  49. double origX = endPt[0]->fX;
  50. double origY = endPt[0]->fY;
  51. double adj = endPt[1]->fX - origX;
  52. double opp = endPt[1]->fY - origY;
  53. double sign = (fPts[oddMan].fY - origY) * adj - (fPts[oddMan].fX - origX) * opp;
  54. if (approximately_zero(sign)) {
  55. continue;
  56. }
  57. linear = false;
  58. bool foundOutlier = false;
  59. for (int n = 0; n < kPointCount; ++n) {
  60. double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp;
  61. if (test * sign > 0 && !precisely_zero(test)) {
  62. foundOutlier = true;
  63. break;
  64. }
  65. }
  66. if (!foundOutlier) {
  67. return false;
  68. }
  69. }
  70. if (linear && !matchesEnd(fPts, q2.fPts[0]) && !matchesEnd(fPts, q2.fPts[2])) {
  71. // if the end point of the opposite quad is inside the hull that is nearly a line,
  72. // then representing the quad as a line may cause the intersection to be missed.
  73. // Check to see if the endpoint is in the triangle.
  74. if (pointInTriangle(fPts, q2.fPts[0]) || pointInTriangle(fPts, q2.fPts[2])) {
  75. linear = false;
  76. }
  77. }
  78. *isLinear = linear;
  79. return true;
  80. }
  81. bool SkDQuad::hullIntersects(const SkDConic& conic, bool* isLinear) const {
  82. return conic.hullIntersects(*this, isLinear);
  83. }
  84. bool SkDQuad::hullIntersects(const SkDCubic& cubic, bool* isLinear) const {
  85. return cubic.hullIntersects(*this, isLinear);
  86. }
  87. /* bit twiddling for finding the off curve index (x&~m is the pair in [0,1,2] excluding oddMan)
  88. oddMan opp x=oddMan^opp x=x-oddMan m=x>>2 x&~m
  89. 0 1 1 1 0 1
  90. 2 2 2 0 2
  91. 1 1 0 -1 -1 0
  92. 2 3 2 0 2
  93. 2 1 3 1 0 1
  94. 2 0 -2 -1 0
  95. */
  96. void SkDQuad::otherPts(int oddMan, const SkDPoint* endPt[2]) const {
  97. for (int opp = 1; opp < kPointCount; ++opp) {
  98. int end = (oddMan ^ opp) - oddMan; // choose a value not equal to oddMan
  99. end &= ~(end >> 2); // if the value went negative, set it to zero
  100. endPt[opp - 1] = &fPts[end];
  101. }
  102. }
  103. int SkDQuad::AddValidTs(double s[], int realRoots, double* t) {
  104. int foundRoots = 0;
  105. for (int index = 0; index < realRoots; ++index) {
  106. double tValue = s[index];
  107. if (approximately_zero_or_more(tValue) && approximately_one_or_less(tValue)) {
  108. if (approximately_less_than_zero(tValue)) {
  109. tValue = 0;
  110. } else if (approximately_greater_than_one(tValue)) {
  111. tValue = 1;
  112. }
  113. for (int idx2 = 0; idx2 < foundRoots; ++idx2) {
  114. if (approximately_equal(t[idx2], tValue)) {
  115. goto nextRoot;
  116. }
  117. }
  118. t[foundRoots++] = tValue;
  119. }
  120. nextRoot:
  121. {}
  122. }
  123. return foundRoots;
  124. }
  125. // note: caller expects multiple results to be sorted smaller first
  126. // note: http://en.wikipedia.org/wiki/Loss_of_significance has an interesting
  127. // analysis of the quadratic equation, suggesting why the following looks at
  128. // the sign of B -- and further suggesting that the greatest loss of precision
  129. // is in b squared less two a c
  130. int SkDQuad::RootsValidT(double A, double B, double C, double t[2]) {
  131. double s[2];
  132. int realRoots = RootsReal(A, B, C, s);
  133. int foundRoots = AddValidTs(s, realRoots, t);
  134. return foundRoots;
  135. }
  136. static int handle_zero(const double B, const double C, double s[2]) {
  137. if (approximately_zero(B)) {
  138. s[0] = 0;
  139. return C == 0;
  140. }
  141. s[0] = -C / B;
  142. return 1;
  143. }
  144. /*
  145. Numeric Solutions (5.6) suggests to solve the quadratic by computing
  146. Q = -1/2(B + sgn(B)Sqrt(B^2 - 4 A C))
  147. and using the roots
  148. t1 = Q / A
  149. t2 = C / Q
  150. */
  151. // this does not discard real roots <= 0 or >= 1
  152. int SkDQuad::RootsReal(const double A, const double B, const double C, double s[2]) {
  153. if (!A) {
  154. return handle_zero(B, C, s);
  155. }
  156. const double p = B / (2 * A);
  157. const double q = C / A;
  158. if (approximately_zero(A) && (approximately_zero_inverse(p) || approximately_zero_inverse(q))) {
  159. return handle_zero(B, C, s);
  160. }
  161. /* normal form: x^2 + px + q = 0 */
  162. const double p2 = p * p;
  163. if (!AlmostDequalUlps(p2, q) && p2 < q) {
  164. return 0;
  165. }
  166. double sqrt_D = 0;
  167. if (p2 > q) {
  168. sqrt_D = sqrt(p2 - q);
  169. }
  170. s[0] = sqrt_D - p;
  171. s[1] = -sqrt_D - p;
  172. return 1 + !AlmostDequalUlps(s[0], s[1]);
  173. }
  174. bool SkDQuad::isLinear(int startIndex, int endIndex) const {
  175. SkLineParameters lineParameters;
  176. lineParameters.quadEndPoints(*this, startIndex, endIndex);
  177. // FIXME: maybe it's possible to avoid this and compare non-normalized
  178. lineParameters.normalize();
  179. double distance = lineParameters.controlPtDistance(*this);
  180. double tiniest = SkTMin(SkTMin(SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY),
  181. fPts[1].fX), fPts[1].fY), fPts[2].fX), fPts[2].fY);
  182. double largest = SkTMax(SkTMax(SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY),
  183. fPts[1].fX), fPts[1].fY), fPts[2].fX), fPts[2].fY);
  184. largest = SkTMax(largest, -tiniest);
  185. return approximately_zero_when_compared_to(distance, largest);
  186. }
  187. SkDVector SkDQuad::dxdyAtT(double t) const {
  188. double a = t - 1;
  189. double b = 1 - 2 * t;
  190. double c = t;
  191. SkDVector result = { a * fPts[0].fX + b * fPts[1].fX + c * fPts[2].fX,
  192. a * fPts[0].fY + b * fPts[1].fY + c * fPts[2].fY };
  193. if (result.fX == 0 && result.fY == 0) {
  194. if (zero_or_one(t)) {
  195. result = fPts[2] - fPts[0];
  196. } else {
  197. // incomplete
  198. SkDebugf("!q");
  199. }
  200. }
  201. return result;
  202. }
  203. // OPTIMIZE: assert if caller passes in t == 0 / t == 1 ?
  204. SkDPoint SkDQuad::ptAtT(double t) const {
  205. if (0 == t) {
  206. return fPts[0];
  207. }
  208. if (1 == t) {
  209. return fPts[2];
  210. }
  211. double one_t = 1 - t;
  212. double a = one_t * one_t;
  213. double b = 2 * one_t * t;
  214. double c = t * t;
  215. SkDPoint result = { a * fPts[0].fX + b * fPts[1].fX + c * fPts[2].fX,
  216. a * fPts[0].fY + b * fPts[1].fY + c * fPts[2].fY };
  217. return result;
  218. }
  219. static double interp_quad_coords(const double* src, double t) {
  220. if (0 == t) {
  221. return src[0];
  222. }
  223. if (1 == t) {
  224. return src[4];
  225. }
  226. double ab = SkDInterp(src[0], src[2], t);
  227. double bc = SkDInterp(src[2], src[4], t);
  228. double abc = SkDInterp(ab, bc, t);
  229. return abc;
  230. }
  231. bool SkDQuad::monotonicInX() const {
  232. return between(fPts[0].fX, fPts[1].fX, fPts[2].fX);
  233. }
  234. bool SkDQuad::monotonicInY() const {
  235. return between(fPts[0].fY, fPts[1].fY, fPts[2].fY);
  236. }
  237. /*
  238. Given a quadratic q, t1, and t2, find a small quadratic segment.
  239. The new quadratic is defined by A, B, and C, where
  240. A = c[0]*(1 - t1)*(1 - t1) + 2*c[1]*t1*(1 - t1) + c[2]*t1*t1
  241. C = c[3]*(1 - t1)*(1 - t1) + 2*c[2]*t1*(1 - t1) + c[1]*t1*t1
  242. To find B, compute the point halfway between t1 and t2:
  243. q(at (t1 + t2)/2) == D
  244. Next, compute where D must be if we know the value of B:
  245. _12 = A/2 + B/2
  246. 12_ = B/2 + C/2
  247. 123 = A/4 + B/2 + C/4
  248. = D
  249. Group the known values on one side:
  250. B = D*2 - A/2 - C/2
  251. */
  252. // OPTIMIZE? : special case t1 = 1 && t2 = 0
  253. SkDQuad SkDQuad::subDivide(double t1, double t2) const {
  254. if (0 == t1 && 1 == t2) {
  255. return *this;
  256. }
  257. SkDQuad dst;
  258. double ax = dst[0].fX = interp_quad_coords(&fPts[0].fX, t1);
  259. double ay = dst[0].fY = interp_quad_coords(&fPts[0].fY, t1);
  260. double dx = interp_quad_coords(&fPts[0].fX, (t1 + t2) / 2);
  261. double dy = interp_quad_coords(&fPts[0].fY, (t1 + t2) / 2);
  262. double cx = dst[2].fX = interp_quad_coords(&fPts[0].fX, t2);
  263. double cy = dst[2].fY = interp_quad_coords(&fPts[0].fY, t2);
  264. /* bx = */ dst[1].fX = 2 * dx - (ax + cx) / 2;
  265. /* by = */ dst[1].fY = 2 * dy - (ay + cy) / 2;
  266. return dst;
  267. }
  268. void SkDQuad::align(int endIndex, SkDPoint* dstPt) const {
  269. if (fPts[endIndex].fX == fPts[1].fX) {
  270. dstPt->fX = fPts[endIndex].fX;
  271. }
  272. if (fPts[endIndex].fY == fPts[1].fY) {
  273. dstPt->fY = fPts[endIndex].fY;
  274. }
  275. }
  276. SkDPoint SkDQuad::subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2) const {
  277. SkASSERT(t1 != t2);
  278. SkDPoint b;
  279. SkDQuad sub = subDivide(t1, t2);
  280. SkDLine b0 = {{a, sub[1] + (a - sub[0])}};
  281. SkDLine b1 = {{c, sub[1] + (c - sub[2])}};
  282. SkIntersections i;
  283. i.intersectRay(b0, b1);
  284. if (i.used() == 1 && i[0][0] >= 0 && i[1][0] >= 0) {
  285. b = i.pt(0);
  286. } else {
  287. SkASSERT(i.used() <= 2);
  288. return SkDPoint::Mid(b0[1], b1[1]);
  289. }
  290. if (t1 == 0 || t2 == 0) {
  291. align(0, &b);
  292. }
  293. if (t1 == 1 || t2 == 1) {
  294. align(2, &b);
  295. }
  296. if (AlmostBequalUlps(b.fX, a.fX)) {
  297. b.fX = a.fX;
  298. } else if (AlmostBequalUlps(b.fX, c.fX)) {
  299. b.fX = c.fX;
  300. }
  301. if (AlmostBequalUlps(b.fY, a.fY)) {
  302. b.fY = a.fY;
  303. } else if (AlmostBequalUlps(b.fY, c.fY)) {
  304. b.fY = c.fY;
  305. }
  306. return b;
  307. }
  308. /* classic one t subdivision */
  309. static void interp_quad_coords(const double* src, double* dst, double t) {
  310. double ab = SkDInterp(src[0], src[2], t);
  311. double bc = SkDInterp(src[2], src[4], t);
  312. dst[0] = src[0];
  313. dst[2] = ab;
  314. dst[4] = SkDInterp(ab, bc, t);
  315. dst[6] = bc;
  316. dst[8] = src[4];
  317. }
  318. SkDQuadPair SkDQuad::chopAt(double t) const
  319. {
  320. SkDQuadPair dst;
  321. interp_quad_coords(&fPts[0].fX, &dst.pts[0].fX, t);
  322. interp_quad_coords(&fPts[0].fY, &dst.pts[0].fY, t);
  323. return dst;
  324. }
  325. static int valid_unit_divide(double numer, double denom, double* ratio)
  326. {
  327. if (numer < 0) {
  328. numer = -numer;
  329. denom = -denom;
  330. }
  331. if (denom == 0 || numer == 0 || numer >= denom) {
  332. return 0;
  333. }
  334. double r = numer / denom;
  335. if (r == 0) { // catch underflow if numer <<<< denom
  336. return 0;
  337. }
  338. *ratio = r;
  339. return 1;
  340. }
  341. /** Quad'(t) = At + B, where
  342. A = 2(a - 2b + c)
  343. B = 2(b - a)
  344. Solve for t, only if it fits between 0 < t < 1
  345. */
  346. int SkDQuad::FindExtrema(const double src[], double tValue[1]) {
  347. /* At + B == 0
  348. t = -B / A
  349. */
  350. double a = src[0];
  351. double b = src[2];
  352. double c = src[4];
  353. return valid_unit_divide(a - b, a - b - b + c, tValue);
  354. }
  355. /* Parameterization form, given A*t*t + 2*B*t*(1-t) + C*(1-t)*(1-t)
  356. *
  357. * a = A - 2*B + C
  358. * b = 2*B - 2*C
  359. * c = C
  360. */
  361. void SkDQuad::SetABC(const double* quad, double* a, double* b, double* c) {
  362. *a = quad[0]; // a = A
  363. *b = 2 * quad[2]; // b = 2*B
  364. *c = quad[4]; // c = C
  365. *b -= *c; // b = 2*B - C
  366. *a -= *b; // a = A - 2*B + C
  367. *b -= *c; // b = 2*B - 2*C
  368. }
  369. int SkTQuad::intersectRay(SkIntersections* i, const SkDLine& line) const {
  370. return i->intersectRay(fQuad, line);
  371. }
  372. bool SkTQuad::hullIntersects(const SkDConic& conic, bool* isLinear) const {
  373. return conic.hullIntersects(fQuad, isLinear);
  374. }
  375. bool SkTQuad::hullIntersects(const SkDCubic& cubic, bool* isLinear) const {
  376. return cubic.hullIntersects(fQuad, isLinear);
  377. }
  378. void SkTQuad::setBounds(SkDRect* rect) const {
  379. rect->setBounds(fQuad);
  380. }