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