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