diff options
Diffstat (limited to 'src/3rdparty/libdepixelize/priv/homogeneoussplines.h')
| -rw-r--r-- | src/3rdparty/libdepixelize/priv/homogeneoussplines.h | 472 |
1 files changed, 472 insertions, 0 deletions
diff --git a/src/3rdparty/libdepixelize/priv/homogeneoussplines.h b/src/3rdparty/libdepixelize/priv/homogeneoussplines.h new file mode 100644 index 0000000..6c4894d --- /dev/null +++ b/src/3rdparty/libdepixelize/priv/homogeneoussplines.h @@ -0,0 +1,472 @@ +/* This file is part of the libdepixelize project + Copyright (C) 2013 VinÃcius dos Santos Oliveira <vini.ipsmaker@gmail.com> + + GNU Lesser General Public License Usage + This library is free software; you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as published by the + Free Software Foundation; either version 2.1 of the License, or (at your + option) any later version. + You should have received a copy of the GNU Lesser General Public License + along with this library. If not, see <http://www.gnu.org/licenses/>. + + GNU General Public License Usage + Alternatively, this library may be used under the terms of the GNU General + Public License as published by the Free Software Foundation, either version + 2 of the License, or (at your option) any later version. + You should have received a copy of the GNU General Public License along with + this library. If not, see <http://www.gnu.org/licenses/>. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. +*/ + +#ifndef LIBDEPIXELIZE_TRACER_HOMOGENEOUSSPLINES_H +#define LIBDEPIXELIZE_TRACER_HOMOGENEOUSSPLINES_H + +#include "simplifiedvoronoi.h" +#include "point.h" +#include <algorithm> +#include <utility> + +namespace Tracer { + +template<typename T> +class HomogeneousSplines +{ +public: + struct Polygon + { + typedef std::vector< Point<T> > Points; + typedef typename Points::iterator points_iter; + typedef typename Points::const_iterator const_points_iter; + typedef typename std::vector<Points>::iterator holes_iter; + typedef typename std::vector<Points>::const_iterator const_holes_iter; + + Polygon() {} + Polygon(const guint8 (&rgba)[4]) + { + for ( int i = 0 ; i != 4 ; ++i ) + this->rgba[i] = rgba[i]; + } + + std::vector< Point<T> > vertices; + + /** + * It may be benefited from C++11 move references. + */ + std::vector< std::vector< Point<T> > > holes; + + guint8 rgba[4]; + }; + + typedef typename std::vector<Polygon>::iterator iterator; + typedef typename std::vector<Polygon>::const_iterator const_iterator; + typedef typename std::vector<Polygon>::size_type size_type; + + template<bool adjust_splines> + HomogeneousSplines(const SimplifiedVoronoi<T, adjust_splines> &voronoi); + + // Iterators + iterator begin() + { + return _polygons.begin(); + } + + const_iterator begin() const + { + return _polygons.begin(); + } + + iterator end() + { + return _polygons.end(); + } + + const_iterator end() const + { + return _polygons.end(); + } + + size_type size() const + { + return _polygons.size(); + } + + int width() const + { + return _width; + } + + int height() const + { + return _height; + } + +private: + typedef std::vector< Point<T> > Points; + typedef typename Points::iterator points_iter; + typedef typename Points::const_iterator points_citer; + typedef typename Points::reverse_iterator points_riter; + typedef typename Points::const_reverse_iterator points_criter; + + typedef std::pair<points_iter, points_iter> points_range; + typedef std::pair<points_citer, points_citer> points_crange; + + struct CommonEdge + { + bool ok; //< share an edge + Points *dst; + const Points *src; + + // the interval is closed on both ends + // different from [begin, end) STL style + points_iter dst_begin, dst_end; + points_citer src_begin, src_end; + }; + + struct SelfCommonEdge + { + bool ok; //< share an edge + + // Greater range. The one that should be erased from the vector. + points_riter grt_begin, grt_end; + + // Smaller range. The one that should be used to create a new vector. + points_riter sml_begin, sml_end; + }; + + /** + * Return ok == true if they share an edge (more than one point). + */ + CommonEdge _common_edge(Points &dst, const Points &src); + + /** + * Return ok == true if they share an edge (more than one point). + * + * - [dst_begin, dst_end) will contain the hole polygon + * - [src_begin, src_end) will contain the range to be erased + * + * It's required to do the search in backward order. + */ + SelfCommonEdge _common_edge(Points &points, points_riter it); + + /*! + * Add polygon represented by \p common_edge.src to \p common_edge.dst. + */ + void _polygon_union(CommonEdge common_edge); + + /** + * Weird recursive function created to solve the complex problem to fill + * polygons holes without the need to store temporaries on the heap nor + * changing requirements to some data type that don't invalidate iterators + * that point before the current element (maybe I'll write some poetry about + * the problem someday). + */ + void _fill_holes(std::vector<Points> &holes, points_iter region_begin, + points_iter region_end); + + std::vector<Polygon> _polygons; + int _width; + int _height; +}; + +template<class T> +template<bool adjust_splines> +HomogeneousSplines<T>::HomogeneousSplines(const SimplifiedVoronoi<T, + adjust_splines> &voronoi) : + _width(voronoi.width()), + _height(voronoi.height()) +{ + //if (!voronoi.size()) + // return; + using colorspace::same_color; + + typedef typename SimplifiedVoronoi<T, adjust_splines>::const_iterator + voronoi_citer; + + // Identify visible edges (group polygons with the same color) + for ( voronoi_citer cell_it = voronoi.begin(), cell_end = voronoi.end() + ; cell_it != cell_end ; ++cell_it ) { + bool found = false; + for ( iterator polygon_it = _polygons.begin(), + polygon_end = _polygons.end() + ; polygon_it != polygon_end ; ++polygon_it ) { + if ( same_color(polygon_it->rgba, cell_it->rgba) ) { + CommonEdge common_edge = _common_edge(polygon_it->vertices, + cell_it->vertices); + if ( common_edge.ok ) { + _polygon_union(common_edge); + found = true; + + for ( iterator polygon2_it = polygon_it + 1 + ; polygon2_it != polygon_end ; ++polygon2_it ) { + if ( same_color(polygon_it->rgba, polygon2_it->rgba) ) { + CommonEdge common_edge2 + = _common_edge(polygon_it->vertices, + polygon2_it->vertices); + if ( common_edge2.ok ) { + _polygon_union(common_edge2); + _polygons.erase(polygon2_it); + break; + } + } + } + + break; + } + } + } + if ( !found ) { + Polygon polygon(cell_it->rgba); + polygon.vertices = cell_it->vertices; + _polygons.insert(_polygons.end(), polygon); + } + } + + // Find polygons with holes and fix them + // This iteration runs such complex time-consuming algorithm, but each + // polygon has an independent result. They wouldn't even need to share/sync + // results and the only waste would be a join at the end of the for. + for ( typename std::vector<Polygon>::iterator it = _polygons.begin(), + end = _polygons.end() ; it != end ; ++it ) { + SelfCommonEdge ce = _common_edge(it->vertices, it->vertices.rbegin()); + while ( ce.ok ) { + _fill_holes(it->holes, ce.sml_end.base(), ce.sml_begin.base()); + it->vertices.erase(ce.grt_end.base() + 1, ce.grt_begin.base()); + ce = _common_edge(it->vertices, ce.grt_end); + } + } +} + +// it can infinite loop if points of both entities are equal, +// but this shouldn't happen if user has only access to Kopf2011 interface +template<class T> +typename HomogeneousSplines<T>::CommonEdge +HomogeneousSplines<T>::_common_edge(Points &dst, const Points &src) +{ + // It's an edge, then the points are closer together. After we find the + // first point, there is no need for check against all points of the src + // a second time + + const points_iter dst_begin = dst.begin(); + const points_iter dst_end = dst.end(); + + const points_citer src_begin = src.begin(); + const points_citer src_end = src.end(); + + for ( points_iter it = dst_begin ; it != dst_end ; ++it ) { + points_citer src_it = std::find(src_begin, src_end, *it); + + if ( src_it == src_end ) + continue; + + points_iter dst_common_edge_begin = it; + points_citer src_common_edge_end = src_it; + + // iterate until find the beginning of the common edge range + while ( *dst_common_edge_begin == *src_common_edge_end ) { + if ( dst_common_edge_begin == dst_begin ) + dst_common_edge_begin = dst_end - 1; + else + --dst_common_edge_begin; + + ++src_common_edge_end; + if ( src_common_edge_end == src_end ) + src_common_edge_end = src_begin; + } + + // fix {dst_begin, src_end} range + ++dst_common_edge_begin; + if ( dst_common_edge_begin == dst_end ) + dst_common_edge_begin = dst_begin; + + if ( src_common_edge_end == src_begin ) + src_common_edge_end = src_end - 1; + else + --src_common_edge_end; + + points_iter dst_common_edge_end = it; + points_citer src_common_edge_begin = src_it; + + // find the end of the common edge range + while ( *dst_common_edge_end == *src_common_edge_begin ) { + ++dst_common_edge_end; + if ( dst_common_edge_end == dst_end ) + dst_common_edge_end = dst_begin; + + if ( src_common_edge_begin == src_begin ) + src_common_edge_begin = src_end - 1; + else + --src_common_edge_begin; + } + + // fix {dst_end, src_begin} range + if ( dst_common_edge_end == dst_begin ) + dst_common_edge_end = dst_end - 1; + else + --dst_common_edge_end; + + ++src_common_edge_begin; + if ( src_common_edge_begin == src_end ) + src_common_edge_begin = src_begin; + + CommonEdge ret; + + // if only one point in common + if ( dst_common_edge_begin == dst_common_edge_end ) + continue; + + ret.ok = true; + + ret.dst = &dst; + ret.dst_begin = dst_common_edge_begin; + ret.dst_end = dst_common_edge_end; + + ret.src = &src; + ret.src_begin = src_common_edge_begin; + ret.src_end = src_common_edge_end; + + return ret; + } + + CommonEdge ret; + ret.ok = false; + return ret; +} + +template<class T> +typename HomogeneousSplines<T>::SelfCommonEdge +HomogeneousSplines<T>::_common_edge(Points &points, points_riter it) +{ + SelfCommonEdge ret; + + ret.grt_end = points.rend(); + + for ( ; it != ret.grt_end ; ++it ) { + ret.sml_end = std::find(it + 1, ret.grt_end, *it); + + if ( ret.sml_end == ret.grt_end ) + continue; + + ret.grt_begin = it; + ret.grt_end = ret.sml_end + 1; + + ret.sml_begin = it; + + while ( *ret.sml_begin == *ret.sml_end ) { + ++ret.sml_begin; + --ret.sml_end; + } + + --ret.sml_begin; + ++ret.sml_end; + ++ret.sml_end; + + ret.ok = true; + return ret; + } + + ret.ok = false; + return ret; +} + +template<class T> +void HomogeneousSplines<T>::_polygon_union(CommonEdge common_edge) +{ + Points &dst = *common_edge.dst; + const Points &src = *common_edge.src; + + // the rotated cell must be inserted before (dst.begin() + index) + typename Points::difference_type index; + + // first, we remove the common edge in dst + if ( common_edge.dst_begin < common_edge.dst_end ) { + // common edge is in the middle of dst + + index = dst.erase(common_edge.dst_begin, + common_edge.dst_end + 1) - dst.begin(); + } else { + // common edge cross the end of dst + + dst.erase(common_edge.dst_begin, dst.end()); + dst.erase(dst.begin(), common_edge.dst_end); + index = dst.end() - dst.begin(); + } + + // second, we copy src points to polygon + if ( common_edge.src_begin < common_edge.src_end ) { + // common edge is in the middle of src + + const typename Points::difference_type nfirstinserted + = src.end() - common_edge.src_end; + const typename Points::difference_type nsecondinserted + = 1 + (common_edge.src_begin - src.begin()); + + dst.reserve(dst.size() + nfirstinserted + nsecondinserted); + + dst.insert(dst.begin() + index, common_edge.src_end, src.end()); + + dst.insert(dst.begin() + index + nfirstinserted, + src.begin(), common_edge.src_begin + 1); + } else { + // common edge cross the end of src + + dst.reserve(dst.size() + 1 + + (common_edge.src_begin - common_edge.src_end)); + + dst.insert(dst.begin() + index, + common_edge.src_end, common_edge.src_begin + 1); + } +} + +// The following piece of code is so evil that you could end up invoking an +// ancient beast if you proceed to read it, but I'll be able to explain it in +// the form of some video (text is not so representative as an image). +template<class T> +void HomogeneousSplines<T>::_fill_holes(std::vector<Points> &holes, + points_iter region_begin, + points_iter region_end) +{ + // the exact location might not always be back and iterators will be + // invalidated after some insertions, then the index is required + const typename std::vector<Points>::size_type hole_index = holes.size(); + holes.resize(hole_index + 1); + + for ( points_iter it = region_begin + 1 ; it != region_end ; ++it ) { + points_iter res = std::find(it + 1, region_end, *it); + if ( res == region_end ) + continue; + + holes[hole_index].insert(holes[hole_index].end(), region_begin, + it); + region_begin = res; + + do { + ++it; + --res; + } while ( *it == *res ); + _fill_holes(holes, it - 1, res + 2); + + it = region_begin; + } + + holes[hole_index].insert(holes[hole_index].end(), region_begin, + region_end - 1); +} + +} // namespace Tracer + +#endif // LIBDEPIXELIZE_TRACER_HOMOGENEOUSSPLINES_H + +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 : |