| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924 |
- /* svg_raster: SVG geometry flattening + antialiased scanline fill.
- * See svg_raster.h. */
- #include "svg_raster.h"
- #include <stdlib.h>
- #include <math.h>
- #define SVGR_PI 3.14159265358979323846
- /* ---- numbers and transforms ---- */
- static int is_ws(char c)
- {
- return c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == '\f';
- }
- static const char *skip_sep(const char *p)
- {
- while (is_ws(*p) || *p == ',')
- p++;
- return p;
- }
- double svgr_num(const char **pp, int *ok)
- {
- const char *p = skip_sep(*pp);
- double v = 0, scale = 1;
- int neg = 0, digits = 0;
- if (*p == '-' || *p == '+') {
- neg = *p == '-';
- p++;
- }
- while (*p >= '0' && *p <= '9') {
- v = v * 10 + (*p - '0');
- p++;
- digits++;
- }
- if (*p == '.') {
- p++;
- while (*p >= '0' && *p <= '9') {
- scale /= 10;
- v += (*p - '0') * scale;
- p++;
- digits++;
- }
- }
- if (!digits) {
- if (ok)
- *ok = 0;
- return 0;
- }
- if ((*p == 'e' || *p == 'E') &&
- ((p[1] >= '0' && p[1] <= '9') ||
- ((p[1] == '-' || p[1] == '+') && p[2] >= '0' && p[2] <= '9'))) {
- int eneg = 0, e = 0;
- p++;
- if (*p == '-' || *p == '+') {
- eneg = *p == '-';
- p++;
- }
- while (*p >= '0' && *p <= '9') {
- if (e < 300)
- e = e * 10 + (*p - '0');
- p++;
- }
- while (e-- > 0)
- v = eneg ? v / 10 : v * 10;
- }
- *pp = p;
- if (ok)
- *ok = 1;
- return neg ? -v : v;
- }
- void svgr_mat_mul(double out[6], const double a[6], const double b[6])
- {
- double r[6];
- r[0] = a[0] * b[0] + a[2] * b[1];
- r[1] = a[1] * b[0] + a[3] * b[1];
- r[2] = a[0] * b[2] + a[2] * b[3];
- r[3] = a[1] * b[2] + a[3] * b[3];
- r[4] = a[0] * b[4] + a[2] * b[5] + a[4];
- r[5] = a[1] * b[4] + a[3] * b[5] + a[5];
- out[0] = r[0];
- out[1] = r[1];
- out[2] = r[2];
- out[3] = r[3];
- out[4] = r[4];
- out[5] = r[5];
- }
- static int name_is(const char *p, const char *name, const char **end)
- {
- while (*name) {
- char c = *p;
- if (c >= 'A' && c <= 'Z')
- c = (char)(c - 'A' + 'a');
- if (c != *name)
- return 0;
- p++;
- name++;
- }
- *end = p;
- return 1;
- }
- void svgr_transform(double m[6], const char *s)
- {
- const char *p = s;
- while (p && *p) {
- double v[6], t[6] = { 1, 0, 0, 1, 0, 0 };
- int n = 0, ok = 1, kind;
- const char *q;
- p = skip_sep(p);
- if (!*p)
- break;
- if (name_is(p, "matrix", &q))
- kind = 0;
- else if (name_is(p, "translate", &q))
- kind = 1;
- else if (name_is(p, "scale", &q))
- kind = 2;
- else if (name_is(p, "rotate", &q))
- kind = 3;
- else if (name_is(p, "skewx", &q))
- kind = 4;
- else if (name_is(p, "skewy", &q))
- kind = 5;
- else
- return;
- p = q;
- while (is_ws(*p))
- p++;
- if (*p != '(')
- return;
- p++;
- while (n < 6) {
- const char *save = p;
- double x = svgr_num(&p, &ok);
- if (!ok) {
- p = save;
- break;
- }
- v[n++] = x;
- }
- p = skip_sep(p);
- if (*p != ')')
- return;
- p++;
- switch (kind) {
- case 0:
- if (n != 6)
- return;
- t[0] = v[0]; t[1] = v[1]; t[2] = v[2];
- t[3] = v[3]; t[4] = v[4]; t[5] = v[5];
- break;
- case 1:
- if (n < 1)
- return;
- t[4] = v[0];
- t[5] = n > 1 ? v[1] : 0;
- break;
- case 2:
- if (n < 1)
- return;
- t[0] = v[0];
- t[3] = n > 1 ? v[1] : v[0];
- break;
- case 3: {
- double a, c, sn;
- if (n < 1)
- return;
- a = v[0] * SVGR_PI / 180.0;
- c = cos(a);
- sn = sin(a);
- t[0] = c; t[1] = sn; t[2] = -sn; t[3] = c;
- if (n >= 3) {
- t[4] = v[1] - c * v[1] + sn * v[2];
- t[5] = v[2] - sn * v[1] - c * v[2];
- }
- break;
- }
- case 4:
- if (n < 1)
- return;
- t[2] = tan(v[0] * SVGR_PI / 180.0);
- break;
- default:
- if (n < 1)
- return;
- t[1] = tan(v[0] * SVGR_PI / 180.0);
- break;
- }
- svgr_mat_mul(m, m, t);
- }
- }
- /* ---- geometry ---- */
- void svgr_init(struct svgr *r, void *buf, unsigned int cap)
- {
- r->pt = (float *)buf;
- r->fl = (unsigned char *)buf + cap * 2 * sizeof(float);
- r->cap = cap;
- r->n = 0;
- r->overflow = 0;
- r->m[0] = 1; r->m[1] = 0; r->m[2] = 0;
- r->m[3] = 1; r->m[4] = 0; r->m[5] = 0;
- r->open = 0;
- r->sp = 0;
- r->last = 0;
- r->cx = r->cy = r->sx = r->sy = r->lcx = r->lcy = 0;
- }
- void svgr_reset(struct svgr *r, const double m[6])
- {
- unsigned int i;
- r->n = 0;
- r->overflow = 0;
- for (i = 0; i < 6; i++)
- r->m[i] = m[i];
- r->open = 0;
- r->sp = 0;
- r->last = 0;
- r->cx = r->cy = r->sx = r->sy = r->lcx = r->lcy = 0;
- }
- static void add_dev(struct svgr *r, double x, double y, unsigned char fl)
- {
- if (r->n >= r->cap) {
- r->overflow = 1;
- return;
- }
- /* Keep coordinates sane: a wild transform must not overflow the
- * float -> int conversions in the scanline code. */
- if (x < -100000)
- x = -100000;
- if (x > 100000)
- x = 100000;
- if (y < -100000)
- y = -100000;
- if (y > 100000)
- y = 100000;
- r->pt[2 * r->n] = (float)x;
- r->pt[2 * r->n + 1] = (float)y;
- r->fl[r->n] = fl;
- r->n++;
- }
- static void add_user(struct svgr *r, double x, double y, unsigned char fl)
- {
- const double *m = r->m;
- add_dev(r, m[0] * x + m[2] * y + m[4], m[1] * x + m[3] * y + m[5], fl);
- }
- void svgr_move(struct svgr *r, double x, double y)
- {
- r->sp = r->n;
- add_user(r, x, y, SVGR_PT_START);
- r->open = 1;
- r->cx = r->sx = x;
- r->cy = r->sy = y;
- r->lcx = x;
- r->lcy = y;
- }
- void svgr_line(struct svgr *r, double x, double y)
- {
- if (!r->open)
- svgr_move(r, r->cx, r->cy);
- add_user(r, x, y, 0);
- r->cx = r->lcx = x;
- r->cy = r->lcy = y;
- }
- /* Device-space length of a control polygon, for the flattening step. */
- static double dev_len(const struct svgr *r, const double *xy, int npts)
- {
- const double *m = r->m;
- double len = 0, px = 0, py = 0;
- int i;
- for (i = 0; i < npts; i++) {
- double x = m[0] * xy[2 * i] + m[2] * xy[2 * i + 1] + m[4];
- double y = m[1] * xy[2 * i] + m[3] * xy[2 * i + 1] + m[5];
- if (i)
- len += sqrt((x - px) * (x - px) + (y - py) * (y - py));
- px = x;
- py = y;
- }
- return len;
- }
- static int seg_count(double len)
- {
- int n = (int)(len / 3.0) + 1;
- if (n > 64)
- n = 64;
- return n;
- }
- void svgr_cubic(struct svgr *r, double x1, double y1, double x2, double y2,
- double x, double y)
- {
- double xy[8];
- double x0 = r->cx, y0 = r->cy;
- int i, n;
- if (!r->open)
- svgr_move(r, x0, y0);
- xy[0] = x0; xy[1] = y0; xy[2] = x1; xy[3] = y1;
- xy[4] = x2; xy[5] = y2; xy[6] = x; xy[7] = y;
- n = seg_count(dev_len(r, xy, 4));
- for (i = 1; i <= n; i++) {
- double t = (double)i / n, u = 1 - t;
- double a = u * u * u, b = 3 * u * u * t, c = 3 * u * t * t,
- d = t * t * t;
- add_user(r, a * x0 + b * x1 + c * x2 + d * x,
- a * y0 + b * y1 + c * y2 + d * y, 0);
- }
- r->cx = x;
- r->cy = y;
- r->lcx = x2;
- r->lcy = y2;
- }
- void svgr_quad(struct svgr *r, double x1, double y1, double x, double y)
- {
- double xy[6];
- double x0 = r->cx, y0 = r->cy;
- int i, n;
- if (!r->open)
- svgr_move(r, x0, y0);
- xy[0] = x0; xy[1] = y0; xy[2] = x1; xy[3] = y1; xy[4] = x; xy[5] = y;
- n = seg_count(dev_len(r, xy, 3));
- for (i = 1; i <= n; i++) {
- double t = (double)i / n, u = 1 - t;
- add_user(r, u * u * x0 + 2 * u * t * x1 + t * t * x,
- u * u * y0 + 2 * u * t * y1 + t * t * y, 0);
- }
- r->cx = x;
- r->cy = y;
- r->lcx = x1;
- r->lcy = y1;
- }
- static double vec_angle(double ux, double uy, double vx, double vy)
- {
- return atan2(ux * vy - uy * vx, ux * vx + uy * vy);
- }
- /* Endpoint -> center parameterization (SVG 1.1 implementation notes F.6). */
- void svgr_arc(struct svgr *r, double rx, double ry, double rot, int large,
- int sweep, double x, double y)
- {
- double x0 = r->cx, y0 = r->cy;
- double phi, cp, sp, dx2, dy2, x1p, y1p, lam, sq, num, den, coef;
- double cxp, cyp, cx, cy, th1, dth, scale;
- int i, n;
- if (!r->open)
- svgr_move(r, x0, y0);
- if (x0 == x && y0 == y)
- return;
- rx = fabs(rx);
- ry = fabs(ry);
- if (rx == 0 || ry == 0) {
- svgr_line(r, x, y);
- return;
- }
- phi = rot * SVGR_PI / 180.0;
- cp = cos(phi);
- sp = sin(phi);
- dx2 = (x0 - x) / 2;
- dy2 = (y0 - y) / 2;
- x1p = cp * dx2 + sp * dy2;
- y1p = -sp * dx2 + cp * dy2;
- lam = (x1p * x1p) / (rx * rx) + (y1p * y1p) / (ry * ry);
- if (lam > 1) {
- sq = sqrt(lam);
- rx *= sq;
- ry *= sq;
- }
- num = rx * rx * ry * ry - rx * rx * y1p * y1p - ry * ry * x1p * x1p;
- den = rx * rx * y1p * y1p + ry * ry * x1p * x1p;
- coef = (den > 0 && num > 0) ? sqrt(num / den) : 0;
- if (large == sweep)
- coef = -coef;
- cxp = coef * rx * y1p / ry;
- cyp = -coef * ry * x1p / rx;
- cx = cp * cxp - sp * cyp + (x0 + x) / 2;
- cy = sp * cxp + cp * cyp + (y0 + y) / 2;
- th1 = vec_angle(1, 0, (x1p - cxp) / rx, (y1p - cyp) / ry);
- dth = vec_angle((x1p - cxp) / rx, (y1p - cyp) / ry,
- (-x1p - cxp) / rx, (-y1p - cyp) / ry);
- if (!sweep && dth > 0)
- dth -= 2 * SVGR_PI;
- else if (sweep && dth < 0)
- dth += 2 * SVGR_PI;
- scale = sqrt(fabs(r->m[0] * r->m[3] - r->m[1] * r->m[2]));
- n = seg_count(fabs(dth) * (rx > ry ? rx : ry) * scale);
- if (n < 2)
- n = 2;
- for (i = 1; i <= n; i++) {
- double t = th1 + dth * i / n;
- double ex = rx * cos(t), ey = ry * sin(t);
- if (i == n)
- add_user(r, x, y, 0);
- else
- add_user(r, cp * ex - sp * ey + cx,
- sp * ex + cp * ey + cy, 0);
- }
- r->cx = r->lcx = x;
- r->cy = r->lcy = y;
- }
- void svgr_close(struct svgr *r)
- {
- if (r->open && r->sp < r->n)
- r->fl[r->sp] |= SVGR_PT_CLOSED;
- r->open = 0;
- r->cx = r->lcx = r->sx;
- r->cy = r->lcy = r->sy;
- }
- static const char *read_flag(const char *p, int *flag, int *ok)
- {
- p = skip_sep(p);
- if (*p == '0' || *p == '1') {
- *flag = *p - '0';
- *ok = 1;
- return p + 1;
- }
- *ok = 0;
- return p;
- }
- int svgr_path(struct svgr *r, const char *d)
- {
- const char *p = d;
- char cmd = 0;
- r->last = 0;
- while (p && *p) {
- double a[7];
- int fresh = 0, rel, need, i, ok = 1;
- char c;
- p = skip_sep(p);
- if (!*p)
- break;
- if ((*p >= 'A' && *p <= 'Z') || (*p >= 'a' && *p <= 'z')) {
- cmd = *p++;
- fresh = 1;
- } else if (!cmd) {
- return -1;
- }
- rel = cmd >= 'a' && cmd <= 'z';
- c = rel ? (char)(cmd - 'a' + 'A') : cmd;
- if (c == 'Z') {
- if (!fresh)
- return -1;
- svgr_close(r);
- r->last = 'Z';
- continue;
- }
- switch (c) {
- case 'M': case 'L': case 'T': need = 2; break;
- case 'H': case 'V': need = 1; break;
- case 'C': need = 6; break;
- case 'S': case 'Q': need = 4; break;
- case 'A': need = 7; break;
- default: return -1;
- }
- for (i = 0; i < need && ok; i++) {
- if (c == 'A' && (i == 3 || i == 4)) {
- int f = 0;
- p = read_flag(p, &f, &ok);
- a[i] = f;
- } else {
- a[i] = svgr_num(&p, &ok);
- }
- }
- if (!ok)
- return -1;
- if (rel) {
- double ox = r->cx, oy = r->cy;
- switch (c) {
- case 'H': a[0] += ox; break;
- case 'V': a[0] += oy; break;
- case 'A': a[5] += ox; a[6] += oy; break;
- default:
- for (i = 0; i + 1 < need; i += 2) {
- a[i] += ox;
- a[i + 1] += oy;
- }
- }
- }
- switch (c) {
- case 'M':
- if (fresh)
- svgr_move(r, a[0], a[1]);
- else
- svgr_line(r, a[0], a[1]);
- break;
- case 'L':
- svgr_line(r, a[0], a[1]);
- break;
- case 'H':
- svgr_line(r, a[0], r->cy);
- break;
- case 'V':
- svgr_line(r, r->cx, a[0]);
- break;
- case 'C':
- svgr_cubic(r, a[0], a[1], a[2], a[3], a[4], a[5]);
- break;
- case 'S': {
- double x1 = r->cx, y1 = r->cy;
- if (r->last == 'C' || r->last == 'S') {
- x1 = 2 * r->cx - r->lcx;
- y1 = 2 * r->cy - r->lcy;
- }
- svgr_cubic(r, x1, y1, a[0], a[1], a[2], a[3]);
- break;
- }
- case 'Q':
- svgr_quad(r, a[0], a[1], a[2], a[3]);
- break;
- case 'T': {
- double x1 = r->cx, y1 = r->cy;
- if (r->last == 'Q' || r->last == 'T') {
- x1 = 2 * r->cx - r->lcx;
- y1 = 2 * r->cy - r->lcy;
- }
- svgr_quad(r, x1, y1, a[0], a[1]);
- break;
- }
- case 'A':
- svgr_arc(r, a[0], a[1], a[2], (int)a[3], (int)a[4],
- a[5], a[6]);
- break;
- }
- r->last = c;
- /* Extra coordinate pairs after a moveto are linetos. */
- if (c == 'M')
- cmd = rel ? 'l' : 'L';
- }
- return 0;
- }
- void svgr_rect(struct svgr *r, double x, double y, double w, double h,
- double rx, double ry)
- {
- if (w <= 0 || h <= 0)
- return;
- if (rx < 0)
- rx = 0;
- if (ry < 0)
- ry = 0;
- if (rx > w / 2)
- rx = w / 2;
- if (ry > h / 2)
- ry = h / 2;
- if (rx == 0 || ry == 0) {
- svgr_move(r, x, y);
- svgr_line(r, x + w, y);
- svgr_line(r, x + w, y + h);
- svgr_line(r, x, y + h);
- svgr_close(r);
- return;
- }
- svgr_move(r, x + rx, y);
- svgr_line(r, x + w - rx, y);
- svgr_arc(r, rx, ry, 0, 0, 1, x + w, y + ry);
- svgr_line(r, x + w, y + h - ry);
- svgr_arc(r, rx, ry, 0, 0, 1, x + w - rx, y + h);
- svgr_line(r, x + rx, y + h);
- svgr_arc(r, rx, ry, 0, 0, 1, x, y + h - ry);
- svgr_line(r, x, y + ry);
- svgr_arc(r, rx, ry, 0, 0, 1, x + rx, y);
- svgr_close(r);
- }
- void svgr_ellipse(struct svgr *r, double cx, double cy, double rx, double ry)
- {
- if (rx <= 0 || ry <= 0)
- return;
- svgr_move(r, cx + rx, cy);
- svgr_arc(r, rx, ry, 0, 0, 1, cx - rx, cy);
- svgr_arc(r, rx, ry, 0, 0, 1, cx + rx, cy);
- svgr_close(r);
- }
- void svgr_points(struct svgr *r, const char *pts, int close)
- {
- const char *p = pts;
- int first = 1, ok = 1;
- while (p && *p) {
- double x = svgr_num(&p, &ok), y;
- if (!ok)
- break;
- y = svgr_num(&p, &ok);
- if (!ok)
- break;
- if (first)
- svgr_move(r, x, y);
- else
- svgr_line(r, x, y);
- first = 0;
- }
- if (!first && close)
- svgr_close(r);
- }
- /* ---- scanline fill ---- */
- struct edge {
- float x0, y0, x1, y1; /* y0 < y1 */
- float dxdy;
- int dir;
- int next; /* bucket chain */
- };
- struct cross {
- float x;
- int dir;
- };
- static void composite_row(struct svgr_layer *L, int y, const int *cov,
- int x0, int x1, unsigned short color,
- unsigned int alpha)
- {
- unsigned int sr = (color >> 11) & 31, sg = (color >> 5) & 63,
- sb = color & 31;
- int x;
- for (x = x0; x <= x1; x++) {
- int c = cov[x];
- unsigned int sa, da, oa, idx;
- unsigned short d;
- if (c <= 0)
- continue;
- if (c > 256)
- c = 256;
- sa = (unsigned int)c * alpha / 256;
- if (!sa)
- continue;
- idx = (unsigned int)y * (unsigned int)L->w + (unsigned int)x;
- da = L->a[idx];
- if (sa >= 255 || !da) {
- L->px[idx] = color;
- oa = sa + da * (255 - sa) / 255;
- L->a[idx] = (unsigned char)(oa > 255 ? 255 : oa);
- continue;
- }
- d = L->px[idx];
- {
- unsigned int dw = da * (255 - sa) / 255;
- unsigned int r5, g6, b5;
- oa = sa + dw;
- r5 = (sr * sa + ((d >> 11) & 31) * dw) / oa;
- g6 = (sg * sa + ((d >> 5) & 63) * dw) / oa;
- b5 = (sb * sa + (d & 31) * dw) / oa;
- L->px[idx] = (unsigned short)((r5 << 11) | (g6 << 5) |
- b5);
- L->a[idx] = (unsigned char)(oa > 255 ? 255 : oa);
- }
- }
- }
- static void span_add(int *cov, int w, float xa, float xb, int *minx,
- int *maxx)
- {
- int ia, ib, i;
- if (xa < 0)
- xa = 0;
- if (xb > (float)w)
- xb = (float)w;
- if (xb <= xa)
- return;
- ia = (int)xa;
- ib = (int)xb;
- if (ia < *minx)
- *minx = ia;
- if ((ib < w ? ib : w - 1) > *maxx)
- *maxx = ib < w ? ib : w - 1;
- if (ia == ib) {
- cov[ia] += (int)(64.0f * (xb - xa) + 0.5f);
- return;
- }
- cov[ia] += (int)(64.0f * ((float)(ia + 1) - xa) + 0.5f);
- for (i = ia + 1; i < ib; i++)
- cov[i] += 64;
- if (ib < w)
- cov[ib] += (int)(64.0f * (xb - (float)ib) + 0.5f);
- }
- void svgr_fill(struct svgr *r, struct svgr_layer *L, unsigned short color,
- unsigned int alpha, int evenodd)
- {
- struct edge *e;
- struct cross *xs;
- int *head, *active, *cov;
- unsigned int i, ne = 0, start = 0;
- int nact = 0, y, ymin_all = L->h, ymax_all = -1;
- if (r->n < 2 || L->w <= 0 || L->h <= 0 || !alpha)
- return;
- e = (struct edge *)malloc((r->n + 1) * sizeof(*e));
- xs = (struct cross *)malloc((r->n + 1) * sizeof(*xs));
- head = (int *)malloc((unsigned int)L->h * sizeof(int));
- active = (int *)malloc((r->n + 1) * sizeof(int));
- cov = (int *)malloc(((unsigned int)L->w + 1) * sizeof(int));
- if (!e || !xs || !head || !active || !cov)
- goto out;
- for (i = 0; i < (unsigned int)L->h; i++)
- head[i] = -1;
- for (i = 0; i <= (unsigned int)L->w; i++)
- cov[i] = 0;
- /* Edges: consecutive points of each subpath, plus the implicit
- * closing edge (fills always close). */
- for (i = 0; i < r->n; i++) {
- unsigned int j;
- float ax, ay, bx, by;
- if (i + 1 < r->n && !(r->fl[i + 1] & SVGR_PT_START))
- j = i + 1;
- else
- j = start;
- if (i + 1 >= r->n || (r->fl[i + 1] & SVGR_PT_START))
- start = i + 1;
- ax = r->pt[2 * i];
- ay = r->pt[2 * i + 1];
- bx = r->pt[2 * j];
- by = r->pt[2 * j + 1];
- if (ay == by || j == i)
- continue;
- if (ay < by) {
- e[ne].x0 = ax; e[ne].y0 = ay;
- e[ne].x1 = bx; e[ne].y1 = by;
- e[ne].dir = 1;
- } else {
- e[ne].x0 = bx; e[ne].y0 = by;
- e[ne].x1 = ax; e[ne].y1 = ay;
- e[ne].dir = -1;
- }
- if (e[ne].y1 <= 0 || e[ne].y0 >= (float)L->h)
- continue;
- e[ne].dxdy = (e[ne].x1 - e[ne].x0) / (e[ne].y1 - e[ne].y0);
- {
- int row = e[ne].y0 < 0 ? 0 : (int)e[ne].y0;
- int last = (int)e[ne].y1;
- if (row >= L->h)
- continue;
- if (last >= L->h)
- last = L->h - 1;
- if (row < ymin_all)
- ymin_all = row;
- if (last > ymax_all)
- ymax_all = last;
- e[ne].next = head[row];
- head[row] = (int)ne;
- }
- ne++;
- }
- for (y = ymin_all; y <= ymax_all && y < L->h; y++) {
- int k, minx = L->w, maxx = -1, a;
- for (a = head[y]; a >= 0; a = e[a].next)
- active[nact++] = a;
- /* drop finished edges */
- for (k = 0; k < nact;) {
- if (e[active[k]].y1 <= (float)y)
- active[k] = active[--nact];
- else
- k++;
- }
- if (!nact)
- continue;
- for (k = 0; k < 4; k++) {
- float sy = (float)y + ((float)k + 0.5f) * 0.25f;
- int nx = 0, q, wind = 0;
- for (q = 0; q < nact; q++) {
- struct edge *ed = &e[active[q]];
- int t;
- float x;
- if (sy < ed->y0 || sy >= ed->y1)
- continue;
- x = ed->x0 + (sy - ed->y0) * ed->dxdy;
- /* insertion sort by x */
- t = nx++;
- while (t > 0 && xs[t - 1].x > x) {
- xs[t] = xs[t - 1];
- t--;
- }
- xs[t].x = x;
- xs[t].dir = ed->dir;
- }
- for (q = 0; q + 1 < nx; q++) {
- int inside;
- wind += xs[q].dir;
- inside = evenodd ? (wind & 1) : wind != 0;
- if (inside)
- span_add(cov, L->w, xs[q].x,
- xs[q + 1].x, &minx, &maxx);
- }
- }
- if (maxx >= minx) {
- composite_row(L, y, cov, minx, maxx, color, alpha);
- for (k = minx; k <= maxx; k++)
- cov[k] = 0;
- }
- }
- out:
- free(e);
- free(xs);
- free(head);
- free(active);
- free(cov);
- }
- /* Strokes become filled geometry: one quad per segment, all with the same
- * winding, plus an octagon at each joint, filled with the nonzero rule so
- * the overlaps union. */
- void svgr_stroke(struct svgr *r, struct svgr_layer *L, double width,
- unsigned short color, unsigned int alpha)
- {
- struct svgr s;
- unsigned int i, start = 0, cap;
- double hw = width / 2;
- void *buf;
- int joins = width > 1.5;
- if (r->n < 2 || width <= 0)
- return;
- if (hw < 0.35)
- hw = 0.35;
- cap = r->n * (joins ? 12 : 4) + 16;
- buf = malloc(cap * (2 * sizeof(float) + 1));
- if (!buf)
- return;
- svgr_init(&s, buf, cap);
- for (i = 0; i < r->n; i++) {
- unsigned int j;
- int closing = 0;
- double ax, ay, bx, by, dx, dy, len, nx, ny;
- if (r->fl[i] & SVGR_PT_START)
- start = i;
- if (i + 1 < r->n && !(r->fl[i + 1] & SVGR_PT_START)) {
- j = i + 1;
- } else {
- if (!(r->fl[start] & SVGR_PT_CLOSED))
- continue;
- j = start;
- closing = 1;
- }
- (void)closing;
- ax = r->pt[2 * i];
- ay = r->pt[2 * i + 1];
- bx = r->pt[2 * j];
- by = r->pt[2 * j + 1];
- dx = bx - ax;
- dy = by - ay;
- len = sqrt(dx * dx + dy * dy);
- if (len < 1e-6)
- continue;
- nx = -dy / len * hw;
- ny = dx / len * hw;
- add_dev(&s, ax + nx, ay + ny, SVGR_PT_START);
- add_dev(&s, bx + nx, by + ny, 0);
- add_dev(&s, bx - nx, by - ny, 0);
- add_dev(&s, ax - nx, ay - ny, 0);
- if (joins) {
- /* The quad above runs clockwise in device space
- * (y down) for every direction; draw the octagon in
- * the same sense. */
- int k;
- double sgn = (nx * dy - ny * dx) > 0 ? 1 : -1;
- for (k = 0; k < 8; k++) {
- double ang = sgn * k * SVGR_PI / 4;
- add_dev(&s, bx + hw * cos(ang),
- by + hw * sin(ang),
- k ? 0 : SVGR_PT_START);
- }
- }
- }
- svgr_fill(&s, L, color, alpha, 0);
- free(buf);
- }
|