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