SkEdgeBuilder.cpp 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439
  1. /*
  2. * Copyright 2011 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 "include/core/SkPath.h"
  8. #include "include/private/SkTo.h"
  9. #include "src/core/SkAnalyticEdge.h"
  10. #include "src/core/SkEdge.h"
  11. #include "src/core/SkEdgeBuilder.h"
  12. #include "src/core/SkEdgeClipper.h"
  13. #include "src/core/SkGeometry.h"
  14. #include "src/core/SkLineClipper.h"
  15. #include "src/core/SkPathPriv.h"
  16. #include "src/core/SkSafeMath.h"
  17. SkEdgeBuilder::Combine SkBasicEdgeBuilder::combineVertical(const SkEdge* edge, SkEdge* last) {
  18. if (last->fCurveCount || last->fDX || edge->fX != last->fX) {
  19. return kNo_Combine;
  20. }
  21. if (edge->fWinding == last->fWinding) {
  22. if (edge->fLastY + 1 == last->fFirstY) {
  23. last->fFirstY = edge->fFirstY;
  24. return kPartial_Combine;
  25. }
  26. if (edge->fFirstY == last->fLastY + 1) {
  27. last->fLastY = edge->fLastY;
  28. return kPartial_Combine;
  29. }
  30. return kNo_Combine;
  31. }
  32. if (edge->fFirstY == last->fFirstY) {
  33. if (edge->fLastY == last->fLastY) {
  34. return kTotal_Combine;
  35. }
  36. if (edge->fLastY < last->fLastY) {
  37. last->fFirstY = edge->fLastY + 1;
  38. return kPartial_Combine;
  39. }
  40. last->fFirstY = last->fLastY + 1;
  41. last->fLastY = edge->fLastY;
  42. last->fWinding = edge->fWinding;
  43. return kPartial_Combine;
  44. }
  45. if (edge->fLastY == last->fLastY) {
  46. if (edge->fFirstY > last->fFirstY) {
  47. last->fLastY = edge->fFirstY - 1;
  48. return kPartial_Combine;
  49. }
  50. last->fLastY = last->fFirstY - 1;
  51. last->fFirstY = edge->fFirstY;
  52. last->fWinding = edge->fWinding;
  53. return kPartial_Combine;
  54. }
  55. return kNo_Combine;
  56. }
  57. SkEdgeBuilder::Combine SkAnalyticEdgeBuilder::combineVertical(const SkAnalyticEdge* edge,
  58. SkAnalyticEdge* last) {
  59. auto approximately_equal = [](SkFixed a, SkFixed b) {
  60. return SkAbs32(a - b) < 0x100;
  61. };
  62. if (last->fCurveCount || last->fDX || edge->fX != last->fX) {
  63. return kNo_Combine;
  64. }
  65. if (edge->fWinding == last->fWinding) {
  66. if (edge->fLowerY == last->fUpperY) {
  67. last->fUpperY = edge->fUpperY;
  68. last->fY = last->fUpperY;
  69. return kPartial_Combine;
  70. }
  71. if (approximately_equal(edge->fUpperY, last->fLowerY)) {
  72. last->fLowerY = edge->fLowerY;
  73. return kPartial_Combine;
  74. }
  75. return kNo_Combine;
  76. }
  77. if (approximately_equal(edge->fUpperY, last->fUpperY)) {
  78. if (approximately_equal(edge->fLowerY, last->fLowerY)) {
  79. return kTotal_Combine;
  80. }
  81. if (edge->fLowerY < last->fLowerY) {
  82. last->fUpperY = edge->fLowerY;
  83. last->fY = last->fUpperY;
  84. return kPartial_Combine;
  85. }
  86. last->fUpperY = last->fLowerY;
  87. last->fY = last->fUpperY;
  88. last->fLowerY = edge->fLowerY;
  89. last->fWinding = edge->fWinding;
  90. return kPartial_Combine;
  91. }
  92. if (approximately_equal(edge->fLowerY, last->fLowerY)) {
  93. if (edge->fUpperY > last->fUpperY) {
  94. last->fLowerY = edge->fUpperY;
  95. return kPartial_Combine;
  96. }
  97. last->fLowerY = last->fUpperY;
  98. last->fUpperY = edge->fUpperY;
  99. last->fY = last->fUpperY;
  100. last->fWinding = edge->fWinding;
  101. return kPartial_Combine;
  102. }
  103. return kNo_Combine;
  104. }
  105. template <typename Edge>
  106. static bool is_vertical(const Edge* edge) {
  107. return edge->fDX == 0
  108. && edge->fCurveCount == 0;
  109. }
  110. // TODO: we can deallocate the edge if edge->setFoo() fails
  111. // or when we don't use it (kPartial_Combine or kTotal_Combine).
  112. void SkBasicEdgeBuilder::addLine(const SkPoint pts[]) {
  113. SkEdge* edge = fAlloc.make<SkEdge>();
  114. if (edge->setLine(pts[0], pts[1], fClipShift)) {
  115. Combine combine = is_vertical(edge) && !fList.empty()
  116. ? this->combineVertical(edge, (SkEdge*)fList.top())
  117. : kNo_Combine;
  118. switch (combine) {
  119. case kTotal_Combine: fList.pop(); break;
  120. case kPartial_Combine: break;
  121. case kNo_Combine: fList.push_back(edge); break;
  122. }
  123. }
  124. }
  125. void SkAnalyticEdgeBuilder::addLine(const SkPoint pts[]) {
  126. SkAnalyticEdge* edge = fAlloc.make<SkAnalyticEdge>();
  127. if (edge->setLine(pts[0], pts[1])) {
  128. Combine combine = is_vertical(edge) && !fList.empty()
  129. ? this->combineVertical(edge, (SkAnalyticEdge*)fList.top())
  130. : kNo_Combine;
  131. switch (combine) {
  132. case kTotal_Combine: fList.pop(); break;
  133. case kPartial_Combine: break;
  134. case kNo_Combine: fList.push_back(edge); break;
  135. }
  136. }
  137. }
  138. void SkBasicEdgeBuilder::addQuad(const SkPoint pts[]) {
  139. SkQuadraticEdge* edge = fAlloc.make<SkQuadraticEdge>();
  140. if (edge->setQuadratic(pts, fClipShift)) {
  141. fList.push_back(edge);
  142. }
  143. }
  144. void SkAnalyticEdgeBuilder::addQuad(const SkPoint pts[]) {
  145. SkAnalyticQuadraticEdge* edge = fAlloc.make<SkAnalyticQuadraticEdge>();
  146. if (edge->setQuadratic(pts)) {
  147. fList.push_back(edge);
  148. }
  149. }
  150. void SkBasicEdgeBuilder::addCubic(const SkPoint pts[]) {
  151. SkCubicEdge* edge = fAlloc.make<SkCubicEdge>();
  152. if (edge->setCubic(pts, fClipShift)) {
  153. fList.push_back(edge);
  154. }
  155. }
  156. void SkAnalyticEdgeBuilder::addCubic(const SkPoint pts[]) {
  157. SkAnalyticCubicEdge* edge = fAlloc.make<SkAnalyticCubicEdge>();
  158. if (edge->setCubic(pts)) {
  159. fList.push_back(edge);
  160. }
  161. }
  162. // TODO: merge addLine() and addPolyLine()?
  163. SkEdgeBuilder::Combine SkBasicEdgeBuilder::addPolyLine(SkPoint pts[],
  164. char* arg_edge, char** arg_edgePtr) {
  165. auto edge = (SkEdge*) arg_edge;
  166. auto edgePtr = (SkEdge**)arg_edgePtr;
  167. if (edge->setLine(pts[0], pts[1], fClipShift)) {
  168. return is_vertical(edge) && edgePtr > (SkEdge**)fEdgeList
  169. ? this->combineVertical(edge, edgePtr[-1])
  170. : kNo_Combine;
  171. }
  172. return SkEdgeBuilder::kPartial_Combine; // A convenient lie. Same do-nothing behavior.
  173. }
  174. SkEdgeBuilder::Combine SkAnalyticEdgeBuilder::addPolyLine(SkPoint pts[],
  175. char* arg_edge, char** arg_edgePtr) {
  176. auto edge = (SkAnalyticEdge*) arg_edge;
  177. auto edgePtr = (SkAnalyticEdge**)arg_edgePtr;
  178. if (edge->setLine(pts[0], pts[1])) {
  179. return is_vertical(edge) && edgePtr > (SkAnalyticEdge**)fEdgeList
  180. ? this->combineVertical(edge, edgePtr[-1])
  181. : kNo_Combine;
  182. }
  183. return SkEdgeBuilder::kPartial_Combine; // As above.
  184. }
  185. SkRect SkBasicEdgeBuilder::recoverClip(const SkIRect& src) const {
  186. return { SkIntToScalar(src.fLeft >> fClipShift),
  187. SkIntToScalar(src.fTop >> fClipShift),
  188. SkIntToScalar(src.fRight >> fClipShift),
  189. SkIntToScalar(src.fBottom >> fClipShift), };
  190. }
  191. SkRect SkAnalyticEdgeBuilder::recoverClip(const SkIRect& src) const {
  192. return SkRect::Make(src);
  193. }
  194. char* SkBasicEdgeBuilder::allocEdges(size_t n, size_t* size) {
  195. *size = sizeof(SkEdge);
  196. return (char*)fAlloc.makeArrayDefault<SkEdge>(n);
  197. }
  198. char* SkAnalyticEdgeBuilder::allocEdges(size_t n, size_t* size) {
  199. *size = sizeof(SkAnalyticEdge);
  200. return (char*)fAlloc.makeArrayDefault<SkAnalyticEdge>(n);
  201. }
  202. // TODO: maybe get rid of buildPoly() entirely?
  203. int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, bool canCullToTheRight) {
  204. SkPath::Iter iter(path, true);
  205. SkPoint pts[4];
  206. SkPath::Verb verb;
  207. size_t maxEdgeCount = path.countPoints();
  208. if (iclip) {
  209. // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since
  210. // we turn portions that are clipped out on the left/right into vertical
  211. // segments.
  212. SkSafeMath safe;
  213. maxEdgeCount = safe.mul(maxEdgeCount, SkLineClipper::kMaxClippedLineSegments);
  214. if (!safe) {
  215. return 0;
  216. }
  217. }
  218. size_t edgeSize;
  219. char* edge = this->allocEdges(maxEdgeCount, &edgeSize);
  220. SkDEBUGCODE(char* edgeStart = edge);
  221. char** edgePtr = fAlloc.makeArrayDefault<char*>(maxEdgeCount);
  222. fEdgeList = (void**)edgePtr;
  223. if (iclip) {
  224. SkRect clip = this->recoverClip(*iclip);
  225. while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
  226. switch (verb) {
  227. case SkPath::kMove_Verb:
  228. case SkPath::kClose_Verb:
  229. // we ignore these, and just get the whole segment from
  230. // the corresponding line/quad/cubic verbs
  231. break;
  232. case SkPath::kLine_Verb: {
  233. SkPoint lines[SkLineClipper::kMaxPoints];
  234. int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight);
  235. SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments);
  236. for (int i = 0; i < lineCount; i++) {
  237. switch( this->addPolyLine(lines + i, edge, edgePtr) ) {
  238. case kTotal_Combine: edgePtr--; break;
  239. case kPartial_Combine: break;
  240. case kNo_Combine: *edgePtr++ = edge;
  241. edge += edgeSize;
  242. }
  243. }
  244. break;
  245. }
  246. default:
  247. SkDEBUGFAIL("unexpected verb");
  248. break;
  249. }
  250. }
  251. } else {
  252. while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
  253. switch (verb) {
  254. case SkPath::kMove_Verb:
  255. case SkPath::kClose_Verb:
  256. // we ignore these, and just get the whole segment from
  257. // the corresponding line/quad/cubic verbs
  258. break;
  259. case SkPath::kLine_Verb: {
  260. switch( this->addPolyLine(pts, edge, edgePtr) ) {
  261. case kTotal_Combine: edgePtr--; break;
  262. case kPartial_Combine: break;
  263. case kNo_Combine: *edgePtr++ = edge;
  264. edge += edgeSize;
  265. }
  266. break;
  267. }
  268. default:
  269. SkDEBUGFAIL("unexpected verb");
  270. break;
  271. }
  272. }
  273. }
  274. SkASSERT((size_t)(edge - edgeStart) <= maxEdgeCount * edgeSize);
  275. SkASSERT((size_t)(edgePtr - (char**)fEdgeList) <= maxEdgeCount);
  276. return SkToInt(edgePtr - (char**)fEdgeList);
  277. }
  278. int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, bool canCullToTheRight) {
  279. SkAutoConicToQuads quadder;
  280. const SkScalar conicTol = SK_Scalar1 / 4;
  281. SkPath::Iter iter(path, true);
  282. SkPoint pts[4];
  283. SkPath::Verb verb;
  284. bool is_finite = true;
  285. if (iclip) {
  286. SkRect clip = this->recoverClip(*iclip);
  287. SkEdgeClipper clipper(canCullToTheRight);
  288. auto apply_clipper = [this, &clipper, &is_finite] {
  289. SkPoint pts[4];
  290. SkPath::Verb verb;
  291. while ((verb = clipper.next(pts)) != SkPath::kDone_Verb) {
  292. const int count = SkPathPriv::PtsInIter(verb);
  293. if (!SkScalarsAreFinite(&pts[0].fX, count*2)) {
  294. is_finite = false;
  295. return;
  296. }
  297. switch (verb) {
  298. case SkPath::kLine_Verb: this->addLine (pts); break;
  299. case SkPath::kQuad_Verb: this->addQuad (pts); break;
  300. case SkPath::kCubic_Verb: this->addCubic(pts); break;
  301. default: break;
  302. }
  303. }
  304. };
  305. while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
  306. switch (verb) {
  307. case SkPath::kMove_Verb:
  308. case SkPath::kClose_Verb:
  309. // we ignore these, and just get the whole segment from
  310. // the corresponding line/quad/cubic verbs
  311. break;
  312. case SkPath::kLine_Verb:
  313. if (clipper.clipLine(pts[0], pts[1], clip)) {
  314. apply_clipper();
  315. }
  316. break;
  317. case SkPath::kQuad_Verb:
  318. if (clipper.clipQuad(pts, clip)) {
  319. apply_clipper();
  320. }
  321. break;
  322. case SkPath::kConic_Verb: {
  323. const SkPoint* quadPts = quadder.computeQuads(
  324. pts, iter.conicWeight(), conicTol);
  325. for (int i = 0; i < quadder.countQuads(); ++i) {
  326. if (clipper.clipQuad(quadPts, clip)) {
  327. apply_clipper();
  328. }
  329. quadPts += 2;
  330. }
  331. } break;
  332. case SkPath::kCubic_Verb:
  333. if (clipper.clipCubic(pts, clip)) {
  334. apply_clipper();
  335. }
  336. break;
  337. default:
  338. SkDEBUGFAIL("unexpected verb");
  339. break;
  340. }
  341. }
  342. } else {
  343. while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
  344. auto handle_quad = [this](const SkPoint pts[3]) {
  345. SkPoint monoX[5];
  346. int n = SkChopQuadAtYExtrema(pts, monoX);
  347. for (int i = 0; i <= n; i++) {
  348. this->addQuad(&monoX[i * 2]);
  349. }
  350. };
  351. switch (verb) {
  352. case SkPath::kMove_Verb:
  353. case SkPath::kClose_Verb:
  354. // we ignore these, and just get the whole segment from
  355. // the corresponding line/quad/cubic verbs
  356. break;
  357. case SkPath::kLine_Verb:
  358. this->addLine(pts);
  359. break;
  360. case SkPath::kQuad_Verb: {
  361. handle_quad(pts);
  362. break;
  363. }
  364. case SkPath::kConic_Verb: {
  365. const SkPoint* quadPts = quadder.computeQuads(
  366. pts, iter.conicWeight(), conicTol);
  367. for (int i = 0; i < quadder.countQuads(); ++i) {
  368. handle_quad(quadPts);
  369. quadPts += 2;
  370. }
  371. } break;
  372. case SkPath::kCubic_Verb: {
  373. SkPoint monoY[10];
  374. int n = SkChopCubicAtYExtrema(pts, monoY);
  375. for (int i = 0; i <= n; i++) {
  376. this->addCubic(&monoY[i * 3]);
  377. }
  378. break;
  379. }
  380. default:
  381. SkDEBUGFAIL("unexpected verb");
  382. break;
  383. }
  384. }
  385. }
  386. fEdgeList = fList.begin();
  387. return is_finite ? fList.count() : 0;
  388. }
  389. int SkEdgeBuilder::buildEdges(const SkPath& path,
  390. const SkIRect* shiftedClip) {
  391. // If we're convex, then we need both edges, even if the right edge is past the clip.
  392. const bool canCullToTheRight = !path.isConvex();
  393. // We can use our buildPoly() optimization if all the segments are lines.
  394. // (Edges are homogenous and stored contiguously in memory, no need for indirection.)
  395. const int count = SkPath::kLine_SegmentMask == path.getSegmentMasks()
  396. ? this->buildPoly(path, shiftedClip, canCullToTheRight)
  397. : this->build (path, shiftedClip, canCullToTheRight);
  398. SkASSERT(count >= 0);
  399. // If we can't cull to the right, we should have count > 1 (or 0).
  400. if (!canCullToTheRight) {
  401. SkASSERT(count != 1);
  402. }
  403. return count;
  404. }