lib/gfxpoly/poly.c

   1 #include <stdlib.h>
   2 #include <assert.h>
   3 #include <memory.h>
   4 #include <math.h>
   5 #include "../mem.h"
   6 #include "../types.h"
   7 #include "../q.h"
   8 #include "poly.h"
   9 #include "active.h"
  10 #include "xrow.h"
  11 #include "wind.h"
  12
  13 //#define DEBUG
  14 //#undef assert
  15 //#define assert(x)
  16
  17 char point_equals(const void*o1, const void*o2)
  18 {
  19     const point_t*p1 = o1;
  20     const point_t*p2 = o2;
  21     return p1->x == p2->x && p1->y == p2->y;
  22 }
  23 unsigned int point_hash(const void*o)
  24 {
  25     const point_t*p = o;
  26     return p->x^p->y;
  27 }
  28 void* point_dup(const void*o)
  29 {
  30     const point_t*p = o;
  31     point_t*n = malloc(sizeof(point_t));
  32     n->x = p->x;
  33     n->y = p->y;
  34     return n;
  35 }
  36 void point_free(void*o)
  37 {
  38     point_t*p = o;
  39     p->x = 0;
  40     p->y = 0;
  41     free(p);
  42 }
  43 type_t point_type = {
  44     equals: point_equals,
  45     hash: point_hash,
  46     dup: point_dup,
  47     free: point_free,
  48 };
  49
  50 typedef struct _status {
  51     int y;
  52     int num_polygons;
  53     actlist_t*actlist;
  54     heap_t*queue;
  55     edge_t*output;
  56     xrow_t*xrow;
  57     windrule_t*windrule;
  58 #ifdef DEBUG
  59     dict_t*seen_crossings; //list of crossing we saw so far
  60     dict_t*intersecting_segs; //list of segments intersecting in this scanline
  61     dict_t*segs_with_point; //lists of segments that received a point in this scanline
  62 #endif
  63 } status_t;
  64
  65 int compare_events_simple(const void*_a,const void*_b)
  66 {
  67     event_t* a = (event_t*)_a;
  68     event_t* b = (event_t*)_b;
  69     if(a->p.y < b->p.y) {
  70         return 1;
  71     } else if(a->p.y > b->p.y) {
  72         return -1;
  73     } else if(a->p.x < b->p.x) {
  74         return 1;
  75     } else if(a->p.x > b->p.x) {
  76         return -1;
  77     } else
  78         return 0;
  79 }
  80
  81 int compare_events(const void*_a,const void*_b)
  82 {
  83     event_t* a = (event_t*)_a;
  84     event_t* b = (event_t*)_b;
  85     int d = b->p.y - a->p.y;
  86     if(d) return d;
  87     /* we should schedule start events after end/intersect.
  88        The order of end/intersect doesn't actually matter, however,
  89        so this might be doing too much */
  90     d = b->type - a->type;
  91     if(d) return d;
  92     d = b->p.x - a->p.x;
  93     return d;
  94 }
  95
  96 gfxpoly_t* gfxpoly_new(double gridsize)
  97 {
  98     gfxpoly_t*p = (gfxpoly_t*)rfx_calloc(sizeof(gfxpoly_t));
  99     p->gridsize = gridsize;
 100     return p;
 101 }
 102 void gfxpoly_destroy(gfxpoly_t*poly)
 103 {
 104     edge_t* s = poly->edges;
 105     while(s) {
 106         edge_t*next  = s->next;
 107         free(s);
 108         s = next;
 109     }
 110     free(poly);
 111 }
 112 char gfxpoly_check(gfxpoly_t*poly)
 113 {
 114     edge_t* s = poly->edges;
 115     dict_t*d = dict_new2(&point_type);
 116     while(s) {
 117         if(!dict_contains(d, &s->a)) {
 118             dict_put(d, &s->a, (void*)(ptroff_t)1);
 119         } else {
 120             int count = (ptroff_t)dict_lookup(d, &s->a);
 121             dict_del(d, &s->a);
 122             count++;
 123             dict_put(d, &s->a, (void*)(ptroff_t)count);
 124         }
 125         if(!dict_contains(d, &s->b)) {
 126             dict_put(d, &s->b, (void*)(ptroff_t)1);
 127         } else {
 128             int count = (ptroff_t)dict_lookup(d, &s->b);
 129             dict_del(d, &s->b);
 130             count++;
 131             dict_put(d, &s->b, (void*)(ptroff_t)count);
 132         }
 133         s = s->next;
 134     }
 135     DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
 136         int count = (ptroff_t)c;
 137         if(count&1) {
 138             fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count);
 139             return 0;
 140         }
 141     }
 142     return 1;
 143 }
 144
 145 void gfxpoly_dump(gfxpoly_t*poly)
 146 {
 147     edge_t* s = poly->edges;
 148     double g = poly->gridsize;
 149     while(s) {
 150         fprintf(stderr, "(%f,%f) -> (%f,%f)\n", s->a.x*g, s->a.y*g, s->b.x*g, s->b.y*g);
 151         s = s->next;
 152     }
 153 }
 154
 155 inline static event_t event_new()
 156 {
 157     event_t e;
 158     memset(&e, 0, sizeof(e));
 159     return e;
 160 }
 161
 162 void event_dump(event_t*e)
 163 {
 164     if(e->type == EVENT_HORIZONTAL) {
 165         fprintf(stderr, "Horizontal [%d] (%d,%d) -> (%d,%d)\n", e->s1->nr, e->s1->a.x, e->s1->a.y, e->s1->b.x, e->s1->b.y);
 166     } else if(e->type == EVENT_START) {
 167         fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
 168     } else if(e->type == EVENT_END) {
 169         fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
 170     } else if(e->type == EVENT_CROSS) {
 171         fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
 172     } else {
 173         assert(0);
 174     }
 175 }
 176
 177 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
 178 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
 179
 180 void segment_init(segment_t*s, int x1, int y1, int x2, int y2, windstate_t windstate, int polygon_nr)
 181 {
 182     if(y1<y2) {
 183         s->dir = DIR_DOWN;
 184     } else if(y1>y2) {
 185         int x = x1;x1=x2;x2=x;
 186         int y = y1;y1=y2;y2=y;
 187         s->dir = DIR_UP;
 188     } else {
 189         /* up/down for horizontal segments is handled by "rotating"
 190            them 90° anticlockwise in screen coordinates (tilt your head to
 191            the right) */
 192         s->dir = DIR_UP;
 193         if(x1>x2) {
 194             s->dir = DIR_DOWN;
 195             int x = x1;x1=x2;x2=x;
 196             int y = y1;y1=y2;y2=y;
 197         }
 198     }
 199     s->a.x = x1;
 200     s->a.y = y1;
 201     s->b.x = x2;
 202     s->b.y = y2;
 203     s->k = (double)x1*y2-(double)x2*y1;
 204     s->left = s->right = 0;
 205     s->delta.x = x2-x1;
 206     s->delta.y = y2-y1;
 207     s->pos = s->a;
 208     s->polygon_nr = polygon_nr;
 209 #define XDEBUG
 210 #ifdef XDEBUG
 211     static int segment_count=0;
 212     s->nr = segment_count++;
 213 #endif
 214
 215     assert(LINE_EQ(s->a, s) == 0);
 216     assert(LINE_EQ(s->b, s) == 0);
 217
 218     /* check that all signs are in order:
 219        a        a
 220        |\      /|
 221        | \    / |
 222      minx-b  b--maxx
 223      < 0        > 0
 224     */
 225     point_t p = s->b;
 226     p.x = min32(s->a.x, s->b.x);
 227     assert(LINE_EQ(p, s) <= 0);
 228     p.x = max32(s->a.x, s->b.x);
 229     assert(LINE_EQ(p, s) >= 0);
 230
 231     dict_init2(&s->scheduled_crossings, &ptr_type, 0);
 232 }
 233
 234 segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2, windstate_t initial, int polygon_nr)
 235 {
 236     segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
 237     segment_init(s, x1, y1, x2, y2, initial, polygon_nr);
 238     return s;
 239 }
 240 void segment_destroy(segment_t*s)
 241 {
 242     dict_clear(&s->scheduled_crossings);
 243     free(s);
 244 }
 245
 246 void gfxpoly_enqueue(edge_t*list, heap_t*queue, windstate_t initial, int polygon_nr)
 247 {
 248     edge_t*l;
 249     for(l=list;l;l=l->next) {
 250         if(l->a.x == l->b.x &&
 251            l->a.y == l->b.y) {
 252             fprintf(stderr, "Warning: intersector input contains zero-length segments\n");
 253             continue;
 254         }
 255         segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y, initial, polygon_nr);
 256 #ifdef DEBUG
 257         fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n",
 258                 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
 259                 s->dir==DIR_UP?"up":"down");
 260 #endif
 261         event_t e = event_new();
 262         e.type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
 263         e.p = s->a;
 264         e.s1 = s;
 265         e.s2 = 0;
 266         heap_put(queue, &e);
 267     }
 268 }
 269
 270 void schedule_endpoint(status_t*status, segment_t*s)
 271 {
 272     // schedule end point of segment
 273     assert(s->b.y > status->y);
 274     event_t e;
 275     e.type = EVENT_END;
 276     e.p = s->b;
 277     e.s1 = s;
 278     e.s2 = 0;
 279     heap_put(status->queue, &e);
 280 }
 281
 282 void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
 283 {
 284     /* the code that's required (and the checks you can perform) before
 285        it can be said with 100% certainty that we indeed have a valid crossing
 286        amazes me every time. -mk */
 287     assert(s1!=s2);
 288
 289     /* we probably could precompute these */
 290     int32_t minx1 = min32(s1->a.x,s1->b.x);
 291     int32_t miny1 = min32(s1->a.y,s1->b.y);
 292     int32_t maxx1 = max32(s1->a.x,s1->b.x);
 293     int32_t maxy1 = max32(s1->a.y,s1->b.y);
 294     int32_t minx2 = min32(s2->a.x,s2->b.x);
 295     int32_t miny2 = min32(s2->a.y,s2->b.y);
 296     int32_t maxx2 = max32(s2->a.x,s2->b.x);
 297     int32_t maxy2 = max32(s2->a.y,s2->b.y);
 298
 299     /* both segments are active, so this can't happen */
 300     assert(!(maxy1 <= miny2 || maxy2 <= miny1));
 301
 302     /* TODO: optimize this. remove y, precompute the two x values */
 303     if(maxx1 <= minx2 || maxx2 <= minx1 ||
 304        maxy1 <= miny2 || maxy2 <= miny1) {
 305         /* bounding boxes don't intersect */
 306         return;
 307     }
 308
 309     if(dict_contains(&s1->scheduled_crossings, s2)) {
 310         /* FIXME: this whole segment hashing thing is really slow */
 311         //fprintf(stderr, "Encountered crossing between [%d] and [%d] twice\n", s1->nr, s2->nr);
 312
 313         // we already know about this one
 314         return;
 315     }
 316
 317     double adx = s1->delta.x;
 318     double ady = s1->delta.y;
 319     double bdx = s2->delta.x;
 320     double bdy = s2->delta.y;
 321     double det = adx*bdy - ady*bdx;
 322     if(!det) {
 323         if(s1->k == s2->k) {
 324             // lines are exactly on top of each other (ignored)
 325 #ifdef DEBUG
 326             fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
 327 #endif
 328             return;
 329         } else {
 330             /* lines are parallel */
 331             return;
 332         }
 333     }
 334     double asign2 = LINE_EQ(s1->a, s2);
 335     double bsign2 = LINE_EQ(s1->b, s2);
 336     if(asign2<0 && bsign2<0) {
 337         // segment1 is completely to the left of segment2
 338         return;
 339     }
 340     if(asign2>0 && bsign2>0)  {
 341         // segment2 is completely to the left of segment1
 342         return;
 343     }
 344     if(asign2==0) {
 345         // segment1 touches segment2 in a single point (ignored)
 346 #ifdef DEBUG
 347         fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
 348 #endif
 349         return;
 350     }
 351     if(bsign2==0) {
 352         // segment1 touches segment2 in a single point (ignored)
 353 #ifdef DEBUG
 354         fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
 355 #endif
 356         return;
 357     }
 358     double asign1 = LINE_EQ(s2->a, s1);
 359     double bsign1 = LINE_EQ(s2->b, s1);
 360     if(asign1<0 && bsign1<0) {
 361         // segment1 is completely to the left of segment2
 362         return;
 363     }
 364     if(asign1>0 && bsign1>0)  {
 365         // segment2 is completely to the left of segment1
 366         return;
 367     }
 368     if(asign1==0) {
 369         // segment2 touches segment1 in a single point (ignored)
 370 #ifdef DEBUG
 371         fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
 372 #endif
 373         return;
 374     }
 375     if(asign2==0) {
 376         // segment2 touches segment1 in a single point (ignored)
 377 #ifdef DEBUG
 378         fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
 379 #endif
 380         return;
 381     }
 382
 383     double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
 384     double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
 385
 386     point_t p;
 387     p.x = (int32_t)ceil((-la*bdx +lb*adx) / det);
 388     p.y = (int32_t)ceil((+lb*ady -la*bdy) / det);
 389
 390     assert(p.y >= status->y);
 391 #ifdef DEBUG
 392     point_t pair;
 393     pair.x = s1->nr;
 394     pair.y = s2->nr;
 395     assert(!dict_contains(status->seen_crossings, &pair));
 396     dict_put(status->seen_crossings, &pair, 0);
 397     fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
 398 #endif
 399
 400     /* we insert into each other's intersection history because these segments might switch
 401        places and we still want to look them up quickly after they did */
 402     dict_put(&s1->scheduled_crossings, s2, 0);
 403     dict_put(&s2->scheduled_crossings, s1, 0);
 404
 405     event_t e = event_new();
 406     e.type = EVENT_CROSS;
 407     e.p = p;
 408     e.s1 = s1;
 409     e.s2 = s2;
 410     heap_put(status->queue, &e);
 411     return;
 412 }
 413
 414 void exchange_two(status_t*status, event_t*e)
 415 {
 416     //exchange two segments in list
 417     segment_t*s1 = e->s1;
 418     segment_t*s2 = e->s2;
 419 #ifdef DEBUG
 420     if(!dict_contains(status->intersecting_segs, s1))
 421         dict_put(status->intersecting_segs, s1, 0);
 422     if(!dict_contains(status->intersecting_segs, s2))
 423         dict_put(status->intersecting_segs, s2, 0);
 424 #endif
 425     segment_t*left = actlist_left(status->actlist, s2);
 426     segment_t*right = actlist_right(status->actlist, s1);
 427     assert(left == s1);
 428     assert(right == s2);
 429     actlist_swap(status->actlist, s1, s2);
 430     assert(actlist_right(status->actlist, s2) == s1);
 431     assert(actlist_left(status->actlist, s1) == s2);
 432     left = actlist_left(status->actlist, s2);
 433     right = actlist_right(status->actlist, s1);
 434     if(left)
 435         schedule_crossing(status, left, s2);
 436     if(right)
 437         schedule_crossing(status, s1, right);
 438 }
 439
 440 typedef struct _box {
 441     point_t left1, left2, right1, right2;
 442 } box_t;
 443 static inline box_t box_new(int x, int y)
 444 {
 445     box_t box;
 446     box.right1.x = box.right2.x = x;
 447     box.left1.x = box.left2.x = x-1;
 448     box.left1.y = box.right1.y = y-1;
 449     box.left2.y = box.right2.y = y;
 450     return box;
 451 }
 452
 453
 454 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
 455 {
 456     assert(s->pos.x != p.x || s->pos.y != p.y);
 457
 458 #ifdef DEBUG
 459     if(!dict_contains(status->segs_with_point, s))
 460         dict_put(status->segs_with_point, s, 0);
 461 #endif
 462
 463     assert(s->fs_out_ok);
 464     if(s->fs_out) {
 465 #ifdef DEBUG
 466         fprintf(stderr, "[%d] receives next point (%d,%d) (drawing)\n", s->nr, p.x, p.y);
 467 #endif
 468         // omit horizontal lines
 469         if(s->pos.y != p.y) {
 470             edge_t*e = malloc(sizeof(edge_t));
 471             e->a = s->pos;
 472             e->b = p;
 473             assert(e->a.y != e->b.y);
 474             e->next = status->output;
 475             status->output = e;
 476         }
 477     } else {
 478 #ifdef DEBUG
 479         fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
 480 #endif
 481     }
 482     s->pos = p;
 483 }
 484
 485 /* possible optimizations:
 486    1.) keep two different active lists around, one for negative and one for
 487        positive slopes
 488    2.) delay starting events until after this function (tricky, because we *do*
 489        need the start coordinates)
 490 */
 491 /*
 492    SLOPE_POSITIVE:
 493       \+     \ +
 494 ------ I      \I
 495       -I\----  I
 496        I \   --I\---
 497        I  \    I \  -------
 498        +   \   +  \
 499 */
 500 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y)
 501 {
 502     int t;
 503     for(t=0;t<status->xrow->num;t++) {
 504         box_t box = box_new(status->xrow->x[t], y);
 505         segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
 506         seg = actlist_right(status->actlist, seg);
 507         while(seg) {
 508             if(seg->a.y == y) {
 509                 // this segment just started, ignore it
 510             } else if(seg->delta.x < 0) {
 511                 // ignore segment w/ negative slope
 512             } else {
 513                 double d1 = LINE_EQ(box.right1, seg);
 514                 double d2 = LINE_EQ(box.right2, seg);
 515                 if(d1>=0 || d2>=0) {
 516                     insert_point_into_segment(status, seg, box.right2);
 517                 } else {
 518                     break;
 519                 }
 520             }
 521             seg = actlist_right(status->actlist, seg);
 522         }
 523     }
 524 }
 525 /* SLOPE_NEGATIVE:
 526    |   +   /|  +  /    /
 527    |   I  / |  I /    /
 528    |   I /  |  I/    /
 529    |   I/   |  I    /
 530    |   I    | /I   /
 531    |  /+    |/ +  /
 532 */
 533 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y)
 534 {
 535     int t;
 536     for(t=status->xrow->num-1;t>=0;t--) {
 537         box_t box = box_new(status->xrow->x[t], y);
 538         segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
 539         while(seg) {
 540             if(seg->a.y == y) {
 541                 // this segment just started, ignore it
 542             } else if(seg->delta.x >= 0) {
 543                 // ignore segment w/ positive slope
 544             } else {
 545                 double d1 = LINE_EQ(box.left1, seg);
 546                 double d2 = LINE_EQ(box.left2, seg);
 547                 if(d1<0 || d2<0) {
 548                     insert_point_into_segment(status, seg, box.right2);
 549                 } else {
 550                     break;
 551                 }
 552             }
 553             seg = actlist_left(status->actlist, seg);
 554         }
 555     }
 556 }
 557
 558 static void recalculate_windings(status_t*status)
 559 {
 560     /* TODO: we could use some clever second linked list structure so that we
 561              only need to process points we know we marked */
 562
 563     segment_t*s = actlist_leftmost(status->actlist);
 564     segment_t*last = 0;
 565     while(s) {
 566         windstate_t wind = last?last->wind:status->windrule->start(status->num_polygons);
 567         s->wind = status->windrule->add(wind, s->fs, s->dir, s->polygon_nr);
 568         s->fs_out = status->windrule->diff(&wind, &s->wind);
 569         s->fs_out_ok = 1;
 570 #ifdef DEBUG
 571         fprintf(stderr, "[%d] %s/%d/%s/%s ", s->nr, s->dir==DIR_UP?"up":"down", s->wind.wind_nr, s->wind.is_filled?"fill":"nofill", s->fs_out?"draw":"omit");
 572 #endif
 573         last = s;
 574         s = actlist_right(status->actlist, s);
 575     }
 576 #ifdef DEBUG
 577     fprintf(stderr, "\n");
 578 #endif
 579
 580 }
 581
 582 /* we need to handle horizontal lines in order to add points to segments
 583    we otherwise would miss during the windrule re-evaluation */
 584 void intersect_with_horizontal(status_t*status, segment_t*h)
 585 {
 586     segment_t* left = actlist_find(status->actlist, h->a, h->a);
 587     segment_t* right = actlist_find(status->actlist, h->b, h->b);
 588
 589     /* not strictly necessary, also done by the event */
 590     xrow_add(status->xrow, h->a.x);
 591     point_t o = h->a;
 592
 593     left = actlist_right(status->actlist, left);
 594     right = actlist_right(status->actlist, right);
 595     segment_t* s = left;
 596
 597     while(s!=right) {
 598         assert(s);
 599         /*
 600            x1 + ((x2-x1)*(y-y1)) / dy =
 601            (x1*(y2-y) + x2*(y-y1)) / dy
 602         */
 603         point_t p;
 604         p.y = status->y;
 605         p.x = XPOS(s, p.y);
 606 #ifdef DEBUG
 607         fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
 608                 s->a.x, s->a.y,
 609                 s->b.x, s->b.y,
 610                 p.x, p.y
 611                 );
 612 #endif
 613         assert(p.x >= h->a.x);
 614         assert(p.x <= h->b.x);
 615         assert(s->delta.x > 0 && p.x >= s->a.x || s->delta.x <= 0 && p.x <= s->a.x);
 616         assert(s->delta.x > 0 && p.x <= s->b.x || s->delta.x <= 0 && p.x >= s->b.x);
 617         xrow_add(status->xrow, p.x);
 618
 619         s = actlist_right(status->actlist, s);
 620     }
 621 }
 622
 623 void event_apply(status_t*status, event_t*e)
 624 {
 625     switch(e->type) {
 626         case EVENT_HORIZONTAL: {
 627 #ifdef DEBUG
 628             event_dump(e);
 629 #endif
 630             intersect_with_horizontal(status, e->s1);
 631             break;
 632         }
 633         case EVENT_END: {
 634             //delete segment from list
 635             segment_t*s = e->s1;
 636 #ifdef DEBUG
 637             event_dump(e);
 638             dict_del(status->intersecting_segs, s);
 639             dict_del(status->segs_with_point, s);
 640             assert(!dict_contains(status->intersecting_segs, s));
 641             assert(!dict_contains(status->segs_with_point, s));
 642 #endif
 643             insert_point_into_segment(status, s, s->b);
 644             segment_t*left = actlist_left(status->actlist, s);
 645             segment_t*right = actlist_right(status->actlist, s);
 646             actlist_delete(status->actlist, s);
 647             if(left && right)
 648                 schedule_crossing(status, left, right);
 649             segment_destroy(s);e->s1=0;
 650             break;
 651         }
 652         case EVENT_START: {
 653             //insert segment into list
 654 #ifdef DEBUG
 655             event_dump(e);
 656 #endif
 657             segment_t*s = e->s1;
 658             actlist_insert(status->actlist, e->p, s);
 659             segment_t*left = actlist_left(status->actlist, s);
 660             segment_t*right = actlist_right(status->actlist, s);
 661             if(left)
 662                 schedule_crossing(status, left, s);
 663             if(right)
 664                 schedule_crossing(status, s, right);
 665             schedule_endpoint(status, e->s1);
 666             break;
 667         }
 668         case EVENT_CROSS: {
 669             // exchange two segments
 670 #ifdef DEBUG
 671             event_dump(e);
 672 #endif
 673             if(actlist_right(status->actlist, e->s1) == e->s2 &&
 674                actlist_left(status->actlist, e->s2) == e->s1) {
 675                 exchange_two(status, e);
 676             } else {
 677                 /* ignore this crossing for now (there are some line segments in between).
 678                    it'll get rescheduled as soon as the "obstacles" are gone */
 679                 char del1 = dict_del(&e->s1->scheduled_crossings, e->s2);
 680                 char del2 = dict_del(&e->s2->scheduled_crossings, e->s1);
 681                 assert(del1 && del2);
 682 #ifdef DEBUG
 683                 point_t pair;
 684                 pair.x = e->s1->nr;
 685                 pair.y = e->s2->nr;
 686                 assert(dict_contains(status->seen_crossings, &pair));
 687                 dict_del(status->seen_crossings, &pair);
 688 #endif
 689             }
 690         }
 691     }
 692 }
 693
 694 #ifdef DEBUG
 695 void check_status(status_t*status)
 696 {
 697     DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
 698         if((s->pos.x != s->b.x ||
 699             s->pos.y != s->b.y) &&
 700            !dict_contains(status->segs_with_point, s)) {
 701             fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
 702                     s->nr,
 703                     s->delta.x<0?"-":"+",
 704                     status->y);
 705             assert(0);
 706         }
 707     }
 708 }
 709 #endif
 710
 711 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule)
 712 {
 713     /*
 714           |..|        |...........|                 |           |
 715           |..|        |...........|                 |           |
 716           |..+        +        +..|                 +--+     +--+
 717           |...........|        |..|                    |     |
 718           |...........|        |..|                    |     |
 719      */
 720
 721 #ifdef DEBUG
 722     fprintf(stderr, "========================================================================\n");
 723 #endif
 724     heap_t* queue = heap_new(sizeof(event_t), compare_events_simple);
 725     gfxpoly_enqueue(poly->edges, queue, windrule->start(1), 0);
 726
 727     actlist_t* actlist = actlist_new();
 728
 729     event_t*e = heap_chopmax(queue);
 730     while(e) {
 731         int y = e->p.y;
 732         int x = 0;
 733         char fill = 0;
 734 #ifdef DEBUG
 735         actlist_verify_and_dump(actlist, y-1);
 736 #endif
 737         do {
 738             if(fill && x != e->p.x) {
 739 #ifdef DEBUG
 740                 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
 741 #endif
 742                 edge_t*l= malloc(sizeof(edge_t));
 743                 l->a.y = l->b.y = y;
 744                 l->a.x = x;
 745                 l->b.x = e->p.x;
 746                 l->next = poly->edges;
 747                 poly->edges = l;
 748             }
 749             segment_t*left = 0;
 750             segment_t*s = e->s1;
 751
 752             windstate_t before,after;
 753             switch(e->type) {
 754                 case EVENT_START: {
 755                     actlist_insert(actlist, e->p, s);
 756                     event_t e;
 757                     e.type = EVENT_END;
 758                     e.p = s->b;
 759                     e.s1 = s;
 760                     e.s2 = 0;
 761                     heap_put(queue, &e);
 762                     left = actlist_left(actlist, s);
 763
 764                     before = left?left->wind:windrule->start(1);
 765                     after = s->wind = windrule->add(before, s->fs, s->dir, s->polygon_nr);
 766                     break;
 767                 }
 768                 case EVENT_END: {
 769                     left = actlist_left(actlist, s);
 770                     actlist_delete(actlist, s);
 771
 772                     before = s->wind;
 773                     after = left?left->wind:windrule->start(1);
 774                     break;
 775                 }
 776                 default: assert(0);
 777             }
 778
 779             x = e->p.x;
 780             fill ^= 1;//(before.is_filled != after.is_filled);
 781 #ifdef DEBUG
 782             fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d before:%d after:%d\n",
 783                     y, e->type==EVENT_START?"start":"end",
 784                     s->nr,
 785                     left?left->nr:-1,
 786                     x,
 787                     before.is_filled, after.is_filled);
 788 #endif
 789
 790             if(e->type == EVENT_END)
 791                 segment_destroy(s);
 792
 793             e = heap_chopmax(queue);
 794         } while(e && y == e->p.y);
 795
 796         if(fill) {
 797             fprintf(stderr, "Error: polygon is bleeding\n");
 798             exit(0);
 799         }
 800     }
 801 }
 802
 803 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule)
 804 {
 805     heap_t* queue = heap_new(sizeof(event_t), compare_events);
 806
 807     gfxpoly_enqueue(poly->edges, queue, windrule->start(1), /*polygon nr*/0);
 808
 809     status_t status;
 810     memset(&status, 0, sizeof(status_t));
 811     status.num_polygons = 1;
 812     status.queue = queue;
 813     status.windrule = windrule;
 814     status.actlist = actlist_new();
 815 #ifdef DEBUG
 816     status.seen_crossings = dict_new2(&point_type);
 817 #endif
 818
 819     status.xrow = xrow_new();
 820
 821     event_t*e = heap_chopmax(queue);
 822     while(e) {
 823         status.y = e->p.y;
 824 #ifdef DEBUG
 825         status.intersecting_segs = dict_new2(&ptr_type);
 826         status.segs_with_point = dict_new2(&ptr_type);
 827         fprintf(stderr, "----------------------------------- %d\n", status.y);
 828         actlist_verify_and_dump(status.actlist, status.y-1);
 829 #endif
 830         xrow_reset(status.xrow);
 831         do {
 832             xrow_add(status.xrow, e->p.x);
 833             event_apply(&status, e);
 834             free(e);
 835             e = heap_chopmax(queue);
 836         } while(e && status.y == e->p.y);
 837
 838         xrow_sort(status.xrow);
 839         add_points_to_positively_sloped_segments(&status, status.y);
 840         add_points_to_negatively_sloped_segments(&status, status.y);
 841         recalculate_windings(&status);
 842 #ifdef DEBUG
 843         check_status(&status);
 844         dict_destroy(status.intersecting_segs);
 845         dict_destroy(status.segs_with_point);
 846 #endif
 847     }
 848 #ifdef DEBUG
 849     dict_destroy(status.seen_crossings);
 850 #endif
 851     actlist_destroy(status.actlist);
 852     heap_destroy(queue);
 853     xrow_destroy(status.xrow);
 854
 855     gfxpoly_t*p = gfxpoly_new(poly->gridsize);
 856     p->edges = status.output;
 857
 858     add_horizontals(p, &windrule_evenodd); // output is always even/odd
 859     return p;
 860 }