The cavalier flattener works!!1!

8 files changed, 150 insertions, 53 deletions

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 <string>
 #include <iostream>
 #include <iomanip>
-#include <clipper.hpp>
 #include <gerbolyze.hpp>
 #include <svg_import_defs.h>
 #include <svg_geom.h>
+#include "polylinecombine.hpp"
 
 using namespace gerbolyze;
 using namespace std;
 
+static void polygon_to_cavc (const Polygon &in, cavc::Polyline<double> &out) {
+    for (auto &p : in) {
+        out.addVertex(p[0], p[1], 0);
+    }
+    out.isClosed() = true; /* sic! */
+}
+
+static void cavc_to_polygon (const cavc::Polyline<double> &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<cavc::Polyline<double>> 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<double> sub;
+        polygon_to_cavc (poly, sub);
+
+        vector<cavc::Polyline<double>> new_dark_polys;
+        new_dark_polys.reserve(d->dark_polys.size());
+
+        for (cavc::Polyline<double> 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<double> 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 <cmath>
 #include <string>
 #include <sstream>
+#include <queue>
 #include <assert.h>
 #include <cairo.h>
 #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<PolyTree> &todo) {
     for (int i=0; i<ptree.ChildCount(); i++) {
         PolyNode *nod = ptree.Childs[i];
         assert(nod);
@@ -107,7 +104,7 @@ void gerbolyze::dehole_polytree(PolyNode &ptree, Paths &out) {
             assert(child->IsHole());
 
             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<PolyTree> 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
+Subproject b955785cc3db9689704d6135cbb60177fab835b