diff options
Diffstat (limited to 'Build/source/texk/dvisvgm/dvisvgm-src/src/PathClipper.cpp')
-rw-r--r-- | Build/source/texk/dvisvgm/dvisvgm-src/src/PathClipper.cpp | 346 |
1 files changed, 0 insertions, 346 deletions
diff --git a/Build/source/texk/dvisvgm/dvisvgm-src/src/PathClipper.cpp b/Build/source/texk/dvisvgm/dvisvgm-src/src/PathClipper.cpp deleted file mode 100644 index a36dc5d3dfc..00000000000 --- a/Build/source/texk/dvisvgm/dvisvgm-src/src/PathClipper.cpp +++ /dev/null @@ -1,346 +0,0 @@ -/************************************************************************* -** PathClipper.cpp ** -** ** -** This file is part of dvisvgm -- a fast DVI to SVG converter ** -** Copyright (C) 2005-2021 Martin Gieseking <martin.gieseking@uos.de> ** -** ** -** This program is free software; you can redistribute it and/or ** -** modify it under the terms of the GNU General Public License as ** -** published by the Free Software Foundation; either version 3 of ** -** the License, or (at your option) any later version. ** -** ** -** This program 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 General Public License for more details. ** -** ** -** You should have received a copy of the GNU General Public License ** -** along with this program; if not, see <http://www.gnu.org/licenses/>. ** -*************************************************************************/ - -#include <cmath> -#include "Bezier.hpp" -#include "PathClipper.hpp" - -using namespace std; -using namespace ClipperLib; - -using Polygon = ClipperLib::Path; -using Polygons = ClipperLib::Paths; -using CurvedPath = PathClipper::CurvedPath; - -const int SCALE_FACTOR = 1000; - -inline cInt to_cInt (double x) { - return static_cast<cInt>(lround(x*SCALE_FACTOR)); -} - - -inline double to_double (cInt x) { - return static_cast<double>(x)/SCALE_FACTOR; -} - - -inline DPair to_DPair (const IntPoint &p) { - return DPair(to_double(p.X), to_double(p.Y)); -} - - -/** In order to flatten a curved path, all path segements are processed sequentially. - * Depending on the type of the segment, one of the methods provided by this class - * is called. */ -class FlattenActions : public CurvedPath::IterationActions { - public: - FlattenActions (vector<Bezier> &curves, Polygons &polygons, int &numLines) - : _polygons(polygons), _curves(curves), _numLines(numLines) {} - - void moveto (const CurvedPath::Point &p) override { - if (p == _currentPoint && !_currentPoly.empty()) - return; - closepath(); - _currentPoly.emplace_back(IntPoint(to_cInt(p.x()), to_cInt(p.y()), 0)); - _currentPoint = _startPoint = p; - } - - void lineto (const CurvedPath::Point &p) override { - if (p == _currentPoint && !_currentPoly.empty()) - return; - if (_currentPoly.empty()) // this shouldn't happen but in case it does... - _currentPoly.emplace_back(IntPoint(0, 0, 0)); // ...add a start point first - _numLines--; - _currentPoly.back().Z.label2 = _numLines; - _currentPoly.emplace_back(IntPoint(to_cInt(p.x()), to_cInt(p.y()), ZType(_numLines, 0))); - _currentPoint = p; - } - - void quadto (const CurvedPath::Point &p1, const CurvedPath::Point &p2) override { - Bezier bezier(_currentPoint, p1, p2); - addCurvePoints(bezier); - } - - void cubicto (const CurvedPath::Point &p1, const CurvedPath::Point &p2, const CurvedPath::Point &p3) override { - Bezier bezier(_currentPoint, p1, p2, p3); - addCurvePoints(bezier); - } - - void closepath () override { - if (_currentPoly.empty()) - return; - _numLines--; - _currentPoly.back().Z.label2 = ZLabel(_numLines, 0); - _currentPoly.front().Z.label1 = ZLabel(_numLines, 0); - _polygons.push_back(_currentPoly); - _currentPoly.clear(); - } - - void finished () override { - closepath(); - } - - protected: - void addCurvePoints (const Bezier &bezier) { - if (_currentPoly.empty()) // this shouldn't happen but in case it does, ... - _currentPoly.emplace_back(IntPoint(0, 0, 0)); // ...add a start point first - vector<DPair> points; // points of flattened curve - vector<double> t; // corresponding 'time' parameters - bezier.approximate(0.01, points, &t); - if (points.size() < 2) - return; - _curves.push_back(bezier); - for (size_t i=1; i < points.size(); i++) { - const DPair &p = points[i]; - if (p == _currentPoint) - continue; - _currentPoly.back().Z.label2 = ZLabel(_curves.size(), t[i-1]); - ZLabel label(_curves.size(), t[i]); - _currentPoly.emplace_back(IntPoint(to_cInt(p.x()), to_cInt(p.y()), ZType(label, label))); - _currentPoint = p; - } - } - - private: - CurvedPath::Point _startPoint, _currentPoint; - Polygon _currentPoly; ///< polygon being created - Polygons &_polygons; ///< all polygons created - vector<Bezier> &_curves; - int &_numLines; -}; - - -/** Removes adjacent polygon vertices that equal their predecessor. */ -static void remove_redundant_vertices (Polygon &polygon) { - auto it1=polygon.begin(); - while (it1 != polygon.end()) { - auto it2 = it1+1; - if (it2 == polygon.end()) - it2 = polygon.begin(); - if (it1 == it2) - return; - - if (*it1 != *it2) - ++it1; - else { - it1->Z.label2 = it2->Z.label2; - polygon.erase(it2); - } - } -} - - -/** Approximates a curved path by a set of polygons and stores information - * to reconstruct the curved segments later. The z component of each - * polygon vertex holds two integers representing information about the two - * adjacent edges the vertex belongs to. This is required to identify the - * affected edges and thus the former (curve/line) segment of the path during - * the intersection process. - * @param[in] curvedPath curved path to be flattened - * @param[out] polygons the flattened path (set of polygons) */ -void PathClipper::flatten (const CurvedPath &curvedPath, Polygons &polygons) { - FlattenActions flattenActions(_curves, polygons, _numLines); - curvedPath.iterate(flattenActions, false); - for (Polygon &poly : polygons) - remove_redundant_vertices(poly); -} - - -/** Returns the ID of the path segment the polygon edge defined by its start - * and end point belongs to. The z component of a polygon vertex holds a pair - * of labels that allows to identify the original path segments the point belongs to. - * Since always two adjacent segments share a point, each point gets two values assigned. - * Negative numbers denote line segments, positive ones Bézier curves. - * There are only these two segment types, so we don't need further flags in - * order to distinguish them. By comparing the labels of two adjacent polygon - * vertexes it's possible to identify the original path segment the corresponding - * edge belongs to. - * @param[in] p1 first of two adjacent vertices - * @param[in] p2 second of two adjacent vertices - * @param[out] t1 time parameter of p1 - * @param[out] t2 time parameter of p2 - * @return id of edge between p1 and p2, or 0 if it's not possible to identify the segment */ -static int32_t segment_id (const IntPoint &p1, const IntPoint &p2, double &t1, double &t2) { - const ZType &z1=p1.Z, &z2=p2.Z; - if (z1 == z2 && z1.minLabel().id < 0) return z1.minLabel().id; - if (z1.label1 == z2.label2) {t1=z1.label1.t; t2=z2.label2.t; return z1.label1.id;} - if (z1.label2 == z2.label1) {t1=z1.label2.t; t2=z2.label1.t; return z1.label2.id;} - if (z1.label1 == z2.label1) {t1=z1.label1.t; t2=z2.label1.t; return z1.label1.id;} - if (z1.label2 == z2.label2) {t1=z1.label2.t; t2=z2.label2.t; return z1.label2.id;} - // if we get here, it's not possible to identify the segment - // => the edge is going to be handled as line segment - return 0; -} - - -/** This function expects 3 colinear points p1, p2, and q, where q lies between p1 and p2, - * i.e. q divides the line \f$ \overline{p_1 p_2} \f$ somewhere. The function returns - * the corresponding division ratio. */ -static double division_ratio (const IntPoint &p1, const IntPoint &p2, const IntPoint &q) { - if (p1 == p2 || q == p1) - return 0; - if (q == p2) - return 1; - if (p1.X == p2.X) - return double(q.Y-p1.Y)/(p2.Y-p1.Y); - return double(q.X-p1.X)/(p2.X-p1.X); -} - - -/** Returns the label of point q that lies on the line between points p1 and p2. */ -inline ZLabel division_label (const IntPoint &p1, const IntPoint &p2, const IntPoint &q) { - double t1=0, t2=0; - double s=0; - int32_t id = segment_id(p1, p2, t1, t2); - if (id > 0) - s = t1+(t2-t1)*division_ratio(p1, p2, q); - return ZLabel(id, s); -} - - -/** This method is called if the clipper library finds an intersection between two polygon edges. - * It populates the z coordinate of the intersection point with the idexes of the two edges. - * @param[in] e1bot first endpoint of edge 1 - * @param[in] e1top second endpoint of edge 1 - * @param[in] e2bot first endpoint of edge 2 - * @param[in] e2top second endpoint of edge 2 - * @param[in] ip intersection point of edge 1 and 2 */ -void PathClipper::callback (IntPoint &e1bot, IntPoint &e1top, IntPoint &e2bot, IntPoint &e2top, IntPoint &ip) { - ZLabel label1 = division_label(e1bot, e1top, ip); - ZLabel label2 = division_label(e2bot, e2top, ip); - ip.Z = ZType(label1, label2); -} - - -/** Iterates along the polygon edges until the endpoint of the current - * path segment is found and returns its vector index afterwards. - * @param[in] polygon the polygon to be processed - * @param[in] start index of the vertex where the iteration starts - * @param[out] label if not 0, retrieves the label of the endpoint - * @param[in] startLabel if true, the found endpoint is treated as start point and - * parameter 'label' gets the corresponding value */ -static size_t find_segment_endpoint (const Polygon &polygon, size_t start, ZLabel *label=nullptr, bool startLabel=false) { - if (polygon.empty()) - return 0; - - const size_t num_points = polygon.size(); - int i = start%num_points; - double t1=0, t2=0; // time parameters of start and endpoint of current edge - int32_t id1 = segment_id(polygon[i], polygon[(i+1)%num_points], t1, t2); - int32_t id2 = id1; - double t = t2; // time parameter of resulting endpoint - for (size_t j=1; id1 == id2 && j < num_points; j++) { - t = t2; - i = (i+1)%num_points; - if (id1 == 0) - break; - id2 = segment_id(polygon[i], polygon[(i+1)%num_points], t1, t2); - } - if (label) { - *label = ZLabel(id1, id1 < 0 ? 0 : t); - if (startLabel && id1 != 0) - *label = polygon[i].Z.otherLabel(*label); - } - return i; -} - - -/** Reconstructs a curved path from the set of polygons. - * @param[in] polygons set of polygons to reconstruct - * @param[out] path the reconstructed curved path */ -void PathClipper::reconstruct (const Polygons &polygons, CurvedPath &path) { - for (const Polygon &polygon : polygons) - reconstruct(polygon, path); -} - - -/** Reconstructs a curved path from a single polygon. - * @param[in] polygon polygon to reconstruct - * @param[out] path the reconstructed curved path */ -void PathClipper::reconstruct (const Polygon &polygon, CurvedPath &path) { - size_t num_points = polygon.size(); - if (num_points < 2) - return; - - ZLabel label1, label2; // labels of the current segment's start and endpoint - int index1 = find_segment_endpoint(polygon, 0, &label1, true); - int index2 = find_segment_endpoint(polygon, index1, &label2); - int diff = (num_points+index2-index1)%num_points; - path.moveto(to_DPair(polygon[index1])); - for (size_t count = diff; count <= num_points; count += diff) { - if (diff == 1 || label1.id <= 0) // line segment? - path.lineto(to_DPair(polygon[index2])); - else { // Bézier curve segment - Bezier bezier(_curves[label1.id-1], label1.t, label2.t); - if (label1.t > label2.t) - bezier.reverse(); - path.cubicto(bezier.point(1), bezier.point(2), bezier.point(3)); - } - if (label1.id == 0) - find_segment_endpoint(polygon, index2, &label1, true); - else - label1 = polygon[index2].Z.otherLabel(label2); - index1 = index2; - index2 = find_segment_endpoint(polygon, index1, &label2); - diff = (num_points+index2-index1)%num_points; - } - path.closepath(); -} - - -inline PolyFillType polyFillType (CurvedPath::WindingRule wr) { - return (wr == CurvedPath::WindingRule::NON_ZERO) ? pftNonZero : pftEvenOdd; -} - - -/** Combines two curved paths by applying a boolean operation on them. - * @param[in] op operation to perform - * @param[in] p1 first curved path - * @param[in] p2 second curved path - * @return intersection of p1 and p2 */ -CurvedPath PathClipper::combine (ClipType op, const CurvedPath &p1, const CurvedPath &p2) { - CurvedPath result; - if (p1.size() > 1 && p2.size() > 1) { - Clipper clipper; - Polygons polygons; - flatten(p1, polygons); - clipper.AddPaths(polygons, ptSubject, true); - polygons.clear(); - flatten(p2, polygons); - clipper.AddPaths(polygons, ptClip, true); - clipper.ZFillFunction(callback); - Polygons flattenedPath; - clipper.Execute(op, flattenedPath, polyFillType(p1.windingRule()), polyFillType(p2.windingRule())); - reconstruct(flattenedPath, result); - } - return result; -} - - -/** Returns the intersection of two curved paths. */ -CurvedPath PathClipper::intersect (const CurvedPath &p1, const CurvedPath &p2) { - return combine(ctIntersection, p1, p2); -} - - -/** Returns the union of two curved paths. */ -CurvedPath PathClipper::unite (const CurvedPath &p1, const CurvedPath &p2) { - return combine(ctUnion, p1, p2); -} |