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, edgestyle_t*fs, int polygon_nr, segment_dir_t dir)
286 /* We need to make sure horizontal segments always go from left to right.
287 "up/down" for horizontal segments is handled by "rotating"
288 them 90° anticlockwise in screen coordinates (tilt your head to
294 int32_t x = x1;x1=x2;x2=x;
295 int32_t y = y1;y1=y2;y2=y;
302 s->k = (double)x1*y2-(double)x2*y1;
303 s->left = s->right = 0;
306 s->minx = min32(x1,x2);
307 s->maxx = max32(x1,x2);
310 s->polygon_nr = polygon_nr;
311 static int segment_count=0;
312 s->nr = segment_count++;
315 /* notice: on some systems (with some compilers), for the line
316 (1073741823,-1073741824)->(1073741823,1073741823)
317 we get LINE_EQ(s->a, s) == 1.
318 That's why we now clamp to 26 bit.
320 assert(LINE_EQ(s->a, s) == 0);
321 assert(LINE_EQ(s->b, s) == 0);
323 /* check that all signs are in order:
331 p.x = min32(s->a.x, s->b.x);
332 assert(LINE_EQ(p, s) <= 0);
333 p.x = max32(s->a.x, s->b.x);
334 assert(LINE_EQ(p, s) >= 0);
337 #ifndef DONT_REMEMBER_CROSSINGS
338 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
342 static segment_t* segment_new(point_t a, point_t b, edgestyle_t*fs, int polygon_nr, segment_dir_t dir)
344 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
345 segment_init(s, a.x, a.y, b.x, b.y, fs, polygon_nr, dir);
349 static void segment_clear(segment_t*s)
351 #ifndef DONT_REMEMBER_CROSSINGS
352 dict_clear(&s->scheduled_crossings);
355 static void segment_destroy(segment_t*s)
361 static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*stroke, int polygon_nr, int pos)
366 /* we need to queue multiple segments at once because we need to process start events
367 before horizontal events */
368 while(pos < stroke->num_points-1) {
369 assert(stroke->points[pos].y <= stroke->points[pos+1].y);
370 s = segment_new(stroke->points[pos], stroke->points[pos+1], stroke->fs, polygon_nr, stroke->dir);
377 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (stroke %p, %d more to come)\n",
378 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
379 s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos);
381 event_t* e = event_new();
382 e->type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
387 if(queue) queue_put(queue, e);
388 else hqueue_put(hqueue, e);
390 if(e->type != EVENT_HORIZONTAL) {
400 static void gfxpoly_enqueue(gfxpoly_t*p, queue_t*queue, hqueue_t*hqueue, int polygon_nr)
403 gfxpolystroke_t*stroke = p->strokes;
404 for(;stroke;stroke=stroke->next) {
405 assert(stroke->num_points > 1);
409 for(s=0;s<stroke->num_points-1;s++) {
410 assert(stroke->points[s].y <= stroke->points[s+1].y);
413 advance_stroke(queue, hqueue, stroke, polygon_nr, 0);
417 static void schedule_endpoint(status_t*status, segment_t*s)
419 // schedule end point of segment
420 assert(s->b.y > status->y);
421 event_t*e = event_new();
426 queue_put(&status->queue, e);
429 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
431 /* the code that's required (and the checks you can perform) before
432 it can be said with 100% certainty that we indeed have a valid crossing
433 amazes me every time. -mk */
436 assert(s1->right == s2);
437 assert(s2->left == s1);
438 int32_t miny1 = min32(s1->a.y,s1->b.y);
439 int32_t maxy1 = max32(s1->a.y,s1->b.y);
440 int32_t miny2 = min32(s2->a.y,s2->b.y);
441 int32_t maxy2 = max32(s2->a.y,s2->b.y);
442 int32_t minx1 = min32(s1->a.x,s1->b.x);
443 int32_t minx2 = min32(s2->a.x,s2->b.x);
444 int32_t maxx1 = max32(s1->a.x,s1->b.x);
445 int32_t maxx2 = max32(s2->a.x,s2->b.x);
446 /* check that precomputation is sane */
447 assert(minx1 == s1->minx && minx2 == s2->minx);
448 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
449 /* both segments are active, so this can't happen */
450 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
451 /* we know that right now, s2 is to the right of s1, so there's
452 no way the complete bounding box of s1 is to the right of s1 */
453 assert(!(s1->minx > s2->maxx));
454 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
457 if(s1->maxx <= s2->minx) {
459 fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
461 /* bounding boxes don't intersect */
465 #ifndef DONT_REMEMBER_CROSSINGS
466 if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
467 /* FIXME: this whole segment hashing thing is really slow */
469 fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
470 // DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
471 // fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
474 return; // we already know about this one
478 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
481 // lines are exactly on top of each other (ignored)
483 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
488 fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
490 /* lines are parallel */
495 double asign2 = LINE_EQ(s1->a, s2);
497 // segment1 touches segment2 in a single point (ignored)
499 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
503 double bsign2 = LINE_EQ(s1->b, s2);
505 // segment1 touches segment2 in a single point (ignored)
507 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
512 if(asign2<0 && bsign2<0) {
513 // segment1 is completely to the left of segment2
515 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);
519 if(asign2>0 && bsign2>0) {
520 // segment1 is completely to the right of segment2
521 #ifndef DONT_REMEMBER_CROSSINGS
525 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);
530 double asign1 = LINE_EQ(s2->a, s1);
532 // segment2 touches segment1 in a single point (ignored)
534 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
538 double bsign1 = LINE_EQ(s2->b, s1);
540 // segment2 touches segment1 in a single point (ignored)
542 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
547 if(asign1<0 && bsign1<0) {
548 // segment2 is completely to the left of segment1
549 #ifndef DONT_REMEMBER_CROSSINGS
553 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);
557 if(asign1>0 && bsign1>0) {
558 // segment2 is completely to the right of segment1
560 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);
565 #ifdef DONT_REMEMBER_CROSSINGS
566 /* s2 crosses s1 from *left* to *right*. This is a crossing we already processed-
567 there's not way s2 would be to the left of s1 otherwise */
568 if(asign1<0 && bsign1>0) return;
569 if(asign2>0 && bsign2<0) return;
572 assert(!(asign1<0 && bsign1>0));
573 assert(!(asign2>0 && bsign2<0));
575 /* TODO: should we precompute these? */
576 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
577 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
580 p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
581 p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
583 assert(p.y >= status->y);
585 assert(p.x >= s1->minx && p.x <= s1->maxx);
586 assert(p.x >= s2->minx && p.x <= s2->maxx);
591 #ifndef DONT_REMEMBER_CROSSINGS
592 assert(!dict_contains(status->seen_crossings, &pair));
593 dict_put(status->seen_crossings, &pair, 0);
597 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
600 #ifndef DONT_REMEMBER_CROSSINGS
601 /* we insert into each other's intersection history because these segments might switch
602 places and we still want to look them up quickly after they did */
603 dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
604 dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
607 event_t* e = event_new();
608 e->type = EVENT_CROSS;
612 queue_put(&status->queue, e);
616 static void exchange_two(status_t*status, event_t*e)
618 //exchange two segments in list
619 segment_t*s1 = e->s1;
620 segment_t*s2 = e->s2;
622 if(!dict_contains(status->intersecting_segs, s1))
623 dict_put(status->intersecting_segs, s1, 0);
624 if(!dict_contains(status->intersecting_segs, s2))
625 dict_put(status->intersecting_segs, s2, 0);
627 assert(s2->left == s1);
628 assert(s1->right == s2);
629 actlist_swap(status->actlist, s1, s2);
630 assert(s2->right == s1);
631 assert(s1->left == s2);
632 segment_t*left = s2->left;
633 segment_t*right = s1->right;
635 schedule_crossing(status, left, s2);
637 schedule_crossing(status, s1, right);
640 typedef struct _box {
641 point_t left1, left2, right1, right2;
643 static inline box_t box_new(int32_t x, int32_t y)
646 box.right1.x = box.right2.x = x;
647 box.left1.x = box.left2.x = x-1;
648 box.left1.y = box.right1.y = y-1;
649 box.left2.y = box.right2.y = y;
653 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
655 assert(s->pos.x != p.x || s->pos.y != p.y);
658 if(!dict_contains(status->segs_with_point, s))
659 dict_put(status->segs_with_point, s, 0);
660 assert(s->fs_out_ok);
665 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
666 s->pos.x, s->pos.y, p.x, p.y);
668 edgestyle_t*fs = s->fs_out;
670 // omit horizontal lines
671 if(s->pos.y != p.y) {
676 gfxpolystroke_t*stroke = status->strokes;
677 /* find a stoke to attach this segment to. It has to have an endpoint
678 matching our start point, and a matching edgestyle */
680 point_t p = stroke->points[stroke->num_points-1];
681 if(p.x == a.x && p.y == a.y && stroke->fs == fs)
683 stroke = stroke->next;
686 stroke = rfx_calloc(sizeof(gfxpolystroke_t));
687 stroke->dir = DIR_DOWN;
689 stroke->next = status->strokes;
690 status->strokes = stroke;
691 stroke->points_size = 2;
692 stroke->points = rfx_calloc(sizeof(point_t)*stroke->points_size);
693 stroke->points[0] = a;
694 stroke->num_points = 1;
695 } else if(stroke->num_points == stroke->points_size) {
697 stroke->points_size *= 2;
698 stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size);
700 stroke->points[stroke->num_points++] = b;
704 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
710 typedef struct _segrange {
717 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
719 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
720 segment_t*min = range->segmin;
721 segment_t*max = range->segmax;
723 /* we need this because if two segments intersect exactly on
724 the scanline, segrange_test_segment_{min,max} can't tell which
725 one is smaller/larger */
726 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
729 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
735 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
738 /* we need to calculate the xpos anew (and can't use start coordinate or
739 intersection coordinate), because we need the xpos exactly at the end of
742 double x = XPOS(seg, y);
743 if(!range->segmin || x<range->xmin) {
748 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
751 double x = XPOS(seg, y);
752 if(!range->segmax || x>range->xmax) {
767 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
769 segment_t*first=0, *last = 0;
771 for(t=0;t<status->xrow->num;t++) {
772 box_t box = box_new(status->xrow->x[t], y);
773 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
775 seg = actlist_right(status->actlist, seg);
778 // this segment started in this scanline, ignore it
779 seg->changed = 1;last = seg;if(!first) {first=seg;}
780 } else if(seg->delta.x <= 0) {
781 // ignore segment w/ negative slope
783 last = seg;if(!first) {first=seg;}
784 double d1 = LINE_EQ(box.right1, seg);
785 double d2 = LINE_EQ(box.right2, seg);
788 insert_point_into_segment(status, seg, box.right2);
790 /* we unfortunately can't break here- the active list is sorted according
791 to the *bottom* of the scanline. hence pretty much everything that's still
792 coming might reach into our box */
799 segrange_test_segment_min(range, first, y);
800 segrange_test_segment_max(range, last, y);
810 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
812 segment_t*first=0, *last = 0;
814 for(t=status->xrow->num-1;t>=0;t--) {
815 box_t box = box_new(status->xrow->x[t], y);
816 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
820 // this segment started in this scanline, ignore it
821 seg->changed = 1;last = seg;if(!first) {first=seg;}
822 } else if(seg->delta.x > 0) {
823 // ignore segment w/ positive slope
825 last = seg;if(!first) {first=seg;}
826 double d1 = LINE_EQ(box.left1, seg);
827 double d2 = LINE_EQ(box.left2, seg);
830 insert_point_into_segment(status, seg, box.right2);
838 segrange_test_segment_min(range, last, y);
839 segrange_test_segment_max(range, first, y);
842 /* segments ending in the current scanline need xrow treatment like everything else.
843 (consider an intersection taking place just above a nearly horizontal segment
844 ending on the current scanline- the intersection would snap down *below* the
845 ending segment if we don't add the intersection point to the latter right away)
846 we need to treat ending segments seperately, however. we have to delete them from
847 the active list right away to make room for intersect operations (which might
848 still be in the current scanline- consider two 45° polygons and a vertical polygon
849 intersecting on an integer coordinate). but once they're no longer in the active list,
850 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
851 them to the active list just for point snapping would be overkill.
852 (One other option to consider, however, would be to create a new active list only
855 static void add_points_to_ending_segments(status_t*status, int32_t y)
857 segment_t*seg = status->ending_segments;
859 segment_t*next = seg->right;seg->right=0;
861 assert(seg->b.y == status->y);
863 if(status->xrow->num == 1) {
865 assert(seg->b.x == status->xrow->x[0]);
866 point_t p = {status->xrow->x[0], y};
867 insert_point_into_segment(status, seg, p);
870 int start=0,end=status->xrow->num,dir=1;
871 if(seg->delta.x < 0) {
872 start = status->xrow->num-1;
875 for(t=start;t!=end;t+=dir) {
876 box_t box = box_new(status->xrow->x[t], y);
877 double d0 = LINE_EQ(box.left1, seg);
878 double d1 = LINE_EQ(box.left2, seg);
879 double d2 = LINE_EQ(box.right1, seg);
880 double d3 = LINE_EQ(box.right2, seg);
881 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
882 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
883 insert_point_into_segment(status, seg, box.right2);
889 /* we *need* to find a point to insert. the segment's own end point
890 is in that list, for Pete's sake. */
894 // now that this is done, too, we can also finally free this segment
895 segment_destroy(seg);
898 status->ending_segments = 0;
901 static void recalculate_windings(status_t*status, segrange_t*range)
904 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
906 segrange_adjust_endpoints(range, status->y);
908 segment_t*s = range->segmin;
909 segment_t*end = range->segmax;
913 s = actlist_leftmost(status->actlist);
915 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
916 s == range->segmin?"S":(
917 s == range->segmax?"E":""));
920 fprintf(stderr, "\n");
924 /* test sanity: verify that we don't have changed segments
925 outside of the given range */
926 s = actlist_leftmost(status->actlist);
927 while(s && s!=range->segmin) {
931 s = actlist_rightmost(status->actlist);
932 while(s && s!=range->segmax) {
936 /* in check mode, go through the whole interval so we can test
937 that all polygons where the edgestyle changed also have seg->changed=1 */
938 s = actlist_leftmost(status->actlist);
949 segment_t* left = actlist_left(status->actlist, s);
950 windstate_t wind = left?left->wind:status->windrule->start(status->context);
951 s->wind = status->windrule->add(status->context, wind, s->fs_orig, s->dir, s->polygon_nr);
952 edgestyle_t*fs_old = s->fs_out;
953 s->fs_out = status->windrule->diff(&wind, &s->wind);
956 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",
957 fs_old?"draw":"omit", s->fs_out?"draw":"omit",
958 fs_old!=s->fs_out?"CHANGED":"");
960 assert(!(!s->changed && fs_old!=s->fs_out));
971 /* we need to handle horizontal lines in order to add points to segments
972 we otherwise would miss during the windrule re-evaluation */
973 static void intersect_with_horizontal(status_t*status, segment_t*h)
975 segment_t* left = actlist_find(status->actlist, h->a, h->a);
976 segment_t* right = actlist_find(status->actlist, h->b, h->b);
978 /* not strictly necessary, also done by the event */
979 xrow_add(status->xrow, h->a.x);
987 left = actlist_right(status->actlist, left); //first seg to the right of h->a
988 right = right->right; //first seg to the right of h->b
993 int32_t x = XPOS_INT(s, status->y);
995 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
1001 assert(x >= h->a.x);
1002 assert(x <= h->b.x);
1003 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
1004 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
1005 xrow_add(status->xrow, x);
1011 static void event_apply(status_t*status, event_t*e)
1014 case EVENT_HORIZONTAL: {
1015 segment_t*s = e->s1;
1019 intersect_with_horizontal(status, s);
1020 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1021 segment_destroy(s);e->s1=0;
1025 //delete segment from list
1026 segment_t*s = e->s1;
1031 dict_del(status->intersecting_segs, s);
1032 dict_del(status->segs_with_point, s);
1033 assert(!dict_contains(status->intersecting_segs, s));
1034 assert(!dict_contains(status->segs_with_point, s));
1036 segment_t*left = s->left;
1037 segment_t*right = s->right;
1038 actlist_delete(status->actlist, s);
1040 schedule_crossing(status, left, right);
1042 /* schedule segment for xrow handling */
1043 s->left = 0; s->right = status->ending_segments;
1044 status->ending_segments = s;
1045 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1049 //insert segment into list
1053 segment_t*s = e->s1;
1054 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1055 actlist_insert(status->actlist, s->a, s->b, s);
1056 segment_t*left = s->left;
1057 segment_t*right = s->right;
1059 schedule_crossing(status, left, s);
1061 schedule_crossing(status, s, right);
1062 schedule_endpoint(status, s);
1066 // exchange two segments
1070 if(e->s1->right == e->s2) {
1071 assert(e->s2->left == e->s1);
1072 exchange_two(status, e);
1074 assert(e->s2->left != e->s1);
1076 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1078 #ifndef DONT_REMEMBER_CROSSINGS
1079 /* ignore this crossing for now (there are some line segments in between).
1080 it'll get rescheduled as soon as the "obstacles" are gone */
1081 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1082 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1083 assert(del1 && del2);
1089 #ifndef DONT_REMEMBER_CROSSINGS
1090 assert(dict_contains(status->seen_crossings, &pair));
1091 dict_del(status->seen_crossings, &pair);
1100 static void check_status(status_t*status)
1102 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1103 if((s->pos.x != s->b.x ||
1104 s->pos.y != s->b.y) &&
1105 !dict_contains(status->segs_with_point, s)) {
1106 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1108 s->delta.x<0?"-":"+",
1116 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1119 |..| |...........| | |
1120 |..| |...........| | |
1121 |..+ + +..| +--+ +--+
1122 |...........| |..| | |
1123 |...........| |..| | |
1127 fprintf(stderr, "========================================================================\n");
1130 hqueue_init(&hqueue);
1131 gfxpoly_enqueue(poly, 0, &hqueue, 0);
1133 actlist_t* actlist = actlist_new();
1135 event_t*e = hqueue_get(&hqueue);
1139 windstate_t w = windrule->start(context);
1141 fprintf(stderr, "HORIZONTALS ----------------------------------- %d\n", y);
1142 actlist_dump(actlist, y-1);
1145 actlist_verify(actlist, y-1);
1147 edgestyle_t*fill = 0;
1148 edgestyle_t*fill2 = 0;
1151 assert(e->s1->fs_orig);
1152 if(fill && x != e->p.x) {
1154 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
1158 gfxpolystroke_t*stroke = rfx_calloc(sizeof(gfxpolystroke_t));
1159 stroke->next = poly->strokes;
1160 poly->strokes = stroke;
1162 stroke->num_points = 2;
1163 stroke->points = malloc(sizeof(point_t)*2);
1164 stroke->dir = DIR_UP; // FIXME
1168 /* we draw from low x to high x so that left/right fillstyles add up
1169 (because the horizontal line's fill style controls the area *below* the line)
1173 stroke->points[0] = a;
1174 stroke->points[1] = b;
1176 /* the output should always be intersection free polygons, so check this horizontal
1177 line isn't puncturing any segments in the active list */
1178 segment_t* start = actlist_find(actlist, b, b);
1179 segment_t* s = actlist_find(actlist, a, a);
1181 assert(s->a.y == y || s->b.y == y);
1194 edgestyle_t*old_fill = fill;
1195 windstate_t before1 = w;
1197 /* the current horizontal line is between before1 and before2: */
1198 windstate_t before2 = fill?windrule->add(context, before1, fill, DIR_UNKNOWN, -1):before1;
1201 segment_t*s = e->s1;
1207 after2 = windrule->add(context, before2, s->fs_orig, DIR_UNKNOWN, s->polygon_nr);
1211 after1 = windrule->add(context, before1, s->fs_orig, DIR_UNKNOWN, s->polygon_nr);
1217 fill2 = windrule->diff(&after1, &after2);
1222 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1223 actlist_insert(actlist, s->a, s->b, s);
1224 event_t* e = event_new();
1225 e->type = EVENT_END;
1229 hqueue_put(&hqueue, e);
1230 left = actlist_left(actlist, s);
1234 left = actlist_left(actlist, s);
1235 actlist_delete(actlist, s);
1236 advance_stroke(0, &hqueue, s->stroke, s->polygon_nr, s->stroke_pos);
1244 if(windrule==&windrule_evenodd) {
1245 fill = fill?0:&edgestyle_default;
1246 if(!!fill != !!fill2) {
1249 printf("at y=%d x=%d (hline:%p)\n", e->p.y, x, old_fill);
1250 if(e->type==EVENT_END) {
1251 printf(" %9p\n", s->fs_orig);
1254 printf(" %3d %c%2d \n", before1.is_filled, e->type==EVENT_END?'|':' ', after1.is_filled);
1255 printf("%12p -----+----- %p\n", old_fill, fill2);
1256 printf(" %3d %c%2d \n", before2.is_filled, e->type==EVENT_START?'|':' ', after2.is_filled);
1257 if(e->type==EVENT_START) {
1259 printf(" %9p\n", s->fs_orig);
1262 assert(!!fill == !!fill2);
1267 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d\n",
1268 y, e->type==EVENT_START?"start":"end",
1274 if(e->type == EVENT_END)
1278 e = hqueue_get(&hqueue);
1279 } while(e && y == e->p.y);
1282 edgestyle_t*bleeding = fill;
1287 actlist_destroy(actlist);
1288 hqueue_destroy(&hqueue);
1291 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly1, gfxpoly_t*poly2, windrule_t*windrule, windcontext_t*context)
1293 current_polygon = poly1;
1296 memset(&status, 0, sizeof(status_t));
1297 queue_init(&status.queue);
1298 gfxpoly_enqueue(poly1, &status.queue, 0, /*polygon nr*/0);
1300 assert(poly1->gridsize == poly2->gridsize);
1301 gfxpoly_enqueue(poly2, &status.queue, 0, /*polygon nr*/1);
1304 status.windrule = windrule;
1305 status.context = context;
1306 status.actlist = actlist_new();
1309 status.seen_crossings = dict_new2(&point_type);
1310 int32_t lasty=-0x80000000;
1313 status.xrow = xrow_new();
1315 event_t*e = queue_get(&status.queue);
1317 assert(e->s1->fs_orig);
1320 assert(status.y>=lasty);
1322 status.intersecting_segs = dict_new2(&ptr_type);
1323 status.segs_with_point = dict_new2(&ptr_type);
1327 fprintf(stderr, "----------------------------------- %d\n", status.y);
1328 actlist_dump(status.actlist, status.y-1);
1331 actlist_verify(status.actlist, status.y-1);
1333 xrow_reset(status.xrow);
1335 xrow_add(status.xrow, e->p.x);
1336 event_apply(&status, e);
1338 e = queue_get(&status.queue);
1339 } while(e && status.y == e->p.y);
1341 xrow_sort(status.xrow);
1343 memset(&range, 0, sizeof(range));
1345 actlist_dump(status.actlist, status.y);
1347 add_points_to_positively_sloped_segments(&status, status.y, &range);
1348 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1349 add_points_to_ending_segments(&status, status.y);
1351 recalculate_windings(&status, &range);
1353 check_status(&status);
1354 dict_destroy(status.intersecting_segs);
1355 dict_destroy(status.segs_with_point);
1359 dict_destroy(status.seen_crossings);
1361 actlist_destroy(status.actlist);
1362 queue_destroy(&status.queue);
1363 xrow_destroy(status.xrow);
1365 gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t));
1366 p->gridsize = poly1->gridsize;
1367 p->strokes = status.strokes;
1370 /* we only add segments with non-empty edgestyles to strokes in
1371 recalculate_windings, but better safe than sorry */
1372 gfxpolystroke_t*stroke = p->strokes;
1375 stroke = stroke->next;
1379 add_horizontals(p, &windrule_evenodd, context); // output is always even/odd
1380 //add_horizontals(p, windrule, context);
1384 static windcontext_t twopolygons = {2};
1385 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*p1, gfxpoly_t*p2)
1387 return gfxpoly_process(p1, p2, &windrule_intersect, &twopolygons);
1389 gfxpoly_t* gfxpoly_union(gfxpoly_t*p1, gfxpoly_t*p2)
1391 return gfxpoly_process(p1, p2, &windrule_union, &twopolygons);