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