lib/gfxpoly/poly.c

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