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
  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  */
  27
  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 };
  39
  40 class Shape;
  41
  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;
  48
  49 public:
  50
  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   };
  60
  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;
  69
  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) {}
  78
  79     int isMoveTo;
  80     NR::Point  p;
  81     int piece;
  82     double t;
  83   };
  84
  85   std::vector<path_lineto> pts;
  86
  87   bool back;
  88
  89   Path();
  90   ~Path();
  91
  92   // creation of the path description
  93   void Reset();         // reset to the empty description
  94   void Copy (Path * who);
  95
  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)
 108
 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);
 116
 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
 125
 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);
 133
 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);
 138
 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);
 144
 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);
 148
 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);
 152
 153   // polyline to cubic bezier patches
 154   void Simplify (double treshhold);
 155
 156   // description simplification
 157   void Coalesce (double tresh);
 158
 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);
 165
 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;
 169
 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);
 173
 174   //utilitaire pour inkscape
 175   void  LoadArtBPath(void *iP,NR::Matrix const &tr,bool doTransformation);
 176         void* MakeArtBPath();
 177
 178         void  Transform(const NR::Matrix &trans);
 179
 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();
 194
 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);
 205
 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);
 209
 210   void  Affiche();
 211   char *svg_dump_path() const;
 212
 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);
 224
 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);
 228
 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);
 236
 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);
 243
 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);
 259
 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);
 267
 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   };
 297
 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   };
 305
 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);
 313
 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);
 326
 327   static bool IsNulCurve (std::vector<PathDescr*> const &cmd, int curD, NR::Point const &curX);
 328
 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);
 338
 339
 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);
 356
 357
 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);
 363
 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
 380
 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 :