diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/svg_color.cpp | 125 | ||||
| -rw-r--r-- | src/svg_color.h | 59 | ||||
| -rw-r--r-- | src/svg_doc.cpp | 462 | ||||
| -rw-r--r-- | src/svg_doc.h | 97 | ||||
| -rw-r--r-- | src/svg_geom.cpp | 181 | ||||
| -rw-r--r-- | src/svg_geom.h | 44 | ||||
| -rw-r--r-- | src/svg_import_defs.h | 49 | ||||
| -rw-r--r-- | src/svg_import_util.cpp | 129 | ||||
| -rw-r--r-- | src/svg_import_util.h | 69 | ||||
| -rw-r--r-- | src/svg_path.cpp | 219 | ||||
| -rw-r--r-- | src/svg_path.h | 38 | ||||
| -rw-r--r-- | src/svg_pattern.cpp | 119 | ||||
| -rw-r--r-- | src/svg_pattern.h | 60 | ||||
| -rw-r--r-- | src/vec_core.cpp | 339 | ||||
| -rw-r--r-- | src/vec_core.h | 37 | ||||
| -rw-r--r-- | src/vec_grid.cpp | 105 | ||||
| -rw-r--r-- | src/vec_grid.h | 52 |
17 files changed, 2184 insertions, 0 deletions
diff --git a/src/svg_color.cpp b/src/svg_color.cpp new file mode 100644 index 0000000..acd793d --- /dev/null +++ b/src/svg_color.cpp @@ -0,0 +1,125 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2021 Jan Sebastian Götte <kicad@jaseg.de> + * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#include "svg_color.h" + +#include <assert.h> +#include <string> +#include <cmath> + +using namespace svg_plugin; +using namespace std; + +/* Map an SVG fill or stroke definition (color, but may also be a pattern) to a gerber color. + * + * This function handles transparency: Transparent SVG colors are mapped such that no gerber output is generated for + * them. + */ +enum gerber_color svg_plugin::svg_color_to_gerber(string color, string opacity, enum gerber_color default_val) { + float alpha = 1.0; + if (!opacity.empty() && opacity[0] != '\0') { + char *endptr = nullptr; + alpha = strtof(opacity.data(), &endptr); + assert(endptr); + assert(*endptr == '\0'); + } + + if (alpha < 0.5f) { + return GRB_NONE; + } + + if (color.empty()) { + return default_val; + } + + if (color == "none") { + return GRB_NONE; + } + + if (color.rfind("url(#", 0) != string::npos) { + return GRB_PATTERN_FILL; + } + + if (color.length() == 7 && color[0] == '#') { + HSVColor hsv(color); + if (hsv.v >= 0.5) { + return GRB_CLEAR; + } + } + + return GRB_DARK; +} + +svg_plugin::RGBColor::RGBColor(string hex) { + assert(hex[0] == '#'); + char *endptr = nullptr; + const char *c = hex.data(); + int rgb = strtol(c + 1, &endptr, 16); + assert(endptr); + assert(endptr == c + 7); + assert(*endptr == '\0'); + r = ((rgb >> 16) & 0xff) / 255.0f; + g = ((rgb >> 8) & 0xff) / 255.0f; + b = ((rgb >> 0) & 0xff) / 255.0f; +}; + +svg_plugin::HSVColor::HSVColor(const RGBColor &color) { + float xmax = fmax(color.r, fmax(color.g, color.b)); + float xmin = fmin(color.r, fmin(color.g, color.b)); + float c = xmax - xmin; + + v = xmax; + + if (c == 0) + h = 0; + else if (v == color.r) + h = 1/3 * (0 + (color.g - color.b) / c); + else if (v == color.g) + h = 1/3 * (2 + (color.b - color.r) / c); + else // v == color.b + h = 1/3 * (4 + (color.r - color.g) / c); + + s = (v == 0) ? 0 : (c/v); +} + +/* Invert gerber color */ +enum gerber_color svg_plugin::gerber_color_invert(enum gerber_color color) { + switch (color) { + case GRB_CLEAR: return GRB_DARK; + case GRB_DARK: return GRB_CLEAR; + default: return color; /* none, pattern */ + } +} + +/* Read node's fill attribute and convert it to a gerber color */ +enum gerber_color svg_plugin::gerber_fill_color(const pugi::xml_node &node) { + return svg_color_to_gerber(node.attribute("fill").value(), node.attribute("fill-opacity").value(), GRB_DARK); +} + +/* Read node's stroke attribute and convert it to a gerber color */ +enum gerber_color svg_plugin::gerber_stroke_color(const pugi::xml_node &node) { + return svg_color_to_gerber(node.attribute("stroke").value(), node.attribute("stroke-opacity").value(), GRB_NONE); +} + + diff --git a/src/svg_color.h b/src/svg_color.h new file mode 100644 index 0000000..5183dab --- /dev/null +++ b/src/svg_color.h @@ -0,0 +1,59 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2021 Jan Sebastian Götte <kicad@jaseg.de> + * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#ifndef SVG_COLOR_H +#define SVG_COLOR_H + +#include <pugixml.hpp> + +namespace svg_plugin { + +/* Enum that describes the color with which an SVG primite should be exported */ +enum gerber_color { + GRB_NONE = 0, + GRB_CLEAR, + GRB_DARK, + GRB_PATTERN_FILL, +}; + +class RGBColor { +public: + float r, g, b; + RGBColor(std::string hex); +}; + +class HSVColor { +public: + float h, s, v; + HSVColor(const RGBColor &color); +}; + +enum gerber_color svg_color_to_gerber(std::string color, std::string opacity, enum gerber_color default_val); +enum gerber_color gerber_color_invert(enum gerber_color color); +enum gerber_color gerber_fill_color(const pugi::xml_node &node); +enum gerber_color gerber_stroke_color(const pugi::xml_node &node); + +} /* namespace svg_plugin */ + +#endif /* SVG_COLOR_H */ diff --git a/src/svg_doc.cpp b/src/svg_doc.cpp new file mode 100644 index 0000000..2543146 --- /dev/null +++ b/src/svg_doc.cpp @@ -0,0 +1,462 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2021 Jan Sebastian Götte <kicad@jaseg.de> + * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#include "svg_import_defs.h" +#include "svg_doc.h" +#include "svg_color.h" +#include "svg_geom.h" +#include "svg_path.h" +#include "vec_core.h" + +using namespace svg_plugin; +using namespace std; +using namespace ClipperLib; +using namespace vectorizer; + +svg_plugin::SVGDocument::~SVGDocument() { + if (cr) + cairo_destroy (cr); + if (surface) + cairo_surface_destroy (surface); +} + +bool svg_plugin::SVGDocument::load(string filename, string debug_out_filename) { + /* Load XML document */ + auto res = svg_doc.load_file(filename.c_str()); + if (!res) { + cerr << "Cannot open input file \"" << filename << "\": " << res << endl; + return false; + } + + root_elem = svg_doc.child("svg"); + if (!root_elem) { + cerr << "Cannot load input file \"" << filename << endl; + return false; + } + + /* Set up the document's viewport transform */ + istringstream vb_stream(root_elem.attribute("viewBox").value()); + vb_stream >> vb_x >> vb_y >> vb_w >> vb_h; + cerr << "loaded viewbox: " << vb_x << ", " << vb_y << ", " << vb_w << ", " << vb_h << endl; + + page_w = usvg_double_attr(root_elem, "width"); + page_h = usvg_double_attr(root_elem, "height"); + /* usvg resolves all units, but instead of outputting some reasonable absolute length like mm, it converts + * everything to px, which depends on usvg's DPI setting (--dpi). + */ + page_w_mm = page_w / assumed_usvg_dpi * 25.4; + page_h_mm = page_h / assumed_usvg_dpi * 25.4; + if (!(page_w_mm > 0.0 && page_h_mm > 0.0 && page_w_mm < 10e3 && page_h_mm < 10e3)) { + cerr << "Warning: Page has zero or negative size, or is larger than 10 x 10 meters! Parsed size: " << page_w << " x " << page_h << " millimeter" << endl; + } + + if (fabs((vb_w / page_w) / (vb_h / page_h) - 1.0) > 0.001) { + cerr << "Warning: Document has different document unit scale in x and y direction! Output will likely be garbage!" << endl; + } + + /* Get the one document defs element */ + defs_node = root_elem.child("defs"); + if (!defs_node) { + cerr << "Warning: Input file is missing <defs> node" << endl; + } + + setup_debug_output(debug_out_filename); + setup_viewport_clip(); + load_clips(); + load_patterns(); + + _valid = true; + return true; +} + +const Paths *svg_plugin::SVGDocument::lookup_clip_path(const pugi::xml_node &node) { + string id(usvg_id_url(node.attribute("clip-path").value())); + if (id.empty() || !clip_path_map.contains(id)) { + return nullptr; + } + return &clip_path_map[id]; +} + +Pattern *svg_plugin::SVGDocument::lookup_pattern(const string id) { + if (id.empty() || !pattern_map.contains(id)) { + return nullptr; + } + return &pattern_map[id]; +}; + +/* Used to convert mm values from configuration such as the minimum feature size into document units. */ +double svg_plugin::SVGDocument::mm_to_doc_units(double mm) const { + return mm * (vb_w / page_w_mm); +} + +double svg_plugin::SVGDocument::doc_units_to_mm(double px) const { + return px / (vb_w / page_w_mm); +} + +/* Recursively export all SVG elements in the given group. */ +void svg_plugin::SVGDocument::export_svg_group(const pugi::xml_node &group, Paths &parent_clip_path) { + /* Enter the group's coordinate system */ + cairo_save(cr); + apply_cairo_transform_from_svg(cr, group.attribute("transform").value()); + + /* Fetch clip path from global registry and transform it into document coordinates. */ + Paths clip_path; + auto *lookup = lookup_clip_path(group); + if (!lookup) { + string id(usvg_id_url(group.attribute("clip-path").value())); + if (!id.empty()) { + cerr << "Warning: Cannot find clip path with ID \"" << group.attribute("clip-path").value() << "\" for group \"" << group.attribute("id").value() << "\"." << endl; + } + + } else { + clip_path = *lookup; + } + transform_paths(cr, clip_path); + + /* Clip against parent's clip path (both are now in document coordinates) */ + if (!parent_clip_path.empty()) { + if (!clip_path.empty()) { + cerr << "Combining clip paths" << endl; + combine_clip_paths(parent_clip_path, clip_path, clip_path); + } else { + cerr << "using parent clip path" << endl; + clip_path = parent_clip_path; + } + } + + ClipperLib::Clipper c2; + c2.AddPaths(clip_path, ptSubject, /* closed */ true); + ClipperLib::IntRect bbox = c2.GetBounds(); + cerr << "clip path is now: bbox={" << bbox.left << ", " << bbox.top << "} - {" << bbox.right << ", " << bbox.bottom << "}" << endl; + + /* Iterate over the group's children, exporting them one by one. */ + for (const auto &node : group.children()) { + string name(node.name()); + if (name == "g") { + export_svg_group(node, clip_path); + + } else if (name == "path") { + export_svg_path(node, clip_path); + + } else if (name == "image") { + double min_feature_size_mm = 0.1; /* TODO make configurable */ + double min_feature_size_px = mm_to_doc_units(min_feature_size_mm); + vectorize_image(cr, node, min_feature_size_px, clip_path, viewport_matrix); + } else if (name == "defs") { + /* ignore */ + } else { + cerr << " Unexpected child: <" << node.name() << ">" << endl; + } + } + + cairo_restore(cr); +} + +/* Export an SVG path element to gerber. Apply patterns and clip on the fly. */ +void svg_plugin::SVGDocument::export_svg_path(const pugi::xml_node &node, Paths &clip_path) { + enum gerber_color fill_color = gerber_fill_color(node); + enum gerber_color stroke_color = gerber_stroke_color(node); + + double stroke_width = usvg_double_attr(node, "stroke-width", /* default */ 1.0); + assert(stroke_width > 0.0); + enum ClipperLib::EndType end_type = clipper_end_type(node); + enum ClipperLib::JoinType join_type = clipper_join_type(node); + vector<double> dasharray; + parse_dasharray(node, dasharray); + /* TODO add stroke-miterlimit */ + + if (!fill_color && !stroke_color) { /* Ignore "transparent" paths */ + return; + } + + /* Load path from SVG path data and transform into document units. */ + PolyTree ptree; + cairo_save(cr); + apply_cairo_transform_from_svg(cr, node.attribute("transform").value()); + load_svg_path(cr, node, ptree); + cairo_restore (cr); + + Paths open_paths, closed_paths; + OpenPathsFromPolyTree(ptree, open_paths); + ClosedPathsFromPolyTree(ptree, closed_paths); + + /* Skip filling for transparent fills */ + if (fill_color) { + /* Clip paths. Consider all paths closed for filling. */ + if (!clip_path.empty()) { + Clipper c; + c.AddPaths(open_paths, ptSubject, /* closed */ false); + c.AddPaths(closed_paths, ptSubject, /* closed */ true); + c.AddPaths(clip_path, ptClip, /* closed */ true); + c.StrictlySimple(true); + /* fill rules are nonzero since both subject and clip have already been normalized by clipper. */ + c.Execute(ctIntersection, ptree, pftNonZero, pftNonZero); + } + + /* Call out to pattern tiler for pattern fills. The path becomes the clip here. */ + if (fill_color == GRB_PATTERN_FILL) { + string fill_pattern_id = usvg_id_url(node.attribute("fill").value()); + Pattern *pattern = lookup_pattern(fill_pattern_id); + if (!pattern) { + cerr << "Warning: Fill pattern with id \"" << fill_pattern_id << "\" not found." << endl; + + } else { + Paths clip; + PolyTreeToPaths(ptree, clip); + pattern->tile(clip); + } + + } else { /* solid fill */ + Paths f_polys; + /* Important for gerber spec compliance and also for reliable rendering results irrespective of board house + * and gerber viewer. */ + dehole_polytree(ptree, f_polys); + + /* Export SVG */ + cairo_save(cr); + cairo_set_matrix(cr, &viewport_matrix); + cairo_new_path(cr); + ClipperLib::cairo::clipper_to_cairo(f_polys, cr, CAIRO_PRECISION, ClipperLib::cairo::tNone); + if (fill_color == GRB_DARK) { + cairo_set_source_rgba(cr, 0.0, 0.0, 1.0, dbg_fill_alpha); + } else { /* GRB_CLEAR */ + cairo_set_source_rgba(cr, 1.0, 0.0, 0.0, dbg_fill_alpha); + } + cairo_fill (cr); + + /* export gerber */ + cairo_identity_matrix(cr); + for (const auto &poly : f_polys) { + vector<array<double, 2>> out; + for (const auto &p : poly) + out.push_back(std::array<double, 2>{ + ((double)p.X) / clipper_scale, ((double)p.Y) / clipper_scale + }); + std::cerr << "calling sink" << std::endl; + polygon_sink(out, fill_color == GRB_DARK); + } + cairo_restore(cr); + } + } + + if (stroke_color && stroke_width > 0.0) { + ClipperOffset offx; + + /* For stroking we have to separately handle open and closed paths */ + for (const auto &poly : closed_paths) { + if (poly.empty()) /* do we need this? */ + continue; + + /* Special case: A closed path becomes a number of open paths when it is dashed. */ + if (dasharray.empty()) { + offx.AddPath(poly, join_type, etClosedLine); + + } else { + Path poly_copy(poly); + poly_copy.push_back(poly[0]); + Paths out; + dash_path(poly_copy, out, dasharray); + offx.AddPaths(out, join_type, end_type); + } + } + + for (const auto &poly : open_paths) { + Paths out; + dash_path(poly, out, dasharray); + offx.AddPaths(out, join_type, end_type); + } + + /* Execute clipper offset operation to generate stroke outlines */ + offx.Execute(ptree, 0.5 * stroke_width * clipper_scale); + + /* Clip. Note that after the outline, all we have is closed paths as any open path's stroke outline is itself + * a closed path. */ + if (!clip_path.empty()) { + Clipper c; + + Paths outline_paths; + PolyTreeToPaths(ptree, outline_paths); + c.AddPaths(outline_paths, ptSubject, /* closed */ true); + c.AddPaths(clip_path, ptClip, /* closed */ true); + c.StrictlySimple(true); + /* fill rules are nonzero since both subject and clip have already been normalized by clipper. */ + c.Execute(ctIntersection, ptree, pftNonZero, pftNonZero); + } + + /* Call out to pattern tiler for pattern strokes. The stroke's outline becomes the clip here. */ + if (stroke_color == GRB_PATTERN_FILL) { + string stroke_pattern_id = usvg_id_url(node.attribute("stroke").value()); + Pattern *pattern = lookup_pattern(stroke_pattern_id); + if (!pattern) { + cerr << "Warning: Fill pattern with id \"" << stroke_pattern_id << "\" not found." << endl; + + } else { + Paths clip; + PolyTreeToPaths(ptree, clip); + pattern->tile(clip); + } + + } else { + Paths s_polys; + dehole_polytree(ptree, s_polys); + + /* Export debug svg */ + cairo_save(cr); + cairo_set_matrix(cr, &viewport_matrix); + cairo_new_path(cr); + ClipperLib::cairo::clipper_to_cairo(s_polys, cr, CAIRO_PRECISION, ClipperLib::cairo::tNone); + if (stroke_color == GRB_DARK) { + cairo_set_source_rgba(cr, 0.0, 0.0, 1.0, dbg_stroke_alpha); + } else { /* GRB_CLEAR */ + cairo_set_source_rgba(cr, 1.0, 0.0, 0.0, dbg_stroke_alpha); + } + cairo_fill (cr); + + /* export gerber */ + cairo_identity_matrix(cr); + for (const auto &poly : s_polys) { + vector<array<double, 2>> out; + for (const auto &p : poly) + out.push_back(std::array<double, 2>{ + ((double)p.X) / clipper_scale, ((double)p.Y) / clipper_scale + }); + std::cerr << "calling sink" << std::endl; + polygon_sink(out, stroke_color == GRB_DARK); + } + cairo_restore(cr); + } + } +} + +void svg_plugin::SVGDocument::do_export(string debug_out_filename) { + assert(_valid); + /* Export the actual SVG document to both SVG for debuggin and to gerber. We do this as we go, i.e. we immediately + * process each element to gerber as we encounter it instead of first rendering everything to a giant list of gerber + * primitives and then serializing those later. Exporting them on the fly saves a ton of memory and is much faster. + */ + ClipperLib::Clipper c; + c.AddPaths(vb_paths, ptSubject, /* closed */ true); + ClipperLib::IntRect bbox = c.GetBounds(); + cerr << "document viewbox clip: bbox={" << bbox.left << ", " << bbox.top << "} - {" << bbox.right << ", " << bbox.bottom << "}" << endl; + export_svg_group(root_elem, vb_paths); +} + +void svg_plugin::SVGDocument::setup_debug_output(string filename) { + /* Setup cairo to draw into a SVG surface (for debugging). For actual rendering, something like a recording surface + * would work fine, too. */ + /* Cairo expects the SVG surface size to be given in pt (72.0 pt = 1.0 in = 25.4 mm) */ + const char *fn = filename.empty() ? nullptr : filename.c_str(); + assert (!cr); + assert (!surface); + surface = cairo_svg_surface_create(fn, page_w_mm / 25.4 * 72.0, page_h_mm / 25.4 * 72.0); + cr = cairo_create (surface); + /* usvg returns "pixels", cairo thinks we draw "points" at 72.0 pt per inch. */ + cairo_scale(cr, page_w / vb_w * 72.0 / assumed_usvg_dpi, page_h / vb_h * 72.0 / assumed_usvg_dpi); + + cairo_translate(cr, -vb_x, -vb_y); + + /* Store viewport transform and reset cairo's active transform. We have to do this since we have to render out all + * gerber primitives in mm, not px and most gerber primitives we export pass through Cairo at some point. + * + * We manually apply this viewport transform every time for debugging we actually use Cairo to export SVG. */ + cairo_get_matrix(cr, &viewport_matrix); + cairo_identity_matrix(cr); + + cairo_set_line_width (cr, 0.1); + cairo_set_source_rgba (cr, 1.0, 0.0, 0.0, 1.0); +} + +void svg_plugin::SVGDocument::setup_viewport_clip() { + /* Set up view port clip path */ + Path vb_path; + for (auto &elem : vector<pair<double, double>> {{vb_x, vb_y}, {vb_x+vb_w, vb_y}, {vb_x+vb_w, vb_y+vb_h}, {vb_x, vb_y+vb_h}}) { + double x = elem.first, y = elem.second; + vb_path.push_back({ (cInt)round(x * clipper_scale), (cInt)round(y * clipper_scale) }); + cerr << "adding to path: " << (cInt)round(x * clipper_scale) << ", " << (cInt)round(y * clipper_scale) << endl; + } + vb_paths.push_back(vb_path); + + ClipperLib::Clipper c; + c.AddPaths(vb_paths, ptSubject, /* closed */ true); + ClipperLib::IntRect bbox = c.GetBounds(); + cerr << "did set up viewbox clip: bbox={" << bbox.left << ", " << bbox.top << "} - {" << bbox.right << ", " << bbox.bottom << "}" << endl; + export_svg_group(root_elem, vb_paths); +} + +void svg_plugin::SVGDocument::load_patterns() { + /* Set up document-wide pattern registry. Load patterns from <defs> node. */ + for (const auto &node : defs_node.children("pattern")) { + pattern_map.emplace(std::piecewise_construct, std::forward_as_tuple(node.attribute("id").value()), std::forward_as_tuple(node, *this)); + } +} + +void svg_plugin::SVGDocument::load_clips() { + /* Set up document-wide clip path registry: Extract clip path definitions from <defs> element */ + for (const auto &node : defs_node.children("clipPath")) { + cairo_save(cr); + apply_cairo_transform_from_svg(cr, node.attribute("transform").value()); + + string meta_clip_path_id(usvg_id_url(node.attribute("clip-path").value())); + Clipper c; + + /* The clipPath node can only contain <path> children. usvg converts all geometric objects (rect etc.) to + * <path>s. Raster images are invalid inside a clip path. usvg removes all groups that are not relevant to + * rendering, and the only way a group might stay is if it affects rasterization (e.g. through mask, clipPath). + */ + for (const auto &child : node.children("path")) { + PolyTree ptree; + cairo_save(cr); + /* TODO: we currently only support clipPathUnits="userSpaceOnUse", not "objectBoundingBox". */ + apply_cairo_transform_from_svg(cr, child.attribute("transform").value()); + load_svg_path(cr, child, ptree); + cairo_restore (cr); + + Paths paths; + PolyTreeToPaths(ptree, paths); + c.AddPaths(paths, ptSubject, /* closed */ false); + } + + /* Support clip paths that themselves have clip paths */ + if (!meta_clip_path_id.empty()) { + if (clip_path_map.contains(meta_clip_path_id)) { + /* all clip paths must be closed */ + c.AddPaths(clip_path_map[meta_clip_path_id], ptClip, /* closed */ true); + + } else { + cerr << "Warning: Cannot find clip path with ID \"" << meta_clip_path_id << "\", ignoring." << endl; + } + } + + PolyTree ptree; + c.StrictlySimple(true); + /* This unions all child <path>s together and at the same time applies any meta clip path. */ + /* The fill rules are both nonzero since both subject and clip have already been normalized by clipper. */ + c.Execute(ctUnion, ptree, pftNonZero, pftNonZero); + /* Insert into document clip path map */ + PolyTreeToPaths(ptree, clip_path_map[node.attribute("id").value()]); + + cairo_restore(cr); + } +} + diff --git a/src/svg_doc.h b/src/svg_doc.h new file mode 100644 index 0000000..01a4e7a --- /dev/null +++ b/src/svg_doc.h @@ -0,0 +1,97 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2021 Jan Sebastian Götte <kicad@jaseg.de> + * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#ifndef SVG_DOC_H +#define SVG_DOC_H + +#include <map> + +#include <pugixml.hpp> + +#include "svg_pattern.h" + +namespace svg_plugin { + + typedef std::function<void (std::vector<std::array<double, 2>>, bool)> polygon_sink_fun; + + class SVGDocument { + public: + SVGDocument() : _valid(false) {} + SVGDocument(polygon_sink_fun sink_fun) : _valid(false), polygon_sink(sink_fun) {} + ~SVGDocument(); + + /* true -> load successful */ + bool load(std::string filename, std::string debug_out_filename="/tmp/kicad_svg_debug.svg"); + /* true -> load successful */ + bool valid() const { return _valid; } + operator bool() const { return valid(); } + + double mm_to_doc_units(double) const; + double doc_units_to_mm(double) const; + + double width() const { return page_w_mm; } + double height() const { return page_h_mm; } + + void do_export(std::string debug_out_filename=""); + + private: + friend class Pattern; + + cairo_t *cairo() { return cr; } + const ClipperLib::Paths *lookup_clip_path(const pugi::xml_node &node); + Pattern *lookup_pattern(const std::string id); + + void export_svg_group(const pugi::xml_node &group, ClipperLib::Paths &parent_clip_path); + void export_svg_path(const pugi::xml_node &node, ClipperLib::Paths &clip_path); + void setup_debug_output(std::string filename=""); + void setup_viewport_clip(); + void load_clips(); + void load_patterns(); + + bool _valid; + pugi::xml_document svg_doc; + pugi::xml_node root_elem; + pugi::xml_node defs_node; + double vb_x, vb_y, vb_w, vb_h; + double page_w, page_h; + double page_w_mm, page_h_mm; + std::map<std::string, Pattern> pattern_map; + std::map<std::string, ClipperLib::Paths> clip_path_map; + cairo_matrix_t viewport_matrix; + ClipperLib::Paths vb_paths; /* viewport clip rect */ + + cairo_t *cr = nullptr; + cairo_surface_t *surface = nullptr; + + polygon_sink_fun polygon_sink; + + static constexpr double dbg_fill_alpha = 0.8; + static constexpr double dbg_stroke_alpha = 1.0; + static constexpr double assumed_usvg_dpi = 96.0; + }; + +} /* namespace svg_plugin */ + +#endif /* SVG_DOC_H */ + diff --git a/src/svg_geom.cpp b/src/svg_geom.cpp new file mode 100644 index 0000000..0e40e7b --- /dev/null +++ b/src/svg_geom.cpp @@ -0,0 +1,181 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2021 Jan Sebastian Götte <kicad@jaseg.de> + * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#include "svg_geom.h" + +#include <cmath> +#include <string> +#include <sstream> +#include <assert.h> +#include <cairo.h> +#include "svg_import_defs.h" + +using namespace ClipperLib; +using namespace std; + +/* Get bounding box of a Clipper Paths */ +IntRect svg_plugin::get_paths_bounds(const Paths &paths) { + if (paths.empty()) { + return {0, 0, 0, 0}; + } + + if (paths[0].empty()) { + return {0, 0, 0, 0}; + } + + IntPoint p0 = paths[0][0]; + cInt x0=p0.X, y0=p0.Y, x1=p0.X, y1=p0.Y; + + for (const Path &p : paths) { + for (const IntPoint ip : p) { + if (ip.X < x0) + x0 = ip.X; + + if (ip.Y < y0) + y0 = ip.Y; + + if (ip.X > x1) + x1 = ip.X; + + if (ip.Y > y1) + y1 = ip.Y; + } + } + + return {x0, y0, x1, y1}; +} + +enum ClipperLib::PolyFillType svg_plugin::clipper_fill_rule(const pugi::xml_node &node) { + string val(node.attribute("fill-rule").value()); + if (val == "evenodd") + return ClipperLib::pftEvenOdd; + else + return ClipperLib::pftNonZero; /* default */ +} + +enum ClipperLib::EndType svg_plugin::clipper_end_type(const pugi::xml_node &node) { + string val(node.attribute("stroke-linecap").value()); + if (val == "round") + return ClipperLib::etOpenRound; + + if (val == "square") + return ClipperLib::etOpenSquare; + + return ClipperLib::etOpenButt; +} + +enum ClipperLib::JoinType svg_plugin::clipper_join_type(const pugi::xml_node &node) { + string val(node.attribute("stroke-linejoin").value()); + if (val == "round") + return ClipperLib::jtRound; + + if (val == "bevel") + return ClipperLib::jtSquare; + + return ClipperLib::jtMiter; +} + +/* Take a Clipper polytree, i.e. a description of a set of polygons, their holes and their inner polygons, and remove + * all holes from it. We remove holes by splitting each polygon that has a hole into two or more pieces so that the hole + * is no more. These pieces perfectly fit each other so there is no visual or functional difference. + */ +void svg_plugin::dehole_polytree(PolyNode &ptree, Paths &out) { + for (int i=0; i<ptree.ChildCount(); i++) { + PolyNode *nod = ptree.Childs[i]; + assert(nod); + assert(!nod->IsHole()); + + /* First, recursively process inner polygons. */ + for (int j=0; j<nod->ChildCount(); j++) { + PolyNode *child = nod->Childs[j]; + assert(child); + assert(child->IsHole()); + + if (child->ChildCount() > 0) { + dehole_polytree(*child, out); + } + } + + if (nod->ChildCount() == 0) { + out.push_back(nod->Contour); + + } else { + + /* Do not add children's children, those were handled in the recursive call above */ + Clipper c; + c.AddPath(nod->Contour, ptSubject, /* closed= */ true); + for (int k=0; k<nod->ChildCount(); k++) { + c.AddPath(nod->Childs[k]->Contour, ptSubject, /* closed= */ true); + } + + /* Find a viable cut: Cut from top-left bounding box corner, through two subsequent points on the hole + * outline and to top-right bbox corner. */ + IntRect bbox = c.GetBounds(); + Path tri = { { bbox.left, bbox.top }, nod->Childs[0]->Contour[0], nod->Childs[0]->Contour[1], { bbox.right, bbox.top } }; + c.AddPath(tri, ptClip, true); + + PolyTree solution; + c.StrictlySimple(true); + /* Execute twice, once for intersection fragment and once for difference fragment. Note that this will yield + * at least two, but possibly more polygons. */ + c.Execute(ctDifference, solution, pftNonZero); + dehole_polytree(solution, out); + + c.Execute(ctIntersection, solution, pftNonZero); + dehole_polytree(solution, out); + } + } +} + +/* Intersect two clip paths. Both must share a coordinate system. */ +void svg_plugin::combine_clip_paths(Paths &in_a, Paths &in_b, Paths &out) { + Clipper c; + c.StrictlySimple(true); + c.AddPaths(in_a, ptClip, /* closed */ true); + c.AddPaths(in_b, ptSubject, /* closed */ true); + /* Nonzero fill since both input clip paths must already have been preprocessed by clipper. */ + c.Execute(ctIntersection, out, pftNonZero); +} + +/* Transform given clipper paths under the given cairo transform. If no transform is given, use cairo's current + * user-to-device transform. */ +void svg_plugin::transform_paths(cairo_t *cr, Paths &paths, cairo_matrix_t *mat) { + cairo_save(cr); + if (mat != nullptr) { + cairo_set_matrix(cr, mat); + } + + for (Path &p : paths) { + transform(p.begin(), p.end(), p.begin(), + [cr](IntPoint p) -> IntPoint { + double x = p.X / clipper_scale, y = p.Y / clipper_scale; + cairo_user_to_device(cr, &x, &y); + return { (cInt)round(x * clipper_scale), (cInt)round(y * clipper_scale) }; + }); + } + + cairo_restore(cr); +} + + diff --git a/src/svg_geom.h b/src/svg_geom.h new file mode 100644 index 0000000..dfd1c80 --- /dev/null +++ b/src/svg_geom.h @@ -0,0 +1,44 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2021 Jan Sebastian Götte <kicad@jaseg.de> + * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#ifndef SVG_GEOM_H +#define SVG_GEOM_H + +#include <cairo.h> +#include <clipper.hpp> +#include <pugixml.hpp> + +namespace svg_plugin { + +ClipperLib::IntRect get_paths_bounds(const ClipperLib::Paths &paths); +enum ClipperLib::PolyFillType clipper_fill_rule(const pugi::xml_node &node); +enum ClipperLib::EndType clipper_end_type(const pugi::xml_node &node); +enum ClipperLib::JoinType clipper_join_type(const pugi::xml_node &node); +void dehole_polytree(ClipperLib::PolyNode &ptree, ClipperLib::Paths &out); +void combine_clip_paths(ClipperLib::Paths &in_a, ClipperLib::Paths &in_b, ClipperLib::Paths &out); +void transform_paths(cairo_t *cr, ClipperLib::Paths &paths, cairo_matrix_t *mat=nullptr); + +} /* namespace svg_plugin */ + +#endif /* SVG_GEOM_H */ diff --git a/src/svg_import_defs.h b/src/svg_import_defs.h new file mode 100644 index 0000000..e25c52c --- /dev/null +++ b/src/svg_import_defs.h @@ -0,0 +1,49 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2016 CERN + * @author Janito V. Ferreira Filho <janito.vff@gmail.com> + * Copyright (C) 2018-2019 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#ifndef SVG_IMPORT_DEFS_H +#define SVG_IMPORT_DEFS_H + +#include <cfloat> + +template <typename T> +constexpr T ipow(T num, unsigned int pow) +{ + return (pow >= sizeof(unsigned int)*8) ? 0 : + pow == 0 ? 1 : num * ipow(num, pow-1); +} + +constexpr int CAIRO_PRECISION = 7; +constexpr double clipper_scale = ipow(10.0, CAIRO_PRECISION); + +#define JC_VORONOI_IMPLEMENTATION +#define JCV_REAL_TYPE double +#define JCV_ATAN2 atan2 +#define JCV_SQRT sqrt +#define JCV_FLT_MAX DBL_MAX +#define JCV_PI 3.141592653589793115997963468544185161590576171875 +//define JCV_EDGE_INTERSECT_THRESHOLD 1.0e-10F + +#endif /* SVG_IMPORT_DEFS_H */ diff --git a/src/svg_import_util.cpp b/src/svg_import_util.cpp new file mode 100644 index 0000000..5624bd9 --- /dev/null +++ b/src/svg_import_util.cpp @@ -0,0 +1,129 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2021 Jan Sebastian Götte <kicad@jaseg.de> + * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#include <cmath> +#include "base64.h" +#include "svg_import_util.h" + +using namespace std; + +void svg_plugin::print_matrix(cairo_t *cr, bool print_examples) { + cairo_matrix_t mat; + cairo_get_matrix(cr, &mat); + cerr << " xform matrix = { xx=" << mat.xx << ", yx=" << mat.yx << ", xy=" << mat.xy << ", yy=" << mat.yy << ", x0=" << mat.x0 << ", y0=" << mat.y0 << " }" << endl; + if (print_examples) { + double x=0, y=0; + cairo_user_to_device(cr, &x, &y); + cerr << " (0, 0) -> (" << x << ", " << y << ")" << endl; + x = 1, y = 0; + cairo_user_to_device(cr, &x, &y); + cerr << " (1, 0) -> (" << x << ", " << y << ")" << endl; + x = 0, y = 1; + cairo_user_to_device(cr, &x, &y); + cerr << " (0, 1) -> (" << x << ", " << y << ")" << endl; + x = 1, y = 1; + cairo_user_to_device(cr, &x, &y); + cerr << " (1, 1) -> (" << x << ", " << y << ")" << endl; + } +} + +/* Read a double value formatted like usvg formats doubles from an SVG attribute */ +double svg_plugin::usvg_double_attr(const pugi::xml_node &node, const char *attr, double default_value) { + const auto *val = node.attribute(attr).value(); + if (*val == '\0') + return default_value; + + return atof(val); +} + +/* Read an url from an usvg attribute */ +string svg_plugin::usvg_id_url(string attr) { + if (attr.rfind("url(#", 0) == string::npos) + return string(); + + attr = attr.substr(strlen("url(#")); + attr = attr.substr(0, attr.size()-1); + return attr; +} + +svg_plugin::RelativeUnits svg_plugin::map_str_to_units(string str, svg_plugin::RelativeUnits default_val) { + if (str == "objectBoundingBox") + return SVG_ObjectBoundingBox; + else if (str == "userSpaceOnUse") + return SVG_UserSpaceOnUse; + return default_val; +} + +void svg_plugin::load_cairo_matrix_from_svg(const string &transform, cairo_matrix_t &mat) { + if (transform.empty()) { + cairo_matrix_init_identity(&mat); + return; + } + + string start("matrix("); + assert(transform.substr(0, start.length()) == start); + assert(transform.back() == ')'); + const string &foo = transform.substr(start.length(), transform.length()); + const string &bar = foo.substr(0, foo.length() - 1); + + istringstream xform(bar); + + double a, c, e, + b, d, f; + xform >> a >> b >> c >> d >> e >> f; + assert(!xform.fail()); + + cairo_matrix_init(&mat, a, b, c, d, e, f); +} + +void svg_plugin::apply_cairo_transform_from_svg(cairo_t *cr, const string &transform) { + cairo_matrix_t mat; + load_cairo_matrix_from_svg(transform, mat); + cairo_transform(cr, &mat); /* or cairo_transform? */ +} + +/* Cf. https://tools.ietf.org/html/rfc2397 */ +string svg_plugin::parse_data_iri(const string &data_url) { + if (data_url.rfind("data:", 0) == string::npos) /* check if url starts with "data:" */ + return string(); + + size_t foo = data_url.find("base64,"); + if (foo == string::npos) /* check if this is actually a data URL */ + return string(); + + size_t b64_begin = data_url.find_first_not_of(" ", foo + strlen("base64,")); + assert(b64_begin != string::npos); + + return base64_decode(data_url.substr(b64_begin)); +} + +/* for debug svg output */ +void svg_plugin::apply_viewport_matrix(cairo_t *cr, cairo_matrix_t &viewport_matrix) { + /* Multiply viewport matrix *from the left*, i.e. as if it had been applied *before* the currently set matrix. */ + cairo_matrix_t old_matrix; + cairo_get_matrix(cr, &old_matrix); + cairo_set_matrix(cr, &viewport_matrix); + cairo_transform(cr, &old_matrix); +} + diff --git a/src/svg_import_util.h b/src/svg_import_util.h new file mode 100644 index 0000000..8485957 --- /dev/null +++ b/src/svg_import_util.h @@ -0,0 +1,69 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2021 Jan Sebastian Götte <kicad@jaseg.de> + * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#ifndef SVG_IMPORT_UTIL_H +#define SVG_IMPORT_UTIL_H + +#include <math.h> +#include <cmath> +#include <stdlib.h> +#include <assert.h> +#include <limits> +#include <vector> +#include <string> +#include <iostream> +#include <sstream> +#include <regex> + +#include <pango/pangocairo.h> +#include <cairo-svg.h> + +#include <clipper.hpp> +#include "cairo_clipper.hpp" + +#include <pugixml.hpp> + +#include "svg_import_defs.h" + +namespace svg_plugin { + +/* Coordinate system selection for things like "patternContentUnits" */ +enum RelativeUnits { + SVG_UnknownUnits = 0, + SVG_UserSpaceOnUse, + SVG_ObjectBoundingBox, +}; + +void print_matrix(cairo_t *cr, bool print_examples=false); +double usvg_double_attr(const pugi::xml_node &node, const char *attr, double default_value=0.0); +std::string usvg_id_url(std::string attr); +RelativeUnits map_str_to_units(std::string str, RelativeUnits default_val=SVG_UnknownUnits); +void load_cairo_matrix_from_svg(const std::string &transform, cairo_matrix_t &mat); +void apply_cairo_transform_from_svg(cairo_t *cr, const std::string &transform); +std::string parse_data_iri(const std::string &data_url); +void apply_viewport_matrix(cairo_t *cr, cairo_matrix_t &viewport_matrix); + +} /* namespace svg_plugin */ + +#endif /* SVG_IMPORT_UTIL_H */ diff --git a/src/svg_path.cpp b/src/svg_path.cpp new file mode 100644 index 0000000..9137e1a --- /dev/null +++ b/src/svg_path.cpp @@ -0,0 +1,219 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2021 Jan Sebastian Götte <kicad@jaseg.de> + * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#include <cmath> +#include <assert.h> +#include <iostream> +#include <sstream> +#include "cairo_clipper.hpp" +#include "svg_import_defs.h" +#include "svg_path.h" + +using namespace std; + +static void clipper_add_cairo_path(cairo_t *cr, ClipperLib::Clipper &c, bool closed) { + ClipperLib::Paths in_poly; + ClipperLib::cairo::cairo_to_clipper(cr, in_poly, CAIRO_PRECISION, ClipperLib::cairo::tNone); + c.AddPaths(in_poly, ClipperLib::ptSubject, closed); +} + +static void path_to_clipper_via_cairo(cairo_t *cr, ClipperLib::Clipper &c, const pugi::char_t *path_data) { + istringstream d(path_data); + + string cmd; + double x, y, c1x, c1y, c2x, c2y; + + bool first = true; + bool path_is_empty = true; + while (!d.eof()) { + d >> cmd; + assert (!d.fail()); + assert(!first || cmd == "M"); + + if (cmd == "Z") { /* Close path */ + cairo_close_path(cr); + clipper_add_cairo_path(cr, c, /* closed= */ true); + cairo_new_path(cr); + path_is_empty = true; + + } else if (cmd == "M") { /* Move to */ + d >> x >> y; + /* We need to transform all points ourselves here, and cannot use the transform feature of cairo_to_clipper: + * Our transform may contain offsets, and clipper only passes its data into cairo's transform functions + * after scaling up to its internal fixed-point ints, but it does not scale the transform accordingly. This + * means a scale/rotation we set before calling clipper works out fine, but translations get lost as they + * get scaled by something like 1e-6. + */ + cairo_user_to_device(cr, &x, &y); + assert (!d.fail()); + if (!first) + clipper_add_cairo_path(cr, c, /* closed= */ false); + cairo_new_path (cr); + path_is_empty = true; + cairo_move_to(cr, x, y); + + } else if (cmd == "L") { /* Line to */ + d >> x >> y; + cairo_user_to_device(cr, &x, &y); + assert (!d.fail()); + cairo_line_to(cr, x, y); + path_is_empty = false; + + } else { /* Curve to */ + assert(cmd == "C"); + d >> c1x >> c1y; /* first control point */ + cairo_user_to_device(cr, &c1x, &c1y); + d >> c2x >> c2y; /* second control point */ + cairo_user_to_device(cr, &c2x, &c2y); + d >> x >> y; /* end point */ + cairo_user_to_device(cr, &x, &y); + assert (!d.fail()); + cairo_curve_to(cr, c1x, c1y, c2x, c2y, x, y); + path_is_empty = false; + } + + first = false; + } + if (!path_is_empty) { + cairo_close_path(cr); + clipper_add_cairo_path(cr, c, /* closed= */ false); + } +} + +void svg_plugin::load_svg_path(cairo_t *cr, const pugi::xml_node &node, ClipperLib::PolyTree &ptree) { + auto *path_data = node.attribute("d").value(); + auto fill_rule = clipper_fill_rule(node); + + /* For open paths, clipper does not correctly remove self-intersections. Thus, we pass everything into + * clipper twice: Once with all paths set to "closed" to compute fill areas, and once with correct + * open/closed properties for stroke offsetting. */ + cairo_set_tolerance (cr, 0.1); /* FIXME make configurable, scale properly for units */ + cairo_set_fill_rule(cr, CAIRO_FILL_RULE_WINDING); + + ClipperLib::Clipper c; + c.StrictlySimple(true); + path_to_clipper_via_cairo(cr, c, path_data); + /* We canont clip the polygon here since that would produce incorrect results for our stroke. */ + c.Execute(ClipperLib::ctUnion, ptree, fill_rule, ClipperLib::pftNonZero); +} + +void svg_plugin::parse_dasharray(const pugi::xml_node &node, vector<double> &out) { + out.clear(); + + string val(node.attribute("stroke-dasharray").value()); + if (val.empty() || val == "none") + return; + + istringstream desc_stream(val); + while (!desc_stream.eof()) { + /* usvg says the array only contains unitless (px) values. I don't know what resvg does with percentages inside + * dash arrays. We just assume everything is a unitless number here. In case usvg passes through percentages, + * well, bad luck. They are a kind of weird thing inside a dash array in the first place. */ + double d; + desc_stream >> d; + out.push_back(d); + } + + assert(out.size() % 2 == 0); /* according to resvg spec */ +} + +/* Take a Clipper path in clipper-scaled document units, and apply the given SVG dash array to it. Do this by walking + * the path from start to end while emitting dashes. */ +void svg_plugin::dash_path(const ClipperLib::Path &in, ClipperLib::Paths &out, const vector<double> dasharray, double dash_offset) { + out.clear(); + if (dasharray.empty() || in.size() < 2) { + out.push_back(in); + return; + } + + size_t dash_idx = 0; + size_t num_dashes = dasharray.size(); + while (dash_offset > dasharray[dash_idx]) { + dash_offset -= dasharray[dash_idx]; + dash_idx = (dash_idx + 1) % num_dashes; + } + + double dash_remaining = dasharray[dash_idx] - dash_offset; + + ClipperLib::Path current_dash; + current_dash.push_back(in[0]); + double dbg_total_len = 0.0; + for (size_t i=1; i<in.size(); i++) { + ClipperLib::IntPoint p1(in[i-1]), p2(in[i]); + + double x1 = p1.X / clipper_scale, y1 = p1.Y / clipper_scale, x2 = p2.X / clipper_scale, y2 = p2.Y / clipper_scale; + double dist = sqrt(pow(x2-x1, 2) + pow(y2-y1, 2)); + dbg_total_len += dist; + + if (dist < dash_remaining) { + /* dash extends beyond this segment, append this segment and continue. */ + dash_remaining -= dist; + current_dash.push_back(p2); + + } else { + /* dash started in some previous segment ends in this segment */ + double dash_frac = dash_remaining/dist; + double x = x1 + (x2 - x1) * dash_frac, + y = y1 + (y2 - y1) * dash_frac; + ClipperLib::IntPoint intermediate {(ClipperLib::cInt)round(x * clipper_scale), (ClipperLib::cInt)round(y * clipper_scale)}; + + /* end this dash */ + current_dash.push_back(intermediate); + if (dash_idx%2 == 0) { /* dash */ + out.push_back(current_dash); + } /* else space */ + dash_idx = (dash_idx + 1) % num_dashes; + double offset = dash_remaining; + + /* start next dash */ + current_dash.clear(); + current_dash.push_back(intermediate); + + /* handle case where multiple dashes fit into this segment */ + while ((dist - offset) > dasharray[dash_idx]) { + offset += dasharray[dash_idx]; + + double dash_frac = offset/dist; + double x = x1 + (x2 - x1) * dash_frac, + y = y1 + (y2 - y1) * dash_frac; + ClipperLib::IntPoint intermediate {(ClipperLib::cInt)round(x * clipper_scale), (ClipperLib::cInt)round(y * clipper_scale)}; + + /* end this dash */ + current_dash.push_back(intermediate); + if (dash_idx%2 == 0) { /* dash */ + out.push_back(current_dash); + } /* else space */ + dash_idx = (dash_idx + 1) % num_dashes; + + /* start next dash */ + current_dash.clear(); + current_dash.push_back(intermediate); + } + + dash_remaining = dasharray[dash_idx] - (dist - offset); + current_dash.push_back(p2); + } + } +} + diff --git a/src/svg_path.h b/src/svg_path.h new file mode 100644 index 0000000..0a527f6 --- /dev/null +++ b/src/svg_path.h @@ -0,0 +1,38 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2021 Jan Sebastian Götte <kicad@jaseg.de> + * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#ifndef SVG_PATH_H +#define SVG_PATH_H + +#include <vector> +#include <cairo.h> +#include "svg_geom.h" + +namespace svg_plugin { +void load_svg_path(cairo_t *cr, const pugi::xml_node &node, ClipperLib::PolyTree &ptree); +void parse_dasharray(const pugi::xml_node &node, std::vector<double> &out); +void dash_path(const ClipperLib::Path &in, ClipperLib::Paths &out, const std::vector<double> dasharray, double dash_offset=0.0); +} + +#endif /* SVG_PATH_H */ diff --git a/src/svg_pattern.cpp b/src/svg_pattern.cpp new file mode 100644 index 0000000..8ca6572 --- /dev/null +++ b/src/svg_pattern.cpp @@ -0,0 +1,119 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2021 Jan Sebastian Götte <kicad@jaseg.de> + * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#include <assert.h> +#include "svg_import_util.h" +#include "svg_pattern.h" +#include "svg_import_defs.h" +#include "svg_geom.h" +#include "svg_doc.h" + +using namespace std; + +svg_plugin::Pattern::Pattern(const pugi::xml_node &node, SVGDocument &doc) : _node(node), doc(&doc) { + /* Read pattern attributes from SVG node */ + cerr << "creating pattern for node with id \"" << node.attribute("id").value() << "\"" << endl; + x = usvg_double_attr(node, "x"); + y = usvg_double_attr(node, "y"); + w = usvg_double_attr(node, "width"); + h = usvg_double_attr(node, "height"); + patternTransform = node.attribute("patternTransform").value(); + + string vb_s(node.attribute("viewBox").value()); + has_vb = !vb_s.empty(); + if (has_vb) { + istringstream vb_stream(vb_s); + vb_stream >> vb_x >> vb_y >> vb_w >> vb_h; + } + + patternUnits = map_str_to_units(node.attribute("patternUnits").value(), SVG_ObjectBoundingBox); + patternContentUnits = map_str_to_units(node.attribute("patternContentUnits").value(), SVG_UserSpaceOnUse); +} + +/* Tile pattern into gerber. Note that this function may be called several times in case the pattern is + * referenced from multiple places, so we must not clobber any of the object's state. */ +void svg_plugin::Pattern::tile (ClipperLib::Paths &clip) { + assert(doc); + cairo_t *cr = doc->cairo(); + assert(cr); + + cairo_save(cr); + /* Transform x, y, w, h from pattern coordinate space into parent coordinates by applying the inverse + * patternTransform. This is necessary so we iterate over the correct bounds when tiling below */ + cairo_matrix_t mat; + load_cairo_matrix_from_svg(patternTransform, mat); + if (cairo_matrix_invert(&mat) != CAIRO_STATUS_SUCCESS) { + cerr << "Cannot invert patternTransform matrix on pattern \"" << _node.attribute("id").value() << "\"." << endl; + cairo_restore(cr); + } + double inst_x = x, inst_y = y, inst_w = w, inst_h = h; + cairo_user_to_device(cr, &inst_x, &inst_y); + cairo_user_to_device_distance(cr, &inst_w, &inst_h); + cairo_restore(cr); + + ClipperLib::IntRect clip_bounds = get_paths_bounds(clip); + double bx = clip_bounds.left / clipper_scale; + double by = clip_bounds.top / clipper_scale; + double bw = (clip_bounds.right - clip_bounds.left) / clipper_scale; + double bh = (clip_bounds.bottom - clip_bounds.top) / clipper_scale; + + if (patternUnits == SVG_ObjectBoundingBox) { + inst_x *= bw; + inst_y *= bh; + inst_w *= bw; + inst_h *= bh; + } + + /* Switch to pattern coordinates */ + cairo_save(cr); + cairo_translate(cr, bx, by); + apply_cairo_transform_from_svg(cr, patternTransform); + + /* Iterate over all pattern tiles in pattern coordinates */ + for (double inst_off_x = fmod(inst_x, inst_w) - inst_w; + inst_off_x < bw + inst_w; + inst_off_x += inst_w) { + + for (double inst_off_y = fmod(inst_y, inst_h) - inst_h; + inst_off_y < bh + inst_h; + inst_off_y += inst_h) { + + cairo_save(cr); + /* Change into this individual tile's coordinate system */ + cairo_translate(cr, inst_off_x, inst_off_y); + if (has_vb) { + cairo_translate(cr, vb_x, vb_y); + cairo_scale(cr, inst_w / vb_w, inst_h / vb_h); + } else if (patternContentUnits == SVG_ObjectBoundingBox) { + cairo_scale(cr, bw, bh); + } + + /* Export the pattern tile's content like a group */ + doc->export_svg_group(_node, clip); + cairo_restore(cr); + } + } + cairo_restore(cr); +} + diff --git a/src/svg_pattern.h b/src/svg_pattern.h new file mode 100644 index 0000000..e11fde5 --- /dev/null +++ b/src/svg_pattern.h @@ -0,0 +1,60 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2021 Jan Sebastian Götte <kicad@jaseg.de> + * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#ifndef SVG_PATTERN_H +#define SVG_PATTERN_H + +#include <string> +#include <cairo.h> + +#include <pugixml.hpp> +#include <clipper.hpp> + +#include "svg_import_util.h" + +namespace svg_plugin { + +class SVGDocument; + +class Pattern { +public: + Pattern() {} + Pattern(const pugi::xml_node &node, SVGDocument &doc); + + void tile (ClipperLib::Paths &clip); + +private: + double x, y, w, h; + double vb_x, vb_y, vb_w, vb_h; + bool has_vb; + std::string patternTransform; + enum RelativeUnits patternUnits; + enum RelativeUnits patternContentUnits; + const pugi::xml_node _node; + SVGDocument *doc = nullptr; +}; + +} /* namespace svg_plugin */ + +#endif /* SVG_PATTERN_H */ diff --git a/src/vec_core.cpp b/src/vec_core.cpp new file mode 100644 index 0000000..0c60c7d --- /dev/null +++ b/src/vec_core.cpp @@ -0,0 +1,339 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2021 Jan Sebastian Götte <kicad@jaseg.de> + * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#include <cmath> +#include <string> +#include <iostream> +#include <vector> +#include <opencv2/opencv.hpp> +#include "svg_import_util.h" +#include "vec_core.h" +#include "svg_import_defs.h" +#include "jc_voronoi.h" + +using namespace svg_plugin; +using namespace std; + +/* debug function */ +static void dbg_show_cv_image(cv::Mat &img) { + string windowName = "Debug image"; + cv::namedWindow(windowName); + cv::imshow(windowName, img); + cv::waitKey(0); + cv::destroyWindow(windowName); +} + +/* From jcv voronoi README */ +static void voronoi_relax_points(const jcv_diagram* diagram, jcv_point* points) { + const jcv_site* sites = jcv_diagram_get_sites(diagram); + for (int i=0; i<diagram->numsites; i++) { + const jcv_site* site = &sites[i]; + jcv_point sum = site->p; + int count = 1; + + const jcv_graphedge* edge = site->edges; + + while (edge) { + sum.x += edge->pos[0].x; + sum.y += edge->pos[0].y; + count++; + edge = edge->next; + } + + points[site->index].x = sum.x / count; + points[site->index].y = sum.y / count; + } +} + +/* Render image into gerber file. + * + * This function renders an image into a number of vector primitives emulating the images grayscale brightness by + * differently sized vector shaped giving an effect similar to halftone printing used in newspapers. + * + * On a high level, this function does this in four steps: + * 1. It preprocesses the source image at the pixel level. This involves several tasks: + * 1.1. It converts the image to grayscale. + * 1.2. It scales the image up or down to match the given minimum feature size. + * 1.3. It applies a blur depending on the given minimum feature size to prevent aliasing artifacts. + * 2. It randomly spread points across the image using poisson disc sampling. This yields points that have a fairly even + * average distance to each other across the image, and that have a guaranteed minimum distance that depends on + * minimum feature size. + * 3. It calculates a voronoi map based on this set of points and it calculats the polygon shape of each cell of the + * voronoi map. + * 4. It scales each of these voronoi cell polygons to match the input images brightness at the spot covered by this + * cell. + */ +void vectorizer::vectorize_image(cairo_t *cr, const pugi::xml_node &node, double min_feature_size_px, ClipperLib::Paths &clip_path, cairo_matrix_t &viewport_matrix) { + /* Read XML node attributes */ + auto x = usvg_double_attr(node, "x", 0.0); + auto y = usvg_double_attr(node, "y", 0.0); + auto width = usvg_double_attr(node, "width", 0.0); + auto height = usvg_double_attr(node, "height", 0.0); + assert (width > 0 && height > 0); + cerr << "image elem: w="<<width<<", h="<<height<<endl; + + /* Read image from data:base64... URL */ + string img_data = parse_data_iri(node.attribute("xlink:href").value()); + if (img_data.empty()) { + cerr << "Warning: Empty or invalid image element with id \"" << node.attribute("id").value() << "\"" << endl; + return; + } + + /* slightly annoying round-trip through the std:: and cv:: APIs */ + vector<unsigned char> img_vec(img_data.begin(), img_data.end()); + cv::Mat data_mat(img_vec, true); + cv::Mat img = cv::imdecode(data_mat, cv::ImreadModes::IMREAD_GRAYSCALE | cv::ImreadModes::IMREAD_ANYDEPTH); + data_mat.release(); + + if (img.empty()) { + cerr << "Warning: Could not decode content of image element with id \"" << node.attribute("id").value() << "\"" << endl; + return; + } + + /* Set up target transform using SVG transform and x/y attributes */ + cairo_save(cr); + apply_cairo_transform_from_svg(cr, node.attribute("transform").value()); + cairo_translate(cr, x, y); + + /* Adjust minimum feature size given in mm and translate into px document units in our local coordinate system. */ + double f_x = min_feature_size_px, f_y = 0; + cairo_device_to_user_distance(cr, &f_x, &f_y); + min_feature_size_px = sqrt(f_x*f_x + f_y*f_y); + + /* For both our debug SVG output and for the gerber output, we have to paint the image's bounding box in black as + * background for our halftone blobs. We cannot simply draw a rect here, though. Instead we have to first intersect + * the bounding box with the clip path we get from the caller, then we have to translate it into Cairo-SVG's + * document units. */ + /* First, setup the bounding box rectangle in our local px coordinate space. */ + ClipperLib::Path rect_path; + for (auto &elem : vector<pair<double, double>> {{0, 0}, {width, 0}, {width, height}, {0, height}}) { + double x = elem.first, y = elem.second; + cairo_user_to_device(cr, &x, &y); + rect_path.push_back({ (ClipperLib::cInt)round(x * clipper_scale), (ClipperLib::cInt)round(y * clipper_scale) }); + } + + /* Intersect the bounding box with the caller's clip path */ + ClipperLib::Clipper c; + c.AddPath(rect_path, ClipperLib::ptSubject, /* closed */ true); + if (!clip_path.empty()) { + c.AddPaths(clip_path, ClipperLib::ptClip, /* closed */ true); + } + + ClipperLib::Paths rect_out; + c.StrictlySimple(true); + c.Execute(ClipperLib::ctIntersection, rect_out, ClipperLib::pftNonZero, ClipperLib::pftNonZero); + + /* Finally, translate into Cairo-SVG's document units and draw. */ + cairo_save(cr); + cairo_set_matrix(cr, &viewport_matrix); + cairo_new_path(cr); + ClipperLib::cairo::clipper_to_cairo(rect_out, cr, CAIRO_PRECISION, ClipperLib::cairo::tNone); + cairo_set_source_rgba (cr, 0.0, 0.0, 0.0, 1.0); + /* First, draw into SVG */ + cairo_fill(cr); + cairo_restore(cr); + + /* Second, draw into gerber. */ + cairo_save(cr); + cairo_identity_matrix(cr); + for (const auto &poly : rect_out) { + /* FIXME */ + //export_as_gerber(cr, poly, /* dark */ false); + } + cairo_restore(cr); + + /* Set up a poisson-disc sampled point "grid" covering the image. Calculate poisson disc parameters from given + * minimum feature size. */ + double grayscale_overhead = 0.8; /* fraction of distance between two adjacent cell centers that is reserved for + grayscale interpolation. Larger values -> better grayscale resolution, + larger cells. */ + double center_distance = min_feature_size_px * 2.0 * (1.0 / (1.0-grayscale_overhead)); + vector<d2p> *grid_centers = sample_poisson_disc(width, height, min_feature_size_px * 2.0 * 2.0); + /* TODO make these alternative grids available to callers */ + //vector<d2p> *grid_centers = sample_hexgrid(width, height, center_distance); + //vector<d2p> *grid_centers = sample_squaregrid(width, height, center_distance); + + /* Target factor between given min_feature_size and intermediate image pixels, + * i.e. <scale_featuresize_factor> px ^= min_feature_size */ + double scale_featuresize_factor = 3.0; + /* TODO: support for preserveAspectRatio attribute */ + double px_w = width / min_feature_size_px * scale_featuresize_factor; + double px_h = height / min_feature_size_px * scale_featuresize_factor; + + /* Scale intermediate image (step 1.2) to have <scale_featuresize_factor> pixels per min_feature_size. */ + cv::Mat scaled(cv::Size{(int)round(px_w), (int)round(px_h)}, img.type()); + cv::resize(img, scaled, scaled.size(), 0, 0); + img.release(); + + /* Blur image with a kernel larger than our minimum feature size to avoid aliasing. */ + cv::Mat blurred(scaled.size(), scaled.type()); + int blur_size = (int)ceil(fmax(scaled.cols / width, scaled.rows / height) * center_distance); + cv::GaussianBlur(scaled, blurred, {blur_size, blur_size}, 0, 0); + scaled.release(); + + /* Calculate voronoi diagram for the grid generated above. */ + jcv_diagram diagram; + memset(&diagram, 0, sizeof(jcv_diagram)); + jcv_rect rect {{0.0, 0.0}, {width, height}}; + jcv_point *pts = reinterpret_cast<jcv_point *>(grid_centers->data()); /* hackety hack */ + jcv_diagram_generate(grid_centers->size(), pts, &rect, 0, &diagram); + /* Relax points, i.e. wiggle them around a little bit to equalize differences between cell sizes a little bit. */ + voronoi_relax_points(&diagram, pts); + memset(&diagram, 0, sizeof(jcv_diagram)); + jcv_diagram_generate(grid_centers->size(), pts, &rect, 0, &diagram); + + /* For each voronoi cell calculated above, find the brightness of the blurred image pixel below its center. We do + * not have to average over the entire cell's area here: The blur is doing a good approximation of that while being + * simpler and faster. + * + * We do this step before generating the cell poygons below because we have to look up a cell's neighbor's fill + * factor during gap filling for minimum feature size preservation. */ + vector<double> fill_factors(diagram.numsites); /* Factor to be multiplied with site polygon radius to yield target + fill level */ + const jcv_site* sites = jcv_diagram_get_sites(&diagram); + int j = 0; + for (int i=0; i<diagram.numsites; i++) { + const jcv_point center = sites[i].p; + + double pxd = (double)blurred.at<unsigned char>( + (int)round(center.y / height * blurred.rows), + (int)round(center.x / width * blurred.cols)) / 255.0; + fill_factors[sites[i].index] = sqrt(pxd); + } + + /* Minimum gap between adjacent scaled site polygons. */ + double min_gap_px = min_feature_size_px; + vector<double> adjusted_fill_factors; + adjusted_fill_factors.reserve(32); /* Vector to hold adjusted fill factors for each edge for gap filling */ + /* now iterate over all voronoi cells again to generate each cell's scaled polygon halftone blob. */ + for (int i=0; i<diagram.numsites; i++) { + const jcv_point center = sites[i].p; + double fill_factor_ours = fill_factors[sites[i].index]; + + /* Do not render halftone blobs that are too small */ + if (fill_factor_ours * 0.5 * center_distance < min_gap_px) + continue; + + /* Iterate over this cell's edges. For each edge, check the gap that would result between this cell's halftone + * blob and the neighboring cell's halftone blob based on their fill factors. If the gap is too small, either + * widen it by adjusting both fill factors down a bit (for this edge only!), or eliminate it by setting both + * fill factors to 1.0 (again, for this edge only!). */ + adjusted_fill_factors.clear(); + const jcv_graphedge* e = sites[i].edges; + while (e) { + /* half distance between both neighbors of this edge, i.e. sites[i] and its neighbor. */ + /* Note that in a voronoi tesselation, this edge is always halfway between. */ + double adjusted_fill_factor = fill_factor_ours; + + if (e->neighbor != nullptr) { /* nullptr -> edge is on the voronoi map's border */ + double rad = sqrt(pow(center.x - e->neighbor->p.x, 2) + pow(center.y - e->neighbor->p.y, 2)) / 2.0; + double fill_factor_theirs = fill_factors[e->neighbor->index]; + double gap_px = (1.0 - fill_factor_ours) * rad + (1.0 - fill_factor_theirs) * rad; + + if (gap_px > min_gap_px) { + /* all good. gap is wider than minimum. */ + } else if (gap_px > 0.5 * min_gap_px) { + /* gap is narrower than minimum, but more than half of minimum width. */ + /* force gap open, distribute adjustment evenly on left/right */ + double fill_factor_adjustment = (min_gap_px - gap_px) / 2.0 / rad; + adjusted_fill_factor -= fill_factor_adjustment; + } else { + /* gap is less than half of minimum width. Force gap closed. */ + adjusted_fill_factor = 1.0; + } + } + adjusted_fill_factors.push_back(adjusted_fill_factor); + e = e->next; + } + + /* Now, generate the actual halftone blob polygon */ + ClipperLib::Path cell_path; + double last_fill_factor = adjusted_fill_factors.back(); + e = sites[i].edges; + j = 0; + while (e) { + double fill_factor = adjusted_fill_factors[j]; + if (last_fill_factor != fill_factor) { + /* Fill factor was adjusted since last edge, so generate one extra point so we have a nice radial + * "step". */ + double x = e->pos[0].x; + double y = e->pos[0].y; + x = center.x + (x - center.x) * fill_factor; + y = center.y + (y - center.y) * fill_factor; + + cairo_user_to_device(cr, &x, &y); + cell_path.push_back({ (ClipperLib::cInt)round(x * clipper_scale), (ClipperLib::cInt)round(y * clipper_scale) }); + } + + /* Emit endpoint of current edge */ + double x = e->pos[1].x; + double y = e->pos[1].y; + x = center.x + (x - center.x) * fill_factor; + y = center.y + (y - center.y) * fill_factor; + + cairo_user_to_device(cr, &x, &y); + cell_path.push_back({ (ClipperLib::cInt)round(x * clipper_scale), (ClipperLib::cInt)round(y * clipper_scale) }); + + j += 1; + last_fill_factor = fill_factor; + e = e->next; + } + + /* Now, clip the halftone blob generated above against the given clip path. We do this individually for each + * blob since this way is *much* faster than throwing a million blobs at once at poor clipper. */ + ClipperLib::Paths polys; + ClipperLib::Clipper c; + c.AddPath(cell_path, ClipperLib::ptSubject, /* closed */ true); + if (!clip_path.empty()) { + c.AddPaths(clip_path, ClipperLib::ptClip, /* closed */ true); + } + c.StrictlySimple(true); + c.Execute(ClipperLib::ctIntersection, polys, ClipperLib::pftNonZero, ClipperLib::pftNonZero); + + /* Export halftone blob to debug svg */ + cairo_save(cr); + cairo_set_matrix(cr, &viewport_matrix); + cairo_new_path(cr); + ClipperLib::cairo::clipper_to_cairo(polys, cr, CAIRO_PRECISION, ClipperLib::cairo::tNone); + cairo_set_source_rgba(cr, 1, 1, 1, 1); + cairo_fill(cr); + cairo_restore(cr); + + /* And finally, export halftone blob to gerber. */ + cairo_save(cr); + cairo_identity_matrix(cr); + for (const auto &poly : polys) { + /* FIXME */ + //export_as_gerber(cr, poly, /* dark */ true); + } + cairo_restore(cr); + } + + blurred.release(); + jcv_diagram_free( &diagram ); + delete grid_centers; + cairo_restore(cr); +} + + diff --git a/src/vec_core.h b/src/vec_core.h new file mode 100644 index 0000000..20ffd24 --- /dev/null +++ b/src/vec_core.h @@ -0,0 +1,37 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2021 Jan Sebastian Götte <kicad@jaseg.de> + * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#ifndef VEC_CORE_H +#define VEC_CORE_H + +#include <cairo.h> +#include <pugixml.hpp> +#include <clipper.hpp> +#include "vec_grid.h" + +namespace vectorizer { + void vectorize_image(cairo_t *cr, const pugi::xml_node &node, double min_feature_size_px, ClipperLib::Paths &clip_path, cairo_matrix_t &viewport_matrix); +} + +#endif /* VEC_CORE_H */ diff --git a/src/vec_grid.cpp b/src/vec_grid.cpp new file mode 100644 index 0000000..0a3eaa2 --- /dev/null +++ b/src/vec_grid.cpp @@ -0,0 +1,105 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2021 Jan Sebastian Götte <kicad@jaseg.de> + * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#include "poisson_disk_sampling.h" + +#include "vec_grid.h" + +using namespace std; +using namespace vectorizer; + +sampling_fun vectorizer::get_sampler(enum grid_type type) { + switch(type) { + case POISSON_DISC: + return sample_poisson_disc; + case HEXGRID: + return sample_hexgrid; + case SQUAREGRID: + return sample_squaregrid; + default: + return sample_poisson_disc; + } +} + +vector<d2p> *vectorizer::sample_poisson_disc(double w, double h, double center_distance) { + d2p top_left {0, 0}; + d2p bottom_right {w, h}; + return new auto(thinks::PoissonDiskSampling(center_distance, top_left, bottom_right)); +} + +vector<d2p> *vectorizer::sample_hexgrid(double w, double h, double center_distance) { + double radius = center_distance / 2.0 / (sqrt(3) / 2.0); /* radius of hexagon */ + double pitch_v = 1.5 * radius; + double pitch_h = center_distance; + + /* offset of first hexagon to make sure the entire area is covered. We use slightly larger values here to avoid + * corner cases during clipping in the voronoi map generator. The inaccuracies this causes at the edges are + * negligible. */ + double off_x = 0.5001 * center_distance; + double off_y = 0.5001 * radius; + + /* NOTE: The voronoi generator is not quite stable when points lie outside the bounds. Thus, floor(). */ + long long int points_x = floor(w / pitch_h); + long long int points_y = floor(h / pitch_v); + + vector<d2p> *out = new vector<d2p>(); + out->reserve((points_x+1) * points_y); + + /* This may generate up to one extra row of points. We don't care since these points will simply be clipped during + * voronoi map generation. */ + for (long long int y_i=0; y_i<points_y; y_i+=2) { + for (long long int x_i=0; x_i<points_x; x_i++) { /* allow one extra point to compensate for row shift */ + out->push_back(d2p{off_x + x_i * pitch_h, off_y + y_i * pitch_v}); + } + + for (long long int x_i=0; x_i<points_x+1; x_i++) { /* allow one extra point to compensate for row shift */ + out->push_back(d2p{off_x + (x_i - 0.5) * pitch_h, off_y + (y_i + 1) * pitch_v}); + } + } + + return out; +} + +vector<d2p> *vectorizer::sample_squaregrid(double w, double h, double center_distance) { + /* offset of first square to make sure the entire area is covered. We use slightly larger values here to avoid + * corner cases during clipping in the voronoi map generator. The inaccuracies this causes at the edges are + * negligible. */ + double off_x = 0.5 * center_distance; + double off_y = 0.5 * center_distance; + + long long int points_x = ceil(w / center_distance); + long long int points_y = ceil(h / center_distance); + + vector<d2p> *out = new vector<d2p>(); + out->reserve(points_x * points_y); + + for (long long int y_i=0; y_i<points_y; y_i++) { + for (long long int x_i=0; x_i<points_x; x_i++) { + out->push_back({off_x + x_i*center_distance, off_y + y_i*center_distance}); + } + } + + return out; +} + diff --git a/src/vec_grid.h b/src/vec_grid.h new file mode 100644 index 0000000..cdd61df --- /dev/null +++ b/src/vec_grid.h @@ -0,0 +1,52 @@ +/* + * This program source code file is part of KICAD, a free EDA CAD application. + * + * Copyright (C) 2021 Jan Sebastian Götte <kicad@jaseg.de> + * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, you may find one here: + * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html + * or you may search the http://www.gnu.org website for the version 2 license, + * or you may write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA + */ + +#ifndef VEC_GRID_H +#define VEC_GRID_H + +#include <array> +#include <vector> +#include <functional> + +namespace vectorizer { + +typedef std::array<double, 2> d2p; + +enum grid_type { + POISSON_DISC, + HEXGRID, + SQUAREGRID +}; + +typedef std::function<std::vector<d2p> *(double, double, double)> sampling_fun; + +sampling_fun get_sampler(enum grid_type type); + +std::vector<d2p> *sample_poisson_disc(double w, double h, double center_distance); +std::vector<d2p> *sample_hexgrid(double w, double h, double center_distance); +std::vector<d2p> *sample_squaregrid(double w, double h, double center_distance); + +} /* namespace vectorizer */ + +#endif /* VEC_GRID_H */ |