SkEdge.cpp 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503
  1. /*
  2. * Copyright 2006 The Android Open Source Project
  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/SkEdge.h"
  8. #include "include/private/SkTo.h"
  9. #include "src/core/SkFDot6.h"
  10. #include "src/core/SkMathPriv.h"
  11. #include <utility>
  12. /*
  13. In setLine, setQuadratic, setCubic, the first thing we do is to convert
  14. the points into FDot6. This is modulated by the shift parameter, which
  15. will either be 0, or something like 2 for antialiasing.
  16. In the float case, we want to turn the float into .6 by saying pt * 64,
  17. or pt * 256 for antialiasing. This is implemented as 1 << (shift + 6).
  18. In the fixed case, we want to turn the fixed into .6 by saying pt >> 10,
  19. or pt >> 8 for antialiasing. This is implemented as pt >> (10 - shift).
  20. */
  21. static inline SkFixed SkFDot6ToFixedDiv2(SkFDot6 value) {
  22. // we want to return SkFDot6ToFixed(value >> 1), but we don't want to throw
  23. // away data in value, so just perform a modify up-shift
  24. return SkLeftShift(value, 16 - 6 - 1);
  25. }
  26. /////////////////////////////////////////////////////////////////////////
  27. int SkEdge::setLine(const SkPoint& p0, const SkPoint& p1, const SkIRect* clip,
  28. int shift) {
  29. SkFDot6 x0, y0, x1, y1;
  30. {
  31. #ifdef SK_RASTERIZE_EVEN_ROUNDING
  32. x0 = SkScalarRoundToFDot6(p0.fX, shift);
  33. y0 = SkScalarRoundToFDot6(p0.fY, shift);
  34. x1 = SkScalarRoundToFDot6(p1.fX, shift);
  35. y1 = SkScalarRoundToFDot6(p1.fY, shift);
  36. #else
  37. float scale = float(1 << (shift + 6));
  38. x0 = int(p0.fX * scale);
  39. y0 = int(p0.fY * scale);
  40. x1 = int(p1.fX * scale);
  41. y1 = int(p1.fY * scale);
  42. #endif
  43. }
  44. int winding = 1;
  45. if (y0 > y1) {
  46. using std::swap;
  47. swap(x0, x1);
  48. swap(y0, y1);
  49. winding = -1;
  50. }
  51. int top = SkFDot6Round(y0);
  52. int bot = SkFDot6Round(y1);
  53. // are we a zero-height line?
  54. if (top == bot) {
  55. return 0;
  56. }
  57. // are we completely above or below the clip?
  58. if (clip && (top >= clip->fBottom || bot <= clip->fTop)) {
  59. return 0;
  60. }
  61. SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0);
  62. const SkFDot6 dy = SkEdge_Compute_DY(top, y0);
  63. fX = SkFDot6ToFixed(x0 + SkFixedMul(slope, dy)); // + SK_Fixed1/2
  64. fDX = slope;
  65. fFirstY = top;
  66. fLastY = bot - 1;
  67. fCurveCount = 0;
  68. fWinding = SkToS8(winding);
  69. fCurveShift = 0;
  70. if (clip) {
  71. this->chopLineWithClip(*clip);
  72. }
  73. return 1;
  74. }
  75. // called from a curve subclass
  76. int SkEdge::updateLine(SkFixed x0, SkFixed y0, SkFixed x1, SkFixed y1)
  77. {
  78. SkASSERT(fWinding == 1 || fWinding == -1);
  79. SkASSERT(fCurveCount != 0);
  80. // SkASSERT(fCurveShift != 0);
  81. y0 >>= 10;
  82. y1 >>= 10;
  83. SkASSERT(y0 <= y1);
  84. int top = SkFDot6Round(y0);
  85. int bot = SkFDot6Round(y1);
  86. // SkASSERT(top >= fFirstY);
  87. // are we a zero-height line?
  88. if (top == bot)
  89. return 0;
  90. x0 >>= 10;
  91. x1 >>= 10;
  92. SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0);
  93. const SkFDot6 dy = SkEdge_Compute_DY(top, y0);
  94. fX = SkFDot6ToFixed(x0 + SkFixedMul(slope, dy)); // + SK_Fixed1/2
  95. fDX = slope;
  96. fFirstY = top;
  97. fLastY = bot - 1;
  98. return 1;
  99. }
  100. void SkEdge::chopLineWithClip(const SkIRect& clip)
  101. {
  102. int top = fFirstY;
  103. SkASSERT(top < clip.fBottom);
  104. // clip the line to the top
  105. if (top < clip.fTop)
  106. {
  107. SkASSERT(fLastY >= clip.fTop);
  108. fX += fDX * (clip.fTop - top);
  109. fFirstY = clip.fTop;
  110. }
  111. }
  112. ///////////////////////////////////////////////////////////////////////////////
  113. /* We store 1<<shift in a (signed) byte, so its maximum value is 1<<6 == 64.
  114. Note that this limits the number of lines we use to approximate a curve.
  115. If we need to increase this, we need to store fCurveCount in something
  116. larger than int8_t.
  117. */
  118. #define MAX_COEFF_SHIFT 6
  119. static inline SkFDot6 cheap_distance(SkFDot6 dx, SkFDot6 dy)
  120. {
  121. dx = SkAbs32(dx);
  122. dy = SkAbs32(dy);
  123. // return max + min/2
  124. if (dx > dy)
  125. dx += dy >> 1;
  126. else
  127. dx = dy + (dx >> 1);
  128. return dx;
  129. }
  130. static inline int diff_to_shift(SkFDot6 dx, SkFDot6 dy, int shiftAA = 2)
  131. {
  132. // cheap calc of distance from center of p0-p2 to the center of the curve
  133. SkFDot6 dist = cheap_distance(dx, dy);
  134. // shift down dist (it is currently in dot6)
  135. // down by 3 should give us 1/8 pixel accuracy (assuming our dist is accurate...)
  136. // this is chosen by heuristic: make it as big as possible (to minimize segments)
  137. // ... but small enough so that our curves still look smooth
  138. // When shift > 0, we're using AA and everything is scaled up so we can
  139. // lower the accuracy.
  140. dist = (dist + (1 << 4)) >> (3 + shiftAA);
  141. // each subdivision (shift value) cuts this dist (error) by 1/4
  142. return (32 - SkCLZ(dist)) >> 1;
  143. }
  144. bool SkQuadraticEdge::setQuadraticWithoutUpdate(const SkPoint pts[3], int shift) {
  145. SkFDot6 x0, y0, x1, y1, x2, y2;
  146. {
  147. #ifdef SK_RASTERIZE_EVEN_ROUNDING
  148. x0 = SkScalarRoundToFDot6(pts[0].fX, shift);
  149. y0 = SkScalarRoundToFDot6(pts[0].fY, shift);
  150. x1 = SkScalarRoundToFDot6(pts[1].fX, shift);
  151. y1 = SkScalarRoundToFDot6(pts[1].fY, shift);
  152. x2 = SkScalarRoundToFDot6(pts[2].fX, shift);
  153. y2 = SkScalarRoundToFDot6(pts[2].fY, shift);
  154. #else
  155. float scale = float(1 << (shift + 6));
  156. x0 = int(pts[0].fX * scale);
  157. y0 = int(pts[0].fY * scale);
  158. x1 = int(pts[1].fX * scale);
  159. y1 = int(pts[1].fY * scale);
  160. x2 = int(pts[2].fX * scale);
  161. y2 = int(pts[2].fY * scale);
  162. #endif
  163. }
  164. int winding = 1;
  165. if (y0 > y2)
  166. {
  167. using std::swap;
  168. swap(x0, x2);
  169. swap(y0, y2);
  170. winding = -1;
  171. }
  172. SkASSERT(y0 <= y1 && y1 <= y2);
  173. int top = SkFDot6Round(y0);
  174. int bot = SkFDot6Round(y2);
  175. // are we a zero-height quad (line)?
  176. if (top == bot)
  177. return 0;
  178. // compute number of steps needed (1 << shift)
  179. {
  180. SkFDot6 dx = (SkLeftShift(x1, 1) - x0 - x2) >> 2;
  181. SkFDot6 dy = (SkLeftShift(y1, 1) - y0 - y2) >> 2;
  182. // This is a little confusing:
  183. // before this line, shift is the scale up factor for AA;
  184. // after this line, shift is the fCurveShift.
  185. shift = diff_to_shift(dx, dy, shift);
  186. SkASSERT(shift >= 0);
  187. }
  188. // need at least 1 subdivision for our bias trick
  189. if (shift == 0) {
  190. shift = 1;
  191. } else if (shift > MAX_COEFF_SHIFT) {
  192. shift = MAX_COEFF_SHIFT;
  193. }
  194. fWinding = SkToS8(winding);
  195. //fCubicDShift only set for cubics
  196. fCurveCount = SkToS8(1 << shift);
  197. /*
  198. * We want to reformulate into polynomial form, to make it clear how we
  199. * should forward-difference.
  200. *
  201. * p0 (1 - t)^2 + p1 t(1 - t) + p2 t^2 ==> At^2 + Bt + C
  202. *
  203. * A = p0 - 2p1 + p2
  204. * B = 2(p1 - p0)
  205. * C = p0
  206. *
  207. * Our caller must have constrained our inputs (p0..p2) to all fit into
  208. * 16.16. However, as seen above, we sometimes compute values that can be
  209. * larger (e.g. B = 2*(p1 - p0)). To guard against overflow, we will store
  210. * A and B at 1/2 of their actual value, and just apply a 2x scale during
  211. * application in updateQuadratic(). Hence we store (shift - 1) in
  212. * fCurveShift.
  213. */
  214. fCurveShift = SkToU8(shift - 1);
  215. SkFixed A = SkFDot6ToFixedDiv2(x0 - x1 - x1 + x2); // 1/2 the real value
  216. SkFixed B = SkFDot6ToFixed(x1 - x0); // 1/2 the real value
  217. fQx = SkFDot6ToFixed(x0);
  218. fQDx = B + (A >> shift); // biased by shift
  219. fQDDx = A >> (shift - 1); // biased by shift
  220. A = SkFDot6ToFixedDiv2(y0 - y1 - y1 + y2); // 1/2 the real value
  221. B = SkFDot6ToFixed(y1 - y0); // 1/2 the real value
  222. fQy = SkFDot6ToFixed(y0);
  223. fQDy = B + (A >> shift); // biased by shift
  224. fQDDy = A >> (shift - 1); // biased by shift
  225. fQLastX = SkFDot6ToFixed(x2);
  226. fQLastY = SkFDot6ToFixed(y2);
  227. return true;
  228. }
  229. int SkQuadraticEdge::setQuadratic(const SkPoint pts[3], int shift) {
  230. if (!setQuadraticWithoutUpdate(pts, shift)) {
  231. return 0;
  232. }
  233. return this->updateQuadratic();
  234. }
  235. int SkQuadraticEdge::updateQuadratic()
  236. {
  237. int success;
  238. int count = fCurveCount;
  239. SkFixed oldx = fQx;
  240. SkFixed oldy = fQy;
  241. SkFixed dx = fQDx;
  242. SkFixed dy = fQDy;
  243. SkFixed newx, newy;
  244. int shift = fCurveShift;
  245. SkASSERT(count > 0);
  246. do {
  247. if (--count > 0)
  248. {
  249. newx = oldx + (dx >> shift);
  250. dx += fQDDx;
  251. newy = oldy + (dy >> shift);
  252. dy += fQDDy;
  253. }
  254. else // last segment
  255. {
  256. newx = fQLastX;
  257. newy = fQLastY;
  258. }
  259. success = this->updateLine(oldx, oldy, newx, newy);
  260. oldx = newx;
  261. oldy = newy;
  262. } while (count > 0 && !success);
  263. fQx = newx;
  264. fQy = newy;
  265. fQDx = dx;
  266. fQDy = dy;
  267. fCurveCount = SkToS8(count);
  268. return success;
  269. }
  270. /////////////////////////////////////////////////////////////////////////
  271. static inline int SkFDot6UpShift(SkFDot6 x, int upShift) {
  272. SkASSERT((SkLeftShift(x, upShift) >> upShift) == x);
  273. return SkLeftShift(x, upShift);
  274. }
  275. /* f(1/3) = (8a + 12b + 6c + d) / 27
  276. f(2/3) = (a + 6b + 12c + 8d) / 27
  277. f(1/3)-b = (8a - 15b + 6c + d) / 27
  278. f(2/3)-c = (a + 6b - 15c + 8d) / 27
  279. use 16/512 to approximate 1/27
  280. */
  281. static SkFDot6 cubic_delta_from_line(SkFDot6 a, SkFDot6 b, SkFDot6 c, SkFDot6 d)
  282. {
  283. // since our parameters may be negative, we don't use << to avoid ASAN warnings
  284. SkFDot6 oneThird = (a*8 - b*15 + 6*c + d) * 19 >> 9;
  285. SkFDot6 twoThird = (a + 6*b - c*15 + d*8) * 19 >> 9;
  286. return SkMax32(SkAbs32(oneThird), SkAbs32(twoThird));
  287. }
  288. bool SkCubicEdge::setCubicWithoutUpdate(const SkPoint pts[4], int shift, bool sortY) {
  289. SkFDot6 x0, y0, x1, y1, x2, y2, x3, y3;
  290. {
  291. #ifdef SK_RASTERIZE_EVEN_ROUNDING
  292. x0 = SkScalarRoundToFDot6(pts[0].fX, shift);
  293. y0 = SkScalarRoundToFDot6(pts[0].fY, shift);
  294. x1 = SkScalarRoundToFDot6(pts[1].fX, shift);
  295. y1 = SkScalarRoundToFDot6(pts[1].fY, shift);
  296. x2 = SkScalarRoundToFDot6(pts[2].fX, shift);
  297. y2 = SkScalarRoundToFDot6(pts[2].fY, shift);
  298. x3 = SkScalarRoundToFDot6(pts[3].fX, shift);
  299. y3 = SkScalarRoundToFDot6(pts[3].fY, shift);
  300. #else
  301. float scale = float(1 << (shift + 6));
  302. x0 = int(pts[0].fX * scale);
  303. y0 = int(pts[0].fY * scale);
  304. x1 = int(pts[1].fX * scale);
  305. y1 = int(pts[1].fY * scale);
  306. x2 = int(pts[2].fX * scale);
  307. y2 = int(pts[2].fY * scale);
  308. x3 = int(pts[3].fX * scale);
  309. y3 = int(pts[3].fY * scale);
  310. #endif
  311. }
  312. int winding = 1;
  313. if (sortY && y0 > y3)
  314. {
  315. using std::swap;
  316. swap(x0, x3);
  317. swap(x1, x2);
  318. swap(y0, y3);
  319. swap(y1, y2);
  320. winding = -1;
  321. }
  322. int top = SkFDot6Round(y0);
  323. int bot = SkFDot6Round(y3);
  324. // are we a zero-height cubic (line)?
  325. if (sortY && top == bot)
  326. return 0;
  327. // compute number of steps needed (1 << shift)
  328. {
  329. // Can't use (center of curve - center of baseline), since center-of-curve
  330. // need not be the max delta from the baseline (it could even be coincident)
  331. // so we try just looking at the two off-curve points
  332. SkFDot6 dx = cubic_delta_from_line(x0, x1, x2, x3);
  333. SkFDot6 dy = cubic_delta_from_line(y0, y1, y2, y3);
  334. // add 1 (by observation)
  335. shift = diff_to_shift(dx, dy) + 1;
  336. }
  337. // need at least 1 subdivision for our bias trick
  338. SkASSERT(shift > 0);
  339. if (shift > MAX_COEFF_SHIFT) {
  340. shift = MAX_COEFF_SHIFT;
  341. }
  342. /* Since our in coming data is initially shifted down by 10 (or 8 in
  343. antialias). That means the most we can shift up is 8. However, we
  344. compute coefficients with a 3*, so the safest upshift is really 6
  345. */
  346. int upShift = 6; // largest safe value
  347. int downShift = shift + upShift - 10;
  348. if (downShift < 0) {
  349. downShift = 0;
  350. upShift = 10 - shift;
  351. }
  352. fWinding = SkToS8(winding);
  353. fCurveCount = SkToS8(SkLeftShift(-1, shift));
  354. fCurveShift = SkToU8(shift);
  355. fCubicDShift = SkToU8(downShift);
  356. SkFixed B = SkFDot6UpShift(3 * (x1 - x0), upShift);
  357. SkFixed C = SkFDot6UpShift(3 * (x0 - x1 - x1 + x2), upShift);
  358. SkFixed D = SkFDot6UpShift(x3 + 3 * (x1 - x2) - x0, upShift);
  359. fCx = SkFDot6ToFixed(x0);
  360. fCDx = B + (C >> shift) + (D >> 2*shift); // biased by shift
  361. fCDDx = 2*C + (3*D >> (shift - 1)); // biased by 2*shift
  362. fCDDDx = 3*D >> (shift - 1); // biased by 2*shift
  363. B = SkFDot6UpShift(3 * (y1 - y0), upShift);
  364. C = SkFDot6UpShift(3 * (y0 - y1 - y1 + y2), upShift);
  365. D = SkFDot6UpShift(y3 + 3 * (y1 - y2) - y0, upShift);
  366. fCy = SkFDot6ToFixed(y0);
  367. fCDy = B + (C >> shift) + (D >> 2*shift); // biased by shift
  368. fCDDy = 2*C + (3*D >> (shift - 1)); // biased by 2*shift
  369. fCDDDy = 3*D >> (shift - 1); // biased by 2*shift
  370. fCLastX = SkFDot6ToFixed(x3);
  371. fCLastY = SkFDot6ToFixed(y3);
  372. return true;
  373. }
  374. int SkCubicEdge::setCubic(const SkPoint pts[4], int shift) {
  375. if (!this->setCubicWithoutUpdate(pts, shift)) {
  376. return 0;
  377. }
  378. return this->updateCubic();
  379. }
  380. int SkCubicEdge::updateCubic()
  381. {
  382. int success;
  383. int count = fCurveCount;
  384. SkFixed oldx = fCx;
  385. SkFixed oldy = fCy;
  386. SkFixed newx, newy;
  387. const int ddshift = fCurveShift;
  388. const int dshift = fCubicDShift;
  389. SkASSERT(count < 0);
  390. do {
  391. if (++count < 0)
  392. {
  393. newx = oldx + (fCDx >> dshift);
  394. fCDx += fCDDx >> ddshift;
  395. fCDDx += fCDDDx;
  396. newy = oldy + (fCDy >> dshift);
  397. fCDy += fCDDy >> ddshift;
  398. fCDDy += fCDDDy;
  399. }
  400. else // last segment
  401. {
  402. // SkDebugf("LastX err=%d, LastY err=%d\n", (oldx + (fCDx >> shift) - fLastX), (oldy + (fCDy >> shift) - fLastY));
  403. newx = fCLastX;
  404. newy = fCLastY;
  405. }
  406. // we want to say SkASSERT(oldy <= newy), but our finite fixedpoint
  407. // doesn't always achieve that, so we have to explicitly pin it here.
  408. if (newy < oldy) {
  409. newy = oldy;
  410. }
  411. success = this->updateLine(oldx, oldy, newx, newy);
  412. oldx = newx;
  413. oldy = newy;
  414. } while (count < 0 && !success);
  415. fCx = newx;
  416. fCy = newy;
  417. fCurveCount = SkToS8(count);
  418. return success;
  419. }