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 = initialize_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 /* In order to not confuse the fill/wind logic, existing segments must have
176 a non-zero edge style */
179 /* put all the segments into dictionaries so that we can check
180 that the endpoint multiplicity is two */
181 for(s=0;s<stroke->num_points;s++) {
182 point_t p = stroke->points[s];
183 int num = (s>=1 && s<stroke->num_points-1)?2:1; // mid points are two points (start+end)
184 if(!dict_contains(d, &p)) {
185 dict_put(d, &p, (void*)(ptroff_t)num);
187 int count = (ptroff_t)dict_lookup(d, &p);
190 dict_put(d, &p, (void*)(ptroff_t)count);
194 DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
195 int count = (ptroff_t)c;
197 fprintf(stderr, "Point (%d,%d) occurs %d times\n", p->x, p->y, count);
199 assert(count%2 == 0);
206 void gfxpoly_dump(gfxpoly_t*poly)
209 double g = poly->gridsize;
210 fprintf(stderr, "polyon %p (gridsize: %f)\n", poly, poly->gridsize);
211 gfxpolystroke_t*stroke = poly->strokes;
212 for(;stroke;stroke=stroke->next) {
213 fprintf(stderr, "%p", stroke);
214 for(s=0;s<stroke->num_points-1;s++) {
215 point_t a = stroke->points[s];
216 point_t b = stroke->points[s+1];
217 fprintf(stderr, "%s (%f,%f) -> (%f,%f)%s\n", s?" ":"", a.x*g, a.y*g, b.x*g, b.y*g,
218 s==stroke->num_points-2?"]":"");
223 void gfxpoly_save(gfxpoly_t*poly, const char*filename)
225 FILE*fi = fopen(filename, "wb");
226 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
227 fprintf(fi, "%% begin\n");
229 gfxpolystroke_t*stroke = poly->strokes;
230 for(;stroke;stroke=stroke->next) {
231 fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
232 point_t p = stroke->points[0];
233 fprintf(fi, "%d %d moveto\n", p.x, p.y);
234 for(s=1;s<stroke->num_points;s++) {
235 p = stroke->points[s];
236 fprintf(fi, "%d %d lineto\n", p.x, p.y);
238 fprintf(fi, "stroke\n");
240 fprintf(fi, "showpage\n");
244 inline static event_t* event_new()
246 event_t*e = rfx_calloc(sizeof(event_t));
249 inline static void event_free(event_t*e)
254 static void event_dump(event_t*e)
256 if(e->type == EVENT_HORIZONTAL) {
257 fprintf(stderr, "Horizontal [%d] (%d,%d) -> (%d,%d)\n", (int)e->s1->nr, e->s1->a.x, e->s1->a.y, e->s1->b.x, e->s1->b.y);
258 } else if(e->type == EVENT_START) {
259 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", (int)e->s1->nr, e->p.x, e->p.y);
260 } else if(e->type == EVENT_END) {
261 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", (int)e->s1->nr, e->p.x, e->p.y);
262 } else if(e->type == EVENT_CROSS) {
263 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", (int)e->s1->nr, (int)e->s2->nr, e->p.x, e->p.y);
269 static inline int32_t max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
270 static inline int32_t min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
272 static void segment_dump(segment_t*s)
274 fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", (int)s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
275 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f fs=%p\n", s->delta.x, s->delta.y, s->k,
276 (double)s->delta.x / s->delta.y, s->fs_orig);
279 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)
285 /* We need to make sure horizontal segments always go from left to right.
286 "up/down" for horizontal segments is handled by "rotating"
287 them 90° anticlockwise in screen coordinates (tilt your head to
293 int32_t x = x1;x1=x2;x2=x;
294 int32_t y = y1;y1=y2;y2=y;
301 s->k = (double)x1*y2-(double)x2*y1;
302 s->left = s->right = 0;
305 s->minx = min32(x1,x2);
306 s->maxx = max32(x1,x2);
309 s->polygon_nr = polygon_nr;
310 static int segment_count=0;
311 s->nr = segment_count++;
314 /* notice: on some systems (with some compilers), for the line
315 (1073741823,-1073741824)->(1073741823,1073741823)
316 we get LINE_EQ(s->a, s) == 1.
317 That's why we now clamp to 26 bit.
319 assert(LINE_EQ(s->a, s) == 0);
320 assert(LINE_EQ(s->b, s) == 0);
322 /* check that all signs are in order:
330 p.x = min32(s->a.x, s->b.x);
331 assert(LINE_EQ(p, s) <= 0);
332 p.x = max32(s->a.x, s->b.x);
333 assert(LINE_EQ(p, s) >= 0);
336 #ifndef DONT_REMEMBER_CROSSINGS
337 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
341 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
343 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
344 segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
348 static void segment_clear(segment_t*s)
350 #ifndef DONT_REMEMBER_CROSSINGS
351 dict_clear(&s->scheduled_crossings);
354 static void segment_destroy(segment_t*s)
360 static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*stroke, int polygon_nr, int pos)
365 /* we need to queue multiple segments at once because we need to process start events
366 before horizontal events */
367 while(pos < stroke->num_points-1) {
368 assert(stroke->points[pos].y <= stroke->points[pos+1].y);
369 s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
370 s->fs_orig = stroke->fs;
371 s->fs_old = stroke->fs_old;
378 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (stroke %p, %d more to come)\n",
379 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
380 s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos);
382 event_t* e = event_new();
383 e->type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
388 if(queue) queue_put(queue, e);
389 else hqueue_put(hqueue, e);
391 if(e->type != EVENT_HORIZONTAL) {
401 static void gfxpoly_enqueue(gfxpoly_t*p, queue_t*queue, hqueue_t*hqueue, int polygon_nr)
404 gfxpolystroke_t*stroke = p->strokes;
405 for(;stroke;stroke=stroke->next) {
406 assert(stroke->num_points > 1);
410 for(s=0;s<stroke->num_points-1;s++) {
411 assert(stroke->points[s].y <= stroke->points[s+1].y);
414 advance_stroke(queue, hqueue, stroke, polygon_nr, 0);
418 static void schedule_endpoint(status_t*status, segment_t*s)
420 // schedule end point of segment
421 assert(s->b.y > status->y);
422 event_t*e = event_new();
427 queue_put(&status->queue, e);
430 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
432 /* the code that's required (and the checks you can perform) before
433 it can be said with 100% certainty that we indeed have a valid crossing
434 amazes me every time. -mk */
437 assert(s1->right == s2);
438 assert(s2->left == s1);
439 int32_t miny1 = min32(s1->a.y,s1->b.y);
440 int32_t maxy1 = max32(s1->a.y,s1->b.y);
441 int32_t miny2 = min32(s2->a.y,s2->b.y);
442 int32_t maxy2 = max32(s2->a.y,s2->b.y);
443 int32_t minx1 = min32(s1->a.x,s1->b.x);
444 int32_t minx2 = min32(s2->a.x,s2->b.x);
445 int32_t maxx1 = max32(s1->a.x,s1->b.x);
446 int32_t maxx2 = max32(s2->a.x,s2->b.x);
447 /* check that precomputation is sane */
448 assert(minx1 == s1->minx && minx2 == s2->minx);
449 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
450 /* both segments are active, so this can't happen */
451 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
452 /* we know that right now, s2 is to the right of s1, so there's
453 no way the complete bounding box of s1 is to the right of s1 */
454 assert(!(s1->minx > s2->maxx));
455 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
458 if(s1->maxx <= s2->minx) {
460 fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
462 /* bounding boxes don't intersect */
466 #ifndef DONT_REMEMBER_CROSSINGS
467 if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
468 /* FIXME: this whole segment hashing thing is really slow */
470 fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
471 // DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
472 // fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
475 return; // we already know about this one
479 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
482 // lines are exactly on top of each other (ignored)
484 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
489 fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
491 /* lines are parallel */
496 double asign2 = LINE_EQ(s1->a, s2);
498 // segment1 touches segment2 in a single point (ignored)
500 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
504 double bsign2 = LINE_EQ(s1->b, s2);
506 // segment1 touches segment2 in a single point (ignored)
508 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
513 if(asign2<0 && bsign2<0) {
514 // segment1 is completely to the left of segment2
516 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);
520 if(asign2>0 && bsign2>0) {
521 // segment1 is completely to the right of segment2
522 #ifndef DONT_REMEMBER_CROSSINGS
526 fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s2->nr, s1->nr);
531 double asign1 = LINE_EQ(s2->a, s1);
533 // segment2 touches segment1 in a single point (ignored)
535 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
539 double bsign1 = LINE_EQ(s2->b, s1);
541 // segment2 touches segment1 in a single point (ignored)
543 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
548 if(asign1<0 && bsign1<0) {
549 // segment2 is completely to the left of segment1
550 #ifndef DONT_REMEMBER_CROSSINGS
554 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);
558 if(asign1>0 && bsign1>0) {
559 // segment2 is completely to the right of segment1
561 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);
566 #ifdef DONT_REMEMBER_CROSSINGS
567 /* s2 crosses s1 from *left* to *right*. This is a crossing we already processed-
568 there's not way s2 would be to the left of s1 otherwise */
569 if(asign1<0 && bsign1>0) return;
570 if(asign2>0 && bsign2<0) return;
573 assert(!(asign1<0 && bsign1>0));
574 assert(!(asign2>0 && bsign2<0));
576 /* TODO: should we precompute these? */
577 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
578 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
581 p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
582 p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
584 assert(p.y >= status->y);
586 assert(p.x >= s1->minx && p.x <= s1->maxx);
587 assert(p.x >= s2->minx && p.x <= s2->maxx);
592 #ifndef DONT_REMEMBER_CROSSINGS
593 assert(!dict_contains(status->seen_crossings, &pair));
594 dict_put(status->seen_crossings, &pair, 0);
598 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
601 #ifndef DONT_REMEMBER_CROSSINGS
602 /* we insert into each other's intersection history because these segments might switch
603 places and we still want to look them up quickly after they did */
604 dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
605 dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
608 event_t* e = event_new();
609 e->type = EVENT_CROSS;
613 queue_put(&status->queue, e);
617 static void exchange_two(status_t*status, event_t*e)
619 //exchange two segments in list
620 segment_t*s1 = e->s1;
621 segment_t*s2 = e->s2;
623 if(!dict_contains(status->intersecting_segs, s1))
624 dict_put(status->intersecting_segs, s1, 0);
625 if(!dict_contains(status->intersecting_segs, s2))
626 dict_put(status->intersecting_segs, s2, 0);
628 assert(s2->left == s1);
629 assert(s1->right == s2);
630 actlist_swap(status->actlist, s1, s2);
631 assert(s2->right == s1);
632 assert(s1->left == s2);
633 segment_t*left = s2->left;
634 segment_t*right = s1->right;
636 schedule_crossing(status, left, s2);
638 schedule_crossing(status, s1, right);
641 typedef struct _box {
642 point_t left1, left2, right1, right2;
644 static inline box_t box_new(int32_t x, int32_t y)
647 box.right1.x = box.right2.x = x;
648 box.left1.x = box.left2.x = x-1;
649 box.left1.y = box.right1.y = y-1;
650 box.left2.y = box.right2.y = y;
654 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
656 assert(s->pos.x != p.x || s->pos.y != p.y);
659 if(!dict_contains(status->segs_with_point, s))
660 dict_put(status->segs_with_point, s, 0);
661 assert(s->fs_out_ok);
666 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
667 s->pos.x, s->pos.y, p.x, p.y);
669 edgestyle_t*fs = s->fs_out;
670 edgestyle_t*fs_old = s->fs_orig;
672 // omit horizontal lines
673 if(s->pos.y != p.y) {
678 gfxpolystroke_t*stroke = status->strokes;
679 /* find a stoke to attach this segment to. It has to have an endpoint
680 matching our start point, and a matching edgestyle */
682 point_t p = stroke->points[stroke->num_points-1];
683 if(p.x == a.x && p.y == a.y && stroke->fs == fs && stroke->fs_old == fs_old)
685 stroke = stroke->next;
688 stroke = rfx_calloc(sizeof(gfxpolystroke_t));
689 stroke->dir = DIR_DOWN;
691 stroke->fs_old = fs_old;
692 stroke->next = status->strokes;
693 status->strokes = stroke;
694 stroke->points_size = 2;
695 stroke->points = rfx_calloc(sizeof(point_t)*stroke->points_size);
696 stroke->points[0] = a;
697 stroke->num_points = 1;
698 } else if(stroke->num_points == stroke->points_size) {
700 stroke->points_size *= 2;
701 stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size);
703 stroke->points[stroke->num_points++] = b;
707 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
713 typedef struct _segrange {
720 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
722 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
723 segment_t*min = range->segmin;
724 segment_t*max = range->segmax;
726 /* we need this because if two segments intersect exactly on
727 the scanline, segrange_test_segment_{min,max} can't tell which
728 one is smaller/larger */
729 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
732 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
738 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
741 /* we need to calculate the xpos anew (and can't use start coordinate or
742 intersection coordinate), because we need the xpos exactly at the end of
745 double x = XPOS(seg, y);
746 if(!range->segmin || x<range->xmin) {
751 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
754 double x = XPOS(seg, y);
755 if(!range->segmax || x>range->xmax) {
770 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
772 segment_t*first=0, *last = 0;
774 for(t=0;t<status->xrow->num;t++) {
775 box_t box = box_new(status->xrow->x[t], y);
776 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
778 seg = actlist_right(status->actlist, seg);
781 // this segment started in this scanline, ignore it
782 seg->changed = 1;last = seg;if(!first) {first=seg;}
783 } else if(seg->delta.x <= 0) {
784 // ignore segment w/ negative slope
786 last = seg;if(!first) {first=seg;}
787 double d1 = LINE_EQ(box.right1, seg);
788 double d2 = LINE_EQ(box.right2, seg);
791 insert_point_into_segment(status, seg, box.right2);
793 /* we unfortunately can't break here- the active list is sorted according
794 to the *bottom* of the scanline. hence pretty much everything that's still
795 coming might reach into our box */
802 segrange_test_segment_min(range, first, y);
803 segrange_test_segment_max(range, last, y);
813 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
815 segment_t*first=0, *last = 0;
817 for(t=status->xrow->num-1;t>=0;t--) {
818 box_t box = box_new(status->xrow->x[t], y);
819 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
823 // this segment started in this scanline, ignore it
824 seg->changed = 1;last = seg;if(!first) {first=seg;}
825 } else if(seg->delta.x > 0) {
826 // ignore segment w/ positive slope
828 last = seg;if(!first) {first=seg;}
829 double d1 = LINE_EQ(box.left1, seg);
830 double d2 = LINE_EQ(box.left2, seg);
833 insert_point_into_segment(status, seg, box.right2);
841 segrange_test_segment_min(range, last, y);
842 segrange_test_segment_max(range, first, y);
845 /* segments ending in the current scanline need xrow treatment like everything else.
846 (consider an intersection taking place just above a nearly horizontal segment
847 ending on the current scanline- the intersection would snap down *below* the
848 ending segment if we don't add the intersection point to the latter right away)
849 we need to treat ending segments seperately, however. we have to delete them from
850 the active list right away to make room for intersect operations (which might
851 still be in the current scanline- consider two 45° polygons and a vertical polygon
852 intersecting on an integer coordinate). but once they're no longer in the active list,
853 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
854 them to the active list just for point snapping would be overkill.
855 (One other option to consider, however, would be to create a new active list only
858 static void add_points_to_ending_segments(status_t*status, int32_t y)
860 segment_t*seg = status->ending_segments;
862 segment_t*next = seg->right;seg->right=0;
864 assert(seg->b.y == status->y);
866 if(status->xrow->num == 1) {
868 assert(seg->b.x == status->xrow->x[0]);
869 point_t p = {status->xrow->x[0], y};
870 insert_point_into_segment(status, seg, p);
873 int start=0,end=status->xrow->num,dir=1;
874 if(seg->delta.x < 0) {
875 start = status->xrow->num-1;
878 for(t=start;t!=end;t+=dir) {
879 box_t box = box_new(status->xrow->x[t], y);
880 double d0 = LINE_EQ(box.left1, seg);
881 double d1 = LINE_EQ(box.left2, seg);
882 double d2 = LINE_EQ(box.right1, seg);
883 double d3 = LINE_EQ(box.right2, seg);
884 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
885 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
886 insert_point_into_segment(status, seg, box.right2);
892 /* we *need* to find a point to insert. the segment's own end point
893 is in that list, for Pete's sake. */
897 // now that this is done, too, we can also finally free this segment
898 segment_destroy(seg);
901 status->ending_segments = 0;
904 static void recalculate_windings(status_t*status, segrange_t*range)
907 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
909 segrange_adjust_endpoints(range, status->y);
911 segment_t*s = range->segmin;
912 segment_t*end = range->segmax;
916 s = actlist_leftmost(status->actlist);
918 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
919 s == range->segmin?"S":(
920 s == range->segmax?"E":""));
923 fprintf(stderr, "\n");
927 /* test sanity: verify that we don't have changed segments
928 outside of the given range */
929 s = actlist_leftmost(status->actlist);
930 while(s && s!=range->segmin) {
934 s = actlist_rightmost(status->actlist);
935 while(s && s!=range->segmax) {
939 /* in check mode, go through the whole interval so we can test
940 that all polygons where the edgestyle changed also have seg->changed=1 */
941 s = actlist_leftmost(status->actlist);
952 segment_t* left = actlist_left(status->actlist, s);
953 windstate_t wind = left?left->wind:status->windrule->start(status->context);
954 s->wind = status->windrule->add(status->context, wind, s->fs_orig, s->dir, s->polygon_nr);
955 edgestyle_t*fs_old = s->fs_out;
956 s->fs_out = status->windrule->diff(&wind, &s->wind);
959 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",
960 fs_old?"draw":"omit", s->fs_out?"draw":"omit",
961 fs_old!=s->fs_out?"CHANGED":"");
963 assert(!(!s->changed && fs_old!=s->fs_out));
974 /* we need to handle horizontal lines in order to add points to segments
975 we otherwise would miss during the windrule re-evaluation */
976 static void intersect_with_horizontal(status_t*status, segment_t*h)
978 segment_t* left = actlist_find(status->actlist, h->a, h->a);
979 segment_t* right = actlist_find(status->actlist, h->b, h->b);
981 /* not strictly necessary, also done by the event */
982 xrow_add(status->xrow, h->a.x);
990 left = actlist_right(status->actlist, left); //first seg to the right of h->a
991 right = right->right; //first seg to the right of h->b
996 int32_t x = XPOS_INT(s, status->y);
998 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
1004 assert(x >= h->a.x);
1005 assert(x <= h->b.x);
1006 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
1007 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
1008 xrow_add(status->xrow, x);
1014 static void event_apply(status_t*status, event_t*e)
1017 case EVENT_HORIZONTAL: {
1018 segment_t*s = e->s1;
1022 intersect_with_horizontal(status, s);
1023 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1024 segment_destroy(s);e->s1=0;
1028 //delete segment from list
1029 segment_t*s = e->s1;
1034 dict_del(status->intersecting_segs, s);
1035 dict_del(status->segs_with_point, s);
1036 assert(!dict_contains(status->intersecting_segs, s));
1037 assert(!dict_contains(status->segs_with_point, s));
1039 segment_t*left = s->left;
1040 segment_t*right = s->right;
1041 actlist_delete(status->actlist, s);
1043 schedule_crossing(status, left, right);
1045 /* schedule segment for xrow handling */
1046 s->left = 0; s->right = status->ending_segments;
1047 status->ending_segments = s;
1048 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1052 //insert segment into list
1056 segment_t*s = e->s1;
1057 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1058 actlist_insert(status->actlist, s->a, s->b, s);
1059 segment_t*left = s->left;
1060 segment_t*right = s->right;
1062 schedule_crossing(status, left, s);
1064 schedule_crossing(status, s, right);
1065 schedule_endpoint(status, s);
1069 // exchange two segments
1073 if(e->s1->right == e->s2) {
1074 assert(e->s2->left == e->s1);
1075 exchange_two(status, e);
1077 assert(e->s2->left != e->s1);
1079 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1081 #ifndef DONT_REMEMBER_CROSSINGS
1082 /* ignore this crossing for now (there are some line segments in between).
1083 it'll get rescheduled as soon as the "obstacles" are gone */
1084 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1085 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1086 assert(del1 && del2);
1092 #ifndef DONT_REMEMBER_CROSSINGS
1093 assert(dict_contains(status->seen_crossings, &pair));
1094 dict_del(status->seen_crossings, &pair);
1103 static void check_status(status_t*status)
1105 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1106 if((s->pos.x != s->b.x ||
1107 s->pos.y != s->b.y) &&
1108 !dict_contains(status->segs_with_point, s)) {
1109 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1111 s->delta.x<0?"-":"+",
1119 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1122 |..| |...........| | |
1123 |..| |...........| | |
1124 |..+ + +..| +--+ +--+
1125 |...........| |..| | |
1126 |...........| |..| | |
1130 fprintf(stderr, "========================================================================\n");
1133 hqueue_init(&hqueue);
1134 gfxpoly_enqueue(poly, 0, &hqueue, 0);
1136 actlist_t* actlist = actlist_new();
1138 event_t*e = hqueue_get(&hqueue);
1142 windstate_t w = windrule->start(context);
1144 fprintf(stderr, "HORIZONTALS ----------------------------------- %d\n", y);
1145 actlist_dump(actlist, y-1);
1148 actlist_verify(actlist, y-1);
1150 edgestyle_t*fill = 0;
1151 edgestyle_t*fill2 = 0;
1154 assert(e->s1->fs_orig);
1155 if(fill && x != e->p.x) {
1157 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
1161 gfxpolystroke_t*stroke = rfx_calloc(sizeof(gfxpolystroke_t));
1162 stroke->next = poly->strokes;
1163 poly->strokes = stroke;
1165 stroke->num_points = 2;
1166 stroke->points = malloc(sizeof(point_t)*2);
1167 stroke->dir = DIR_UP; // FIXME
1171 /* we draw from low x to high x so that left/right fillstyles add up
1172 (because the horizontal line's fill style controls the area *below* the line)
1176 stroke->points[0] = a;
1177 stroke->points[1] = b;
1179 /* the output should always be intersection free polygons, so check this horizontal
1180 line isn't puncturing any segments in the active list */
1181 segment_t* start = actlist_find(actlist, b, b);
1182 segment_t* s = actlist_find(actlist, a, a);
1184 assert(s->a.y == y || s->b.y == y);
1197 edgestyle_t*old_fill = fill;
1198 windstate_t before1 = w;
1200 /* the current horizontal line is between before1 and before2: */
1201 windstate_t before2 = fill?windrule->add(context, before1, fill, DIR_UNKNOWN, -1):before1;
1204 segment_t*s = e->s1;
1210 after2 = windrule->add(context, before2, s->fs_orig, DIR_UNKNOWN, s->polygon_nr);
1214 after1 = windrule->add(context, before1, s->fs_orig, DIR_UNKNOWN, s->polygon_nr);
1220 fill2 = windrule->diff(&after1, &after2);
1225 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1226 actlist_insert(actlist, s->a, s->b, s);
1227 event_t* e = event_new();
1228 e->type = EVENT_END;
1232 hqueue_put(&hqueue, e);
1233 left = actlist_left(actlist, s);
1237 left = actlist_left(actlist, s);
1238 actlist_delete(actlist, s);
1239 advance_stroke(0, &hqueue, s->stroke, s->polygon_nr, s->stroke_pos);
1247 if(windrule==&windrule_evenodd) {
1248 fill = fill?0:&edgestyle_default;
1249 if(!!fill != !!fill2) {
1252 printf("at y=%d x=%d (hline:%p)\n", e->p.y, x, old_fill);
1253 if(e->type==EVENT_END) {
1254 printf(" %9p\n", s->fs_orig);
1257 printf(" %3d %c%2d \n", before1.is_filled, e->type==EVENT_END?'|':' ', after1.is_filled);
1258 printf("%12p -----+----- %p\n", old_fill, fill2);
1259 printf(" %3d %c%2d \n", before2.is_filled, e->type==EVENT_START?'|':' ', after2.is_filled);
1260 if(e->type==EVENT_START) {
1262 printf(" %9p\n", s->fs_orig);
1265 assert(!!fill == !!fill2);
1270 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d\n",
1271 y, e->type==EVENT_START?"start":"end",
1277 if(e->type == EVENT_END)
1281 e = hqueue_get(&hqueue);
1282 } while(e && y == e->p.y);
1285 edgestyle_t*bleeding = fill;
1290 actlist_destroy(actlist);
1291 hqueue_destroy(&hqueue);
1294 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly1, gfxpoly_t*poly2, windrule_t*windrule, windcontext_t*context)
1296 current_polygon = poly1;
1299 memset(&status, 0, sizeof(status_t));
1300 queue_init(&status.queue);
1301 gfxpoly_enqueue(poly1, &status.queue, 0, /*polygon nr*/0);
1303 assert(poly1->gridsize == poly2->gridsize);
1304 gfxpoly_enqueue(poly2, &status.queue, 0, /*polygon nr*/1);
1307 status.windrule = windrule;
1308 status.context = context;
1309 status.actlist = actlist_new();
1312 status.seen_crossings = dict_new2(&point_type);
1313 int32_t lasty=-0x80000000;
1316 status.xrow = xrow_new();
1318 event_t*e = queue_get(&status.queue);
1320 assert(e->s1->fs_orig);
1323 assert(status.y>=lasty);
1325 status.intersecting_segs = dict_new2(&ptr_type);
1326 status.segs_with_point = dict_new2(&ptr_type);
1330 fprintf(stderr, "----------------------------------- %d\n", status.y);
1331 actlist_dump(status.actlist, status.y-1);
1334 actlist_verify(status.actlist, status.y-1);
1336 xrow_reset(status.xrow);
1338 xrow_add(status.xrow, e->p.x);
1339 event_apply(&status, e);
1341 e = queue_get(&status.queue);
1342 } while(e && status.y == e->p.y);
1344 xrow_sort(status.xrow);
1346 memset(&range, 0, sizeof(range));
1348 actlist_dump(status.actlist, status.y);
1350 add_points_to_positively_sloped_segments(&status, status.y, &range);
1351 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1352 add_points_to_ending_segments(&status, status.y);
1354 recalculate_windings(&status, &range);
1356 check_status(&status);
1357 dict_destroy(status.intersecting_segs);
1358 dict_destroy(status.segs_with_point);
1362 dict_destroy(status.seen_crossings);
1364 actlist_destroy(status.actlist);
1365 queue_destroy(&status.queue);
1366 xrow_destroy(status.xrow);
1368 gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t));
1369 p->gridsize = poly1->gridsize;
1370 p->strokes = status.strokes;
1373 /* we only add segments with non-empty edgestyles to strokes in
1374 recalculate_windings, but better safe than sorry */
1375 gfxpolystroke_t*stroke = p->strokes;
1378 stroke = stroke->next;
1382 add_horizontals(p, &windrule_evenodd, context); // output is always even/odd
1383 //add_horizontals(p, windrule, context);
1387 static windcontext_t twopolygons = {2};
1388 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*p1, gfxpoly_t*p2)
1390 return gfxpoly_process(p1, p2, &windrule_intersect, &twopolygons);
1392 gfxpoly_t* gfxpoly_union(gfxpoly_t*p1, gfxpoly_t*p2)
1394 return gfxpoly_process(p1, p2, &windrule_union, &twopolygons);