SkOpEdgeBuilder.cpp 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357
  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/SkGeometry.h"
  8. #include "src/pathops/SkOpEdgeBuilder.h"
  9. #include "src/pathops/SkReduceOrder.h"
  10. void SkOpEdgeBuilder::init() {
  11. fOperand = false;
  12. fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
  13. : kWinding_PathOpsMask;
  14. fUnparseable = false;
  15. fSecondHalf = preFetch();
  16. }
  17. // very tiny points cause numerical instability : don't allow them
  18. static void force_small_to_zero(SkPoint* pt) {
  19. if (SkScalarAbs(pt->fX) < FLT_EPSILON_ORDERABLE_ERR) {
  20. pt->fX = 0;
  21. }
  22. if (SkScalarAbs(pt->fY) < FLT_EPSILON_ORDERABLE_ERR) {
  23. pt->fY = 0;
  24. }
  25. }
  26. static bool can_add_curve(SkPath::Verb verb, SkPoint* curve) {
  27. if (SkPath::kMove_Verb == verb) {
  28. return false;
  29. }
  30. for (int index = 0; index <= SkPathOpsVerbToPoints(verb); ++index) {
  31. force_small_to_zero(&curve[index]);
  32. }
  33. return SkPath::kLine_Verb != verb || !SkDPoint::ApproximatelyEqual(curve[0], curve[1]);
  34. }
  35. void SkOpEdgeBuilder::addOperand(const SkPath& path) {
  36. SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb);
  37. fPathVerbs.pop();
  38. fPath = &path;
  39. fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
  40. : kWinding_PathOpsMask;
  41. preFetch();
  42. }
  43. bool SkOpEdgeBuilder::finish() {
  44. fOperand = false;
  45. if (fUnparseable || !walk()) {
  46. return false;
  47. }
  48. complete();
  49. SkOpContour* contour = fContourBuilder.contour();
  50. if (contour && !contour->count()) {
  51. fContoursHead->remove(contour);
  52. }
  53. return true;
  54. }
  55. void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) {
  56. if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) {
  57. *fPathVerbs.append() = SkPath::kLine_Verb;
  58. *fPathPts.append() = curveStart;
  59. } else {
  60. int verbCount = fPathVerbs.count();
  61. int ptsCount = fPathPts.count();
  62. if (SkPath::kLine_Verb == fPathVerbs[verbCount - 1]
  63. && fPathPts[ptsCount - 2] == curveStart) {
  64. fPathVerbs.pop();
  65. fPathPts.pop();
  66. } else {
  67. fPathPts[ptsCount - 1] = curveStart;
  68. }
  69. }
  70. *fPathVerbs.append() = SkPath::kClose_Verb;
  71. }
  72. int SkOpEdgeBuilder::preFetch() {
  73. if (!fPath->isFinite()) {
  74. fUnparseable = true;
  75. return 0;
  76. }
  77. SkPath::RawIter iter(*fPath);
  78. SkPoint curveStart;
  79. SkPoint curve[4];
  80. SkPoint pts[4];
  81. SkPath::Verb verb;
  82. bool lastCurve = false;
  83. do {
  84. verb = iter.next(pts);
  85. switch (verb) {
  86. case SkPath::kMove_Verb:
  87. if (!fAllowOpenContours && lastCurve) {
  88. closeContour(curve[0], curveStart);
  89. }
  90. *fPathVerbs.append() = verb;
  91. force_small_to_zero(&pts[0]);
  92. *fPathPts.append() = pts[0];
  93. curveStart = curve[0] = pts[0];
  94. lastCurve = false;
  95. continue;
  96. case SkPath::kLine_Verb:
  97. force_small_to_zero(&pts[1]);
  98. if (SkDPoint::ApproximatelyEqual(curve[0], pts[1])) {
  99. uint8_t lastVerb = fPathVerbs.top();
  100. if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) {
  101. fPathPts.top() = curve[0] = pts[1];
  102. }
  103. continue; // skip degenerate points
  104. }
  105. break;
  106. case SkPath::kQuad_Verb:
  107. force_small_to_zero(&pts[1]);
  108. force_small_to_zero(&pts[2]);
  109. curve[1] = pts[1];
  110. curve[2] = pts[2];
  111. verb = SkReduceOrder::Quad(curve, pts);
  112. if (verb == SkPath::kMove_Verb) {
  113. continue; // skip degenerate points
  114. }
  115. break;
  116. case SkPath::kConic_Verb:
  117. force_small_to_zero(&pts[1]);
  118. force_small_to_zero(&pts[2]);
  119. curve[1] = pts[1];
  120. curve[2] = pts[2];
  121. verb = SkReduceOrder::Quad(curve, pts);
  122. if (SkPath::kQuad_Verb == verb && 1 != iter.conicWeight()) {
  123. verb = SkPath::kConic_Verb;
  124. } else if (verb == SkPath::kMove_Verb) {
  125. continue; // skip degenerate points
  126. }
  127. break;
  128. case SkPath::kCubic_Verb:
  129. force_small_to_zero(&pts[1]);
  130. force_small_to_zero(&pts[2]);
  131. force_small_to_zero(&pts[3]);
  132. curve[1] = pts[1];
  133. curve[2] = pts[2];
  134. curve[3] = pts[3];
  135. verb = SkReduceOrder::Cubic(curve, pts);
  136. if (verb == SkPath::kMove_Verb) {
  137. continue; // skip degenerate points
  138. }
  139. break;
  140. case SkPath::kClose_Verb:
  141. closeContour(curve[0], curveStart);
  142. lastCurve = false;
  143. continue;
  144. case SkPath::kDone_Verb:
  145. continue;
  146. }
  147. *fPathVerbs.append() = verb;
  148. int ptCount = SkPathOpsVerbToPoints(verb);
  149. fPathPts.append(ptCount, &pts[1]);
  150. if (verb == SkPath::kConic_Verb) {
  151. *fWeights.append() = iter.conicWeight();
  152. }
  153. curve[0] = pts[ptCount];
  154. lastCurve = true;
  155. } while (verb != SkPath::kDone_Verb);
  156. if (!fAllowOpenContours && lastCurve) {
  157. closeContour(curve[0], curveStart);
  158. }
  159. *fPathVerbs.append() = SkPath::kDone_Verb;
  160. return fPathVerbs.count() - 1;
  161. }
  162. bool SkOpEdgeBuilder::close() {
  163. complete();
  164. return true;
  165. }
  166. bool SkOpEdgeBuilder::walk() {
  167. uint8_t* verbPtr = fPathVerbs.begin();
  168. uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
  169. SkPoint* pointsPtr = fPathPts.begin();
  170. SkScalar* weightPtr = fWeights.begin();
  171. SkPath::Verb verb;
  172. SkOpContour* contour = fContourBuilder.contour();
  173. int moveToPtrBump = 0;
  174. while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
  175. if (verbPtr == endOfFirstHalf) {
  176. fOperand = true;
  177. }
  178. verbPtr++;
  179. switch (verb) {
  180. case SkPath::kMove_Verb:
  181. if (contour && contour->count()) {
  182. if (fAllowOpenContours) {
  183. complete();
  184. } else if (!close()) {
  185. return false;
  186. }
  187. }
  188. if (!contour) {
  189. fContourBuilder.setContour(contour = fContoursHead->appendContour());
  190. }
  191. contour->init(fGlobalState, fOperand,
  192. fXorMask[fOperand] == kEvenOdd_PathOpsMask);
  193. pointsPtr += moveToPtrBump;
  194. moveToPtrBump = 1;
  195. continue;
  196. case SkPath::kLine_Verb:
  197. fContourBuilder.addLine(pointsPtr);
  198. break;
  199. case SkPath::kQuad_Verb:
  200. {
  201. SkVector v1 = pointsPtr[1] - pointsPtr[0];
  202. SkVector v2 = pointsPtr[2] - pointsPtr[1];
  203. if (v1.dot(v2) < 0) {
  204. SkPoint pair[5];
  205. if (SkChopQuadAtMaxCurvature(pointsPtr, pair) == 1) {
  206. goto addOneQuad;
  207. }
  208. if (!SkScalarsAreFinite(&pair[0].fX, SK_ARRAY_COUNT(pair) * 2)) {
  209. return false;
  210. }
  211. for (unsigned index = 0; index < SK_ARRAY_COUNT(pair); ++index) {
  212. force_small_to_zero(&pair[index]);
  213. }
  214. SkPoint cStorage[2][2];
  215. SkPath::Verb v1 = SkReduceOrder::Quad(&pair[0], cStorage[0]);
  216. SkPath::Verb v2 = SkReduceOrder::Quad(&pair[2], cStorage[1]);
  217. SkPoint* curve1 = v1 != SkPath::kLine_Verb ? &pair[0] : cStorage[0];
  218. SkPoint* curve2 = v2 != SkPath::kLine_Verb ? &pair[2] : cStorage[1];
  219. if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
  220. fContourBuilder.addCurve(v1, curve1);
  221. fContourBuilder.addCurve(v2, curve2);
  222. break;
  223. }
  224. }
  225. }
  226. addOneQuad:
  227. fContourBuilder.addQuad(pointsPtr);
  228. break;
  229. case SkPath::kConic_Verb: {
  230. SkVector v1 = pointsPtr[1] - pointsPtr[0];
  231. SkVector v2 = pointsPtr[2] - pointsPtr[1];
  232. SkScalar weight = *weightPtr++;
  233. if (v1.dot(v2) < 0) {
  234. // FIXME: max curvature for conics hasn't been implemented; use placeholder
  235. SkScalar maxCurvature = SkFindQuadMaxCurvature(pointsPtr);
  236. if (0 < maxCurvature && maxCurvature < 1) {
  237. SkConic conic(pointsPtr, weight);
  238. SkConic pair[2];
  239. if (!conic.chopAt(maxCurvature, pair)) {
  240. // if result can't be computed, use original
  241. fContourBuilder.addConic(pointsPtr, weight);
  242. break;
  243. }
  244. SkPoint cStorage[2][3];
  245. SkPath::Verb v1 = SkReduceOrder::Conic(pair[0], cStorage[0]);
  246. SkPath::Verb v2 = SkReduceOrder::Conic(pair[1], cStorage[1]);
  247. SkPoint* curve1 = v1 != SkPath::kLine_Verb ? pair[0].fPts : cStorage[0];
  248. SkPoint* curve2 = v2 != SkPath::kLine_Verb ? pair[1].fPts : cStorage[1];
  249. if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
  250. fContourBuilder.addCurve(v1, curve1, pair[0].fW);
  251. fContourBuilder.addCurve(v2, curve2, pair[1].fW);
  252. break;
  253. }
  254. }
  255. }
  256. fContourBuilder.addConic(pointsPtr, weight);
  257. } break;
  258. case SkPath::kCubic_Verb:
  259. {
  260. // Split complex cubics (such as self-intersecting curves or
  261. // ones with difficult curvature) in two before proceeding.
  262. // This can be required for intersection to succeed.
  263. SkScalar splitT[3];
  264. int breaks = SkDCubic::ComplexBreak(pointsPtr, splitT);
  265. if (!breaks) {
  266. fContourBuilder.addCubic(pointsPtr);
  267. break;
  268. }
  269. SkASSERT(breaks <= (int) SK_ARRAY_COUNT(splitT));
  270. struct Splitsville {
  271. double fT[2];
  272. SkPoint fPts[4];
  273. SkPoint fReduced[4];
  274. SkPath::Verb fVerb;
  275. bool fCanAdd;
  276. } splits[4];
  277. SkASSERT(SK_ARRAY_COUNT(splits) == SK_ARRAY_COUNT(splitT) + 1);
  278. SkTQSort(splitT, &splitT[breaks - 1]);
  279. for (int index = 0; index <= breaks; ++index) {
  280. Splitsville* split = &splits[index];
  281. split->fT[0] = index ? splitT[index - 1] : 0;
  282. split->fT[1] = index < breaks ? splitT[index] : 1;
  283. SkDCubic part = SkDCubic::SubDivide(pointsPtr, split->fT[0], split->fT[1]);
  284. if (!part.toFloatPoints(split->fPts)) {
  285. return false;
  286. }
  287. split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced);
  288. SkPoint* curve = SkPath::kCubic_Verb == verb
  289. ? split->fPts : split->fReduced;
  290. split->fCanAdd = can_add_curve(split->fVerb, curve);
  291. }
  292. for (int index = 0; index <= breaks; ++index) {
  293. Splitsville* split = &splits[index];
  294. if (!split->fCanAdd) {
  295. continue;
  296. }
  297. int prior = index;
  298. while (prior > 0 && !splits[prior - 1].fCanAdd) {
  299. --prior;
  300. }
  301. if (prior < index) {
  302. split->fT[0] = splits[prior].fT[0];
  303. split->fPts[0] = splits[prior].fPts[0];
  304. }
  305. int next = index;
  306. int breakLimit = SkTMin(breaks, (int) SK_ARRAY_COUNT(splits) - 1);
  307. while (next < breakLimit && !splits[next + 1].fCanAdd) {
  308. ++next;
  309. }
  310. if (next > index) {
  311. split->fT[1] = splits[next].fT[1];
  312. split->fPts[3] = splits[next].fPts[3];
  313. }
  314. if (prior < index || next > index) {
  315. split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced);
  316. }
  317. SkPoint* curve = SkPath::kCubic_Verb == split->fVerb
  318. ? split->fPts : split->fReduced;
  319. if (!can_add_curve(split->fVerb, curve)) {
  320. return false;
  321. }
  322. fContourBuilder.addCurve(split->fVerb, curve);
  323. }
  324. }
  325. break;
  326. case SkPath::kClose_Verb:
  327. SkASSERT(contour);
  328. if (!close()) {
  329. return false;
  330. }
  331. contour = nullptr;
  332. continue;
  333. default:
  334. SkDEBUGFAIL("bad verb");
  335. return false;
  336. }
  337. SkASSERT(contour);
  338. if (contour->count()) {
  339. contour->debugValidate();
  340. }
  341. pointsPtr += SkPathOpsVerbToPoints(verb);
  342. }
  343. fContourBuilder.flush();
  344. if (contour && contour->count() &&!fAllowOpenContours && !close()) {
  345. return false;
  346. }
  347. return true;
  348. }