12 char point_equals(const void*o1, const void*o2)
14 const point_t*p1 = o1;
15 const point_t*p2 = o2;
16 return p1->x == p2->x && p1->y == p2->y;
18 unsigned int point_hash(const void*o)
23 void* point_dup(const void*o)
26 point_t*n = malloc(sizeof(point_t));
31 void point_free(void*o)
45 typedef struct _status {
50 dict_t*seen_crossings; //list of crossing we saw so far
51 dict_t*intersecting_segs; //list of segments intersecting in this scanline
52 dict_t*segs_with_point; //lists of segments that received a point in this scanline
56 int compare_events(const void*_a,const void*_b)
58 event_t* a = (event_t*)_a;
59 event_t* b = (event_t*)_b;
62 } else if(a->p.y > b->p.y) {
64 } else if(a->type < b->type) {
66 } else if(a->type > b->type) {
68 } else if(a->p.x < b->p.x) {
70 } else if(a->p.x > b->p.x) {
76 gfxpoly_t* gfxpoly_new()
80 void gfxpoly_destroy(gfxpoly_t*poly)
84 segment_t*right = s->right;
92 void gfxpoly_dump(gfxpoly_t*poly)
94 segment_t* s = (segment_t*)poly;
96 printf("[%d] (%d,%d) -> (%d,%d) %s\n",
97 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
98 s->dir==DIR_UP?"up":"down");
105 inline static event_t event_new()
108 memset(&e, 0, sizeof(e));
112 void event_dump(event_t*e)
114 if(e->type == EVENT_START) {
115 printf("event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
116 } else if(e->type == EVENT_END) {
117 printf("event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
118 } else if(e->type == EVENT_CROSS) {
119 printf("event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
123 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
124 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
126 void segment_init(segment_t*s, int x1, int y1, int x2, int y2)
132 int x = x1;x1=x2;x2=x;
133 int y = y1;y1=y2;y2=y;
140 s->k = (double)x1*y2-(double)x2*y1;
141 s->left = s->right = 0;
147 static int segment_count=0; //for debugging
148 s->nr = segment_count++;
151 assert(LINE_EQ(s->a, s) == 0);
152 assert(LINE_EQ(s->b, s) == 0);
154 /* check that all signs are in order:
162 p.x = min32(s->a.x, s->b.x);
163 assert(LINE_EQ(p, s) <= 0);
164 p.x = max32(s->a.x, s->b.x);
165 assert(LINE_EQ(p, s) >= 0);
167 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
170 segment_t*segment_new(int x1, int y1, int x2, int y2)
172 segment_t*s = malloc(sizeof(segment_t));
173 segment_init(s, x1, y1, x2, y2);
177 void segment_insert_before(segment_t**list, segment_t*add)
181 add->left = add->right = add;
183 add->left = (*list)->left;
184 add->right = (*list);
185 add->right->left = add;
186 add->left->right = add;
190 void segments_enqueue(segment_t*list, heap_t*queue)
194 segment_t*right = l->right;
195 l->left = l->right = 0;
196 event_t e = event_new();
197 e.type = EVENT_START;
198 e.p = l->a;e.s1 = l;e.s2 = 0;
201 e.p = l->b;e.s1 = l;e.s2 = 0;
208 void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2, int miny)
210 /* the code that's required (and the checks you can perform) before
211 it can be said with 100% certainty that we indeed have a valid crossing
212 amazes me every time. -mk */
215 if(dict_contains(&s1->scheduled_crossings, s2)) {
216 // we already know about this one
220 /* we probably could precompute these */
221 int32_t minx1 = min32(s1->a.x,s1->b.x);
222 int32_t miny1 = min32(s1->a.y,s1->b.y);
223 int32_t maxx1 = max32(s1->a.x,s1->b.x);
224 int32_t maxy1 = max32(s1->a.y,s1->b.y);
225 int32_t minx2 = min32(s2->a.x,s2->b.x);
226 int32_t miny2 = min32(s2->a.y,s2->b.y);
227 int32_t maxx2 = max32(s2->a.x,s2->b.x);
228 int32_t maxy2 = max32(s2->a.y,s2->b.y);
230 if(maxx1 <= minx2 || maxx2 <= minx1 ||
231 maxy1 <= miny2 || maxy2 <= miny1) {
232 /* bounding boxes don't intersect */
235 double adx = s1->delta.x;
236 double ady = s1->delta.y;
237 double bdx = s2->delta.x;
238 double bdy = s2->delta.y;
239 double det = adx*bdy - ady*bdx;
242 // lines are exactly on top of each other (ignored)
243 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
246 /* lines are parallel */
250 double asign2 = LINE_EQ(s1->a, s2);
251 double bsign2 = LINE_EQ(s1->b, s2);
252 if(asign2<0 && bsign2<0) {
253 // segment1 is completely to the left of segment2
256 if(asign2>0 && bsign2>0) {
257 // segment2 is completely to the left of segment1
261 // segment1 touches segment2 in a single point (ignored)
263 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
268 // segment1 touches segment2 in a single point (ignored)
270 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
274 double asign1 = LINE_EQ(s2->a, s1);
275 double bsign1 = LINE_EQ(s2->b, s1);
276 if(asign1<0 && bsign1<0) {
277 // segment1 is completely to the left of segment2
280 if(asign1>0 && bsign1>0) {
281 // segment2 is completely to the left of segment1
285 // segment2 touches segment1 in a single point (ignored)
287 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
292 // segment2 touches segment1 in a single point (ignored)
294 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
299 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
300 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
303 p.x = (int32_t)ceil((-la*bdx +lb*adx) / det);
304 p.y = (int32_t)ceil((+lb*ady -la*bdy) / det);
305 /* we only schedule crossings if they are *after* the current y. That way, we don't
306 schedule the same crossing twice */
312 assert(!dict_contains(status->seen_crossings, &pair));
313 dict_put(status->seen_crossings, &pair, 0);
315 event_t e = event_new();
316 e.type = EVENT_CROSS;
321 printf("schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, e.p.x, e.p.y);
323 /* we insert into each other's intersection history because these segments might switch
325 dict_put(&s1->scheduled_crossings, s2, 0);
326 dict_put(&s2->scheduled_crossings, s1, 0);
328 heap_put(status->queue, &e);
333 /* routine dealing with the special case of a number of line segments intersecting in exactly one
335 void exchange_many(status_t*status, event_t*e)
339 segment_t**segs = (segment_t**)malloc(sizeof(segment_t*)*size);
340 segs[n] = e->s1;e->s1->tmp = n;n++;
341 segs[n] = e->s2;e->s2->tmp = n;n++;
343 dict_put(status->intersecting_segs, e->s1, 0);
344 dict_put(status->intersecting_segs, e->s2, 0);
347 event_t*ee = heap_peek(status->queue);
348 if(ee->p.x != e->p.x ||
350 ee->type != e->type) {
355 segs = realloc(segs, sizeof(segment_t*)*size);
357 ee = heap_chopmax(status->queue);
359 segs[n] = ee->s1;ee->s1->tmp = n;n++;
362 segs[n] = ee->s2;ee->s2->tmp = n;n++;
365 dict_put(status->intersecting_segs, ee->s1, 0);
366 dict_put(status->intersecting_segs, ee->s2, 0);
371 printf("event: multi-intersect: ");
373 printf("[%d] ", segs[t]->nr);
381 if(!segs[t]->left || segs[t]->left->tmp<0) {
385 if(!segs[t]->right || segs[t]->right->tmp<0) {
393 fprintf(stderr, "Warning: multi-cross section contains rogue segments\n");
398 actlist_invert_fromto(status->actlist, left, right);
404 schedule_crossing(status, right->left, right, status->y);
406 schedule_crossing(status, left, left->right, status->y);
409 void exchange_two(status_t*status, event_t*e)
411 //exchange two segments in list
412 segment_t*s1 = e->s1;
413 segment_t*s2 = e->s2;
415 dict_put(status->intersecting_segs, s1, 0);
416 dict_put(status->intersecting_segs, s2, 0);
418 segment_t*left = actlist_left(status->actlist, s2);
419 segment_t*right = actlist_right(status->actlist, s1);
422 actlist_swap(status->actlist, s1, s2);
423 assert(actlist_right(status->actlist, s2) == s1);
424 assert(actlist_left(status->actlist, s1) == s2);
425 left = actlist_left(status->actlist, s2);
426 right = actlist_right(status->actlist, s1);
428 schedule_crossing(status, left, s2, status->y);
430 schedule_crossing(status, s1, right, status->y);
433 void insert_point_into_segment(segment_t*s, point_t p)
435 if(s->pos.x == p.x && s->pos.y == p.y) {
437 fprintf(stderr, "Notice: tried to add (%d,%d) to segment [%d] twice\n", p.x, p.y, s->nr);
442 printf("[%d] gets extra point (%d,%d)\n", s->nr, p.x, p.y);
447 typedef struct _box {
448 point_t left1, left2, right1, right2;
450 static inline box_t box_new(int x, int y)
453 box.right1.x = box.right2.x = x;
454 box.left1.x = box.left2.x = x-1;
455 box.left1.y = box.right1.y = y-1;
456 box.left2.y = box.right2.y = y;
460 /* possible optimizations:
461 1.) keep two different active lists around, one for negative and one for
463 2.) delay starting events until after this function (tricky, because we *do*
464 need the start coordinates)
475 void add_points_to_positively_sloped_segments(status_t*status, xrow_t*xrow, int32_t y)
478 for(t=0;t<xrow->num;t++) {
479 box_t box = box_new(xrow->x[t], y);
480 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
484 seg = actlist_leftmost(status->actlist);
487 // this segment just started, ignore it
488 } else if(seg->delta.x < 0) {
489 // ignore segment w/ negative slope
491 double d1 = LINE_EQ(box.right1, seg);
492 double d2 = LINE_EQ(box.right2, seg);
495 dict_put(status->segs_with_point, seg, 0);
497 insert_point_into_segment(seg, box.right2);
514 void add_points_to_negatively_sloped_segments(status_t*status, xrow_t*xrow, int32_t y)
517 for(t=xrow->num-1;t>=0;t--) {
518 box_t box = box_new(xrow->x[t], y);
519 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
522 // this segment just started, ignore it
523 } else if(seg->delta.x >= 0) {
524 // ignore segment w/ positive slope
526 double d1 = LINE_EQ(box.left1, seg);
527 double d2 = LINE_EQ(box.left2, seg);
530 dict_put(status->segs_with_point, seg, 0);
532 insert_point_into_segment(seg, box.right2);
542 void event_apply(status_t*status, event_t*e)
546 //delete segment from list
549 insert_point_into_segment(s, s->b);
550 segment_t*left = actlist_left(status->actlist, s);
551 segment_t*right = actlist_right(status->actlist, s);
552 actlist_delete(status->actlist, s);
553 dict_clear(&s->scheduled_crossings);
555 schedule_crossing(status, left, right, status->y+1);
559 //insert segment into list
562 actlist_insert(status->actlist, e->p, s);
563 segment_t*left = actlist_left(status->actlist, s);
564 segment_t*right = actlist_right(status->actlist, s);
566 schedule_crossing(status, left, s, status->y+1);
568 schedule_crossing(status, s, right, status->y+1);
572 // exchange two (or more) segments
573 event_t*ee = heap_peek(status->queue);
574 if(ee->p.x != e->p.x ||
576 ee->type != e->type) {
578 exchange_two(status, e);
580 exchange_many(status, e);
587 void check_status(status_t*status)
589 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
590 if(!dict_contains(status->segs_with_point, s)) {
591 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
593 s->delta.x<0?"-":"+",
601 void gfxpoly_process(segment_t*poly)
603 heap_t* queue = heap_new(sizeof(event_t), compare_events);
604 segments_enqueue(poly, queue);
606 memset(&status, 0, sizeof(status_t));
607 status.queue = queue;
608 status.actlist = actlist_new();
610 status.seen_crossings = dict_new2(&point_type);
613 xrow_t*xrow = xrow_new();
615 event_t*e = heap_chopmax(queue);
619 status.intersecting_segs = dict_new2(&ptr_type);
620 status.segs_with_point = dict_new2(&ptr_type);
621 printf("----------------------------------- %d\n", status.y);
622 actlist_verify_and_dump(status.actlist, status.y-1);
626 xrow_add(xrow, e->p.x);
627 event_apply(&status, e);
629 e = heap_chopmax(queue);
630 } while(e && status.y == e->p.y);
633 add_points_to_positively_sloped_segments(&status, xrow, status.y);
634 add_points_to_negatively_sloped_segments(&status, xrow, status.y);
636 check_status(&status);
637 dict_destroy(status.intersecting_segs);
638 dict_destroy(status.segs_with_point);
642 dict_destroy(status.seen_crossings);
645 gfxpoly_destroy(poly);