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     printf("writing %s\n", filename);
 727     FILE*fi = fopen(filename, "wb");
 728     int i, j;
 729     double xmin=0,ymin=0,xmax=0,ymax=0;
 730     fprintf(fi, "%% begin\n");
 731     for (i = 0; i < svp->n_segs; i++) {
 732         for (j = 0; j < svp->segs[i].n_points; j++) {
 733             double x = svp->segs[i].points[j].x;
 734             double y = svp->segs[i].points[j].y;
 735             if(i==0 && j==0) {
 736                 xmin = xmax = x;
 737                 ymin = ymax = y;
 738             } else {
 739                 if(x < xmin) xmin = x;
 740                 if(x > xmax) xmax = x;
 741                 if(y < ymin) ymin = y;
 742                 if(y > ymax) ymax = y;
 743             }
 744         }
 745     }
 746     if(xmax == xmin) xmax=xmin+1;
 747     if(ymax == ymin) ymax=ymin+1;
 748
 749     for (i = 0; i < svp->n_segs; i++)
 750       {
 751         fprintf(fi, "%g setgray\n", svp->segs[i].dir ? 0.7 : 0);
 752         for (j = 0; j < svp->segs[i].n_points; j++)
 753           {
 754             //fprintf(fi, "%g %g %s\n",
 755             //        20 + 550*(svp->segs[i].points[j].x-xmin)/(xmax-xmin),
 756             //        820 - 800*(svp->segs[i].points[j].y-ymin)/(ymax-ymin),
 757             //        j ? "lineto" : "moveto");
 758             fprintf(fi, "%.32f %.32f %s\n",
 759                     svp->segs[i].points[j].x,
 760                     svp->segs[i].points[j].y,
 761                     j ? "lineto" : "moveto");
 762           }
 763         fprintf(fi, "stroke\n");
 764       }
 765
 766     fprintf(fi, "showpage\n");
 767     fclose(fi);
 768 }
 769
 770 void write_vpath_postscript(const char*filename, ArtVpath*path)
 771 {
 772     FILE*fi = fopen(filename, "wb");
 773     int i, j;
 774     double xmin=0,ymin=0,xmax=0,ymax=0;
 775     fprintf(fi, "%% begin\n");
 776     ArtVpath*p = path;
 777     char first = 1;
 778     while(p->code != ART_END) {
 779         if(p->code == ART_MOVETO || p->code == ART_MOVETO_OPEN) {
 780             if(!first)
 781                 fprintf(fi, "stroke\n");
 782             first = 0;
 783             fprintf(fi, "0.0 setgray\n");
 784             fprintf(fi, "%.32f %.32f moveto\n", p->x, p->y);
 785         } else {
 786             fprintf(fi, "%.32f %.32f lineto\n", p->x, p->y);
 787         }
 788         p++;
 789     }
 790     if(!first)
 791         fprintf(fi, "stroke\n");
 792     fprintf(fi, "showpage\n");
 793     fclose(fi);
 794 }
 795
 796 void write_gfxline_postscript(const char*filename, gfxline_t*line)
 797 {
 798     FILE*fi = fopen(filename, "wb");
 799     int i, j;
 800     fprintf(fi, "%% begin\n");
 801     char first = 1;
 802     while(line) {
 803         if(line->type == gfx_moveTo) {
 804             if(!first)
 805                 fprintf(fi, "stroke\n");
 806             first = 0;
 807             fprintf(fi, "0.0 setgray\n");
 808             fprintf(fi, "%.32f %.32f moveto\n", line->x, line->y);
 809         } else {
 810             fprintf(fi, "%.32f %.32f lineto\n", line->x, line->y);
 811         }
 812         line = line->next;
 813     }
 814     if(!first)
 815         fprintf(fi, "stroke\n");
 816     fprintf(fi, "showpage\n");
 817     fclose(fi);
 818 }
 819
 820 static int vpath_len(ArtVpath*svp)
 821 {
 822     int len = 0;
 823     while(svp->code != ART_END) {
 824         svp ++;
 825         len ++;
 826     }
 827     return len;
 828 }
 829
 830 int gfxline_len(gfxline_t*line)
 831 {
 832     gfxline_t*i = line;
 833     int len = 0;
 834     while(i) {
 835         len ++;
 836         i = i->next;
 837     }
 838     return len;
 839 }
 840
 841 static ArtVpath*pvpath= 0;
 842 static int cmppos(const void*_p1, const void*_p2)
 843 {
 844     int*p1 = (int*)_p1;
 845     int*p2 = (int*)_p2;
 846     ArtVpath*v1 = &pvpath[*p1];
 847     ArtVpath*v2 = &pvpath[*p2];
 848     if(v1->y < v2->y)
 849         return -1;
 850     else if(v1->y > v2->y)
 851         return 1;
 852     else if(v1->x < v2->x)
 853         return -2;
 854     else if(v1->x > v2->x)
 855         return 2;
 856     else
 857         return 0;
 858 }
 859
 860 #define PERTURBATION 2e-3
 861 static void my_perturb(ArtVpath*vpath)
 862 {
 863     int t;
 864     int len = vpath_len(vpath);
 865     int*pos = (int*)malloc(len*sizeof(int));
 866     for(t=0;t<len;t++)
 867         pos[t] = t;
 868     pvpath = vpath;
 869     qsort(pos, len, sizeof(int), cmppos);
 870     t=0;
 871     while(t<len) {
 872         int t2=t+1;
 873         while(t2<len && !cmppos(&pos[t],&pos[t2])) {
 874             t2++;
 875         }
 876
 877         double dx = (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5;
 878         double dy = (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5;
 879         int s;
 880         for(s=t;s<t2;s++) {
 881             vpath[pos[s]].x += dx;
 882             vpath[pos[s]].y += dy;
 883         }
 884         t = t2;
 885     }
 886     free(pos);
 887     pvpath = 0;
 888 }
 889
 890 static ArtSVP* gfxfillToSVP(gfxline_t*line, int perturb)
 891 {
 892     ArtVpath* vec = gfxline_to_ArtVpath(line, 1);
 893     msg("<verbose> Casting gfxline of %d segments (%d line segments) to a gfxpoly", gfxline_len(line), vpath_len(vec));
 894
 895     if(perturb) {
 896         //ArtVpath* vec2 = art_vpath_perturb(vec);
 897         //free(vec);
 898         //vec = vec2;
 899         my_perturb(vec);
 900     }
 901     ArtSVP *svp = art_svp_from_vpath(vec);
 902     free(vec);
 903
 904     return svp;
 905 }
 906
 907 //#ifdef SHEAR
 908 //    double shear = find_shear_value(svp);
 909 //    gfxline_t*line =  gfxpoly_to_gfxline((gfxpoly_t*)svp);
 910 //    gfxline_t*l = line;
 911 //    while(l) {
 912 //        l->y += l->x*shear;
 913 //        l->sy += l->sx*shear;
 914 //        l= l->next;
 915 //    }
 916 //    svp = (ArtSVP*)gfxpoly_fillToPoly(line);
 917 //    printf("shearing svp by %.16f\n", shear);
 918 //#endif
 919 // ....
 920 //#ifdef SHEAR
 921 //    art_svp_free(svp);
 922 //    shear_svp(result, -shear);
 923 //#endif
 924
 925
 926
 927 extern const ArtSVP* current_svp;
 928 extern void art_report_error();
 929 extern int art_error_in_intersector;
 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* gfxpoly_to_gfxline(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_fillToPoly(gfxline_t*line)
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_strokeToPoly(gfxline_t*line, gfxcoord_t width, gfx_capType cap_style, gfx_joinType joint_style, double miterLimit)
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* gfxline_circularToEvenOdd(gfxline_t*line)
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     /* TODO: ART_WIND_RULE_POSITIVE means that a shape is visible if
1131              positive and negative line segments add up to something positive.
1132              I *think* that clockwise fill in PDF is defined in a way, however,
1133              that the *last* shape's direction will determine whether something
1134              is filled */
1135     ArtSVP* svp_rewinded;
1136
1137     svp_rewinded = run_intersector(svp, ART_WIND_RULE_POSITIVE);
1138     if(!svp_rewinded) {
1139         art_svp_free(svp);
1140         return 0;
1141     }
1142
1143     gfxline_t* result = gfxpoly_to_gfxline((gfxpoly_t*)svp_rewinded);
1144     art_svp_free(svp);
1145     art_svp_free(svp_rewinded);
1146     return result;
1147 }
1148
1149 gfxpoly_t* gfxpoly_createbox(double x1, double y1,double x2, double y2)
1150 {
1151     ArtVpath *vec = art_new (ArtVpath, 5+1);
1152     vec[0].code = ART_MOVETO;
1153     vec[0].x = x1;
1154     vec[0].y = y1;
1155     vec[1].code = ART_LINETO;
1156     vec[1].x = x1;
1157     vec[1].y = y2;
1158     vec[2].code = ART_LINETO;
1159     vec[2].x = x2;
1160     vec[2].y = y2;
1161     vec[3].code = ART_LINETO;
1162     vec[3].x = x2;
1163     vec[3].y = y1;
1164     vec[4].code = ART_LINETO;
1165     vec[4].x = x1;
1166     vec[4].y = y1;
1167     vec[5].code = ART_END;
1168     vec[5].x = 0;
1169     vec[5].y = 0;
1170     ArtSVP *svp = art_svp_from_vpath(vec);
1171     free(vec);
1172     return (gfxpoly_t*)svp;
1173 }
1174
1175 void gfxpoly_free(gfxpoly_t*poly)
1176 {
1177     ArtSVP*svp = (ArtSVP*)poly;
1178     art_svp_free(svp);
1179 }