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