From 3cee5d4f018be6d4f494fb2ab1018fbf53b2f15f Mon Sep 17 00:00:00 2001 From: jaseg Date: Tue, 26 Jan 2021 23:21:31 +0100 Subject: The cavalier flattener works!!1! --- .gitmodules | 3 ++ Makefile | 22 +++++---- include/gerbolyze.hpp | 20 ++++++++ src/main.cpp | 10 ++-- src/out_flattener.cpp | 115 +++++++++++++++++++++++++++++++++++----------- src/svg_geom.cpp | 31 ++++++++----- src/svg_geom.h | 2 +- upstream/CavalierContours | 1 + 8 files changed, 151 insertions(+), 53 deletions(-) create mode 160000 upstream/CavalierContours diff --git a/.gitmodules b/.gitmodules index dfae908..36615a6 100644 --- a/.gitmodules +++ b/.gitmodules @@ -10,3 +10,6 @@ [submodule "upstream/argagg"] path = upstream/argagg url = https://github.com/vietjtnguyen/argagg +[submodule "upstream/CavalierContours"] + path = upstream/CavalierContours + url = https://github.com/jbuckmccready/CavalierContours diff --git a/Makefile b/Makefile index 074c6b8..ed71204 100644 --- a/Makefile +++ b/Makefile @@ -16,17 +16,21 @@ SOURCES := src/svg_color.cpp \ src/main.cpp \ src/out_svg.cpp \ src/out_gerber.cpp \ + src/out_flattener.cpp \ src/lambda_sink.cpp \ -SOURCES += upstream/clipper-6.4.2/cpp/clipper.cpp upstream/clipper-6.4.2/cpp/cpp_cairo/cairo_clipper.cpp -CLIPPER_INCLUDES := -Iupstream/clipper-6.4.2/cpp -Iupstream/clipper-6.4.2/cpp/cpp_cairo/ -VORONOI_INCLUDES := -Iupstream/voronoi/src -POISSON_INCLUDES := -Iupstream/poisson-disk-sampling/thinks/poisson_disk_sampling/ -BASE64_INCLUDES := -Iupstream/cpp-base64 -ARGAGG_INCLUDES := -Iupstream/argagg/include/argagg -INCLUDES := -Iinclude -Isrc $(CLIPPER_INCLUDES) $(VORONOI_INCLUDES) $(POISSON_INCLUDES) $(BASE64_INCLUDES) $(ARGAGG_INCLUDES) +CLIPPER_SOURCES ?= upstream/clipper-6.4.2/cpp/clipper.cpp upstream/clipper-6.4.2/cpp/cpp_cairo/cairo_clipper.cpp +CLIPPER_INCLUDES ?= -Iupstream/clipper-6.4.2/cpp -Iupstream/clipper-6.4.2/cpp/cpp_cairo/ +VORONOI_INCLUDES ?= -Iupstream/voronoi/src +POISSON_INCLUDES ?= -Iupstream/poisson-disk-sampling/thinks/poisson_disk_sampling/ +BASE64_INCLUDES ?= -Iupstream/cpp-base64 +ARGAGG_INCLUDES ?= -Iupstream/argagg/include/argagg +CAVC_INCLUDES ?= -Iupstream/CavalierContours/include/cavc/ -CXXFLAGS := -std=c++2a -g -Wall -Wextra +SOURCES += $(CLIPPER_SOURCES) +INCLUDES := -Iinclude -Isrc $(CLIPPER_INCLUDES) $(VORONOI_INCLUDES) $(POISSON_INCLUDES) $(BASE64_INCLUDES) $(ARGAGG_INCLUDES) $(CAVC_INCLUDES) + +CXXFLAGS := -std=c++2a -g -Wall -Wextra -O0 CXXFLAGS += $(shell $(PKG_CONFIG) --cflags pangocairo pugixml opencv4) LDFLAGS := -lm -lc -lstdc++ @@ -41,7 +45,7 @@ $(BUILDDIR)/%.o: %.cpp @mkdir -p $(dir $@) $(CXX) -c $(CXXFLAGS) $(CXXFLAGS) $(INCLUDES) -o $@ $^ -$(BUILDDIR)/svg-render: $(SOURCES:%.cpp=$(BUILDDIR)/%.o) $(BUILDDIR)/upstream/cpp-base64/base64.o $(CLIPPER_SOURCES:.cpp=.o) +$(BUILDDIR)/svg-render: $(SOURCES:%.cpp=$(BUILDDIR)/%.o) $(BUILDDIR)/upstream/cpp-base64/base64.o @mkdir -p $(dir $@) $(CXX) $(CXXFLAGS) $(LDFLAGS) -o $@ $^ diff --git a/include/gerbolyze.hpp b/include/gerbolyze.hpp index ac3d6ad..03ac42d 100644 --- a/include/gerbolyze.hpp +++ b/include/gerbolyze.hpp @@ -38,15 +38,33 @@ namespace gerbolyze { class PolygonSink { public: + virtual ~PolygonSink() {} virtual void header(d2p origin, d2p size) {(void) origin; (void) size;} virtual PolygonSink &operator<<(const Polygon &poly) = 0; virtual PolygonSink &operator<<(GerberPolarityToken pol) = 0; virtual void footer() {} }; + class Flattener_D; + class Flattener : public PolygonSink { + public: + Flattener(PolygonSink &sink); + virtual ~Flattener(); + virtual void header(d2p origin, d2p size); + virtual Flattener &operator<<(const Polygon &poly); + virtual Flattener &operator<<(GerberPolarityToken pol); + virtual void footer(); + + private: + PolygonSink &m_sink; + GerberPolarityToken m_current_polarity = GRB_POL_DARK; + Flattener_D *d; + }; + class StreamPolygonSink : public PolygonSink { public: StreamPolygonSink(std::ostream &out, bool only_polys=false) : m_only_polys(only_polys), m_out(out) {} + virtual ~StreamPolygonSink() {} virtual void header(d2p origin, d2p size) { if (!m_only_polys) header_impl(origin, size); } virtual void footer() { if (!m_only_polys) { footer_impl(); } m_out.flush(); } @@ -130,6 +148,7 @@ namespace gerbolyze { class SimpleGerberOutput : public StreamPolygonSink { public: SimpleGerberOutput(std::ostream &out, bool only_polys=false, int digits_int=4, int digits_frac=6, d2p offset={0,0}); + virtual ~SimpleGerberOutput() {} virtual SimpleGerberOutput &operator<<(const Polygon &poly); virtual SimpleGerberOutput &operator<<(GerberPolarityToken pol); virtual void header_impl(d2p origin, d2p size); @@ -147,6 +166,7 @@ namespace gerbolyze { class SimpleSVGOutput : public StreamPolygonSink { public: SimpleSVGOutput(std::ostream &out, bool only_polys=false, int digits_frac=6, std::string dark_color="#000000", std::string clear_color="#ffffff"); + virtual ~SimpleSVGOutput() {} virtual SimpleSVGOutput &operator<<(const Polygon &poly); virtual SimpleSVGOutput &operator<<(GerberPolarityToken pol); virtual void header_impl(d2p origin, d2p size); diff --git a/src/main.cpp b/src/main.cpp index 8656662..773b1a4 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -35,7 +35,7 @@ int main(int argc, char **argv) { {"no_header", {"--no-header"}, "Do not export output format header/footer, only export the primitives themselves", 0}, - {"flatten", {"-f", "--flatten"}, + {"flatten", {"--flatten"}, "Flatten output so it only consists of non-overlapping white polygons. This perform composition at the vector level. Potentially slow.", 0}, }}; @@ -122,7 +122,8 @@ int main(int argc, char **argv) { string fmt = args["ofmt"] ? args["ofmt"] : "gerber"; transform(fmt.begin(), fmt.end(), fmt.begin(), [](unsigned char c){ return std::tolower(c); }); - PolygonSink *sink; + PolygonSink *sink = nullptr; + PolygonSink *flattener = nullptr; if (fmt == "svg") { string dark_color = args["svg_dark_color"] ? args["svg_dark_color"] : "#000000"; string clear_color = args["svg_clear_color"] ? args["svg_clear_color"] : "#ffffff"; @@ -138,10 +139,11 @@ int main(int argc, char **argv) { return EXIT_FAILURE; } - if (args["version"]) { + if (args["flatten"]) { + flattener = new Flattener(*sink); } - doc.render(*sink); + doc.render(flattener ? *flattener : *sink); return EXIT_SUCCESS; } diff --git a/src/out_flattener.cpp b/src/out_flattener.cpp index edb93b7..9bc4cbe 100644 --- a/src/out_flattener.cpp +++ b/src/out_flattener.cpp @@ -21,24 +21,40 @@ #include #include #include -#include #include #include #include +#include "polylinecombine.hpp" using namespace gerbolyze; using namespace std; +static void polygon_to_cavc (const Polygon &in, cavc::Polyline &out) { + for (auto &p : in) { + out.addVertex(p[0], p[1], 0); + } + out.isClosed() = true; /* sic! */ +} + +static void cavc_to_polygon (const cavc::Polyline &in, Polygon &out) { + for (auto &p : in.vertexes()) { + out.emplace_back(d2p{p.x(), p.y()}); + } +} + namespace gerbolyze { class Flattener_D { public: - ClipperLib::Clipper c; + vector> dark_polys; + + void add_dark_polygon(const Polygon &in) { + polygon_to_cavc(in, dark_polys.emplace_back()); + } }; } Flattener::Flattener(PolygonSink &sink) : m_sink(sink) { d = new Flattener_D(); - d->c.StrictlySimple(true); } Flattener::~Flattener() { @@ -49,6 +65,8 @@ void Flattener::header(d2p origin, d2p size) { m_sink.header(origin, size); } + + Flattener &Flattener::operator<<(GerberPolarityToken pol) { if (m_current_polarity != pol) { m_current_polarity = pol; @@ -58,42 +76,85 @@ Flattener &Flattener::operator<<(GerberPolarityToken pol) { } Flattener &Flattener::operator<<(const Polygon &poly) { - ClipperLib::Path le_path; - for (auto &p : poly) { - le_path.push_back({(ClipperLib::cInt)round(p[0] * clipper_scale), (ClipperLib::cInt)round(p[1] * clipper_scale)}); - } - - ClipperLib::Paths out; + static int i=0, j=0; if (m_current_polarity == GRB_POL_DARK) { - d->c.AddPath(le_path, ClipperLib::ptSubject, true); - d->c.Execute(ClipperLib::ctUnion, out, ClipperLib::pftNonZero); - + d->add_dark_polygon(poly); + cerr << "dark primitive " << i++ << endl; } else { /* clear */ - d->c.AddPath(le_path, ClipperLib::ptClip, true); - d->c.Execute(ClipperLib::ctDifference, out, ClipperLib::pftNonZero); - } + cerr << "clear primitive " << j++ << endl; + + cavc::Polyline sub; + polygon_to_cavc (poly, sub); + + vector> new_dark_polys; + new_dark_polys.reserve(d->dark_polys.size()); + + for (cavc::Polyline cavc_in : d->dark_polys) { + auto res = cavc::combinePolylines(cavc_in, sub, cavc::PlineCombineMode::Exclude); + + if (res.subtracted.size() == 0) { + for (auto &rem : res.remaining) { + new_dark_polys.push_back(std::move(rem)); + } + + } else { + assert (res.remaining.size() == 1); + assert (res.subtracted.size() == 1); + + auto &rem = res.remaining[0]; + auto &sub = res.subtracted[0]; + auto bbox = getExtents(rem); + + cavc::Polyline quad; + quad.addVertex(bbox.xMin, bbox.yMin, 0); + if (sub.vertexes()[0].x() < sub.vertexes()[1].x()) { + quad.addVertex(sub.vertexes()[0]); + quad.addVertex(sub.vertexes()[1]); + } else { + quad.addVertex(sub.vertexes()[1]); + quad.addVertex(sub.vertexes()[0]); + } + quad.addVertex(bbox.xMax, bbox.yMin, 0); + quad.isClosed() = true; /* sic! */ + + auto res2 = cavc::combinePolylines(rem, quad, cavc::PlineCombineMode::Exclude); + assert (res2.subtracted.size() == 0); + + for (auto &rem : res2.remaining) { + auto res3 = cavc::combinePolylines(rem, sub, cavc::PlineCombineMode::Exclude); + assert (res3.subtracted.size() == 0); + for (auto &p : res3.remaining) { + new_dark_polys.push_back(std::move(p)); + } + } + + auto res4 = cavc::combinePolylines(rem, quad, cavc::PlineCombineMode::Intersect); + assert (res4.subtracted.size() == 0); + + for (auto &rem : res4.remaining) { + auto res5 = cavc::combinePolylines(rem, sub, cavc::PlineCombineMode::Exclude); + assert (res5.subtracted.size() == 0); + for (auto &p : res5.remaining) { + new_dark_polys.push_back(std::move(p)); + } + } + } + } - d->c.Clear(); - d->c.AddPaths(out, ClipperLib::ptSubject, true); + d->dark_polys = std::move(new_dark_polys); + } return *this; } void Flattener::footer() { - ClipperLib::PolyTree t_out; - d->c.Execute(ClipperLib::ctDifference, t_out, ClipperLib::pftNonZero); - d->c.Clear(); - m_sink << GRB_POL_DARK; - ClipperLib::Paths out; - cerr << "deholing" << endl; - dehole_polytree(t_out, out); - for (auto &poly : out) { + for (auto &poly : d->dark_polys) { Polygon poly_out; - for (auto &p : poly) { - poly_out.push_back({p.X / clipper_scale, p.Y / clipper_scale}); + for (auto &p : poly.vertexes()) { + poly_out.emplace_back(d2p{p.x(), p.y()}); } m_sink << poly_out; } diff --git a/src/svg_geom.cpp b/src/svg_geom.cpp index e152f3a..385e848 100644 --- a/src/svg_geom.cpp +++ b/src/svg_geom.cpp @@ -21,6 +21,7 @@ #include #include #include +#include #include #include #include "svg_import_defs.h" @@ -90,11 +91,7 @@ enum ClipperLib::JoinType gerbolyze::clipper_join_type(const pugi::xml_node &nod 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 gerbolyze::dehole_polytree(PolyNode &ptree, Paths &out) { +static void dehole_polytree_worker(PolyNode &ptree, Paths &out, queue &todo) { for (int i=0; iIsHole()); if (child->ChildCount() > 0) { - dehole_polytree(*child, out); + dehole_polytree_worker(*child, out, todo); } } @@ -129,19 +126,29 @@ void gerbolyze::dehole_polytree(PolyNode &ptree, Paths &out) { 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); + c.Execute(ctDifference, todo.emplace(), pftNonZero); + c.Execute(ctIntersection, todo.emplace(), pftNonZero); } } } +/* 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 gerbolyze::dehole_polytree(PolyTree &ptree, Paths &out) { + queue todo; + dehole_polytree_worker(ptree, out, todo); + while (!todo.empty()) { + dehole_polytree_worker(todo.front(), out, todo); + todo.pop(); + } +} + + /* Intersect two clip paths. Both must share a coordinate system. */ void gerbolyze::combine_clip_paths(Paths &in_a, Paths &in_b, Paths &out) { Clipper c; diff --git a/src/svg_geom.h b/src/svg_geom.h index 1763d52..5f00479 100644 --- a/src/svg_geom.h +++ b/src/svg_geom.h @@ -28,7 +28,7 @@ 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 dehole_polytree(ClipperLib::PolyTree &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); diff --git a/upstream/CavalierContours b/upstream/CavalierContours new file mode 160000 index 0000000..b955785 --- /dev/null +++ b/upstream/CavalierContours @@ -0,0 +1 @@ +Subproject commit b955785cc3db9689704d6135cbb60177fab835bb -- cgit