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             assert(e->p.x == s->a.x && e->p.y == s->a.y);
 891             actlist_insert(status->actlist, s->a, s->b, 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                     assert(e->p.x == s->a.x && e->p.y == s->a.y);
 994                     actlist_insert(actlist, s->a, s->b, s);
 995                     event_t e;
 996                     e.type = EVENT_END;
 997                     e.p = s->b;
 998                     e.s1 = s;
 999                     e.s2 = 0;
1000                     heap_put(queue, &e);
1001                     left = actlist_left(actlist, s);
1002
1003                     before = left?left->wind:windrule->start(1);
1004                     after = s->wind = windrule->add(before, s->fs, s->dir, s->polygon_nr);
1005                     break;
1006                 }
1007                 case EVENT_END: {
1008                     left = actlist_left(actlist, s);
1009                     actlist_delete(actlist, s);
1010
1011                     before = s->wind;
1012                     after = left?left->wind:windrule->start(1);
1013                     break;
1014                 }
1015                 default: assert(0);
1016             }
1017
1018             x = e->p.x;
1019             fill ^= 1;//(before.is_filled != after.is_filled);
1020 #ifdef DEBUG
1021             fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d before:%d after:%d\n",
1022                     y, e->type==EVENT_START?"start":"end",
1023                     s->nr,
1024                     left?left->nr:-1,
1025                     x,
1026                     before.is_filled, after.is_filled);
1027 #endif
1028
1029             if(e->type == EVENT_END)
1030                 segment_destroy(s);
1031
1032             free(e);
1033             e = heap_chopmax(queue);
1034         } while(e && y == e->p.y);
1035
1036         assert(!fill); // check that polygon is not bleeding
1037     }
1038     actlist_destroy(actlist);
1039     heap_destroy(queue);
1040 }
1041
1042 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule)
1043 {
1044     current_polygon = poly;
1045     heap_t* queue = heap_new(sizeof(event_t), compare_events);
1046
1047     gfxpoly_enqueue(poly->edges, queue, windrule->start(1), /*polygon nr*/0);
1048
1049     status_t status;
1050     memset(&status, 0, sizeof(status_t));
1051     status.num_polygons = 1;
1052     status.queue = queue;
1053     status.windrule = windrule;
1054     status.actlist = actlist_new();
1055 #ifdef CHECKS
1056     status.seen_crossings = dict_new2(&point_type);
1057 #endif
1058
1059     status.xrow = xrow_new();
1060
1061     event_t*e = heap_chopmax(queue);
1062     while(e) {
1063         status.y = e->p.y;
1064 #ifdef CHECKS
1065         status.intersecting_segs = dict_new2(&ptr_type);
1066         status.segs_with_point = dict_new2(&ptr_type);
1067 #endif
1068
1069 #ifdef DEBUG
1070         fprintf(stderr, "----------------------------------- %d\n", status.y);
1071         actlist_dump(status.actlist, status.y-1);
1072 #endif
1073 #ifdef CHECKS
1074         actlist_verify(status.actlist, status.y-1);
1075 #endif
1076         xrow_reset(status.xrow);
1077         do {
1078             xrow_add(status.xrow, e->p.x);
1079             event_apply(&status, e);
1080             free(e);
1081             e = heap_chopmax(queue);
1082         } while(e && status.y == e->p.y);
1083
1084         xrow_sort(status.xrow);
1085         segrange_t range;
1086         memset(&range, 0, sizeof(range));
1087 #ifdef DEBUG
1088         actlist_dump(status.actlist, status.y);
1089 #endif
1090         add_points_to_positively_sloped_segments(&status, status.y, &range);
1091         add_points_to_negatively_sloped_segments(&status, status.y, &range);
1092         add_points_to_ending_segments(&status, status.y);
1093
1094         recalculate_windings(&status, &range);
1095 #ifdef CHECKS
1096         check_status(&status);
1097         dict_destroy(status.intersecting_segs);
1098         dict_destroy(status.segs_with_point);
1099 #endif
1100     }
1101 #ifdef CHECKS
1102     dict_destroy(status.seen_crossings);
1103 #endif
1104     actlist_destroy(status.actlist);
1105     heap_destroy(queue);
1106     xrow_destroy(status.xrow);
1107
1108     gfxpoly_t*p = gfxpoly_new(poly->gridsize);
1109     p->edges = status.output;
1110
1111     add_horizontals(p, &windrule_evenodd); // output is always even/odd
1112     return p;
1113 }