lib/gfxpoly/poly.c

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