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 "art/art_svp_ops.h"
  31 #include "log.h"
  32 #include <assert.h>
  33 #include <memory.h>
  34 #include <math.h>
  35
  36 #define PERTURBATE
  37 //#define SHEAR
  38 //#define DEBUG
  39
  40 static ArtVpath* gfxline_to_ArtVpath(gfxline_t*line, char fill)
  41 {
  42     ArtVpath *vec = NULL;
  43     int pos=0,len=0;
  44     gfxline_t*l2;
  45     double x=0,y=0;
  46
  47     /* factor which determines into how many line fragments a spline is converted */
  48     double subfraction = 2.4;//0.3
  49
  50     l2 = line;
  51     while(l2) {
  52         if(l2->type == gfx_moveTo) {
  53             pos ++;
  54         } else if(l2->type == gfx_lineTo) {
  55             pos ++;
  56         } else if(l2->type == gfx_splineTo) {
  57             int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
  58             if(!parts) parts = 1;
  59             pos += parts + 1;
  60         }
  61         x = l2->x;
  62         y = l2->y;
  63         l2 = l2->next;
  64     }
  65     pos++;
  66     len = pos;
  67
  68     vec = art_new (ArtVpath, len+1);
  69
  70     pos = 0;
  71     l2 = line;
  72     while(l2) {
  73         if(l2->type == gfx_moveTo) {
  74             vec[pos].code = ART_MOVETO_OPEN;
  75             vec[pos].x = l2->x;
  76             vec[pos].y = l2->y;
  77             pos++;
  78             assert(pos<=len);
  79         } else if(l2->type == gfx_lineTo) {
  80             vec[pos].code = ART_LINETO;
  81             vec[pos].x = l2->x;
  82             vec[pos].y = l2->y;
  83             pos++;
  84             assert(pos<=len);
  85         } else if(l2->type == gfx_splineTo) {
  86             int i;
  87             int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
  88             if(!parts) parts = 1;
  89             double stepsize = 1.0/parts;
  90             for(i=0;i<=parts;i++) {
  91                 double t = (double)i*stepsize;
  92                 vec[pos].code = ART_LINETO;
  93                 vec[pos].x = l2->x*t*t + 2*l2->sx*t*(1-t) + x*(1-t)*(1-t);
  94                 vec[pos].y = l2->y*t*t + 2*l2->sy*t*(1-t) + y*(1-t)*(1-t);
  95                 pos++;
  96                 assert(pos<=len);
  97             }
  98         }
  99         x = l2->x;
 100         y = l2->y;
 101         l2 = l2->next;
 102     }
 103     vec[pos++].code = ART_END;
 104     assert(pos == len);
 105
 106     if(!fill) {
 107         /* Fix "dotted" lines. Those are lines where singular points are created
 108            by a moveto x,y lineto x,y combination. We "fix" these by shifting the
 109            point in the lineto a little bit to the right
 110            These should only occur in strokes, not in fills, so do this only
 111            when we know we're not filling.
 112          */
 113         int t;
 114         for(t=0;vec[t].code!=ART_END;t++) {
 115             if(t>0 && (vec[t-1].code==ART_MOVETO_OPEN || vec[t-1].code==ART_MOVETO)
 116                    && vec[t].code==ART_LINETO && vec[t+1].code!=ART_LINETO &&
 117                 vec[t-1].x == vec[t].x &&
 118                 vec[t-1].y == vec[t].y) {
 119                 vec[t].x += 0.01;
 120             }
 121         }
 122     }
 123
 124     /* Find adjacent identical points. If an ajdacent pair of identical
 125        points is found, the second is removed.
 126        So moveto x,y lineto x,y becomes moveto x,y
 127           lineto x,y lineto x,y becomes lineto x,y
 128           lineto x,y moveto x,y becomes lineto x,y
 129           moveto x,y moveto x,y becomes moveto x,y
 130           lineto x,y lineto x2,y2 becomes lineto x2,y2 (if dir(x,y) ~= dir(x2,y2))
 131      */
 132     pos = 0;
 133     int outpos = 0;
 134     while(1)
 135     {
 136         if(vec[pos].code == ART_END) {
 137             vec[outpos++] = vec[pos++];
 138             break;
 139         }
 140
 141         char samedir = 0, samepoint = 0;
 142         if(outpos) {
 143             double dx = vec[pos].x-vec[pos-1].x;
 144             double dy = vec[pos].y-vec[pos-1].y;
 145             /*if(pos<len-1 && vec[pos].code == ART_LINETO && vec[pos+1].code == ART_LINETO) {
 146                 double dx2 = vec[pos+1].x-vec[pos].x;
 147                 double dy2 = vec[pos+1].y-vec[pos].y;
 148                 if(fabs(dx*dy2 - dy*dx2) < 0.0001 && dx*dx2 + dy*dy2 >= 0) {
 149                     samedir=1;
 150                 }
 151             }*/
 152             if(fabs(dx) + fabs(dy) < 0.0001) {
 153                 samepoint=1;
 154             }
 155         }
 156         if(!samepoint && !samedir) {
 157             vec[outpos++] = vec[pos++];
 158         } else {
 159             pos++; // skip
 160         }
 161     }
 162
 163     return vec;
 164 }
 165
 166 static void shear_svp(ArtSVP*svp, double v)
 167 {
 168     /* do a "shearing on the polygon. We do this to eliminate all
 169        horizontal lines (which libart can't handle properly, even though
 170        it tries). */
 171
 172     int t;
 173     for(t=0;t<svp->n_segs;t++) {
 174         ArtSVPSeg* seg = &svp->segs[t];
 175         int s;
 176         for(s=0;s<seg->n_points;s++) {
 177             ArtPoint* point = &seg->points[s];
 178             point->y += point->x*v;
 179         }
 180     }
 181 }
 182
 183 static double find_shear_value(ArtSVP*svp)
 184 {
 185     /* We try random values until we find one
 186        where there's no slope below a given value, or if that fails,
 187        at least no slope of 0 */
 188
 189     double v = 0;
 190     int tries = 0;
 191     while(1) {
 192         char fail = 0;
 193         int t;
 194         for(t=0;t<svp->n_segs;t++) {
 195             ArtSVPSeg* seg = &svp->segs[t];
 196             int s;
 197             for(s=0;s<seg->n_points-1;s++) {
 198                 ArtPoint* p1 = &seg->points[s];
 199                 ArtPoint* p2 = &seg->points[s+1];
 200                 double dx = p2->x - p1->x;
 201                 double dy = p2->y - p1->y;
 202                 dy += dx*v;
 203                 if(dy==0) {
 204                     fail = 1;
 205                     break;
 206                 }
 207                 if(tries<100 && dx && fabs(dy / dx) < 1e-5) {
 208                     fail = 1;
 209                     break;
 210                 }
 211             }
 212             if(fail)
 213                 break;
 214         }
 215         if(!fail)
 216             break;
 217         v = lrand48() / 2000000000.0;
 218         tries++;
 219     }
 220     return v;
 221 }
 222
 223 void show_path(ArtSVP*path)
 224 {
 225     int t;
 226     printf("Segments: %d\n", path->n_segs);
 227     for(t=0;t<path->n_segs;t++) {
 228         ArtSVPSeg* seg = &path->segs[t];
 229         printf("Segment %d: %d points, %s, BBox: (%f,%f,%f,%f)\n",
 230                 t, seg->n_points, seg->dir==0?"UP  ":"DOWN",
 231                 seg->bbox.x0, seg->bbox.y0, seg->bbox.x1, seg->bbox.y1);
 232         int p;
 233         for(p=0;p<seg->n_points;p++) {
 234             ArtPoint* point = &seg->points[p];
 235             printf("        (%f,%f)\n", point->x, point->y);
 236         }
 237     }
 238     printf("\n");
 239 }
 240
 241
 242 typedef struct svp_segment_part
 243 {
 244     double y1;
 245     double y2;
 246     char active;
 247 } svp_segment_part_t;
 248
 249 int compare_double(const void*_y1, const void*_y2)
 250 {
 251     const double*y1 = _y1;
 252     const double*y2 = _y2;
 253     if(*y1<*y2) return -1;
 254     if(*y1>*y2) return 1;
 255     else return 0;
 256 }
 257
 258 int compare_seg_start(const void*_s1, const void*_s2)
 259 {
 260     svp_segment_part_t*s1 = *(svp_segment_part_t**)_s1;
 261     svp_segment_part_t*s2 = *(svp_segment_part_t**)_s2;
 262     if(s1->y1 < s2->y1) return -1;
 263     if(s1->y1 > s2->y1) return 1;
 264     else return 0;
 265 }
 266
 267 int compare_seg_end(const void*_s1, const void*_s2)
 268 {
 269     svp_segment_part_t*s1 = *(svp_segment_part_t**)_s1;
 270     svp_segment_part_t*s2 = *(svp_segment_part_t**)_s2;
 271     if(s1->y2 < s2->y2) return -1;
 272     if(s1->y2 > s2->y2) return 1;
 273     else return 0;
 274 }
 275
 276 void clean_svp(ArtSVP*svp)
 277 {
 278     int t;
 279     int oldpoints = 0;
 280     int newpoints = 0;
 281     int oldsegs = 0;
 282     int newsegs = 0;
 283     for(t=0;t<svp->n_segs;t++) {
 284         ArtSVPSeg* seg = &svp->segs[t];
 285         int p;
 286         int pos=0;
 287         double lasty = 0;
 288         oldpoints += seg->n_points;
 289         for(p=0;p<seg->n_points;p++) {
 290             ArtPoint* p1 = &seg->points[p];
 291             if(!p || lasty!=p1->y) {
 292                 seg->points[pos] = seg->points[p];
 293                 pos++;
 294                 lasty = p1->y;
 295             }
 296         }
 297         seg->n_points = pos;
 298         newpoints += seg->n_points;
 299     }
 300     int pos = 0;
 301     oldsegs = svp->n_segs;
 302     for(t=0;t<svp->n_segs;t++) {
 303         if(svp->segs[t].n_points > 1) {
 304             svp->segs[pos++] = svp->segs[t];
 305         }
 306     }
 307     svp->n_segs = pos;
 308     newsegs = svp->n_segs;
 309     if(newsegs < oldsegs || newpoints < oldpoints) {
 310         msg("<verbose> Simplified polygon from %d points to %d points, %d to %d segs",
 311                 oldpoints, newpoints, oldsegs, newsegs);
 312     }
 313 }
 314
 315 int check_svp(ArtSVP*svp)
 316 {
 317     /* count number of y coordinates and segs */
 318     int t;
 319     int num_points = 0;
 320     int num_segs = 0;
 321     for(t=0;t<svp->n_segs;t++) {
 322         if(!svp->segs[t].n_points) {
 323             msg("<error> svp contains segment with zero points\n");
 324             return 0;
 325         }
 326         num_points += svp->segs[t].n_points;
 327         num_segs += svp->segs[t].n_points - 1;
 328     }
 329
 330     /* create segs and ys */
 331     double*y = malloc(sizeof(double)*num_points);
 332     svp_segment_part_t*segs = malloc(sizeof(svp_segment_part_t)*num_segs);
 333     svp_segment_part_t**seg_start = malloc(sizeof(svp_segment_part_t*)*num_segs);
 334     svp_segment_part_t**seg_end = malloc(sizeof(svp_segment_part_t*)*num_segs);
 335
 336     int c1=0;
 337     num_segs = 0;
 338     for(t=0;t<svp->n_segs;t++) {
 339         ArtSVPSeg* seg = &svp->segs[t];
 340         int p;
 341         for(p=0;p<seg->n_points;p++) {
 342             y[c1++] = seg->points[p].y;
 343             assert(c1 <= num_points);
 344         }
 345         for(p=0;p<seg->n_points-1;p++) {
 346             ArtPoint* p1 = &seg->points[p];
 347             ArtPoint* p2 = &seg->points[p+1];
 348
 349             if(p1->y >= p2->y) {
 350                 msg("<error> bad svp, y in seg is non-increasing %.16f -> %.16f\n", p1->y, p2->y);
 351             } else {
 352                 segs[num_segs].y1 = p1->y;
 353                 segs[num_segs].y2 = p2->y;
 354                 segs[num_segs].active = 0;
 355                 seg_start[num_segs] = &segs[num_segs];
 356                 seg_end[num_segs] = &segs[num_segs];
 357                 num_segs++;
 358             }
 359         }
 360     }
 361
 362     qsort(y, num_points, sizeof(double), compare_double);
 363     qsort(seg_start, num_segs, sizeof(svp_segment_part_t*), compare_seg_start);
 364     qsort(seg_end, num_segs, sizeof(svp_segment_part_t*), compare_seg_end);
 365
 366     double lasty = y[0]+1;
 367     int num_active = 0;
 368     int bleed = 0;
 369     double bleedy1=0,bleedy2 = 0;
 370     for(t=0;t<num_points;t++) {
 371         if(lasty == y[t])
 372             continue;
 373         int s;
 374         for(s=0;s<num_segs;s++) {
 375             if(segs[s].y1==y[t]) {
 376                 /* segment is starting */
 377                 segs[s].active = 1;
 378                 num_active++;
 379             } else if(segs[s].y2==y[t]) {
 380                 segs[s].active = 0;
 381                 num_active--;
 382             }
 383         }
 384         if(num_active&1) {
 385             bleed = num_active;
 386             bleedy1 = y[t];
 387         } else {
 388             if(bleed) {
 389                 bleedy2 = y[t];
 390                 break;
 391             }
 392         }
 393         lasty = y[t];
 394     }
 395     if(bleed) {
 396         msg("<warning> svp bleeds from y=%.16f to y=%.16f (%d/%d active segments)\n",
 397                 bleedy1, bleedy2,
 398                 bleed, num_segs);
 399         free(y);free(segs);free(seg_start);free(seg_end);
 400         return 0;
 401     }
 402
 403     free(y);
 404     free(segs);
 405     free(seg_start);
 406     free(seg_end);
 407
 408     return 1;
 409 }
 410
 411 void write_svp_postscript(const char*filename, ArtSVP*svp)
 412 {
 413     if(!svp)
 414         return;
 415     printf("writing %s\n", filename);
 416     FILE*fi = fopen(filename, "wb");
 417     int i, j;
 418     double xmin=0,ymin=0,xmax=0,ymax=0;
 419     fprintf(fi, "%% begin\n");
 420     for (i = 0; i < svp->n_segs; i++) {
 421         for (j = 0; j < svp->segs[i].n_points; j++) {
 422             double x = svp->segs[i].points[j].x;
 423             double y = svp->segs[i].points[j].y;
 424             if(i==0 && j==0) {
 425                 xmin = xmax = x;
 426                 ymin = ymax = y;
 427             } else {
 428                 if(x < xmin) xmin = x;
 429                 if(x > xmax) xmax = x;
 430                 if(y < ymin) ymin = y;
 431                 if(y > ymax) ymax = y;
 432             }
 433         }
 434     }
 435     if(xmax == xmin) xmax=xmin+1;
 436     if(ymax == ymin) ymax=ymin+1;
 437
 438     for (i = 0; i < svp->n_segs; i++)
 439       {
 440         fprintf(fi, "%g setgray\n", svp->segs[i].dir ? 0.7 : 0);
 441         for (j = 0; j < svp->segs[i].n_points; j++)
 442           {
 443             //fprintf(fi, "%g %g %s\n",
 444             //        20 + 550*(svp->segs[i].points[j].x-xmin)/(xmax-xmin),
 445             //        820 - 800*(svp->segs[i].points[j].y-ymin)/(ymax-ymin),
 446             //        j ? "lineto" : "moveto");
 447             fprintf(fi, "%.32f %.32f %s\n",
 448                     svp->segs[i].points[j].x,
 449                     svp->segs[i].points[j].y,
 450                     j ? "lineto" : "moveto");
 451           }
 452         fprintf(fi, "stroke\n");
 453       }
 454
 455     fprintf(fi, "showpage\n");
 456     fclose(fi);
 457 }
 458
 459 void write_vpath_postscript(const char*filename, ArtVpath*path)
 460 {
 461     FILE*fi = fopen(filename, "wb");
 462     int i, j;
 463     double xmin=0,ymin=0,xmax=0,ymax=0;
 464     fprintf(fi, "%% begin\n");
 465     ArtVpath*p = path;
 466     char first = 1;
 467     while(p->code != ART_END) {
 468         if(p->code == ART_MOVETO || p->code == ART_MOVETO_OPEN) {
 469             if(!first)
 470                 fprintf(fi, "stroke\n");
 471             first = 0;
 472             fprintf(fi, "0.0 setgray\n");
 473             fprintf(fi, "%.32f %.32f moveto\n", p->x, p->y);
 474         } else {
 475             fprintf(fi, "%.32f %.32f lineto\n", p->x, p->y);
 476         }
 477         p++;
 478     }
 479     if(!first)
 480         fprintf(fi, "stroke\n");
 481     fprintf(fi, "showpage\n");
 482     fclose(fi);
 483 }
 484
 485 void write_gfxline_postscript(const char*filename, gfxline_t*line)
 486 {
 487     FILE*fi = fopen(filename, "wb");
 488     int i, j;
 489     fprintf(fi, "%% begin\n");
 490     char first = 1;
 491     while(line) {
 492         if(line->type == gfx_moveTo) {
 493             if(!first)
 494                 fprintf(fi, "stroke\n");
 495             first = 0;
 496             fprintf(fi, "0.0 setgray\n");
 497             fprintf(fi, "%.32f %.32f moveto\n", line->x, line->y);
 498         } else {
 499             fprintf(fi, "%.32f %.32f lineto\n", line->x, line->y);
 500         }
 501         line = line->next;
 502     }
 503     if(!first)
 504         fprintf(fi, "stroke\n");
 505     fprintf(fi, "showpage\n");
 506     fclose(fi);
 507 }
 508
 509 static int vpath_len(ArtVpath*svp)
 510 {
 511     int len = 0;
 512     while(svp->code != ART_END) {
 513         svp ++;
 514         len ++;
 515     }
 516     return len;
 517 }
 518
 519 int gfxline_len(gfxline_t*line)
 520 {
 521     gfxline_t*i = line;
 522     int len = 0;
 523     while(i) {
 524         len ++;
 525         i = i->next;
 526     }
 527     return len;
 528 }
 529
 530 static ArtVpath*pvpath= 0;
 531 static int cmppos(const void*_p1, const void*_p2)
 532 {
 533     int*p1 = (int*)_p1;
 534     int*p2 = (int*)_p2;
 535     ArtVpath*v1 = &pvpath[*p1];
 536     ArtVpath*v2 = &pvpath[*p2];
 537     if(v1->y < v2->y)
 538         return -1;
 539     else if(v1->y > v2->y)
 540         return 1;
 541     else if(v1->x < v2->x)
 542         return -2;
 543     else if(v1->x > v2->x)
 544         return 2;
 545     else
 546         return 0;
 547 }
 548
 549 #define PERTURBATION 2e-3
 550 static void my_perturb(ArtVpath*vpath)
 551 {
 552     int t;
 553     int len = vpath_len(vpath);
 554     int*pos = (int*)malloc(len*sizeof(int));
 555     for(t=0;t<len;t++)
 556         pos[t] = t;
 557     pvpath = vpath;
 558     qsort(pos, len, sizeof(int), cmppos);
 559     t=0;
 560     while(t<len) {
 561         int t2=t+1;
 562         while(t2<len && !cmppos(&pos[t],&pos[t2])) {
 563             t2++;
 564         }
 565
 566         double dx = (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5;
 567         double dy = (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5;
 568         int s;
 569         for(s=t;s<t2;s++) {
 570             vpath[pos[s]].x += dx;
 571             vpath[pos[s]].y += dy;
 572         }
 573         t = t2;
 574     }
 575     free(pos);
 576     pvpath = 0;
 577 }
 578
 579 static ArtSVP* gfxfillToSVP(gfxline_t*line, int perturb)
 580 {
 581     ArtVpath* vec = gfxline_to_ArtVpath(line, 1);
 582     msg("<verbose> Casting gfxline of %d segments (%d line segments) to a gfxpoly", gfxline_len(line), vpath_len(vec));
 583
 584     if(perturb) {
 585         //ArtVpath* vec2 = art_vpath_perturb(vec);
 586         //free(vec);
 587         //vec = vec2;
 588         my_perturb(vec);
 589     }
 590     ArtSVP *svp = art_svp_from_vpath(vec);
 591     free(vec);
 592
 593     return svp;
 594 }
 595
 596 //#ifdef SHEAR
 597 //    double shear = find_shear_value(svp);
 598 //    gfxline_t*line =  gfxpoly_to_gfxline((gfxpoly_t*)svp);
 599 //    gfxline_t*l = line;
 600 //    while(l) {
 601 //        l->y += l->x*shear;
 602 //        l->sy += l->sx*shear;
 603 //        l= l->next;
 604 //    }
 605 //    svp = (ArtSVP*)gfxpoly_fillToPoly(line);
 606 //    printf("shearing svp by %.16f\n", shear);
 607 //#endif
 608 // ....
 609 //#ifdef SHEAR
 610 //    art_svp_free(svp);
 611 //    shear_svp(result, -shear);
 612 //#endif
 613
 614
 615
 616 extern const ArtSVP* current_svp;
 617 extern void art_report_error();
 618 extern int art_error_in_intersector;
 619
 620 ArtSVP* run_intersector(ArtSVP*svp, ArtWindRule rule)
 621 {
 622     ArtSvpWriter * swr = art_svp_writer_rewind_new(rule);
 623
 624     art_svp_intersector(svp, swr);
 625     ArtSVP*result = art_svp_writer_rewind_reap(swr);
 626     clean_svp(result);
 627     if(!check_svp(result)) {
 628         msg("<warning> Error in polygon processing");
 629         current_svp = result;
 630         art_report_error(); // might set art_error_in_intersector
 631     }
 632     if(art_error_in_intersector) {
 633         art_svp_free(result);
 634         art_error_in_intersector=0;
 635         return 0;
 636     }
 637     return result;
 638 }
 639
 640 gfxline_t* gfxpoly_to_gfxline(gfxpoly_t*poly)
 641 {
 642     ArtSVP*svp = (ArtSVP*)poly;
 643     int size = 0;
 644     int t;
 645     int pos = 0;
 646
 647     msg("<verbose> Casting polygon of %d segments back to gfxline", svp->n_segs);
 648
 649     for(t=0;t<svp->n_segs;t++) {
 650         size += svp->segs[t].n_points;
 651     }
 652     size = size + 1;
 653     gfxline_t* lines = (gfxline_t*)rfx_alloc(sizeof(gfxline_t)*size);
 654
 655     for(t=0;t<svp->n_segs;t++) {
 656         ArtSVPSeg* seg = &svp->segs[t];
 657         int p;
 658         for(p=0;p<seg->n_points;p++) {
 659             lines[pos].type = p==0?gfx_moveTo:gfx_lineTo;
 660             ArtPoint* point = &seg->points[p];
 661             lines[pos].x = point->x;
 662             lines[pos].y = point->y;
 663             lines[pos].next = &lines[pos+1];
 664             pos++;
 665         }
 666     }
 667     if(pos) {
 668         lines[pos-1].next = 0;
 669         return lines;
 670     } else {
 671         return 0;
 672     }
 673 }
 674
 675 gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line)
 676 {
 677     /* I'm not sure whether doing perturbation here is actually
 678        a good idea- if that line has been run through the machine
 679        several times already, it might be safer to leave it alone,
 680        since it should already be in a format libart can handle */
 681 #ifdef PERTURBATE
 682     ArtSVP* svp = gfxfillToSVP(line, 1);
 683 #else
 684     ArtSVP* svp = gfxfillToSVP(line, 0);
 685 #endif
 686
 687 #ifdef DEBUG
 688     char filename[80];
 689     static int counter = 0;
 690     sprintf(filename, "svp%d.ps", counter);
 691     write_svp_postscript(filename, svp);
 692     sprintf(filename, "gfxline%d.ps", counter);
 693     write_gfxline_postscript(filename, line);
 694 #endif
 695
 696     /* we do xor-filling by default, so dir is always 1
 697        (actually for oddeven rewinding it makes no difference, but
 698         it's "cleaner")
 699      */
 700     int t;
 701     for(t=0; t<svp->n_segs; t++) {
 702         svp->segs[t].dir = 1;
 703     }
 704
 705     /* for some reason, we need to rewind / self-intersect the polygons that gfxfillToSVP
 706        returns- art probably uses a different fill mode (circular?) for vpaths */
 707     ArtSVP*svp_uncrossed=0;
 708
 709 #ifdef DEBUG
 710     sprintf(filename, "svp%d_in.ps", counter);
 711     write_svp_postscript(filename, svp);
 712     counter++;
 713 #endif
 714
 715     svp_uncrossed = run_intersector(svp, ART_WIND_RULE_ODDEVEN);
 716
 717     art_svp_free(svp);
 718     svp=svp_uncrossed;
 719
 720     return (gfxpoly_t*)svp;
 721 }
 722
 723 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*poly1, gfxpoly_t*poly2)
 724 {
 725     ArtSvpWriter *swr;
 726
 727     static int counter = 0;
 728
 729     ArtSVP* svp1 = (ArtSVP*)poly1;
 730     ArtSVP* svp2 = (ArtSVP*)poly2;
 731     msg("<verbose> Intersecting two polygons of %d and %d segments", svp1->n_segs, svp2->n_segs);
 732
 733 #ifdef DEBUG
 734     char filename[80];
 735     sprintf(filename, "isvp%d_src1.ps", counter);
 736     write_svp_postscript(filename, svp1);
 737     sprintf(filename, "isvp%d_src2.ps", counter);
 738     write_svp_postscript(filename, svp2);
 739 #endif
 740
 741     ArtSVP* svp3 = art_svp_merge (svp1, svp2);
 742
 743 #ifdef DEBUG
 744     sprintf(filename, "isvp%d_src.ps", counter);
 745     write_svp_postscript(filename, svp3);
 746 #endif
 747
 748     //write_svp_postscript("svp.ps", svp3);
 749     ArtSVP*svp_new = run_intersector(svp3, ART_WIND_RULE_INTERSECT);
 750
 751     art_free (svp3); /* shallow free because svp3 contains shared segments */
 752
 753 #ifdef DEBUG
 754     sprintf(filename, "isvp%d.ps", counter);
 755     write_svp_postscript(filename, svp_new);
 756 #endif
 757
 758     counter++;
 759
 760     //write_svp_postscript("svp_new.ps", svp_new);
 761
 762     return (gfxpoly_t*)svp_new;
 763 }
 764
 765 gfxpoly_t* gfxpoly_union(gfxpoly_t*poly1, gfxpoly_t*poly2)
 766 {
 767     ArtSVP* svp1 = (ArtSVP*)poly1;
 768     ArtSVP* svp2 = (ArtSVP*)poly2;
 769     msg("<verbose> Unifying two polygons of %d and %d segments", svp1->n_segs, svp2->n_segs);
 770
 771     ArtSVP* svp = art_svp_union(svp1, svp2);
 772     return (gfxpoly_t*)svp;
 773 }
 774
 775 gfxpoly_t* gfxpoly_strokeToPoly(gfxline_t*line, gfxcoord_t width, gfx_capType cap_style, gfx_joinType joint_style, double miterLimit)
 776 {
 777     ArtVpath* vec = gfxline_to_ArtVpath(line, 0);
 778     msg("<verbose> Casting gfxline of %d segments to a stroke-polygon", gfxline_len(line));
 779
 780     ArtVpath* vec2 = art_vpath_perturb(vec);
 781     free(vec);
 782     vec = vec2;
 783
 784     ArtSVP *svp = art_svp_vpath_stroke (vec,
 785                         (joint_style==gfx_joinMiter)?ART_PATH_STROKE_JOIN_MITER:
 786                         ((joint_style==gfx_joinRound)?ART_PATH_STROKE_JOIN_ROUND:
 787                          ((joint_style==gfx_joinBevel)?ART_PATH_STROKE_JOIN_BEVEL:ART_PATH_STROKE_JOIN_BEVEL)),
 788                         (cap_style==gfx_capButt)?ART_PATH_STROKE_CAP_BUTT:
 789                         ((cap_style==gfx_capRound)?ART_PATH_STROKE_CAP_ROUND:
 790                          ((cap_style==gfx_capSquare)?ART_PATH_STROKE_CAP_SQUARE:ART_PATH_STROKE_CAP_SQUARE)),
 791                         width, //line_width
 792                         miterLimit, //miter_limit
 793                         0.05 //flatness
 794                         );
 795     free(vec);
 796     return (gfxpoly_t*)svp;
 797 }
 798
 799 gfxline_t* gfxline_circularToEvenOdd(gfxline_t*line)
 800 {
 801     msg("<verbose> Converting circular-filled gfxline of %d segments to even-odd filled gfxline", gfxline_len(line));
 802     ArtSVP* svp = gfxfillToSVP(line, 1);
 803
 804     /* TODO: ART_WIND_RULE_POSITIVE means that a shape is visible if
 805              positive and negative line segments add up to something positive.
 806              I *think* that clockwise fill in PDF is defined in a way, however,
 807              that the *last* shape's direction will determine whether something
 808              is filled */
 809     ArtSVP* svp_rewinded;
 810
 811     svp_rewinded = run_intersector(svp, ART_WIND_RULE_POSITIVE);
 812     if(!svp_rewinded) {
 813         art_svp_free(svp);
 814         return 0;
 815     }
 816
 817     gfxline_t* result = gfxpoly_to_gfxline((gfxpoly_t*)svp_rewinded);
 818     art_svp_free(svp);
 819     art_svp_free(svp_rewinded);
 820     return result;
 821 }
 822
 823 gfxpoly_t* gfxpoly_createbox(double x1, double y1,double x2, double y2)
 824 {
 825     ArtVpath *vec = art_new (ArtVpath, 5+1);
 826     vec[0].code = ART_MOVETO;
 827     vec[0].x = x1;
 828     vec[0].y = y1;
 829     vec[1].code = ART_LINETO;
 830     vec[1].x = x1;
 831     vec[1].y = y2;
 832     vec[2].code = ART_LINETO;
 833     vec[2].x = x2;
 834     vec[2].y = y2;
 835     vec[3].code = ART_LINETO;
 836     vec[3].x = x2;
 837     vec[3].y = y1;
 838     vec[4].code = ART_LINETO;
 839     vec[4].x = x1;
 840     vec[4].y = y1;
 841     vec[5].code = ART_END;
 842     vec[5].x = 0;
 843     vec[5].y = 0;
 844     ArtSVP *svp = art_svp_from_vpath(vec);
 845     free(vec);
 846     return (gfxpoly_t*)svp;
 847 }
 848
 849 void gfxpoly_free(gfxpoly_t*poly)
 850 {
 851     ArtSVP*svp = (ArtSVP*)poly;
 852     art_svp_free(svp);
 853 }