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