SkPathWriter.cpp 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434
  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/SkOpSegment.h"
  9. #include "src/pathops/SkOpSpan.h"
  10. #include "src/pathops/SkPathOpsPoint.h"
  11. #include "src/pathops/SkPathWriter.h"
  12. // wrap path to keep track of whether the contour is initialized and non-empty
  13. SkPathWriter::SkPathWriter(SkPath& path)
  14. : fPathPtr(&path)
  15. {
  16. init();
  17. }
  18. void SkPathWriter::close() {
  19. if (fCurrent.isEmpty()) {
  20. return;
  21. }
  22. SkASSERT(this->isClosed());
  23. #if DEBUG_PATH_CONSTRUCTION
  24. SkDebugf("path.close();\n");
  25. #endif
  26. fCurrent.close();
  27. fPathPtr->addPath(fCurrent);
  28. fCurrent.reset();
  29. init();
  30. }
  31. void SkPathWriter::conicTo(const SkPoint& pt1, const SkOpPtT* pt2, SkScalar weight) {
  32. SkPoint pt2pt = this->update(pt2);
  33. #if DEBUG_PATH_CONSTRUCTION
  34. SkDebugf("path.conicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g);\n",
  35. pt1.fX, pt1.fY, pt2pt.fX, pt2pt.fY, weight);
  36. #endif
  37. fCurrent.conicTo(pt1, pt2pt, weight);
  38. }
  39. void SkPathWriter::cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkOpPtT* pt3) {
  40. SkPoint pt3pt = this->update(pt3);
  41. #if DEBUG_PATH_CONSTRUCTION
  42. SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n",
  43. pt1.fX, pt1.fY, pt2.fX, pt2.fY, pt3pt.fX, pt3pt.fY);
  44. #endif
  45. fCurrent.cubicTo(pt1, pt2, pt3pt);
  46. }
  47. bool SkPathWriter::deferredLine(const SkOpPtT* pt) {
  48. SkASSERT(fFirstPtT);
  49. SkASSERT(fDefer[0]);
  50. if (fDefer[0] == pt) {
  51. // FIXME: why we're adding a degenerate line? Caller should have preflighted this.
  52. return true;
  53. }
  54. if (pt->contains(fDefer[0])) {
  55. // FIXME: why we're adding a degenerate line?
  56. return true;
  57. }
  58. if (this->matchedLast(pt)) {
  59. return false;
  60. }
  61. if (fDefer[1] && this->changedSlopes(pt)) {
  62. this->lineTo();
  63. fDefer[0] = fDefer[1];
  64. }
  65. fDefer[1] = pt;
  66. return true;
  67. }
  68. void SkPathWriter::deferredMove(const SkOpPtT* pt) {
  69. if (!fDefer[1]) {
  70. fFirstPtT = fDefer[0] = pt;
  71. return;
  72. }
  73. SkASSERT(fDefer[0]);
  74. if (!this->matchedLast(pt)) {
  75. this->finishContour();
  76. fFirstPtT = fDefer[0] = pt;
  77. }
  78. }
  79. void SkPathWriter::finishContour() {
  80. if (!this->matchedLast(fDefer[0])) {
  81. if (!fDefer[1]) {
  82. return;
  83. }
  84. this->lineTo();
  85. }
  86. if (fCurrent.isEmpty()) {
  87. return;
  88. }
  89. if (this->isClosed()) {
  90. this->close();
  91. } else {
  92. SkASSERT(fDefer[1]);
  93. fEndPtTs.push_back(fFirstPtT);
  94. fEndPtTs.push_back(fDefer[1]);
  95. fPartials.push_back(fCurrent);
  96. this->init();
  97. }
  98. }
  99. void SkPathWriter::init() {
  100. fCurrent.reset();
  101. fFirstPtT = fDefer[0] = fDefer[1] = nullptr;
  102. }
  103. bool SkPathWriter::isClosed() const {
  104. return this->matchedLast(fFirstPtT);
  105. }
  106. void SkPathWriter::lineTo() {
  107. if (fCurrent.isEmpty()) {
  108. this->moveTo();
  109. }
  110. #if DEBUG_PATH_CONSTRUCTION
  111. SkDebugf("path.lineTo(%1.9g,%1.9g);\n", fDefer[1]->fPt.fX, fDefer[1]->fPt.fY);
  112. #endif
  113. fCurrent.lineTo(fDefer[1]->fPt);
  114. }
  115. bool SkPathWriter::matchedLast(const SkOpPtT* test) const {
  116. if (test == fDefer[1]) {
  117. return true;
  118. }
  119. if (!test) {
  120. return false;
  121. }
  122. if (!fDefer[1]) {
  123. return false;
  124. }
  125. return test->contains(fDefer[1]);
  126. }
  127. void SkPathWriter::moveTo() {
  128. #if DEBUG_PATH_CONSTRUCTION
  129. SkDebugf("path.moveTo(%1.9g,%1.9g);\n", fFirstPtT->fPt.fX, fFirstPtT->fPt.fY);
  130. #endif
  131. fCurrent.moveTo(fFirstPtT->fPt);
  132. }
  133. void SkPathWriter::quadTo(const SkPoint& pt1, const SkOpPtT* pt2) {
  134. SkPoint pt2pt = this->update(pt2);
  135. #if DEBUG_PATH_CONSTRUCTION
  136. SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n",
  137. pt1.fX, pt1.fY, pt2pt.fX, pt2pt.fY);
  138. #endif
  139. fCurrent.quadTo(pt1, pt2pt);
  140. }
  141. // if last point to be written matches the current path's first point, alter the
  142. // last to avoid writing a degenerate lineTo when the path is closed
  143. SkPoint SkPathWriter::update(const SkOpPtT* pt) {
  144. if (!fDefer[1]) {
  145. this->moveTo();
  146. } else if (!this->matchedLast(fDefer[0])) {
  147. this->lineTo();
  148. }
  149. SkPoint result = pt->fPt;
  150. if (fFirstPtT && result != fFirstPtT->fPt && fFirstPtT->contains(pt)) {
  151. result = fFirstPtT->fPt;
  152. }
  153. fDefer[0] = fDefer[1] = pt; // set both to know that there is not a pending deferred line
  154. return result;
  155. }
  156. bool SkPathWriter::someAssemblyRequired() {
  157. this->finishContour();
  158. return fEndPtTs.count() > 0;
  159. }
  160. bool SkPathWriter::changedSlopes(const SkOpPtT* ptT) const {
  161. if (matchedLast(fDefer[0])) {
  162. return false;
  163. }
  164. SkVector deferDxdy = fDefer[1]->fPt - fDefer[0]->fPt;
  165. SkVector lineDxdy = ptT->fPt - fDefer[1]->fPt;
  166. return deferDxdy.fX * lineDxdy.fY != deferDxdy.fY * lineDxdy.fX;
  167. }
  168. class DistanceLessThan {
  169. public:
  170. DistanceLessThan(double* distances) : fDistances(distances) { }
  171. double* fDistances;
  172. bool operator()(const int one, const int two) {
  173. return fDistances[one] < fDistances[two];
  174. }
  175. };
  176. /*
  177. check start and end of each contour
  178. if not the same, record them
  179. match them up
  180. connect closest
  181. reassemble contour pieces into new path
  182. */
  183. void SkPathWriter::assemble() {
  184. #if DEBUG_SHOW_TEST_NAME
  185. SkDebugf("</div>\n");
  186. #endif
  187. if (!this->someAssemblyRequired()) {
  188. return;
  189. }
  190. #if DEBUG_PATH_CONSTRUCTION
  191. SkDebugf("%s\n", __FUNCTION__);
  192. #endif
  193. SkOpPtT const* const* runs = fEndPtTs.begin(); // starts, ends of partial contours
  194. int endCount = fEndPtTs.count(); // all starts and ends
  195. SkASSERT(endCount > 0);
  196. SkASSERT(endCount == fPartials.count() * 2);
  197. #if DEBUG_ASSEMBLE
  198. for (int index = 0; index < endCount; index += 2) {
  199. const SkOpPtT* eStart = runs[index];
  200. const SkOpPtT* eEnd = runs[index + 1];
  201. SkASSERT(eStart != eEnd);
  202. SkASSERT(!eStart->contains(eEnd));
  203. SkDebugf("%s contour start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n", __FUNCTION__,
  204. eStart->fPt.fX, eStart->fPt.fY, eEnd->fPt.fX, eEnd->fPt.fY);
  205. }
  206. #endif
  207. // lengthen any partial contour adjacent to a simple segment
  208. for (int pIndex = 0; pIndex < endCount; pIndex++) {
  209. SkOpPtT* opPtT = const_cast<SkOpPtT*>(runs[pIndex]);
  210. SkPath dummy;
  211. SkPathWriter partWriter(dummy);
  212. do {
  213. if (!zero_or_one(opPtT->fT)) {
  214. break;
  215. }
  216. SkOpSpanBase* opSpanBase = opPtT->span();
  217. SkOpSpanBase* start = opPtT->fT ? opSpanBase->prev() : opSpanBase->upCast()->next();
  218. int step = opPtT->fT ? 1 : -1;
  219. const SkOpSegment* opSegment = opSpanBase->segment();
  220. const SkOpSegment* nextSegment = opSegment->isSimple(&start, &step);
  221. if (!nextSegment) {
  222. break;
  223. }
  224. SkOpSpanBase* opSpanEnd = start->t() ? start->prev() : start->upCast()->next();
  225. if (start->starter(opSpanEnd)->alreadyAdded()) {
  226. break;
  227. }
  228. nextSegment->addCurveTo(start, opSpanEnd, &partWriter);
  229. opPtT = opSpanEnd->ptT();
  230. SkOpPtT** runsPtr = const_cast<SkOpPtT**>(&runs[pIndex]);
  231. *runsPtr = opPtT;
  232. } while (true);
  233. partWriter.finishContour();
  234. const SkTArray<SkPath>& partPartials = partWriter.partials();
  235. if (!partPartials.count()) {
  236. continue;
  237. }
  238. // if pIndex is even, reverse and prepend to fPartials; otherwise, append
  239. SkPath& partial = const_cast<SkPath&>(fPartials[pIndex >> 1]);
  240. const SkPath& part = partPartials[0];
  241. if (pIndex & 1) {
  242. partial.addPath(part, SkPath::kExtend_AddPathMode);
  243. } else {
  244. SkPath reverse;
  245. reverse.reverseAddPath(part);
  246. reverse.addPath(partial, SkPath::kExtend_AddPathMode);
  247. partial = reverse;
  248. }
  249. }
  250. SkTDArray<int> sLink, eLink;
  251. int linkCount = endCount / 2; // number of partial contours
  252. sLink.append(linkCount);
  253. eLink.append(linkCount);
  254. int rIndex, iIndex;
  255. for (rIndex = 0; rIndex < linkCount; ++rIndex) {
  256. sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
  257. }
  258. const int entries = endCount * (endCount - 1) / 2; // folded triangle
  259. SkSTArray<8, double, true> distances(entries);
  260. SkSTArray<8, int, true> sortedDist(entries);
  261. SkSTArray<8, int, true> distLookup(entries);
  262. int rRow = 0;
  263. int dIndex = 0;
  264. for (rIndex = 0; rIndex < endCount - 1; ++rIndex) {
  265. const SkOpPtT* oPtT = runs[rIndex];
  266. for (iIndex = rIndex + 1; iIndex < endCount; ++iIndex) {
  267. const SkOpPtT* iPtT = runs[iIndex];
  268. double dx = iPtT->fPt.fX - oPtT->fPt.fX;
  269. double dy = iPtT->fPt.fY - oPtT->fPt.fY;
  270. double dist = dx * dx + dy * dy;
  271. distLookup.push_back(rRow + iIndex);
  272. distances.push_back(dist); // oStart distance from iStart
  273. sortedDist.push_back(dIndex++);
  274. }
  275. rRow += endCount;
  276. }
  277. SkASSERT(dIndex == entries);
  278. SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin()));
  279. int remaining = linkCount; // number of start/end pairs
  280. for (rIndex = 0; rIndex < entries; ++rIndex) {
  281. int pair = sortedDist[rIndex];
  282. pair = distLookup[pair];
  283. int row = pair / endCount;
  284. int col = pair - row * endCount;
  285. int ndxOne = row >> 1;
  286. bool endOne = row & 1;
  287. int* linkOne = endOne ? eLink.begin() : sLink.begin();
  288. if (linkOne[ndxOne] != SK_MaxS32) {
  289. continue;
  290. }
  291. int ndxTwo = col >> 1;
  292. bool endTwo = col & 1;
  293. int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
  294. if (linkTwo[ndxTwo] != SK_MaxS32) {
  295. continue;
  296. }
  297. SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
  298. bool flip = endOne == endTwo;
  299. linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
  300. linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
  301. if (!--remaining) {
  302. break;
  303. }
  304. }
  305. SkASSERT(!remaining);
  306. #if DEBUG_ASSEMBLE
  307. for (rIndex = 0; rIndex < linkCount; ++rIndex) {
  308. int s = sLink[rIndex];
  309. int e = eLink[rIndex];
  310. SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
  311. s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
  312. }
  313. #endif
  314. rIndex = 0;
  315. do {
  316. bool forward = true;
  317. bool first = true;
  318. int sIndex = sLink[rIndex];
  319. SkASSERT(sIndex != SK_MaxS32);
  320. sLink[rIndex] = SK_MaxS32;
  321. int eIndex;
  322. if (sIndex < 0) {
  323. eIndex = sLink[~sIndex];
  324. sLink[~sIndex] = SK_MaxS32;
  325. } else {
  326. eIndex = eLink[sIndex];
  327. eLink[sIndex] = SK_MaxS32;
  328. }
  329. SkASSERT(eIndex != SK_MaxS32);
  330. #if DEBUG_ASSEMBLE
  331. SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
  332. sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
  333. eIndex < 0 ? ~eIndex : eIndex);
  334. #endif
  335. do {
  336. const SkPath& contour = fPartials[rIndex];
  337. if (!first) {
  338. SkPoint prior, next;
  339. if (!fPathPtr->getLastPt(&prior)) {
  340. return;
  341. }
  342. if (forward) {
  343. next = contour.getPoint(0);
  344. } else {
  345. SkAssertResult(contour.getLastPt(&next));
  346. }
  347. if (prior != next) {
  348. /* TODO: if there is a gap between open path written so far and path to come,
  349. connect by following segments from one to the other, rather than introducing
  350. a diagonal to connect the two.
  351. */
  352. SkDebugf("");
  353. }
  354. }
  355. if (forward) {
  356. fPathPtr->addPath(contour,
  357. first ? SkPath::kAppend_AddPathMode : SkPath::kExtend_AddPathMode);
  358. } else {
  359. SkASSERT(!first);
  360. fPathPtr->reversePathTo(contour);
  361. }
  362. if (first) {
  363. first = false;
  364. }
  365. #if DEBUG_ASSEMBLE
  366. SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex,
  367. eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,
  368. sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));
  369. #endif
  370. if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
  371. fPathPtr->close();
  372. break;
  373. }
  374. if (forward) {
  375. eIndex = eLink[rIndex];
  376. SkASSERT(eIndex != SK_MaxS32);
  377. eLink[rIndex] = SK_MaxS32;
  378. if (eIndex >= 0) {
  379. SkASSERT(sLink[eIndex] == rIndex);
  380. sLink[eIndex] = SK_MaxS32;
  381. } else {
  382. SkASSERT(eLink[~eIndex] == ~rIndex);
  383. eLink[~eIndex] = SK_MaxS32;
  384. }
  385. } else {
  386. eIndex = sLink[rIndex];
  387. SkASSERT(eIndex != SK_MaxS32);
  388. sLink[rIndex] = SK_MaxS32;
  389. if (eIndex >= 0) {
  390. SkASSERT(eLink[eIndex] == rIndex);
  391. eLink[eIndex] = SK_MaxS32;
  392. } else {
  393. SkASSERT(sLink[~eIndex] == ~rIndex);
  394. sLink[~eIndex] = SK_MaxS32;
  395. }
  396. }
  397. rIndex = eIndex;
  398. if (rIndex < 0) {
  399. forward ^= 1;
  400. rIndex = ~rIndex;
  401. }
  402. } while (true);
  403. for (rIndex = 0; rIndex < linkCount; ++rIndex) {
  404. if (sLink[rIndex] != SK_MaxS32) {
  405. break;
  406. }
  407. }
  408. } while (rIndex < linkCount);
  409. #if DEBUG_ASSEMBLE
  410. for (rIndex = 0; rIndex < linkCount; ++rIndex) {
  411. SkASSERT(sLink[rIndex] == SK_MaxS32);
  412. SkASSERT(eLink[rIndex] == SK_MaxS32);
  413. }
  414. #endif
  415. return;
  416. }