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.xmax) 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 int compare_bitmaps(intbbox_t*bbox, unsigned char*data1, unsigned char*data2)
 300 {
 301     int similar = 0;
 302     int x,y;
 303     int height = bbox->height;
 304     int width = bbox->width;
 305     int width8 = (width+7) >> 3;
 306     unsigned char*l1 = &data1[width8];
 307     unsigned char*l2 = &data2[width8];
 308     int fail = 0;
 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))
 315                 fail == 1;
 316             if((a&B01110000) && !(l2[x]&B00100000))
 317                 fail == 1;
 318             if((a&B00111000) && !(l2[x]&B00010000))
 319                 fail == 1;
 320             if((a&B00011100) && !(l2[x]&B00001000))
 321                 fail == 1;
 322             if((a&B00001110) && !(l2[x]&B00000100))
 323                 fail == 1;
 324             if((a&B00000111) && !(l2[x]&B00000010))
 325                 fail == 1;
 326
 327             if((b&B11100000) && !(l1[x]&B01000000))
 328                 fail == 1;
 329             if((b&B01110000) && !(l1[x]&B00100000))
 330                 fail == 1;
 331             if((b&B00111000) && !(l1[x]&B00010000))
 332                 fail == 1;
 333             if((b&B00011100) && !(l1[x]&B00001000))
 334                 fail == 1;
 335             if((b&B00001110) && !(l1[x]&B00000100))
 336                 fail == 1;
 337             if((b&B00000111) && !(l1[x]&B00000010))
 338                 fail == 1;
 339         }
 340         l1 += width8;
 341         l2 += width8;
 342     }
 343     return !fail;
 344 }
 345
 346
 347 //-----------------------------------------------------------------------------------------------
 348
 349 static ArtVpath* gfxline_to_ArtVpath(gfxline_t*line, char fill)
 350 {
 351     ArtVpath *vec = NULL;
 352     int pos=0,len=0;
 353     gfxline_t*l2;
 354     double x=0,y=0;
 355
 356     /* factor which determines into how many line fragments a spline is converted */
 357     double subfraction = 2.4;//0.3
 358
 359     l2 = line;
 360     while(l2) {
 361         if(l2->type == gfx_moveTo) {
 362             pos ++;
 363         } else if(l2->type == gfx_lineTo) {
 364             pos ++;
 365         } else if(l2->type == gfx_splineTo) {
 366             int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
 367             if(!parts) parts = 1;
 368             pos += parts + 1;
 369         }
 370         x = l2->x;
 371         y = l2->y;
 372         l2 = l2->next;
 373     }
 374     pos++;
 375     len = pos;
 376
 377     vec = art_new (ArtVpath, len+1);
 378
 379     pos = 0;
 380     l2 = line;
 381     while(l2) {
 382         if(l2->type == gfx_moveTo) {
 383             vec[pos].code = ART_MOVETO_OPEN;
 384             vec[pos].x = l2->x;
 385             vec[pos].y = l2->y;
 386             pos++;
 387             assert(pos<=len);
 388         } else if(l2->type == gfx_lineTo) {
 389             vec[pos].code = ART_LINETO;
 390             vec[pos].x = l2->x;
 391             vec[pos].y = l2->y;
 392             pos++;
 393             assert(pos<=len);
 394         } else if(l2->type == gfx_splineTo) {
 395             int i;
 396             int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
 397             if(!parts) parts = 1;
 398             double stepsize = 1.0/parts;
 399             for(i=0;i<=parts;i++) {
 400                 double t = (double)i*stepsize;
 401                 vec[pos].code = ART_LINETO;
 402                 vec[pos].x = l2->x*t*t + 2*l2->sx*t*(1-t) + x*(1-t)*(1-t);
 403                 vec[pos].y = l2->y*t*t + 2*l2->sy*t*(1-t) + y*(1-t)*(1-t);
 404                 pos++;
 405                 assert(pos<=len);
 406             }
 407         }
 408         x = l2->x;
 409         y = l2->y;
 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 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         v = lrand48() / 2000000000.0;
 527         tries++;
 528     }
 529     return v;
 530 }
 531
 532 void show_path(ArtSVP*path)
 533 {
 534     int t;
 535     printf("Segments: %d\n", path->n_segs);
 536     for(t=0;t<path->n_segs;t++) {
 537         ArtSVPSeg* seg = &path->segs[t];
 538         printf("Segment %d: %d points, %s, BBox: (%f,%f,%f,%f)\n",
 539                 t, seg->n_points, seg->dir==0?"UP  ":"DOWN",
 540                 seg->bbox.x0, seg->bbox.y0, seg->bbox.x1, seg->bbox.y1);
 541         int p;
 542         for(p=0;p<seg->n_points;p++) {
 543             ArtPoint* point = &seg->points[p];
 544             printf("        (%f,%f)\n", point->x, point->y);
 545         }
 546     }
 547     printf("\n");
 548 }
 549
 550
 551 typedef struct svp_segment_part
 552 {
 553     double y1;
 554     double y2;
 555     char active;
 556 } svp_segment_part_t;
 557
 558 int compare_double(const void*_y1, const void*_y2)
 559 {
 560     const double*y1 = _y1;
 561     const double*y2 = _y2;
 562     if(*y1<*y2) return -1;
 563     if(*y1>*y2) return 1;
 564     else return 0;
 565 }
 566
 567 int compare_seg_start(const void*_s1, const void*_s2)
 568 {
 569     svp_segment_part_t*s1 = *(svp_segment_part_t**)_s1;
 570     svp_segment_part_t*s2 = *(svp_segment_part_t**)_s2;
 571     if(s1->y1 < s2->y1) return -1;
 572     if(s1->y1 > s2->y1) return 1;
 573     else return 0;
 574 }
 575
 576 int compare_seg_end(const void*_s1, const void*_s2)
 577 {
 578     svp_segment_part_t*s1 = *(svp_segment_part_t**)_s1;
 579     svp_segment_part_t*s2 = *(svp_segment_part_t**)_s2;
 580     if(s1->y2 < s2->y2) return -1;
 581     if(s1->y2 > s2->y2) return 1;
 582     else return 0;
 583 }
 584
 585 void clean_svp(ArtSVP*svp)
 586 {
 587     int t;
 588     int oldpoints = 0;
 589     int newpoints = 0;
 590     int oldsegs = 0;
 591     int newsegs = 0;
 592     for(t=0;t<svp->n_segs;t++) {
 593         ArtSVPSeg* seg = &svp->segs[t];
 594         int p;
 595         int pos=0;
 596         double lasty = 0;
 597         oldpoints += seg->n_points;
 598         for(p=0;p<seg->n_points;p++) {
 599             ArtPoint* p1 = &seg->points[p];
 600             if(!p || lasty!=p1->y) {
 601                 seg->points[pos] = seg->points[p];
 602                 pos++;
 603                 lasty = p1->y;
 604             }
 605         }
 606         seg->n_points = pos;
 607         newpoints += seg->n_points;
 608     }
 609     int pos = 0;
 610     oldsegs = svp->n_segs;
 611     for(t=0;t<svp->n_segs;t++) {
 612         if(svp->segs[t].n_points > 1) {
 613             svp->segs[pos++] = svp->segs[t];
 614         }
 615     }
 616     svp->n_segs = pos;
 617     newsegs = svp->n_segs;
 618     if(newsegs < oldsegs || newpoints < oldpoints) {
 619         msg("<verbose> Simplified polygon from %d points to %d points, %d to %d segs",
 620                 oldpoints, newpoints, oldsegs, newsegs);
 621     }
 622 }
 623
 624 int check_svp(ArtSVP*svp)
 625 {
 626     /* count number of y coordinates and segs */
 627     int t;
 628     int num_points = 0;
 629     int num_segs = 0;
 630     for(t=0;t<svp->n_segs;t++) {
 631         if(!svp->segs[t].n_points) {
 632             msg("<error> svp contains segment with zero points\n");
 633             return 0;
 634         }
 635         num_points += svp->segs[t].n_points;
 636         num_segs += svp->segs[t].n_points - 1;
 637     }
 638
 639     /* create segs and ys */
 640     double*y = malloc(sizeof(double)*num_points);
 641     svp_segment_part_t*segs = malloc(sizeof(svp_segment_part_t)*num_segs);
 642     svp_segment_part_t**seg_start = malloc(sizeof(svp_segment_part_t*)*num_segs);
 643     svp_segment_part_t**seg_end = malloc(sizeof(svp_segment_part_t*)*num_segs);
 644
 645     int c1=0;
 646     num_segs = 0;
 647     for(t=0;t<svp->n_segs;t++) {
 648         ArtSVPSeg* seg = &svp->segs[t];
 649         int p;
 650         for(p=0;p<seg->n_points;p++) {
 651             y[c1++] = seg->points[p].y;
 652             assert(c1 <= num_points);
 653         }
 654         for(p=0;p<seg->n_points-1;p++) {
 655             ArtPoint* p1 = &seg->points[p];
 656             ArtPoint* p2 = &seg->points[p+1];
 657
 658             if(p1->y >= p2->y) {
 659                 if(p1->y > p2->y) {
 660                     msg("<error> bad svp, y in seg is non-increasing %.16f -> %.16f\n", p1->y, p2->y);
 661                 }
 662             } else {
 663                 segs[num_segs].y1 = p1->y;
 664                 segs[num_segs].y2 = p2->y;
 665                 segs[num_segs].active = 0;
 666                 seg_start[num_segs] = &segs[num_segs];
 667                 seg_end[num_segs] = &segs[num_segs];
 668                 num_segs++;
 669             }
 670         }
 671     }
 672
 673     qsort(y, num_points, sizeof(double), compare_double);
 674     qsort(seg_start, num_segs, sizeof(svp_segment_part_t*), compare_seg_start);
 675     qsort(seg_end, num_segs, sizeof(svp_segment_part_t*), compare_seg_end);
 676
 677     double lasty = num_points?y[0]+1:0;
 678     int num_active = 0;
 679     int bleed = 0;
 680     double bleedy1=0,bleedy2 = 0;
 681     for(t=0;t<num_points;t++) {
 682         if(lasty == y[t])
 683             continue;
 684         int s;
 685         for(s=0;s<num_segs;s++) {
 686             if(segs[s].y1==y[t]) {
 687                 /* segment is starting */
 688                 segs[s].active = 1;
 689                 num_active++;
 690             } else if(segs[s].y2==y[t]) {
 691                 segs[s].active = 0;
 692                 num_active--;
 693             }
 694         }
 695         if(num_active&1) {
 696             bleed = num_active;
 697             bleedy1 = y[t];
 698         } else {
 699             if(bleed) {
 700                 bleedy2 = y[t];
 701                 break;
 702             }
 703         }
 704         lasty = y[t];
 705     }
 706     if(bleed) {
 707         msg("<verbose> svp bleeds from y=%.16f to y=%.16f (%d/%d active segments)\n",
 708                 bleedy1, bleedy2,
 709                 bleed, num_segs);
 710         free(y);free(segs);free(seg_start);free(seg_end);
 711         return 0;
 712     }
 713
 714     free(y);
 715     free(segs);
 716     free(seg_start);
 717     free(seg_end);
 718
 719     return 1;
 720 }
 721
 722 void write_svp_postscript(const char*filename, ArtSVP*svp)
 723 {
 724     if(!svp)
 725         return;
 726     FILE*fi = fopen(filename, "wb");
 727     int i, j;
 728     double xmin=0,ymin=0,xmax=0,ymax=0;
 729     fprintf(fi, "%% begin\n");
 730     for (i = 0; i < svp->n_segs; i++) {
 731         for (j = 0; j < svp->segs[i].n_points; j++) {
 732             double x = svp->segs[i].points[j].x;
 733             double y = svp->segs[i].points[j].y;
 734             if(i==0 && j==0) {
 735                 xmin = xmax = x;
 736                 ymin = ymax = y;
 737             } else {
 738                 if(x < xmin) xmin = x;
 739                 if(x > xmax) xmax = x;
 740                 if(y < ymin) ymin = y;
 741                 if(y > ymax) ymax = y;
 742             }
 743         }
 744     }
 745     if(xmax == xmin) xmax=xmin+1;
 746     if(ymax == ymin) ymax=ymin+1;
 747
 748     for (i = 0; i < svp->n_segs; i++)
 749       {
 750         fprintf(fi, "%g setgray\n", svp->segs[i].dir ? 0.7 : 0);
 751         for (j = 0; j < svp->segs[i].n_points; j++)
 752           {
 753             //fprintf(fi, "%g %g %s\n",
 754             //        20 + 550*(svp->segs[i].points[j].x-xmin)/(xmax-xmin),
 755             //        820 - 800*(svp->segs[i].points[j].y-ymin)/(ymax-ymin),
 756             //        j ? "lineto" : "moveto");
 757             fprintf(fi, "%.32f %.32f %s\n",
 758                     svp->segs[i].points[j].x,
 759                     svp->segs[i].points[j].y,
 760                     j ? "lineto" : "moveto");
 761           }
 762         fprintf(fi, "stroke\n");
 763       }
 764
 765     fprintf(fi, "showpage\n");
 766     fclose(fi);
 767 }
 768
 769 void write_vpath_postscript(const char*filename, ArtVpath*path)
 770 {
 771     FILE*fi = fopen(filename, "wb");
 772     int i, j;
 773     double xmin=0,ymin=0,xmax=0,ymax=0;
 774     fprintf(fi, "%% begin\n");
 775     ArtVpath*p = path;
 776     char first = 1;
 777     while(p->code != ART_END) {
 778         if(p->code == ART_MOVETO || p->code == ART_MOVETO_OPEN) {
 779             if(!first)
 780                 fprintf(fi, "stroke\n");
 781             first = 0;
 782             fprintf(fi, "0.0 setgray\n");
 783             fprintf(fi, "%.32f %.32f moveto\n", p->x, p->y);
 784         } else {
 785             fprintf(fi, "%.32f %.32f lineto\n", p->x, p->y);
 786         }
 787         p++;
 788     }
 789     if(!first)
 790         fprintf(fi, "stroke\n");
 791     fprintf(fi, "showpage\n");
 792     fclose(fi);
 793 }
 794
 795 void write_gfxline_postscript(const char*filename, gfxline_t*line)
 796 {
 797     FILE*fi = fopen(filename, "wb");
 798     int i, j;
 799     fprintf(fi, "%% begin\n");
 800     char first = 1;
 801     while(line) {
 802         if(line->type == gfx_moveTo) {
 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", line->x, line->y);
 808         } else {
 809             fprintf(fi, "%.32f %.32f lineto\n", line->x, line->y);
 810         }
 811         line = line->next;
 812     }
 813     if(!first)
 814         fprintf(fi, "stroke\n");
 815     fprintf(fi, "showpage\n");
 816     fclose(fi);
 817 }
 818
 819 static int vpath_len(ArtVpath*svp)
 820 {
 821     int len = 0;
 822     while(svp->code != ART_END) {
 823         svp ++;
 824         len ++;
 825     }
 826     return len;
 827 }
 828
 829 int gfxline_len(gfxline_t*line)
 830 {
 831     gfxline_t*i = line;
 832     int len = 0;
 833     while(i) {
 834         len ++;
 835         i = i->next;
 836     }
 837     return len;
 838 }
 839
 840 static ArtVpath*pvpath= 0;
 841 static int cmppos(const void*_p1, const void*_p2)
 842 {
 843     int*p1 = (int*)_p1;
 844     int*p2 = (int*)_p2;
 845     ArtVpath*v1 = &pvpath[*p1];
 846     ArtVpath*v2 = &pvpath[*p2];
 847     if(v1->y < v2->y)
 848         return -1;
 849     else if(v1->y > v2->y)
 850         return 1;
 851     else if(v1->x < v2->x)
 852         return -2;
 853     else if(v1->x > v2->x)
 854         return 2;
 855     else
 856         return 0;
 857 }
 858
 859 #define PERTURBATION 2e-3
 860 static void my_perturb(ArtVpath*vpath)
 861 {
 862     int t;
 863     int len = vpath_len(vpath);
 864     int*pos = (int*)malloc(len*sizeof(int));
 865     for(t=0;t<len;t++)
 866         pos[t] = t;
 867     pvpath = vpath;
 868     qsort(pos, len, sizeof(int), cmppos);
 869     t=0;
 870     while(t<len) {
 871         int t2=t+1;
 872         while(t2<len && !cmppos(&pos[t],&pos[t2])) {
 873             t2++;
 874         }
 875
 876         double dx = (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5;
 877         double dy = (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5;
 878         int s;
 879         for(s=t;s<t2;s++) {
 880             vpath[pos[s]].x += dx;
 881             vpath[pos[s]].y += dy;
 882         }
 883         t = t2;
 884     }
 885     free(pos);
 886     pvpath = 0;
 887 }
 888
 889 static ArtSVP* gfxfillToSVP(gfxline_t*line, int perturb)
 890 {
 891     ArtVpath* vec = gfxline_to_ArtVpath(line, 1);
 892     msg("<verbose> Casting gfxline of %d segments (%d line segments) to a gfxpoly", gfxline_len(line), vpath_len(vec));
 893
 894     if(perturb) {
 895         //ArtVpath* vec2 = art_vpath_perturb(vec);
 896         //free(vec);
 897         //vec = vec2;
 898         my_perturb(vec);
 899     }
 900     ArtSVP *svp = art_svp_from_vpath(vec);
 901     free(vec);
 902
 903     return svp;
 904 }
 905
 906 //#ifdef SHEAR
 907 //    double shear = find_shear_value(svp);
 908 //    gfxline_t*line =  gfxpoly_to_gfxline((gfxpoly_t*)svp);
 909 //    gfxline_t*l = line;
 910 //    while(l) {
 911 //        l->y += l->x*shear;
 912 //        l->sy += l->sx*shear;
 913 //        l= l->next;
 914 //    }
 915 //    svp = (ArtSVP*)gfxpoly_fillToPoly(line);
 916 //    printf("shearing svp by %.16f\n", shear);
 917 //#endif
 918 // ....
 919 //#ifdef SHEAR
 920 //    art_svp_free(svp);
 921 //    shear_svp(result, -shear);
 922 //#endif
 923
 924
 925 ArtSVP* run_intersector(ArtSVP*svp, ArtWindRule rule)
 926 {
 927     ArtSvpWriter * swr = art_svp_writer_rewind_new(rule);
 928
 929     double zoom = 1.0;
 930     intbbox_t bbox = get_svp_bbox(svp, zoom);
 931
 932     art_svp_intersector(svp, swr);
 933     ArtSVP*result = art_svp_writer_rewind_reap(swr);
 934     clean_svp(result);
 935     if(!check_svp(result)) {
 936         current_svp = result;
 937         art_report_error(); // might set art_error_in_intersector
 938     } else {
 939         msg("<verbose> Comparing polygon renderings of size %dx%d and %dx%d", bbox.width, bbox.height, bbox.width, bbox.height);
 940         unsigned char*data1 = render_svp(svp, &bbox, zoom, rule);
 941         unsigned char*data2 = render_svp(result, &bbox, zoom, ART_WIND_RULE_ODDEVEN);
 942         if(!compare_bitmaps(&bbox, data1, data2)) {
 943             msg("<verbose> Bad SVP rewinding result- polygons don't match");
 944             current_svp = result;
 945             art_report_error(); // might set art_error_in_intersector
 946         }
 947         free(data1);
 948         free(data2);
 949     }
 950
 951     if(art_error_in_intersector) {
 952         msg("<verbose> Error in polygon processing");
 953         art_svp_free(result);
 954         art_error_in_intersector=0;
 955         return 0;
 956     }
 957     return result;
 958 }
 959
 960 gfxline_t* gfxpoly_to_gfxline(gfxpoly_t*poly)
 961 {
 962     ArtSVP*svp = (ArtSVP*)poly;
 963     int size = 0;
 964     int t;
 965     int pos = 0;
 966
 967     msg("<verbose> Casting polygon of %d segments back to gfxline", svp->n_segs);
 968
 969     for(t=0;t<svp->n_segs;t++) {
 970         size += svp->segs[t].n_points;
 971     }
 972     size = size + 1;
 973     gfxline_t* lines = (gfxline_t*)rfx_alloc(sizeof(gfxline_t)*size);
 974
 975     for(t=0;t<svp->n_segs;t++) {
 976         ArtSVPSeg* seg = &svp->segs[t];
 977         int p;
 978         for(p=0;p<seg->n_points;p++) {
 979             lines[pos].type = p==0?gfx_moveTo:gfx_lineTo;
 980             ArtPoint* point = &seg->points[p];
 981             lines[pos].x = point->x;
 982             lines[pos].y = point->y;
 983             lines[pos].next = &lines[pos+1];
 984             pos++;
 985         }
 986     }
 987     if(pos) {
 988         lines[pos-1].next = 0;
 989         return lines;
 990     } else {
 991         return 0;
 992     }
 993 }
 994
 995 gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line)
 996 {
 997     /* I'm not sure whether doing perturbation here is actually
 998        a good idea- if that line has been run through the machinery
 999        several times already, it might be safer to leave it alone,
1000        since it should already be in a format libart can handle */
1001 #ifdef PERTURBATE
1002     ArtSVP* svp = gfxfillToSVP(line, 1);
1003 #else
1004     ArtSVP* svp = gfxfillToSVP(line, 0);
1005 #endif
1006
1007 #ifdef DEBUG
1008     char filename[80];
1009     static int counter = 0;
1010     sprintf(filename, "svp%d.ps", counter);
1011     write_svp_postscript(filename, svp);
1012     sprintf(filename, "gfxline%d.ps", counter);
1013     write_gfxline_postscript(filename, line);
1014 #endif
1015
1016     /* we do xor-filling by default, so dir is always 1
1017        (actually for oddeven rewinding it makes no difference, but
1018         it's "cleaner")
1019      */
1020     int t;
1021     for(t=0; t<svp->n_segs; t++) {
1022         svp->segs[t].dir = 1;
1023     }
1024
1025     /* for some reason, we need to rewind / self-intersect the polygons that gfxfillToSVP
1026        returns- art probably uses a different fill mode (circular?) for vpaths */
1027     ArtSVP*svp_uncrossed=0;
1028
1029 #ifdef DEBUG
1030     sprintf(filename, "svp%d_in.ps", counter);
1031     write_svp_postscript(filename, svp);
1032     counter++;
1033 #endif
1034
1035     svp_uncrossed = run_intersector(svp, ART_WIND_RULE_ODDEVEN);
1036
1037     art_svp_free(svp);
1038     svp=svp_uncrossed;
1039
1040     return (gfxpoly_t*)svp;
1041 }
1042
1043 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*poly1, gfxpoly_t*poly2)
1044 {
1045     ArtSvpWriter *swr;
1046
1047     static int counter = 0;
1048
1049     ArtSVP* svp1 = (ArtSVP*)poly1;
1050     ArtSVP* svp2 = (ArtSVP*)poly2;
1051     msg("<verbose> Intersecting two polygons of %d and %d segments", svp1->n_segs, svp2->n_segs);
1052
1053 #ifdef DEBUG
1054     char filename[80];
1055     sprintf(filename, "isvp%d_src1.ps", counter);
1056     write_svp_postscript(filename, svp1);
1057     sprintf(filename, "isvp%d_src2.ps", counter);
1058     write_svp_postscript(filename, svp2);
1059 #endif
1060
1061     ArtSVP* svp3 = art_svp_merge (svp1, svp2);
1062
1063 #ifdef DEBUG
1064     sprintf(filename, "isvp%d_src.ps", counter);
1065     write_svp_postscript(filename, svp3);
1066 #endif
1067
1068     //write_svp_postscript("svp.ps", svp3);
1069     ArtSVP*svp_new = run_intersector(svp3, ART_WIND_RULE_INTERSECT);
1070
1071     art_free (svp3); /* shallow free because svp3 contains shared segments */
1072
1073 #ifdef DEBUG
1074     sprintf(filename, "isvp%d.ps", counter);
1075     write_svp_postscript(filename, svp_new);
1076 #endif
1077
1078     counter++;
1079
1080     //write_svp_postscript("svp_new.ps", svp_new);
1081
1082     return (gfxpoly_t*)svp_new;
1083 }
1084
1085 gfxpoly_t* gfxpoly_union(gfxpoly_t*poly1, gfxpoly_t*poly2)
1086 {
1087     ArtSVP* svp1 = (ArtSVP*)poly1;
1088     ArtSVP* svp2 = (ArtSVP*)poly2;
1089     msg("<verbose> Unifying two polygons of %d and %d segments", svp1->n_segs, svp2->n_segs);
1090
1091     ArtSVP* svp = art_svp_union(svp1, svp2);
1092     return (gfxpoly_t*)svp;
1093 }
1094
1095 gfxpoly_t* gfxpoly_strokeToPoly(gfxline_t*line, gfxcoord_t width, gfx_capType cap_style, gfx_joinType joint_style, double miterLimit)
1096 {
1097     ArtVpath* vec = gfxline_to_ArtVpath(line, 0);
1098     msg("<verbose> Casting gfxline of %d segments to a stroke-polygon", gfxline_len(line));
1099
1100     ArtVpath* vec2 = art_vpath_perturb(vec);
1101     free(vec);
1102     vec = vec2;
1103
1104     ArtSVP *svp = art_svp_vpath_stroke (vec,
1105                         (joint_style==gfx_joinMiter)?ART_PATH_STROKE_JOIN_MITER:
1106                         ((joint_style==gfx_joinRound)?ART_PATH_STROKE_JOIN_ROUND:
1107                          ((joint_style==gfx_joinBevel)?ART_PATH_STROKE_JOIN_BEVEL:ART_PATH_STROKE_JOIN_BEVEL)),
1108                         (cap_style==gfx_capButt)?ART_PATH_STROKE_CAP_BUTT:
1109                         ((cap_style==gfx_capRound)?ART_PATH_STROKE_CAP_ROUND:
1110                          ((cap_style==gfx_capSquare)?ART_PATH_STROKE_CAP_SQUARE:ART_PATH_STROKE_CAP_SQUARE)),
1111                         width, //line_width
1112                         miterLimit, //miter_limit
1113                         0.05 //flatness
1114                         );
1115     free(vec);
1116     return (gfxpoly_t*)svp;
1117 }
1118
1119 gfxline_t* gfxline_circularToEvenOdd(gfxline_t*line)
1120 {
1121     msg("<verbose> Converting circular-filled gfxline of %d segments to even-odd filled gfxline", gfxline_len(line));
1122     ArtSVP* svp = gfxfillToSVP(line, 1);
1123
1124     /* TODO: ART_WIND_RULE_POSITIVE means that a shape is visible if
1125              positive and negative line segments add up to something positive.
1126              I *think* that clockwise fill in PDF is defined in a way, however,
1127              that the *last* shape's direction will determine whether something
1128              is filled */
1129     ArtSVP* svp_rewinded;
1130
1131     svp_rewinded = run_intersector(svp, ART_WIND_RULE_POSITIVE);
1132     if(!svp_rewinded) {
1133         art_svp_free(svp);
1134         return 0;
1135     }
1136
1137     gfxline_t* result = gfxpoly_to_gfxline((gfxpoly_t*)svp_rewinded);
1138     art_svp_free(svp);
1139     art_svp_free(svp_rewinded);
1140     return result;
1141 }
1142
1143 gfxpoly_t* gfxpoly_createbox(double x1, double y1,double x2, double y2)
1144 {
1145     ArtVpath *vec = art_new (ArtVpath, 5+1);
1146     vec[0].code = ART_MOVETO;
1147     vec[0].x = x1;
1148     vec[0].y = y1;
1149     vec[1].code = ART_LINETO;
1150     vec[1].x = x1;
1151     vec[1].y = y2;
1152     vec[2].code = ART_LINETO;
1153     vec[2].x = x2;
1154     vec[2].y = y2;
1155     vec[3].code = ART_LINETO;
1156     vec[3].x = x2;
1157     vec[3].y = y1;
1158     vec[4].code = ART_LINETO;
1159     vec[4].x = x1;
1160     vec[4].y = y1;
1161     vec[5].code = ART_END;
1162     vec[5].x = 0;
1163     vec[5].y = 0;
1164     ArtSVP *svp = art_svp_from_vpath(vec);
1165     free(vec);
1166     return (gfxpoly_t*)svp;
1167 }
1168
1169 void gfxpoly_free(gfxpoly_t*poly)
1170 {
1171     ArtSVP*svp = (ArtSVP*)poly;
1172     art_svp_free(svp);
1173 }