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 //----------------------------------------- svp renderer ----------------------------------------
  41
  42 typedef struct {
  43     int xmin;
  44     int ymin;
  45     int xmax;
  46     int ymax;
  47     int width;
  48     int height;
  49 } intbbox_t;
  50
  51 typedef struct _renderpoint
  52 {
  53     double x;
  54     signed char direction;
  55 } renderpoint_t;
  56
  57 typedef struct _renderline
  58 {
  59     renderpoint_t*points;
  60     int size;
  61     int num;
  62 } renderline_t;
  63
  64 typedef struct _renderbuf
  65 {
  66     intbbox_t bbox;
  67     int width;
  68     int height;
  69     double zoom;
  70     renderline_t*lines;
  71 } renderbuf_t;
  72
  73 static inline void add_pixel(renderbuf_t*buf, double x, int y, signed char direction)
  74 {
  75     renderpoint_t p;
  76     p.x = x;
  77     p.direction = direction;
  78
  79     if(x >= buf->bbox.xmax || y >= buf->bbox.ymax || y < buf->bbox.ymin)
  80         return;
  81     renderline_t*l = &buf->lines[y-buf->bbox.ymin];
  82
  83     if(l->num == l->size) {
  84         l->size += 32;
  85         l->points = (renderpoint_t*)rfx_realloc(l->points, l->size * sizeof(renderpoint_t));
  86     }
  87     l->points[l->num] = p;
  88     l->num++;
  89 }
  90 #define CUT 0.5
  91 #define INT(x) ((int)((x)+16)-16)
  92 static void add_line(renderbuf_t*buf, double x1, double y1, double x2, double y2, signed char direction)
  93 {
  94     x1 *= buf->zoom;
  95     y1 *= buf->zoom;
  96     x2 *= buf->zoom;
  97     y2 *= buf->zoom;
  98     double diffx, diffy;
  99     double ny1, ny2, stepx;
 100     if(y2 < y1) {
 101         double x,y;
 102         x = x1;x1 = x2;x2=x;
 103         y = y1;y1 = y2;y2=y;
 104     }
 105     diffx = x2 - x1;
 106     diffy = y2 - y1;
 107     ny1 = INT(y1)+CUT;
 108     ny2 = INT(y2)+CUT;
 109
 110     if(ny1 < y1) {
 111         ny1 = INT(y1) + 1.0 + CUT;
 112     }
 113     if(ny2 >= y2) {
 114         ny2 = INT(y2) - 1.0 + CUT;
 115     }
 116     if(ny1 > ny2)
 117         return;
 118
 119     stepx = diffx/diffy;
 120     x1 = x1 + (ny1-y1)*stepx;
 121     x2 = x2 + (ny2-y2)*stepx;
 122
 123     int posy=INT(ny1);
 124     int endy=INT(ny2);
 125     double posx=0;
 126     double startx = x1;
 127
 128     while(posy<=endy) {
 129         double xx = startx + posx;
 130         add_pixel(buf, xx, posy, direction);
 131         posx+=stepx;
 132         posy++;
 133     }
 134 }
 135
 136 static int compare_renderpoints(const void * _a, const void * _b)
 137 {
 138     renderpoint_t*a = (renderpoint_t*)_a;
 139     renderpoint_t*b = (renderpoint_t*)_b;
 140     if(a->x < b->x) return -1;
 141     if(a->x > b->x) return 1;
 142     return 0;
 143 }
 144
 145 static void fill_bitwise(unsigned char*line, int x1, int x2)
 146 {
 147     int p1 = x1>>3;
 148     int p2 = x2>>3;
 149     int b1 = 0xff >> (x1&7);
 150     int b2 = 0xff << (1+7-(x2&7));
 151     if(p1==p2) {
 152         line[p1] |= b1&b2;
 153     } else {
 154         line[p1] |= b1;
 155         memset(&line[p1+1], 255, p2-(p1+1));
 156         line[p2] = b2;
 157     }
 158 }
 159
 160 unsigned char* render_svp(ArtSVP*svp, intbbox_t*bbox, double zoom, ArtWindRule rule)
 161 {
 162     renderbuf_t _buf, *buf=&_buf;
 163     buf->width = (bbox->xmax - bbox->xmin);
 164     buf->height = (bbox->ymax - bbox->ymin);
 165     buf->bbox = *bbox;
 166     buf->zoom = zoom;
 167     int width8 = (buf->width+7) >> 3;
 168     unsigned char* image = (unsigned char*)malloc(width8*buf->height);
 169     memset(image, 0, width8*buf->height);
 170
 171     buf->lines = (renderline_t*)rfx_alloc(buf->height*sizeof(renderline_t));
 172     int y;
 173     for(y=0;y<buf->height;y++) {
 174         memset(&buf->lines[y], 0, sizeof(renderline_t));
 175         buf->lines[y].points = 0;
 176         buf->lines[y].num = 0;
 177     }
 178
 179     int t;
 180     for(t=0;t<svp->n_segs;t++) {
 181         ArtSVPSeg* seg = &svp->segs[t];
 182         int s;
 183         for(s=0;s<seg->n_points-1;s++) {
 184             int dir = seg->dir? 1 : -1;
 185             add_line(buf, seg->points[s].x, seg->points[s].y, seg->points[s+1].x, seg->points[s+1].y, dir);
 186         }
 187     }
 188     for(y=0;y<buf->height;y++) {
 189         renderpoint_t*points = buf->lines[y].points;
 190         unsigned char*line = &image[width8*y];
 191         int n;
 192         int num = buf->lines[y].num;
 193         int wind = 0;
 194         qsort(points, num, sizeof(renderpoint_t), compare_renderpoints);
 195         int lastx = 0;
 196         int fill = 0;
 197
 198         for(n=0;n<num;n++) {
 199             renderpoint_t*p = &points[n];
 200             int x = (int)(p->x - bbox->xmin);
 201
 202             if(x < lastx)
 203                 x = lastx;
 204             if(x > buf->width) {
 205                 break;
 206             }
 207             if(fill && x!=lastx) {
 208                 fill_bitwise(line, lastx, x);
 209             }
 210             wind += p->direction;
 211             if(rule == ART_WIND_RULE_INTERSECT) {
 212                 fill = wind>=2;
 213             } else if (rule == ART_WIND_RULE_NONZERO) {
 214                 fill = wind!=0;
 215             } else if (rule == ART_WIND_RULE_ODDEVEN) {
 216                 fill = wind&1;
 217             } else { // rule == ART_WIND_RULE_POSITIVE
 218                 fill = wind>=1;
 219             }
 220             lastx = x;
 221         }
 222         if(fill && lastx!=buf->width)
 223             fill_bitwise(line, lastx, buf->width);
 224     }
 225
 226     for(y=0;y<buf->height;y++) {
 227         if(buf->lines[y].points) {
 228             free(buf->lines[y].points);
 229         }
 230         memset(&buf->lines[y], 0, sizeof(renderline_t));
 231     }
 232     free(buf->lines);buf->lines=0;
 233     return image;
 234 }
 235
 236 intbbox_t get_svp_bbox(ArtSVP*svp, double zoom)
 237 {
 238     int t;
 239     intbbox_t b = {0,0,0,0};
 240     if(svp->n_segs && svp->segs[0].n_points) {
 241         b.xmin = svp->segs[0].points[0].x;
 242         b.ymin = svp->segs[0].points[0].y;
 243         b.xmax = svp->segs[0].points[0].x;
 244         b.ymax = svp->segs[0].points[0].y;
 245     }
 246     for(t=0;t<svp->n_segs;t++) {
 247         ArtSVPSeg* seg = &svp->segs[t];
 248         int s;
 249         for(s=0;s<seg->n_points;s++) {
 250             double x = seg->points[s].x*zoom;
 251             double y = seg->points[s].y*zoom;
 252             int x1 = floor(x);
 253             int x2 = ceil(x);
 254             int y1 = floor(y);
 255             int y2 = ceil(y);
 256             if(x1 < b.xmin) b.xmin = x1;
 257             if(y1 < b.ymin) b.ymin = y1;
 258             if(x2 > b.xmax) b.xmax = x2;
 259             if(y2 > b.xmax) b.ymax = y2;
 260         }
 261     }
 262     b.width = b.xmax - b.xmin;
 263     b.height = b.ymax - b.ymin;
 264     return b;
 265 }
 266
 267 #define B11100000 0xe0
 268 #define B01110000 0x70
 269 #define B00111000 0x38
 270 #define B00011100 0x1c
 271 #define B00001110 0x0e
 272 #define B00000111 0x07
 273 #define B10000000 0x80
 274 #define B01000000 0x40
 275 #define B00100000 0x20
 276 #define B00010000 0x10
 277 #define B00001000 0x08
 278 #define B00000100 0x04
 279 #define B00000010 0x02
 280 #define B00000001 0x01
 281
 282 int compare_bitmaps(intbbox_t*bbox, unsigned char*data1, unsigned char*data2)
 283 {
 284     int similar = 0;
 285     int x,y;
 286     int height = bbox->height;
 287     int width = bbox->width;
 288     int width8 = (width+7) >> 3;
 289     unsigned char*l1 = &data1[width8];
 290     unsigned char*l2 = &data2[width8];
 291     int fail = 0;
 292     for(y=1;y<height-1;y++) {
 293         for(x=0;x<width8;x++) {
 294             unsigned a = l1[x-width8] & l1[x] & l1[x+width8];
 295             unsigned b = l2[x-width8] & l2[x] & l2[x+width8];
 296
 297             if((a&B11100000) && !(l2[x]&B01000000))
 298                 fail == 1;
 299             if((a&B01110000) && !(l2[x]&B00100000))
 300                 fail == 1;
 301             if((a&B00111000) && !(l2[x]&B00010000))
 302                 fail == 1;
 303             if((a&B00011100) && !(l2[x]&B00001000))
 304                 fail == 1;
 305             if((a&B00001110) && !(l2[x]&B00000100))
 306                 fail == 1;
 307             if((a&B00000111) && !(l2[x]&B00000010))
 308                 fail == 1;
 309
 310             if((b&B11100000) && !(l1[x]&B01000000))
 311                 fail == 1;
 312             if((b&B01110000) && !(l1[x]&B00100000))
 313                 fail == 1;
 314             if((b&B00111000) && !(l1[x]&B00010000))
 315                 fail == 1;
 316             if((b&B00011100) && !(l1[x]&B00001000))
 317                 fail == 1;
 318             if((b&B00001110) && !(l1[x]&B00000100))
 319                 fail == 1;
 320             if((b&B00000111) && !(l1[x]&B00000010))
 321                 fail == 1;
 322         }
 323         l1 += width8;
 324         l2 += width8;
 325     }
 326     return !fail;
 327 }
 328
 329
 330 //-----------------------------------------------------------------------------------------------
 331
 332 static ArtVpath* gfxline_to_ArtVpath(gfxline_t*line, char fill)
 333 {
 334     ArtVpath *vec = NULL;
 335     int pos=0,len=0;
 336     gfxline_t*l2;
 337     double x=0,y=0;
 338
 339     /* factor which determines into how many line fragments a spline is converted */
 340     double subfraction = 2.4;//0.3
 341
 342     l2 = line;
 343     while(l2) {
 344         if(l2->type == gfx_moveTo) {
 345             pos ++;
 346         } else if(l2->type == gfx_lineTo) {
 347             pos ++;
 348         } else if(l2->type == gfx_splineTo) {
 349             int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
 350             if(!parts) parts = 1;
 351             pos += parts + 1;
 352         }
 353         x = l2->x;
 354         y = l2->y;
 355         l2 = l2->next;
 356     }
 357     pos++;
 358     len = pos;
 359
 360     vec = art_new (ArtVpath, len+1);
 361
 362     pos = 0;
 363     l2 = line;
 364     while(l2) {
 365         if(l2->type == gfx_moveTo) {
 366             vec[pos].code = ART_MOVETO_OPEN;
 367             vec[pos].x = l2->x;
 368             vec[pos].y = l2->y;
 369             pos++;
 370             assert(pos<=len);
 371         } else if(l2->type == gfx_lineTo) {
 372             vec[pos].code = ART_LINETO;
 373             vec[pos].x = l2->x;
 374             vec[pos].y = l2->y;
 375             pos++;
 376             assert(pos<=len);
 377         } else if(l2->type == gfx_splineTo) {
 378             int i;
 379             int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
 380             if(!parts) parts = 1;
 381             double stepsize = 1.0/parts;
 382             for(i=0;i<=parts;i++) {
 383                 double t = (double)i*stepsize;
 384                 vec[pos].code = ART_LINETO;
 385                 vec[pos].x = l2->x*t*t + 2*l2->sx*t*(1-t) + x*(1-t)*(1-t);
 386                 vec[pos].y = l2->y*t*t + 2*l2->sy*t*(1-t) + y*(1-t)*(1-t);
 387                 pos++;
 388                 assert(pos<=len);
 389             }
 390         }
 391         x = l2->x;
 392         y = l2->y;
 393         l2 = l2->next;
 394     }
 395     vec[pos++].code = ART_END;
 396     assert(pos == len);
 397
 398     if(!fill) {
 399         /* Fix "dotted" lines. Those are lines where singular points are created
 400            by a moveto x,y lineto x,y combination. We "fix" these by shifting the
 401            point in the lineto a little bit to the right
 402            These should only occur in strokes, not in fills, so do this only
 403            when we know we're not filling.
 404          */
 405         int t;
 406         for(t=0;vec[t].code!=ART_END;t++) {
 407             if(t>0 && (vec[t-1].code==ART_MOVETO_OPEN || vec[t-1].code==ART_MOVETO)
 408                    && vec[t].code==ART_LINETO && vec[t+1].code!=ART_LINETO &&
 409                 vec[t-1].x == vec[t].x &&
 410                 vec[t-1].y == vec[t].y) {
 411                 vec[t].x += 0.01;
 412             }
 413         }
 414     }
 415
 416     /* Find adjacent identical points. If an ajdacent pair of identical
 417        points is found, the second is removed.
 418        So moveto x,y lineto x,y becomes moveto x,y
 419           lineto x,y lineto x,y becomes lineto x,y
 420           lineto x,y moveto x,y becomes lineto x,y
 421           moveto x,y moveto x,y becomes moveto x,y
 422           lineto x,y lineto x2,y2 becomes lineto x2,y2 (if dir(x,y) ~= dir(x2,y2))
 423      */
 424     pos = 0;
 425     int outpos = 0;
 426     while(1)
 427     {
 428         if(vec[pos].code == ART_END) {
 429             vec[outpos++] = vec[pos++];
 430             break;
 431         }
 432
 433         char samedir = 0, samepoint = 0;
 434         if(outpos) {
 435             double dx = vec[pos].x-vec[pos-1].x;
 436             double dy = vec[pos].y-vec[pos-1].y;
 437             /*if(pos<len-1 && vec[pos].code == ART_LINETO && vec[pos+1].code == ART_LINETO) {
 438                 double dx2 = vec[pos+1].x-vec[pos].x;
 439                 double dy2 = vec[pos+1].y-vec[pos].y;
 440                 if(fabs(dx*dy2 - dy*dx2) < 0.0001 && dx*dx2 + dy*dy2 >= 0) {
 441                     samedir=1;
 442                 }
 443             }*/
 444             if(fabs(dx) + fabs(dy) < 0.0001) {
 445                 samepoint=1;
 446             }
 447         }
 448         if(!samepoint && !samedir) {
 449             vec[outpos++] = vec[pos++];
 450         } else {
 451             pos++; // skip
 452         }
 453     }
 454
 455     return vec;
 456 }
 457
 458 static void shear_svp(ArtSVP*svp, double v)
 459 {
 460     /* do a "shearing" on the polygon. We do this to eliminate all
 461        horizontal lines (which libart can't handle properly, even though
 462        it tries). */
 463
 464     int t;
 465     for(t=0;t<svp->n_segs;t++) {
 466         ArtSVPSeg* seg = &svp->segs[t];
 467         int s;
 468         for(s=0;s<seg->n_points;s++) {
 469             ArtPoint* point = &seg->points[s];
 470             point->y += point->x*v;
 471         }
 472     }
 473 }
 474
 475 static double find_shear_value(ArtSVP*svp)
 476 {
 477     /* We try random values until we find one
 478        where there's no slope below a given value, or if that fails,
 479        at least no slope of 0 */
 480
 481     double v = 0;
 482     int tries = 0;
 483     while(1) {
 484         char fail = 0;
 485         int t;
 486         for(t=0;t<svp->n_segs;t++) {
 487             ArtSVPSeg* seg = &svp->segs[t];
 488             int s;
 489             for(s=0;s<seg->n_points-1;s++) {
 490                 ArtPoint* p1 = &seg->points[s];
 491                 ArtPoint* p2 = &seg->points[s+1];
 492                 double dx = p2->x - p1->x;
 493                 double dy = p2->y - p1->y;
 494                 dy += dx*v;
 495                 if(dy==0) {
 496                     fail = 1;
 497                     break;
 498                 }
 499                 if(tries<100 && dx && fabs(dy / dx) < 1e-5) {
 500                     fail = 1;
 501                     break;
 502                 }
 503             }
 504             if(fail)
 505                 break;
 506         }
 507         if(!fail)
 508             break;
 509         v = lrand48() / 2000000000.0;
 510         tries++;
 511     }
 512     return v;
 513 }
 514
 515 void show_path(ArtSVP*path)
 516 {
 517     int t;
 518     printf("Segments: %d\n", path->n_segs);
 519     for(t=0;t<path->n_segs;t++) {
 520         ArtSVPSeg* seg = &path->segs[t];
 521         printf("Segment %d: %d points, %s, BBox: (%f,%f,%f,%f)\n",
 522                 t, seg->n_points, seg->dir==0?"UP  ":"DOWN",
 523                 seg->bbox.x0, seg->bbox.y0, seg->bbox.x1, seg->bbox.y1);
 524         int p;
 525         for(p=0;p<seg->n_points;p++) {
 526             ArtPoint* point = &seg->points[p];
 527             printf("        (%f,%f)\n", point->x, point->y);
 528         }
 529     }
 530     printf("\n");
 531 }
 532
 533
 534 typedef struct svp_segment_part
 535 {
 536     double y1;
 537     double y2;
 538     char active;
 539 } svp_segment_part_t;
 540
 541 int compare_double(const void*_y1, const void*_y2)
 542 {
 543     const double*y1 = _y1;
 544     const double*y2 = _y2;
 545     if(*y1<*y2) return -1;
 546     if(*y1>*y2) return 1;
 547     else return 0;
 548 }
 549
 550 int compare_seg_start(const void*_s1, const void*_s2)
 551 {
 552     svp_segment_part_t*s1 = *(svp_segment_part_t**)_s1;
 553     svp_segment_part_t*s2 = *(svp_segment_part_t**)_s2;
 554     if(s1->y1 < s2->y1) return -1;
 555     if(s1->y1 > s2->y1) return 1;
 556     else return 0;
 557 }
 558
 559 int compare_seg_end(const void*_s1, const void*_s2)
 560 {
 561     svp_segment_part_t*s1 = *(svp_segment_part_t**)_s1;
 562     svp_segment_part_t*s2 = *(svp_segment_part_t**)_s2;
 563     if(s1->y2 < s2->y2) return -1;
 564     if(s1->y2 > s2->y2) return 1;
 565     else return 0;
 566 }
 567
 568 void clean_svp(ArtSVP*svp)
 569 {
 570     int t;
 571     int oldpoints = 0;
 572     int newpoints = 0;
 573     int oldsegs = 0;
 574     int newsegs = 0;
 575     for(t=0;t<svp->n_segs;t++) {
 576         ArtSVPSeg* seg = &svp->segs[t];
 577         int p;
 578         int pos=0;
 579         double lasty = 0;
 580         oldpoints += seg->n_points;
 581         for(p=0;p<seg->n_points;p++) {
 582             ArtPoint* p1 = &seg->points[p];
 583             if(!p || lasty!=p1->y) {
 584                 seg->points[pos] = seg->points[p];
 585                 pos++;
 586                 lasty = p1->y;
 587             }
 588         }
 589         seg->n_points = pos;
 590         newpoints += seg->n_points;
 591     }
 592     int pos = 0;
 593     oldsegs = svp->n_segs;
 594     for(t=0;t<svp->n_segs;t++) {
 595         if(svp->segs[t].n_points > 1) {
 596             svp->segs[pos++] = svp->segs[t];
 597         }
 598     }
 599     svp->n_segs = pos;
 600     newsegs = svp->n_segs;
 601     if(newsegs < oldsegs || newpoints < oldpoints) {
 602         msg("<verbose> Simplified polygon from %d points to %d points, %d to %d segs",
 603                 oldpoints, newpoints, oldsegs, newsegs);
 604     }
 605 }
 606
 607 int check_svp(ArtSVP*svp)
 608 {
 609     /* count number of y coordinates and segs */
 610     int t;
 611     int num_points = 0;
 612     int num_segs = 0;
 613     for(t=0;t<svp->n_segs;t++) {
 614         if(!svp->segs[t].n_points) {
 615             msg("<error> svp contains segment with zero points\n");
 616             return 0;
 617         }
 618         num_points += svp->segs[t].n_points;
 619         num_segs += svp->segs[t].n_points - 1;
 620     }
 621
 622     /* create segs and ys */
 623     double*y = malloc(sizeof(double)*num_points);
 624     svp_segment_part_t*segs = malloc(sizeof(svp_segment_part_t)*num_segs);
 625     svp_segment_part_t**seg_start = malloc(sizeof(svp_segment_part_t*)*num_segs);
 626     svp_segment_part_t**seg_end = malloc(sizeof(svp_segment_part_t*)*num_segs);
 627
 628     int c1=0;
 629     num_segs = 0;
 630     for(t=0;t<svp->n_segs;t++) {
 631         ArtSVPSeg* seg = &svp->segs[t];
 632         int p;
 633         for(p=0;p<seg->n_points;p++) {
 634             y[c1++] = seg->points[p].y;
 635             assert(c1 <= num_points);
 636         }
 637         for(p=0;p<seg->n_points-1;p++) {
 638             ArtPoint* p1 = &seg->points[p];
 639             ArtPoint* p2 = &seg->points[p+1];
 640
 641             if(p1->y >= p2->y) {
 642                 if(p1->y > p2->y) {
 643                     msg("<error> bad svp, y in seg is non-increasing %.16f -> %.16f\n", p1->y, p2->y);
 644                 }
 645             } else {
 646                 segs[num_segs].y1 = p1->y;
 647                 segs[num_segs].y2 = p2->y;
 648                 segs[num_segs].active = 0;
 649                 seg_start[num_segs] = &segs[num_segs];
 650                 seg_end[num_segs] = &segs[num_segs];
 651                 num_segs++;
 652             }
 653         }
 654     }
 655
 656     qsort(y, num_points, sizeof(double), compare_double);
 657     qsort(seg_start, num_segs, sizeof(svp_segment_part_t*), compare_seg_start);
 658     qsort(seg_end, num_segs, sizeof(svp_segment_part_t*), compare_seg_end);
 659
 660     double lasty = y[0]+1;
 661     int num_active = 0;
 662     int bleed = 0;
 663     double bleedy1=0,bleedy2 = 0;
 664     for(t=0;t<num_points;t++) {
 665         if(lasty == y[t])
 666             continue;
 667         int s;
 668         for(s=0;s<num_segs;s++) {
 669             if(segs[s].y1==y[t]) {
 670                 /* segment is starting */
 671                 segs[s].active = 1;
 672                 num_active++;
 673             } else if(segs[s].y2==y[t]) {
 674                 segs[s].active = 0;
 675                 num_active--;
 676             }
 677         }
 678         if(num_active&1) {
 679             bleed = num_active;
 680             bleedy1 = y[t];
 681         } else {
 682             if(bleed) {
 683                 bleedy2 = y[t];
 684                 break;
 685             }
 686         }
 687         lasty = y[t];
 688     }
 689     if(bleed) {
 690         msg("<verbose> svp bleeds from y=%.16f to y=%.16f (%d/%d active segments)\n",
 691                 bleedy1, bleedy2,
 692                 bleed, num_segs);
 693         free(y);free(segs);free(seg_start);free(seg_end);
 694         return 0;
 695     }
 696
 697     free(y);
 698     free(segs);
 699     free(seg_start);
 700     free(seg_end);
 701
 702     return 1;
 703 }
 704
 705 void write_svp_postscript(const char*filename, ArtSVP*svp)
 706 {
 707     if(!svp)
 708         return;
 709     printf("writing %s\n", filename);
 710     FILE*fi = fopen(filename, "wb");
 711     int i, j;
 712     double xmin=0,ymin=0,xmax=0,ymax=0;
 713     fprintf(fi, "%% begin\n");
 714     for (i = 0; i < svp->n_segs; i++) {
 715         for (j = 0; j < svp->segs[i].n_points; j++) {
 716             double x = svp->segs[i].points[j].x;
 717             double y = svp->segs[i].points[j].y;
 718             if(i==0 && j==0) {
 719                 xmin = xmax = x;
 720                 ymin = ymax = y;
 721             } else {
 722                 if(x < xmin) xmin = x;
 723                 if(x > xmax) xmax = x;
 724                 if(y < ymin) ymin = y;
 725                 if(y > ymax) ymax = y;
 726             }
 727         }
 728     }
 729     if(xmax == xmin) xmax=xmin+1;
 730     if(ymax == ymin) ymax=ymin+1;
 731
 732     for (i = 0; i < svp->n_segs; i++)
 733       {
 734         fprintf(fi, "%g setgray\n", svp->segs[i].dir ? 0.7 : 0);
 735         for (j = 0; j < svp->segs[i].n_points; j++)
 736           {
 737             //fprintf(fi, "%g %g %s\n",
 738             //        20 + 550*(svp->segs[i].points[j].x-xmin)/(xmax-xmin),
 739             //        820 - 800*(svp->segs[i].points[j].y-ymin)/(ymax-ymin),
 740             //        j ? "lineto" : "moveto");
 741             fprintf(fi, "%.32f %.32f %s\n",
 742                     svp->segs[i].points[j].x,
 743                     svp->segs[i].points[j].y,
 744                     j ? "lineto" : "moveto");
 745           }
 746         fprintf(fi, "stroke\n");
 747       }
 748
 749     fprintf(fi, "showpage\n");
 750     fclose(fi);
 751 }
 752
 753 void write_vpath_postscript(const char*filename, ArtVpath*path)
 754 {
 755     FILE*fi = fopen(filename, "wb");
 756     int i, j;
 757     double xmin=0,ymin=0,xmax=0,ymax=0;
 758     fprintf(fi, "%% begin\n");
 759     ArtVpath*p = path;
 760     char first = 1;
 761     while(p->code != ART_END) {
 762         if(p->code == ART_MOVETO || p->code == ART_MOVETO_OPEN) {
 763             if(!first)
 764                 fprintf(fi, "stroke\n");
 765             first = 0;
 766             fprintf(fi, "0.0 setgray\n");
 767             fprintf(fi, "%.32f %.32f moveto\n", p->x, p->y);
 768         } else {
 769             fprintf(fi, "%.32f %.32f lineto\n", p->x, p->y);
 770         }
 771         p++;
 772     }
 773     if(!first)
 774         fprintf(fi, "stroke\n");
 775     fprintf(fi, "showpage\n");
 776     fclose(fi);
 777 }
 778
 779 void write_gfxline_postscript(const char*filename, gfxline_t*line)
 780 {
 781     FILE*fi = fopen(filename, "wb");
 782     int i, j;
 783     fprintf(fi, "%% begin\n");
 784     char first = 1;
 785     while(line) {
 786         if(line->type == gfx_moveTo) {
 787             if(!first)
 788                 fprintf(fi, "stroke\n");
 789             first = 0;
 790             fprintf(fi, "0.0 setgray\n");
 791             fprintf(fi, "%.32f %.32f moveto\n", line->x, line->y);
 792         } else {
 793             fprintf(fi, "%.32f %.32f lineto\n", line->x, line->y);
 794         }
 795         line = line->next;
 796     }
 797     if(!first)
 798         fprintf(fi, "stroke\n");
 799     fprintf(fi, "showpage\n");
 800     fclose(fi);
 801 }
 802
 803 static int vpath_len(ArtVpath*svp)
 804 {
 805     int len = 0;
 806     while(svp->code != ART_END) {
 807         svp ++;
 808         len ++;
 809     }
 810     return len;
 811 }
 812
 813 int gfxline_len(gfxline_t*line)
 814 {
 815     gfxline_t*i = line;
 816     int len = 0;
 817     while(i) {
 818         len ++;
 819         i = i->next;
 820     }
 821     return len;
 822 }
 823
 824 static ArtVpath*pvpath= 0;
 825 static int cmppos(const void*_p1, const void*_p2)
 826 {
 827     int*p1 = (int*)_p1;
 828     int*p2 = (int*)_p2;
 829     ArtVpath*v1 = &pvpath[*p1];
 830     ArtVpath*v2 = &pvpath[*p2];
 831     if(v1->y < v2->y)
 832         return -1;
 833     else if(v1->y > v2->y)
 834         return 1;
 835     else if(v1->x < v2->x)
 836         return -2;
 837     else if(v1->x > v2->x)
 838         return 2;
 839     else
 840         return 0;
 841 }
 842
 843 #define PERTURBATION 2e-3
 844 static void my_perturb(ArtVpath*vpath)
 845 {
 846     int t;
 847     int len = vpath_len(vpath);
 848     int*pos = (int*)malloc(len*sizeof(int));
 849     for(t=0;t<len;t++)
 850         pos[t] = t;
 851     pvpath = vpath;
 852     qsort(pos, len, sizeof(int), cmppos);
 853     t=0;
 854     while(t<len) {
 855         int t2=t+1;
 856         while(t2<len && !cmppos(&pos[t],&pos[t2])) {
 857             t2++;
 858         }
 859
 860         double dx = (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5;
 861         double dy = (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5;
 862         int s;
 863         for(s=t;s<t2;s++) {
 864             vpath[pos[s]].x += dx;
 865             vpath[pos[s]].y += dy;
 866         }
 867         t = t2;
 868     }
 869     free(pos);
 870     pvpath = 0;
 871 }
 872
 873 static ArtSVP* gfxfillToSVP(gfxline_t*line, int perturb)
 874 {
 875     ArtVpath* vec = gfxline_to_ArtVpath(line, 1);
 876     msg("<verbose> Casting gfxline of %d segments (%d line segments) to a gfxpoly", gfxline_len(line), vpath_len(vec));
 877
 878     if(perturb) {
 879         //ArtVpath* vec2 = art_vpath_perturb(vec);
 880         //free(vec);
 881         //vec = vec2;
 882         my_perturb(vec);
 883     }
 884     ArtSVP *svp = art_svp_from_vpath(vec);
 885     free(vec);
 886
 887     return svp;
 888 }
 889
 890 //#ifdef SHEAR
 891 //    double shear = find_shear_value(svp);
 892 //    gfxline_t*line =  gfxpoly_to_gfxline((gfxpoly_t*)svp);
 893 //    gfxline_t*l = line;
 894 //    while(l) {
 895 //        l->y += l->x*shear;
 896 //        l->sy += l->sx*shear;
 897 //        l= l->next;
 898 //    }
 899 //    svp = (ArtSVP*)gfxpoly_fillToPoly(line);
 900 //    printf("shearing svp by %.16f\n", shear);
 901 //#endif
 902 // ....
 903 //#ifdef SHEAR
 904 //    art_svp_free(svp);
 905 //    shear_svp(result, -shear);
 906 //#endif
 907
 908
 909
 910 extern const ArtSVP* current_svp;
 911 extern void art_report_error();
 912 extern int art_error_in_intersector;
 913
 914 ArtSVP* run_intersector(ArtSVP*svp, ArtWindRule rule)
 915 {
 916     ArtSvpWriter * swr = art_svp_writer_rewind_new(rule);
 917
 918     double zoom = 1.0;
 919     intbbox_t bbox = get_svp_bbox(svp, zoom);
 920
 921     art_svp_intersector(svp, swr);
 922     ArtSVP*result = art_svp_writer_rewind_reap(swr);
 923     clean_svp(result);
 924     if(!check_svp(result)) {
 925         current_svp = result;
 926         art_report_error(); // might set art_error_in_intersector
 927     } else {
 928         unsigned char*data1 = render_svp(svp, &bbox, zoom, rule);
 929         unsigned char*data2 = render_svp(result, &bbox, zoom, ART_WIND_RULE_ODDEVEN);
 930         msg("<verbose> Comparing polygon renderings of size %dx%d and %dx%d", bbox.width, bbox.height, bbox.width, bbox.height);
 931         if(!compare_bitmaps(&bbox, data1, data2)) {
 932             msg("<verbose> Bad SVP rewinding result- polygons don't match");
 933             current_svp = result;
 934             art_report_error(); // might set art_error_in_intersector
 935         }
 936         free(data1);
 937         free(data2);
 938     }
 939
 940     if(art_error_in_intersector) {
 941         msg("<verbose> Error in polygon processing");
 942         art_svp_free(result);
 943         art_error_in_intersector=0;
 944         return 0;
 945     }
 946     return result;
 947 }
 948
 949 gfxline_t* gfxpoly_to_gfxline(gfxpoly_t*poly)
 950 {
 951     ArtSVP*svp = (ArtSVP*)poly;
 952     int size = 0;
 953     int t;
 954     int pos = 0;
 955
 956     msg("<verbose> Casting polygon of %d segments back to gfxline", svp->n_segs);
 957
 958     for(t=0;t<svp->n_segs;t++) {
 959         size += svp->segs[t].n_points;
 960     }
 961     size = size + 1;
 962     gfxline_t* lines = (gfxline_t*)rfx_alloc(sizeof(gfxline_t)*size);
 963
 964     for(t=0;t<svp->n_segs;t++) {
 965         ArtSVPSeg* seg = &svp->segs[t];
 966         int p;
 967         for(p=0;p<seg->n_points;p++) {
 968             lines[pos].type = p==0?gfx_moveTo:gfx_lineTo;
 969             ArtPoint* point = &seg->points[p];
 970             lines[pos].x = point->x;
 971             lines[pos].y = point->y;
 972             lines[pos].next = &lines[pos+1];
 973             pos++;
 974         }
 975     }
 976     if(pos) {
 977         lines[pos-1].next = 0;
 978         return lines;
 979     } else {
 980         return 0;
 981     }
 982 }
 983
 984 gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line)
 985 {
 986     /* I'm not sure whether doing perturbation here is actually
 987        a good idea- if that line has been run through the machine
 988        several times already, it might be safer to leave it alone,
 989        since it should already be in a format libart can handle */
 990 #ifdef PERTURBATE
 991     ArtSVP* svp = gfxfillToSVP(line, 1);
 992 #else
 993     ArtSVP* svp = gfxfillToSVP(line, 0);
 994 #endif
 995
 996 #ifdef DEBUG
 997     char filename[80];
 998     static int counter = 0;
 999     sprintf(filename, "svp%d.ps", counter);
1000     write_svp_postscript(filename, svp);
1001     sprintf(filename, "gfxline%d.ps", counter);
1002     write_gfxline_postscript(filename, line);
1003 #endif
1004
1005     /* we do xor-filling by default, so dir is always 1
1006        (actually for oddeven rewinding it makes no difference, but
1007         it's "cleaner")
1008      */
1009     int t;
1010     for(t=0; t<svp->n_segs; t++) {
1011         svp->segs[t].dir = 1;
1012     }
1013
1014     /* for some reason, we need to rewind / self-intersect the polygons that gfxfillToSVP
1015        returns- art probably uses a different fill mode (circular?) for vpaths */
1016     ArtSVP*svp_uncrossed=0;
1017
1018 #ifdef DEBUG
1019     sprintf(filename, "svp%d_in.ps", counter);
1020     write_svp_postscript(filename, svp);
1021     counter++;
1022 #endif
1023
1024     svp_uncrossed = run_intersector(svp, ART_WIND_RULE_ODDEVEN);
1025
1026     art_svp_free(svp);
1027     svp=svp_uncrossed;
1028
1029     return (gfxpoly_t*)svp;
1030 }
1031
1032 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*poly1, gfxpoly_t*poly2)
1033 {
1034     ArtSvpWriter *swr;
1035
1036     static int counter = 0;
1037
1038     ArtSVP* svp1 = (ArtSVP*)poly1;
1039     ArtSVP* svp2 = (ArtSVP*)poly2;
1040     msg("<verbose> Intersecting two polygons of %d and %d segments", svp1->n_segs, svp2->n_segs);
1041
1042 #ifdef DEBUG
1043     char filename[80];
1044     sprintf(filename, "isvp%d_src1.ps", counter);
1045     write_svp_postscript(filename, svp1);
1046     sprintf(filename, "isvp%d_src2.ps", counter);
1047     write_svp_postscript(filename, svp2);
1048 #endif
1049
1050     ArtSVP* svp3 = art_svp_merge (svp1, svp2);
1051
1052 #ifdef DEBUG
1053     sprintf(filename, "isvp%d_src.ps", counter);
1054     write_svp_postscript(filename, svp3);
1055 #endif
1056
1057     //write_svp_postscript("svp.ps", svp3);
1058     ArtSVP*svp_new = run_intersector(svp3, ART_WIND_RULE_INTERSECT);
1059
1060     art_free (svp3); /* shallow free because svp3 contains shared segments */
1061
1062 #ifdef DEBUG
1063     sprintf(filename, "isvp%d.ps", counter);
1064     write_svp_postscript(filename, svp_new);
1065 #endif
1066
1067     counter++;
1068
1069     //write_svp_postscript("svp_new.ps", svp_new);
1070
1071     return (gfxpoly_t*)svp_new;
1072 }
1073
1074 gfxpoly_t* gfxpoly_union(gfxpoly_t*poly1, gfxpoly_t*poly2)
1075 {
1076     ArtSVP* svp1 = (ArtSVP*)poly1;
1077     ArtSVP* svp2 = (ArtSVP*)poly2;
1078     msg("<verbose> Unifying two polygons of %d and %d segments", svp1->n_segs, svp2->n_segs);
1079
1080     ArtSVP* svp = art_svp_union(svp1, svp2);
1081     return (gfxpoly_t*)svp;
1082 }
1083
1084 gfxpoly_t* gfxpoly_strokeToPoly(gfxline_t*line, gfxcoord_t width, gfx_capType cap_style, gfx_joinType joint_style, double miterLimit)
1085 {
1086     ArtVpath* vec = gfxline_to_ArtVpath(line, 0);
1087     msg("<verbose> Casting gfxline of %d segments to a stroke-polygon", gfxline_len(line));
1088
1089     ArtVpath* vec2 = art_vpath_perturb(vec);
1090     free(vec);
1091     vec = vec2;
1092
1093     ArtSVP *svp = art_svp_vpath_stroke (vec,
1094                         (joint_style==gfx_joinMiter)?ART_PATH_STROKE_JOIN_MITER:
1095                         ((joint_style==gfx_joinRound)?ART_PATH_STROKE_JOIN_ROUND:
1096                          ((joint_style==gfx_joinBevel)?ART_PATH_STROKE_JOIN_BEVEL:ART_PATH_STROKE_JOIN_BEVEL)),
1097                         (cap_style==gfx_capButt)?ART_PATH_STROKE_CAP_BUTT:
1098                         ((cap_style==gfx_capRound)?ART_PATH_STROKE_CAP_ROUND:
1099                          ((cap_style==gfx_capSquare)?ART_PATH_STROKE_CAP_SQUARE:ART_PATH_STROKE_CAP_SQUARE)),
1100                         width, //line_width
1101                         miterLimit, //miter_limit
1102                         0.05 //flatness
1103                         );
1104     free(vec);
1105     return (gfxpoly_t*)svp;
1106 }
1107
1108 gfxline_t* gfxline_circularToEvenOdd(gfxline_t*line)
1109 {
1110     msg("<verbose> Converting circular-filled gfxline of %d segments to even-odd filled gfxline", gfxline_len(line));
1111     ArtSVP* svp = gfxfillToSVP(line, 1);
1112
1113     /* TODO: ART_WIND_RULE_POSITIVE means that a shape is visible if
1114              positive and negative line segments add up to something positive.
1115              I *think* that clockwise fill in PDF is defined in a way, however,
1116              that the *last* shape's direction will determine whether something
1117              is filled */
1118     ArtSVP* svp_rewinded;
1119
1120     svp_rewinded = run_intersector(svp, ART_WIND_RULE_POSITIVE);
1121     if(!svp_rewinded) {
1122         art_svp_free(svp);
1123         return 0;
1124     }
1125
1126     gfxline_t* result = gfxpoly_to_gfxline((gfxpoly_t*)svp_rewinded);
1127     art_svp_free(svp);
1128     art_svp_free(svp_rewinded);
1129     return result;
1130 }
1131
1132 gfxpoly_t* gfxpoly_createbox(double x1, double y1,double x2, double y2)
1133 {
1134     ArtVpath *vec = art_new (ArtVpath, 5+1);
1135     vec[0].code = ART_MOVETO;
1136     vec[0].x = x1;
1137     vec[0].y = y1;
1138     vec[1].code = ART_LINETO;
1139     vec[1].x = x1;
1140     vec[1].y = y2;
1141     vec[2].code = ART_LINETO;
1142     vec[2].x = x2;
1143     vec[2].y = y2;
1144     vec[3].code = ART_LINETO;
1145     vec[3].x = x2;
1146     vec[3].y = y1;
1147     vec[4].code = ART_LINETO;
1148     vec[4].x = x1;
1149     vec[4].y = y1;
1150     vec[5].code = ART_END;
1151     vec[5].x = 0;
1152     vec[5].y = 0;
1153     ArtSVP *svp = art_svp_from_vpath(vec);
1154     free(vec);
1155     return (gfxpoly_t*)svp;
1156 }
1157
1158 void gfxpoly_free(gfxpoly_t*poly)
1159 {
1160     ArtSVP*svp = (ArtSVP*)poly;
1161     art_svp_free(svp);
1162 }