lib/gfxpoly/poly.c

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