diff options
Diffstat (limited to 'src/3rdparty/libdepixelize')
| -rw-r--r-- | src/3rdparty/libdepixelize/CMakeLists.txt | 24 | ||||
| -rw-r--r-- | src/3rdparty/libdepixelize/README | 7 | ||||
| -rw-r--r-- | src/3rdparty/libdepixelize/kopftracer2011.cpp | 665 | ||||
| -rw-r--r-- | src/3rdparty/libdepixelize/kopftracer2011.h | 150 | ||||
| -rw-r--r-- | src/3rdparty/libdepixelize/priv/branchless.h | 58 | ||||
| -rw-r--r-- | src/3rdparty/libdepixelize/priv/colorspace.h | 111 | ||||
| -rw-r--r-- | src/3rdparty/libdepixelize/priv/curvature.h | 115 | ||||
| -rw-r--r-- | src/3rdparty/libdepixelize/priv/homogeneoussplines.h | 472 | ||||
| -rw-r--r-- | src/3rdparty/libdepixelize/priv/integral.h | 61 | ||||
| -rw-r--r-- | src/3rdparty/libdepixelize/priv/iterator.h | 123 | ||||
| -rw-r--r-- | src/3rdparty/libdepixelize/priv/optimization-kopf2011.h | 263 | ||||
| -rw-r--r-- | src/3rdparty/libdepixelize/priv/pixelgraph.h | 555 | ||||
| -rw-r--r-- | src/3rdparty/libdepixelize/priv/point.h | 112 | ||||
| -rw-r--r-- | src/3rdparty/libdepixelize/priv/simplifiedvoronoi.h | 1707 | ||||
| -rw-r--r-- | src/3rdparty/libdepixelize/priv/splines-kopf2011.h | 167 | ||||
| -rw-r--r-- | src/3rdparty/libdepixelize/splines.h | 120 |
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 : |