15 static gfxpoly_t*current_polygon = 0;
16 void gfxpoly_fail(char*expr, char*file, int line, const char*function)
18 if(!current_polygon) {
19 fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
23 void*md5 = init_md5();
26 gfxpolystroke_t*stroke = current_polygon->strokes;
27 for(;stroke;stroke=stroke->next) {
28 for(t=0;t<stroke->num_points;t++) {
29 update_md5(md5, (unsigned char*)&stroke->points[t].x, sizeof(stroke->points[t].x));
30 update_md5(md5, (unsigned char*)&stroke->points[t].y, sizeof(stroke->points[t].y));
34 char filename[32+4+1];
36 sprintf(filename, "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x.ps",
37 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]);
39 fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
40 fprintf(stderr, "I'm saving a debug file \"%s\" to the current directory.\n", filename);
42 gfxpoly_save(current_polygon, filename);
46 static char point_equals(const void*o1, const void*o2)
48 const point_t*p1 = o1;
49 const point_t*p2 = o2;
50 return p1->x == p2->x && p1->y == p2->y;
52 static unsigned int point_hash(const void*o)
57 static void* point_dup(const void*o)
60 point_t*n = malloc(sizeof(point_t));
65 static void point_free(void*o)
72 static type_t point_type = {
79 typedef struct _event {
86 /* compare_events_simple differs from compare_events in that it schedules
87 events from left to right regardless of type. It's only used in horizontal
88 processing, in order to get an x-wise sorting of the current scanline */
89 static inline int compare_events_simple(const void*_a,const void*_b)
91 event_t* a = (event_t*)_a;
92 event_t* b = (event_t*)_b;
93 int d = b->p.y - a->p.y;
100 static inline int compare_events(const void*_a,const void*_b)
102 event_t* a = (event_t*)_a;
103 event_t* b = (event_t*)_b;
104 int d = b->p.y - a->p.y;
106 /* we need to schedule end after intersect (so that a segment about
107 to end has a chance to tear up a few other segs first) and start
108 events after end (in order not to confuse the intersection check, which
109 assumes there's an actual y overlap between active segments, and
110 because ending segments in the active list make it difficult to insert
111 starting segments at the right position)).
112 Horizontal lines come last, because the only purpose
113 they have is to create snapping coordinates for the segments (still)
114 existing in this scanline.
116 d = b->type - a->type;
120 /* I don't see any reason why we would need to order by x- at least as long
121 as we do horizontal lines in a seperate pass */
122 //d = b->p.x - a->p.x;
126 #define COMPARE_EVENTS(x,y) (compare_events(x,y)>0)
127 #define COMPARE_EVENTS_SIMPLE(x,y) (compare_events_simple(x,y)>0)
128 HEAP_DEFINE(queue,event_t,COMPARE_EVENTS);
129 HEAP_DEFINE(hqueue,event_t,COMPARE_EVENTS_SIMPLE);
131 typedef struct _status {
137 windcontext_t*context;
138 segment_t*ending_segments;
140 gfxpolystroke_t*strokes;
142 dict_t*seen_crossings; //list of crossing we saw so far
143 dict_t*intersecting_segs; //list of segments intersecting in this scanline
144 dict_t*segs_with_point; //lists of segments that received a point in this scanline
149 int gfxpoly_size(gfxpoly_t*poly)
153 gfxpolystroke_t*stroke = poly->strokes;
154 for(;stroke;stroke=stroke->next) {
155 edges += stroke->num_points-1;
160 char gfxpoly_check(gfxpoly_t*poly)
162 dict_t*d = dict_new2(&point_type);
164 gfxpolystroke_t*stroke = poly->strokes;
165 for(;stroke;stroke=stroke->next) {
166 for(s=0;s<stroke->num_points;s++) {
167 point_t p = stroke->points[s];
168 int num = (s>=1 && s<stroke->num_points-1)?2:1; // mid points are two points (start+end)
169 if(!dict_contains(d, &p)) {
170 dict_put(d, &p, (void*)(ptroff_t)num);
172 int count = (ptroff_t)dict_lookup(d, &p);
175 dict_put(d, &p, (void*)(ptroff_t)count);
179 DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
180 int count = (ptroff_t)c;
182 fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count);
191 void gfxpoly_dump(gfxpoly_t*poly)
194 double g = poly->gridsize;
195 fprintf(stderr, "polyon %08x (gridsize: %f)\n", poly, poly->gridsize);
196 gfxpolystroke_t*stroke = poly->strokes;
197 for(;stroke;stroke=stroke->next) {
198 fprintf(stderr, "%08x", stroke);
199 for(s=0;s<stroke->num_points-1;s++) {
200 point_t a = stroke->points[s];
201 point_t b = stroke->points[s+1];
202 fprintf(stderr, "%s (%f,%f) -> (%f,%f)%s\n", s?" ":"", a.x*g, a.y*g, b.x*g, b.y*g,
203 s==stroke->num_points-2?"]":"");
208 void gfxpoly_save(gfxpoly_t*poly, const char*filename)
210 FILE*fi = fopen(filename, "wb");
211 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
212 fprintf(fi, "%% begin\n");
214 gfxpolystroke_t*stroke = poly->strokes;
215 for(;stroke;stroke=stroke->next) {
216 fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
217 point_t p = stroke->points[0];
218 fprintf(fi, "%d %d moveto\n", p.x, p.y);
219 for(s=1;s<stroke->num_points;s++) {
220 p = stroke->points[s];
221 fprintf(fi, "%d %d lineto\n", p.x, p.y);
223 fprintf(fi, "stroke\n");
225 fprintf(fi, "showpage\n");
229 inline static event_t* event_new()
231 event_t*e = rfx_calloc(sizeof(event_t));
234 inline static void event_free(event_t*e)
239 static void event_dump(event_t*e)
241 if(e->type == EVENT_HORIZONTAL) {
242 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);
243 } else if(e->type == EVENT_START) {
244 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
245 } else if(e->type == EVENT_END) {
246 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
247 } else if(e->type == EVENT_CROSS) {
248 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
254 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
255 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
257 static void segment_dump(segment_t*s)
259 fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
260 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k,
261 (double)s->delta.x / s->delta.y);
264 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)
270 /* We need to make sure horizontal segments always go from left to right.
271 "up/down" for horizontal segments is handled by "rotating"
272 them 90° anticlockwise in screen coordinates (tilt your head to
278 int32_t x = x1;x1=x2;x2=x;
279 int32_t y = y1;y1=y2;y2=y;
286 s->k = (double)x1*y2-(double)x2*y1;
287 s->left = s->right = 0;
290 s->minx = min32(x1,x2);
291 s->maxx = max32(x1,x2);
294 s->polygon_nr = polygon_nr;
295 static int segment_count=0;
296 s->nr = segment_count++;
299 assert(LINE_EQ(s->a, s) == 0);
300 assert(LINE_EQ(s->b, s) == 0);
302 /* check that all signs are in order:
310 p.x = min32(s->a.x, s->b.x);
311 assert(LINE_EQ(p, s) <= 0);
312 p.x = max32(s->a.x, s->b.x);
313 assert(LINE_EQ(p, s) >= 0);
316 #ifndef DONT_REMEMBER_CROSSINGS
317 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
321 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
323 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
324 segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
328 static void segment_clear(segment_t*s)
330 #ifndef DONT_REMEMBER_CROSSINGS
331 dict_clear(&s->scheduled_crossings);
334 static void segment_destroy(segment_t*s)
340 static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*stroke, int polygon_nr, int pos)
345 /* we need to queue multiple segments at once because we need to process start events
346 before horizontal events */
347 while(pos < stroke->num_points-1) {
348 assert(stroke->points[pos].y <= stroke->points[pos+1].y);
349 s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
356 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (stroke %08x, %d more to come)\n",
357 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
358 s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos);
360 event_t* e = event_new();
361 e->type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
366 if(queue) queue_put(queue, e);
367 else hqueue_put(hqueue, e);
369 if(e->type != EVENT_HORIZONTAL) {
375 fprintf(stderr, "attaching contingency of stroke %08x to segment [%d] %s\n",
376 stroke, s, s->delta.y?"":"(horizontal)");
383 static void gfxpoly_enqueue(gfxpoly_t*p, queue_t*queue, hqueue_t*hqueue, int polygon_nr)
386 gfxpolystroke_t*stroke = p->strokes;
387 for(;stroke;stroke=stroke->next) {
388 assert(stroke->num_points > 1);
392 for(s=0;s<stroke->num_points-1;s++) {
393 assert(stroke->points[s].y <= stroke->points[s+1].y);
396 advance_stroke(queue, hqueue, stroke, polygon_nr, 0);
400 static void schedule_endpoint(status_t*status, segment_t*s)
402 // schedule end point of segment
403 assert(s->b.y > status->y);
404 event_t*e = event_new();
409 queue_put(&status->queue, e);
412 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
414 /* the code that's required (and the checks you can perform) before
415 it can be said with 100% certainty that we indeed have a valid crossing
416 amazes me every time. -mk */
419 assert(s1->right == s2);
420 assert(s2->left == s1);
421 int32_t miny1 = min32(s1->a.y,s1->b.y);
422 int32_t maxy1 = max32(s1->a.y,s1->b.y);
423 int32_t miny2 = min32(s2->a.y,s2->b.y);
424 int32_t maxy2 = max32(s2->a.y,s2->b.y);
425 int32_t minx1 = min32(s1->a.x,s1->b.x);
426 int32_t minx2 = min32(s2->a.x,s2->b.x);
427 int32_t maxx1 = max32(s1->a.x,s1->b.x);
428 int32_t maxx2 = max32(s2->a.x,s2->b.x);
429 /* check that precomputation is sane */
430 assert(minx1 == s1->minx && minx2 == s2->minx);
431 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
432 /* both segments are active, so this can't happen */
433 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
434 /* we know that right now, s2 is to the right of s1, so there's
435 no way the complete bounding box of s1 is to the right of s1 */
436 assert(!(s1->minx > s2->maxx));
437 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
440 if(s1->maxx <= s2->minx) {
442 fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
444 /* bounding boxes don't intersect */
448 #ifndef DONT_REMEMBER_CROSSINGS
449 if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
450 /* FIXME: this whole segment hashing thing is really slow */
452 fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
453 // DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
454 // fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
457 return; // we already know about this one
461 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
464 // lines are exactly on top of each other (ignored)
466 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
471 fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
473 /* lines are parallel */
478 double asign2 = LINE_EQ(s1->a, s2);
480 // segment1 touches segment2 in a single point (ignored)
482 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
486 double bsign2 = LINE_EQ(s1->b, s2);
488 // segment1 touches segment2 in a single point (ignored)
490 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
495 if(asign2<0 && bsign2<0) {
496 // segment1 is completely to the left of segment2
498 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);
502 if(asign2>0 && bsign2>0) {
503 // segment1 is completely to the right of segment2
504 #ifndef DONT_REMEMBER_CROSSINGS
508 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);
513 double asign1 = LINE_EQ(s2->a, s1);
515 // segment2 touches segment1 in a single point (ignored)
517 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
521 double bsign1 = LINE_EQ(s2->b, s1);
523 // segment2 touches segment1 in a single point (ignored)
525 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
530 if(asign1<0 && bsign1<0) {
531 // segment2 is completely to the left of segment1
532 #ifndef DONT_REMEMBER_CROSSINGS
536 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);
540 if(asign1>0 && bsign1>0) {
541 // segment2 is completely to the right of segment1
543 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);
548 #ifdef DONT_REMEMBER_CROSSINGS
549 /* s2 crosses s1 from *left* to *right*. This is a crossing we already processed-
550 there's not way s2 would be to the left of s1 otherwise */
551 if(asign1<0 && bsign1>0) return;
552 if(asign2>0 && bsign2<0) return;
555 assert(!(asign1<0 && bsign1>0));
556 assert(!(asign2>0 && bsign2<0));
558 /* TODO: should we precompute these? */
559 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
560 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
563 p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
564 p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
566 assert(p.y >= status->y);
568 assert(p.x >= s1->minx && p.x <= s1->maxx);
569 assert(p.x >= s2->minx && p.x <= s2->maxx);
574 #ifndef DONT_REMEMBER_CROSSINGS
575 assert(!dict_contains(status->seen_crossings, &pair));
576 dict_put(status->seen_crossings, &pair, 0);
580 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
583 #ifndef DONT_REMEMBER_CROSSINGS
584 /* we insert into each other's intersection history because these segments might switch
585 places and we still want to look them up quickly after they did */
586 dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
587 dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
590 event_t* e = event_new();
591 e->type = EVENT_CROSS;
595 queue_put(&status->queue, e);
599 static void exchange_two(status_t*status, event_t*e)
601 //exchange two segments in list
602 segment_t*s1 = e->s1;
603 segment_t*s2 = e->s2;
605 if(!dict_contains(status->intersecting_segs, s1))
606 dict_put(status->intersecting_segs, s1, 0);
607 if(!dict_contains(status->intersecting_segs, s2))
608 dict_put(status->intersecting_segs, s2, 0);
610 assert(s2->left == s1);
611 assert(s1->right == s2);
612 actlist_swap(status->actlist, s1, s2);
613 assert(s2->right == s1);
614 assert(s1->left == s2);
615 segment_t*left = s2->left;
616 segment_t*right = s1->right;
618 schedule_crossing(status, left, s2);
620 schedule_crossing(status, s1, right);
623 typedef struct _box {
624 point_t left1, left2, right1, right2;
626 static inline box_t box_new(int32_t x, int32_t y)
629 box.right1.x = box.right2.x = x;
630 box.left1.x = box.left2.x = x-1;
631 box.left1.y = box.right1.y = y-1;
632 box.left2.y = box.right2.y = y;
636 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
638 assert(s->pos.x != p.x || s->pos.y != p.y);
641 if(!dict_contains(status->segs_with_point, s))
642 dict_put(status->segs_with_point, s, 0);
643 assert(s->fs_out_ok);
648 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
649 s->pos.x, s->pos.y, p.x, p.y);
651 /* XXX we probably will never output circular/anticircular polygons, but if
652 we do, we would need to set the segment direction here */
653 fillstyle_t*fs = s->fs_out;
655 // omit horizontal lines
656 if(s->pos.y != p.y) {
661 gfxpolystroke_t*stroke = status->strokes;
663 point_t p = stroke->points[stroke->num_points-1];
664 if(p.x == a.x && p.y == a.y && stroke->fs == fs)
666 stroke = stroke->next;
669 stroke = rfx_calloc(sizeof(gfxpolystroke_t));
670 stroke->dir = DIR_DOWN;
672 stroke->next = status->strokes;
673 status->strokes = stroke;
674 stroke->points_size = 2;
675 stroke->points = rfx_calloc(sizeof(point_t)*stroke->points_size);
676 stroke->points[0] = a;
677 stroke->num_points = 1;
678 } else if(stroke->num_points == stroke->points_size) {
679 stroke->points_size *= 2;
680 stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size);
682 stroke->points[stroke->num_points++] = b;
686 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
692 typedef struct _segrange {
699 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
701 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
702 segment_t*min = range->segmin;
703 segment_t*max = range->segmax;
705 /* we need this because if two segments intersect exactly on
706 the scanline, segrange_test_segment_{min,max} can't tell which
707 one is smaller/larger */
708 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
711 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
717 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
720 /* we need to calculate the xpos anew (and can't use start coordinate or
721 intersection coordinate), because we need the xpos exactly at the end of
724 double x = XPOS(seg, y);
725 if(!range->segmin || x<range->xmin) {
730 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
733 double x = XPOS(seg, y);
734 if(!range->segmax || x>range->xmax) {
749 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
751 segment_t*first=0, *last = 0;
753 for(t=0;t<status->xrow->num;t++) {
754 box_t box = box_new(status->xrow->x[t], y);
755 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
757 seg = actlist_right(status->actlist, seg);
760 // this segment started in this scanline, ignore it
761 seg->changed = 1;last = seg;if(!first) {first=seg;}
762 } else if(seg->delta.x <= 0) {
763 // ignore segment w/ negative slope
765 last = seg;if(!first) {first=seg;}
766 double d1 = LINE_EQ(box.right1, seg);
767 double d2 = LINE_EQ(box.right2, seg);
770 insert_point_into_segment(status, seg, box.right2);
772 /* we unfortunately can't break here- the active list is sorted according
773 to the *bottom* of the scanline. hence pretty much everything that's still
774 coming might reach into our box */
781 segrange_test_segment_min(range, first, y);
782 segrange_test_segment_max(range, last, y);
792 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
794 segment_t*first=0, *last = 0;
796 for(t=status->xrow->num-1;t>=0;t--) {
797 box_t box = box_new(status->xrow->x[t], y);
798 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
802 // this segment started in this scanline, ignore it
803 seg->changed = 1;last = seg;if(!first) {first=seg;}
804 } else if(seg->delta.x > 0) {
805 // ignore segment w/ positive slope
807 last = seg;if(!first) {first=seg;}
808 double d1 = LINE_EQ(box.left1, seg);
809 double d2 = LINE_EQ(box.left2, seg);
812 insert_point_into_segment(status, seg, box.right2);
820 segrange_test_segment_min(range, last, y);
821 segrange_test_segment_max(range, first, y);
824 /* segments ending in the current scanline need xrow treatment like everything else.
825 (consider an intersection taking place just above a nearly horizontal segment
826 ending on the current scanline- the intersection would snap down *below* the
827 ending segment if we don't add the intersection point to the latter right away)
828 we need to treat ending segments seperately, however. we have to delete them from
829 the active list right away to make room for intersect operations (which might
830 still be in the current scanline- consider two 45° polygons and a vertical polygon
831 intersecting on an integer coordinate). but once they're no longer in the active list,
832 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
833 them to the active list just for point snapping would be overkill.
834 (One other option to consider, however, would be to create a new active list only
837 static void add_points_to_ending_segments(status_t*status, int32_t y)
839 segment_t*seg = status->ending_segments;
841 segment_t*next = seg->right;seg->right=0;
843 assert(seg->b.y == status->y);
845 if(status->xrow->num == 1) {
847 assert(seg->b.x == status->xrow->x[0]);
848 point_t p = {status->xrow->x[0], y};
849 insert_point_into_segment(status, seg, p);
852 int start=0,end=status->xrow->num,dir=1;
853 if(seg->delta.x < 0) {
854 start = status->xrow->num-1;
857 for(t=start;t!=end;t+=dir) {
858 box_t box = box_new(status->xrow->x[t], y);
859 double d0 = LINE_EQ(box.left1, seg);
860 double d1 = LINE_EQ(box.left2, seg);
861 double d2 = LINE_EQ(box.right1, seg);
862 double d3 = LINE_EQ(box.right2, seg);
863 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
864 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
865 insert_point_into_segment(status, seg, box.right2);
871 /* we *need* to find a point to insert. the segment's own end point
872 is in that list, for Pete's sake. */
876 // now that this is done, too, we can also finally free this segment
877 segment_destroy(seg);
880 status->ending_segments = 0;
883 static void recalculate_windings(status_t*status, segrange_t*range)
886 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
888 segrange_adjust_endpoints(range, status->y);
890 segment_t*s = range->segmin;
891 segment_t*end = range->segmax;
895 s = actlist_leftmost(status->actlist);
897 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
898 s == range->segmin?"S":(
899 s == range->segmax?"E":""));
902 fprintf(stderr, "\n");
906 /* test sanity: check that we don't have changed segments
907 outside of the given range */
908 s = actlist_leftmost(status->actlist);
909 while(s && s!=range->segmin) {
913 s = actlist_rightmost(status->actlist);
914 while(s && s!=range->segmax) {
918 /* in check mode, go through the whole interval so we can test
919 that all polygons where the fillstyle changed also have seg->changed=1 */
920 s = actlist_leftmost(status->actlist);
931 segment_t* left = actlist_left(status->actlist, s);
932 windstate_t wind = left?left->wind:status->windrule->start(status->context);
933 s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
934 fillstyle_t*fs_old = s->fs_out;
935 s->fs_out = status->windrule->diff(&wind, &s->wind);
938 fprintf(stderr, "[%d] %s/%d/%s/%s %s\n", s->nr, s->dir==DIR_UP?"up":"down", s->wind.wind_nr, s->wind.is_filled?"fill":"nofill", s->fs_out?"draw":"omit",
939 fs_old!=s->fs_out?"CHANGED":"");
941 assert(!(!s->changed && fs_old!=s->fs_out));
952 /* we need to handle horizontal lines in order to add points to segments
953 we otherwise would miss during the windrule re-evaluation */
954 static void intersect_with_horizontal(status_t*status, segment_t*h)
956 segment_t* left = actlist_find(status->actlist, h->a, h->a);
957 segment_t* right = actlist_find(status->actlist, h->b, h->b);
959 /* not strictly necessary, also done by the event */
960 xrow_add(status->xrow, h->a.x);
968 left = actlist_right(status->actlist, left); //first seg to the right of h->a
969 right = right->right; //first seg to the right of h->b
974 int32_t x = XPOS_INT(s, status->y);
976 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
984 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
985 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
986 xrow_add(status->xrow, x);
992 static void event_apply(status_t*status, event_t*e)
995 case EVENT_HORIZONTAL: {
1000 intersect_with_horizontal(status, s);
1001 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1002 segment_destroy(s);e->s1=0;
1006 //delete segment from list
1007 segment_t*s = e->s1;
1012 dict_del(status->intersecting_segs, s);
1013 dict_del(status->segs_with_point, s);
1014 assert(!dict_contains(status->intersecting_segs, s));
1015 assert(!dict_contains(status->segs_with_point, s));
1017 segment_t*left = s->left;
1018 segment_t*right = s->right;
1019 actlist_delete(status->actlist, s);
1021 schedule_crossing(status, left, right);
1023 /* schedule segment for xrow handling */
1024 s->left = 0; s->right = status->ending_segments;
1025 status->ending_segments = s;
1026 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1030 //insert segment into list
1034 segment_t*s = e->s1;
1035 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1036 actlist_insert(status->actlist, s->a, s->b, s);
1037 segment_t*left = s->left;
1038 segment_t*right = s->right;
1040 schedule_crossing(status, left, s);
1042 schedule_crossing(status, s, right);
1043 schedule_endpoint(status, s);
1047 // exchange two segments
1051 if(e->s1->right == e->s2) {
1052 assert(e->s2->left == e->s1);
1053 exchange_two(status, e);
1055 assert(e->s2->left != e->s1);
1057 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1059 #ifndef DONT_REMEMBER_CROSSINGS
1060 /* ignore this crossing for now (there are some line segments in between).
1061 it'll get rescheduled as soon as the "obstacles" are gone */
1062 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1063 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1064 assert(del1 && del2);
1070 #ifndef DONT_REMEMBER_CROSSINGS
1071 assert(dict_contains(status->seen_crossings, &pair));
1072 dict_del(status->seen_crossings, &pair);
1081 static void check_status(status_t*status)
1083 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1084 if((s->pos.x != s->b.x ||
1085 s->pos.y != s->b.y) &&
1086 !dict_contains(status->segs_with_point, s)) {
1087 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1089 s->delta.x<0?"-":"+",
1097 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1100 |..| |...........| | |
1101 |..| |...........| | |
1102 |..+ + +..| +--+ +--+
1103 |...........| |..| | |
1104 |...........| |..| | |
1108 fprintf(stderr, "========================================================================\n");
1111 hqueue_init(&hqueue);
1112 gfxpoly_enqueue(poly, 0, &hqueue, 0);
1114 actlist_t* actlist = actlist_new();
1116 event_t*e = hqueue_get(&hqueue);
1122 fprintf(stderr, "HORIZONTALS ----------------------------------- %d\n", y);
1123 actlist_dump(actlist, y-1);
1126 actlist_verify(actlist, y-1);
1129 if(fill && x != e->p.x) {
1131 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
1135 gfxpolystroke_t*stroke = rfx_calloc(sizeof(gfxpolystroke_t));
1136 stroke->next = poly->strokes;
1137 poly->strokes = stroke;
1139 stroke->num_points = 2;
1140 stroke->points = malloc(sizeof(point_t)*2);
1141 stroke->dir = DIR_UP; // FIXME
1145 /* we draw from low x to high x so that left/right fillstyles add up
1146 (because the horizontal line's fill style controls the area *below* the line)
1150 stroke->points[0] = a;
1151 stroke->points[1] = b;
1153 /* the output should always be intersection free polygons, so check this horizontal
1154 line isn't hacking through any segments in the active list */
1155 segment_t* start = actlist_find(actlist, b, b);
1156 segment_t* s = actlist_find(actlist, a, a);
1158 assert(s->a.y == y || s->b.y == y);
1164 segment_t*s = e->s1;
1168 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1169 actlist_insert(actlist, s->a, s->b, s);
1170 event_t* e = event_new();
1171 e->type = EVENT_END;
1175 hqueue_put(&hqueue, e);
1176 left = actlist_left(actlist, s);
1180 left = actlist_left(actlist, s);
1181 actlist_delete(actlist, s);
1182 advance_stroke(0, &hqueue, s->stroke, s->polygon_nr, s->stroke_pos);
1189 fill ^= 1;//(before.is_filled != after.is_filled);
1191 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d\n",
1192 y, e->type==EVENT_START?"start":"end",
1198 if(e->type == EVENT_END)
1202 e = hqueue_get(&hqueue);
1203 } while(e && y == e->p.y);
1205 assert(!fill); // check that polygon is not bleeding
1208 actlist_destroy(actlist);
1209 hqueue_destroy(&hqueue);
1212 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1214 current_polygon = poly;
1217 memset(&status, 0, sizeof(status_t));
1218 queue_init(&status.queue);
1219 gfxpoly_enqueue(poly, &status.queue, 0, /*polygon nr*/0);
1221 status.windrule = windrule;
1222 status.context = context;
1223 status.actlist = actlist_new();
1226 status.seen_crossings = dict_new2(&point_type);
1227 int32_t lasty=-0x80000000;
1230 status.xrow = xrow_new();
1232 event_t*e = queue_get(&status.queue);
1236 assert(status.y>=lasty);
1238 status.intersecting_segs = dict_new2(&ptr_type);
1239 status.segs_with_point = dict_new2(&ptr_type);
1243 fprintf(stderr, "----------------------------------- %d\n", status.y);
1244 actlist_dump(status.actlist, status.y-1);
1247 actlist_verify(status.actlist, status.y-1);
1249 xrow_reset(status.xrow);
1251 xrow_add(status.xrow, e->p.x);
1252 event_apply(&status, e);
1254 e = queue_get(&status.queue);
1255 } while(e && status.y == e->p.y);
1257 xrow_sort(status.xrow);
1259 memset(&range, 0, sizeof(range));
1261 actlist_dump(status.actlist, status.y);
1263 add_points_to_positively_sloped_segments(&status, status.y, &range);
1264 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1265 add_points_to_ending_segments(&status, status.y);
1267 recalculate_windings(&status, &range);
1269 check_status(&status);
1270 dict_destroy(status.intersecting_segs);
1271 dict_destroy(status.segs_with_point);
1275 dict_destroy(status.seen_crossings);
1277 actlist_destroy(status.actlist);
1278 queue_destroy(&status.queue);
1279 xrow_destroy(status.xrow);
1281 gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t));
1282 p->gridsize = poly->gridsize;
1283 p->strokes = status.strokes;
1286 add_horizontals(p, &windrule_evenodd, context); // output is always even/odd