summaryrefslogtreecommitdiffstats
path: root/src/trace
diff options
context:
space:
mode:
Diffstat (limited to 'src/trace')
-rw-r--r--src/trace/CMakeLists.txt33
-rw-r--r--src/trace/README18
-rw-r--r--src/trace/autotrace/inkscape-autotrace.cpp226
-rw-r--r--src/trace/autotrace/inkscape-autotrace.h61
-rw-r--r--src/trace/cielab.cpp216
-rw-r--r--src/trace/cielab.h106
-rw-r--r--src/trace/depixelize/inkscape-depixelize.cpp107
-rw-r--r--src/trace/depixelize/inkscape-depixelize.h60
-rw-r--r--src/trace/filterset.cpp272
-rw-r--r--src/trace/filterset.h39
-rw-r--r--src/trace/imagemap-gdk.cpp110
-rw-r--r--src/trace/imagemap-gdk.h27
-rw-r--r--src/trace/imagemap.cpp128
-rw-r--r--src/trace/imagemap.h91
-rw-r--r--src/trace/pool.h117
-rw-r--r--src/trace/potrace/bitmap.h118
-rw-r--r--src/trace/potrace/inkscape-potrace.cpp456
-rw-r--r--src/trace/potrace/inkscape-potrace.h140
-rw-r--r--src/trace/quantize.cpp555
-rw-r--r--src/trace/quantize.h28
-rw-r--r--src/trace/siox.cpp770
-rw-r--r--src/trace/siox.h219
-rw-r--r--src/trace/trace.cpp538
-rw-r--r--src/trace/trace.h103
24 files changed, 4538 insertions, 0 deletions
diff --git a/src/trace/CMakeLists.txt b/src/trace/CMakeLists.txt
new file mode 100644
index 0000000..bb98981
--- /dev/null
+++ b/src/trace/CMakeLists.txt
@@ -0,0 +1,33 @@
+# SPDX-License-Identifier: GPL-2.0-or-later
+set(trace_SRC
+ cielab.cpp
+ filterset.cpp
+ imagemap.cpp
+ imagemap-gdk.cpp
+ quantize.cpp
+ siox.cpp
+ trace.cpp
+
+ potrace/inkscape-potrace.cpp
+ autotrace/inkscape-autotrace.cpp
+ depixelize/inkscape-depixelize.cpp
+
+ # -------
+ # Headers
+ cielab.h
+ filterset.h
+ imagemap-gdk.h
+ imagemap.h
+ pool.h
+ quantize.h
+ siox.h
+ trace.h
+
+ potrace/bitmap.h
+ potrace/inkscape-potrace.h
+ autotrace/inkscape-autotrace.h
+ depixelize/inkscape-depixelize.h
+)
+
+add_inkscape_source("${trace_SRC}")
+
diff --git a/src/trace/README b/src/trace/README
new file mode 100644
index 0000000..f436aa0
--- /dev/null
+++ b/src/trace/README
@@ -0,0 +1,18 @@
+
+This directory contains code for converting bitmap images to vector images.
+The subdirectories contain code for the three tracers used in Inkscape: potrace
+(external dependency), autotrace, and libdepixelize (currently in src/3rdparty).
+
+
+To do:
+
+* Think about conceptually changing how the tracing works: Ideally, it should
+ be three steps clearly separated:
+ 1/ Preprocessing (color reduction, blurring, background removing, image
+ inversion...)
+ 2/ Tracing the preprocessed image, using some tracing engine
+ 3/ Post-processing (suppressing speckles, optimizing paths...)
+
+ The main problem is that the tracing engine sometimes *also* does 1 and 3, so
+ there is some discussion to have whether this can be done.
+
diff --git a/src/trace/autotrace/inkscape-autotrace.cpp b/src/trace/autotrace/inkscape-autotrace.cpp
new file mode 100644
index 0000000..9a8f6eb
--- /dev/null
+++ b/src/trace/autotrace/inkscape-autotrace.cpp
@@ -0,0 +1,226 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * This is the C++ glue between Inkscape and Autotrace
+ *//*
+ *
+ * Authors:
+ * Marc Jeanmougin
+ *
+ * Copyright (C) 2018 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ *
+ */
+#include <iomanip>
+#include <2geom/path-sink.h>
+#include <glibmm/i18n.h>
+
+#include "inkscape-autotrace.h"
+#include "async/progress.h"
+
+extern "C" {
+#include "3rdparty/autotrace/autotrace.h"
+#include "3rdparty/autotrace/output.h"
+#include "3rdparty/autotrace/spline.h"
+}
+
+namespace Inkscape {
+namespace Trace {
+namespace Autotrace {
+namespace {
+
+struct at_splines_deleter { void operator()(at_splines_type *p) { at_splines_free(p); }; };
+using at_splines_uniqptr = std::unique_ptr<at_splines_type, at_splines_deleter>;
+
+/**
+ * Eliminate the alpha channel by overlaying on top of white, and ensure the result is in packed RGB8 format.
+ * If nothing needs to be done, the original pixbuf is returned, otherwise a new pixbuf is returned.
+ */
+Glib::RefPtr<Gdk::Pixbuf> to_rgb8_packed(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf)
+{
+ int width = pixbuf->get_width();
+ int height = pixbuf->get_height();
+ int rowstride = pixbuf->get_rowstride();
+ int nchannels = pixbuf->get_n_channels();
+ auto data = pixbuf->get_pixels();
+
+ if (nchannels == 3 && rowstride == width * 3) {
+ return pixbuf;
+ }
+
+ int imgsize = width * height;
+ auto out = new unsigned char[3 * imgsize];
+ auto q = out;
+
+ for (int y = 0; y < height; y++) {
+ auto p = data + rowstride * y;
+ for (int x = 0; x < width; x++) {
+ unsigned char alpha = nchannels == 3 ? 255 : p[3];
+ unsigned char white = 255 - alpha;
+ for (int c = 0; c < 3; c++) {
+ *(q++) = (int)p[c] * alpha / 256 + white;
+ }
+ p += nchannels;
+ }
+ }
+
+ return Gdk::Pixbuf::create_from_data(out, Gdk::COLORSPACE_RGB, false, 8, width, height, width * 3, [out] (auto) { delete [] out; });
+}
+
+} // namespace
+
+AutotraceTracingEngine::AutotraceTracingEngine()
+{
+ // Create options struct, automatically filled with defaults.
+ opts = at_fitting_opts_new();
+ opts->background_color = at_color_new(255, 255, 255);
+ autotrace_init();
+}
+
+AutotraceTracingEngine::~AutotraceTracingEngine()
+{
+ at_fitting_opts_free(opts);
+}
+
+Glib::RefPtr<Gdk::Pixbuf> AutotraceTracingEngine::preview(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf)
+{
+ // Todo: Actually generate a meaningful preview.
+ return to_rgb8_packed(pixbuf);
+}
+
+TraceResult AutotraceTracingEngine::trace(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress)
+{
+ auto pb = to_rgb8_packed(pixbuf);
+
+ at_bitmap bitmap;
+ bitmap.height = pb->get_height();
+ bitmap.width = pb->get_width();
+ bitmap.bitmap = pb->get_pixels();
+ bitmap.np = 3;
+
+ auto throttled = Async::ProgressStepThrottler(progress, 0.02);
+ auto sub_trace = Async::SubProgress(throttled, 0.0, 0.8);
+
+ auto splines = at_splines_uniqptr(at_splines_new_full(
+ &bitmap, opts,
+ nullptr, nullptr,
+ [] (gfloat frac, gpointer data) { reinterpret_cast<decltype(sub_trace)*>(data)->report(frac); }, &sub_trace,
+ [] (gpointer data) -> gboolean { return !reinterpret_cast<decltype(sub_trace)*>(data)->keepgoing(); }, &sub_trace
+ ));
+ // at_output_write_func wfunc = at_output_get_handler_by_suffix("svg");
+ // at_spline_writer *wfunc = at_output_get_handler_by_suffix("svg");
+ // at_splines_write(wfunc, stdout, "", NULL, splines, NULL, NULL);
+
+ sub_trace.report_or_throw(1.0);
+ auto sub_convert = Async::SubProgress(throttled, 0.8, 0.2);
+
+ int height = splines->height;
+ at_spline_list_type list;
+ at_color last_color = { 0, 0, 0 };
+
+ std::string style;
+ Geom::PathBuilder pathbuilder;
+ TraceResult res;
+
+ auto get_style = [&] {
+ char color[10];
+ std::sprintf(color, "#%02x%02x%02x;", list.color.r, list.color.g, list.color.b);
+
+ std::stringstream ss;
+ ss << (splines->centerline || list.open ? "stroke:" : "fill:") << color
+ << (splines->centerline || list.open ? "fill:" : "stroke:") << "none";
+
+ return ss.str();
+ };
+
+ auto to_geom = [=] (at_real_coord const &c) {
+ return Geom::Point(c.x, height - c.y);
+ };
+
+ int const num_splines = SPLINE_LIST_ARRAY_LENGTH(*splines);
+ for (int list_i = 0; list_i < num_splines; list_i++) {
+ sub_convert.report_or_throw((double)list_i / num_splines);
+
+ list = SPLINE_LIST_ARRAY_ELT(*splines, list_i);
+
+ if (list_i == 0 || !at_color_equal(&list.color, &last_color)) {
+ if (list_i > 0) {
+ if (!(splines->centerline || list.open)) {
+ pathbuilder.closePath();
+ } else {
+ pathbuilder.flush();
+ }
+ res.emplace_back(std::move(style), pathbuilder.peek());
+ pathbuilder.clear();
+ }
+
+ style = get_style();
+ }
+
+ auto const first = SPLINE_LIST_ELT(list, 0);
+ pathbuilder.moveTo(to_geom(START_POINT(first)));
+
+ for (int spline_i = 0; spline_i < SPLINE_LIST_LENGTH(list); spline_i++) {
+ auto const spline = SPLINE_LIST_ELT(list, spline_i);
+
+ if (SPLINE_DEGREE(spline) == AT_LINEARTYPE) {
+ pathbuilder.lineTo(to_geom(END_POINT(spline)));
+ } else {
+ pathbuilder.curveTo(to_geom(CONTROL1(spline)), to_geom(CONTROL2(spline)), to_geom(END_POINT(spline)));
+ }
+
+ last_color = list.color;
+ }
+ }
+
+ if (SPLINE_LIST_ARRAY_LENGTH(*splines) > 0) {
+ if (!(splines->centerline || list.open)) {
+ pathbuilder.closePath();
+ } else {
+ pathbuilder.flush();
+ }
+ res.emplace_back(std::move(style), pathbuilder.peek());
+ }
+
+ return res;
+}
+
+void AutotraceTracingEngine::setColorCount(unsigned color_count)
+{
+ opts->color_count = color_count;
+}
+
+void AutotraceTracingEngine::setCenterLine(bool centerline)
+{
+ opts->centerline = centerline;
+}
+
+void AutotraceTracingEngine::setPreserveWidth(bool preserve_width)
+{
+ opts->preserve_width = preserve_width;
+}
+
+void AutotraceTracingEngine::setFilterIterations(unsigned filter_iterations)
+{
+ opts->filter_iterations = filter_iterations;
+}
+
+void AutotraceTracingEngine::setErrorThreshold(float error_threshold)
+{
+ opts->error_threshold = error_threshold;
+}
+
+} // namespace Autotrace
+} // namespace Trace
+} // namespace Inkscape
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
diff --git a/src/trace/autotrace/inkscape-autotrace.h b/src/trace/autotrace/inkscape-autotrace.h
new file mode 100644
index 0000000..a117592
--- /dev/null
+++ b/src/trace/autotrace/inkscape-autotrace.h
@@ -0,0 +1,61 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * This is the C++ glue between Inkscape and Autotrace
+ *//*
+ *
+ * Authors:
+ * Marc Jeanmougin
+ *
+ * Copyright (C) 2018 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ *
+ * Autotrace is available at http://github.com/autotrace/autotrace.
+ *
+ */
+#ifndef INKSCAPE_TRACE_AUTOTRACE_H
+#define INKSCAPE_TRACE_AUTOTRACE_H
+
+#include "trace/trace.h"
+using at_fitting_opts_type = struct _at_fitting_opts_type;
+
+namespace Inkscape {
+namespace Trace {
+namespace Autotrace {
+
+class AutotraceTracingEngine final
+ : public TracingEngine
+{
+public:
+ AutotraceTracingEngine();
+ ~AutotraceTracingEngine() override;
+
+ TraceResult trace(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress) override;
+ Glib::RefPtr<Gdk::Pixbuf> preview(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf) override;
+
+ void setColorCount(unsigned);
+ void setCenterLine(bool);
+ void setPreserveWidth(bool);
+ void setFilterIterations(unsigned);
+ void setErrorThreshold(float);
+
+private:
+ at_fitting_opts_type *opts;
+};
+
+} // namespace Autotrace
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_AUTOTRACE_H
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
diff --git a/src/trace/cielab.cpp b/src/trace/cielab.cpp
new file mode 100644
index 0000000..222fb91
--- /dev/null
+++ b/src/trace/cielab.cpp
@@ -0,0 +1,216 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Copyright 2005, 2006 by Gerald Friedland, Kristian Jantz and Lars Knipping
+ * Conversion to C++ for Inkscape by Bob Jamison
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#include <algorithm>
+#include <cmath>
+#include "cielab.h"
+
+namespace Inkscape {
+namespace Trace {
+
+namespace {
+
+/**
+ * Convert integer RGB values into a pixel value.
+ */
+uint32_t getRGB(int r, int g, int b)
+{
+ r = std::clamp(r, 0, 255);
+ g = std::clamp(g, 0, 255);
+ b = std::clamp(b, 0, 255);
+ return (r << 16) | (g << 8) | b;
+}
+
+/**
+ * Convert float RGB values (0.0-1.0) into a pixel value.
+ */
+uint32_t getRGB(float r, float g, float b)
+{
+ return getRGB((int)(r * 256.0f),
+ (int)(g * 256.0f),
+ (int)(b * 256.0f));
+}
+
+//#########################################
+//# Root approximations for large speedup.
+//# By njh!
+//#########################################
+
+class Tables
+{
+public:
+ static int constexpr SIZE = 16;
+ float cbrt[SIZE + 1];
+ float qn[SIZE + 1];
+
+ static auto &get()
+ {
+ static Tables const instance;
+ return instance;
+ }
+
+private:
+ Tables();
+};
+
+template <typename T>
+auto sq(T t)
+{
+ return t * t;
+}
+
+// Cube root.
+double cbrt(double x)
+{
+ auto polish = [x] (double y) {
+ return (2.0 * y + x / sq(y)) / 3.0;
+ };
+ double y = Tables::get().cbrt[(int)(x * Tables::SIZE)]; // assuming x \in [0, 1]
+ y = polish(y);
+ y = polish(y);
+ return y;
+}
+
+// Quintic root.
+double qnrt(double x)
+{
+ auto polish = [x] (double y) {
+ return (4.0 * y + x / sq(sq(y))) / 5.0;
+ };
+ double y = Tables::get().qn[(int)(x * Tables::SIZE)]; // assuming x \in [0, 1]
+ y = polish(y);
+ y = polish(y);
+ return y;
+}
+
+double pow24(double x)
+{
+ return sq(x * qnrt(x));
+}
+
+Tables::Tables()
+{
+ auto entry = [&] (int i, float x) {
+ cbrt[i] = std::pow(x / SIZE, 0.3333f);
+ qn[i] = std::pow(x / SIZE, 0.2f);
+ };
+
+ entry(0, 0.5f);
+ for (int i = 1; i < SIZE + 1; i++) {
+ entry(i, i);
+ }
+}
+
+} // namespace
+
+CieLab::CieLab(uint32_t rgb)
+{
+ uint8_t ir = (rgb >> 16) & 0xff;
+ uint8_t ig = (rgb >> 8) & 0xff;
+ uint8_t ib = (rgb ) & 0xff;
+
+ float fr = ir / 255.0f;
+ float fg = ig / 255.0f;
+ float fb = ib / 255.0f;
+
+ // printf("fr:%f fg:%f fb:%f\n", fr, fg, fb);
+
+ auto to_linear = [] (float &x) {
+ if (x > 0.04045) {
+ x = pow24((x + 0.055) / 1.055);
+ } else {
+ x /= 12.92;
+ }
+ };
+
+ to_linear(fr);
+ to_linear(fg);
+ to_linear(fb);
+
+ // Use white = D65
+ float x = fr * 0.4124 + fg * 0.3576 + fb * 0.1805;
+ float y = fr * 0.2126 + fg * 0.7152 + fb * 0.0722;
+ float z = fr * 0.0193 + fg * 0.1192 + fb * 0.9505;
+
+ float vx = x / 0.95047;
+ float vy = y;
+ float vz = z / 1.08883;
+
+ // printf("vx:%f vy:%f vz:%f\n", vx, vy, vz);
+
+ auto f = [] (float &x) {
+ if (x > 0.008856) {
+ x = cbrt(x);
+ } else {
+ x = (7.787 * x) + (16.0 / 116.0);
+ }
+ };
+
+ f(vx);
+ f(vy);
+ f(vz);
+
+ C = 0;
+ L = 116.0 * vy - 16.0;
+ A = 500.0 * (vx - vy);
+ B = 200.0 * (vy - vz);
+}
+
+uint32_t CieLab::toRGB() const
+{
+ float vy = (L + 16.0) / 116.0;
+ float vx = A / 500.0 + vy;
+ float vz = vy - B / 200.0;
+
+ auto finv = [] (float &x) {
+ float x3 = x * x * x;
+ if (x3 > 0.008856) {
+ x = x3;
+ } else {
+ x = (x - 16.0 / 116.0) / 7.787;
+ }
+ };
+
+ finv(vx);
+ finv(vy);
+ finv(vz);
+
+ vx *= 0.95047; // use white = D65
+ vz *= 1.08883;
+
+ float vr = vx * 3.2406 + vy * -1.5372 + vz * -0.4986;
+ float vg = vx * -0.9689 + vy * 1.8758 + vz * 0.0415;
+ float vb = vx * 0.0557 + vy * -0.2040 + vz * 1.0570;
+
+ auto from_linear = [] (float &x) {
+ if (x > 0.0031308) {
+ x = 1.055 * std::pow(x, 1.0 / 2.4) - 0.055;
+ } else {
+ x *= 12.92;
+ }
+ };
+
+ from_linear(vr);
+ from_linear(vg);
+ from_linear(vb);
+
+ return getRGB(vr, vg, vb);
+}
+
+float CieLab::diffSq(CieLab const &c1, CieLab const &c2)
+{
+ return sq(c1.L - c2.L)
+ + sq(c1.A - c2.A)
+ + sq(c1.B - c2.B);
+}
+
+float CieLab::diff(CieLab const &c1, CieLab const &c2)
+{
+ return std::sqrt(diffSq(c1, c2));
+}
+
+} // namespace Trace
+} // namespace Inkscape
diff --git a/src/trace/cielab.h b/src/trace/cielab.h
new file mode 100644
index 0000000..66b0ea6
--- /dev/null
+++ b/src/trace/cielab.h
@@ -0,0 +1,106 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Copyright 2005, 2006 by Gerald Friedland, Kristian Jantz and Lars Knipping
+ * Conversion to C++ for Inkscape by Bob Jamison
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#ifndef INKSCAPE_TRACE_CIELAB_H
+#define INKSCAPE_TRACE_CIELAB_H
+
+#include <cstdint>
+
+namespace Inkscape {
+namespace Trace {
+
+class CieLab
+{
+public:
+ CieLab()
+ {
+ C = 0;
+ L = A = B = 0.0f;
+ }
+
+ /**
+ * Construct this CieLab from an ARGB value
+ */
+ CieLab(uint32_t rgb);
+
+ CieLab(float l, float a, float b)
+ {
+ C = 0;
+ L = l;
+ A = a;
+ B = b;
+ }
+
+ CieLab(CieLab const &other)
+ {
+ C = other.C;
+ L = other.L;
+ A = other.A;
+ B = other.B;
+ }
+
+ CieLab &operator=(CieLab const &other)
+ {
+ C = other.C;
+ L = other.L;
+ A = other.A;
+ B = other.B;
+ return *this;
+ }
+
+ /**
+ * Retrieve a CieLab value via index.
+ */
+ float operator()(unsigned index) const
+ {
+ switch (index) {
+ case 0: return L;
+ case 1: return A;
+ case 2: return B;
+ default: return 0;
+ }
+ }
+
+ void add(CieLab const &other)
+ {
+ C += other.C;
+ L += other.L;
+ A += other.A;
+ B += other.B;
+ }
+
+ void mul(float scale)
+ {
+ L *= scale;
+ A *= scale;
+ B *= scale;
+ }
+
+ /**
+ * Return this CieLab's value converted to an ARGB value
+ */
+ uint32_t toRGB() const;
+
+ /**
+ * Squared Euclidean distance between two colors in CieLab space.
+ */
+ static float diffSq(CieLab const &c1, CieLab const &c2);
+
+ /**
+ * Computes euclidean distance in CieLab space between two colors.
+ */
+ static float diff(CieLab const &c1, CieLab const &c2);
+
+ unsigned C;
+ float L;
+ float A;
+ float B;
+};
+
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_CIELAB_H
diff --git a/src/trace/depixelize/inkscape-depixelize.cpp b/src/trace/depixelize/inkscape-depixelize.cpp
new file mode 100644
index 0000000..ae3c783
--- /dev/null
+++ b/src/trace/depixelize/inkscape-depixelize.cpp
@@ -0,0 +1,107 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * This is the C++ glue between Inkscape and Potrace
+ *
+ * Authors:
+ * Bob Jamison <rjamison@titan.com>
+ * Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2004-2006 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ *
+ * Potrace, the wonderful tracer located at http://potrace.sourceforge.net,
+ * is provided by the generosity of Peter Selinger, to whom we are grateful.
+ *
+ */
+#include <iomanip>
+#include <thread>
+#include <glibmm/i18n.h>
+
+#include "inkscape-depixelize.h"
+
+#include "color.h"
+#include "preferences.h"
+#include "async/progress.h"
+#include "svg/svg-color.h"
+#include "svg/css-ostringstream.h"
+
+namespace Inkscape {
+namespace Trace {
+namespace Depixelize {
+
+DepixelizeTracingEngine::DepixelizeTracingEngine(TraceType traceType, double curves, int islands, int sparsePixels, double sparseMultiplier, bool optimize)
+ : traceType(traceType)
+{
+ params.curvesMultiplier = curves;
+ params.islandsWeight = islands;
+ params.sparsePixelsRadius = sparsePixels;
+ params.sparsePixelsMultiplier = sparseMultiplier;
+ params.optimize = optimize;
+ params.nthreads = Inkscape::Preferences::get()->getIntLimited("/options/threading/numthreads", std::thread::hardware_concurrency(), 1, 256);
+}
+
+TraceResult DepixelizeTracingEngine::trace(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress)
+{
+ TraceResult res;
+
+ ::Tracer::Splines splines;
+
+ if (traceType == TraceType::VORONOI) {
+ splines = ::Tracer::Kopf2011::to_voronoi(pixbuf, params);
+ } else {
+ splines = ::Tracer::Kopf2011::to_splines(pixbuf, params);
+ }
+
+ progress.report_or_throw(0.5);
+
+ auto subprogress = Async::SubProgress(progress, 0.5, 0.5);
+ auto throttled = Async::ProgressStepThrottler(subprogress, 0.02);
+
+ int num_splines = std::distance(splines.begin(), splines.end());
+ int i = 0;
+
+ for (auto &it : splines) {
+ throttled.report_or_throw((double)i / num_splines);
+ i++;
+
+ char b[64];
+ sp_svg_write_color(b, sizeof(b),
+ SP_RGBA32_U_COMPOSE(unsigned(it.rgba[0]),
+ unsigned(it.rgba[1]),
+ unsigned(it.rgba[2]),
+ unsigned(it.rgba[3])));
+ Inkscape::CSSOStringStream osalpha;
+ osalpha << it.rgba[3] / 255.0f;
+ char *style = g_strdup_printf("fill:%s;fill-opacity:%s;", b, osalpha.str().c_str());
+ res.emplace_back(style, std::move(it.pathVector));
+ g_free(style);
+ }
+
+ return res;
+}
+
+Glib::RefPtr<Gdk::Pixbuf> DepixelizeTracingEngine::preview(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf)
+{
+ return pixbuf;
+}
+
+bool DepixelizeTracingEngine::check_image_size(Geom::IntPoint const &size) const
+{
+ return size.x() > 256 || size.y() > 256;
+}
+
+} // namespace Depixelize
+} // namespace Trace
+} // namespace Inkscape
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
diff --git a/src/trace/depixelize/inkscape-depixelize.h b/src/trace/depixelize/inkscape-depixelize.h
new file mode 100644
index 0000000..adeefdc
--- /dev/null
+++ b/src/trace/depixelize/inkscape-depixelize.h
@@ -0,0 +1,60 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * This is the C++ glue between Inkscape and Potrace
+ *
+ * Copyright (C) 2019 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ *
+ * Potrace, the wonderful tracer located at http://potrace.sourceforge.net,
+ * is provided by the generosity of Peter Selinger, to whom we are grateful.
+ *
+ */
+#ifndef INKSCAPE_TRACE_DEPIXELIZE_H
+#define INKSCAPE_TRACE_DEPIXELIZE_H
+
+#include "trace/trace.h"
+#include "3rdparty/libdepixelize/kopftracer2011.h" // Cannot move to source file due to nested class.
+
+namespace Inkscape {
+namespace Trace {
+namespace Depixelize {
+
+enum class TraceType
+{
+ VORONOI,
+ BSPLINES
+};
+
+class DepixelizeTracingEngine final
+ : public TracingEngine
+{
+public:
+ DepixelizeTracingEngine() = default;
+ DepixelizeTracingEngine(TraceType traceType, double curves, int islands, int sparsePixels, double sparseMultiplier, bool optimize);
+
+ TraceResult trace(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress) override;
+ Glib::RefPtr<Gdk::Pixbuf> preview(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf) override;
+ bool check_image_size(Geom::IntPoint const &size) const override;
+
+private:
+ ::Tracer::Kopf2011::Options params;
+ TraceType traceType = TraceType::VORONOI;
+};
+
+} // namespace Depixelize
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_DEPIXELIZE_H
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
diff --git a/src/trace/filterset.cpp b/src/trace/filterset.cpp
new file mode 100644
index 0000000..1be5228
--- /dev/null
+++ b/src/trace/filterset.cpp
@@ -0,0 +1,272 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Some filters for Potrace in Inkscape
+ *
+ * Authors:
+ * Bob Jamison <rjamison@titan.com>
+ * Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2004-2006 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#include <cstdio>
+#include "imagemap-gdk.h"
+#include "filterset.h"
+#include "quantize.h"
+
+namespace Inkscape {
+namespace Trace {
+
+/*#########################################################################
+### G A U S S I A N (smoothing)
+#########################################################################*/
+
+static int gaussMatrix[] =
+{
+ 2, 4, 5, 4, 2,
+ 4, 9, 12, 9, 4,
+ 5, 12, 15, 12, 5,
+ 4, 9, 12, 9, 4,
+ 2, 4, 5, 4, 2
+};
+
+GrayMap grayMapGaussian(GrayMap const &me) // Todo: Make member function, keep implementation here
+{
+ int width = me.width;
+ int height = me.height;
+ int firstX = 2;
+ int lastX = width - 3;
+ int firstY = 2;
+ int lastY = height - 3;
+
+ auto newGm = GrayMap(width, height);
+
+ for (int y = 0; y < height; y++) {
+ for (int x = 0; x < width; x++) {
+ // image boundaries
+ if (x < firstX || x > lastX || y < firstY || y > lastY) {
+ newGm.setPixel(x, y, me.getPixel(x, y));
+ continue;
+ }
+
+ // all other pixels
+ int gaussIndex = 0;
+ unsigned long sum = 0;
+ for (int i = y - 2; i <= y + 2; i++) {
+ for (int j = x - 2; j <= x + 2; j++) {
+ int weight = gaussMatrix[gaussIndex++];
+ sum += me.getPixel(j, i) * weight;
+ }
+ }
+ sum /= 159;
+ sum = std::min(sum, GrayMap::WHITE);
+ newGm.setPixel(x, y, sum);
+ }
+ }
+
+ return newGm;
+}
+
+RgbMap rgbMapGaussian(RgbMap const &me)
+{
+ int width = me.width;
+ int height = me.height;
+ int firstX = 2;
+ int lastX = width-3;
+ int firstY = 2;
+ int lastY = height-3;
+
+ auto newGm = RgbMap(width, height);
+
+ for (int y = 0; y < height; y++) {
+ for (int x = 0; x < width; x++) {
+ // image boundaries
+ if (x < firstX || x > lastX || y < firstY || y > lastY) {
+ newGm.setPixel(x, y, me.getPixel(x, y));
+ continue;
+ }
+
+ // all other pixels
+ int gaussIndex = 0;
+ int sumR = 0;
+ int sumG = 0;
+ int sumB = 0;
+ for (int i = y - 2; i <= y + 2; i++) {
+ for (int j = x - 2; j <= x + 2; j++) {
+ int weight = gaussMatrix[gaussIndex++];
+ RGB rgb = me.getPixel(j, i);
+ sumR += weight * rgb.r;
+ sumG += weight * rgb.g;
+ sumB += weight * rgb.b;
+ }
+ }
+ RGB rout;
+ rout.r = (sumR / 159) & 0xff;
+ rout.g = (sumG / 159) & 0xff;
+ rout.b = (sumB / 159) & 0xff;
+ newGm.setPixel(x, y, rout);
+ }
+ }
+
+ return newGm;
+}
+
+/*#########################################################################
+### C A N N Y E D G E D E T E C T I O N
+#########################################################################*/
+
+static int sobelX[] =
+{
+ -1, 0, 1 ,
+ -2, 0, 2 ,
+ -1, 0, 1
+};
+
+static int sobelY[] =
+{
+ 1, 2, 1 ,
+ 0, 0, 0 ,
+ -1, -2, -1
+};
+
+/**
+ * Perform Sobel convolution on a GrayMap.
+ */
+GrayMap grayMapCanny(GrayMap const &gm, double dLowThreshold, double dHighThreshold)
+{
+ int width = gm.width;
+ int height = gm.height;
+ int firstX = 1;
+ int lastX = width - 2;
+ int firstY = 1;
+ int lastY = height - 2;
+
+ auto map = GrayMap(width, height);
+
+ for (int y = 0; y < height; y++) {
+ for (int x = 0; x < width; x++) {
+ bool edge;
+ // image boundaries
+ if (x < firstX || x > lastX || y < firstY || y > lastY) {
+ edge = false;
+ } else {
+ // SOBEL FILTERING
+ long sumX = 0;
+ long sumY = 0;
+ int sobelIndex = 0;
+ for (int i = y-1; i <= y + 1; i++) {
+ for (int j = x - 1; j <= x + 1; j++) {
+ sumX += gm.getPixel(j, i) * sobelX[sobelIndex++];
+ }
+ }
+
+ sobelIndex = 0;
+ for (int i = y - 1; i <= y + 1; i++) {
+ for (int j = x - 1; j <= x + 1; j++) {
+ sumY += gm.getPixel(j, i) * sobelY[sobelIndex++];
+ }
+ }
+
+ // GET VALUE
+ unsigned long sum = std::abs(sumX) + std::abs(sumY);
+ sum = std::min(sum, GrayMap::WHITE);
+
+ // GET EDGE DIRECTION (fast way)
+ int edgeDirection = 0; // x, y = 0
+ if (sumX == 0) {
+ if (sumY != 0) {
+ edgeDirection = 90;
+ }
+ } else {
+ long slope = sumY * 1024 / sumX;
+ if (slope > 2472 || slope< -2472) { // tan(67.5) * 1024
+ edgeDirection = 90;
+ } else if (slope > 414) { // tan(22.5) * 1024
+ edgeDirection = 45;
+ } else if (slope < -414) { // -tan(22.5) * 1024
+ edgeDirection = 135;
+ }
+ }
+
+ // printf("%ld %ld %f %d\n", sumX, sumY, orient, edgeDirection);
+
+ // Get two adjacent pixels in edge direction
+ unsigned long leftPixel;
+ unsigned long rightPixel;
+ if (edgeDirection == 0) {
+ leftPixel = gm.getPixel(x - 1, y);
+ rightPixel = gm.getPixel(x + 1, y);
+ } else if (edgeDirection == 45) {
+ leftPixel = gm.getPixel(x - 1, y + 1);
+ rightPixel = gm.getPixel(x + 1, y - 1);
+ } else if (edgeDirection == 90) {
+ leftPixel = gm.getPixel(x, y - 1);
+ rightPixel = gm.getPixel(x, y + 1);
+ } else { // 135
+ leftPixel = gm.getPixel(x - 1, y - 1);
+ rightPixel = gm.getPixel(x + 1, y + 1);
+ }
+
+ // Compare current value to adjacent pixels. (If less than either, suppress it.)
+ if (sum < leftPixel || sum < rightPixel) {
+ edge = false;
+ } else {
+ unsigned long highThreshold = dHighThreshold * GrayMap::WHITE;
+ unsigned long lowThreshold = dLowThreshold * GrayMap::WHITE;
+ if (sum >= highThreshold) {
+ edge = true;
+ } else if (sum < lowThreshold) {
+ edge = false;
+ } else {
+ edge = gm.getPixel(x - 1, y - 1) > highThreshold ||
+ gm.getPixel(x , y - 1) > highThreshold ||
+ gm.getPixel(x + 1, y - 1) > highThreshold ||
+ gm.getPixel(x - 1, y ) > highThreshold ||
+ gm.getPixel(x + 1, y ) > highThreshold ||
+ gm.getPixel(x - 1, y + 1) > highThreshold ||
+ gm.getPixel(x , y + 1) > highThreshold ||
+ gm.getPixel(x + 1, y + 1) > highThreshold;
+ }
+ }
+ }
+
+ // show edges as dark over light
+ map.setPixel(x, y, edge ? GrayMap::BLACK : GrayMap::WHITE);
+ }
+ }
+
+ // map.writePPM("canny.ppm");
+ return map;
+}
+
+/*#########################################################################
+### Q U A N T I Z A T I O N
+#########################################################################*/
+
+GrayMap quantizeBand(RgbMap const &rgbMap, int nrColors)
+{
+ auto gaussMap = rgbMapGaussian(rgbMap);
+ // gaussMap->writePPM(gaussMap, "rgbgauss.ppm");
+
+ auto qMap = rgbMapQuantize(gaussMap, nrColors);
+ // qMap->writePPM(qMap, "rgbquant.ppm");
+
+ auto gm = GrayMap(rgbMap.width, rgbMap.height);
+
+ // RGB is quantized. There should now be a small set of (R+G+B)
+ for (int y = 0; y < qMap.height; y++) {
+ for (int x = 0; x < qMap.width; x++) {
+ auto rgb = qMap.getPixelValue(x, y);
+ int sum = rgb.r + rgb.g + rgb.b;
+ auto result = (sum & 1) ? GrayMap::WHITE : GrayMap::BLACK;
+ // printf("%d %d %d : %d\n", rgb.r, rgb.g, rgb.b, index);
+ gm.setPixel(x, y, result);
+ }
+ }
+
+ return gm;
+}
+
+} // namespace Trace
+} // namespace Inkscape
diff --git a/src/trace/filterset.h b/src/trace/filterset.h
new file mode 100644
index 0000000..a85714d
--- /dev/null
+++ b/src/trace/filterset.h
@@ -0,0 +1,39 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Some filters for Potrace in Inkscape
+ *
+ * Authors:
+ * Bob Jamison <rjamison@titan.com>
+ * Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2004-2006 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#ifndef INKSCAPE_TRACE_FILTERSET_H
+#define INKSCAPE_TRACE_FILTERSET_H
+
+#include <gdk-pixbuf/gdk-pixbuf.h>
+#include "imagemap.h"
+
+namespace Inkscape {
+namespace Trace {
+
+/**
+ * Apply gaussian blur to an GrayMap.
+ */
+GrayMap grayMapGaussian(GrayMap const &gmap);
+
+/**
+ * Apply gaussian blur to an RgbMap.
+ */
+RgbMap rgbMapGaussian(RgbMap const &rgbmap);
+
+GrayMap grayMapCanny(GrayMap const &gmap, double lowThreshold, double highThreshold);
+
+GrayMap quantizeBand(RgbMap const &rgbmap, int nrColors);
+
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_FILTERSET_H
diff --git a/src/trace/imagemap-gdk.cpp b/src/trace/imagemap-gdk.cpp
new file mode 100644
index 0000000..9d47b3b
--- /dev/null
+++ b/src/trace/imagemap-gdk.cpp
@@ -0,0 +1,110 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * TODO: insert short description here
+ *//*
+ * Authors: see git history
+ *
+ * Copyright (C) 2018 Authors
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#include <cassert>
+#include "imagemap-gdk.h"
+
+namespace Inkscape {
+namespace Trace {
+
+GrayMap gdkPixbufToGrayMap(Glib::RefPtr<Gdk::Pixbuf> const &buf)
+{
+ int width = buf->get_width();
+ int height = buf->get_height();
+ int rowstride = buf->get_rowstride();
+ int nchannels = buf->get_n_channels();
+ auto data = buf->get_pixels();
+
+ auto map = GrayMap(width, height);
+
+ for (int y = 0; y < height; y++) {
+ auto p = data + rowstride * y;
+ for (int x = 0; x < width; x++) {
+ int alpha = nchannels == 3 ? 255 : p[3];
+ int white = 3 * (255 - alpha);
+ unsigned long sample = (int)p[0] + (int)p[1] + (int)p[2];
+ unsigned long bright = sample * alpha / 256 + white;
+ map.setPixel(x, y, bright);
+ p += nchannels;
+ }
+ }
+
+ return map;
+}
+
+Glib::RefPtr<Gdk::Pixbuf> grayMapToGdkPixbuf(GrayMap const &map)
+{
+ auto buf = Gdk::Pixbuf::create(Gdk::COLORSPACE_RGB, false, 8, map.width, map.height);
+
+ int rowstride = buf->get_rowstride();
+ int nchannels = buf->get_n_channels();
+ auto data = buf->get_pixels();
+
+ for (int y = 0; y < map.height; y++) {
+ auto p = data + rowstride * y;
+ for (int x = 0; x < map.width; x++) {
+ unsigned long pix = map.getPixel(x, y) / 3;
+ p[0] = p[1] = p[2] = pix & 0xff;
+ p += nchannels;
+ }
+ }
+
+ return buf;
+}
+
+RgbMap gdkPixbufToRgbMap(Glib::RefPtr<Gdk::Pixbuf> const &buf)
+{
+ int width = buf->get_width();
+ int height = buf->get_height();
+ int rowstride = buf->get_rowstride();
+ int nchannels = buf->get_n_channels();
+ auto data = buf->get_pixels();
+
+ auto map = RgbMap(width, height);
+
+ for (int y = 0; y < height; y++) {
+ auto p = data + rowstride * y;
+ for (int x = 0; x < width; x++) {
+ int alpha = nchannels == 3 ? 255 : p[3];
+ int white = 255 - alpha;
+ unsigned char r = (int)p[0] * alpha / 256 + white;
+ unsigned char g = (int)p[1] * alpha / 256 + white;
+ unsigned char b = (int)p[2] * alpha / 256 + white;
+ map.setPixel(x, y, {r, g, b});
+ p += nchannels;
+ }
+ }
+
+ return map;
+}
+
+Glib::RefPtr<Gdk::Pixbuf> indexedMapToGdkPixbuf(IndexedMap const &map)
+{
+ auto buf = Gdk::Pixbuf::create(Gdk::COLORSPACE_RGB, false, 8, map.width, map.height);
+
+ auto data = buf->get_pixels();
+ int rowstride = buf->get_rowstride();
+ int nchannels = buf->get_n_channels();
+
+ for (int y = 0; y < map.height; y++) {
+ auto p = data + rowstride * y;
+ for (int x = 0; x < map.width; x++) {
+ auto rgb = map.getPixelValue(x, y);
+ p[0] = rgb.r & 0xff;
+ p[1] = rgb.g & 0xff;
+ p[2] = rgb.b & 0xff;
+ p += nchannels;
+ }
+ }
+
+ return buf;
+}
+
+} // namespace Trace
+} // namespace Inkscape
diff --git a/src/trace/imagemap-gdk.h b/src/trace/imagemap-gdk.h
new file mode 100644
index 0000000..58ebbbb
--- /dev/null
+++ b/src/trace/imagemap-gdk.h
@@ -0,0 +1,27 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * TODO: insert short description here
+ *//*
+ * Authors: see git history
+ *
+ * Copyright (C) 2013 Authors
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#ifndef INKSCAPE_TRACE_IMAGEMAP_GDK_H
+#define INKSCAPE_TRACE_IMAGEMAP_GDK_H
+
+#include <gdkmm/pixbuf.h>
+#include "imagemap.h"
+
+namespace Inkscape {
+namespace Trace {
+
+GrayMap gdkPixbufToGrayMap(Glib::RefPtr<Gdk::Pixbuf> const &);
+Glib::RefPtr<Gdk::Pixbuf> grayMapToGdkPixbuf(GrayMap const &);
+RgbMap gdkPixbufToRgbMap(Glib::RefPtr<Gdk::Pixbuf> const &);
+Glib::RefPtr<Gdk::Pixbuf> indexedMapToGdkPixbuf(IndexedMap const &);
+
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_IMAGEMAP_GDK_H
diff --git a/src/trace/imagemap.cpp b/src/trace/imagemap.cpp
new file mode 100644
index 0000000..48acd8c
--- /dev/null
+++ b/src/trace/imagemap.cpp
@@ -0,0 +1,128 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * TODO: insert short description here
+ *//*
+ * Authors: see git history
+ *
+ * Copyright (C) 2018 Authors
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#include <cstdio>
+#include "imagemap.h"
+
+namespace Inkscape {
+namespace Trace {
+
+/*
+ * GrayMap
+ */
+
+GrayMap::GrayMap(int width, int height)
+ : MapBase(width, height)
+{
+}
+
+bool GrayMap::writePPM(char const *fileName)
+{
+ if (!fileName) {
+ return false;
+ }
+
+ auto f = std::fopen(fileName, "wb");
+ if (!f) {
+ return false;
+ }
+
+ std::fprintf(f, "P6 %d %d 255\n", width, height);
+
+ for (int y = 0; y < height; y++) {
+ for (int x = 0; x < width; x++) {
+ auto pix = getPixel(x, y) / 3;
+ unsigned char pixb = pix & 0xff;
+ std::fputc(pixb, f);
+ std::fputc(pixb, f);
+ std::fputc(pixb, f);
+ }
+ }
+
+ std::fclose(f);
+
+ return true;
+}
+
+/*
+ * RgbMap
+ */
+
+RgbMap::RgbMap(int width, int height)
+ : MapBase(width, height)
+{
+}
+
+bool RgbMap::writePPM(char const *fileName)
+{
+ if (!fileName) {
+ return false;
+ }
+
+ auto f = std::fopen(fileName, "wb");
+ if (!f) {
+ return false;
+ }
+
+ std::fprintf(f, "P6 %d %d 255\n", width, height);
+
+ for (int y = 0; y < height; y++) {
+ for (int x = 0; x < width; x++) {
+ auto rgb = getPixel(x, y);
+ std::fputc(rgb.r, f);
+ std::fputc(rgb.g, f);
+ std::fputc(rgb.b, f);
+ }
+ }
+
+ std::fclose(f);
+
+ return true;
+}
+
+/*
+ * IndexedMap
+ */
+
+IndexedMap::IndexedMap(int width, int height)
+ : MapBase(width, height)
+ , nrColors(0)
+{
+ clut.fill(RGB{0, 0, 0});
+}
+
+bool IndexedMap::writePPM(char const *fileName)
+{
+ if (!fileName) {
+ return false;
+ }
+
+ auto f = std::fopen(fileName, "wb");
+ if (!f) {
+ return false;
+ }
+
+ std::fprintf(f, "P6 %d %d 255\n", width, height);
+
+ for (int y = 0; y < height; y++) {
+ for (int x = 0; x < width; x++) {
+ auto rgb = getPixelValue(x, y);
+ std::fputc(rgb.r, f);
+ std::fputc(rgb.g, f);
+ std::fputc(rgb.b, f);
+ }
+ }
+
+ std::fclose(f);
+
+ return true;
+}
+
+} // namespace Trace
+} // namespace Inkscape
diff --git a/src/trace/imagemap.h b/src/trace/imagemap.h
new file mode 100644
index 0000000..542e641
--- /dev/null
+++ b/src/trace/imagemap.h
@@ -0,0 +1,91 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * TODO: insert short description here
+ *//*
+ * Authors: see git history
+ *
+ * Copyright (C) 2018 Authors
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#ifndef INKSCAPE_TRACE_IMAGEMAP_H
+#define INKSCAPE_TRACE_IMAGEMAP_H
+
+#include <vector>
+#include <array>
+
+namespace Inkscape {
+namespace Trace {
+
+template <typename T>
+struct MapBase
+{
+ int width;
+ int height;
+ std::vector<T> pixels;
+
+ MapBase(int width, int height)
+ : width(width)
+ , height(height)
+ , pixels(width * height) {}
+
+ int offset(int x, int y) const { return x + y * width; }
+ T *row(int y) { return pixels.data() + y * width; }
+ T const *row(int y) const { return pixels.data() + y * width; }
+ void setPixel(int x, int y, T val) { pixels[offset(x, y)] = val; }
+ T getPixel(int x, int y) const { return pixels[offset(x, y)]; }
+};
+
+/*
+ * GrayMap
+ */
+
+struct GrayMap
+ : MapBase<unsigned long>
+{
+ static unsigned long constexpr BLACK = 0;
+ static unsigned long constexpr WHITE = 255 * 3;
+
+ GrayMap(int width, int height);
+
+ bool writePPM(char const *fileName);
+};
+
+/*
+ * RgbMap
+ */
+
+struct RGB
+{
+ unsigned char r;
+ unsigned char g;
+ unsigned char b;
+};
+
+struct RgbMap
+ : MapBase<RGB>
+{
+ RgbMap(int width, int height);
+
+ bool writePPM(char const *fileName);
+};
+
+/*
+ * IndexedMap
+ */
+
+struct IndexedMap
+ : MapBase<unsigned>
+{
+ IndexedMap(int width, int height);
+
+ RGB getPixelValue(int x, int y) const { return clut[getPixel(x, y) % clut.size()]; }
+ bool writePPM(char const *fileName);
+
+ int nrColors;
+ std::array<RGB, 256> clut; ///< Color look-up table.
+};
+
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_IMAGEMAP_H
diff --git a/src/trace/pool.h b/src/trace/pool.h
new file mode 100644
index 0000000..742050a
--- /dev/null
+++ b/src/trace/pool.h
@@ -0,0 +1,117 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Pool memory allocation
+ *
+ * Authors:
+ * Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2004-2006 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+
+// not thread safe (a pool cannot be shared by threads safely)
+
+/*
+-- principle:
+
+ - user operations on a pool of objects of type T are:
+ - T *draw() : obtain a unused slot to store an object T
+ - void drop(T *) : release a slot
+
+-- implementation:
+
+ - a pool for objects T is:
+
+ * blocks[64] : an array of allocated blocks of memory:
+ |---0--> block with capacity 64
+ |---1--> block with capacity 64
+ |---2--> block with capacity 128
+ |---3--> block with capacity 128
+ |---4--> block with capacity 256
+ |---5--> block with capacity 256
+ |---6--> block with capacity 512
+ |---7--> not yet allocated
+ :
+ |---k--> not yet allocated (future capacity ~ 2^(6+k/2))
+ :
+ '--63--> not yet allocated
+ * cblock : the index of the next unallocated block (here 7).
+ * next : a pointer to an unused slot inside an allocated bloc
+
+ - the first bytes of an unallocated slot inside a bloc are used to store a
+ pointer to some other unallocated slot. (this way, we keep a list of all
+ unused slots starting at <next>)
+
+ - insertions and deletions in this list are done at the root <next>.
+ if <next> points to NULL (no slots are available) when a draw()
+ operation is performed a new block is allocated, and the unused slots
+ list is filled with the allocated slots.
+
+ - memory is freed only at pool's deletion.
+*/
+#ifndef INKSCAPE_TRACE_POOL_H
+#define INKSCAPE_TRACE_POOL_H
+
+#include <cstdlib>
+#include <exception>
+#include <algorithm>
+
+template <typename T>
+class Pool
+{
+public:
+ Pool()
+ {
+ cblock = 0;
+ size = std::max(sizeof(T), sizeof(void *));
+ next = nullptr;
+ for (auto &k : block) {
+ k = nullptr;
+ }
+ }
+
+ ~Pool()
+ {
+ for (int k = 0; k < cblock; k++) {
+ std::free(block[k]);
+ }
+ }
+
+ T *draw()
+ {
+ if (!next) addblock();
+ void *p = next;
+ next = *(void **)p;
+ return (T *)p;
+ }
+
+ void drop(T *p)
+ {
+ *(void **)p = next;
+ next = (void *)p;
+ }
+
+private:
+ int size;
+ int cblock;
+ void *block[64]; // enough to store unlimited number of objects, if 64 is changed: see constructor too
+ void *next;
+
+ void addblock()
+ {
+ int i = cblock++;
+ int blocksize = 1 << (6 + (i / 2));
+ block[i] = (void *)std::malloc(blocksize * size);
+ if (!block[i]) throw std::bad_alloc();
+ char *p = (char *)block[i];
+ for (int k = 0; k < blocksize - 1; k++) {
+ *(void**)p = (void *)(p + size);
+ p += size;
+ }
+ *(void **)p = next;
+ next = block[i];
+ }
+};
+
+#endif // INKSCAPE_TRACE_POOL_H
diff --git a/src/trace/potrace/bitmap.h b/src/trace/potrace/bitmap.h
new file mode 100644
index 0000000..2fb07e8
--- /dev/null
+++ b/src/trace/potrace/bitmap.h
@@ -0,0 +1,118 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * inline macros for accessing bitmaps
+ */
+/* Copyright (C) 2001-2015 Peter Selinger.
+ This file is part of Potrace. It is free software and it is covered
+ by the GNU General Public License. See the file COPYING for details. */
+
+#ifndef BITMAP_H
+#define BITMAP_H
+
+#include <cstring>
+#include <cstdlib>
+#include <cerrno>
+#include <cstddef>
+
+/* The bitmap type is defined in potracelib.h */
+#include "potracelib.h"
+
+/* The present file defines some convenient macros and static inline
+ functions for accessing bitmaps. Since they only produce inline
+ code, they can be conveniently shared by the library and frontends,
+ if desired */
+
+/* ---------------------------------------------------------------------- */
+/* some measurements */
+
+#define BM_WORDSIZE ((int)sizeof(potrace_word))
+#define BM_WORDBITS (8*BM_WORDSIZE)
+#define BM_HIBIT (((potrace_word)1)<<(BM_WORDBITS-1))
+#define BM_ALLBITS (~(potrace_word)0)
+
+/* macros for accessing pixel at index (x,y). U* macros omit the
+ bounds check. */
+
+#define bm_scanline(bm, y) ((bm)->map + (ptrdiff_t)(y)*(ptrdiff_t)(bm)->dy)
+#define bm_index(bm, x, y) (&bm_scanline(bm, y)[(x)/BM_WORDBITS])
+#define bm_mask(x) (BM_HIBIT >> ((x) & (BM_WORDBITS-1)))
+#define bm_range(x, a) ((int)(x) >= 0 && (int)(x) < (a))
+#define bm_safe(bm, x, y) (bm_range(x, (bm)->w) && bm_range(y, (bm)->h))
+#define BM_UGET(bm, x, y) ((*bm_index(bm, x, y) & bm_mask(x)) != 0)
+#define BM_USET(bm, x, y) (*bm_index(bm, x, y) |= bm_mask(x))
+#define BM_UCLR(bm, x, y) (*bm_index(bm, x, y) &= ~bm_mask(x))
+#define BM_UINV(bm, x, y) (*bm_index(bm, x, y) ^= bm_mask(x))
+#define BM_UPUT(bm, x, y, b) ((b) ? BM_USET(bm, x, y) : BM_UCLR(bm, x, y))
+#define BM_GET(bm, x, y) (bm_safe(bm, x, y) ? BM_UGET(bm, x, y) : 0)
+#define BM_SET(bm, x, y) (bm_safe(bm, x, y) ? BM_USET(bm, x, y) : 0)
+#define BM_CLR(bm, x, y) (bm_safe(bm, x, y) ? BM_UCLR(bm, x, y) : 0)
+#define BM_INV(bm, x, y) (bm_safe(bm, x, y) ? BM_UINV(bm, x, y) : 0)
+#define BM_PUT(bm, x, y, b) (bm_safe(bm, x, y) ? BM_UPUT(bm, x, y, b) : 0)
+
+/* free the given bitmap. Leaves errno untouched. */
+static inline void bm_free(potrace_bitmap_t *bm) {
+ if (bm) {
+ free(bm->map);
+ }
+ free(bm);
+}
+
+/* return new un-initialized bitmap. NULL with errno on error.
+ Assumes w, h >= 0. */
+static inline potrace_bitmap_t *bm_new(int w, int h) {
+ potrace_bitmap_t *bm;
+ int dy = w == 0 ? 0 : (w - 1) / BM_WORDBITS + 1;
+ ptrdiff_t size = (ptrdiff_t)dy * (ptrdiff_t)h * (ptrdiff_t)BM_WORDSIZE;
+
+ /* check for overflow error */
+ if (size < 0 || (h != 0 && dy != 0 && size / h / dy != BM_WORDSIZE)) {
+ errno = ENOMEM;
+ return nullptr;
+ }
+
+ bm = (potrace_bitmap_t *) malloc(sizeof(potrace_bitmap_t));
+ if (!bm) {
+ return nullptr;
+ }
+ bm->w = w;
+ bm->h = h;
+ bm->dy = dy;
+ bm->map = (potrace_word *) malloc(size);
+ if (!bm->map) {
+ g_warning("bm_new: can not allocate memory for bitmap (%td).", size);
+ free(bm);
+ return nullptr;
+ }
+ return bm;
+}
+
+/* clear the given bitmap. Set all bits to c. */
+static inline void bm_clear(potrace_bitmap_t *bm, int c) {
+ /* Note: if the bitmap was created with bm_new, then it is
+ guaranteed that size will fit into the ptrdiff_t type. */
+ ptrdiff_t size = (ptrdiff_t)bm->dy * (ptrdiff_t)bm->h * (ptrdiff_t)BM_WORDSIZE;
+ memset(bm->map, c ? -1 : 0, size);
+}
+
+/* duplicate the given bitmap. Return NULL on error with errno set. */
+static inline potrace_bitmap_t *bm_dup(const potrace_bitmap_t *bm) {
+ potrace_bitmap_t *bm1 = bm_new(bm->w, bm->h);
+ ptrdiff_t size = (ptrdiff_t)bm->dy * (ptrdiff_t)bm->h * (ptrdiff_t)BM_WORDSIZE;
+ if (!bm1) {
+ return nullptr;
+ }
+ memcpy(bm1->map, bm->map, size);
+ return bm1;
+}
+
+/* invert the given bitmap. */
+static inline void bm_invert(potrace_bitmap_t *bm) {
+ ptrdiff_t i;
+ ptrdiff_t size = (ptrdiff_t)bm->dy * (ptrdiff_t)bm->h;
+
+ for (i = 0; i < size; i++) {
+ bm->map[i] ^= BM_ALLBITS;
+ }
+}
+
+#endif /* BITMAP_H */
diff --git a/src/trace/potrace/inkscape-potrace.cpp b/src/trace/potrace/inkscape-potrace.cpp
new file mode 100644
index 0000000..24fe173
--- /dev/null
+++ b/src/trace/potrace/inkscape-potrace.cpp
@@ -0,0 +1,456 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * This is the C++ glue between Inkscape and Potrace
+ *
+ * Authors:
+ * Bob Jamison <rjamison@titan.com>
+ * Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2004-2006 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ *
+ * Potrace, the wonderful tracer located at http://potrace.sourceforge.net,
+ * is provided by the generosity of Peter Selinger, to whom we are grateful.
+ *
+ */
+#include <iomanip>
+#include <glibmm/i18n.h>
+#include <gtkmm/main.h>
+#include <potracelib.h>
+
+#include "inkscape-potrace.h"
+#include "bitmap.h"
+
+#include "async/progress.h"
+#include "trace/filterset.h"
+#include "trace/quantize.h"
+#include "trace/imagemap-gdk.h"
+
+namespace {
+
+struct potrace_state_deleter { void operator()(potrace_state_t *p) { potrace_state_free(p); }; };
+using potrace_state_uniqptr = std::unique_ptr<potrace_state_t, potrace_state_deleter>;
+
+struct potrace_bitmap_deleter { void operator()(potrace_bitmap_t *p) { bm_free(p); }; };
+using potrace_bitmap_uniqptr = std::unique_ptr<potrace_bitmap_t, potrace_bitmap_deleter>;
+
+Glib::ustring twohex(int value)
+{
+ return Glib::ustring::format(std::hex, std::setfill(L'0'), std::setw(2), value);
+}
+
+} // namespace
+
+namespace Inkscape {
+namespace Trace {
+namespace Potrace {
+
+PotraceTracingEngine::PotraceTracingEngine() { common_init(); }
+
+PotraceTracingEngine::PotraceTracingEngine(TraceType traceType, bool invert, int quantizationNrColors, double brightnessThreshold, double brightnessFloor, double cannyHighThreshold, int multiScanNrColors, bool multiScanStack, bool multiScanSmooth, bool multiScanRemoveBackground)
+ : traceType(traceType)
+ , invert(invert)
+ , quantizationNrColors(quantizationNrColors)
+ , brightnessThreshold(brightnessThreshold)
+ , brightnessFloor(brightnessFloor)
+ , cannyHighThreshold(cannyHighThreshold)
+ , multiScanNrColors(multiScanNrColors)
+ , multiScanStack(multiScanStack)
+ , multiScanSmooth(multiScanSmooth)
+ , multiScanRemoveBackground(multiScanRemoveBackground) { common_init(); }
+
+void PotraceTracingEngine::common_init()
+{
+ potraceParams = potrace_param_default();
+}
+
+PotraceTracingEngine::~PotraceTracingEngine()
+{
+ potrace_param_free(potraceParams);
+}
+
+void PotraceTracingEngine::setOptiCurve(int opticurve)
+{
+ potraceParams->opticurve = opticurve;
+}
+
+void PotraceTracingEngine::setOptTolerance(double opttolerance)
+{
+ potraceParams->opttolerance = opttolerance;
+}
+
+void PotraceTracingEngine::setAlphaMax(double alphamax)
+{
+ potraceParams->alphamax = alphamax;
+}
+
+void PotraceTracingEngine::setTurdSize(int turdsize)
+{
+ potraceParams->turdsize = turdsize;
+}
+
+/**
+ * Recursively descend the potrace_path_t node tree \a paths, writing paths to \a builder.
+ * The \a points set is used to prevent redundant paths.
+ */
+void PotraceTracingEngine::writePaths(potrace_path_t *paths, Geom::PathBuilder &builder, std::unordered_set<Geom::Point, geom_point_hash> &points, Async::Progress<double> &progress) const
+{
+ auto to_geom = [] (potrace_dpoint_t const &c) {
+ return Geom::Point(c.x, c.y);
+ };
+
+ for (auto path = paths; path; path = path->sibling) {
+ progress.throw_if_cancelled();
+
+ auto const &curve = path->curve;
+ // g_message("node->fm:%d\n", node->fm);
+ if (curve.n == 0) {
+ continue;
+ }
+
+ auto seg = curve.c[curve.n - 1];
+ auto const pt = to_geom(seg[2]);
+ // Have we been here already?
+ auto inserted = points.emplace(pt).second;
+ if (!inserted) {
+ // g_message("duplicate point: (%f,%f)\n", x2, y2);
+ continue;
+ }
+ builder.moveTo(pt);
+
+ for (int i = 0; i < curve.n; i++) {
+ auto seg = curve.c[i];
+ switch (curve.tag[i]) {
+ case POTRACE_CORNER:
+ builder.lineTo(to_geom(seg[1]));
+ builder.lineTo(to_geom(seg[2]));
+ break;
+ case POTRACE_CURVETO:
+ builder.curveTo(to_geom(seg[0]), to_geom(seg[1]), to_geom(seg[2]));
+ break;
+ default:
+ break;
+ }
+ }
+ builder.closePath();
+
+ for (auto child = path->childlist; child; child = child->sibling) {
+ writePaths(child, builder, points, progress);
+ }
+ }
+}
+
+std::optional<GrayMap> PotraceTracingEngine::filter(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf) const
+{
+ std::optional<GrayMap> map;
+
+ if (traceType == TraceType::QUANT) {
+
+ // Color quantization -- banding
+ auto rgbmap = gdkPixbufToRgbMap(pixbuf);
+ // rgbMap->writePPM(rgbMap, "rgb.ppm");
+ map = quantizeBand(rgbmap, quantizationNrColors);
+
+ } else if (traceType == TraceType::BRIGHTNESS || traceType == TraceType::BRIGHTNESS_MULTI) {
+
+ // Brightness threshold
+ auto gm = gdkPixbufToGrayMap(pixbuf);
+ map = GrayMap(gm.width, gm.height);
+
+ double floor = 3.0 * brightnessFloor * 256.0;
+ double cutoff = 3.0 * brightnessThreshold * 256.0;
+ for (int y = 0; y < gm.height; y++) {
+ for (int x = 0; x < gm.width; x++) {
+ double brightness = gm.getPixel(x, y);
+ bool black = brightness >= floor && brightness < cutoff;
+ map->setPixel(x, y, black ? GrayMap::BLACK : GrayMap::WHITE);
+ }
+ }
+
+ // map->writePPM(map, "brightness.ppm");
+
+ } else if (traceType == TraceType::CANNY) {
+
+ // Canny edge detection
+ auto gm = gdkPixbufToGrayMap(pixbuf);
+ map = grayMapCanny(gm, 0.1, cannyHighThreshold);
+ // map->writePPM(map, "canny.ppm");
+
+ }
+
+ // Invert the image if necessary.
+ if (map && invert) {
+ for (int y = 0; y < map->height; y++) {
+ for (int x = 0; x < map->width; x++) {
+ auto brightness = map->getPixel(x, y);
+ brightness = GrayMap::WHITE - brightness;
+ map->setPixel(x, y, brightness);
+ }
+ }
+ }
+
+ return map;
+}
+
+IndexedMap PotraceTracingEngine::filterIndexed(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf) const
+{
+ auto map = gdkPixbufToRgbMap(pixbuf);
+
+ if (multiScanSmooth) {
+ map = rgbMapGaussian(map);
+ }
+
+ auto imap = rgbMapQuantize(map, multiScanNrColors);
+
+ auto tomono = [] (RGB c) -> RGB {
+ unsigned char s = ((int)c.r + (int)c.g + (int)c.b) / 3;
+ return { s, s, s };
+ };
+
+ if (traceType == TraceType::QUANT_MONO || traceType == TraceType::BRIGHTNESS_MULTI) {
+ // Turn to grays
+ for (auto &c : imap.clut) {
+ c = tomono(c);
+ }
+ }
+
+ return imap;
+}
+
+Glib::RefPtr<Gdk::Pixbuf> PotraceTracingEngine::preview(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf)
+{
+ if (traceType == TraceType::QUANT_COLOR ||
+ traceType == TraceType::QUANT_MONO ||
+ traceType == TraceType::BRIGHTNESS_MULTI) // this is a lie: multipass doesn't use filterIndexed, but it's a better preview approx than filter()
+ {
+ auto gm = filterIndexed(pixbuf);
+
+ return indexedMapToGdkPixbuf(gm);
+
+ } else {
+
+ auto gm = filter(pixbuf);
+ if (!gm) {
+ return {};
+ }
+
+ return grayMapToGdkPixbuf(*gm);
+ }
+}
+
+/**
+ * This is the actual wrapper of the call to Potrace.
+ */
+Geom::PathVector PotraceTracingEngine::grayMapToPath(GrayMap const &grayMap, Async::Progress<double> &progress)
+{
+ auto potraceBitmap = potrace_bitmap_uniqptr(bm_new(grayMap.width, grayMap.height));
+ if (!potraceBitmap) {
+ return {};
+ }
+
+ bm_clear(potraceBitmap.get(), 0);
+
+ // Read the data out of the GrayMap
+ for (int y = 0; y < grayMap.height; y++) {
+ for (int x = 0; x < grayMap.width; x++) {
+ BM_UPUT(potraceBitmap, x, y, grayMap.getPixel(x, y) ? 0 : 1);
+ }
+ }
+
+ progress.throw_if_cancelled();
+
+ //##Debug
+ /*
+ FILE *f = fopen("poimage.pbm", "wb");
+ bm_writepbm(f, bm);
+ fclose(f);
+ */
+
+ // Trace the bitmap.
+
+ auto throttled = Async::ProgressStepThrottler(progress, 0.02);
+
+ potraceParams->progress.data = &throttled;
+ potraceParams->progress.callback = [] (double progress, void *data) { reinterpret_cast<decltype(throttled)*>(data)->report(progress); };
+ auto potraceState = potrace_state_uniqptr(potrace_trace(potraceParams, potraceBitmap.get()));
+
+ potraceBitmap.reset();
+
+ progress.throw_if_cancelled();
+
+ // Extract the paths into a pathvector and return it.
+ Geom::PathBuilder builder;
+ std::unordered_set<Geom::Point, geom_point_hash> points;
+ writePaths(potraceState->plist, builder, points, progress);
+ return builder.peek();
+}
+
+/**
+ * This is called for a single scan.
+ */
+TraceResult PotraceTracingEngine::traceSingle(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress)
+{
+ brightnessFloor = 0.0; // important to set this, since used by filter()
+
+ auto grayMap = filter(pixbuf);
+ if (!grayMap) {
+ return {};
+ }
+
+ progress.report_or_throw(0.2);
+
+ auto sub_gm = Async::SubProgress(progress, 0.2, 0.8);
+ auto pv = grayMapToPath(*grayMap, sub_gm);
+
+ TraceResult results;
+ results.emplace_back("fill:#000000", std::move(pv));
+ return results;
+}
+
+/**
+ * This allows routines that already generate GrayMaps to skip image filtering, increasing performance.
+ */
+TraceResult PotraceTracingEngine::traceGrayMap(GrayMap const &grayMap, Async::Progress<double> &progress)
+{
+ auto pv = grayMapToPath(grayMap, progress);
+
+ TraceResult results;
+ results.emplace_back("fill:#000000", std::move(pv));
+ return results;
+}
+
+/**
+ * Called for multiple-scanning algorithms
+ */
+TraceResult PotraceTracingEngine::traceBrightnessMulti(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress)
+{
+ double constexpr low = 0.2; // bottom of range
+ double constexpr high = 0.9; // top of range
+ double const delta = (high - low) / multiScanNrColors;
+
+ brightnessFloor = 0.0; // Set bottom to black
+
+ TraceResult results;
+
+ for (int i = 0; i < multiScanNrColors; i++) {
+ auto subprogress = Async::SubProgress(progress, (double)i / multiScanNrColors, 1.0 / multiScanNrColors);
+
+ brightnessThreshold = low + delta * i;
+
+ auto grayMap = filter(pixbuf);
+ if (!grayMap) {
+ continue;
+ }
+
+ subprogress.report_or_throw(0.2);
+
+ auto sub_gmtopath = Async::SubProgress(subprogress, 0.2, 0.8);
+ auto pv = grayMapToPath(*grayMap, sub_gmtopath);
+ if (pv.empty()) {
+ continue;
+ }
+
+ // get style info
+ int grayVal = 256.0 * brightnessThreshold;
+ auto style = Glib::ustring::compose("fill-opacity:1.0;fill:#%1%2%3", twohex(grayVal), twohex(grayVal), twohex(grayVal));
+
+ // g_message("### GOT '%s' \n", style.c_str());
+ results.emplace_back(style.raw(), std::move(pv));
+
+ if (!multiScanStack) {
+ brightnessFloor = brightnessThreshold;
+ }
+
+ subprogress.report_or_throw(1.0);
+ }
+
+ // Remove the bottom-most scan, if requested.
+ if (results.size() > 1 && multiScanRemoveBackground) {
+ results.pop_back();
+ }
+
+ return results;
+}
+
+/**
+ * Quantization
+ */
+TraceResult PotraceTracingEngine::traceQuant(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress)
+{
+ auto imap = filterIndexed(pixbuf);
+
+ // Create and clear a gray map
+ auto gm = GrayMap(imap.width, imap.height);
+ for (int row = 0; row < gm.height; row++) {
+ for (int col = 0; col < gm.width; col++) {
+ gm.setPixel(col, row, GrayMap::WHITE);
+ }
+ }
+
+ TraceResult results;
+
+ for (int colorIndex = 0; colorIndex < imap.nrColors; colorIndex++) {
+ auto subprogress = Async::SubProgress(progress, (double)colorIndex / imap.nrColors, 1.0 / imap.nrColors);
+
+ // Update the graymap for the current color index
+ for (int row = 0; row < imap.height; row++) {
+ for (int col = 0; col < imap.width; col++) {
+ int index = imap.getPixel(col, row);
+ if (index == colorIndex) {
+ gm.setPixel(col, row, GrayMap::BLACK);
+ } else if (!multiScanStack) {
+ gm.setPixel(col, row, GrayMap::WHITE);
+ }
+ }
+ }
+
+ subprogress.report_or_throw(0.2);
+
+ // Now we have a traceable graymap
+ auto sub_gmtopath = Async::SubProgress(subprogress, 0.2, 0.8);
+ auto pv = grayMapToPath(gm, sub_gmtopath);
+
+ if (!pv.empty()) {
+ // get style info
+ auto rgb = imap.clut[colorIndex];
+ auto style = Glib::ustring::compose("fill:#%1%2%3", twohex(rgb.r), twohex(rgb.g), twohex(rgb.b));
+ results.emplace_back(style.raw(), std::move(pv));
+ }
+
+ subprogress.report_or_throw(1.0);
+ }
+
+ // Remove the bottom-most scan, if requested.
+ if (results.size() > 1 && multiScanRemoveBackground) {
+ results.pop_back();
+ }
+
+ return results;
+}
+
+TraceResult PotraceTracingEngine::trace(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress)
+{
+ if (traceType == TraceType::QUANT_COLOR || traceType == TraceType::QUANT_MONO) {
+ return traceQuant(pixbuf, progress);
+ } else if (traceType == TraceType::BRIGHTNESS_MULTI) {
+ return traceBrightnessMulti(pixbuf, progress);
+ } else {
+ return traceSingle(pixbuf, progress);
+ }
+}
+
+} // namespace Potrace
+} // namespace Trace
+} // namespace Inkscape
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
diff --git a/src/trace/potrace/inkscape-potrace.h b/src/trace/potrace/inkscape-potrace.h
new file mode 100644
index 0000000..0e4a9c6
--- /dev/null
+++ b/src/trace/potrace/inkscape-potrace.h
@@ -0,0 +1,140 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * This is the C++ glue between Inkscape and Potrace
+ *
+ * Authors:
+ * Bob Jamison <rjamison@titan.com>
+ * Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2004-2006 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ *
+ * Potrace, the wonderful tracer located at http://potrace.sourceforge.net,
+ * is provided by the generosity of Peter Selinger, to whom we are grateful.
+ *
+ */
+#ifndef INKSCAPE_TRACE_POTRACE_H
+#define INKSCAPE_TRACE_POTRACE_H
+
+#include <optional>
+#include <unordered_set>
+#include <boost/functional/hash.hpp>
+#include <2geom/point.h>
+#include <2geom/path-sink.h>
+#include "trace/trace.h"
+#include "trace/imagemap.h"
+using potrace_param_t = struct potrace_param_s;
+using potrace_path_t = struct potrace_path_s;
+
+namespace Inkscape {
+namespace Trace {
+namespace Potrace {
+
+enum class TraceType
+{
+ BRIGHTNESS,
+ BRIGHTNESS_MULTI,
+ CANNY,
+ QUANT,
+ QUANT_COLOR,
+ QUANT_MONO,
+ // Used in tracedialog.cpp
+ AUTOTRACE_SINGLE,
+ AUTOTRACE_MULTI,
+ AUTOTRACE_CENTERLINE
+};
+
+// Todo: Make lib2geom types hashable.
+struct geom_point_hash
+{
+ std::size_t operator()(Geom::Point const &pt) const
+ {
+ std::size_t hash = 0;
+ boost::hash_combine(hash, pt.x());
+ boost::hash_combine(hash, pt.y());
+ return hash;
+ }
+};
+
+class PotraceTracingEngine final
+ : public TracingEngine
+{
+public:
+ PotraceTracingEngine();
+ PotraceTracingEngine(TraceType traceType,
+ bool invert,
+ int quantizationNrColors,
+ double brightnessThreshold,
+ double brightnessFloor,
+ double cannyHighThreshold,
+ int multiScanNrColors,
+ bool multiScanStack,
+ bool multiScanSmooth ,
+ bool multiScanRemoveBackground);
+ ~PotraceTracingEngine() override;
+
+ TraceResult trace(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress) override;
+ Glib::RefPtr<Gdk::Pixbuf> preview(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf) override;
+
+ TraceResult traceGrayMap(GrayMap const &grayMap, Async::Progress<double> &progress);
+
+ void setOptiCurve(int);
+ void setOptTolerance(double);
+ void setAlphaMax(double);
+ void setTurdSize(int);
+
+private:
+ potrace_param_t *potraceParams;
+
+ TraceType traceType = TraceType::BRIGHTNESS;
+
+ // Whether the image should be inverted at the end.
+ bool invert = false;
+
+ // Color -> b&w quantization
+ int quantizationNrColors = 8;
+
+ // Brightness items
+ double brightnessThreshold = 0.45;
+ double brightnessFloor = 0.0;
+
+ // Canny items
+ double cannyHighThreshold = 0.65;
+
+ // Color -> multiscan quantization
+ int multiScanNrColors = 8;
+ bool multiScanStack = true; // do we tile or stack?
+ bool multiScanSmooth = false; // do we use gaussian filter?
+ bool multiScanRemoveBackground = false; // do we remove the bottom trace?
+
+ void common_init();
+
+ TraceResult traceQuant (Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress);
+ TraceResult traceBrightnessMulti(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress);
+ TraceResult traceSingle (Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress);
+
+ IndexedMap filterIndexed(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf) const;
+ std::optional<GrayMap> filter(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf) const;
+
+ Geom::PathVector grayMapToPath(GrayMap const &gm, Async::Progress<double> &progress);
+
+ void writePaths(potrace_path_t *paths, Geom::PathBuilder &builder, std::unordered_set<Geom::Point, geom_point_hash> &points, Async::Progress<double> &progress) const;
+};
+
+} // namespace Potrace
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_POTRACE_H
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
diff --git a/src/trace/quantize.cpp b/src/trace/quantize.cpp
new file mode 100644
index 0000000..a79ec01
--- /dev/null
+++ b/src/trace/quantize.cpp
@@ -0,0 +1,555 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Quantization for Inkscape
+ *
+ * Authors:
+ * Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2006 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#include <memory>
+#include <cassert>
+#include <cstdio>
+#include <glib.h>
+
+#include "pool.h"
+#include "imagemap.h"
+#include "quantize.h"
+
+namespace Inkscape {
+namespace Trace {
+
+namespace {
+
+/**
+ * an octree node datastructure
+ */
+struct Ocnode
+{
+ Ocnode *parent; // parent node
+ Ocnode **ref; // node's reference
+ Ocnode *child[8]; // children
+ int nchild; // number of children
+ int width; // width level of this node
+ RGB rgb; // rgb's prefix of that node
+ unsigned long weight; // number of pixels this node accounts for
+ unsigned long rs, gs, bs; // sum of pixels colors this node accounts for
+ int nleaf; // number of leaves under this node
+ unsigned long mi; // minimum impact
+};
+
+/*
+-- algorithm principle:
+
+- inspired by the octree method, we associate a tree to a given color map
+
+- nodes in those trees have this shape:
+
+ parent
+ |
+ color_prefix(stored in rgb):width
+ colors_sum(stored in rs,gs,bs)/weight
+ / | \
+ child1 child2 child3
+
+- (grayscale) trees associated to pixels with colors 87 = 0b1010111 and
+ 69 = 0b1000101 are:
+
+ . . <-- roots of the trees
+ | |
+ 1010111:0 and 1000101:0 <-- color prefixes, written in binary form
+ 87/1 69/1 <-- color sums, written in decimal form
+
+- the result of merging the two trees is:
+
+ .
+ |
+ 10:5 <----- longest common prefix and binary width
+ 156/2 <---. of the covered color range.
+ / \ |
+ 1000101:0 1010111:0 '- sum of colors and quantity of pixels
+ 69/1 87/1 this node accounts for
+
+ one should consider three cases when two trees are to be merged:
+ - one tree range is included in the range of the other one, and the first
+ tree has to be inserted as a child (or merged with the corresponding
+ child) of the other.
+ - their ranges are the same, and their children have to be merged under
+ a single root.
+ - ranges have no intersection, and a fork node has to be created (like in
+ the given example).
+
+- a tree for an image is built dividing the image in 2 parts and merging
+ the trees obtained recursively for the two parts. a tree for a one pixel
+ part is a leaf like one of those which were given above.
+
+- last, this tree is reduced a specified number of leaves, deleting first
+ leaves with minimal impact i.e. [ weight * 2^(2*parentwidth) ] value :
+ a fair approximation of the impact a leaf removal would have on the final
+ result : it's the corresponding covered area times the square of the
+ introduced color distance.
+
+ deletion of a node A below a node with only two children is done as
+ follows :
+
+ - when the sibling is a leaf, the sibling is deleted as well, both nodes
+ are then represented by their parent.
+
+ | |
+ . ==> .
+ / \
+ A .
+
+ - otherwise the deletion of A deletes also its parent, which plays no
+ role anymore:
+
+ | |
+ . ==> \
+ / \ |
+ A . .
+ / \ / \
+
+ in that way, every leaf removal operation really decreases the remaining
+ total number of leaves by one.
+
+- very last, color indexes are attributed to leaves; associated colors are
+ averages, computed from weight and color components sums.
+
+-- improvements to the usual octree method:
+
+- since this algorithm shall often be used to perform quantization using a
+ very low (2-16) set of colors and not with a usual 256 value, we choose
+ more carefully which nodes are to be deleted.
+
+- depth of leaves is not fixed to an arbitrary number (which should be 8
+ when color components are in 0-255), so there is no need to go down to a
+ depth of 8 for each pixel (at full precision), unless it is really
+ required.
+
+- tree merging also fastens the overall tree building, and intermediate
+ processing could be done.
+
+- a huge optimization against the stupid removal algorithm (i.e. find a best
+ match over the whole tree, remove it and do it again) was implemented:
+ nodes are marked with the minimal impact of the removal of a leaf below
+ it. we proceed to the removal recursively. we stop when current removal
+ level is above the current node minimal, otherwise reached leaves are
+ removed, and every change over minimal impacts is propagated back to the
+ whole tree when the recursion ends.
+
+-- specific optimizations
+
+- pool allocation is used to allocate nodes (increased performance on large
+ images).
+
+*/
+
+RGB operator>>(RGB rgb, int s)
+{
+ RGB res;
+ res.r = rgb.r >> s;
+ res.g = rgb.g >> s;
+ res.b = rgb.b >> s;
+ return res;
+}
+
+bool operator==(RGB rgb1, RGB rgb2)
+{
+ return rgb1.r == rgb2.r && rgb1.g == rgb2.g && rgb1.b == rgb2.b;
+}
+
+int childIndex(RGB rgb)
+{
+ return ((rgb.r & 1) << 2) | ((rgb.g & 1) << 1) | (rgb.b & 1);
+}
+
+/**
+ * allocate a new node
+ */
+Ocnode *ocnodeNew(Pool<Ocnode> &pool)
+{
+ Ocnode *node = pool.draw();
+ node->ref = nullptr;
+ node->parent = nullptr;
+ node->nchild = 0;
+ for (auto &i : node->child) {
+ i = nullptr;
+ }
+ node->mi = 0;
+ return node;
+}
+
+void ocnodeFree(Pool<Ocnode> &pool, Ocnode *node)
+{
+ pool.drop(node);
+}
+
+/**
+ * free a full octree
+ */
+void octreeDelete(Pool<Ocnode> &pool, Ocnode *node)
+{
+ if (!node) return;
+ for (auto &i : node->child) {
+ octreeDelete(pool, i);
+ }
+ ocnodeFree(pool, node);
+}
+
+/**
+ * pretty-print an octree, debugging purposes
+ */
+#if 0
+void ocnodePrint(Ocnode *node, int indent)
+{
+ if (!node) return;
+ printf("width:%d weight:%lu rgb:%6x nleaf:%d mi:%lu\n",
+ node->width,
+ node->weight,
+ (unsigned int)(
+ ((node->rs / node->weight) << 16) +
+ ((node->gs / node->weight) << 8) +
+ (node->bs / node->weight)),
+ node->nleaf,
+ node->mi
+ );
+ for (int i = 0; i < 8; i++) if (node->child[i])
+ {
+ for (int k = 0; k < indent; k++) printf(" ");//indentation
+ printf("[%d:%p] ", i, node->child[i]);
+ ocnodePrint(node->child[i], indent+2);
+ }
+}
+
+void octreePrint(Ocnode *node)
+{
+ printf("<<octree>>\n");
+ if (node) printf("[r:%p] ", node); ocnodePrint(node, 2);
+}
+#endif
+
+/**
+ * builds a single <rgb> color leaf at location <ref>
+ */
+void ocnodeLeaf(Pool<Ocnode> &pool, Ocnode **ref, RGB rgb)
+{
+ assert(ref);
+ Ocnode *node = ocnodeNew(pool);
+ node->width = 0;
+ node->rgb = rgb;
+ node->rs = rgb.r; node->gs = rgb.g; node->bs = rgb.b;
+ node->weight = 1;
+ node->nleaf = 1;
+ node->mi = 0;
+ node->ref = ref;
+ *ref = node;
+}
+
+/**
+ * merge nodes <node1> and <node2> at location <ref> with parent <parent>
+ */
+int octreeMerge(Pool<Ocnode> &pool, Ocnode *parent, Ocnode **ref, Ocnode *node1, Ocnode *node2)
+{
+ assert(ref);
+ if (!node1 && !node2) return 0;
+ assert(node1 != node2);
+ if (parent && !*ref) parent->nchild++;
+ if (!node1) {
+ *ref = node2; node2->ref = ref; node2->parent = parent;
+ return node2->nleaf;
+ }
+ if (!node2) {
+ *ref = node1; node1->ref = ref; node1->parent = parent;
+ return node1->nleaf;
+ }
+ int dwitdth = node1->width - node2->width;
+ if (dwitdth > 0 && node1->rgb == node2->rgb >> dwitdth) {
+ // place node2 below node1
+ *ref = node1; node1->ref = ref; node1->parent = parent;
+ int i = childIndex(node2->rgb >> (dwitdth - 1));
+ node1->rs += node2->rs; node1->gs += node2->gs; node1->bs += node2->bs;
+ node1->weight += node2->weight;
+ node1->mi = 0;
+ if (node1->child[i]) node1->nleaf -= node1->child[i]->nleaf;
+ node1->nleaf += octreeMerge(pool, node1, &node1->child[i], node1->child[i], node2);
+ return node1->nleaf;
+ } else if (dwitdth < 0 && node2->rgb == node1->rgb >> (-dwitdth)) {
+ // place node1 below node2
+ *ref = node2; node2->ref = ref; node2->parent = parent;
+ int i = childIndex(node1->rgb >> (-dwitdth - 1));
+ node2->rs += node1->rs; node2->gs += node1->gs; node2->bs += node1->bs;
+ node2->weight += node1->weight;
+ node2->mi = 0;
+ if (node2->child[i]) node2->nleaf -= node2->child[i]->nleaf;
+ node2->nleaf += octreeMerge(pool, node2, &node2->child[i], node2->child[i], node1);
+ return node2->nleaf;
+ } else {
+ // nodes have either no intersection or the same root
+ Ocnode *newnode;
+ newnode = ocnodeNew(pool);
+ newnode->rs = node1->rs + node2->rs;
+ newnode->gs = node1->gs + node2->gs;
+ newnode->bs = node1->bs + node2->bs;
+ newnode->weight = node1->weight + node2->weight;
+ *ref = newnode; newnode->ref = ref; newnode->parent = parent;
+ if (dwitdth == 0 && node1->rgb == node2->rgb) {
+ // merge the nodes in <newnode>
+ newnode->width = node1->width; // == node2->width
+ newnode->rgb = node1->rgb; // == node2->rgb
+ newnode->nchild = 0;
+ newnode->nleaf = 0;
+ if (node1->nchild == 0 && node2->nchild == 0) {
+ newnode->nleaf = 1;
+ } else {
+ for (int i = 0; i < 8; i++) {
+ if (node1->child[i] || node2->child[i]) {
+ newnode->nleaf += octreeMerge(pool, newnode, &newnode->child[i], node1->child[i], node2->child[i]);
+ }
+ }
+ }
+ ocnodeFree(pool, node1); ocnodeFree(pool, node2);
+ return newnode->nleaf;
+ } else {
+ // use <newnode> as a fork node with children <node1> and <node2>
+ int newwidth = std::max(node1->width, node2->width);
+ RGB rgb1 = node1->rgb >> (newwidth - node1->width);
+ RGB rgb2 = node2->rgb >> (newwidth - node2->width);
+ // according to the previous tests <rgb1> != <rgb2> before the loop
+ while (!(rgb1 == rgb2)) {
+ rgb1 = rgb1 >> 1;
+ rgb2 = rgb2 >> 1;
+ newwidth++;
+ }
+ newnode->width = newwidth;
+ newnode->rgb = rgb1; // == rgb2
+ newnode->nchild = 2;
+ newnode->nleaf = node1->nleaf + node2->nleaf;
+ int i1 = childIndex(node1->rgb >> (newwidth - node1->width - 1));
+ int i2 = childIndex(node2->rgb >> (newwidth - node2->width - 1));
+ node1->parent = newnode;
+ node1->ref = &newnode->child[i1];
+ newnode->child[i1] = node1;
+ node2->parent = newnode;
+ node2->ref = &newnode->child[i2];
+ newnode->child[i2] = node2;
+ return newnode->nleaf;
+ }
+ }
+}
+
+/**
+ * upatade mi value for leaves
+ */
+void ocnodeMi(Ocnode *node)
+{
+ node->mi = node->parent ? node->weight << (2 * node->parent->width) : 0;
+}
+
+/**
+ * remove leaves whose prune impact value is lower than <lvl>. at most
+ * <count> leaves are removed, and <count> is decreased on each removal.
+ * all parameters including minimal impact values are regenerated.
+ */
+void ocnodeStrip(Pool<Ocnode> &pool, Ocnode **ref, int &count, unsigned long lvl)
+{
+ Ocnode *node = *ref;
+ if (!node) return;
+ assert(ref == node->ref);
+ if (node->nchild == 0) { // leaf node
+ if (!node->mi) ocnodeMi(node); // mi generation may be required
+ if (node->mi > lvl) return; // leaf is above strip level
+ ocnodeFree(pool, node);
+ *ref = nullptr;
+ count--;
+ } else {
+ if (node->mi && node->mi > lvl) return; // node is above strip level
+ node->nchild = 0;
+ node->nleaf = 0;
+ node->mi = 0;
+ Ocnode **lonelychild = nullptr;
+ for (auto & i : node->child) {
+ if (i) {
+ ocnodeStrip(pool, &i, count, lvl);
+ if (i) {
+ lonelychild = &i;
+ node->nchild++;
+ node->nleaf += i->nleaf;
+ if (!node->mi || node->mi > i->mi) {
+ node->mi = i->mi;
+ }
+ }
+ }
+ }
+ // tree adjustments
+ if (node->nchild == 0) {
+ count++;
+ node->nleaf = 1;
+ ocnodeMi(node);
+ } else if (node->nchild == 1) {
+ if ((*lonelychild)->nchild == 0) {
+ // remove the <lonelychild> leaf under a 1 child node
+ node->nchild = 0;
+ node->nleaf = 1;
+ ocnodeMi(node);
+ ocnodeFree(pool, *lonelychild);
+ *lonelychild = nullptr;
+ } else {
+ // make a bridge to <lonelychild> over a 1 child node
+ (*lonelychild)->parent = node->parent;
+ (*lonelychild)->ref = ref;
+ ocnodeFree(pool, node);
+ *ref = *lonelychild;
+ }
+ }
+ }
+}
+
+/**
+ * reduce the leaves of an octree to a given number
+ */
+void octreePrune(Pool<Ocnode> &pool, Ocnode **ref, int ncolor)
+{
+ assert(ref);
+ assert(ncolor > 0);
+ int n = (*ref)->nleaf - ncolor;
+ if (!*ref || n <= 0) return;
+ while (n > 0) {
+ ocnodeStrip(pool, ref, n, (*ref)->mi);
+ }
+}
+
+/**
+ * build an octree associated to the area of a color map <rgbmap>,
+ * included in the specified (x1,y1)--(x2,y2) rectangle.
+ */
+void octreeBuildArea(Pool<Ocnode> &pool, RgbMap const &rgbmap, Ocnode **ref, int x1, int y1, int x2, int y2, int ncolor)
+{
+ int dx = x2 - x1, dy = y2 - y1;
+ int xm = x1 + dx / 2, ym = y1 + dy / 2;
+ Ocnode *ref1 = nullptr;
+ Ocnode *ref2 = nullptr;
+ if (dx == 1 && dy == 1) {
+ ocnodeLeaf(pool, ref, rgbmap.getPixel(x1, y1));
+ } else if (dx > dy) {
+ octreeBuildArea(pool, rgbmap, &ref1, x1, y1, xm, y2, ncolor);
+ octreeBuildArea(pool, rgbmap, &ref2, xm, y1, x2, y2, ncolor);
+ octreeMerge(pool, nullptr, ref, ref1, ref2);
+ } else {
+ octreeBuildArea(pool, rgbmap, &ref1, x1, y1, x2, ym, ncolor);
+ octreeBuildArea(pool, rgbmap, &ref2, x1, ym, x2, y2, ncolor);
+ octreeMerge(pool, nullptr, ref, ref1, ref2);
+ }
+
+ // octreePrune(ref, 2 * ncolor);
+ // affects result quality for almost same performance :/
+}
+
+/**
+ * build an octree associated to the <rgbmap> color map,
+ * pruned to <ncolor> colors.
+ */
+Ocnode *octreeBuild(Pool<Ocnode> &pool, RgbMap const &rgbmap, int ncolor)
+{
+ // create the octree
+ Ocnode *node = nullptr;
+ octreeBuildArea(pool,
+ rgbmap, &node,
+ 0, 0, rgbmap.width, rgbmap.height, ncolor);
+
+ // prune the octree
+ octreePrune(pool, &node, ncolor);
+
+ return node;
+}
+
+/**
+ * compute the color palette associated to an octree.
+ */
+void octreeIndex(Ocnode *node, RGB *rgbpal, int &index)
+{
+ if (!node) return;
+ if (node->nchild == 0) {
+ rgbpal[index].r = node->rs / node->weight;
+ rgbpal[index].g = node->gs / node->weight;
+ rgbpal[index].b = node->bs / node->weight;
+ index++;
+ } else {
+ for (auto &i : node->child) {
+ if (i) {
+ octreeIndex(i, rgbpal, index);
+ }
+ }
+ }
+}
+
+/**
+ * compute the squared distance between two colors
+ */
+int distRGB(RGB rgb1, RGB rgb2)
+{
+ return (rgb1.r - rgb2.r) * (rgb1.r - rgb2.r)
+ + (rgb1.g - rgb2.g) * (rgb1.g - rgb2.g)
+ + (rgb1.b - rgb2.b) * (rgb1.b - rgb2.b);
+}
+
+/**
+ * find the index of closest color in a palette
+ */
+int findRGB(RGB const *rgbs, int ncolor, RGB rgb)
+{
+ int index = -1, dist = 0;
+ for (int k = 0; k < ncolor; k++) {
+ int d = distRGB(rgbs[k], rgb);
+ if (index == -1 || d < dist) { dist = d; index = k; }
+ }
+ return index;
+}
+
+} // namespace
+
+/**
+ * quantize an RGB image to a reduced number of colors.
+ */
+IndexedMap rgbMapQuantize(RgbMap const &rgbmap, int ncolor)
+{
+ assert(ncolor > 0);
+
+ auto imap = IndexedMap(rgbmap.width, rgbmap.height);
+
+ Pool<Ocnode> pool;
+ auto tree = octreeBuild(pool, rgbmap, ncolor);
+
+ auto rgbs = std::make_unique<RGB[]>(ncolor);
+ int index = 0;
+ octreeIndex(tree, rgbs.get(), index);
+
+ octreeDelete(pool, tree);
+
+ // stacking with increasing contrasts
+ std::sort(rgbs.get(), rgbs.get() + ncolor, [] (auto &ra, auto &rb) {
+ return (ra.r + ra.g + ra.b) < (rb.r + rb.g + rb.b);
+ });
+
+ // make the new map
+ // fill in the color lookup table
+ for (int i = 0; i < index; i++) {
+ imap.clut[i] = rgbs[i];
+ }
+ imap.nrColors = index;
+
+ // fill in new map pixels
+ for (int y = 0; y < rgbmap.height; y++) {
+ for (int x = 0; x < rgbmap.width; x++) {
+ auto rgb = rgbmap.getPixel(x, y);
+ int index = findRGB(rgbs.get(), ncolor, rgb);
+ imap.setPixel(x, y, index);
+ }
+ }
+
+ return imap;
+}
+
+} // namespace Trace
+} // namespace Inkscape
diff --git a/src/trace/quantize.h b/src/trace/quantize.h
new file mode 100644
index 0000000..fea2d39
--- /dev/null
+++ b/src/trace/quantize.h
@@ -0,0 +1,28 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Quantization for Inkscape
+ *
+ * Authors:
+ * Stéphane Gimenez <dev@gim.name>
+ *
+ * Copyright (C) 2006 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#ifndef INKSCAPE_TRACE_QUANTIZE_H
+#define INKSCAPE_TRACE_QUANTIZE_H
+
+#include "imagemap.h"
+
+namespace Inkscape {
+namespace Trace {
+
+/**
+ * Quantize an RGB image to a reduced number of colors.
+ */
+IndexedMap rgbMapQuantize(RgbMap const &rgbmap, int nrColors);
+
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_QUANTIZE_H
diff --git a/src/trace/siox.cpp b/src/trace/siox.cpp
new file mode 100644
index 0000000..a958821
--- /dev/null
+++ b/src/trace/siox.cpp
@@ -0,0 +1,770 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ Copyright 2005, 2006 by Gerald Friedland, Kristian Jantz and Lars Knipping
+
+ Conversion to C++ for Inkscape by Bob Jamison
+
+ Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#include <cmath>
+#include <cstdarg>
+#include <unordered_map>
+#include <algorithm>
+#include <cstdlib>
+#include <cassert>
+
+#include "siox.h"
+#include "async/progress.h"
+
+namespace Inkscape {
+namespace Trace {
+
+//########################################################################
+//# S I O X I M A G E
+//########################################################################
+
+SioxImage::SioxImage(Glib::RefPtr<Gdk::Pixbuf> const &buf)
+{
+ width = buf->get_width();
+ height = buf->get_height();
+
+ // Allocate data arrays.
+ int size = width * height;
+ pixdata.resize(size);
+ cmdata.resize(size);
+
+ int rowstride = buf->get_rowstride();
+ int nchannels = buf->get_n_channels();
+ auto data = buf->get_pixels();
+
+ // Copy pixel data.
+ for (int y = 0; y < height; y++) {
+ auto p = data + rowstride * y;
+ for (int x = 0; x < width; x++) {
+ uint32_t r = p[0];
+ uint32_t g = p[1];
+ uint32_t b = p[2];
+ uint32_t a = nchannels == 3 ? 255 : p[3];
+ pixdata[offset(x, y)] = (a << 24) | (r << 16) | (g << 8) | b;
+ p += nchannels;
+ }
+ }
+
+ // Zero confidence matrix.
+ std::fill(cmdata.begin(), cmdata.end(), 0.0f);
+}
+
+Glib::RefPtr<Gdk::Pixbuf> SioxImage::getGdkPixbuf() const
+{
+ auto buf = Gdk::Pixbuf::create(Gdk::COLORSPACE_RGB, true, 8, width, height);
+
+ int rowstride = buf->get_rowstride();
+ int nchannels = buf->get_n_channels();
+ auto data = buf->get_pixels();
+
+ for (int y = 0; y < height; y++) {
+ auto p = data + rowstride * y;
+ for (int x = 0; x < width; x++) {
+ uint32_t rgb = pixdata[offset(x, y)];
+ p[0] = (rgb >> 16) & 0xff; // r
+ p[1] = (rgb >> 8) & 0xff; // g
+ p[2] = (rgb ) & 0xff; // b
+ p[3] = (rgb >> 24) & 0xff; // a
+ p += nchannels;
+ }
+ }
+
+ return buf;
+}
+
+bool SioxImage::writePPM(char const *filename) const
+{
+ auto f = std::fopen(filename, "wb");
+ if (!f) {
+ return false;
+ }
+
+ std::fprintf(f, "P6 %u %u 255\n", width, height);
+
+ for (int y = 0; y < height; y++) {
+ for (int x = 0; x < width; x++) {
+ uint32_t rgb = pixdata[offset(x, y)];
+ uint8_t r = (rgb >> 16) & 0xff;
+ uint8_t g = (rgb >> 8) & 0xff;
+ uint8_t b = (rgb ) & 0xff;
+ std::fputc(r, f);
+ std::fputc(g, f);
+ std::fputc(b, f);
+ }
+ }
+
+ std::fclose(f);
+
+ return true;
+}
+
+unsigned SioxImage::hash() const
+{
+ unsigned result = width * height;
+
+ for (int i = 0; i < width * height; i++) {
+ result = 3 * result + (unsigned)pixdata[i] + (unsigned)((1 << 16) * cmdata[i]);
+ }
+
+ return result;
+}
+
+//########################################################################
+//# S I O X
+//########################################################################
+
+namespace {
+
+/**
+ * Apply a function which updates each pixel depending on the value of its neighbours.
+ */
+template <typename F>
+void apply_adjacent(float *cm, int xres, int yres, F f)
+{
+ for (int y = 0; y < yres; y++) {
+ for (int x = 0; x < xres - 1; x++) {
+ int idx = y * xres + x;
+ f(cm[idx], cm[idx + 1]);
+ }
+ }
+ for (int y = 0; y < yres; y++) {
+ for (int x = xres - 1; x >= 1; x--) {
+ int idx = y * xres + x;
+ f(cm[idx], cm[idx - 1]);
+ }
+ }
+ for (int y = 0; y < yres - 1; y++) {
+ for (int x = 0; x < xres; x++) {
+ int idx = y * xres + x;
+ f(cm[idx], cm[idx + xres]);
+ }
+ }
+ for (int y = yres - 1; y >= 1; y--) {
+ for (int x = 0; x < xres; x++) {
+ int idx = y * xres + x;
+ f(cm[idx], cm[idx - xres]);
+ }
+ }
+}
+
+/**
+ * Applies the morphological dilate operator.
+ *
+ * Can be used to close small holes in the given confidence matrix.
+ */
+void dilate(float *cm, int xres, int yres)
+{
+ apply_adjacent(cm, xres, yres, [] (float &a, float b) {
+ if (b > a) {
+ a = b;
+ }
+ });
+}
+
+/**
+ * Applies the morphological erode operator.
+ */
+void erode(float *cm, int xres, int yres)
+{
+ apply_adjacent(cm, xres, yres, [] (float &a, float b) {
+ if (b < a) {
+ a = b;
+ }
+ });
+}
+
+/**
+ * Multiplies matrix with the given scalar.
+ */
+void premultiplyMatrix(float alpha, float *cm, int cmSize)
+{
+ for (int i = 0; i < cmSize; i++) {
+ cm[i] *= alpha;
+ }
+}
+
+/**
+ * Normalizes the matrix to values to [0..1].
+ */
+void normalizeMatrix(float *cm, int cmSize)
+{
+ float max = 0.0f;
+ for (int i = 0; i < cmSize; i++) {
+ if (cm[i] > max) {
+ max = cm[i];
+ }
+ }
+
+ if (max <= 0.0f || max == 1.0f) {
+ return;
+ }
+
+ float alpha = 1.0f / max;
+ premultiplyMatrix(alpha, cm, cmSize);
+}
+
+/**
+ * Blurs confidence matrix with a given symmetrically weighted kernel.
+ *
+ * In the standard case confidence matrix entries are between 0...1 and
+ * the weight factors sum up to 1.
+ */
+void smooth(float *cm, int xres, int yres, float f1, float f2, float f3)
+{
+ for (int y = 0; y < yres; y++) {
+ for (int x = 0; x < xres - 2; x++) {
+ int idx = y * xres + x;
+ cm[idx] = f1 * cm[idx] + f2 * cm[idx + 1] + f3 * cm[idx + 2];
+ }
+ }
+ for (int y = 0; y < yres; y++) {
+ for (int x = xres - 1; x >= 2; x--) {
+ int idx = y * xres + x;
+ cm[idx] = f3 * cm[idx - 2] + f2 * cm[idx - 1] + f1 * cm[idx];
+ }
+ }
+ for (int y = 0; y < yres - 2; y++) {
+ for (int x = 0; x < xres; x++) {
+ int idx = y * xres + x;
+ cm[idx] = f1 * cm[idx] + f2 * cm[((y + 1) * xres) + x] + f3 * cm[((y + 2) * xres) + x];
+ }
+ }
+ for (int y = yres - 1; y >= 2; y--) {
+ for (int x = 0; x < xres; x++) {
+ int idx = y * xres + x;
+ cm[idx] = f3 * cm[((y - 2) * xres) + x] + f2 * cm[((y - 1) * xres) + x] + f1 * cm[idx];
+ }
+ }
+}
+
+/**
+ * Squared Euclidean distance of p and q.
+ */
+float sqrEuclideanDist(float *p, int pSize, float *q)
+{
+ float sum = 0.0;
+ for (int i = 0; i < pSize; i++) {
+ float v = p[i] - q[i];
+ sum += v * v;
+ }
+ return sum;
+}
+
+} // namespace
+
+Siox::Siox(Async::Progress<double> &progress)
+ : progress(&progress)
+ , width(0)
+ , height(0)
+ , pixelCount(0)
+ , image(nullptr)
+ , cm(nullptr) {}
+
+void Siox::error(std::string const &msg)
+{
+ g_warning("Siox error: %s\n", msg.c_str());
+}
+
+void Siox::trace(std::string const &msg)
+{
+ g_message("Siox: %s\n", msg.c_str());
+}
+
+SioxImage Siox::extractForeground(SioxImage const &originalImage, uint32_t backgroundFillColor)
+{
+ trace("### Start");
+
+ init();
+
+ SioxImage workImage = originalImage;
+
+ // Fetch some info from the image.
+ width = workImage.getWidth();
+ height = workImage.getHeight();
+ pixelCount = width * height;
+ image = workImage.getImageData();
+ cm = workImage.getConfidenceData();
+
+ // Create labelField.
+ auto labelField_storage = std::make_unique<int[]>(pixelCount);
+ labelField = labelField_storage.get();
+
+ trace("### Creating signatures");
+
+ // Create color signatures.
+ std::vector<CieLab> knownBg, knownFg;
+ auto imageClab = std::make_unique<CieLab[]>(pixelCount);
+ for (int i = 0; i < pixelCount; i++) {
+ float conf = cm[i];
+ uint32_t pix = image[i];
+ CieLab lab = pix;
+ imageClab[i] = lab;
+ if (conf <= BACKGROUND_CONFIDENCE) {
+ knownBg.emplace_back(lab);
+ } else if (conf >= FOREGROUND_CONFIDENCE) {
+ knownFg.emplace_back(lab);
+ }
+ }
+
+ progress->report_or_throw(0.1);
+
+ trace("knownBg:" + std::to_string(knownBg.size()) + " knownFg:" + std::to_string(knownFg.size()));
+
+ std::vector<CieLab> bgSignature;
+ colorSignature(knownBg, bgSignature, 3);
+
+ progress->report_or_throw(0.2);
+
+ std::vector<CieLab> fgSignature;
+ colorSignature(knownFg, fgSignature, 3);
+
+ // trace("### bgSignature:" + std::to_string(bgSignature.size()));
+
+ if (bgSignature.empty()) {
+ // segmentation impossible
+ error("Signature size is < 1. Segmentation is impossible");
+ throw Exception();
+ }
+
+ progress->report_or_throw(0.3);
+
+ // classify using color signatures,
+ // classification cached in hashmap for drb and speedup purposes
+ trace("### Analyzing image");
+
+ std::unordered_map<uint32_t, bool> hs;
+
+ int progressResolution = pixelCount / 10;
+
+ for (int i = 0; i < pixelCount; i++) {
+ if (i % progressResolution == 0) {
+ progress->report_or_throw(0.3 + 0.6 * i / pixelCount);
+ }
+
+ if (cm[i] >= FOREGROUND_CONFIDENCE) {
+ cm[i] = CERTAIN_FOREGROUND_CONFIDENCE;
+ } else if (cm[i] <= BACKGROUND_CONFIDENCE) {
+ cm[i] = CERTAIN_BACKGROUND_CONFIDENCE;
+ } else { // somewhere in between
+ auto [it, inserted] = hs.emplace(image[i], false);
+ if (inserted) {
+ auto const &lab = imageClab[i];
+
+ float minBg = std::numeric_limits<float>::max();
+ for (auto const &s : bgSignature) {
+ minBg = std::min(minBg, CieLab::diffSq(lab, s));
+ }
+
+ float minFg;
+ if (fgSignature.empty()) {
+ minFg = clusterSize;
+ } else {
+ minFg = std::numeric_limits<float>::max();
+ for (auto const &s : fgSignature) {
+ minFg = std::min(minFg, CieLab::diffSq(lab, s));
+ }
+ }
+
+ it->second = minBg < minFg;
+ }
+
+ bool isBackground = it->second;
+ cm[i] = isBackground ? CERTAIN_BACKGROUND_CONFIDENCE : CERTAIN_FOREGROUND_CONFIDENCE;
+ }
+ }
+
+ hs.clear();
+ imageClab.reset();
+
+ trace("### postProcessing");
+
+ // Postprocessing
+ smooth(cm, width, height, 0.333f, 0.333f, 0.333f); // average
+ normalizeMatrix(cm, pixelCount);
+ erode(cm, width, height);
+ keepOnlyLargeComponents(UNKNOWN_REGION_CONFIDENCE, 1.0/*sizeFactorToKeep*/);
+
+ // for (int i = 0; i < 2/*smoothness*/; i++)
+ // smooth(cm, width, height, 0.333f, 0.333f, 0.333f); // average
+
+ normalizeMatrix(cm, pixelCount);
+
+ for (int i = 0; i < pixelCount; i++) {
+ cm[i] = cm[i] >= UNKNOWN_REGION_CONFIDENCE
+ ? CERTAIN_FOREGROUND_CONFIDENCE
+ : CERTAIN_BACKGROUND_CONFIDENCE;
+ }
+
+ keepOnlyLargeComponents(UNKNOWN_REGION_CONFIDENCE, 1.5/*sizeFactorToKeep*/);
+ fillColorRegions();
+ dilate(cm, width, height);
+
+ progress->report_or_throw(1.0);
+
+ // We are done. Now clear everything but the background.
+ for (int i = 0; i < pixelCount; i++) {
+ if (cm[i] < FOREGROUND_CONFIDENCE) {
+ image[i] = backgroundFillColor;
+ }
+ }
+
+ trace("### Done");
+ return workImage;
+}
+
+void Siox::init()
+{
+ limits[0] = 0.64f;
+ limits[1] = 1.28f;
+ limits[2] = 2.56f;
+
+ float negLimits[3];
+ negLimits[0] = -limits[0];
+ negLimits[1] = -limits[1];
+ negLimits[2] = -limits[2];
+
+ clusterSize = sqrEuclideanDist(limits, 3, negLimits);
+}
+
+void Siox::colorSignatureStage1(CieLab *points,
+ unsigned leftBase,
+ unsigned rightBase,
+ unsigned recursionDepth,
+ unsigned *clusterCount,
+ unsigned dims)
+{
+ unsigned currentDim = recursionDepth % dims;
+ CieLab point = points[leftBase];
+ float min = point(currentDim);
+ float max = min;
+
+ for (unsigned i = leftBase + 1; i < rightBase; i++) {
+ point = points[i];
+ float curval = point(currentDim);
+ if (curval < min) min = curval;
+ if (curval > max) max = curval;
+ }
+
+ // Do the Rubner-rule split (sounds like a dance)
+ if (max - min > limits[currentDim]) {
+ float pivotPoint = (min + max) / 2.0; // average
+ unsigned left = leftBase;
+ unsigned right = rightBase - 1;
+
+ // partition points according to the dimension
+ while (true) {
+ while (true) {
+ point = points[left];
+ if (point(currentDim) > pivotPoint) {
+ break;
+ }
+ left++;
+ }
+ while (true) {
+ point = points[right];
+ if (point(currentDim) <= pivotPoint) {
+ break;
+ }
+ right--;
+ }
+
+ if (left > right) {
+ break;
+ }
+
+ point = points[left];
+ points[left] = points[right];
+ points[right] = point;
+
+ left++;
+ right--;
+ }
+
+ // Recurse and create sub-trees
+ colorSignatureStage1(points, leftBase, left, recursionDepth + 1, clusterCount, dims);
+ colorSignatureStage1(points, left, rightBase, recursionDepth + 1, clusterCount, dims);
+
+ } else {
+ // create a leaf
+ CieLab newpoint;
+
+ newpoint.C = rightBase - leftBase;
+
+ for (; leftBase < rightBase; leftBase++) {
+ newpoint.add(points[leftBase]);
+ }
+
+ // printf("clusters:%d\n", *clusters);
+
+ if (newpoint.C != 0) {
+ newpoint.mul(1.0f / newpoint.C);
+ }
+ points[*clusterCount] = newpoint;
+ (*clusterCount)++;
+ }
+}
+
+void Siox::colorSignatureStage2(CieLab *points,
+ unsigned leftBase,
+ unsigned rightBase,
+ unsigned recursionDepth,
+ unsigned *clusterCount,
+ float threshold,
+ unsigned dims)
+{
+ unsigned currentDim = recursionDepth % dims;
+ CieLab point = points[leftBase];
+ float min = point(currentDim);
+ float max = min;
+
+ for (unsigned i = leftBase+ 1; i < rightBase; i++) {
+ point = points[i];
+ float curval = point(currentDim);
+ if (curval < min) min = curval;
+ if (curval > max) max = curval;
+ }
+
+ // Do the Rubner-rule split (sounds like a dance)
+ if (max - min > limits[currentDim]) {
+ float pivotPoint = (min + max) / 2.0; //average
+ unsigned left = leftBase;
+ unsigned right = rightBase - 1;
+
+ // partition points according to the dimension
+ while (true) {
+ while (true) {
+ point = points[left];
+ if (point(currentDim) > pivotPoint) {
+ break;
+ }
+ left++;
+ }
+ while (true) {
+ point = points[right];
+ if (point(currentDim) <= pivotPoint) {
+ break;
+ }
+ right--;
+ }
+
+ if (left > right) {
+ break;
+ }
+
+ point = points[left];
+ points[left] = points[right];
+ points[right] = point;
+
+ left++;
+ right--;
+ }
+
+ //# Recurse and create sub-trees
+ colorSignatureStage2(points, leftBase, left, recursionDepth + 1, clusterCount, threshold, dims);
+ colorSignatureStage2(points, left, rightBase, recursionDepth + 1, clusterCount, threshold, dims);
+
+ } else {
+ //### Create a leaf
+ unsigned sum = 0;
+ for (unsigned i = leftBase; i < rightBase; i++) {
+ sum += points[i].C;
+ }
+
+ if (sum >= threshold) {
+ float scale = rightBase - leftBase;
+ CieLab newpoint;
+
+ for (; leftBase < rightBase; leftBase++) {
+ newpoint.add(points[leftBase]);
+ }
+
+ if (scale != 0.0) {
+ newpoint.mul(1.0 / scale);
+ }
+ points[*clusterCount] = newpoint;
+ (*clusterCount)++;
+ }
+ }
+}
+
+void Siox::colorSignature(std::vector<CieLab> const &inputVec,
+ std::vector<CieLab> &result,
+ unsigned dims)
+{
+ if (inputVec.empty()) { // no error. just don't do anything
+ return;
+ }
+
+ unsigned length = inputVec.size();
+ result = inputVec;
+
+ unsigned stage1length = 0;
+ colorSignatureStage1(result.data(), 0, length, 0, &stage1length, dims);
+
+ unsigned stage2length = 0;
+ colorSignatureStage2(result.data(), 0, stage1length, 0, &stage2length, length * 0.001, dims);
+
+ result.resize(stage2length);
+}
+
+void Siox::keepOnlyLargeComponents(float threshold, double sizeFactorToKeep)
+{
+ for (int idx = 0; idx < pixelCount; idx++) {
+ labelField[idx] = -1;
+ }
+
+ int curlabel = 0;
+ int maxregion = 0;
+ int maxblob = 0;
+
+ // slow but easy to understand:
+ std::vector<int> labelSizes;
+ for (int i = 0; i < pixelCount; i++) {
+ int regionCount = 0;
+ if (labelField[i] == -1 && cm[i] >= threshold) {
+ regionCount = depthFirstSearch(i, threshold, curlabel++);
+ labelSizes.emplace_back(regionCount);
+ }
+
+ if (regionCount > maxregion) {
+ maxregion = regionCount;
+ maxblob = curlabel-1;
+ }
+ }
+
+ for (int i = 0; i < pixelCount; i++) {
+ if (labelField[i] != -1) {
+ // remove if the component is to small
+ if (labelSizes[labelField[i]] * sizeFactorToKeep < maxregion) {
+ cm[i] = CERTAIN_BACKGROUND_CONFIDENCE;
+ }
+
+ // add maxblob always to foreground
+ if (labelField[i] == maxblob) {
+ cm[i] = CERTAIN_FOREGROUND_CONFIDENCE;
+ }
+ }
+ }
+}
+
+int Siox::depthFirstSearch(int startPos, float threshold, int curLabel)
+{
+ // stores positions of labeled pixels, where the neighbours
+ // should still be checked for processing:
+
+ // trace("startPos:%d threshold:%f curLabel:%d",
+ // startPos, threshold, curLabel);
+
+ std::vector<int> pixelsToVisit;
+ int componentSize = 0;
+
+ if (labelField[startPos] == -1 && cm[startPos] >= threshold) {
+ labelField[startPos] = curLabel;
+ componentSize++;
+ pixelsToVisit.emplace_back(startPos);
+ }
+
+ while (!pixelsToVisit.empty()) {
+ int pos = pixelsToVisit[pixelsToVisit.size() - 1];
+ pixelsToVisit.erase(pixelsToVisit.end() - 1);
+ int x = pos % width;
+ int y = pos / width;
+
+ // check all four neighbours
+ int left = pos - 1;
+ if (x - 1 >= 0 && labelField[left] == -1 && cm[left] >= threshold) {
+ labelField[left] = curLabel;
+ componentSize++;
+ pixelsToVisit.emplace_back(left);
+ }
+
+ int right = pos + 1;
+ if (x + 1 < width && labelField[right] == -1 && cm[right] >= threshold) {
+ labelField[right] = curLabel;
+ componentSize++;
+ pixelsToVisit.emplace_back(right);
+ }
+
+ int top = pos - width;
+ if (y - 1 >= 0 && labelField[top] == -1 && cm[top] >= threshold) {
+ labelField[top] = curLabel;
+ componentSize++;
+ pixelsToVisit.emplace_back(top);
+ }
+
+ int bottom = pos + width;
+ if (y + 1 < height && labelField[bottom] == -1 && cm[bottom] >= threshold) {
+ labelField[bottom] = curLabel;
+ componentSize++;
+ pixelsToVisit.emplace_back(bottom);
+ }
+ }
+
+ return componentSize;
+}
+
+void Siox::fillColorRegions()
+{
+ for (int idx = 0; idx < pixelCount; idx++) {
+ labelField[idx] = -1;
+ }
+
+ std::vector<int> pixelsToVisit;
+ for (int i = 0; i < pixelCount; i++) { // for all pixels
+ if (labelField[i] != -1 || cm[i] < UNKNOWN_REGION_CONFIDENCE) {
+ continue; // already visited or bg
+ }
+
+ uint32_t origColor = image[i];
+ int curLabel = i+1;
+ labelField[i] = curLabel;
+ cm[i] = CERTAIN_FOREGROUND_CONFIDENCE;
+
+ // int componentSize = 1;
+ pixelsToVisit.emplace_back(i);
+ // depth first search to fill region
+ while (!pixelsToVisit.empty()) {
+ int pos = pixelsToVisit[pixelsToVisit.size() - 1];
+ pixelsToVisit.erase(pixelsToVisit.end() - 1);
+ int x = pos % width;
+ int y = pos / width;
+ // check all four neighbours
+ int left = pos - 1;
+ if (x - 1 >= 0 && labelField[left] == -1 && CieLab::diff(image[left], origColor) < 1.0) {
+ labelField[left] = curLabel;
+ cm[left] = CERTAIN_FOREGROUND_CONFIDENCE;
+ // ++componentSize;
+ pixelsToVisit.emplace_back(left);
+ }
+ int right = pos + 1;
+ if (x + 1 < width && labelField[right] == -1 && CieLab::diff(image[right], origColor) < 1.0) {
+ labelField[right] = curLabel;
+ cm[right] = CERTAIN_FOREGROUND_CONFIDENCE;
+ // ++componentSize;
+ pixelsToVisit.emplace_back(right);
+ }
+ int top = pos - width;
+ if (y - 1 >= 0 && labelField[top] == -1 && CieLab::diff(image[top], origColor) < 1.0) {
+ labelField[top] = curLabel;
+ cm[top] = CERTAIN_FOREGROUND_CONFIDENCE;
+ // ++componentSize;
+ pixelsToVisit.emplace_back(top);
+ }
+ int bottom = pos + width;
+ if (y + 1 < height && labelField[bottom] == -1 && CieLab::diff(image[bottom], origColor) < 1.0) {
+ labelField[bottom] = curLabel;
+ cm[bottom] = CERTAIN_FOREGROUND_CONFIDENCE;
+ // ++componentSize;
+ pixelsToVisit.emplace_back(bottom);
+ }
+ }
+ }
+}
+
+} // namespace Trace
+} // namespace Inkscape
diff --git a/src/trace/siox.h b/src/trace/siox.h
new file mode 100644
index 0000000..55d0ce4
--- /dev/null
+++ b/src/trace/siox.h
@@ -0,0 +1,219 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+#ifndef INKSCAPE_TRACE_SIOX_H
+#define INKSCAPE_TRACE_SIOX_H
+/*
+ * Copyright 2005, 2006 by Gerald Friedland, Kristian Jantz and Lars Knipping
+ *
+ * Conversion to C++ for Inkscape by Bob Jamison
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+
+/*
+ * Note by Bob Jamison:
+ * After translating the siox.org Java API to C++ and receiving an
+ * education into this wonderful code, I began again,
+ * and started this version using lessons learned. This version is
+ * an attempt to provide an dependency-free SIOX engine that anyone
+ * can use in their project with minimal effort.
+ *
+ * Many thanks to the fine people at siox.org.
+ */
+
+#include <string>
+#include <vector>
+#include <gdkmm/pixbuf.h>
+#include <glib.h>
+#include "cielab.h"
+
+namespace Inkscape {
+namespace Async { template <typename... T> class Progress; }
+namespace Trace {
+
+/**
+ * SioxImage is the input/output format of Siox.
+ * It pairs a 32-bit image with an equally-sized matrix of floats representing foreground confidence values.
+ */
+class SioxImage
+{
+public:
+ /**
+ * Create an image from a Gdk::Pixbuf.
+ * A copy of the pixbuf is set as the pixel data, while the confidence matrix is initialized to zero.
+ */
+ SioxImage(Glib::RefPtr<Gdk::Pixbuf> const &buf);
+
+ /**
+ * Create a Gdk::Pixbuf from this image.
+ */
+ Glib::RefPtr<Gdk::Pixbuf> getGdkPixbuf() const;
+
+ /**
+ * Return the image data buffer.
+ */
+ uint32_t *getImageData() { return pixdata.data(); }
+ uint32_t const *getImageData() const { return pixdata.data(); }
+
+ /**
+ * Set a confidence value at the x, y coordinates to the given value.
+ */
+ void setConfidence(int x, int y, float conf) { cmdata[offset(x, y)] = conf; }
+
+ /**
+ * Return the confidence data buffer.
+ */
+ float *getConfidenceData() { return cmdata.data(); }
+ float const *getConfidenceData() const { return cmdata.data(); }
+
+ /**
+ * Return the width of this image
+ */
+ int getWidth() const { return width; }
+
+ /**
+ * Return the height of this image
+ */
+ int getHeight() const { return height; }
+
+ /**
+ * Save this image as a simple color PPM
+ */
+ bool writePPM(char const *filename) const;
+
+ /**
+ * Return an extremely naive but fast hash of the image/confidence map contents.
+ */
+ unsigned hash() const;
+
+private:
+ int width; ///< Width of the image
+ int height; ///< Height of the image
+ std::vector<uint32_t> pixdata; ///< Pixel data
+ std::vector<float> cmdata; ///< Confidence matrix data
+
+ /**
+ * Return the offset of a given pixel within both data arrays.
+ */
+ int constexpr offset(int x, int y) const { return width * y + x; }
+};
+
+class Siox
+{
+public:
+ /**
+ * Confidence corresponding to a certain foreground region (equals one).
+ */
+ static constexpr float CERTAIN_FOREGROUND_CONFIDENCE = 1.0f;
+
+ /**
+ * Confidence for a region likely being foreground.
+ */
+ static constexpr float FOREGROUND_CONFIDENCE = 0.8f;
+
+ /**
+ * Confidence for foreground or background type being equally likely.
+ */
+ static constexpr float UNKNOWN_REGION_CONFIDENCE = 0.5f;
+
+ /**
+ * Confidence for a region likely being background.
+ */
+ static constexpr float BACKGROUND_CONFIDENCE = 0.1f;
+
+ /**
+ * Confidence corresponding to a certain background reagion (equals zero).
+ */
+ static constexpr float CERTAIN_BACKGROUND_CONFIDENCE = 0.0f;
+
+ Siox(Async::Progress<double> &progress);
+
+ /**
+ * Extract the foreground of the original image, according to the values in the confidence matrix.
+ * If the operation fails or is aborted, an exception is thrown.
+ * \param backgroundFillColor Any ARGB color, such as 0xffffff (white) or 0x000000 (black).
+ * \throws Siox::Exception on error.
+ * \throws Async::CancelledException on cancellation.
+ */
+ SioxImage extractForeground(SioxImage const &originalImage, uint32_t backgroundFillColor);
+
+ class Exception {};
+
+private:
+ Async::Progress<double> *progress;
+
+ int width; ///< Width of the image
+ int height; ///< Height of the image
+ int pixelCount; ///< Number of pixels in the image
+ uint32_t *image; ///< Working image data
+ float *cm; ///< Working image confidence matrix
+
+ /**
+ * Markup for image editing
+ */
+ int *labelField;
+
+ /**
+ * Our signature limits
+ */
+ float limits[3];
+
+ /**
+ * Maximum distance of two lab values.
+ */
+ float clusterSize;
+
+ /**
+ * Initialize the Siox engine to its 'pristine' state.
+ * Performed at the beginning of extractForeground().
+ */
+ void init();
+
+ /**
+ * Error logging
+ */
+ void error(std::string const &str);
+
+ /**
+ * Trace logging
+ */
+ void trace(std::string const &str);
+
+ /**
+ * Stage 1 of the color signature work. 'dims' will be either 2 for grays, or 3 for colors.
+ */
+ void colorSignatureStage1(CieLab *points,
+ unsigned leftBase,
+ unsigned rightBase,
+ unsigned recursionDepth,
+ unsigned *clusters,
+ unsigned dims);
+
+ /**
+ * Stage 2 of the color signature work
+ */
+ void colorSignatureStage2(CieLab *points,
+ unsigned leftBase,
+ unsigned rightBase,
+ unsigned recursionDepth,
+ unsigned *clusters,
+ float threshold,
+ unsigned dims);
+
+ /**
+ * Main color signature method
+ */
+ void colorSignature(std::vector<CieLab> const &inputVec,
+ std::vector<CieLab> &result,
+ unsigned dims);
+
+ void keepOnlyLargeComponents(float threshold, double sizeFactorToKeep);
+
+ int depthFirstSearch(int startPos, float threshold, int curLabel);
+
+ void fillColorRegions();
+};
+
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_SIOX_H
diff --git a/src/trace/trace.cpp b/src/trace/trace.cpp
new file mode 100644
index 0000000..ed39825
--- /dev/null
+++ b/src/trace/trace.cpp
@@ -0,0 +1,538 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * A generic interface for plugging different
+ * autotracers into Inkscape.
+ *
+ * Authors:
+ * Bob Jamison <rjamison@earthlink.net>
+ * Jon A. Cruz <jon@joncruz.org>
+ * Abhishek Sharma
+ * PBS <pbs3141@gmail.com>
+ *
+ * Copyright (C) 2004-2022 Authors
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#include <limits>
+#include <mutex>
+#include <algorithm>
+#include <cassert>
+#include <2geom/transforms.h>
+#include <glibmm/i18n.h>
+
+#include "trace.h"
+#include "siox.h"
+
+#include "desktop.h"
+#include "document.h"
+#include "document-undo.h"
+#include "helper/geom.h"
+#include "inkscape.h"
+#include "message-stack.h"
+#include "selection.h"
+#include "svg/svg.h"
+
+#include "async/async.h"
+#include "async/progress-splitter.h"
+#include "async/background-progress.h"
+
+#include "display/cairo-utils.h"
+#include "display/drawing.h"
+#include "display/drawing-context.h"
+
+#include "object/sp-item.h"
+#include "object/sp-image.h"
+#include "object/weakptr.h"
+
+#include "ui/icon-names.h"
+
+#include "xml/repr.h"
+#include "xml/attribute-record.h"
+
+namespace Inkscape {
+namespace Trace {
+namespace {
+
+/**
+ * Grab the image and siox items from the current selection, performing some validation.
+ * \pre SP_ACTIVE_DESKTOP must not be null.
+ */
+std::optional<std::pair<SPImage*, std::vector<SPItem*>>> getImageAndItems(bool sioxEnabled, bool notifications = true)
+{
+ auto desktop = SP_ACTIVE_DESKTOP;
+ auto msgStack = desktop->getMessageStack();
+ auto sel = desktop->getSelection();
+
+ if (sioxEnabled) {
+ auto selection = std::vector<SPItem*>(sel->items().begin(), sel->items().end());
+ std::sort(selection.begin(), selection.end(), sp_item_repr_compare_position_bool);
+
+ SPImage *img = nullptr;
+ std::vector<SPItem*> items;
+
+ for (auto item : selection) {
+ if (auto itemimg = cast<SPImage>(item)) {
+ if (img) { // we want only one
+ if (notifications) msgStack->flash(Inkscape::ERROR_MESSAGE, _("Select only one <b>image</b> to trace"));
+ return {};
+ }
+ img = itemimg;
+ } else if (img) { // Items are processed back-to-front, so this means "above the image".
+ items.emplace_back(item);
+ }
+ }
+
+ if (!img || items.empty()) {
+ if (notifications) msgStack->flash(Inkscape::ERROR_MESSAGE, _("Select one image and one or more shapes above it"));
+ return {};
+ }
+
+ return std::make_pair(img, std::move(items));
+ } else {
+ // SIOX not enabled. We want exactly one image selected.
+ auto item = sel->singleItem();
+ if (!item) {
+ if (notifications) msgStack->flash(Inkscape::ERROR_MESSAGE, _("Select an <b>image</b> to trace")); // same as above
+ return {};
+ }
+
+ auto img = cast<SPImage>(item);
+ if (!img) {
+ if (notifications) msgStack->flash(Inkscape::ERROR_MESSAGE, _("Select an <b>image</b> to trace"));
+ return {};
+ }
+
+ return {{ img, {} }};
+ }
+}
+
+/**
+ * Given an SPImage, get the transform from pixbuf coordinates to the document.
+ */
+Geom::Affine getImageTransform(SPImage const *img)
+{
+ double x = img->x.computed;
+ double y = img->y.computed;
+ double w = img->width.computed;
+ double h = img->height.computed;
+
+ int iw = img->pixbuf->width();
+ int ih = img->pixbuf->height();
+
+ double wscale = w / iw;
+ double hscale = h / ih;
+
+ return Geom::Scale(wscale, hscale) * Geom::Translate(x, y) * img->transform;
+}
+
+Geom::IntPoint dimensions(Inkscape::Pixbuf const &pixbuf)
+{
+ return { pixbuf.width(), pixbuf.height() };
+}
+
+bool confirm_image_size(TracingEngine const *engine, Geom::IntPoint const &dimensions)
+{
+ if (engine->check_image_size(dimensions)) {
+ char const *msg = _("Image looks too big. Process may take a while and it is"
+ " wise to save your document before continuing."
+ "\n\nContinue the procedure (without saving)?");
+ Gtk::MessageDialog dialog(msg, false, Gtk::MESSAGE_WARNING, Gtk::BUTTONS_OK_CANCEL, true);
+
+ if (dialog.run() != Gtk::RESPONSE_OK) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+/**
+ * Given a list of SPItems, apply a transform and rasterize them to a surface of the specified dimensions.
+ */
+Cairo::RefPtr<Cairo::ImageSurface> rasterizeItems(std::vector<SPItem*> &items, Geom::Affine const &affine, Geom::IntPoint dimensions)
+{
+ auto surface = Cairo::ImageSurface::create(Cairo::FORMAT_ARGB32, dimensions.x(), dimensions.y());
+ auto dc = Inkscape::DrawingContext(surface->cobj(), {});
+ auto const inv = affine.inverse();
+
+ auto dkey = SPItem::display_key_new(1);
+ Inkscape::Drawing drawing;
+
+ for (auto item : items) {
+ auto ai = item->invoke_show(drawing, dkey, SP_ITEM_SHOW_DISPLAY);
+ drawing.setRoot(ai);
+ auto rect = Geom::IntRect({0, 0}, dimensions);
+ drawing.update(rect, inv);
+ drawing.render(dc, rect);
+ item->invoke_hide(dkey);
+ }
+
+ return surface;
+}
+
+class SioxImageCache
+{
+public:
+ static auto &get()
+ {
+ static SioxImageCache const instance;
+ return instance;
+ }
+
+ Glib::RefPtr<Gdk::Pixbuf> process(SioxImage const &sioximage, Async::Progress<double> &progress) const;
+
+private:
+ mutable std::mutex mutables;
+ mutable unsigned last_hash = 0;
+ mutable Glib::RefPtr<Gdk::Pixbuf> last_result;
+
+ SioxImageCache() = default;
+};
+
+Glib::RefPtr<Gdk::Pixbuf> SioxImageCache::process(SioxImage const &sioximage, Async::Progress<double> &progress) const
+{
+ auto hash = sioximage.hash();
+
+ auto g = std::lock_guard(mutables);
+
+ if (hash == last_hash) {
+ return last_result;
+ }
+
+ auto result = Siox(progress).extractForeground(sioximage, 0xffffff);
+
+ // result.writePPM("siox2.ppm");
+
+ last_hash = hash;
+ last_result = result.getGdkPixbuf();
+
+ return last_result;
+}
+
+Glib::RefPtr<Gdk::Pixbuf> sioxProcessImage(Glib::RefPtr<Gdk::Pixbuf> pixbuf, Cairo::RefPtr<Cairo::ImageSurface> siox_mask, Async::Progress<double> &progress)
+{
+ // Copy the pixbuf into the siox image.
+ auto sioximage = SioxImage(pixbuf);
+ int iwidth = sioximage.getWidth();
+ int iheight = sioximage.getHeight();
+
+ // Copy the mask into the siox image.
+ assert(iwidth == siox_mask->get_width());
+ assert(iheight == siox_mask->get_height());
+ for (int y = 0; y < iheight; y++) {
+ for (int x = 0; x < iwidth; x++) {
+ auto p = siox_mask->get_data() + y * siox_mask->get_stride() + 4 * x;
+ float a = p[3] / 255.0f;
+ float cm = Siox::CERTAIN_BACKGROUND_CONFIDENCE + (Siox::UNKNOWN_REGION_CONFIDENCE - Siox::CERTAIN_BACKGROUND_CONFIDENCE) * a;
+ sioximage.setConfidence(x, y, cm);
+ }
+ }
+
+ /*auto tmp = simage;
+ for (int i = 0; i < iwidth * iheight; i++) {
+ tmp.getImageData()[i] = 255 * tmp.getConfidenceData()[i];
+ }
+ tmp.writePPM("/tmp/x1.ppm");*/
+
+ // Process or retrieve from cache.
+ return SioxImageCache::get().process(sioximage, progress);
+}
+
+} // namespace
+
+namespace detail {
+
+struct TraceFutureCreate
+{
+ TraceFutureCreate() = delete;
+
+ static auto create(decltype(TraceFuture::channel) &&channel, decltype(TraceFuture::image_watcher) &&image_watcher)
+ {
+ TraceFuture result;
+ result.channel = std::move(channel);
+ result.image_watcher = std::move(image_watcher);
+ return result;
+ }
+};
+
+} // namespace detail
+
+// Todo: Consider rewriting using C++20 coroutines.
+class TraceTask
+{
+public:
+ TraceTask(std::unique_ptr<TracingEngine> engine, bool sioxEnabled, std::function<void(double)> onprogress, std::function<void()> onfinished)
+ : engine(std::move(engine))
+ , sioxEnabled(sioxEnabled)
+ , type(Type::Trace)
+ , onprogress(std::move(onprogress))
+ , onfinished_trace(std::move(onfinished)) {}
+
+ TraceTask(std::unique_ptr<TracingEngine> engine, bool sioxEnabled, std::function<void(Glib::RefPtr<Gdk::Pixbuf>)> onfinished)
+ : engine(std::move(engine))
+ , sioxEnabled(sioxEnabled)
+ , type(Type::Preview)
+ , onprogress([] (auto&&) {})
+ , onfinished_preview(std::move(onfinished)) {}
+
+ TraceTask(TraceTask const &) = delete;
+ TraceTask &operator=(TraceTask const &) = delete;
+
+ TraceFuture launch(std::unique_ptr<TraceTask> self);
+
+private:
+ std::unique_ptr<TracingEngine> engine;
+ bool sioxEnabled;
+
+ // Whether this is the full trace task, or just the preview task.
+ enum class Type
+ {
+ Trace,
+ Preview
+ };
+ Type type;
+
+ // Unsafe. Cannot call from worker thread since may perform actions in main thread. (This isn't Rust so we need a comment.)
+ std::function<void(double)> onprogress;
+ std::function<void()> onfinished_trace; // For trace task.
+ std::function<void(Glib::RefPtr<Gdk::Pixbuf>)> onfinished_preview; // For preview task.
+
+ // Unsafe. Cannot lock from worker thread since must be destroyed by main thread. (See above.)
+ std::weak_ptr<SPWeakPtr<SPImage>> image_watcher_weak;
+
+ std::shared_ptr<Inkscape::Pixbuf const> image_pixbuf;
+ Geom::Affine image_transform;
+ Cairo::RefPtr<Cairo::ImageSurface> siox_mask;
+ Async::Channel::Source channel;
+
+ TraceResult traceresult;
+
+ void do_async_work(std::unique_ptr<TraceTask> self);
+ void do_final_work(std::unique_ptr<TraceTask> self);
+};
+
+TraceFuture trace(std::unique_ptr<TracingEngine> engine, bool sioxEnabled, std::function<void(double)> onprogress, std::function<void()> onfinished)
+{
+ auto task = std::make_unique<TraceTask>(std::move(engine), sioxEnabled, std::move(onprogress), std::move(onfinished));
+ auto saved = task.get();
+ return saved->launch(std::move(task));
+}
+
+TraceFuture preview(std::unique_ptr<TracingEngine> engine, bool sioxEnabled, std::function<void(Glib::RefPtr<Gdk::Pixbuf>)> onfinished)
+{
+ auto task = std::make_unique<TraceTask>(std::move(engine), sioxEnabled, std::move(onfinished));
+ auto saved = task.get();
+ return saved->launch(std::move(task));
+}
+
+TraceFuture TraceTask::launch(std::unique_ptr<TraceTask> self)
+{
+ // Grab data and validate setup.
+
+ auto desktop = SP_ACTIVE_DESKTOP;
+ if (!desktop) {
+ g_warning("Trace: No active desktop\n");
+ return {};
+ }
+
+ auto msgStack = desktop->getMessageStack();
+
+ auto doc = SP_ACTIVE_DOCUMENT;
+ if (!doc) {
+ if (type == Type::Trace) msgStack->flash(Inkscape::ERROR_MESSAGE, _("Trace: No active document"));
+ return {};
+ }
+ doc->ensureUpToDate();
+
+ auto imageanditems = getImageAndItems(sioxEnabled, type == Type::Trace);
+ if (!imageanditems) {
+ return {};
+ }
+
+ // Copy into coroutine frame.
+
+ auto image = imageanditems->first;
+
+ image_pixbuf = image->pixbuf; // Note: image->pixbuf is immutable, so can be shared thread-safely.
+ if (!image_pixbuf) {
+ if (type == Type::Trace) msgStack->flash(Inkscape::ERROR_MESSAGE, _("Trace: Image has no bitmap data"));
+ return {};
+ }
+
+ if (type == Type::Trace && !confirm_image_size(engine.get(), dimensions(*image_pixbuf))) {
+ // Image is too big and user decided to cancel.
+ return {};
+ }
+
+ image_transform = getImageTransform(image);
+
+ if (sioxEnabled) {
+ siox_mask = rasterizeItems(imageanditems->second, image_transform, dimensions(*image_pixbuf));
+ }
+
+ if (type == Type::Trace) msgStack->flash(Inkscape::NORMAL_MESSAGE, _("Trace: Starting trace..."));
+
+ // Open channel and launch background task.
+
+ auto [src, dst] = Async::Channel::create();
+ auto image_watcher = std::make_shared<SPWeakPtr<SPImage>>(image);
+
+ channel = std::move(src);
+ image_watcher_weak = image_watcher;
+
+ Async::fire_and_forget([this, self = std::move(self)] () mutable {
+ do_async_work(std::move(self));
+ });
+
+ return detail::TraceFutureCreate::create(std::move(dst), std::move(image_watcher));
+}
+
+void TraceTask::do_async_work(std::unique_ptr<TraceTask> self)
+{
+ if (!channel) {
+ // Cancelled while suspended.
+ return;
+ }
+
+ try {
+ auto progress = Async::BackgroundProgress(channel, onprogress);
+ auto throttled = Async::ProgressTimeThrottler(progress, std::chrono::milliseconds(10));
+
+ // Get progress subobjects for siox and trace sub-tasks.
+ std::optional<Async::SubProgress<double>> sub_siox, sub_trace;
+
+ Async::ProgressSplitter(throttled)
+ .add_if(sub_siox, 0.1, sioxEnabled)
+ .add_if(sub_trace, 0.9, type == Type::Trace);
+
+ // Convert the pixbuf to a GdkPixbuf, which due to immutability requires making a copy first.
+ auto copy = Pixbuf(*image_pixbuf);
+ auto gdkpixbuf = Glib::wrap(copy.getPixbufRaw(), true);
+
+ // If SIOX has been enabled, run SIOX processing.
+ if (sioxEnabled) {
+ gdkpixbuf = sioxProcessImage(gdkpixbuf, siox_mask, *sub_siox);
+ siox_mask.clear();
+ sub_siox->report_or_throw(1.0);
+ }
+
+ // If in preview mode, compute and return the preview and exit now.
+ if (type == Type::Preview) {
+ gdkpixbuf = engine->preview(gdkpixbuf);
+ channel.run(std::bind(onfinished_preview, std::move(gdkpixbuf)));
+ return;
+ }
+
+ // Actually perform the tracing.
+ traceresult = engine->trace(gdkpixbuf, *sub_trace);
+
+ gdkpixbuf.reset();
+
+ progress.report_or_throw(1.0);
+
+ // Return to the original thread for the remainder of the processing.
+ channel.run([this, self = std::move(self)] () mutable {
+ do_final_work(std::move(self));
+ });
+
+ } catch (Async::CancelledException const &) {
+
+ // no need to emit signals if manually aborted
+
+ } catch (...) {
+
+ g_warning("TraceTask::do_async_work: tracing aborted due to exception");
+ if (type == Type::Trace) {
+ channel.run(onfinished_trace);
+ } else {
+ channel.run(std::bind(onfinished_preview, Glib::RefPtr<Gdk::Pixbuf>()));
+ }
+
+ }
+}
+
+void TraceTask::do_final_work(std::unique_ptr<TraceTask> self)
+{
+ assert(type == Type::Trace);
+ assert(channel);
+
+ auto doc = SP_ACTIVE_DOCUMENT;
+ auto desktop = SP_ACTIVE_DESKTOP;
+ auto image_watcher = image_watcher_weak.lock();
+
+ if (!doc || !desktop || !image_watcher || traceresult.empty()) {
+ onfinished_trace();
+ return;
+ }
+
+ auto image = image_watcher->get();
+ if (!image) {
+ // Image was deleted.
+ onfinished_trace();
+ return;
+ }
+
+ auto msgStack = desktop->getMessageStack();
+ auto selection = desktop->getSelection();
+
+ // Get pointers to the <image> and its parent.
+ // XML Tree being used directly here while it shouldn't be
+ Inkscape::XML::Node *imgRepr = image->getRepr();
+ Inkscape::XML::Node *par = imgRepr->parent();
+
+ // Update the image transform - it may have changed from its initial value.
+ image_transform = getImageTransform(image);
+
+ // OK. Now let's start making new nodes.
+ Inkscape::XML::Document *xml_doc = desktop->doc()->getReprDoc();
+ Inkscape::XML::Node *groupRepr = nullptr;
+
+ // If more than one path, make a <g>roup of <path>s.
+ int nrPaths = traceresult.size();
+ if (nrPaths > 1) {
+ groupRepr = xml_doc->createElement("svg:g");
+ par->addChild(groupRepr, imgRepr);
+ }
+
+ long totalNodeCount = 0;
+
+ for (auto const &result : traceresult) {
+ totalNodeCount += count_pathvector_nodes(result.path);
+
+ Inkscape::XML::Node *pathRepr = xml_doc->createElement("svg:path");
+ pathRepr->setAttributeOrRemoveIfEmpty("style", result.style);
+ pathRepr->setAttributeOrRemoveIfEmpty("d", sp_svg_write_path(result.path * image_transform));
+
+ if (nrPaths > 1) {
+ groupRepr->addChild(pathRepr, nullptr);
+ } else {
+ par->addChild(pathRepr, imgRepr);
+ }
+
+ if (nrPaths == 1) {
+ selection->clear();
+ selection->add(pathRepr);
+ }
+
+ Inkscape::GC::release(pathRepr);
+ }
+
+ // If we have a group, then focus on it.
+ if (nrPaths > 1) {
+ selection->clear();
+ selection->add(groupRepr);
+ Inkscape::GC::release(groupRepr);
+ }
+
+ // Inform the document, so we can undo.
+ DocumentUndo::done(doc, _("Trace bitmap"), INKSCAPE_ICON("bitmap-trace"));
+
+ char *msg = g_strdup_printf(_("Trace: Done. %ld nodes created"), totalNodeCount);
+ msgStack->flash(Inkscape::NORMAL_MESSAGE, msg);
+ g_free(msg);
+
+ onfinished_trace();
+}
+
+} // namespace Trace
+} // namespace Inkscape
diff --git a/src/trace/trace.h b/src/trace/trace.h
new file mode 100644
index 0000000..0bb39d6
--- /dev/null
+++ b/src/trace/trace.h
@@ -0,0 +1,103 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Authors:
+ * Bob Jamison <rjamison@titan.com>
+ *
+ * Copyright (C) 2004-2006 Bob Jamison
+ *
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+#ifndef INKSCAPE_TRACE_H
+#define INKSCAPE_TRACE_H
+
+#include <vector>
+#include <utility>
+#include <cstring>
+#include <2geom/pathvector.h>
+#include <gdkmm/pixbuf.h>
+#include "async/channel.h"
+#include "object/weakptr.h"
+#include "object/sp-image.h"
+
+namespace Inkscape {
+namespace Async { template <typename... T> class Progress; }
+namespace Trace {
+
+struct TraceResultItem
+{
+ TraceResultItem(std::string style_, Geom::PathVector path_)
+ : style(std::move(style_))
+ , path(std::move(path_)) {}
+
+ std::string style;
+ Geom::PathVector path;
+};
+
+using TraceResult = std::vector<TraceResultItem>;
+
+/**
+ * A generic interface for plugging different autotracers into Inkscape.
+ */
+class TracingEngine
+{
+public:
+ TracingEngine() = default;
+ virtual ~TracingEngine() = default;
+
+ /**
+ * This is the working method of this interface, and all implementing classes. Take a
+ * GdkPixbuf, trace it, and return a style attribute and the path data that is
+ * compatible with the d="" attribute of an SVG <path> element.
+ *
+ * This function will be called off-main-thread, so is required to be thread-safe.
+ * The lack of const however indicates that it is not required to be re-entrant.
+ */
+ virtual TraceResult trace(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf, Async::Progress<double> &progress) = 0;
+
+ /**
+ * Generate a quick preview without any actual tracing. Like trace(), this must be thread-safe.
+ */
+ virtual Glib::RefPtr<Gdk::Pixbuf> preview(Glib::RefPtr<Gdk::Pixbuf> const &pixbuf) = 0;
+
+ /**
+ * Return true if the user should be checked with before tracing because the image is too big.
+ */
+ virtual bool check_image_size(Geom::IntPoint const &size) const { return false; }
+};
+
+namespace detail { struct TraceFutureCreate; }
+
+class TraceFuture
+{
+public:
+ void cancel() { channel.close(); image_watcher.reset(); }
+ explicit operator bool() const { return (bool)channel; }
+
+private:
+ Async::Channel::Dest channel;
+ std::shared_ptr<SPWeakPtr<SPImage>> image_watcher;
+ friend class detail::TraceFutureCreate;
+};
+
+/**
+ * Launch an asynchronous trace operation taking as input \a engine and \a sioxEnabled.
+ * If this returns null, the task failed to launch and no further action will be taken.
+ * Otherwise, a background task is launched which will call \a onprogress some number of times
+ * followed by \a onfinished exactly once. Both callbacks are invoked from the GTK main loop.
+ */
+TraceFuture trace(std::unique_ptr<TracingEngine> engine,
+ bool sioxEnabled,
+ std::function<void(double)> onprogress,
+ std::function<void()> onfinished);
+
+/**
+ * Similar to \a trace(), but computes the preview and passes it to \a onfinished when done.
+ */
+TraceFuture preview(std::unique_ptr<TracingEngine> engine,
+ bool sioxEnabled,
+ std::function<void(Glib::RefPtr<Gdk::Pixbuf>)> onfinished);
+
+} // namespace Trace
+} // namespace Inkscape
+
+#endif // INKSCAPE_TRACE_H
generated by cgit v1.2.3 (git 2.39.1) at 2024-10-07 22:19:39 +0000