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 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));
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 gfxpolystroke_t*stroke = poly->strokes;
146 for(;stroke;stroke=stroke->next) {
147 edges += stroke->num_points-1;
152 char gfxpoly_check(gfxpoly_t*poly)
154 dict_t*d = dict_new2(&point_type);
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);
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 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?"]":"");
200 void gfxpoly_save(gfxpoly_t*poly, const char*filename)
202 FILE*fi = fopen(filename, "wb");
203 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
204 fprintf(fi, "%% begin\n");
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);
215 fprintf(fi, "stroke\n");
217 fprintf(fi, "showpage\n");
221 inline static event_t event_new()
224 memset(&e, 0, sizeof(e));
228 static void event_dump(event_t*e)
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);
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;}
246 static void segment_dump(segment_t*s)
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);
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)
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
267 int32_t x = x1;x1=x2;x2=x;
268 int32_t y = y1;y1=y2;y2=y;
275 s->k = (double)x1*y2-(double)x2*y1;
276 s->left = s->right = 0;
279 s->minx = min32(x1,x2);
280 s->maxx = max32(x1,x2);
283 s->polygon_nr = polygon_nr;
284 static int segment_count=0;
285 s->nr = segment_count++;
288 assert(LINE_EQ(s->a, s) == 0);
289 assert(LINE_EQ(s->b, s) == 0);
291 /* check that all signs are in order:
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);
305 /* TODO: make this int_type */
306 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
309 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
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);
316 static void segment_clear(segment_t*s)
318 dict_clear(&s->scheduled_crossings);
320 static void segment_destroy(segment_t*s)
326 static void advance_stroke(heap_t*queue, gfxpolystroke_t*stroke, int polygon_nr, int pos)
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);
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);
346 event_t e = event_new();
347 e.type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
352 if(e.type != EVENT_HORIZONTAL) {
358 fprintf(stderr, "attaching contingency of stroke %08x to segment [%d] %s\n",
359 stroke, s, s->delta.y?"":"(horizontal)");
366 static void gfxpoly_enqueue(gfxpoly_t*p, heap_t*queue, int polygon_nr)
369 gfxpolystroke_t*stroke = p->strokes;
370 for(;stroke;stroke=stroke->next) {
371 assert(stroke->num_points > 1);
375 for(s=0;s<stroke->num_points-1;s++) {
376 assert(stroke->points[s].y <= stroke->points[s+1].y);
379 advance_stroke(queue, stroke, polygon_nr, 0);
383 static void schedule_endpoint(status_t*status, segment_t*s)
385 // schedule end point of segment
386 assert(s->b.y > status->y);
392 heap_put(status->queue, &e);
395 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
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 */
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));
423 if(s1->maxx <= s2->minx) {
425 fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
427 /* bounding boxes don't intersect */
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 */
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);
440 return; // we already know about this one
444 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
447 // lines are exactly on top of each other (ignored)
449 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
454 fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
456 /* lines are parallel */
461 double asign2 = LINE_EQ(s1->a, s2);
463 // segment1 touches segment2 in a single point (ignored)
465 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
469 double bsign2 = LINE_EQ(s1->b, s2);
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);
478 if(asign2<0 && bsign2<0) {
479 // segment1 is completely to the left of segment2
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);
485 if(asign2>0 && bsign2>0) {
486 // segment1 is completely to the right of segment2
487 #ifndef DONT_REMEMBER_CROSSINGS
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);
496 double asign1 = LINE_EQ(s2->a, s1);
498 // segment2 touches segment1 in a single point (ignored)
500 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
504 double bsign1 = LINE_EQ(s2->b, s1);
506 // segment2 touches segment1 in a single point (ignored)
508 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
513 if(asign1<0 && bsign1<0) {
514 // segment2 is completely to the left of segment1
515 #ifndef DONT_REMEMBER_CROSSINGS
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);
523 if(asign1>0 && bsign1>0) {
524 // segment2 is completely to the right of segment1
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);
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;
538 assert(!(asign1<0 && bsign1>0));
539 assert(!(asign2>0 && bsign2<0));
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;
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);
549 assert(p.y >= status->y);
551 assert(p.x >= s1->minx && p.x <= s1->maxx);
552 assert(p.x >= s2->minx && p.x <= s2->maxx);
557 #ifndef DONT_REMEMBER_CROSSINGS
558 assert(!dict_contains(status->seen_crossings, &pair));
559 dict_put(status->seen_crossings, &pair, 0);
563 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
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);
573 event_t e = event_new();
574 e.type = EVENT_CROSS;
578 heap_put(status->queue, &e);
582 static void exchange_two(status_t*status, event_t*e)
584 //exchange two segments in list
585 segment_t*s1 = e->s1;
586 segment_t*s2 = e->s2;
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);
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;
601 schedule_crossing(status, left, s2);
603 schedule_crossing(status, s1, right);
606 typedef struct _box {
607 point_t left1, left2, right1, right2;
609 static inline box_t box_new(int32_t x, int32_t y)
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;
619 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
621 assert(s->pos.x != p.x || s->pos.y != p.y);
624 if(!dict_contains(status->segs_with_point, s))
625 dict_put(status->segs_with_point, s, 0);
626 assert(s->fs_out_ok);
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);
634 // omit horizontal lines
635 if(s->pos.y != p.y) {
639 status->writer.moveto(&status->writer, a.x, a.y);
640 status->writer.lineto(&status->writer, b.x, b.y);
644 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
650 typedef struct _segrange {
657 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
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;
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)) {
669 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
675 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
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
682 double x = XPOS(seg, y);
683 if(!range->segmin || x<range->xmin) {
688 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
691 double x = XPOS(seg, y);
692 if(!range->segmax || x>range->xmax) {
707 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
709 segment_t*first=0, *last = 0;
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);
715 seg = actlist_right(status->actlist, seg);
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
723 last = seg;if(!first) {first=seg;}
724 double d1 = LINE_EQ(box.right1, seg);
725 double d2 = LINE_EQ(box.right2, seg);
728 insert_point_into_segment(status, seg, box.right2);
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 */
739 segrange_test_segment_min(range, first, y);
740 segrange_test_segment_max(range, last, y);
750 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
752 segment_t*first=0, *last = 0;
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);
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
765 last = seg;if(!first) {first=seg;}
766 double d1 = LINE_EQ(box.left1, seg);
767 double d2 = LINE_EQ(box.left2, seg);
770 insert_point_into_segment(status, seg, box.right2);
778 segrange_test_segment_min(range, last, y);
779 segrange_test_segment_max(range, first, y);
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
795 static void add_points_to_ending_segments(status_t*status, int32_t y)
797 segment_t*seg = status->ending_segments;
799 segment_t*next = seg->right;seg->right=0;
801 assert(seg->b.y == status->y);
803 if(status->xrow->num == 1) {
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);
810 int start=0,end=status->xrow->num,dir=1;
811 if(seg->delta.x < 0) {
812 start = status->xrow->num-1;
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);
829 /* we *need* to find a point to insert. the segment's own end point
830 is in that list, for Pete's sake. */
834 // now that this is done, too, we can also finally free this segment
835 segment_destroy(seg);
838 status->ending_segments = 0;
841 static void recalculate_windings(status_t*status, segrange_t*range)
844 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
846 segrange_adjust_endpoints(range, status->y);
848 segment_t*s = range->segmin;
849 segment_t*end = range->segmax;
853 s = actlist_leftmost(status->actlist);
855 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
856 s == range->segmin?"S":(
857 s == range->segmax?"E":""));
860 fprintf(stderr, "\n");
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) {
871 s = actlist_rightmost(status->actlist);
872 while(s && s!=range->segmax) {
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);
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);
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":"");
899 assert(!(!s->changed && fs_old!=s->fs_out));
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)
914 segment_t* left = actlist_find(status->actlist, h->a, h->a);
915 segment_t* right = actlist_find(status->actlist, h->b, h->b);
917 /* not strictly necessary, also done by the event */
918 xrow_add(status->xrow, h->a.x);
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
932 int32_t x = XPOS_INT(s, status->y);
934 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
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);
950 static void event_apply(status_t*status, event_t*e)
953 case EVENT_HORIZONTAL: {
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;
964 //delete segment from list
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));
975 segment_t*left = s->left;
976 segment_t*right = s->right;
977 actlist_delete(status->actlist, s);
979 schedule_crossing(status, left, right);
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);
988 //insert segment into list
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;
998 schedule_crossing(status, left, s);
1000 schedule_crossing(status, s, right);
1001 schedule_endpoint(status, s);
1005 // exchange two segments
1009 if(e->s1->right == e->s2) {
1010 assert(e->s2->left == e->s1);
1011 exchange_two(status, e);
1013 assert(e->s2->left != e->s1);
1015 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
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);
1028 #ifndef DONT_REMEMBER_CROSSINGS
1029 assert(dict_contains(status->seen_crossings, &pair));
1030 dict_del(status->seen_crossings, &pair);
1039 static void check_status(status_t*status)
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",
1047 s->delta.x<0?"-":"+",
1055 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1058 |..| |...........| | |
1059 |..| |...........| | |
1060 |..+ + +..| +--+ +--+
1061 |...........| |..| | |
1062 |...........| |..| | |
1066 fprintf(stderr, "========================================================================\n");
1068 heap_t* queue = heap_new(sizeof(event_t), compare_events_simple);
1069 gfxpoly_enqueue(poly, queue, 0);
1071 actlist_t* actlist = actlist_new();
1073 event_t*e = heap_chopmax(queue);
1079 fprintf(stderr, "----------------------------------- %d\n", y);
1080 actlist_dump(actlist, y-1);
1083 actlist_verify(actlist, y-1);
1086 if(fill && x != e->p.x) {
1088 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
1092 gfxpolystroke_t*stroke = rfx_calloc(sizeof(gfxpolystroke_t));
1093 stroke->next = poly->strokes;
1094 poly->strokes = stroke;
1096 stroke->num_points = 2;
1097 stroke->points = malloc(sizeof(point_t)*2);
1098 stroke->dir = DIR_UP; // FIXME
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)
1107 stroke->points[0] = a;
1108 stroke->points[1] = b;
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);
1115 assert(s->a.y == y || s->b.y == y);
1121 segment_t*s = e->s1;
1125 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1126 actlist_insert(actlist, s->a, s->b, s);
1132 heap_put(queue, &e);
1133 left = actlist_left(actlist, s);
1137 left = actlist_left(actlist, s);
1138 actlist_delete(actlist, s);
1139 advance_stroke(queue, s->stroke, s->polygon_nr, s->stroke_pos);
1146 fill ^= 1;//(before.is_filled != after.is_filled);
1148 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d\n",
1149 y, e->type==EVENT_START?"start":"end",
1155 if(e->type == EVENT_END)
1159 e = heap_chopmax(queue);
1160 } while(e && y == e->p.y);
1162 assert(!fill); // check that polygon is not bleeding
1165 actlist_destroy(actlist);
1166 heap_destroy(queue);
1169 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1171 current_polygon = poly;
1172 heap_t* queue = heap_new(sizeof(event_t), compare_events);
1174 gfxpoly_enqueue(poly, queue, /*polygon nr*/0);
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);
1186 status.seen_crossings = dict_new2(&point_type);
1187 int lasty=heap_peek(queue)?((event_t*)heap_peek(queue))->p.y-1:0;
1190 status.xrow = xrow_new();
1192 event_t*e = heap_chopmax(queue);
1195 assert(status.y>=lasty);
1197 status.intersecting_segs = dict_new2(&ptr_type);
1198 status.segs_with_point = dict_new2(&ptr_type);
1202 fprintf(stderr, "----------------------------------- %d\n", status.y);
1203 actlist_dump(status.actlist, status.y-1);
1206 actlist_verify(status.actlist, status.y-1);
1208 xrow_reset(status.xrow);
1210 xrow_add(status.xrow, e->p.x);
1211 event_apply(&status, e);
1213 e = heap_chopmax(queue);
1214 } while(e && status.y == e->p.y);
1216 xrow_sort(status.xrow);
1218 memset(&range, 0, sizeof(range));
1220 actlist_dump(status.actlist, status.y);
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);
1226 recalculate_windings(&status, &range);
1228 check_status(&status);
1229 dict_destroy(status.intersecting_segs);
1230 dict_destroy(status.segs_with_point);
1234 dict_destroy(status.seen_crossings);
1236 actlist_destroy(status.actlist);
1237 heap_destroy(queue);
1238 xrow_destroy(status.xrow);
1240 gfxpoly_t*p = (gfxpoly_t*)status.writer.finish(&status.writer);
1242 add_horizontals(p, &windrule_evenodd, context); // output is always even/odd