src/livarot/Path.h

   1 /*
   2  *  Path.h
   3  *  nlivarot
   4  *
   5  *  Created by fred on Tue Jun 17 2003.
   6  *
   7  */
   8
   9 #ifndef my_path
  10 #define my_path
  11
  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>
  18
  19 struct SPStyle;
  20
  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  */
  30
  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 };
  42
  43 class Shape;
  44
  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;
  51
  52 public:
  53
  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   };
  63
  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;
  72
  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) {}
  81
  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   };
  88
  89   std::vector<path_lineto> pts;
  90
  91   bool back;
  92
  93   Path();
  94   virtual ~Path();
  95
  96   // creation of the path description
  97   void Reset();         // reset to the empty description
  98   void Copy (Path * who);
  99
 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)
 112
 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);
 120
 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
 129
 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);
 137
 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);
 142
 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);
 148
 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);
 152
 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);
 156
 157   // polyline to cubic bezier patches
 158   void Simplify (double treshhold);
 159
 160   // description simplification
 161   void Coalesce (double tresh);
 162
 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);
 169
 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;
 173
 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);
 177
 178   void  DashPolylineFromStyle(SPStyle *style, float scale, float min_len);
 179
 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();
 185
 186   void  Transform(const Geom::Matrix &trans);
 187
 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();
 202
 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);
 213
 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);
 217
 218   void  Affiche();
 219   char *svg_dump_path() const;
 220
 221   bool IsLineSegment(int piece);
 222
 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);
 234
 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);
 238
 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);
 246
 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);
 253
 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);
 269
 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);
 277
 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   };
 307
 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   };
 315
 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);
 323
 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);
 336
 337   static bool IsNulCurve (std::vector<PathDescr*> const &cmd, int curD, Geom::Point const &curX);
 338
 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);
 348
 349
 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);
 366
 367
 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);
 373
 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);
 388
 389 private:
 390     void  AddCurve(Geom::Curve const &c);
 391
 392 };
 393 #endif
 394
 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 :