lib/gfxpoly/poly.c

   1 #include <stdlib.h>
   2 #include <memory.h>
   3 #include <math.h>
   4 #include "../mem.h"
   5 #include "../types.h"
   6 #include "../MD5.h"
   7 #include "poly.h"
   8 #include "active.h"
   9 #include "xrow.h"
  10 #include "wind.h"
  11 #include "convert.h"
  12 #include "heap.h"
  13
  14 static gfxpoly_t*current_polygon = 0;
  15 void gfxpoly_fail(char*expr, char*file, int line, const char*function)
  16 {
  17     if(!current_polygon) {
  18         fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
  19         exit(1);
  20     }
  21
  22     void*md5 = initialize_md5();
  23
  24     int s,t;
  25     gfxpolystroke_t*stroke = current_polygon->strokes;
  26     for(;stroke;stroke=stroke->next) {
  27         for(t=0;t<stroke->num_points;t++) {
  28             update_md5(md5, (unsigned char*)&stroke->points[t].x, sizeof(stroke->points[t].x));
  29             update_md5(md5, (unsigned char*)&stroke->points[t].y, sizeof(stroke->points[t].y));
  30         }
  31     }
  32     unsigned char h[16];
  33     char filename[32+4+1];
  34     finish_md5(md5, h);
  35     sprintf(filename, "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x.ps",
  36             h[0],h[1],h[2],h[3],h[4],h[5],h[6],h[7],h[8],h[9],h[10],h[11],h[12],h[13],h[14],h[15]);
  37
  38     fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
  39     fprintf(stderr, "I'm saving a debug file \"%s\" to the current directory.\n", filename);
  40
  41     gfxpoly_save(current_polygon, filename);
  42     exit(1);
  43 }
  44
  45 static char point_equals(const void*o1, const void*o2)
  46 {
  47     const point_t*p1 = o1;
  48     const point_t*p2 = o2;
  49     return p1->x == p2->x && p1->y == p2->y;
  50 }
  51 static unsigned int point_hash(const void*o)
  52 {
  53     const point_t*p = o;
  54     return p->x^p->y;
  55 }
  56 static void* point_dup(const void*o)
  57 {
  58     const point_t*p = o;
  59     point_t*n = malloc(sizeof(point_t));
  60     n->x = p->x;
  61     n->y = p->y;
  62     return n;
  63 }
  64 static void point_free(void*o)
  65 {
  66     point_t*p = o;
  67     p->x = 0;
  68     p->y = 0;
  69     free(p);
  70 }
  71 type_t point_type = {
  72     equals: point_equals,
  73     hash: point_hash,
  74     dup: point_dup,
  75     free: point_free,
  76 };
  77
  78 typedef struct _event {
  79     eventtype_t type;
  80     point_t p;
  81     segment_t*s1;
  82     segment_t*s2;
  83 } event_t;
  84
  85 /* compare_events_simple differs from compare_events in that it schedules
  86    events from left to right regardless of type. It's only used in horizontal
  87    processing, in order to get an x-wise sorting of the current scanline */
  88 static inline int compare_events_simple(const void*_a,const void*_b)
  89 {
  90     event_t* a = (event_t*)_a;
  91     event_t* b = (event_t*)_b;
  92     int d = b->p.y - a->p.y;
  93     if(d) return d;
  94     d = b->p.x - a->p.x;
  95     if(d) return d;
  96     return 0;
  97 }
  98
  99 static inline int compare_events(const void*_a,const void*_b)
 100 {
 101     event_t* a = (event_t*)_a;
 102     event_t* b = (event_t*)_b;
 103     int d = b->p.y - a->p.y;
 104     if(d) return d;
 105     /* we need to schedule end after intersect (so that a segment about
 106        to end has a chance to tear up a few other segs first) and start
 107        events after end (in order not to confuse the intersection check, which
 108        assumes there's an actual y overlap between active segments, and
 109        because ending segments in the active list make it difficult to insert
 110        starting segments at the right position)).
 111        Horizontal lines come last, because the only purpose
 112        they have is to create snapping coordinates for the segments (still)
 113        existing in this scanline.
 114     */
 115     d = b->type - a->type;
 116     if(d) return d;
 117     return 0;
 118
 119     /* I don't see any reason why we would need to order by x- at least as long
 120        as we do horizontal lines in a seperate pass */
 121     //d = b->p.x - a->p.x;
 122     //return d;
 123 }
 124
 125 #define COMPARE_EVENTS(x,y) (compare_events(x,y)>0)
 126 #define COMPARE_EVENTS_SIMPLE(x,y) (compare_events_simple(x,y)>0)
 127 HEAP_DEFINE(queue,event_t,COMPARE_EVENTS);
 128 HEAP_DEFINE(hqueue,event_t,COMPARE_EVENTS_SIMPLE);
 129
 130 typedef struct _status {
 131     int32_t y;
 132     actlist_t*actlist;
 133     queue_t queue;
 134     xrow_t*xrow;
 135     windrule_t*windrule;
 136     windcontext_t*context;
 137     segment_t*ending_segments;
 138
 139     gfxpolystroke_t*strokes;
 140 #ifdef CHECKS
 141     dict_t*seen_crossings; //list of crossing we saw so far
 142     dict_t*intersecting_segs; //list of segments intersecting in this scanline
 143     dict_t*segs_with_point; //lists of segments that received a point in this scanline
 144 #endif
 145 } status_t;
 146
 147
 148 int gfxpoly_num_segments(gfxpoly_t*poly)
 149 {
 150     gfxpolystroke_t*stroke = poly->strokes;
 151     int count = 0;
 152     for(;stroke;stroke=stroke->next) {
 153         count++;
 154     }
 155     return count;
 156 }
 157 int gfxpoly_size(gfxpoly_t*poly)
 158 {
 159     int s,t;
 160     int edges = 0;
 161     gfxpolystroke_t*stroke = poly->strokes;
 162     for(;stroke;stroke=stroke->next) {
 163         edges += stroke->num_points-1;
 164     }
 165     return edges;
 166 }
 167
 168 char gfxpoly_check(gfxpoly_t*poly, char updown)
 169 {
 170     current_polygon = poly;
 171     dict_t*d1 = dict_new2(&point_type);
 172     dict_t*d2 = dict_new2(&point_type);
 173     int s,t;
 174     gfxpolystroke_t*stroke = poly->strokes;
 175     for(;stroke;stroke=stroke->next) {
 176         /* In order to not confuse the fill/wind logic, existing segments must have
 177            a non-zero edge style */
 178         assert(stroke->fs);
 179
 180         /* put all the segments into dictionaries so that we can check
 181            that the endpoint multiplicity is two */
 182         for(s=0;s<stroke->num_points;s++) {
 183             point_t p = stroke->points[s];
 184             int num_xor = (s>=1 && s<stroke->num_points-1)?2:1; // mid points are two points (start+end)
 185             int num_circ = (s>=1 && s<stroke->num_points-1)?0:(s==0?1:-1);
 186             if(stroke->dir==DIR_UP)
 187                 num_circ=-num_circ;
 188
 189             if(!dict_contains(d1, &p)) {
 190                 dict_put(d1, &p, (void*)(ptroff_t)num_xor);
 191                 if(updown) {
 192                     assert(!dict_contains(d2, &p));
 193                     dict_put(d2, &p, (void*)(ptroff_t)num_circ);
 194                 }
 195             } else {
 196                 int count = (ptroff_t)dict_lookup(d1, &p);
 197                 dict_del(d1, &p);
 198                 count+=num_xor;
 199                 dict_put(d1, &p, (void*)(ptroff_t)count);
 200
 201                 if(updown) {
 202                     assert(dict_contains(d2, &p));
 203                     count = (ptroff_t)dict_lookup(d2, &p);
 204                     dict_del(d2, &p);
 205                     count+=num_circ;
 206                     dict_put(d2, &p, (void*)(ptroff_t)count);
 207                 }
 208             }
 209         }
 210     }
 211     DICT_ITERATE_ITEMS(d1, point_t*, p1, void*, c1) {
 212         int count = (ptroff_t)c1;
 213         if(count&1) {
 214             fprintf(stderr, "Point (%d,%d) occurs %d times\n", p1->x, p1->y, count);
 215             dict_destroy(d1);
 216             return 0;
 217         }
 218     }
 219     if(updown) {
 220         DICT_ITERATE_ITEMS(d2, point_t*, p2, void*, c2) {
 221             int count = (ptroff_t)c2;
 222             if(count!=0) {
 223                 if(count>0) fprintf(stderr, "Point (%d,%d) has %d more incoming than outgoing segments\n", p2->x, p2->y, count);
 224                 if(count<0) fprintf(stderr, "Point (%d,%d) has %d more outgoing than incoming segments\n", p2->x, p2->y, -count);
 225                 dict_destroy(d2);
 226                 return 0;
 227             }
 228         }
 229     }
 230     dict_destroy(d1);
 231     dict_destroy(d2);
 232     return 1;
 233 }
 234
 235 void gfxpoly_dump(gfxpoly_t*poly)
 236 {
 237     int s,t;
 238     double g = poly->gridsize;
 239     fprintf(stderr, "polyon %p (gridsize: %f)\n", poly, poly->gridsize);
 240     gfxpolystroke_t*stroke = poly->strokes;
 241     for(;stroke;stroke=stroke->next) {
 242         fprintf(stderr, "%11p", stroke);
 243         if(stroke->dir==DIR_UP) {
 244             for(s=stroke->num_points-1;s>=1;s--) {
 245                 point_t a = stroke->points[s];
 246                 point_t b = stroke->points[s-1];
 247                 fprintf(stderr, "%s (%f,%f) -> (%f,%f)%s%s\n", s!=stroke->num_points-1?"           ":"", a.x*g, a.y*g, b.x*g, b.y*g,
 248                                                             s==1?"]":"", a.y==b.y?"H":"");
 249             }
 250         } else {
 251             for(s=0;s<stroke->num_points-1;s++) {
 252                 point_t a = stroke->points[s];
 253                 point_t b = stroke->points[s+1];
 254                 fprintf(stderr, "%s (%f,%f) -> (%f,%f)%s%s\n", s?"           ":"", a.x*g, a.y*g, b.x*g, b.y*g,
 255                                                             s==stroke->num_points-2?"]":"", a.y==b.y?"H":"");
 256             }
 257         }
 258     }
 259 }
 260
 261 void gfxpoly_save(gfxpoly_t*poly, const char*filename)
 262 {
 263     FILE*fi = fopen(filename, "wb");
 264     fprintf(fi, "%% gridsize %f\n", poly->gridsize);
 265     fprintf(fi, "%% begin\n");
 266     int s,t;
 267     gfxpolystroke_t*stroke = poly->strokes;
 268     for(;stroke;stroke=stroke->next) {
 269             fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
 270         point_t p = stroke->points[0];
 271         fprintf(fi, "%d %d moveto\n", p.x, p.y);
 272         for(s=1;s<stroke->num_points;s++) {
 273             p = stroke->points[s];
 274             fprintf(fi, "%d %d lineto\n", p.x, p.y);
 275         }
 276         fprintf(fi, "stroke\n");
 277     }
 278     fprintf(fi, "showpage\n");
 279     fclose(fi);
 280 }
 281
 282 void gfxpoly_save_arrows(gfxpoly_t*poly, const char*filename)
 283 {
 284     FILE*fi = fopen(filename, "wb");
 285     fprintf(fi, "%% gridsize %f\n", poly->gridsize);
 286     fprintf(fi, "%% begin\n");
 287     int t;
 288     double l = 5.0 / poly->gridsize;
 289     double g = poly->gridsize;
 290     gfxpolystroke_t*stroke = poly->strokes;
 291     for(;stroke;stroke=stroke->next) {
 292         fprintf(fi, "%g setgray\n", 0);
 293
 294         int s = stroke->dir==DIR_UP?stroke->num_points-1:0;
 295         int end = stroke->dir==DIR_UP?-1:stroke->num_points;
 296         int dir = stroke->dir==DIR_UP?-1:1;
 297
 298         point_t p = stroke->points[s];
 299         s+=dir;
 300         point_t o = p;
 301         fprintf(fi, "%f %f moveto\n", p.x * g, p.y * g);
 302         for(;s!=end;s+=dir) {
 303             p = stroke->points[s];
 304             int lx = p.x - o.x;
 305             int ly = p.y - o.y;
 306             double d = sqrt(lx*lx+ly*ly);
 307             if(!d) d=1;
 308             else   d = l / d;
 309             double d2 = d*1.5;
 310             fprintf(fi, "%f %f lineto\n", (p.x - lx*d2) * g, (p.y - ly*d2) * g);
 311             fprintf(fi, "%f %f lineto\n", (p.x - lx*d2 + (ly*d))*g,
 312                                           (p.y - ly*d2 - (lx*d))*g);
 313             fprintf(fi, "%f %f lineto\n", p.x * g, p.y * g);
 314             fprintf(fi, "%f %f lineto\n", (p.x - lx*d2 - (ly*d))*g,
 315                                           (p.y - ly*d2 + (lx*d))*g);
 316             fprintf(fi, "%f %f lineto\n", (p.x - lx*d2) * g, (p.y - ly*d2) * g);
 317             fprintf(fi, "%f %f moveto\n", p.x * g, p.y * g);
 318             o = p;
 319         }
 320         fprintf(fi, "stroke\n");
 321     }
 322     fprintf(fi, "showpage\n");
 323     fclose(fi);
 324 }
 325
 326 inline static event_t* event_new()
 327 {
 328     event_t*e = rfx_calloc(sizeof(event_t));
 329     return e;
 330 }
 331 inline static void event_free(event_t*e)
 332 {
 333     free(e);
 334 }
 335
 336 static void event_dump(event_t*e)
 337 {
 338     if(e->type == EVENT_HORIZONTAL) {
 339         fprintf(stderr, "Horizontal [%d] (%d,%d) -> (%d,%d)\n", (int)e->s1->nr, e->s1->a.x, e->s1->a.y, e->s1->b.x, e->s1->b.y);
 340     } else if(e->type == EVENT_START) {
 341         fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", (int)e->s1->nr, e->p.x, e->p.y);
 342     } else if(e->type == EVENT_END) {
 343         fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", (int)e->s1->nr, e->p.x, e->p.y);
 344     } else if(e->type == EVENT_CROSS) {
 345         fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", (int)e->s1->nr, (int)e->s2->nr, e->p.x, e->p.y);
 346     } else {
 347         assert(0);
 348     }
 349 }
 350
 351 static inline int32_t max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
 352 static inline int32_t min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
 353
 354 static void segment_dump(segment_t*s)
 355 {
 356     fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", (int)s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
 357     fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f fs=%p\n", s->delta.x, s->delta.y, s->k,
 358             (double)s->delta.x / s->delta.y, s->fs);
 359 }
 360
 361 static void segment_init(segment_t*s, int32_t x1, int32_t y1, int32_t x2, int32_t y2, int polygon_nr, segment_dir_t dir)
 362 {
 363     s->dir = dir;
 364     if(y1!=y2) {
 365         assert(y1<y2);
 366     } else {
 367         /* We need to make sure horizontal segments always go from left to right.
 368            "up/down" for horizontal segments is handled by "rotating"
 369            them 90° anticlockwise in screen coordinates (tilt your head to
 370            the right).
 371          */
 372         s->dir = DIR_UP;
 373         if(x1>x2) {
 374             s->dir = DIR_DOWN;
 375             int32_t x = x1;x1=x2;x2=x;
 376             int32_t y = y1;y1=y2;y2=y;
 377         }
 378     }
 379     s->a.x = x1;
 380     s->a.y = y1;
 381     s->b.x = x2;
 382     s->b.y = y2;
 383     s->k = (double)x1*y2-(double)x2*y1;
 384     s->left = s->right = 0;
 385     s->delta.x = x2-x1;
 386     s->delta.y = y2-y1;
 387     s->minx = min32(x1,x2);
 388     s->maxx = max32(x1,x2);
 389
 390     s->pos = s->a;
 391     s->polygon_nr = polygon_nr;
 392     static int segment_count=0;
 393     s->nr = segment_count++;
 394
 395 #ifdef CHECKS
 396     /* notice: on some systems (with some compilers), for the line
 397        (1073741823,-1073741824)->(1073741823,1073741823)
 398        we get LINE_EQ(s->a, s) == 1.
 399        That's why we now clamp to 26 bit.
 400     */
 401     assert(LINE_EQ(s->a, s) == 0);
 402     assert(LINE_EQ(s->b, s) == 0);
 403
 404     /* check that all signs are in order:
 405        a        a
 406        |\      /|
 407        | \    / |
 408      minx-b  b--maxx
 409      < 0        > 0
 410     */
 411     point_t p = s->b;
 412     p.x = min32(s->a.x, s->b.x);
 413     assert(LINE_EQ(p, s) <= 0);
 414     p.x = max32(s->a.x, s->b.x);
 415     assert(LINE_EQ(p, s) >= 0);
 416 #endif
 417
 418 #ifndef DONT_REMEMBER_CROSSINGS
 419     dict_init2(&s->scheduled_crossings, &ptr_type, 0);
 420 #endif
 421 }
 422
 423 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
 424 {
 425     segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
 426     segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
 427     return s;
 428 }
 429
 430 static void segment_clear(segment_t*s)
 431 {
 432 #ifndef DONT_REMEMBER_CROSSINGS
 433     dict_clear(&s->scheduled_crossings);
 434 #endif
 435 }
 436 static void segment_destroy(segment_t*s)
 437 {
 438     segment_clear(s);
 439     free(s);
 440 }
 441
 442 static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*stroke, int polygon_nr, int pos)
 443 {
 444     if(!stroke)
 445         return;
 446     segment_t*s = 0;
 447     /* we need to queue multiple segments at once because we need to process start events
 448        before horizontal events */
 449     while(pos < stroke->num_points-1) {
 450         assert(stroke->points[pos].y <= stroke->points[pos+1].y);
 451         s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
 452         s->fs = stroke->fs;
 453         pos++;
 454         s->stroke = 0;
 455         s->stroke_pos = 0;
 456 #ifdef DEBUG
 457         /*if(l->tmp)
 458             s->nr = l->tmp;*/
 459         fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (stroke %p, %d more to come)\n",
 460                 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
 461                 s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos);
 462 #endif
 463         event_t* e = event_new();
 464         e->type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
 465         e->p = s->a;
 466         e->s1 = s;
 467         e->s2 = 0;
 468
 469         if(queue) queue_put(queue, e);
 470         else hqueue_put(hqueue, e);
 471
 472         if(e->type != EVENT_HORIZONTAL) {
 473             break;
 474         }
 475     }
 476     if(s) {
 477         s->stroke = stroke;
 478         s->stroke_pos = pos;
 479     }
 480 }
 481
 482 static void gfxpoly_enqueue(gfxpoly_t*p, queue_t*queue, hqueue_t*hqueue, int polygon_nr)
 483 {
 484     int t;
 485     gfxpolystroke_t*stroke = p->strokes;
 486     for(;stroke;stroke=stroke->next) {
 487         assert(stroke->num_points > 1);
 488
 489 #ifdef CHECKS
 490         int s;
 491         for(s=0;s<stroke->num_points-1;s++) {
 492             assert(stroke->points[s].y <= stroke->points[s+1].y);
 493         }
 494 #endif
 495         advance_stroke(queue, hqueue, stroke, polygon_nr, 0);
 496     }
 497 }
 498
 499 static void schedule_endpoint(status_t*status, segment_t*s)
 500 {
 501     // schedule end point of segment
 502     assert(s->b.y > status->y);
 503     event_t*e = event_new();
 504     e->type = EVENT_END;
 505     e->p = s->b;
 506     e->s1 = s;
 507     e->s2 = 0;
 508     queue_put(&status->queue, e);
 509 }
 510
 511 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
 512 {
 513     /* the code that's required (and the checks you can perform) before
 514        it can be said with 100% certainty that we indeed have a valid crossing
 515        amazes me every time. -mk */
 516 #ifdef CHECKS
 517     assert(s1!=s2);
 518     assert(s1->right == s2);
 519     assert(s2->left == s1);
 520     int32_t miny1 = min32(s1->a.y,s1->b.y);
 521     int32_t maxy1 = max32(s1->a.y,s1->b.y);
 522     int32_t miny2 = min32(s2->a.y,s2->b.y);
 523     int32_t maxy2 = max32(s2->a.y,s2->b.y);
 524     int32_t minx1 = min32(s1->a.x,s1->b.x);
 525     int32_t minx2 = min32(s2->a.x,s2->b.x);
 526     int32_t maxx1 = max32(s1->a.x,s1->b.x);
 527     int32_t maxx2 = max32(s2->a.x,s2->b.x);
 528     /* check that precomputation is sane */
 529     assert(minx1 == s1->minx && minx2 == s2->minx);
 530     assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
 531     /* both segments are active, so this can't happen */
 532     assert(!(maxy1 <= miny2 || maxy2 <= miny1));
 533     /* we know that right now, s2 is to the right of s1, so there's
 534        no way the complete bounding box of s1 is to the right of s1 */
 535     assert(!(s1->minx > s2->maxx));
 536     assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
 537 #endif
 538
 539     if(s1->maxx <= s2->minx) {
 540 #ifdef DEBUG
 541             fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
 542 #endif
 543         /* bounding boxes don't intersect */
 544         return;
 545     }
 546
 547 #ifndef DONT_REMEMBER_CROSSINGS
 548     if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
 549         /* FIXME: this whole segment hashing thing is really slow */
 550 #ifdef DEBUG
 551         fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
 552 //      DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
 553 //          fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
 554 //      }
 555 #endif
 556         return; // we already know about this one
 557     }
 558 #endif
 559
 560     double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
 561     if(!det) {
 562         if(s1->k == s2->k) {
 563             // lines are exactly on top of each other (ignored)
 564 #ifdef DEBUG
 565             fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
 566 #endif
 567             return;
 568         } else {
 569 #ifdef DEBUG
 570             fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
 571 #endif
 572             /* lines are parallel */
 573             return;
 574         }
 575     }
 576
 577     double asign2 = LINE_EQ(s1->a, s2);
 578     if(asign2==0) {
 579         // segment1 touches segment2 in a single point (ignored)
 580 #ifdef DEBUG
 581         fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
 582 #endif
 583         return;
 584     }
 585     double bsign2 = LINE_EQ(s1->b, s2);
 586     if(bsign2==0) {
 587         // segment1 touches segment2 in a single point (ignored)
 588 #ifdef DEBUG
 589         fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
 590 #endif
 591         return;
 592     }
 593
 594     if(asign2<0 && bsign2<0) {
 595         // segment1 is completely to the left of segment2
 596 #ifdef DEBUG
 597             fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s1->nr, s2->nr);
 598 #endif
 599         return;
 600     }
 601     if(asign2>0 && bsign2>0)  {
 602         // segment1 is completely to the right of segment2
 603 #ifndef DONT_REMEMBER_CROSSINGS
 604         assert(0);
 605 #endif
 606 #ifdef DEBUG
 607             fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s2->nr, s1->nr);
 608 #endif
 609         return;
 610     }
 611
 612     double asign1 = LINE_EQ(s2->a, s1);
 613     if(asign1==0) {
 614         // segment2 touches segment1 in a single point (ignored)
 615 #ifdef DEBUG
 616         fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
 617 #endif
 618         return;
 619     }
 620     double bsign1 = LINE_EQ(s2->b, s1);
 621     if(asign2==0) {
 622         // segment2 touches segment1 in a single point (ignored)
 623 #ifdef DEBUG
 624         fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
 625 #endif
 626         return;
 627     }
 628
 629     if(asign1<0 && bsign1<0) {
 630         // segment2 is completely to the left of segment1
 631 #ifndef DONT_REMEMBER_CROSSINGS
 632         assert(0);
 633 #endif
 634 #ifdef DEBUG
 635             fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s1->nr, s2->nr);
 636 #endif
 637         return;
 638     }
 639     if(asign1>0 && bsign1>0)  {
 640         // segment2 is completely to the right of segment1
 641 #ifdef DEBUG
 642             fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s2->nr, s1->nr);
 643 #endif
 644         return;
 645     }
 646
 647 #ifdef DONT_REMEMBER_CROSSINGS
 648     /* s2 crosses s1 from *left* to *right*. This is a crossing we already processed-
 649        there's not way s2 would be to the left of s1 otherwise */
 650     if(asign1<0 && bsign1>0) return;
 651     if(asign2>0 && bsign2<0) return;
 652 #endif
 653
 654     assert(!(asign1<0 && bsign1>0));
 655     assert(!(asign2>0 && bsign2<0));
 656
 657     /* TODO: should we precompute these? */
 658     double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
 659     double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
 660
 661     point_t p;
 662     p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
 663     p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
 664
 665     assert(p.y >= status->y);
 666 #ifdef CHECKS
 667     assert(p.x >= s1->minx && p.x <= s1->maxx);
 668     assert(p.x >= s2->minx && p.x <= s2->maxx);
 669
 670     point_t pair;
 671     pair.x = s1->nr;
 672     pair.y = s2->nr;
 673 #ifndef DONT_REMEMBER_CROSSINGS
 674     assert(!dict_contains(status->seen_crossings, &pair));
 675     dict_put(status->seen_crossings, &pair, 0);
 676 #endif
 677 #endif
 678 #ifdef DEBUG
 679     fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
 680 #endif
 681
 682 #ifndef DONT_REMEMBER_CROSSINGS
 683     /* we insert into each other's intersection history because these segments might switch
 684        places and we still want to look them up quickly after they did */
 685     dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
 686     dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
 687 #endif
 688
 689     event_t* e = event_new();
 690     e->type = EVENT_CROSS;
 691     e->p = p;
 692     e->s1 = s1;
 693     e->s2 = s2;
 694     queue_put(&status->queue, e);
 695     return;
 696 }
 697
 698 static void exchange_two(status_t*status, event_t*e)
 699 {
 700     //exchange two segments in list
 701     segment_t*s1 = e->s1;
 702     segment_t*s2 = e->s2;
 703 #ifdef CHECKS
 704     if(!dict_contains(status->intersecting_segs, s1))
 705         dict_put(status->intersecting_segs, s1, 0);
 706     if(!dict_contains(status->intersecting_segs, s2))
 707         dict_put(status->intersecting_segs, s2, 0);
 708 #endif
 709     assert(s2->left == s1);
 710     assert(s1->right == s2);
 711     actlist_swap(status->actlist, s1, s2);
 712     assert(s2->right  == s1);
 713     assert(s1->left == s2);
 714     segment_t*left = s2->left;
 715     segment_t*right = s1->right;
 716     if(left)
 717         schedule_crossing(status, left, s2);
 718     if(right)
 719         schedule_crossing(status, s1, right);
 720 }
 721
 722 typedef struct _box {
 723     point_t left1, left2, right1, right2;
 724 } box_t;
 725 static inline box_t box_new(int32_t x, int32_t y)
 726 {
 727     box_t box;
 728     box.right1.x = box.right2.x = x;
 729     box.left1.x = box.left2.x = x-1;
 730     box.left1.y = box.right1.y = y-1;
 731     box.left2.y = box.right2.y = y;
 732     return box;
 733 }
 734
 735 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
 736 {
 737     assert(s->pos.x != p.x || s->pos.y != p.y);
 738
 739 #ifdef CHECKS
 740     if(!dict_contains(status->segs_with_point, s))
 741         dict_put(status->segs_with_point, s, 0);
 742     assert(s->fs_out_ok);
 743 #endif
 744
 745     if(s->fs_out) {
 746 #ifdef DEBUG
 747         fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
 748                 s->pos.x, s->pos.y, p.x, p.y);
 749 #endif
 750         edgestyle_t*fs = s->fs_out;
 751         segment_dir_t dir = s->wind.is_filled?DIR_DOWN:DIR_UP;
 752
 753         // omit horizontal lines
 754         if(s->pos.y != p.y) {
 755             point_t a = s->pos;
 756             point_t b = p;
 757             assert(a.y != b.y);
 758
 759             gfxpolystroke_t*stroke = status->strokes;
 760             /* find a stoke to attach this segment to. It has to have an endpoint
 761                matching our start point, and a matching edgestyle */
 762             while(stroke) {
 763                 point_t p = stroke->points[stroke->num_points-1];
 764                 if(p.x == a.x && p.y == a.y && stroke->fs == fs && stroke->dir == dir)
 765                     break;
 766                 stroke = stroke->next;
 767             }
 768             if(!stroke) {
 769                 stroke = rfx_calloc(sizeof(gfxpolystroke_t));
 770                 stroke->dir = dir;
 771                 stroke->fs = fs;
 772                 stroke->next = status->strokes;
 773                 status->strokes = stroke;
 774                 stroke->points_size = 2;
 775                 stroke->points = rfx_calloc(sizeof(point_t)*stroke->points_size);
 776                 stroke->points[0] = a;
 777                 stroke->num_points = 1;
 778             } else if(stroke->num_points == stroke->points_size) {
 779                 assert(stroke->fs);
 780                 stroke->points_size *= 2;
 781                 stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size);
 782             }
 783             stroke->points[stroke->num_points++] = b;
 784         }
 785     } else {
 786 #ifdef DEBUG
 787         fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
 788 #endif
 789     }
 790     s->pos = p;
 791 }
 792
 793 typedef struct _segrange {
 794     double xmin;
 795     segment_t*segmin;
 796     double xmax;
 797     segment_t*segmax;
 798 } segrange_t;
 799
 800 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
 801 {
 802 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
 803     segment_t*min = range->segmin;
 804     segment_t*max = range->segmax;
 805
 806     /* we need this because if two segments intersect exactly on
 807        the scanline, segrange_test_segment_{min,max} can't tell which
 808        one is smaller/larger */
 809     if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
 810         min = min->left;
 811     }
 812     if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
 813         max = max->right;
 814     }
 815     range->segmin = min;
 816     range->segmax = max;
 817 }
 818 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
 819 {
 820     if(!seg) return;
 821     /* we need to calculate the xpos anew (and can't use start coordinate or
 822        intersection coordinate), because we need the xpos exactly at the end of
 823        this scanline.
 824      */
 825     double x = XPOS(seg, y);
 826     if(!range->segmin || x<range->xmin) {
 827         range->segmin = seg;
 828         range->xmin = x;
 829     }
 830 }
 831 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
 832 {
 833     if(!seg) return;
 834     double x = XPOS(seg, y);
 835     if(!range->segmax || x>range->xmax) {
 836         range->segmax = seg;
 837         range->xmax = x;
 838     }
 839 }
 840
 841 /*
 842    SLOPE_POSITIVE:
 843       \+     \ +
 844 ------ I      \I
 845       -I\----  I
 846        I \   --I\---
 847        I  \    I \  -------
 848        +   \   +  \
 849 */
 850 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
 851 {
 852     segment_t*first=0, *last = 0;
 853     int t;
 854     for(t=0;t<status->xrow->num;t++) {
 855         box_t box = box_new(status->xrow->x[t], y);
 856         segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
 857
 858         seg = actlist_right(status->actlist, seg);
 859         while(seg) {
 860             if(seg->a.y == y) {
 861                 // this segment started in this scanline, ignore it
 862                 seg->changed = 1;last = seg;if(!first) {first=seg;}
 863             } else if(seg->delta.x <= 0) {
 864                 // ignore segment w/ negative slope
 865             } else {
 866                 last = seg;if(!first) {first=seg;}
 867                 double d1 = LINE_EQ(box.right1, seg);
 868                 double d2 = LINE_EQ(box.right2, seg);
 869                 if(d1>0 || d2>=0) {
 870                     seg->changed = 1;
 871                     insert_point_into_segment(status, seg, box.right2);
 872                 } else {
 873                     /* we unfortunately can't break here- the active list is sorted according
 874                        to the *bottom* of the scanline. hence pretty much everything that's still
 875                        coming might reach into our box */
 876                     //break;
 877                 }
 878             }
 879             seg = seg->right;
 880         }
 881     }
 882     segrange_test_segment_min(range, first, y);
 883     segrange_test_segment_max(range, last, y);
 884 }
 885 /* SLOPE_NEGATIVE:
 886    |   +   /|  +  /    /
 887    |   I  / |  I /    /
 888    |   I /  |  I/    /
 889    |   I/   |  I    /
 890    |   I    | /I   /
 891    |  /+    |/ +  /
 892 */
 893 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
 894 {
 895     segment_t*first=0, *last = 0;
 896     int t;
 897     for(t=status->xrow->num-1;t>=0;t--) {
 898         box_t box = box_new(status->xrow->x[t], y);
 899         segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
 900
 901         while(seg) {
 902             if(seg->a.y == y) {
 903                 // this segment started in this scanline, ignore it
 904                 seg->changed = 1;last = seg;if(!first) {first=seg;}
 905             } else if(seg->delta.x > 0) {
 906                 // ignore segment w/ positive slope
 907             } else {
 908                 last = seg;if(!first) {first=seg;}
 909                 double d1 = LINE_EQ(box.left1, seg);
 910                 double d2 = LINE_EQ(box.left2, seg);
 911                 if(d1<0 || d2<0) {
 912                     seg->changed = 1;
 913                     insert_point_into_segment(status, seg, box.right2);
 914                 } else {
 915                     //break;
 916                 }
 917             }
 918             seg = seg->left;
 919         }
 920     }
 921     segrange_test_segment_min(range, last, y);
 922     segrange_test_segment_max(range, first, y);
 923 }
 924
 925 /* segments ending in the current scanline need xrow treatment like everything else.
 926    (consider an intersection taking place just above a nearly horizontal segment
 927    ending on the current scanline- the intersection would snap down *below* the
 928    ending segment if we don't add the intersection point to the latter right away)
 929    we need to treat ending segments seperately, however. we have to delete them from
 930    the active list right away to make room for intersect operations (which might
 931    still be in the current scanline- consider two 45° polygons and a vertical polygon
 932    intersecting on an integer coordinate). but once they're no longer in the active list,
 933    we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
 934    them to the active list just for point snapping would be overkill.
 935    (One other option to consider, however, would be to create a new active list only
 936     for ending segments)
 937 */
 938 static void add_points_to_ending_segments(status_t*status, int32_t y)
 939 {
 940     segment_t*seg = status->ending_segments;
 941     while(seg) {
 942         segment_t*next = seg->right;seg->right=0;
 943
 944         assert(seg->b.y == status->y);
 945
 946         if(status->xrow->num == 1) {
 947             // shortcut
 948             assert(seg->b.x == status->xrow->x[0]);
 949             point_t p = {status->xrow->x[0], y};
 950             insert_point_into_segment(status, seg, p);
 951         } else {
 952             int t;
 953             int start=0,end=status->xrow->num,dir=1;
 954             if(seg->delta.x < 0) {
 955                 start = status->xrow->num-1;
 956                 end = dir = -1;
 957             }
 958             for(t=start;t!=end;t+=dir) {
 959                 box_t box = box_new(status->xrow->x[t], y);
 960                 double d0 = LINE_EQ(box.left1, seg);
 961                 double d1 = LINE_EQ(box.left2, seg);
 962                 double d2 = LINE_EQ(box.right1, seg);
 963                 double d3 = LINE_EQ(box.right2, seg);
 964                 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
 965                      d0<=0 && d1<=0 && d2<=0 && d3<0)) {
 966                     insert_point_into_segment(status, seg, box.right2);
 967                     break;
 968                 }
 969             }
 970
 971 #ifdef CHECKS
 972             /* we *need* to find a point to insert. the segment's own end point
 973                is in that list, for Pete's sake. */
 974             assert(t!=end);
 975 #endif
 976         }
 977         // now that this is done, too, we can also finally free this segment
 978         segment_destroy(seg);
 979         seg = next;
 980     }
 981     status->ending_segments = 0;
 982 }
 983
 984 static void recalculate_windings(status_t*status, segrange_t*range)
 985 {
 986 #ifdef DEBUG
 987     fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
 988 #endif
 989     segrange_adjust_endpoints(range, status->y);
 990
 991     segment_t*s = range->segmin;
 992     segment_t*end = range->segmax;
 993     segment_t*last = 0;
 994
 995 #ifdef DEBUG
 996     s = actlist_leftmost(status->actlist);
 997     while(s) {
 998         fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
 999             s == range->segmin?"S":(
1000             s == range->segmax?"E":""));
1001         s = s->right;
1002     }
1003     fprintf(stderr, "\n");
1004     s = range->segmin;
1005 #endif
1006 #ifdef CHECKS
1007     /* test sanity: verify that we don't have changed segments
1008        outside of the given range */
1009     s = actlist_leftmost(status->actlist);
1010     while(s && s!=range->segmin) {
1011         assert(!s->changed);
1012         s = s->right;
1013     }
1014     s = actlist_rightmost(status->actlist);
1015     while(s && s!=range->segmax) {
1016         assert(!s->changed);
1017         s = s->left;
1018     }
1019     /* in check mode, go through the whole interval so we can test
1020        that all polygons where the edgestyle changed also have seg->changed=1 */
1021     s = actlist_leftmost(status->actlist);
1022     end = 0;
1023 #endif
1024
1025     if(end)
1026         end = end->right;
1027     while(s!=end) {
1028 #ifndef CHECKS
1029         if(s->changed)
1030 #endif
1031         {
1032             segment_t* left = actlist_left(status->actlist, s);
1033             windstate_t wind = left?left->wind:status->windrule->start(status->context);
1034             s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
1035             edgestyle_t*fs_old = s->fs_out;
1036             s->fs_out = status->windrule->diff(&wind, &s->wind);
1037
1038 #ifdef DEBUG
1039             fprintf(stderr, "[%d] dir=%s wind=%d wind.filled=%s fs_old/new=%s/%s %s\n", s->nr, s->dir==DIR_UP?"up":"down", s->wind.wind_nr, s->wind.is_filled?"fill":"nofill",
1040                     fs_old?"draw":"omit", s->fs_out?"draw":"omit",
1041                     fs_old!=s->fs_out?"CHANGED":"");
1042 #endif
1043             assert(!(!s->changed && fs_old!=s->fs_out));
1044             s->changed = 0;
1045
1046 #ifdef CHECKS
1047             s->fs_out_ok = 1;
1048 #endif
1049         }
1050         s = s->right;
1051     }
1052 }
1053
1054 /* we need to handle horizontal lines in order to add points to segments
1055    we otherwise would miss during the windrule re-evaluation */
1056 static void intersect_with_horizontal(status_t*status, segment_t*h)
1057 {
1058     segment_t* left = actlist_find(status->actlist, h->a, h->a);
1059     segment_t* right = actlist_find(status->actlist, h->b, h->b);
1060
1061     /* not strictly necessary, also done by the event */
1062     xrow_add(status->xrow, h->a.x);
1063     point_t o = h->a;
1064
1065     if(!right) {
1066         assert(!left);
1067         return;
1068     }
1069
1070     left = actlist_right(status->actlist, left); //first seg to the right of h->a
1071     right = right->right; //first seg to the right of h->b
1072     segment_t* s = left;
1073
1074     while(s!=right) {
1075         assert(s);
1076         int32_t x = XPOS_INT(s, status->y);
1077 #ifdef DEBUG
1078         fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
1079                 s->a.x, s->a.y,
1080                 s->b.x, s->b.y,
1081                 x, status->y
1082                 );
1083 #endif
1084         assert(x >= h->a.x);
1085         assert(x <= h->b.x);
1086         assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
1087         assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
1088         xrow_add(status->xrow, x);
1089
1090         s = s->right;
1091     }
1092 }
1093
1094 static void event_apply(status_t*status, event_t*e)
1095 {
1096     switch(e->type) {
1097         case EVENT_HORIZONTAL: {
1098             segment_t*s = e->s1;
1099 #ifdef DEBUG
1100             event_dump(e);
1101 #endif
1102             intersect_with_horizontal(status, s);
1103             advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1104             segment_destroy(s);e->s1=0;
1105             break;
1106         }
1107         case EVENT_END: {
1108             //delete segment from list
1109             segment_t*s = e->s1;
1110 #ifdef DEBUG
1111             event_dump(e);
1112 #endif
1113 #ifdef CHECKS
1114             dict_del(status->intersecting_segs, s);
1115             dict_del(status->segs_with_point, s);
1116             assert(!dict_contains(status->intersecting_segs, s));
1117             assert(!dict_contains(status->segs_with_point, s));
1118 #endif
1119             segment_t*left = s->left;
1120             segment_t*right = s->right;
1121             actlist_delete(status->actlist, s);
1122             if(left && right)
1123                 schedule_crossing(status, left, right);
1124
1125             /* schedule segment for xrow handling */
1126             s->left = 0; s->right = status->ending_segments;
1127             status->ending_segments = s;
1128             advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1129             break;
1130         }
1131         case EVENT_START: {
1132             //insert segment into list
1133 #ifdef DEBUG
1134             event_dump(e);
1135 #endif
1136             segment_t*s = e->s1;
1137             assert(e->p.x == s->a.x && e->p.y == s->a.y);
1138             actlist_insert(status->actlist, s->a, s->b, s);
1139             segment_t*left = s->left;
1140             segment_t*right = s->right;
1141             if(left)
1142                 schedule_crossing(status, left, s);
1143             if(right)
1144                 schedule_crossing(status, s, right);
1145             schedule_endpoint(status, s);
1146             break;
1147         }
1148         case EVENT_CROSS: {
1149             // exchange two segments
1150 #ifdef DEBUG
1151             event_dump(e);
1152 #endif
1153             if(e->s1->right == e->s2) {
1154                 assert(e->s2->left == e->s1);
1155                 exchange_two(status, e);
1156             } else {
1157                 assert(e->s2->left != e->s1);
1158 #ifdef DEBUG
1159                 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1160 #endif
1161 #ifndef DONT_REMEMBER_CROSSINGS
1162                 /* ignore this crossing for now (there are some line segments in between).
1163                    it'll get rescheduled as soon as the "obstacles" are gone */
1164                 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1165                 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1166                 assert(del1 && del2);
1167 #endif
1168 #ifdef CHECKS
1169                 point_t pair;
1170                 pair.x = e->s1->nr;
1171                 pair.y = e->s2->nr;
1172 #ifndef DONT_REMEMBER_CROSSINGS
1173                 assert(dict_contains(status->seen_crossings, &pair));
1174                 dict_del(status->seen_crossings, &pair);
1175 #endif
1176 #endif
1177             }
1178         }
1179     }
1180 }
1181
1182 #ifdef CHECKS
1183 static void check_status(status_t*status)
1184 {
1185     DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1186         if((s->pos.x != s->b.x ||
1187             s->pos.y != s->b.y) &&
1188            !dict_contains(status->segs_with_point, s)) {
1189             fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1190                     SEGNR(s),
1191                     s->delta.x<0?"-":"+",
1192                     status->y);
1193             assert(0);
1194         }
1195     }
1196 }
1197 #endif
1198
1199 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1200 {
1201     /*
1202           |..|        |...........|                 |           |
1203           |..|        |...........|                 |           |
1204           |..+        +        +..|                 +--+     +--+
1205           |...........|        |..|                    |     |
1206           |...........|        |..|                    |     |
1207      */
1208
1209 #ifdef DEBUG
1210     fprintf(stderr, "========================================================================\n");
1211 #endif
1212     hqueue_t hqueue;
1213     hqueue_init(&hqueue);
1214     gfxpoly_enqueue(poly, 0, &hqueue, 0);
1215
1216     actlist_t* actlist = actlist_new();
1217
1218     event_t*e = hqueue_get(&hqueue);
1219     while(e) {
1220         int32_t y = e->p.y;
1221         int32_t x = 0;
1222 #ifdef DEBUG
1223         fprintf(stderr, "HORIZONTALS ----------------------------------- %d\n", y);
1224         actlist_dump(actlist, y-1);
1225 #endif
1226 #ifdef CHECKS
1227         actlist_verify(actlist, y-1);
1228 #endif
1229         edgestyle_t*fill = 0;
1230         int wind = 0;
1231
1232         do {
1233             assert(e->s1->fs);
1234             if(fill && x != e->p.x) {
1235                 assert(abs(wind)==1);
1236                 assert(x<e->p.x);
1237
1238                 gfxpolystroke_t*stroke = rfx_calloc(sizeof(gfxpolystroke_t));
1239                 stroke->next = poly->strokes;
1240                 poly->strokes = stroke;
1241
1242                 stroke->num_points = 2;
1243                 stroke->points = malloc(sizeof(point_t)*2);
1244
1245                 if(wind>0) {
1246                     stroke->dir = DIR_DOWN;
1247                 } else {
1248                     stroke->dir = DIR_UP;
1249                 }
1250 #ifdef DEBUG
1251                 fprintf(stderr, "%d) draw horizontal line from %d to %d (dir=%s)\n", y, x, e->p.x, stroke->dir==DIR_UP?"up":"down");
1252 #endif
1253
1254                 stroke->fs = fill;
1255                 point_t a,b;
1256                 a.y = b.y = y;
1257                 a.x = x;
1258                 b.x = e->p.x;
1259                 stroke->points[0] = a;
1260                 stroke->points[1] = b;
1261 #ifdef CHECKS
1262                 /* the output should always be intersection free polygons, so check this horizontal
1263                    line isn't puncturing any segments in the active list */
1264                 segment_t* start = actlist_find(actlist, a, a);
1265                 segment_t* s = actlist_find(actlist, b, b);
1266                 while(s!=start) {
1267                     assert(s->a.y == y || s->b.y == y);
1268                     s = s->left;
1269                 }
1270 #endif
1271             }
1272
1273             segment_t*s = e->s1;
1274
1275             segment_t*left = 0;
1276             switch(e->type) {
1277                 case EVENT_START: {
1278                     assert(e->p.x == s->a.x && e->p.y == s->a.y);
1279                     actlist_insert(actlist, s->a, s->b, s);
1280                     event_t* e = event_new();
1281                     e->type = EVENT_END;
1282                     e->p = s->b;
1283                     e->s1 = s;
1284                     e->s2 = 0;
1285                     hqueue_put(&hqueue, e);
1286                     left = actlist_left(actlist, s);
1287                     wind += e->s1->dir==DIR_DOWN?-1:1;
1288                     break;
1289                 }
1290                 case EVENT_END: {
1291                     left = actlist_left(actlist, s);
1292                     actlist_delete(actlist, s);
1293                     advance_stroke(0, &hqueue, s->stroke, s->polygon_nr, s->stroke_pos);
1294                     wind += e->s1->dir==DIR_DOWN?1:-1;
1295                     break;
1296                 }
1297                 default: assert(0);
1298             }
1299
1300             x = e->p.x;
1301
1302             fill = fill?0:&edgestyle_default;
1303 #if 0
1304             if(windrule==&windrule_evenodd) {
1305                 if(!!fill != !!fill2) {
1306                     segment_dump(s);
1307                     event_dump(e);
1308                     printf("at y=%d x=%d (hline:%p)\n", e->p.y, x, old_fill);
1309                     if(e->type==EVENT_END) {
1310                         printf("            %9p\n", s->fs);
1311                         printf("               |\n");
1312                     }
1313                     printf("              %3d %c%2d \n", before1.is_filled, e->type==EVENT_END?'|':' ', after1.is_filled);
1314                     printf("%12p -----+----- %p\n", old_fill, fill2);
1315                     printf("              %3d %c%2d \n", before2.is_filled, e->type==EVENT_START?'|':' ', after2.is_filled);
1316                     if(e->type==EVENT_START) {
1317                         printf("                  |\n");
1318                         printf("             %9p\n", s->fs);
1319                     }
1320                 }
1321                 assert(!!fill == !!fill2);
1322             }
1323 #endif
1324
1325 #ifdef DEBUG
1326             fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d dir:%s\n",
1327                     y, e->type==EVENT_START?"start":"end",
1328                     s->nr,
1329                     left?left->nr:-1,
1330                     x, s->dir==DIR_UP?"up":"down");
1331 #endif
1332
1333             if(e->type == EVENT_END)
1334                 segment_destroy(s);
1335
1336             event_free(e);
1337             e = hqueue_get(&hqueue);
1338         } while(e && y == e->p.y);
1339
1340 #ifdef CHECKS
1341         edgestyle_t*bleeding = fill;
1342         assert(!bleeding);
1343         segment_t*s = actlist_leftmost(actlist);
1344         int dir = 0;
1345         while(s) {
1346             dir += s->dir==DIR_UP?-1:1;
1347             s = actlist_right(actlist, s);
1348         }
1349         assert(!dir);
1350 #endif
1351     }
1352
1353     actlist_destroy(actlist);
1354     hqueue_destroy(&hqueue);
1355 }
1356
1357 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly1, gfxpoly_t*poly2, windrule_t*windrule, windcontext_t*context)
1358 {
1359     current_polygon = poly1;
1360
1361     status_t status;
1362     memset(&status, 0, sizeof(status_t));
1363     queue_init(&status.queue);
1364     gfxpoly_enqueue(poly1, &status.queue, 0, /*polygon nr*/0);
1365     if(poly2) {
1366         assert(poly1->gridsize == poly2->gridsize);
1367         gfxpoly_enqueue(poly2, &status.queue, 0, /*polygon nr*/1);
1368     }
1369
1370     status.windrule = windrule;
1371     status.context = context;
1372     status.actlist = actlist_new();
1373
1374 #ifdef CHECKS
1375     status.seen_crossings = dict_new2(&point_type);
1376     int32_t lasty=-0x80000000;
1377 #endif
1378
1379     status.xrow = xrow_new();
1380
1381     event_t*e = queue_get(&status.queue);
1382     while(e) {
1383         assert(e->s1->fs);
1384         status.y = e->p.y;
1385 #ifdef CHECKS
1386         assert(status.y>=lasty);
1387         lasty = status.y;
1388         status.intersecting_segs = dict_new2(&ptr_type);
1389         status.segs_with_point = dict_new2(&ptr_type);
1390 #endif
1391
1392 #ifdef DEBUG
1393         fprintf(stderr, "----------------------------------- %d\n", status.y);
1394         actlist_dump(status.actlist, status.y-1);
1395 #endif
1396 #ifdef CHECKS
1397         actlist_verify(status.actlist, status.y-1);
1398 #endif
1399         xrow_reset(status.xrow);
1400         do {
1401             xrow_add(status.xrow, e->p.x);
1402             event_apply(&status, e);
1403             event_free(e);
1404             e = queue_get(&status.queue);
1405         } while(e && status.y == e->p.y);
1406
1407         xrow_sort(status.xrow);
1408         segrange_t range;
1409         memset(&range, 0, sizeof(range));
1410 #ifdef DEBUG
1411         actlist_dump(status.actlist, status.y);
1412 #endif
1413         add_points_to_positively_sloped_segments(&status, status.y, &range);
1414         add_points_to_negatively_sloped_segments(&status, status.y, &range);
1415         add_points_to_ending_segments(&status, status.y);
1416
1417         recalculate_windings(&status, &range);
1418 #ifdef CHECKS
1419         check_status(&status);
1420         dict_destroy(status.intersecting_segs);
1421         dict_destroy(status.segs_with_point);
1422 #endif
1423     }
1424 #ifdef CHECKS
1425     dict_destroy(status.seen_crossings);
1426 #endif
1427     actlist_destroy(status.actlist);
1428     queue_destroy(&status.queue);
1429     xrow_destroy(status.xrow);
1430
1431     gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t));
1432     p->gridsize = poly1->gridsize;
1433     p->strokes = status.strokes;
1434
1435 #ifdef CHECKS
1436     /* we only add segments with non-empty edgestyles to strokes in
1437        recalculate_windings, but better safe than sorry */
1438     gfxpolystroke_t*stroke = p->strokes;
1439     while(stroke) {
1440         assert(stroke->fs);
1441         stroke = stroke->next;
1442     }
1443 #endif
1444
1445     add_horizontals(p, &windrule_evenodd, context); // output is always even/odd
1446     //add_horizontals(p, windrule, context);
1447     return p;
1448 }
1449
1450 static windcontext_t twopolygons = {2};
1451 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*p1, gfxpoly_t*p2)
1452 {
1453     return gfxpoly_process(p1, p2, &windrule_intersect, &twopolygons);
1454 }
1455 gfxpoly_t* gfxpoly_union(gfxpoly_t*p1, gfxpoly_t*p2)
1456 {
1457     return gfxpoly_process(p1, p2, &windrule_union, &twopolygons);
1458 }