14 static gfxcompactpoly_t*current_polygon = 0;
15 void gfxpoly_fail(char*expr, char*file, int line, const char*function)
17 if(!current_polygon) {
18 fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
22 void*md5 = init_md5();
25 for(s=0;s<current_polygon->num_strokes;s++) {
26 gfxpolystroke_t*stroke = ¤t_polygon->strokes[s];
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 gfxcompactpoly_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)
71 static type_t point_type = {
78 typedef struct _status {
84 windcontext_t*context;
85 segment_t*ending_segments;
88 dict_t*seen_crossings; //list of crossing we saw so far
89 dict_t*intersecting_segs; //list of segments intersecting in this scanline
90 dict_t*segs_with_point; //lists of segments that received a point in this scanline
94 typedef struct _event {
101 /* compare_events_simple differs from compare_events in that it schedules
102 events from left to right regardless of type. It's only used in horizontal
103 processing, in order to get an x-wise sorting of the current scanline */
104 static int compare_events_simple(const void*_a,const void*_b)
106 event_t* a = (event_t*)_a;
107 event_t* b = (event_t*)_b;
108 int d = b->p.y - a->p.y;
115 static int compare_events(const void*_a,const void*_b)
117 event_t* a = (event_t*)_a;
118 event_t* b = (event_t*)_b;
119 int d = b->p.y - a->p.y;
121 /* we need to schedule end after intersect (so that a segment about
122 to end has a chance to tear up a few other segs first) and start
123 events after end (in order not to confuse the intersection check, which
124 assumes there's an actual y overlap between active segments, and
125 because ending segments in the active list make it difficult to insert
126 starting segments at the right position)).
127 Horizontal lines come last, because the only purpose
128 they have is to create snapping coordinates for the segments (still)
129 existing in this scanline.
131 d = b->type - a->type;
135 /* I don't see any reason why we would need to order by x- at least as long
136 as we do horizontal lines in a seperate pass */
137 //d = b->p.x - a->p.x;
141 gfxpoly_t* gfxpoly_new(double gridsize)
143 gfxpoly_t*p = (gfxpoly_t*)rfx_calloc(sizeof(gfxpoly_t));
144 p->gridsize = gridsize;
147 void gfxpoly_destroy(gfxpoly_t*poly)
149 edge_t* s = poly->edges;
151 edge_t*next = s->next;
157 int gfxpoly_size(gfxpoly_t*poly)
159 edge_t*e = poly->edges;
167 int gfxcompactpoly_size(gfxcompactpoly_t*poly)
171 for(t=0;t<poly->num_strokes;t++) {
172 gfxpolystroke_t*stroke = &poly->strokes[t];
173 edges += stroke->num_points-1;
178 char gfxpoly_check(gfxpoly_t*poly)
180 edge_t* s = poly->edges;
181 dict_t*d = dict_new2(&point_type);
183 if(!dict_contains(d, &s->a)) {
184 dict_put(d, &s->a, (void*)(ptroff_t)1);
186 int count = (ptroff_t)dict_lookup(d, &s->a);
189 dict_put(d, &s->a, (void*)(ptroff_t)count);
191 if(!dict_contains(d, &s->b)) {
192 dict_put(d, &s->b, (void*)(ptroff_t)1);
194 int count = (ptroff_t)dict_lookup(d, &s->b);
197 dict_put(d, &s->b, (void*)(ptroff_t)count);
201 DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
202 int count = (ptroff_t)c;
204 fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count);
213 char gfxcompactpoly_check(gfxcompactpoly_t*poly)
215 dict_t*d = dict_new2(&point_type);
217 for(t=0;t<poly->num_strokes;t++) {
218 gfxpolystroke_t*stroke = &poly->strokes[t];
219 for(s=0;s<stroke->num_points;s++) {
220 point_t p = stroke->points[s];
221 int num = (s>=1 && s<stroke->num_points-1)?2:1; // mid points are two points (start+end)
222 if(!dict_contains(d, &p)) {
223 dict_put(d, &p, (void*)(ptroff_t)num);
225 int count = (ptroff_t)dict_lookup(d, &p);
228 dict_put(d, &p, (void*)(ptroff_t)count);
232 DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
233 int count = (ptroff_t)c;
235 fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count);
244 void gfxpoly_dump(gfxpoly_t*poly)
246 edge_t* s = poly->edges;
247 double g = poly->gridsize;
248 fprintf(stderr, "polyon %08x (gridsize: %f)\n", poly, poly->gridsize);
250 fprintf(stderr, "(%f,%f) -> (%f,%f)\n", s->a.x*g, s->a.y*g, s->b.x*g, s->b.y*g);
255 void gfxcompactpoly_dump(gfxcompactpoly_t*poly)
258 double g = poly->gridsize;
259 fprintf(stderr, "polyon %08x (gridsize: %f)\n", poly, poly->gridsize);
260 for(t=0;t<poly->num_strokes;t++) {
261 gfxpolystroke_t*stroke = &poly->strokes[t];
262 for(s=0;s<stroke->num_points-1;s++) {
263 point_t a = stroke->points[s];
264 point_t b = stroke->points[s+1];
265 fprintf(stderr, "%s(%f,%f) -> (%f,%f)%s\n", s?" ":"[", a.x*g, a.y*g, b.x*g, b.y*g,
266 s==stroke->num_points-2?"]":"");
271 void gfxcompactpoly_save(gfxcompactpoly_t*poly, const char*filename)
273 FILE*fi = fopen(filename, "wb");
274 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
275 fprintf(fi, "%% begin\n");
277 for(t=0;t<poly->num_strokes;t++) {
278 gfxpolystroke_t*stroke = &poly->strokes[t];
279 for(s=0;s<stroke->num_points-1;s++) {
280 point_t a = stroke->points[s];
281 point_t b = stroke->points[s+1];
282 fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
283 fprintf(fi, "%d %d moveto\n", a.x, a.y);
284 fprintf(fi, "%d %d lineto\n", b.x, b.y);
285 fprintf(fi, "stroke\n");
288 fprintf(fi, "showpage\n");
292 inline static event_t event_new()
295 memset(&e, 0, sizeof(e));
299 static void event_dump(event_t*e)
301 if(e->type == EVENT_HORIZONTAL) {
302 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);
303 } else if(e->type == EVENT_START) {
304 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
305 } else if(e->type == EVENT_END) {
306 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
307 } else if(e->type == EVENT_CROSS) {
308 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
314 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
315 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
317 static void segment_dump(segment_t*s)
319 fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
320 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k,
321 (double)s->delta.x / s->delta.y);
324 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)
330 /* up/down for horizontal segments is handled by "rotating"
331 them 90° anticlockwise in screen coordinates (tilt your head to
333 TODO: is this still needed?
338 int32_t x = x1;x1=x2;x2=x;
339 int32_t y = y1;y1=y2;y2=y;
346 s->k = (double)x1*y2-(double)x2*y1;
347 s->left = s->right = 0;
350 s->minx = min32(x1,x2);
351 s->maxx = max32(x1,x2);
354 s->polygon_nr = polygon_nr;
355 static int segment_count=0;
356 s->nr = segment_count++;
359 assert(LINE_EQ(s->a, s) == 0);
360 assert(LINE_EQ(s->b, s) == 0);
362 /* check that all signs are in order:
370 p.x = min32(s->a.x, s->b.x);
371 assert(LINE_EQ(p, s) <= 0);
372 p.x = max32(s->a.x, s->b.x);
373 assert(LINE_EQ(p, s) >= 0);
376 /* TODO: make this int_type */
377 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
380 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
382 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
383 segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
387 static void segment_clear(segment_t*s)
389 dict_clear(&s->scheduled_crossings);
391 static void segment_destroy(segment_t*s)
397 static void advance_stroke(heap_t*queue, gfxpolystroke_t*stroke, int polygon_nr, int pos)
399 while(pos < stroke->num_points-1) {
400 assert(stroke->points[pos].y <= stroke->points[pos+1].y);
401 segment_t*s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
403 s->stroke_pos = ++pos;
407 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (%d more to come)\n",
408 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
409 s->dir==DIR_UP?"up":"down", stroke->num_points - 1 - pos);
411 event_t e = event_new();
412 e.type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
417 if(e.type != EVENT_HORIZONTAL) {
423 static void gfxpoly_enqueue(gfxcompactpoly_t*p, heap_t*queue, int polygon_nr)
426 for(t=0;t<p->num_strokes;t++) {
427 gfxpolystroke_t*stroke = &p->strokes[t];
428 assert(stroke->num_points > 1);
432 for(s=0;s<stroke->num_points-1;s++) {
433 assert(stroke->points[s].y <= stroke->points[s+1].y);
436 advance_stroke(queue, stroke, polygon_nr, 0);
440 static void schedule_endpoint(status_t*status, segment_t*s)
442 // schedule end point of segment
443 assert(s->b.y > status->y);
449 heap_put(status->queue, &e);
452 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
454 /* the code that's required (and the checks you can perform) before
455 it can be said with 100% certainty that we indeed have a valid crossing
456 amazes me every time. -mk */
459 assert(s1->right == s2);
460 assert(s2->left == s1);
461 int32_t miny1 = min32(s1->a.y,s1->b.y);
462 int32_t maxy1 = max32(s1->a.y,s1->b.y);
463 int32_t miny2 = min32(s2->a.y,s2->b.y);
464 int32_t maxy2 = max32(s2->a.y,s2->b.y);
465 int32_t minx1 = min32(s1->a.x,s1->b.x);
466 int32_t minx2 = min32(s2->a.x,s2->b.x);
467 int32_t maxx1 = max32(s1->a.x,s1->b.x);
468 int32_t maxx2 = max32(s2->a.x,s2->b.x);
469 /* check that precomputation is sane */
470 assert(minx1 == s1->minx && minx2 == s2->minx);
471 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
472 /* both segments are active, so this can't happen */
473 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
474 /* we know that right now, s2 is to the right of s1, so there's
475 no way the complete bounding box of s1 is to the right of s1 */
476 assert(!(s1->minx > s2->maxx));
477 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
480 if(s1->maxx <= s2->minx) {
482 fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
484 /* bounding boxes don't intersect */
488 if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
489 /* FIXME: this whole segment hashing thing is really slow */
491 fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
492 // DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
493 // fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
496 return; // we already know about this one
499 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
502 // lines are exactly on top of each other (ignored)
504 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
509 fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
511 /* lines are parallel */
515 double asign2 = LINE_EQ(s1->a, s2);
516 double bsign2 = LINE_EQ(s1->b, s2);
517 if(asign2<0 && bsign2<0) {
518 // segment1 is completely to the left of segment2
520 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);
524 if(asign2>0 && bsign2>0) {
525 // TODO: can this ever happen?
527 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);
529 // segment2 is completely to the left of segment1
533 // segment1 touches segment2 in a single point (ignored)
535 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
540 // segment1 touches segment2 in a single point (ignored)
542 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
546 double asign1 = LINE_EQ(s2->a, s1);
547 double bsign1 = LINE_EQ(s2->b, s1);
548 if(asign1<0 && bsign1<0) {
549 // segment1 is completely to the left of segment2
551 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);
555 if(asign1>0 && bsign1>0) {
556 // segment2 is completely to the left of segment1
558 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);
563 // segment2 touches segment1 in a single point (ignored)
565 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
570 // segment2 touches segment1 in a single point (ignored)
572 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
577 /* TODO: should we precompute these? */
578 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
579 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
582 p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
583 p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
585 assert(p.y >= status->y);
587 assert(p.x >= s1->minx && p.x <= s1->maxx);
588 assert(p.x >= s2->minx && p.x <= s2->maxx);
593 assert(!dict_contains(status->seen_crossings, &pair));
594 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 /* we insert into each other's intersection history because these segments might switch
601 places and we still want to look them up quickly after they did */
602 dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
603 dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
605 event_t e = event_new();
606 e.type = EVENT_CROSS;
610 heap_put(status->queue, &e);
614 static void exchange_two(status_t*status, event_t*e)
616 //exchange two segments in list
617 segment_t*s1 = e->s1;
618 segment_t*s2 = e->s2;
620 if(!dict_contains(status->intersecting_segs, s1))
621 dict_put(status->intersecting_segs, s1, 0);
622 if(!dict_contains(status->intersecting_segs, s2))
623 dict_put(status->intersecting_segs, s2, 0);
625 assert(s2->left == s1);
626 assert(s1->right == s2);
627 actlist_swap(status->actlist, s1, s2);
628 assert(s2->right == s1);
629 assert(s1->left == s2);
630 segment_t*left = s2->left;
631 segment_t*right = s1->right;
633 schedule_crossing(status, left, s2);
635 schedule_crossing(status, s1, right);
638 typedef struct _box {
639 point_t left1, left2, right1, right2;
641 static inline box_t box_new(int32_t x, int32_t y)
644 box.right1.x = box.right2.x = x;
645 box.left1.x = box.left2.x = x-1;
646 box.left1.y = box.right1.y = y-1;
647 box.left2.y = box.right2.y = y;
652 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
654 assert(s->pos.x != p.x || s->pos.y != p.y);
657 if(!dict_contains(status->segs_with_point, s))
658 dict_put(status->segs_with_point, s, 0);
659 assert(s->fs_out_ok);
664 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
665 s->pos.x, s->pos.y, p.x, p.y);
667 // omit horizontal lines
668 if(s->pos.y != p.y) {
672 status->writer.moveto(&status->writer, a.x, a.y);
673 status->writer.lineto(&status->writer, b.x, b.y);
677 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
683 typedef struct _segrange {
690 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
692 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
693 segment_t*min = range->segmin;
694 segment_t*max = range->segmax;
696 /* we need this because if two segments intersect exactly on
697 the scanline, segrange_test_segment_{min,max} can't tell which
698 one is smaller/larger */
699 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
702 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
708 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
711 /* we need to calculate the xpos anew (and can't use start coordinate or
712 intersection coordinate), because we need the xpos exactly at the end of
715 double x = XPOS(seg, y);
716 if(!range->segmin || x<range->xmin) {
721 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
724 double x = XPOS(seg, y);
725 if(!range->segmax || x>range->xmax) {
740 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
742 segment_t*first=0, *last = 0;
744 for(t=0;t<status->xrow->num;t++) {
745 box_t box = box_new(status->xrow->x[t], y);
746 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
748 seg = actlist_right(status->actlist, seg);
751 // this segment started in this scanline, ignore it
752 seg->changed = 1;last = seg;if(!first) {first=seg;}
753 } else if(seg->delta.x <= 0) {
754 // ignore segment w/ negative slope
756 last = seg;if(!first) {first=seg;}
757 double d1 = LINE_EQ(box.right1, seg);
758 double d2 = LINE_EQ(box.right2, seg);
761 insert_point_into_segment(status, seg, box.right2);
763 /* we unfortunately can't break here- the active list is sorted according
764 to the *bottom* of the scanline. hence pretty much everything that's still
765 coming might reach into our box */
772 segrange_test_segment_min(range, first, y);
773 segrange_test_segment_max(range, last, y);
783 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
785 segment_t*first=0, *last = 0;
787 for(t=status->xrow->num-1;t>=0;t--) {
788 box_t box = box_new(status->xrow->x[t], y);
789 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
793 // this segment started in this scanline, ignore it
794 seg->changed = 1;last = seg;if(!first) {first=seg;}
795 } else if(seg->delta.x > 0) {
796 // ignore segment w/ positive slope
798 last = seg;if(!first) {first=seg;}
799 double d1 = LINE_EQ(box.left1, seg);
800 double d2 = LINE_EQ(box.left2, seg);
803 insert_point_into_segment(status, seg, box.right2);
811 segrange_test_segment_min(range, last, y);
812 segrange_test_segment_max(range, first, y);
815 /* segments ending in the current scanline need xrow treatment like everything else.
816 (consider an intersection taking place just above a nearly horizontal segment
817 ending on the current scanline- the intersection would snap down *below* the
818 ending segment if we don't add the intersection point to the latter right away)
819 we need to treat ending segments seperately, however. we have to delete them from
820 the active list right away to make room for intersect operations (which might
821 still be in the current scanline- consider two 45° polygons and a vertical polygon
822 intersecting on an integer coordinate). but once they're no longer in the active list,
823 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
824 them to the active list just for point snapping would be overkill.
825 (One other option to consider, however, would be to create a new active list only
828 static void add_points_to_ending_segments(status_t*status, int32_t y)
830 segment_t*seg = status->ending_segments;
832 segment_t*next = seg->right;seg->right=0;
834 assert(seg->b.y == status->y);
836 if(status->xrow->num == 1) {
838 assert(seg->b.x == status->xrow->x[0]);
839 point_t p = {status->xrow->x[0], y};
840 insert_point_into_segment(status, seg, p);
843 int start=0,end=status->xrow->num,dir=1;
844 if(seg->delta.x < 0) {
845 start = status->xrow->num-1;
848 for(t=start;t!=end;t+=dir) {
849 box_t box = box_new(status->xrow->x[t], y);
850 double d0 = LINE_EQ(box.left1, seg);
851 double d1 = LINE_EQ(box.left2, seg);
852 double d2 = LINE_EQ(box.right1, seg);
853 double d3 = LINE_EQ(box.right2, seg);
854 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
855 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
856 insert_point_into_segment(status, seg, box.right2);
862 /* we *need* to find a point to insert. the segment's own end point
863 is in that list, for Pete's sake. */
867 // now that this is done, too, we can also finally free this segment
868 segment_destroy(seg);
871 status->ending_segments = 0;
874 static void recalculate_windings(status_t*status, segrange_t*range)
877 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
879 segrange_adjust_endpoints(range, status->y);
881 segment_t*s = range->segmin;
882 segment_t*end = range->segmax;
886 s = actlist_leftmost(status->actlist);
888 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
889 s == range->segmin?"S":(
890 s == range->segmax?"E":""));
893 fprintf(stderr, "\n");
897 /* test sanity: check that we don't have changed segments
898 outside of the given range */
899 s = actlist_leftmost(status->actlist);
900 while(s && s!=range->segmin) {
904 s = actlist_rightmost(status->actlist);
905 while(s && s!=range->segmax) {
909 /* in check mode, go through the whole interval so we can test
910 that all polygons where the fillstyle changed also have seg->changed=1 */
911 s = actlist_leftmost(status->actlist);
922 segment_t* left = actlist_left(status->actlist, s);
923 windstate_t wind = left?left->wind:status->windrule->start(status->context);
924 s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
925 fillstyle_t*fs_old = s->fs_out;
926 s->fs_out = status->windrule->diff(&wind, &s->wind);
929 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",
930 fs_old!=s->fs_out?"CHANGED":"");
932 assert(!(!s->changed && fs_old!=s->fs_out));
943 /* we need to handle horizontal lines in order to add points to segments
944 we otherwise would miss during the windrule re-evaluation */
945 static void intersect_with_horizontal(status_t*status, segment_t*h)
947 segment_t* left = actlist_find(status->actlist, h->a, h->a);
948 segment_t* right = actlist_find(status->actlist, h->b, h->b);
950 /* not strictly necessary, also done by the event */
951 xrow_add(status->xrow, h->a.x);
959 left = actlist_right(status->actlist, left); //first seg to the right of h->a
960 right = right->right; //first seg to the right of h->b
965 int32_t x = XPOS_INT(s, status->y);
967 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
975 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
976 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
977 xrow_add(status->xrow, x);
983 static void event_apply(status_t*status, event_t*e)
986 case EVENT_HORIZONTAL: {
991 intersect_with_horizontal(status, s);
992 advance_stroke(status->queue, s->stroke, s->polygon_nr, s->stroke_pos);
993 segment_destroy(s);e->s1=0;
997 //delete segment from list
1003 dict_del(status->intersecting_segs, s);
1004 dict_del(status->segs_with_point, s);
1005 assert(!dict_contains(status->intersecting_segs, s));
1006 assert(!dict_contains(status->segs_with_point, s));
1008 segment_t*left = s->left;
1009 segment_t*right = s->right;
1010 actlist_delete(status->actlist, s);
1012 schedule_crossing(status, left, right);
1014 /* schedule segment for xrow handling */
1015 s->left = 0; s->right = status->ending_segments;
1016 status->ending_segments = s;
1017 advance_stroke(status->queue, s->stroke, s->polygon_nr, s->stroke_pos);
1021 //insert segment into list
1025 segment_t*s = e->s1;
1026 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1027 actlist_insert(status->actlist, s->a, s->b, s);
1028 segment_t*left = s->left;
1029 segment_t*right = s->right;
1031 schedule_crossing(status, left, s);
1033 schedule_crossing(status, s, right);
1034 schedule_endpoint(status, s);
1038 // exchange two segments
1042 if(e->s1->right == e->s2) {
1043 assert(e->s2->left == e->s1);
1044 exchange_two(status, e);
1046 assert(e->s2->left != e->s1);
1048 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1050 /* ignore this crossing for now (there are some line segments in between).
1051 it'll get rescheduled as soon as the "obstacles" are gone */
1052 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1053 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1054 assert(del1 && del2);
1059 assert(dict_contains(status->seen_crossings, &pair));
1060 dict_del(status->seen_crossings, &pair);
1068 static void check_status(status_t*status)
1070 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1071 if((s->pos.x != s->b.x ||
1072 s->pos.y != s->b.y) &&
1073 !dict_contains(status->segs_with_point, s)) {
1074 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1076 s->delta.x<0?"-":"+",
1084 static void add_horizontals(gfxcompactpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1087 |..| |...........| | |
1088 |..| |...........| | |
1089 |..+ + +..| +--+ +--+
1090 |...........| |..| | |
1091 |...........| |..| | |
1095 fprintf(stderr, "========================================================================\n");
1097 heap_t* queue = heap_new(sizeof(event_t), compare_events_simple);
1098 gfxpoly_enqueue(poly, queue, 0);
1100 actlist_t* actlist = actlist_new();
1102 event_t*e = heap_chopmax(queue);
1103 int newstrokes_size = 4;
1104 int num_newstrokes = 0;
1105 gfxpolystroke_t*newstrokes = malloc(sizeof(gfxpolystroke_t)*newstrokes_size);
1111 fprintf(stderr, "----------------------------------- %d\n", y);
1112 actlist_dump(actlist, y-1);
1115 actlist_verify(actlist, y-1);
1118 if(fill && x != e->p.x) {
1120 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
1124 if(num_newstrokes == newstrokes_size) {
1125 newstrokes_size = (newstrokes_size)<<1;
1126 newstrokes = rfx_realloc(newstrokes, sizeof(gfxpolystroke_t)*newstrokes_size);
1128 gfxpolystroke_t*stroke = &newstrokes[num_newstrokes++];
1129 stroke->num_points = 2;
1130 stroke->points = malloc(sizeof(point_t)*2);
1131 stroke->dir = DIR_UP; // FIXME
1135 /* we draw from low x to high x so that left/right fillstyles add up
1136 (because the horizontal line's fill style controls the area *below* the line)
1140 stroke->points[0] = a;
1141 stroke->points[1] = b;
1143 /* the output should always be intersection free polygons, so check this horizontal
1144 line isn't hacking through any segments in the active list */
1145 segment_t* start = actlist_find(actlist, b, b);
1146 segment_t* s = actlist_find(actlist, a, a);
1148 assert(s->a.y == y || s->b.y == y);
1154 segment_t*s = e->s1;
1158 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1159 actlist_insert(actlist, s->a, s->b, s);
1165 heap_put(queue, &e);
1166 left = actlist_left(actlist, s);
1170 left = actlist_left(actlist, s);
1171 actlist_delete(actlist, s);
1172 advance_stroke(queue, s->stroke, s->polygon_nr, s->stroke_pos);
1179 fill ^= 1;//(before.is_filled != after.is_filled);
1181 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d\n",
1182 y, e->type==EVENT_START?"start":"end",
1188 if(e->type == EVENT_END)
1192 e = heap_chopmax(queue);
1193 } while(e && y == e->p.y);
1195 assert(!fill); // check that polygon is not bleeding
1198 poly->strokes = rfx_realloc(poly->strokes, sizeof(gfxpolystroke_t)*(num_newstrokes+poly->num_strokes));
1199 memcpy(&poly->strokes[poly->num_strokes], newstrokes, sizeof(gfxpolystroke_t)*num_newstrokes);
1200 poly->num_strokes += num_newstrokes;
1203 actlist_destroy(actlist);
1204 heap_destroy(queue);
1207 gfxpoly_t* gfxpoly_process(gfxcompactpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1209 current_polygon = poly;
1210 heap_t* queue = heap_new(sizeof(event_t), compare_events);
1212 gfxpoly_enqueue(poly, queue, /*polygon nr*/0);
1215 memset(&status, 0, sizeof(status_t));
1216 status.queue = queue;
1217 status.windrule = windrule;
1218 status.context = context;
1219 status.actlist = actlist_new();
1220 gfxcompactpolywriter_init(&status.writer);
1221 status.writer.setgridsize(&status.writer, poly->gridsize);
1224 status.seen_crossings = dict_new2(&point_type);
1225 int lasty=heap_peek(queue)?((event_t*)heap_peek(queue))->p.y-1:0;
1228 status.xrow = xrow_new();
1230 event_t*e = heap_chopmax(queue);
1233 assert(status.y>=lasty);
1235 status.intersecting_segs = dict_new2(&ptr_type);
1236 status.segs_with_point = dict_new2(&ptr_type);
1240 fprintf(stderr, "----------------------------------- %d\n", status.y);
1241 actlist_dump(status.actlist, status.y-1);
1244 actlist_verify(status.actlist, status.y-1);
1246 xrow_reset(status.xrow);
1248 xrow_add(status.xrow, e->p.x);
1249 event_apply(&status, e);
1251 e = heap_chopmax(queue);
1252 } while(e && status.y == e->p.y);
1254 xrow_sort(status.xrow);
1256 memset(&range, 0, sizeof(range));
1258 actlist_dump(status.actlist, status.y);
1260 add_points_to_positively_sloped_segments(&status, status.y, &range);
1261 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1262 add_points_to_ending_segments(&status, status.y);
1264 recalculate_windings(&status, &range);
1266 check_status(&status);
1267 dict_destroy(status.intersecting_segs);
1268 dict_destroy(status.segs_with_point);
1272 dict_destroy(status.seen_crossings);
1274 actlist_destroy(status.actlist);
1275 heap_destroy(queue);
1276 xrow_destroy(status.xrow);
1278 gfxcompactpoly_t*p = (gfxcompactpoly_t*)status.writer.finish(&status.writer);
1279 add_horizontals(p, &windrule_evenodd, context); // output is always even/odd
1280 gfxpoly_t*pp = gfxpoly_from_gfxcompactpoly(p);
1281 gfxcompactpoly_destroy(p);