/* svg_raster: SVG geometry flattening + antialiased scanline fill. * See svg_raster.h. */ #include "svg_raster.h" #include #include #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); }