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