From dd18c27c36c9138bc68161ad365bfc61b8d135f8 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Vin=C3=ADcius=20dos=20Santos=20Oliveira?= Date: Thu, 12 Sep 2013 07:23:11 -0300 Subject: Integrating with libdepixelize (bzr r12506.1.1) --- src/libdepixelize/CMakeLists.txt | 11 + src/libdepixelize/Makefile_insert | 11 + src/libdepixelize/kopftracer2011.cpp | 433 +++++++++ src/libdepixelize/kopftracer2011.h | 123 +++ src/libdepixelize/makefile.in | 17 + src/libdepixelize/priv/branchless.h | 76 ++ src/libdepixelize/priv/colorspace.h | 111 +++ src/libdepixelize/priv/homogeneoussplines.h | 467 ++++++++++ src/libdepixelize/priv/pixelgraph.h | 491 ++++++++++ src/libdepixelize/priv/point.h | 77 ++ src/libdepixelize/priv/simplifiedvoronoi.h | 1325 +++++++++++++++++++++++++++ src/libdepixelize/priv/splines.h | 155 ++++ src/libdepixelize/priv/utils.h | 87 ++ src/libdepixelize/splines.h | 120 +++ 14 files changed, 3504 insertions(+) create mode 100644 src/libdepixelize/CMakeLists.txt create mode 100644 src/libdepixelize/Makefile_insert create mode 100644 src/libdepixelize/kopftracer2011.cpp create mode 100644 src/libdepixelize/kopftracer2011.h create mode 100644 src/libdepixelize/makefile.in create mode 100644 src/libdepixelize/priv/branchless.h create mode 100644 src/libdepixelize/priv/colorspace.h create mode 100644 src/libdepixelize/priv/homogeneoussplines.h create mode 100644 src/libdepixelize/priv/pixelgraph.h create mode 100644 src/libdepixelize/priv/point.h create mode 100644 src/libdepixelize/priv/simplifiedvoronoi.h create mode 100644 src/libdepixelize/priv/splines.h create mode 100644 src/libdepixelize/priv/utils.h create mode 100644 src/libdepixelize/splines.h (limited to 'src/libdepixelize') diff --git a/src/libdepixelize/CMakeLists.txt b/src/libdepixelize/CMakeLists.txt new file mode 100644 index 000000000..64a72f9d9 --- /dev/null +++ b/src/libdepixelize/CMakeLists.txt @@ -0,0 +1,11 @@ + +set(libdepixelize_SRC + kopftracer2011.cpp + + # ------- + # Headers + kopftracer2011.h + splines.h +) + +add_inkscape_lib(depixelize_LIB "${libdepixelize_SRC}") diff --git a/src/libdepixelize/Makefile_insert b/src/libdepixelize/Makefile_insert new file mode 100644 index 000000000..75b19bf5c --- /dev/null +++ b/src/libdepixelize/Makefile_insert @@ -0,0 +1,11 @@ +## Makefile.am fragment sourced by src/Makefile.am. + +libdepixelize/all: libdepixelize/libdepixelize.a + +libdepixelize/clean: + rm -f libdepixelize/libdepixelize.a $(libdepixelize_libdepixelize_a_OBJECTS) + +libdepixelize_libdepixelize_a_SOURCES = \ + libdepixelize/kopftracer2011.cpp \ + libdepixelize/kopftracer2011.h \ + libdepixelize/splines.h diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp new file mode 100644 index 000000000..96a415f2c --- /dev/null +++ b/src/libdepixelize/kopftracer2011.cpp @@ -0,0 +1,433 @@ +/* This file is part of the libdepixelize project + Copyright (C) 2013 Vinícius dos Santos Oliveira + + 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 . + + 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 . + + 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 +#endif + +// Build fix under Inkscape build tree +#if GLIBMM_DISABLE_DEPRECATED && HAVE_GLIBMM_THREADS_H +#include +#endif + +#include +#include +#include "kopftracer2011.h" +#include "priv/colorspace.h" +#include "priv/homogeneoussplines.h" +#include "priv/branchless.h" +#include "priv/splines.h" + +namespace Tracer { +namespace Heuristics { + +int curves(PixelGraph &graph, PixelGraph::Node *a, PixelGraph::Node *b); +bool islands(PixelGraph &graph, PixelGraph::Node *a, PixelGraph::Node *b); + +struct SparsePixels +{ + typedef std::pair Edge; + typedef std::pair EdgeWeight; + + void operator()(PixelGraph &graph, unsigned radius); + + static bool similar_colors(PixelGraph::Node *n, Edge edge); + + 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 &buf, + const Options &options) +{ + return Splines(_voronoi(buf, options)); +} + +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 &buf, + const Options &options) +{ + HomogeneousSplines splines(_voronoi(buf, options)); + return Splines(splines, options.optimize, options.nthreads); +} + +template +SimplifiedVoronoi Kopf2011::_voronoi(const Glib::RefPtr &buf, + const Options &options) +{ + PixelGraph graph(buf); + + /*if ( !graph.width() || !graph.height() ) + return;*/ + +#ifndef NDEBUG + graph.checkConsistency(); +#endif + + // This step could be part of the initialization of PixelGraph + // and decrease the necessary number of passes + graph.connectAllNeighbors(); + +#ifndef NDEBUG + graph.checkConsistency(); +#endif + + // 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); + +#ifndef NDEBUG + graph.checkConsistency(); +#endif + + // This and below steps must be executed in separate. + // Otherwise, there will be colateral effects due to misassumption about the + // data being read. + _remove_crossing_edges_safe(graph); + +#ifndef NDEBUG + graph.checkConsistency(); +#endif + + _remove_crossing_edges_unsafe(graph, options); + +#ifndef NDEBUG + graph.checkConsistency(); +#endif + + return SimplifiedVoronoi(graph); +} + +// 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. + * + * \TODO: It should remember/cache who are the unsafe crossing edges? + */ +inline void Kopf2011::_remove_crossing_edges_safe(PixelGraph &graph) +{ + if ( graph.width() < 2 || graph.height() < 2 ) + return; + + PixelGraph::iterator it = graph.begin(); + for ( int i = 0 ; i != graph.height() - 1 ; ++i, ++it ) { + for ( int j = 0 ; j != graph.width() - 1 ; ++j, ++it ) { + // this <-> right + if ( !it->adj.right ) + continue; + + // this <-> down + if ( !it->adj.bottom ) + continue; + + PixelGraph::iterator down_right = it + graph.width() + 1; + + // down_right <-> right + if ( !down_right->adj.top ) + continue; + + // down_right <-> down + if ( !down_right->adj.left ) + continue; + + // main diagonal + // this <-> down_right + it->adj.bottomright = 0; + down_right->adj.topleft = 0; + + // secondary diagonal + // right <-> down + (it + 1)->adj.bottomleft = 0; + (it + graph.width())->adj.topright = 0; + } + } +} + +/** + * This method removes crossing edges using the heuristics. + */ +inline +void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, + const Options &options) +{ + if ( graph.width() < 2 || graph.height() < 2 ) + return; + + // Iterate over the graph, 2x2 blocks at time + PixelGraph::iterator it = graph.begin(); + for (int i = 0 ; i != graph.height() - 1 ; ++i, ++it ) { + for ( int j = 0 ; j != graph.width() - 1 ; ++j, ++it ) { + using std::pair; + using std::make_pair; + + typedef pair Edge; + typedef pair EdgeWeight; + + EdgeWeight diagonals[2] = { + make_pair(make_pair(&*it, &*(it + graph.width() + 1)), 0), + make_pair(make_pair(&*(it + 1), &*(it + graph.width())), 0) + }; + + // Check if there are crossing edges + if ( !diagonals[0].first.first->adj.bottomright + || !diagonals[1].first.first->adj.bottomleft ) { + continue; + } + + // Compute weights + for ( int i = 0 ; i != 2 ; ++i ) { + // Curves and islands heuristics + PixelGraph::Node *a = diagonals[i].first.first; + PixelGraph::Node *b = diagonals[i].first.second; + + diagonals[i].second += Heuristics::curves(graph, a, b) + * options.curvesMultiplier; + + diagonals[i].second += Heuristics::islands(graph, a, b) + * options.islandsWeight; + } + + { + // Sparse pixels heuristic + Heuristics::SparsePixels sparse_pixels; + + for ( int i = 0 ; i != 2 ; ++i ) + sparse_pixels.diagonals[i] = diagonals[i]; + + sparse_pixels(graph, options.sparsePixelsRadius); + + for ( int i = 0 ; i != 2 ; ++i ) { + diagonals[i].second += sparse_pixels.diagonals[i].second + * options.sparsePixelsMultiplier; + } + } + + // Remove edges with lower weight + if ( diagonals[0].second > diagonals[1].second ) { + diagonals[1].first.first->adj.bottomleft = 0; + diagonals[1].first.second->adj.topright = 0; + } else if ( diagonals[0].second < diagonals[1].second ) { + diagonals[0].first.first->adj.bottomright = 0; + diagonals[0].first.second->adj.topleft = 0; + } else { + diagonals[0].first.first->adj.bottomright = 0; + diagonals[0].first.second->adj.topleft = 0; + diagonals[1].first.first->adj.bottomleft = 0; + diagonals[1].first.second->adj.topright = 0; + } + } + } +} + +inline int Heuristics::curves(PixelGraph &graph, PixelGraph::Node *a, + PixelGraph::Node *b) +{ + int count = 1; + + // b -> a + // and then a -> b + for ( int i = 0 ; i != 2 ; ++i ) { + PixelGraph::Node *it = i ? a : b; + PixelGraph::Node *prev = i ? b : a; + int local_count = 0; + + // Used to avoid inifinite loops in circular-like edges + PixelGraph::Node *const 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 = guintptr(it); + aux = it->adj.top * guintptr(it - graph.width()) + + it->adj.topright * guintptr(it - graph.width() + 1) + + it->adj.right * guintptr(it + 1) + + it->adj.bottomright * guintptr(it + graph.width() + 1) + + it->adj.bottom * guintptr(it + graph.width()) + + it->adj.bottomleft * guintptr(it + graph.width() - 1) + + it->adj.left * guintptr(it - 1) + + it->adj.topleft * guintptr(it - graph.width() - 1) + - guintptr(prev); + prev = it; + it = reinterpret_cast(aux); + } + + // Break infinite loops + if ( it == initial ) + return local_count; + } + count += local_count; + } + + return count; +} + +inline void Heuristics::SparsePixels::operator ()(PixelGraph &graph, + unsigned radius) +{ + if ( !graph.width() || !graph.height() ) + return; + + // Clear weights + for ( int i = 0 ; i != 2 ; ++i ) + diagonals[i].second = 0; + + // Compute begin and end nodes under a (2*radius)^2 window + std::pair begin(0, 0); + + // Get midpoint + { + using branchless::max_consecutive; + + unsigned x1 = graph.toX(diagonals[0].first.first); + unsigned x2 = graph.toX(diagonals[0].first.second); + begin.first = max_consecutive(x1, x2); + + unsigned y1 = graph.toY(diagonals[0].first.first); + unsigned y2 = graph.toY(diagonals[0].first.second); + begin.second = max_consecutive(y1, y2); + } + + std::pair end(begin.first + radius, + begin.second + radius); + + // Get beginning point + { + using branchless::first_if; + + begin.first = first_if(begin.first - radius, 0u, begin.first >= radius); + + begin.second = first_if(begin.second - radius, 0u, + begin.second >= radius); + } + + // Fix ending point if misplaced + { + using branchless::first_if; + + end.first = first_if(unsigned(graph.width()), end.first, + end.first > graph.width()); + + end.second = first_if(unsigned(graph.height()), end.second, + end.second > graph.height()); + } + + // Iterate over nodes and count them + for ( int i = begin.second ; i != end.second ; ++i ) { + PixelGraph::Node *it = &graph[begin.first][i]; + for ( int j = begin.first ; j != end.first ; ++j, ++it ) { + for ( int k = 0 ; k != 2 ; ++k ) + diagonals[k].second += similar_colors(it, diagonals[k].first); + } + } + + int minor = branchless::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::Node *n, + Heuristics::SparsePixels::Edge edge) +{ + using colorspace::similar_colors; + return (similar_colors(n->rgba, edge.first->rgba) + || similar_colors(n->rgba, edge.second->rgba)); +} + +inline bool Heuristics::islands(PixelGraph &graph, PixelGraph::Node *a, + PixelGraph::Node *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:encoding=utf-8:textwidth=99 : diff --git a/src/libdepixelize/kopftracer2011.h b/src/libdepixelize/kopftracer2011.h new file mode 100644 index 000000000..73f3b7274 --- /dev/null +++ b/src/libdepixelize/kopftracer2011.h @@ -0,0 +1,123 @@ +/* This file is part of the libdepixelize project + Copyright (C) 2013 Vinícius dos Santos Oliveira + + 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 . + + 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 . + + 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 + +// Contains exception definitions +#include +#include +#include "splines.h" + +namespace Tracer { + +class PixelGraph; +template class SimplifiedVoronoi; +template class HomogeneousSplines; + +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 + * + * Glib::FileError + * Gdk::PixbufError + */ + static Splines to_voronoi(const std::string &filename, + const Options &options = Options()); + + static Splines to_voronoi(const Glib::RefPtr &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 &buf, + const Options &options = Options()); + +private: + typedef double Precision; + + template + static SimplifiedVoronoi _voronoi(const Glib::RefPtr &buf, + const Options &options); + + static void _disconnect_neighbors_with_dissimilar_colors(PixelGraph &graph); + static void _remove_crossing_edges_safe(PixelGraph &graph); + static void _remove_crossing_edges_unsafe(PixelGraph &graph, + 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/libdepixelize/makefile.in b/src/libdepixelize/makefile.in new file mode 100644 index 000000000..51d020db1 --- /dev/null +++ b/src/libdepixelize/makefile.in @@ -0,0 +1,17 @@ +# Convenience stub makefile to call the real Makefile. + +@SET_MAKE@ + +OBJEXT = @OBJEXT@ + +# Explicit so that it's the default rule. +all: + cd .. && $(MAKE) libdepixelize/all + +clean %.a %.$(OBJEXT): + cd .. && $(MAKE) libdepixelize/$@ + +.PHONY: all clean + +.SUFFIXES: +.SUFFIXES: .a .$(OBJEXT) diff --git a/src/libdepixelize/priv/branchless.h b/src/libdepixelize/priv/branchless.h new file mode 100644 index 000000000..f8f041cce --- /dev/null +++ b/src/libdepixelize/priv/branchless.h @@ -0,0 +1,76 @@ +/* This file is part of the libdepixelize project + Copyright (C) 2013 Vinícius dos Santos Oliveira + + 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 . + + 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 . + + 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 { + +template +T first_if(T first, T second, bool cond) +{ + return first * cond + second * (1 - cond); +} + +template +T min(T first, T second) +{ + return first - (first > second) * (first - second); +} + +template +T max(T first, T second) +{ + return first + (first < second) * (second - first); +} + +/** + * When abs(first - second) == 1 + */ +template +T max_consecutive(T first, T second) +{ + return first + (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/libdepixelize/priv/colorspace.h b/src/libdepixelize/priv/colorspace.h new file mode 100644 index 000000000..21025b852 --- /dev/null +++ b/src/libdepixelize/priv/colorspace.h @@ -0,0 +1,111 @@ +/* This file is part of the libdepixelize project + Copyright (C) 2013 Vinícius dos Santos Oliveira + + 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 . + + 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 . + + 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 + +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/libdepixelize/priv/homogeneoussplines.h b/src/libdepixelize/priv/homogeneoussplines.h new file mode 100644 index 000000000..d6860cdf4 --- /dev/null +++ b/src/libdepixelize/priv/homogeneoussplines.h @@ -0,0 +1,467 @@ +/* This file is part of the libdepixelize project + Copyright (C) 2013 Vinícius dos Santos Oliveira + + 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 . + + 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 . + + 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 +#include + +namespace Tracer { + +template +class HomogeneousSplines +{ +public: + struct Polygon + { + Polygon() {} + Polygon(const guint8 (&rgba)[4]) + { + for ( int i = 0 ; i != 4 ; ++i ) + this->rgba[i] = rgba[i]; + } + + std::vector< Point > vertices; + + /** + * It may be benefited from C++11 move references. + */ + std::vector< std::vector< Point > > holes; + + guint8 rgba[4]; + }; + + typedef typename std::vector::iterator iterator; + typedef typename std::vector::const_iterator const_iterator; + typedef typename std::vector::size_type size_type; + + HomogeneousSplines(const SimplifiedVoronoi &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(); + } + + // Capacity + + size_type size() const + { + return _polygons.size(); + } + + int width() const + { + return _width; + } + + int height() const + { + return _height; + } + +private: + typedef typename SimplifiedVoronoi::Cell Cell; + typedef std::vector< Point > Points; + + typedef typename SimplifiedVoronoi::iterator voronoi_iter; + typedef typename SimplifiedVoronoi::const_iterator voronoi_citer; + + 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_range; + typedef std::pair 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 &holes, points_iter region_begin, + points_iter region_end); + + std::vector _polygons; + int _width; + int _height; +}; + +template +HomogeneousSplines::HomogeneousSplines(const SimplifiedVoronoi &voronoi) : + _width(voronoi.width()), + _height(voronoi.height()) +{ + //if (!voronoi.size()) + // return; + using colorspace::same_color; + + // 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::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 +typename HomogeneousSplines::CommonEdge +HomogeneousSplines::_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 +typename HomogeneousSplines::SelfCommonEdge +HomogeneousSplines::_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 +void HomogeneousSplines::_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 +void HomogeneousSplines::_fill_holes(std::vector &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::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/libdepixelize/priv/pixelgraph.h b/src/libdepixelize/priv/pixelgraph.h new file mode 100644 index 000000000..0ae4f36b4 --- /dev/null +++ b/src/libdepixelize/priv/pixelgraph.h @@ -0,0 +1,491 @@ +/* This file is part of the libdepixelize project + Copyright (C) 2013 Vinícius dos Santos Oliveira + + 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 . + + 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 . + + 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 +#include +#include + +namespace Tracer { + +class PixelGraph +{ +public: + class Node + { + public: + /* + * Hamming weight of \p adj + */ + unsigned adjsize() + { + 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::iterator iterator; + typedef std::vector::const_iterator const_iterator; + typedef std::vector::reverse_iterator reverse_iterator; + typedef std::vector::const_reverse_iterator const_reverse_iterator; + + class ColumnView + { + public: + ColumnView(std::vector &nodes, int width, int column) : + _nodes(nodes), _width(width), _column(column) + {} + + Node &operator[](int line); + + private: + std::vector &_nodes; + const int _width; + const int _column; + }; + + PixelGraph(Glib::RefPtr 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(); + } + + // Capacity + size_t size() const + { + return _nodes.size(); + } + + int width() const + { + return _width; + } + + int height() const + { + return _height; + } + + // Algorithms + void connectAllNeighbors(); + + int toX(Node *n) const + { + return (n - &_nodes[0]) % _width; + } + + int toY(Node *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 _nodes; +}; + +inline PixelGraph::PixelGraph(Glib::RefPtr 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 *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 poiting 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]; + 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; + } + } + + // ...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] + 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); + } + } + + // ...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]; + top_left->adj.right = 1; + top_left->adj.bottomright = 1; + top_left->adj.bottom = 1; + } + if ( _width > 1 ) { + Node *const top_right = &(*this)[_width - 1][0]; + 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; + 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; + } +} + +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/libdepixelize/priv/point.h b/src/libdepixelize/priv/point.h new file mode 100644 index 000000000..037c03de6 --- /dev/null +++ b/src/libdepixelize/priv/point.h @@ -0,0 +1,77 @@ +/* This file is part of the libdepixelize project + Copyright (C) 2013 Vinícius dos Santos Oliveira + + 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 . + + 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 . + + 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 + +#include + +namespace Tracer { + +template +struct Point +{ + Point() {} + Point(T x, T y) : x(x), y(y) {} + Point(T x, T y, bool smooth) : smooth(smooth), 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); + } + + bool smooth; + + T x, y; +}; + +template +inline bool operator==(const Point &lhs, const Point &rhs) +{ + return +#ifndef LIBDEPIXELIZE_IS_VERY_WELL_TESTED + lhs.smooth == rhs.smooth && +#endif // LIBDEPIXELIZE_IS_VERY_WELL_TESTED + lhs.x == rhs.x && lhs.y == rhs.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/libdepixelize/priv/simplifiedvoronoi.h b/src/libdepixelize/priv/simplifiedvoronoi.h new file mode 100644 index 000000000..7c4a6d9fb --- /dev/null +++ b/src/libdepixelize/priv/simplifiedvoronoi.h @@ -0,0 +1,1325 @@ +/* This file is part of the libdepixelize project + Copyright (C) 2013 Vinícius dos Santos Oliveira + + 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 . + + 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 . + + 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 +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 > vertices; + guint8 rgba[4]; + }; + + typedef typename std::vector::iterator iterator; + typedef typename std::vector::const_iterator const_iterator; + typedef typename std::vector::reverse_iterator reverse_iterator; + + typedef typename std::vector::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(); + } + + // Capacity + size_t size() const + { + return _cells.size(); + } + + int width() const + { + return _width; + } + + int height() const + { + return _height; + } + +private: + typedef void (*PointTransform)(Point &p, T dx, T dy); + typedef bool (*NodeTransform)(PixelGraph::const_iterator); + + static Point _midpoint(const Point &p1, const Point p2) + { + return Point((p1.x + p2.x) / 2, (p1.y + p2.y) / 2); + } + + /** + * Output is translated by -.5 in each axis. This function fixes this error. + */ + static Point _adjust(Point p) + { + return Point(p.x + .5, p.y + .5); + } + + /** + * Output is translated by -.5 in each axis. This function fixes this error. + */ + static Point _adjust(Point p, bool smooth) + { + return Point(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 &p, T dx, T dy); + static void _complexTopRightTransform(Point &p, T dx, T dy); + static void _complexBottomRightTransform(Point &p, T dx, T dy); + static void _complexBottomLeftTransform(Point &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 + * abstracation. + * + * "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 + */ + 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 _cells; +}; + +template +SimplifiedVoronoi::SimplifiedVoronoi(const PixelGraph &graph) : + _width(graph.width()), + _height(graph.height()), + _cells(graph.size()) +{ + if (!graph.size()) + return; + + // ...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 poiting 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; + + 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(i, 0, false)); + + // Top-right + cells_it->vertices.push_back(Point(i + 1, 0, false)); + + // Bottom-right + _complexBottomRight(graph, graph_it, cells_it, i, 0); + + // Bottom-left + _complexBottomLeft(graph, graph_it, cells_it, i, 0); + } + } + + // ...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(i + 1, _height, false)); + + // Bottom-left + cells_it->vertices.push_back(Point(i, _height, false)); + } + } + + // ...then the "left" cells... + if ( _height > 2 ) { + PixelGraph::const_iterator graph_it = graph.begin() + _width; + Cell *cells_it = &_cells.front() + _width; + + 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(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(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(_width, i, false)); + + // Bottom-right + cells_it->vertices.push_back(Point(_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(0, 0, false)); + + // Top-right + cells_it->vertices.push_back(Point(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(1, 1, false)); + + // Bottom-left + cells_it->vertices.push_back(Point(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(_width - 1, 0, false)); + + // Top-right + cells_it->vertices.push_back(Point(_width, 0, false)); + + // Bottom-right + cells_it->vertices.push_back(Point(_width, 1, false)); + + // Bottom-left + if ( _height > 1 ) + _complexBottomLeft(graph, graph_it, cells_it, _width - 1, 0); + else + cells_it->vertices.push_back(Point(_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(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(1, _height - 1, false)); + + // Bottom-right + cells_it->vertices.push_back(Point(1, _height, false)); + + // Bottom-left + cells_it->vertices.push_back(Point(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(_width, _height - 1, false)); + + // Bottom-right + cells_it->vertices.push_back(Point(_width, _height, false)); + + // Bottom-left + cells_it->vertices.push_back(Point(_width - 1, _height, false)); + } +} + +template void +SimplifiedVoronoi::_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 void +SimplifiedVoronoi::_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 void +SimplifiedVoronoi::_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 void +SimplifiedVoronoi::_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 void +SimplifiedVoronoi::_complexTopLeftTransform(Point &p, T dx, T dy) +{ + p.x -= dx; + p.y -= dy; +} + +template void +SimplifiedVoronoi::_complexTopRightTransform(Point &p, T dx, T dy) +{ + p.x += dy; + p.y -= dx; +} + +template void +SimplifiedVoronoi::_complexBottomRightTransform(Point &p, T dx, T dy) +{ + p.x += dx; + p.y += dy; +} + +template void +SimplifiedVoronoi::_complexBottomLeftTransform(Point &p, T dx, T dy) +{ + p.x -= dy; + p.y += dx; +} + +template +bool SimplifiedVoronoi::_complexTopLeftTransformTop(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.bottom; +} + +template +bool SimplifiedVoronoi::_complexTopLeftTransformTopRight(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.bottomleft; +} + +template +bool SimplifiedVoronoi::_complexTopLeftTransformRight(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.left; +} + +template +bool SimplifiedVoronoi::_complexTopLeftTransformBottomRight(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.topleft; +} + +template +bool SimplifiedVoronoi::_complexTopLeftTransformBottom(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.top; +} + +template +bool SimplifiedVoronoi::_complexTopLeftTransformBottomLeft(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.topright; +} + +template +bool SimplifiedVoronoi::_complexTopLeftTransformLeft(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.right; +} + +template +bool SimplifiedVoronoi::_complexTopLeftTransformTopLeft(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.bottomright; +} + +template +bool SimplifiedVoronoi::_complexTopRightTransformTop(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.left; +} + +template +bool SimplifiedVoronoi::_complexTopRightTransformTopRight(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.topleft; +} + +template +bool SimplifiedVoronoi::_complexTopRightTransformRight(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.top; +} + +template +bool SimplifiedVoronoi::_complexTopRightTransformBottomRight(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.topright; +} + +template +bool SimplifiedVoronoi::_complexTopRightTransformBottom(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.right; +} + +template +bool SimplifiedVoronoi::_complexTopRightTransformBottomLeft(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.bottomright; +} + +template +bool SimplifiedVoronoi::_complexTopRightTransformLeft(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.bottom; +} + +template +bool SimplifiedVoronoi::_complexTopRightTransformTopLeft(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.bottomleft; +} + +template +bool SimplifiedVoronoi::_complexBottomRightTransformTop(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.top; +} + +template +bool SimplifiedVoronoi::_complexBottomRightTransformTopRight(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.topright; +} + +template +bool SimplifiedVoronoi::_complexBottomRightTransformRight(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.right; +} + +template +bool SimplifiedVoronoi::_complexBottomRightTransformBottomRight(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.bottomright; +} + +template +bool SimplifiedVoronoi::_complexBottomRightTransformBottom(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.bottom; +} + +template +bool SimplifiedVoronoi::_complexBottomRightTransformBottomLeft(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.bottomleft; +} + +template +bool SimplifiedVoronoi::_complexBottomRightTransformLeft(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.left; +} + +template +bool SimplifiedVoronoi::_complexBottomRightTransformTopLeft(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.topleft; +} + +template +bool SimplifiedVoronoi::_complexBottomLeftTransformTop(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.right; +} + +template +bool SimplifiedVoronoi::_complexBottomLeftTransformTopRight(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.bottomright; +} + +template +bool SimplifiedVoronoi::_complexBottomLeftTransformRight(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.bottom; +} + +template +bool SimplifiedVoronoi::_complexBottomLeftTransformBottomRight(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.bottomleft; +} + +template +bool SimplifiedVoronoi::_complexBottomLeftTransformBottom(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.left; +} + +template +bool SimplifiedVoronoi::_complexBottomLeftTransformBottomLeft(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.topleft; +} + +template +bool SimplifiedVoronoi::_complexBottomLeftTransformLeft(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.top; +} + +template +bool SimplifiedVoronoi::_complexBottomLeftTransformTopLeft(PixelGraph::const_iterator graph_it) +{ + return graph_it->adj.topright; +} + +template +void +SimplifiedVoronoi +::_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) +{ + using colorspace::contour_edge; + using colorspace::same_color; + + const Point initial(x, y); + + if ( bottomright(a_it) ) { + // this and bottom-right are connected + + bool smooth[2] = { + same_color(a_it->rgba, d_it->rgba) + right(a_it), + same_color(a_it->rgba, d_it->rgba) + bottom(a_it) + }; + + Point borderMid = initial; + { + transform(borderMid, 1, 1); + borderMid = _midpoint(initial, borderMid); + } + + Point 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] ) { + cells_it->vertices.push_back(vertices[0]); + { + Point 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 )); + cells_it->vertices.push_back(another); + } + { + Point 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; + cells_it->vertices.push_back(another); + } + { + Point 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); + cells_it->vertices.push_back(another); + } + { + 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 )); + } + } + + cells_it->vertices.push_back(vertices[0]); + + if ( !smooth[1] ) { + { + Point 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); + cells_it->vertices.push_back(another); + } + { + Point 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); + cells_it->vertices.push_back(another); + } + { + Point 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; + cells_it->vertices.push_back(another); + } + { + Point 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 )); + cells_it->vertices.push_back(another); + } + } + + cells_it->vertices.push_back(vertices[1]); + } else if ( bottomleft(b_it) ) { + // right and bottom are connected + + Point 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 vertex = initial; + transform(vertex, 1, 1); + vertex = _adjust(_midpoint(initial, vertex)); + + // compute smoothness + if ( right(a_it) ) { + // 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 another = vertex; + T amount = 0.125 + - ( ( bottomright(c_it) + topleft(c_it) ) + * 0.03125 ); + transform(another, - amount, amount); + cells_it->vertices.push_back(another); + } + { + Point another = vertex; + T amount = 0.0625 * bottomright(c_it); + transform(another, amount, 0.25 - amount); + cells_it->vertices.push_back(another); + } + { + Point another = vertex; + T amount = 0.0625 * topleft(c_it); + transform(another, - ( 0.25 - amount ), + - amount); + another.smooth = true; + cells_it->vertices.push_back(another); + } + { + Point another = vertex; + T amount = 0.1875 * topleft(c_it); + transform(another, - ( 0.75 - amount ), + - amount); + cells_it->vertices.push_back(another); + } + } else if ( twin_is_contour ) { + T amount = 0.125 + - ( ( bottomleft(d_it) + topright(d_it) ) + * 0.03125 ); + transform(vertex, amount, amount); + } + } + } else { + // {this, right} is the pair with the angle + // closest to 180 degrees + vertex.smooth = true; + } + } 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 + = !( vertex.smooth = bottom(a_it) ^ bottom(b_it) ); + + if ( vertex.smooth ) { + 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) ) { + // 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 ) { + cells_it->vertices.push_back(vertex); + { + Point another = vertex; + T amount = 0.1875 * topleft(b_it); + transform(another, - amount, + - ( 0.75 - amount )); + cells_it->vertices.push_back(another); + } + { + Point another = vertex; + T amount = 0.0625 * topleft(b_it); + transform(another, - amount, + - ( 0.25 - amount )); + another.smooth = true; + cells_it->vertices.push_back(another); + } + { + Point another = vertex; + T amount = 0.0625 * bottomright(b_it); + transform(another, 0.25 - amount, amount); + cells_it->vertices.push_back(another); + } + { + T amount = 0.125 + - (bottomright(b_it) + topleft(b_it)) + * 0.03125; + transform(vertex, amount, - amount); + } + } else if ( twin_is_contour ) { + T amount = 0.125 + - ( ( topright(d_it) + bottomleft(d_it) ) + * 0.03125 ); + transform(vertex, amount, amount); + } + } + } else { + // {this, bottom} is the pair with the angle + // closest to 180 degrees + vertex.smooth = true; + } + } 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 = !( right(a_it) ^ right(c_it) ); + + if ( vertex.smooth ) { + 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) ) { + // 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 another = vertex; + T amount = 0.125 + - ( topleft(c_it) + bottomright(c_it) ) + * 0.03125; + transform(another, - amount, amount); + cells_it->vertices.push_back(another); + } + { + Point another = vertex; + T amount = 0.0625 * bottomright(c_it); + transform(another, amount, 0.25 - amount); + cells_it->vertices.push_back(another); + } + { + Point another = vertex; + T amount = 0.0625 * topleft(c_it); + transform(another, - ( 0.25 - amount ), - amount); + another.smooth = true; + cells_it->vertices.push_back(another); + } + { + Point another = vertex; + T amount = 0.1875 * topleft(c_it); + transform(another, - ( 0.75 - amount ), - amount); + cells_it->vertices.push_back(another); + } + } else { + special = true; + } + } + } else { + // {right, bottom-right} is the pair with the + // angle closest to 180 degrees + vertex.smooth = false; + + special = true; + } + + if ( special ) { + cells_it->vertices.push_back(vertex); + { + Point 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 )); + cells_it->vertices.push_back(another); + } + { + Point 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; + cells_it->vertices.push_back(another); + } + { + Point 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) )); + cells_it->vertices.push_back(another); + } + { + 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); + } + } + } else if ( right(c_it) ) { + // 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 ) { + cells_it->vertices.push_back(vertex); + { + Point another = vertex; + T amount = 0.1875 * topleft(b_it); + transform(another, - amount, - ( 0.75 - amount )); + cells_it->vertices.push_back(another); + } + { + Point another = vertex; + T amount = 0.0625 * topleft(b_it); + transform(another, - amount, - ( 0.25 - amount )); + another.smooth = true; + cells_it->vertices.push_back(another); + } + { + Point another = vertex; + T amount = 0.0625 * bottomright(b_it); + transform(another, 0.25 - amount, amount); + cells_it->vertices.push_back(another); + } + { + T amount = 0.125 + - 0.03125 * (topleft(b_it) + bottomright(b_it)); + transform(vertex, amount, - amount); + } + } 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 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) )); + cells_it->vertices.push_back(another); + } + { + Point 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) )); + cells_it->vertices.push_back(another); + } + { + Point 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; + cells_it->vertices.push_back(another); + } + { + Point 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) )); + cells_it->vertices.push_back(another); + } + } + } 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/libdepixelize/priv/splines.h b/src/libdepixelize/priv/splines.h new file mode 100644 index 000000000..c7ef2b492 --- /dev/null +++ b/src/libdepixelize/priv/splines.h @@ -0,0 +1,155 @@ +/* This file is part of the libdepixelize project + Copyright (C) 2013 Vinícius dos Santos Oliveira + + 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 . + + 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 . + + 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_PRIV_H +#define LIBDEPIXELIZE_TRACER_SPLINES_PRIV_H + +#include "../splines.h" +#include "homogeneoussplines.h" + +namespace Tracer { + +template +Geom::Point to_geom_point(Point p) +{ + return Geom::Point(p.x, p.y); +} + +template +Geom::Path worker_helper(const std::vector< Point > &source, bool optimize) +{ + typedef Geom::LineSegment Line; + typedef Geom::QuadraticBezier Quad; + typedef typename std::vector< Point >::const_iterator iterator; + + iterator it = source.begin(); + Geom::Path ret(to_geom_point((source.back() + *it) / 2)); + + for ( iterator end = --source.end() ; it != end ; ++it ) { + Point next = *(it + 1); + Point middle = (*it + next) / 2; + + if ( !it->smooth ) { + // TODO: remove redundant colinear points + ret.appendNew(Geom::Point(it->x, it->y)); + ret.appendNew(Geom::Point(middle.x, middle.y)); + } else { + ret.appendNew(Geom::Point(it->x, it->y), + Geom::Point(middle.x, middle.y)); + } + } + + { + Point next = source.front(); + Point middle = (*it + next) / 2; + + if ( !it->smooth ) { + ret.appendNew(Geom::Point(it->x, it->y)); + ret.appendNew(Geom::Point(middle.x, middle.y)); + } else { + ret.appendNew(Geom::Point(it->x, it->y), + Geom::Point(middle.x, middle.y)); + } + } + + return ret; +} + +/** + * It should be used by worker threads. Convert only one object. + */ +template +void worker(const typename HomogeneousSplines::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 > >::const_iterator + it = source.holes.begin(), end = source.holes.end() + ; it != end ; ++it ) { + dest.pathVector.push_back(worker_helper(*it, optimize)); + } +} + +template +Splines::Splines(const SimplifiedVoronoi &diagram) +{ + _paths.reserve(diagram.size()); + + for ( typename SimplifiedVoronoi::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 >::const_iterator + it2 = it->vertices.begin(), end2 = it->vertices.end() + ; it2 != end2 ; ++it2 ) { + path.pathVector.back() + .appendNew(Geom::Point(it2->x, it2->y)); + } + + for ( int i = 0 ; i != 4 ; ++i ) + path.rgba[i] = it->rgba[i]; + + _paths.push_back(path); + } +} + +template +Splines::Splines(const HomogeneousSplines &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::const_iterator + it = homogeneousSplines.begin(), end = homogeneousSplines.end() + ; it != end ; ++it, ++paths_it ) { + worker(*it, *paths_it, optimize); + } +} + +} // namespace Tracer + +#endif // LIBDEPIXELIZE_TRACER_SPLINES_PRIV_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/libdepixelize/priv/utils.h b/src/libdepixelize/priv/utils.h new file mode 100644 index 000000000..8a8e03352 --- /dev/null +++ b/src/libdepixelize/priv/utils.h @@ -0,0 +1,87 @@ +/* This file is part of the libdepixelize project + Copyright (C) 2013 Vinícius dos Santos Oliveira + + 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 . + + 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 . + + 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_UTILS_H +#define LIBDEPIXELIZE_TRACER_UTILS_H + +#include "pixelgraph.h" +#include "simplifiedvoronoi.h" +#include +#include +#include + +namespace Tracer { +namespace Utils { + +template +Splines to_splines(const SimplifiedVoronoi &diagram) +{ + svg << ""; + + for ( typename SimplifiedVoronoi::const_iterator it = diagram.begin() + , end = diagram.end() ; it != end ; ++it ) { + typename std::vector< Point >::const_iterator + it2 = it->vertices.begin(), end2 = it->vertices.end(); + if ( it2 == end2 ) + continue; + + svg << "x << ' ' << it2->y; + + std::hex(svg); + svg << " z\" fill=\"#" + << std::setfill('0') + << std::setw(2) << int(it->rgba[0]) + << std::setw(2) << int(it->rgba[1]) + << std::setw(2) << int(it->rgba[2]) + << std::setw(0) << std::setfill(' ') << "\" fill-opacity=\"" + << double(it->rgba[3]) / 255.; + std::dec(svg); + + svg << "\" />"; + } + + svg << "" << std::endl; +} + +} // namespace Utils +} // namespace Tracer + +#endif // LIBDEPIXELIZE_TRACER_UTILS_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/libdepixelize/splines.h b/src/libdepixelize/splines.h new file mode 100644 index 000000000..5f592da44 --- /dev/null +++ b/src/libdepixelize/splines.h @@ -0,0 +1,120 @@ +/* This file is part of the libdepixelize project + Copyright (C) 2013 Vinícius dos Santos Oliveira + + 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 . + + 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 . + + 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 + +namespace Tracer { + +template +class SimplifiedVoronoi; + +template +class HomogeneousSplines; + +class Splines +{ +public: + struct Path + { + /** + * It may be benefited from C++11 move references. + */ + Geom::PathVector pathVector; + + guint8 rgba[4]; + }; + + typedef typename std::vector::iterator iterator; + typedef typename std::vector::const_iterator const_iterator; + + Splines() /* = default */ {} + + template + Splines(const SimplifiedVoronoi &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 + Splines(const HomogeneousSplines &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 _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 : -- cgit v1.2.3 From 0f397bdb1eae4d190a5a7d7a4792d0571917753b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Vin=C3=ADcius=20dos=20Santos=20Oliveira?= Date: Fri, 13 Sep 2013 04:00:18 -0300 Subject: Bumping new version of libdepixelize (bzr r12506.1.3) --- src/libdepixelize/kopftracer2011.cpp | 179 +++++++++++++++++----------- src/libdepixelize/priv/branchless.h | 26 +--- src/libdepixelize/priv/colorspace.h | 2 +- src/libdepixelize/priv/homogeneoussplines.h | 2 - src/libdepixelize/priv/pixelgraph.h | 11 +- src/libdepixelize/priv/point.h | 2 - src/libdepixelize/priv/simplifiedvoronoi.h | 3 +- src/libdepixelize/priv/utils.h | 87 -------------- src/libdepixelize/splines.h | 4 +- 9 files changed, 121 insertions(+), 195 deletions(-) delete mode 100644 src/libdepixelize/priv/utils.h (limited to 'src/libdepixelize') diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp index 96a415f2c..26ad8863b 100644 --- a/src/libdepixelize/kopftracer2011.cpp +++ b/src/libdepixelize/kopftracer2011.cpp @@ -38,22 +38,40 @@ #include "priv/homogeneoussplines.h" #include "priv/branchless.h" #include "priv/splines.h" +#include "priv/iterator.h" namespace Tracer { namespace Heuristics { -int curves(PixelGraph &graph, PixelGraph::Node *a, PixelGraph::Node *b); -bool islands(PixelGraph &graph, PixelGraph::Node *a, PixelGraph::Node *b); +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 { - typedef std::pair Edge; + 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 + Edge; typedef std::pair EdgeWeight; - void operator()(PixelGraph &graph, unsigned radius); + void operator()(const PixelGraph &graph, unsigned radius); - static bool similar_colors(PixelGraph::Node *n, Edge edge); + 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]; }; @@ -231,12 +249,13 @@ void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, using std::pair; using std::make_pair; - typedef pair Edge; + typedef pair Edge; typedef pair EdgeWeight; EdgeWeight diagonals[2] = { - make_pair(make_pair(&*it, &*(it + graph.width() + 1)), 0), - make_pair(make_pair(&*(it + 1), &*(it + graph.width())), 0) + make_pair(make_pair(it, graph.nodeBottomRight(it)), 0), + make_pair(make_pair(graph.nodeRight(it), graph.nodeBottom(it)), + 0) }; // Check if there are crossing edges @@ -248,13 +267,13 @@ void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, // Compute weights for ( int i = 0 ; i != 2 ; ++i ) { // Curves and islands heuristics - PixelGraph::Node *a = diagonals[i].first.first; - PixelGraph::Node *b = diagonals[i].first.second; + PixelGraph::const_iterator a = diagonals[i].first.first; + PixelGraph::const_iterator b = diagonals[i].first.second; diagonals[i].second += Heuristics::curves(graph, a, b) * options.curvesMultiplier; - diagonals[i].second += Heuristics::islands(graph, a, b) + diagonals[i].second += Heuristics::islands(a, b) * options.islandsWeight; } @@ -290,20 +309,23 @@ void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, } } -inline int Heuristics::curves(PixelGraph &graph, PixelGraph::Node *a, - PixelGraph::Node *b) +inline int Heuristics::curves(const PixelGraph &graph, + PixelGraph::const_iterator a, + PixelGraph::const_iterator b) { int count = 1; + ToPtr to_ptr; + ToIter to_iter(graph.begin()); // b -> a // and then a -> b for ( int i = 0 ; i != 2 ; ++i ) { - PixelGraph::Node *it = i ? a : b; - PixelGraph::Node *prev = i ? b : a; + 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 - PixelGraph::Node *const initial = it; + const PixelGraph::const_iterator initial = it; while ( it->adjsize() == 2 ) { ++local_count; @@ -312,18 +334,26 @@ inline int Heuristics::curves(PixelGraph &graph, PixelGraph::Node *a, { // There are only two values that won't be zero'ed // and one of them has the same value of prev - guintptr aux = guintptr(it); - aux = it->adj.top * guintptr(it - graph.width()) - + it->adj.topright * guintptr(it - graph.width() + 1) - + it->adj.right * guintptr(it + 1) - + it->adj.bottomright * guintptr(it + graph.width() + 1) - + it->adj.bottom * guintptr(it + graph.width()) - + it->adj.bottomleft * guintptr(it + graph.width() - 1) - + it->adj.left * guintptr(it - 1) - + it->adj.topleft * guintptr(it - graph.width() - 1) - - guintptr(prev); + guintptr aux = guintptr(to_ptr(it)); + 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 = reinterpret_cast(aux); + it = to_iter(reinterpret_cast(aux)); } // Break infinite loops @@ -336,7 +366,7 @@ inline int Heuristics::curves(PixelGraph &graph, PixelGraph::Node *a, return count; } -inline void Heuristics::SparsePixels::operator ()(PixelGraph &graph, +inline void Heuristics::SparsePixels::operator ()(const PixelGraph &graph, unsigned radius) { if ( !graph.width() || !graph.height() ) @@ -346,72 +376,79 @@ inline void Heuristics::SparsePixels::operator ()(PixelGraph &graph, for ( int i = 0 ; i != 2 ; ++i ) diagonals[i].second = 0; - // Compute begin and end nodes under a (2*radius)^2 window - std::pair begin(0, 0); + if ( !radius ) + return; - // Get midpoint + // Fix radius/bounds { - using branchless::max_consecutive; - - unsigned x1 = graph.toX(diagonals[0].first.first); - unsigned x2 = graph.toX(diagonals[0].first.second); - begin.first = max_consecutive(x1, x2); - - unsigned y1 = graph.toY(diagonals[0].first.first); - unsigned y2 = graph.toY(diagonals[0].first.second); - begin.second = max_consecutive(y1, y2); - } - - std::pair end(begin.first + radius, - begin.second + radius); + unsigned x = graph.toX(diagonals[MAIN_DIAGONAL].first.first); + unsigned y = graph.toY(diagonals[MAIN_DIAGONAL].first.first); + unsigned minor = std::min(x, y); + unsigned displace = radius - 1; + + if ( displace > minor ) { + displace = minor; + radius = displace + 1; + } - // Get beginning point - { - using branchless::first_if; + displace = radius; - begin.first = first_if(begin.first - radius, 0u, begin.first >= radius); + if ( x + displace >= graph.width() ) { + displace = unsigned(graph.width()) - x - 1; + radius = displace; + } - begin.second = first_if(begin.second - radius, 0u, - begin.second >= radius); + if ( y + displace >= graph.height() ) { + displace = unsigned(graph.height()) - y - 1; + radius = displace; + } } - // Fix ending point if misplaced - { - using branchless::first_if; + if ( !radius ) + return; - end.first = first_if(unsigned(graph.width()), end.first, - end.first > graph.width()); + // 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)); - end.second = first_if(unsigned(graph.height()), end.second, - end.second > graph.height()); - } - // Iterate over nodes and count them - for ( int i = begin.second ; i != end.second ; ++i ) { - PixelGraph::Node *it = &graph[begin.first][i]; - for ( int j = begin.first ; j != end.first ; ++j, ++it ) { - for ( int k = 0 ; k != 2 ; ++k ) - diagonals[k].second += similar_colors(it, diagonals[k].first); + invert = !invert; + it = graph.nodeBottom(it); } } - int minor = branchless::min(diagonals[0].second, diagonals[1].second); + 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::Node *n, - Heuristics::SparsePixels::Edge edge) +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, edge.first->rgba) - || similar_colors(n->rgba, edge.second->rgba)); + return similar_colors(n->rgba, a) || similar_colors(n->rgba, b); } -inline bool Heuristics::islands(PixelGraph &graph, PixelGraph::Node *a, - PixelGraph::Node *b) +inline bool Heuristics::islands(PixelGraph::const_iterator a, + PixelGraph::const_iterator b) { if ( a->adjsize() == 1 || b->adjsize() == 1 ) return true; diff --git a/src/libdepixelize/priv/branchless.h b/src/libdepixelize/priv/branchless.h index f8f041cce..487a9688d 100644 --- a/src/libdepixelize/priv/branchless.h +++ b/src/libdepixelize/priv/branchless.h @@ -32,31 +32,13 @@ namespace Tracer { */ namespace branchless { -template -T first_if(T first, T second, bool cond) -{ - return first * cond + second * (1 - cond); -} - -template -T min(T first, T second) -{ - return first - (first > second) * (first - second); -} - -template -T max(T first, T second) -{ - return first + (first < second) * (second - first); -} - -/** - * When abs(first - second) == 1 +/* + * All modern processors optimize the branch to a conditional move */ template -T max_consecutive(T first, T second) +T first_if(T first, T second, bool cond) { - return first + (first < second); + return cond ? first : second; } } // namespace branchless diff --git a/src/libdepixelize/priv/colorspace.h b/src/libdepixelize/priv/colorspace.h index 21025b852..4982630ad 100644 --- a/src/libdepixelize/priv/colorspace.h +++ b/src/libdepixelize/priv/colorspace.h @@ -25,7 +25,7 @@ #ifndef LIBDEPIXELIZE_TRACER_YUV_H #define LIBDEPIXELIZE_TRACER_YUV_H -#include +#include namespace Tracer { namespace colorspace { diff --git a/src/libdepixelize/priv/homogeneoussplines.h b/src/libdepixelize/priv/homogeneoussplines.h index d6860cdf4..57c77a163 100644 --- a/src/libdepixelize/priv/homogeneoussplines.h +++ b/src/libdepixelize/priv/homogeneoussplines.h @@ -82,8 +82,6 @@ public: return _polygons.end(); } - // Capacity - size_type size() const { return _polygons.size(); diff --git a/src/libdepixelize/priv/pixelgraph.h b/src/libdepixelize/priv/pixelgraph.h index 0ae4f36b4..32523d8ee 100644 --- a/src/libdepixelize/priv/pixelgraph.h +++ b/src/libdepixelize/priv/pixelgraph.h @@ -40,7 +40,7 @@ public: /* * Hamming weight of \p adj */ - unsigned adjsize() + unsigned adjsize() const { unsigned all[8] = { adj.top, @@ -145,7 +145,6 @@ public: return _nodes.rend(); } - // Capacity size_t size() const { return _nodes.size(); @@ -164,14 +163,14 @@ public: // Algorithms void connectAllNeighbors(); - int toX(Node *n) const + int toX(const_iterator n) const { - return (n - &_nodes[0]) % _width; + return (&*n - &_nodes[0]) % _width; } - int toY(Node *n) const + int toY(const_iterator n) const { - return (n - &_nodes[0]) / _width; + return (&*n - &_nodes[0]) / _width; } iterator nodeTop(iterator n) diff --git a/src/libdepixelize/priv/point.h b/src/libdepixelize/priv/point.h index 037c03de6..6bea752ed 100644 --- a/src/libdepixelize/priv/point.h +++ b/src/libdepixelize/priv/point.h @@ -25,8 +25,6 @@ #ifndef LIBDEPIXELIZE_TRACER_POINT_H #define LIBDEPIXELIZE_TRACER_POINT_H -#include - namespace Tracer { template diff --git a/src/libdepixelize/priv/simplifiedvoronoi.h b/src/libdepixelize/priv/simplifiedvoronoi.h index 7c4a6d9fb..a33695ff7 100644 --- a/src/libdepixelize/priv/simplifiedvoronoi.h +++ b/src/libdepixelize/priv/simplifiedvoronoi.h @@ -105,7 +105,6 @@ public: return _cells.rend(); } - // Capacity size_t size() const { return _cells.size(); @@ -1011,7 +1010,7 @@ SimplifiedVoronoi // or it might be 1-color and doesn't matter, // because the current node will disappear vertex.smooth - = !( vertex.smooth = bottom(a_it) ^ bottom(b_it) ); + = !( bottom(a_it) ^ bottom(b_it) ); if ( vertex.smooth ) { vertex.smooth diff --git a/src/libdepixelize/priv/utils.h b/src/libdepixelize/priv/utils.h deleted file mode 100644 index 8a8e03352..000000000 --- a/src/libdepixelize/priv/utils.h +++ /dev/null @@ -1,87 +0,0 @@ -/* This file is part of the libdepixelize project - Copyright (C) 2013 Vinícius dos Santos Oliveira - - 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 . - - 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 . - - 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_UTILS_H -#define LIBDEPIXELIZE_TRACER_UTILS_H - -#include "pixelgraph.h" -#include "simplifiedvoronoi.h" -#include -#include -#include - -namespace Tracer { -namespace Utils { - -template -Splines to_splines(const SimplifiedVoronoi &diagram) -{ - svg << ""; - - for ( typename SimplifiedVoronoi::const_iterator it = diagram.begin() - , end = diagram.end() ; it != end ; ++it ) { - typename std::vector< Point >::const_iterator - it2 = it->vertices.begin(), end2 = it->vertices.end(); - if ( it2 == end2 ) - continue; - - svg << "x << ' ' << it2->y; - - std::hex(svg); - svg << " z\" fill=\"#" - << std::setfill('0') - << std::setw(2) << int(it->rgba[0]) - << std::setw(2) << int(it->rgba[1]) - << std::setw(2) << int(it->rgba[2]) - << std::setw(0) << std::setfill(' ') << "\" fill-opacity=\"" - << double(it->rgba[3]) / 255.; - std::dec(svg); - - svg << "\" />"; - } - - svg << "" << std::endl; -} - -} // namespace Utils -} // namespace Tracer - -#endif // LIBDEPIXELIZE_TRACER_UTILS_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/libdepixelize/splines.h b/src/libdepixelize/splines.h index 5f592da44..c4b455aae 100644 --- a/src/libdepixelize/splines.h +++ b/src/libdepixelize/splines.h @@ -49,8 +49,8 @@ public: guint8 rgba[4]; }; - typedef typename std::vector::iterator iterator; - typedef typename std::vector::const_iterator const_iterator; + typedef std::vector::iterator iterator; + typedef std::vector::const_iterator const_iterator; Splines() /* = default */ {} -- cgit v1.2.3 From 15e4b9bc37d3e877828dff093f7670e7894be286 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Vin=C3=ADcius=20dos=20Santos=20Oliveira?= Date: Fri, 13 Sep 2013 14:22:24 -0300 Subject: Missing file from libdepixelize (bzr r12506.1.4) --- src/libdepixelize/priv/iterator.h | 123 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 123 insertions(+) create mode 100644 src/libdepixelize/priv/iterator.h (limited to 'src/libdepixelize') diff --git a/src/libdepixelize/priv/iterator.h b/src/libdepixelize/priv/iterator.h new file mode 100644 index 000000000..7caa9bfa9 --- /dev/null +++ b/src/libdepixelize/priv/iterator.h @@ -0,0 +1,123 @@ +/* This file is part of the libdepixelize project + Copyright (C) 2013 Vinícius dos Santos Oliveira + + 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 . + + 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 . + + 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 +#include + +namespace Tracer { + +template +const T *to_ptr(typename std::vector::const_iterator it) +{ + return &*it; +} + +template +T *to_ptr(typename std::vector::iterator it) +{ + return &*it; +} + +template +typename std::vector::const_iterator to_iterator(T const *ptr, + typename std::vector + ::const_iterator begin) +{ + typedef typename std::vector::const_iterator It; + typedef typename std::iterator_traits::difference_type difference_type; + difference_type idx = ptr - to_ptr(begin); + return begin + idx; +} + +template +typename std::vector::iterator to_iterator(T *ptr, + typename std::vector::iterator + begin) +{ + typedef typename std::vector::iterator It; + typedef typename std::iterator_traits::difference_type difference_type; + difference_type idx = ptr - to_ptr(begin); + return begin + idx; +} + +template +class ToIter +{ +public: + typedef typename std::vector::const_iterator const_iterator; + typedef typename std::vector::iterator iterator; + + ToIter(const_iterator begin) : + begin(begin) + {} + + const_iterator operator()(T const *ptr) const + { + return to_iterator(ptr, begin); + } + + iterator operator()(T *ptr) const + { + return to_iterator(ptr, begin); + } + +private: + typename std::vector::const_iterator begin; +}; + +template +class ToPtr +{ +public: + typedef typename std::vector::const_iterator const_iterator; + typedef typename std::vector::iterator iterator; + + const T *operator()(const_iterator it) const + { + return to_ptr(it); + } + + T *operator()(iterator it) const + { + return to_ptr(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 : -- cgit v1.2.3 From 044c350e4c0e27e97cb39dd6dbb25e7655c302d1 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Fri, 20 Sep 2013 07:38:24 +1000 Subject: updates for cmake (bzr r12547) --- src/libdepixelize/CMakeLists.txt | 13 +++++++++++-- 1 file changed, 11 insertions(+), 2 deletions(-) (limited to 'src/libdepixelize') diff --git a/src/libdepixelize/CMakeLists.txt b/src/libdepixelize/CMakeLists.txt index 64a72f9d9..e05849e29 100644 --- a/src/libdepixelize/CMakeLists.txt +++ b/src/libdepixelize/CMakeLists.txt @@ -4,8 +4,17 @@ set(libdepixelize_SRC # ------- # Headers - kopftracer2011.h - splines.h + kopftracer2011.h + splines.h + + priv/branchless.h + priv/colorspace.h + priv/homogeneoussplines.h + priv/iterator.h + priv/pixelgraph.h + priv/point.h + priv/simplifiedvoronoi.h + priv/splines.h ) add_inkscape_lib(depixelize_LIB "${libdepixelize_SRC}") -- cgit v1.2.3 From 763b5e48a181b326e393b8b6c32b65f4aecf7a40 Mon Sep 17 00:00:00 2001 From: Alex Valavanis Date: Sat, 21 Sep 2013 12:34:52 +0100 Subject: Fix make dist Fixed bugs: - https://launchpad.net/bugs/1188627 (bzr r12564) --- src/libdepixelize/Makefile_insert | 16 ++++++++++++---- 1 file changed, 12 insertions(+), 4 deletions(-) (limited to 'src/libdepixelize') diff --git a/src/libdepixelize/Makefile_insert b/src/libdepixelize/Makefile_insert index 75b19bf5c..421d32439 100644 --- a/src/libdepixelize/Makefile_insert +++ b/src/libdepixelize/Makefile_insert @@ -5,7 +5,15 @@ libdepixelize/all: libdepixelize/libdepixelize.a libdepixelize/clean: rm -f libdepixelize/libdepixelize.a $(libdepixelize_libdepixelize_a_OBJECTS) -libdepixelize_libdepixelize_a_SOURCES = \ - libdepixelize/kopftracer2011.cpp \ - libdepixelize/kopftracer2011.h \ - libdepixelize/splines.h +libdepixelize_libdepixelize_a_SOURCES = \ + libdepixelize/kopftracer2011.cpp \ + libdepixelize/kopftracer2011.h \ + libdepixelize/splines.h \ + libdepixelize/priv/branchless.h \ + libdepixelize/priv/colorspace.h \ + libdepixelize/priv/homogeneoussplines.h \ + libdepixelize/priv/iterator.h \ + libdepixelize/priv/pixelgraph.h \ + libdepixelize/priv/point.h \ + libdepixelize/priv/simplifiedvoronoi.h \ + libdepixelize/priv/splines.h -- cgit v1.2.3 From f26093b0c3d95f1c0c29696325e52a3b748cd881 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Vin=C3=ADcius=20dos=20Santos=20Oliveira?= Date: Mon, 23 Sep 2013 15:20:04 -0300 Subject: Bumping new version of libdepixelize (bzr r12579) --- src/libdepixelize/CMakeLists.txt | 7 +- src/libdepixelize/Makefile_insert | 27 +-- src/libdepixelize/kopftracer2011.cpp | 51 ++++- src/libdepixelize/kopftracer2011.h | 8 +- src/libdepixelize/priv/curvature.h | 115 +++++++++++ src/libdepixelize/priv/integral.h | 61 ++++++ src/libdepixelize/priv/optimization-kopf2011.h | 263 +++++++++++++++++++++++++ src/libdepixelize/priv/pixelgraph.h | 29 ++- src/libdepixelize/priv/point.h | 45 ++++- src/libdepixelize/priv/simplifiedvoronoi.h | 93 +++++---- src/libdepixelize/priv/splines-kopf2011.h | 167 ++++++++++++++++ src/libdepixelize/priv/splines.h | 155 --------------- 12 files changed, 791 insertions(+), 230 deletions(-) create mode 100644 src/libdepixelize/priv/curvature.h create mode 100644 src/libdepixelize/priv/integral.h create mode 100644 src/libdepixelize/priv/optimization-kopf2011.h create mode 100644 src/libdepixelize/priv/splines-kopf2011.h delete mode 100644 src/libdepixelize/priv/splines.h (limited to 'src/libdepixelize') diff --git a/src/libdepixelize/CMakeLists.txt b/src/libdepixelize/CMakeLists.txt index e05849e29..895e16e85 100644 --- a/src/libdepixelize/CMakeLists.txt +++ b/src/libdepixelize/CMakeLists.txt @@ -7,14 +7,17 @@ set(libdepixelize_SRC kopftracer2011.h splines.h - priv/branchless.h + priv/branchless.h priv/colorspace.h + priv/curvature.h priv/homogeneoussplines.h + priv/integral priv/iterator.h + priv/optimization-kopf2011.h priv/pixelgraph.h priv/point.h priv/simplifiedvoronoi.h - priv/splines.h + priv/splines-kopf2011.h ) add_inkscape_lib(depixelize_LIB "${libdepixelize_SRC}") diff --git a/src/libdepixelize/Makefile_insert b/src/libdepixelize/Makefile_insert index 421d32439..b5be88c5f 100644 --- a/src/libdepixelize/Makefile_insert +++ b/src/libdepixelize/Makefile_insert @@ -5,15 +5,18 @@ libdepixelize/all: libdepixelize/libdepixelize.a libdepixelize/clean: rm -f libdepixelize/libdepixelize.a $(libdepixelize_libdepixelize_a_OBJECTS) -libdepixelize_libdepixelize_a_SOURCES = \ - libdepixelize/kopftracer2011.cpp \ - libdepixelize/kopftracer2011.h \ - libdepixelize/splines.h \ - libdepixelize/priv/branchless.h \ - libdepixelize/priv/colorspace.h \ - libdepixelize/priv/homogeneoussplines.h \ - libdepixelize/priv/iterator.h \ - libdepixelize/priv/pixelgraph.h \ - libdepixelize/priv/point.h \ - libdepixelize/priv/simplifiedvoronoi.h \ - libdepixelize/priv/splines.h +libdepixelize_libdepixelize_a_SOURCES = \ + libdepixelize/kopftracer2011.cpp \ + libdepixelize/kopftracer2011.h \ + libdepixelize/splines.h \ + libdepixelize/priv/branchless.h \ + libdepixelize/priv/colorspace.h \ + libdepixelize/priv/curvature.h \ + libdepixelize/priv/homogeneoussplines.h \ + libdepixelize/priv/integral \ + libdepixelize/priv/iterator.h \ + libdepixelize/priv/optimization-kopf2011.h \ + libdepixelize/priv/pixelgraph.h \ + libdepixelize/priv/point.h \ + libdepixelize/priv/simplifiedvoronoi.h \ + libdepixelize/priv/splines-kopf2011.h diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp index 26ad8863b..50b12d527 100644 --- a/src/libdepixelize/kopftracer2011.cpp +++ b/src/libdepixelize/kopftracer2011.cpp @@ -37,7 +37,7 @@ #include "priv/colorspace.h" #include "priv/homogeneoussplines.h" #include "priv/branchless.h" -#include "priv/splines.h" +#include "priv/splines-kopf2011.h" #include "priv/iterator.h" namespace Tracer { @@ -142,6 +142,12 @@ SimplifiedVoronoi Kopf2011::_voronoi(const Glib::RefPtr &b _remove_crossing_edges_unsafe(graph, options); +#ifndef NDEBUG + graph.checkConsistency(); +#endif + + _remove_puzzle_pattern(graph); + #ifndef NDEBUG graph.checkConsistency(); #endif @@ -309,6 +315,33 @@ void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, } } +inline +void Kopf2011::_remove_puzzle_pattern(PixelGraph &graph) +{ + if ( graph.width() < 2 || graph.height() < 2 ) + return; + + PixelGraph::iterator it = graph.begin(); + for ( int i = 0 ; i + 1 != graph.height() ; ++i ) { + PixelGraph::iterator it2 = it; + for ( int j = 0 ; j + 1 != graph.width() ; ++j ) { + // Evil pattern currently not handled correctly in SimplifiedVoronoi + if ( it2->adj.right + it2->adj.bottom + + graph.nodeBottomRight(it2)->adj.left + + graph.nodeBottomRight(it2)->adj.top == 3 ) { + // We fake a new connection =) + it2->adj.right = true; + it2->adj.bottom = true; + graph.nodeBottomRight(it2)->adj.left = true; + graph.nodeBottomRight(it2)->adj.top = true; + } + + it2 = graph.nodeRight(it2); + } + it = graph.nodeBottom(it); + } +} + inline int Heuristics::curves(const PixelGraph &graph, PixelGraph::const_iterator a, PixelGraph::const_iterator b) @@ -383,22 +416,25 @@ inline void Heuristics::SparsePixels::operator ()(const PixelGraph &graph, { unsigned x = graph.toX(diagonals[MAIN_DIAGONAL].first.first); unsigned y = graph.toY(diagonals[MAIN_DIAGONAL].first.first); - unsigned minor = std::min(x, y); unsigned displace = radius - 1; - if ( displace > minor ) { - displace = minor; - radius = displace + 1; + { + unsigned minor = std::min(x, y); + + if ( displace > minor ) { + displace = minor; + radius = displace + 1; + } } displace = radius; - if ( x + displace >= graph.width() ) { + if ( x + displace >= unsigned(graph.width()) ) { displace = unsigned(graph.width()) - x - 1; radius = displace; } - if ( y + displace >= graph.height() ) { + if ( y + displace >= unsigned(graph.height()) ) { displace = unsigned(graph.height()) - y - 1; radius = displace; } @@ -434,7 +470,6 @@ inline void Heuristics::SparsePixels::operator ()(const PixelGraph &graph, 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); } diff --git a/src/libdepixelize/kopftracer2011.h b/src/libdepixelize/kopftracer2011.h index 73f3b7274..aff39d3d8 100644 --- a/src/libdepixelize/kopftracer2011.h +++ b/src/libdepixelize/kopftracer2011.h @@ -73,12 +73,17 @@ public: /** * # 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 &buf, const Options &options = Options()); @@ -95,7 +100,7 @@ public: const Options &options = Options()); private: - typedef double Precision; + typedef Geom::Coord Precision; template static SimplifiedVoronoi _voronoi(const Glib::RefPtr &buf, @@ -105,6 +110,7 @@ private: static void _remove_crossing_edges_safe(PixelGraph &graph); static void _remove_crossing_edges_unsafe(PixelGraph &graph, const Options &options); + static void _remove_puzzle_pattern(PixelGraph &graph); }; } // namespace Tracer diff --git a/src/libdepixelize/priv/curvature.h b/src/libdepixelize/priv/curvature.h new file mode 100644 index 000000000..3a1af4197 --- /dev/null +++ b/src/libdepixelize/priv/curvature.h @@ -0,0 +1,115 @@ +/* This file is part of the libdepixelize project + Copyright (C) 2013 Vinícius dos Santos Oliveira + + 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 . + + 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 . + + 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 + +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 +struct Curvature +{ + Curvature(Point p0, Point c1, Point 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 p0, c1, p2; +}; + +template +T Curvature::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 +T Curvature::xPrime(T t) const +{ + return (1-t)*2*(c1.x-p0.x) + t*2*(p2.x-c1.x); +} + +template +T Curvature::yPrime(T t) const +{ + return (1-t)*2*(c1.y-p0.y) + t*2*(p2.y-c1.y); +} + +template +T Curvature::xPrimePrime() const +{ + return 2 * (p2.x - 2*c1.x + p0.x); +} + +template +T Curvature::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/libdepixelize/priv/integral.h b/src/libdepixelize/priv/integral.h new file mode 100644 index 000000000..fc1a49f27 --- /dev/null +++ b/src/libdepixelize/priv/integral.h @@ -0,0 +1,61 @@ +/* This file is part of the libdepixelize project + Copyright (C) 2013 Vinícius dos Santos Oliveira + + 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 . + + 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 . + + 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 +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/libdepixelize/priv/optimization-kopf2011.h b/src/libdepixelize/priv/optimization-kopf2011.h new file mode 100644 index 000000000..0c9011ca7 --- /dev/null +++ b/src/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 + + 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 . + + 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 . + + 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 +#include + +namespace Tracer { + +/** + * m is angular coeficient + */ +template +bool is_valid_border_m(T a) +{ + if ( a < 0 ) + a *= -1; + + // TODO: alternative behaviour if has no infinity + return a == std::numeric_limits::infinity() + || a == 3 || a == 1; +} + +/** + * Return true if the four points are considered a border. + */ +template +bool is_border(const Point (&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 +typename std::vector< Point >::iterator +skip1visible(typename std::vector< Point >::iterator it, + typename std::vector< Point >::iterator end) +{ + for ( ++it ; it != end ; ++it ) { + if ( it->visible ) + return it; + } + return end; +} + +/** + * Return how many elements should be skipped. + */ +template +typename std::vector< Point >::difference_type +border_detection(typename std::vector< Point >::iterator it, + typename std::vector< Point >::iterator end) +{ + typename std::vector< Point >::iterator begin = it; + + if ( end - it < 4 ) + return 0; + + Point last[4]; + typename std::vector< Point >::iterator prev = it; + + for ( int i = 0 ; i != 4 ; ++i ) { + if ( it == end ) + return 0; + last[i] = *it; + prev = it; + it = skip1visible(it, end); + } + + if ( !is_border(last) ) + return 0; + + if ( it == end ) + return prev - begin; + + bool got_another = false; + for ( it = skip1visible(it, end) ; it != end + ; it = skip1visible(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 +T smoothness_energy(Point c0, Point c1, Point c2) +{ + Point p0 = midpoint(c0, c1); + Point p2 = midpoint(c1, c2); + Curvature cur(p0, c1, p2); + + return std::abs(integral(cur, 0, 1, 16)); +} + +template +T positional_energy(Point guess, Point 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 +Point optimization_guess(Point 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(d[0], d[1]); +} + +template +std::vector< Point > optimize(const std::vector< Point > &path) +{ + typedef std::vector< Point > 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 prev = ( j == 0 ) ? ret.back() : ret[j-1]; + Point 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(it, ret.end()); + j += skip; + if ( j == ret.size() ) + break; + } + + ++n; + + for ( unsigned k = 0 ; k != nguess_per_iteration ; ++k ) { + Point 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/libdepixelize/priv/pixelgraph.h b/src/libdepixelize/priv/pixelgraph.h index 32523d8ee..9e8c2124a 100644 --- a/src/libdepixelize/priv/pixelgraph.h +++ b/src/libdepixelize/priv/pixelgraph.h @@ -378,7 +378,7 @@ inline void PixelGraph::connectAllNeighbors() it = nodeRight(it); } - // After the previous loop, 'it' is poiting to the last node from + // 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) @@ -445,21 +445,34 @@ inline void PixelGraph::connectAllNeighbors() // ...and the 4 corner nodes { Node *const top_left = &(*this)[0][0]; - top_left->adj.right = 1; - top_left->adj.bottomright = 1; - top_left->adj.bottom = 1; + + 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]; - top_right->adj.bottom = 1; - top_right->adj.bottomleft = 1; + + 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; - down_left->adj.topright = 1; - down_left->adj.right = 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]; diff --git a/src/libdepixelize/priv/point.h b/src/libdepixelize/priv/point.h index 6bea752ed..dc28a2b84 100644 --- a/src/libdepixelize/priv/point.h +++ b/src/libdepixelize/priv/point.h @@ -30,9 +30,9 @@ namespace Tracer { template struct Point { - Point() {} - Point(T x, T y) : x(x), y(y) {} - Point(T x, T y, bool smooth) : smooth(smooth), x(x), y(y) {} + Point() : visible(true) {} + Point(T x, T y) : 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 { @@ -44,21 +44,58 @@ struct Point 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 -inline bool operator==(const Point &lhs, const Point &rhs) +Point midpoint(const Point &a, const Point &b) +{ + return Point((a.x + b.x) / 2, (a.y + b.y) / 2); +} + +template +bool operator==(const Point &lhs, const Point &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 +bool weakly_equal(const Point &a, const Point &b) +{ + return a.x == b.x && a.y == b.y; +} + +template +Geom::Point to_geom_point(Point p) +{ + return Geom::Point(p.x, p.y); +} + } // namespace Tracer #endif // LIBDEPIXELIZE_TRACER_POINT_H diff --git a/src/libdepixelize/priv/simplifiedvoronoi.h b/src/libdepixelize/priv/simplifiedvoronoi.h index a33695ff7..d5ebc36e5 100644 --- a/src/libdepixelize/priv/simplifiedvoronoi.h +++ b/src/libdepixelize/priv/simplifiedvoronoi.h @@ -124,11 +124,6 @@ private: typedef void (*PointTransform)(Point &p, T dx, T dy); typedef bool (*NodeTransform)(PixelGraph::const_iterator); - static Point _midpoint(const Point &p1, const Point p2) - { - return Point((p1.x + p2.x) / 2, (p1.y + p2.y) / 2); - } - /** * Output is translated by -.5 in each axis. This function fixes this error. */ @@ -220,7 +215,7 @@ private: * 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 - * abstracation. + * abstraction. * * "All problems in computer science can be solved by another level of * indirection, except for the problem of too many layers of indirection." @@ -255,6 +250,11 @@ SimplifiedVoronoi::SimplifiedVoronoi(const PixelGraph &graph) : 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; @@ -276,7 +276,7 @@ SimplifiedVoronoi::SimplifiedVoronoi(const PixelGraph &graph) : // Bottom-left _complexBottomLeft(graph, graph_it, cells_it, j, i); } - // After the previous loop, 'it' is poiting to the last cell from + // 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) @@ -794,13 +794,13 @@ SimplifiedVoronoi PixelGraph::const_iterator d_it, Cell *const cells_it, int x, int y, PointTransform transform, - NodeTransform top, + NodeTransform, NodeTransform topright, NodeTransform right, NodeTransform bottomright, NodeTransform bottom, NodeTransform bottomleft, - NodeTransform left, + NodeTransform, NodeTransform topleft) { using colorspace::contour_edge; @@ -808,31 +808,36 @@ SimplifiedVoronoi const Point 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) + right(a_it), - same_color(a_it->rgba, d_it->rgba) + bottom(a_it) + same_color(a_it->rgba, d_it->rgba) || right(a_it), + same_color(a_it->rgba, d_it->rgba) || bottom(a_it) }; Point borderMid = initial; { transform(borderMid, 1, 1); - borderMid = _midpoint(initial, borderMid); + borderMid = midpoint(initial, borderMid); } Point vertices[2] = {initial, initial}; { transform(vertices[0], 1, 0); - vertices[0] = _adjust(_midpoint(borderMid, vertices[0]), smooth[0]); + vertices[0] = _adjust(midpoint(borderMid, vertices[0]), smooth[0]); transform(vertices[1], 0, 1); - vertices[1] = _adjust(_midpoint(borderMid, vertices[1]), smooth[1]); + vertices[1] = _adjust(midpoint(borderMid, vertices[1]), smooth[1]); } if ( !smooth[0] ) { - cells_it->vertices.push_back(vertices[0]); + cells_it->vertices.push_back(vertices[0].invisible()); { Point another = vertices[0]; transform(another, @@ -841,7 +846,7 @@ SimplifiedVoronoi // y - ( 0.5625 - ( topright(a_it) + topleft(b_it) ) * 0.1875 )); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } { Point another = vertices[0]; @@ -862,7 +867,7 @@ SimplifiedVoronoi // y 0.0625 + ( bottomright(b_it) - topright(d_it) ) * 0.0625); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } { transform(vertices[0], @@ -874,6 +879,7 @@ SimplifiedVoronoi + ( topright(d_it) - topright(a_it) - topleft(b_it) - bottomright(b_it) ) * 0.03125 )); + vertices[0].visible = false; } } @@ -891,7 +897,7 @@ SimplifiedVoronoi 0.0625 + ( bottomleft(a_it) - bottomleft(d_it) - topleft(c_it) - bottomright(c_it) ) * 0.03125); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } { Point another = vertices[1]; @@ -901,7 +907,7 @@ SimplifiedVoronoi // y 0.1875 - ( bottomright(c_it) + bottomleft(d_it) ) * 0.0625); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } { Point another = vertices[1]; @@ -926,8 +932,9 @@ SimplifiedVoronoi - ( 0.1875 - ( bottomleft(a_it) - topleft(c_it) ) * 0.1875 )); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } + vertices[1].visible = false; } cells_it->vertices.push_back(vertices[1]); @@ -936,7 +943,7 @@ SimplifiedVoronoi Point vertex = initial; transform(vertex, 1, 1); - vertex = _adjust(_midpoint(_midpoint(initial, vertex), initial), true); + 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 @@ -944,7 +951,7 @@ SimplifiedVoronoi Point vertex = initial; transform(vertex, 1, 1); - vertex = _adjust(_midpoint(initial, vertex)); + vertex = _adjust(midpoint(initial, vertex)); // compute smoothness if ( right(a_it) ) { @@ -969,13 +976,13 @@ SimplifiedVoronoi - ( ( bottomright(c_it) + topleft(c_it) ) * 0.03125 ); transform(another, - amount, amount); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } { Point another = vertex; T amount = 0.0625 * bottomright(c_it); transform(another, amount, 0.25 - amount); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } { Point another = vertex; @@ -990,8 +997,9 @@ SimplifiedVoronoi T amount = 0.1875 * topleft(c_it); transform(another, - ( 0.75 - amount ), - amount); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } + vertex.visible = false; } else if ( twin_is_contour ) { T amount = 0.125 - ( ( bottomleft(d_it) + topright(d_it) ) @@ -1036,13 +1044,13 @@ SimplifiedVoronoi if ( !vertex.smooth ) { if ( another_is_contour ) { - cells_it->vertices.push_back(vertex); + cells_it->vertices.push_back(vertex.invisible()); { Point another = vertex; T amount = 0.1875 * topleft(b_it); transform(another, - amount, - ( 0.75 - amount )); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } { Point another = vertex; @@ -1056,13 +1064,14 @@ SimplifiedVoronoi Point another = vertex; T amount = 0.0625 * bottomright(b_it); transform(another, 0.25 - amount, amount); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } { T amount = 0.125 - (bottomright(b_it) + topleft(b_it)) * 0.03125; transform(vertex, amount, - amount); + vertex.visible = false; } } else if ( twin_is_contour ) { T amount = 0.125 @@ -1115,13 +1124,13 @@ SimplifiedVoronoi - ( topleft(c_it) + bottomright(c_it) ) * 0.03125; transform(another, - amount, amount); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } { Point another = vertex; T amount = 0.0625 * bottomright(c_it); transform(another, amount, 0.25 - amount); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } { Point another = vertex; @@ -1134,8 +1143,9 @@ SimplifiedVoronoi Point another = vertex; T amount = 0.1875 * topleft(c_it); transform(another, - ( 0.75 - amount ), - amount); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } + vertex.visible = false; } else { special = true; } @@ -1149,7 +1159,7 @@ SimplifiedVoronoi } if ( special ) { - cells_it->vertices.push_back(vertex); + cells_it->vertices.push_back(vertex.invisible()); { Point another = vertex; T amount = 0.1875; @@ -1159,7 +1169,7 @@ SimplifiedVoronoi - ( 0.75 - ( topleft(b_it) + topright(a_it) ) * amount )); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } { Point another = vertex; @@ -1181,7 +1191,7 @@ SimplifiedVoronoi // y 0.25 - amount * ( bottomleft(d_it) + bottomright(c_it) )); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } { transform(vertex, @@ -1192,6 +1202,7 @@ SimplifiedVoronoi ( topleft(b_it) - bottomleft(d_it) + topright(a_it) - bottomright(c_it) ) * 0.03125); + vertex.visible = false; } } } else if ( right(c_it) ) { @@ -1212,12 +1223,12 @@ SimplifiedVoronoi if ( !vertex.smooth ) { if ( similar_neighbor_is_contour ) { - cells_it->vertices.push_back(vertex); + cells_it->vertices.push_back(vertex.invisible()); { Point another = vertex; T amount = 0.1875 * topleft(b_it); transform(another, - amount, - ( 0.75 - amount )); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } { Point another = vertex; @@ -1230,12 +1241,13 @@ SimplifiedVoronoi Point another = vertex; T amount = 0.0625 * bottomright(b_it); transform(another, 0.25 - amount, amount); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } { T amount = 0.125 - 0.03125 * (topleft(b_it) + bottomright(b_it)); transform(vertex, amount, - amount); + vertex.visible = false; } } else { special = true; @@ -1261,7 +1273,7 @@ SimplifiedVoronoi - amount * ( topleft(c_it) + topright(d_it) - bottomleft(a_it) - bottomright(b_it) )); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } { Point another = vertex; @@ -1272,7 +1284,7 @@ SimplifiedVoronoi // y - amount * ( topright(d_it) - bottomright(b_it) )); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } { Point another = vertex; @@ -1295,8 +1307,9 @@ SimplifiedVoronoi // y - amount * ( topleft(c_it) - bottomleft(a_it) )); - cells_it->vertices.push_back(another); + cells_it->vertices.push_back(another.invisible()); } + vertex.visible = false; } } else { // there is a 4-color pattern, where the current node diff --git a/src/libdepixelize/priv/splines-kopf2011.h b/src/libdepixelize/priv/splines-kopf2011.h new file mode 100644 index 000000000..eb84c3bfb --- /dev/null +++ b/src/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 + + 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 . + + 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 . + + 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 +Geom::Path worker_helper(const std::vector< Point > &source1, bool optimize) +{ + typedef Geom::LineSegment Line; + typedef Geom::QuadraticBezier Quad; + typedef typename std::vector< Point >::const_iterator iterator; + + std::vector< Point > source; + + if ( optimize ) + source = Tracer::optimize(source1); + else + source = source1; + + iterator it = source.begin(); + Point 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(middle); + } + } + + Point next = (it + 1 == end) ? source.front() : *(it + 1); + Point middle = midpoint(*it, next); + + if ( !it->smooth ) { + ret.appendNew(to_geom_point(*it)); + ret.appendNew(to_geom_point(middle)); + } else { + ret.appendNew(to_geom_point(*it), to_geom_point(middle)); + } + + prev = *it; + } + + return ret; +} + +/** + * It should be used by worker threads. Convert only one object. + */ +template +void worker(const typename HomogeneousSplines::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 > >::const_iterator + it = source.holes.begin(), end = source.holes.end() + ; it != end ; ++it ) { + dest.pathVector.push_back(worker_helper(*it, optimize)); + } +} + +template +Splines::Splines(const SimplifiedVoronoi &diagram) : + _width(diagram.width()), + _height(diagram.height()) +{ + _paths.reserve(diagram.size()); + + for ( typename SimplifiedVoronoi::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 >::const_iterator + it2 = it->vertices.begin(), end2 = it->vertices.end() + ; it2 != end2 ; ++it2 ) { + path.pathVector.back() + .appendNew(Geom::Point(it2->x, it2->y)); + } + + for ( int i = 0 ; i != 4 ; ++i ) + path.rgba[i] = it->rgba[i]; + + _paths.push_back(path); + } +} + +template +Splines::Splines(const HomogeneousSplines &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::const_iterator + it = homogeneousSplines.begin(), end = homogeneousSplines.end() + ; it != end ; ++it, ++paths_it ) { + worker(*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/libdepixelize/priv/splines.h b/src/libdepixelize/priv/splines.h deleted file mode 100644 index c7ef2b492..000000000 --- a/src/libdepixelize/priv/splines.h +++ /dev/null @@ -1,155 +0,0 @@ -/* This file is part of the libdepixelize project - Copyright (C) 2013 Vinícius dos Santos Oliveira - - 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 . - - 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 . - - 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_PRIV_H -#define LIBDEPIXELIZE_TRACER_SPLINES_PRIV_H - -#include "../splines.h" -#include "homogeneoussplines.h" - -namespace Tracer { - -template -Geom::Point to_geom_point(Point p) -{ - return Geom::Point(p.x, p.y); -} - -template -Geom::Path worker_helper(const std::vector< Point > &source, bool optimize) -{ - typedef Geom::LineSegment Line; - typedef Geom::QuadraticBezier Quad; - typedef typename std::vector< Point >::const_iterator iterator; - - iterator it = source.begin(); - Geom::Path ret(to_geom_point((source.back() + *it) / 2)); - - for ( iterator end = --source.end() ; it != end ; ++it ) { - Point next = *(it + 1); - Point middle = (*it + next) / 2; - - if ( !it->smooth ) { - // TODO: remove redundant colinear points - ret.appendNew(Geom::Point(it->x, it->y)); - ret.appendNew(Geom::Point(middle.x, middle.y)); - } else { - ret.appendNew(Geom::Point(it->x, it->y), - Geom::Point(middle.x, middle.y)); - } - } - - { - Point next = source.front(); - Point middle = (*it + next) / 2; - - if ( !it->smooth ) { - ret.appendNew(Geom::Point(it->x, it->y)); - ret.appendNew(Geom::Point(middle.x, middle.y)); - } else { - ret.appendNew(Geom::Point(it->x, it->y), - Geom::Point(middle.x, middle.y)); - } - } - - return ret; -} - -/** - * It should be used by worker threads. Convert only one object. - */ -template -void worker(const typename HomogeneousSplines::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 > >::const_iterator - it = source.holes.begin(), end = source.holes.end() - ; it != end ; ++it ) { - dest.pathVector.push_back(worker_helper(*it, optimize)); - } -} - -template -Splines::Splines(const SimplifiedVoronoi &diagram) -{ - _paths.reserve(diagram.size()); - - for ( typename SimplifiedVoronoi::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 >::const_iterator - it2 = it->vertices.begin(), end2 = it->vertices.end() - ; it2 != end2 ; ++it2 ) { - path.pathVector.back() - .appendNew(Geom::Point(it2->x, it2->y)); - } - - for ( int i = 0 ; i != 4 ; ++i ) - path.rgba[i] = it->rgba[i]; - - _paths.push_back(path); - } -} - -template -Splines::Splines(const HomogeneousSplines &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::const_iterator - it = homogeneousSplines.begin(), end = homogeneousSplines.end() - ; it != end ; ++it, ++paths_it ) { - worker(*it, *paths_it, optimize); - } -} - -} // namespace Tracer - -#endif // LIBDEPIXELIZE_TRACER_SPLINES_PRIV_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 : -- cgit v1.2.3 From 4b879c238ff2f4f52ca55c68ea3f887137e5cab6 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Vin=C3=ADcius=20dos=20Santos=20Oliveira?= Date: Wed, 25 Sep 2013 01:37:17 -0300 Subject: Updating libdepixelize version (bzr r12589) --- src/libdepixelize/kopftracer2011.cpp | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'src/libdepixelize') diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp index 50b12d527..5e6e26048 100644 --- a/src/libdepixelize/kopftracer2011.cpp +++ b/src/libdepixelize/kopftracer2011.cpp @@ -331,9 +331,16 @@ void Kopf2011::_remove_puzzle_pattern(PixelGraph &graph) + graph.nodeBottomRight(it2)->adj.top == 3 ) { // We fake a new connection =) it2->adj.right = true; + graph.nodeRight(it2)->adj.left = true; + it2->adj.bottom = true; + graph.nodeBottom(it2)->adj.top = true; + graph.nodeBottomRight(it2)->adj.left = true; + graph.nodeBottom(it2)->adj.right = true; + graph.nodeBottomRight(it2)->adj.top = true; + graph.nodeRight(it2)->adj.bottom = true; } it2 = graph.nodeRight(it2); -- cgit v1.2.3 From b8c53ea8a7e75e863d207b39fd570f5f0212c63f Mon Sep 17 00:00:00 2001 From: Ryan Lerch <> Date: Wed, 25 Sep 2013 16:22:43 +0200 Subject: Fix make dist Fixed bugs: - https://launchpad.net/bugs/1230298 (bzr r12591) --- src/libdepixelize/Makefile_insert | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/libdepixelize') diff --git a/src/libdepixelize/Makefile_insert b/src/libdepixelize/Makefile_insert index b5be88c5f..8aed7244f 100644 --- a/src/libdepixelize/Makefile_insert +++ b/src/libdepixelize/Makefile_insert @@ -13,7 +13,7 @@ libdepixelize_libdepixelize_a_SOURCES = \ libdepixelize/priv/colorspace.h \ libdepixelize/priv/curvature.h \ libdepixelize/priv/homogeneoussplines.h \ - libdepixelize/priv/integral \ + libdepixelize/priv/integral.h \ libdepixelize/priv/iterator.h \ libdepixelize/priv/optimization-kopf2011.h \ libdepixelize/priv/pixelgraph.h \ -- cgit v1.2.3 From 858a1a2d5395cca9f26b32c305d8c7d1dcd3c9b4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Vin=C3=ADcius=20dos=20Santos=20Oliveira?= Date: Sat, 5 Oct 2013 23:09:30 -0300 Subject: Bumping a new release of libdepixelize (bzr r12663) --- ...PLEASE DON'T MAKE CHANGES IN THESE FILES.README | 9 + src/libdepixelize/kopftracer2011.cpp | 54 +-- src/libdepixelize/kopftracer2011.h | 10 +- src/libdepixelize/priv/simplifiedvoronoi.h | 391 ++++++++++++++------- src/libdepixelize/priv/splines-kopf2011.h | 10 +- src/libdepixelize/splines.h | 6 +- 6 files changed, 299 insertions(+), 181 deletions(-) create mode 100644 src/libdepixelize/!PLEASE DON'T MAKE CHANGES IN THESE FILES.README (limited to 'src/libdepixelize') diff --git a/src/libdepixelize/!PLEASE DON'T MAKE CHANGES IN THESE FILES.README b/src/libdepixelize/!PLEASE DON'T MAKE CHANGES IN THESE FILES.README new file mode 100644 index 000000000..df63435d6 --- /dev/null +++ b/src/libdepixelize/!PLEASE DON'T MAKE CHANGES IN THESE FILES.README @@ -0,0 +1,9 @@ +All code files in this directory are *direct* copies of the files in +libdepixelize's BZR repo. +If you want to change the code, please change it in libdepixelize, then copy the +files here. +Otherwise, I will probably miss that you changed something in Inkscape's copy, +and destroy your changes by copying libdepixelize's files over it during the +next time I update Inkscape's copy of libdepixelize. + +libdepixelize's BZR repo = lp:libdepixelize diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp index 5e6e26048..95f91fdcb 100644 --- a/src/libdepixelize/kopftracer2011.cpp +++ b/src/libdepixelize/kopftracer2011.cpp @@ -86,7 +86,7 @@ Splines Kopf2011::to_voronoi(const std::string &filename, Splines Kopf2011::to_voronoi(const Glib::RefPtr &buf, const Options &options) { - return Splines(_voronoi(buf, options)); + return Splines(_voronoi(buf, options)); } Splines Kopf2011::to_splines(const std::string &filename, @@ -98,13 +98,15 @@ Splines Kopf2011::to_splines(const std::string &filename, Splines Kopf2011::to_splines(const Glib::RefPtr &buf, const Options &options) { - HomogeneousSplines splines(_voronoi(buf, options)); + HomogeneousSplines splines(_voronoi + (buf, options)); return Splines(splines, options.optimize, options.nthreads); } -template -SimplifiedVoronoi Kopf2011::_voronoi(const Glib::RefPtr &buf, - const Options &options) +template +SimplifiedVoronoi +Kopf2011::_voronoi(const Glib::RefPtr &buf, + const Options &options) { PixelGraph graph(buf); @@ -146,13 +148,7 @@ SimplifiedVoronoi Kopf2011::_voronoi(const Glib::RefPtr &b graph.checkConsistency(); #endif - _remove_puzzle_pattern(graph); - -#ifndef NDEBUG - graph.checkConsistency(); -#endif - - return SimplifiedVoronoi(graph); + return SimplifiedVoronoi(graph); } // TODO: move this function (plus connectAllNeighbors) to PixelGraph constructor @@ -315,40 +311,6 @@ void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, } } -inline -void Kopf2011::_remove_puzzle_pattern(PixelGraph &graph) -{ - if ( graph.width() < 2 || graph.height() < 2 ) - return; - - PixelGraph::iterator it = graph.begin(); - for ( int i = 0 ; i + 1 != graph.height() ; ++i ) { - PixelGraph::iterator it2 = it; - for ( int j = 0 ; j + 1 != graph.width() ; ++j ) { - // Evil pattern currently not handled correctly in SimplifiedVoronoi - if ( it2->adj.right + it2->adj.bottom - + graph.nodeBottomRight(it2)->adj.left - + graph.nodeBottomRight(it2)->adj.top == 3 ) { - // We fake a new connection =) - it2->adj.right = true; - graph.nodeRight(it2)->adj.left = true; - - it2->adj.bottom = true; - graph.nodeBottom(it2)->adj.top = true; - - graph.nodeBottomRight(it2)->adj.left = true; - graph.nodeBottom(it2)->adj.right = true; - - graph.nodeBottomRight(it2)->adj.top = true; - graph.nodeRight(it2)->adj.bottom = true; - } - - it2 = graph.nodeRight(it2); - } - it = graph.nodeBottom(it); - } -} - inline int Heuristics::curves(const PixelGraph &graph, PixelGraph::const_iterator a, PixelGraph::const_iterator b) diff --git a/src/libdepixelize/kopftracer2011.h b/src/libdepixelize/kopftracer2011.h index aff39d3d8..c224abe9a 100644 --- a/src/libdepixelize/kopftracer2011.h +++ b/src/libdepixelize/kopftracer2011.h @@ -35,8 +35,6 @@ namespace Tracer { class PixelGraph; -template class SimplifiedVoronoi; -template class HomogeneousSplines; class Kopf2011 { @@ -102,15 +100,15 @@ public: private: typedef Geom::Coord Precision; - template - static SimplifiedVoronoi _voronoi(const Glib::RefPtr &buf, - const Options &options); + template + static SimplifiedVoronoi + _voronoi(const Glib::RefPtr &buf, + const Options &options); static void _disconnect_neighbors_with_dissimilar_colors(PixelGraph &graph); static void _remove_crossing_edges_safe(PixelGraph &graph); static void _remove_crossing_edges_unsafe(PixelGraph &graph, const Options &options); - static void _remove_puzzle_pattern(PixelGraph &graph); }; } // namespace Tracer diff --git a/src/libdepixelize/priv/simplifiedvoronoi.h b/src/libdepixelize/priv/simplifiedvoronoi.h index d5ebc36e5..8a25bc626 100644 --- a/src/libdepixelize/priv/simplifiedvoronoi.h +++ b/src/libdepixelize/priv/simplifiedvoronoi.h @@ -32,7 +32,7 @@ namespace Tracer { -template +template class SimplifiedVoronoi { public: @@ -121,8 +121,10 @@ public: } private: +#ifdef LIBDEPIXELIZE_VERY_TYPE_SAFE typedef void (*PointTransform)(Point &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. @@ -221,6 +223,9 @@ private: * indirection, except for the problem of too many layers of indirection." * -- David J. Wheeler */ +#ifndef LIBDEPIXELIZE_VERY_TYPE_SAFE + template +#endif // LIBDEPIXELIZE_VERY_TYPE_SAFE void _genericComplexBottomRight(PixelGraph::const_iterator a_it, PixelGraph::const_iterator b_it, PixelGraph::const_iterator c_it, @@ -241,8 +246,9 @@ private: std::vector _cells; }; -template -SimplifiedVoronoi::SimplifiedVoronoi(const PixelGraph &graph) : +template +SimplifiedVoronoi +::SimplifiedVoronoi(const PixelGraph &graph) : _width(graph.width()), _height(graph.height()), _cells(graph.size()) @@ -481,10 +487,11 @@ SimplifiedVoronoi::SimplifiedVoronoi(const PixelGraph &graph) : } } -template void -SimplifiedVoronoi::_complexTopLeft(const PixelGraph &graph, - PixelGraph::const_iterator graph_it, - Cell *const cells_it, int x, int y) +template void +SimplifiedVoronoi +::_complexTopLeft(const PixelGraph &graph, + PixelGraph::const_iterator graph_it, Cell *const cells_it, + int x, int y) { _genericComplexBottomRight(graph_it, graph.nodeLeft(graph_it), @@ -502,10 +509,11 @@ SimplifiedVoronoi::_complexTopLeft(const PixelGraph &graph, &SimplifiedVoronoi::_complexTopLeftTransformTopLeft); } -template void -SimplifiedVoronoi::_complexTopRight(const PixelGraph &graph, - PixelGraph::const_iterator graph_it, - Cell *const cells_it, int x, int y) +template void +SimplifiedVoronoi +::_complexTopRight(const PixelGraph &graph, + PixelGraph::const_iterator graph_it, Cell *const cells_it, + int x, int y) { _genericComplexBottomRight(graph_it, graph.nodeTop(graph_it), @@ -523,10 +531,11 @@ SimplifiedVoronoi::_complexTopRight(const PixelGraph &graph, &SimplifiedVoronoi::_complexTopRightTransformTopLeft); } -template void -SimplifiedVoronoi::_complexBottomRight(const PixelGraph &graph, - PixelGraph::const_iterator graph_it, - Cell *const cells_it, int x, int y) +template void +SimplifiedVoronoi +::_complexBottomRight(const PixelGraph &graph, + PixelGraph::const_iterator graph_it, Cell *const cells_it, + int x, int y) { _genericComplexBottomRight(graph_it, graph.nodeRight(graph_it), @@ -544,10 +553,11 @@ SimplifiedVoronoi::_complexBottomRight(const PixelGraph &graph, &SimplifiedVoronoi::_complexBottomRightTransformTopLeft); } -template void -SimplifiedVoronoi::_complexBottomLeft(const PixelGraph &graph, - PixelGraph::const_iterator graph_it, - Cell *const cells_it, int x, int y) +template void +SimplifiedVoronoi +::_complexBottomLeft(const PixelGraph &graph, + PixelGraph::const_iterator graph_it, Cell *const cells_it, + int x, int y) { _genericComplexBottomRight(graph_it, graph.nodeBottom(graph_it), @@ -565,229 +575,268 @@ SimplifiedVoronoi::_complexBottomLeft(const PixelGraph &graph, &SimplifiedVoronoi::_complexBottomLeftTransformTopLeft); } -template void -SimplifiedVoronoi::_complexTopLeftTransform(Point &p, T dx, T dy) +template void +SimplifiedVoronoi +::_complexTopLeftTransform(Point &p, T dx, T dy) { p.x -= dx; p.y -= dy; } -template void -SimplifiedVoronoi::_complexTopRightTransform(Point &p, T dx, T dy) +template void +SimplifiedVoronoi +::_complexTopRightTransform(Point &p, T dx, T dy) { p.x += dy; p.y -= dx; } -template void -SimplifiedVoronoi::_complexBottomRightTransform(Point &p, T dx, T dy) +template void +SimplifiedVoronoi +::_complexBottomRightTransform(Point &p, T dx, T dy) { p.x += dx; p.y += dy; } -template void -SimplifiedVoronoi::_complexBottomLeftTransform(Point &p, T dx, T dy) +template void +SimplifiedVoronoi +::_complexBottomLeftTransform(Point &p, T dx, T dy) { p.x -= dy; p.y += dx; } -template -bool SimplifiedVoronoi::_complexTopLeftTransformTop(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexTopLeftTransformTop(PixelGraph::const_iterator graph_it) { return graph_it->adj.bottom; } -template -bool SimplifiedVoronoi::_complexTopLeftTransformTopRight(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexTopLeftTransformTopRight(PixelGraph::const_iterator graph_it) { return graph_it->adj.bottomleft; } -template -bool SimplifiedVoronoi::_complexTopLeftTransformRight(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexTopLeftTransformRight(PixelGraph::const_iterator graph_it) { return graph_it->adj.left; } -template -bool SimplifiedVoronoi::_complexTopLeftTransformBottomRight(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexTopLeftTransformBottomRight(PixelGraph::const_iterator graph_it) { return graph_it->adj.topleft; } -template -bool SimplifiedVoronoi::_complexTopLeftTransformBottom(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexTopLeftTransformBottom(PixelGraph::const_iterator graph_it) { return graph_it->adj.top; } -template -bool SimplifiedVoronoi::_complexTopLeftTransformBottomLeft(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexTopLeftTransformBottomLeft(PixelGraph::const_iterator graph_it) { return graph_it->adj.topright; } -template -bool SimplifiedVoronoi::_complexTopLeftTransformLeft(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexTopLeftTransformLeft(PixelGraph::const_iterator graph_it) { return graph_it->adj.right; } -template -bool SimplifiedVoronoi::_complexTopLeftTransformTopLeft(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexTopLeftTransformTopLeft(PixelGraph::const_iterator graph_it) { return graph_it->adj.bottomright; } -template -bool SimplifiedVoronoi::_complexTopRightTransformTop(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexTopRightTransformTop(PixelGraph::const_iterator graph_it) { return graph_it->adj.left; } -template -bool SimplifiedVoronoi::_complexTopRightTransformTopRight(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexTopRightTransformTopRight(PixelGraph::const_iterator graph_it) { return graph_it->adj.topleft; } -template -bool SimplifiedVoronoi::_complexTopRightTransformRight(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexTopRightTransformRight(PixelGraph::const_iterator graph_it) { return graph_it->adj.top; } -template -bool SimplifiedVoronoi::_complexTopRightTransformBottomRight(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexTopRightTransformBottomRight(PixelGraph::const_iterator graph_it) { return graph_it->adj.topright; } -template -bool SimplifiedVoronoi::_complexTopRightTransformBottom(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexTopRightTransformBottom(PixelGraph::const_iterator graph_it) { return graph_it->adj.right; } -template -bool SimplifiedVoronoi::_complexTopRightTransformBottomLeft(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexTopRightTransformBottomLeft(PixelGraph::const_iterator graph_it) { return graph_it->adj.bottomright; } -template -bool SimplifiedVoronoi::_complexTopRightTransformLeft(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexTopRightTransformLeft(PixelGraph::const_iterator graph_it) { return graph_it->adj.bottom; } -template -bool SimplifiedVoronoi::_complexTopRightTransformTopLeft(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexTopRightTransformTopLeft(PixelGraph::const_iterator graph_it) { return graph_it->adj.bottomleft; } -template -bool SimplifiedVoronoi::_complexBottomRightTransformTop(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexBottomRightTransformTop(PixelGraph::const_iterator graph_it) { return graph_it->adj.top; } -template -bool SimplifiedVoronoi::_complexBottomRightTransformTopRight(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexBottomRightTransformTopRight(PixelGraph::const_iterator graph_it) { return graph_it->adj.topright; } -template -bool SimplifiedVoronoi::_complexBottomRightTransformRight(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexBottomRightTransformRight(PixelGraph::const_iterator graph_it) { return graph_it->adj.right; } -template -bool SimplifiedVoronoi::_complexBottomRightTransformBottomRight(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexBottomRightTransformBottomRight(PixelGraph::const_iterator graph_it) { return graph_it->adj.bottomright; } -template -bool SimplifiedVoronoi::_complexBottomRightTransformBottom(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexBottomRightTransformBottom(PixelGraph::const_iterator graph_it) { return graph_it->adj.bottom; } -template -bool SimplifiedVoronoi::_complexBottomRightTransformBottomLeft(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexBottomRightTransformBottomLeft(PixelGraph::const_iterator graph_it) { return graph_it->adj.bottomleft; } -template -bool SimplifiedVoronoi::_complexBottomRightTransformLeft(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexBottomRightTransformLeft(PixelGraph::const_iterator graph_it) { return graph_it->adj.left; } -template -bool SimplifiedVoronoi::_complexBottomRightTransformTopLeft(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexBottomRightTransformTopLeft(PixelGraph::const_iterator graph_it) { return graph_it->adj.topleft; } -template -bool SimplifiedVoronoi::_complexBottomLeftTransformTop(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexBottomLeftTransformTop(PixelGraph::const_iterator graph_it) { return graph_it->adj.right; } -template -bool SimplifiedVoronoi::_complexBottomLeftTransformTopRight(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexBottomLeftTransformTopRight(PixelGraph::const_iterator graph_it) { return graph_it->adj.bottomright; } -template -bool SimplifiedVoronoi::_complexBottomLeftTransformRight(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexBottomLeftTransformRight(PixelGraph::const_iterator graph_it) { return graph_it->adj.bottom; } -template -bool SimplifiedVoronoi::_complexBottomLeftTransformBottomRight(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexBottomLeftTransformBottomRight(PixelGraph::const_iterator graph_it) { return graph_it->adj.bottomleft; } -template -bool SimplifiedVoronoi::_complexBottomLeftTransformBottom(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexBottomLeftTransformBottom(PixelGraph::const_iterator graph_it) { return graph_it->adj.left; } -template -bool SimplifiedVoronoi::_complexBottomLeftTransformBottomLeft(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexBottomLeftTransformBottomLeft(PixelGraph::const_iterator graph_it) { return graph_it->adj.topleft; } -template -bool SimplifiedVoronoi::_complexBottomLeftTransformLeft(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexBottomLeftTransformLeft(PixelGraph::const_iterator graph_it) { return graph_it->adj.top; } -template -bool SimplifiedVoronoi::_complexBottomLeftTransformTopLeft(PixelGraph::const_iterator graph_it) +template +bool SimplifiedVoronoi +::_complexBottomLeftTransformTopLeft(PixelGraph::const_iterator graph_it) { return graph_it->adj.topright; } -template +template +#ifndef LIBDEPIXELIZE_VERY_TYPE_SAFE +template +#endif // LIBDEPIXELIZE_VERY_TYPE_SAFE void -SimplifiedVoronoi +SimplifiedVoronoi ::_genericComplexBottomRight(PixelGraph::const_iterator a_it, PixelGraph::const_iterator b_it, PixelGraph::const_iterator c_it, @@ -817,8 +866,12 @@ SimplifiedVoronoi // this and bottom-right are connected bool smooth[2] = { - same_color(a_it->rgba, d_it->rgba) || right(a_it), - same_color(a_it->rgba, d_it->rgba) || bottom(a_it) + ( 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 borderMid = initial; @@ -836,7 +889,7 @@ SimplifiedVoronoi vertices[1] = _adjust(midpoint(borderMid, vertices[1]), smooth[1]); } - if ( !smooth[0] ) { + if ( !smooth[0] && adjust_splines ) { cells_it->vertices.push_back(vertices[0].invisible()); { Point another = vertices[0]; @@ -885,7 +938,7 @@ SimplifiedVoronoi cells_it->vertices.push_back(vertices[0]); - if ( !smooth[1] ) { + if ( !smooth[1] && adjust_splines ) { { Point another = vertices[1]; transform(another, @@ -954,7 +1007,7 @@ SimplifiedVoronoi vertex = _adjust(midpoint(initial, vertex)); // compute smoothness - if ( right(a_it) ) { + if ( right(a_it) && adjust_splines ) { // this and right are connected if ( !right(c_it) && !( bottom(a_it) && bottom(b_it) ) ) { @@ -1006,11 +1059,65 @@ SimplifiedVoronoi * 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 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) )); + cells_it->vertices.push_back(another.invisible()); + } + { + Point 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) )); + cells_it->vertices.push_back(another.invisible()); + } + { + Point 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; + cells_it->vertices.push_back(another); + } + { + Point 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) )); + cells_it->vertices.push_back(another.invisible()); + } + vertex.visible = false; } } else { // {this, right} is the pair with the angle // closest to 180 degrees - vertex.smooth = true; + vertex.smooth = same_color(a_it->rgba, b_it->rgba); } } else { // there might be 2-color, then vertex.smooth = true @@ -1018,17 +1125,12 @@ SimplifiedVoronoi // or it might be 1-color and doesn't matter, // because the current node will disappear vertex.smooth - = !( bottom(a_it) ^ bottom(b_it) ); - - if ( vertex.smooth ) { - 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; - } + = 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) ) { + } else if ( bottom(a_it) && adjust_splines ) { // this and bottom are connected if ( !bottom(b_it) && !( right(a_it) && right(c_it) ) ) { @@ -1079,28 +1181,75 @@ SimplifiedVoronoi * 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 + cells_it->vertices.push_back(vertex.invisible()); + { + Point 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 )); + cells_it->vertices.push_back(another.invisible()); + } + { + Point 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; + cells_it->vertices.push_back(another); + } + { + Point 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) )); + cells_it->vertices.push_back(another.invisible()); + } + { + 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); + vertex.visible = false; + } } } else { // {this, bottom} is the pair with the angle // closest to 180 degrees - vertex.smooth = true; + 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 = !( right(a_it) ^ right(c_it) ); - - if ( vertex.smooth ) { - 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; - } + 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) ) { + } else if ( bottom(b_it) && adjust_splines ) { // right and bottom-right are connected bool special = false; @@ -1205,7 +1354,7 @@ SimplifiedVoronoi vertex.visible = false; } } - } else if ( right(c_it) ) { + } else if ( right(c_it) && adjust_splines ) { // bottom and bottom-right are connected bool special = false; diff --git a/src/libdepixelize/priv/splines-kopf2011.h b/src/libdepixelize/priv/splines-kopf2011.h index eb84c3bfb..fb4f8ba1e 100644 --- a/src/libdepixelize/priv/splines-kopf2011.h +++ b/src/libdepixelize/priv/splines-kopf2011.h @@ -107,22 +107,22 @@ void worker(const typename HomogeneousSplines::Polygon &source, } } -template -Splines::Splines(const SimplifiedVoronoi &diagram) : +template +Splines::Splines(const SimplifiedVoronoi &diagram) : _width(diagram.width()), _height(diagram.height()) { _paths.reserve(diagram.size()); - for ( typename SimplifiedVoronoi::const_iterator it = diagram.begin() - , end = diagram.end() ; it != end ; ++it ) { + for ( typename SimplifiedVoronoi::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 >::const_iterator - it2 = it->vertices.begin(), end2 = it->vertices.end() + it2 = ++it->vertices.begin(), end2 = it->vertices.end() ; it2 != end2 ; ++it2 ) { path.pathVector.back() .appendNew(Geom::Point(it2->x, it2->y)); diff --git a/src/libdepixelize/splines.h b/src/libdepixelize/splines.h index c4b455aae..b06ba8ba9 100644 --- a/src/libdepixelize/splines.h +++ b/src/libdepixelize/splines.h @@ -30,7 +30,7 @@ namespace Tracer { -template +template class SimplifiedVoronoi; template @@ -54,8 +54,8 @@ public: Splines() /* = default */ {} - template - Splines(const SimplifiedVoronoi &simplifiedVoronoi); + template + Splines(const SimplifiedVoronoi &simplifiedVoronoi); /** * There are two levels of optimization. The first level only removes -- cgit v1.2.3 From 1a36f75406b76a837ac8d79719a7c23f8d693fed Mon Sep 17 00:00:00 2001 From: Kris De Gussem Date: Mon, 7 Oct 2013 21:25:41 +0200 Subject: cppcheck (bzr r12669) --- src/libdepixelize/kopftracer2011.cpp | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'src/libdepixelize') diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp index 95f91fdcb..ab31d05c3 100644 --- a/src/libdepixelize/kopftracer2011.cpp +++ b/src/libdepixelize/kopftracer2011.cpp @@ -336,8 +336,7 @@ inline int Heuristics::curves(const PixelGraph &graph, { // There are only two values that won't be zero'ed // and one of them has the same value of prev - guintptr aux = guintptr(to_ptr(it)); - aux = (it->adj.top + guintptr aux = (it->adj.top * guintptr(to_ptr(graph.nodeTop(it)))) + (it->adj.topright * guintptr(to_ptr(graph.nodeTopRight(it)))) -- cgit v1.2.3 From 2a512b54b57ae53464601b38b05eab6f6c3cf3c4 Mon Sep 17 00:00:00 2001 From: Kris De Gussem Date: Tue, 22 Oct 2013 16:50:54 +0200 Subject: cppcheck (bzr r12713) --- src/libdepixelize/priv/point.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/libdepixelize') diff --git a/src/libdepixelize/priv/point.h b/src/libdepixelize/priv/point.h index dc28a2b84..53babd9dc 100644 --- a/src/libdepixelize/priv/point.h +++ b/src/libdepixelize/priv/point.h @@ -30,8 +30,8 @@ namespace Tracer { template struct Point { - Point() : visible(true) {} - Point(T x, T y) : visible(true), x(x), y(y) {} + 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 -- cgit v1.2.3 From c9056cd134852d1d1cb46f2a7c5a115b8e8322cc Mon Sep 17 00:00:00 2001 From: Kris De Gussem Date: Wed, 13 Nov 2013 21:50:14 +0100 Subject: fix warning (bzr r12811) --- src/libdepixelize/priv/splines-kopf2011.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/libdepixelize') diff --git a/src/libdepixelize/priv/splines-kopf2011.h b/src/libdepixelize/priv/splines-kopf2011.h index fb4f8ba1e..c586f74b7 100644 --- a/src/libdepixelize/priv/splines-kopf2011.h +++ b/src/libdepixelize/priv/splines-kopf2011.h @@ -137,7 +137,7 @@ Splines::Splines(const SimplifiedVoronoi &diagram) : template Splines::Splines(const HomogeneousSplines &homogeneousSplines, - bool optimize, int nthreads) : + bool optimize, int /*nthreads*/) : _paths(homogeneousSplines.size()), _width(homogeneousSplines.width()), _height(homogeneousSplines.height()) -- cgit v1.2.3 From 3e3246729a56694574405f5d72307f536d05dcad Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Vin=C3=ADcius=20dos=20Santos=20Oliveira?= Date: Mon, 24 Mar 2014 22:34:31 -0300 Subject: Updating libdepixelize. This update is not focused on new features, but on stability. Bugs affecting weird image sizes (single line or single row images) were fixed. A bug on algorithm that could cause wrong result of heuristics on very rare images was also fixed. The correct behaviour required storing all votes before really doing any removal and this extra work made this step of the algorithm 328% slower on one sample image. If the old *_safe function was used, the slowdown could be decreased to 7.7% on the same sample image, but current focus on Inkscape timeline is stabilization, then I'll delay performance optimization to later. Also, the affected step is only responsible for 18% (on the maximum case) of the performance. The performance tests were done using new profiling code that is disabled by default and shouldn't impact stability. (bzr r13209) --- src/libdepixelize/kopftracer2011.cpp | 415 ++++++++++++++++++++-------- src/libdepixelize/kopftracer2011.h | 26 +- src/libdepixelize/priv/homogeneoussplines.h | 21 +- src/libdepixelize/priv/pixelgraph.h | 80 +++++- src/libdepixelize/priv/simplifiedvoronoi.h | 271 ++++++++++++++++-- 5 files changed, 655 insertions(+), 158 deletions(-) (limited to 'src/libdepixelize') diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp index ab31d05c3..e2f387c86 100644 --- a/src/libdepixelize/kopftracer2011.cpp +++ b/src/libdepixelize/kopftracer2011.cpp @@ -31,7 +31,6 @@ #include #endif -#include #include #include "kopftracer2011.h" #include "priv/colorspace.h" @@ -40,6 +39,11 @@ #include "priv/splines-kopf2011.h" #include "priv/iterator.h" +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 +#include +#include +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 + namespace Tracer { namespace Heuristics { @@ -86,7 +90,95 @@ Splines Kopf2011::to_voronoi(const std::string &filename, Splines Kopf2011::to_voronoi(const Glib::RefPtr &buf, const Options &options) { +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + SimplifiedVoronoi voronoi + = _voronoi(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(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 &buf, + const Options &options) +{ +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + SimplifiedVoronoi voronoi + = _voronoi(buf, options); + + Glib::DateTime profiling_info[2]; + profiling_info[0] = Glib::DateTime::create_now_utc(); + + HomogeneousSplines splines(voronoi); + +#else // LIBDEPIXELIZE_PROFILE_KOPF2011 + HomogeneousSplines splines(_voronoi + (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::iterator it = splines.begin(), + end = splines.end() ; it != end ; ++it ) { + for ( HomogeneousSplines::Polygon::points_iter + it2 = it->vertices.begin(), end2 = it->vertices.end() + ; it2 != end2 ; ++it2 ) { + it2->smooth = false; + } + for ( HomogeneousSplines::Polygon::holes_iter + it2 = it->holes.begin(), end2 = it->holes.end() + ; it2 != end2 ; ++it2 ) { + for ( HomogeneousSplines::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, @@ -98,9 +190,36 @@ Splines Kopf2011::to_splines(const std::string &filename, Splines Kopf2011::to_splines(const Glib::RefPtr &buf, const Options &options) { +#ifdef LIBDEPIXELIZE_PROFILE_KOPF2011 + SimplifiedVoronoi voronoi + = _voronoi(buf, options); + + Glib::DateTime profiling_info[2]; + profiling_info[0] = Glib::DateTime::create_now_utc(); + + HomogeneousSplines 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 splines(_voronoi (buf, options)); return Splines(splines, options.optimize, options.nthreads); +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 } template @@ -108,47 +227,131 @@ SimplifiedVoronoi Kopf2011::_voronoi(const Glib::RefPtr &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); - /*if ( !graph.width() || !graph.height() ) - return;*/ +#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 - // This and below steps must be executed in separate. - // Otherwise, there will be colateral effects due to misassumption about the - // data being read. - _remove_crossing_edges_safe(graph); +#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(); + graph.checkConsistency(); #endif - _remove_crossing_edges_unsafe(graph, options); +#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 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(graph); +#endif // LIBDEPIXELIZE_PROFILE_KOPF2011 } // TODO: move this function (plus connectAllNeighbors) to PixelGraph constructor @@ -192,123 +395,115 @@ Kopf2011::_disconnect_neighbors_with_dissimilar_colors(PixelGraph &graph) * * In this case the two diagonal connections can be safely removed without * affecting the final result. - * - * \TODO: It should remember/cache who are the unsafe crossing edges? */ -inline void Kopf2011::_remove_crossing_edges_safe(PixelGraph &graph) +template +void Kopf2011::_remove_crossing_edges_safe(T &container) { - if ( graph.width() < 2 || graph.height() < 2 ) - return; - - PixelGraph::iterator it = graph.begin(); - for ( int i = 0 ; i != graph.height() - 1 ; ++i, ++it ) { - for ( int j = 0 ; j != graph.width() - 1 ; ++j, ++it ) { - // this <-> right - if ( !it->adj.right ) - continue; - - // this <-> down - if ( !it->adj.bottom ) - continue; - - PixelGraph::iterator down_right = it + graph.width() + 1; - - // down_right <-> right - if ( !down_right->adj.top ) - continue; + 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; + } - // down_right <-> down - if ( !down_right->adj.left ) - continue; + // main diagonal + a->adj.bottomright = 0; + d->adj.topleft = 0; - // main diagonal - // this <-> down_right - it->adj.bottomright = 0; - down_right->adj.topleft = 0; + // secondary diagonal + b->adj.bottomleft = 0; + c->adj.topright = 0; - // secondary diagonal - // right <-> down - (it + 1)->adj.bottomleft = 0; - (it + graph.width())->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. */ -inline -void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, +template +void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph, T &edges, const Options &options) { - if ( graph.width() < 2 || graph.height() < 2 ) - return; - - // Iterate over the graph, 2x2 blocks at time - PixelGraph::iterator it = graph.begin(); - for (int i = 0 ; i != graph.height() - 1 ; ++i, ++it ) { - for ( int j = 0 ; j != graph.width() - 1 ; ++j, ++it ) { - using std::pair; - using std::make_pair; - - typedef pair Edge; - typedef pair EdgeWeight; - - EdgeWeight diagonals[2] = { - make_pair(make_pair(it, graph.nodeBottomRight(it)), 0), - make_pair(make_pair(graph.nodeRight(it), graph.nodeBottom(it)), - 0) - }; - - // Check if there are crossing edges - if ( !diagonals[0].first.first->adj.bottomright - || !diagonals[1].first.first->adj.bottomleft ) { - continue; - } - - // Compute weights - for ( int i = 0 ; i != 2 ; ++i ) { - // Curves and islands heuristics - PixelGraph::const_iterator a = diagonals[i].first.first; - PixelGraph::const_iterator b = diagonals[i].first.second; - - diagonals[i].second += Heuristics::curves(graph, a, b) - * options.curvesMultiplier; - - diagonals[i].second += Heuristics::islands(a, b) - * options.islandsWeight; - } - - { - // Sparse pixels heuristic - Heuristics::SparsePixels sparse_pixels; - - for ( int i = 0 ; i != 2 ; ++i ) - sparse_pixels.diagonals[i] = diagonals[i]; - - sparse_pixels(graph, options.sparsePixelsRadius); - - for ( int i = 0 ; i != 2 ; ++i ) { - diagonals[i].second += sparse_pixels.diagonals[i].second - * options.sparsePixelsMultiplier; - } - } + std::vector< std::pair > 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 - if ( diagonals[0].second > diagonals[1].second ) { - diagonals[1].first.first->adj.bottomleft = 0; - diagonals[1].first.second->adj.topright = 0; - } else if ( diagonals[0].second < diagonals[1].second ) { - diagonals[0].first.first->adj.bottomright = 0; - diagonals[0].first.second->adj.topleft = 0; - } else { - diagonals[0].first.first->adj.bottomright = 0; - diagonals[0].first.second->adj.topleft = 0; - diagonals[1].first.first->adj.bottomleft = 0; - diagonals[1].first.second->adj.topright = 0; - } + // 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, diff --git a/src/libdepixelize/kopftracer2011.h b/src/libdepixelize/kopftracer2011.h index c224abe9a..598f6c79c 100644 --- a/src/libdepixelize/kopftracer2011.h +++ b/src/libdepixelize/kopftracer2011.h @@ -85,6 +85,23 @@ public: static Splines to_voronoi(const Glib::RefPtr &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 &buf, + const Options &options = Options()); + /** * # Exceptions * @@ -106,8 +123,13 @@ private: const Options &options); static void _disconnect_neighbors_with_dissimilar_colors(PixelGraph &graph); - static void _remove_crossing_edges_safe(PixelGraph &graph); - static void _remove_crossing_edges_unsafe(PixelGraph &graph, + + // here, T/template is only used as an easy way to not expose internal + // symbols + template + static void _remove_crossing_edges_safe(T &container); + template + static void _remove_crossing_edges_unsafe(PixelGraph &graph, T &edges, const Options &options); }; diff --git a/src/libdepixelize/priv/homogeneoussplines.h b/src/libdepixelize/priv/homogeneoussplines.h index 57c77a163..6c4894dd8 100644 --- a/src/libdepixelize/priv/homogeneoussplines.h +++ b/src/libdepixelize/priv/homogeneoussplines.h @@ -38,6 +38,12 @@ class HomogeneousSplines public: struct Polygon { + typedef std::vector< Point > Points; + typedef typename Points::iterator points_iter; + typedef typename Points::const_iterator const_points_iter; + typedef typename std::vector::iterator holes_iter; + typedef typename std::vector::const_iterator const_holes_iter; + Polygon() {} Polygon(const guint8 (&rgba)[4]) { @@ -59,7 +65,8 @@ public: typedef typename std::vector::const_iterator const_iterator; typedef typename std::vector::size_type size_type; - HomogeneousSplines(const SimplifiedVoronoi &voronoi); + template + HomogeneousSplines(const SimplifiedVoronoi &voronoi); // Iterators iterator begin() @@ -98,12 +105,7 @@ public: } private: - typedef typename SimplifiedVoronoi::Cell Cell; typedef std::vector< Point > Points; - - typedef typename SimplifiedVoronoi::iterator voronoi_iter; - typedef typename SimplifiedVoronoi::const_iterator voronoi_citer; - typedef typename Points::iterator points_iter; typedef typename Points::const_iterator points_citer; typedef typename Points::reverse_iterator points_riter; @@ -171,7 +173,9 @@ private: }; template -HomogeneousSplines::HomogeneousSplines(const SimplifiedVoronoi &voronoi) : +template +HomogeneousSplines::HomogeneousSplines(const SimplifiedVoronoi &voronoi) : _width(voronoi.width()), _height(voronoi.height()) { @@ -179,6 +183,9 @@ HomogeneousSplines::HomogeneousSplines(const SimplifiedVoronoi &voronoi) : // return; using colorspace::same_color; + typedef typename SimplifiedVoronoi::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 ) { diff --git a/src/libdepixelize/priv/pixelgraph.h b/src/libdepixelize/priv/pixelgraph.h index 9e8c2124a..112242647 100644 --- a/src/libdepixelize/priv/pixelgraph.h +++ b/src/libdepixelize/priv/pixelgraph.h @@ -28,6 +28,7 @@ #include #include #include +#include namespace Tracer { @@ -76,6 +77,10 @@ public: typedef std::vector::reverse_iterator reverse_iterator; typedef std::vector::const_reverse_iterator const_reverse_iterator; + typedef std::pair Edge; + typedef std::pair EdgePair; + typedef std::vector EdgePairContainer; + class ColumnView { public: @@ -162,6 +167,7 @@ public: // Algorithms void connectAllNeighbors(); + EdgePairContainer crossingEdges(); int toX(const_iterator n) const { @@ -389,14 +395,23 @@ inline void PixelGraph::connectAllNeighbors() // ...then the "top" nodes... if ( _width > 2 ) { Node *it = &_nodes[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; + 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; + ++it; + } + } else { + for ( int i = 1 ; i != _width - 1 ; ++i ) { + it->adj.right = 1; + it->adj.left = 1; + + ++it; + } } } @@ -417,14 +432,23 @@ inline void PixelGraph::connectAllNeighbors() // ...then the "left" nodes... if ( _height > 2 ) { iterator it = nodeBottom(begin()); // [0][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; + 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); + it = nodeBottom(it); + } + } else { + for ( int i = 1 ; i != _height - 1 ; ++i ) { + it->adj.top = 1; + it->adj.bottom = 1; + + it = nodeBottom(it); + } } } @@ -482,6 +506,34 @@ inline void PixelGraph::connectAllNeighbors() } } +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]; diff --git a/src/libdepixelize/priv/simplifiedvoronoi.h b/src/libdepixelize/priv/simplifiedvoronoi.h index 8a25bc626..84feab08d 100644 --- a/src/libdepixelize/priv/simplifiedvoronoi.h +++ b/src/libdepixelize/priv/simplifiedvoronoi.h @@ -296,21 +296,40 @@ SimplifiedVoronoi PixelGraph::const_iterator graph_it = graph.begin() + 1; Cell *cells_it = &_cells.front() + 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]; + 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(i, 0, false)); + // Top-left + cells_it->vertices.push_back(Point(i, 0, false)); - // Top-right - cells_it->vertices.push_back(Point(i + 1, 0, false)); + // Top-right + cells_it->vertices.push_back(Point(i + 1, 0, false)); - // Bottom-right - _complexBottomRight(graph, graph_it, cells_it, i, 0); + // Bottom-right + _complexBottomRight(graph, graph_it, cells_it, i, 0); - // Bottom-left - _complexBottomLeft(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(i, 0, false)); + + // Top-right + cells_it->vertices.push_back(Point(i + 1, 0, false)); + + // Bottom-right + cells_it->vertices.push_back(Point(i + 1, 1, false)); + + // Bottom-left + cells_it->vertices.push_back(Point(i, 1, false)); + } } } @@ -344,24 +363,46 @@ SimplifiedVoronoi PixelGraph::const_iterator graph_it = graph.begin() + _width; Cell *cells_it = &_cells.front() + _width; - for ( int i = 1 ; i != _height - 1 ; ++i) { - for ( int j = 0 ; j != 4 ; ++j ) - cells_it->rgba[j] = graph_it->rgba[j]; + 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(0, i, false)); + // Top-left + cells_it->vertices.push_back(Point(0, i, false)); - // Top-right - _complexTopRight(graph, graph_it, cells_it, 0, i); + // Top-right + _complexTopRight(graph, graph_it, cells_it, 0, i); - // Bottom-right - _complexBottomRight(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(0, i + 1, false)); + // Bottom-left + cells_it->vertices.push_back(Point(0, i + 1, false)); - graph_it += _width; - cells_it += _width; + 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(0, i, false)); + + // Top-right + cells_it->vertices.push_back(Point(1, i, false)); + + // Bottom-right + cells_it->vertices.push_back(Point(1, i, false)); + + // Bottom-left + cells_it->vertices.push_back(Point(0, i + 1, false)); + + graph_it += _width; + cells_it += _width; + } } } @@ -890,7 +931,11 @@ SimplifiedVoronoi } if ( !smooth[0] && adjust_splines ) { - cells_it->vertices.push_back(vertices[0].invisible()); +#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 another = vertices[0]; transform(another, @@ -899,7 +944,11 @@ SimplifiedVoronoi // 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 another = vertices[0]; @@ -910,7 +959,11 @@ SimplifiedVoronoi - ( 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 another = vertices[0]; @@ -920,7 +973,11 @@ SimplifiedVoronoi // 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], @@ -932,7 +989,9 @@ SimplifiedVoronoi + ( 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 } } @@ -950,7 +1009,11 @@ SimplifiedVoronoi 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 another = vertices[1]; @@ -960,7 +1023,11 @@ SimplifiedVoronoi // 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 another = vertices[1]; @@ -973,7 +1040,11 @@ SimplifiedVoronoi - ( 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 another = vertices[1]; @@ -985,9 +1056,15 @@ SimplifiedVoronoi - ( 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]); @@ -1029,13 +1106,21 @@ SimplifiedVoronoi - ( ( 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 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 another = vertex; @@ -1043,16 +1128,26 @@ SimplifiedVoronoi 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 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) ) @@ -1076,7 +1171,11 @@ SimplifiedVoronoi - 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 another = vertex; @@ -1087,7 +1186,11 @@ SimplifiedVoronoi // 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 another = vertex; @@ -1099,7 +1202,11 @@ SimplifiedVoronoi - 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 another = vertex; @@ -1110,9 +1217,15 @@ SimplifiedVoronoi // 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 @@ -1146,13 +1259,21 @@ SimplifiedVoronoi 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 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 another = vertex; @@ -1160,20 +1281,30 @@ SimplifiedVoronoi 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 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 @@ -1187,7 +1318,11 @@ SimplifiedVoronoi // 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 another = vertex; T amount = 0.1875; @@ -1197,7 +1332,11 @@ SimplifiedVoronoi - ( 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 another = vertex; @@ -1209,7 +1348,11 @@ SimplifiedVoronoi - ( 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 another = vertex; @@ -1219,7 +1362,11 @@ SimplifiedVoronoi // 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, @@ -1230,7 +1377,9 @@ SimplifiedVoronoi ( 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 { @@ -1273,28 +1422,46 @@ SimplifiedVoronoi - ( 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 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 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 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; } @@ -1308,7 +1475,11 @@ SimplifiedVoronoi } 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 another = vertex; T amount = 0.1875; @@ -1318,7 +1489,11 @@ SimplifiedVoronoi - ( 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 another = vertex; @@ -1330,7 +1505,11 @@ SimplifiedVoronoi - ( 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 another = vertex; @@ -1340,7 +1519,11 @@ SimplifiedVoronoi // 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, @@ -1351,7 +1534,9 @@ SimplifiedVoronoi ( 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 ) { @@ -1372,31 +1557,49 @@ SimplifiedVoronoi 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 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 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 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; @@ -1422,7 +1625,11 @@ SimplifiedVoronoi - 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 another = vertex; @@ -1433,7 +1640,11 @@ SimplifiedVoronoi // 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 another = vertex; @@ -1445,7 +1656,11 @@ SimplifiedVoronoi - 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 another = vertex; @@ -1456,9 +1671,15 @@ SimplifiedVoronoi // 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 -- cgit v1.2.3