SkOpAngle.cpp 43 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141
  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/core/SkTSort.h"
  8. #include "src/pathops/SkOpAngle.h"
  9. #include "src/pathops/SkOpSegment.h"
  10. #include "src/pathops/SkPathOpsCurve.h"
  11. /* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest
  12. positive y. The largest angle has a positive x and a zero y. */
  13. #if DEBUG_ANGLE
  14. static bool CompareResult(const char* func, SkString* bugOut, SkString* bugPart, int append,
  15. bool compare) {
  16. SkDebugf("%s %c %d\n", bugOut->c_str(), compare ? 'T' : 'F', append);
  17. SkDebugf("%sPart %s\n", func, bugPart[0].c_str());
  18. SkDebugf("%sPart %s\n", func, bugPart[1].c_str());
  19. SkDebugf("%sPart %s\n", func, bugPart[2].c_str());
  20. return compare;
  21. }
  22. #define COMPARE_RESULT(append, compare) CompareResult(__FUNCTION__, &bugOut, bugPart, append, \
  23. compare)
  24. #else
  25. #define COMPARE_RESULT(append, compare) compare
  26. #endif
  27. /* quarter angle values for sector
  28. 31 x > 0, y == 0 horizontal line (to the right)
  29. 0 x > 0, y == epsilon quad/cubic horizontal tangent eventually going +y
  30. 1 x > 0, y > 0, x > y nearer horizontal angle
  31. 2 x + e == y quad/cubic 45 going horiz
  32. 3 x > 0, y > 0, x == y 45 angle
  33. 4 x == y + e quad/cubic 45 going vert
  34. 5 x > 0, y > 0, x < y nearer vertical angle
  35. 6 x == epsilon, y > 0 quad/cubic vertical tangent eventually going +x
  36. 7 x == 0, y > 0 vertical line (to the top)
  37. 8 7 6
  38. 9 | 5
  39. 10 | 4
  40. 11 | 3
  41. 12 \ | / 2
  42. 13 | 1
  43. 14 | 0
  44. 15 --------------+------------- 31
  45. 16 | 30
  46. 17 | 29
  47. 18 / | \ 28
  48. 19 | 27
  49. 20 | 26
  50. 21 | 25
  51. 22 23 24
  52. */
  53. // return true if lh < this < rh
  54. bool SkOpAngle::after(SkOpAngle* test) {
  55. SkOpAngle* lh = test;
  56. SkOpAngle* rh = lh->fNext;
  57. SkASSERT(lh != rh);
  58. fPart.fCurve = fOriginalCurvePart;
  59. lh->fPart.fCurve = lh->fOriginalCurvePart;
  60. lh->fPart.fCurve.offset(lh->segment()->verb(), fPart.fCurve[0] - lh->fPart.fCurve[0]);
  61. rh->fPart.fCurve = rh->fOriginalCurvePart;
  62. rh->fPart.fCurve.offset(rh->segment()->verb(), fPart.fCurve[0] - rh->fPart.fCurve[0]);
  63. #if DEBUG_ANGLE
  64. SkString bugOut;
  65. bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
  66. " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
  67. " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__,
  68. lh->segment()->debugID(), lh->debugID(), lh->fSectorStart, lh->fSectorEnd,
  69. lh->fStart->t(), lh->fEnd->t(),
  70. segment()->debugID(), debugID(), fSectorStart, fSectorEnd, fStart->t(), fEnd->t(),
  71. rh->segment()->debugID(), rh->debugID(), rh->fSectorStart, rh->fSectorEnd,
  72. rh->fStart->t(), rh->fEnd->t());
  73. SkString bugPart[3] = { lh->debugPart(), this->debugPart(), rh->debugPart() };
  74. #endif
  75. if (lh->fComputeSector && !lh->computeSector()) {
  76. return COMPARE_RESULT(1, true);
  77. }
  78. if (fComputeSector && !this->computeSector()) {
  79. return COMPARE_RESULT(2, true);
  80. }
  81. if (rh->fComputeSector && !rh->computeSector()) {
  82. return COMPARE_RESULT(3, true);
  83. }
  84. #if DEBUG_ANGLE // reset bugOut with computed sectors
  85. bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
  86. " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
  87. " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__,
  88. lh->segment()->debugID(), lh->debugID(), lh->fSectorStart, lh->fSectorEnd,
  89. lh->fStart->t(), lh->fEnd->t(),
  90. segment()->debugID(), debugID(), fSectorStart, fSectorEnd, fStart->t(), fEnd->t(),
  91. rh->segment()->debugID(), rh->debugID(), rh->fSectorStart, rh->fSectorEnd,
  92. rh->fStart->t(), rh->fEnd->t());
  93. #endif
  94. bool ltrOverlap = (lh->fSectorMask | rh->fSectorMask) & fSectorMask;
  95. bool lrOverlap = lh->fSectorMask & rh->fSectorMask;
  96. int lrOrder; // set to -1 if either order works
  97. if (!lrOverlap) { // no lh/rh sector overlap
  98. if (!ltrOverlap) { // no lh/this/rh sector overlap
  99. return COMPARE_RESULT(4, (lh->fSectorEnd > rh->fSectorStart)
  100. ^ (fSectorStart > lh->fSectorEnd) ^ (fSectorStart > rh->fSectorStart));
  101. }
  102. int lrGap = (rh->fSectorStart - lh->fSectorStart + 32) & 0x1f;
  103. /* A tiny change can move the start +/- 4. The order can only be determined if
  104. lr gap is not 12 to 20 or -12 to -20.
  105. -31 ..-21 1
  106. -20 ..-12 -1
  107. -11 .. -1 0
  108. 0 shouldn't get here
  109. 11 .. 1 1
  110. 12 .. 20 -1
  111. 21 .. 31 0
  112. */
  113. lrOrder = lrGap > 20 ? 0 : lrGap > 11 ? -1 : 1;
  114. } else {
  115. lrOrder = lh->orderable(rh);
  116. if (!ltrOverlap && lrOrder >= 0) {
  117. return COMPARE_RESULT(5, !lrOrder);
  118. }
  119. }
  120. int ltOrder;
  121. SkASSERT((lh->fSectorMask & fSectorMask) || (rh->fSectorMask & fSectorMask) || -1 == lrOrder);
  122. if (lh->fSectorMask & fSectorMask) {
  123. ltOrder = lh->orderable(this);
  124. } else {
  125. int ltGap = (fSectorStart - lh->fSectorStart + 32) & 0x1f;
  126. ltOrder = ltGap > 20 ? 0 : ltGap > 11 ? -1 : 1;
  127. }
  128. int trOrder;
  129. if (rh->fSectorMask & fSectorMask) {
  130. trOrder = this->orderable(rh);
  131. } else {
  132. int trGap = (rh->fSectorStart - fSectorStart + 32) & 0x1f;
  133. trOrder = trGap > 20 ? 0 : trGap > 11 ? -1 : 1;
  134. }
  135. this->alignmentSameSide(lh, &ltOrder);
  136. this->alignmentSameSide(rh, &trOrder);
  137. if (lrOrder >= 0 && ltOrder >= 0 && trOrder >= 0) {
  138. return COMPARE_RESULT(7, lrOrder ? (ltOrder & trOrder) : (ltOrder | trOrder));
  139. }
  140. // SkASSERT(lrOrder >= 0 || ltOrder >= 0 || trOrder >= 0);
  141. // There's not enough information to sort. Get the pairs of angles in opposite planes.
  142. // If an order is < 0, the pair is already in an opposite plane. Check the remaining pairs.
  143. // FIXME : once all variants are understood, rewrite this more simply
  144. if (ltOrder == 0 && lrOrder == 0) {
  145. SkASSERT(trOrder < 0);
  146. // FIXME : once this is verified to work, remove one opposite angle call
  147. SkDEBUGCODE(bool lrOpposite = lh->oppositePlanes(rh));
  148. bool ltOpposite = lh->oppositePlanes(this);
  149. SkOPASSERT(lrOpposite != ltOpposite);
  150. return COMPARE_RESULT(8, ltOpposite);
  151. } else if (ltOrder == 1 && trOrder == 0) {
  152. SkASSERT(lrOrder < 0);
  153. bool trOpposite = oppositePlanes(rh);
  154. return COMPARE_RESULT(9, trOpposite);
  155. } else if (lrOrder == 1 && trOrder == 1) {
  156. SkASSERT(ltOrder < 0);
  157. // SkDEBUGCODE(bool trOpposite = oppositePlanes(rh));
  158. bool lrOpposite = lh->oppositePlanes(rh);
  159. // SkASSERT(lrOpposite != trOpposite);
  160. return COMPARE_RESULT(10, lrOpposite);
  161. }
  162. // If a pair couldn't be ordered, there's not enough information to determine the sort.
  163. // Refer to: https://docs.google.com/drawings/d/1KV-8SJTedku9fj4K6fd1SB-8divuV_uivHVsSgwXICQ
  164. if (fUnorderable || lh->fUnorderable || rh->fUnorderable) {
  165. // limit to lines; should work with curves, but wait for a failing test to verify
  166. if (!fPart.isCurve() && !lh->fPart.isCurve() && !rh->fPart.isCurve()) {
  167. // see if original raw data is orderable
  168. // if two share a point, check if third has both points in same half plane
  169. int ltShare = lh->fOriginalCurvePart[0] == fOriginalCurvePart[0];
  170. int lrShare = lh->fOriginalCurvePart[0] == rh->fOriginalCurvePart[0];
  171. int trShare = fOriginalCurvePart[0] == rh->fOriginalCurvePart[0];
  172. // if only one pair are the same, the third point touches neither of the pair
  173. if (ltShare + lrShare + trShare == 1) {
  174. if (lrShare) {
  175. int ltOOrder = lh->linesOnOriginalSide(this);
  176. int rtOOrder = rh->linesOnOriginalSide(this);
  177. if ((rtOOrder ^ ltOOrder) == 1) {
  178. return ltOOrder;
  179. }
  180. } else if (trShare) {
  181. int tlOOrder = this->linesOnOriginalSide(lh);
  182. int rlOOrder = rh->linesOnOriginalSide(lh);
  183. if ((tlOOrder ^ rlOOrder) == 1) {
  184. return rlOOrder;
  185. }
  186. } else {
  187. SkASSERT(ltShare);
  188. int trOOrder = rh->linesOnOriginalSide(this);
  189. int lrOOrder = lh->linesOnOriginalSide(rh);
  190. // result must be 0 and 1 or 1 and 0 to be valid
  191. if ((lrOOrder ^ trOOrder) == 1) {
  192. return trOOrder;
  193. }
  194. }
  195. }
  196. }
  197. }
  198. if (lrOrder < 0) {
  199. if (ltOrder < 0) {
  200. return COMPARE_RESULT(11, trOrder);
  201. }
  202. return COMPARE_RESULT(12, ltOrder);
  203. }
  204. return COMPARE_RESULT(13, !lrOrder);
  205. }
  206. int SkOpAngle::lineOnOneSide(const SkDPoint& origin, const SkDVector& line, const SkOpAngle* test,
  207. bool useOriginal) const {
  208. double crosses[3];
  209. SkPath::Verb testVerb = test->segment()->verb();
  210. int iMax = SkPathOpsVerbToPoints(testVerb);
  211. // SkASSERT(origin == test.fCurveHalf[0]);
  212. const SkDCurve& testCurve = useOriginal ? test->fOriginalCurvePart : test->fPart.fCurve;
  213. for (int index = 1; index <= iMax; ++index) {
  214. double xy1 = line.fX * (testCurve[index].fY - origin.fY);
  215. double xy2 = line.fY * (testCurve[index].fX - origin.fX);
  216. crosses[index - 1] = AlmostBequalUlps(xy1, xy2) ? 0 : xy1 - xy2;
  217. }
  218. if (crosses[0] * crosses[1] < 0) {
  219. return -1;
  220. }
  221. if (SkPath::kCubic_Verb == testVerb) {
  222. if (crosses[0] * crosses[2] < 0 || crosses[1] * crosses[2] < 0) {
  223. return -1;
  224. }
  225. }
  226. if (crosses[0]) {
  227. return crosses[0] < 0;
  228. }
  229. if (crosses[1]) {
  230. return crosses[1] < 0;
  231. }
  232. if (SkPath::kCubic_Verb == testVerb && crosses[2]) {
  233. return crosses[2] < 0;
  234. }
  235. return -2;
  236. }
  237. // given a line, see if the opposite curve's convex hull is all on one side
  238. // returns -1=not on one side 0=this CW of test 1=this CCW of test
  239. int SkOpAngle::lineOnOneSide(const SkOpAngle* test, bool useOriginal) {
  240. SkASSERT(!fPart.isCurve());
  241. SkASSERT(test->fPart.isCurve());
  242. SkDPoint origin = fPart.fCurve[0];
  243. SkDVector line = fPart.fCurve[1] - origin;
  244. int result = this->lineOnOneSide(origin, line, test, useOriginal);
  245. if (-2 == result) {
  246. fUnorderable = true;
  247. result = -1;
  248. }
  249. return result;
  250. }
  251. // experiment works only with lines for now
  252. int SkOpAngle::linesOnOriginalSide(const SkOpAngle* test) {
  253. SkASSERT(!fPart.isCurve());
  254. SkASSERT(!test->fPart.isCurve());
  255. SkDPoint origin = fOriginalCurvePart[0];
  256. SkDVector line = fOriginalCurvePart[1] - origin;
  257. double dots[2];
  258. double crosses[2];
  259. const SkDCurve& testCurve = test->fOriginalCurvePart;
  260. for (int index = 0; index < 2; ++index) {
  261. SkDVector testLine = testCurve[index] - origin;
  262. double xy1 = line.fX * testLine.fY;
  263. double xy2 = line.fY * testLine.fX;
  264. dots[index] = line.fX * testLine.fX + line.fY * testLine.fY;
  265. crosses[index] = AlmostBequalUlps(xy1, xy2) ? 0 : xy1 - xy2;
  266. }
  267. if (crosses[0] * crosses[1] < 0) {
  268. return -1;
  269. }
  270. if (crosses[0]) {
  271. return crosses[0] < 0;
  272. }
  273. if (crosses[1]) {
  274. return crosses[1] < 0;
  275. }
  276. if ((!dots[0] && dots[1] < 0) || (dots[0] < 0 && !dots[1])) {
  277. return 2; // 180 degrees apart
  278. }
  279. fUnorderable = true;
  280. return -1;
  281. }
  282. // To sort the angles, all curves are translated to have the same starting point.
  283. // If the curve's control point in its original position is on one side of a compared line,
  284. // and translated is on the opposite side, reverse the previously computed order.
  285. void SkOpAngle::alignmentSameSide(const SkOpAngle* test, int* order) const {
  286. if (*order < 0) {
  287. return;
  288. }
  289. if (fPart.isCurve()) {
  290. // This should support all curve types, but only bug that requires this has lines
  291. // Turning on for curves causes existing tests to fail
  292. return;
  293. }
  294. if (test->fPart.isCurve()) {
  295. return;
  296. }
  297. const SkDPoint& xOrigin = test->fPart.fCurve.fLine[0];
  298. const SkDPoint& oOrigin = test->fOriginalCurvePart.fLine[0];
  299. if (xOrigin == oOrigin) {
  300. return;
  301. }
  302. int iMax = SkPathOpsVerbToPoints(this->segment()->verb());
  303. SkDVector xLine = test->fPart.fCurve.fLine[1] - xOrigin;
  304. SkDVector oLine = test->fOriginalCurvePart.fLine[1] - oOrigin;
  305. for (int index = 1; index <= iMax; ++index) {
  306. const SkDPoint& testPt = fPart.fCurve[index];
  307. double xCross = oLine.crossCheck(testPt - xOrigin);
  308. double oCross = xLine.crossCheck(testPt - oOrigin);
  309. if (oCross * xCross < 0) {
  310. *order ^= 1;
  311. break;
  312. }
  313. }
  314. }
  315. bool SkOpAngle::checkCrossesZero() const {
  316. int start = SkTMin(fSectorStart, fSectorEnd);
  317. int end = SkTMax(fSectorStart, fSectorEnd);
  318. bool crossesZero = end - start > 16;
  319. return crossesZero;
  320. }
  321. bool SkOpAngle::checkParallel(SkOpAngle* rh) {
  322. SkDVector scratch[2];
  323. const SkDVector* sweep, * tweep;
  324. if (this->fPart.isOrdered()) {
  325. sweep = this->fPart.fSweep;
  326. } else {
  327. scratch[0] = this->fPart.fCurve[1] - this->fPart.fCurve[0];
  328. sweep = &scratch[0];
  329. }
  330. if (rh->fPart.isOrdered()) {
  331. tweep = rh->fPart.fSweep;
  332. } else {
  333. scratch[1] = rh->fPart.fCurve[1] - rh->fPart.fCurve[0];
  334. tweep = &scratch[1];
  335. }
  336. double s0xt0 = sweep->crossCheck(*tweep);
  337. if (tangentsDiverge(rh, s0xt0)) {
  338. return s0xt0 < 0;
  339. }
  340. // compute the perpendicular to the endpoints and see where it intersects the opposite curve
  341. // if the intersections within the t range, do a cross check on those
  342. bool inside;
  343. if (!fEnd->contains(rh->fEnd)) {
  344. if (this->endToSide(rh, &inside)) {
  345. return inside;
  346. }
  347. if (rh->endToSide(this, &inside)) {
  348. return !inside;
  349. }
  350. }
  351. if (this->midToSide(rh, &inside)) {
  352. return inside;
  353. }
  354. if (rh->midToSide(this, &inside)) {
  355. return !inside;
  356. }
  357. // compute the cross check from the mid T values (last resort)
  358. SkDVector m0 = segment()->dPtAtT(this->midT()) - this->fPart.fCurve[0];
  359. SkDVector m1 = rh->segment()->dPtAtT(rh->midT()) - rh->fPart.fCurve[0];
  360. double m0xm1 = m0.crossCheck(m1);
  361. if (m0xm1 == 0) {
  362. this->fUnorderable = true;
  363. rh->fUnorderable = true;
  364. return true;
  365. }
  366. return m0xm1 < 0;
  367. }
  368. // the original angle is too short to get meaningful sector information
  369. // lengthen it until it is long enough to be meaningful or leave it unset if lengthening it
  370. // would cause it to intersect one of the adjacent angles
  371. bool SkOpAngle::computeSector() {
  372. if (fComputedSector) {
  373. return !fUnorderable;
  374. }
  375. fComputedSector = true;
  376. bool stepUp = fStart->t() < fEnd->t();
  377. SkOpSpanBase* checkEnd = fEnd;
  378. if (checkEnd->final() && stepUp) {
  379. fUnorderable = true;
  380. return false;
  381. }
  382. do {
  383. // advance end
  384. const SkOpSegment* other = checkEnd->segment();
  385. const SkOpSpanBase* oSpan = other->head();
  386. do {
  387. if (oSpan->segment() != segment()) {
  388. continue;
  389. }
  390. if (oSpan == checkEnd) {
  391. continue;
  392. }
  393. if (!approximately_equal(oSpan->t(), checkEnd->t())) {
  394. continue;
  395. }
  396. goto recomputeSector;
  397. } while (!oSpan->final() && (oSpan = oSpan->upCast()->next()));
  398. checkEnd = stepUp ? !checkEnd->final()
  399. ? checkEnd->upCast()->next() : nullptr
  400. : checkEnd->prev();
  401. } while (checkEnd);
  402. recomputeSector:
  403. SkOpSpanBase* computedEnd = stepUp ? checkEnd ? checkEnd->prev() : fEnd->segment()->head()
  404. : checkEnd ? checkEnd->upCast()->next() : fEnd->segment()->tail();
  405. if (checkEnd == fEnd || computedEnd == fEnd || computedEnd == fStart) {
  406. fUnorderable = true;
  407. return false;
  408. }
  409. if (stepUp != (fStart->t() < computedEnd->t())) {
  410. fUnorderable = true;
  411. return false;
  412. }
  413. SkOpSpanBase* saveEnd = fEnd;
  414. fComputedEnd = fEnd = computedEnd;
  415. setSpans();
  416. setSector();
  417. fEnd = saveEnd;
  418. return !fUnorderable;
  419. }
  420. int SkOpAngle::convexHullOverlaps(const SkOpAngle* rh) {
  421. const SkDVector* sweep = this->fPart.fSweep;
  422. const SkDVector* tweep = rh->fPart.fSweep;
  423. double s0xs1 = sweep[0].crossCheck(sweep[1]);
  424. double s0xt0 = sweep[0].crossCheck(tweep[0]);
  425. double s1xt0 = sweep[1].crossCheck(tweep[0]);
  426. bool tBetweenS = s0xs1 > 0 ? s0xt0 > 0 && s1xt0 < 0 : s0xt0 < 0 && s1xt0 > 0;
  427. double s0xt1 = sweep[0].crossCheck(tweep[1]);
  428. double s1xt1 = sweep[1].crossCheck(tweep[1]);
  429. tBetweenS |= s0xs1 > 0 ? s0xt1 > 0 && s1xt1 < 0 : s0xt1 < 0 && s1xt1 > 0;
  430. double t0xt1 = tweep[0].crossCheck(tweep[1]);
  431. if (tBetweenS) {
  432. return -1;
  433. }
  434. if ((s0xt0 == 0 && s1xt1 == 0) || (s1xt0 == 0 && s0xt1 == 0)) { // s0 to s1 equals t0 to t1
  435. return -1;
  436. }
  437. bool sBetweenT = t0xt1 > 0 ? s0xt0 < 0 && s0xt1 > 0 : s0xt0 > 0 && s0xt1 < 0;
  438. sBetweenT |= t0xt1 > 0 ? s1xt0 < 0 && s1xt1 > 0 : s1xt0 > 0 && s1xt1 < 0;
  439. if (sBetweenT) {
  440. return -1;
  441. }
  442. // if all of the sweeps are in the same half plane, then the order of any pair is enough
  443. if (s0xt0 >= 0 && s0xt1 >= 0 && s1xt0 >= 0 && s1xt1 >= 0) {
  444. return 0;
  445. }
  446. if (s0xt0 <= 0 && s0xt1 <= 0 && s1xt0 <= 0 && s1xt1 <= 0) {
  447. return 1;
  448. }
  449. // if the outside sweeps are greater than 180 degress:
  450. // first assume the inital tangents are the ordering
  451. // if the midpoint direction matches the inital order, that is enough
  452. SkDVector m0 = this->segment()->dPtAtT(this->midT()) - this->fPart.fCurve[0];
  453. SkDVector m1 = rh->segment()->dPtAtT(rh->midT()) - rh->fPart.fCurve[0];
  454. double m0xm1 = m0.crossCheck(m1);
  455. if (s0xt0 > 0 && m0xm1 > 0) {
  456. return 0;
  457. }
  458. if (s0xt0 < 0 && m0xm1 < 0) {
  459. return 1;
  460. }
  461. if (tangentsDiverge(rh, s0xt0)) {
  462. return s0xt0 < 0;
  463. }
  464. return m0xm1 < 0;
  465. }
  466. // OPTIMIZATION: longest can all be either lazily computed here or precomputed in setup
  467. double SkOpAngle::distEndRatio(double dist) const {
  468. double longest = 0;
  469. const SkOpSegment& segment = *this->segment();
  470. int ptCount = SkPathOpsVerbToPoints(segment.verb());
  471. const SkPoint* pts = segment.pts();
  472. for (int idx1 = 0; idx1 <= ptCount - 1; ++idx1) {
  473. for (int idx2 = idx1 + 1; idx2 <= ptCount; ++idx2) {
  474. if (idx1 == idx2) {
  475. continue;
  476. }
  477. SkDVector v;
  478. v.set(pts[idx2] - pts[idx1]);
  479. double lenSq = v.lengthSquared();
  480. longest = SkTMax(longest, lenSq);
  481. }
  482. }
  483. return sqrt(longest) / dist;
  484. }
  485. bool SkOpAngle::endsIntersect(SkOpAngle* rh) {
  486. SkPath::Verb lVerb = this->segment()->verb();
  487. SkPath::Verb rVerb = rh->segment()->verb();
  488. int lPts = SkPathOpsVerbToPoints(lVerb);
  489. int rPts = SkPathOpsVerbToPoints(rVerb);
  490. SkDLine rays[] = {{{this->fPart.fCurve[0], rh->fPart.fCurve[rPts]}},
  491. {{this->fPart.fCurve[0], this->fPart.fCurve[lPts]}}};
  492. if (this->fEnd->contains(rh->fEnd)) {
  493. return checkParallel(rh);
  494. }
  495. double smallTs[2] = {-1, -1};
  496. bool limited[2] = {false, false};
  497. for (int index = 0; index < 2; ++index) {
  498. SkPath::Verb cVerb = index ? rVerb : lVerb;
  499. // if the curve is a line, then the line and the ray intersect only at their crossing
  500. if (cVerb == SkPath::kLine_Verb) {
  501. continue;
  502. }
  503. const SkOpSegment& segment = index ? *rh->segment() : *this->segment();
  504. SkIntersections i;
  505. (*CurveIntersectRay[cVerb])(segment.pts(), segment.weight(), rays[index], &i);
  506. double tStart = index ? rh->fStart->t() : this->fStart->t();
  507. double tEnd = index ? rh->fComputedEnd->t() : this->fComputedEnd->t();
  508. bool testAscends = tStart < (index ? rh->fComputedEnd->t() : this->fComputedEnd->t());
  509. double t = testAscends ? 0 : 1;
  510. for (int idx2 = 0; idx2 < i.used(); ++idx2) {
  511. double testT = i[0][idx2];
  512. if (!approximately_between_orderable(tStart, testT, tEnd)) {
  513. continue;
  514. }
  515. if (approximately_equal_orderable(tStart, testT)) {
  516. continue;
  517. }
  518. smallTs[index] = t = testAscends ? SkTMax(t, testT) : SkTMin(t, testT);
  519. limited[index] = approximately_equal_orderable(t, tEnd);
  520. }
  521. }
  522. bool sRayLonger = false;
  523. SkDVector sCept = {0, 0};
  524. double sCeptT = -1;
  525. int sIndex = -1;
  526. bool useIntersect = false;
  527. for (int index = 0; index < 2; ++index) {
  528. if (smallTs[index] < 0) {
  529. continue;
  530. }
  531. const SkOpSegment& segment = index ? *rh->segment() : *this->segment();
  532. const SkDPoint& dPt = segment.dPtAtT(smallTs[index]);
  533. SkDVector cept = dPt - rays[index][0];
  534. // If this point is on the curve, it should have been detected earlier by ordinary
  535. // curve intersection. This may be hard to determine in general, but for lines,
  536. // the point could be close to or equal to its end, but shouldn't be near the start.
  537. if ((index ? lPts : rPts) == 1) {
  538. SkDVector total = rays[index][1] - rays[index][0];
  539. if (cept.lengthSquared() * 2 < total.lengthSquared()) {
  540. continue;
  541. }
  542. }
  543. SkDVector end = rays[index][1] - rays[index][0];
  544. if (cept.fX * end.fX < 0 || cept.fY * end.fY < 0) {
  545. continue;
  546. }
  547. double rayDist = cept.length();
  548. double endDist = end.length();
  549. bool rayLonger = rayDist > endDist;
  550. if (limited[0] && limited[1] && rayLonger) {
  551. useIntersect = true;
  552. sRayLonger = rayLonger;
  553. sCept = cept;
  554. sCeptT = smallTs[index];
  555. sIndex = index;
  556. break;
  557. }
  558. double delta = fabs(rayDist - endDist);
  559. double minX, minY, maxX, maxY;
  560. minX = minY = SK_ScalarInfinity;
  561. maxX = maxY = -SK_ScalarInfinity;
  562. const SkDCurve& curve = index ? rh->fPart.fCurve : this->fPart.fCurve;
  563. int ptCount = index ? rPts : lPts;
  564. for (int idx2 = 0; idx2 <= ptCount; ++idx2) {
  565. minX = SkTMin(minX, curve[idx2].fX);
  566. minY = SkTMin(minY, curve[idx2].fY);
  567. maxX = SkTMax(maxX, curve[idx2].fX);
  568. maxY = SkTMax(maxY, curve[idx2].fY);
  569. }
  570. double maxWidth = SkTMax(maxX - minX, maxY - minY);
  571. delta = sk_ieee_double_divide(delta, maxWidth);
  572. // FIXME: move these magic numbers
  573. // This fixes skbug.com/8380
  574. // Larger changes (like changing the constant in the next block) cause other
  575. // tests to fail as documented in the bug.
  576. // This could probably become a more general test: e.g., if translating the
  577. // curve causes the cross product of any control point or end point to change
  578. // sign with regard to the opposite curve's hull, treat the curves as parallel.
  579. // Moreso, this points to the general fragility of this approach of assigning
  580. // winding by sorting the angles of curves sharing a common point, as mentioned
  581. // in the bug.
  582. if (delta < 4e-3 && delta > 1e-3 && !useIntersect && fPart.isCurve()
  583. && rh->fPart.isCurve() && fOriginalCurvePart[0] != fPart.fCurve.fLine[0]) {
  584. // see if original curve is on one side of hull; translated is on the other
  585. const SkDPoint& origin = rh->fOriginalCurvePart[0];
  586. int count = SkPathOpsVerbToPoints(rh->segment()->verb());
  587. const SkDVector line = rh->fOriginalCurvePart[count] - origin;
  588. int originalSide = rh->lineOnOneSide(origin, line, this, true);
  589. if (originalSide >= 0) {
  590. int translatedSide = rh->lineOnOneSide(origin, line, this, false);
  591. if (originalSide != translatedSide) {
  592. continue;
  593. }
  594. }
  595. }
  596. if (delta > 1e-3 && (useIntersect ^= true)) {
  597. sRayLonger = rayLonger;
  598. sCept = cept;
  599. sCeptT = smallTs[index];
  600. sIndex = index;
  601. }
  602. }
  603. if (useIntersect) {
  604. const SkDCurve& curve = sIndex ? rh->fPart.fCurve : this->fPart.fCurve;
  605. const SkOpSegment& segment = sIndex ? *rh->segment() : *this->segment();
  606. double tStart = sIndex ? rh->fStart->t() : fStart->t();
  607. SkDVector mid = segment.dPtAtT(tStart + (sCeptT - tStart) / 2) - curve[0];
  608. double septDir = mid.crossCheck(sCept);
  609. if (!septDir) {
  610. return checkParallel(rh);
  611. }
  612. return sRayLonger ^ (sIndex == 0) ^ (septDir < 0);
  613. } else {
  614. return checkParallel(rh);
  615. }
  616. }
  617. bool SkOpAngle::endToSide(const SkOpAngle* rh, bool* inside) const {
  618. const SkOpSegment* segment = this->segment();
  619. SkPath::Verb verb = segment->verb();
  620. SkDLine rayEnd;
  621. rayEnd[0].set(this->fEnd->pt());
  622. rayEnd[1] = rayEnd[0];
  623. SkDVector slopeAtEnd = (*CurveDSlopeAtT[verb])(segment->pts(), segment->weight(),
  624. this->fEnd->t());
  625. rayEnd[1].fX += slopeAtEnd.fY;
  626. rayEnd[1].fY -= slopeAtEnd.fX;
  627. SkIntersections iEnd;
  628. const SkOpSegment* oppSegment = rh->segment();
  629. SkPath::Verb oppVerb = oppSegment->verb();
  630. (*CurveIntersectRay[oppVerb])(oppSegment->pts(), oppSegment->weight(), rayEnd, &iEnd);
  631. double endDist;
  632. int closestEnd = iEnd.closestTo(rh->fStart->t(), rh->fEnd->t(), rayEnd[0], &endDist);
  633. if (closestEnd < 0) {
  634. return false;
  635. }
  636. if (!endDist) {
  637. return false;
  638. }
  639. SkDPoint start;
  640. start.set(this->fStart->pt());
  641. // OPTIMIZATION: multiple times in the code we find the max scalar
  642. double minX, minY, maxX, maxY;
  643. minX = minY = SK_ScalarInfinity;
  644. maxX = maxY = -SK_ScalarInfinity;
  645. const SkDCurve& curve = rh->fPart.fCurve;
  646. int oppPts = SkPathOpsVerbToPoints(oppVerb);
  647. for (int idx2 = 0; idx2 <= oppPts; ++idx2) {
  648. minX = SkTMin(minX, curve[idx2].fX);
  649. minY = SkTMin(minY, curve[idx2].fY);
  650. maxX = SkTMax(maxX, curve[idx2].fX);
  651. maxY = SkTMax(maxY, curve[idx2].fY);
  652. }
  653. double maxWidth = SkTMax(maxX - minX, maxY - minY);
  654. endDist = sk_ieee_double_divide(endDist, maxWidth);
  655. if (!(endDist >= 5e-12)) { // empirically found
  656. return false; // ! above catches NaN
  657. }
  658. const SkDPoint* endPt = &rayEnd[0];
  659. SkDPoint oppPt = iEnd.pt(closestEnd);
  660. SkDVector vLeft = *endPt - start;
  661. SkDVector vRight = oppPt - start;
  662. double dir = vLeft.crossNoNormalCheck(vRight);
  663. if (!dir) {
  664. return false;
  665. }
  666. *inside = dir < 0;
  667. return true;
  668. }
  669. /* y<0 y==0 y>0 x<0 x==0 x>0 xy<0 xy==0 xy>0
  670. 0 x x x
  671. 1 x x x
  672. 2 x x x
  673. 3 x x x
  674. 4 x x x
  675. 5 x x x
  676. 6 x x x
  677. 7 x x x
  678. 8 x x x
  679. 9 x x x
  680. 10 x x x
  681. 11 x x x
  682. 12 x x x
  683. 13 x x x
  684. 14 x x x
  685. 15 x x x
  686. */
  687. int SkOpAngle::findSector(SkPath::Verb verb, double x, double y) const {
  688. double absX = fabs(x);
  689. double absY = fabs(y);
  690. double xy = SkPath::kLine_Verb == verb || !AlmostEqualUlps(absX, absY) ? absX - absY : 0;
  691. // If there are four quadrants and eight octants, and since the Latin for sixteen is sedecim,
  692. // one could coin the term sedecimant for a space divided into 16 sections.
  693. // http://english.stackexchange.com/questions/133688/word-for-something-partitioned-into-16-parts
  694. static const int sedecimant[3][3][3] = {
  695. // y<0 y==0 y>0
  696. // x<0 x==0 x>0 x<0 x==0 x>0 x<0 x==0 x>0
  697. {{ 4, 3, 2}, { 7, -1, 15}, {10, 11, 12}}, // abs(x) < abs(y)
  698. {{ 5, -1, 1}, {-1, -1, -1}, { 9, -1, 13}}, // abs(x) == abs(y)
  699. {{ 6, 3, 0}, { 7, -1, 15}, { 8, 11, 14}}, // abs(x) > abs(y)
  700. };
  701. int sector = sedecimant[(xy >= 0) + (xy > 0)][(y >= 0) + (y > 0)][(x >= 0) + (x > 0)] * 2 + 1;
  702. // SkASSERT(SkPath::kLine_Verb == verb || sector >= 0);
  703. return sector;
  704. }
  705. SkOpGlobalState* SkOpAngle::globalState() const {
  706. return this->segment()->globalState();
  707. }
  708. // OPTIMIZE: if this loops to only one other angle, after first compare fails, insert on other side
  709. // OPTIMIZE: return where insertion succeeded. Then, start next insertion on opposite side
  710. bool SkOpAngle::insert(SkOpAngle* angle) {
  711. if (angle->fNext) {
  712. if (loopCount() >= angle->loopCount()) {
  713. if (!merge(angle)) {
  714. return true;
  715. }
  716. } else if (fNext) {
  717. if (!angle->merge(this)) {
  718. return true;
  719. }
  720. } else {
  721. angle->insert(this);
  722. }
  723. return true;
  724. }
  725. bool singleton = nullptr == fNext;
  726. if (singleton) {
  727. fNext = this;
  728. }
  729. SkOpAngle* next = fNext;
  730. if (next->fNext == this) {
  731. if (singleton || angle->after(this)) {
  732. this->fNext = angle;
  733. angle->fNext = next;
  734. } else {
  735. next->fNext = angle;
  736. angle->fNext = this;
  737. }
  738. debugValidateNext();
  739. return true;
  740. }
  741. SkOpAngle* last = this;
  742. bool flipAmbiguity = false;
  743. do {
  744. SkASSERT(last->fNext == next);
  745. if (angle->after(last) ^ (angle->tangentsAmbiguous() & flipAmbiguity)) {
  746. last->fNext = angle;
  747. angle->fNext = next;
  748. debugValidateNext();
  749. return true;
  750. }
  751. last = next;
  752. if (last == this) {
  753. FAIL_IF(flipAmbiguity);
  754. // We're in a loop. If a sort was ambiguous, flip it to end the loop.
  755. flipAmbiguity = true;
  756. }
  757. next = next->fNext;
  758. } while (true);
  759. return true;
  760. }
  761. SkOpSpanBase* SkOpAngle::lastMarked() const {
  762. if (fLastMarked) {
  763. if (fLastMarked->chased()) {
  764. return nullptr;
  765. }
  766. fLastMarked->setChased(true);
  767. }
  768. return fLastMarked;
  769. }
  770. bool SkOpAngle::loopContains(const SkOpAngle* angle) const {
  771. if (!fNext) {
  772. return false;
  773. }
  774. const SkOpAngle* first = this;
  775. const SkOpAngle* loop = this;
  776. const SkOpSegment* tSegment = angle->fStart->segment();
  777. double tStart = angle->fStart->t();
  778. double tEnd = angle->fEnd->t();
  779. do {
  780. const SkOpSegment* lSegment = loop->fStart->segment();
  781. if (lSegment != tSegment) {
  782. continue;
  783. }
  784. double lStart = loop->fStart->t();
  785. if (lStart != tEnd) {
  786. continue;
  787. }
  788. double lEnd = loop->fEnd->t();
  789. if (lEnd == tStart) {
  790. return true;
  791. }
  792. } while ((loop = loop->fNext) != first);
  793. return false;
  794. }
  795. int SkOpAngle::loopCount() const {
  796. int count = 0;
  797. const SkOpAngle* first = this;
  798. const SkOpAngle* next = this;
  799. do {
  800. next = next->fNext;
  801. ++count;
  802. } while (next && next != first);
  803. return count;
  804. }
  805. bool SkOpAngle::merge(SkOpAngle* angle) {
  806. SkASSERT(fNext);
  807. SkASSERT(angle->fNext);
  808. SkOpAngle* working = angle;
  809. do {
  810. if (this == working) {
  811. return false;
  812. }
  813. working = working->fNext;
  814. } while (working != angle);
  815. do {
  816. SkOpAngle* next = working->fNext;
  817. working->fNext = nullptr;
  818. insert(working);
  819. working = next;
  820. } while (working != angle);
  821. // it's likely that a pair of the angles are unorderable
  822. debugValidateNext();
  823. return true;
  824. }
  825. double SkOpAngle::midT() const {
  826. return (fStart->t() + fEnd->t()) / 2;
  827. }
  828. bool SkOpAngle::midToSide(const SkOpAngle* rh, bool* inside) const {
  829. const SkOpSegment* segment = this->segment();
  830. SkPath::Verb verb = segment->verb();
  831. const SkPoint& startPt = this->fStart->pt();
  832. const SkPoint& endPt = this->fEnd->pt();
  833. SkDPoint dStartPt;
  834. dStartPt.set(startPt);
  835. SkDLine rayMid;
  836. rayMid[0].fX = (startPt.fX + endPt.fX) / 2;
  837. rayMid[0].fY = (startPt.fY + endPt.fY) / 2;
  838. rayMid[1].fX = rayMid[0].fX + (endPt.fY - startPt.fY);
  839. rayMid[1].fY = rayMid[0].fY - (endPt.fX - startPt.fX);
  840. SkIntersections iMid;
  841. (*CurveIntersectRay[verb])(segment->pts(), segment->weight(), rayMid, &iMid);
  842. int iOutside = iMid.mostOutside(this->fStart->t(), this->fEnd->t(), dStartPt);
  843. if (iOutside < 0) {
  844. return false;
  845. }
  846. const SkOpSegment* oppSegment = rh->segment();
  847. SkPath::Verb oppVerb = oppSegment->verb();
  848. SkIntersections oppMid;
  849. (*CurveIntersectRay[oppVerb])(oppSegment->pts(), oppSegment->weight(), rayMid, &oppMid);
  850. int oppOutside = oppMid.mostOutside(rh->fStart->t(), rh->fEnd->t(), dStartPt);
  851. if (oppOutside < 0) {
  852. return false;
  853. }
  854. SkDVector iSide = iMid.pt(iOutside) - dStartPt;
  855. SkDVector oppSide = oppMid.pt(oppOutside) - dStartPt;
  856. double dir = iSide.crossCheck(oppSide);
  857. if (!dir) {
  858. return false;
  859. }
  860. *inside = dir < 0;
  861. return true;
  862. }
  863. bool SkOpAngle::oppositePlanes(const SkOpAngle* rh) const {
  864. int startSpan = SkTAbs(rh->fSectorStart - fSectorStart);
  865. return startSpan >= 8;
  866. }
  867. int SkOpAngle::orderable(SkOpAngle* rh) {
  868. int result;
  869. if (!fPart.isCurve()) {
  870. if (!rh->fPart.isCurve()) {
  871. double leftX = fTangentHalf.dx();
  872. double leftY = fTangentHalf.dy();
  873. double rightX = rh->fTangentHalf.dx();
  874. double rightY = rh->fTangentHalf.dy();
  875. double x_ry = leftX * rightY;
  876. double rx_y = rightX * leftY;
  877. if (x_ry == rx_y) {
  878. if (leftX * rightX < 0 || leftY * rightY < 0) {
  879. return 1; // exactly 180 degrees apart
  880. }
  881. goto unorderable;
  882. }
  883. SkASSERT(x_ry != rx_y); // indicates an undetected coincidence -- worth finding earlier
  884. return x_ry < rx_y ? 1 : 0;
  885. }
  886. if ((result = this->lineOnOneSide(rh, false)) >= 0) {
  887. return result;
  888. }
  889. if (fUnorderable || approximately_zero(rh->fSide)) {
  890. goto unorderable;
  891. }
  892. } else if (!rh->fPart.isCurve()) {
  893. if ((result = rh->lineOnOneSide(this, false)) >= 0) {
  894. return result ? 0 : 1;
  895. }
  896. if (rh->fUnorderable || approximately_zero(fSide)) {
  897. goto unorderable;
  898. }
  899. } else if ((result = this->convexHullOverlaps(rh)) >= 0) {
  900. return result;
  901. }
  902. return this->endsIntersect(rh) ? 1 : 0;
  903. unorderable:
  904. fUnorderable = true;
  905. rh->fUnorderable = true;
  906. return -1;
  907. }
  908. // OPTIMIZE: if this shows up in a profile, add a previous pointer
  909. // as is, this should be rarely called
  910. SkOpAngle* SkOpAngle::previous() const {
  911. SkOpAngle* last = fNext;
  912. do {
  913. SkOpAngle* next = last->fNext;
  914. if (next == this) {
  915. return last;
  916. }
  917. last = next;
  918. } while (true);
  919. }
  920. SkOpSegment* SkOpAngle::segment() const {
  921. return fStart->segment();
  922. }
  923. void SkOpAngle::set(SkOpSpanBase* start, SkOpSpanBase* end) {
  924. fStart = start;
  925. fComputedEnd = fEnd = end;
  926. SkASSERT(start != end);
  927. fNext = nullptr;
  928. fComputeSector = fComputedSector = fCheckCoincidence = fTangentsAmbiguous = false;
  929. setSpans();
  930. setSector();
  931. SkDEBUGCODE(fID = start ? start->globalState()->nextAngleID() : -1);
  932. }
  933. void SkOpAngle::setSpans() {
  934. fUnorderable = false;
  935. fLastMarked = nullptr;
  936. if (!fStart) {
  937. fUnorderable = true;
  938. return;
  939. }
  940. const SkOpSegment* segment = fStart->segment();
  941. const SkPoint* pts = segment->pts();
  942. SkDEBUGCODE(fPart.fCurve.fVerb = SkPath::kCubic_Verb); // required for SkDCurve debug check
  943. SkDEBUGCODE(fPart.fCurve[2].fX = fPart.fCurve[2].fY = fPart.fCurve[3].fX = fPart.fCurve[3].fY
  944. = SK_ScalarNaN); // make the non-line part uninitialized
  945. SkDEBUGCODE(fPart.fCurve.fVerb = segment->verb()); // set the curve type for real
  946. segment->subDivide(fStart, fEnd, &fPart.fCurve); // set at least the line part if not more
  947. fOriginalCurvePart = fPart.fCurve;
  948. const SkPath::Verb verb = segment->verb();
  949. fPart.setCurveHullSweep(verb);
  950. if (SkPath::kLine_Verb != verb && !fPart.isCurve()) {
  951. SkDLine lineHalf;
  952. fPart.fCurve[1] = fPart.fCurve[SkPathOpsVerbToPoints(verb)];
  953. fOriginalCurvePart[1] = fPart.fCurve[1];
  954. lineHalf[0].set(fPart.fCurve[0].asSkPoint());
  955. lineHalf[1].set(fPart.fCurve[1].asSkPoint());
  956. fTangentHalf.lineEndPoints(lineHalf);
  957. fSide = 0;
  958. }
  959. switch (verb) {
  960. case SkPath::kLine_Verb: {
  961. SkASSERT(fStart != fEnd);
  962. const SkPoint& cP1 = pts[fStart->t() < fEnd->t()];
  963. SkDLine lineHalf;
  964. lineHalf[0].set(fStart->pt());
  965. lineHalf[1].set(cP1);
  966. fTangentHalf.lineEndPoints(lineHalf);
  967. fSide = 0;
  968. } return;
  969. case SkPath::kQuad_Verb:
  970. case SkPath::kConic_Verb: {
  971. SkLineParameters tangentPart;
  972. (void) tangentPart.quadEndPoints(fPart.fCurve.fQuad);
  973. fSide = -tangentPart.pointDistance(fPart.fCurve[2]); // not normalized -- compare sign only
  974. } break;
  975. case SkPath::kCubic_Verb: {
  976. SkLineParameters tangentPart;
  977. (void) tangentPart.cubicPart(fPart.fCurve.fCubic);
  978. fSide = -tangentPart.pointDistance(fPart.fCurve[3]);
  979. double testTs[4];
  980. // OPTIMIZATION: keep inflections precomputed with cubic segment?
  981. int testCount = SkDCubic::FindInflections(pts, testTs);
  982. double startT = fStart->t();
  983. double endT = fEnd->t();
  984. double limitT = endT;
  985. int index;
  986. for (index = 0; index < testCount; ++index) {
  987. if (!::between(startT, testTs[index], limitT)) {
  988. testTs[index] = -1;
  989. }
  990. }
  991. testTs[testCount++] = startT;
  992. testTs[testCount++] = endT;
  993. SkTQSort<double>(testTs, &testTs[testCount - 1]);
  994. double bestSide = 0;
  995. int testCases = (testCount << 1) - 1;
  996. index = 0;
  997. while (testTs[index] < 0) {
  998. ++index;
  999. }
  1000. index <<= 1;
  1001. for (; index < testCases; ++index) {
  1002. int testIndex = index >> 1;
  1003. double testT = testTs[testIndex];
  1004. if (index & 1) {
  1005. testT = (testT + testTs[testIndex + 1]) / 2;
  1006. }
  1007. // OPTIMIZE: could avoid call for t == startT, endT
  1008. SkDPoint pt = dcubic_xy_at_t(pts, segment->weight(), testT);
  1009. SkLineParameters tangentPart;
  1010. tangentPart.cubicEndPoints(fPart.fCurve.fCubic);
  1011. double testSide = tangentPart.pointDistance(pt);
  1012. if (fabs(bestSide) < fabs(testSide)) {
  1013. bestSide = testSide;
  1014. }
  1015. }
  1016. fSide = -bestSide; // compare sign only
  1017. } break;
  1018. default:
  1019. SkASSERT(0);
  1020. }
  1021. }
  1022. void SkOpAngle::setSector() {
  1023. if (!fStart) {
  1024. fUnorderable = true;
  1025. return;
  1026. }
  1027. const SkOpSegment* segment = fStart->segment();
  1028. SkPath::Verb verb = segment->verb();
  1029. fSectorStart = this->findSector(verb, fPart.fSweep[0].fX, fPart.fSweep[0].fY);
  1030. if (fSectorStart < 0) {
  1031. goto deferTilLater;
  1032. }
  1033. if (!fPart.isCurve()) { // if it's a line or line-like, note that both sectors are the same
  1034. SkASSERT(fSectorStart >= 0);
  1035. fSectorEnd = fSectorStart;
  1036. fSectorMask = 1 << fSectorStart;
  1037. return;
  1038. }
  1039. SkASSERT(SkPath::kLine_Verb != verb);
  1040. fSectorEnd = this->findSector(verb, fPart.fSweep[1].fX, fPart.fSweep[1].fY);
  1041. if (fSectorEnd < 0) {
  1042. deferTilLater:
  1043. fSectorStart = fSectorEnd = -1;
  1044. fSectorMask = 0;
  1045. fComputeSector = true; // can't determine sector until segment length can be found
  1046. return;
  1047. }
  1048. if (fSectorEnd == fSectorStart
  1049. && (fSectorStart & 3) != 3) { // if the sector has no span, it can't be an exact angle
  1050. fSectorMask = 1 << fSectorStart;
  1051. return;
  1052. }
  1053. bool crossesZero = this->checkCrossesZero();
  1054. int start = SkTMin(fSectorStart, fSectorEnd);
  1055. bool curveBendsCCW = (fSectorStart == start) ^ crossesZero;
  1056. // bump the start and end of the sector span if they are on exact compass points
  1057. if ((fSectorStart & 3) == 3) {
  1058. fSectorStart = (fSectorStart + (curveBendsCCW ? 1 : 31)) & 0x1f;
  1059. }
  1060. if ((fSectorEnd & 3) == 3) {
  1061. fSectorEnd = (fSectorEnd + (curveBendsCCW ? 31 : 1)) & 0x1f;
  1062. }
  1063. crossesZero = this->checkCrossesZero();
  1064. start = SkTMin(fSectorStart, fSectorEnd);
  1065. int end = SkTMax(fSectorStart, fSectorEnd);
  1066. if (!crossesZero) {
  1067. fSectorMask = (unsigned) -1 >> (31 - end + start) << start;
  1068. } else {
  1069. fSectorMask = (unsigned) -1 >> (31 - start) | ((unsigned) -1 << end);
  1070. }
  1071. }
  1072. SkOpSpan* SkOpAngle::starter() {
  1073. return fStart->starter(fEnd);
  1074. }
  1075. bool SkOpAngle::tangentsDiverge(const SkOpAngle* rh, double s0xt0) {
  1076. if (s0xt0 == 0) {
  1077. return false;
  1078. }
  1079. // if the ctrl tangents are not nearly parallel, use them
  1080. // solve for opposite direction displacement scale factor == m
  1081. // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x
  1082. // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1]
  1083. // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x)
  1084. // v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x)
  1085. // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x
  1086. // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y)
  1087. // m = v1.cross(v2) / v1.dot(v2)
  1088. const SkDVector* sweep = fPart.fSweep;
  1089. const SkDVector* tweep = rh->fPart.fSweep;
  1090. double s0dt0 = sweep[0].dot(tweep[0]);
  1091. if (!s0dt0) {
  1092. return true;
  1093. }
  1094. SkASSERT(s0dt0 != 0);
  1095. double m = s0xt0 / s0dt0;
  1096. double sDist = sweep[0].length() * m;
  1097. double tDist = tweep[0].length() * m;
  1098. bool useS = fabs(sDist) < fabs(tDist);
  1099. double mFactor = fabs(useS ? this->distEndRatio(sDist) : rh->distEndRatio(tDist));
  1100. fTangentsAmbiguous = mFactor >= 50 && mFactor < 200;
  1101. return mFactor < 50; // empirically found limit
  1102. }