17 char point_equals(const void*o1, const void*o2)
19 const point_t*p1 = o1;
20 const point_t*p2 = o2;
21 return p1->x == p2->x && p1->y == p2->y;
23 unsigned int point_hash(const void*o)
28 void* point_dup(const void*o)
31 point_t*n = malloc(sizeof(point_t));
36 void point_free(void*o)
50 typedef struct _status {
59 dict_t*seen_crossings; //list of crossing we saw so far
60 dict_t*intersecting_segs; //list of segments intersecting in this scanline
61 dict_t*segs_with_point; //lists of segments that received a point in this scanline
65 int compare_events(const void*_a,const void*_b)
67 event_t* a = (event_t*)_a;
68 event_t* b = (event_t*)_b;
71 } else if(a->p.y > b->p.y) {
73 /* we should schedule start events after end/intersect.
74 The order of end/intersect doesn't actually matter, however,
75 so this might be doing too much */
76 } else if(a->type < b->type) {
78 } else if(a->type > b->type) {
80 } else if(a->p.x < b->p.x) {
82 } else if(a->p.x > b->p.x) {
88 gfxpoly_t* gfxpoly_new(double gridsize)
90 gfxpoly_t*p = (gfxpoly_t*)rfx_calloc(sizeof(gfxpoly_t));
91 p->gridsize = gridsize;
94 void gfxpoly_destroy(gfxpoly_t*poly)
96 edge_t* s = poly->edges;
98 edge_t*next = s->next;
104 char gfxpoly_check(gfxpoly_t*poly)
106 edge_t* s = poly->edges;
107 dict_t*d = dict_new2(&point_type);
109 if(!dict_contains(d, &s->a)) {
110 dict_put(d, &s->a, (void*)(ptroff_t)1);
112 int count = (ptroff_t)dict_lookup(d, &s->a);
115 dict_put(d, &s->a, (void*)(ptroff_t)count);
117 if(!dict_contains(d, &s->b)) {
118 dict_put(d, &s->b, (void*)(ptroff_t)1);
120 int count = (ptroff_t)dict_lookup(d, &s->b);
123 dict_put(d, &s->b, (void*)(ptroff_t)count);
127 DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
128 int count = (ptroff_t)c;
130 fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count);
137 void gfxpoly_dump(gfxpoly_t*poly)
139 edge_t* s = poly->edges;
140 double g = poly->gridsize;
142 fprintf(stderr, "(%f,%f) -> (%f,%f)\n", s->a.x*g, s->a.y*g, s->b.x*g, s->b.y*g);
147 inline static event_t event_new()
150 memset(&e, 0, sizeof(e));
154 void event_dump(event_t*e)
156 if(e->type == EVENT_HORIZONTAL) {
157 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);
158 } else if(e->type == EVENT_START) {
159 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
160 } else if(e->type == EVENT_END) {
161 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
162 } else if(e->type == EVENT_CROSS) {
163 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
169 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
170 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
172 void segment_init(segment_t*s, int x1, int y1, int x2, int y2, windstate_t windstate, int polygon_nr)
177 int x = x1;x1=x2;x2=x;
178 int y = y1;y1=y2;y2=y;
181 /* up/down for horizontal segments is handled by "rotating"
182 them 90° anticlockwise in screen coordinates (tilt your head to
187 int x = x1;x1=x2;x2=x;
188 int y = y1;y1=y2;y2=y;
195 s->k = (double)x1*y2-(double)x2*y1;
196 s->left = s->right = 0;
200 s->polygon_nr = polygon_nr;
203 static int segment_count=0;
204 s->nr = segment_count++;
207 assert(LINE_EQ(s->a, s) == 0);
208 assert(LINE_EQ(s->b, s) == 0);
210 /* check that all signs are in order:
218 p.x = min32(s->a.x, s->b.x);
219 assert(LINE_EQ(p, s) <= 0);
220 p.x = max32(s->a.x, s->b.x);
221 assert(LINE_EQ(p, s) >= 0);
223 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
226 segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2, windstate_t initial, int polygon_nr)
228 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
229 segment_init(s, x1, y1, x2, y2, initial, polygon_nr);
232 void segment_destroy(segment_t*s)
234 dict_clear(&s->scheduled_crossings);
238 void gfxpoly_enqueue(edge_t*list, heap_t*queue, windstate_t initial, int polygon_nr)
241 for(l=list;l;l=l->next) {
242 if(l->a.x == l->b.x &&
244 fprintf(stderr, "Warning: intersector input contains zero-length segments\n");
247 segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y, initial, polygon_nr);
249 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n",
250 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
251 s->dir==DIR_UP?"up":"down");
253 event_t e = event_new();
254 e.type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
262 void schedule_endpoint(status_t*status, segment_t*s)
264 // schedule end point of segment
265 assert(s->b.y > status->y);
271 heap_put(status->queue, &e);
274 void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
276 /* the code that's required (and the checks you can perform) before
277 it can be said with 100% certainty that we indeed have a valid crossing
278 amazes me every time. -mk */
281 /* we probably could precompute these */
282 int32_t minx1 = min32(s1->a.x,s1->b.x);
283 int32_t miny1 = min32(s1->a.y,s1->b.y);
284 int32_t maxx1 = max32(s1->a.x,s1->b.x);
285 int32_t maxy1 = max32(s1->a.y,s1->b.y);
286 int32_t minx2 = min32(s2->a.x,s2->b.x);
287 int32_t miny2 = min32(s2->a.y,s2->b.y);
288 int32_t maxx2 = max32(s2->a.x,s2->b.x);
289 int32_t maxy2 = max32(s2->a.y,s2->b.y);
291 /* both segments are active, so this can't happen */
292 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
294 /* TODO: optimize this. remove y, precompute the two x values */
295 if(maxx1 <= minx2 || maxx2 <= minx1 ||
296 maxy1 <= miny2 || maxy2 <= miny1) {
297 /* bounding boxes don't intersect */
301 if(dict_contains(&s1->scheduled_crossings, s2)) {
302 /* FIXME: this whole segment hashing thing is really slow */
303 //fprintf(stderr, "Encountered crossing between [%d] and [%d] twice\n", s1->nr, s2->nr);
305 // we already know about this one
309 double adx = s1->delta.x;
310 double ady = s1->delta.y;
311 double bdx = s2->delta.x;
312 double bdy = s2->delta.y;
313 double det = adx*bdy - ady*bdx;
316 // lines are exactly on top of each other (ignored)
318 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
322 /* lines are parallel */
326 double asign2 = LINE_EQ(s1->a, s2);
327 double bsign2 = LINE_EQ(s1->b, s2);
328 if(asign2<0 && bsign2<0) {
329 // segment1 is completely to the left of segment2
332 if(asign2>0 && bsign2>0) {
333 // segment2 is completely to the left of segment1
337 // segment1 touches segment2 in a single point (ignored)
339 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
344 // segment1 touches segment2 in a single point (ignored)
346 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
350 double asign1 = LINE_EQ(s2->a, s1);
351 double bsign1 = LINE_EQ(s2->b, s1);
352 if(asign1<0 && bsign1<0) {
353 // segment1 is completely to the left of segment2
356 if(asign1>0 && bsign1>0) {
357 // segment2 is completely to the left of segment1
361 // segment2 touches segment1 in a single point (ignored)
363 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
368 // segment2 touches segment1 in a single point (ignored)
370 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
375 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
376 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
379 p.x = (int32_t)ceil((-la*bdx +lb*adx) / det);
380 p.y = (int32_t)ceil((+lb*ady -la*bdy) / det);
382 assert(p.y >= status->y);
387 assert(!dict_contains(status->seen_crossings, &pair));
388 dict_put(status->seen_crossings, &pair, 0);
389 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
392 /* we insert into each other's intersection history because these segments might switch
393 places and we still want to look them up quickly after they did */
394 dict_put(&s1->scheduled_crossings, s2, 0);
395 dict_put(&s2->scheduled_crossings, s1, 0);
397 event_t e = event_new();
398 e.type = EVENT_CROSS;
402 heap_put(status->queue, &e);
406 void exchange_two(status_t*status, event_t*e)
408 //exchange two segments in list
409 segment_t*s1 = e->s1;
410 segment_t*s2 = e->s2;
412 if(!dict_contains(status->intersecting_segs, s1))
413 dict_put(status->intersecting_segs, s1, 0);
414 if(!dict_contains(status->intersecting_segs, s2))
415 dict_put(status->intersecting_segs, s2, 0);
417 segment_t*left = actlist_left(status->actlist, s2);
418 segment_t*right = actlist_right(status->actlist, s1);
421 actlist_swap(status->actlist, s1, s2);
422 assert(actlist_right(status->actlist, s2) == s1);
423 assert(actlist_left(status->actlist, s1) == s2);
424 left = actlist_left(status->actlist, s2);
425 right = actlist_right(status->actlist, s1);
427 schedule_crossing(status, left, s2);
429 schedule_crossing(status, s1, right);
432 typedef struct _box {
433 point_t left1, left2, right1, right2;
435 static inline box_t box_new(int x, int y)
438 box.right1.x = box.right2.x = x;
439 box.left1.x = box.left2.x = x-1;
440 box.left1.y = box.right1.y = y-1;
441 box.left2.y = box.right2.y = y;
446 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
448 assert(s->pos.x != p.x || s->pos.y != p.y);
451 if(!dict_contains(status->segs_with_point, s))
452 dict_put(status->segs_with_point, s, 0);
455 assert(s->fs_out_ok);
458 fprintf(stderr, "[%d] receives next point (%d,%d) (drawing)\n", s->nr, p.x, p.y);
460 // omit horizontal lines
461 if(s->pos.y != p.y) {
462 edge_t*e = malloc(sizeof(edge_t));
465 assert(e->a.y != e->b.y);
466 e->next = status->output;
471 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
477 /* possible optimizations:
478 1.) keep two different active lists around, one for negative and one for
480 2.) delay starting events until after this function (tricky, because we *do*
481 need the start coordinates)
492 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y)
495 for(t=0;t<status->xrow->num;t++) {
496 box_t box = box_new(status->xrow->x[t], y);
497 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
498 seg = actlist_right(status->actlist, seg);
501 // this segment just started, ignore it
502 } else if(seg->delta.x < 0) {
503 // ignore segment w/ negative slope
505 double d1 = LINE_EQ(box.right1, seg);
506 double d2 = LINE_EQ(box.right2, seg);
508 insert_point_into_segment(status, seg, box.right2);
513 seg = actlist_right(status->actlist, seg);
525 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y)
528 for(t=status->xrow->num-1;t>=0;t--) {
529 box_t box = box_new(status->xrow->x[t], y);
530 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
533 // this segment just started, ignore it
534 } else if(seg->delta.x >= 0) {
535 // ignore segment w/ positive slope
537 double d1 = LINE_EQ(box.left1, seg);
538 double d2 = LINE_EQ(box.left2, seg);
540 insert_point_into_segment(status, seg, box.right2);
545 seg = actlist_left(status->actlist, seg);
550 static void recalculate_windings(status_t*status)
552 /* TODO: we could use some clever second linked list structure so that we
553 only need to process points we know we marked */
555 segment_t*s = actlist_leftmost(status->actlist);
558 windstate_t wind = last?last->wind:status->windrule->start(status->num_polygons);
559 s->wind = status->windrule->add(wind, s->fs, s->dir, s->polygon_nr);
560 s->fs_out = status->windrule->diff(&wind, &s->wind);
563 fprintf(stderr, "[%d] %s/%d/%s/%s ", s->nr, s->dir==DIR_UP?"up":"down", s->wind.wind_nr, s->wind.is_filled?"fill":"nofill", s->fs_out?"draw":"omit");
566 s = actlist_right(status->actlist, s);
569 fprintf(stderr, "\n");
574 void intersect_with_horizontal(status_t*status, segment_t*h)
576 segment_t* left = actlist_find(status->actlist, h->a, h->a);
577 segment_t* right = actlist_find(status->actlist, h->b, h->b);
579 segment_t* s = right;
584 x1 + ((x2-x1)*(y-y1)) / dy =
585 (x1*(y2-y) + x2*(y-y1)) / dy
591 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
597 assert(p.x >= h->a.x);
598 assert(p.x <= h->b.x);
599 assert(s->delta.x > 0 && p.x >= s->a.x || s->delta.x <= 0 && p.x <= s->a.x);
600 assert(s->delta.x > 0 && p.x <= s->b.x || s->delta.x <= 0 && p.x >= s->b.x);
601 xrow_add(status->xrow, p.x);
603 s = actlist_left(status->actlist, s);
605 xrow_add(status->xrow, h->a.x);
608 void event_apply(status_t*status, event_t*e)
611 case EVENT_HORIZONTAL: {
615 intersect_with_horizontal(status, e->s1);
619 //delete segment from list
623 dict_del(status->intersecting_segs, s);
624 dict_del(status->segs_with_point, s);
625 assert(!dict_contains(status->intersecting_segs, s));
626 assert(!dict_contains(status->segs_with_point, s));
628 insert_point_into_segment(status, s, s->b);
629 segment_t*left = actlist_left(status->actlist, s);
630 segment_t*right = actlist_right(status->actlist, s);
631 actlist_delete(status->actlist, s);
633 schedule_crossing(status, left, right);
634 segment_destroy(s);e->s1=0;
638 //insert segment into list
643 actlist_insert(status->actlist, e->p, s);
644 segment_t*left = actlist_left(status->actlist, s);
645 segment_t*right = actlist_right(status->actlist, s);
647 schedule_crossing(status, left, s);
649 schedule_crossing(status, s, right);
650 schedule_endpoint(status, e->s1);
654 // exchange two segments
658 if(actlist_right(status->actlist, e->s1) == e->s2 &&
659 actlist_left(status->actlist, e->s2) == e->s1) {
660 exchange_two(status, e);
662 /* ignore this crossing for now (there are some line segments in between).
663 it'll get rescheduled as soon as the "obstacles" are gone */
664 char del1 = dict_del(&e->s1->scheduled_crossings, e->s2);
665 char del2 = dict_del(&e->s2->scheduled_crossings, e->s1);
666 assert(del1 && del2);
671 assert(dict_contains(status->seen_crossings, &pair));
672 dict_del(status->seen_crossings, &pair);
680 void check_status(status_t*status)
682 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
683 if((s->pos.x != s->b.x ||
684 s->pos.y != s->b.y) &&
685 !dict_contains(status->segs_with_point, s)) {
686 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
688 s->delta.x<0?"-":"+",
696 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule)
698 heap_t* queue = heap_new(sizeof(event_t), compare_events);
700 gfxpoly_enqueue(poly->edges, queue, windrule->start(1), /*polygon nr*/0);
703 memset(&status, 0, sizeof(status_t));
704 status.num_polygons = 1;
705 status.queue = queue;
706 status.windrule = windrule;
707 status.actlist = actlist_new();
709 status.seen_crossings = dict_new2(&point_type);
712 status.xrow = xrow_new();
714 event_t*e = heap_chopmax(queue);
718 status.intersecting_segs = dict_new2(&ptr_type);
719 status.segs_with_point = dict_new2(&ptr_type);
720 fprintf(stderr, "----------------------------------- %d\n", status.y);
721 actlist_verify_and_dump(status.actlist, status.y-1);
723 xrow_reset(status.xrow);
725 if(e->type != EVENT_HORIZONTAL) {
726 xrow_add(status.xrow, e->p.x);
728 event_apply(&status, e);
730 e = heap_chopmax(queue);
731 } while(e && status.y == e->p.y);
733 xrow_sort(status.xrow);
734 add_points_to_positively_sloped_segments(&status, status.y);
735 add_points_to_negatively_sloped_segments(&status, status.y);
736 recalculate_windings(&status);
738 check_status(&status);
739 dict_destroy(status.intersecting_segs);
740 dict_destroy(status.segs_with_point);
744 dict_destroy(status.seen_crossings);
746 actlist_destroy(status.actlist);
748 xrow_destroy(status.xrow);
750 gfxpoly_t*p = gfxpoly_new(poly->gridsize);
751 p->edges = status.output;