SkPathOpsWinding.cpp 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425
  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. // given a prospective edge, compute its initial winding by projecting a ray
  8. // if the ray hits another edge
  9. // if the edge doesn't have a winding yet, hop up to that edge and start over
  10. // concern : check for hops forming a loop
  11. // if the edge is unsortable, or
  12. // the intersection is nearly at the ends, or
  13. // the tangent at the intersection is nearly coincident to the ray,
  14. // choose a different ray and try again
  15. // concern : if it is unable to succeed after N tries, try another edge? direction?
  16. // if no edge is hit, compute the winding directly
  17. // given the top span, project the most perpendicular ray and look for intersections
  18. // let's try up and then down. What the hey
  19. // bestXY is initialized by caller with basePt
  20. #include "src/pathops/SkOpContour.h"
  21. #include "src/pathops/SkOpSegment.h"
  22. #include "src/pathops/SkPathOpsCurve.h"
  23. #include <utility>
  24. enum class SkOpRayDir {
  25. kLeft,
  26. kTop,
  27. kRight,
  28. kBottom,
  29. };
  30. #if DEBUG_WINDING
  31. const char* gDebugRayDirName[] = {
  32. "kLeft",
  33. "kTop",
  34. "kRight",
  35. "kBottom"
  36. };
  37. #endif
  38. static int xy_index(SkOpRayDir dir) {
  39. return static_cast<int>(dir) & 1;
  40. }
  41. static SkScalar pt_xy(const SkPoint& pt, SkOpRayDir dir) {
  42. return (&pt.fX)[xy_index(dir)];
  43. }
  44. static SkScalar pt_yx(const SkPoint& pt, SkOpRayDir dir) {
  45. return (&pt.fX)[!xy_index(dir)];
  46. }
  47. static double pt_dxdy(const SkDVector& v, SkOpRayDir dir) {
  48. return (&v.fX)[xy_index(dir)];
  49. }
  50. static double pt_dydx(const SkDVector& v, SkOpRayDir dir) {
  51. return (&v.fX)[!xy_index(dir)];
  52. }
  53. static SkScalar rect_side(const SkRect& r, SkOpRayDir dir) {
  54. return (&r.fLeft)[static_cast<int>(dir)];
  55. }
  56. static bool sideways_overlap(const SkRect& rect, const SkPoint& pt, SkOpRayDir dir) {
  57. int i = !xy_index(dir);
  58. return approximately_between((&rect.fLeft)[i], (&pt.fX)[i], (&rect.fRight)[i]);
  59. }
  60. static bool less_than(SkOpRayDir dir) {
  61. return static_cast<bool>((static_cast<int>(dir) & 2) == 0);
  62. }
  63. static bool ccw_dxdy(const SkDVector& v, SkOpRayDir dir) {
  64. bool vPartPos = pt_dydx(v, dir) > 0;
  65. bool leftBottom = ((static_cast<int>(dir) + 1) & 2) != 0;
  66. return vPartPos == leftBottom;
  67. }
  68. struct SkOpRayHit {
  69. SkOpRayDir makeTestBase(SkOpSpan* span, double t) {
  70. fNext = nullptr;
  71. fSpan = span;
  72. fT = span->t() * (1 - t) + span->next()->t() * t;
  73. SkOpSegment* segment = span->segment();
  74. fSlope = segment->dSlopeAtT(fT);
  75. fPt = segment->ptAtT(fT);
  76. fValid = true;
  77. return fabs(fSlope.fX) < fabs(fSlope.fY) ? SkOpRayDir::kLeft : SkOpRayDir::kTop;
  78. }
  79. SkOpRayHit* fNext;
  80. SkOpSpan* fSpan;
  81. SkPoint fPt;
  82. double fT;
  83. SkDVector fSlope;
  84. bool fValid;
  85. };
  86. void SkOpContour::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits,
  87. SkArenaAlloc* allocator) {
  88. // if the bounds extreme is outside the best, we're done
  89. SkScalar baseXY = pt_xy(base.fPt, dir);
  90. SkScalar boundsXY = rect_side(fBounds, dir);
  91. bool checkLessThan = less_than(dir);
  92. if (!approximately_equal(baseXY, boundsXY) && (baseXY < boundsXY) == checkLessThan) {
  93. return;
  94. }
  95. SkOpSegment* testSegment = &fHead;
  96. do {
  97. testSegment->rayCheck(base, dir, hits, allocator);
  98. } while ((testSegment = testSegment->next()));
  99. }
  100. void SkOpSegment::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits,
  101. SkArenaAlloc* allocator) {
  102. if (!sideways_overlap(fBounds, base.fPt, dir)) {
  103. return;
  104. }
  105. SkScalar baseXY = pt_xy(base.fPt, dir);
  106. SkScalar boundsXY = rect_side(fBounds, dir);
  107. bool checkLessThan = less_than(dir);
  108. if (!approximately_equal(baseXY, boundsXY) && (baseXY < boundsXY) == checkLessThan) {
  109. return;
  110. }
  111. double tVals[3];
  112. SkScalar baseYX = pt_yx(base.fPt, dir);
  113. int roots = (*CurveIntercept[fVerb * 2 + xy_index(dir)])(fPts, fWeight, baseYX, tVals);
  114. for (int index = 0; index < roots; ++index) {
  115. double t = tVals[index];
  116. if (base.fSpan->segment() == this && approximately_equal(base.fT, t)) {
  117. continue;
  118. }
  119. SkDVector slope;
  120. SkPoint pt;
  121. SkDEBUGCODE(sk_bzero(&slope, sizeof(slope)));
  122. bool valid = false;
  123. if (approximately_zero(t)) {
  124. pt = fPts[0];
  125. } else if (approximately_equal(t, 1)) {
  126. pt = fPts[SkPathOpsVerbToPoints(fVerb)];
  127. } else {
  128. SkASSERT(between(0, t, 1));
  129. pt = this->ptAtT(t);
  130. if (SkDPoint::ApproximatelyEqual(pt, base.fPt)) {
  131. if (base.fSpan->segment() == this) {
  132. continue;
  133. }
  134. } else {
  135. SkScalar ptXY = pt_xy(pt, dir);
  136. if (!approximately_equal(baseXY, ptXY) && (baseXY < ptXY) == checkLessThan) {
  137. continue;
  138. }
  139. slope = this->dSlopeAtT(t);
  140. if (fVerb == SkPath::kCubic_Verb && base.fSpan->segment() == this
  141. && roughly_equal(base.fT, t)
  142. && SkDPoint::RoughlyEqual(pt, base.fPt)) {
  143. #if DEBUG_WINDING
  144. SkDebugf("%s (rarely expect this)\n", __FUNCTION__);
  145. #endif
  146. continue;
  147. }
  148. if (fabs(pt_dydx(slope, dir) * 10000) > fabs(pt_dxdy(slope, dir))) {
  149. valid = true;
  150. }
  151. }
  152. }
  153. SkOpSpan* span = this->windingSpanAtT(t);
  154. if (!span) {
  155. valid = false;
  156. } else if (!span->windValue() && !span->oppValue()) {
  157. continue;
  158. }
  159. SkOpRayHit* newHit = allocator->make<SkOpRayHit>();
  160. newHit->fNext = *hits;
  161. newHit->fPt = pt;
  162. newHit->fSlope = slope;
  163. newHit->fSpan = span;
  164. newHit->fT = t;
  165. newHit->fValid = valid;
  166. *hits = newHit;
  167. }
  168. }
  169. SkOpSpan* SkOpSegment::windingSpanAtT(double tHit) {
  170. SkOpSpan* span = &fHead;
  171. SkOpSpanBase* next;
  172. do {
  173. next = span->next();
  174. if (approximately_equal(tHit, next->t())) {
  175. return nullptr;
  176. }
  177. if (tHit < next->t()) {
  178. return span;
  179. }
  180. } while (!next->final() && (span = next->upCast()));
  181. return nullptr;
  182. }
  183. static bool hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) {
  184. return a->fPt.fX < b->fPt.fX;
  185. }
  186. static bool reverse_hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) {
  187. return b->fPt.fX < a->fPt.fX;
  188. }
  189. static bool hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) {
  190. return a->fPt.fY < b->fPt.fY;
  191. }
  192. static bool reverse_hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) {
  193. return b->fPt.fY < a->fPt.fY;
  194. }
  195. static double get_t_guess(int tTry, int* dirOffset) {
  196. double t = 0.5;
  197. *dirOffset = tTry & 1;
  198. int tBase = tTry >> 1;
  199. int tBits = 0;
  200. while (tTry >>= 1) {
  201. t /= 2;
  202. ++tBits;
  203. }
  204. if (tBits) {
  205. int tIndex = (tBase - 1) & ((1 << tBits) - 1);
  206. t += t * 2 * tIndex;
  207. }
  208. return t;
  209. }
  210. bool SkOpSpan::sortableTop(SkOpContour* contourHead) {
  211. SkSTArenaAlloc<1024> allocator;
  212. int dirOffset;
  213. double t = get_t_guess(fTopTTry++, &dirOffset);
  214. SkOpRayHit hitBase;
  215. SkOpRayDir dir = hitBase.makeTestBase(this, t);
  216. if (hitBase.fSlope.fX == 0 && hitBase.fSlope.fY == 0) {
  217. return false;
  218. }
  219. SkOpRayHit* hitHead = &hitBase;
  220. dir = static_cast<SkOpRayDir>(static_cast<int>(dir) + dirOffset);
  221. if (hitBase.fSpan && hitBase.fSpan->segment()->verb() > SkPath::kLine_Verb
  222. && !pt_dydx(hitBase.fSlope, dir)) {
  223. return false;
  224. }
  225. SkOpContour* contour = contourHead;
  226. do {
  227. if (!contour->count()) {
  228. continue;
  229. }
  230. contour->rayCheck(hitBase, dir, &hitHead, &allocator);
  231. } while ((contour = contour->next()));
  232. // sort hits
  233. SkSTArray<1, SkOpRayHit*> sorted;
  234. SkOpRayHit* hit = hitHead;
  235. while (hit) {
  236. sorted.push_back(hit);
  237. hit = hit->fNext;
  238. }
  239. int count = sorted.count();
  240. SkTQSort(sorted.begin(), sorted.end() - 1, xy_index(dir)
  241. ? less_than(dir) ? hit_compare_y : reverse_hit_compare_y
  242. : less_than(dir) ? hit_compare_x : reverse_hit_compare_x);
  243. // verify windings
  244. #if DEBUG_WINDING
  245. SkDebugf("%s dir=%s seg=%d t=%1.9g pt=(%1.9g,%1.9g)\n", __FUNCTION__,
  246. gDebugRayDirName[static_cast<int>(dir)], hitBase.fSpan->segment()->debugID(),
  247. hitBase.fT, hitBase.fPt.fX, hitBase.fPt.fY);
  248. for (int index = 0; index < count; ++index) {
  249. hit = sorted[index];
  250. SkOpSpan* span = hit->fSpan;
  251. SkOpSegment* hitSegment = span ? span->segment() : nullptr;
  252. bool operand = span ? hitSegment->operand() : false;
  253. bool ccw = ccw_dxdy(hit->fSlope, dir);
  254. SkDebugf("%s [%d] valid=%d operand=%d span=%d ccw=%d ", __FUNCTION__, index,
  255. hit->fValid, operand, span ? span->debugID() : -1, ccw);
  256. if (span) {
  257. hitSegment->dumpPtsInner();
  258. }
  259. SkDebugf(" t=%1.9g pt=(%1.9g,%1.9g) slope=(%1.9g,%1.9g)\n", hit->fT,
  260. hit->fPt.fX, hit->fPt.fY, hit->fSlope.fX, hit->fSlope.fY);
  261. }
  262. #endif
  263. const SkPoint* last = nullptr;
  264. int wind = 0;
  265. int oppWind = 0;
  266. for (int index = 0; index < count; ++index) {
  267. hit = sorted[index];
  268. if (!hit->fValid) {
  269. return false;
  270. }
  271. bool ccw = ccw_dxdy(hit->fSlope, dir);
  272. // SkASSERT(!approximately_zero(hit->fT) || !hit->fValid);
  273. SkOpSpan* span = hit->fSpan;
  274. if (!span) {
  275. return false;
  276. }
  277. SkOpSegment* hitSegment = span->segment();
  278. if (span->windValue() == 0 && span->oppValue() == 0) {
  279. continue;
  280. }
  281. if (last && SkDPoint::ApproximatelyEqual(*last, hit->fPt)) {
  282. return false;
  283. }
  284. if (index < count - 1) {
  285. const SkPoint& next = sorted[index + 1]->fPt;
  286. if (SkDPoint::ApproximatelyEqual(next, hit->fPt)) {
  287. return false;
  288. }
  289. }
  290. bool operand = hitSegment->operand();
  291. if (operand) {
  292. using std::swap;
  293. swap(wind, oppWind);
  294. }
  295. int lastWind = wind;
  296. int lastOpp = oppWind;
  297. int windValue = ccw ? -span->windValue() : span->windValue();
  298. int oppValue = ccw ? -span->oppValue() : span->oppValue();
  299. wind += windValue;
  300. oppWind += oppValue;
  301. bool sumSet = false;
  302. int spanSum = span->windSum();
  303. int windSum = SkOpSegment::UseInnerWinding(lastWind, wind) ? wind : lastWind;
  304. if (spanSum == SK_MinS32) {
  305. span->setWindSum(windSum);
  306. sumSet = true;
  307. } else {
  308. // the need for this condition suggests that UseInnerWinding is flawed
  309. // happened when last = 1 wind = -1
  310. #if 0
  311. SkASSERT((hitSegment->isXor() ? (windSum & 1) == (spanSum & 1) : windSum == spanSum)
  312. || (abs(wind) == abs(lastWind)
  313. && (windSum ^ wind ^ lastWind) == spanSum));
  314. #endif
  315. }
  316. int oSpanSum = span->oppSum();
  317. int oppSum = SkOpSegment::UseInnerWinding(lastOpp, oppWind) ? oppWind : lastOpp;
  318. if (oSpanSum == SK_MinS32) {
  319. span->setOppSum(oppSum);
  320. } else {
  321. #if 0
  322. SkASSERT(hitSegment->oppXor() ? (oppSum & 1) == (oSpanSum & 1) : oppSum == oSpanSum
  323. || (abs(oppWind) == abs(lastOpp)
  324. && (oppSum ^ oppWind ^ lastOpp) == oSpanSum));
  325. #endif
  326. }
  327. if (sumSet) {
  328. if (this->globalState()->phase() == SkOpPhase::kFixWinding) {
  329. hitSegment->contour()->setCcw(ccw);
  330. } else {
  331. (void) hitSegment->markAndChaseWinding(span, span->next(), windSum, oppSum, nullptr);
  332. (void) hitSegment->markAndChaseWinding(span->next(), span, windSum, oppSum, nullptr);
  333. }
  334. }
  335. if (operand) {
  336. using std::swap;
  337. swap(wind, oppWind);
  338. }
  339. last = &hit->fPt;
  340. this->globalState()->bumpNested();
  341. }
  342. return true;
  343. }
  344. SkOpSpan* SkOpSegment::findSortableTop(SkOpContour* contourHead) {
  345. SkOpSpan* span = &fHead;
  346. SkOpSpanBase* next;
  347. do {
  348. next = span->next();
  349. if (span->done()) {
  350. continue;
  351. }
  352. if (span->windSum() != SK_MinS32) {
  353. return span;
  354. }
  355. if (span->sortableTop(contourHead)) {
  356. return span;
  357. }
  358. } while (!next->final() && (span = next->upCast()));
  359. return nullptr;
  360. }
  361. SkOpSpan* SkOpContour::findSortableTop(SkOpContour* contourHead) {
  362. bool allDone = true;
  363. if (fCount) {
  364. SkOpSegment* testSegment = &fHead;
  365. do {
  366. if (testSegment->done()) {
  367. continue;
  368. }
  369. allDone = false;
  370. SkOpSpan* result = testSegment->findSortableTop(contourHead);
  371. if (result) {
  372. return result;
  373. }
  374. } while ((testSegment = testSegment->next()));
  375. }
  376. if (allDone) {
  377. fDone = true;
  378. }
  379. return nullptr;
  380. }
  381. SkOpSpan* FindSortableTop(SkOpContourHead* contourHead) {
  382. for (int index = 0; index < SkOpGlobalState::kMaxWindingTries; ++index) {
  383. SkOpContour* contour = contourHead;
  384. do {
  385. if (contour->done()) {
  386. continue;
  387. }
  388. SkOpSpan* result = contour->findSortableTop(contourHead);
  389. if (result) {
  390. return result;
  391. }
  392. } while ((contour = contour->next()));
  393. }
  394. return nullptr;
  395. }