Viewing is open to everyone. Downloading and starring need a GitHub sign-in.
Sign in with GitHub
svg_raster.h
v0.1.0-build.85
Latest
Commit ede38f5
Sign in with GitHub to download. Each download is recorded with your GitHub username.
| 1 | // Reference rasterizer (header-only, no dependencies) for the SVG subset |
| 2 | // emitted by CKey's renderers. Used by the tests and by the CLI's print |
| 3 | // sheets, so both rasterize exactly what the renderer emits: <g> |
| 4 | // with translate/scale transforms and inherited fill/stroke/linecap/class, |
| 5 | // <rect> (filled or stroked, rounded), <circle>, <polygon>, and stroked |
| 6 | // <path> made of M/L/A commands. Styled output: <defs> are skipped, gradient |
| 7 | // fills count as ink, full-canvas rects are background, <image> is not |
| 8 | // drawn, and the "ckey-logo-plate" layer erases (painter's order). It consumes the rendered SVG text, not the encoder's |
| 9 | // internal geometry, so round-trip tests check what is actually printed. |
| 10 | |
| 11 | |
| 12 | |
| 13 | <algorithm> |
| 14 | <cmath> |
| 15 | <cstdint> |
| 16 | <limits> |
| 17 | <map> |
| 18 | <sstream> |
| 19 | <string> |
| 20 | <vector> |
| 21 | |
| 22 | namespace svgtest { |
| 23 | |
| 24 | constexpr double kPi = 3.14159265358979323846; |
| 25 | |
| 26 | struct Affine { double sx = 1, sy = 1, tx = 0, ty = 0; }; // parent = s * local + t |
| 27 | |
| 28 | struct Segment { |
| 29 | bool arc = false; |
| 30 | double x0 = 0, y0 = 0, x1 = 0, y1 = 0; // endpoints |
| 31 | double cx = 0, cy = 0, r = 0, theta = 0, sweep = 0; // arc parameterization |
| 32 | }; |
| 33 | |
| 34 | struct Prim { |
| 35 | enum Kind { FillRect, StrokeRect, Circle, Stroke, Polygon } kind = FillRect; |
| 36 | std::string layer; |
| 37 | bool erase = false; |
| 38 | std::vector<std::pair<double, double>> points; // polygon vertices |
| 39 | Affine xf; |
| 40 | double x = 0, y = 0, w = 0, h = 0, rx = 0; // rects; circle uses x,y,rx |
| 41 | double half_width = 0; bool round_cap = false; |
| 42 | std::vector<Segment> segments; |
| 43 | double bx0 = 0, by0 = 0, bx1 = 0, by1 = 0; // bounding box in user space |
| 44 | }; |
| 45 | |
| 46 | struct Svg { double vx = 0, vy = 0, vw = 1, vh = 1; std::vector<Prim> prims; }; |
| 47 | |
| 48 | inline std::map<std::string, std::string> attributes(const std::string &tag) { |
| 49 | std::map<std::string, std::string> out; |
| 50 | size_t i = 0; |
| 51 | while ((i = tag.find('=', i)) != std::string::npos) { |
| 52 | size_t k = i; while (k > 0 && tag[k - 1] != ' ') --k; |
| 53 | const std::string key = tag.substr(k, i - k); |
| 54 | const size_t q0 = tag.find('"', i), q1 = tag.find('"', q0 + 1); |
| 55 | out[key] = tag.substr(q0 + 1, q1 - q0 - 1); |
| 56 | i = q1 + 1; |
| 57 | } |
| 58 | return out; |
| 59 | } |
| 60 | |
| 61 | inline double sdf_round_rect(double px, double py, double x, double y, double w, double h, double r) { |
| 62 | const double cx = x + w / 2, cy = y + h / 2; |
| 63 | const double qx = std::abs(px - cx) - (w / 2 - r), qy = std::abs(py - cy) - (h / 2 - r); |
| 64 | return std::hypot(std::max(qx, 0.0), std::max(qy, 0.0)) + std::min(std::max(qx, qy), 0.0) - r; |
| 65 | } |
| 66 | |
| 67 | inline double angle_offset(double a, double from, double sweep) { |
| 68 | double d = a - from; |
| 69 | if (sweep >= 0) { while (d < 0) d += 2 * kPi; while (d >= 2 * kPi) d -= 2 * kPi; } |
| 70 | else { while (d > 0) d -= 2 * kPi; while (d <= -2 * kPi) d += 2 * kPi; } |
| 71 | return d; |
| 72 | } |
| 73 | |
| 74 | // Ink test for a stroked segment: distance <= half_width, honoring caps. |
| 75 | inline bool stroke_hit(const Segment &s, double px, double py, double hw, bool round_cap) { |
| 76 | if (!s.arc) { |
| 77 | const double vx = s.x1 - s.x0, vy = s.y1 - s.y0, len2 = vx * vx + vy * vy; |
| 78 | const double t = len2 > 0 ? ((px - s.x0) * vx + (py - s.y0) * vy) / len2 : 0; |
| 79 | if (!round_cap && (t < 0 || t > 1)) return false; |
| 80 | const double c = std::clamp(t, 0.0, 1.0); |
| 81 | return std::hypot(s.x0 + c * vx - px, s.y0 + c * vy - py) <= hw; |
| 82 | } |
| 83 | const double d = angle_offset(std::atan2(py - s.cy, px - s.cx), s.theta, s.sweep); |
| 84 | if (std::abs(d) <= std::abs(s.sweep)) return std::abs(std::hypot(px - s.cx, py - s.cy) - s.r) <= hw; |
| 85 | if (!round_cap) return false; |
| 86 | return std::hypot(px - s.x0, py - s.y0) <= hw || std::hypot(px - s.x1, py - s.y1) <= hw; |
| 87 | } |
| 88 | |
| 89 | inline bool prim_hit(const Prim &p, double ux, double uy) { |
| 90 | const double x = (ux - p.xf.tx) / p.xf.sx, y = (uy - p.xf.ty) / p.xf.sy; |
| 91 | switch (p.kind) { |
| 92 | case Prim::FillRect: return sdf_round_rect(x, y, p.x, p.y, p.w, p.h, std::min(p.rx, std::min(p.w, p.h) / 2)) <= 0; |
| 93 | case Prim::StrokeRect: return std::abs(sdf_round_rect(x, y, p.x, p.y, p.w, p.h, p.rx)) <= p.half_width; |
| 94 | case Prim::Circle: return std::hypot(x - p.x, y - p.y) <= p.rx; |
| 95 | case Prim::Stroke: |
| 96 | for (const auto &s : p.segments) if (stroke_hit(s, x, y, p.half_width, p.round_cap)) return true; |
| 97 | return false; |
| 98 | case Prim::Polygon: { |
| 99 | bool inside = false; |
| 100 | for (size_t i = 0, j = p.points.size() - 1; i < p.points.size(); j = i++) { |
| 101 | const auto &a = p.points[i], &b = p.points[j]; |
| 102 | if ((a.second > y) != (b.second > y) && x < (b.first - a.first) * (y - a.second) / (b.second - a.second) + a.first) inside = !inside; |
| 103 | } |
| 104 | return inside; |
| 105 | } |
| 106 | } |
| 107 | return false; |
| 108 | } |
| 109 | |
| 110 | inline void finish_bbox(Prim &p) { |
| 111 | double x0 = 1e300, y0 = 1e300, x1 = -1e300, y1 = -1e300; |
| 112 | const auto add = [&](double x, double y, double pad) { x0 = std::min(x0, x - pad); y0 = std::min(y0, y - pad); x1 = std::max(x1, x + pad); y1 = std::max(y1, y + pad); }; |
| 113 | if (p.kind == Prim::FillRect || p.kind == Prim::StrokeRect) { add(p.x, p.y, p.half_width); add(p.x + p.w, p.y + p.h, p.half_width); } |
| 114 | else if (p.kind == Prim::Circle) add(p.x, p.y, p.rx); |
| 115 | else if (p.kind == Prim::Polygon) for (const auto &[x, y] : p.points) add(x, y, 0); |
| 116 | else for (const auto &s : p.segments) { |
| 117 | if (s.arc) { |
| 118 | // Tight bound: the sweep's endpoints plus every axis extreme it crosses. |
| 119 | add(s.x0, s.y0, p.half_width); add(s.x1, s.y1, p.half_width); |
| 120 | for (int q = -8; q <= 8; ++q) { |
| 121 | const double a = q * kPi / 2; |
| 122 | if (std::abs(angle_offset(a, s.theta, s.sweep)) <= std::abs(s.sweep)) |
| 123 | add(s.cx + s.r * std::cos(a), s.cy + s.r * std::sin(a), p.half_width); |
| 124 | } |
| 125 | } |
| 126 | else { add(s.x0, s.y0, p.half_width); add(s.x1, s.y1, p.half_width); } |
| 127 | } |
| 128 | const double ax = p.xf.sx * x0 + p.xf.tx, bx = p.xf.sx * x1 + p.xf.tx; |
| 129 | const double ay = p.xf.sy * y0 + p.xf.ty, by = p.xf.sy * y1 + p.xf.ty; |
| 130 | p.bx0 = std::min(ax, bx); p.bx1 = std::max(ax, bx); p.by0 = std::min(ay, by); p.by1 = std::max(ay, by); |
| 131 | } |
| 132 | |
| 133 | // SVG 1.1 F.6.5 endpoint-to-center conversion for a circular arc (rx = ry, no rotation). |
| 134 | inline Segment make_arc(double x0, double y0, double r, bool large, bool sweep, double x1, double y1) { |
| 135 | Segment s; s.arc = true; s.x0 = x0; s.y0 = y0; s.x1 = x1; s.y1 = y1; |
| 136 | const double hx = (x0 - x1) / 2, hy = (y0 - y1) / 2, d2 = hx * hx + hy * hy; |
| 137 | if (d2 > r * r) r = std::sqrt(d2); |
| 138 | const double coef = (large != sweep ? 1.0 : -1.0) * std::sqrt(std::max(0.0, (r * r - d2) / d2)); |
| 139 | const double cxp = coef * hy, cyp = -coef * hx; |
| 140 | s.cx = cxp + (x0 + x1) / 2; s.cy = cyp + (y0 + y1) / 2; s.r = r; |
| 141 | s.theta = std::atan2(hy - cyp, hx - cxp); |
| 142 | const double end = std::atan2(-hy - cyp, -hx - cxp); |
| 143 | double delta = end - s.theta; |
| 144 | if (sweep && delta < 0) delta += 2 * kPi; |
| 145 | if (!sweep && delta > 0) delta -= 2 * kPi; |
| 146 | s.sweep = delta; |
| 147 | return s; |
| 148 | } |
| 149 | |
| 150 | inline Svg parse(const std::string &text) { |
| 151 | Svg svg; |
| 152 | struct Ctx { Affine xf; std::string fill, stroke, cap, layer; }; |
| 153 | std::vector<Ctx> stack{{}}; |
| 154 | size_t i = 0; |
| 155 | while ((i = text.find('<', i)) != std::string::npos) { |
| 156 | const size_t j = text.find('>', i); |
| 157 | std::string tag = text.substr(i + 1, j - i - 1); |
| 158 | i = j + 1; |
| 159 | if (tag.rfind("defs", 0) == 0) { const size_t end = text.find("</defs>", i); i = end == std::string::npos ? text.size() : end + 7; continue; } |
| 160 | if (tag.rfind("/g", 0) == 0) { stack.pop_back(); continue; } |
| 161 | if (tag[0] == '/') continue; |
| 162 | const bool self_close = !tag.empty() && tag.back() == '/'; |
| 163 | const std::string name = tag.substr(0, tag.find_first_of(" /")); |
| 164 | auto a = attributes(tag); |
| 165 | Ctx ctx = stack.back(); |
| 166 | if (a.count("fill")) ctx.fill = a["fill"]; |
| 167 | if (a.count("stroke")) ctx.stroke = a["stroke"]; |
| 168 | if (a.count("stroke-linecap")) ctx.cap = a["stroke-linecap"]; |
| 169 | if (a.count("class")) ctx.layer = a["class"]; |
| 170 | if (name == "svg") { |
| 171 | std::istringstream v(a["viewBox"]); v >> svg.vx >> svg.vy >> svg.vw >> svg.vh; |
| 172 | continue; |
| 173 | } |
| 174 | if (name == "g") { |
| 175 | const std::string t = a["transform"]; |
| 176 | if (!t.empty()) { |
| 177 | double tx = 0, ty = 0, sx = 1, sy = 1; |
| 178 | const size_t tp = t.find("translate("), sp = t.find("scale("); |
| 179 | if (tp != std::string::npos) std::sscanf(t.c_str() + tp, "translate(%lf %lf)", &tx, &ty); |
| 180 | if (sp != std::string::npos) std::sscanf(t.c_str() + sp, "scale(%lf %lf)", &sx, &sy); |
| 181 | // child = parent_xf( translate( scale(p) ) ) |
| 182 | const Affine &q = stack.back().xf; |
| 183 | ctx.xf = {q.sx * sx, q.sy * sy, q.sx * tx + q.tx, q.sy * ty + q.ty}; |
| 184 | } |
| 185 | if (!self_close) stack.push_back(ctx); |
| 186 | continue; |
| 187 | } |
| 188 | if (ctx.fill == "#050505") continue; // background, not ink |
| 189 | Prim p; p.layer = ctx.layer; p.xf = ctx.xf; p.erase = ctx.layer == "ckey-logo-plate"; |
| 190 | if (name == "rect" && std::stod(a["x"]) == svg.vx && std::stod(a["width"]) == svg.vw) continue; // background / texture |
| 191 | if (name == "polygon") { |
| 192 | p.kind = Prim::Polygon; |
| 193 | std::string pts = a["points"]; for (char &ch : pts) if (ch == ',') ch = ' '; |
| 194 | std::istringstream in(pts); double px, py; while (in >> px >> py) p.points.push_back({px, py}); |
| 195 | } else if (name == "rect") { |
| 196 | p.x = std::stod(a["x"]); p.y = std::stod(a["y"]); p.w = std::stod(a["width"]); p.h = std::stod(a["height"]); |
| 197 | p.rx = a.count("rx") ? std::stod(a["rx"]) : 0.0; |
| 198 | if (ctx.fill == "none") { p.kind = Prim::StrokeRect; p.half_width = std::stod(a["stroke-width"]) / 2; } |
| 199 | else p.kind = Prim::FillRect; |
| 200 | } else if (name == "circle") { |
| 201 | p.kind = Prim::Circle; p.x = std::stod(a["cx"]); p.y = std::stod(a["cy"]); p.rx = std::stod(a["r"]); |
| 202 | } else if (name == "path") { |
| 203 | p.kind = Prim::Stroke; p.half_width = std::stod(a["stroke-width"]) / 2; p.round_cap = ctx.cap == "round"; |
| 204 | std::istringstream d(a["d"]); std::string cmd; double cx = 0, cy = 0; |
| 205 | while (d >> cmd) { |
| 206 | if (cmd == "M") d >> cx >> cy; |
| 207 | else if (cmd == "L") { Segment s; s.x0 = cx; s.y0 = cy; d >> s.x1 >> s.y1; cx = s.x1; cy = s.y1; p.segments.push_back(s); } |
| 208 | else if (cmd == "A") { |
| 209 | double r, ry, rot, x1, y1; int large, sweep; d >> r >> ry >> rot >> large >> sweep >> x1 >> y1; |
| 210 | p.segments.push_back(make_arc(cx, cy, r, large != 0, sweep != 0, x1, y1)); cx = x1; cy = y1; |
| 211 | } |
| 212 | } |
| 213 | } else continue; |
| 214 | finish_bbox(p); |
| 215 | svg.prims.push_back(p); |
| 216 | } |
| 217 | return svg; |
| 218 | } |
| 219 | |
| 220 | // Antialiased grayscale raster (ss x ss supersampling). Pixels map the |
| 221 | // viewBox onto width x height. layer_prefix filters primitives by class. |
| 222 | inline std::vector<uint8_t> rasterize(const Svg &svg, int width, int height, int ss = 4, |
| 223 | uint8_t background = 5, uint8_t ink = 241, |
| 224 | const std::string &layer_prefix = "") { |
| 225 | const int W = width * ss, H = height * ss; |
| 226 | std::vector<uint8_t> hit(static_cast<size_t>(W) * H, 0); |
| 227 | const double kx = svg.vw / W, ky = svg.vh / H; |
| 228 | for (const auto &p : svg.prims) { |
| 229 | if (!layer_prefix.empty() && p.layer.rfind(layer_prefix, 0) != 0) continue; |
| 230 | const int x0 = std::max(0, static_cast<int>(std::floor((p.bx0 - svg.vx) / kx)) - 1); |
| 231 | const int x1 = std::min(W - 1, static_cast<int>(std::ceil((p.bx1 - svg.vx) / kx)) + 1); |
| 232 | const int y0 = std::max(0, static_cast<int>(std::floor((p.by0 - svg.vy) / ky)) - 1); |
| 233 | const int y1 = std::min(H - 1, static_cast<int>(std::ceil((p.by1 - svg.vy) / ky)) + 1); |
| 234 | for (int y = y0; y <= y1; ++y) for (int x = x0; x <= x1; ++x) { |
| 235 | uint8_t &cell = hit[static_cast<size_t>(y) * W + x]; |
| 236 | if (p.erase) { if (cell && prim_hit(p, svg.vx + (x + .5) * kx, svg.vy + (y + .5) * ky)) cell = 0; } |
| 237 | else if (!cell && prim_hit(p, svg.vx + (x + .5) * kx, svg.vy + (y + .5) * ky)) cell = 1; |
| 238 | } |
| 239 | } |
| 240 | std::vector<uint8_t> out(static_cast<size_t>(width) * height); |
| 241 | for (int y = 0; y < height; ++y) for (int x = 0; x < width; ++x) { |
| 242 | int count = 0; |
| 243 | for (int sy = 0; sy < ss; ++sy) for (int sx = 0; sx < ss; ++sx) count += hit[static_cast<size_t>(y * ss + sy) * W + x * ss + sx]; |
| 244 | out[static_cast<size_t>(y) * width + x] = static_cast<uint8_t>(background + (ink - background) * count / (ss * ss)); |
| 245 | } |
| 246 | return out; |
| 247 | } |
| 248 | |
| 249 | // Exact squared Euclidean distance transform (Felzenszwalb-Huttenlocher) of |
| 250 | // a binary mask: distance in pixels from each pixel to the nearest set pixel. |
| 251 | inline std::vector<double> distance_to_set(const std::vector<uint8_t> &mask, int width, int height) { |
| 252 | const double inf = 1e20; |
| 253 | std::vector<double> f(static_cast<size_t>(width) * height); |
| 254 | for (size_t i = 0; i < f.size(); ++i) f[i] = mask[i] ? 0.0 : inf; |
| 255 | const auto pass = [&](std::vector<double> &line) { |
| 256 | const int n = static_cast<int>(line.size()); |
| 257 | std::vector<double> d(n), z(n + 1); std::vector<int> v(n); |
| 258 | int k = 0; v[0] = 0; z[0] = -inf; z[1] = inf; |
| 259 | for (int q = 1; q < n; ++q) { |
| 260 | double s; |
| 261 | while (true) { |
| 262 | s = ((line[q] + q * 1.0 * q) - (line[v[k]] + v[k] * 1.0 * v[k])) / (2.0 * q - 2.0 * v[k]); |
| 263 | if (s <= z[k] && k > 0) --k; else break; |
| 264 | } |
| 265 | if (s <= z[k]) { v[0] = q; z[0] = -inf; z[1] = inf; k = 0; continue; } |
| 266 | ++k; v[k] = q; z[k] = s; z[k + 1] = inf; |
| 267 | } |
| 268 | k = 0; |
| 269 | for (int q = 0; q < n; ++q) { while (z[k + 1] < q) ++k; d[q] = (q - v[k]) * 1.0 * (q - v[k]) + line[v[k]]; } |
| 270 | line = d; |
| 271 | }; |
| 272 | std::vector<double> line; |
| 273 | for (int x = 0; x < width; ++x) { |
| 274 | line.resize(height); for (int y = 0; y < height; ++y) line[y] = f[static_cast<size_t>(y) * width + x]; |
| 275 | pass(line); for (int y = 0; y < height; ++y) f[static_cast<size_t>(y) * width + x] = line[y]; |
| 276 | } |
| 277 | for (int y = 0; y < height; ++y) { |
| 278 | line.assign(f.begin() + static_cast<std::ptrdiff_t>(y) * width, f.begin() + static_cast<std::ptrdiff_t>(y + 1) * width); |
| 279 | pass(line); std::copy(line.begin(), line.end(), f.begin() + static_cast<std::ptrdiff_t>(y) * width); |
| 280 | } |
| 281 | for (double &value : f) value = std::sqrt(value); |
| 282 | return f; |
| 283 | } |
| 284 | |
| 285 | } // namespace svgtest |
| 286 |