15 char point_equals(const void*o1, const void*o2)
17 const point_t*p1 = o1;
18 const point_t*p2 = o2;
19 return p1->x == p2->x && p1->y == p2->y;
21 unsigned int point_hash(const void*o)
26 void* point_dup(const void*o)
29 point_t*n = malloc(sizeof(point_t));
34 void point_free(void*o)
48 typedef struct _status {
55 dict_t*seen_crossings; //list of crossing we saw so far
56 dict_t*intersecting_segs; //list of segments intersecting in this scanline
57 dict_t*segs_with_point; //lists of segments that received a point in this scanline
61 int compare_events(const void*_a,const void*_b)
63 event_t* a = (event_t*)_a;
64 event_t* b = (event_t*)_b;
67 } else if(a->p.y > b->p.y) {
69 /* we should schedule start events after end/intersect.
70 The order of end/intersect doesn't actually matter, however,
71 so this might be doing too much */
72 } else if(a->type < b->type) {
74 } else if(a->type > b->type) {
76 } else if(a->p.x < b->p.x) {
78 } else if(a->p.x > b->p.x) {
84 gfxpoly_t* gfxpoly_new()
88 void gfxpoly_destroy(gfxpoly_t*poly)
92 edge_t*next = s->next;
98 void gfxpoly_dump(gfxpoly_t*poly)
100 edge_t* s = (edge_t*)poly;
102 fprintf(stderr, "(%d,%d) -> (%d,%d)\n", s->a.x, s->a.y, s->b.x, s->b.y);
107 inline static event_t event_new()
110 memset(&e, 0, sizeof(e));
114 void event_dump(event_t*e)
116 if(e->type == EVENT_HORIZONTAL) {
117 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);
118 } else if(e->type == EVENT_START) {
119 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
120 } else if(e->type == EVENT_END) {
121 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
122 } else if(e->type == EVENT_CROSS) {
123 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
129 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
130 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
132 void segment_init(segment_t*s, int x1, int y1, int x2, int y2)
137 int x = x1;x1=x2;x2=x;
138 int y = y1;y1=y2;y2=y;
141 s->dir = DIR_HORIZONTAL;
143 int x = x1;x1=x2;x2=x;
144 int y = y1;y1=y2;y2=y;
151 s->k = (double)x1*y2-(double)x2*y1;
152 s->left = s->right = 0;
157 s->new_point.y = y1-1;
160 static int segment_count=0;
161 s->nr = segment_count++;
164 assert(LINE_EQ(s->a, s) == 0);
165 assert(LINE_EQ(s->b, s) == 0);
167 /* check that all signs are in order:
175 p.x = min32(s->a.x, s->b.x);
176 assert(LINE_EQ(p, s) <= 0);
177 p.x = max32(s->a.x, s->b.x);
178 assert(LINE_EQ(p, s) >= 0);
180 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
183 segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2)
185 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
186 segment_init(s, x1, y1, x2, y2);
189 void segment_destroy(segment_t*s)
191 dict_clear(&s->scheduled_crossings);
195 void gfxpoly_enqueue(edge_t*list, heap_t*queue)
198 for(l=list;l;l=l->next) {
199 if(l->a.x == l->b.x &&
201 fprintf(stderr, "Warning: intersector input contains zero-length segments\n");
204 segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y);
206 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n",
207 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
208 s->dir==DIR_UP?"up":"down");
210 event_t e = event_new();
211 e.type = s->dir==DIR_HORIZONTAL?EVENT_HORIZONTAL:EVENT_START;
219 void schedule_endpoint(status_t*status, segment_t*s)
221 // schedule end point of segment
222 assert(s->b.y > status->y);
228 heap_put(status->queue, &e);
231 void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
233 /* the code that's required (and the checks you can perform) before
234 it can be said with 100% certainty that we indeed have a valid crossing
235 amazes me every time. -mk */
238 /* we probably could precompute these */
239 int32_t minx1 = min32(s1->a.x,s1->b.x);
240 int32_t miny1 = min32(s1->a.y,s1->b.y);
241 int32_t maxx1 = max32(s1->a.x,s1->b.x);
242 int32_t maxy1 = max32(s1->a.y,s1->b.y);
243 int32_t minx2 = min32(s2->a.x,s2->b.x);
244 int32_t miny2 = min32(s2->a.y,s2->b.y);
245 int32_t maxx2 = max32(s2->a.x,s2->b.x);
246 int32_t maxy2 = max32(s2->a.y,s2->b.y);
248 /* both segments are active, so this can't happen */
249 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
251 /* TODO: optimize this. remove y, precompute the two x values */
252 if(maxx1 <= minx2 || maxx2 <= minx1 ||
253 maxy1 <= miny2 || maxy2 <= miny1) {
254 /* bounding boxes don't intersect */
258 if(dict_contains(&s1->scheduled_crossings, s2)) {
259 /* FIXME: this whole segment hashing thing is really slow */
260 //fprintf(stderr, "Encountered crossing between [%d] and [%d] twice\n", s1->nr, s2->nr);
262 // we already know about this one
266 double adx = s1->delta.x;
267 double ady = s1->delta.y;
268 double bdx = s2->delta.x;
269 double bdy = s2->delta.y;
270 double det = adx*bdy - ady*bdx;
273 // lines are exactly on top of each other (ignored)
275 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
279 /* lines are parallel */
283 double asign2 = LINE_EQ(s1->a, s2);
284 double bsign2 = LINE_EQ(s1->b, s2);
285 if(asign2<0 && bsign2<0) {
286 // segment1 is completely to the left of segment2
289 if(asign2>0 && bsign2>0) {
290 // segment2 is completely to the left of segment1
294 // segment1 touches segment2 in a single point (ignored)
296 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
301 // segment1 touches segment2 in a single point (ignored)
303 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
307 double asign1 = LINE_EQ(s2->a, s1);
308 double bsign1 = LINE_EQ(s2->b, s1);
309 if(asign1<0 && bsign1<0) {
310 // segment1 is completely to the left of segment2
313 if(asign1>0 && bsign1>0) {
314 // segment2 is completely to the left of segment1
318 // segment2 touches segment1 in a single point (ignored)
320 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
325 // segment2 touches segment1 in a single point (ignored)
327 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
332 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
333 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
336 p.x = (int32_t)ceil((-la*bdx +lb*adx) / det);
337 p.y = (int32_t)ceil((+lb*ady -la*bdy) / det);
339 assert(p.y >= status->y);
344 assert(!dict_contains(status->seen_crossings, &pair));
345 dict_put(status->seen_crossings, &pair, 0);
346 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
349 /* we insert into each other's intersection history because these segments might switch
350 places and we still want to look them up quickly after they did */
351 dict_put(&s1->scheduled_crossings, s2, 0);
352 dict_put(&s2->scheduled_crossings, s1, 0);
354 event_t e = event_new();
355 e.type = EVENT_CROSS;
359 heap_put(status->queue, &e);
363 void exchange_two(status_t*status, event_t*e)
365 //exchange two segments in list
366 segment_t*s1 = e->s1;
367 segment_t*s2 = e->s2;
369 if(!dict_contains(status->intersecting_segs, s1))
370 dict_put(status->intersecting_segs, s1, 0);
371 if(!dict_contains(status->intersecting_segs, s2))
372 dict_put(status->intersecting_segs, s2, 0);
374 segment_t*left = actlist_left(status->actlist, s2);
375 segment_t*right = actlist_right(status->actlist, s1);
378 actlist_swap(status->actlist, s1, s2);
379 assert(actlist_right(status->actlist, s2) == s1);
380 assert(actlist_left(status->actlist, s1) == s2);
381 left = actlist_left(status->actlist, s2);
382 right = actlist_right(status->actlist, s1);
384 schedule_crossing(status, left, s2);
386 schedule_crossing(status, s1, right);
389 typedef struct _box {
390 point_t left1, left2, right1, right2;
392 static inline box_t box_new(int x, int y)
395 box.right1.x = box.right2.x = x;
396 box.left1.x = box.left2.x = x-1;
397 box.left1.y = box.right1.y = y-1;
398 box.left2.y = box.right2.y = y;
402 void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
404 edge_t*e = malloc(sizeof(edge_t));
407 assert(e->a.y != e->b.y);
408 e->next = status->output;
412 void mark_point_in_segment(status_t*status, segment_t*s, point_t p)
415 if(s->pos.x == p.x && s->pos.y == p.y) {
416 fprintf(stderr, "Error: tried to add (%d,%d) to segment [%d] twice\n", p.x, p.y, s->nr);
419 assert(s->pos.x != p.x || s->pos.y != p.y);
421 fprintf(stderr, "[%d] gets extra point (%d,%d)\n", s->nr, p.x, p.y);
422 if(!dict_contains(status->segs_with_point, s))
423 dict_put(status->segs_with_point, s, 0);
425 if(s->new_point.y != p.y) {
431 /* possible optimizations:
432 1.) keep two different active lists around, one for negative and one for
434 2.) delay starting events until after this function (tricky, because we *do*
435 need the start coordinates)
446 static void mark_points_in_positively_sloped_segments(status_t*status, int32_t y)
449 for(t=0;t<status->xrow->num;t++) {
450 box_t box = box_new(status->xrow->x[t], y);
451 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
452 seg = actlist_right(status->actlist, seg);
455 // this segment just started, ignore it
456 } else if(seg->delta.x < 0) {
457 // ignore segment w/ negative slope
459 double d1 = LINE_EQ(box.right1, seg);
460 double d2 = LINE_EQ(box.right2, seg);
462 mark_point_in_segment(status, seg, box.right2);
467 seg = actlist_right(status->actlist, seg);
479 static void mark_points_in_negatively_sloped_segments(status_t*status, int32_t y)
482 for(t=status->xrow->num-1;t>=0;t--) {
483 box_t box = box_new(status->xrow->x[t], y);
484 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
487 // this segment just started, ignore it
488 } else if(seg->delta.x >= 0) {
489 // ignore segment w/ positive slope
491 double d1 = LINE_EQ(box.left1, seg);
492 double d2 = LINE_EQ(box.left2, seg);
494 mark_point_in_segment(status, seg, box.right2);
499 seg = actlist_left(status->actlist, seg);
504 static void add_points(status_t*status)
506 /* TODO: we could use some clever second linked list structure so that we
507 only need to process points which we know we marked */
509 segment_t*s = actlist_leftmost(status->actlist);
511 if(s->new_point.y == status->y) {
512 insert_point_into_segment(status, s, s->new_point);
515 s = actlist_right(status->actlist, s);
519 void intersect_with_horizontal(status_t*status, segment_t*h)
521 segment_t* left = actlist_find(status->actlist, h->a, h->a);
522 segment_t* right = actlist_find(status->actlist, h->b, h->b);
524 segment_t* s = right;
529 x1 + ((x2-x1)*(y-y1)) / dy =
530 (x1*(y2-y) + x2*(y-y1)) / dy
536 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
542 assert(p.x >= h->a.x);
543 assert(p.x <= h->b.x);
544 assert(s->delta.x > 0 && p.x >= s->a.x || s->delta.x <= 0 && p.x <= s->a.x);
545 assert(s->delta.x > 0 && p.x <= s->b.x || s->delta.x <= 0 && p.x >= s->b.x);
546 xrow_add(status->xrow, p.x);
548 s = actlist_left(status->actlist, s);
550 xrow_add(status->xrow, h->a.x);
553 void event_apply(status_t*status, event_t*e)
556 case EVENT_HORIZONTAL: {
560 intersect_with_horizontal(status, e->s1);
564 //delete segment from list
568 dict_del(status->intersecting_segs, s);
569 dict_del(status->segs_with_point, s);
570 assert(!dict_contains(status->intersecting_segs, s));
571 assert(!dict_contains(status->segs_with_point, s));
573 insert_point_into_segment(status, s, s->b);
574 segment_t*left = actlist_left(status->actlist, s);
575 segment_t*right = actlist_right(status->actlist, s);
576 actlist_delete(status->actlist, s);
578 schedule_crossing(status, left, right);
579 segment_destroy(s);e->s1=0;
583 //insert segment into list
588 actlist_insert(status->actlist, e->p, s);
589 segment_t*left = actlist_left(status->actlist, s);
590 segment_t*right = actlist_right(status->actlist, s);
592 schedule_crossing(status, left, s);
594 schedule_crossing(status, s, right);
596 schedule_endpoint(status, e->s1);
600 // exchange two (or more) segments
601 if(actlist_right(status->actlist, e->s1) == e->s2 &&
602 actlist_left(status->actlist, e->s2) == e->s1) {
603 exchange_two(status, e);
605 /* ignore this crossing for now (there are some line segments in between).
606 it'll get rescheduled as soon as the "obstacles" are gone */
607 char del1 = dict_del(&e->s1->scheduled_crossings, e->s2);
608 char del2 = dict_del(&e->s2->scheduled_crossings, e->s1);
609 assert(del1 && del2);
614 assert(dict_contains(status->seen_crossings, &pair));
615 dict_del(status->seen_crossings, &pair);
623 void check_status(status_t*status)
625 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
626 if((s->pos.x != s->b.x ||
627 s->pos.y != s->b.y) &&
628 !dict_contains(status->segs_with_point, s)) {
629 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
631 s->delta.x<0?"-":"+",
639 edge_t* gfxpoly_process(edge_t*poly)
641 heap_t* queue = heap_new(sizeof(event_t), compare_events);
642 gfxpoly_enqueue(poly, queue);
644 memset(&status, 0, sizeof(status_t));
645 status.queue = queue;
646 status.actlist = actlist_new();
648 status.seen_crossings = dict_new2(&point_type);
652 status.xrow = xrow_new();
654 event_t*e = heap_chopmax(queue);
658 status.intersecting_segs = dict_new2(&ptr_type);
659 status.segs_with_point = dict_new2(&ptr_type);
660 fprintf(stderr, "----------------------------------- %d\n", status.y);
661 actlist_verify_and_dump(status.actlist, status.y-1);
663 xrow_reset(status.xrow);
665 if(e->type != EVENT_HORIZONTAL) {
666 xrow_add(status.xrow, e->p.x);
668 event_apply(&status, e);
670 e = heap_chopmax(queue);
671 } while(e && status.y == e->p.y);
673 xrow_sort(status.xrow);
674 mark_points_in_positively_sloped_segments(&status, status.y);
675 mark_points_in_negatively_sloped_segments(&status, status.y);
678 check_status(&status);
679 dict_destroy(status.intersecting_segs);
680 dict_destroy(status.segs_with_point);
684 dict_destroy(status.seen_crossings);
686 actlist_destroy(status.actlist);
688 xrow_destroy(status.xrow);
690 return status.output;