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