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