summaryrefslogtreecommitdiffstats
path: root/src/3rdparty/libdepixelize
diff options
context:
space:
mode:
Diffstat (limited to 'src/3rdparty/libdepixelize')
-rw-r--r--src/3rdparty/libdepixelize/CMakeLists.txt24
-rw-r--r--src/3rdparty/libdepixelize/README7
-rw-r--r--src/3rdparty/libdepixelize/kopftracer2011.cpp665
-rw-r--r--src/3rdparty/libdepixelize/kopftracer2011.h150
-rw-r--r--src/3rdparty/libdepixelize/priv/branchless.h58
-rw-r--r--src/3rdparty/libdepixelize/priv/colorspace.h111
-rw-r--r--src/3rdparty/libdepixelize/priv/curvature.h115
-rw-r--r--src/3rdparty/libdepixelize/priv/homogeneoussplines.h472
-rw-r--r--src/3rdparty/libdepixelize/priv/integral.h61
-rw-r--r--src/3rdparty/libdepixelize/priv/iterator.h123
-rw-r--r--src/3rdparty/libdepixelize/priv/optimization-kopf2011.h263
-rw-r--r--src/3rdparty/libdepixelize/priv/pixelgraph.h555
-rw-r--r--src/3rdparty/libdepixelize/priv/point.h112
-rw-r--r--src/3rdparty/libdepixelize/priv/simplifiedvoronoi.h1707
-rw-r--r--src/3rdparty/libdepixelize/priv/splines-kopf2011.h167
-rw-r--r--src/3rdparty/libdepixelize/splines.h120
16 files changed, 4710 insertions, 0 deletions
diff --git a/src/3rdparty/libdepixelize/CMakeLists.txt b/src/3rdparty/libdepixelize/CMakeLists.txt
new file mode 100644
index 0000000..8c7df77
--- /dev/null
+++ b/src/3rdparty/libdepixelize/CMakeLists.txt
@@ -0,0 +1,24 @@
+
+set(libdepixelize_SRC
+ kopftracer2011.cpp
+
+ # -------
+ # Headers
+ kopftracer2011.h
+ splines.h
+
+ priv/branchless.h
+ priv/colorspace.h
+ priv/curvature.h
+ priv/homogeneoussplines.h
+ priv/integral.h
+ priv/iterator.h
+ priv/optimization-kopf2011.h
+ priv/pixelgraph.h
+ priv/point.h
+ priv/simplifiedvoronoi.h
+ priv/splines-kopf2011.h
+)
+
+add_inkscape_lib(depixelize_LIB "${libdepixelize_SRC}")
+target_link_libraries(depixelize_LIB PUBLIC 2Geom::2geom) \ No newline at end of file
diff --git a/src/3rdparty/libdepixelize/README b/src/3rdparty/libdepixelize/README
new file mode 100644
index 0000000..1f9c0fd
--- /dev/null
+++ b/src/3rdparty/libdepixelize/README
@@ -0,0 +1,7 @@
+Libdepixelize pixelart tracing library.
+
+This code must be kept in sync with our "upstream" project
+https://gitlab.com/inkscape/devel/libdepixelize
+
+Any change must first (or in parallel) be submitted to the upstream project
+and ideally be tested there, independently of Inkscape.
diff --git a/src/3rdparty/libdepixelize/kopftracer2011.cpp b/src/3rdparty/libdepixelize/kopftracer2011.cpp
new file mode 100644
index 0000000..96784b1
--- /dev/null
+++ b/src/3rdparty/libdepixelize/kopftracer2011.cpp
@@ -0,0 +1,665 @@
+/* This file is part of the libdepixelize project
+ Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+ GNU Lesser General Public License Usage
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by the
+ Free Software Foundation; either version 2.1 of the License, or (at your
+ option) any later version.
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library. If not, see <http://www.gnu.org/licenses/>.
+
+ GNU General Public License Usage
+ Alternatively, this library may be used under the terms of the GNU General
+ Public License as published by the Free Software Foundation, either version
+ 2 of the License, or (at your option) any later version.
+ You should have received a copy of the GNU General Public License along with
+ this library. If not, see <http://www.gnu.org/licenses/>.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+*/
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include <glibmm.h>
+
+#include <algorithm>
+#include "kopftracer2011.h"
+#include "priv/colorspace.h"
+#include "priv/homogeneoussplines.h"
+#include "priv/branchless.h"
+#include "priv/splines-kopf2011.h"
+#include "priv/iterator.h"
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+#include <glibmm/datetime.h>
+#include <iostream>
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+namespace Tracer {
+namespace Heuristics {
+
+int curves(const PixelGraph &graph, PixelGraph::const_iterator a,
+ PixelGraph::const_iterator b);
+bool islands(PixelGraph::const_iterator a, PixelGraph::const_iterator b);
+
+struct SparsePixels
+{
+ enum Diagonal {
+ /**
+ * From (first) the top left corner to (second) the bottom right.
+ */
+ MAIN_DIAGONAL = 0,
+ /**
+ * From (first) the top right to (second) the bottom left.
+ */
+ SECONDARY_DIAGONAL = 1
+ };
+
+ typedef std::pair<PixelGraph::const_iterator, PixelGraph::const_iterator>
+ Edge;
+ typedef std::pair<Edge, int> EdgeWeight;
+
+ void operator()(const PixelGraph &graph, unsigned radius);
+
+ static bool similar_colors(PixelGraph::const_iterator n,
+ const guint8 (&a)[4], const guint8 (&b)[4]);
+
+ /*
+ * Precondition: Must be filled according to Diagonal enum.
+ */
+ EdgeWeight diagonals[2];
+};
+
+} // namespace Heuristics
+
+Splines Kopf2011::to_voronoi(const std::string &filename,
+ const Options &options)
+{
+ return to_voronoi(Gdk::Pixbuf::create_from_file(filename), options);
+}
+
+Splines Kopf2011::to_voronoi(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
+ const Options &options)
+{
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ SimplifiedVoronoi<Precision, false> voronoi
+ = _voronoi<Precision, false>(buf, options);
+
+ Glib::DateTime profiling_info[2];
+ profiling_info[0] = Glib::DateTime::create_now_utc();
+
+ Splines ret(voronoi);
+
+ profiling_info[1] = Glib::DateTime::create_now_utc();
+ std::cerr << "Tracer::Splines construction time: "
+ << profiling_info[1].difference(profiling_info[0])
+ << std::endl;
+
+ return ret;
+#else // LIBDEPIXELIZE_PROFILE_KOPF2011
+ return Splines(_voronoi<Precision, false>(buf, options));
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+}
+
+Splines Kopf2011::to_grouped_voronoi(const std::string &filename,
+ const Options &options)
+{
+ return to_grouped_voronoi(Gdk::Pixbuf::create_from_file(filename), options);
+}
+
+Splines Kopf2011::to_grouped_voronoi(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
+ const Options &options)
+{
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ SimplifiedVoronoi<Precision, false> voronoi
+ = _voronoi<Precision, false>(buf, options);
+
+ Glib::DateTime profiling_info[2];
+ profiling_info[0] = Glib::DateTime::create_now_utc();
+
+ HomogeneousSplines<Precision> splines(voronoi);
+
+#else // LIBDEPIXELIZE_PROFILE_KOPF2011
+ HomogeneousSplines<Precision> splines(_voronoi<Precision, false>
+ (buf, options));
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ profiling_info[1] = Glib::DateTime::create_now_utc();
+ std::cerr << "Tracer::HomogeneousSplines<" << typeid(Precision).name()
+ << ">(Tracer::SimplifiedVoronoi<" << typeid(Precision).name()
+ << ",false>) construction time: "
+ << profiling_info[1].difference(profiling_info[0])
+ << std::endl;
+ profiling_info[0] = Glib::DateTime::create_now_utc();
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+ for ( HomogeneousSplines<Precision>::iterator it = splines.begin(),
+ end = splines.end() ; it != end ; ++it ) {
+ for ( HomogeneousSplines<Precision>::Polygon::points_iter
+ it2 = it->vertices.begin(), end2 = it->vertices.end()
+ ; it2 != end2 ; ++it2 ) {
+ it2->smooth = false;
+ }
+ for ( HomogeneousSplines<Precision>::Polygon::holes_iter
+ it2 = it->holes.begin(), end2 = it->holes.end()
+ ; it2 != end2 ; ++it2 ) {
+ for ( HomogeneousSplines<Precision>::Polygon::points_iter
+ it3 = it2->begin(), end3 = it2->end()
+ ; it3 != end3 ; ++it3 ) {
+ it3->smooth = false;
+ }
+ }
+ }
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ profiling_info[1] = Glib::DateTime::create_now_utc();
+ std::cerr << "Tracer::Kopf2011::to_grouped_voronoi internal work time: "
+ << profiling_info[1].difference(profiling_info[0])
+ << std::endl;
+ profiling_info[0] = Glib::DateTime::create_now_utc();
+
+ Splines ret(splines, false, options.nthreads);
+
+ profiling_info[1] = Glib::DateTime::create_now_utc();
+ std::cerr << "Tracer::Splines construction time: "
+ << profiling_info[1].difference(profiling_info[0])
+ << std::endl;
+
+ return ret;
+#else // LIBDEPIXELIZE_PROFILE_KOPF2011
+ return Splines(splines, false, options.nthreads);
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+}
+
+Splines Kopf2011::to_splines(const std::string &filename,
+ const Options &options)
+{
+ return to_splines(Gdk::Pixbuf::create_from_file(filename), options);
+}
+
+Splines Kopf2011::to_splines(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
+ const Options &options)
+{
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ SimplifiedVoronoi<Precision, true> voronoi
+ = _voronoi<Precision, true>(buf, options);
+
+ Glib::DateTime profiling_info[2];
+ profiling_info[0] = Glib::DateTime::create_now_utc();
+
+ HomogeneousSplines<Precision> splines(voronoi);
+
+ profiling_info[1] = Glib::DateTime::create_now_utc();
+ std::cerr << "Tracer::HomogeneousSplines<" << typeid(Precision).name()
+ << "> construction time: "
+ << profiling_info[1].difference(profiling_info[0])
+ << std::endl;
+
+ profiling_info[0] = Glib::DateTime::create_now_utc();
+
+ Splines ret(splines, options.optimize, options.nthreads);
+
+ profiling_info[1] = Glib::DateTime::create_now_utc();
+ std::cerr << "Tracer::Splines construction time: "
+ << profiling_info[1].difference(profiling_info[0])
+ << std::endl;
+
+ return ret;
+#else // LIBDEPIXELIZE_PROFILE_KOPF2011
+ HomogeneousSplines<Precision> splines(_voronoi<Precision, true>
+ (buf, options));
+ return Splines(splines, options.optimize, options.nthreads);
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+}
+
+template<class T, bool adjust_splines>
+SimplifiedVoronoi<T, adjust_splines>
+Kopf2011::_voronoi(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
+ const Options &options)
+{
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ Glib::DateTime profiling_info[2];
+ profiling_info[0] = Glib::DateTime::create_now_utc();
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+ PixelGraph graph(buf);
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ profiling_info[1] = Glib::DateTime::create_now_utc();
+ std::cerr << "Tracer::PixelGraph creation time: "
+ << profiling_info[1].difference(profiling_info[0]) << std::endl;
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+ // gdk-pixbuf2 already checks if image size is meaningful, but asserts state
+ // preconditions and will be useful if gdk-pixbuf is replaced later
+ assert(graph.width() > 0);
+ assert(graph.height() > 0);
+
+#ifndef NDEBUG
+ graph.checkConsistency();
+#endif
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ profiling_info[0] = Glib::DateTime::create_now_utc();
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+ // This step could be part of the initialization of PixelGraph
+ // and decrease the necessary number of passes
+ graph.connectAllNeighbors();
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ profiling_info[1] = Glib::DateTime::create_now_utc();
+ std::cerr << "Tracer::PixelGraph::connectAllNeighbors() time: "
+ << profiling_info[1].difference(profiling_info[0]) << std::endl;
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+#ifndef NDEBUG
+ graph.checkConsistency();
+#endif
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ profiling_info[0] = Glib::DateTime::create_now_utc();
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+ // This step can't be part of PixelGraph initilization without adding some
+ // cache misses due to random access patterns that might be injected
+ _disconnect_neighbors_with_dissimilar_colors(graph);
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ profiling_info[1] = Glib::DateTime::create_now_utc();
+ std::cerr << "Tracer::Kopf2011::"
+ "_disconnect_neighbors_with_dissimilar_colors(Tracer::PixelGraph) time: "
+ << profiling_info[1].difference(profiling_info[0]) << std::endl;
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+#ifndef NDEBUG
+ graph.checkConsistency();
+#endif
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ profiling_info[0] = Glib::DateTime::create_now_utc();
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+ {
+ // edges_safe and edges_unsafe must be executed in separate.
+ // Otherwise, there will be colateral effects due to misassumption about
+ // the data being read.
+ PixelGraph::EdgePairContainer edges = graph.crossingEdges();
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ profiling_info[1] = Glib::DateTime::create_now_utc();
+ std::cerr << "Tracer::PixelGraph::crossingEdges() time: "
+ << profiling_info[1].difference(profiling_info[0]) << std::endl;
+ profiling_info[0] = Glib::DateTime::create_now_utc();
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+ _remove_crossing_edges_safe(edges);
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ profiling_info[1] = Glib::DateTime::create_now_utc();
+ std::cerr << "Tracer::Kopf2011::_remove_crossing_edges_safe"
+ "(Tracer::PixelGraph) time: "
+ << profiling_info[1].difference(profiling_info[0])
+ << std::endl;
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+#ifndef NDEBUG
+ graph.checkConsistency();
+#endif
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ profiling_info[0] = Glib::DateTime::create_now_utc();
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+ _remove_crossing_edges_unsafe(graph, edges, options);
+ }
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ profiling_info[1] = Glib::DateTime::create_now_utc();
+ std::cerr << "Tracer::Kopf2011::_remove_crossing_edges_unsafe"
+ "(Tracer::PixelGraph) time: "
+ << profiling_info[1].difference(profiling_info[0]) << std::endl;
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+
+#ifndef NDEBUG
+ graph.checkConsistency();
+#endif
+
+ assert(graph.crossingEdges().size() == 0);
+
+#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011
+ profiling_info[0] = Glib::DateTime::create_now_utc();
+
+ SimplifiedVoronoi<T, adjust_splines> ret(graph);
+
+ profiling_info[1] = Glib::DateTime::create_now_utc();
+ std::cerr << "Tracer::SimplifiedVoronoi<" << typeid(T).name() << ','
+ << (adjust_splines ? "true" : "false")
+ << ">(Tracer::PixelGraph) construction time: "
+ << profiling_info[1].difference(profiling_info[0]) << std::endl;
+
+ return ret;
+#else // LIBDEPIXELIZE_PROFILE_KOPF2011
+ return SimplifiedVoronoi<T, adjust_splines>(graph);
+#endif // LIBDEPIXELIZE_PROFILE_KOPF2011
+}
+
+// TODO: move this function (plus connectAllNeighbors) to PixelGraph constructor
+inline void
+Kopf2011::_disconnect_neighbors_with_dissimilar_colors(PixelGraph &graph)
+{
+ using colorspace::similar_colors;
+ for ( PixelGraph::iterator it = graph.begin(), end = graph.end() ; it != end
+ ; ++it ) {
+ if ( it->adj.top )
+ it->adj.top = similar_colors(it->rgba, (it - graph.width())->rgba);
+ if ( it->adj.topright ) {
+ it->adj.topright
+ = similar_colors(it->rgba, (it - graph.width() + 1)->rgba);
+ }
+ if ( it->adj.right )
+ it->adj.right = similar_colors(it->rgba, (it + 1)->rgba);
+ if ( it->adj.bottomright ) {
+ it->adj.bottomright
+ = similar_colors(it->rgba, (it + graph.width() + 1)->rgba);
+ }
+ if ( it->adj.bottom ) {
+ it->adj.bottom
+ = similar_colors(it->rgba, (it + graph.width())->rgba);
+ }
+ if ( it->adj.bottomleft ) {
+ it->adj.bottomleft
+ = similar_colors(it->rgba, (it + graph.width() - 1)->rgba);
+ }
+ if ( it->adj.left )
+ it->adj.left = similar_colors(it->rgba, (it - 1)->rgba);
+ if ( it->adj.topleft ) {
+ it->adj.topleft = similar_colors(it->rgba,
+ (it - graph.width() - 1)->rgba);
+ }
+ }
+}
+
+/**
+ * This method removes crossing edges if the 2x2 block is fully connected.
+ *
+ * In this case the two diagonal connections can be safely removed without
+ * affecting the final result.
+ */
+template<class T>
+void Kopf2011::_remove_crossing_edges_safe(T &container)
+{
+ for ( typename T::reverse_iterator it = container.rbegin(),
+ end = container.rend() ; it != end ; ) {
+ /* A | B
+ --+--
+ C | D */
+ PixelGraph::iterator a = it->first.first;
+ PixelGraph::iterator b = it->second.first;
+ PixelGraph::iterator c = it->second.second;
+ PixelGraph::iterator d = it->first.second;
+
+ if ( !a->adj.right || !a->adj.bottom || !b->adj.bottom
+ || !c->adj.right ) {
+ ++it;
+ continue;
+ }
+
+ // main diagonal
+ a->adj.bottomright = 0;
+ d->adj.topleft = 0;
+
+ // secondary diagonal
+ b->adj.bottomleft = 0;
+ c->adj.topright = 0;
+
+ // base iterator is always past one
+ typename T::iterator current = --(it.base());
+ ++it;
+ container.erase(current);
+ }
+}
+
+/**
+ * This method removes crossing edges using the heuristics.
+ */
+template<class T>
+void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, T &edges,
+ const Options &options)
+{
+ std::vector< std::pair<int, int> > weights(edges.size(),
+ std::make_pair(0, 0));
+
+ // Compute weights
+ for ( typename T::size_type i = 0 ; i != edges.size() ; ++i ) {
+ /* A | B
+ --+--
+ C | D */
+ PixelGraph::iterator a = edges[i].first.first;
+ PixelGraph::iterator b = edges[i].second.first;
+ PixelGraph::iterator c = edges[i].second.second;
+ PixelGraph::iterator d = edges[i].first.second;
+
+ // Curves heuristic
+ weights[i].first += Heuristics::curves(graph, a, d)
+ * options.curvesMultiplier;
+ weights[i].second += Heuristics::curves(graph, b, c)
+ * options.curvesMultiplier;
+
+ // Islands heuristic
+ weights[i].first += Heuristics::islands(a, d) * options.islandsWeight;
+ weights[i].second += Heuristics::islands(b, c) * options.islandsWeight;
+
+ // Sparse pixels heuristic
+ using Heuristics::SparsePixels;
+ SparsePixels sparse_pixels;
+
+ sparse_pixels.diagonals[SparsePixels::MAIN_DIAGONAL].first
+ = edges[i].first;
+ sparse_pixels.diagonals[SparsePixels::SECONDARY_DIAGONAL].first
+ = edges[i].second;
+
+ sparse_pixels(graph, options.sparsePixelsRadius);
+
+ weights[i].first
+ += sparse_pixels.diagonals[SparsePixels::MAIN_DIAGONAL].second
+ * options.sparsePixelsMultiplier;
+ weights[i].second
+ += sparse_pixels.diagonals[SparsePixels::SECONDARY_DIAGONAL].second
+ * options.sparsePixelsMultiplier;
+ }
+
+ // Remove edges with lower weight
+ for ( typename T::size_type i = 0 ; i != edges.size() ; ++i ) {
+ /* A | B
+ --+--
+ C | D */
+ PixelGraph::iterator a = edges[i].first.first;
+ PixelGraph::iterator b = edges[i].second.first;
+ PixelGraph::iterator c = edges[i].second.second;
+ PixelGraph::iterator d = edges[i].first.second;
+
+ if ( weights[i].first > weights[i].second ) {
+ b->adj.bottomleft = 0;
+ c->adj.topright = 0;
+ } else if ( weights[i].first < weights[i].second ) {
+ a->adj.bottomright = 0;
+ d->adj.topleft = 0;
+ } else {
+ a->adj.bottomright = 0;
+ b->adj.bottomleft = 0;
+ c->adj.topright = 0;
+ d->adj.topleft = 0;
+ }
+ }
+
+ edges.clear();
+}
+
+inline int Heuristics::curves(const PixelGraph &graph,
+ PixelGraph::const_iterator a,
+ PixelGraph::const_iterator b)
+{
+ int count = 1;
+ ToPtr<PixelGraph::Node> to_ptr;
+ ToIter<PixelGraph::Node> to_iter(graph.begin());
+
+ // b -> a
+ // and then a -> b
+ for ( int i = 0 ; i != 2 ; ++i ) {
+ PixelGraph::const_iterator it = i ? a : b;
+ PixelGraph::const_iterator prev = i ? b : a;
+ int local_count = 0;
+
+ // Used to avoid inifinite loops in circular-like edges
+ const PixelGraph::const_iterator initial = it;
+
+ while ( it->adjsize() == 2 ) {
+ ++local_count;
+
+ // Iterate to next
+ {
+ // There are only two values that won't be zero'ed
+ // and one of them has the same value of prev
+ guintptr aux = (it->adj.top
+ * guintptr(to_ptr(graph.nodeTop(it))))
+ + (it->adj.topright
+ * guintptr(to_ptr(graph.nodeTopRight(it))))
+ + (it->adj.right
+ * guintptr(to_ptr(graph.nodeRight(it))))
+ + (it->adj.bottomright
+ * guintptr(to_ptr(graph.nodeBottomRight(it))))
+ + (it->adj.bottom
+ * guintptr(to_ptr(graph.nodeBottom(it))))
+ + (it->adj.bottomleft
+ * guintptr(to_ptr(graph.nodeBottomLeft(it))))
+ + (it->adj.left
+ * guintptr(to_ptr(graph.nodeLeft(it))))
+ + (it->adj.topleft
+ * guintptr(to_ptr(graph.nodeTopLeft(it))))
+ - guintptr(to_ptr(prev));
+ prev = it;
+ it = to_iter(reinterpret_cast<PixelGraph::Node const*>(aux));
+ }
+
+ // Break infinite loops
+ if ( it == initial )
+ return local_count;
+ }
+ count += local_count;
+ }
+
+ return count;
+}
+
+inline void Heuristics::SparsePixels::operator ()(const PixelGraph &graph,
+ unsigned radius)
+{
+ if ( !graph.width() || !graph.height() )
+ return;
+
+ // Clear weights
+ for ( int i = 0 ; i != 2 ; ++i )
+ diagonals[i].second = 0;
+
+ if ( !radius )
+ return;
+
+ // Fix radius/bounds
+ {
+ unsigned x = graph.toX(diagonals[MAIN_DIAGONAL].first.first);
+ unsigned y = graph.toY(diagonals[MAIN_DIAGONAL].first.first);
+ unsigned displace = radius - 1;
+
+ {
+ unsigned minor = std::min(x, y);
+
+ if ( displace > minor ) {
+ displace = minor;
+ radius = displace + 1;
+ }
+ }
+
+ displace = radius;
+
+ if ( x + displace >= unsigned(graph.width()) ) {
+ displace = unsigned(graph.width()) - x - 1;
+ radius = displace;
+ }
+
+ if ( y + displace >= unsigned(graph.height()) ) {
+ displace = unsigned(graph.height()) - y - 1;
+ radius = displace;
+ }
+ }
+
+ if ( !radius )
+ return;
+
+ // Iterate over nodes and count them
+ {
+ PixelGraph::const_iterator it = diagonals[MAIN_DIAGONAL].first.first;
+ for ( unsigned i = radius - 1 ; i ; --i )
+ it = graph.nodeTopLeft(it);
+
+ bool invert = false;
+ for ( unsigned i = 0 ; i != 2 * radius ; ++i ) {
+ for ( unsigned j = 0 ; j != 2 * radius ; ++j ) {
+ for ( int k = 0 ; k != 2 ; ++k ) {
+ diagonals[k].second
+ += similar_colors(it, diagonals[k].first.first->rgba,
+ diagonals[k].first.second->rgba);
+ }
+ it = (invert ? graph.nodeLeft(it) : graph.nodeRight(it));
+ }
+ it = (invert ? graph.nodeRight(it) : graph.nodeLeft(it));
+
+
+ invert = !invert;
+ it = graph.nodeBottom(it);
+ }
+ }
+
+ int minor = std::min(diagonals[0].second, diagonals[1].second);
+ for ( int i = 0 ; i != 2 ; ++i )
+ diagonals[i].second -= minor;
+ std::swap(diagonals[0].second, diagonals[1].second);
+}
+
+inline bool
+Heuristics::SparsePixels::similar_colors(PixelGraph::const_iterator n,
+ const guint8 (&a)[4],
+ const guint8 (&b)[4])
+{
+ using colorspace::similar_colors;
+ return similar_colors(n->rgba, a) || similar_colors(n->rgba, b);
+}
+
+inline bool Heuristics::islands(PixelGraph::const_iterator a,
+ PixelGraph::const_iterator b)
+{
+ if ( a->adjsize() == 1 || b->adjsize() == 1 )
+ return true;
+
+ return false;
+}
+
+} // namespace Tracer
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
diff --git a/src/3rdparty/libdepixelize/kopftracer2011.h b/src/3rdparty/libdepixelize/kopftracer2011.h
new file mode 100644
index 0000000..c60d0a6
--- /dev/null
+++ b/src/3rdparty/libdepixelize/kopftracer2011.h
@@ -0,0 +1,150 @@
+/* This file is part of the libdepixelize project
+ Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+ GNU Lesser General Public License Usage
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by the
+ Free Software Foundation; either version 2.1 of the License, or (at your
+ option) any later version.
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library. If not, see <http://www.gnu.org/licenses/>.
+
+ GNU General Public License Usage
+ Alternatively, this library may be used under the terms of the GNU General
+ Public License as published by the Free Software Foundation, either version
+ 2 of the License, or (at your option) any later version.
+ You should have received a copy of the GNU General Public License along with
+ this library. If not, see <http://www.gnu.org/licenses/>.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_KOPFTRACER2011_H
+#define LIBDEPIXELIZE_TRACER_KOPFTRACER2011_H
+
+#include <string>
+
+#include <glibmm.h>
+// Contains exception definitions
+#include <glibmm/fileutils.h>
+#include <gdkmm/pixbuf.h>
+#include "splines.h"
+
+namespace Tracer {
+
+class PixelGraph;
+
+class Kopf2011
+{
+public:
+ struct Options
+ {
+ enum Defaults {
+ CURVES_MULTIPLIER = 1,
+ ISLANDS_WEIGHT = 5,
+ SPARSE_PIXELS_MULTIPLIER = 1,
+ SPARSE_PIXELS_RADIUS = 4
+ };
+
+ Options() :
+ curvesMultiplier(CURVES_MULTIPLIER),
+ islandsWeight(ISLANDS_WEIGHT),
+ sparsePixelsMultiplier(SPARSE_PIXELS_MULTIPLIER),
+ sparsePixelsRadius(SPARSE_PIXELS_RADIUS),
+ optimize(true),
+ nthreads(1)
+ {}
+
+ // Heuristics
+ double curvesMultiplier;
+ int islandsWeight;
+ double sparsePixelsMultiplier;
+ unsigned sparsePixelsRadius;
+
+ // Other options
+ bool optimize;
+ int nthreads;
+ };
+
+ /**
+ * # Exceptions
+ *
+ * \p options.optimize and options.nthreads will be ignored
+ *
+ * Glib::FileError
+ * Gdk::PixbufError
+ */
+ static Splines to_voronoi(const std::string &filename,
+ const Options &options = Options());
+
+ /*
+ * \p options.optimize and options.nthreads will be ignored
+ */
+ static Splines to_voronoi(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
+ const Options &options = Options());
+
+ /**
+ * # Exceptions
+ *
+ * \p options.optimize and options.nthreads will be ignored
+ *
+ * Glib::FileError
+ * Gdk::PixbufError
+ */
+ static Splines to_grouped_voronoi(const std::string &filename,
+ const Options &options = Options());
+
+ /*
+ * \p options.optimize and options.nthreads will be ignored
+ */
+ static Splines to_grouped_voronoi(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
+ const Options &options = Options());
+
+ /**
+ * # Exceptions
+ *
+ * Glib::FileError
+ * Gdk::PixbufError
+ */
+ static Splines to_splines(const std::string &filename,
+ const Options &options = Options());
+
+ static Splines to_splines(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
+ const Options &options = Options());
+
+private:
+ typedef Geom::Coord Precision;
+
+ template<class T, bool adjust_splines>
+ static SimplifiedVoronoi<T, adjust_splines>
+ _voronoi(const Glib::RefPtr<Gdk::Pixbuf const> &buf,
+ const Options &options);
+
+ static void _disconnect_neighbors_with_dissimilar_colors(PixelGraph &graph);
+
+ // here, T/template is only used as an easy way to not expose internal
+ // symbols
+ template<class T>
+ static void _remove_crossing_edges_safe(T &container);
+ template<class T>
+ static void _remove_crossing_edges_unsafe(PixelGraph &graph, T &edges,
+ const Options &options);
+};
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_KOPFTRACER2011_H
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/3rdparty/libdepixelize/priv/branchless.h b/src/3rdparty/libdepixelize/priv/branchless.h
new file mode 100644
index 0000000..487a968
--- /dev/null
+++ b/src/3rdparty/libdepixelize/priv/branchless.h
@@ -0,0 +1,58 @@
+/* This file is part of the libdepixelize project
+ Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+ GNU Lesser General Public License Usage
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by the
+ Free Software Foundation; either version 2.1 of the License, or (at your
+ option) any later version.
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library. If not, see <http://www.gnu.org/licenses/>.
+
+ GNU General Public License Usage
+ Alternatively, this library may be used under the terms of the GNU General
+ Public License as published by the Free Software Foundation, either version
+ 2 of the License, or (at your option) any later version.
+ You should have received a copy of the GNU General Public License along with
+ this library. If not, see <http://www.gnu.org/licenses/>.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_BRANCHLESS_H
+#define LIBDEPIXELIZE_TRACER_BRANCHLESS_H
+
+namespace Tracer {
+
+/**
+ * Branch misprediction proof operations
+ */
+namespace branchless {
+
+/*
+ * All modern processors optimize the branch to a conditional move
+ */
+template<class T>
+T first_if(T first, T second, bool cond)
+{
+ return cond ? first : second;
+}
+
+} // namespace branchless
+} // namespace Tracer {
+
+#endif // LIBDEPIXELIZE_TRACER_BRANCHLESS_H
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/3rdparty/libdepixelize/priv/colorspace.h b/src/3rdparty/libdepixelize/priv/colorspace.h
new file mode 100644
index 0000000..4982630
--- /dev/null
+++ b/src/3rdparty/libdepixelize/priv/colorspace.h
@@ -0,0 +1,111 @@
+/* This file is part of the libdepixelize project
+ Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+ GNU Lesser General Public License Usage
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by the
+ Free Software Foundation; either version 2.1 of the License, or (at your
+ option) any later version.
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library. If not, see <http://www.gnu.org/licenses/>.
+
+ GNU General Public License Usage
+ Alternatively, this library may be used under the terms of the GNU General
+ Public License as published by the Free Software Foundation, either version
+ 2 of the License, or (at your option) any later version.
+ You should have received a copy of the GNU General Public License along with
+ this library. If not, see <http://www.gnu.org/licenses/>.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_YUV_H
+#define LIBDEPIXELIZE_TRACER_YUV_H
+
+#include <glib.h>
+
+namespace Tracer {
+namespace colorspace {
+
+/**
+ * The same algorithm used in hqx filter
+ */
+inline void rgb2yuv(guint8 r, guint8 g, guint8 b,
+ guint8 &y, guint8 &u, guint8 &v)
+{
+ y = 0.299 * r + 0.587 * g + 0.114 * b;
+ u = guint16(-0.169 * r - 0.331 * g + 0.5 * b) + 128;
+ v = guint16(0.5 * r - 0.419 * g - 0.081 * b) + 128;
+}
+
+inline void rgb2yuv(const guint8 rgb[], guint8 yuv[])
+{
+ rgb2yuv(rgb[0], rgb[1], rgb[2], yuv[0], yuv[1], yuv[2]);
+}
+
+inline bool same_color(const guint8 (&a)[4], const guint8 (&b)[4])
+{
+ return (a[0] == b[0]
+ && a[1] == b[1]
+ && a[2] == b[2]
+ && a[3] == b[3]);
+}
+
+inline bool dissimilar_colors(const guint8 a[], const guint8 b[])
+{
+ // C uses row-major order, so
+ // A[2][3] = { {1, 2, 3}, {4, 5, 6} } = {1, 2, 3, 4, 5, 6}
+ guint8 yuv[2][3];
+ rgb2yuv(a, yuv[0]);
+ rgb2yuv(b, yuv[1]);
+
+ // Magic numbers taken from hqx algorithm
+ // Only used to describe the level of tolerance
+ return abs(yuv[0][0] - yuv[1][0]) > 0x30
+ || abs(yuv[0][1] - yuv[1][1]) > 7
+ || abs(yuv[0][2] - yuv[1][2]) > 6;
+}
+
+inline bool similar_colors(const guint8 a[], const guint8 b[])
+{
+ return !dissimilar_colors(a, b);
+}
+
+inline bool shading_edge(const guint8 a[], const guint8 b[])
+{
+ // C uses row-major order, so
+ // A[2][3] = { {1, 2, 3}, {4, 5, 6} } = {1, 2, 3, 4, 5, 6}
+ guint8 yuv[2][3];
+ rgb2yuv(a, yuv[0]);
+ rgb2yuv(b, yuv[1]);
+
+ // Magic numbers taken from Kopf-Lischinski algorithm
+ // Only used to describe the level of tolerance
+ return abs(yuv[0][0] - yuv[1][0]) <= 100
+ && abs(yuv[0][1] - yuv[1][1]) <= 100
+ && abs(yuv[0][2] - yuv[1][2]) <= 100;
+}
+
+inline bool contour_edge(const guint8 a[], const guint8 b[])
+{
+ return !shading_edge(a, b);
+}
+
+} // namespace colorspace
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_YUV_H
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/3rdparty/libdepixelize/priv/curvature.h b/src/3rdparty/libdepixelize/priv/curvature.h
new file mode 100644
index 0000000..3a1af41
--- /dev/null
+++ b/src/3rdparty/libdepixelize/priv/curvature.h
@@ -0,0 +1,115 @@
+/* This file is part of the libdepixelize project
+ Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+ GNU Lesser General Public License Usage
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by the
+ Free Software Foundation; either version 2.1 of the License, or (at your
+ option) any later version.
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library. If not, see <http://www.gnu.org/licenses/>.
+
+ GNU General Public License Usage
+ Alternatively, this library may be used under the terms of the GNU General
+ Public License as published by the Free Software Foundation, either version
+ 2 of the License, or (at your option) any later version.
+ You should have received a copy of the GNU General Public License along with
+ this library. If not, see <http://www.gnu.org/licenses/>.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_CURVATURE_H
+#define LIBDEPIXELIZE_TRACER_CURVATURE_H
+
+#include "point.h"
+#include <cmath>
+
+namespace Tracer {
+
+/**
+ * Curvature function for a quadratic Bézier curve where the points are know.
+ * Its main use is to numerically integrate the curvature function and then
+ * smooth the B-Splines generated by the Kopf-Lischinski algorithm.
+ */
+template<class T>
+struct Curvature
+{
+ Curvature(Point<T> p0, Point<T> c1, Point<T> p2) :
+ p0(p0), c1(c1), p2(p2)
+ {}
+
+ T operator()(T t) const;
+
+ /**
+ * The derivative of x
+ */
+ T xPrime(T t) const;
+
+ /**
+ * The derivative of y
+ */
+ T yPrime(T t) const;
+
+ /**
+ * The second derivative of x
+ */
+ T xPrimePrime() const;
+
+ /**
+ * The second derivative of y
+ */
+ T yPrimePrime() const;
+
+ Point<T> p0, c1, p2;
+};
+
+template<class T>
+T Curvature<T>::operator()(T t) const
+{
+ T num = xPrime(t) * yPrimePrime() - yPrime(t) * xPrimePrime();
+ T den = std::pow(xPrime(t) * xPrime(t) + yPrime(t) * yPrime(t), T(3) / 2);
+ return num / den;
+}
+
+template<class T>
+T Curvature<T>::xPrime(T t) const
+{
+ return (1-t)*2*(c1.x-p0.x) + t*2*(p2.x-c1.x);
+}
+
+template<class T>
+T Curvature<T>::yPrime(T t) const
+{
+ return (1-t)*2*(c1.y-p0.y) + t*2*(p2.y-c1.y);
+}
+
+template<class T>
+T Curvature<T>::xPrimePrime() const
+{
+ return 2 * (p2.x - 2*c1.x + p0.x);
+}
+
+template<class T>
+T Curvature<T>::yPrimePrime() const
+{
+ return 2 * (p2.y - 2*c1.y + p0.y);
+}
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_CURVATURE_H
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/3rdparty/libdepixelize/priv/homogeneoussplines.h b/src/3rdparty/libdepixelize/priv/homogeneoussplines.h
new file mode 100644
index 0000000..6c4894d
--- /dev/null
+++ b/src/3rdparty/libdepixelize/priv/homogeneoussplines.h
@@ -0,0 +1,472 @@
+/* This file is part of the libdepixelize project
+ Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+ GNU Lesser General Public License Usage
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by the
+ Free Software Foundation; either version 2.1 of the License, or (at your
+ option) any later version.
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library. If not, see <http://www.gnu.org/licenses/>.
+
+ GNU General Public License Usage
+ Alternatively, this library may be used under the terms of the GNU General
+ Public License as published by the Free Software Foundation, either version
+ 2 of the License, or (at your option) any later version.
+ You should have received a copy of the GNU General Public License along with
+ this library. If not, see <http://www.gnu.org/licenses/>.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_HOMOGENEOUSSPLINES_H
+#define LIBDEPIXELIZE_TRACER_HOMOGENEOUSSPLINES_H
+
+#include "simplifiedvoronoi.h"
+#include "point.h"
+#include <algorithm>
+#include <utility>
+
+namespace Tracer {
+
+template<typename T>
+class HomogeneousSplines
+{
+public:
+ struct Polygon
+ {
+ typedef std::vector< Point<T> > Points;
+ typedef typename Points::iterator points_iter;
+ typedef typename Points::const_iterator const_points_iter;
+ typedef typename std::vector<Points>::iterator holes_iter;
+ typedef typename std::vector<Points>::const_iterator const_holes_iter;
+
+ Polygon() {}
+ Polygon(const guint8 (&rgba)[4])
+ {
+ for ( int i = 0 ; i != 4 ; ++i )
+ this->rgba[i] = rgba[i];
+ }
+
+ std::vector< Point<T> > vertices;
+
+ /**
+ * It may be benefited from C++11 move references.
+ */
+ std::vector< std::vector< Point<T> > > holes;
+
+ guint8 rgba[4];
+ };
+
+ typedef typename std::vector<Polygon>::iterator iterator;
+ typedef typename std::vector<Polygon>::const_iterator const_iterator;
+ typedef typename std::vector<Polygon>::size_type size_type;
+
+ template<bool adjust_splines>
+ HomogeneousSplines(const SimplifiedVoronoi<T, adjust_splines> &voronoi);
+
+ // Iterators
+ iterator begin()
+ {
+ return _polygons.begin();
+ }
+
+ const_iterator begin() const
+ {
+ return _polygons.begin();
+ }
+
+ iterator end()
+ {
+ return _polygons.end();
+ }
+
+ const_iterator end() const
+ {
+ return _polygons.end();
+ }
+
+ size_type size() const
+ {
+ return _polygons.size();
+ }
+
+ int width() const
+ {
+ return _width;
+ }
+
+ int height() const
+ {
+ return _height;
+ }
+
+private:
+ typedef std::vector< Point<T> > Points;
+ typedef typename Points::iterator points_iter;
+ typedef typename Points::const_iterator points_citer;
+ typedef typename Points::reverse_iterator points_riter;
+ typedef typename Points::const_reverse_iterator points_criter;
+
+ typedef std::pair<points_iter, points_iter> points_range;
+ typedef std::pair<points_citer, points_citer> points_crange;
+
+ struct CommonEdge
+ {
+ bool ok; //< share an edge
+ Points *dst;
+ const Points *src;
+
+ // the interval is closed on both ends
+ // different from [begin, end) STL style
+ points_iter dst_begin, dst_end;
+ points_citer src_begin, src_end;
+ };
+
+ struct SelfCommonEdge
+ {
+ bool ok; //< share an edge
+
+ // Greater range. The one that should be erased from the vector.
+ points_riter grt_begin, grt_end;
+
+ // Smaller range. The one that should be used to create a new vector.
+ points_riter sml_begin, sml_end;
+ };
+
+ /**
+ * Return ok == true if they share an edge (more than one point).
+ */
+ CommonEdge _common_edge(Points &dst, const Points &src);
+
+ /**
+ * Return ok == true if they share an edge (more than one point).
+ *
+ * - [dst_begin, dst_end) will contain the hole polygon
+ * - [src_begin, src_end) will contain the range to be erased
+ *
+ * It's required to do the search in backward order.
+ */
+ SelfCommonEdge _common_edge(Points &points, points_riter it);
+
+ /*!
+ * Add polygon represented by \p common_edge.src to \p common_edge.dst.
+ */
+ void _polygon_union(CommonEdge common_edge);
+
+ /**
+ * Weird recursive function created to solve the complex problem to fill
+ * polygons holes without the need to store temporaries on the heap nor
+ * changing requirements to some data type that don't invalidate iterators
+ * that point before the current element (maybe I'll write some poetry about
+ * the problem someday).
+ */
+ void _fill_holes(std::vector<Points> &holes, points_iter region_begin,
+ points_iter region_end);
+
+ std::vector<Polygon> _polygons;
+ int _width;
+ int _height;
+};
+
+template<class T>
+template<bool adjust_splines>
+HomogeneousSplines<T>::HomogeneousSplines(const SimplifiedVoronoi<T,
+ adjust_splines> &voronoi) :
+ _width(voronoi.width()),
+ _height(voronoi.height())
+{
+ //if (!voronoi.size())
+ // return;
+ using colorspace::same_color;
+
+ typedef typename SimplifiedVoronoi<T, adjust_splines>::const_iterator
+ voronoi_citer;
+
+ // Identify visible edges (group polygons with the same color)
+ for ( voronoi_citer cell_it = voronoi.begin(), cell_end = voronoi.end()
+ ; cell_it != cell_end ; ++cell_it ) {
+ bool found = false;
+ for ( iterator polygon_it = _polygons.begin(),
+ polygon_end = _polygons.end()
+ ; polygon_it != polygon_end ; ++polygon_it ) {
+ if ( same_color(polygon_it->rgba, cell_it->rgba) ) {
+ CommonEdge common_edge = _common_edge(polygon_it->vertices,
+ cell_it->vertices);
+ if ( common_edge.ok ) {
+ _polygon_union(common_edge);
+ found = true;
+
+ for ( iterator polygon2_it = polygon_it + 1
+ ; polygon2_it != polygon_end ; ++polygon2_it ) {
+ if ( same_color(polygon_it->rgba, polygon2_it->rgba) ) {
+ CommonEdge common_edge2
+ = _common_edge(polygon_it->vertices,
+ polygon2_it->vertices);
+ if ( common_edge2.ok ) {
+ _polygon_union(common_edge2);
+ _polygons.erase(polygon2_it);
+ break;
+ }
+ }
+ }
+
+ break;
+ }
+ }
+ }
+ if ( !found ) {
+ Polygon polygon(cell_it->rgba);
+ polygon.vertices = cell_it->vertices;
+ _polygons.insert(_polygons.end(), polygon);
+ }
+ }
+
+ // Find polygons with holes and fix them
+ // This iteration runs such complex time-consuming algorithm, but each
+ // polygon has an independent result. They wouldn't even need to share/sync
+ // results and the only waste would be a join at the end of the for.
+ for ( typename std::vector<Polygon>::iterator it = _polygons.begin(),
+ end = _polygons.end() ; it != end ; ++it ) {
+ SelfCommonEdge ce = _common_edge(it->vertices, it->vertices.rbegin());
+ while ( ce.ok ) {
+ _fill_holes(it->holes, ce.sml_end.base(), ce.sml_begin.base());
+ it->vertices.erase(ce.grt_end.base() + 1, ce.grt_begin.base());
+ ce = _common_edge(it->vertices, ce.grt_end);
+ }
+ }
+}
+
+// it can infinite loop if points of both entities are equal,
+// but this shouldn't happen if user has only access to Kopf2011 interface
+template<class T>
+typename HomogeneousSplines<T>::CommonEdge
+HomogeneousSplines<T>::_common_edge(Points &dst, const Points &src)
+{
+ // It's an edge, then the points are closer together. After we find the
+ // first point, there is no need for check against all points of the src
+ // a second time
+
+ const points_iter dst_begin = dst.begin();
+ const points_iter dst_end = dst.end();
+
+ const points_citer src_begin = src.begin();
+ const points_citer src_end = src.end();
+
+ for ( points_iter it = dst_begin ; it != dst_end ; ++it ) {
+ points_citer src_it = std::find(src_begin, src_end, *it);
+
+ if ( src_it == src_end )
+ continue;
+
+ points_iter dst_common_edge_begin = it;
+ points_citer src_common_edge_end = src_it;
+
+ // iterate until find the beginning of the common edge range
+ while ( *dst_common_edge_begin == *src_common_edge_end ) {
+ if ( dst_common_edge_begin == dst_begin )
+ dst_common_edge_begin = dst_end - 1;
+ else
+ --dst_common_edge_begin;
+
+ ++src_common_edge_end;
+ if ( src_common_edge_end == src_end )
+ src_common_edge_end = src_begin;
+ }
+
+ // fix {dst_begin, src_end} range
+ ++dst_common_edge_begin;
+ if ( dst_common_edge_begin == dst_end )
+ dst_common_edge_begin = dst_begin;
+
+ if ( src_common_edge_end == src_begin )
+ src_common_edge_end = src_end - 1;
+ else
+ --src_common_edge_end;
+
+ points_iter dst_common_edge_end = it;
+ points_citer src_common_edge_begin = src_it;
+
+ // find the end of the common edge range
+ while ( *dst_common_edge_end == *src_common_edge_begin ) {
+ ++dst_common_edge_end;
+ if ( dst_common_edge_end == dst_end )
+ dst_common_edge_end = dst_begin;
+
+ if ( src_common_edge_begin == src_begin )
+ src_common_edge_begin = src_end - 1;
+ else
+ --src_common_edge_begin;
+ }
+
+ // fix {dst_end, src_begin} range
+ if ( dst_common_edge_end == dst_begin )
+ dst_common_edge_end = dst_end - 1;
+ else
+ --dst_common_edge_end;
+
+ ++src_common_edge_begin;
+ if ( src_common_edge_begin == src_end )
+ src_common_edge_begin = src_begin;
+
+ CommonEdge ret;
+
+ // if only one point in common
+ if ( dst_common_edge_begin == dst_common_edge_end )
+ continue;
+
+ ret.ok = true;
+
+ ret.dst = &dst;
+ ret.dst_begin = dst_common_edge_begin;
+ ret.dst_end = dst_common_edge_end;
+
+ ret.src = &src;
+ ret.src_begin = src_common_edge_begin;
+ ret.src_end = src_common_edge_end;
+
+ return ret;
+ }
+
+ CommonEdge ret;
+ ret.ok = false;
+ return ret;
+}
+
+template<class T>
+typename HomogeneousSplines<T>::SelfCommonEdge
+HomogeneousSplines<T>::_common_edge(Points &points, points_riter it)
+{
+ SelfCommonEdge ret;
+
+ ret.grt_end = points.rend();
+
+ for ( ; it != ret.grt_end ; ++it ) {
+ ret.sml_end = std::find(it + 1, ret.grt_end, *it);
+
+ if ( ret.sml_end == ret.grt_end )
+ continue;
+
+ ret.grt_begin = it;
+ ret.grt_end = ret.sml_end + 1;
+
+ ret.sml_begin = it;
+
+ while ( *ret.sml_begin == *ret.sml_end ) {
+ ++ret.sml_begin;
+ --ret.sml_end;
+ }
+
+ --ret.sml_begin;
+ ++ret.sml_end;
+ ++ret.sml_end;
+
+ ret.ok = true;
+ return ret;
+ }
+
+ ret.ok = false;
+ return ret;
+}
+
+template<class T>
+void HomogeneousSplines<T>::_polygon_union(CommonEdge common_edge)
+{
+ Points &dst = *common_edge.dst;
+ const Points &src = *common_edge.src;
+
+ // the rotated cell must be inserted before (dst.begin() + index)
+ typename Points::difference_type index;
+
+ // first, we remove the common edge in dst
+ if ( common_edge.dst_begin < common_edge.dst_end ) {
+ // common edge is in the middle of dst
+
+ index = dst.erase(common_edge.dst_begin,
+ common_edge.dst_end + 1) - dst.begin();
+ } else {
+ // common edge cross the end of dst
+
+ dst.erase(common_edge.dst_begin, dst.end());
+ dst.erase(dst.begin(), common_edge.dst_end);
+ index = dst.end() - dst.begin();
+ }
+
+ // second, we copy src points to polygon
+ if ( common_edge.src_begin < common_edge.src_end ) {
+ // common edge is in the middle of src
+
+ const typename Points::difference_type nfirstinserted
+ = src.end() - common_edge.src_end;
+ const typename Points::difference_type nsecondinserted
+ = 1 + (common_edge.src_begin - src.begin());
+
+ dst.reserve(dst.size() + nfirstinserted + nsecondinserted);
+
+ dst.insert(dst.begin() + index, common_edge.src_end, src.end());
+
+ dst.insert(dst.begin() + index + nfirstinserted,
+ src.begin(), common_edge.src_begin + 1);
+ } else {
+ // common edge cross the end of src
+
+ dst.reserve(dst.size() + 1
+ + (common_edge.src_begin - common_edge.src_end));
+
+ dst.insert(dst.begin() + index,
+ common_edge.src_end, common_edge.src_begin + 1);
+ }
+}
+
+// The following piece of code is so evil that you could end up invoking an
+// ancient beast if you proceed to read it, but I'll be able to explain it in
+// the form of some video (text is not so representative as an image).
+template<class T>
+void HomogeneousSplines<T>::_fill_holes(std::vector<Points> &holes,
+ points_iter region_begin,
+ points_iter region_end)
+{
+ // the exact location might not always be back and iterators will be
+ // invalidated after some insertions, then the index is required
+ const typename std::vector<Points>::size_type hole_index = holes.size();
+ holes.resize(hole_index + 1);
+
+ for ( points_iter it = region_begin + 1 ; it != region_end ; ++it ) {
+ points_iter res = std::find(it + 1, region_end, *it);
+ if ( res == region_end )
+ continue;
+
+ holes[hole_index].insert(holes[hole_index].end(), region_begin,
+ it);
+ region_begin = res;
+
+ do {
+ ++it;
+ --res;
+ } while ( *it == *res );
+ _fill_holes(holes, it - 1, res + 2);
+
+ it = region_begin;
+ }
+
+ holes[hole_index].insert(holes[hole_index].end(), region_begin,
+ region_end - 1);
+}
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_HOMOGENEOUSSPLINES_H
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/3rdparty/libdepixelize/priv/integral.h b/src/3rdparty/libdepixelize/priv/integral.h
new file mode 100644
index 0000000..fc1a49f
--- /dev/null
+++ b/src/3rdparty/libdepixelize/priv/integral.h
@@ -0,0 +1,61 @@
+/* This file is part of the libdepixelize project
+ Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+ GNU Lesser General Public License Usage
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by the
+ Free Software Foundation; either version 2.1 of the License, or (at your
+ option) any later version.
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library. If not, see <http://www.gnu.org/licenses/>.
+
+ GNU General Public License Usage
+ Alternatively, this library may be used under the terms of the GNU General
+ Public License as published by the Free Software Foundation, either version
+ 2 of the License, or (at your option) any later version.
+ You should have received a copy of the GNU General Public License along with
+ this library. If not, see <http://www.gnu.org/licenses/>.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_INTEGRAL_H
+#define LIBDEPIXELIZE_TRACER_INTEGRAL_H
+
+#include <2geom/coord.h>
+
+namespace Tracer {
+
+/**
+ * Compute the integral numerically using Gaussian Quadrature rule with
+ * \p samples number of samples.
+ */
+template<class T, class F>
+Geom::Coord integral(F f, T begin, T end, unsigned samples)
+{
+ T ret = 0;
+ const T width = (end - begin) / samples;
+
+ for ( unsigned i = 0 ; i != samples ; ++i )
+ ret += width * f(begin + width * (i + .5));
+
+ return ret;
+}
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_INTEGRAL_H
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/3rdparty/libdepixelize/priv/iterator.h b/src/3rdparty/libdepixelize/priv/iterator.h
new file mode 100644
index 0000000..7caa9bf
--- /dev/null
+++ b/src/3rdparty/libdepixelize/priv/iterator.h
@@ -0,0 +1,123 @@
+/* This file is part of the libdepixelize project
+ Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+ GNU Lesser General Public License Usage
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by the
+ Free Software Foundation; either version 2.1 of the License, or (at your
+ option) any later version.
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library. If not, see <http://www.gnu.org/licenses/>.
+
+ GNU General Public License Usage
+ Alternatively, this library may be used under the terms of the GNU General
+ Public License as published by the Free Software Foundation, either version
+ 2 of the License, or (at your option) any later version.
+ You should have received a copy of the GNU General Public License along with
+ this library. If not, see <http://www.gnu.org/licenses/>.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_ITERATOR_H
+#define LIBDEPIXELIZE_TRACER_ITERATOR_H
+
+#include <vector>
+#include <iterator>
+
+namespace Tracer {
+
+template<typename T>
+const T *to_ptr(typename std::vector<T>::const_iterator it)
+{
+ return &*it;
+}
+
+template<typename T>
+T *to_ptr(typename std::vector<T>::iterator it)
+{
+ return &*it;
+}
+
+template<typename T>
+typename std::vector<T>::const_iterator to_iterator(T const *ptr,
+ typename std::vector<T>
+ ::const_iterator begin)
+{
+ typedef typename std::vector<T>::const_iterator It;
+ typedef typename std::iterator_traits<It>::difference_type difference_type;
+ difference_type idx = ptr - to_ptr<T>(begin);
+ return begin + idx;
+}
+
+template<typename T>
+typename std::vector<T>::iterator to_iterator(T *ptr,
+ typename std::vector<T>::iterator
+ begin)
+{
+ typedef typename std::vector<T>::iterator It;
+ typedef typename std::iterator_traits<It>::difference_type difference_type;
+ difference_type idx = ptr - to_ptr<T>(begin);
+ return begin + idx;
+}
+
+template<typename T>
+class ToIter
+{
+public:
+ typedef typename std::vector<T>::const_iterator const_iterator;
+ typedef typename std::vector<T>::iterator iterator;
+
+ ToIter(const_iterator begin) :
+ begin(begin)
+ {}
+
+ const_iterator operator()(T const *ptr) const
+ {
+ return to_iterator<T>(ptr, begin);
+ }
+
+ iterator operator()(T *ptr) const
+ {
+ return to_iterator<T>(ptr, begin);
+ }
+
+private:
+ typename std::vector<T>::const_iterator begin;
+};
+
+template<typename T>
+class ToPtr
+{
+public:
+ typedef typename std::vector<T>::const_iterator const_iterator;
+ typedef typename std::vector<T>::iterator iterator;
+
+ const T *operator()(const_iterator it) const
+ {
+ return to_ptr<T>(it);
+ }
+
+ T *operator()(iterator it) const
+ {
+ return to_ptr<T>(it);
+ }
+};
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_ITERATOR_H
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/3rdparty/libdepixelize/priv/optimization-kopf2011.h b/src/3rdparty/libdepixelize/priv/optimization-kopf2011.h
new file mode 100644
index 0000000..0c9011c
--- /dev/null
+++ b/src/3rdparty/libdepixelize/priv/optimization-kopf2011.h
@@ -0,0 +1,263 @@
+/* This file is part of the libdepixelize project
+ Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+ GNU Lesser General Public License Usage
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by the
+ Free Software Foundation; either version 2.1 of the License, or (at your
+ option) any later version.
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library. If not, see <http://www.gnu.org/licenses/>.
+
+ GNU General Public License Usage
+ Alternatively, this library may be used under the terms of the GNU General
+ Public License as published by the Free Software Foundation, either version
+ 2 of the License, or (at your option) any later version.
+ You should have received a copy of the GNU General Public License along with
+ this library. If not, see <http://www.gnu.org/licenses/>.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_OPTIMIZATION_KOPF2011_H
+#define LIBDEPIXELIZE_TRACER_OPTIMIZATION_KOPF2011_H
+
+#include "curvature.h"
+#include "integral.h"
+#include <cmath>
+#include <limits>
+
+namespace Tracer {
+
+/**
+ * m is angular coeficient
+ */
+template<class T>
+bool is_valid_border_m(T a)
+{
+ if ( a < 0 )
+ a *= -1;
+
+ // TODO: alternative behaviour if has no infinity
+ return a == std::numeric_limits<T>::infinity()
+ || a == 3 || a == 1;
+}
+
+/**
+ * Return true if the four points are considered a border.
+ */
+template<class T>
+bool is_border(const Point<T> (&points)[4])
+{
+ T dy[2];
+ T dx[2];
+ T m[2];
+ if ( points[1].y == points[2].y ) {
+ dy[0] = points[1].y - points[0].y;
+ dy[1] = points[3].y - points[2].y;
+
+ dx[0] = points[1].x - points[0].x;
+ dx[1] = points[3].x - points[2].x;
+
+ m[0] = dy[0] / dx[0];
+ m[1] = dy[1] / dx[1];
+ } else if ( points[1].x == points[2].x ) {
+ // It's easier to have a unified logic, then we'll fake dx and dy
+ dy[0] = points[1].x - points[0].x;
+ dy[1] = points[3].x - points[2].x;
+
+ dx[0] = points[1].y - points[0].y;
+ dx[1] = points[3].y - points[2].y;
+
+ m[0] = dy[0] / dx[0];
+ m[1] = dy[1] / dx[1];
+ } else {
+ return false;
+ }
+
+ return m[0] == -m[1] && is_valid_border_m(m[0]);
+}
+
+template<class T>
+typename std::vector< Point<T> >::iterator
+skip1visible(typename std::vector< Point<T> >::iterator it,
+ typename std::vector< Point<T> >::iterator end)
+{
+ for ( ++it ; it != end ; ++it ) {
+ if ( it->visible )
+ return it;
+ }
+ return end;
+}
+
+/**
+ * Return how many elements should be skipped.
+ */
+template<class T>
+typename std::vector< Point<T> >::difference_type
+border_detection(typename std::vector< Point<T> >::iterator it,
+ typename std::vector< Point<T> >::iterator end)
+{
+ typename std::vector< Point<T> >::iterator begin = it;
+
+ if ( end - it < 4 )
+ return 0;
+
+ Point<T> last[4];
+ typename std::vector< Point<T> >::iterator prev = it;
+
+ for ( int i = 0 ; i != 4 ; ++i ) {
+ if ( it == end )
+ return 0;
+ last[i] = *it;
+ prev = it;
+ it = skip1visible<T>(it, end);
+ }
+
+ if ( !is_border(last) )
+ return 0;
+
+ if ( it == end )
+ return prev - begin;
+
+ bool got_another = false;
+ for ( it = skip1visible<T>(it, end) ; it != end
+ ; it = skip1visible<T>(it, end) ) {
+ if ( !got_another ) {
+ last[0] = last[2];
+ last[1] = last[3];
+ last[2] = *it;
+
+ got_another = true;
+ continue;
+ }
+ last[3] = *it;
+
+ if ( !is_border(last) )
+ return prev - begin;
+ prev = it;
+ }
+
+ return prev - begin;
+}
+
+template<class T>
+T smoothness_energy(Point<T> c0, Point<T> c1, Point<T> c2)
+{
+ Point<T> p0 = midpoint(c0, c1);
+ Point<T> p2 = midpoint(c1, c2);
+ Curvature<T> cur(p0, c1, p2);
+
+ return std::abs(integral<T>(cur, 0, 1, 16));
+}
+
+template<class T>
+T positional_energy(Point<T> guess, Point<T> initial)
+{
+ using std::pow;
+
+ return pow(pow(guess.x - initial.x, 2)
+ + pow(guess.y - initial.y, 2), 2);
+}
+
+/**
+ * Kopf-Lischinski simple relaxation procedure: a random new offset position
+ * within a small radius around its current location.
+ *
+ * The small radius is not revealed. I chose the empirically determined value of
+ * 0.125. New tests can give a better value for "small". I believe this value
+ * showed up because the optimization sharply penalize larger deviations.
+ */
+template<class T>
+Point<T> optimization_guess(Point<T> p)
+{
+ // See the value explanation in the function documentation.
+ T radius = 0.125;
+
+ T d[] = {
+ (T(std::rand()) / RAND_MAX) * radius * 2 - radius,
+ (T(std::rand()) / RAND_MAX) * radius * 2 - radius
+ };
+
+ return p + Point<T>(d[0], d[1]);
+}
+
+template<class T>
+std::vector< Point<T> > optimize(const std::vector< Point<T> > &path)
+{
+ typedef std::vector< Point<T> > Path;
+
+ Path ret = path;
+
+ /* The number of vertices not constrained by optimization */
+ unsigned n = 0;
+
+ /* Values chosen by test
+ * TODO: make values configurable via function parameters. */
+ const unsigned iterations = 4;
+ const unsigned nguess_per_iteration = 4;
+
+ for ( unsigned i = 0 ; i != iterations ; ++i ) {
+ n = 0;
+
+ /* This iteration bounds is not something to worry about, because the
+ * smallest path has size 4. */
+ for ( typename Path::size_type j = 0 ; j != ret.size() ; ++j ) {
+ Point<T> prev = ( j == 0 ) ? ret.back() : ret[j-1];
+ Point<T> next = ( j + 1 == ret.size() ) ? ret.front() : ret[j+1] ;
+
+ if ( !ret[j].visible || !ret[j].smooth )
+ continue;
+
+ {
+ typename Path::iterator it = ret.begin() + j;
+ typename Path::difference_type skip
+ = border_detection<T>(it, ret.end());
+ j += skip;
+ if ( j == ret.size() )
+ break;
+ }
+
+ ++n;
+
+ for ( unsigned k = 0 ; k != nguess_per_iteration ; ++k ) {
+ Point<T> guess = optimization_guess(ret[j]);
+
+ T s = smoothness_energy(prev, guess, next);
+ T p = positional_energy(guess, path[j]);
+
+ T e = s + p;
+
+ T prev_e = smoothness_energy(prev, ret[j], next)
+ + positional_energy(ret[j], path[j]);
+
+ if ( prev_e > e ) {
+ // We don't want to screw other metadata, then we manually
+ // assign the new coords
+ ret[j].x = guess.x;
+ ret[j].y = guess.y;
+ }
+ }
+ }
+ }
+
+ return ret;
+}
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_OPTIMIZATION_KOPF2011_H
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/3rdparty/libdepixelize/priv/pixelgraph.h b/src/3rdparty/libdepixelize/priv/pixelgraph.h
new file mode 100644
index 0000000..a6e0f1a
--- /dev/null
+++ b/src/3rdparty/libdepixelize/priv/pixelgraph.h
@@ -0,0 +1,555 @@
+/* This file is part of the libdepixelize project
+ Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+ GNU Lesser General Public License Usage
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by the
+ Free Software Foundation; either version 2.1 of the License, or (at your
+ option) any later version.
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library. If not, see <http://www.gnu.org/licenses/>.
+
+ GNU General Public License Usage
+ Alternatively, this library may be used under the terms of the GNU General
+ Public License as published by the Free Software Foundation, either version
+ 2 of the License, or (at your option) any later version.
+ You should have received a copy of the GNU General Public License along with
+ this library. If not, see <http://www.gnu.org/licenses/>.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_PIXELGRAPH_H
+#define LIBDEPIXELIZE_TRACER_PIXELGRAPH_H
+
+#include <gdkmm/pixbuf.h>
+#include <vector>
+#include <cassert>
+#include <utility>
+
+namespace Tracer {
+
+class PixelGraph
+{
+public:
+ class Node
+ {
+ public:
+ /*
+ * Hamming weight of \p adj
+ */
+ unsigned adjsize() const
+ {
+ unsigned all[8] = {
+ adj.top,
+ adj.topright,
+ adj.right,
+ adj.bottomright,
+ adj.bottom,
+ adj.bottomleft,
+ adj.left,
+ adj.topleft
+ };
+ return all[0] + all[1] + all[2] + all[3]
+ + all[4] + all[5] + all[6] + all[7];
+ }
+
+ guint8 rgba[4];
+ // Nodes pointing from this
+ struct Adj
+ {
+ unsigned top: 1;
+ unsigned topright: 1;
+ unsigned right: 1;
+ unsigned bottomright: 1;
+ unsigned bottom: 1;
+ unsigned bottomleft: 1;
+ unsigned left: 1;
+ unsigned topleft: 1;
+ } adj;
+ };
+
+ typedef std::vector<Node>::iterator iterator;
+ typedef std::vector<Node>::const_iterator const_iterator;
+ typedef std::vector<Node>::reverse_iterator reverse_iterator;
+ typedef std::vector<Node>::const_reverse_iterator const_reverse_iterator;
+
+ typedef std::pair<iterator, iterator> Edge;
+ typedef std::pair<Edge, Edge> EdgePair;
+ typedef std::vector<EdgePair> EdgePairContainer;
+
+ class ColumnView
+ {
+ public:
+ ColumnView(std::vector<Node> &nodes, int width, int column) :
+ _nodes(nodes), _width(width), _column(column)
+ {}
+
+ Node &operator[](int line);
+
+ private:
+ std::vector<Node> &_nodes;
+ const int _width;
+ const int _column;
+ };
+
+ PixelGraph(Glib::RefPtr<Gdk::Pixbuf const> pixbuf);
+
+ void checkConsistency();
+
+ /**
+ * It'll let you access the nodes using the syntax:
+ *
+ * graph[x][y]
+ *
+ * Where x is the column and y is the line.
+ */
+ ColumnView operator[](int column);
+
+ // Iterators
+ iterator begin()
+ {
+ return _nodes.begin();
+ }
+
+ const_iterator begin() const
+ {
+ return _nodes.begin();
+ }
+
+ iterator end()
+ {
+ return _nodes.end();
+ }
+
+ const_iterator end() const
+ {
+ return _nodes.end();
+ }
+
+ reverse_iterator rbegin()
+ {
+ return _nodes.rbegin();
+ }
+
+ const_reverse_iterator rbegin() const
+ {
+ return _nodes.rbegin();
+ }
+
+ reverse_iterator rend()
+ {
+ return _nodes.rend();
+ }
+
+ const_reverse_iterator rend() const
+ {
+ return _nodes.rend();
+ }
+
+ size_t size() const
+ {
+ return _nodes.size();
+ }
+
+ int width() const
+ {
+ return _width;
+ }
+
+ int height() const
+ {
+ return _height;
+ }
+
+ // Algorithms
+ void connectAllNeighbors();
+ EdgePairContainer crossingEdges();
+
+ int toX(const_iterator n) const
+ {
+ return (&*n - &_nodes[0]) % _width;
+ }
+
+ int toY(const_iterator n) const
+ {
+ return (&*n - &_nodes[0]) / _width;
+ }
+
+ iterator nodeTop(iterator n)
+ {
+ return n - _width;
+ }
+
+ iterator nodeBottom(iterator n)
+ {
+ return n + _width;
+ }
+
+ iterator nodeLeft(iterator n)
+ {
+ return n - 1;
+ }
+
+ iterator nodeRight(iterator n)
+ {
+ return n + 1;
+ }
+
+ iterator nodeTopLeft(iterator n)
+ {
+ return n - _width - 1;
+ }
+
+ iterator nodeTopRight(iterator n)
+ {
+ return n - _width + 1;
+ }
+
+ iterator nodeBottomLeft(iterator n)
+ {
+ return n + _width - 1;
+ }
+
+ iterator nodeBottomRight(iterator n)
+ {
+ return n + _width + 1;
+ }
+
+ const_iterator nodeTop(const_iterator n) const
+ {
+ return n - _width;
+ }
+
+ const_iterator nodeBottom(const_iterator n) const
+ {
+ return n + _width;
+ }
+
+ const_iterator nodeLeft(const_iterator n) const
+ {
+ return n - 1;
+ }
+
+ const_iterator nodeRight(const_iterator n) const
+ {
+ return n + 1;
+ }
+
+ const_iterator nodeTopLeft(const_iterator n) const
+ {
+ return n - _width - 1;
+ }
+
+ const_iterator nodeTopRight(const_iterator n) const
+ {
+ return n - _width + 1;
+ }
+
+ const_iterator nodeBottomLeft(const_iterator n) const
+ {
+ return n + _width - 1;
+ }
+
+ const_iterator nodeBottomRight(const_iterator n) const
+ {
+ return n + _width + 1;
+ }
+
+private:
+ PixelGraph(const PixelGraph&);
+
+ int _width;
+ int _height;
+
+ // The data representation follows the image data pattern from gdk-pixbuf.
+ //
+ // Quoting:
+ // "Image data in a pixbuf is stored in memory in uncompressed, packed
+ // format. Rows in the image are stored top to bottom, and in each row
+ // pixels are stored from left to right. There may be padding at the end of
+ // a row."
+ //
+ // Differently, _nodes don't put padding among rows.
+ std::vector<Node> _nodes;
+};
+
+inline PixelGraph::PixelGraph(Glib::RefPtr<Gdk::Pixbuf const> pixbuf) :
+ _width(pixbuf->get_width()),
+ _height(pixbuf->get_height()),
+ _nodes(size_t(_width) * _height)
+{
+ if ( !_width || !_height )
+ return;
+
+ // Initialize the graph using the pixels' color data
+ guint8 const *pixels = pixbuf->get_pixels();
+ Node *dest = &_nodes[0];
+ const int n_channels = pixbuf->get_n_channels();
+ const int rowpadding = pixbuf->get_rowstride() - _width * n_channels;
+
+ if ( n_channels == 4 ) {
+ for ( int i = 0 ; i != _height ; ++i ) {
+ for ( int j = 0 ; j != _width ; ++j ) {
+ for ( int k = 0 ; k != 4 ; ++k )
+ dest->rgba[k] = pixels[k];
+ {
+ dest->adj.top = 0;
+ dest->adj.topright = 0;
+ dest->adj.right = 0;
+ dest->adj.bottomright = 0;
+ dest->adj.bottom = 0;
+ dest->adj.bottomleft = 0;
+ dest->adj.left = 0;
+ dest->adj.topleft = 0;
+ }
+ pixels += n_channels;
+ ++dest;
+ }
+ pixels += rowpadding;
+ }
+ } else {
+ assert(n_channels == 3);
+ for ( int i = 0 ; i != _height ; ++i ) {
+ for ( int j = 0 ; j != _width ; ++j ) {
+ for ( int k = 0 ; k != 3 ; ++k )
+ dest->rgba[k] = pixels[k];
+ dest->rgba[3] = '\xFF';
+ {
+ dest->adj.top = 0;
+ dest->adj.topright = 0;
+ dest->adj.right = 0;
+ dest->adj.bottomright = 0;
+ dest->adj.bottom = 0;
+ dest->adj.bottomleft = 0;
+ dest->adj.left = 0;
+ dest->adj.topleft = 0;
+ }
+ pixels += n_channels;
+ ++dest;
+ }
+ pixels += rowpadding;
+ }
+ }
+}
+
+inline void PixelGraph::checkConsistency()
+{
+ PixelGraph::Node *it = &_nodes.front();
+ for ( int i = 0 ; i != _height ; ++i ) {
+ for ( int j = 0 ; j != _width ; ++j, ++it ) {
+ if ( it->adj.top )
+ assert((it - _width)->adj.bottom);
+ if ( it->adj.topright )
+ assert((it - _width + 1)->adj.bottomleft);
+ if ( it->adj.right )
+ assert((it + 1)->adj.left);
+ if ( it->adj.bottomright )
+ assert((it + _width + 1)->adj.topleft);
+ if ( it->adj.bottom )
+ assert((it + _width)->adj.top);
+ if ( it->adj.bottomleft )
+ assert((it + _width - 1)->adj.topright);
+ if ( it->adj.left )
+ assert((it - 1)->adj.right);
+ if ( it->adj.topleft )
+ assert((it - _width - 1)->adj.bottomright);
+ }
+ }
+}
+
+inline PixelGraph::ColumnView PixelGraph::operator[](int column)
+{
+ return ColumnView(_nodes, _width, column);
+}
+
+inline void PixelGraph::connectAllNeighbors()
+{
+ // ...the "center" nodes first...
+ if ( _width > 2 && _height > 2 ) {
+ iterator it = nodeBottomRight(begin()); // [1][1]
+ for ( int i = 1 ; i != _height - 1 ; ++i ) {
+ for ( int j = 1 ; j != _width - 1 ; ++j ) {
+ it->adj.top = 1;
+ it->adj.topright = 1;
+ it->adj.right = 1;
+ it->adj.bottomright = 1;
+ it->adj.bottom = 1;
+ it->adj.bottomleft = 1;
+ it->adj.left = 1;
+ it->adj.topleft = 1;
+
+ it = nodeRight(it);
+ }
+ // After the previous loop, 'it' is pointing to the last node from
+ // the row.
+ // Go south, then first node in the row (increment 'it' by 1)
+ // Go to the second node in the line (increment 'it' by 1)
+ it += 2;
+ }
+ }
+
+ // ...then the "top" nodes...
+ if ( _width > 2 ) {
+ Node *it = &_nodes[1];
+ if ( _height > 1 ) {
+ for ( int i = 1 ; i != _width - 1 ; ++i ) {
+ it->adj.right = 1;
+ it->adj.bottomright = 1;
+ it->adj.bottom = 1;
+ it->adj.bottomleft = 1;
+ it->adj.left = 1;
+
+ ++it;
+ }
+ } else {
+ for ( int i = 1 ; i != _width - 1 ; ++i ) {
+ it->adj.right = 1;
+ it->adj.left = 1;
+
+ ++it;
+ }
+ }
+ }
+
+ // ...then the "bottom" nodes...
+ if ( _width > 2 && _height > 1 ) {
+ Node *it = &((*this)[1][_height - 1]);
+ for ( int i = 1 ; i != _width - 1 ; ++i ) {
+ it->adj.left = 1;
+ it->adj.topleft = 1;
+ it->adj.top = 1;
+ it->adj.topright = 1;
+ it->adj.right = 1;
+
+ ++it;
+ }
+ }
+
+ // ...then the "left" nodes...
+ if ( _height > 2 ) {
+ iterator it = nodeBottom(begin()); // [0][1]
+ if ( _width > 1 ) {
+ for ( int i = 1 ; i != _height - 1 ; ++i ) {
+ it->adj.top = 1;
+ it->adj.topright = 1;
+ it->adj.right = 1;
+ it->adj.bottomright = 1;
+ it->adj.bottom = 1;
+
+ it = nodeBottom(it);
+ }
+ } else {
+ for ( int i = 1 ; i != _height - 1 ; ++i ) {
+ it->adj.top = 1;
+ it->adj.bottom = 1;
+
+ it = nodeBottom(it);
+ }
+ }
+ }
+
+ // ...then the "right" nodes...
+ if ( _height > 2 && _width > 1 ) {
+ iterator it = nodeBottom(begin() + _width - 1);// [_width - 1][1]
+ for ( int i = 1 ; i != _height - 1 ; ++i ) {
+ it->adj.bottom = 1;
+ it->adj.bottomleft = 1;
+ it->adj.left = 1;
+ it->adj.topleft = 1;
+ it->adj.top = 1;
+
+ it = nodeBottom(it);
+ }
+ }
+
+ // ...and the 4 corner nodes
+ {
+ Node *const top_left = &(*this)[0][0];
+
+ if ( _width > 1 )
+ top_left->adj.right = 1;
+
+ if ( _width > 1 && _height > 1 )
+ top_left->adj.bottomright = 1;
+
+ if ( _height > 1 )
+ top_left->adj.bottom = 1;
+ }
+ if ( _width > 1 ) {
+ Node *const top_right = &(*this)[_width - 1][0];
+
+ if ( _height > 1 ) {
+ top_right->adj.bottom = 1;
+ top_right->adj.bottomleft = 1;
+ }
+
+ top_right->adj.left = 1;
+ }
+ if ( _height > 1 ) {
+ Node *const down_left = &(*this)[0][_height - 1];
+ down_left->adj.top = 1;
+
+ if ( _width > 1 ) {
+ down_left->adj.topright = 1;
+ down_left->adj.right = 1;
+ }
+ }
+ if ( _width > 1 && _height > 1 ) {
+ Node *const down_right = &(*this)[_width - 1][_height - 1];
+ down_right->adj.left = 1;
+ down_right->adj.topleft = 1;
+ down_right->adj.top = 1;
+ }
+}
+
+PixelGraph::EdgePairContainer PixelGraph::crossingEdges()
+{
+ EdgePairContainer ret;
+
+ if ( width() < 2 || height() < 2 )
+ return ret;
+
+ // Iterate over the graph, 2x2 blocks at time
+ PixelGraph::iterator it = begin();
+ for (int i = 0 ; i != height() - 1 ; ++i, ++it ) {
+ for ( int j = 0 ; j != width() - 1 ; ++j, ++it ) {
+ EdgePair diagonals(
+ Edge(it, nodeBottomRight(it)),
+ Edge(nodeRight(it), nodeBottom(it)));
+
+ // Check if there are crossing edges
+ if ( !diagonals.first.first->adj.bottomright
+ || !diagonals.second.first->adj.bottomleft ) {
+ continue;
+ }
+
+ ret.push_back(diagonals);
+ }
+ }
+
+ return ret;
+}
+
+inline PixelGraph::Node &PixelGraph::ColumnView::operator[](int line)
+{
+ return _nodes[line * _width + _column];
+}
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_PIXELGRAPH_H
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/3rdparty/libdepixelize/priv/point.h b/src/3rdparty/libdepixelize/priv/point.h
new file mode 100644
index 0000000..53babd9
--- /dev/null
+++ b/src/3rdparty/libdepixelize/priv/point.h
@@ -0,0 +1,112 @@
+/* This file is part of the libdepixelize project
+ Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+ GNU Lesser General Public License Usage
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by the
+ Free Software Foundation; either version 2.1 of the License, or (at your
+ option) any later version.
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library. If not, see <http://www.gnu.org/licenses/>.
+
+ GNU General Public License Usage
+ Alternatively, this library may be used under the terms of the GNU General
+ Public License as published by the Free Software Foundation, either version
+ 2 of the License, or (at your option) any later version.
+ You should have received a copy of the GNU General Public License along with
+ this library. If not, see <http://www.gnu.org/licenses/>.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_POINT_H
+#define LIBDEPIXELIZE_TRACER_POINT_H
+
+namespace Tracer {
+
+template<class T>
+struct Point
+{
+ Point() : smooth(false), visible(true) {}
+ Point(T x, T y) : smooth(false), visible(true), x(x), y(y) {}
+ Point(T x, T y, bool smooth) : smooth(smooth), visible(true), x(x), y(y) {}
+
+ Point operator+(const Point &rhs) const
+ {
+ return Point(x + rhs.x, y + rhs.y);
+ }
+
+ Point operator/(T foo) const
+ {
+ return Point(x / foo, y / foo);
+ }
+
+ Point invisible() const
+ {
+ Point p = *this;
+ p.visible = false;
+ return p;
+ }
+
+ bool smooth;
+
+ /**
+ * By default, all points are visible, but the poor amount of information
+ * that B-Splines (libdepixelize-specific) allows us to represent forces us
+ * to create additional points. But... these additional points don't need to
+ * be visible.
+ */
+ bool visible;
+
+ T x, y;
+};
+
+template<class T>
+Point<T> midpoint(const Point<T> &a, const Point<T> &b)
+{
+ return Point<T>((a.x + b.x) / 2, (a.y + b.y) / 2);
+}
+
+template<class T>
+bool operator==(const Point<T> &lhs, const Point<T> &rhs)
+{
+ return
+ /*
+ * Will make a better job identifying which points can be eliminated by
+ * cells union.
+ */
+#ifndef LIBDEPIXELIZE_IS_VERY_WELL_TESTED
+ lhs.smooth == rhs.smooth &&
+#endif // LIBDEPIXELIZE_IS_VERY_WELL_TESTED
+ lhs.x == rhs.x && lhs.y == rhs.y;
+}
+
+template<class T>
+bool weakly_equal(const Point<T> &a, const Point<T> &b)
+{
+ return a.x == b.x && a.y == b.y;
+}
+
+template<class T>
+Geom::Point to_geom_point(Point<T> p)
+{
+ return Geom::Point(p.x, p.y);
+}
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_POINT_H
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/3rdparty/libdepixelize/priv/simplifiedvoronoi.h b/src/3rdparty/libdepixelize/priv/simplifiedvoronoi.h
new file mode 100644
index 0000000..84feab0
--- /dev/null
+++ b/src/3rdparty/libdepixelize/priv/simplifiedvoronoi.h
@@ -0,0 +1,1707 @@
+/* This file is part of the libdepixelize project
+ Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+ GNU Lesser General Public License Usage
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by the
+ Free Software Foundation; either version 2.1 of the License, or (at your
+ option) any later version.
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library. If not, see <http://www.gnu.org/licenses/>.
+
+ GNU General Public License Usage
+ Alternatively, this library may be used under the terms of the GNU General
+ Public License as published by the Free Software Foundation, either version
+ 2 of the License, or (at your option) any later version.
+ You should have received a copy of the GNU General Public License along with
+ this library. If not, see <http://www.gnu.org/licenses/>.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_SIMPLIFIEDVORONOI_H
+#define LIBDEPIXELIZE_TRACER_SIMPLIFIEDVORONOI_H
+
+#include "pixelgraph.h"
+#include "colorspace.h"
+#include "point.h"
+#include "branchless.h"
+
+namespace Tracer {
+
+template<typename T, bool adjust_splines>
+class SimplifiedVoronoi
+{
+public:
+ /**
+ * The "smooth" attribute of each vertex is only accurate if edge is
+ * visible. This decision was made because invisible edges will disappear
+ * during polygon-union, the next phase of Kopf-Lischinski.
+ */
+ struct Cell
+ {
+ // There may not exist more than 8 vertices per cell and a
+ // "small vector optimization" could improve the performance
+ // by avoiding memory fragmentation. Serious testing is needed.
+
+ // The vertices are filled in clockwise order
+ std::vector< Point<T> > vertices;
+ guint8 rgba[4];
+ };
+
+ typedef typename std::vector<Cell>::iterator iterator;
+ typedef typename std::vector<Cell>::const_iterator const_iterator;
+ typedef typename std::vector<Cell>::reverse_iterator reverse_iterator;
+
+ typedef typename std::vector<Cell>::const_reverse_iterator
+ const_reverse_iterator;
+
+ /*
+ It will work correctly if no crossing-edges are present.
+ */
+ SimplifiedVoronoi(const PixelGraph &graph);
+
+ // Iterators
+ iterator begin()
+ {
+ return _cells.begin();
+ }
+
+ const_iterator begin() const
+ {
+ return _cells.begin();
+ }
+
+ iterator end()
+ {
+ return _cells.end();
+ }
+
+ const_iterator end() const
+ {
+ return _cells.end();
+ }
+
+ reverse_iterator rbegin()
+ {
+ return _cells.rbegin();
+ }
+
+ const_reverse_iterator rbegin() const
+ {
+ return _cells.rbegin();
+ }
+
+ reverse_iterator rend()
+ {
+ return _cells.rend();
+ }
+
+ const_reverse_iterator rend() const
+ {
+ return _cells.rend();
+ }
+
+ size_t size() const
+ {
+ return _cells.size();
+ }
+
+ int width() const
+ {
+ return _width;
+ }
+
+ int height() const
+ {
+ return _height;
+ }
+
+private:
+#ifdef LIBDEPIXELIZE_VERY_TYPE_SAFE
+ typedef void (*PointTransform)(Point<T> &p, T dx, T dy);
+ typedef bool (*NodeTransform)(PixelGraph::const_iterator);
+#endif // LIBDEPIXELIZE_VERY_TYPE_SAFE
+
+ /**
+ * Output is translated by -.5 in each axis. This function fixes this error.
+ */
+ static Point<T> _adjust(Point<T> p)
+ {
+ return Point<T>(p.x + .5, p.y + .5);
+ }
+
+ /**
+ * Output is translated by -.5 in each axis. This function fixes this error.
+ */
+ static Point<T> _adjust(Point<T> p, bool smooth)
+ {
+ return Point<T>(p.x + .5, p.y + .5, smooth);
+ }
+
+ void _complexTopLeft(const PixelGraph &graph,
+ PixelGraph::const_iterator graph_it,
+ Cell *const cells_it, int x, int y);
+ void _complexTopRight(const PixelGraph &graph,
+ PixelGraph::const_iterator graph_it,
+ Cell *const cells_it, int x, int y);
+ void _complexBottomRight(const PixelGraph &graph,
+ PixelGraph::const_iterator graph_it,
+ Cell *const cells_it, int x, int y);
+ void _complexBottomLeft(const PixelGraph &graph,
+ PixelGraph::const_iterator graph_it,
+ Cell *const cells_it, int x, int y);
+
+ static void _complexTopLeftTransform(Point<T> &p, T dx, T dy);
+ static void _complexTopRightTransform(Point<T> &p, T dx, T dy);
+ static void _complexBottomRightTransform(Point<T> &p, T dx, T dy);
+ static void _complexBottomLeftTransform(Point<T> &p, T dx, T dy);
+
+ static bool _complexTopLeftTransformTop(PixelGraph::const_iterator graph_it);
+ static bool _complexTopLeftTransformTopRight(PixelGraph::const_iterator graph_it);
+ static bool _complexTopLeftTransformRight(PixelGraph::const_iterator graph_it);
+ static bool _complexTopLeftTransformBottomRight(PixelGraph::const_iterator graph_it);
+ static bool _complexTopLeftTransformBottom(PixelGraph::const_iterator graph_it);
+ static bool _complexTopLeftTransformBottomLeft(PixelGraph::const_iterator graph_it);
+ static bool _complexTopLeftTransformLeft(PixelGraph::const_iterator graph_it);
+ static bool _complexTopLeftTransformTopLeft(PixelGraph::const_iterator graph_it);
+
+ static bool _complexTopRightTransformTop(PixelGraph::const_iterator graph_it);
+ static bool _complexTopRightTransformTopRight(PixelGraph::const_iterator graph_it);
+ static bool _complexTopRightTransformRight(PixelGraph::const_iterator graph_it);
+ static bool _complexTopRightTransformBottomRight(PixelGraph::const_iterator graph_it);
+ static bool _complexTopRightTransformBottom(PixelGraph::const_iterator graph_it);
+ static bool _complexTopRightTransformBottomLeft(PixelGraph::const_iterator graph_it);
+ static bool _complexTopRightTransformLeft(PixelGraph::const_iterator graph_it);
+ static bool _complexTopRightTransformTopLeft(PixelGraph::const_iterator graph_it);
+
+ static bool _complexBottomRightTransformTop(PixelGraph::const_iterator graph_it);
+ static bool _complexBottomRightTransformTopRight(PixelGraph::const_iterator graph_it);
+ static bool _complexBottomRightTransformRight(PixelGraph::const_iterator graph_it);
+ static bool _complexBottomRightTransformBottomRight(PixelGraph::const_iterator graph_it);
+ static bool _complexBottomRightTransformBottom(PixelGraph::const_iterator graph_it);
+ static bool _complexBottomRightTransformBottomLeft(PixelGraph::const_iterator graph_it);
+ static bool _complexBottomRightTransformLeft(PixelGraph::const_iterator graph_it);
+ static bool _complexBottomRightTransformTopLeft(PixelGraph::const_iterator graph_it);
+
+ static bool _complexBottomLeftTransformTop(PixelGraph::const_iterator graph_it);
+ static bool _complexBottomLeftTransformTopRight(PixelGraph::const_iterator graph_it);
+ static bool _complexBottomLeftTransformRight(PixelGraph::const_iterator graph_it);
+ static bool _complexBottomLeftTransformBottomRight(PixelGraph::const_iterator graph_it);
+ static bool _complexBottomLeftTransformBottom(PixelGraph::const_iterator graph_it);
+ static bool _complexBottomLeftTransformBottomLeft(PixelGraph::const_iterator graph_it);
+ static bool _complexBottomLeftTransformLeft(PixelGraph::const_iterator graph_it);
+ static bool _complexBottomLeftTransformTopLeft(PixelGraph::const_iterator graph_it);
+
+ /*
+ * The memory layout assumed goes like this (with a_it being the current
+ * iterated element):
+ *
+ * (a_it) | (b_it)
+ * -------+-------
+ * (c_it) | (d_it)
+ *
+ * If you want to use it with another directions (topleft, topright, ...)
+ * **DO NOT** invert x or y axis, because the insertion order will go mad.
+ *
+ * The idea behind this abstraction is to rotate the iterators, then the
+ * insertion order will be preserved.
+ *
+ * The initial value of all nodes that will be inserted is {x, y}. All
+ * changes to this node **MUST** occur through \p transform or _adjust.
+ *
+ * Some maintainers may like this function because they will handle a
+ * code base 4 times smaller and bugs will be MUCH MUCH difficult to hide.
+ *
+ * Some maintainers may go mad because the level extra level of
+ * abstraction.
+ *
+ * "All problems in computer science can be solved by another level of
+ * indirection, except for the problem of too many layers of indirection."
+ * -- David J. Wheeler
+ */
+#ifndef LIBDEPIXELIZE_VERY_TYPE_SAFE
+ template<class PointTransform, class NodeTransform>
+#endif // LIBDEPIXELIZE_VERY_TYPE_SAFE
+ void _genericComplexBottomRight(PixelGraph::const_iterator a_it,
+ PixelGraph::const_iterator b_it,
+ PixelGraph::const_iterator c_it,
+ PixelGraph::const_iterator d_it,
+ Cell *const cells_it, int x, int y,
+ PointTransform transform,
+ NodeTransform top,
+ NodeTransform topright,
+ NodeTransform right,
+ NodeTransform bottomright,
+ NodeTransform bottom,
+ NodeTransform bottomleft,
+ NodeTransform left,
+ NodeTransform topleft);
+
+ int _width;
+ int _height;
+ std::vector<Cell> _cells;
+};
+
+template<class T, bool adjust_splines>
+SimplifiedVoronoi<T, adjust_splines>
+::SimplifiedVoronoi(const PixelGraph &graph) :
+ _width(graph.width()),
+ _height(graph.height()),
+ _cells(graph.size())
+{
+ if (!graph.size())
+ return;
+
+ /*
+ * The insertion order of cells is not a big deal. Here I just follow
+ * the order of PixelGraph arrangement.
+ */
+
+ // ...the "center" cells first...
+ if ( _width > 2 && _height > 2 ) {
+ PixelGraph::const_iterator graph_it = graph.begin() + _width + 1;
+ Cell *cells_it = &_cells.front() + _width + 1;
+
+ for ( int i = 1 ; i != _height - 1 ; ++i ) {
+ for ( int j = 1 ; j != _width - 1 ; ++j, ++graph_it, ++cells_it ) {
+ for ( int k = 0 ; k != 4 ; ++k )
+ cells_it->rgba[k] = graph_it->rgba[k];
+ // Top-left
+ _complexTopLeft(graph, graph_it, cells_it, j, i);
+
+ // Top-right
+ _complexTopRight(graph, graph_it, cells_it, j, i);
+
+ // Bottom-right
+ _complexBottomRight(graph, graph_it, cells_it, j, i);
+
+ // Bottom-left
+ _complexBottomLeft(graph, graph_it, cells_it, j, i);
+ }
+ // After the previous loop, 'it' is pointing to the last cell from
+ // the row.
+ // Go south, then first node in the row (increment 'it' by 1)
+ // Go to the second node in the line (increment 'it' by 1)
+ graph_it += 2;
+ cells_it += 2;
+ }
+ }
+
+ // ...then the "top" cells...
+ if ( _width > 2 ) {
+ PixelGraph::const_iterator graph_it = graph.begin() + 1;
+ Cell *cells_it = &_cells.front() + 1;
+
+ if ( _height > 1 ) {
+ for ( int i = 1 ; i != _width - 1 ; ++i, ++graph_it, ++cells_it ) {
+ for ( int j = 0 ; j != 4 ; ++j )
+ cells_it->rgba[j] = graph_it->rgba[j];
+
+ // Top-left
+ cells_it->vertices.push_back(Point<T>(i, 0, false));
+
+ // Top-right
+ cells_it->vertices.push_back(Point<T>(i + 1, 0, false));
+
+ // Bottom-right
+ _complexBottomRight(graph, graph_it, cells_it, i, 0);
+
+ // Bottom-left
+ _complexBottomLeft(graph, graph_it, cells_it, i, 0);
+ }
+ } else {
+ for ( int i = 1 ; i != _width - 1 ; ++i, ++graph_it, ++cells_it ) {
+ for ( int j = 0 ; j != 4 ; ++j )
+ cells_it->rgba[j] = graph_it->rgba[j];
+
+ // Top-left
+ cells_it->vertices.push_back(Point<T>(i, 0, false));
+
+ // Top-right
+ cells_it->vertices.push_back(Point<T>(i + 1, 0, false));
+
+ // Bottom-right
+ cells_it->vertices.push_back(Point<T>(i + 1, 1, false));
+
+ // Bottom-left
+ cells_it->vertices.push_back(Point<T>(i, 1, false));
+ }
+ }
+ }
+
+ // ...then the "bottom" cells...
+ if ( _width > 2 && _height > 1 ) {
+ // Node *it = &((*this)[1][_height - 1]);
+ PixelGraph::const_iterator graph_it
+ = graph.begin() + (_height - 1) * _width + 1;
+ Cell *cells_it = &_cells.front() + (_height - 1) * _width + 1;
+
+ for ( int i = 1 ; i != _width - 1 ; ++i, ++graph_it, ++cells_it ) {
+ for ( int j = 0 ; j != 4 ; ++j )
+ cells_it->rgba[j] = graph_it->rgba[j];
+
+ // Top-left
+ _complexTopLeft(graph, graph_it, cells_it, i, _height - 1);
+
+ // Top-right
+ _complexTopRight(graph, graph_it, cells_it, i, _height - 1);
+
+ // Bottom-right
+ cells_it->vertices.push_back(Point<T>(i + 1, _height, false));
+
+ // Bottom-left
+ cells_it->vertices.push_back(Point<T>(i, _height, false));
+ }
+ }
+
+ // ...then the "left" cells...
+ if ( _height > 2 ) {
+ PixelGraph::const_iterator graph_it = graph.begin() + _width;
+ Cell *cells_it = &_cells.front() + _width;
+
+ if ( _width > 1 ) {
+ for ( int i = 1 ; i != _height - 1 ; ++i) {
+ for ( int j = 0 ; j != 4 ; ++j )
+ cells_it->rgba[j] = graph_it->rgba[j];
+
+ // Top-left
+ cells_it->vertices.push_back(Point<T>(0, i, false));
+
+ // Top-right
+ _complexTopRight(graph, graph_it, cells_it, 0, i);
+
+ // Bottom-right
+ _complexBottomRight(graph, graph_it, cells_it, 0, i);
+
+ // Bottom-left
+ cells_it->vertices.push_back(Point<T>(0, i + 1, false));
+
+ graph_it += _width;
+ cells_it += _width;
+ }
+ } else {
+ for ( int i = 1 ; i != _height - 1 ; ++i) {
+ for ( int j = 0 ; j != 4 ; ++j )
+ cells_it->rgba[j] = graph_it->rgba[j];
+
+ // Top-left
+ cells_it->vertices.push_back(Point<T>(0, i, false));
+
+ // Top-right
+ cells_it->vertices.push_back(Point<T>(1, i, false));
+
+ // Bottom-right
+ cells_it->vertices.push_back(Point<T>(1, i, false));
+
+ // Bottom-left
+ cells_it->vertices.push_back(Point<T>(0, i + 1, false));
+
+ graph_it += _width;
+ cells_it += _width;
+ }
+ }
+ }
+
+ // ...then the "right" cells...
+ if ( _height > 2 && _width > 1 ) {
+ PixelGraph::const_iterator graph_it = graph.begin() + 2 * _width - 1;
+ Cell *cells_it = &_cells.front() + 2 * _width - 1;
+
+ for ( int i = 1 ; i != _height - 1 ; ++i ) {
+ for ( int j = 0 ; j != 4 ; ++j )
+ cells_it->rgba[j] = graph_it->rgba[j];
+
+ // Top-left
+ _complexTopLeft(graph, graph_it, cells_it, _width - 1, i);
+
+ // Top-right
+ cells_it->vertices.push_back(Point<T>(_width, i, false));
+
+ // Bottom-right
+ cells_it->vertices.push_back(Point<T>(_width, i + 1, false));
+
+ // Bottom-left
+ _complexBottomLeft(graph, graph_it, cells_it, _width - 1, i);
+
+ graph_it += _width;
+ cells_it += _width;
+ }
+ }
+
+ // ...and the 4 corner nodes
+ // top-left
+ {
+ PixelGraph::const_iterator graph_it = graph.begin();
+ Cell *cells_it = &_cells.front();
+
+ for ( int i = 0 ; i != 4 ; ++i )
+ cells_it->rgba[i] = graph_it->rgba[i];
+
+ // Top-left
+ cells_it->vertices.push_back(Point<T>(0, 0, false));
+
+ // Top-right
+ cells_it->vertices.push_back(Point<T>(1, 0, false));
+
+ // Bottom-right
+ if ( _width > 1 && _height > 1 )
+ _complexBottomRight(graph, graph_it, cells_it, 0, 0);
+ else
+ cells_it->vertices.push_back(Point<T>(1, 1, false));
+
+ // Bottom-left
+ cells_it->vertices.push_back(Point<T>(0, 1, false));
+ }
+
+ // top-right
+ if ( _width > 1 ) {
+ PixelGraph::const_iterator graph_it = graph.begin() + _width - 1;
+ Cell *cells_it = &_cells.front() + _width - 1;
+
+ for ( int i = 0 ; i != 4 ; ++i )
+ cells_it->rgba[i] = graph_it->rgba[i];
+
+ // Top-left
+ cells_it->vertices.push_back(Point<T>(_width - 1, 0, false));
+
+ // Top-right
+ cells_it->vertices.push_back(Point<T>(_width, 0, false));
+
+ // Bottom-right
+ cells_it->vertices.push_back(Point<T>(_width, 1, false));
+
+ // Bottom-left
+ if ( _height > 1 )
+ _complexBottomLeft(graph, graph_it, cells_it, _width - 1, 0);
+ else
+ cells_it->vertices.push_back(Point<T>(_width - 1, 1, false));
+ }
+
+ // bottom-left
+ if ( _height > 1 ) {
+ PixelGraph::const_iterator graph_it
+ = graph.begin() + (_height - 1) * _width;
+ Cell *cells_it = &_cells.front() + (_height - 1) * _width;
+
+ for ( int i = 0 ; i != 4 ; ++i )
+ cells_it->rgba[i] = graph_it->rgba[i];
+
+ // Top-left
+ cells_it->vertices.push_back(Point<T>(0, _height - 1, false));
+
+ // Top-right
+ if ( _width > 1)
+ _complexTopRight(graph, graph_it, cells_it, 0, _height - 1);
+ else
+ cells_it->vertices.push_back(Point<T>(1, _height - 1, false));
+
+ // Bottom-right
+ cells_it->vertices.push_back(Point<T>(1, _height, false));
+
+ // Bottom-left
+ cells_it->vertices.push_back(Point<T>(0, _height, false));
+ }
+
+ // bottom-right
+ if ( _width > 1 && _height > 1 ) {
+ PixelGraph::const_iterator graph_it = --graph.end();
+ Cell *cells_it = &_cells.back();
+
+ for ( int i = 0 ; i != 4 ; ++i )
+ cells_it->rgba[i] = graph_it->rgba[i];
+
+ // Top-left
+ _complexTopLeft(graph, graph_it, cells_it, _width - 1, _height - 1);
+
+ // Top-right
+ cells_it->vertices.push_back(Point<T>(_width, _height - 1, false));
+
+ // Bottom-right
+ cells_it->vertices.push_back(Point<T>(_width, _height, false));
+
+ // Bottom-left
+ cells_it->vertices.push_back(Point<T>(_width - 1, _height, false));
+ }
+}
+
+template<class T, bool adjust_splines> void
+SimplifiedVoronoi<T, adjust_splines>
+::_complexTopLeft(const PixelGraph &graph,
+ PixelGraph::const_iterator graph_it, Cell *const cells_it,
+ int x, int y)
+{
+ _genericComplexBottomRight(graph_it,
+ graph.nodeLeft(graph_it),
+ graph.nodeTop(graph_it),
+ graph.nodeTopLeft(graph_it),
+ cells_it, x, y,
+ &SimplifiedVoronoi::_complexTopLeftTransform,
+ &SimplifiedVoronoi::_complexTopLeftTransformTop,
+ &SimplifiedVoronoi::_complexTopLeftTransformTopRight,
+ &SimplifiedVoronoi::_complexTopLeftTransformRight,
+ &SimplifiedVoronoi::_complexTopLeftTransformBottomRight,
+ &SimplifiedVoronoi::_complexTopLeftTransformBottom,
+ &SimplifiedVoronoi::_complexTopLeftTransformBottomLeft,
+ &SimplifiedVoronoi::_complexTopLeftTransformLeft,
+ &SimplifiedVoronoi::_complexTopLeftTransformTopLeft);
+}
+
+template<class T, bool adjust_splines> void
+SimplifiedVoronoi<T, adjust_splines>
+::_complexTopRight(const PixelGraph &graph,
+ PixelGraph::const_iterator graph_it, Cell *const cells_it,
+ int x, int y)
+{
+ _genericComplexBottomRight(graph_it,
+ graph.nodeTop(graph_it),
+ graph.nodeRight(graph_it),
+ graph.nodeTopRight(graph_it),
+ cells_it, x, y,
+ &SimplifiedVoronoi::_complexTopRightTransform,
+ &SimplifiedVoronoi::_complexTopRightTransformTop,
+ &SimplifiedVoronoi::_complexTopRightTransformTopRight,
+ &SimplifiedVoronoi::_complexTopRightTransformRight,
+ &SimplifiedVoronoi::_complexTopRightTransformBottomRight,
+ &SimplifiedVoronoi::_complexTopRightTransformBottom,
+ &SimplifiedVoronoi::_complexTopRightTransformBottomLeft,
+ &SimplifiedVoronoi::_complexTopRightTransformLeft,
+ &SimplifiedVoronoi::_complexTopRightTransformTopLeft);
+}
+
+template<class T, bool adjust_splines> void
+SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomRight(const PixelGraph &graph,
+ PixelGraph::const_iterator graph_it, Cell *const cells_it,
+ int x, int y)
+{
+ _genericComplexBottomRight(graph_it,
+ graph.nodeRight(graph_it),
+ graph.nodeBottom(graph_it),
+ graph.nodeBottomRight(graph_it),
+ cells_it, x, y,
+ &SimplifiedVoronoi::_complexBottomRightTransform,
+ &SimplifiedVoronoi::_complexBottomRightTransformTop,
+ &SimplifiedVoronoi::_complexBottomRightTransformTopRight,
+ &SimplifiedVoronoi::_complexBottomRightTransformRight,
+ &SimplifiedVoronoi::_complexBottomRightTransformBottomRight,
+ &SimplifiedVoronoi::_complexBottomRightTransformBottom,
+ &SimplifiedVoronoi::_complexBottomRightTransformBottomLeft,
+ &SimplifiedVoronoi::_complexBottomRightTransformLeft,
+ &SimplifiedVoronoi::_complexBottomRightTransformTopLeft);
+}
+
+template<class T, bool adjust_splines> void
+SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomLeft(const PixelGraph &graph,
+ PixelGraph::const_iterator graph_it, Cell *const cells_it,
+ int x, int y)
+{
+ _genericComplexBottomRight(graph_it,
+ graph.nodeBottom(graph_it),
+ graph.nodeLeft(graph_it),
+ graph.nodeBottomLeft(graph_it),
+ cells_it, x, y,
+ &SimplifiedVoronoi::_complexBottomLeftTransform,
+ &SimplifiedVoronoi::_complexBottomLeftTransformTop,
+ &SimplifiedVoronoi::_complexBottomLeftTransformTopRight,
+ &SimplifiedVoronoi::_complexBottomLeftTransformRight,
+ &SimplifiedVoronoi::_complexBottomLeftTransformBottomRight,
+ &SimplifiedVoronoi::_complexBottomLeftTransformBottom,
+ &SimplifiedVoronoi::_complexBottomLeftTransformBottomLeft,
+ &SimplifiedVoronoi::_complexBottomLeftTransformLeft,
+ &SimplifiedVoronoi::_complexBottomLeftTransformTopLeft);
+}
+
+template<class T, bool adjust_splines> void
+SimplifiedVoronoi<T, adjust_splines>
+::_complexTopLeftTransform(Point<T> &p, T dx, T dy)
+{
+ p.x -= dx;
+ p.y -= dy;
+}
+
+template<class T, bool adjust_splines> void
+SimplifiedVoronoi<T, adjust_splines>
+::_complexTopRightTransform(Point<T> &p, T dx, T dy)
+{
+ p.x += dy;
+ p.y -= dx;
+}
+
+template<class T, bool adjust_splines> void
+SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomRightTransform(Point<T> &p, T dx, T dy)
+{
+ p.x += dx;
+ p.y += dy;
+}
+
+template<class T, bool adjust_splines> void
+SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomLeftTransform(Point<T> &p, T dx, T dy)
+{
+ p.x -= dy;
+ p.y += dx;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexTopLeftTransformTop(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.bottom;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexTopLeftTransformTopRight(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.bottomleft;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexTopLeftTransformRight(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.left;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexTopLeftTransformBottomRight(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.topleft;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexTopLeftTransformBottom(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.top;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexTopLeftTransformBottomLeft(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.topright;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexTopLeftTransformLeft(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.right;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexTopLeftTransformTopLeft(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.bottomright;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexTopRightTransformTop(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.left;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexTopRightTransformTopRight(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.topleft;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexTopRightTransformRight(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.top;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexTopRightTransformBottomRight(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.topright;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexTopRightTransformBottom(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.right;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexTopRightTransformBottomLeft(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.bottomright;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexTopRightTransformLeft(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.bottom;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexTopRightTransformTopLeft(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.bottomleft;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomRightTransformTop(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.top;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomRightTransformTopRight(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.topright;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomRightTransformRight(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.right;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomRightTransformBottomRight(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.bottomright;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomRightTransformBottom(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.bottom;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomRightTransformBottomLeft(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.bottomleft;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomRightTransformLeft(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.left;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomRightTransformTopLeft(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.topleft;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomLeftTransformTop(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.right;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomLeftTransformTopRight(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.bottomright;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomLeftTransformRight(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.bottom;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomLeftTransformBottomRight(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.bottomleft;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomLeftTransformBottom(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.left;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomLeftTransformBottomLeft(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.topleft;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomLeftTransformLeft(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.top;
+}
+
+template<class T, bool adjust_splines>
+bool SimplifiedVoronoi<T, adjust_splines>
+::_complexBottomLeftTransformTopLeft(PixelGraph::const_iterator graph_it)
+{
+ return graph_it->adj.topright;
+}
+
+template<class T, bool adjust_splines>
+#ifndef LIBDEPIXELIZE_VERY_TYPE_SAFE
+template<class PointTransform, class NodeTransform>
+#endif // LIBDEPIXELIZE_VERY_TYPE_SAFE
+void
+SimplifiedVoronoi<T, adjust_splines>
+::_genericComplexBottomRight(PixelGraph::const_iterator a_it,
+ PixelGraph::const_iterator b_it,
+ PixelGraph::const_iterator c_it,
+ PixelGraph::const_iterator d_it,
+ Cell *const cells_it, int x, int y,
+ PointTransform transform,
+ NodeTransform,
+ NodeTransform topright,
+ NodeTransform right,
+ NodeTransform bottomright,
+ NodeTransform bottom,
+ NodeTransform bottomleft,
+ NodeTransform,
+ NodeTransform topleft)
+{
+ using colorspace::contour_edge;
+ using colorspace::same_color;
+
+ const Point<T> initial(x, y);
+
+ /*
+ * The insertion order of points within the cell is very important. You must
+ * follow current practice: Clockwise order.
+ */
+
+ if ( bottomright(a_it) ) {
+ // this and bottom-right are connected
+
+ bool smooth[2] = {
+ ( same_color(a_it->rgba, d_it->rgba)
+ || same_color(a_it->rgba, b_it->rgba)
+ || same_color(b_it->rgba, d_it->rgba) ),
+ ( same_color(a_it->rgba, d_it->rgba)
+ || same_color(a_it->rgba, c_it->rgba)
+ || same_color(c_it->rgba, d_it->rgba) )
+ };
+
+ Point<T> borderMid = initial;
+ {
+ transform(borderMid, 1, 1);
+ borderMid = midpoint(initial, borderMid);
+ }
+
+ Point<T> vertices[2] = {initial, initial};
+ {
+ transform(vertices[0], 1, 0);
+ vertices[0] = _adjust(midpoint(borderMid, vertices[0]), smooth[0]);
+
+ transform(vertices[1], 0, 1);
+ vertices[1] = _adjust(midpoint(borderMid, vertices[1]), smooth[1]);
+ }
+
+ if ( !smooth[0] && adjust_splines ) {
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_1ST_IS_INVISIBLE
+ cells_it->vertices.push_back(vertices[0].invisible());
+#else
+ cells_it->vertices.push_back(vertices[0]);
+#endif
+ {
+ Point<T> another = vertices[0];
+ transform(another,
+ - ( 0.1875
+ - ( topright(a_it) - topleft(b_it) ) * 0.1875 ),
+ // y
+ - ( 0.5625
+ - ( topright(a_it) + topleft(b_it) ) * 0.1875 ));
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_2ND_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertices[0];
+ transform(another,
+ - ( 0.0625
+ - ( topright(a_it) - topleft(b_it) ) * 0.0625 ),
+ // y
+ - ( 0.1875
+ - ( topright(a_it) + topleft(b_it) ) * 0.0625) );
+ another.smooth = true;
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_3RD_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertices[0];
+ transform(another,
+ 0.1875
+ - ( bottomright(b_it) + topright(d_it) ) * 0.0625,
+ // y
+ 0.0625
+ + ( bottomright(b_it) - topright(d_it) ) * 0.0625);
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_4TH_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ transform(vertices[0],
+ 0.0625
+ + ( topright(a_it) - topright(d_it) - topleft(b_it)
+ - bottomright(b_it) ) * 0.03125,
+ // y
+ - ( 0.0625
+ + ( topright(d_it) - topright(a_it)
+ - topleft(b_it) - bottomright(b_it) )
+ * 0.03125 ));
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_5TH_IS_INVISIBLE
+ vertices[0].visible = false;
+#endif
+ }
+ }
+
+ cells_it->vertices.push_back(vertices[0]);
+
+ if ( !smooth[1] && adjust_splines ) {
+ {
+ Point<T> another = vertices[1];
+ transform(another,
+ - ( 0.0625
+ + ( bottomleft(d_it) - bottomleft(a_it)
+ - topleft(c_it) - bottomright(c_it) )
+ * 0.03125 ),
+ // y
+ 0.0625
+ + ( bottomleft(a_it) - bottomleft(d_it)
+ - topleft(c_it) - bottomright(c_it) ) * 0.03125);
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_1ST_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertices[1];
+ transform(another,
+ 0.0625
+ + ( bottomright(c_it) - bottomleft(d_it) ) * 0.0625,
+ // y
+ 0.1875
+ - ( bottomright(c_it) + bottomleft(d_it) ) * 0.0625);
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_2ND_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertices[1];
+ transform(another,
+ - ( 0.1875
+ - ( bottomleft(a_it) + topleft(c_it) )
+ * 0.0625 ),
+ // y
+ - ( 0.0625
+ - ( bottomleft(a_it) - topleft(c_it) )
+ * 0.0625 ));
+ another.smooth = true;
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_3RD_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertices[1];
+ transform(another,
+ - ( 0.5625
+ - ( bottomleft(a_it) + topleft(c_it) )
+ * 0.1875 ),
+ // y
+ - ( 0.1875
+ - ( bottomleft(a_it) - topleft(c_it) )
+ * 0.1875 ));
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_4TH_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_5TH_IS_INVISIBLE
+ vertices[1].visible = false;
+#endif
+ }
+
+ cells_it->vertices.push_back(vertices[1]);
+ } else if ( bottomleft(b_it) ) {
+ // right and bottom are connected
+
+ Point<T> vertex = initial;
+ transform(vertex, 1, 1);
+ vertex = _adjust(midpoint(midpoint(initial, vertex), initial), true);
+ cells_it->vertices.push_back(vertex);
+ } else {
+ // Connections don't affect the shape of this squared-like
+ // pixel
+
+ Point<T> vertex = initial;
+ transform(vertex, 1, 1);
+ vertex = _adjust(midpoint(initial, vertex));
+
+ // compute smoothness
+ if ( right(a_it) && adjust_splines ) {
+ // this and right are connected
+
+ if ( !right(c_it) && !( bottom(a_it) && bottom(b_it) ) ) {
+ // bottom and bottom-right are disconnected
+
+ bool foreign_is_contour = contour_edge(c_it->rgba, d_it->rgba);
+ bool twin_is_contour = contour_edge(b_it->rgba, d_it->rgba);
+ bool another_is_contour = contour_edge(a_it->rgba, c_it->rgba);
+
+ if ( another_is_contour + twin_is_contour
+ + foreign_is_contour == 2 ) {
+ vertex.smooth = !foreign_is_contour;
+
+ if ( !vertex.smooth ) {
+ if ( another_is_contour ) {
+ {
+ Point<T> another = vertex;
+ T amount = 0.125
+ - ( ( bottomright(c_it) + topleft(c_it) )
+ * 0.03125 );
+ transform(another, - amount, amount);
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_1ST_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.0625 * bottomright(c_it);
+ transform(another, amount, 0.25 - amount);
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_2ND_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.0625 * topleft(c_it);
+ transform(another, - ( 0.25 - amount ),
+ - amount);
+ another.smooth = true;
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_3RD_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.1875 * topleft(c_it);
+ transform(another, - ( 0.75 - amount ),
+ - amount);
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_4TH_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_5TH_IS_INVISIBLE
+ vertex.visible = false;
+#endif
+ } else if ( twin_is_contour ) {
+ T amount = 0.125
+ - ( ( bottomleft(d_it) + topright(d_it) )
+ * 0.03125 );
+ transform(vertex, amount, amount);
+ }
+ } else if ( !same_color(a_it->rgba, b_it->rgba) ) {
+ vertex.smooth = false;
+ // This is the same code of the if ( special )
+ // I REALLY NEED lambdas to improve this code without
+ // creating yet another interface that takes a million
+ // of function parameters and keep code locality
+ {
+ Point<T> another = vertex;
+ T amount = 0.03125;
+ transform(another,
+ amount
+ * ( topleft(c_it) - topright(d_it)
+ + bottomleft(a_it) - bottomright(b_it) ),
+ // y
+ - amount
+ * ( topleft(c_it) + topright(d_it)
+ - bottomleft(a_it) - bottomright(b_it) ));
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_1ST_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.0625;
+ transform(another,
+ 0.25 - amount
+ * ( topright(d_it) + bottomright(b_it) ),
+ // y
+ - amount
+ * ( topright(d_it) - bottomright(b_it) ));
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_2ND_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.0625;
+ transform(another,
+ - ( 0.25 - amount
+ * ( topleft(c_it) + bottomleft(a_it) ) ),
+ // y
+ - amount
+ * ( topleft(c_it) - bottomleft(a_it) ));
+ another.smooth = true;
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_3RD_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.1875;
+ transform(another,
+ - ( 0.75 - amount
+ * ( topleft(c_it) + bottomleft(a_it) ) ),
+ // y
+ - amount
+ * ( topleft(c_it) - bottomleft(a_it) ));
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_4TH_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_5TH_IS_INVISIBLE
+ vertex.visible = false;
+#endif
+ }
+ } else {
+ // {this, right} is the pair with the angle
+ // closest to 180 degrees
+ vertex.smooth = same_color(a_it->rgba, b_it->rgba);
+ }
+ } else {
+ // there might be 2-color, then vertex.smooth = true
+
+ // or it might be 1-color and doesn't matter,
+ // because the current node will disappear
+ vertex.smooth
+ = same_color(a_it->rgba, b_it->rgba)
+ + same_color(a_it->rgba, c_it->rgba)
+ + same_color(d_it->rgba, b_it->rgba)
+ + same_color(d_it->rgba, c_it->rgba) == 2;
+ }
+ } else if ( bottom(a_it) && adjust_splines ) {
+ // this and bottom are connected
+
+ if ( !bottom(b_it) && !( right(a_it) && right(c_it) ) ) {
+ // right and bottom-right are disconnected
+
+ bool foreign_is_contour = contour_edge(b_it->rgba, d_it->rgba);
+ bool twin_is_contour = contour_edge(c_it->rgba, d_it->rgba);
+ bool another_is_contour = contour_edge(a_it->rgba, b_it->rgba);
+
+ if ( another_is_contour + twin_is_contour
+ + foreign_is_contour == 2 ) {
+ vertex.smooth = !foreign_is_contour;
+
+ if ( !vertex.smooth ) {
+ if ( another_is_contour ) {
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_1ST_IS_INVISIBLE
+ cells_it->vertices.push_back(vertex.invisible());
+#else
+ cells_it->vertices.push_back(vertex);
+#endif
+ {
+ Point<T> another = vertex;
+ T amount = 0.1875 * topleft(b_it);
+ transform(another, - amount,
+ - ( 0.75 - amount ));
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_2ND_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.0625 * topleft(b_it);
+ transform(another, - amount,
+ - ( 0.25 - amount ));
+ another.smooth = true;
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_3RD_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.0625 * bottomright(b_it);
+ transform(another, 0.25 - amount, amount);
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_4TH_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ T amount = 0.125
+ - (bottomright(b_it) + topleft(b_it))
+ * 0.03125;
+ transform(vertex, amount, - amount);
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_5TH_IS_INVISIBLE
+ vertex.visible = false;
+#endif
+ }
+ } else if ( twin_is_contour ) {
+ T amount = 0.125
+ - ( ( topright(d_it) + bottomleft(d_it) )
+ * 0.03125 );
+ transform(vertex, amount, amount);
+ }
+ } else if ( !same_color(a_it->rgba, c_it->rgba) ) {
+ vertex.smooth = false;
+ // This is the same code of the if ( special )
+ // I REALLY NEED lambdas to improve this code without
+ // creating yet another interface that takes a million
+ // of function parameters and keep code locality
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_1ST_IS_INVISIBLE
+ cells_it->vertices.push_back(vertex.invisible());
+#else
+ cells_it->vertices.push_back(vertex);
+#endif
+ {
+ Point<T> another = vertex;
+ T amount = 0.1875;
+ transform(another,
+ - ( topleft(b_it) - topright(a_it) ) * amount,
+ // y
+ - ( 0.75
+ - ( topleft(b_it) + topright(a_it) )
+ * amount ));
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_2ND_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.0625;
+ transform(another,
+ - ( topleft(b_it) - topright(a_it) ) * amount,
+ // y
+ - ( 0.25
+ - ( topleft(b_it) + topright(a_it) )
+ * amount ));
+ another.smooth = true;
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_3RD_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.0625;
+ transform(another, - amount
+ * ( bottomleft(d_it) - bottomright(c_it) ),
+ // y
+ 0.25 - amount
+ * ( bottomleft(d_it) + bottomright(c_it) ));
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_4TH_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ transform(vertex,
+ - ( topleft(b_it) + bottomleft(d_it)
+ - topright(a_it) - bottomright(c_it) )
+ * 0.03125,
+ // y
+ ( topleft(b_it) - bottomleft(d_it)
+ + topright(a_it) - bottomright(c_it) )
+ * 0.03125);
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_5TH_IS_INVISIBLE
+ vertex.visible = false;
+#endif
+ }
+ }
+ } else {
+ // {this, bottom} is the pair with the angle
+ // closest to 180 degrees
+ vertex.smooth = same_color(a_it->rgba, c_it->rgba);
+ }
+ } else {
+ // there might be 2-color, then vertex.smooth = true
+
+ // or it might be 1-color and doesn't matter,
+ // because the current node will disappear
+ vertex.smooth
+ = same_color(a_it->rgba, c_it->rgba)
+ + same_color(a_it->rgba, b_it->rgba)
+ + same_color(d_it->rgba, b_it->rgba)
+ + same_color(d_it->rgba, c_it->rgba) == 2;
+ }
+ } else if ( bottom(b_it) && adjust_splines ) {
+ // right and bottom-right are connected
+
+ bool special = false;
+
+ bool foreign_is_contour = contour_edge(c_it->rgba, d_it->rgba);
+
+ // the neighbor similar in 90° feature
+ bool similar_neighbor_is_contour
+ = contour_edge(a_it->rgba, c_it->rgba);
+
+ if ( contour_edge(a_it->rgba, b_it->rgba)
+ + similar_neighbor_is_contour
+ + foreign_is_contour == 2 ) {
+ vertex.smooth = !foreign_is_contour;
+
+ if ( !vertex.smooth ) {
+ if ( similar_neighbor_is_contour ) {
+ {
+ Point<T> another = vertex;
+ T amount = 0.125
+ - ( topleft(c_it) + bottomright(c_it) )
+ * 0.03125;
+ transform(another, - amount, amount);
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_1ST_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.0625 * bottomright(c_it);
+ transform(another, amount, 0.25 - amount);
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_2ND_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.0625 * topleft(c_it);
+ transform(another, - ( 0.25 - amount ), - amount);
+ another.smooth = true;
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_3RD_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.1875 * topleft(c_it);
+ transform(another, - ( 0.75 - amount ), - amount);
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_4TH_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_5TH_IS_INVISIBLE
+ vertex.visible = false;
+#endif
+ } else {
+ special = true;
+ }
+ }
+ } else {
+ // {right, bottom-right} is the pair with the
+ // angle closest to 180 degrees
+ vertex.smooth = false;
+
+ special = true;
+ }
+
+ if ( special ) {
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_1ST_IS_INVISIBLE
+ cells_it->vertices.push_back(vertex.invisible());
+#else
+ cells_it->vertices.push_back(vertex);
+#endif
+ {
+ Point<T> another = vertex;
+ T amount = 0.1875;
+ transform(another,
+ - ( topleft(b_it) - topright(a_it) ) * amount,
+ // y
+ - ( 0.75
+ - ( topleft(b_it) + topright(a_it) )
+ * amount ));
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_2ND_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.0625;
+ transform(another,
+ - ( topleft(b_it) - topright(a_it) ) * amount,
+ // y
+ - ( 0.25
+ - ( topleft(b_it) + topright(a_it) )
+ * amount ));
+ another.smooth = true;
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_3RD_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.0625;
+ transform(another, - amount
+ * ( bottomleft(d_it) - bottomright(c_it) ),
+ // y
+ 0.25 - amount
+ * ( bottomleft(d_it) + bottomright(c_it) ));
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_4TH_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ transform(vertex,
+ - ( topleft(b_it) + bottomleft(d_it)
+ - topright(a_it) - bottomright(c_it) )
+ * 0.03125,
+ // y
+ ( topleft(b_it) - bottomleft(d_it)
+ + topright(a_it) - bottomright(c_it) )
+ * 0.03125);
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_5TH_IS_INVISIBLE
+ vertex.visible = false;
+#endif
+ }
+ }
+ } else if ( right(c_it) && adjust_splines ) {
+ // bottom and bottom-right are connected
+
+ bool special = false;
+
+ bool foreign_is_contour = contour_edge(b_it->rgba, d_it->rgba);
+
+ // the neighbor similar in 90° feature
+ bool similar_neighbor_is_contour
+ = contour_edge(a_it->rgba, b_it->rgba);
+
+ if ( contour_edge(a_it->rgba, c_it->rgba)
+ + similar_neighbor_is_contour
+ + foreign_is_contour == 2 ) {
+ vertex.smooth = !foreign_is_contour;
+
+ if ( !vertex.smooth ) {
+ if ( similar_neighbor_is_contour ) {
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_1ST_IS_INVISIBLE
+ cells_it->vertices.push_back(vertex.invisible());
+#else
+ cells_it->vertices.push_back(vertex);
+#endif
+ {
+ Point<T> another = vertex;
+ T amount = 0.1875 * topleft(b_it);
+ transform(another, - amount, - ( 0.75 - amount ));
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_2ND_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.0625 * topleft(b_it);
+ transform(another, - amount, - ( 0.25 - amount ));
+ another.smooth = true;
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_3RD_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.0625 * bottomright(b_it);
+ transform(another, 0.25 - amount, amount);
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_4TH_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ T amount = 0.125
+ - 0.03125 * (topleft(b_it) + bottomright(b_it));
+ transform(vertex, amount, - amount);
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_5TH_IS_INVISIBLE
+ vertex.visible = false;
+#endif
+ }
+ } else {
+ special = true;
+ }
+ }
+ } else {
+ // {bottom, bottom-right} is the pair with the
+ // angle closest to 180 degrees
+ vertex.smooth = false;
+
+ special = true;
+ }
+
+ if ( special ) {
+ {
+ Point<T> another = vertex;
+ T amount = 0.03125;
+ transform(another,
+ amount
+ * ( topleft(c_it) - topright(d_it)
+ + bottomleft(a_it) - bottomright(b_it) ),
+ // y
+ - amount
+ * ( topleft(c_it) + topright(d_it)
+ - bottomleft(a_it) - bottomright(b_it) ));
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_1ST_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.0625;
+ transform(another,
+ 0.25 - amount
+ * ( topright(d_it) + bottomright(b_it) ),
+ // y
+ - amount
+ * ( topright(d_it) - bottomright(b_it) ));
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_2ND_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.0625;
+ transform(another,
+ - ( 0.25 - amount
+ * ( topleft(c_it) + bottomleft(a_it) ) ),
+ // y
+ - amount
+ * ( topleft(c_it) - bottomleft(a_it) ));
+ another.smooth = true;
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_3RD_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+ {
+ Point<T> another = vertex;
+ T amount = 0.1875;
+ transform(another,
+ - ( 0.75 - amount
+ * ( topleft(c_it) + bottomleft(a_it) ) ),
+ // y
+ - amount
+ * ( topleft(c_it) - bottomleft(a_it) ));
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_4TH_IS_INVISIBLE
+ cells_it->vertices.push_back(another.invisible());
+#else
+ cells_it->vertices.push_back(another);
+#endif
+ }
+#ifdef LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES_5TH_IS_INVISIBLE
+ vertex.visible = false;
+#endif
+ }
+ } else {
+ // there is a 4-color pattern, where the current node
+ // won't be smooth
+ vertex.smooth = false;
+ }
+
+ cells_it->vertices.push_back(vertex);
+ }
+}
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_SIMPLIFIEDVORONOI_H
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/3rdparty/libdepixelize/priv/splines-kopf2011.h b/src/3rdparty/libdepixelize/priv/splines-kopf2011.h
new file mode 100644
index 0000000..c3da58c
--- /dev/null
+++ b/src/3rdparty/libdepixelize/priv/splines-kopf2011.h
@@ -0,0 +1,167 @@
+/* This file is part of the libdepixelize project
+ Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+ GNU Lesser General Public License Usage
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by the
+ Free Software Foundation; either version 2.1 of the License, or (at your
+ option) any later version.
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library. If not, see <http://www.gnu.org/licenses/>.
+
+ GNU General Public License Usage
+ Alternatively, this library may be used under the terms of the GNU General
+ Public License as published by the Free Software Foundation, either version
+ 2 of the License, or (at your option) any later version.
+ You should have received a copy of the GNU General Public License along with
+ this library. If not, see <http://www.gnu.org/licenses/>.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_SPLINES_KOPF2011_H
+#define LIBDEPIXELIZE_TRACER_SPLINES_KOPF2011_H
+
+#include "../splines.h"
+#include "homogeneoussplines.h"
+#include "optimization-kopf2011.h"
+
+namespace Tracer {
+
+/**
+ * Maybe the pass-by-value and then move idiom should be more efficient. But all
+ * this is inlinable and we're not even in C++11 yet.
+ */
+template<class T>
+Geom::Path worker_helper(const std::vector< Point<T> > &source1, bool optimize)
+{
+ typedef Geom::LineSegment Line;
+ typedef Geom::QuadraticBezier Quad;
+ typedef typename std::vector< Point<T> >::const_iterator iterator;
+
+ std::vector< Point<T> > source;
+
+ if ( optimize )
+ source = Tracer::optimize(source1);
+ else
+ source = source1;
+
+ iterator it = source.begin();
+ Point<T> prev = source.back();
+ Geom::Path ret(to_geom_point(midpoint(prev, *it)));
+
+ for ( iterator end = source.end() ; it != end ; ++it ) {
+#if LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES
+ // remove redundant points
+ if ( !it->visible ) {
+ prev = *it;
+ continue;
+ }
+#endif // LIBDEPIXELIZE_ENABLE_EXPERIMENTAL_FEATURES
+
+ if ( !prev.visible ) {
+ Geom::Point middle = to_geom_point(midpoint(prev, *it));
+ if ( ret.finalPoint() != middle ) {
+ // All generated invisible points are straight lines
+ ret.appendNew<Line>(middle);
+ }
+ }
+
+ Point<T> next = (it + 1 == end) ? source.front() : *(it + 1);
+ Point<T> middle = midpoint(*it, next);
+
+ if ( !it->smooth ) {
+ ret.appendNew<Line>(to_geom_point(*it));
+ ret.appendNew<Line>(to_geom_point(middle));
+ } else {
+ ret.appendNew<Quad>(to_geom_point(*it), to_geom_point(middle));
+ }
+
+ prev = *it;
+ }
+
+ return ret;
+}
+
+/**
+ * It should be used by worker threads. Convert only one object.
+ */
+template<class T>
+void worker(const typename HomogeneousSplines<T>::Polygon &source,
+ Splines::Path &dest, bool optimize)
+{
+ //dest.pathVector.reserve(source.holes.size() + 1);
+
+ for ( int i = 0 ; i != 4 ; ++i )
+ dest.rgba[i] = source.rgba[i];
+
+ dest.pathVector.push_back(worker_helper(source.vertices, optimize));
+
+ for ( typename std::vector< std::vector< Point<T> > >::const_iterator
+ it = source.holes.begin(), end = source.holes.end()
+ ; it != end ; ++it ) {
+ dest.pathVector.push_back(worker_helper(*it, optimize));
+ }
+}
+
+template<typename T, bool adjust_splines>
+Splines::Splines(const SimplifiedVoronoi<T, adjust_splines> &diagram) :
+ _width(diagram.width()),
+ _height(diagram.height())
+{
+ _paths.reserve(diagram.size());
+
+ for ( typename SimplifiedVoronoi<T, adjust_splines>::const_iterator
+ it = diagram.begin() , end = diagram.end() ; it != end ; ++it ) {
+ Path path;
+
+ path.pathVector
+ .push_back(Geom::Path(to_geom_point(it->vertices.front())));
+
+ for ( typename std::vector< Point<T> >::const_iterator
+ it2 = ++it->vertices.begin(), end2 = it->vertices.end()
+ ; it2 != end2 ; ++it2 ) {
+ path.pathVector.back()
+ .appendNew<Geom::LineSegment>(Geom::Point(it2->x, it2->y));
+ }
+
+ for ( int i = 0 ; i != 4 ; ++i )
+ path.rgba[i] = it->rgba[i];
+
+ _paths.push_back(path);
+ }
+}
+
+template<class T>
+Splines::Splines(const HomogeneousSplines<T> &homogeneousSplines,
+ bool optimize, int /*nthreads*/) :
+ _paths(homogeneousSplines.size()),
+ _width(homogeneousSplines.width()),
+ _height(homogeneousSplines.height())
+{
+ // TODO: It should be threaded
+ iterator paths_it = begin();
+ for ( typename HomogeneousSplines<T>::const_iterator
+ it = homogeneousSplines.begin(), end = homogeneousSplines.end()
+ ; it != end ; ++it, ++paths_it ) {
+ worker<T>(*it, *paths_it, optimize);
+ }
+}
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_SPLINES_KOPF2011_H
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/3rdparty/libdepixelize/splines.h b/src/3rdparty/libdepixelize/splines.h
new file mode 100644
index 0000000..b06ba8b
--- /dev/null
+++ b/src/3rdparty/libdepixelize/splines.h
@@ -0,0 +1,120 @@
+/* This file is part of the libdepixelize project
+ Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
+
+ GNU Lesser General Public License Usage
+ This library is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by the
+ Free Software Foundation; either version 2.1 of the License, or (at your
+ option) any later version.
+ You should have received a copy of the GNU Lesser General Public License
+ along with this library. If not, see <http://www.gnu.org/licenses/>.
+
+ GNU General Public License Usage
+ Alternatively, this library may be used under the terms of the GNU General
+ Public License as published by the Free Software Foundation, either version
+ 2 of the License, or (at your option) any later version.
+ You should have received a copy of the GNU General Public License along with
+ this library. If not, see <http://www.gnu.org/licenses/>.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+*/
+
+#ifndef LIBDEPIXELIZE_TRACER_SPLINES_H
+#define LIBDEPIXELIZE_TRACER_SPLINES_H
+
+#include <2geom/pathvector.h>
+#include <glib.h>
+
+namespace Tracer {
+
+template<typename T, bool adjust_splines = true>
+class SimplifiedVoronoi;
+
+template<typename T>
+class HomogeneousSplines;
+
+class Splines
+{
+public:
+ struct Path
+ {
+ /**
+ * It may be benefited from C++11 move references.
+ */
+ Geom::PathVector pathVector;
+
+ guint8 rgba[4];
+ };
+
+ typedef std::vector<Path>::iterator iterator;
+ typedef std::vector<Path>::const_iterator const_iterator;
+
+ Splines() /* = default */ {}
+
+ template<typename T, bool adjust_splines>
+ Splines(const SimplifiedVoronoi<T, adjust_splines> &simplifiedVoronoi);
+
+ /**
+ * There are two levels of optimization. The first level only removes
+ * redundant points of colinear points. The second level uses the
+ * Kopf-Lischinski optimization. The first level is always enabled.
+ * The second level is enabled using \p optimize.
+ */
+ template<typename T>
+ Splines(const HomogeneousSplines<T> &homogeneousSplines, bool optimize,
+ int nthreads);
+
+ // Iterators
+ iterator begin()
+ {
+ return _paths.begin();
+ }
+
+ const_iterator begin() const
+ {
+ return _paths.begin();
+ }
+
+ iterator end()
+ {
+ return _paths.end();
+ }
+
+ const_iterator end() const
+ {
+ return _paths.end();
+ }
+
+ int width() const
+ {
+ return _width;
+ }
+
+ int height() const
+ {
+ return _height;
+ }
+
+private:
+ std::vector<Path> _paths;
+ int _width;
+ int _height;
+};
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_SPLINES_H
+
+/*
+ Local Variables:
+ mode:c++
+ c-file-style:"stroustrup"
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+ indent-tabs-mode:nil
+ fill-column:99
+ End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :