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