svg_raster.c 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924
  1. /* svg_raster: SVG geometry flattening + antialiased scanline fill.
  2. * See svg_raster.h. */
  3. #include "svg_raster.h"
  4. #include <stdlib.h>
  5. #include <math.h>
  6. #define SVGR_PI 3.14159265358979323846
  7. /* ---- numbers and transforms ---- */
  8. static int is_ws(char c)
  9. {
  10. return c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == '\f';
  11. }
  12. static const char *skip_sep(const char *p)
  13. {
  14. while (is_ws(*p) || *p == ',')
  15. p++;
  16. return p;
  17. }
  18. double svgr_num(const char **pp, int *ok)
  19. {
  20. const char *p = skip_sep(*pp);
  21. double v = 0, scale = 1;
  22. int neg = 0, digits = 0;
  23. if (*p == '-' || *p == '+') {
  24. neg = *p == '-';
  25. p++;
  26. }
  27. while (*p >= '0' && *p <= '9') {
  28. v = v * 10 + (*p - '0');
  29. p++;
  30. digits++;
  31. }
  32. if (*p == '.') {
  33. p++;
  34. while (*p >= '0' && *p <= '9') {
  35. scale /= 10;
  36. v += (*p - '0') * scale;
  37. p++;
  38. digits++;
  39. }
  40. }
  41. if (!digits) {
  42. if (ok)
  43. *ok = 0;
  44. return 0;
  45. }
  46. if ((*p == 'e' || *p == 'E') &&
  47. ((p[1] >= '0' && p[1] <= '9') ||
  48. ((p[1] == '-' || p[1] == '+') && p[2] >= '0' && p[2] <= '9'))) {
  49. int eneg = 0, e = 0;
  50. p++;
  51. if (*p == '-' || *p == '+') {
  52. eneg = *p == '-';
  53. p++;
  54. }
  55. while (*p >= '0' && *p <= '9') {
  56. if (e < 300)
  57. e = e * 10 + (*p - '0');
  58. p++;
  59. }
  60. while (e-- > 0)
  61. v = eneg ? v / 10 : v * 10;
  62. }
  63. *pp = p;
  64. if (ok)
  65. *ok = 1;
  66. return neg ? -v : v;
  67. }
  68. void svgr_mat_mul(double out[6], const double a[6], const double b[6])
  69. {
  70. double r[6];
  71. r[0] = a[0] * b[0] + a[2] * b[1];
  72. r[1] = a[1] * b[0] + a[3] * b[1];
  73. r[2] = a[0] * b[2] + a[2] * b[3];
  74. r[3] = a[1] * b[2] + a[3] * b[3];
  75. r[4] = a[0] * b[4] + a[2] * b[5] + a[4];
  76. r[5] = a[1] * b[4] + a[3] * b[5] + a[5];
  77. out[0] = r[0];
  78. out[1] = r[1];
  79. out[2] = r[2];
  80. out[3] = r[3];
  81. out[4] = r[4];
  82. out[5] = r[5];
  83. }
  84. static int name_is(const char *p, const char *name, const char **end)
  85. {
  86. while (*name) {
  87. char c = *p;
  88. if (c >= 'A' && c <= 'Z')
  89. c = (char)(c - 'A' + 'a');
  90. if (c != *name)
  91. return 0;
  92. p++;
  93. name++;
  94. }
  95. *end = p;
  96. return 1;
  97. }
  98. void svgr_transform(double m[6], const char *s)
  99. {
  100. const char *p = s;
  101. while (p && *p) {
  102. double v[6], t[6] = { 1, 0, 0, 1, 0, 0 };
  103. int n = 0, ok = 1, kind;
  104. const char *q;
  105. p = skip_sep(p);
  106. if (!*p)
  107. break;
  108. if (name_is(p, "matrix", &q))
  109. kind = 0;
  110. else if (name_is(p, "translate", &q))
  111. kind = 1;
  112. else if (name_is(p, "scale", &q))
  113. kind = 2;
  114. else if (name_is(p, "rotate", &q))
  115. kind = 3;
  116. else if (name_is(p, "skewx", &q))
  117. kind = 4;
  118. else if (name_is(p, "skewy", &q))
  119. kind = 5;
  120. else
  121. return;
  122. p = q;
  123. while (is_ws(*p))
  124. p++;
  125. if (*p != '(')
  126. return;
  127. p++;
  128. while (n < 6) {
  129. const char *save = p;
  130. double x = svgr_num(&p, &ok);
  131. if (!ok) {
  132. p = save;
  133. break;
  134. }
  135. v[n++] = x;
  136. }
  137. p = skip_sep(p);
  138. if (*p != ')')
  139. return;
  140. p++;
  141. switch (kind) {
  142. case 0:
  143. if (n != 6)
  144. return;
  145. t[0] = v[0]; t[1] = v[1]; t[2] = v[2];
  146. t[3] = v[3]; t[4] = v[4]; t[5] = v[5];
  147. break;
  148. case 1:
  149. if (n < 1)
  150. return;
  151. t[4] = v[0];
  152. t[5] = n > 1 ? v[1] : 0;
  153. break;
  154. case 2:
  155. if (n < 1)
  156. return;
  157. t[0] = v[0];
  158. t[3] = n > 1 ? v[1] : v[0];
  159. break;
  160. case 3: {
  161. double a, c, sn;
  162. if (n < 1)
  163. return;
  164. a = v[0] * SVGR_PI / 180.0;
  165. c = cos(a);
  166. sn = sin(a);
  167. t[0] = c; t[1] = sn; t[2] = -sn; t[3] = c;
  168. if (n >= 3) {
  169. t[4] = v[1] - c * v[1] + sn * v[2];
  170. t[5] = v[2] - sn * v[1] - c * v[2];
  171. }
  172. break;
  173. }
  174. case 4:
  175. if (n < 1)
  176. return;
  177. t[2] = tan(v[0] * SVGR_PI / 180.0);
  178. break;
  179. default:
  180. if (n < 1)
  181. return;
  182. t[1] = tan(v[0] * SVGR_PI / 180.0);
  183. break;
  184. }
  185. svgr_mat_mul(m, m, t);
  186. }
  187. }
  188. /* ---- geometry ---- */
  189. void svgr_init(struct svgr *r, void *buf, unsigned int cap)
  190. {
  191. r->pt = (float *)buf;
  192. r->fl = (unsigned char *)buf + cap * 2 * sizeof(float);
  193. r->cap = cap;
  194. r->n = 0;
  195. r->overflow = 0;
  196. r->m[0] = 1; r->m[1] = 0; r->m[2] = 0;
  197. r->m[3] = 1; r->m[4] = 0; r->m[5] = 0;
  198. r->open = 0;
  199. r->sp = 0;
  200. r->last = 0;
  201. r->cx = r->cy = r->sx = r->sy = r->lcx = r->lcy = 0;
  202. }
  203. void svgr_reset(struct svgr *r, const double m[6])
  204. {
  205. unsigned int i;
  206. r->n = 0;
  207. r->overflow = 0;
  208. for (i = 0; i < 6; i++)
  209. r->m[i] = m[i];
  210. r->open = 0;
  211. r->sp = 0;
  212. r->last = 0;
  213. r->cx = r->cy = r->sx = r->sy = r->lcx = r->lcy = 0;
  214. }
  215. static void add_dev(struct svgr *r, double x, double y, unsigned char fl)
  216. {
  217. if (r->n >= r->cap) {
  218. r->overflow = 1;
  219. return;
  220. }
  221. /* Keep coordinates sane: a wild transform must not overflow the
  222. * float -> int conversions in the scanline code. */
  223. if (x < -100000)
  224. x = -100000;
  225. if (x > 100000)
  226. x = 100000;
  227. if (y < -100000)
  228. y = -100000;
  229. if (y > 100000)
  230. y = 100000;
  231. r->pt[2 * r->n] = (float)x;
  232. r->pt[2 * r->n + 1] = (float)y;
  233. r->fl[r->n] = fl;
  234. r->n++;
  235. }
  236. static void add_user(struct svgr *r, double x, double y, unsigned char fl)
  237. {
  238. const double *m = r->m;
  239. add_dev(r, m[0] * x + m[2] * y + m[4], m[1] * x + m[3] * y + m[5], fl);
  240. }
  241. void svgr_move(struct svgr *r, double x, double y)
  242. {
  243. r->sp = r->n;
  244. add_user(r, x, y, SVGR_PT_START);
  245. r->open = 1;
  246. r->cx = r->sx = x;
  247. r->cy = r->sy = y;
  248. r->lcx = x;
  249. r->lcy = y;
  250. }
  251. void svgr_line(struct svgr *r, double x, double y)
  252. {
  253. if (!r->open)
  254. svgr_move(r, r->cx, r->cy);
  255. add_user(r, x, y, 0);
  256. r->cx = r->lcx = x;
  257. r->cy = r->lcy = y;
  258. }
  259. /* Device-space length of a control polygon, for the flattening step. */
  260. static double dev_len(const struct svgr *r, const double *xy, int npts)
  261. {
  262. const double *m = r->m;
  263. double len = 0, px = 0, py = 0;
  264. int i;
  265. for (i = 0; i < npts; i++) {
  266. double x = m[0] * xy[2 * i] + m[2] * xy[2 * i + 1] + m[4];
  267. double y = m[1] * xy[2 * i] + m[3] * xy[2 * i + 1] + m[5];
  268. if (i)
  269. len += sqrt((x - px) * (x - px) + (y - py) * (y - py));
  270. px = x;
  271. py = y;
  272. }
  273. return len;
  274. }
  275. static int seg_count(double len)
  276. {
  277. int n = (int)(len / 3.0) + 1;
  278. if (n > 64)
  279. n = 64;
  280. return n;
  281. }
  282. void svgr_cubic(struct svgr *r, double x1, double y1, double x2, double y2,
  283. double x, double y)
  284. {
  285. double xy[8];
  286. double x0 = r->cx, y0 = r->cy;
  287. int i, n;
  288. if (!r->open)
  289. svgr_move(r, x0, y0);
  290. xy[0] = x0; xy[1] = y0; xy[2] = x1; xy[3] = y1;
  291. xy[4] = x2; xy[5] = y2; xy[6] = x; xy[7] = y;
  292. n = seg_count(dev_len(r, xy, 4));
  293. for (i = 1; i <= n; i++) {
  294. double t = (double)i / n, u = 1 - t;
  295. double a = u * u * u, b = 3 * u * u * t, c = 3 * u * t * t,
  296. d = t * t * t;
  297. add_user(r, a * x0 + b * x1 + c * x2 + d * x,
  298. a * y0 + b * y1 + c * y2 + d * y, 0);
  299. }
  300. r->cx = x;
  301. r->cy = y;
  302. r->lcx = x2;
  303. r->lcy = y2;
  304. }
  305. void svgr_quad(struct svgr *r, double x1, double y1, double x, double y)
  306. {
  307. double xy[6];
  308. double x0 = r->cx, y0 = r->cy;
  309. int i, n;
  310. if (!r->open)
  311. svgr_move(r, x0, y0);
  312. xy[0] = x0; xy[1] = y0; xy[2] = x1; xy[3] = y1; xy[4] = x; xy[5] = y;
  313. n = seg_count(dev_len(r, xy, 3));
  314. for (i = 1; i <= n; i++) {
  315. double t = (double)i / n, u = 1 - t;
  316. add_user(r, u * u * x0 + 2 * u * t * x1 + t * t * x,
  317. u * u * y0 + 2 * u * t * y1 + t * t * y, 0);
  318. }
  319. r->cx = x;
  320. r->cy = y;
  321. r->lcx = x1;
  322. r->lcy = y1;
  323. }
  324. static double vec_angle(double ux, double uy, double vx, double vy)
  325. {
  326. return atan2(ux * vy - uy * vx, ux * vx + uy * vy);
  327. }
  328. /* Endpoint -> center parameterization (SVG 1.1 implementation notes F.6). */
  329. void svgr_arc(struct svgr *r, double rx, double ry, double rot, int large,
  330. int sweep, double x, double y)
  331. {
  332. double x0 = r->cx, y0 = r->cy;
  333. double phi, cp, sp, dx2, dy2, x1p, y1p, lam, sq, num, den, coef;
  334. double cxp, cyp, cx, cy, th1, dth, scale;
  335. int i, n;
  336. if (!r->open)
  337. svgr_move(r, x0, y0);
  338. if (x0 == x && y0 == y)
  339. return;
  340. rx = fabs(rx);
  341. ry = fabs(ry);
  342. if (rx == 0 || ry == 0) {
  343. svgr_line(r, x, y);
  344. return;
  345. }
  346. phi = rot * SVGR_PI / 180.0;
  347. cp = cos(phi);
  348. sp = sin(phi);
  349. dx2 = (x0 - x) / 2;
  350. dy2 = (y0 - y) / 2;
  351. x1p = cp * dx2 + sp * dy2;
  352. y1p = -sp * dx2 + cp * dy2;
  353. lam = (x1p * x1p) / (rx * rx) + (y1p * y1p) / (ry * ry);
  354. if (lam > 1) {
  355. sq = sqrt(lam);
  356. rx *= sq;
  357. ry *= sq;
  358. }
  359. num = rx * rx * ry * ry - rx * rx * y1p * y1p - ry * ry * x1p * x1p;
  360. den = rx * rx * y1p * y1p + ry * ry * x1p * x1p;
  361. coef = (den > 0 && num > 0) ? sqrt(num / den) : 0;
  362. if (large == sweep)
  363. coef = -coef;
  364. cxp = coef * rx * y1p / ry;
  365. cyp = -coef * ry * x1p / rx;
  366. cx = cp * cxp - sp * cyp + (x0 + x) / 2;
  367. cy = sp * cxp + cp * cyp + (y0 + y) / 2;
  368. th1 = vec_angle(1, 0, (x1p - cxp) / rx, (y1p - cyp) / ry);
  369. dth = vec_angle((x1p - cxp) / rx, (y1p - cyp) / ry,
  370. (-x1p - cxp) / rx, (-y1p - cyp) / ry);
  371. if (!sweep && dth > 0)
  372. dth -= 2 * SVGR_PI;
  373. else if (sweep && dth < 0)
  374. dth += 2 * SVGR_PI;
  375. scale = sqrt(fabs(r->m[0] * r->m[3] - r->m[1] * r->m[2]));
  376. n = seg_count(fabs(dth) * (rx > ry ? rx : ry) * scale);
  377. if (n < 2)
  378. n = 2;
  379. for (i = 1; i <= n; i++) {
  380. double t = th1 + dth * i / n;
  381. double ex = rx * cos(t), ey = ry * sin(t);
  382. if (i == n)
  383. add_user(r, x, y, 0);
  384. else
  385. add_user(r, cp * ex - sp * ey + cx,
  386. sp * ex + cp * ey + cy, 0);
  387. }
  388. r->cx = r->lcx = x;
  389. r->cy = r->lcy = y;
  390. }
  391. void svgr_close(struct svgr *r)
  392. {
  393. if (r->open && r->sp < r->n)
  394. r->fl[r->sp] |= SVGR_PT_CLOSED;
  395. r->open = 0;
  396. r->cx = r->lcx = r->sx;
  397. r->cy = r->lcy = r->sy;
  398. }
  399. static const char *read_flag(const char *p, int *flag, int *ok)
  400. {
  401. p = skip_sep(p);
  402. if (*p == '0' || *p == '1') {
  403. *flag = *p - '0';
  404. *ok = 1;
  405. return p + 1;
  406. }
  407. *ok = 0;
  408. return p;
  409. }
  410. int svgr_path(struct svgr *r, const char *d)
  411. {
  412. const char *p = d;
  413. char cmd = 0;
  414. r->last = 0;
  415. while (p && *p) {
  416. double a[7];
  417. int fresh = 0, rel, need, i, ok = 1;
  418. char c;
  419. p = skip_sep(p);
  420. if (!*p)
  421. break;
  422. if ((*p >= 'A' && *p <= 'Z') || (*p >= 'a' && *p <= 'z')) {
  423. cmd = *p++;
  424. fresh = 1;
  425. } else if (!cmd) {
  426. return -1;
  427. }
  428. rel = cmd >= 'a' && cmd <= 'z';
  429. c = rel ? (char)(cmd - 'a' + 'A') : cmd;
  430. if (c == 'Z') {
  431. if (!fresh)
  432. return -1;
  433. svgr_close(r);
  434. r->last = 'Z';
  435. continue;
  436. }
  437. switch (c) {
  438. case 'M': case 'L': case 'T': need = 2; break;
  439. case 'H': case 'V': need = 1; break;
  440. case 'C': need = 6; break;
  441. case 'S': case 'Q': need = 4; break;
  442. case 'A': need = 7; break;
  443. default: return -1;
  444. }
  445. for (i = 0; i < need && ok; i++) {
  446. if (c == 'A' && (i == 3 || i == 4)) {
  447. int f = 0;
  448. p = read_flag(p, &f, &ok);
  449. a[i] = f;
  450. } else {
  451. a[i] = svgr_num(&p, &ok);
  452. }
  453. }
  454. if (!ok)
  455. return -1;
  456. if (rel) {
  457. double ox = r->cx, oy = r->cy;
  458. switch (c) {
  459. case 'H': a[0] += ox; break;
  460. case 'V': a[0] += oy; break;
  461. case 'A': a[5] += ox; a[6] += oy; break;
  462. default:
  463. for (i = 0; i + 1 < need; i += 2) {
  464. a[i] += ox;
  465. a[i + 1] += oy;
  466. }
  467. }
  468. }
  469. switch (c) {
  470. case 'M':
  471. if (fresh)
  472. svgr_move(r, a[0], a[1]);
  473. else
  474. svgr_line(r, a[0], a[1]);
  475. break;
  476. case 'L':
  477. svgr_line(r, a[0], a[1]);
  478. break;
  479. case 'H':
  480. svgr_line(r, a[0], r->cy);
  481. break;
  482. case 'V':
  483. svgr_line(r, r->cx, a[0]);
  484. break;
  485. case 'C':
  486. svgr_cubic(r, a[0], a[1], a[2], a[3], a[4], a[5]);
  487. break;
  488. case 'S': {
  489. double x1 = r->cx, y1 = r->cy;
  490. if (r->last == 'C' || r->last == 'S') {
  491. x1 = 2 * r->cx - r->lcx;
  492. y1 = 2 * r->cy - r->lcy;
  493. }
  494. svgr_cubic(r, x1, y1, a[0], a[1], a[2], a[3]);
  495. break;
  496. }
  497. case 'Q':
  498. svgr_quad(r, a[0], a[1], a[2], a[3]);
  499. break;
  500. case 'T': {
  501. double x1 = r->cx, y1 = r->cy;
  502. if (r->last == 'Q' || r->last == 'T') {
  503. x1 = 2 * r->cx - r->lcx;
  504. y1 = 2 * r->cy - r->lcy;
  505. }
  506. svgr_quad(r, x1, y1, a[0], a[1]);
  507. break;
  508. }
  509. case 'A':
  510. svgr_arc(r, a[0], a[1], a[2], (int)a[3], (int)a[4],
  511. a[5], a[6]);
  512. break;
  513. }
  514. r->last = c;
  515. /* Extra coordinate pairs after a moveto are linetos. */
  516. if (c == 'M')
  517. cmd = rel ? 'l' : 'L';
  518. }
  519. return 0;
  520. }
  521. void svgr_rect(struct svgr *r, double x, double y, double w, double h,
  522. double rx, double ry)
  523. {
  524. if (w <= 0 || h <= 0)
  525. return;
  526. if (rx < 0)
  527. rx = 0;
  528. if (ry < 0)
  529. ry = 0;
  530. if (rx > w / 2)
  531. rx = w / 2;
  532. if (ry > h / 2)
  533. ry = h / 2;
  534. if (rx == 0 || ry == 0) {
  535. svgr_move(r, x, y);
  536. svgr_line(r, x + w, y);
  537. svgr_line(r, x + w, y + h);
  538. svgr_line(r, x, y + h);
  539. svgr_close(r);
  540. return;
  541. }
  542. svgr_move(r, x + rx, y);
  543. svgr_line(r, x + w - rx, y);
  544. svgr_arc(r, rx, ry, 0, 0, 1, x + w, y + ry);
  545. svgr_line(r, x + w, y + h - ry);
  546. svgr_arc(r, rx, ry, 0, 0, 1, x + w - rx, y + h);
  547. svgr_line(r, x + rx, y + h);
  548. svgr_arc(r, rx, ry, 0, 0, 1, x, y + h - ry);
  549. svgr_line(r, x, y + ry);
  550. svgr_arc(r, rx, ry, 0, 0, 1, x + rx, y);
  551. svgr_close(r);
  552. }
  553. void svgr_ellipse(struct svgr *r, double cx, double cy, double rx, double ry)
  554. {
  555. if (rx <= 0 || ry <= 0)
  556. return;
  557. svgr_move(r, cx + rx, cy);
  558. svgr_arc(r, rx, ry, 0, 0, 1, cx - rx, cy);
  559. svgr_arc(r, rx, ry, 0, 0, 1, cx + rx, cy);
  560. svgr_close(r);
  561. }
  562. void svgr_points(struct svgr *r, const char *pts, int close)
  563. {
  564. const char *p = pts;
  565. int first = 1, ok = 1;
  566. while (p && *p) {
  567. double x = svgr_num(&p, &ok), y;
  568. if (!ok)
  569. break;
  570. y = svgr_num(&p, &ok);
  571. if (!ok)
  572. break;
  573. if (first)
  574. svgr_move(r, x, y);
  575. else
  576. svgr_line(r, x, y);
  577. first = 0;
  578. }
  579. if (!first && close)
  580. svgr_close(r);
  581. }
  582. /* ---- scanline fill ---- */
  583. struct edge {
  584. float x0, y0, x1, y1; /* y0 < y1 */
  585. float dxdy;
  586. int dir;
  587. int next; /* bucket chain */
  588. };
  589. struct cross {
  590. float x;
  591. int dir;
  592. };
  593. static void composite_row(struct svgr_layer *L, int y, const int *cov,
  594. int x0, int x1, unsigned short color,
  595. unsigned int alpha)
  596. {
  597. unsigned int sr = (color >> 11) & 31, sg = (color >> 5) & 63,
  598. sb = color & 31;
  599. int x;
  600. for (x = x0; x <= x1; x++) {
  601. int c = cov[x];
  602. unsigned int sa, da, oa, idx;
  603. unsigned short d;
  604. if (c <= 0)
  605. continue;
  606. if (c > 256)
  607. c = 256;
  608. sa = (unsigned int)c * alpha / 256;
  609. if (!sa)
  610. continue;
  611. idx = (unsigned int)y * (unsigned int)L->w + (unsigned int)x;
  612. da = L->a[idx];
  613. if (sa >= 255 || !da) {
  614. L->px[idx] = color;
  615. oa = sa + da * (255 - sa) / 255;
  616. L->a[idx] = (unsigned char)(oa > 255 ? 255 : oa);
  617. continue;
  618. }
  619. d = L->px[idx];
  620. {
  621. unsigned int dw = da * (255 - sa) / 255;
  622. unsigned int r5, g6, b5;
  623. oa = sa + dw;
  624. r5 = (sr * sa + ((d >> 11) & 31) * dw) / oa;
  625. g6 = (sg * sa + ((d >> 5) & 63) * dw) / oa;
  626. b5 = (sb * sa + (d & 31) * dw) / oa;
  627. L->px[idx] = (unsigned short)((r5 << 11) | (g6 << 5) |
  628. b5);
  629. L->a[idx] = (unsigned char)(oa > 255 ? 255 : oa);
  630. }
  631. }
  632. }
  633. static void span_add(int *cov, int w, float xa, float xb, int *minx,
  634. int *maxx)
  635. {
  636. int ia, ib, i;
  637. if (xa < 0)
  638. xa = 0;
  639. if (xb > (float)w)
  640. xb = (float)w;
  641. if (xb <= xa)
  642. return;
  643. ia = (int)xa;
  644. ib = (int)xb;
  645. if (ia < *minx)
  646. *minx = ia;
  647. if ((ib < w ? ib : w - 1) > *maxx)
  648. *maxx = ib < w ? ib : w - 1;
  649. if (ia == ib) {
  650. cov[ia] += (int)(64.0f * (xb - xa) + 0.5f);
  651. return;
  652. }
  653. cov[ia] += (int)(64.0f * ((float)(ia + 1) - xa) + 0.5f);
  654. for (i = ia + 1; i < ib; i++)
  655. cov[i] += 64;
  656. if (ib < w)
  657. cov[ib] += (int)(64.0f * (xb - (float)ib) + 0.5f);
  658. }
  659. void svgr_fill(struct svgr *r, struct svgr_layer *L, unsigned short color,
  660. unsigned int alpha, int evenodd)
  661. {
  662. struct edge *e;
  663. struct cross *xs;
  664. int *head, *active, *cov;
  665. unsigned int i, ne = 0, start = 0;
  666. int nact = 0, y, ymin_all = L->h, ymax_all = -1;
  667. if (r->n < 2 || L->w <= 0 || L->h <= 0 || !alpha)
  668. return;
  669. e = (struct edge *)malloc((r->n + 1) * sizeof(*e));
  670. xs = (struct cross *)malloc((r->n + 1) * sizeof(*xs));
  671. head = (int *)malloc((unsigned int)L->h * sizeof(int));
  672. active = (int *)malloc((r->n + 1) * sizeof(int));
  673. cov = (int *)malloc(((unsigned int)L->w + 1) * sizeof(int));
  674. if (!e || !xs || !head || !active || !cov)
  675. goto out;
  676. for (i = 0; i < (unsigned int)L->h; i++)
  677. head[i] = -1;
  678. for (i = 0; i <= (unsigned int)L->w; i++)
  679. cov[i] = 0;
  680. /* Edges: consecutive points of each subpath, plus the implicit
  681. * closing edge (fills always close). */
  682. for (i = 0; i < r->n; i++) {
  683. unsigned int j;
  684. float ax, ay, bx, by;
  685. if (i + 1 < r->n && !(r->fl[i + 1] & SVGR_PT_START))
  686. j = i + 1;
  687. else
  688. j = start;
  689. if (i + 1 >= r->n || (r->fl[i + 1] & SVGR_PT_START))
  690. start = i + 1;
  691. ax = r->pt[2 * i];
  692. ay = r->pt[2 * i + 1];
  693. bx = r->pt[2 * j];
  694. by = r->pt[2 * j + 1];
  695. if (ay == by || j == i)
  696. continue;
  697. if (ay < by) {
  698. e[ne].x0 = ax; e[ne].y0 = ay;
  699. e[ne].x1 = bx; e[ne].y1 = by;
  700. e[ne].dir = 1;
  701. } else {
  702. e[ne].x0 = bx; e[ne].y0 = by;
  703. e[ne].x1 = ax; e[ne].y1 = ay;
  704. e[ne].dir = -1;
  705. }
  706. if (e[ne].y1 <= 0 || e[ne].y0 >= (float)L->h)
  707. continue;
  708. e[ne].dxdy = (e[ne].x1 - e[ne].x0) / (e[ne].y1 - e[ne].y0);
  709. {
  710. int row = e[ne].y0 < 0 ? 0 : (int)e[ne].y0;
  711. int last = (int)e[ne].y1;
  712. if (row >= L->h)
  713. continue;
  714. if (last >= L->h)
  715. last = L->h - 1;
  716. if (row < ymin_all)
  717. ymin_all = row;
  718. if (last > ymax_all)
  719. ymax_all = last;
  720. e[ne].next = head[row];
  721. head[row] = (int)ne;
  722. }
  723. ne++;
  724. }
  725. for (y = ymin_all; y <= ymax_all && y < L->h; y++) {
  726. int k, minx = L->w, maxx = -1, a;
  727. for (a = head[y]; a >= 0; a = e[a].next)
  728. active[nact++] = a;
  729. /* drop finished edges */
  730. for (k = 0; k < nact;) {
  731. if (e[active[k]].y1 <= (float)y)
  732. active[k] = active[--nact];
  733. else
  734. k++;
  735. }
  736. if (!nact)
  737. continue;
  738. for (k = 0; k < 4; k++) {
  739. float sy = (float)y + ((float)k + 0.5f) * 0.25f;
  740. int nx = 0, q, wind = 0;
  741. for (q = 0; q < nact; q++) {
  742. struct edge *ed = &e[active[q]];
  743. int t;
  744. float x;
  745. if (sy < ed->y0 || sy >= ed->y1)
  746. continue;
  747. x = ed->x0 + (sy - ed->y0) * ed->dxdy;
  748. /* insertion sort by x */
  749. t = nx++;
  750. while (t > 0 && xs[t - 1].x > x) {
  751. xs[t] = xs[t - 1];
  752. t--;
  753. }
  754. xs[t].x = x;
  755. xs[t].dir = ed->dir;
  756. }
  757. for (q = 0; q + 1 < nx; q++) {
  758. int inside;
  759. wind += xs[q].dir;
  760. inside = evenodd ? (wind & 1) : wind != 0;
  761. if (inside)
  762. span_add(cov, L->w, xs[q].x,
  763. xs[q + 1].x, &minx, &maxx);
  764. }
  765. }
  766. if (maxx >= minx) {
  767. composite_row(L, y, cov, minx, maxx, color, alpha);
  768. for (k = minx; k <= maxx; k++)
  769. cov[k] = 0;
  770. }
  771. }
  772. out:
  773. free(e);
  774. free(xs);
  775. free(head);
  776. free(active);
  777. free(cov);
  778. }
  779. /* Strokes become filled geometry: one quad per segment, all with the same
  780. * winding, plus an octagon at each joint, filled with the nonzero rule so
  781. * the overlaps union. */
  782. void svgr_stroke(struct svgr *r, struct svgr_layer *L, double width,
  783. unsigned short color, unsigned int alpha)
  784. {
  785. struct svgr s;
  786. unsigned int i, start = 0, cap;
  787. double hw = width / 2;
  788. void *buf;
  789. int joins = width > 1.5;
  790. if (r->n < 2 || width <= 0)
  791. return;
  792. if (hw < 0.35)
  793. hw = 0.35;
  794. cap = r->n * (joins ? 12 : 4) + 16;
  795. buf = malloc(cap * (2 * sizeof(float) + 1));
  796. if (!buf)
  797. return;
  798. svgr_init(&s, buf, cap);
  799. for (i = 0; i < r->n; i++) {
  800. unsigned int j;
  801. int closing = 0;
  802. double ax, ay, bx, by, dx, dy, len, nx, ny;
  803. if (r->fl[i] & SVGR_PT_START)
  804. start = i;
  805. if (i + 1 < r->n && !(r->fl[i + 1] & SVGR_PT_START)) {
  806. j = i + 1;
  807. } else {
  808. if (!(r->fl[start] & SVGR_PT_CLOSED))
  809. continue;
  810. j = start;
  811. closing = 1;
  812. }
  813. (void)closing;
  814. ax = r->pt[2 * i];
  815. ay = r->pt[2 * i + 1];
  816. bx = r->pt[2 * j];
  817. by = r->pt[2 * j + 1];
  818. dx = bx - ax;
  819. dy = by - ay;
  820. len = sqrt(dx * dx + dy * dy);
  821. if (len < 1e-6)
  822. continue;
  823. nx = -dy / len * hw;
  824. ny = dx / len * hw;
  825. add_dev(&s, ax + nx, ay + ny, SVGR_PT_START);
  826. add_dev(&s, bx + nx, by + ny, 0);
  827. add_dev(&s, bx - nx, by - ny, 0);
  828. add_dev(&s, ax - nx, ay - ny, 0);
  829. if (joins) {
  830. /* The quad above runs clockwise in device space
  831. * (y down) for every direction; draw the octagon in
  832. * the same sense. */
  833. int k;
  834. double sgn = (nx * dy - ny * dx) > 0 ? 1 : -1;
  835. for (k = 0; k < 8; k++) {
  836. double ang = sgn * k * SVGR_PI / 4;
  837. add_dev(&s, bx + hw * cos(ang),
  838. by + hw * sin(ang),
  839. k ? 0 : SVGR_PT_START);
  840. }
  841. }
  842. }
  843. svgr_fill(&s, L, color, alpha, 0);
  844. free(buf);
  845. }