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 "../MD5.h"
   7 #include "poly.h"
   8 #include "active.h"
   9 #include "xrow.h"
  10 #include "wind.h"
  11 #include "convert.h"
  12 #include "heap.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 = initialize_md5();
  23
  24     int s,t;
  25     gfxpolystroke_t*stroke = current_polygon->strokes;
  26     for(;stroke;stroke=stroke->next) {
  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 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 _event {
  79     eventtype_t type;
  80     point_t p;
  81     segment_t*s1;
  82     segment_t*s2;
  83 } event_t;
  84
  85 /* compare_events_simple differs from compare_events in that it schedules
  86    events from left to right regardless of type. It's only used in horizontal
  87    processing, in order to get an x-wise sorting of the current scanline */
  88 static inline int compare_events_simple(const void*_a,const void*_b)
  89 {
  90     event_t* a = (event_t*)_a;
  91     event_t* b = (event_t*)_b;
  92     int d = b->p.y - a->p.y;
  93     if(d) return d;
  94     d = b->p.x - a->p.x;
  95     if(d) return d;
  96     return 0;
  97 }
  98
  99 static inline int compare_events(const void*_a,const void*_b)
 100 {
 101     event_t* a = (event_t*)_a;
 102     event_t* b = (event_t*)_b;
 103     int d = b->p.y - a->p.y;
 104     if(d) return d;
 105     /* we need to schedule end after intersect (so that a segment about
 106        to end has a chance to tear up a few other segs first) and start
 107        events after end (in order not to confuse the intersection check, which
 108        assumes there's an actual y overlap between active segments, and
 109        because ending segments in the active list make it difficult to insert
 110        starting segments at the right position)).
 111        Horizontal lines come last, because the only purpose
 112        they have is to create snapping coordinates for the segments (still)
 113        existing in this scanline.
 114     */
 115     d = b->type - a->type;
 116     if(d) return d;
 117     return 0;
 118
 119     /* I don't see any reason why we would need to order by x- at least as long
 120        as we do horizontal lines in a seperate pass */
 121     //d = b->p.x - a->p.x;
 122     //return d;
 123 }
 124
 125 #define COMPARE_EVENTS(x,y) (compare_events(x,y)>0)
 126 #define COMPARE_EVENTS_SIMPLE(x,y) (compare_events_simple(x,y)>0)
 127 HEAP_DEFINE(queue,event_t,COMPARE_EVENTS);
 128 HEAP_DEFINE(hqueue,event_t,COMPARE_EVENTS_SIMPLE);
 129
 130 typedef struct _horizontal {
 131     int32_t y;
 132     int32_t x1, x2;
 133     edgestyle_t*fs;
 134     segment_dir_t dir;
 135     int polygon_nr;
 136     int xpos;
 137     int pos;
 138 } horizontal_t;
 139
 140 typedef struct _horizdata {
 141     horizontal_t*data;
 142     int num;
 143     int size;
 144 } horizdata_t;
 145
 146 typedef struct _status {
 147     int32_t y;
 148     double gridsize;
 149     actlist_t*actlist;
 150     queue_t queue;
 151     xrow_t*xrow;
 152     windrule_t*windrule;
 153     windcontext_t*context;
 154     segment_t*ending_segments;
 155
 156     horizdata_t horiz;
 157
 158     gfxpolystroke_t*strokes;
 159 #ifdef CHECKS
 160     dict_t*seen_crossings; //list of crossing we saw so far
 161     dict_t*intersecting_segs; //list of segments intersecting in this scanline
 162     dict_t*segs_with_point; //lists of segments that received a point in this scanline
 163 #endif
 164 } status_t;
 165
 166
 167 int gfxpoly_num_segments(gfxpoly_t*poly)
 168 {
 169     gfxpolystroke_t*stroke = poly->strokes;
 170     int count = 0;
 171     for(;stroke;stroke=stroke->next) {
 172         count++;
 173     }
 174     return count;
 175 }
 176 int gfxpoly_size(gfxpoly_t*poly)
 177 {
 178     int s,t;
 179     int edges = 0;
 180     gfxpolystroke_t*stroke = poly->strokes;
 181     for(;stroke;stroke=stroke->next) {
 182         edges += stroke->num_points-1;
 183     }
 184     return edges;
 185 }
 186
 187 char gfxpoly_check(gfxpoly_t*poly, char updown)
 188 {
 189     dict_t*d1 = dict_new2(&point_type);
 190     dict_t*d2 = dict_new2(&point_type);
 191     int s,t;
 192     gfxpolystroke_t*stroke = poly->strokes;
 193     for(;stroke;stroke=stroke->next) {
 194         /* In order to not confuse the fill/wind logic, existing segments must have
 195            a non-zero edge style */
 196         assert(stroke->fs);
 197
 198         /* put all the segments into dictionaries so that we can check
 199            that the endpoint multiplicity is two */
 200         for(s=0;s<stroke->num_points;s++) {
 201             point_t p = stroke->points[s];
 202             int num_xor = (s>=1 && s<stroke->num_points-1)?2:1; // mid points are two points (start+end)
 203             int num_circ = (s>=1 && s<stroke->num_points-1)?0:(s==0?1:-1);
 204             if(stroke->dir==DIR_UP)
 205                 num_circ=-num_circ;
 206
 207             if(!dict_contains(d1, &p)) {
 208                 dict_put(d1, &p, (void*)(ptroff_t)num_xor);
 209                 if(updown) {
 210                     assert(!dict_contains(d2, &p));
 211                     dict_put(d2, &p, (void*)(ptroff_t)num_circ);
 212                 }
 213             } else {
 214                 int count = (ptroff_t)dict_lookup(d1, &p);
 215                 dict_del(d1, &p);
 216                 count+=num_xor;
 217                 dict_put(d1, &p, (void*)(ptroff_t)count);
 218
 219                 if(updown) {
 220                     assert(dict_contains(d2, &p));
 221                     count = (ptroff_t)dict_lookup(d2, &p);
 222                     dict_del(d2, &p);
 223                     count+=num_circ;
 224                     dict_put(d2, &p, (void*)(ptroff_t)count);
 225                 }
 226             }
 227         }
 228     }
 229     DICT_ITERATE_ITEMS(d1, point_t*, p1, void*, c1) {
 230         int count = (ptroff_t)c1;
 231         if(count&1) {
 232             fprintf(stderr, "Error: Point (%.2f,%.2f) occurs %d times\n", p1->x * poly->gridsize, p1->y * poly->gridsize, count);
 233             dict_destroy(d1);
 234             dict_destroy(d2);
 235             return 0;
 236         }
 237     }
 238     if(updown) {
 239         DICT_ITERATE_ITEMS(d2, point_t*, p2, void*, c2) {
 240             int count = (ptroff_t)c2;
 241             assert(dict_contains(d1, p2));
 242             int ocount = (ptroff_t)dict_lookup(d1, p2);
 243             if(count!=0) {
 244                 if(count>0) fprintf(stderr, "Error: Point (%.2f,%.2f) has %d more incoming than outgoing segments (%d incoming, %d outgoing)\n", p2->x * poly->gridsize, p2->y * poly->gridsize, count, (ocount+count)/2, (ocount-count)/2);
 245                 if(count<0) fprintf(stderr, "Error: Point (%.2f,%.2f) has %d more outgoing than incoming segments (%d incoming, %d outgoing)\n", p2->x * poly->gridsize, p2->y * poly->gridsize, -count, (ocount+count)/2, (ocount-count)/2);
 246                 gfxpolystroke_t*stroke = poly->strokes;
 247                 for(;stroke;stroke=stroke->next) {
 248                     for(s=0;s<stroke->num_points-1;s++) {
 249                         point_t a = stroke->points[s];
 250                         point_t b = stroke->points[s+1];
 251                         if(a.x == p2->x && a.y == p2->y ||
 252                            b.x == p2->x && b.y == p2->y) {
 253                             fprintf(stderr, "%.2f,%.2f -> %.2f,%.2f\n",
 254                                     a.x * poly->gridsize,
 255                                     a.y * poly->gridsize,
 256                                     b.x * poly->gridsize,
 257                                     b.y * poly->gridsize);
 258                         }
 259                     }
 260                 }
 261                 dict_destroy(d2);
 262                 return 0;
 263             }
 264         }
 265     }
 266     dict_destroy(d1);
 267     dict_destroy(d2);
 268     return 1;
 269 }
 270
 271 void gfxpoly_dump(gfxpoly_t*poly)
 272 {
 273     int s,t;
 274     double g = poly->gridsize;
 275     fprintf(stderr, "polyon %p (gridsize: %.2f)\n", poly, poly->gridsize);
 276     gfxpolystroke_t*stroke = poly->strokes;
 277     for(;stroke;stroke=stroke->next) {
 278         fprintf(stderr, "%11p", stroke);
 279         if(stroke->dir==DIR_UP) {
 280             for(s=stroke->num_points-1;s>=1;s--) {
 281                 point_t a = stroke->points[s];
 282                 point_t b = stroke->points[s-1];
 283                 fprintf(stderr, "%s (%.2f,%.2f) -> (%.2f,%.2f)%s%s\n", s!=stroke->num_points-1?"           ":"", a.x*g, a.y*g, b.x*g, b.y*g,
 284                                                             s==1?"]":"", a.y==b.y?"H":"");
 285             }
 286         } else {
 287             for(s=0;s<stroke->num_points-1;s++) {
 288                 point_t a = stroke->points[s];
 289                 point_t b = stroke->points[s+1];
 290                 fprintf(stderr, "%s (%.2f,%.2f) -> (%.2f,%.2f)%s%s\n", s?"           ":"", a.x*g, a.y*g, b.x*g, b.y*g,
 291                                                             s==stroke->num_points-2?"]":"", a.y==b.y?"H":"");
 292             }
 293         }
 294     }
 295 }
 296
 297 void gfxpoly_save(gfxpoly_t*poly, const char*filename)
 298 {
 299     FILE*fi = fopen(filename, "wb");
 300     fprintf(fi, "%% gridsize %f\n", poly->gridsize);
 301     fprintf(fi, "%% begin\n");
 302     int s,t;
 303     gfxpolystroke_t*stroke = poly->strokes;
 304     for(;stroke;stroke=stroke->next) {
 305             fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
 306         point_t p = stroke->points[0];
 307         fprintf(fi, "%d %d moveto\n", p.x, p.y);
 308         for(s=1;s<stroke->num_points;s++) {
 309             p = stroke->points[s];
 310             fprintf(fi, "%d %d lineto\n", p.x, p.y);
 311         }
 312         fprintf(fi, "stroke\n");
 313     }
 314     fprintf(fi, "showpage\n");
 315     fclose(fi);
 316 }
 317
 318 void gfxpoly_save_arrows(gfxpoly_t*poly, const char*filename)
 319 {
 320     FILE*fi = fopen(filename, "wb");
 321     fprintf(fi, "%% gridsize %f\n", poly->gridsize);
 322     fprintf(fi, "%% begin\n");
 323     int t;
 324     double l = 5.0 / poly->gridsize;
 325     double g = poly->gridsize;
 326     gfxpolystroke_t*stroke = poly->strokes;
 327     for(;stroke;stroke=stroke->next) {
 328         fprintf(fi, "0 setgray\n");
 329
 330         int s = stroke->dir==DIR_UP?stroke->num_points-1:0;
 331         int end = stroke->dir==DIR_UP?-1:stroke->num_points;
 332         int dir = stroke->dir==DIR_UP?-1:1;
 333
 334         point_t p = stroke->points[s];
 335         s+=dir;
 336         point_t o = p;
 337         fprintf(fi, "%f %f moveto\n", p.x * g, p.y * g);
 338         for(;s!=end;s+=dir) {
 339             p = stroke->points[s];
 340             int lx = p.x - o.x;
 341             int ly = p.y - o.y;
 342             double d = sqrt(lx*lx+ly*ly);
 343             if(!d) d=1;
 344             else   d = l / d;
 345             double d2 = d*1.5;
 346             fprintf(fi, "%f %f lineto\n", (p.x - lx*d2) * g, (p.y - ly*d2) * g);
 347             fprintf(fi, "%f %f lineto\n", (p.x - lx*d2 + (ly*d))*g,
 348                                           (p.y - ly*d2 - (lx*d))*g);
 349             fprintf(fi, "%f %f lineto\n", p.x * g, p.y * g);
 350             fprintf(fi, "%f %f lineto\n", (p.x - lx*d2 - (ly*d))*g,
 351                                           (p.y - ly*d2 + (lx*d))*g);
 352             fprintf(fi, "%f %f lineto\n", (p.x - lx*d2) * g, (p.y - ly*d2) * g);
 353             fprintf(fi, "%f %f moveto\n", p.x * g, p.y * g);
 354             o = p;
 355         }
 356         fprintf(fi, "stroke\n");
 357     }
 358     fprintf(fi, "showpage\n");
 359     fclose(fi);
 360 }
 361
 362 inline static event_t* event_new()
 363 {
 364     event_t*e = rfx_calloc(sizeof(event_t));
 365     return e;
 366 }
 367 inline static void event_free(event_t*e)
 368 {
 369     free(e);
 370 }
 371
 372 static void event_dump(status_t*status, event_t*e)
 373 {
 374     if(e->type == EVENT_HORIZONTAL) {
 375         fprintf(stderr, "Horizontal [%d] (%.2f,%.2f) -> (%.2f,%.2f)\n", (int)e->s1->nr,
 376                 e->s1->a.x * status->gridsize, e->s1->a.y * status->gridsize, e->s1->b.x * status->gridsize, e->s1->b.y * status->gridsize);
 377     } else if(e->type == EVENT_START) {
 378         fprintf(stderr, "event: segment [%d] starts at (%.2f,%.2f)\n", (int)e->s1->nr,
 379                 e->p.x * status->gridsize, e->p.y * status->gridsize);
 380     } else if(e->type == EVENT_END) {
 381         fprintf(stderr, "event: segment [%d] ends at (%.2f,%.2f)\n", (int)e->s1->nr,
 382                 e->p.x * status->gridsize, e->p.y * status->gridsize);
 383     } else if(e->type == EVENT_CROSS) {
 384         fprintf(stderr, "event: segment [%d] and [%d] intersect at (%.2f,%.2f)\n", (int)e->s1->nr, (int)e->s2->nr,
 385                 e->p.x * status->gridsize, e->p.y * status->gridsize);
 386     } else {
 387         assert(0);
 388     }
 389 }
 390
 391 static inline int32_t max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
 392 static inline int32_t min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
 393
 394 static void segment_dump(segment_t*s)
 395 {
 396     fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", (int)s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
 397     fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f fs=%p\n", s->delta.x, s->delta.y, s->k,
 398             (double)s->delta.x / s->delta.y, s->fs);
 399 }
 400
 401 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)
 402 {
 403     static int segment_count=0;
 404     s->nr = segment_count++;
 405     s->dir = dir;
 406     if(y1!=y2) {
 407         assert(y1<y2);
 408     } else {
 409         /* We need to make sure horizontal segments always go from left to right.
 410            "up/down" for horizontal segments is handled by "rotating"
 411            them 90° counterclockwise in screen coordinates (tilt your head to
 412            the right). In other words, the "normal" direction (what's positive dy for
 413            vertical segments) is positive dx for horizontal segments ("down" is right).
 414          */
 415         if(x1>x2) {
 416             s->dir = DIR_INVERT(s->dir);
 417             int32_t x = x1;x1=x2;x2=x;
 418             int32_t y = y1;y1=y2;y2=y;
 419         }
 420 #ifdef DEBUG
 421         fprintf(stderr, "Scheduling horizontal segment [%d] (%.2f,%.2f) -> (%.2f,%.2f) %s\n",
 422                 segment_count,
 423                 x1 * 0.05, y1 * 0.05, x2 * 0.05, y2 * 0.05, s->dir==DIR_UP?"up":"down");
 424 #endif
 425     }
 426     s->a.x = x1;
 427     s->a.y = y1;
 428     s->b.x = x2;
 429     s->b.y = y2;
 430     s->k = (double)x1*y2-(double)x2*y1;
 431     s->left = s->right = 0;
 432     s->delta.x = x2-x1;
 433     s->delta.y = y2-y1;
 434     s->minx = min32(x1,x2);
 435     s->maxx = max32(x1,x2);
 436
 437     s->pos = s->a;
 438     s->polygon_nr = polygon_nr;
 439
 440 #ifdef CHECKS
 441     /* notice: on some systems (with some compilers), for the line
 442        (1073741823,-1073741824)->(1073741823,1073741823)
 443        we get LINE_EQ(s->a, s) == 1.
 444        That's why we now clamp to 26 bit.
 445     */
 446     assert(LINE_EQ(s->a, s) == 0);
 447     assert(LINE_EQ(s->b, s) == 0);
 448
 449     /* check that all signs are in order:
 450        a        a
 451        |\      /|
 452        | \    / |
 453      minx-b  b--maxx
 454      < 0        > 0
 455     */
 456     point_t p = s->b;
 457     p.x = min32(s->a.x, s->b.x);
 458     assert(LINE_EQ(p, s) <= 0);
 459     p.x = max32(s->a.x, s->b.x);
 460     assert(LINE_EQ(p, s) >= 0);
 461 #endif
 462
 463 #ifndef DONT_REMEMBER_CROSSINGS
 464     dict_init2(&s->scheduled_crossings, &ptr_type, 0);
 465 #endif
 466 }
 467
 468 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
 469 {
 470     segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
 471     segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
 472     return s;
 473 }
 474
 475 static void segment_clear(segment_t*s)
 476 {
 477 #ifndef DONT_REMEMBER_CROSSINGS
 478     dict_clear(&s->scheduled_crossings);
 479 #endif
 480 }
 481 static void segment_destroy(segment_t*s)
 482 {
 483     segment_clear(s);
 484     free(s);
 485 }
 486
 487 static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*stroke, int polygon_nr, int pos, double gridsize)
 488 {
 489     if(!stroke)
 490         return;
 491     segment_t*s = 0;
 492     /* we need to queue multiple segments at once because we need to process start events
 493        before horizontal events */
 494     while(pos < stroke->num_points-1) {
 495         assert(stroke->points[pos].y <= stroke->points[pos+1].y);
 496         s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
 497         s->fs = stroke->fs;
 498         pos++;
 499         s->stroke = 0;
 500         s->stroke_pos = 0;
 501 #ifdef DEBUG
 502         /*if(l->tmp)
 503             s->nr = l->tmp;*/
 504         fprintf(stderr, "[%d] (%.2f,%.2f) -> (%.2f,%.2f) %s (stroke %p, %d more to come)\n",
 505                 s->nr, s->a.x * gridsize, s->a.y * gridsize,
 506                 s->b.x * gridsize, s->b.y * gridsize,
 507                 s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos);
 508 #endif
 509         event_t* e = event_new();
 510         e->type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
 511         e->p = s->a;
 512         e->s1 = s;
 513         e->s2 = 0;
 514
 515         if(queue) queue_put(queue, e);
 516         else hqueue_put(hqueue, e);
 517
 518         if(e->type != EVENT_HORIZONTAL) {
 519             break;
 520         }
 521     }
 522     if(s) {
 523         s->stroke = stroke;
 524         s->stroke_pos = pos;
 525     }
 526 }
 527
 528 static void gfxpoly_enqueue(gfxpoly_t*p, queue_t*queue, hqueue_t*hqueue, int polygon_nr)
 529 {
 530     int t;
 531     gfxpolystroke_t*stroke = p->strokes;
 532     for(;stroke;stroke=stroke->next) {
 533         assert(stroke->num_points > 1);
 534
 535 #ifdef CHECKS
 536         int s;
 537         for(s=0;s<stroke->num_points-1;s++) {
 538             assert(stroke->points[s].y <= stroke->points[s+1].y);
 539         }
 540 #endif
 541         advance_stroke(queue, hqueue, stroke, polygon_nr, 0, p->gridsize);
 542     }
 543 }
 544
 545 static void schedule_endpoint(status_t*status, segment_t*s)
 546 {
 547     // schedule end point of segment
 548     assert(s->b.y > status->y);
 549     event_t*e = event_new();
 550     e->type = EVENT_END;
 551     e->p = s->b;
 552     e->s1 = s;
 553     e->s2 = 0;
 554     queue_put(&status->queue, e);
 555 }
 556
 557 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
 558 {
 559     /* the code that's required (and the checks you can perform) before
 560        it can be said with 100% certainty that we indeed have a valid crossing
 561        amazes me every time. -mk */
 562 #ifdef CHECKS
 563     assert(s1!=s2);
 564     assert(s1->right == s2);
 565     assert(s2->left == s1);
 566     int32_t miny1 = min32(s1->a.y,s1->b.y);
 567     int32_t maxy1 = max32(s1->a.y,s1->b.y);
 568     int32_t miny2 = min32(s2->a.y,s2->b.y);
 569     int32_t maxy2 = max32(s2->a.y,s2->b.y);
 570     int32_t minx1 = min32(s1->a.x,s1->b.x);
 571     int32_t minx2 = min32(s2->a.x,s2->b.x);
 572     int32_t maxx1 = max32(s1->a.x,s1->b.x);
 573     int32_t maxx2 = max32(s2->a.x,s2->b.x);
 574     /* check that precomputation is sane */
 575     assert(minx1 == s1->minx && minx2 == s2->minx);
 576     assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
 577     /* both segments are active, so this can't happen */
 578     assert(!(maxy1 <= miny2 || maxy2 <= miny1));
 579     /* we know that right now, s2 is to the right of s1, so there's
 580        no way the complete bounding box of s1 is to the right of s1 */
 581     assert(!(s1->minx > s2->maxx));
 582     assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
 583 #endif
 584
 585     if(s1->maxx <= s2->minx) {
 586 #ifdef DEBUG
 587             fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
 588 #endif
 589         /* bounding boxes don't intersect */
 590         return;
 591     }
 592
 593 #ifndef DONT_REMEMBER_CROSSINGS
 594     if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
 595         /* FIXME: this whole segment hashing thing is really slow */
 596 #ifdef DEBUG
 597         fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
 598 //      DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
 599 //          fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
 600 //      }
 601 #endif
 602         return; // we already know about this one
 603     }
 604 #endif
 605
 606     double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
 607     if(!det) {
 608         if(s1->k == s2->k) {
 609             // lines are exactly on top of each other (ignored)
 610 #ifdef DEBUG
 611             fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
 612 #endif
 613             return;
 614         } else {
 615 #ifdef DEBUG
 616             fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
 617 #endif
 618             /* lines are parallel */
 619             return;
 620         }
 621     }
 622
 623     double asign2 = LINE_EQ(s1->a, s2);
 624     if(asign2==0) {
 625         // segment1 touches segment2 in a single point (ignored)
 626 #ifdef DEBUG
 627         fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
 628 #endif
 629         return;
 630     }
 631     double bsign2 = LINE_EQ(s1->b, s2);
 632     if(bsign2==0) {
 633         // segment1 touches segment2 in a single point (ignored)
 634 #ifdef DEBUG
 635         fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
 636 #endif
 637         return;
 638     }
 639
 640     if(asign2<0 && bsign2<0) {
 641         // segment1 is completely to the left of segment2
 642 #ifdef DEBUG
 643             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);
 644 #endif
 645         return;
 646     }
 647     if(asign2>0 && bsign2>0)  {
 648         // segment1 is completely to the right of segment2
 649 #ifndef DONT_REMEMBER_CROSSINGS
 650         assert(0);
 651 #endif
 652 #ifdef DEBUG
 653             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);
 654 #endif
 655         return;
 656     }
 657
 658     double asign1 = LINE_EQ(s2->a, s1);
 659     if(asign1==0) {
 660         // segment2 touches segment1 in a single point (ignored)
 661 #ifdef DEBUG
 662         fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
 663 #endif
 664         return;
 665     }
 666     double bsign1 = LINE_EQ(s2->b, s1);
 667     if(asign2==0) {
 668         // segment2 touches segment1 in a single point (ignored)
 669 #ifdef DEBUG
 670         fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
 671 #endif
 672         return;
 673     }
 674
 675     if(asign1<0 && bsign1<0) {
 676         // segment2 is completely to the left of segment1
 677 #ifndef DONT_REMEMBER_CROSSINGS
 678         assert(0);
 679 #endif
 680 #ifdef DEBUG
 681             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);
 682 #endif
 683         return;
 684     }
 685     if(asign1>0 && bsign1>0)  {
 686         // segment2 is completely to the right of segment1
 687 #ifdef DEBUG
 688             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);
 689 #endif
 690         return;
 691     }
 692
 693 #ifdef DONT_REMEMBER_CROSSINGS
 694     /* s2 crosses s1 from *left* to *right*. This is a crossing we already processed-
 695        there's not way s2 would be to the left of s1 otherwise */
 696     if(asign1<0 && bsign1>0) return;
 697     if(asign2>0 && bsign2<0) return;
 698 #endif
 699
 700     assert(!(asign1<0 && bsign1>0));
 701     assert(!(asign2>0 && bsign2<0));
 702
 703     /* TODO: should we precompute these? */
 704     double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
 705     double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
 706
 707     point_t p;
 708     p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
 709     p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
 710
 711     assert(p.y >= status->y);
 712 #ifdef CHECKS
 713     assert(p.x >= s1->minx && p.x <= s1->maxx);
 714     assert(p.x >= s2->minx && p.x <= s2->maxx);
 715
 716     point_t pair;
 717     pair.x = s1->nr;
 718     pair.y = s2->nr;
 719 #ifndef DONT_REMEMBER_CROSSINGS
 720     assert(!dict_contains(status->seen_crossings, &pair));
 721     dict_put(status->seen_crossings, &pair, 0);
 722 #endif
 723 #endif
 724 #ifdef DEBUG
 725     fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
 726 #endif
 727
 728 #ifndef DONT_REMEMBER_CROSSINGS
 729     /* we insert into each other's intersection history because these segments might switch
 730        places and we still want to look them up quickly after they did */
 731     dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
 732     dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
 733 #endif
 734
 735     event_t* e = event_new();
 736     e->type = EVENT_CROSS;
 737     e->p = p;
 738     e->s1 = s1;
 739     e->s2 = s2;
 740     queue_put(&status->queue, e);
 741     return;
 742 }
 743
 744 static void exchange_two(status_t*status, event_t*e)
 745 {
 746     //exchange two segments in list
 747     segment_t*s1 = e->s1;
 748     segment_t*s2 = e->s2;
 749 #ifdef CHECKS
 750     if(!dict_contains(status->intersecting_segs, s1))
 751         dict_put(status->intersecting_segs, s1, 0);
 752     if(!dict_contains(status->intersecting_segs, s2))
 753         dict_put(status->intersecting_segs, s2, 0);
 754 #endif
 755     assert(s2->left == s1);
 756     assert(s1->right == s2);
 757     actlist_swap(status->actlist, s1, s2);
 758     assert(s2->right  == s1);
 759     assert(s1->left == s2);
 760     segment_t*left = s2->left;
 761     segment_t*right = s1->right;
 762     if(left)
 763         schedule_crossing(status, left, s2);
 764     if(right)
 765         schedule_crossing(status, s1, right);
 766 }
 767
 768 typedef struct _box {
 769     point_t left1, left2, right1, right2;
 770 } box_t;
 771 static inline box_t box_new(int32_t x, int32_t y)
 772 {
 773     box_t box;
 774     box.right1.x = box.right2.x = x;
 775     box.left1.x = box.left2.x = x-1;
 776     box.left1.y = box.right1.y = y-1;
 777     box.left2.y = box.right2.y = y;
 778     return box;
 779 }
 780
 781 static void store_horizontal(status_t*status, point_t p1, point_t p2, edgestyle_t*fs, segment_dir_t dir, int polygon_nr);
 782
 783 static void append_stroke(status_t*status, point_t a, point_t b, segment_dir_t dir, edgestyle_t*fs)
 784 {
 785     gfxpolystroke_t*stroke = status->strokes;
 786     /* find a stoke to attach this segment to. It has to have an endpoint
 787        matching our start point, and a matching edgestyle */
 788     while(stroke) {
 789         point_t p = stroke->points[stroke->num_points-1];
 790         if(p.x == a.x && p.y == a.y && stroke->fs == fs && stroke->dir == dir)
 791             break;
 792         stroke = stroke->next;
 793     }
 794     if(!stroke) {
 795         stroke = rfx_calloc(sizeof(gfxpolystroke_t));
 796         stroke->dir = dir;
 797         stroke->fs = fs;
 798         stroke->next = status->strokes;
 799         status->strokes = stroke;
 800         stroke->points_size = 2;
 801         stroke->points = rfx_calloc(sizeof(point_t)*stroke->points_size);
 802         stroke->points[0] = a;
 803         stroke->num_points = 1;
 804     } else if(stroke->num_points == stroke->points_size) {
 805         assert(stroke->fs);
 806         stroke->points_size *= 2;
 807         stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size);
 808     }
 809     stroke->points[stroke->num_points++] = b;
 810 }
 811
 812 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
 813 {
 814     assert(s->pos.x != p.x || s->pos.y != p.y);
 815
 816 #ifdef CHECKS
 817     if(!dict_contains(status->segs_with_point, s))
 818         dict_put(status->segs_with_point, s, 0);
 819     assert(s->fs_out_ok);
 820 #endif
 821
 822     if(s->pos.y != p.y) {
 823         /* non horizontal line- copy to output */
 824         if(s->fs_out) {
 825             segment_dir_t dir = s->wind.is_filled?DIR_DOWN:DIR_UP;
 826 #ifdef DEBUG
 827             fprintf(stderr, "[%d] receives next point (%.2f,%.2f)->(%.2f,%.2f) (drawing (%s))\n", s->nr,
 828                     s->pos.x * status->gridsize, s->pos.y * status->gridsize,
 829                     p.x * status->gridsize, p.y * status->gridsize,
 830                     dir==DIR_UP?"up":"down"
 831                     );
 832 #endif
 833             assert(s->pos.y != p.y);
 834             append_stroke(status, s->pos, p, dir, s->fs_out);
 835         } else {
 836 #ifdef DEBUG
 837             fprintf(stderr, "[%d] receives next point (%.2f,%.2f) (omitting)\n", s->nr,
 838                     p.x * status->gridsize,
 839                     p.y * status->gridsize);
 840 #endif
 841         }
 842     } else {
 843         /* horizontal line. we need to look at this more closely at the end of this
 844            scanline */
 845         store_horizontal(status, s->pos, p, s->fs, s->dir, s->polygon_nr);
 846     }
 847
 848     s->pos = p;
 849 }
 850
 851 typedef struct _segrange {
 852     double xmin;
 853     segment_t*segmin;
 854     double xmax;
 855     segment_t*segmax;
 856 } segrange_t;
 857
 858 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
 859 {
 860 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
 861     segment_t*min = range->segmin;
 862     segment_t*max = range->segmax;
 863
 864     /* we need this because if two segments intersect exactly on
 865        the scanline, segrange_test_segment_{min,max} can't tell which
 866        one is smaller/larger */
 867     if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
 868         min = min->left;
 869     }
 870     if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
 871         max = max->right;
 872     }
 873     range->segmin = min;
 874     range->segmax = max;
 875 }
 876 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
 877 {
 878     if(!seg) return;
 879     /* we need to calculate the xpos anew (and can't use start coordinate or
 880        intersection coordinate), because we need the xpos exactly at the end of
 881        this scanline.
 882      */
 883     double x = XPOS(seg, y);
 884     if(!range->segmin || x<range->xmin) {
 885         range->segmin = seg;
 886         range->xmin = x;
 887     }
 888 }
 889 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
 890 {
 891     if(!seg) return;
 892     double x = XPOS(seg, y);
 893     if(!range->segmax || x>range->xmax) {
 894         range->segmax = seg;
 895         range->xmax = x;
 896     }
 897 }
 898
 899 /*
 900    SLOPE_POSITIVE:
 901       \+     \ +
 902 ------ I      \I
 903       -I\----  I
 904        I \   --I\---
 905        I  \    I \  -------
 906        +   \   +  \
 907 */
 908 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
 909 {
 910     segment_t*first=0, *last = 0;
 911     int t;
 912     for(t=0;t<status->xrow->num;t++) {
 913         box_t box = box_new(status->xrow->x[t], y);
 914         segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
 915
 916         seg = actlist_right(status->actlist, seg);
 917         while(seg) {
 918             if(seg->a.y == y) {
 919                 // this segment started in this scanline, ignore it
 920                 seg->changed = 1;last = seg;if(!first) {first=seg;}
 921             } else if(seg->delta.x <= 0) {
 922                 // ignore segment w/ negative slope
 923             } else {
 924                 last = seg;if(!first) {first=seg;}
 925                 double d1 = LINE_EQ(box.right1, seg);
 926                 double d2 = LINE_EQ(box.right2, seg);
 927                 if(d1>0 || d2>=0) {
 928                     seg->changed = 1;
 929                     insert_point_into_segment(status, seg, box.right2);
 930                 } else {
 931                     /* we unfortunately can't break here- the active list is sorted according
 932                        to the *bottom* of the scanline. hence pretty much everything that's still
 933                        coming might reach into our box */
 934                     //break;
 935                 }
 936             }
 937             seg = seg->right;
 938         }
 939     }
 940     segrange_test_segment_min(range, first, y);
 941     segrange_test_segment_max(range, last, y);
 942 }
 943 /* SLOPE_NEGATIVE:
 944    |   +   /|  +  /    /
 945    |   I  / |  I /    /
 946    |   I /  |  I/    /
 947    |   I/   |  I    /
 948    |   I    | /I   /
 949    |  /+    |/ +  /
 950 */
 951 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
 952 {
 953     segment_t*first=0, *last = 0;
 954     int t;
 955     for(t=status->xrow->num-1;t>=0;t--) {
 956         box_t box = box_new(status->xrow->x[t], y);
 957         segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
 958
 959         while(seg) {
 960             if(seg->a.y == y) {
 961                 // this segment started in this scanline, ignore it
 962                 seg->changed = 1;last = seg;if(!first) {first=seg;}
 963             } else if(seg->delta.x > 0) {
 964                 // ignore segment w/ positive slope
 965             } else {
 966                 last = seg;if(!first) {first=seg;}
 967                 double d1 = LINE_EQ(box.left1, seg);
 968                 double d2 = LINE_EQ(box.left2, seg);
 969                 if(d1<0 || d2<0) {
 970                     seg->changed = 1;
 971                     insert_point_into_segment(status, seg, box.right2);
 972                 } else {
 973                     //break;
 974                 }
 975             }
 976             seg = seg->left;
 977         }
 978     }
 979     segrange_test_segment_min(range, last, y);
 980     segrange_test_segment_max(range, first, y);
 981 }
 982
 983 /* segments ending in the current scanline need xrow treatment like everything else.
 984    (consider an intersection taking place just above a nearly horizontal segment
 985    ending on the current scanline- the intersection would snap down *below* the
 986    ending segment if we don't add the intersection point to the latter right away)
 987    we need to treat ending segments seperately, however. we have to delete them from
 988    the active list right away to make room for intersect operations (which might
 989    still be in the current scanline- consider two 45° polygons and a vertical polygon
 990    intersecting on an integer coordinate). but once they're no longer in the active list,
 991    we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
 992    them to the active list just for point snapping would be overkill.
 993    (One other option to consider, however, would be to create a new active list only
 994     for ending segments)
 995 */
 996 static void add_points_to_ending_segments(status_t*status, int32_t y)
 997 {
 998     segment_t*seg = status->ending_segments;
 999     while(seg) {
1000         segment_t*next = seg->right;seg->right=0;
1001
1002         assert(seg->b.y == status->y);
1003
1004         if(status->xrow->num == 1) {
1005             // shortcut
1006             assert(seg->b.x == status->xrow->x[0]);
1007             point_t p = {status->xrow->x[0], y};
1008             insert_point_into_segment(status, seg, p);
1009         } else {
1010             int t;
1011             int start=0,end=status->xrow->num,dir=1;
1012             if(seg->delta.x < 0) {
1013                 start = status->xrow->num-1;
1014                 end = dir = -1;
1015             }
1016 #ifdef CHECKS
1017             char ok = 0;
1018 #endif
1019             for(t=start;t!=end;t+=dir) {
1020                 box_t box = box_new(status->xrow->x[t], y);
1021                 double d0 = LINE_EQ(box.left1, seg);
1022                 double d1 = LINE_EQ(box.left2, seg);
1023                 double d2 = LINE_EQ(box.right1, seg);
1024                 double d3 = LINE_EQ(box.right2, seg);
1025                 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
1026                      d0<=0 && d1<=0 && d2<=0 && d3<0)) {
1027                     insert_point_into_segment(status, seg, box.right2);
1028                     //break;
1029 #ifdef CHECKS
1030                     ok = 1;
1031 #endif
1032                 }
1033             }
1034
1035 #ifdef CHECKS
1036             /* we *need* to find a point to insert. the segment's own end point
1037                is in that list, for Pete's sake. */
1038             assert(ok);
1039 #endif
1040         }
1041         // now that this is done, too, we can also finally free this segment
1042         segment_destroy(seg);
1043         seg = next;
1044     }
1045     status->ending_segments = 0;
1046 }
1047
1048 static void recalculate_windings(status_t*status, segrange_t*range)
1049 {
1050 #ifdef DEBUG
1051     fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
1052 #endif
1053     segrange_adjust_endpoints(range, status->y);
1054
1055     segment_t*s = range->segmin;
1056     segment_t*end = range->segmax;
1057     segment_t*last = 0;
1058
1059 #ifdef DEBUG
1060     s = actlist_leftmost(status->actlist);
1061     while(s) {
1062         fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
1063             s == range->segmin?"S":(
1064             s == range->segmax?"E":""));
1065         s = s->right;
1066     }
1067     fprintf(stderr, "\n");
1068     s = range->segmin;
1069 #endif
1070 #ifdef CHECKS
1071     /* test sanity: verify that we don't have changed segments
1072        outside of the given range */
1073     s = actlist_leftmost(status->actlist);
1074     while(s && s!=range->segmin) {
1075         assert(!s->changed);
1076         s = s->right;
1077     }
1078     s = actlist_rightmost(status->actlist);
1079     while(s && s!=range->segmax) {
1080         assert(!s->changed);
1081         s = s->left;
1082     }
1083     /* in check mode, go through the whole interval so we can test
1084        that all polygons where the edgestyle changed also have seg->changed=1 */
1085     s = actlist_leftmost(status->actlist);
1086     end = 0;
1087 #endif
1088
1089     if(end)
1090         end = end->right;
1091     while(s!=end) {
1092 #ifndef CHECKS
1093         if(s->changed)
1094 #endif
1095         {
1096             segment_t* left = actlist_left(status->actlist, s);
1097             windstate_t wind = left?left->wind:status->windrule->start(status->context);
1098             s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
1099             edgestyle_t*fs_old = s->fs_out;
1100             s->fs_out = status->windrule->diff(&wind, &s->wind);
1101
1102 #ifdef DEBUG
1103             fprintf(stderr, "[%d] dir=%s wind=%d wind.filled=%s fs_old/new=%s/%s %s\n", s->nr, s->dir==DIR_UP?"up":"down", s->wind.wind_nr, s->wind.is_filled?"fill":"nofill",
1104                     fs_old?"draw":"omit", s->fs_out?"draw":"omit",
1105                     fs_old!=s->fs_out?"CHANGED":"");
1106 #endif
1107             assert(!(!s->changed && fs_old!=s->fs_out));
1108             s->changed = 0;
1109
1110 #ifdef CHECKS
1111             s->fs_out_ok = 1;
1112 #endif
1113         }
1114         s = s->right;
1115     }
1116 }
1117
1118 /* we need to handle horizontal lines in order to add points to segments
1119    we otherwise would miss during the windrule re-evaluation */
1120 static void intersect_with_horizontal(status_t*status, segment_t*h)
1121 {
1122     segment_t* left = actlist_find(status->actlist, h->a, h->a);
1123     segment_t* right = actlist_find(status->actlist, h->b, h->b);
1124
1125     /* h->a.x is not strictly necessary, as it's also done by the event */
1126     xrow_add(status->xrow, h->a.x);
1127     xrow_add(status->xrow, h->b.x);
1128
1129     if(!right) {
1130         assert(!left);
1131         return;
1132     }
1133
1134     left = actlist_right(status->actlist, left); //first seg to the right of h->a
1135     right = right->right; //first seg to the right of h->b
1136     segment_t* s = left;
1137
1138     point_t o = h->a;
1139     while(s!=right) {
1140         assert(s);
1141         int32_t x = XPOS_INT(s, status->y);
1142         point_t p = {x, status->y};
1143 #ifdef DEBUG
1144         fprintf(stderr, "...intersecting with [%d] (%.2f,%.2f) -> (%.2f,%.2f) at (%.2f,%.2f)\n",
1145                 s->nr,
1146                 s->a.x * status->gridsize, s->a.y * status->gridsize,
1147                 s->b.x * status->gridsize, s->b.y * status->gridsize,
1148                 x * status->gridsize, status->y * status->gridsize
1149                 );
1150 #endif
1151         assert(x >= h->a.x);
1152         assert(x <= h->b.x);
1153         assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
1154         assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
1155         xrow_add(status->xrow, x);
1156
1157         o = p;
1158         s = s->right;
1159     }
1160 }
1161
1162 /* while, for a scanline, we need both starting as well as ending segments in order
1163    to *reconstruct* horizontal lines, we only need one or the other to *process*
1164    horizontal lines from the input data.
1165
1166    So horizontal lines are processed twice: first they create hotpixels by intersecting
1167    all segments on the scanline (EVENT_HORIZTONAL). Secondly, they are processed for
1168    their actual content. The second also happens for all segments that received more than
1169    one point in this scanline.
1170 */
1171 void horiz_reset(horizdata_t*horiz)
1172 {
1173     horiz->num = 0;
1174 }
1175
1176 void horiz_destroy(horizdata_t*horiz)
1177 {
1178     if(horiz->data) rfx_free(horiz->data);
1179     horiz->data = 0;
1180 }
1181
1182 static windstate_t get_horizontal_first_windstate(status_t*status, int x1, int x2)
1183 {
1184     point_t p1 = {x1,status->y};
1185     point_t p2 = {x2,status->y};
1186     segment_t*left = actlist_find(status->actlist, p1, p2);
1187
1188     segment_t*a = actlist_right(status->actlist, left);
1189     while(a) {
1190         if(a->pos.y == status->y) {
1191             /* we need to iterate through all segments that received a point in this
1192                scanline, as actlist_find above will miss (positively sloped) segments
1193                that are to the right of (x1,y) only as long as we don't take the
1194                hotpixel re-routing into account
1195                TODO: this is inefficient, we should probably be iterating through the
1196                hotpixels on this scanline.
1197              */
1198             if(a->pos.x == x1)
1199                 left = a;
1200             if(a->pos.x > x1)
1201                 break;
1202         }
1203         a = a->right;
1204     }
1205
1206     assert(!left || left->fs_out_ok);
1207 #ifdef DEBUG
1208     fprintf(stderr, "  fragment %.2f..%.2f\n",
1209             x1 * status->gridsize,
1210             x2 * status->gridsize);
1211     if(left) {
1212         fprintf(stderr, "    segment [%d] (%.2f,%.2f -> %.2f,%2f, at %.2f,%.2f) is to the left\n",
1213                 SEGNR(left),
1214                 left->a.x * status->gridsize,
1215                 left->a.y * status->gridsize,
1216                 left->b.x * status->gridsize,
1217                 left->b.y * status->gridsize,
1218                 left->pos.x * status->gridsize,
1219                 left->pos.y * status->gridsize
1220                 );
1221         /* this segment might be a distance away from the left point
1222            of the horizontal line if the horizontal line belongs to a stroke
1223            with segments that just ended (so this horizontal line appears to
1224            be "floating in space" from our current point of view)
1225         assert(left->pos.y == h->y && left->pos.x == h->x1);
1226         */
1227     }
1228 #endif
1229     return left?left->wind:status->windrule->start(status->context);
1230 }
1231
1232 static windstate_t process_horizontal_fragment(status_t*status, horizontal_t*h, int x1, int x2, windstate_t below)
1233 {
1234     windstate_t above = status->windrule->add(status->context, below, h->fs, h->dir, h->polygon_nr);
1235     edgestyle_t*fs = status->windrule->diff(&above, &below);
1236
1237     segment_dir_t dir = above.is_filled?DIR_DOWN:DIR_UP;
1238     point_t p1 = {x1,h->y};
1239     point_t p2 = {x2,h->y};
1240
1241     if(fs) {
1242         //append_stroke(status, p1, p2, DIR_INVERT(h->dir), fs);
1243         append_stroke(status, p1, p2, dir, fs);
1244     }
1245 #ifdef DEBUG
1246     fprintf(stderr, "    ...%s (below: (wind_nr=%d, filled=%d), above: (wind_nr=%d, filled=%d) %s %d-%d\n",
1247             fs?"storing":"ignoring",
1248             below.wind_nr, below.is_filled,
1249             above.wind_nr, above.is_filled,
1250             dir==DIR_UP?"up":"down", x1, x2);
1251 #endif
1252     return above;
1253 }
1254
1255 typedef enum {hevent_hotpixel,hevent_end,hevent_start} horizontal_event_type_t;
1256 typedef struct _hevent {
1257     int32_t x;
1258     horizontal_t*h;
1259     horizontal_event_type_t type;
1260 } hevent_t;
1261
1262 typedef struct _hevents {
1263     hevent_t*events;
1264     int num;
1265 } hevents_t;
1266
1267 static int compare_hevents(const void *_e1, const void *_e2)
1268 {
1269     hevent_t*e1 = (hevent_t*)_e1;
1270     hevent_t*e2 = (hevent_t*)_e2;
1271     int diff = e1->x - e2->x;
1272     if(diff) return diff;
1273     return e1->type - e2->type; //schedule hotpixel before hend
1274 }
1275
1276 static hevents_t hevents_fill(status_t*status)
1277 {
1278     horizdata_t*horiz = &status->horiz;
1279     xrow_t*xrow = status->xrow;
1280
1281     hevents_t e;
1282     e.events = malloc(sizeof(hevent_t)*(horiz->num*2 + xrow->num));
1283     e.num = 0;
1284
1285     int t;
1286     for(t=0;t<horiz->num;t++) {
1287         assert(horiz->data[t].x1 != horiz->data[t].x2);
1288         e.events[e.num].x = horiz->data[t].x1;
1289         e.events[e.num].h = &horiz->data[t];
1290         e.events[e.num].type = hevent_start;
1291         e.num++;
1292         e.events[e.num].x = horiz->data[t].x2;
1293         e.events[e.num].h = &horiz->data[t];
1294         e.events[e.num].type = hevent_end;
1295         e.num++;
1296     }
1297     for(t=0;t<xrow->num;t++) {
1298         e.events[e.num].x = status->xrow->x[t];
1299         e.events[e.num].h = 0;
1300         e.events[e.num].type = hevent_hotpixel;
1301         e.num++;
1302     }
1303     qsort(e.events, e.num, sizeof(hevent_t), compare_hevents);
1304     return e;
1305
1306 }
1307
1308 static void process_horizontals(status_t*status)
1309 {
1310     horizdata_t*horiz = &status->horiz;
1311
1312     if(!horiz->num)
1313         return;
1314
1315     hevents_t events = hevents_fill(status);
1316     int num_open = 0;
1317     horizontal_t**open = malloc(sizeof(horizontal_t*)*horiz->num);
1318
1319     int s,t;
1320     for(t=0;t<events.num;t++) {
1321         hevent_t*e = &events.events[t];
1322         switch(e->type) {
1323             case hevent_start:
1324                 e->h->pos = num_open;
1325                 open[num_open++] = e->h;
1326 #ifdef DEBUG
1327                 fprintf(stderr, "horizontal (y=%.2f): %.2f -> %.2f dir=%s fs=%p\n",
1328                         e->h->y * status->gridsize,
1329                         e->h->x1 * status->gridsize,
1330                         e->h->x2 * status->gridsize,
1331                         e->h->dir==DIR_UP?"up":"down", e->h->fs);
1332 #endif
1333                 assert(e->h->y == status->y);
1334                 assert(xrow_contains(status->xrow, e->h->x1));
1335                 assert(xrow_contains(status->xrow, e->h->x2));
1336             break;
1337             case hevent_end:
1338                 num_open--;
1339                 if(num_open) {
1340                     open[num_open]->pos = e->h->pos;
1341                     open[e->h->pos] = open[num_open];
1342                 }
1343             break;
1344             case hevent_hotpixel:
1345                 {
1346                     windstate_t below;
1347                     for(s=0;s<num_open;s++) {
1348                         int x1 = open[s]->xpos;
1349                         int x2 = e->x;
1350                         assert(status->y == open[s]->y);
1351                         if(!s)
1352                             below = get_horizontal_first_windstate(status, x1, x2);
1353                         open[s]->xpos = e->x;
1354                         assert(x1 < x2);
1355                         below = process_horizontal_fragment(status, open[s], x1, x2, below);
1356                     }
1357                 }
1358             break;
1359         }
1360     }
1361     free(open);
1362     free(events.events);
1363 }
1364
1365 static void store_horizontal(status_t*status, point_t p1, point_t p2, edgestyle_t*fs, segment_dir_t dir, int polygon_nr)
1366 {
1367     assert(p1.y == p2.y);
1368     assert(p1.x != p2.x); // TODO: can this happen?
1369
1370     if(p1.x > p2.x) {
1371         dir = DIR_INVERT(dir);
1372         point_t p_1 = p1;
1373         point_t p_2 = p2;
1374         p1 = p_2;
1375         p2 = p_1;
1376     }
1377
1378     /* TODO: convert this into a linked list */
1379     if(status->horiz.size == status->horiz.num) {
1380         if(!status->horiz.size)
1381             status->horiz.size = 16;
1382         status->horiz.size *= 2;
1383         status->horiz.data = rfx_realloc(status->horiz.data, sizeof(status->horiz.data[0])*status->horiz.size);
1384     }
1385     horizontal_t*h = &status->horiz.data[status->horiz.num++];
1386     h->y = p1.y;
1387     h->xpos = p1.x;
1388     h->x1 = p1.x;
1389     h->x2 = p2.x;
1390     h->fs = fs;
1391     h->dir = dir;
1392     h->polygon_nr = polygon_nr;
1393 }
1394
1395
1396 static void event_apply(status_t*status, event_t*e)
1397 {
1398 #ifdef DEBUG
1399     event_dump(status, e);
1400 #endif
1401
1402     switch(e->type) {
1403         case EVENT_HORIZONTAL: {
1404             segment_t*s = e->s1;
1405             intersect_with_horizontal(status, s);
1406             store_horizontal(status, s->a, s->b, s->fs, s->dir, s->polygon_nr);
1407             advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos, status->gridsize);
1408             segment_destroy(s);e->s1=0;
1409             break;
1410         }
1411         case EVENT_END: {
1412             //delete segment from list
1413             segment_t*s = e->s1;
1414 #ifdef CHECKS
1415             dict_del(status->intersecting_segs, s);
1416             dict_del(status->segs_with_point, s);
1417             assert(!dict_contains(status->intersecting_segs, s));
1418             assert(!dict_contains(status->segs_with_point, s));
1419 #endif
1420             segment_t*left = s->left;
1421             segment_t*right = s->right;
1422             actlist_delete(status->actlist, s);
1423             if(left && right)
1424                 schedule_crossing(status, left, right);
1425
1426             /* schedule segment for xrow handling */
1427             s->left = 0; s->right = status->ending_segments;
1428             status->ending_segments = s;
1429             advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos, status->gridsize);
1430             break;
1431         }
1432         case EVENT_START: {
1433             //insert segment into list
1434             segment_t*s = e->s1;
1435             assert(e->p.x == s->a.x && e->p.y == s->a.y);
1436             actlist_insert(status->actlist, s->a, s->b, s);
1437             segment_t*left = s->left;
1438             segment_t*right = s->right;
1439             if(left)
1440                 schedule_crossing(status, left, s);
1441             if(right)
1442                 schedule_crossing(status, s, right);
1443             schedule_endpoint(status, s);
1444             break;
1445         }
1446         case EVENT_CROSS: {
1447             // exchange two segments
1448             if(e->s1->right == e->s2) {
1449                 assert(e->s2->left == e->s1);
1450                 exchange_two(status, e);
1451             } else {
1452                 assert(e->s2->left != e->s1);
1453 #ifdef DEBUG
1454                 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1455 #endif
1456 #ifndef DONT_REMEMBER_CROSSINGS
1457                 /* ignore this crossing for now (there are some line segments in between).
1458                    it'll get rescheduled as soon as the "obstacles" are gone */
1459                 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1460                 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1461                 assert(del1 && del2);
1462 #endif
1463 #ifdef CHECKS
1464                 point_t pair;
1465                 pair.x = e->s1->nr;
1466                 pair.y = e->s2->nr;
1467 #ifndef DONT_REMEMBER_CROSSINGS
1468                 assert(dict_contains(status->seen_crossings, &pair));
1469                 dict_del(status->seen_crossings, &pair);
1470 #endif
1471 #endif
1472             }
1473         }
1474     }
1475 }
1476
1477 #ifdef CHECKS
1478 static void check_status(status_t*status)
1479 {
1480     DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1481         if((s->pos.x != s->b.x ||
1482             s->pos.y != s->b.y) &&
1483            !dict_contains(status->segs_with_point, s)) {
1484             fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1485                     SEGNR(s),
1486                     s->delta.x<0?"-":"+",
1487                     status->y);
1488             assert(0);
1489         }
1490     }
1491 }
1492 #endif
1493
1494 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly1, gfxpoly_t*poly2, windrule_t*windrule, windcontext_t*context)
1495 {
1496     current_polygon = poly1;
1497
1498     status_t status;
1499     memset(&status, 0, sizeof(status_t));
1500     status.gridsize = poly1->gridsize;
1501
1502     queue_init(&status.queue);
1503     gfxpoly_enqueue(poly1, &status.queue, 0, /*polygon nr*/0);
1504     if(poly2) {
1505         assert(poly1->gridsize == poly2->gridsize);
1506         gfxpoly_enqueue(poly2, &status.queue, 0, /*polygon nr*/1);
1507     }
1508
1509     status.windrule = windrule;
1510     status.context = context;
1511     status.actlist = actlist_new();
1512
1513 #ifdef CHECKS
1514     status.seen_crossings = dict_new2(&point_type);
1515     int32_t lasty=-0x80000000;
1516 #endif
1517
1518     status.xrow = xrow_new();
1519
1520     event_t*e = queue_get(&status.queue);
1521     while(e) {
1522         assert(e->s1->fs);
1523         status.y = e->p.y;
1524 #ifdef CHECKS
1525         assert(status.y>=lasty);
1526         lasty = status.y;
1527         status.intersecting_segs = dict_new2(&ptr_type);
1528         status.segs_with_point = dict_new2(&ptr_type);
1529 #endif
1530
1531 #ifdef DEBUG
1532         fprintf(stderr, "----------------------------------- %.2f\n", status.y * status.gridsize);
1533         actlist_dump(status.actlist, status.y-1, status.gridsize);
1534 #endif
1535 #ifdef CHECKS
1536         actlist_verify(status.actlist, status.y-1);
1537 #endif
1538         xrow_reset(status.xrow);
1539         horiz_reset(&status.horiz);
1540
1541         do {
1542             xrow_add(status.xrow, e->p.x);
1543             event_apply(&status, e);
1544             event_free(e);
1545             e = queue_get(&status.queue);
1546         } while(e && status.y == e->p.y);
1547
1548         xrow_sort(status.xrow);
1549         segrange_t range;
1550         memset(&range, 0, sizeof(range));
1551 #ifdef DEBUG
1552         actlist_dump(status.actlist, status.y, status.gridsize);
1553         xrow_dump(status.xrow, status.gridsize);
1554 #endif
1555         add_points_to_positively_sloped_segments(&status, status.y, &range);
1556         add_points_to_negatively_sloped_segments(&status, status.y, &range);
1557         add_points_to_ending_segments(&status, status.y);
1558
1559         recalculate_windings(&status, &range);
1560
1561         actlist_verify(status.actlist, status.y);
1562         process_horizontals(&status);
1563 #ifdef CHECKS
1564         check_status(&status);
1565         dict_destroy(status.intersecting_segs);
1566         dict_destroy(status.segs_with_point);
1567 #endif
1568     }
1569 #ifdef CHECKS
1570     dict_destroy(status.seen_crossings);
1571 #endif
1572     actlist_destroy(status.actlist);
1573     queue_destroy(&status.queue);
1574     horiz_destroy(&status.horiz);
1575     xrow_destroy(status.xrow);
1576
1577     gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t));
1578     p->gridsize = poly1->gridsize;
1579     p->strokes = status.strokes;
1580
1581 #ifdef CHECKS
1582     /* we only add segments with non-empty edgestyles to strokes in
1583        recalculate_windings, but better safe than sorry */
1584     gfxpolystroke_t*stroke = p->strokes;
1585     while(stroke) {
1586         assert(stroke->fs);
1587         stroke = stroke->next;
1588     }
1589 #endif
1590     return p;
1591 }
1592
1593 static windcontext_t twopolygons = {2};
1594 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*p1, gfxpoly_t*p2)
1595 {
1596     return gfxpoly_process(p1, p2, &windrule_intersect, &twopolygons);
1597 }
1598 gfxpoly_t* gfxpoly_union(gfxpoly_t*p1, gfxpoly_t*p2)
1599 {
1600     return gfxpoly_process(p1, p2, &windrule_union, &twopolygons);
1601 }