1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /** @file 3 * TODO: insert short description here 4 *//* 5 * Authors: see git history 6 * 7 * Copyright (C) 2014 Authors 8 * Released under GNU GPL v2+, read the file 'COPYING' for more information. 9 */ 10 /* 11 * Path.h 12 * nlivarot 13 * 14 * Created by fred on Tue Jun 17 2003. 15 * 16 */ 17 18 #ifndef my_path 19 #define my_path 20 21 #include <vector> 22 #include "LivarotDefs.h" 23 #include <2geom/point.h> 24 25 struct PathDescr; 26 struct PathDescrLineTo; 27 struct PathDescrArcTo; 28 struct PathDescrCubicTo; 29 struct PathDescrBezierTo; 30 struct PathDescrIntermBezierTo; 31 32 class SPStyle; 33 34 /* 35 * the Path class: a structure to hold path description and their polyline approximation (not kept in sync) 36 * the path description is built with regular commands like MoveTo() LineTo(), etc 37 * the polyline approximation is built by a call to Convert() or its variants 38 * another possibility would be to call directly the AddPoint() functions, but that is not encouraged 39 * the conversion to polyline can salvage data as to where on the path each polyline's point lies; use 40 * ConvertWithBackData() for this. after this call, it's easy to rewind the polyline: sequences of points 41 * of the same path command can be reassembled in a command 42 */ 43 44 // polyline description commands 45 enum 46 { 47 polyline_lineto = 0, // a lineto 48 polyline_moveto = 1, // a moveto 49 polyline_forced = 2 // a forced point, ie a point that was an angle or an intersection in a previous life 50 // or more realistically a control point in the path description that created the polyline 51 // forced points are used as "breakable" points for the polyline -> cubic bezier patch operations 52 // each time the bezier fitter encounters such a point in the polyline, it decreases its treshhold, 53 // so that it is more likely to cut the polyline at that position and produce a bezier patch 54 }; 55 56 class Shape; 57 58 // path creation: 2 phases: first the path is given as a succession of commands (MoveTo, LineTo, CurveTo...); then it 59 // is converted in a polyline 60 // a polylone can be stroked or filled to make a polygon 61 class Path 62 { 63 friend class Shape; 64 65 public: 66 67 // flags for the path construction 68 enum 69 { 70 descr_ready = 0, 71 descr_adding_bezier = 1, // we're making a bezier spline, so you can expect pending_bezier_* to have a value 72 descr_doing_subpath = 2, // we're doing a path, so there is a moveto somewhere 73 descr_delayed_bezier = 4,// the bezier spline we're doing was initiated by a TempBezierTo(), so we'll need an endpoint 74 descr_dirty = 16 // the path description was modified 75 }; 76 77 // some data for the construction: what's pending, and some flags 78 int descr_flags; 79 int pending_bezier_cmd; 80 int pending_bezier_data; 81 int pending_moveto_cmd; 82 int pending_moveto_data; 83 // the path description 84 std::vector<PathDescr*> descr_cmd; 85 86 // polyline storage: a series of coordinates (and maybe weights) 87 // also back data: info on where this polyline's segment comes from, ie which command in the path description: "piece" 88 // and what abcissis on the chunk of path for this command: "t" 89 // t=0 means it's at the start of the command's chunk, t=1 it's at the end 90 struct path_lineto 91 { path_linetopath_lineto92 path_lineto(bool m, Geom::Point pp) : isMoveTo(m), p(pp), piece(-1), t(0), closed(false) {} path_linetopath_lineto93 path_lineto(bool m, Geom::Point pp, int pie, double tt) : isMoveTo(m), p(pp), piece(pie), t(tt), closed(false) {} 94 95 int isMoveTo; 96 Geom::Point p; 97 int piece; 98 double t; 99 bool closed; // true if subpath is closed (this point is the last point of a closed subpath) 100 }; 101 102 std::vector<path_lineto> pts; 103 104 bool back; 105 106 Path(); 107 virtual ~Path(); 108 109 // creation of the path description 110 void Reset(); // reset to the empty description 111 void Copy (Path * who); 112 113 // the commands... 114 int ForcePoint(); 115 int Close(); 116 int MoveTo ( Geom::Point const &ip); 117 int LineTo ( Geom::Point const &ip); 118 int CubicTo ( Geom::Point const &ip, Geom::Point const &iStD, Geom::Point const &iEnD); 119 int ArcTo ( Geom::Point const &ip, double iRx, double iRy, double angle, bool iLargeArc, bool iClockwise); 120 int IntermBezierTo ( Geom::Point const &ip); // add a quadratic bezier spline control point 121 int BezierTo ( Geom::Point const &ip); // quadratic bezier spline to this point (control points can be added after this) 122 int TempBezierTo(); // start a quadratic bezier spline (control points can be added after this) 123 int EndBezierTo(); 124 int EndBezierTo ( Geom::Point const &ip); // ends a quadratic bezier spline (for curves started with TempBezierTo) 125 126 // transforms a description in a polyline (for stroking and filling) 127 // treshhold is the max length^2 (sort of) 128 void Convert (double treshhold); 129 void ConvertEvenLines (double treshhold); // decomposes line segments too, for later recomposition 130 // same function for use when you want to later recompose the curves from the polyline 131 void ConvertWithBackData (double treshhold); 132 133 // creation of the polyline (you can tinker with these function if you want) 134 void SetBackData (bool nVal); // has back data? 135 void ResetPoints(); // resets to the empty polyline 136 int AddPoint ( Geom::Point const &iPt, bool mvto = false); // add point 137 int AddPoint ( Geom::Point const &iPt, int ip, double it, bool mvto = false); 138 int AddForcedPoint ( Geom::Point const &iPt); // add point 139 int AddForcedPoint ( Geom::Point const &iPt, int ip, double it); 140 int ReplacePoint(Geom::Point const &iPt); // replace point 141 142 // transform in a polygon (in a graph, in fact; a subsequent call to ConvertToShape is needed) 143 // - fills the polyline; justAdd=true doesn't reset the Shape dest, but simply adds the polyline into it 144 // closeIfNeeded=false prevent the function from closing the path (resulting in a non-eulerian graph 145 // pathID is a identification number for the path, and is used for recomposing curves from polylines 146 // give each different Path a different ID, and feed the appropriate orig[] to the ConvertToForme() function 147 void Fill(Shape *dest, int pathID = -1, bool justAdd = false, 148 bool closeIfNeeded = true, bool invert = false); 149 150 // - stroke the path; usual parameters: type of cap=butt, type of join=join and miter (see LivarotDefs.h) 151 // doClose treat the path as closed (ie a loop) 152 void Stroke(Shape *dest, bool doClose, double width, JoinType join, 153 ButtType butt, double miter, bool justAdd = false); 154 155 // build a Path that is the outline of the Path instance's description (the result is stored in dest) 156 // it doesn't compute the exact offset (it's way too complicated, but an approximation made of cubic bezier patches 157 // and segments. the algorithm was found in a plugin for Impress (by Chris Cox), but i can't find it back... 158 void Outline(Path *dest, double width, JoinType join, ButtType butt, 159 double miter); 160 161 // half outline with edges having the same direction as the original 162 void OutsideOutline(Path *dest, double width, JoinType join, ButtType butt, 163 double miter); 164 165 // half outline with edges having the opposite direction as the original 166 void InsideOutline (Path * dest, double width, JoinType join, ButtType butt, 167 double miter); 168 169 // polyline to cubic bezier patches 170 void Simplify (double treshhold); 171 172 // description simplification 173 void Coalesce (double tresh); 174 175 // utilities 176 // piece is a command no in the command list 177 // "at" is an abcissis on the path portion associated with this command 178 // 0=beginning of portion, 1=end of portion. 179 void PointAt (int piece, double at, Geom::Point & pos); 180 void PointAndTangentAt (int piece, double at, Geom::Point & pos, Geom::Point & tgt); 181 182 // last control point before the command i (i included) 183 // used when dealing with quadratic bezier spline, cause these can contain arbitrarily many commands 184 const Geom::Point PrevPoint (const int i) const; 185 186 // dash the polyline 187 // the result is stored in the polyline, so you lose the original. make a copy before if needed 188 void DashPolyline(float head,float tail,float body,int nbD,float *dashs,bool stPlain,float stOffset); 189 190 void DashPolylineFromStyle(SPStyle *style, float scale, float min_len); 191 192 //utilitaire pour inkscape 193 void LoadPath(Geom::Path const &path, Geom::Affine const &tr, bool doTransformation, bool append = false); 194 void LoadPathVector(Geom::PathVector const &pv, Geom::Affine const &tr, bool doTransformation); 195 void LoadPathVector(Geom::PathVector const &pv); 196 Geom::PathVector MakePathVector(); 197 198 void Transform(const Geom::Affine &trans); 199 200 // decompose le chemin en ses sous-chemin 201 // killNoSurf=true -> oublie les chemins de surface nulle 202 Path** SubPaths(int &outNb,bool killNoSurf); 203 // pour recuperer les trous 204 // nbNest= nombre de contours 205 // conts= debut de chaque contour 206 // nesting= parent de chaque contour 207 Path** SubPathsWithNesting(int &outNb,bool killNoSurf,int nbNest,int* nesting,int* conts); 208 // surface du chemin (considere comme ferme) 209 double Surface(); 210 void PolylineBoundingBox(double &l,double &t,double &r,double &b); 211 void FastBBox(double &l,double &t,double &r,double &b); 212 // longueur (totale des sous-chemins) 213 double Length(); 214 215 void ConvertForcedToMoveTo(); 216 void ConvertForcedToVoid(); 217 struct cut_position { 218 int piece; 219 double t; 220 }; 221 cut_position* CurvilignToPosition(int nbCv,double* cvAbs,int &nbCut); 222 cut_position PointToCurvilignPosition(Geom::Point const &pos, unsigned seg = 0) const; 223 //Should this take a cut_position as a param? 224 double PositionToLength(int piece, double t); 225 226 // caution: not tested on quadratic b-splines, most certainly buggy 227 void ConvertPositionsToMoveTo(int nbPos,cut_position* poss); 228 void ConvertPositionsToForced(int nbPos,cut_position* poss); 229 230 void Affiche(); 231 char *svg_dump_path() const; 232 233 bool IsLineSegment(int piece); 234 235 private: 236 // utilitary functions for the path construction 237 void CancelBezier (); 238 void CloseSubpath(); 239 void InsertMoveTo (Geom::Point const &iPt,int at); 240 void InsertForcePoint (int at); 241 void InsertLineTo (Geom::Point const &iPt,int at); 242 void InsertArcTo (Geom::Point const &ip, double iRx, double iRy, double angle, bool iLargeArc, bool iClockwise,int at); 243 void InsertCubicTo (Geom::Point const &ip, Geom::Point const &iStD, Geom::Point const &iEnD,int at); 244 void InsertBezierTo (Geom::Point const &iPt,int iNb,int at); 245 void InsertIntermBezierTo (Geom::Point const &iPt,int at); 246 247 // creation of dashes: take the polyline given by spP (length spL) and dash it according to head, body, etc. put the result in 248 // the polyline of this instance 249 void DashSubPath(int spL, int spP, std::vector<path_lineto> const &orig_pts, float head,float tail,float body,int nbD,float *dashs,bool stPlain,float stOffset); 250 251 // Functions used by the conversion. 252 // they append points to the polyline 253 void DoArc ( Geom::Point const &iS, Geom::Point const &iE, double rx, double ry, 254 double angle, bool large, bool wise, double tresh); 255 void RecCubicTo ( Geom::Point const &iS, Geom::Point const &iSd, Geom::Point const &iE, Geom::Point const &iEd, double tresh, int lev, 256 double maxL = -1.0); 257 void RecBezierTo ( Geom::Point const &iPt, Geom::Point const &iS, Geom::Point const &iE, double treshhold, int lev, double maxL = -1.0); 258 259 void DoArc ( Geom::Point const &iS, Geom::Point const &iE, double rx, double ry, 260 double angle, bool large, bool wise, double tresh, int piece); 261 void RecCubicTo ( Geom::Point const &iS, Geom::Point const &iSd, Geom::Point const &iE, Geom::Point const &iEd, double tresh, int lev, 262 double st, double et, int piece); 263 void RecBezierTo ( Geom::Point const &iPt, Geom::Point const &iS, const Geom::Point &iE, double treshhold, int lev, double st, double et, 264 int piece); 265 266 // don't pay attention 267 struct offset_orig 268 { 269 Path *orig; 270 int piece; 271 double tSt, tEn; 272 double off_dec; 273 }; 274 void DoArc ( Geom::Point const &iS, Geom::Point const &iE, double rx, double ry, 275 double angle, bool large, bool wise, double tresh, int piece, 276 offset_orig & orig); 277 void RecCubicTo ( Geom::Point const &iS, Geom::Point const &iSd, Geom::Point const &iE, Geom::Point const &iEd, double tresh, int lev, 278 double st, double et, int piece, offset_orig & orig); 279 void RecBezierTo ( Geom::Point const &iPt, Geom::Point const &iS, Geom::Point const &iE, double treshhold, int lev, double st, double et, 280 int piece, offset_orig & orig); 281 282 static void ArcAngles ( Geom::Point const &iS, Geom::Point const &iE, double rx, 283 double ry, double angle, bool large, bool wise, 284 double &sang, double &eang); 285 static void QuadraticPoint (double t, Geom::Point &oPt, Geom::Point const &iS, Geom::Point const &iM, Geom::Point const &iE); 286 static void CubicTangent (double t, Geom::Point &oPt, Geom::Point const &iS, 287 Geom::Point const &iSd, Geom::Point const &iE, 288 Geom::Point const &iEd); 289 290 struct outline_callback_data 291 { 292 Path *orig; 293 int piece; 294 double tSt, tEn; 295 Path *dest; 296 double x1, y1, x2, y2; 297 union 298 { 299 struct 300 { 301 double dx1, dy1, dx2, dy2; 302 } 303 c; 304 struct 305 { 306 double mx, my; 307 } 308 b; 309 struct 310 { 311 double rx, ry, angle; 312 bool clock, large; 313 double stA, enA; 314 } 315 a; 316 } 317 d; 318 }; 319 320 typedef void (outlineCallback) (outline_callback_data * data, double tol, double width); 321 struct outline_callbacks 322 { 323 outlineCallback *cubicto; 324 outlineCallback *bezierto; 325 outlineCallback *arcto; 326 }; 327 328 void SubContractOutline (int off, int num_pd, 329 Path * dest, outline_callbacks & calls, 330 double tolerance, double width, JoinType join, 331 ButtType butt, double miter, bool closeIfNeeded, 332 bool skipMoveto, Geom::Point & lastP, Geom::Point & lastT); 333 void DoStroke(int off, int N, Shape *dest, bool doClose, double width, JoinType join, 334 ButtType butt, double miter, bool justAdd = false); 335 336 static void TangentOnSegAt(double at, Geom::Point const &iS, PathDescrLineTo const &fin, 337 Geom::Point &pos, Geom::Point &tgt, double &len); 338 static void TangentOnArcAt(double at, Geom::Point const &iS, PathDescrArcTo const &fin, 339 Geom::Point &pos, Geom::Point &tgt, double &len, double &rad); 340 static void TangentOnCubAt (double at, Geom::Point const &iS, PathDescrCubicTo const &fin, bool before, 341 Geom::Point &pos, Geom::Point &tgt, double &len, double &rad); 342 static void TangentOnBezAt (double at, Geom::Point const &iS, 343 PathDescrIntermBezierTo & mid, 344 PathDescrBezierTo & fin, bool before, 345 Geom::Point & pos, Geom::Point & tgt, double &len, double &rad); 346 static void OutlineJoin (Path * dest, Geom::Point pos, Geom::Point stNor, Geom::Point enNor, 347 double width, JoinType join, double miter, int nType); 348 349 static bool IsNulCurve (std::vector<PathDescr*> const &cmd, int curD, Geom::Point const &curX); 350 351 static void RecStdCubicTo (outline_callback_data * data, double tol, 352 double width, int lev); 353 static void StdCubicTo (outline_callback_data * data, double tol, 354 double width); 355 static void StdBezierTo (outline_callback_data * data, double tol, 356 double width); 357 static void RecStdArcTo (outline_callback_data * data, double tol, 358 double width, int lev); 359 static void StdArcTo (outline_callback_data * data, double tol, double width); 360 361 362 // fonctions annexes pour le stroke 363 static void DoButt (Shape * dest, double width, ButtType butt, Geom::Point pos, 364 Geom::Point dir, int &leftNo, int &rightNo); 365 static void DoJoin (Shape * dest, double width, JoinType join, Geom::Point pos, 366 Geom::Point prev, Geom::Point next, double miter, double prevL, 367 double nextL, int *stNo, int *enNo); 368 static void DoLeftJoin (Shape * dest, double width, JoinType join, Geom::Point pos, 369 Geom::Point prev, Geom::Point next, double miter, double prevL, 370 double nextL, int &leftStNo, int &leftEnNo,int pathID=-1,int pieceID=0,double tID=0.0); 371 static void DoRightJoin (Shape * dest, double width, JoinType join, Geom::Point pos, 372 Geom::Point prev, Geom::Point next, double miter, double prevL, 373 double nextL, int &rightStNo, int &rightEnNo,int pathID=-1,int pieceID=0,double tID=0.0); 374 static void RecRound (Shape * dest, int sNo, int eNo, 375 Geom::Point const &iS, Geom::Point const &iE, 376 Geom::Point const &nS, Geom::Point const &nE, 377 Geom::Point &origine,float width); 378 379 380 void DoSimplify(int off, int N, double treshhold); 381 bool AttemptSimplify(int off, int N, double treshhold, PathDescrCubicTo &res, int &worstP); 382 static bool FitCubic(Geom::Point const &start, 383 PathDescrCubicTo &res, 384 double *Xk, double *Yk, double *Qk, double *tk, int nbPt); 385 386 struct fitting_tables { 387 int nbPt,maxPt,inPt; 388 double *Xk; 389 double *Yk; 390 double *Qk; 391 double *tk; 392 double *lk; 393 char *fk; 394 double totLen; 395 }; 396 bool AttemptSimplify (fitting_tables &data,double treshhold, PathDescrCubicTo & res,int &worstP); 397 bool ExtendFit(int off, int N, fitting_tables &data,double treshhold, PathDescrCubicTo & res,int &worstP); 398 double RaffineTk (Geom::Point pt, Geom::Point p0, Geom::Point p1, Geom::Point p2, Geom::Point p3, double it); 399 void FlushPendingAddition(Path* dest,PathDescr *lastAddition,PathDescrCubicTo &lastCubic,int lastAD); 400 401 private: 402 void AddCurve(Geom::Curve const &c); 403 404 }; 405 #endif 406 407 /* 408 Local Variables: 409 mode:c++ 410 c-file-style:"stroustrup" 411 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) 412 indent-tabs-mode:nil 413 fill-column:99 414 End: 415 */ 416 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : 417