src/livarot/Shape.h

   1 /*
   2  *  Digraph.h
   3  *  nlivarot
   4  *
   5  *  Created by fred on Thu Jun 12 2003.
   6  *
   7  */
   8
   9 #ifndef my_shape
  10 #define my_shape
  11
  12 #include <cmath>
  13 #include <cstdio>
  14 #include <cstdlib>
  15 #include <cstring>
  16 #include <vector>
  17
  18 #include "libnr/nr-point.h"
  19 #include "livarot/livarot-forward.h"
  20 #include "livarot/LivarotDefs.h"
  21
  22 struct SweepTree;
  23 struct SweepTreeList;
  24 struct SweepEventQueue;
  25
  26 /*
  27  * the Shape class (was the Digraph class, as the header says) stores digraphs (no kidding!) of which
  28  * a very interesting kind are polygons.
  29  * the main use of this class is the ConvertToShape() (or Booleen(), quite the same) function, which
  30  * removes all problems a polygon can present: duplicate points or edges, self-intersection. you end up with a
  31  * full-fledged polygon
  32  */
  33
  34 // possible values for the "type" field in the Shape class:
  35 enum
  36 {
  37   shape_graph = 0,              // it's just a graph; a bunch of edges, maybe intersections
  38   shape_polygon = 1,            // a polygon: intersection-free, edges oriented so that the inside is on their left
  39   shape_polypatch = 2           // a graph without intersection; each face is a polygon (not yet used)
  40 };
  41
  42 class IntLigne;
  43 class BitLigne;
  44 class AlphaLigne;
  45
  46 class Shape
  47 {
  48 public:
  49
  50     struct back_data
  51     {
  52         int pathID, pieceID;
  53         double tSt, tEn;
  54     };
  55
  56     struct voronoi_point
  57     {                           // info for points treated as points of a voronoi diagram (obtained by MakeShape())
  58         double value;           // distance to source
  59         int winding;            // winding relatively to source
  60     };
  61
  62     struct voronoi_edge
  63     {                           // info for edges, treated as approximation of edges of the voronoi diagram
  64         int leF, riF;           // left and right site
  65         double leStX, leStY, riStX, riStY;      // on the left side: (leStX,leStY) is the smallest vector from the source to st
  66         // etc...
  67         double leEnX, leEnY, riEnX, riEnY;
  68     };
  69
  70     struct quick_raster_data
  71     {
  72         double x;                           // x-position on the sweepline
  73         int    bord;                    // index of the edge
  74         int    ind;       // index of qrsData elem for edge (ie inverse of the bord)
  75         int    next,prev; // dbl linkage
  76     };
  77
  78     enum sTreeChangeType
  79     {
  80         EDGE_INSERTED = 0,
  81         EDGE_REMOVED = 1,
  82         INTERSECTION = 2
  83     };
  84
  85     struct sTreeChange
  86     {
  87         sTreeChangeType type;           // type of modification to the sweepline:
  88         int ptNo;                       // point at which the modification takes place
  89
  90         Shape *src;                     // left edge (or unique edge if not an intersection) involved in the event
  91         int bord;
  92         Shape *osrc;            // right edge (if intersection)
  93         int obord;
  94         Shape *lSrc;            // edge directly on the left in the sweepline at the moment of the event
  95         int lBrd;
  96         Shape *rSrc;            // edge directly on the right
  97         int rBrd;
  98     };
  99
 100     struct incidenceData
 101     {
 102         int nextInc;            // next incidence in the linked list
 103         int pt;                 // point incident to the edge (there is one list per edge)
 104         double theta;           // coordinate of the incidence on the edge
 105     };
 106
 107     Shape();
 108     ~Shape();
 109
 110     void MakeBackData(bool nVal);
 111     void MakeVoronoiData(bool nVal);
 112
 113     void Affiche();
 114
 115     // insertion/deletion/movement of elements in the graph
 116     void Copy(Shape *a);
 117     // -reset the graph, and ensure there's room for n points and m edges
 118     void Reset(int n = 0, int m = 0);
 119     //  -points:
 120     int AddPoint(const NR::Point x);    // as the function name says
 121     // returns the index at which the point has been added in the array
 122     void SubPoint(int p);       // removes the point at index p
 123     // nota: this function relocates the last point to the index p
 124     // so don't trust point indices if you use SubPoint
 125     void SwapPoints(int a, int b);      // swaps 2 points at indices a and b
 126     void SwapPoints(int a, int b, int c);       // swaps 3 points: c <- a <- b <- c
 127     void SortPoints();  // sorts the points if needed (checks the need_points_sorting flag)
 128
 129     //  -edges:
 130     // add an edge between points of indices st and en
 131     int AddEdge(int st, int en);
 132     // return the edge index in the array
 133
 134     // add an edge between points of indices st and en
 135     int AddEdge(int st, int en, int leF, int riF);
 136     // return the edge index in the array
 137
 138     // version for the voronoi (with faces IDs)
 139     void SubEdge(int e);                // removes the edge at index e (same remarks as for SubPoint)
 140     void SwapEdges(int a, int b);       // swaps 2 edges
 141     void SwapEdges(int a, int b, int c);        // swaps 3 edges
 142     void SortEdges();   // sort the edges if needed (checks the need_edges_sorting falg)
 143
 144     // primitives for topological manipulations
 145
 146     // endpoint of edge at index b that is different from the point p
 147     inline int Other(int p, int b) const
 148     {
 149         if (getEdge(b).st == p) {
 150             return getEdge(b).en;
 151         }
 152         return getEdge(b).st;
 153     }
 154
 155     // next edge (after edge b) in the double-linked list at point p
 156     inline int NextAt(int p, int b) const
 157     {
 158         if (p == getEdge(b).st) {
 159             return getEdge(b).nextS;
 160         }
 161         else if (p == getEdge(b).en) {
 162             return getEdge(b).nextE;
 163         }
 164
 165         return -1;
 166     }
 167
 168     // previous edge
 169     inline int PrevAt(int p, int b) const
 170     {
 171         if (p == getEdge(b).st) {
 172             return getEdge(b).prevS;
 173         }
 174         else if (p == getEdge(b).en) {
 175             return getEdge(b).prevE;
 176         }
 177
 178         return -1;
 179     }
 180
 181     // same as NextAt, but the list is considered circular
 182     inline int CycleNextAt(int p, int b) const
 183     {
 184         if (p == getEdge(b).st) {
 185             if (getEdge(b).nextS < 0) {
 186                 return getPoint(p).incidentEdge[FIRST];
 187             }
 188             return getEdge(b).nextS;
 189         } else if (p == getEdge(b).en) {
 190             if (getEdge(b).nextE < 0) {
 191                 return getPoint(p).incidentEdge[FIRST];
 192             }
 193
 194             return getEdge(b).nextE;
 195         }
 196
 197         return -1;
 198     }
 199
 200     // same as PrevAt, but the list is considered circular
 201     inline int CyclePrevAt(int p, int b) const
 202     {
 203         if (p == getEdge(b).st) {
 204             if (getEdge(b).prevS < 0) {
 205                 return getPoint(p).incidentEdge[LAST];
 206             }
 207             return getEdge(b).prevS;
 208         } else if (p == getEdge(b).en) {
 209             if (getEdge(b).prevE < 0) {
 210                 return getPoint(p).incidentEdge[LAST];
 211             }
 212             return getEdge(b).prevE;
 213         }
 214
 215         return -1;
 216     }
 217
 218     void ConnectStart(int p, int b);    // set the point p as the start of edge b
 219     void ConnectEnd(int p, int b);      // set the point p as the end of edge b
 220     void DisconnectStart(int b);        // disconnect edge b from its start point
 221     void DisconnectEnd(int b);  // disconnect edge b from its end point
 222
 223     // reverses edge b (start <-> end)
 224     void Inverse(int b);
 225     // calc bounding box and sets leftX,rightX,topY and bottomY to their values
 226     void CalcBBox(bool strict_degree = false);
 227
 228     // debug function: plots the graph (mac only)
 229     void Plot(double ix, double iy, double ir, double mx, double my, bool doPoint,
 230               bool edgesNo, bool pointNo, bool doDir, char *fileName);
 231
 232     // transforms a polygon in a "forme" structure, ie a set of contours, which can be holes (see ShapeUtils.h)
 233     // return NULL in case it's not possible
 234     void ConvertToForme(Path *dest);
 235
 236     // version to use when conversion was done with ConvertWithBackData(): will attempt to merge segment belonging to
 237     // the same curve
 238     // nota: apparently the function doesn't like very small segments of arc
 239     void ConvertToForme(Path *dest, int nbP, Path **orig, bool splitWhenForced = false);
 240     // version trying to recover the nesting of subpaths (ie: holes)
 241     void ConvertToFormeNested(Path *dest, int nbP, Path **orig, int wildPath, int &nbNest,
 242                               int *&nesting, int *&contStart, bool splitWhenForced = false);
 243
 244     // sweeping a digraph to produce a intersection-free polygon
 245     // return 0 if everything is ok and a return code otherwise (see LivarotDefs.h)
 246     // the input is the Shape "a"
 247     // directed=true <=> non-zero fill rule
 248     int ConvertToShape(Shape *a, FillRule directed = fill_nonZero, bool invert = false);
 249     // directed=false <=> even-odd fill rule
 250     // invert=true: make as if you inverted all edges in the source
 251     int Reoriente(Shape *a);    // subcase of ConvertToShape: the input a is already intersection-free
 252     // all that's missing are the correct directions of the edges
 253     // Reoriented is equivalent to ConvertToShape(a,false,false) , but faster sicne
 254     // it doesn't computes interections nor adjacencies
 255     void ForceToPolygon();      // force the Shape to believe it's a polygon (eulerian+intersection-free+no
 256     // duplicate edges+no duplicate points)
 257     // be careful when using this function
 258
 259     // the coordinate rounding function
 260     inline static double Round(double x)
 261     {
 262         return ldexp(rint(ldexp(x, 5)), -5);
 263     }
 264
 265     // 2 miscannellous variations on it, to scale to and back the rounding grid
 266     inline static double HalfRound(double x)
 267     {
 268         return ldexp(x, -5);
 269     }
 270
 271     inline static double IHalfRound(double x)
 272     {
 273         return ldexp(x, 5);
 274     }
 275
 276     // boolean operations on polygons (requests intersection-free poylygons)
 277     // boolean operation types are defined in LivarotDefs.h
 278     // same return code as ConvertToShape
 279     int Booleen(Shape *a, Shape *b, BooleanOp mod, int cutPathID = -1);
 280
 281     // create a graph that is an offseted version of the graph "of"
 282     // the offset is dec, with joins between edges of type "join" (see LivarotDefs.h)
 283     // the result is NOT a polygon; you need a subsequent call to ConvertToShape to get a real polygon
 284     int MakeOffset(Shape *of, double dec, JoinType join, double miter, bool do_profile=false, double cx = 0, double cy = 0, double radius = 0, NR::Matrix *i2doc = NULL);
 285
 286     int MakeRepel(Shape *of, double dec, JoinType join, double miter, bool do_profile=false, double cx = 0, double cy = 0, double radius = 0, NR::Matrix *i2doc = NULL);
 287
 288     int MakePush (Shape * a, JoinType join, double miter, bool do_profile, NR::Point c, NR::Point vector, double radius, NR::Matrix *i2doc = NULL);
 289
 290     int MakeJitter (Shape * a, JoinType join, double miter, bool do_profile, NR::Point c, double power, double radius, NR::Matrix *i2doc = NULL);
 291
 292     int PtWinding(const NR::Point px) const; // plus rapide
 293     int Winding(const NR::Point px) const;
 294
 295     // rasterization
 296     void BeginRaster(float &pos, int &curPt);
 297     void EndRaster();
 298     void BeginQuickRaster(float &pos, int &curPt);
 299     void EndQuickRaster();
 300
 301     void Scan(float &pos, int &curP, float to, float step);
 302     void QuickScan(float &pos, int &curP, float to, bool doSort, float step);
 303     void DirectScan(float &pos, int &curP, float to, float step);
 304     void DirectQuickScan(float &pos, int &curP, float to, bool doSort, float step);
 305
 306     void Scan(float &pos, int &curP, float to, FloatLigne *line, bool exact, float step);
 307     void Scan(float &pos, int &curP, float to, FillRule directed, BitLigne *line, bool exact, float step);
 308     void Scan(float &pos, int &curP, float to, AlphaLigne *line, bool exact, float step);
 309
 310     void QuickScan(float &pos, int &curP, float to, FloatLigne* line, float step);
 311     void QuickScan(float &pos, int &curP, float to, FillRule directed, BitLigne* line, float step);
 312     void QuickScan(float &pos, int &curP, float to, AlphaLigne* line, float step);
 313
 314     void Transform(NR::Matrix const &tr)
 315         {for(std::vector<dg_point>::iterator it=_pts.begin();it!=_pts.end();it++) it->x*=tr;}
 316
 317     std::vector<back_data> ebData;
 318     std::vector<voronoi_point> vorpData;
 319     std::vector<voronoi_edge> voreData;
 320
 321     int nbQRas;
 322     int firstQRas;
 323     int lastQRas;
 324     quick_raster_data *qrsData;
 325
 326     std::vector<sTreeChange> chgts;
 327     int nbInc;
 328     int maxInc;
 329
 330     incidenceData *iData;
 331     // these ones are allocated at the beginning of each sweep and freed at the end of the sweep
 332     SweepTreeList *sTree;
 333     SweepEventQueue *sEvts;
 334
 335     // bounding box stuff
 336     double leftX, topY, rightX, bottomY;
 337
 338     // topological information: who links who?
 339     struct dg_point
 340     {
 341         NR::Point x;            // position
 342         int dI, dO;             // indegree and outdegree
 343         int incidentEdge[2];    // first and last incident edge
 344         int oldDegree;
 345
 346         int totalDegree() const { return dI + dO; }
 347     };
 348
 349     struct dg_arete
 350     {
 351         NR::Point dx;           // edge vector
 352         int st, en;             // start and end points of the edge
 353         int nextS, prevS;       // next and previous edge in the double-linked list at the start point
 354         int nextE, prevE;       // next and previous edge in the double-linked list at the end point
 355     };
 356
 357     // lists of the nodes and edges
 358     int maxPt; // [FIXME: remove this]
 359     int maxAr; // [FIXME: remove this]
 360
 361     // flags
 362     int type;
 363
 364     inline int numberOfPoints() const { return _pts.size(); }
 365     inline bool hasPoints() const { return (_pts.empty() == false); }
 366     inline int numberOfEdges() const { return _aretes.size(); }
 367     inline bool hasEdges() const { return (_aretes.empty() == false); }
 368
 369     inline void needPointsSorting() { _need_points_sorting = true; }
 370     inline void needEdgesSorting()  { _need_edges_sorting = true; }
 371
 372     inline bool hasBackData() const { return _has_back_data; }
 373
 374     inline dg_point const &getPoint(int n) const { return _pts[n]; }
 375     inline dg_arete const &getEdge(int n) const { return _aretes[n]; }
 376
 377 private:
 378
 379     friend class SweepTree;
 380     friend class SweepEvent;
 381     friend class SweepEventQueue;
 382
 383     // temporary data for the various algorithms
 384     struct edge_data
 385     {
 386         int weight;                     // weight of the edge (to handle multiple edges)
 387         NR::Point rdx;          // rounded edge vector
 388         double length, sqlength, ilength, isqlength;    // length^2, length, 1/length^2, 1/length
 389         double siEd, coEd;              // siEd=abs(rdy/length) and coEd=rdx/length
 390         edge_data() : weight(0), length(0.0), sqlength(0.0), ilength(0.0), isqlength(0.0), siEd(0.0), coEd(0.0) {}
 391         // used to determine the "most horizontal" edge between 2 edges
 392     };
 393
 394     struct sweep_src_data
 395     {
 396         void *misc;                     // pointer to the SweepTree* in the sweepline
 397         int firstLinkedPoint;   // not used
 398         int stPt, enPt;         // start- end end- points for this edge in the resulting polygon
 399         int ind;                        // for the GetAdjacencies function: index in the sliceSegs array (for quick deletions)
 400         int leftRnd, rightRnd;  // leftmost and rightmost points (in the result polygon) that are incident to
 401         // the edge, for the current sweep position
 402         // not set if the edge doesn't start/end or intersect at the current sweep position
 403         Shape *nextSh;          // nextSh and nextBo identify the next edge in the list
 404         int nextBo;                     // they are used to maintain a linked list of edge that start/end or intersect at
 405         // the current sweep position
 406         int curPoint, doneTo;
 407         double curT;
 408     };
 409
 410     struct sweep_dest_data
 411     {
 412         void *misc;                     // used to check if an edge has already been seen during the depth-first search
 413         int suivParc, precParc; // previous and current next edge in the depth-first search
 414         int leW, riW;           // left and right winding numbers for this edge
 415         int ind;                        // order of the edges during the depth-first search
 416     };
 417
 418     struct raster_data
 419     {
 420         SweepTree *misc;                // pointer to the associated SweepTree* in the sweepline
 421         double lastX, lastY, curX, curY;        // curX;curY is the current intersection of the edge with the sweepline
 422         // lastX;lastY is the intersection with the previous sweepline
 423         bool sens;                      // true if the edge goes down, false otherwise
 424         double calcX;           // horizontal position of the intersection of the edge with the
 425         // previous sweepline
 426         double dxdy, dydx;              // horizontal change per unit vertical move of the intersection with the sweepline
 427         int guess;
 428     };
 429
 430     struct point_data
 431     {
 432         int oldInd, newInd;             // back and forth indices used when sorting the points, to know where they have
 433         // been relocated in the array
 434         int pending;            // number of intersection attached to this edge, and also used when sorting arrays
 435         int edgeOnLeft;         // not used (should help speeding up winding calculations)
 436         int nextLinkedPoint;    // not used
 437         Shape *askForWindingS;
 438         int askForWindingB;
 439         NR::Point  rx;          // rounded coordinates of the point
 440     };
 441
 442
 443     struct edge_list
 444     {                           // temporary array of edges for easier sorting
 445         int no;
 446         bool starting;
 447         NR::Point x;
 448     };
 449
 450     void initialisePointData();
 451     void initialiseEdgeData();
 452     void clearIncidenceData();
 453
 454     void _countUpDown(int P, int *numberUp, int *numberDown, int *upEdge, int *downEdge) const;
 455     void _countUpDownTotalDegree2(int P, int *numberUp, int *numberDown, int *upEdge, int *downEdge) const;
 456     void _updateIntersection(int e, int p);
 457
 458     // activation/deactivation of the temporary data arrays
 459     void MakePointData(bool nVal);
 460     void MakeEdgeData(bool nVal);
 461     void MakeSweepSrcData(bool nVal);
 462     void MakeSweepDestData(bool nVal);
 463     void MakeRasterData(bool nVal);
 464     void MakeQuickRasterData(bool nVal);
 465
 466     void SortPoints(int s, int e);
 467     void SortPointsByOldInd(int s, int e);
 468
 469     // fonctions annexes pour ConvertToShape et Booleen
 470     void ResetSweep();  // allocates sweep structures
 471     void CleanupSweep();        // deallocates them
 472
 473     // edge sorting function
 474     void SortEdgesList(edge_list *edges, int s, int e);
 475
 476     void TesteIntersection(SweepTree *t, Side s, bool onlyDiff);        // test if there is an intersection
 477     bool TesteIntersection(SweepTree *iL, SweepTree *iR, NR::Point &atx, double &atL, double &atR, bool onlyDiff);
 478     bool TesteIntersection(Shape *iL, Shape *iR, int ilb, int irb,
 479                            NR::Point &atx, double &atL, double &atR,
 480                            bool onlyDiff);
 481     bool TesteAdjacency(Shape *iL, int ilb, const NR::Point atx, int nPt,
 482                         bool push);
 483     int PushIncidence(Shape *a, int cb, int pt, double theta);
 484     int CreateIncidence(Shape *a, int cb, int pt);
 485     void AssemblePoints(Shape *a);
 486     int AssemblePoints(int st, int en);
 487     void AssembleAretes(FillRule directed = fill_nonZero);
 488     void AddChgt(int lastPointNo, int lastChgtPt, Shape *&shapeHead,
 489                  int &edgeHead, sTreeChangeType type, Shape *lS, int lB, Shape *rS,
 490                  int rB);
 491     void CheckAdjacencies(int lastPointNo, int lastChgtPt, Shape *shapeHead, int edgeHead);
 492     void CheckEdges(int lastPointNo, int lastChgtPt, Shape *a, Shape *b, BooleanOp mod);
 493     void Avance(int lastPointNo, int lastChgtPt, Shape *iS, int iB, Shape *a, Shape *b, BooleanOp mod);
 494     void DoEdgeTo(Shape *iS, int iB, int iTo, bool direct, bool sens);
 495     void GetWindings(Shape *a, Shape *b = NULL, BooleanOp mod = bool_op_union, bool brutal = false);
 496
 497     void Validate();
 498
 499     int Winding(int nPt) const;
 500     void SortPointsRounded();
 501     void SortPointsRounded(int s, int e);
 502
 503     void CreateEdge(int no, float to, float step);
 504     void AvanceEdge(int no, float to, bool exact, float step);
 505     void DestroyEdge(int no, float to, FloatLigne *line);
 506     void AvanceEdge(int no, float to, FloatLigne *line, bool exact, float step);
 507     void DestroyEdge(int no, BitLigne *line);
 508     void AvanceEdge(int no, float to, BitLigne *line, bool exact, float step);
 509     void DestroyEdge(int no, AlphaLigne *line);
 510     void AvanceEdge(int no, float to, AlphaLigne *line, bool exact, float step);
 511
 512     void AddContour(Path * dest, int nbP, Path **orig, int startBord,
 513                    int curBord, bool splitWhenForced);
 514     int ReFormeLineTo(int bord, int curBord, Path *dest, Path *orig);
 515     int ReFormeArcTo(int bord, int curBord, Path *dest, Path *orig);
 516     int ReFormeCubicTo(int bord, int curBord, Path *dest, Path *orig);
 517     int ReFormeBezierTo(int bord, int curBord, Path *dest, Path *orig);
 518     void ReFormeBezierChunk(const NR::Point px, const NR::Point nx,
 519                             Path *dest, int inBezier, int nbInterm,
 520                             Path *from, int p, double ts, double te);
 521
 522     int QuickRasterChgEdge(int oBord, int nbord, double x);
 523     int QuickRasterAddEdge(int bord, double x, int guess);
 524     void QuickRasterSubEdge(int bord);
 525     void QuickRasterSwapEdge(int a, int b);
 526     void QuickRasterSort();
 527
 528     bool _need_points_sorting;  ///< points have been added or removed: we need to sort the points again
 529     bool _need_edges_sorting;   ///< edges have been added: maybe they are not ordered clockwise
 530     ///< nota: if you remove an edge, the clockwise order still holds
 531     bool _has_points_data;      ///< the pData array is allocated
 532     bool _point_data_initialised;///< the pData array is up to date
 533     bool _has_edges_data;       ///< the eData array is allocated
 534     bool _has_sweep_src_data;   ///< the swsData array is allocated
 535     bool _has_sweep_dest_data;  ///< the swdData array is allocated
 536     bool _has_raster_data;      ///< the swrData array is allocated
 537     bool _has_quick_raster_data;///< the swrData array is allocated
 538     bool _has_back_data;        //< the ebData array is allocated
 539     bool _has_voronoi_data;
 540     bool _bbox_up_to_date;      ///< the leftX/rightX/topY/bottomY are up to date
 541
 542     std::vector<dg_point> _pts;
 543     std::vector<dg_arete> _aretes;
 544
 545     // the arrays of temporary data
 546     // these ones are dynamically kept at a length of maxPt or maxAr
 547     std::vector<edge_data> eData;
 548     std::vector<sweep_src_data> swsData;
 549     std::vector<sweep_dest_data> swdData;
 550     std::vector<raster_data> swrData;
 551     std::vector<point_data> pData;
 552
 553     static int CmpQRs(const quick_raster_data &p1, const quick_raster_data &p2) {
 554         if ( fabs(p1.x - p2.x) < 0.00001 ) {
 555             return 0;
 556         }
 557
 558         return ( ( p1.x < p2.x ) ? -1 : 1 );
 559     };
 560
 561     // edge direction comparison function
 562     static int CmpToVert(const NR::Point ax, const NR::Point bx, bool as, bool bs);
 563 };
 564
 565 bool directedEulerian(Shape const *s);
 566 double distance(Shape const *s, NR::Point const &p);
 567 bool distanceLessThanOrEqual(Shape const *s, NR::Point const &p, double const max_l2);
 568
 569 #endif