15 static gfxpoly_t*current_polygon = 0;
16 void gfxpoly_fail(char*expr, char*file, int line, const char*function)
18 if(!current_polygon) {
19 fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
23 void*md5 = init_md5();
26 gfxpolystroke_t*stroke = current_polygon->strokes;
27 for(;stroke;stroke=stroke->next) {
28 for(t=0;t<stroke->num_points;t++) {
29 update_md5(md5, (unsigned char*)&stroke->points[t].x, sizeof(stroke->points[t].x));
30 update_md5(md5, (unsigned char*)&stroke->points[t].y, sizeof(stroke->points[t].y));
34 char filename[32+4+1];
36 sprintf(filename, "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x.ps",
37 h[0],h[1],h[2],h[3],h[4],h[5],h[6],h[7],h[8],h[9],h[10],h[11],h[12],h[13],h[14],h[15]);
39 fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
40 fprintf(stderr, "I'm saving a debug file \"%s\" to the current directory.\n", filename);
42 gfxpoly_save(current_polygon, filename);
46 static char point_equals(const void*o1, const void*o2)
48 const point_t*p1 = o1;
49 const point_t*p2 = o2;
50 return p1->x == p2->x && p1->y == p2->y;
52 static unsigned int point_hash(const void*o)
57 static void* point_dup(const void*o)
60 point_t*n = malloc(sizeof(point_t));
65 static void point_free(void*o)
72 static type_t point_type = {
79 typedef struct _event {
86 /* compare_events_simple differs from compare_events in that it schedules
87 events from left to right regardless of type. It's only used in horizontal
88 processing, in order to get an x-wise sorting of the current scanline */
89 static inline int compare_events_simple(const void*_a,const void*_b)
91 event_t* a = (event_t*)_a;
92 event_t* b = (event_t*)_b;
93 int d = b->p.y - a->p.y;
100 static inline int compare_events(const void*_a,const void*_b)
102 event_t* a = (event_t*)_a;
103 event_t* b = (event_t*)_b;
104 int d = b->p.y - a->p.y;
106 /* we need to schedule end after intersect (so that a segment about
107 to end has a chance to tear up a few other segs first) and start
108 events after end (in order not to confuse the intersection check, which
109 assumes there's an actual y overlap between active segments, and
110 because ending segments in the active list make it difficult to insert
111 starting segments at the right position)).
112 Horizontal lines come last, because the only purpose
113 they have is to create snapping coordinates for the segments (still)
114 existing in this scanline.
116 d = b->type - a->type;
120 /* I don't see any reason why we would need to order by x- at least as long
121 as we do horizontal lines in a seperate pass */
122 //d = b->p.x - a->p.x;
126 #define COMPARE_EVENTS(x,y) (compare_events(x,y)>0)
127 #define COMPARE_EVENTS_SIMPLE(x,y) (compare_events_simple(x,y)>0)
128 HEAP_DEFINE(queue,event_t,COMPARE_EVENTS);
129 HEAP_DEFINE(hqueue,event_t,COMPARE_EVENTS_SIMPLE);
131 typedef struct _status {
137 windcontext_t*context;
138 segment_t*ending_segments;
141 dict_t*seen_crossings; //list of crossing we saw so far
142 dict_t*intersecting_segs; //list of segments intersecting in this scanline
143 dict_t*segs_with_point; //lists of segments that received a point in this scanline
148 int gfxpoly_size(gfxpoly_t*poly)
152 gfxpolystroke_t*stroke = poly->strokes;
153 for(;stroke;stroke=stroke->next) {
154 edges += stroke->num_points-1;
159 char gfxpoly_check(gfxpoly_t*poly)
161 dict_t*d = dict_new2(&point_type);
163 gfxpolystroke_t*stroke = poly->strokes;
164 for(;stroke;stroke=stroke->next) {
165 for(s=0;s<stroke->num_points;s++) {
166 point_t p = stroke->points[s];
167 int num = (s>=1 && s<stroke->num_points-1)?2:1; // mid points are two points (start+end)
168 if(!dict_contains(d, &p)) {
169 dict_put(d, &p, (void*)(ptroff_t)num);
171 int count = (ptroff_t)dict_lookup(d, &p);
174 dict_put(d, &p, (void*)(ptroff_t)count);
178 DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
179 int count = (ptroff_t)c;
181 fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count);
190 void gfxpoly_dump(gfxpoly_t*poly)
193 double g = poly->gridsize;
194 fprintf(stderr, "polyon %08x (gridsize: %f)\n", poly, poly->gridsize);
195 gfxpolystroke_t*stroke = poly->strokes;
196 for(;stroke;stroke=stroke->next) {
197 fprintf(stderr, "%08x", stroke);
198 for(s=0;s<stroke->num_points-1;s++) {
199 point_t a = stroke->points[s];
200 point_t b = stroke->points[s+1];
201 fprintf(stderr, "%s (%f,%f) -> (%f,%f)%s\n", s?" ":"", a.x*g, a.y*g, b.x*g, b.y*g,
202 s==stroke->num_points-2?"]":"");
207 void gfxpoly_save(gfxpoly_t*poly, const char*filename)
209 FILE*fi = fopen(filename, "wb");
210 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
211 fprintf(fi, "%% begin\n");
213 gfxpolystroke_t*stroke = poly->strokes;
214 for(;stroke;stroke=stroke->next) {
215 fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
216 point_t p = stroke->points[0];
217 fprintf(fi, "%d %d moveto\n", p.x, p.y);
218 for(s=1;s<stroke->num_points;s++) {
219 p = stroke->points[s];
220 fprintf(fi, "%d %d lineto\n", p.x, p.y);
222 fprintf(fi, "stroke\n");
224 fprintf(fi, "showpage\n");
228 inline static event_t* event_new()
230 event_t*e = rfx_calloc(sizeof(event_t));
233 inline static void event_free(event_t*e)
238 static void event_dump(event_t*e)
240 if(e->type == EVENT_HORIZONTAL) {
241 fprintf(stderr, "Horizontal [%d] (%d,%d) -> (%d,%d)\n", e->s1->nr, e->s1->a.x, e->s1->a.y, e->s1->b.x, e->s1->b.y);
242 } else if(e->type == EVENT_START) {
243 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
244 } else if(e->type == EVENT_END) {
245 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
246 } else if(e->type == EVENT_CROSS) {
247 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
253 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
254 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
256 static void segment_dump(segment_t*s)
258 fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
259 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k,
260 (double)s->delta.x / s->delta.y);
263 static void segment_init(segment_t*s, int32_t x1, int32_t y1, int32_t x2, int32_t y2, int polygon_nr, segment_dir_t dir)
269 /* We need to make sure horizontal segments always go from left to right.
270 "up/down" for horizontal segments is handled by "rotating"
271 them 90° anticlockwise in screen coordinates (tilt your head to
277 int32_t x = x1;x1=x2;x2=x;
278 int32_t y = y1;y1=y2;y2=y;
285 s->k = (double)x1*y2-(double)x2*y1;
286 s->left = s->right = 0;
289 s->minx = min32(x1,x2);
290 s->maxx = max32(x1,x2);
293 s->polygon_nr = polygon_nr;
294 static int segment_count=0;
295 s->nr = segment_count++;
298 assert(LINE_EQ(s->a, s) == 0);
299 assert(LINE_EQ(s->b, s) == 0);
301 /* check that all signs are in order:
309 p.x = min32(s->a.x, s->b.x);
310 assert(LINE_EQ(p, s) <= 0);
311 p.x = max32(s->a.x, s->b.x);
312 assert(LINE_EQ(p, s) >= 0);
315 #ifndef DONT_REMEMBER_CROSSINGS
316 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
320 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
322 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
323 segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
327 static void segment_clear(segment_t*s)
329 #ifndef DONT_REMEMBER_CROSSINGS
330 dict_clear(&s->scheduled_crossings);
333 static void segment_destroy(segment_t*s)
339 static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*stroke, int polygon_nr, int pos)
344 /* we need to queue multiple segments at once because we need to process start events
345 before horizontal events */
346 while(pos < stroke->num_points-1) {
347 assert(stroke->points[pos].y <= stroke->points[pos+1].y);
348 s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
355 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (stroke %08x, %d more to come)\n",
356 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
357 s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos);
359 event_t* e = event_new();
360 e->type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
365 if(queue) queue_put(queue, e);
366 else hqueue_put(hqueue, e);
368 if(e->type != EVENT_HORIZONTAL) {
374 fprintf(stderr, "attaching contingency of stroke %08x to segment [%d] %s\n",
375 stroke, s, s->delta.y?"":"(horizontal)");
382 static void gfxpoly_enqueue(gfxpoly_t*p, queue_t*queue, hqueue_t*hqueue, int polygon_nr)
385 gfxpolystroke_t*stroke = p->strokes;
386 for(;stroke;stroke=stroke->next) {
387 assert(stroke->num_points > 1);
391 for(s=0;s<stroke->num_points-1;s++) {
392 assert(stroke->points[s].y <= stroke->points[s+1].y);
395 advance_stroke(queue, hqueue, stroke, polygon_nr, 0);
399 static void schedule_endpoint(status_t*status, segment_t*s)
401 // schedule end point of segment
402 assert(s->b.y > status->y);
403 event_t*e = event_new();
408 queue_put(&status->queue, e);
411 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
413 /* the code that's required (and the checks you can perform) before
414 it can be said with 100% certainty that we indeed have a valid crossing
415 amazes me every time. -mk */
418 assert(s1->right == s2);
419 assert(s2->left == s1);
420 int32_t miny1 = min32(s1->a.y,s1->b.y);
421 int32_t maxy1 = max32(s1->a.y,s1->b.y);
422 int32_t miny2 = min32(s2->a.y,s2->b.y);
423 int32_t maxy2 = max32(s2->a.y,s2->b.y);
424 int32_t minx1 = min32(s1->a.x,s1->b.x);
425 int32_t minx2 = min32(s2->a.x,s2->b.x);
426 int32_t maxx1 = max32(s1->a.x,s1->b.x);
427 int32_t maxx2 = max32(s2->a.x,s2->b.x);
428 /* check that precomputation is sane */
429 assert(minx1 == s1->minx && minx2 == s2->minx);
430 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
431 /* both segments are active, so this can't happen */
432 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
433 /* we know that right now, s2 is to the right of s1, so there's
434 no way the complete bounding box of s1 is to the right of s1 */
435 assert(!(s1->minx > s2->maxx));
436 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
439 if(s1->maxx <= s2->minx) {
441 fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
443 /* bounding boxes don't intersect */
447 #ifndef DONT_REMEMBER_CROSSINGS
448 if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
449 /* FIXME: this whole segment hashing thing is really slow */
451 fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
452 // DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
453 // fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
456 return; // we already know about this one
460 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
463 // lines are exactly on top of each other (ignored)
465 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
470 fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
472 /* lines are parallel */
477 double asign2 = LINE_EQ(s1->a, s2);
479 // segment1 touches segment2 in a single point (ignored)
481 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
485 double bsign2 = LINE_EQ(s1->b, s2);
487 // segment1 touches segment2 in a single point (ignored)
489 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
494 if(asign2<0 && bsign2<0) {
495 // segment1 is completely to the left of segment2
497 fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s1->nr, s2->nr);
501 if(asign2>0 && bsign2>0) {
502 // segment1 is completely to the right of segment2
503 #ifndef DONT_REMEMBER_CROSSINGS
507 fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s2->nr, s1->nr);
512 double asign1 = LINE_EQ(s2->a, s1);
514 // segment2 touches segment1 in a single point (ignored)
516 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
520 double bsign1 = LINE_EQ(s2->b, s1);
522 // segment2 touches segment1 in a single point (ignored)
524 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
529 if(asign1<0 && bsign1<0) {
530 // segment2 is completely to the left of segment1
531 #ifndef DONT_REMEMBER_CROSSINGS
535 fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s1->nr, s2->nr);
539 if(asign1>0 && bsign1>0) {
540 // segment2 is completely to the right of segment1
542 fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s2->nr, s1->nr);
547 #ifdef DONT_REMEMBER_CROSSINGS
548 /* s2 crosses s1 from *left* to *right*. This is a crossing we already processed-
549 there's not way s2 would be to the left of s1 otherwise */
550 if(asign1<0 && bsign1>0) return;
551 if(asign2>0 && bsign2<0) return;
554 assert(!(asign1<0 && bsign1>0));
555 assert(!(asign2>0 && bsign2<0));
557 /* TODO: should we precompute these? */
558 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
559 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
562 p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
563 p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
565 assert(p.y >= status->y);
567 assert(p.x >= s1->minx && p.x <= s1->maxx);
568 assert(p.x >= s2->minx && p.x <= s2->maxx);
573 #ifndef DONT_REMEMBER_CROSSINGS
574 assert(!dict_contains(status->seen_crossings, &pair));
575 dict_put(status->seen_crossings, &pair, 0);
579 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
582 #ifndef DONT_REMEMBER_CROSSINGS
583 /* we insert into each other's intersection history because these segments might switch
584 places and we still want to look them up quickly after they did */
585 dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
586 dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
589 event_t* e = event_new();
590 e->type = EVENT_CROSS;
594 queue_put(&status->queue, e);
598 static void exchange_two(status_t*status, event_t*e)
600 //exchange two segments in list
601 segment_t*s1 = e->s1;
602 segment_t*s2 = e->s2;
604 if(!dict_contains(status->intersecting_segs, s1))
605 dict_put(status->intersecting_segs, s1, 0);
606 if(!dict_contains(status->intersecting_segs, s2))
607 dict_put(status->intersecting_segs, s2, 0);
609 assert(s2->left == s1);
610 assert(s1->right == s2);
611 actlist_swap(status->actlist, s1, s2);
612 assert(s2->right == s1);
613 assert(s1->left == s2);
614 segment_t*left = s2->left;
615 segment_t*right = s1->right;
617 schedule_crossing(status, left, s2);
619 schedule_crossing(status, s1, right);
622 typedef struct _box {
623 point_t left1, left2, right1, right2;
625 static inline box_t box_new(int32_t x, int32_t y)
628 box.right1.x = box.right2.x = x;
629 box.left1.x = box.left2.x = x-1;
630 box.left1.y = box.right1.y = y-1;
631 box.left2.y = box.right2.y = y;
635 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
637 assert(s->pos.x != p.x || s->pos.y != p.y);
640 if(!dict_contains(status->segs_with_point, s))
641 dict_put(status->segs_with_point, s, 0);
642 assert(s->fs_out_ok);
647 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
648 s->pos.x, s->pos.y, p.x, p.y);
650 // omit horizontal lines
651 if(s->pos.y != p.y) {
655 status->writer.moveto(&status->writer, a.x, a.y);
656 status->writer.lineto(&status->writer, b.x, b.y);
660 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
666 typedef struct _segrange {
673 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
675 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
676 segment_t*min = range->segmin;
677 segment_t*max = range->segmax;
679 /* we need this because if two segments intersect exactly on
680 the scanline, segrange_test_segment_{min,max} can't tell which
681 one is smaller/larger */
682 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
685 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
691 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
694 /* we need to calculate the xpos anew (and can't use start coordinate or
695 intersection coordinate), because we need the xpos exactly at the end of
698 double x = XPOS(seg, y);
699 if(!range->segmin || x<range->xmin) {
704 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
707 double x = XPOS(seg, y);
708 if(!range->segmax || x>range->xmax) {
723 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
725 segment_t*first=0, *last = 0;
727 for(t=0;t<status->xrow->num;t++) {
728 box_t box = box_new(status->xrow->x[t], y);
729 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
731 seg = actlist_right(status->actlist, seg);
734 // this segment started in this scanline, ignore it
735 seg->changed = 1;last = seg;if(!first) {first=seg;}
736 } else if(seg->delta.x <= 0) {
737 // ignore segment w/ negative slope
739 last = seg;if(!first) {first=seg;}
740 double d1 = LINE_EQ(box.right1, seg);
741 double d2 = LINE_EQ(box.right2, seg);
744 insert_point_into_segment(status, seg, box.right2);
746 /* we unfortunately can't break here- the active list is sorted according
747 to the *bottom* of the scanline. hence pretty much everything that's still
748 coming might reach into our box */
755 segrange_test_segment_min(range, first, y);
756 segrange_test_segment_max(range, last, y);
766 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
768 segment_t*first=0, *last = 0;
770 for(t=status->xrow->num-1;t>=0;t--) {
771 box_t box = box_new(status->xrow->x[t], y);
772 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
776 // this segment started in this scanline, ignore it
777 seg->changed = 1;last = seg;if(!first) {first=seg;}
778 } else if(seg->delta.x > 0) {
779 // ignore segment w/ positive slope
781 last = seg;if(!first) {first=seg;}
782 double d1 = LINE_EQ(box.left1, seg);
783 double d2 = LINE_EQ(box.left2, seg);
786 insert_point_into_segment(status, seg, box.right2);
794 segrange_test_segment_min(range, last, y);
795 segrange_test_segment_max(range, first, y);
798 /* segments ending in the current scanline need xrow treatment like everything else.
799 (consider an intersection taking place just above a nearly horizontal segment
800 ending on the current scanline- the intersection would snap down *below* the
801 ending segment if we don't add the intersection point to the latter right away)
802 we need to treat ending segments seperately, however. we have to delete them from
803 the active list right away to make room for intersect operations (which might
804 still be in the current scanline- consider two 45° polygons and a vertical polygon
805 intersecting on an integer coordinate). but once they're no longer in the active list,
806 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
807 them to the active list just for point snapping would be overkill.
808 (One other option to consider, however, would be to create a new active list only
811 static void add_points_to_ending_segments(status_t*status, int32_t y)
813 segment_t*seg = status->ending_segments;
815 segment_t*next = seg->right;seg->right=0;
817 assert(seg->b.y == status->y);
819 if(status->xrow->num == 1) {
821 assert(seg->b.x == status->xrow->x[0]);
822 point_t p = {status->xrow->x[0], y};
823 insert_point_into_segment(status, seg, p);
826 int start=0,end=status->xrow->num,dir=1;
827 if(seg->delta.x < 0) {
828 start = status->xrow->num-1;
831 for(t=start;t!=end;t+=dir) {
832 box_t box = box_new(status->xrow->x[t], y);
833 double d0 = LINE_EQ(box.left1, seg);
834 double d1 = LINE_EQ(box.left2, seg);
835 double d2 = LINE_EQ(box.right1, seg);
836 double d3 = LINE_EQ(box.right2, seg);
837 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
838 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
839 insert_point_into_segment(status, seg, box.right2);
845 /* we *need* to find a point to insert. the segment's own end point
846 is in that list, for Pete's sake. */
850 // now that this is done, too, we can also finally free this segment
851 segment_destroy(seg);
854 status->ending_segments = 0;
857 static void recalculate_windings(status_t*status, segrange_t*range)
860 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
862 segrange_adjust_endpoints(range, status->y);
864 segment_t*s = range->segmin;
865 segment_t*end = range->segmax;
869 s = actlist_leftmost(status->actlist);
871 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
872 s == range->segmin?"S":(
873 s == range->segmax?"E":""));
876 fprintf(stderr, "\n");
880 /* test sanity: check that we don't have changed segments
881 outside of the given range */
882 s = actlist_leftmost(status->actlist);
883 while(s && s!=range->segmin) {
887 s = actlist_rightmost(status->actlist);
888 while(s && s!=range->segmax) {
892 /* in check mode, go through the whole interval so we can test
893 that all polygons where the fillstyle changed also have seg->changed=1 */
894 s = actlist_leftmost(status->actlist);
905 segment_t* left = actlist_left(status->actlist, s);
906 windstate_t wind = left?left->wind:status->windrule->start(status->context);
907 s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
908 fillstyle_t*fs_old = s->fs_out;
909 s->fs_out = status->windrule->diff(&wind, &s->wind);
912 fprintf(stderr, "[%d] %s/%d/%s/%s %s\n", s->nr, s->dir==DIR_UP?"up":"down", s->wind.wind_nr, s->wind.is_filled?"fill":"nofill", s->fs_out?"draw":"omit",
913 fs_old!=s->fs_out?"CHANGED":"");
915 assert(!(!s->changed && fs_old!=s->fs_out));
926 /* we need to handle horizontal lines in order to add points to segments
927 we otherwise would miss during the windrule re-evaluation */
928 static void intersect_with_horizontal(status_t*status, segment_t*h)
930 segment_t* left = actlist_find(status->actlist, h->a, h->a);
931 segment_t* right = actlist_find(status->actlist, h->b, h->b);
933 /* not strictly necessary, also done by the event */
934 xrow_add(status->xrow, h->a.x);
942 left = actlist_right(status->actlist, left); //first seg to the right of h->a
943 right = right->right; //first seg to the right of h->b
948 int32_t x = XPOS_INT(s, status->y);
950 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
958 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
959 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
960 xrow_add(status->xrow, x);
966 static void event_apply(status_t*status, event_t*e)
969 case EVENT_HORIZONTAL: {
974 intersect_with_horizontal(status, s);
975 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
976 segment_destroy(s);e->s1=0;
980 //delete segment from list
986 dict_del(status->intersecting_segs, s);
987 dict_del(status->segs_with_point, s);
988 assert(!dict_contains(status->intersecting_segs, s));
989 assert(!dict_contains(status->segs_with_point, s));
991 segment_t*left = s->left;
992 segment_t*right = s->right;
993 actlist_delete(status->actlist, s);
995 schedule_crossing(status, left, right);
997 /* schedule segment for xrow handling */
998 s->left = 0; s->right = status->ending_segments;
999 status->ending_segments = s;
1000 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1004 //insert segment into list
1008 segment_t*s = e->s1;
1009 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1010 actlist_insert(status->actlist, s->a, s->b, s);
1011 segment_t*left = s->left;
1012 segment_t*right = s->right;
1014 schedule_crossing(status, left, s);
1016 schedule_crossing(status, s, right);
1017 schedule_endpoint(status, s);
1021 // exchange two segments
1025 if(e->s1->right == e->s2) {
1026 assert(e->s2->left == e->s1);
1027 exchange_two(status, e);
1029 assert(e->s2->left != e->s1);
1031 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1033 #ifndef DONT_REMEMBER_CROSSINGS
1034 /* ignore this crossing for now (there are some line segments in between).
1035 it'll get rescheduled as soon as the "obstacles" are gone */
1036 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1037 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1038 assert(del1 && del2);
1044 #ifndef DONT_REMEMBER_CROSSINGS
1045 assert(dict_contains(status->seen_crossings, &pair));
1046 dict_del(status->seen_crossings, &pair);
1055 static void check_status(status_t*status)
1057 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1058 if((s->pos.x != s->b.x ||
1059 s->pos.y != s->b.y) &&
1060 !dict_contains(status->segs_with_point, s)) {
1061 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1063 s->delta.x<0?"-":"+",
1071 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1074 |..| |...........| | |
1075 |..| |...........| | |
1076 |..+ + +..| +--+ +--+
1077 |...........| |..| | |
1078 |...........| |..| | |
1082 fprintf(stderr, "========================================================================\n");
1085 hqueue_init(&hqueue);
1086 gfxpoly_enqueue(poly, 0, &hqueue, 0);
1088 actlist_t* actlist = actlist_new();
1090 event_t*e = hqueue_get(&hqueue);
1096 fprintf(stderr, "HORIZONTALS ----------------------------------- %d\n", y);
1097 actlist_dump(actlist, y-1);
1100 actlist_verify(actlist, y-1);
1103 if(fill && x != e->p.x) {
1105 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
1109 gfxpolystroke_t*stroke = rfx_calloc(sizeof(gfxpolystroke_t));
1110 stroke->next = poly->strokes;
1111 poly->strokes = stroke;
1113 stroke->num_points = 2;
1114 stroke->points = malloc(sizeof(point_t)*2);
1115 stroke->dir = DIR_UP; // FIXME
1119 /* we draw from low x to high x so that left/right fillstyles add up
1120 (because the horizontal line's fill style controls the area *below* the line)
1124 stroke->points[0] = a;
1125 stroke->points[1] = b;
1127 /* the output should always be intersection free polygons, so check this horizontal
1128 line isn't hacking through any segments in the active list */
1129 segment_t* start = actlist_find(actlist, b, b);
1130 segment_t* s = actlist_find(actlist, a, a);
1132 assert(s->a.y == y || s->b.y == y);
1138 segment_t*s = e->s1;
1142 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1143 actlist_insert(actlist, s->a, s->b, s);
1144 event_t* e = event_new();
1145 e->type = EVENT_END;
1149 hqueue_put(&hqueue, e);
1150 left = actlist_left(actlist, s);
1154 left = actlist_left(actlist, s);
1155 actlist_delete(actlist, s);
1156 advance_stroke(0, &hqueue, s->stroke, s->polygon_nr, s->stroke_pos);
1163 fill ^= 1;//(before.is_filled != after.is_filled);
1165 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d\n",
1166 y, e->type==EVENT_START?"start":"end",
1172 if(e->type == EVENT_END)
1176 e = hqueue_get(&hqueue);
1177 } while(e && y == e->p.y);
1179 assert(!fill); // check that polygon is not bleeding
1182 actlist_destroy(actlist);
1183 hqueue_destroy(&hqueue);
1186 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1188 current_polygon = poly;
1191 memset(&status, 0, sizeof(status_t));
1192 queue_init(&status.queue);
1193 gfxpoly_enqueue(poly, &status.queue, 0, /*polygon nr*/0);
1195 status.windrule = windrule;
1196 status.context = context;
1197 status.actlist = actlist_new();
1198 gfxpolywriter_init(&status.writer);
1199 status.writer.setgridsize(&status.writer, poly->gridsize);
1202 status.seen_crossings = dict_new2(&point_type);
1203 int32_t lasty=-0x80000000;
1206 status.xrow = xrow_new();
1208 event_t*e = queue_get(&status.queue);
1212 assert(status.y>=lasty);
1214 status.intersecting_segs = dict_new2(&ptr_type);
1215 status.segs_with_point = dict_new2(&ptr_type);
1219 fprintf(stderr, "----------------------------------- %d\n", status.y);
1220 actlist_dump(status.actlist, status.y-1);
1223 actlist_verify(status.actlist, status.y-1);
1225 xrow_reset(status.xrow);
1227 xrow_add(status.xrow, e->p.x);
1228 event_apply(&status, e);
1230 e = queue_get(&status.queue);
1231 } while(e && status.y == e->p.y);
1233 xrow_sort(status.xrow);
1235 memset(&range, 0, sizeof(range));
1237 actlist_dump(status.actlist, status.y);
1239 add_points_to_positively_sloped_segments(&status, status.y, &range);
1240 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1241 add_points_to_ending_segments(&status, status.y);
1243 recalculate_windings(&status, &range);
1245 check_status(&status);
1246 dict_destroy(status.intersecting_segs);
1247 dict_destroy(status.segs_with_point);
1251 dict_destroy(status.seen_crossings);
1253 actlist_destroy(status.actlist);
1254 queue_destroy(&status.queue);
1255 xrow_destroy(status.xrow);
1257 gfxpoly_t*p = (gfxpoly_t*)status.writer.finish(&status.writer);
1259 add_horizontals(p, &windrule_evenodd, context); // output is always even/odd