Add beginnings of minimalist contour tracing code

21 files changed, 459 insertions, 0 deletions

diff --git a/.gitmodules b/.gitmodules
index e42d3c4..deedaea 100644
--- a/.gitmodules
+++ b/.gitmodules
@@ -16,3 +16,9 @@
 [submodule "upstream/subprocess.h"]
 	path = upstream/subprocess.h
 	url = https://github.com/sheredom/subprocess.h
+[submodule "svg-flatten/upstream/minunit"]
+	path = upstream/minunit
+	url = https://github.com/siu/minunit
+[submodule "upstream/stb"]
+	path = upstream/stb
+	url = https://github.com/nothings/stb
diff --git a/svg-flatten/src/nopencv.cpp b/svg-flatten/src/nopencv.cpp
new file mode 100644
index 0000000..77c6cc6
--- /dev/null
+++ b/svg-flatten/src/nopencv.cpp
@@ -0,0 +1,157 @@
+
+#include <iostream>
+
+#include "nopencv.hpp"
+
+using namespace gerbolyze;
+using namespace gerbolyze::nopencv;
+
+/* directions:
+ *        0
+ *   7         1
+ *        ^   
+ *        |
+ * 6 <--- X ---> 2
+ *        |
+ *        v
+ *   5         3
+ *        4
+ *
+ */
+enum Direction {
+    D_N,
+    D_NE,
+    D_E,
+    D_SE,
+    D_S,
+    D_SW,
+    D_W,
+    D_NW
+};
+
+//const char * const dir_str[8] = { "N", "NE", "E", "SE", "S", "SW", "W", "NW" };
+
+static struct {
+    int x;
+    int y;
+} dir_to_coords[8] = {{0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}};
+
+static Direction flip_direction[8] = {
+    D_S,
+    D_SW,
+    D_W,
+    D_NW,
+    D_N,
+    D_NE,
+    D_E,
+    D_SE
+};
+
+static void follow(gerbolyze::nopencv::Image32 img, int start_x, int start_y, Direction initial_direction, int nbd, int connectivity, Polygon &poly) {
+
+    //cerr << "follow " << start_x << " " << start_y << " | dir=" << dir_str[initial_direction] << " nbd=" << nbd << " conn=" << connectivity << endl;
+    int dir_inc = (connectivity == 4) ? 2 : 1;
+
+    int probe_x, probe_y;
+
+    /* homing run: find starting point for algorithm steps below. */
+    bool found = false;
+    int k;
+    for (k=initial_direction; k<initial_direction+8; k += dir_inc) {
+        probe_x = start_x + dir_to_coords[k % 8].x;
+        probe_y = start_y + dir_to_coords[k % 8].y;
+
+        if (img.at_default(probe_x, probe_y) != 0) {
+            found = true;
+            break;
+        }
+    }
+
+    if (!found) { /* No nonzero pixels found. This is a single-pixel contour */
+        img.at(start_x, start_y) = nbd;
+        poly.emplace_back(d2p{(double)start_x,   (double)start_y});
+        poly.emplace_back(d2p{(double)start_x+1, (double)start_y});
+        poly.emplace_back(d2p{(double)start_x+1, (double)start_y+1});
+        poly.emplace_back(d2p{(double)start_x,   (double)start_y+1});
+        return;
+    }
+
+    /* starting point found. */
+    int current_direction = k % 8;
+    int start_direction = current_direction;
+    int center_x = start_x, center_y = start_y;
+    //cerr << "  init: " << center_x << " " << center_y << " / " << dir_str[current_direction] << endl;
+
+    do {
+        bool flag = false;
+        for (k = current_direction + 8 - dir_inc; k >= current_direction; k -= dir_inc) {
+            probe_x = center_x + dir_to_coords[k % 8].x;
+            probe_y = center_y + dir_to_coords[k % 8].y;
+            if (k%8 == D_E)
+                flag = true;
+
+            if (img.at_default(probe_x, probe_y) != 0) {
+                break;
+            }
+        }
+
+        int set_val = 0;
+        if (flag && img.at_default(center_x+1, center_y) == 0) {
+            img.at(center_x, center_y) = -nbd;
+            set_val = -nbd;
+        } else if (img.at(center_x, center_y) == 1) {
+            img.at(center_x, center_y) = nbd;
+            set_val = nbd;
+        }
+
+        for (int l = (current_direction + 8 - 2 + 1) / 2 * 2; l > k; l -= dir_inc) {
+            switch (l%8) {
+                case 0: poly.emplace_back(d2p{(double)center_x,   (double)center_y}); break;
+                case 2: poly.emplace_back(d2p{(double)center_x+1, (double)center_y}); break;
+                case 4: poly.emplace_back(d2p{(double)center_x+1, (double)center_y+1}); break;
+                case 6: poly.emplace_back(d2p{(double)center_x,   (double)center_y+1}); break;
+            }
+        }
+
+        center_x = probe_x;
+        center_y = probe_y;
+        current_direction = flip_direction[k % 8];
+
+        //cerr << "  " << center_x << " " << center_y << " / " << dir_str[current_direction] << " -> " << set_val << endl;
+    } while (center_x != start_x || center_y != start_y || current_direction != start_direction);
+}
+
+
+void gerbolyze::nopencv::find_blobs(gerbolyze::nopencv::Image32 img, gerbolyze::nopencv::ContourCallback cb) {
+    int nbd = 1;
+    Polygon poly;
+    for (int y=0; y<img.rows(); y++) {
+        for (int x=0; x<img.cols(); x++) {
+            int val_xy = img.at(x, y);
+            /* Note: outer borders are followed with 8-connectivity, hole borders with 4-connectivity. This prevents
+             * incorrect results in this case:
+             *
+             *    1   1   1 | 0   0   0
+             *              |
+             *    1   1   1 | 0   0   0
+             *    ----------+---------- <== Here
+             *    0   0   0 | 1   1   1
+             *              |
+             *    0   0   0 | 1   1   1
+             */
+            if (img.at_default(x-1, y) == 0 && val_xy == 1) { /* outer border starting point */
+                nbd += 1;
+                follow(img, x, y, D_W, nbd, 8, poly);
+                cb(poly, CP_CONTOUR);
+                poly.clear();
+
+            } else if (val_xy >= 1 && img.at_default(x+1, y) == 0) { /* hole border starting point */
+                nbd += 1;
+                follow(img, x, y, D_E, nbd, 4, poly);
+                cb(poly, CP_HOLE);
+                poly.clear();
+            }
+        }
+    }
+}
+
diff --git a/svg-flatten/src/nopencv.hpp b/svg-flatten/src/nopencv.hpp
new file mode 100644
index 0000000..b749808
--- /dev/null
+++ b/svg-flatten/src/nopencv.hpp
@@ -0,0 +1,98 @@
+/*
+ * This file is part of gerbolyze, a vector image preprocessing toolchain 
+ * Copyright (C) 2021 Jan Sebastian Götte <gerbolyze@jaseg.de>
+ * 
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation, either version 3 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 Affero General Public License for more details.
+ * 
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
+#pragma once
+
+#include <array>
+#include <string>
+#include <sstream>
+#include <cmath>
+#include <algorithm>
+#include <assert.h>
+
+#include "geom2d.hpp"
+
+using namespace std;
+
+namespace gerbolyze {
+    namespace nopencv {
+
+        enum ContourPolarity {
+            CP_CONTOUR,
+            CP_HOLE
+        };
+
+        typedef std::function<void(Polygon, ContourPolarity)> ContourCallback;
+
+        class Image32 {
+        public:
+            Image32(int size_x, int size_y, const int32_t *data=nullptr) {
+                assert(size_x > 0 && size_x < 100000);
+                assert(size_y > 0 && size_y < 100000);
+                m_data = new int32_t[size_x * size_y] { 0 };
+                m_rows = size_y;
+                m_cols = size_x;
+                if (data != nullptr) {
+                    memcpy(m_data, data, sizeof(int32_t) * size_x * size_y);
+                }
+            }
+
+            Image32(const Image32 &other) : Image32(other.cols(), other.rows(), other.ptr()) {}
+
+            ~Image32() {
+                delete m_data;
+            }
+            
+            int32_t &at(int x, int y) {
+                assert(x >= 0 && y >= 0 && x < m_cols && y < m_rows);
+                assert(m_data != nullptr);
+
+                return m_data[y*m_cols + x];
+            };
+
+            const int32_t &at(int x, int y) const {
+                assert(x >= 0 && y >= 0 && x < m_cols && y < m_rows);
+                assert(m_data != nullptr);
+
+                return m_data[y*m_cols + x];
+            };
+
+            int32_t at_default(int x, int y, int32_t default_value=0) const {
+                assert(m_data != nullptr);
+
+                if (x >= 0 && y >= 0 && x < m_cols && y < m_rows) {
+                    return at(x, y);
+
+                } else {
+                    return default_value;
+                }
+            };
+
+            int rows() const { return m_rows; }
+            int cols() const { return m_cols; }
+            const int32_t *ptr() const { return m_data; }
+
+        private:
+            int32_t *m_data = nullptr;
+            int m_rows=0, m_cols=0;
+        };
+
+        void find_blobs(Image32 img, ContourCallback cb);
+    }
+}
+
diff --git a/svg-flatten/src/nopencv_test.cpp b/svg-flatten/src/nopencv_test.cpp
new file mode 100644
index 0000000..cc1c988
--- /dev/null
+++ b/svg-flatten/src/nopencv_test.cpp
@@ -0,0 +1,198 @@
+
+#include <iostream>
+#include <fstream>
+#include <iomanip>
+#include <cmath>
+#include <filesystem>
+
+#include "nopencv.hpp"
+
+#include <subprocess.h>
+#include <minunit.h>
+
+#define STB_IMAGE_IMPLEMENTATION
+#include "stb_image.h"
+
+using namespace gerbolyze;
+using namespace gerbolyze::nopencv;
+
+char msg[1024];
+
+MU_TEST(test_complex_example_from_paper) {
+    int32_t img_data[6*9] = {
+        0, 0, 0, 0, 0, 0, 0, 0, 0,
+        0, 1, 1, 1, 1, 1, 1, 1, 0,
+        0, 1, 0, 0, 1, 0, 0, 1, 0,
+        0, 1, 0, 0, 1, 0, 0, 1, 0,
+        0, 1, 1, 1, 1, 1, 1, 1, 0,
+        0, 0, 0, 0, 0, 0, 0, 0, 0,
+    };
+    Image32 test_img(9, 6, static_cast<int*>(img_data));
+
+    const Polygon expected_polys[3] = {
+        {
+            {1,1}, {1,2}, {1,3}, {1,4}, {1,5},
+            {2,5}, {3,5}, {4,5}, {5,5}, {6,5}, {7,5}, {8,5},
+            {8,4}, {8,3}, {8,2}, {8,1},
+            {7,1}, {6,1}, {5,1}, {4,1}, {3,1}, {2,1}
+        },
+        {
+            {2,2}, {2,3}, {2,4},
+            {3,4}, {4,4},
+            {4,3}, {4,2},
+            {3,2}
+        },
+        {
+            {5,2}, {5,3}, {5,4},
+            {6,4}, {7,4},
+            {7,3}, {7,2},
+            {6,2}
+        }
+    };
+
+    const ContourPolarity expected_polarities[3] = {CP_CONTOUR, CP_HOLE, CP_HOLE};
+    
+    int invocation_count = 0;
+    gerbolyze::nopencv::find_blobs(test_img, [&invocation_count, &expected_polarities, &expected_polys](Polygon poly, ContourPolarity pol) {
+            invocation_count += 1;
+            mu_assert((invocation_count <= 3), "Too many contours returned"); 
+
+            mu_assert(poly.size() > 0, "Empty contour returned");
+            mu_assert_int_eq(pol, expected_polarities[invocation_count-1]);
+
+            d2p last;
+            bool first = true;
+            Polygon exp = expected_polys[invocation_count-1];
+            //cout << "poly: ";
+            for (d2p &p : poly) {
+                //cout << "(" << p[0] << ", " << p[1] << "), ";
+                if (!first) {
+                    mu_assert((fabs(p[0] - last[0]) + fabs(p[1] - last[1]) == 1), "Subsequent contour points have distance other than one");
+                    mu_assert(find(exp.begin(), exp.end(), p) != exp.end(), "Got unexpected contour point");
+                }
+                last = p;
+            }
+            //cout << endl;
+        });
+    mu_assert_int_eq(3, invocation_count);
+
+    int32_t tpl[6*9] = {
+        0, 0, 0, 0, 0, 0, 0, 0, 0,
+        0, 2, 2, 2, 2, 2, 2,-2, 0,
+        0,-3, 0, 0,-4, 0, 0,-2, 0,
+        0,-3, 0, 0,-4, 0, 0,-2, 0,
+        0, 2, 2, 2, 2, 2, 2,-2, 0,
+        0, 0, 0, 0, 0, 0, 0, 0, 0,
+    };
+
+
+    for (int y=0; y<6; y++) {
+        for (int x=0; x<9; x++) {
+            int a = test_img.at(x, y), b = tpl[y*9+x];
+            if (a != b) {
+                cout << "Result:" << endl;
+                cout << "    ";
+                for (int x=0; x<9; x++) {
+                    cout << x << "  ";
+                }
+                cout << endl;
+                cout << "    ";
+                for (int x=0; x<9; x++) {
+                    cout << "---";
+                }
+                cout << endl;
+                for (int y=0; y<6; y++) {
+                    cout << y << " | ";
+                    for (int x=0; x<9; x++) {
+                        cout << setfill(' ') << setw(2) << test_img.at(x, y) << " ";
+                    }
+                    cout << endl;
+                }
+
+                snprintf(msg, sizeof(msg), "Result does not match template @(%d, %d): %d != %d\n", x, y, a, b);
+                mu_fail(msg);
+            }
+        }
+    }
+}
+
+MU_TEST(test_round_trip) {
+    int x, y;
+    uint8_t *data = stbi_load("testdata/paper-example.png", &x, &y, nullptr, 1);
+    Image32 ref_img(x, y);
+    for (int cy=0; cy<y; cy++) {
+        for (int cx=0; cx<x; cx++) {
+            ref_img.at(cx, cy) = data[cy*x + cx];
+        }
+    }
+    stbi_image_free(data);
+    Image32 ref_img_copy(ref_img);
+
+    filesystem::path tmp_svg = { filesystem::temp_directory_path() /= (std::tmpnam(nullptr) + string(".svg")) };
+    filesystem::path tmp_png = { filesystem::temp_directory_path() /= (std::tmpnam(nullptr) + string(".png")) };
+    ofstream svg(tmp_svg.c_str());
+
+    svg << "<svg width=\"" << x << "px\" height=\"" << y << "px\" viewBox=\"0 0 "
+        << x << " " << y << "\" "
+        << "xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">" << endl;
+    svg << "<rect width=\"100%\" height=\"100%\" fill=\"black\">" << endl;
+
+    gerbolyze::nopencv::find_blobs(ref_img, [&svg](Polygon poly, ContourPolarity pol) {
+        mu_assert(poly.size() > 0, "Empty contour returned");
+        mu_assert(poly.size() > 2, "Contour has less than three points, no area");
+        mu_assert(pol == CP_CONTOUR || pol == CP_HOLE, "Contour has invalid polarity");
+
+        svg << "<path fill=\"" << (pol == CP_HOLE ? "black" : "white") << "\" d=\"";
+        svg << "M " << poly[0][0] << " " << poly[0][1];
+        for (size_t i=1; i<poly.size(); i++) {
+            svg << " L " << poly[i][0] << " " << poly[i][1];
+        }
+        svg << " Z\">" << endl;
+    });
+    svg << "</svg>" << endl;
+    svg.close();
+
+    const char *command_line[] = {"resvg", tmp_svg.c_str(), tmp_png.c_str()};
+    struct subprocess_s subprocess;
+    int rc = subprocess_create(command_line, subprocess_option_inherit_environment, &subprocess);
+    mu_assert_int_eq(rc, 0);
+
+    int resvg_rc = -1;
+    rc = subprocess_join(&subprocess, &resvg_rc);
+    mu_assert_int_eq(rc, 0);
+    mu_assert_int_eq(resvg_rc, 0);
+
+    rc = subprocess_destroy(&subprocess);
+    mu_assert_int_eq(rc, 0);
+
+    int out_x, out_y;
+    uint8_t *out_data = stbi_load(tmp_png.c_str(), &out_x, &out_y, nullptr, 1);
+    mu_assert_int_eq(out_x, x);
+    mu_assert_int_eq(out_y, y);
+
+    for (int cy=0; cy<y; cy++) {
+        for (int cx=0; cx<x; cx++) {
+            int actual = out_data[cy*x + cx];
+            int expected = ref_img_copy.at(x, y);
+            if (actual != expected) {
+                snprintf(msg, sizeof(msg), "Result does not match input @(%d, %d): %d != %d\n", cx, cy, actual, expected);
+                mu_fail(msg);
+            }
+        }
+    }
+    stbi_image_free(out_data);
+}
+
+MU_TEST_SUITE(nopencv_contours_suite) {
+    MU_RUN_TEST(test_complex_example_from_paper);
+//    MU_RUN_TEST(test_round_trip);
+}
+
+int main(int argc, char **argv) {
+    (void)argc;
+    (void)argv;
+
+    MU_RUN_SUITE(nopencv_contours_suite);
+    MU_REPORT();
+    return MU_EXIT_CODE;
+}
diff --git a/svg-flatten/testdata/blank.png b/svg-flatten/testdata/blank.png
new file mode 100644
index 0000000..8dd7068
--- /dev/null
+++ b/svg-flatten/testdata/blank.png
diff --git a/svg-flatten/testdata/blob-border-w.png b/svg-flatten/testdata/blob-border-w.png
new file mode 100644
index 0000000..b904783
--- /dev/null
+++ b/svg-flatten/testdata/blob-border-w.png
diff --git a/svg-flatten/testdata/blobs-borders.png b/svg-flatten/testdata/blobs-borders.png
new file mode 100644
index 0000000..e183bd4
--- /dev/null
+++ b/svg-flatten/testdata/blobs-borders.png
diff --git a/svg-flatten/testdata/blobs-corners.png b/svg-flatten/testdata/blobs-corners.png
new file mode 100644
index 0000000..d2bfb45
--- /dev/null
+++ b/svg-flatten/testdata/blobs-corners.png
diff --git a/svg-flatten/testdata/blobs-crossing.png b/svg-flatten/testdata/blobs-crossing.png
new file mode 100644
index 0000000..30e4214
--- /dev/null
+++ b/svg-flatten/testdata/blobs-crossing.png
diff --git a/svg-flatten/testdata/cross.png b/svg-flatten/testdata/cross.png
new file mode 100644
index 0000000..7936bde
--- /dev/null
+++ b/svg-flatten/testdata/cross.png
diff --git a/svg-flatten/testdata/letter-e.png b/svg-flatten/testdata/letter-e.png
new file mode 100644
index 0000000..141f187
--- /dev/null
+++ b/svg-flatten/testdata/letter-e.png
diff --git a/svg-flatten/testdata/paper-example-inv.png b/svg-flatten/testdata/paper-example-inv.png
new file mode 100644
index 0000000..64250f1
--- /dev/null
+++ b/svg-flatten/testdata/paper-example-inv.png
diff --git a/svg-flatten/testdata/paper-example.png b/svg-flatten/testdata/paper-example.png
new file mode 100644
index 0000000..a724556
--- /dev/null
+++ b/svg-flatten/testdata/paper-example.png
diff --git a/svg-flatten/testdata/single-px-inv.png b/svg-flatten/testdata/single-px-inv.png
new file mode 100644
index 0000000..fd1223e
--- /dev/null
+++ b/svg-flatten/testdata/single-px-inv.png
diff --git a/svg-flatten/testdata/single-px.png b/svg-flatten/testdata/single-px.png
new file mode 100644
index 0000000..22228fd
--- /dev/null
+++ b/svg-flatten/testdata/single-px.png
diff --git a/svg-flatten/testdata/two-blobs.png b/svg-flatten/testdata/two-blobs.png
new file mode 100644
index 0000000..bc2d549
--- /dev/null
+++ b/svg-flatten/testdata/two-blobs.png
diff --git a/svg-flatten/testdata/two-px-inv.png b/svg-flatten/testdata/two-px-inv.png
new file mode 100644
index 0000000..2768d0f
--- /dev/null
+++ b/svg-flatten/testdata/two-px-inv.png
diff --git a/svg-flatten/testdata/two-px.png b/svg-flatten/testdata/two-px.png
new file mode 100644
index 0000000..90db5e6
--- /dev/null
+++ b/svg-flatten/testdata/two-px.png
diff --git a/svg-flatten/testdata/white.png b/svg-flatten/testdata/white.png
new file mode 100644
index 0000000..efe9983
--- /dev/null
+++ b/svg-flatten/testdata/white.png
diff --git a/upstream/minunit b/upstream/minunit
new file mode 160000
+Subproject b15ad0ae28f1a7a43881ea17defb0a4367d9582
diff --git a/upstream/stb b/upstream/stb
new file mode 160000
+Subproject c9064e317699d2e495f36ba4f9ac037e88ee371