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