lib/gfxpoly.c

   1 /* gfxpoly.c
   2
   3    Various boolean polygon functions.
   4
   5    Part of the swftools package.
   6
   7    Copyright (c) 2005 Matthias Kramm <kramm@quiss.org>
   8
   9    This program is free software; you can redistribute it and/or modify
  10    it under the terms of the GNU General Public License as published by
  11    the Free Software Foundation; either version 2 of the License, or
  12    (at your option) any later version.
  13
  14    This program is distributed in the hope that it will be useful,
  15    but WITHOUT ANY WARRANTY; without even the implied warranty of
  16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17    GNU General Public License for more details.
  18
  19    You should have received a copy of the GNU General Public License
  20    along with this program; if not, write to the Free Software
  21    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  22
  23 #include "../config.h"
  24 #include "gfxdevice.h"
  25 #include "gfxtools.h"
  26 #include "gfxpoly.h"
  27 #include "mem.h"
  28 #include "art/libart.h"
  29 #include "art/art_svp_intersect.h"
  30 #include "log.h"
  31 #include <assert.h>
  32 #include <memory.h>
  33 #include <math.h>
  34
  35 static ArtVpath* gfxline_to_ArtVpath(gfxline_t*line, char fill)
  36 {
  37     ArtVpath *vec = NULL;
  38     int pos=0,len=0;
  39     gfxline_t*l2;
  40     double x=0,y=0;
  41
  42     /* factor which determines into how many line fragments a spline is converted */
  43     double subfraction = 2.4;//0.3
  44
  45     l2 = line;
  46     while(l2) {
  47         if(l2->type == gfx_moveTo) {
  48             pos ++;
  49         } if(l2->type == gfx_lineTo) {
  50             pos ++;
  51         } if(l2->type == gfx_splineTo) {
  52             int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
  53             if(!parts) parts = 1;
  54             pos += parts + 1;
  55         }
  56         x = l2->x;
  57         y = l2->y;
  58         l2 = l2->next;
  59     }
  60     pos++;
  61     len = pos;
  62
  63     vec = art_new (ArtVpath, len+1);
  64
  65     pos = 0;
  66     l2 = line;
  67     while(l2) {
  68         if(l2->type == gfx_moveTo) {
  69             vec[pos].code = ART_MOVETO;
  70             vec[pos].x = l2->x;
  71             vec[pos].y = l2->y;
  72             pos++;
  73             assert(pos<=len);
  74         } else if(l2->type == gfx_lineTo) {
  75             vec[pos].code = ART_LINETO;
  76             vec[pos].x = l2->x;
  77             vec[pos].y = l2->y;
  78             pos++;
  79             assert(pos<=len);
  80         } else if(l2->type == gfx_splineTo) {
  81             int i;
  82             int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
  83             double stepsize = parts?1.0/parts:0;
  84             for(i=0;i<=parts;i++) {
  85                 double t = (double)i*stepsize;
  86                 vec[pos].code = ART_LINETO;
  87                 vec[pos].x = l2->x*t*t + 2*l2->sx*t*(1-t) + x*(1-t)*(1-t);
  88                 vec[pos].y = l2->y*t*t + 2*l2->sy*t*(1-t) + y*(1-t)*(1-t);
  89                 pos++;
  90                 assert(pos<=len);
  91             }
  92         }
  93         x = l2->x;
  94         y = l2->y;
  95         l2 = l2->next;
  96     }
  97     vec[pos].code = ART_END;
  98
  99     if(!fill) {
 100         /* Fix "dotted" lines. Those are lines where singular points are created
 101            by a moveto x,y lineto x,y combination. We "fix" these by shifting the
 102            point in the lineto a little bit to the right
 103            These should only occur in strokes, not in fills, so do this only
 104            when we know we're not filling.
 105          */
 106         int t;
 107         for(t=0;vec[t].code!=ART_END;t++) {
 108             if(t>0 && vec[t-1].code==ART_MOVETO && vec[t].code==ART_LINETO
 109                     && vec[t+1].code!=ART_LINETO &&
 110                 vec[t-1].x == vec[t].x &&
 111                 vec[t-1].y == vec[t].y) {
 112                 vec[t].x += 0.01;
 113             }
 114             x = vec[t].x;
 115             y = vec[t].y;
 116         }
 117     }
 118
 119     /* Find adjacent identical points. If an ajdacent pair of identical
 120        points is found, the second is removed.
 121        So moveto x,y lineto x,y becomes moveto x,y
 122           lineto x,y lineto x,y becomes lineto x,y
 123           lineto x,y moveto x,y becomes lineto x,y
 124           moveto x,y moveto x,y becomes moveto x,y
 125           lineto x,y lineto x2,y2 becomes lineto x2,y2 (if dir(x,y) ~= dir(x2,y2))
 126      */
 127     int t = 1;
 128     while(t < pos)
 129     {
 130         double dx = vec[t].x-vec[t-1].x;
 131         double dy = vec[t].y-vec[t-1].y;
 132         char samedir = 0;
 133         if(t<pos-1 && vec[t].code == ART_LINETO && vec[t+1].code == ART_LINETO) {
 134             double dx2 = vec[t+1].x-vec[t].x;
 135             double dy2 = vec[t+1].y-vec[t].y;
 136             if(fabs(dx*dy2 - dy*dx2) < 0.001) {
 137                 samedir=1;
 138             }
 139         }
 140         if(fabs(dx) + fabs(dy) < 0.01 || samedir) {
 141             // adjacent identical points; remove the second
 142             memcpy(&vec[t], &vec[t+1], sizeof(vec[0]) * (pos - t - 1));
 143             pos--;
 144         } else {
 145             t++;
 146         }
 147     }
 148
 149     /* adjacency remover disabled for now, pending code inspection */
 150     return vec;
 151
 152     // Check for further non-adjacent identical points. We don't want any
 153     // points other than the first and last points to exactly match.
 154     //
 155     // If we do find matching points, move the second point slightly. This
 156     // currently moves the duplicate 2% towards the midpoint of its neighbours
 157     // (easier to calculate than 2% down the perpendicular to the line joining
 158     // the neighbours) but limiting the change to 0.1 twips to avoid visual
 159     // problems when the shapes are large. Note that there is no minimum
 160     // change: if the neighbouring points are colinear and equally spaced,
 161     // e.g. they were generated as part of a straight spline, then the
 162     // duplicate point may not actually move.
 163     //
 164     // The scan for duplicates algorithm is quadratic in the number of points:
 165     // there's probably a better method but the numbers of points is generally
 166     // small so this will do for now.
 167     {
 168         int i = 1, j;
 169         for(; i < (pos - 1); ++i)
 170         {
 171             for (j = 0; j < i; ++j)
 172             {
 173                 if ((vec[i].x == vec[j].x)
 174                     && (vec[i].y == vec[j].y))
 175                 {
 176                     // points match; shuffle point
 177                     double dx = (vec[i-1].x + vec[i+1].x - (vec[i].x * 2.0)) / 100.0;
 178                     double dy = (vec[i-1].y + vec[i+1].y - (vec[i].y * 2.0)) / 100.0;
 179                     double dxxyy = (dx*dx) + (dy*dy);
 180                     if (dxxyy > 0.01)
 181                     {
 182                         // This is more than 0.1 twip's distance; scale down
 183                         double dscale = sqrt(dxxyy) * 10.0;
 184                         dx /= dscale;
 185                         dy /= dscale;
 186                     };
 187                     vec[i].x += dx;
 188                     vec[i].y += dy;
 189                     break;
 190                 }
 191             }
 192         }
 193     }
 194
 195     return vec;
 196 }
 197
 198 void show_path(ArtSVP*path)
 199 {
 200     int t;
 201     printf("Segments: %d\n", path->n_segs);
 202     for(t=0;t<path->n_segs;t++) {
 203         ArtSVPSeg* seg = &path->segs[t];
 204         printf("Segment %d: %d points, %s, BBox: (%f,%f,%f,%f)\n",
 205                 t, seg->n_points, seg->dir==0?"UP  ":"DOWN",
 206                 seg->bbox.x0, seg->bbox.y0, seg->bbox.x1, seg->bbox.y1);
 207         int p;
 208         for(p=0;p<seg->n_points;p++) {
 209             ArtPoint* point = &seg->points[p];
 210             printf("        (%f,%f)\n", point->x, point->y);
 211         }
 212     }
 213     printf("\n");
 214 }
 215
 216 void write_svp_postscript(const char*filename, ArtSVP*svp)
 217 {
 218     FILE*fi = fopen(filename, "wb");
 219     int i, j;
 220     double xmin=0,ymin=0,xmax=0,ymax=0;
 221     fprintf(fi, "%% begin\n");
 222     for (i = 0; i < svp->n_segs; i++) {
 223         for (j = 0; j < svp->segs[i].n_points; j++) {
 224             double x = svp->segs[i].points[j].x;
 225             double y = svp->segs[i].points[j].y;
 226             if(i==0 && j==0) {
 227                 xmin = xmax = x;
 228                 ymin = ymax = y;
 229             } else {
 230                 if(x < xmin) xmin = x;
 231                 if(x > xmax) xmax = x;
 232                 if(y < ymin) ymin = y;
 233                 if(y > ymax) ymax = y;
 234             }
 235         }
 236     }
 237     if(xmax == xmin) xmax=xmin+1;
 238     if(ymax == ymin) ymax=ymin+1;
 239
 240     for (i = 0; i < svp->n_segs; i++)
 241       {
 242         fprintf(fi, "%g setgray\n", svp->segs[i].dir ? 0.7 : 0);
 243         for (j = 0; j < svp->segs[i].n_points; j++)
 244           {
 245             fprintf(fi, "%g %g %s\n",
 246                     20 + 550*(svp->segs[i].points[j].x-xmin)/(xmax-xmin),
 247                     820 - 800*(svp->segs[i].points[j].y-ymin)/(ymax-ymin),
 248                     j ? "lineto" : "moveto");
 249           }
 250         fprintf(fi, "stroke\n");
 251       }
 252
 253     fprintf(fi, "showpage\n");
 254     fclose(fi);
 255 }
 256
 257 void write_vpath_postscript(const char*filename, ArtVpath*path)
 258 {
 259     FILE*fi = fopen(filename, "wb");
 260     int i, j;
 261     double xmin=0,ymin=0,xmax=0,ymax=0;
 262     fprintf(fi, "%% begin\n");
 263     ArtVpath*p = path;
 264     char first = 1;
 265     while(p->code != ART_END) {
 266         if(p->code == ART_MOVETO || p->code == ART_MOVETO_OPEN) {
 267             if(!first)
 268                 fprintf(fi, "stroke\n");
 269             first = 0;
 270             fprintf(fi, "1 setgray\n");
 271             fprintf(fi, "%.32f %.32f moveto\n", p->x, p->y);
 272         } else {
 273             fprintf(fi, "%.32f %.32f lineto\n", p->x, p->y);
 274         }
 275         p++;
 276     }
 277     if(!first)
 278         fprintf(fi, "stroke\n");
 279     fprintf(fi, "showpage\n");
 280     fclose(fi);
 281 }
 282
 283 static int vpath_len(ArtVpath*svp)
 284 {
 285     int len = 0;
 286     while(svp->code != ART_END) {
 287         svp ++;
 288         len ++;
 289     }
 290     return len;
 291 }
 292
 293 int gfxline_len(gfxline_t*line)
 294 {
 295     gfxline_t*i = line;
 296     int len = 0;
 297     while(i) {
 298         len ++;
 299         i = i->next;
 300     }
 301     return len;
 302 }
 303
 304
 305 static int debug = 0;
 306 static ArtSVP* gfxfillToSVP(gfxline_t*line, int perturb)
 307 {
 308     ArtVpath* vec = gfxline_to_ArtVpath(line, 1);
 309     msg("<verbose> Casting gfxline of %d segments (%d line segments) to a gfxpoly", gfxline_len(line), vpath_len(vec));
 310
 311     if(perturb) {
 312         ArtVpath* vec2 = art_vpath_perturb(vec);
 313         free(vec);
 314         vec = vec2;
 315     }
 316     ArtSVP *svp = art_svp_from_vpath(vec);
 317     if(debug) {
 318         write_vpath_postscript("vpath.ps", vec);
 319         write_svp_postscript("polygon.ps", svp);
 320     }
 321     free(vec);
 322
 323 #if 0
 324     // We need to make sure that the SVP we now have bounds an area (i.e. the
 325     // source line wound anticlockwise) rather than excludes an area (i.e. the
 326     // line wound clockwise). It seems that PDF (or xpdf) is less strict about
 327     // this for bitmaps than it is for fill areas.
 328     //
 329     // To check this, we'll sum the cross products of all pairs of adjacent
 330     // lines. If the result is positive, the direction is correct; if not, we
 331     // need to reverse the sense of the SVP generated. The easiest way to do
 332     // this is to flip the up/down flags of all the segments.
 333     //
 334     // This is approximate; since the gfxline_t structure can contain any
 335     // combination of moveTo, lineTo and splineTo in any order, not all pairs
 336     // of lines in the shape that share a point need be described next to each
 337     // other in the sequence. For ease, we'll consider only pairs of lines
 338     // stored as lineTos and splineTos without intervening moveTos.
 339     //
 340     // TODO is this a valid algorithm? My vector maths is rusty.
 341     //
 342     // It may be more correct to instead reverse the line before we feed it
 343     // into gfxfilltoSVP. However, this seems equivalent and is easier to
 344     // implement!
 345     double total_cross_product = 0.0;
 346     gfxline_t* cursor = line;
 347     if (cursor != NULL)
 348     {
 349         double x_last = cursor->x;
 350         double y_last = cursor->y;
 351         cursor = cursor->next;
 352
 353         while((cursor != NULL) && (cursor->next != NULL))
 354         {
 355             if (((cursor->type == gfx_lineTo) || (cursor->type == gfx_splineTo))
 356                 && ((cursor->next->type == gfx_lineTo) || (cursor->next->type == gfx_splineTo)))
 357             {
 358                 // Process these lines
 359                 //
 360                 // In this space (x right, y down) the cross-product is
 361                 // (x1 * y0) - (x0 * y1)
 362                 double x0 = cursor->x - x_last;
 363                 double y0 = cursor->y - y_last;
 364                 double x1 = cursor->next->x - cursor->x;
 365                 double y1 = cursor->next->y - cursor->y;
 366                 total_cross_product += (x1 * y0) - (x0 * y1);
 367             }
 368
 369             x_last = cursor->x;
 370             y_last = cursor->y;
 371             cursor = cursor->next;
 372         }
 373     }
 374     if (total_cross_product < 0.0)
 375     {
 376         int i = 0;
 377         for(; i < svp->n_segs; ++i)
 378         {
 379             if (svp->segs[i].dir != 0)
 380                 svp->segs[i].dir = 0;
 381             else
 382                 svp->segs[i].dir = 1;
 383         }
 384     }
 385 #endif
 386
 387     return svp;
 388 }
 389
 390 gfxline_t* gfxpoly_to_gfxline(gfxpoly_t*poly)
 391 {
 392     ArtSVP*svp = (ArtSVP*)poly;
 393     int size = 0;
 394     int t;
 395     int pos = 0;
 396
 397     msg("<verbose> Casting polygon of %d segments back to gfxline", svp->n_segs);
 398
 399     for(t=0;t<svp->n_segs;t++) {
 400         size += svp->segs[t].n_points + 1;
 401     }
 402     gfxline_t* lines = (gfxline_t*)rfx_alloc(sizeof(gfxline_t)*size);
 403
 404     for(t=0;t<svp->n_segs;t++) {
 405         ArtSVPSeg* seg = &svp->segs[t];
 406         int p;
 407         for(p=0;p<seg->n_points;p++) {
 408             lines[pos].type = p==0?gfx_moveTo:gfx_lineTo;
 409             ArtPoint* point = &seg->points[p];
 410             lines[pos].x = point->x;
 411             lines[pos].y = point->y;
 412             lines[pos].next = &lines[pos+1];
 413             pos++;
 414         }
 415     }
 416     if(pos) {
 417         lines[pos-1].next = 0;
 418         return lines;
 419     } else {
 420         return 0;
 421     }
 422 }
 423 gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line)
 424 {
 425     ArtSVP* svp = gfxfillToSVP(line, 1);
 426
 427     /* we do xor-filling by default, so dir is always 1
 428        (actually for oddeven rewinding it makes no difference, but
 429         it's "cleaner")
 430      */
 431     int t;
 432     for(t=0; t<svp->n_segs; t++) {
 433         svp->segs[t].dir = 1;
 434     }
 435
 436     /* for some reason, we need to rewind / self-intersect the polygons that gfxfillToSVP
 437        returns- art probably uses a different fill mode (circular?) for vpaths */
 438     ArtSVP*svp_uncrossed=0;
 439 #ifdef ART_USE_NEW_INTERSECTOR
 440     ArtSvpWriter * swr = art_svp_writer_rewind_new(ART_WIND_RULE_ODDEVEN);
 441     art_svp_intersector(svp, swr);
 442     svp_uncrossed = art_svp_writer_rewind_reap(swr);
 443 #else
 444     svp_uncrossed = art_svp_rewind_uncrossed(art_svp_uncross(svp),ART_WIND_RULE_ODDEVEN);
 445 #endif
 446     art_svp_free(svp);
 447     svp=svp_uncrossed;
 448
 449     return (gfxpoly_t*)svp;
 450 }
 451
 452 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*poly1, gfxpoly_t*poly2)
 453 {
 454     ArtSVP* svp1 = (ArtSVP*)poly1;
 455     ArtSVP* svp2 = (ArtSVP*)poly2;
 456     msg("<verbose> Intersecting two polygons of %d and %d segments", svp1->n_segs, svp2->n_segs);
 457
 458     ArtSVP* svp = art_svp_intersect(svp1, svp2);
 459     return (gfxpoly_t*)svp;
 460 }
 461
 462 gfxpoly_t* gfxpoly_union(gfxpoly_t*poly1, gfxpoly_t*poly2)
 463 {
 464     ArtSVP* svp1 = (ArtSVP*)poly1;
 465     ArtSVP* svp2 = (ArtSVP*)poly2;
 466     msg("<verbose> Unifying two polygons of %d and %d segments", svp1->n_segs, svp2->n_segs);
 467
 468     ArtSVP* svp = art_svp_union(svp1, svp2);
 469     return (gfxpoly_t*)svp;
 470 }
 471
 472 gfxpoly_t* gfxpoly_strokeToPoly(gfxline_t*line, gfxcoord_t width, gfx_capType cap_style, gfx_joinType joint_style, double miterLimit)
 473 {
 474     ArtVpath* vec = gfxline_to_ArtVpath(line, 0);
 475     msg("<verbose> Casting gfxline of %d segments to a stroke-polygon", gfxline_len(line));
 476
 477     ArtSVP *svp = art_svp_vpath_stroke (vec,
 478                         (joint_style==gfx_joinMiter)?ART_PATH_STROKE_JOIN_MITER:
 479                         ((joint_style==gfx_joinRound)?ART_PATH_STROKE_JOIN_ROUND:
 480                          ((joint_style==gfx_joinBevel)?ART_PATH_STROKE_JOIN_BEVEL:ART_PATH_STROKE_JOIN_BEVEL)),
 481                         (cap_style==gfx_capButt)?ART_PATH_STROKE_CAP_BUTT:
 482                         ((cap_style==gfx_capRound)?ART_PATH_STROKE_CAP_ROUND:
 483                          ((cap_style==gfx_capSquare)?ART_PATH_STROKE_CAP_SQUARE:ART_PATH_STROKE_CAP_SQUARE)),
 484                         width, //line_width
 485                         miterLimit, //miter_limit
 486                         0.05 //flatness
 487                         );
 488     free(vec);
 489     return (gfxpoly_t*)svp;
 490 }
 491
 492 gfxline_t* gfxline_circularToEvenOdd(gfxline_t*line)
 493 {
 494     msg("<verbose> Converting circular-filled gfxline of %d segments to even-odd filled gfxline", gfxline_len(line));
 495     ArtSVP* svp = gfxfillToSVP(line, 1);
 496
 497     /* TODO: ART_WIND_RULE_POSITIVE means that a shape is visible if
 498              positive and negative line segments add up to something positive.
 499              I *think* that clockwise fill in PDF is defined in a way, however,
 500              that the *last* shape's direction will determine whether something
 501              is filled */
 502     ArtSVP* svp_rewinded;
 503 #ifdef ART_USE_NEW_INTERSECTOR
 504     ArtSvpWriter * swr = art_svp_writer_rewind_new (ART_WIND_RULE_POSITIVE);
 505     art_svp_intersector(svp, swr);
 506     svp_rewinded = art_svp_writer_rewind_reap(swr);
 507 #else
 508     error
 509     svp_rewinded = art_svp_rewind_uncrossed(art_svp_uncross(svp),ART_WIND_RULE_POSITIVE);
 510 #endif
 511
 512     gfxline_t* result = gfxpoly_to_gfxline((gfxpoly_t*)svp_rewinded);
 513     art_svp_free(svp);
 514     art_svp_free(svp_rewinded);
 515     return result;
 516 }
 517
 518 gfxpoly_t* gfxpoly_createbox(double x1, double y1,double x2, double y2)
 519 {
 520     ArtVpath *vec = art_new (ArtVpath, 5+1);
 521     vec[0].code = ART_MOVETO;
 522     vec[0].x = x1;
 523     vec[0].y = y1;
 524     vec[1].code = ART_LINETO;
 525     vec[1].x = x1;
 526     vec[1].y = y2;
 527     vec[2].code = ART_LINETO;
 528     vec[2].x = x2;
 529     vec[2].y = y2;
 530     vec[3].code = ART_LINETO;
 531     vec[3].x = x2;
 532     vec[3].y = y1;
 533     vec[4].code = ART_LINETO;
 534     vec[4].x = x1;
 535     vec[4].y = y1;
 536     vec[5].code = ART_END;
 537     vec[5].x = 0;
 538     vec[5].y = 0;
 539     ArtSVP *svp = art_svp_from_vpath(vec);
 540     free(vec);
 541     return (gfxpoly_t*)svp;
 542 }
 543
 544 void gfxpoly_free(gfxpoly_t*poly)
 545 {
 546     ArtSVP*svp = (ArtSVP*)poly;
 547     art_svp_free(svp);
 548 }