14 static gfxpoly_t*current_polygon = 0;
15 void gfxpoly_fail(char*expr, char*file, int line, const char*function)
17 if(!current_polygon) {
18 fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
22 void*md5 = init_md5();
25 for(s=0;s<current_polygon->num_strokes;s++) {
26 gfxpolystroke_t*stroke = ¤t_polygon->strokes[s];
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));
33 char filename[32+4+1];
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]);
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);
41 gfxpoly_save(current_polygon, filename);
45 static char point_equals(const void*o1, const void*o2)
47 const point_t*p1 = o1;
48 const point_t*p2 = o2;
49 return p1->x == p2->x && p1->y == p2->y;
51 static unsigned int point_hash(const void*o)
56 static void* point_dup(const void*o)
59 point_t*n = malloc(sizeof(point_t));
64 static void point_free(void*o)
71 static type_t point_type = {
78 typedef struct _status {
84 windcontext_t*context;
85 segment_t*ending_segments;
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
94 typedef struct _event {
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)
106 event_t* a = (event_t*)_a;
107 event_t* b = (event_t*)_b;
108 int d = b->p.y - a->p.y;
115 static int compare_events(const void*_a,const void*_b)
117 event_t* a = (event_t*)_a;
118 event_t* b = (event_t*)_b;
119 int d = b->p.y - a->p.y;
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.
131 d = b->type - a->type;
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;
141 int gfxpoly_size(gfxpoly_t*poly)
145 for(t=0;t<poly->num_strokes;t++) {
146 gfxpolystroke_t*stroke = &poly->strokes[t];
147 edges += stroke->num_points-1;
152 char gfxpoly_check(gfxpoly_t*poly)
154 dict_t*d = dict_new2(&point_type);
156 for(t=0;t<poly->num_strokes;t++) {
157 gfxpolystroke_t*stroke = &poly->strokes[t];
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);
164 int count = (ptroff_t)dict_lookup(d, &p);
167 dict_put(d, &p, (void*)(ptroff_t)count);
171 DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
172 int count = (ptroff_t)c;
174 fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count);
183 void gfxpoly_dump(gfxpoly_t*poly)
186 double g = poly->gridsize;
187 fprintf(stderr, "polyon %08x (gridsize: %f)\n", poly, poly->gridsize);
188 for(t=0;t<poly->num_strokes;t++) {
189 gfxpolystroke_t*stroke = &poly->strokes[t];
190 for(s=0;s<stroke->num_points-1;s++) {
191 point_t a = stroke->points[s];
192 point_t b = stroke->points[s+1];
193 fprintf(stderr, "%s(%f,%f) -> (%f,%f)%s\n", s?" ":"[", a.x*g, a.y*g, b.x*g, b.y*g,
194 s==stroke->num_points-2?"]":"");
199 void gfxpoly_save(gfxpoly_t*poly, const char*filename)
201 FILE*fi = fopen(filename, "wb");
202 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
203 fprintf(fi, "%% begin\n");
205 for(t=0;t<poly->num_strokes;t++) {
206 gfxpolystroke_t*stroke = &poly->strokes[t];
207 for(s=0;s<stroke->num_points-1;s++) {
208 point_t a = stroke->points[s];
209 point_t b = stroke->points[s+1];
210 fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
211 fprintf(fi, "%d %d moveto\n", a.x, a.y);
212 fprintf(fi, "%d %d lineto\n", b.x, b.y);
213 fprintf(fi, "stroke\n");
216 fprintf(fi, "showpage\n");
220 inline static event_t event_new()
223 memset(&e, 0, sizeof(e));
227 static void event_dump(event_t*e)
229 if(e->type == EVENT_HORIZONTAL) {
230 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);
231 } else if(e->type == EVENT_START) {
232 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
233 } else if(e->type == EVENT_END) {
234 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
235 } else if(e->type == EVENT_CROSS) {
236 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
242 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
243 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
245 static void segment_dump(segment_t*s)
247 fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
248 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k,
249 (double)s->delta.x / s->delta.y);
252 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)
258 /* up/down for horizontal segments is handled by "rotating"
259 them 90° anticlockwise in screen coordinates (tilt your head to
261 TODO: is this still needed?
266 int32_t x = x1;x1=x2;x2=x;
267 int32_t y = y1;y1=y2;y2=y;
274 s->k = (double)x1*y2-(double)x2*y1;
275 s->left = s->right = 0;
278 s->minx = min32(x1,x2);
279 s->maxx = max32(x1,x2);
282 s->polygon_nr = polygon_nr;
283 static int segment_count=0;
284 s->nr = segment_count++;
287 assert(LINE_EQ(s->a, s) == 0);
288 assert(LINE_EQ(s->b, s) == 0);
290 /* check that all signs are in order:
298 p.x = min32(s->a.x, s->b.x);
299 assert(LINE_EQ(p, s) <= 0);
300 p.x = max32(s->a.x, s->b.x);
301 assert(LINE_EQ(p, s) >= 0);
304 /* TODO: make this int_type */
305 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
308 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
310 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
311 segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
315 static void segment_clear(segment_t*s)
317 dict_clear(&s->scheduled_crossings);
319 static void segment_destroy(segment_t*s)
325 static void advance_stroke(heap_t*queue, gfxpolystroke_t*stroke, int polygon_nr, int pos)
327 while(pos < stroke->num_points-1) {
328 assert(stroke->points[pos].y <= stroke->points[pos+1].y);
329 segment_t*s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
331 s->stroke_pos = ++pos;
335 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (%d more to come)\n",
336 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
337 s->dir==DIR_UP?"up":"down", stroke->num_points - 1 - pos);
339 event_t e = event_new();
340 e.type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
345 if(e.type != EVENT_HORIZONTAL) {
351 static void gfxpoly_enqueue(gfxpoly_t*p, heap_t*queue, int polygon_nr)
354 for(t=0;t<p->num_strokes;t++) {
355 gfxpolystroke_t*stroke = &p->strokes[t];
356 assert(stroke->num_points > 1);
360 for(s=0;s<stroke->num_points-1;s++) {
361 assert(stroke->points[s].y <= stroke->points[s+1].y);
364 advance_stroke(queue, stroke, polygon_nr, 0);
368 static void schedule_endpoint(status_t*status, segment_t*s)
370 // schedule end point of segment
371 assert(s->b.y > status->y);
377 heap_put(status->queue, &e);
380 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
382 /* the code that's required (and the checks you can perform) before
383 it can be said with 100% certainty that we indeed have a valid crossing
384 amazes me every time. -mk */
387 assert(s1->right == s2);
388 assert(s2->left == s1);
389 int32_t miny1 = min32(s1->a.y,s1->b.y);
390 int32_t maxy1 = max32(s1->a.y,s1->b.y);
391 int32_t miny2 = min32(s2->a.y,s2->b.y);
392 int32_t maxy2 = max32(s2->a.y,s2->b.y);
393 int32_t minx1 = min32(s1->a.x,s1->b.x);
394 int32_t minx2 = min32(s2->a.x,s2->b.x);
395 int32_t maxx1 = max32(s1->a.x,s1->b.x);
396 int32_t maxx2 = max32(s2->a.x,s2->b.x);
397 /* check that precomputation is sane */
398 assert(minx1 == s1->minx && minx2 == s2->minx);
399 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
400 /* both segments are active, so this can't happen */
401 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
402 /* we know that right now, s2 is to the right of s1, so there's
403 no way the complete bounding box of s1 is to the right of s1 */
404 assert(!(s1->minx > s2->maxx));
405 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
408 if(s1->maxx <= s2->minx) {
410 fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
412 /* bounding boxes don't intersect */
416 #define REMEMBER_CROSSINGS
417 #ifdef REMEMBER_CROSSINGS
418 if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
419 /* FIXME: this whole segment hashing thing is really slow */
421 fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
422 // DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
423 // fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
426 return; // we already know about this one
430 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
433 // lines are exactly on top of each other (ignored)
435 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
440 fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
442 /* lines are parallel */
446 double asign2 = LINE_EQ(s1->a, s2);
447 double bsign2 = LINE_EQ(s1->b, s2);
448 if(asign2<0 && bsign2<0) {
449 // segment1 is completely to the left of segment2
451 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);
455 if(asign2>0 && bsign2>0) {
456 // TODO: can this ever happen?
458 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);
460 // segment2 is completely to the left of segment1
464 // segment1 touches segment2 in a single point (ignored)
466 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
471 // segment1 touches segment2 in a single point (ignored)
473 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
477 double asign1 = LINE_EQ(s2->a, s1);
478 double bsign1 = LINE_EQ(s2->b, s1);
479 if(asign1<0 && bsign1<0) {
480 // segment1 is completely to the left of segment2
482 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);
486 if(asign1>0 && bsign1>0) {
487 // segment2 is completely to the left of segment1
489 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);
494 // segment2 touches segment1 in a single point (ignored)
496 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
501 // segment2 touches segment1 in a single point (ignored)
503 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
508 /* TODO: should we precompute these? */
509 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
510 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
513 p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
514 p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
516 #ifndef REMEMBER_CROSSINGS
517 if(p.y < status->y) return;
520 assert(p.y >= status->y);
522 assert(p.x >= s1->minx && p.x <= s1->maxx);
523 assert(p.x >= s2->minx && p.x <= s2->maxx);
528 #ifdef REMEMBER_CROSSINGS
529 assert(!dict_contains(status->seen_crossings, &pair));
530 dict_put(status->seen_crossings, &pair, 0);
534 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
537 #ifdef REMEMBER_CROSSINGS
538 /* we insert into each other's intersection history because these segments might switch
539 places and we still want to look them up quickly after they did */
540 dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
541 dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
544 event_t e = event_new();
545 e.type = EVENT_CROSS;
549 heap_put(status->queue, &e);
553 static void exchange_two(status_t*status, event_t*e)
555 //exchange two segments in list
556 segment_t*s1 = e->s1;
557 segment_t*s2 = e->s2;
559 if(!dict_contains(status->intersecting_segs, s1))
560 dict_put(status->intersecting_segs, s1, 0);
561 if(!dict_contains(status->intersecting_segs, s2))
562 dict_put(status->intersecting_segs, s2, 0);
564 assert(s2->left == s1);
565 assert(s1->right == s2);
566 actlist_swap(status->actlist, s1, s2);
567 assert(s2->right == s1);
568 assert(s1->left == s2);
569 segment_t*left = s2->left;
570 segment_t*right = s1->right;
572 schedule_crossing(status, left, s2);
574 schedule_crossing(status, s1, right);
577 typedef struct _box {
578 point_t left1, left2, right1, right2;
580 static inline box_t box_new(int32_t x, int32_t y)
583 box.right1.x = box.right2.x = x;
584 box.left1.x = box.left2.x = x-1;
585 box.left1.y = box.right1.y = y-1;
586 box.left2.y = box.right2.y = y;
590 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
592 assert(s->pos.x != p.x || s->pos.y != p.y);
595 if(!dict_contains(status->segs_with_point, s))
596 dict_put(status->segs_with_point, s, 0);
597 assert(s->fs_out_ok);
602 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
603 s->pos.x, s->pos.y, p.x, p.y);
605 // omit horizontal lines
606 if(s->pos.y != p.y) {
610 status->writer.moveto(&status->writer, a.x, a.y);
611 status->writer.lineto(&status->writer, b.x, b.y);
615 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
621 typedef struct _segrange {
628 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
630 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
631 segment_t*min = range->segmin;
632 segment_t*max = range->segmax;
634 /* we need this because if two segments intersect exactly on
635 the scanline, segrange_test_segment_{min,max} can't tell which
636 one is smaller/larger */
637 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
640 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
646 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
649 /* we need to calculate the xpos anew (and can't use start coordinate or
650 intersection coordinate), because we need the xpos exactly at the end of
653 double x = XPOS(seg, y);
654 if(!range->segmin || x<range->xmin) {
659 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
662 double x = XPOS(seg, y);
663 if(!range->segmax || x>range->xmax) {
678 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
680 segment_t*first=0, *last = 0;
682 for(t=0;t<status->xrow->num;t++) {
683 box_t box = box_new(status->xrow->x[t], y);
684 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
686 seg = actlist_right(status->actlist, seg);
689 // this segment started in this scanline, ignore it
690 seg->changed = 1;last = seg;if(!first) {first=seg;}
691 } else if(seg->delta.x <= 0) {
692 // ignore segment w/ negative slope
694 last = seg;if(!first) {first=seg;}
695 double d1 = LINE_EQ(box.right1, seg);
696 double d2 = LINE_EQ(box.right2, seg);
699 insert_point_into_segment(status, seg, box.right2);
701 /* we unfortunately can't break here- the active list is sorted according
702 to the *bottom* of the scanline. hence pretty much everything that's still
703 coming might reach into our box */
710 segrange_test_segment_min(range, first, y);
711 segrange_test_segment_max(range, last, y);
721 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
723 segment_t*first=0, *last = 0;
725 for(t=status->xrow->num-1;t>=0;t--) {
726 box_t box = box_new(status->xrow->x[t], y);
727 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
731 // this segment started in this scanline, ignore it
732 seg->changed = 1;last = seg;if(!first) {first=seg;}
733 } else if(seg->delta.x > 0) {
734 // ignore segment w/ positive slope
736 last = seg;if(!first) {first=seg;}
737 double d1 = LINE_EQ(box.left1, seg);
738 double d2 = LINE_EQ(box.left2, seg);
741 insert_point_into_segment(status, seg, box.right2);
749 segrange_test_segment_min(range, last, y);
750 segrange_test_segment_max(range, first, y);
753 /* segments ending in the current scanline need xrow treatment like everything else.
754 (consider an intersection taking place just above a nearly horizontal segment
755 ending on the current scanline- the intersection would snap down *below* the
756 ending segment if we don't add the intersection point to the latter right away)
757 we need to treat ending segments seperately, however. we have to delete them from
758 the active list right away to make room for intersect operations (which might
759 still be in the current scanline- consider two 45° polygons and a vertical polygon
760 intersecting on an integer coordinate). but once they're no longer in the active list,
761 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
762 them to the active list just for point snapping would be overkill.
763 (One other option to consider, however, would be to create a new active list only
766 static void add_points_to_ending_segments(status_t*status, int32_t y)
768 segment_t*seg = status->ending_segments;
770 segment_t*next = seg->right;seg->right=0;
772 assert(seg->b.y == status->y);
774 if(status->xrow->num == 1) {
776 assert(seg->b.x == status->xrow->x[0]);
777 point_t p = {status->xrow->x[0], y};
778 insert_point_into_segment(status, seg, p);
781 int start=0,end=status->xrow->num,dir=1;
782 if(seg->delta.x < 0) {
783 start = status->xrow->num-1;
786 for(t=start;t!=end;t+=dir) {
787 box_t box = box_new(status->xrow->x[t], y);
788 double d0 = LINE_EQ(box.left1, seg);
789 double d1 = LINE_EQ(box.left2, seg);
790 double d2 = LINE_EQ(box.right1, seg);
791 double d3 = LINE_EQ(box.right2, seg);
792 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
793 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
794 insert_point_into_segment(status, seg, box.right2);
800 /* we *need* to find a point to insert. the segment's own end point
801 is in that list, for Pete's sake. */
805 // now that this is done, too, we can also finally free this segment
806 segment_destroy(seg);
809 status->ending_segments = 0;
812 static void recalculate_windings(status_t*status, segrange_t*range)
815 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
817 segrange_adjust_endpoints(range, status->y);
819 segment_t*s = range->segmin;
820 segment_t*end = range->segmax;
824 s = actlist_leftmost(status->actlist);
826 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
827 s == range->segmin?"S":(
828 s == range->segmax?"E":""));
831 fprintf(stderr, "\n");
835 /* test sanity: check that we don't have changed segments
836 outside of the given range */
837 s = actlist_leftmost(status->actlist);
838 while(s && s!=range->segmin) {
842 s = actlist_rightmost(status->actlist);
843 while(s && s!=range->segmax) {
847 /* in check mode, go through the whole interval so we can test
848 that all polygons where the fillstyle changed also have seg->changed=1 */
849 s = actlist_leftmost(status->actlist);
860 segment_t* left = actlist_left(status->actlist, s);
861 windstate_t wind = left?left->wind:status->windrule->start(status->context);
862 s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
863 fillstyle_t*fs_old = s->fs_out;
864 s->fs_out = status->windrule->diff(&wind, &s->wind);
867 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",
868 fs_old!=s->fs_out?"CHANGED":"");
870 assert(!(!s->changed && fs_old!=s->fs_out));
881 /* we need to handle horizontal lines in order to add points to segments
882 we otherwise would miss during the windrule re-evaluation */
883 static void intersect_with_horizontal(status_t*status, segment_t*h)
885 segment_t* left = actlist_find(status->actlist, h->a, h->a);
886 segment_t* right = actlist_find(status->actlist, h->b, h->b);
888 /* not strictly necessary, also done by the event */
889 xrow_add(status->xrow, h->a.x);
897 left = actlist_right(status->actlist, left); //first seg to the right of h->a
898 right = right->right; //first seg to the right of h->b
903 int32_t x = XPOS_INT(s, status->y);
905 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
913 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
914 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
915 xrow_add(status->xrow, x);
921 static void event_apply(status_t*status, event_t*e)
924 case EVENT_HORIZONTAL: {
929 intersect_with_horizontal(status, s);
930 advance_stroke(status->queue, s->stroke, s->polygon_nr, s->stroke_pos);
931 segment_destroy(s);e->s1=0;
935 //delete segment from list
941 dict_del(status->intersecting_segs, s);
942 dict_del(status->segs_with_point, s);
943 assert(!dict_contains(status->intersecting_segs, s));
944 assert(!dict_contains(status->segs_with_point, s));
946 segment_t*left = s->left;
947 segment_t*right = s->right;
948 actlist_delete(status->actlist, s);
950 schedule_crossing(status, left, right);
952 /* schedule segment for xrow handling */
953 s->left = 0; s->right = status->ending_segments;
954 status->ending_segments = s;
955 advance_stroke(status->queue, s->stroke, s->polygon_nr, s->stroke_pos);
959 //insert segment into list
964 assert(e->p.x == s->a.x && e->p.y == s->a.y);
965 actlist_insert(status->actlist, s->a, s->b, s);
966 segment_t*left = s->left;
967 segment_t*right = s->right;
969 schedule_crossing(status, left, s);
971 schedule_crossing(status, s, right);
972 schedule_endpoint(status, s);
976 // exchange two segments
980 if(e->s1->right == e->s2) {
981 assert(e->s2->left == e->s1);
982 exchange_two(status, e);
984 assert(e->s2->left != e->s1);
986 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
988 #ifdef REMEMBER_CROSSINGS
989 /* ignore this crossing for now (there are some line segments in between).
990 it'll get rescheduled as soon as the "obstacles" are gone */
991 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
992 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
993 assert(del1 && del2);
999 #ifdef REMEMBER_CROSSINGS
1000 assert(dict_contains(status->seen_crossings, &pair));
1001 dict_del(status->seen_crossings, &pair);
1010 static void check_status(status_t*status)
1012 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1013 if((s->pos.x != s->b.x ||
1014 s->pos.y != s->b.y) &&
1015 !dict_contains(status->segs_with_point, s)) {
1016 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1018 s->delta.x<0?"-":"+",
1026 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1029 |..| |...........| | |
1030 |..| |...........| | |
1031 |..+ + +..| +--+ +--+
1032 |...........| |..| | |
1033 |...........| |..| | |
1037 fprintf(stderr, "========================================================================\n");
1039 heap_t* queue = heap_new(sizeof(event_t), compare_events_simple);
1040 gfxpoly_enqueue(poly, queue, 0);
1042 actlist_t* actlist = actlist_new();
1044 event_t*e = heap_chopmax(queue);
1045 int newstrokes_size = 4;
1046 int num_newstrokes = 0;
1047 gfxpolystroke_t*newstrokes = malloc(sizeof(gfxpolystroke_t)*newstrokes_size);
1053 fprintf(stderr, "----------------------------------- %d\n", y);
1054 actlist_dump(actlist, y-1);
1057 actlist_verify(actlist, y-1);
1060 if(fill && x != e->p.x) {
1062 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
1066 if(num_newstrokes == newstrokes_size) {
1067 newstrokes_size = (newstrokes_size)<<1;
1068 newstrokes = rfx_realloc(newstrokes, sizeof(gfxpolystroke_t)*newstrokes_size);
1070 gfxpolystroke_t*stroke = &newstrokes[num_newstrokes++];
1071 stroke->num_points = 2;
1072 stroke->points = malloc(sizeof(point_t)*2);
1073 stroke->dir = DIR_UP; // FIXME
1077 /* we draw from low x to high x so that left/right fillstyles add up
1078 (because the horizontal line's fill style controls the area *below* the line)
1082 stroke->points[0] = a;
1083 stroke->points[1] = b;
1085 /* the output should always be intersection free polygons, so check this horizontal
1086 line isn't hacking through any segments in the active list */
1087 segment_t* start = actlist_find(actlist, b, b);
1088 segment_t* s = actlist_find(actlist, a, a);
1090 assert(s->a.y == y || s->b.y == y);
1096 segment_t*s = e->s1;
1100 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1101 actlist_insert(actlist, s->a, s->b, s);
1107 heap_put(queue, &e);
1108 left = actlist_left(actlist, s);
1112 left = actlist_left(actlist, s);
1113 actlist_delete(actlist, s);
1114 advance_stroke(queue, s->stroke, s->polygon_nr, s->stroke_pos);
1121 fill ^= 1;//(before.is_filled != after.is_filled);
1123 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d\n",
1124 y, e->type==EVENT_START?"start":"end",
1130 if(e->type == EVENT_END)
1134 e = heap_chopmax(queue);
1135 } while(e && y == e->p.y);
1137 assert(!fill); // check that polygon is not bleeding
1140 poly->strokes = rfx_realloc(poly->strokes, sizeof(gfxpolystroke_t)*(num_newstrokes+poly->num_strokes));
1141 memcpy(&poly->strokes[poly->num_strokes], newstrokes, sizeof(gfxpolystroke_t)*num_newstrokes);
1142 poly->num_strokes += num_newstrokes;
1145 actlist_destroy(actlist);
1146 heap_destroy(queue);
1149 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1151 current_polygon = poly;
1152 heap_t* queue = heap_new(sizeof(event_t), compare_events);
1154 gfxpoly_enqueue(poly, queue, /*polygon nr*/0);
1157 memset(&status, 0, sizeof(status_t));
1158 status.queue = queue;
1159 status.windrule = windrule;
1160 status.context = context;
1161 status.actlist = actlist_new();
1162 gfxpolywriter_init(&status.writer);
1163 status.writer.setgridsize(&status.writer, poly->gridsize);
1166 status.seen_crossings = dict_new2(&point_type);
1167 int lasty=heap_peek(queue)?((event_t*)heap_peek(queue))->p.y-1:0;
1170 status.xrow = xrow_new();
1172 event_t*e = heap_chopmax(queue);
1175 assert(status.y>=lasty);
1177 status.intersecting_segs = dict_new2(&ptr_type);
1178 status.segs_with_point = dict_new2(&ptr_type);
1182 fprintf(stderr, "----------------------------------- %d\n", status.y);
1183 actlist_dump(status.actlist, status.y-1);
1186 actlist_verify(status.actlist, status.y-1);
1188 xrow_reset(status.xrow);
1190 xrow_add(status.xrow, e->p.x);
1191 event_apply(&status, e);
1193 e = heap_chopmax(queue);
1194 } while(e && status.y == e->p.y);
1196 xrow_sort(status.xrow);
1198 memset(&range, 0, sizeof(range));
1200 actlist_dump(status.actlist, status.y);
1202 add_points_to_positively_sloped_segments(&status, status.y, &range);
1203 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1204 add_points_to_ending_segments(&status, status.y);
1206 recalculate_windings(&status, &range);
1208 check_status(&status);
1209 dict_destroy(status.intersecting_segs);
1210 dict_destroy(status.segs_with_point);
1214 dict_destroy(status.seen_crossings);
1216 actlist_destroy(status.actlist);
1217 heap_destroy(queue);
1218 xrow_destroy(status.xrow);
1220 gfxpoly_t*p = (gfxpoly_t*)status.writer.finish(&status.writer);
1222 add_horizontals(p, &windrule_evenodd, context); // output is always even/odd