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