+ segrange_test_segment_min(range, last, y);
+ segrange_test_segment_max(range, first, y);
+}
+
+/* segments ending in the current scanline need xrow treatment like everything else.
+ (consider an intersection taking place just above a nearly horizontal segment
+ ending on the current scanline- the intersection would snap down *below* the
+ ending segment if we don't add the intersection point to the latter right away)
+ we need to treat ending segments seperately, however. we have to delete them from
+ the active list right away to make room for intersect operations (which might
+ still be in the current scanline- consider two 45° polygons and a vertical polygon
+ intersecting on an integer coordinate). but once they're no longer in the active list,
+ we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
+ them to the active list just for point snapping would be overkill.
+ (One other option to consider, however, would be to create a new active list only
+ for ending segments)
+*/
+static void add_points_to_ending_segments(status_t*status, int32_t y)
+{
+ segment_t*seg = status->ending_segments;
+ while(seg) {
+ segment_t*next = seg->right;seg->right=0;
+
+ assert(seg->b.y == status->y);
+
+ if(status->xrow->num == 1) {
+ // shortcut
+ assert(seg->b.x == status->xrow->x[0]);
+ point_t p = {status->xrow->x[0], y};
+ insert_point_into_segment(status, seg, p);
+ } else {
+ int t;
+ int start=0,end=status->xrow->num,dir=1;
+ if(seg->delta.x < 0) {
+ start = status->xrow->num-1;
+ end = dir = -1;
+ }
+#ifdef CHECKS
+ char ok = 0;
+#endif
+ for(t=start;t!=end;t+=dir) {
+ box_t box = box_new(status->xrow->x[t], y);
+ double d0 = LINE_EQ(box.left1, seg);
+ double d1 = LINE_EQ(box.left2, seg);
+ double d2 = LINE_EQ(box.right1, seg);
+ double d3 = LINE_EQ(box.right2, seg);
+ if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
+ d0<=0 && d1<=0 && d2<=0 && d3<0)) {
+ insert_point_into_segment(status, seg, box.right2);
+ //break;
+#ifdef CHECKS
+ ok = 1;
+#endif
+ }
+ }
+
+#ifdef CHECKS
+ /* we *need* to find a point to insert. the segment's own end point
+ is in that list, for Pete's sake. */
+ assert(ok);
+#endif
+ }
+ // now that this is done, too, we can also finally free this segment
+ segment_destroy(seg);
+ seg = next;
+ }
+ status->ending_segments = 0;
+}
+
+static void recalculate_windings(status_t*status, segrange_t*range)
+{
+#ifdef DEBUG
+ fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
+#endif
+ segrange_adjust_endpoints(range, status->y);
+
+ segment_t*s = range->segmin;
+ segment_t*end = range->segmax;
+ segment_t*last = 0;
+
+#ifdef DEBUG
+ s = actlist_leftmost(status->actlist);
+ while(s) {
+ fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
+ s == range->segmin?"S":(
+ s == range->segmax?"E":""));
+ s = s->right;
+ }
+ fprintf(stderr, "\n");
+ s = range->segmin;
+#endif
+#ifdef CHECKS
+ /* test sanity: verify that we don't have changed segments
+ outside of the given range */
+ s = actlist_leftmost(status->actlist);
+ while(s && s!=range->segmin) {
+ assert(!s->changed);
+ s = s->right;
+ }
+ s = actlist_rightmost(status->actlist);
+ while(s && s!=range->segmax) {
+ assert(!s->changed);
+ s = s->left;
+ }
+ /* in check mode, go through the whole interval so we can test
+ that all polygons where the edgestyle changed also have seg->changed=1 */
+ s = actlist_leftmost(status->actlist);
+ end = 0;
+#endif
+
+ if(end)
+ end = end->right;
+ while(s!=end) {
+#ifndef CHECKS
+ if(s->changed)
+#endif
+ {
+ segment_t* left = actlist_left(status->actlist, s);
+ windstate_t wind = left?left->wind:status->windrule->start(status->context);
+ s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
+ edgestyle_t*fs_old = s->fs_out;
+ s->fs_out = status->windrule->diff(&wind, &s->wind);
+
+#ifdef DEBUG
+ fprintf(stderr, "[%d] dir=%s wind=%d wind.filled=%s fs_old/new=%s/%s %s\n", s->nr, s->dir==DIR_UP?"up":"down", s->wind.wind_nr, s->wind.is_filled?"fill":"nofill",
+ fs_old?"draw":"omit", s->fs_out?"draw":"omit",
+ fs_old!=s->fs_out?"CHANGED":"");
+#endif
+ assert(!(!s->changed && fs_old!=s->fs_out));
+ s->changed = 0;
+
+#ifdef CHECKS
+ s->fs_out_ok = 1;
+#endif
+ }
+ s = s->right;
+ }
+}
+
+/* we need to handle horizontal lines in order to add points to segments
+ we otherwise would miss during the windrule re-evaluation */
+static void intersect_with_horizontal(status_t*status, segment_t*h)
+{
+ segment_t* left = actlist_find(status->actlist, h->a, h->a);
+ segment_t* right = actlist_find(status->actlist, h->b, h->b);
+
+ /* h->a.x is not strictly necessary, as it's also done by the event */
+ xrow_add(status->xrow, h->a.x);
+ xrow_add(status->xrow, h->b.x);
+
+ if(!right) {
+ assert(!left);
+ return;
+ }
+
+ left = actlist_right(status->actlist, left); //first seg to the right of h->a
+ right = right->right; //first seg to the right of h->b
+ segment_t* s = left;
+
+ point_t o = h->a;
+ while(s!=right) {
+ assert(s);
+ int32_t x = XPOS_INT(s, status->y);
+ point_t p = {x, status->y};
+#ifdef DEBUG
+ fprintf(stderr, "...intersecting with [%d] (%.2f,%.2f) -> (%.2f,%.2f) at (%.2f,%.2f)\n",
+ s->nr,
+ s->a.x * status->gridsize, s->a.y * status->gridsize,
+ s->b.x * status->gridsize, s->b.y * status->gridsize,
+ x * status->gridsize, status->y * status->gridsize
+ );
+#endif
+ assert(x >= h->a.x);
+ assert(x <= h->b.x);
+ assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
+ assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
+ xrow_add(status->xrow, x);
+
+ o = p;
+ s = s->right;
+ }
+}
+
+/* while, for a scanline, we need both starting as well as ending segments in order
+ to *reconstruct* horizontal lines, we only need one or the other to *process*
+ horizontal lines from the input data.
+
+ So horizontal lines are processed twice: first they create hotpixels by intersecting
+ all segments on the scanline (EVENT_HORIZTONAL). Secondly, they are processed for
+ their actual content. The second also happens for all segments that received more than
+ one point in this scanline.
+*/
+void horiz_reset(horizdata_t*horiz)
+{
+ horiz->num = 0;
+}
+
+void horiz_destroy(horizdata_t*horiz)
+{
+ if(horiz->data) rfx_free(horiz->data);
+ horiz->data = 0;
+}
+
+static windstate_t get_horizontal_first_windstate(status_t*status, int x1, int x2)
+{
+ point_t p1 = {x1,status->y};
+ point_t p2 = {x2,status->y};
+ segment_t*left = actlist_find(status->actlist, p1, p2);
+
+ segment_t*a = actlist_right(status->actlist, left);
+ while(a) {
+ if(a->pos.y == status->y) {
+ /* we need to iterate through all segments that received a point in this
+ scanline, as actlist_find above will miss (positively sloped) segments
+ that are to the right of (x1,y) only as long as we don't take the
+ hotpixel re-routing into account
+ TODO: this is inefficient, we should probably be iterating through the
+ hotpixels on this scanline.
+ */
+ if(a->pos.x == x1)
+ left = a;
+ if(a->pos.x > x1)
+ break;
+ }
+ a = a->right;
+ }
+
+ assert(!left || left->fs_out_ok);
+#ifdef DEBUG
+ fprintf(stderr, " fragment %.2f..%.2f\n",
+ x1 * status->gridsize,
+ x2 * status->gridsize);
+ if(left) {
+ fprintf(stderr, " segment [%d] (%.2f,%.2f -> %.2f,%2f, at %.2f,%.2f) is to the left\n",
+ SEGNR(left),
+ left->a.x * status->gridsize,
+ left->a.y * status->gridsize,
+ left->b.x * status->gridsize,
+ left->b.y * status->gridsize,
+ left->pos.x * status->gridsize,
+ left->pos.y * status->gridsize
+ );
+ /* this segment might be a distance away from the left point
+ of the horizontal line if the horizontal line belongs to a stroke
+ with segments that just ended (so this horizontal line appears to
+ be "floating in space" from our current point of view)
+ assert(left->pos.y == h->y && left->pos.x == h->x1);
+ */
+ }
+#endif
+ return left?left->wind:status->windrule->start(status->context);
+}
+
+static windstate_t process_horizontal_fragment(status_t*status, horizontal_t*h, int x1, int x2, windstate_t below)
+{
+ windstate_t above = status->windrule->add(status->context, below, h->fs, h->dir, h->polygon_nr);
+ edgestyle_t*fs = status->windrule->diff(&above, &below);
+
+ segment_dir_t dir = above.is_filled?DIR_DOWN:DIR_UP;
+ point_t p1 = {x1,h->y};
+ point_t p2 = {x2,h->y};
+
+ if(fs) {
+ //append_stroke(status, p1, p2, DIR_INVERT(h->dir), fs);
+ append_stroke(status, p1, p2, dir, fs);
+ }
+#ifdef DEBUG
+ fprintf(stderr, " ...%s (below: (wind_nr=%d, filled=%d), above: (wind_nr=%d, filled=%d) %s %d-%d\n",
+ fs?"storing":"ignoring",
+ below.wind_nr, below.is_filled,
+ above.wind_nr, above.is_filled,
+ dir==DIR_UP?"up":"down", x1, x2);
+#endif
+ return above;
+}
+
+typedef enum {hevent_hotpixel,hevent_end,hevent_start} horizontal_event_type_t;
+typedef struct _hevent {
+ int32_t x;
+ horizontal_t*h;
+ horizontal_event_type_t type;
+} hevent_t;
+
+typedef struct _hevents {
+ hevent_t*events;
+ int num;
+} hevents_t;
+
+static int compare_hevents(const void *_e1, const void *_e2)
+{
+ hevent_t*e1 = (hevent_t*)_e1;
+ hevent_t*e2 = (hevent_t*)_e2;
+ int diff = e1->x - e2->x;
+ if(diff) return diff;
+ return e1->type - e2->type; //schedule hotpixel before hend
+}
+
+static hevents_t hevents_fill(status_t*status)
+{
+ horizdata_t*horiz = &status->horiz;
+ xrow_t*xrow = status->xrow;
+
+ hevents_t e;
+ e.events = malloc(sizeof(hevent_t)*(horiz->num*2 + xrow->num));
+ e.num = 0;
+
+ int t;
+ for(t=0;t<horiz->num;t++) {
+ assert(horiz->data[t].x1 != horiz->data[t].x2);
+ e.events[e.num].x = horiz->data[t].x1;
+ e.events[e.num].h = &horiz->data[t];
+ e.events[e.num].type = hevent_start;
+ e.num++;
+ e.events[e.num].x = horiz->data[t].x2;
+ e.events[e.num].h = &horiz->data[t];
+ e.events[e.num].type = hevent_end;
+ e.num++;
+ }
+ for(t=0;t<xrow->num;t++) {
+ e.events[e.num].x = status->xrow->x[t];
+ e.events[e.num].h = 0;
+ e.events[e.num].type = hevent_hotpixel;
+ e.num++;
+ }
+ qsort(e.events, e.num, sizeof(hevent_t), compare_hevents);
+ return e;
+
+}
+
+static void process_horizontals(status_t*status)
+{
+ horizdata_t*horiz = &status->horiz;
+
+ if(!horiz->num)
+ return;
+
+ hevents_t events = hevents_fill(status);
+ int num_open = 0;
+ horizontal_t**open = malloc(sizeof(horizontal_t*)*horiz->num);
+
+ int s,t;
+ for(t=0;t<events.num;t++) {
+ hevent_t*e = &events.events[t];
+ switch(e->type) {
+ case hevent_start:
+ e->h->pos = num_open;
+ open[num_open++] = e->h;
+#ifdef DEBUG
+ fprintf(stderr, "horizontal (y=%.2f): %.2f -> %.2f dir=%s fs=%p\n",
+ e->h->y * status->gridsize,
+ e->h->x1 * status->gridsize,
+ e->h->x2 * status->gridsize,
+ e->h->dir==DIR_UP?"up":"down", e->h->fs);
+#endif
+ assert(e->h->y == status->y);
+ assert(xrow_contains(status->xrow, e->h->x1));
+ assert(xrow_contains(status->xrow, e->h->x2));
+ break;
+ case hevent_end:
+ num_open--;
+ if(num_open) {
+ open[num_open]->pos = e->h->pos;
+ open[e->h->pos] = open[num_open];
+ }
+ break;
+ case hevent_hotpixel:
+ {
+ windstate_t below;
+ for(s=0;s<num_open;s++) {
+ int x1 = open[s]->xpos;
+ int x2 = e->x;
+ assert(status->y == open[s]->y);
+ if(!s)
+ below = get_horizontal_first_windstate(status, x1, x2);
+ open[s]->xpos = e->x;
+ assert(x1 < x2);
+ below = process_horizontal_fragment(status, open[s], x1, x2, below);
+ }
+ }
+ break;
+ }
+ }
+ free(open);
+ free(events.events);