lib/gfxpoly.c

   1 /* gfxpoly.c
   2
   3    Various boolean polygon functions.
   4
   5    Part of the swftools package.
   6
   7    Copyright (c) 2005 Matthias Kramm <kramm@quiss.org>
   8
   9    This program is free software; you can redistribute it and/or modify
  10    it under the terms of the GNU General Public License as published by
  11    the Free Software Foundation; either version 2 of the License, or
  12    (at your option) any later version.
  13
  14    This program is distributed in the hope that it will be useful,
  15    but WITHOUT ANY WARRANTY; without even the implied warranty of
  16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17    GNU General Public License for more details.
  18
  19    You should have received a copy of the GNU General Public License
  20    along with this program; if not, write to the Free Software
  21    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  22
  23 #include "../config.h"
  24 #include "gfxdevice.h"
  25 #include "gfxtools.h"
  26 #include "gfxpoly.h"
  27 #include "mem.h"
  28 #ifdef INTERNAL_LIBART
  29 #include "art/libart.h"
  30 #include "art/art_svp_intersect.h"
  31 #include "art/art_svp_ops.h"
  32 #else
  33 #include <libart_lgpl/libart.h>
  34 #include <libart_lgpl/art_svp_intersect.h>
  35 #include <libart_lgpl/art_svp_ops.h>
  36 #endif
  37 #include "log.h"
  38 #include <assert.h>
  39 #include <memory.h>
  40 #include <math.h>
  41
  42 #define PERTURBATE
  43 //#define SHEAR
  44 //#define DEBUG
  45
  46 //----------------------------------------- svp renderer ----------------------------------------
  47
  48 typedef struct {
  49     int xmin;
  50     int ymin;
  51     int xmax;
  52     int ymax;
  53     int width;
  54     int height;
  55 } intbbox_t;
  56
  57 typedef struct _renderpoint
  58 {
  59     double x;
  60     signed char direction;
  61 } renderpoint_t;
  62
  63 typedef struct _renderline
  64 {
  65     renderpoint_t*points;
  66     int size;
  67     int num;
  68 } renderline_t;
  69
  70 typedef struct _renderbuf
  71 {
  72     intbbox_t bbox;
  73     int width;
  74     int height;
  75     double zoom;
  76     renderline_t*lines;
  77 } renderbuf_t;
  78
  79 static inline void add_pixel(renderbuf_t*buf, double x, int y, signed char direction)
  80 {
  81     renderpoint_t p;
  82     p.x = x;
  83     p.direction = direction;
  84
  85     if(x >= buf->bbox.xmax || y >= buf->bbox.ymax || y < buf->bbox.ymin)
  86         return;
  87     renderline_t*l = &buf->lines[y-buf->bbox.ymin];
  88
  89     if(l->num == l->size) {
  90         l->size += 32;
  91         l->points = (renderpoint_t*)rfx_realloc(l->points, l->size * sizeof(renderpoint_t));
  92     }
  93     l->points[l->num] = p;
  94     l->num++;
  95 }
  96 #define CUT 0.5
  97 #define INT(x) ((int)((x)+16)-16)
  98 static void add_line(renderbuf_t*buf, double x1, double y1, double x2, double y2, signed char direction)
  99 {
 100     x1 *= buf->zoom;
 101     y1 *= buf->zoom;
 102     x2 *= buf->zoom;
 103     y2 *= buf->zoom;
 104     double diffx, diffy;
 105     double ny1, ny2, stepx;
 106     if(y2 < y1) {
 107         double x,y;
 108         x = x1;x1 = x2;x2=x;
 109         y = y1;y1 = y2;y2=y;
 110     }
 111     diffx = x2 - x1;
 112     diffy = y2 - y1;
 113     ny1 = INT(y1)+CUT;
 114     ny2 = INT(y2)+CUT;
 115
 116     if(ny1 < y1) {
 117         ny1 = INT(y1) + 1.0 + CUT;
 118     }
 119     if(ny2 >= y2) {
 120         ny2 = INT(y2) - 1.0 + CUT;
 121     }
 122     if(ny1 > ny2)
 123         return;
 124
 125     stepx = diffx/diffy;
 126     x1 = x1 + (ny1-y1)*stepx;
 127     x2 = x2 + (ny2-y2)*stepx;
 128
 129     int posy=INT(ny1);
 130     int endy=INT(ny2);
 131     double posx=0;
 132     double startx = x1;
 133
 134     while(posy<=endy) {
 135         double xx = startx + posx;
 136         add_pixel(buf, xx, posy, direction);
 137         posx+=stepx;
 138         posy++;
 139     }
 140 }
 141
 142 static int compare_renderpoints(const void * _a, const void * _b)
 143 {
 144     renderpoint_t*a = (renderpoint_t*)_a;
 145     renderpoint_t*b = (renderpoint_t*)_b;
 146     if(a->x < b->x) return -1;
 147     if(a->x > b->x) return 1;
 148     return 0;
 149 }
 150
 151 static void fill_bitwise(unsigned char*line, int x1, int x2)
 152 {
 153     int p1 = x1>>3;
 154     int p2 = x2>>3;
 155     int b1 = 0xff >> (x1&7);
 156     int b2 = 0xff << (1+7-(x2&7));
 157     if(p1==p2) {
 158         line[p1] |= b1&b2;
 159     } else {
 160         line[p1] |= b1;
 161         memset(&line[p1+1], 255, p2-(p1+1));
 162         line[p2] = b2;
 163     }
 164 }
 165
 166 unsigned char* render_svp(ArtSVP*svp, intbbox_t*bbox, double zoom, ArtWindRule rule)
 167 {
 168     renderbuf_t _buf, *buf=&_buf;
 169     buf->width = (bbox->xmax - bbox->xmin);
 170     buf->height = (bbox->ymax - bbox->ymin);
 171     buf->bbox = *bbox;
 172     buf->zoom = zoom;
 173     int width8 = (buf->width+7) >> 3;
 174     unsigned char* image = (unsigned char*)malloc(width8*buf->height);
 175     memset(image, 0, width8*buf->height);
 176
 177     buf->lines = (renderline_t*)rfx_alloc(buf->height*sizeof(renderline_t));
 178     int y;
 179     for(y=0;y<buf->height;y++) {
 180         memset(&buf->lines[y], 0, sizeof(renderline_t));
 181         buf->lines[y].points = 0;
 182         buf->lines[y].num = 0;
 183     }
 184
 185     int t;
 186     for(t=0;t<svp->n_segs;t++) {
 187         ArtSVPSeg* seg = &svp->segs[t];
 188         int s;
 189         for(s=0;s<seg->n_points-1;s++) {
 190             int dir = seg->dir? 1 : -1;
 191             add_line(buf, seg->points[s].x, seg->points[s].y, seg->points[s+1].x, seg->points[s+1].y, dir);
 192         }
 193     }
 194     for(y=0;y<buf->height;y++) {
 195         renderpoint_t*points = buf->lines[y].points;
 196         unsigned char*line = &image[width8*y];
 197         int n;
 198         int num = buf->lines[y].num;
 199         int wind = 0;
 200         qsort(points, num, sizeof(renderpoint_t), compare_renderpoints);
 201         int lastx = 0;
 202         int fill = 0;
 203
 204         for(n=0;n<num;n++) {
 205             renderpoint_t*p = &points[n];
 206             int x = (int)(p->x - bbox->xmin);
 207
 208             if(x < lastx)
 209                 x = lastx;
 210             if(x > buf->width) {
 211                 break;
 212             }
 213             if(fill && x!=lastx) {
 214                 fill_bitwise(line, lastx, x);
 215             }
 216             wind += p->direction;
 217             if(rule == ART_WIND_RULE_INTERSECT) {
 218                 fill = wind>=2;
 219             } else if (rule == ART_WIND_RULE_NONZERO) {
 220                 fill = wind!=0;
 221             } else if (rule == ART_WIND_RULE_ODDEVEN) {
 222                 fill = wind&1;
 223             } else { // rule == ART_WIND_RULE_POSITIVE
 224                 fill = wind>=1;
 225             }
 226             lastx = x;
 227         }
 228         if(fill && lastx!=buf->width)
 229             fill_bitwise(line, lastx, buf->width);
 230     }
 231
 232     for(y=0;y<buf->height;y++) {
 233         if(buf->lines[y].points) {
 234             free(buf->lines[y].points);
 235         }
 236         memset(&buf->lines[y], 0, sizeof(renderline_t));
 237     }
 238     free(buf->lines);buf->lines=0;
 239     return image;
 240 }
 241
 242 #define MAX_WIDTH 8192
 243 #define MAX_HEIGHT 4096
 244
 245 intbbox_t get_svp_bbox(ArtSVP*svp, double zoom)
 246 {
 247     int t;
 248     intbbox_t b = {0,0,0,0};
 249     if(svp->n_segs && svp->segs[0].n_points) {
 250         b.xmin = svp->segs[0].points[0].x;
 251         b.ymin = svp->segs[0].points[0].y;
 252         b.xmax = svp->segs[0].points[0].x;
 253         b.ymax = svp->segs[0].points[0].y;
 254     }
 255     for(t=0;t<svp->n_segs;t++) {
 256         ArtSVPSeg* seg = &svp->segs[t];
 257         int s;
 258         for(s=0;s<seg->n_points;s++) {
 259             double x = seg->points[s].x*zoom;
 260             double y = seg->points[s].y*zoom;
 261             int x1 = floor(x);
 262             int x2 = ceil(x);
 263             int y1 = floor(y);
 264             int y2 = ceil(y);
 265             if(x1 < b.xmin) b.xmin = x1;
 266             if(y1 < b.ymin) b.ymin = y1;
 267             if(x2 > b.xmax) b.xmax = x2;
 268             if(y2 > b.xmax) b.ymax = y2;
 269         }
 270     }
 271     if(b.xmax > (int)(MAX_WIDTH*zoom))
 272         b.xmax = (int)(MAX_WIDTH*zoom);
 273     if(b.ymax > (int)(MAX_HEIGHT*zoom))
 274         b.ymax = (int)(MAX_HEIGHT*zoom);
 275     if(b.xmin < -(int)(MAX_WIDTH*zoom))
 276         b.xmin = -(int)(MAX_WIDTH*zoom);
 277     if(b.ymin < -(int)(MAX_HEIGHT*zoom))
 278         b.ymin = -(int)(MAX_HEIGHT*zoom);
 279
 280     if(b.xmin > b.xmax)
 281         b.xmin = b.xmax;
 282     if(b.ymin > b.ymax)
 283         b.ymin = b.ymax;
 284
 285     b.width = b.xmax - b.xmin;
 286     b.height = b.ymax - b.ymin;
 287     return b;
 288 }
 289
 290 #define B11100000 0xe0
 291 #define B01110000 0x70
 292 #define B00111000 0x38
 293 #define B00011100 0x1c
 294 #define B00001110 0x0e
 295 #define B00000111 0x07
 296 #define B10000000 0x80
 297 #define B01000000 0x40
 298 #define B00100000 0x20
 299 #define B00010000 0x10
 300 #define B00001000 0x08
 301 #define B00000100 0x04
 302 #define B00000010 0x02
 303 #define B00000001 0x01
 304
 305 int compare_bitmaps(intbbox_t*bbox, unsigned char*data1, unsigned char*data2)
 306 {
 307     int similar = 0;
 308     int x,y;
 309     int height = bbox->height;
 310     int width = bbox->width;
 311     int width8 = (width+7) >> 3;
 312     unsigned char*l1 = &data1[width8];
 313     unsigned char*l2 = &data2[width8];
 314     int fail = 0;
 315     for(y=1;y<height-1;y++) {
 316         for(x=0;x<width8;x++) {
 317             unsigned a = l1[x-width8] & l1[x] & l1[x+width8];
 318             unsigned b = l2[x-width8] & l2[x] & l2[x+width8];
 319
 320             if((a&B11100000) && !(l2[x]&B01000000))
 321                 fail == 1;
 322             if((a&B01110000) && !(l2[x]&B00100000))
 323                 fail == 1;
 324             if((a&B00111000) && !(l2[x]&B00010000))
 325                 fail == 1;
 326             if((a&B00011100) && !(l2[x]&B00001000))
 327                 fail == 1;
 328             if((a&B00001110) && !(l2[x]&B00000100))
 329                 fail == 1;
 330             if((a&B00000111) && !(l2[x]&B00000010))
 331                 fail == 1;
 332
 333             if((b&B11100000) && !(l1[x]&B01000000))
 334                 fail == 1;
 335             if((b&B01110000) && !(l1[x]&B00100000))
 336                 fail == 1;
 337             if((b&B00111000) && !(l1[x]&B00010000))
 338                 fail == 1;
 339             if((b&B00011100) && !(l1[x]&B00001000))
 340                 fail == 1;
 341             if((b&B00001110) && !(l1[x]&B00000100))
 342                 fail == 1;
 343             if((b&B00000111) && !(l1[x]&B00000010))
 344                 fail == 1;
 345         }
 346         l1 += width8;
 347         l2 += width8;
 348     }
 349     return !fail;
 350 }
 351
 352
 353 //-----------------------------------------------------------------------------------------------
 354
 355 static ArtVpath* gfxline_to_ArtVpath(gfxline_t*line, char fill)
 356 {
 357     ArtVpath *vec = NULL;
 358     int pos=0,len=0;
 359     gfxline_t*l2;
 360     double x=0,y=0;
 361
 362     /* factor which determines into how many line fragments a spline is converted */
 363     double subfraction = 2.4;//0.3
 364
 365     l2 = line;
 366     while(l2) {
 367         if(l2->type == gfx_moveTo) {
 368             pos ++;
 369         } else if(l2->type == gfx_lineTo) {
 370             pos ++;
 371         } else if(l2->type == gfx_splineTo) {
 372             int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
 373             if(!parts) parts = 1;
 374             pos += parts + 1;
 375         }
 376         x = l2->x;
 377         y = l2->y;
 378         l2 = l2->next;
 379     }
 380     pos++;
 381     len = pos;
 382
 383     vec = art_new (ArtVpath, len+1);
 384
 385     pos = 0;
 386     l2 = line;
 387     while(l2) {
 388         if(l2->type == gfx_moveTo) {
 389             vec[pos].code = ART_MOVETO_OPEN;
 390             vec[pos].x = l2->x;
 391             vec[pos].y = l2->y;
 392             pos++;
 393             assert(pos<=len);
 394         } else if(l2->type == gfx_lineTo) {
 395             vec[pos].code = ART_LINETO;
 396             vec[pos].x = l2->x;
 397             vec[pos].y = l2->y;
 398             pos++;
 399             assert(pos<=len);
 400         } else if(l2->type == gfx_splineTo) {
 401             int i;
 402             int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
 403             if(!parts) parts = 1;
 404             double stepsize = 1.0/parts;
 405             for(i=0;i<=parts;i++) {
 406                 double t = (double)i*stepsize;
 407                 vec[pos].code = ART_LINETO;
 408                 vec[pos].x = l2->x*t*t + 2*l2->sx*t*(1-t) + x*(1-t)*(1-t);
 409                 vec[pos].y = l2->y*t*t + 2*l2->sy*t*(1-t) + y*(1-t)*(1-t);
 410                 pos++;
 411                 assert(pos<=len);
 412             }
 413         }
 414         x = l2->x;
 415         y = l2->y;
 416         l2 = l2->next;
 417     }
 418     vec[pos++].code = ART_END;
 419     assert(pos == len);
 420
 421     if(!fill) {
 422         /* Fix "dotted" lines. Those are lines where singular points are created
 423            by a moveto x,y lineto x,y combination. We "fix" these by shifting the
 424            point in the lineto a little bit to the right
 425            These should only occur in strokes, not in fills, so do this only
 426            when we know we're not filling.
 427          */
 428         int t;
 429         for(t=0;vec[t].code!=ART_END;t++) {
 430             if(t>0 && (vec[t-1].code==ART_MOVETO_OPEN || vec[t-1].code==ART_MOVETO)
 431                    && vec[t].code==ART_LINETO && vec[t+1].code!=ART_LINETO &&
 432                 vec[t-1].x == vec[t].x &&
 433                 vec[t-1].y == vec[t].y) {
 434                 vec[t].x += 0.01;
 435             }
 436         }
 437     }
 438
 439     /* Find adjacent identical points. If an ajdacent pair of identical
 440        points is found, the second is removed.
 441        So moveto x,y lineto x,y becomes moveto x,y
 442           lineto x,y lineto x,y becomes lineto x,y
 443           lineto x,y moveto x,y becomes lineto x,y
 444           moveto x,y moveto x,y becomes moveto x,y
 445           lineto x,y lineto x2,y2 becomes lineto x2,y2 (if dir(x,y) ~= dir(x2,y2))
 446      */
 447     pos = 0;
 448     int outpos = 0;
 449     while(1)
 450     {
 451         if(vec[pos].code == ART_END) {
 452             vec[outpos++] = vec[pos++];
 453             break;
 454         }
 455
 456         char samedir = 0, samepoint = 0;
 457         if(outpos) {
 458             double dx = vec[pos].x-vec[pos-1].x;
 459             double dy = vec[pos].y-vec[pos-1].y;
 460             /*if(pos<len-1 && vec[pos].code == ART_LINETO && vec[pos+1].code == ART_LINETO) {
 461                 double dx2 = vec[pos+1].x-vec[pos].x;
 462                 double dy2 = vec[pos+1].y-vec[pos].y;
 463                 if(fabs(dx*dy2 - dy*dx2) < 0.0001 && dx*dx2 + dy*dy2 >= 0) {
 464                     samedir=1;
 465                 }
 466             }*/
 467             if(fabs(dx) + fabs(dy) < 0.0001) {
 468                 samepoint=1;
 469             }
 470         }
 471         if(!samepoint && !samedir) {
 472             vec[outpos++] = vec[pos++];
 473         } else {
 474             pos++; // skip
 475         }
 476     }
 477
 478     return vec;
 479 }
 480
 481 static void shear_svp(ArtSVP*svp, double v)
 482 {
 483     /* do a "shearing" on the polygon. We do this to eliminate all
 484        horizontal lines (which libart can't handle properly, even though
 485        it tries). */
 486
 487     int t;
 488     for(t=0;t<svp->n_segs;t++) {
 489         ArtSVPSeg* seg = &svp->segs[t];
 490         int s;
 491         for(s=0;s<seg->n_points;s++) {
 492             ArtPoint* point = &seg->points[s];
 493             point->y += point->x*v;
 494         }
 495     }
 496 }
 497
 498 static double find_shear_value(ArtSVP*svp)
 499 {
 500     /* We try random values until we find one
 501        where there's no slope below a given value, or if that fails,
 502        at least no slope of 0 */
 503
 504     double v = 0;
 505     int tries = 0;
 506     while(1) {
 507         char fail = 0;
 508         int t;
 509         for(t=0;t<svp->n_segs;t++) {
 510             ArtSVPSeg* seg = &svp->segs[t];
 511             int s;
 512             for(s=0;s<seg->n_points-1;s++) {
 513                 ArtPoint* p1 = &seg->points[s];
 514                 ArtPoint* p2 = &seg->points[s+1];
 515                 double dx = p2->x - p1->x;
 516                 double dy = p2->y - p1->y;
 517                 dy += dx*v;
 518                 if(dy==0) {
 519                     fail = 1;
 520                     break;
 521                 }
 522                 if(tries<100 && dx && fabs(dy / dx) < 1e-5) {
 523                     fail = 1;
 524                     break;
 525                 }
 526             }
 527             if(fail)
 528                 break;
 529         }
 530         if(!fail)
 531             break;
 532         v = lrand48() / 2000000000.0;
 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 =  gfxpoly_to_gfxline((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* 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 }