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