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        TODO: might be faster to use XPOS_COMPARE here (see also _max)
 600      */
 601     double x = XPOS(seg, y);
 602     if(!range->segmin || x<range->xmin) {
 603         range->segmin = seg;
 604         range->xmin = x;
 605     }
 606 }
 607 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
 608 {
 609     if(!seg) return;
 610     double x = XPOS(seg, y);
 611     if(!range->segmax || x>range->xmax) {
 612         range->segmax = seg;
 613         range->xmax = x;
 614     }
 615 }
 616
 617 /*
 618    SLOPE_POSITIVE:
 619       \+     \ +
 620 ------ I      \I
 621       -I\----  I
 622        I \   --I\---
 623        I  \    I \  -------
 624        +   \   +  \
 625 */
 626 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
 627 {
 628     segment_t*first=0, *last = 0;
 629     int t;
 630     for(t=0;t<status->xrow->num;t++) {
 631         box_t box = box_new(status->xrow->x[t], y);
 632         segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
 633
 634         seg = actlist_right(status->actlist, seg);
 635         while(seg) {
 636             if(seg->a.y == y) {
 637                 // this segment started in this scanline, ignore it
 638                 seg->changed = 1;last = seg;if(!first) {first=seg;}
 639             } else if(seg->delta.x <= 0) {
 640                 // ignore segment w/ negative slope
 641             } else {
 642                 last = seg;if(!first) {first=seg;}
 643                 double d1 = LINE_EQ(box.right1, seg);
 644                 double d2 = LINE_EQ(box.right2, seg);
 645                 if(d1>0 || d2>=0) {
 646                     seg->changed = 1;
 647                     insert_point_into_segment(status, seg, box.right2);
 648                 } else {
 649                     /* we unfortunately can't break here- the active list is sorted according
 650                        to the *bottom* of the scanline. hence pretty much everything that's still
 651                        coming might reach into our box */
 652                     //break;
 653                 }
 654             }
 655             seg = actlist_right(status->actlist, seg);
 656         }
 657     }
 658     segrange_test_segment_min(range, first, y);
 659     segrange_test_segment_max(range, last, y);
 660 }
 661 /* SLOPE_NEGATIVE:
 662    |   +   /|  +  /    /
 663    |   I  / |  I /    /
 664    |   I /  |  I/    /
 665    |   I/   |  I    /
 666    |   I    | /I   /
 667    |  /+    |/ +  /
 668 */
 669 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
 670 {
 671     segment_t*first=0, *last = 0;
 672     int t;
 673     for(t=status->xrow->num-1;t>=0;t--) {
 674         box_t box = box_new(status->xrow->x[t], y);
 675         segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
 676
 677         while(seg) {
 678             if(seg->a.y == y) {
 679                 // this segment started in this scanline, ignore it
 680                 seg->changed = 1;last = seg;if(!first) {first=seg;}
 681             } else if(seg->delta.x > 0) {
 682                 // ignore segment w/ positive slope
 683             } else {
 684                 last = seg;if(!first) {first=seg;}
 685                 double d1 = LINE_EQ(box.left1, seg);
 686                 double d2 = LINE_EQ(box.left2, seg);
 687                 if(d1<0 || d2<0) {
 688                     seg->changed = 1;
 689                     insert_point_into_segment(status, seg, box.right2);
 690                 } else {
 691                     //break;
 692                 }
 693             }
 694             seg = actlist_left(status->actlist, seg);
 695         }
 696     }
 697     segrange_test_segment_min(range, last, y);
 698     segrange_test_segment_max(range, first, y);
 699 }
 700
 701 /* segments ending in the current scanline need xrow treatment like everything else.
 702    (consider an intersection taking place just above a nearly horizontal segment
 703    ending on the current scanline- the intersection would snap down *below* the
 704    ending segment if we don't add the intersection point to the latter right away)
 705    we need to treat ending segments seperately, however. we have to delete them from
 706    the active list right away to make room for intersect operations (which might
 707    still be in the current scanline- consider two 45° polygons and a vertical polygon
 708    intersecting on an integer coordinate). but once they're no longer in the active list,
 709    we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
 710    them to the active list just for point snapping would be overkill.
 711    (One other option to consider, however, would be to create a new active list only
 712     for ending segments)
 713 */
 714 static void add_points_to_ending_segments(status_t*status, int32_t y)
 715 {
 716     segment_t*seg = status->ending_segments;
 717     while(seg) {
 718         segment_t*next = seg->right;seg->right=0;
 719
 720         assert(seg->b.y == status->y);
 721
 722         if(status->xrow->num == 1) {
 723             // shortcut
 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 = actlist_right(status->actlist, end);
 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 = actlist_left(status->actlist, s);
 892             segment_t*right = actlist_right(status->actlist, s);
 893             actlist_delete(status->actlist, s);
 894             if(left && right)
 895                 schedule_crossing(status, left, right);
 896
 897             s->left = 0; s->right = status->ending_segments;
 898             status->ending_segments = s;
 899             break;
 900         }
 901         case EVENT_START: {
 902             //insert segment into list
 903 #ifdef DEBUG
 904             event_dump(e);
 905 #endif
 906             segment_t*s = e->s1;
 907             assert(e->p.x == s->a.x && e->p.y == s->a.y);
 908             actlist_insert(status->actlist, s->a, s->b, s);
 909             segment_t*left = actlist_left(status->actlist, s);
 910             segment_t*right = actlist_right(status->actlist, s);
 911             if(left)
 912                 schedule_crossing(status, left, s);
 913             if(right)
 914                 schedule_crossing(status, s, right);
 915             schedule_endpoint(status, e->s1);
 916             break;
 917         }
 918         case EVENT_CROSS: {
 919             // exchange two segments
 920 #ifdef DEBUG
 921             event_dump(e);
 922 #endif
 923             if(actlist_right(status->actlist, e->s1) == e->s2 &&
 924                actlist_left(status->actlist, e->s2) == e->s1) {
 925                 exchange_two(status, e);
 926             } else {
 927 #ifdef DEBUG
 928                 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
 929 #endif
 930                 /* ignore this crossing for now (there are some line segments in between).
 931                    it'll get rescheduled as soon as the "obstacles" are gone */
 932                 char del1 = dict_del(&e->s1->scheduled_crossings, e->s2);
 933                 char del2 = dict_del(&e->s2->scheduled_crossings, e->s1);
 934                 assert(del1 && del2);
 935 #ifdef CHECKS
 936                 point_t pair;
 937                 pair.x = e->s1->nr;
 938                 pair.y = e->s2->nr;
 939                 assert(dict_contains(status->seen_crossings, &pair));
 940                 dict_del(status->seen_crossings, &pair);
 941 #endif
 942             }
 943         }
 944     }
 945 }
 946
 947 #ifdef CHECKS
 948 static void check_status(status_t*status)
 949 {
 950     DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
 951         if((s->pos.x != s->b.x ||
 952             s->pos.y != s->b.y) &&
 953            !dict_contains(status->segs_with_point, s)) {
 954             fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
 955                     s->nr,
 956                     s->delta.x<0?"-":"+",
 957                     status->y);
 958             assert(0);
 959         }
 960     }
 961 }
 962 #endif
 963
 964 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
 965 {
 966     /*
 967           |..|        |...........|                 |           |
 968           |..|        |...........|                 |           |
 969           |..+        +        +..|                 +--+     +--+
 970           |...........|        |..|                    |     |
 971           |...........|        |..|                    |     |
 972      */
 973
 974 #ifdef DEBUG
 975     fprintf(stderr, "========================================================================\n");
 976 #endif
 977     heap_t* queue = heap_new(sizeof(event_t), compare_events_simple);
 978     gfxpoly_enqueue(poly->edges, queue, 0);
 979
 980     actlist_t* actlist = actlist_new();
 981
 982     event_t*e = heap_chopmax(queue);
 983     while(e) {
 984         int32_t y = e->p.y;
 985         int32_t x = 0;
 986         char fill = 0;
 987 #ifdef DEBUG
 988         fprintf(stderr, "----------------------------------- %d\n", y);
 989         actlist_dump(actlist, y-1);
 990 #endif
 991 #ifdef CHECKS
 992         actlist_verify(actlist, y-1);
 993 #endif
 994         do {
 995             if(fill && x != e->p.x) {
 996 #ifdef DEBUG
 997                 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
 998 #endif
 999                 assert(x<e->p.x);
1000                 edge_t*l= malloc(sizeof(edge_t));
1001                 l->a.y = l->b.y = y;
1002                 /* TODO: strictly speaking we need to draw from low x to high x so that left/right fillstyles add up
1003                          (because the horizontal line's fill style controls the area *below* the line)
1004                  */
1005                 l->a.x = x;
1006                 l->b.x = e->p.x;
1007                 l->next = poly->edges;
1008                 poly->edges = l;
1009 #ifdef CHECKS
1010                 /* the output should always be intersection free polygons, so check this horizontal
1011                    line isn't hacking through any segments in the active list */
1012                 segment_t* start = actlist_find(actlist, l->a, l->a);
1013                 segment_t* s = actlist_find(actlist, l->b, l->b);
1014                 while(s!=start) {
1015                     assert(s->a.y == y || s->b.y == y);
1016                     s = s->left;
1017                 }
1018 #endif
1019             }
1020             segment_t*left = 0;
1021             segment_t*s = e->s1;
1022
1023             windstate_t before,after;
1024             switch(e->type) {
1025                 case EVENT_START: {
1026                     assert(e->p.x == s->a.x && e->p.y == s->a.y);
1027                     actlist_insert(actlist, s->a, s->b, s);
1028                     event_t e;
1029                     e.type = EVENT_END;
1030                     e.p = s->b;
1031                     e.s1 = s;
1032                     e.s2 = 0;
1033                     heap_put(queue, &e);
1034                     left = actlist_left(actlist, s);
1035
1036                     before = left?left->wind:windrule->start(context);
1037                     after = s->wind = windrule->add(context, before, s->fs, s->dir, s->polygon_nr);
1038                     break;
1039                 }
1040                 case EVENT_END: {
1041                     left = actlist_left(actlist, s);
1042                     actlist_delete(actlist, s);
1043
1044                     before = s->wind;
1045                     after = left?left->wind:windrule->start(context);
1046                     break;
1047                 }
1048                 default: assert(0);
1049             }
1050
1051             x = e->p.x;
1052             fill ^= 1;//(before.is_filled != after.is_filled);
1053 #ifdef DEBUG
1054             fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d before:%d after:%d\n",
1055                     y, e->type==EVENT_START?"start":"end",
1056                     s->nr,
1057                     left?left->nr:-1,
1058                     x,
1059                     before.is_filled, after.is_filled);
1060 #endif
1061
1062             if(e->type == EVENT_END)
1063                 segment_destroy(s);
1064
1065             free(e);
1066             e = heap_chopmax(queue);
1067         } while(e && y == e->p.y);
1068
1069         assert(!fill); // check that polygon is not bleeding
1070     }
1071     actlist_destroy(actlist);
1072     heap_destroy(queue);
1073 }
1074
1075 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1076 {
1077     current_polygon = poly;
1078     heap_t* queue = heap_new(sizeof(event_t), compare_events);
1079
1080     gfxpoly_enqueue(poly->edges, queue, /*polygon nr*/0);
1081
1082     status_t status;
1083     memset(&status, 0, sizeof(status_t));
1084     status.queue = queue;
1085     status.windrule = windrule;
1086     status.context = context;
1087     status.actlist = actlist_new();
1088 #ifdef CHECKS
1089     status.seen_crossings = dict_new2(&point_type);
1090 #endif
1091
1092     status.xrow = xrow_new();
1093
1094     event_t*e = heap_chopmax(queue);
1095     while(e) {
1096         status.y = e->p.y;
1097 #ifdef CHECKS
1098         status.intersecting_segs = dict_new2(&ptr_type);
1099         status.segs_with_point = dict_new2(&ptr_type);
1100 #endif
1101
1102 #ifdef DEBUG
1103         fprintf(stderr, "----------------------------------- %d\n", status.y);
1104         actlist_dump(status.actlist, status.y-1);
1105 #endif
1106 #ifdef CHECKS
1107         actlist_verify(status.actlist, status.y-1);
1108 #endif
1109         xrow_reset(status.xrow);
1110         do {
1111             xrow_add(status.xrow, e->p.x);
1112             event_apply(&status, e);
1113             free(e);
1114             e = heap_chopmax(queue);
1115         } while(e && status.y == e->p.y);
1116
1117         xrow_sort(status.xrow);
1118         segrange_t range;
1119         memset(&range, 0, sizeof(range));
1120 #ifdef DEBUG
1121         actlist_dump(status.actlist, status.y);
1122 #endif
1123         add_points_to_positively_sloped_segments(&status, status.y, &range);
1124         add_points_to_negatively_sloped_segments(&status, status.y, &range);
1125         add_points_to_ending_segments(&status, status.y);
1126
1127         recalculate_windings(&status, &range);
1128 #ifdef CHECKS
1129         check_status(&status);
1130         dict_destroy(status.intersecting_segs);
1131         dict_destroy(status.segs_with_point);
1132 #endif
1133     }
1134 #ifdef CHECKS
1135     dict_destroy(status.seen_crossings);
1136 #endif
1137     actlist_destroy(status.actlist);
1138     heap_destroy(queue);
1139     xrow_destroy(status.xrow);
1140
1141     gfxpoly_t*p = gfxpoly_new(poly->gridsize);
1142     p->edges = status.output;
1143
1144     add_horizontals(p, &windrule_evenodd, context); // output is always even/odd
1145     return p;
1146 }