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 assert(LINE_EQ(s->a, s) == 0);
309 assert(LINE_EQ(s->b, s) == 0);
311 /* check that all signs are in order:
319 p.x = min32(s->a.x, s->b.x);
320 assert(LINE_EQ(p, s) <= 0);
321 p.x = max32(s->a.x, s->b.x);
322 assert(LINE_EQ(p, s) >= 0);
325 #ifndef DONT_REMEMBER_CROSSINGS
326 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
330 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
332 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
333 segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
337 static void segment_clear(segment_t*s)
339 #ifndef DONT_REMEMBER_CROSSINGS
340 dict_clear(&s->scheduled_crossings);
343 static void segment_destroy(segment_t*s)
349 static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*stroke, int polygon_nr, int pos)
354 /* we need to queue multiple segments at once because we need to process start events
355 before horizontal events */
356 while(pos < stroke->num_points-1) {
357 assert(stroke->points[pos].y <= stroke->points[pos+1].y);
358 s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
365 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (stroke %08x, %d more to come)\n",
366 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
367 s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos);
369 event_t* e = event_new();
370 e->type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
375 if(queue) queue_put(queue, e);
376 else hqueue_put(hqueue, e);
378 if(e->type != EVENT_HORIZONTAL) {
388 static void gfxpoly_enqueue(gfxpoly_t*p, queue_t*queue, hqueue_t*hqueue, int polygon_nr)
391 gfxpolystroke_t*stroke = p->strokes;
392 for(;stroke;stroke=stroke->next) {
393 assert(stroke->num_points > 1);
397 for(s=0;s<stroke->num_points-1;s++) {
398 assert(stroke->points[s].y <= stroke->points[s+1].y);
401 advance_stroke(queue, hqueue, stroke, polygon_nr, 0);
405 static void schedule_endpoint(status_t*status, segment_t*s)
407 // schedule end point of segment
408 assert(s->b.y > status->y);
409 event_t*e = event_new();
414 queue_put(&status->queue, e);
417 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
419 /* the code that's required (and the checks you can perform) before
420 it can be said with 100% certainty that we indeed have a valid crossing
421 amazes me every time. -mk */
424 assert(s1->right == s2);
425 assert(s2->left == s1);
426 int32_t miny1 = min32(s1->a.y,s1->b.y);
427 int32_t maxy1 = max32(s1->a.y,s1->b.y);
428 int32_t miny2 = min32(s2->a.y,s2->b.y);
429 int32_t maxy2 = max32(s2->a.y,s2->b.y);
430 int32_t minx1 = min32(s1->a.x,s1->b.x);
431 int32_t minx2 = min32(s2->a.x,s2->b.x);
432 int32_t maxx1 = max32(s1->a.x,s1->b.x);
433 int32_t maxx2 = max32(s2->a.x,s2->b.x);
434 /* check that precomputation is sane */
435 assert(minx1 == s1->minx && minx2 == s2->minx);
436 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
437 /* both segments are active, so this can't happen */
438 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
439 /* we know that right now, s2 is to the right of s1, so there's
440 no way the complete bounding box of s1 is to the right of s1 */
441 assert(!(s1->minx > s2->maxx));
442 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
445 if(s1->maxx <= s2->minx) {
447 fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
449 /* bounding boxes don't intersect */
453 #ifndef DONT_REMEMBER_CROSSINGS
454 if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
455 /* FIXME: this whole segment hashing thing is really slow */
457 fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
458 // DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
459 // fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
462 return; // we already know about this one
466 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
469 // lines are exactly on top of each other (ignored)
471 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
476 fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
478 /* lines are parallel */
483 double asign2 = LINE_EQ(s1->a, s2);
485 // segment1 touches segment2 in a single point (ignored)
487 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
491 double bsign2 = LINE_EQ(s1->b, s2);
493 // segment1 touches segment2 in a single point (ignored)
495 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
500 if(asign2<0 && bsign2<0) {
501 // segment1 is completely to the left of segment2
503 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);
507 if(asign2>0 && bsign2>0) {
508 // segment1 is completely to the right of segment2
509 #ifndef DONT_REMEMBER_CROSSINGS
513 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);
518 double asign1 = LINE_EQ(s2->a, s1);
520 // segment2 touches segment1 in a single point (ignored)
522 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
526 double bsign1 = LINE_EQ(s2->b, s1);
528 // segment2 touches segment1 in a single point (ignored)
530 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
535 if(asign1<0 && bsign1<0) {
536 // segment2 is completely to the left of segment1
537 #ifndef DONT_REMEMBER_CROSSINGS
541 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);
545 if(asign1>0 && bsign1>0) {
546 // segment2 is completely to the right of segment1
548 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);
553 #ifdef DONT_REMEMBER_CROSSINGS
554 /* s2 crosses s1 from *left* to *right*. This is a crossing we already processed-
555 there's not way s2 would be to the left of s1 otherwise */
556 if(asign1<0 && bsign1>0) return;
557 if(asign2>0 && bsign2<0) return;
560 assert(!(asign1<0 && bsign1>0));
561 assert(!(asign2>0 && bsign2<0));
563 /* TODO: should we precompute these? */
564 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
565 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
568 p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
569 p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
571 assert(p.y >= status->y);
573 assert(p.x >= s1->minx && p.x <= s1->maxx);
574 assert(p.x >= s2->minx && p.x <= s2->maxx);
579 #ifndef DONT_REMEMBER_CROSSINGS
580 assert(!dict_contains(status->seen_crossings, &pair));
581 dict_put(status->seen_crossings, &pair, 0);
585 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
588 #ifndef DONT_REMEMBER_CROSSINGS
589 /* we insert into each other's intersection history because these segments might switch
590 places and we still want to look them up quickly after they did */
591 dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
592 dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
595 event_t* e = event_new();
596 e->type = EVENT_CROSS;
600 queue_put(&status->queue, e);
604 static void exchange_two(status_t*status, event_t*e)
606 //exchange two segments in list
607 segment_t*s1 = e->s1;
608 segment_t*s2 = e->s2;
610 if(!dict_contains(status->intersecting_segs, s1))
611 dict_put(status->intersecting_segs, s1, 0);
612 if(!dict_contains(status->intersecting_segs, s2))
613 dict_put(status->intersecting_segs, s2, 0);
615 assert(s2->left == s1);
616 assert(s1->right == s2);
617 actlist_swap(status->actlist, s1, s2);
618 assert(s2->right == s1);
619 assert(s1->left == s2);
620 segment_t*left = s2->left;
621 segment_t*right = s1->right;
623 schedule_crossing(status, left, s2);
625 schedule_crossing(status, s1, right);
628 typedef struct _box {
629 point_t left1, left2, right1, right2;
631 static inline box_t box_new(int32_t x, int32_t y)
634 box.right1.x = box.right2.x = x;
635 box.left1.x = box.left2.x = x-1;
636 box.left1.y = box.right1.y = y-1;
637 box.left2.y = box.right2.y = y;
641 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
643 assert(s->pos.x != p.x || s->pos.y != p.y);
646 if(!dict_contains(status->segs_with_point, s))
647 dict_put(status->segs_with_point, s, 0);
648 assert(s->fs_out_ok);
653 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
654 s->pos.x, s->pos.y, p.x, p.y);
656 /* XXX we probably will never output circular/anticircular polygons, but if
657 we do, we would need to set the segment direction here */
658 fillstyle_t*fs = s->fs_out;
660 // omit horizontal lines
661 if(s->pos.y != p.y) {
666 gfxpolystroke_t*stroke = status->strokes;
668 point_t p = stroke->points[stroke->num_points-1];
669 if(p.x == a.x && p.y == a.y && stroke->fs == fs)
671 stroke = stroke->next;
674 stroke = rfx_calloc(sizeof(gfxpolystroke_t));
675 stroke->dir = DIR_DOWN;
677 stroke->next = status->strokes;
678 status->strokes = stroke;
679 stroke->points_size = 2;
680 stroke->points = rfx_calloc(sizeof(point_t)*stroke->points_size);
681 stroke->points[0] = a;
682 stroke->num_points = 1;
683 } else if(stroke->num_points == stroke->points_size) {
684 stroke->points_size *= 2;
685 stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size);
687 stroke->points[stroke->num_points++] = b;
691 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
697 typedef struct _segrange {
704 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
706 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
707 segment_t*min = range->segmin;
708 segment_t*max = range->segmax;
710 /* we need this because if two segments intersect exactly on
711 the scanline, segrange_test_segment_{min,max} can't tell which
712 one is smaller/larger */
713 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
716 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
722 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
725 /* we need to calculate the xpos anew (and can't use start coordinate or
726 intersection coordinate), because we need the xpos exactly at the end of
729 double x = XPOS(seg, y);
730 if(!range->segmin || x<range->xmin) {
735 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
738 double x = XPOS(seg, y);
739 if(!range->segmax || x>range->xmax) {
754 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
756 segment_t*first=0, *last = 0;
758 for(t=0;t<status->xrow->num;t++) {
759 box_t box = box_new(status->xrow->x[t], y);
760 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
762 seg = actlist_right(status->actlist, seg);
765 // this segment started in this scanline, ignore it
766 seg->changed = 1;last = seg;if(!first) {first=seg;}
767 } else if(seg->delta.x <= 0) {
768 // ignore segment w/ negative slope
770 last = seg;if(!first) {first=seg;}
771 double d1 = LINE_EQ(box.right1, seg);
772 double d2 = LINE_EQ(box.right2, seg);
775 insert_point_into_segment(status, seg, box.right2);
777 /* we unfortunately can't break here- the active list is sorted according
778 to the *bottom* of the scanline. hence pretty much everything that's still
779 coming might reach into our box */
786 segrange_test_segment_min(range, first, y);
787 segrange_test_segment_max(range, last, y);
797 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
799 segment_t*first=0, *last = 0;
801 for(t=status->xrow->num-1;t>=0;t--) {
802 box_t box = box_new(status->xrow->x[t], y);
803 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
807 // this segment started in this scanline, ignore it
808 seg->changed = 1;last = seg;if(!first) {first=seg;}
809 } else if(seg->delta.x > 0) {
810 // ignore segment w/ positive slope
812 last = seg;if(!first) {first=seg;}
813 double d1 = LINE_EQ(box.left1, seg);
814 double d2 = LINE_EQ(box.left2, seg);
817 insert_point_into_segment(status, seg, box.right2);
825 segrange_test_segment_min(range, last, y);
826 segrange_test_segment_max(range, first, y);
829 /* segments ending in the current scanline need xrow treatment like everything else.
830 (consider an intersection taking place just above a nearly horizontal segment
831 ending on the current scanline- the intersection would snap down *below* the
832 ending segment if we don't add the intersection point to the latter right away)
833 we need to treat ending segments seperately, however. we have to delete them from
834 the active list right away to make room for intersect operations (which might
835 still be in the current scanline- consider two 45° polygons and a vertical polygon
836 intersecting on an integer coordinate). but once they're no longer in the active list,
837 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
838 them to the active list just for point snapping would be overkill.
839 (One other option to consider, however, would be to create a new active list only
842 static void add_points_to_ending_segments(status_t*status, int32_t y)
844 segment_t*seg = status->ending_segments;
846 segment_t*next = seg->right;seg->right=0;
848 assert(seg->b.y == status->y);
850 if(status->xrow->num == 1) {
852 assert(seg->b.x == status->xrow->x[0]);
853 point_t p = {status->xrow->x[0], y};
854 insert_point_into_segment(status, seg, p);
857 int start=0,end=status->xrow->num,dir=1;
858 if(seg->delta.x < 0) {
859 start = status->xrow->num-1;
862 for(t=start;t!=end;t+=dir) {
863 box_t box = box_new(status->xrow->x[t], y);
864 double d0 = LINE_EQ(box.left1, seg);
865 double d1 = LINE_EQ(box.left2, seg);
866 double d2 = LINE_EQ(box.right1, seg);
867 double d3 = LINE_EQ(box.right2, seg);
868 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
869 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
870 insert_point_into_segment(status, seg, box.right2);
876 /* we *need* to find a point to insert. the segment's own end point
877 is in that list, for Pete's sake. */
881 // now that this is done, too, we can also finally free this segment
882 segment_destroy(seg);
885 status->ending_segments = 0;
888 static void recalculate_windings(status_t*status, segrange_t*range)
891 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
893 segrange_adjust_endpoints(range, status->y);
895 segment_t*s = range->segmin;
896 segment_t*end = range->segmax;
900 s = actlist_leftmost(status->actlist);
902 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
903 s == range->segmin?"S":(
904 s == range->segmax?"E":""));
907 fprintf(stderr, "\n");
911 /* test sanity: check that we don't have changed segments
912 outside of the given range */
913 s = actlist_leftmost(status->actlist);
914 while(s && s!=range->segmin) {
918 s = actlist_rightmost(status->actlist);
919 while(s && s!=range->segmax) {
923 /* in check mode, go through the whole interval so we can test
924 that all polygons where the fillstyle changed also have seg->changed=1 */
925 s = actlist_leftmost(status->actlist);
936 segment_t* left = actlist_left(status->actlist, s);
937 windstate_t wind = left?left->wind:status->windrule->start(status->context);
938 s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
939 fillstyle_t*fs_old = s->fs_out;
940 s->fs_out = status->windrule->diff(&wind, &s->wind);
943 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",
944 fs_old?"draw":"omit", s->fs_out?"draw":"omit",
945 fs_old!=s->fs_out?"CHANGED":"");
947 assert(!(!s->changed && fs_old!=s->fs_out));
958 /* we need to handle horizontal lines in order to add points to segments
959 we otherwise would miss during the windrule re-evaluation */
960 static void intersect_with_horizontal(status_t*status, segment_t*h)
962 segment_t* left = actlist_find(status->actlist, h->a, h->a);
963 segment_t* right = actlist_find(status->actlist, h->b, h->b);
965 /* not strictly necessary, also done by the event */
966 xrow_add(status->xrow, h->a.x);
974 left = actlist_right(status->actlist, left); //first seg to the right of h->a
975 right = right->right; //first seg to the right of h->b
980 int32_t x = XPOS_INT(s, status->y);
982 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
990 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
991 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
992 xrow_add(status->xrow, x);
998 static void event_apply(status_t*status, event_t*e)
1001 case EVENT_HORIZONTAL: {
1002 segment_t*s = e->s1;
1006 intersect_with_horizontal(status, s);
1007 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1008 segment_destroy(s);e->s1=0;
1012 //delete segment from list
1013 segment_t*s = e->s1;
1018 dict_del(status->intersecting_segs, s);
1019 dict_del(status->segs_with_point, s);
1020 assert(!dict_contains(status->intersecting_segs, s));
1021 assert(!dict_contains(status->segs_with_point, s));
1023 segment_t*left = s->left;
1024 segment_t*right = s->right;
1025 actlist_delete(status->actlist, s);
1027 schedule_crossing(status, left, right);
1029 /* schedule segment for xrow handling */
1030 s->left = 0; s->right = status->ending_segments;
1031 status->ending_segments = s;
1032 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1036 //insert segment into list
1040 segment_t*s = e->s1;
1041 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1042 actlist_insert(status->actlist, s->a, s->b, s);
1043 segment_t*left = s->left;
1044 segment_t*right = s->right;
1046 schedule_crossing(status, left, s);
1048 schedule_crossing(status, s, right);
1049 schedule_endpoint(status, s);
1053 // exchange two segments
1057 if(e->s1->right == e->s2) {
1058 assert(e->s2->left == e->s1);
1059 exchange_two(status, e);
1061 assert(e->s2->left != e->s1);
1063 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1065 #ifndef DONT_REMEMBER_CROSSINGS
1066 /* ignore this crossing for now (there are some line segments in between).
1067 it'll get rescheduled as soon as the "obstacles" are gone */
1068 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1069 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1070 assert(del1 && del2);
1076 #ifndef DONT_REMEMBER_CROSSINGS
1077 assert(dict_contains(status->seen_crossings, &pair));
1078 dict_del(status->seen_crossings, &pair);
1087 static void check_status(status_t*status)
1089 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1090 if((s->pos.x != s->b.x ||
1091 s->pos.y != s->b.y) &&
1092 !dict_contains(status->segs_with_point, s)) {
1093 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1095 s->delta.x<0?"-":"+",
1103 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1106 |..| |...........| | |
1107 |..| |...........| | |
1108 |..+ + +..| +--+ +--+
1109 |...........| |..| | |
1110 |...........| |..| | |
1114 fprintf(stderr, "========================================================================\n");
1117 hqueue_init(&hqueue);
1118 gfxpoly_enqueue(poly, 0, &hqueue, 0);
1120 actlist_t* actlist = actlist_new();
1122 event_t*e = hqueue_get(&hqueue);
1128 fprintf(stderr, "HORIZONTALS ----------------------------------- %d\n", y);
1129 actlist_dump(actlist, y-1);
1132 actlist_verify(actlist, y-1);
1135 if(fill && x != e->p.x) {
1137 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
1141 gfxpolystroke_t*stroke = rfx_calloc(sizeof(gfxpolystroke_t));
1142 stroke->next = poly->strokes;
1143 poly->strokes = stroke;
1145 stroke->num_points = 2;
1146 stroke->points = malloc(sizeof(point_t)*2);
1147 stroke->dir = DIR_UP; // FIXME
1151 /* we draw from low x to high x so that left/right fillstyles add up
1152 (because the horizontal line's fill style controls the area *below* the line)
1156 stroke->points[0] = a;
1157 stroke->points[1] = b;
1159 /* the output should always be intersection free polygons, so check this horizontal
1160 line isn't hacking through any segments in the active list */
1161 segment_t* start = actlist_find(actlist, b, b);
1162 segment_t* s = actlist_find(actlist, a, a);
1164 assert(s->a.y == y || s->b.y == y);
1170 segment_t*s = e->s1;
1174 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1175 actlist_insert(actlist, s->a, s->b, s);
1176 event_t* e = event_new();
1177 e->type = EVENT_END;
1181 hqueue_put(&hqueue, e);
1182 left = actlist_left(actlist, s);
1186 left = actlist_left(actlist, s);
1187 actlist_delete(actlist, s);
1188 advance_stroke(0, &hqueue, s->stroke, s->polygon_nr, s->stroke_pos);
1195 fill ^= 1;//(before.is_filled != after.is_filled);
1197 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d\n",
1198 y, e->type==EVENT_START?"start":"end",
1204 if(e->type == EVENT_END)
1208 e = hqueue_get(&hqueue);
1209 } while(e && y == e->p.y);
1212 char bleeding = fill;
1217 actlist_destroy(actlist);
1218 hqueue_destroy(&hqueue);
1221 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly1, gfxpoly_t*poly2, windrule_t*windrule, windcontext_t*context)
1223 current_polygon = poly1;
1226 memset(&status, 0, sizeof(status_t));
1227 queue_init(&status.queue);
1228 gfxpoly_enqueue(poly1, &status.queue, 0, /*polygon nr*/0);
1230 assert(poly1->gridsize == poly2->gridsize);
1231 gfxpoly_enqueue(poly2, &status.queue, 0, /*polygon nr*/1);
1234 status.windrule = windrule;
1235 status.context = context;
1236 status.actlist = actlist_new();
1239 status.seen_crossings = dict_new2(&point_type);
1240 int32_t lasty=-0x80000000;
1243 status.xrow = xrow_new();
1245 event_t*e = queue_get(&status.queue);
1249 assert(status.y>=lasty);
1251 status.intersecting_segs = dict_new2(&ptr_type);
1252 status.segs_with_point = dict_new2(&ptr_type);
1256 fprintf(stderr, "----------------------------------- %d\n", status.y);
1257 actlist_dump(status.actlist, status.y-1);
1260 actlist_verify(status.actlist, status.y-1);
1262 xrow_reset(status.xrow);
1264 xrow_add(status.xrow, e->p.x);
1265 event_apply(&status, e);
1267 e = queue_get(&status.queue);
1268 } while(e && status.y == e->p.y);
1270 xrow_sort(status.xrow);
1272 memset(&range, 0, sizeof(range));
1274 actlist_dump(status.actlist, status.y);
1276 add_points_to_positively_sloped_segments(&status, status.y, &range);
1277 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1278 add_points_to_ending_segments(&status, status.y);
1280 recalculate_windings(&status, &range);
1282 check_status(&status);
1283 dict_destroy(status.intersecting_segs);
1284 dict_destroy(status.segs_with_point);
1288 dict_destroy(status.seen_crossings);
1290 actlist_destroy(status.actlist);
1291 queue_destroy(&status.queue);
1292 xrow_destroy(status.xrow);
1294 gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t));
1295 p->gridsize = poly1->gridsize;
1296 p->strokes = status.strokes;
1298 add_horizontals(p, &windrule_evenodd, context); // output is always even/odd
1302 static windcontext_t twopolygons = {2};
1303 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*p1, gfxpoly_t*p2)
1305 return gfxpoly_process(p1, p2, &windrule_intersect, &twopolygons);
1307 gfxpoly_t* gfxpoly_union(gfxpoly_t*p1, gfxpoly_t*p2)
1309 return gfxpoly_process(p1, p2, &windrule_union, &twopolygons);