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