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 current_polygon = poly;
171 dict_t*d = dict_new2(&point_type);
173 gfxpolystroke_t*stroke = poly->strokes;
174 for(;stroke;stroke=stroke->next) {
175 for(s=0;s<stroke->num_points;s++) {
176 point_t p = stroke->points[s];
177 int num = (s>=1 && s<stroke->num_points-1)?2:1; // mid points are two points (start+end)
178 if(!dict_contains(d, &p)) {
179 dict_put(d, &p, (void*)(ptroff_t)num);
181 int count = (ptroff_t)dict_lookup(d, &p);
184 dict_put(d, &p, (void*)(ptroff_t)count);
188 DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
189 int count = (ptroff_t)c;
191 fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count);
200 void gfxpoly_dump(gfxpoly_t*poly)
203 double g = poly->gridsize;
204 fprintf(stderr, "polyon %08x (gridsize: %f)\n", poly, poly->gridsize);
205 gfxpolystroke_t*stroke = poly->strokes;
206 for(;stroke;stroke=stroke->next) {
207 fprintf(stderr, "%08x", stroke);
208 for(s=0;s<stroke->num_points-1;s++) {
209 point_t a = stroke->points[s];
210 point_t b = stroke->points[s+1];
211 fprintf(stderr, "%s (%f,%f) -> (%f,%f)%s\n", s?" ":"", a.x*g, a.y*g, b.x*g, b.y*g,
212 s==stroke->num_points-2?"]":"");
217 void gfxpoly_save(gfxpoly_t*poly, const char*filename)
219 FILE*fi = fopen(filename, "wb");
220 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
221 fprintf(fi, "%% begin\n");
223 gfxpolystroke_t*stroke = poly->strokes;
224 for(;stroke;stroke=stroke->next) {
225 fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
226 point_t p = stroke->points[0];
227 fprintf(fi, "%d %d moveto\n", p.x, p.y);
228 for(s=1;s<stroke->num_points;s++) {
229 p = stroke->points[s];
230 fprintf(fi, "%d %d lineto\n", p.x, p.y);
232 fprintf(fi, "stroke\n");
234 fprintf(fi, "showpage\n");
238 inline static event_t* event_new()
240 event_t*e = rfx_calloc(sizeof(event_t));
243 inline static void event_free(event_t*e)
248 static void event_dump(event_t*e)
250 if(e->type == EVENT_HORIZONTAL) {
251 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);
252 } else if(e->type == EVENT_START) {
253 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
254 } else if(e->type == EVENT_END) {
255 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
256 } else if(e->type == EVENT_CROSS) {
257 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
263 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
264 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
266 static void segment_dump(segment_t*s)
268 fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
269 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k,
270 (double)s->delta.x / s->delta.y);
273 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)
279 /* We need to make sure horizontal segments always go from left to right.
280 "up/down" for horizontal segments is handled by "rotating"
281 them 90° anticlockwise in screen coordinates (tilt your head to
287 int32_t x = x1;x1=x2;x2=x;
288 int32_t y = y1;y1=y2;y2=y;
295 s->k = (double)x1*y2-(double)x2*y1;
296 s->left = s->right = 0;
299 s->minx = min32(x1,x2);
300 s->maxx = max32(x1,x2);
303 s->polygon_nr = polygon_nr;
304 static int segment_count=0;
305 s->nr = segment_count++;
308 /* notice: on some systems (with some compilers), for the line
309 (1073741823,-1073741824)->(1073741823,1073741823)
310 we get LINE_EQ(s->a, s) == 1.
311 That's why we now clamp to 26 bit.
313 assert(LINE_EQ(s->a, s) == 0);
314 assert(LINE_EQ(s->b, s) == 0);
316 /* check that all signs are in order:
324 p.x = min32(s->a.x, s->b.x);
325 assert(LINE_EQ(p, s) <= 0);
326 p.x = max32(s->a.x, s->b.x);
327 assert(LINE_EQ(p, s) >= 0);
330 #ifndef DONT_REMEMBER_CROSSINGS
331 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
335 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
337 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
338 segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
342 static void segment_clear(segment_t*s)
344 #ifndef DONT_REMEMBER_CROSSINGS
345 dict_clear(&s->scheduled_crossings);
348 static void segment_destroy(segment_t*s)
354 static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*stroke, int polygon_nr, int pos)
359 /* we need to queue multiple segments at once because we need to process start events
360 before horizontal events */
361 while(pos < stroke->num_points-1) {
362 assert(stroke->points[pos].y <= stroke->points[pos+1].y);
363 s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
370 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (stroke %08x, %d more to come)\n",
371 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
372 s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos);
374 event_t* e = event_new();
375 e->type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
380 if(queue) queue_put(queue, e);
381 else hqueue_put(hqueue, e);
383 if(e->type != EVENT_HORIZONTAL) {
393 static void gfxpoly_enqueue(gfxpoly_t*p, queue_t*queue, hqueue_t*hqueue, int polygon_nr)
396 gfxpolystroke_t*stroke = p->strokes;
397 for(;stroke;stroke=stroke->next) {
398 assert(stroke->num_points > 1);
402 for(s=0;s<stroke->num_points-1;s++) {
403 assert(stroke->points[s].y <= stroke->points[s+1].y);
406 advance_stroke(queue, hqueue, stroke, polygon_nr, 0);
410 static void schedule_endpoint(status_t*status, segment_t*s)
412 // schedule end point of segment
413 assert(s->b.y > status->y);
414 event_t*e = event_new();
419 queue_put(&status->queue, e);
422 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
424 /* the code that's required (and the checks you can perform) before
425 it can be said with 100% certainty that we indeed have a valid crossing
426 amazes me every time. -mk */
429 assert(s1->right == s2);
430 assert(s2->left == s1);
431 int32_t miny1 = min32(s1->a.y,s1->b.y);
432 int32_t maxy1 = max32(s1->a.y,s1->b.y);
433 int32_t miny2 = min32(s2->a.y,s2->b.y);
434 int32_t maxy2 = max32(s2->a.y,s2->b.y);
435 int32_t minx1 = min32(s1->a.x,s1->b.x);
436 int32_t minx2 = min32(s2->a.x,s2->b.x);
437 int32_t maxx1 = max32(s1->a.x,s1->b.x);
438 int32_t maxx2 = max32(s2->a.x,s2->b.x);
439 /* check that precomputation is sane */
440 assert(minx1 == s1->minx && minx2 == s2->minx);
441 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
442 /* both segments are active, so this can't happen */
443 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
444 /* we know that right now, s2 is to the right of s1, so there's
445 no way the complete bounding box of s1 is to the right of s1 */
446 assert(!(s1->minx > s2->maxx));
447 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
450 if(s1->maxx <= s2->minx) {
452 fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
454 /* bounding boxes don't intersect */
458 #ifndef DONT_REMEMBER_CROSSINGS
459 if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
460 /* FIXME: this whole segment hashing thing is really slow */
462 fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
463 // DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
464 // fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
467 return; // we already know about this one
471 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
474 // lines are exactly on top of each other (ignored)
476 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
481 fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
483 /* lines are parallel */
488 double asign2 = LINE_EQ(s1->a, s2);
490 // segment1 touches segment2 in a single point (ignored)
492 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
496 double bsign2 = LINE_EQ(s1->b, s2);
498 // segment1 touches segment2 in a single point (ignored)
500 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
505 if(asign2<0 && bsign2<0) {
506 // segment1 is completely to the left of segment2
508 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);
512 if(asign2>0 && bsign2>0) {
513 // segment1 is completely to the right of segment2
514 #ifndef DONT_REMEMBER_CROSSINGS
518 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);
523 double asign1 = LINE_EQ(s2->a, s1);
525 // segment2 touches segment1 in a single point (ignored)
527 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
531 double bsign1 = LINE_EQ(s2->b, s1);
533 // segment2 touches segment1 in a single point (ignored)
535 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
540 if(asign1<0 && bsign1<0) {
541 // segment2 is completely to the left of segment1
542 #ifndef DONT_REMEMBER_CROSSINGS
546 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);
550 if(asign1>0 && bsign1>0) {
551 // segment2 is completely to the right of segment1
553 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);
558 #ifdef DONT_REMEMBER_CROSSINGS
559 /* s2 crosses s1 from *left* to *right*. This is a crossing we already processed-
560 there's not way s2 would be to the left of s1 otherwise */
561 if(asign1<0 && bsign1>0) return;
562 if(asign2>0 && bsign2<0) return;
565 assert(!(asign1<0 && bsign1>0));
566 assert(!(asign2>0 && bsign2<0));
568 /* TODO: should we precompute these? */
569 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
570 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
573 p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
574 p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
576 assert(p.y >= status->y);
578 assert(p.x >= s1->minx && p.x <= s1->maxx);
579 assert(p.x >= s2->minx && p.x <= s2->maxx);
584 #ifndef DONT_REMEMBER_CROSSINGS
585 assert(!dict_contains(status->seen_crossings, &pair));
586 dict_put(status->seen_crossings, &pair, 0);
590 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
593 #ifndef DONT_REMEMBER_CROSSINGS
594 /* we insert into each other's intersection history because these segments might switch
595 places and we still want to look them up quickly after they did */
596 dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
597 dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
600 event_t* e = event_new();
601 e->type = EVENT_CROSS;
605 queue_put(&status->queue, e);
609 static void exchange_two(status_t*status, event_t*e)
611 //exchange two segments in list
612 segment_t*s1 = e->s1;
613 segment_t*s2 = e->s2;
615 if(!dict_contains(status->intersecting_segs, s1))
616 dict_put(status->intersecting_segs, s1, 0);
617 if(!dict_contains(status->intersecting_segs, s2))
618 dict_put(status->intersecting_segs, s2, 0);
620 assert(s2->left == s1);
621 assert(s1->right == s2);
622 actlist_swap(status->actlist, s1, s2);
623 assert(s2->right == s1);
624 assert(s1->left == s2);
625 segment_t*left = s2->left;
626 segment_t*right = s1->right;
628 schedule_crossing(status, left, s2);
630 schedule_crossing(status, s1, right);
633 typedef struct _box {
634 point_t left1, left2, right1, right2;
636 static inline box_t box_new(int32_t x, int32_t y)
639 box.right1.x = box.right2.x = x;
640 box.left1.x = box.left2.x = x-1;
641 box.left1.y = box.right1.y = y-1;
642 box.left2.y = box.right2.y = y;
646 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
648 assert(s->pos.x != p.x || s->pos.y != p.y);
651 if(!dict_contains(status->segs_with_point, s))
652 dict_put(status->segs_with_point, s, 0);
653 assert(s->fs_out_ok);
658 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
659 s->pos.x, s->pos.y, p.x, p.y);
661 /* XXX we probably will never output circular/anticircular polygons, but if
662 we do, we would need to set the segment direction here */
663 fillstyle_t*fs = s->fs_out;
665 // omit horizontal lines
666 if(s->pos.y != p.y) {
671 gfxpolystroke_t*stroke = status->strokes;
673 point_t p = stroke->points[stroke->num_points-1];
674 if(p.x == a.x && p.y == a.y && stroke->fs == fs)
676 stroke = stroke->next;
679 stroke = rfx_calloc(sizeof(gfxpolystroke_t));
680 stroke->dir = DIR_DOWN;
682 stroke->next = status->strokes;
683 status->strokes = stroke;
684 stroke->points_size = 2;
685 stroke->points = rfx_calloc(sizeof(point_t)*stroke->points_size);
686 stroke->points[0] = a;
687 stroke->num_points = 1;
688 } else if(stroke->num_points == stroke->points_size) {
689 stroke->points_size *= 2;
690 stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size);
692 stroke->points[stroke->num_points++] = b;
696 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
702 typedef struct _segrange {
709 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
711 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
712 segment_t*min = range->segmin;
713 segment_t*max = range->segmax;
715 /* we need this because if two segments intersect exactly on
716 the scanline, segrange_test_segment_{min,max} can't tell which
717 one is smaller/larger */
718 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
721 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
727 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
730 /* we need to calculate the xpos anew (and can't use start coordinate or
731 intersection coordinate), because we need the xpos exactly at the end of
734 double x = XPOS(seg, y);
735 if(!range->segmin || x<range->xmin) {
740 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
743 double x = XPOS(seg, y);
744 if(!range->segmax || x>range->xmax) {
759 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
761 segment_t*first=0, *last = 0;
763 for(t=0;t<status->xrow->num;t++) {
764 box_t box = box_new(status->xrow->x[t], y);
765 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
767 seg = actlist_right(status->actlist, seg);
770 // this segment started in this scanline, ignore it
771 seg->changed = 1;last = seg;if(!first) {first=seg;}
772 } else if(seg->delta.x <= 0) {
773 // ignore segment w/ negative slope
775 last = seg;if(!first) {first=seg;}
776 double d1 = LINE_EQ(box.right1, seg);
777 double d2 = LINE_EQ(box.right2, seg);
780 insert_point_into_segment(status, seg, box.right2);
782 /* we unfortunately can't break here- the active list is sorted according
783 to the *bottom* of the scanline. hence pretty much everything that's still
784 coming might reach into our box */
791 segrange_test_segment_min(range, first, y);
792 segrange_test_segment_max(range, last, y);
802 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
804 segment_t*first=0, *last = 0;
806 for(t=status->xrow->num-1;t>=0;t--) {
807 box_t box = box_new(status->xrow->x[t], y);
808 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
812 // this segment started in this scanline, ignore it
813 seg->changed = 1;last = seg;if(!first) {first=seg;}
814 } else if(seg->delta.x > 0) {
815 // ignore segment w/ positive slope
817 last = seg;if(!first) {first=seg;}
818 double d1 = LINE_EQ(box.left1, seg);
819 double d2 = LINE_EQ(box.left2, seg);
822 insert_point_into_segment(status, seg, box.right2);
830 segrange_test_segment_min(range, last, y);
831 segrange_test_segment_max(range, first, y);
834 /* segments ending in the current scanline need xrow treatment like everything else.
835 (consider an intersection taking place just above a nearly horizontal segment
836 ending on the current scanline- the intersection would snap down *below* the
837 ending segment if we don't add the intersection point to the latter right away)
838 we need to treat ending segments seperately, however. we have to delete them from
839 the active list right away to make room for intersect operations (which might
840 still be in the current scanline- consider two 45° polygons and a vertical polygon
841 intersecting on an integer coordinate). but once they're no longer in the active list,
842 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
843 them to the active list just for point snapping would be overkill.
844 (One other option to consider, however, would be to create a new active list only
847 static void add_points_to_ending_segments(status_t*status, int32_t y)
849 segment_t*seg = status->ending_segments;
851 segment_t*next = seg->right;seg->right=0;
853 assert(seg->b.y == status->y);
855 if(status->xrow->num == 1) {
857 assert(seg->b.x == status->xrow->x[0]);
858 point_t p = {status->xrow->x[0], y};
859 insert_point_into_segment(status, seg, p);
862 int start=0,end=status->xrow->num,dir=1;
863 if(seg->delta.x < 0) {
864 start = status->xrow->num-1;
867 for(t=start;t!=end;t+=dir) {
868 box_t box = box_new(status->xrow->x[t], y);
869 double d0 = LINE_EQ(box.left1, seg);
870 double d1 = LINE_EQ(box.left2, seg);
871 double d2 = LINE_EQ(box.right1, seg);
872 double d3 = LINE_EQ(box.right2, seg);
873 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
874 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
875 insert_point_into_segment(status, seg, box.right2);
881 /* we *need* to find a point to insert. the segment's own end point
882 is in that list, for Pete's sake. */
886 // now that this is done, too, we can also finally free this segment
887 segment_destroy(seg);
890 status->ending_segments = 0;
893 static void recalculate_windings(status_t*status, segrange_t*range)
896 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
898 segrange_adjust_endpoints(range, status->y);
900 segment_t*s = range->segmin;
901 segment_t*end = range->segmax;
905 s = actlist_leftmost(status->actlist);
907 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
908 s == range->segmin?"S":(
909 s == range->segmax?"E":""));
912 fprintf(stderr, "\n");
916 /* test sanity: check that we don't have changed segments
917 outside of the given range */
918 s = actlist_leftmost(status->actlist);
919 while(s && s!=range->segmin) {
923 s = actlist_rightmost(status->actlist);
924 while(s && s!=range->segmax) {
928 /* in check mode, go through the whole interval so we can test
929 that all polygons where the fillstyle changed also have seg->changed=1 */
930 s = actlist_leftmost(status->actlist);
941 segment_t* left = actlist_left(status->actlist, s);
942 windstate_t wind = left?left->wind:status->windrule->start(status->context);
943 s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
944 fillstyle_t*fs_old = s->fs_out;
945 s->fs_out = status->windrule->diff(&wind, &s->wind);
948 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",
949 fs_old?"draw":"omit", s->fs_out?"draw":"omit",
950 fs_old!=s->fs_out?"CHANGED":"");
952 assert(!(!s->changed && fs_old!=s->fs_out));
963 /* we need to handle horizontal lines in order to add points to segments
964 we otherwise would miss during the windrule re-evaluation */
965 static void intersect_with_horizontal(status_t*status, segment_t*h)
967 segment_t* left = actlist_find(status->actlist, h->a, h->a);
968 segment_t* right = actlist_find(status->actlist, h->b, h->b);
970 /* not strictly necessary, also done by the event */
971 xrow_add(status->xrow, h->a.x);
979 left = actlist_right(status->actlist, left); //first seg to the right of h->a
980 right = right->right; //first seg to the right of h->b
985 int32_t x = XPOS_INT(s, status->y);
987 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
995 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
996 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
997 xrow_add(status->xrow, x);
1003 static void event_apply(status_t*status, event_t*e)
1006 case EVENT_HORIZONTAL: {
1007 segment_t*s = e->s1;
1011 intersect_with_horizontal(status, s);
1012 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1013 segment_destroy(s);e->s1=0;
1017 //delete segment from list
1018 segment_t*s = e->s1;
1023 dict_del(status->intersecting_segs, s);
1024 dict_del(status->segs_with_point, s);
1025 assert(!dict_contains(status->intersecting_segs, s));
1026 assert(!dict_contains(status->segs_with_point, s));
1028 segment_t*left = s->left;
1029 segment_t*right = s->right;
1030 actlist_delete(status->actlist, s);
1032 schedule_crossing(status, left, right);
1034 /* schedule segment for xrow handling */
1035 s->left = 0; s->right = status->ending_segments;
1036 status->ending_segments = s;
1037 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1041 //insert segment into list
1045 segment_t*s = e->s1;
1046 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1047 actlist_insert(status->actlist, s->a, s->b, s);
1048 segment_t*left = s->left;
1049 segment_t*right = s->right;
1051 schedule_crossing(status, left, s);
1053 schedule_crossing(status, s, right);
1054 schedule_endpoint(status, s);
1058 // exchange two segments
1062 if(e->s1->right == e->s2) {
1063 assert(e->s2->left == e->s1);
1064 exchange_two(status, e);
1066 assert(e->s2->left != e->s1);
1068 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1070 #ifndef DONT_REMEMBER_CROSSINGS
1071 /* ignore this crossing for now (there are some line segments in between).
1072 it'll get rescheduled as soon as the "obstacles" are gone */
1073 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1074 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1075 assert(del1 && del2);
1081 #ifndef DONT_REMEMBER_CROSSINGS
1082 assert(dict_contains(status->seen_crossings, &pair));
1083 dict_del(status->seen_crossings, &pair);
1092 static void check_status(status_t*status)
1094 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1095 if((s->pos.x != s->b.x ||
1096 s->pos.y != s->b.y) &&
1097 !dict_contains(status->segs_with_point, s)) {
1098 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1100 s->delta.x<0?"-":"+",
1108 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1111 |..| |...........| | |
1112 |..| |...........| | |
1113 |..+ + +..| +--+ +--+
1114 |...........| |..| | |
1115 |...........| |..| | |
1119 fprintf(stderr, "========================================================================\n");
1122 hqueue_init(&hqueue);
1123 gfxpoly_enqueue(poly, 0, &hqueue, 0);
1125 actlist_t* actlist = actlist_new();
1127 event_t*e = hqueue_get(&hqueue);
1133 fprintf(stderr, "HORIZONTALS ----------------------------------- %d\n", y);
1134 actlist_dump(actlist, y-1);
1137 actlist_verify(actlist, y-1);
1140 if(fill && x != e->p.x) {
1142 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
1146 gfxpolystroke_t*stroke = rfx_calloc(sizeof(gfxpolystroke_t));
1147 stroke->next = poly->strokes;
1148 poly->strokes = stroke;
1150 stroke->num_points = 2;
1151 stroke->points = malloc(sizeof(point_t)*2);
1152 stroke->dir = DIR_UP; // FIXME
1156 /* we draw from low x to high x so that left/right fillstyles add up
1157 (because the horizontal line's fill style controls the area *below* the line)
1161 stroke->points[0] = a;
1162 stroke->points[1] = b;
1164 /* the output should always be intersection free polygons, so check this horizontal
1165 line isn't hacking through any segments in the active list */
1166 segment_t* start = actlist_find(actlist, b, b);
1167 segment_t* s = actlist_find(actlist, a, a);
1169 assert(s->a.y == y || s->b.y == y);
1175 segment_t*s = e->s1;
1179 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1180 actlist_insert(actlist, s->a, s->b, s);
1181 event_t* e = event_new();
1182 e->type = EVENT_END;
1186 hqueue_put(&hqueue, e);
1187 left = actlist_left(actlist, s);
1191 left = actlist_left(actlist, s);
1192 actlist_delete(actlist, s);
1193 advance_stroke(0, &hqueue, s->stroke, s->polygon_nr, s->stroke_pos);
1200 fill ^= 1;//(before.is_filled != after.is_filled);
1202 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d\n",
1203 y, e->type==EVENT_START?"start":"end",
1209 if(e->type == EVENT_END)
1213 e = hqueue_get(&hqueue);
1214 } while(e && y == e->p.y);
1217 char bleeding = fill;
1222 actlist_destroy(actlist);
1223 hqueue_destroy(&hqueue);
1226 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly1, gfxpoly_t*poly2, windrule_t*windrule, windcontext_t*context)
1228 current_polygon = poly1;
1231 memset(&status, 0, sizeof(status_t));
1232 queue_init(&status.queue);
1233 gfxpoly_enqueue(poly1, &status.queue, 0, /*polygon nr*/0);
1235 assert(poly1->gridsize == poly2->gridsize);
1236 gfxpoly_enqueue(poly2, &status.queue, 0, /*polygon nr*/1);
1239 status.windrule = windrule;
1240 status.context = context;
1241 status.actlist = actlist_new();
1244 status.seen_crossings = dict_new2(&point_type);
1245 int32_t lasty=-0x80000000;
1248 status.xrow = xrow_new();
1250 event_t*e = queue_get(&status.queue);
1254 assert(status.y>=lasty);
1256 status.intersecting_segs = dict_new2(&ptr_type);
1257 status.segs_with_point = dict_new2(&ptr_type);
1261 fprintf(stderr, "----------------------------------- %d\n", status.y);
1262 actlist_dump(status.actlist, status.y-1);
1265 actlist_verify(status.actlist, status.y-1);
1267 xrow_reset(status.xrow);
1269 xrow_add(status.xrow, e->p.x);
1270 event_apply(&status, e);
1272 e = queue_get(&status.queue);
1273 } while(e && status.y == e->p.y);
1275 xrow_sort(status.xrow);
1277 memset(&range, 0, sizeof(range));
1279 actlist_dump(status.actlist, status.y);
1281 add_points_to_positively_sloped_segments(&status, status.y, &range);
1282 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1283 add_points_to_ending_segments(&status, status.y);
1285 recalculate_windings(&status, &range);
1287 check_status(&status);
1288 dict_destroy(status.intersecting_segs);
1289 dict_destroy(status.segs_with_point);
1293 dict_destroy(status.seen_crossings);
1295 actlist_destroy(status.actlist);
1296 queue_destroy(&status.queue);
1297 xrow_destroy(status.xrow);
1299 gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t));
1300 p->gridsize = poly1->gridsize;
1301 p->strokes = status.strokes;
1303 add_horizontals(p, &windrule_evenodd, context); // output is always even/odd
1307 static windcontext_t twopolygons = {2};
1308 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*p1, gfxpoly_t*p2)
1310 return gfxpoly_process(p1, p2, &windrule_intersect, &twopolygons);
1312 gfxpoly_t* gfxpoly_union(gfxpoly_t*p1, gfxpoly_t*p2)
1314 return gfxpoly_process(p1, p2, &windrule_union, &twopolygons);