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