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)
78 typedef struct _event {
85 /* compare_events_simple differs from compare_events in that it schedules
86 events from left to right regardless of type. It's only used in horizontal
87 processing, in order to get an x-wise sorting of the current scanline */
88 static inline int compare_events_simple(const void*_a,const void*_b)
90 event_t* a = (event_t*)_a;
91 event_t* b = (event_t*)_b;
92 int d = b->p.y - a->p.y;
99 static inline int compare_events(const void*_a,const void*_b)
101 event_t* a = (event_t*)_a;
102 event_t* b = (event_t*)_b;
103 int d = b->p.y - a->p.y;
105 /* we need to schedule end after intersect (so that a segment about
106 to end has a chance to tear up a few other segs first) and start
107 events after end (in order not to confuse the intersection check, which
108 assumes there's an actual y overlap between active segments, and
109 because ending segments in the active list make it difficult to insert
110 starting segments at the right position)).
111 Horizontal lines come last, because the only purpose
112 they have is to create snapping coordinates for the segments (still)
113 existing in this scanline.
115 d = b->type - a->type;
119 /* I don't see any reason why we would need to order by x- at least as long
120 as we do horizontal lines in a seperate pass */
121 //d = b->p.x - a->p.x;
125 #define COMPARE_EVENTS(x,y) (compare_events(x,y)>0)
126 #define COMPARE_EVENTS_SIMPLE(x,y) (compare_events_simple(x,y)>0)
127 HEAP_DEFINE(queue,event_t,COMPARE_EVENTS);
128 HEAP_DEFINE(hqueue,event_t,COMPARE_EVENTS_SIMPLE);
130 typedef struct _status {
136 windcontext_t*context;
137 segment_t*ending_segments;
139 gfxpolystroke_t*strokes;
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_num_segments(gfxpoly_t*poly)
150 gfxpolystroke_t*stroke = poly->strokes;
152 for(;stroke;stroke=stroke->next) {
157 int gfxpoly_size(gfxpoly_t*poly)
161 gfxpolystroke_t*stroke = poly->strokes;
162 for(;stroke;stroke=stroke->next) {
163 edges += stroke->num_points-1;
168 char gfxpoly_check(gfxpoly_t*poly)
170 dict_t*d = dict_new2(&point_type);
172 gfxpolystroke_t*stroke = poly->strokes;
173 for(;stroke;stroke=stroke->next) {
174 for(s=0;s<stroke->num_points;s++) {
175 point_t p = stroke->points[s];
176 int num = (s>=1 && s<stroke->num_points-1)?2:1; // mid points are two points (start+end)
177 if(!dict_contains(d, &p)) {
178 dict_put(d, &p, (void*)(ptroff_t)num);
180 int count = (ptroff_t)dict_lookup(d, &p);
183 dict_put(d, &p, (void*)(ptroff_t)count);
187 DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
188 int count = (ptroff_t)c;
190 fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count);
199 void gfxpoly_dump(gfxpoly_t*poly)
202 double g = poly->gridsize;
203 fprintf(stderr, "polyon %08x (gridsize: %f)\n", poly, poly->gridsize);
204 gfxpolystroke_t*stroke = poly->strokes;
205 for(;stroke;stroke=stroke->next) {
206 fprintf(stderr, "%08x", stroke);
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(stderr, "%s (%f,%f) -> (%f,%f)%s\n", s?" ":"", a.x*g, a.y*g, b.x*g, b.y*g,
211 s==stroke->num_points-2?"]":"");
216 void gfxpoly_save(gfxpoly_t*poly, const char*filename)
218 FILE*fi = fopen(filename, "wb");
219 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
220 fprintf(fi, "%% begin\n");
222 gfxpolystroke_t*stroke = poly->strokes;
223 for(;stroke;stroke=stroke->next) {
224 fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
225 point_t p = stroke->points[0];
226 fprintf(fi, "%d %d moveto\n", p.x, p.y);
227 for(s=1;s<stroke->num_points;s++) {
228 p = stroke->points[s];
229 fprintf(fi, "%d %d lineto\n", p.x, p.y);
231 fprintf(fi, "stroke\n");
233 fprintf(fi, "showpage\n");
237 inline static event_t* event_new()
239 event_t*e = rfx_calloc(sizeof(event_t));
242 inline static void event_free(event_t*e)
247 static void event_dump(event_t*e)
249 if(e->type == EVENT_HORIZONTAL) {
250 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);
251 } else if(e->type == EVENT_START) {
252 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
253 } else if(e->type == EVENT_END) {
254 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
255 } else if(e->type == EVENT_CROSS) {
256 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
262 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
263 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
265 static void segment_dump(segment_t*s)
267 fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
268 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k,
269 (double)s->delta.x / s->delta.y);
272 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)
278 /* We need to make sure horizontal segments always go from left to right.
279 "up/down" for horizontal segments is handled by "rotating"
280 them 90° anticlockwise in screen coordinates (tilt your head to
286 int32_t x = x1;x1=x2;x2=x;
287 int32_t y = y1;y1=y2;y2=y;
294 s->k = (double)x1*y2-(double)x2*y1;
295 s->left = s->right = 0;
298 s->minx = min32(x1,x2);
299 s->maxx = max32(x1,x2);
302 s->polygon_nr = polygon_nr;
303 static int segment_count=0;
304 s->nr = segment_count++;
307 assert(LINE_EQ(s->a, s) == 0);
308 assert(LINE_EQ(s->b, s) == 0);
310 /* check that all signs are in order:
318 p.x = min32(s->a.x, s->b.x);
319 assert(LINE_EQ(p, s) <= 0);
320 p.x = max32(s->a.x, s->b.x);
321 assert(LINE_EQ(p, s) >= 0);
324 #ifndef DONT_REMEMBER_CROSSINGS
325 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
329 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
331 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
332 segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
336 static void segment_clear(segment_t*s)
338 #ifndef DONT_REMEMBER_CROSSINGS
339 dict_clear(&s->scheduled_crossings);
342 static void segment_destroy(segment_t*s)
348 static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*stroke, int polygon_nr, int pos)
353 /* we need to queue multiple segments at once because we need to process start events
354 before horizontal events */
355 while(pos < stroke->num_points-1) {
356 assert(stroke->points[pos].y <= stroke->points[pos+1].y);
357 s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
364 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (stroke %08x, %d more to come)\n",
365 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
366 s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos);
368 event_t* e = event_new();
369 e->type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
374 if(queue) queue_put(queue, e);
375 else hqueue_put(hqueue, e);
377 if(e->type != EVENT_HORIZONTAL) {
387 static void gfxpoly_enqueue(gfxpoly_t*p, queue_t*queue, hqueue_t*hqueue, int polygon_nr)
390 gfxpolystroke_t*stroke = p->strokes;
391 for(;stroke;stroke=stroke->next) {
392 assert(stroke->num_points > 1);
396 for(s=0;s<stroke->num_points-1;s++) {
397 assert(stroke->points[s].y <= stroke->points[s+1].y);
400 advance_stroke(queue, hqueue, stroke, polygon_nr, 0);
404 static void schedule_endpoint(status_t*status, segment_t*s)
406 // schedule end point of segment
407 assert(s->b.y > status->y);
408 event_t*e = event_new();
413 queue_put(&status->queue, e);
416 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
418 /* the code that's required (and the checks you can perform) before
419 it can be said with 100% certainty that we indeed have a valid crossing
420 amazes me every time. -mk */
423 assert(s1->right == s2);
424 assert(s2->left == s1);
425 int32_t miny1 = min32(s1->a.y,s1->b.y);
426 int32_t maxy1 = max32(s1->a.y,s1->b.y);
427 int32_t miny2 = min32(s2->a.y,s2->b.y);
428 int32_t maxy2 = max32(s2->a.y,s2->b.y);
429 int32_t minx1 = min32(s1->a.x,s1->b.x);
430 int32_t minx2 = min32(s2->a.x,s2->b.x);
431 int32_t maxx1 = max32(s1->a.x,s1->b.x);
432 int32_t maxx2 = max32(s2->a.x,s2->b.x);
433 /* check that precomputation is sane */
434 assert(minx1 == s1->minx && minx2 == s2->minx);
435 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
436 /* both segments are active, so this can't happen */
437 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
438 /* we know that right now, s2 is to the right of s1, so there's
439 no way the complete bounding box of s1 is to the right of s1 */
440 assert(!(s1->minx > s2->maxx));
441 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
444 if(s1->maxx <= s2->minx) {
446 fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
448 /* bounding boxes don't intersect */
452 #ifndef DONT_REMEMBER_CROSSINGS
453 if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
454 /* FIXME: this whole segment hashing thing is really slow */
456 fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
457 // DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
458 // fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
461 return; // we already know about this one
465 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
468 // lines are exactly on top of each other (ignored)
470 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
475 fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
477 /* lines are parallel */
482 double asign2 = LINE_EQ(s1->a, s2);
484 // segment1 touches segment2 in a single point (ignored)
486 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
490 double bsign2 = LINE_EQ(s1->b, s2);
492 // segment1 touches segment2 in a single point (ignored)
494 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
499 if(asign2<0 && bsign2<0) {
500 // segment1 is completely to the left of segment2
502 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);
506 if(asign2>0 && bsign2>0) {
507 // segment1 is completely to the right of segment2
508 #ifndef DONT_REMEMBER_CROSSINGS
512 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);
517 double asign1 = LINE_EQ(s2->a, s1);
519 // segment2 touches segment1 in a single point (ignored)
521 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
525 double bsign1 = LINE_EQ(s2->b, s1);
527 // segment2 touches segment1 in a single point (ignored)
529 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
534 if(asign1<0 && bsign1<0) {
535 // segment2 is completely to the left of segment1
536 #ifndef DONT_REMEMBER_CROSSINGS
540 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);
544 if(asign1>0 && bsign1>0) {
545 // segment2 is completely to the right of segment1
547 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);
552 #ifdef DONT_REMEMBER_CROSSINGS
553 /* s2 crosses s1 from *left* to *right*. This is a crossing we already processed-
554 there's not way s2 would be to the left of s1 otherwise */
555 if(asign1<0 && bsign1>0) return;
556 if(asign2>0 && bsign2<0) return;
559 assert(!(asign1<0 && bsign1>0));
560 assert(!(asign2>0 && bsign2<0));
562 /* TODO: should we precompute these? */
563 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
564 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
567 p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
568 p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
570 assert(p.y >= status->y);
572 assert(p.x >= s1->minx && p.x <= s1->maxx);
573 assert(p.x >= s2->minx && p.x <= s2->maxx);
578 #ifndef DONT_REMEMBER_CROSSINGS
579 assert(!dict_contains(status->seen_crossings, &pair));
580 dict_put(status->seen_crossings, &pair, 0);
584 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
587 #ifndef DONT_REMEMBER_CROSSINGS
588 /* we insert into each other's intersection history because these segments might switch
589 places and we still want to look them up quickly after they did */
590 dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
591 dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
594 event_t* e = event_new();
595 e->type = EVENT_CROSS;
599 queue_put(&status->queue, e);
603 static void exchange_two(status_t*status, event_t*e)
605 //exchange two segments in list
606 segment_t*s1 = e->s1;
607 segment_t*s2 = e->s2;
609 if(!dict_contains(status->intersecting_segs, s1))
610 dict_put(status->intersecting_segs, s1, 0);
611 if(!dict_contains(status->intersecting_segs, s2))
612 dict_put(status->intersecting_segs, s2, 0);
614 assert(s2->left == s1);
615 assert(s1->right == s2);
616 actlist_swap(status->actlist, s1, s2);
617 assert(s2->right == s1);
618 assert(s1->left == s2);
619 segment_t*left = s2->left;
620 segment_t*right = s1->right;
622 schedule_crossing(status, left, s2);
624 schedule_crossing(status, s1, right);
627 typedef struct _box {
628 point_t left1, left2, right1, right2;
630 static inline box_t box_new(int32_t x, int32_t y)
633 box.right1.x = box.right2.x = x;
634 box.left1.x = box.left2.x = x-1;
635 box.left1.y = box.right1.y = y-1;
636 box.left2.y = box.right2.y = y;
640 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
642 assert(s->pos.x != p.x || s->pos.y != p.y);
645 if(!dict_contains(status->segs_with_point, s))
646 dict_put(status->segs_with_point, s, 0);
647 assert(s->fs_out_ok);
652 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
653 s->pos.x, s->pos.y, p.x, p.y);
655 /* XXX we probably will never output circular/anticircular polygons, but if
656 we do, we would need to set the segment direction here */
657 fillstyle_t*fs = s->fs_out;
659 // omit horizontal lines
660 if(s->pos.y != p.y) {
665 gfxpolystroke_t*stroke = status->strokes;
667 point_t p = stroke->points[stroke->num_points-1];
668 if(p.x == a.x && p.y == a.y && stroke->fs == fs)
670 stroke = stroke->next;
673 stroke = rfx_calloc(sizeof(gfxpolystroke_t));
674 stroke->dir = DIR_DOWN;
676 stroke->next = status->strokes;
677 status->strokes = stroke;
678 stroke->points_size = 2;
679 stroke->points = rfx_calloc(sizeof(point_t)*stroke->points_size);
680 stroke->points[0] = a;
681 stroke->num_points = 1;
682 } else if(stroke->num_points == stroke->points_size) {
683 stroke->points_size *= 2;
684 stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size);
686 stroke->points[stroke->num_points++] = b;
690 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
696 typedef struct _segrange {
703 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
705 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
706 segment_t*min = range->segmin;
707 segment_t*max = range->segmax;
709 /* we need this because if two segments intersect exactly on
710 the scanline, segrange_test_segment_{min,max} can't tell which
711 one is smaller/larger */
712 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
715 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
721 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
724 /* we need to calculate the xpos anew (and can't use start coordinate or
725 intersection coordinate), because we need the xpos exactly at the end of
728 double x = XPOS(seg, y);
729 if(!range->segmin || x<range->xmin) {
734 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
737 double x = XPOS(seg, y);
738 if(!range->segmax || x>range->xmax) {
753 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
755 segment_t*first=0, *last = 0;
757 for(t=0;t<status->xrow->num;t++) {
758 box_t box = box_new(status->xrow->x[t], y);
759 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
761 seg = actlist_right(status->actlist, seg);
764 // this segment started in this scanline, ignore it
765 seg->changed = 1;last = seg;if(!first) {first=seg;}
766 } else if(seg->delta.x <= 0) {
767 // ignore segment w/ negative slope
769 last = seg;if(!first) {first=seg;}
770 double d1 = LINE_EQ(box.right1, seg);
771 double d2 = LINE_EQ(box.right2, seg);
774 insert_point_into_segment(status, seg, box.right2);
776 /* we unfortunately can't break here- the active list is sorted according
777 to the *bottom* of the scanline. hence pretty much everything that's still
778 coming might reach into our box */
785 segrange_test_segment_min(range, first, y);
786 segrange_test_segment_max(range, last, y);
796 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
798 segment_t*first=0, *last = 0;
800 for(t=status->xrow->num-1;t>=0;t--) {
801 box_t box = box_new(status->xrow->x[t], y);
802 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
806 // this segment started in this scanline, ignore it
807 seg->changed = 1;last = seg;if(!first) {first=seg;}
808 } else if(seg->delta.x > 0) {
809 // ignore segment w/ positive slope
811 last = seg;if(!first) {first=seg;}
812 double d1 = LINE_EQ(box.left1, seg);
813 double d2 = LINE_EQ(box.left2, seg);
816 insert_point_into_segment(status, seg, box.right2);
824 segrange_test_segment_min(range, last, y);
825 segrange_test_segment_max(range, first, y);
828 /* segments ending in the current scanline need xrow treatment like everything else.
829 (consider an intersection taking place just above a nearly horizontal segment
830 ending on the current scanline- the intersection would snap down *below* the
831 ending segment if we don't add the intersection point to the latter right away)
832 we need to treat ending segments seperately, however. we have to delete them from
833 the active list right away to make room for intersect operations (which might
834 still be in the current scanline- consider two 45° polygons and a vertical polygon
835 intersecting on an integer coordinate). but once they're no longer in the active list,
836 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
837 them to the active list just for point snapping would be overkill.
838 (One other option to consider, however, would be to create a new active list only
841 static void add_points_to_ending_segments(status_t*status, int32_t y)
843 segment_t*seg = status->ending_segments;
845 segment_t*next = seg->right;seg->right=0;
847 assert(seg->b.y == status->y);
849 if(status->xrow->num == 1) {
851 assert(seg->b.x == status->xrow->x[0]);
852 point_t p = {status->xrow->x[0], y};
853 insert_point_into_segment(status, seg, p);
856 int start=0,end=status->xrow->num,dir=1;
857 if(seg->delta.x < 0) {
858 start = status->xrow->num-1;
861 for(t=start;t!=end;t+=dir) {
862 box_t box = box_new(status->xrow->x[t], y);
863 double d0 = LINE_EQ(box.left1, seg);
864 double d1 = LINE_EQ(box.left2, seg);
865 double d2 = LINE_EQ(box.right1, seg);
866 double d3 = LINE_EQ(box.right2, seg);
867 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
868 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
869 insert_point_into_segment(status, seg, box.right2);
875 /* we *need* to find a point to insert. the segment's own end point
876 is in that list, for Pete's sake. */
880 // now that this is done, too, we can also finally free this segment
881 segment_destroy(seg);
884 status->ending_segments = 0;
887 static void recalculate_windings(status_t*status, segrange_t*range)
890 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
892 segrange_adjust_endpoints(range, status->y);
894 segment_t*s = range->segmin;
895 segment_t*end = range->segmax;
899 s = actlist_leftmost(status->actlist);
901 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
902 s == range->segmin?"S":(
903 s == range->segmax?"E":""));
906 fprintf(stderr, "\n");
910 /* test sanity: check that we don't have changed segments
911 outside of the given range */
912 s = actlist_leftmost(status->actlist);
913 while(s && s!=range->segmin) {
917 s = actlist_rightmost(status->actlist);
918 while(s && s!=range->segmax) {
922 /* in check mode, go through the whole interval so we can test
923 that all polygons where the fillstyle changed also have seg->changed=1 */
924 s = actlist_leftmost(status->actlist);
935 segment_t* left = actlist_left(status->actlist, s);
936 windstate_t wind = left?left->wind:status->windrule->start(status->context);
937 s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
938 fillstyle_t*fs_old = s->fs_out;
939 s->fs_out = status->windrule->diff(&wind, &s->wind);
942 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",
943 fs_old?"draw":"omit", s->fs_out?"draw":"omit",
944 fs_old!=s->fs_out?"CHANGED":"");
946 assert(!(!s->changed && fs_old!=s->fs_out));
957 /* we need to handle horizontal lines in order to add points to segments
958 we otherwise would miss during the windrule re-evaluation */
959 static void intersect_with_horizontal(status_t*status, segment_t*h)
961 segment_t* left = actlist_find(status->actlist, h->a, h->a);
962 segment_t* right = actlist_find(status->actlist, h->b, h->b);
964 /* not strictly necessary, also done by the event */
965 xrow_add(status->xrow, h->a.x);
973 left = actlist_right(status->actlist, left); //first seg to the right of h->a
974 right = right->right; //first seg to the right of h->b
979 int32_t x = XPOS_INT(s, status->y);
981 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
989 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
990 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
991 xrow_add(status->xrow, x);
997 static void event_apply(status_t*status, event_t*e)
1000 case EVENT_HORIZONTAL: {
1001 segment_t*s = e->s1;
1005 intersect_with_horizontal(status, s);
1006 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1007 segment_destroy(s);e->s1=0;
1011 //delete segment from list
1012 segment_t*s = e->s1;
1017 dict_del(status->intersecting_segs, s);
1018 dict_del(status->segs_with_point, s);
1019 assert(!dict_contains(status->intersecting_segs, s));
1020 assert(!dict_contains(status->segs_with_point, s));
1022 segment_t*left = s->left;
1023 segment_t*right = s->right;
1024 actlist_delete(status->actlist, s);
1026 schedule_crossing(status, left, right);
1028 /* schedule segment for xrow handling */
1029 s->left = 0; s->right = status->ending_segments;
1030 status->ending_segments = s;
1031 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1035 //insert segment into list
1039 segment_t*s = e->s1;
1040 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1041 actlist_insert(status->actlist, s->a, s->b, s);
1042 segment_t*left = s->left;
1043 segment_t*right = s->right;
1045 schedule_crossing(status, left, s);
1047 schedule_crossing(status, s, right);
1048 schedule_endpoint(status, s);
1052 // exchange two segments
1056 if(e->s1->right == e->s2) {
1057 assert(e->s2->left == e->s1);
1058 exchange_two(status, e);
1060 assert(e->s2->left != e->s1);
1062 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1064 #ifndef DONT_REMEMBER_CROSSINGS
1065 /* ignore this crossing for now (there are some line segments in between).
1066 it'll get rescheduled as soon as the "obstacles" are gone */
1067 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1068 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1069 assert(del1 && del2);
1075 #ifndef DONT_REMEMBER_CROSSINGS
1076 assert(dict_contains(status->seen_crossings, &pair));
1077 dict_del(status->seen_crossings, &pair);
1086 static void check_status(status_t*status)
1088 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1089 if((s->pos.x != s->b.x ||
1090 s->pos.y != s->b.y) &&
1091 !dict_contains(status->segs_with_point, s)) {
1092 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1094 s->delta.x<0?"-":"+",
1102 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1105 |..| |...........| | |
1106 |..| |...........| | |
1107 |..+ + +..| +--+ +--+
1108 |...........| |..| | |
1109 |...........| |..| | |
1113 fprintf(stderr, "========================================================================\n");
1116 hqueue_init(&hqueue);
1117 gfxpoly_enqueue(poly, 0, &hqueue, 0);
1119 actlist_t* actlist = actlist_new();
1121 event_t*e = hqueue_get(&hqueue);
1127 fprintf(stderr, "HORIZONTALS ----------------------------------- %d\n", y);
1128 actlist_dump(actlist, y-1);
1131 actlist_verify(actlist, y-1);
1134 if(fill && x != e->p.x) {
1136 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
1140 gfxpolystroke_t*stroke = rfx_calloc(sizeof(gfxpolystroke_t));
1141 stroke->next = poly->strokes;
1142 poly->strokes = stroke;
1144 stroke->num_points = 2;
1145 stroke->points = malloc(sizeof(point_t)*2);
1146 stroke->dir = DIR_UP; // FIXME
1150 /* we draw from low x to high x so that left/right fillstyles add up
1151 (because the horizontal line's fill style controls the area *below* the line)
1155 stroke->points[0] = a;
1156 stroke->points[1] = b;
1158 /* the output should always be intersection free polygons, so check this horizontal
1159 line isn't hacking through any segments in the active list */
1160 segment_t* start = actlist_find(actlist, b, b);
1161 segment_t* s = actlist_find(actlist, a, a);
1163 assert(s->a.y == y || s->b.y == y);
1169 segment_t*s = e->s1;
1173 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1174 actlist_insert(actlist, s->a, s->b, s);
1175 event_t* e = event_new();
1176 e->type = EVENT_END;
1180 hqueue_put(&hqueue, e);
1181 left = actlist_left(actlist, s);
1185 left = actlist_left(actlist, s);
1186 actlist_delete(actlist, s);
1187 advance_stroke(0, &hqueue, s->stroke, s->polygon_nr, s->stroke_pos);
1194 fill ^= 1;//(before.is_filled != after.is_filled);
1196 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d\n",
1197 y, e->type==EVENT_START?"start":"end",
1203 if(e->type == EVENT_END)
1207 e = hqueue_get(&hqueue);
1208 } while(e && y == e->p.y);
1211 char bleeding = fill;
1216 actlist_destroy(actlist);
1217 hqueue_destroy(&hqueue);
1220 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly1, gfxpoly_t*poly2, windrule_t*windrule, windcontext_t*context)
1222 current_polygon = poly1;
1225 memset(&status, 0, sizeof(status_t));
1226 queue_init(&status.queue);
1227 gfxpoly_enqueue(poly1, &status.queue, 0, /*polygon nr*/0);
1229 assert(poly1->gridsize == poly2->gridsize);
1230 gfxpoly_enqueue(poly2, &status.queue, 0, /*polygon nr*/1);
1233 status.windrule = windrule;
1234 status.context = context;
1235 status.actlist = actlist_new();
1238 status.seen_crossings = dict_new2(&point_type);
1239 int32_t lasty=-0x80000000;
1242 status.xrow = xrow_new();
1244 event_t*e = queue_get(&status.queue);
1248 assert(status.y>=lasty);
1250 status.intersecting_segs = dict_new2(&ptr_type);
1251 status.segs_with_point = dict_new2(&ptr_type);
1255 fprintf(stderr, "----------------------------------- %d\n", status.y);
1256 actlist_dump(status.actlist, status.y-1);
1259 actlist_verify(status.actlist, status.y-1);
1261 xrow_reset(status.xrow);
1263 xrow_add(status.xrow, e->p.x);
1264 event_apply(&status, e);
1266 e = queue_get(&status.queue);
1267 } while(e && status.y == e->p.y);
1269 xrow_sort(status.xrow);
1271 memset(&range, 0, sizeof(range));
1273 actlist_dump(status.actlist, status.y);
1275 add_points_to_positively_sloped_segments(&status, status.y, &range);
1276 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1277 add_points_to_ending_segments(&status, status.y);
1279 recalculate_windings(&status, &range);
1281 check_status(&status);
1282 dict_destroy(status.intersecting_segs);
1283 dict_destroy(status.segs_with_point);
1287 dict_destroy(status.seen_crossings);
1289 actlist_destroy(status.actlist);
1290 queue_destroy(&status.queue);
1291 xrow_destroy(status.xrow);
1293 gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t));
1294 p->gridsize = poly1->gridsize;
1295 p->strokes = status.strokes;
1297 add_horizontals(p, &windrule_evenodd, context); // output is always even/odd
1301 static windcontext_t twopolygons = {2};
1302 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*p1, gfxpoly_t*p2)
1304 return gfxpoly_process(p1, p2, &windrule_intersect, &twopolygons);
1306 gfxpoly_t* gfxpoly_union(gfxpoly_t*p1, gfxpoly_t*p2)
1308 return gfxpoly_process(p1, p2, &windrule_union, &twopolygons);