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 {
54 dict_t*seen_crossings; //list of crossing we saw so far
55 dict_t*intersecting_segs; //list of segments intersecting in this scanline
56 dict_t*segs_with_point; //lists of segments that received a point in this scanline
60 int compare_events(const void*_a,const void*_b)
62 event_t* a = (event_t*)_a;
63 event_t* b = (event_t*)_b;
66 } else if(a->p.y > b->p.y) {
68 /* we should schedule start events after end/intersect.
69 The order of end/intersect doesn't actually matter, however,
70 so this might be doing too much */
71 } else if(a->type < b->type) {
73 } else if(a->type > b->type) {
75 } else if(a->p.x < b->p.x) {
77 } else if(a->p.x > b->p.x) {
83 gfxpoly_t* gfxpoly_new()
87 void gfxpoly_destroy(gfxpoly_t*poly)
91 edge_t*next = s->next;
97 void gfxpoly_dump(gfxpoly_t*poly)
99 edge_t* s = (edge_t*)poly;
101 fprintf(stderr, "(%d,%d) -> (%d,%d)\n", s->a.x, s->a.y, s->b.x, s->b.y);
106 inline static event_t event_new()
109 memset(&e, 0, sizeof(e));
113 void event_dump(event_t*e)
115 if(e->type == EVENT_START) {
116 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
117 } else if(e->type == EVENT_END) {
118 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
119 } else if(e->type == EVENT_CROSS) {
120 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
126 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
127 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
129 void segment_init(segment_t*s, int x1, int y1, int x2, int y2)
135 int x = x1;x1=x2;x2=x;
136 int y = y1;y1=y2;y2=y;
143 s->k = (double)x1*y2-(double)x2*y1;
144 s->left = s->right = 0;
150 static int segment_count=0; //for debugging
151 s->nr = segment_count++;
154 assert(LINE_EQ(s->a, s) == 0);
155 assert(LINE_EQ(s->b, s) == 0);
157 /* check that all signs are in order:
165 p.x = min32(s->a.x, s->b.x);
166 assert(LINE_EQ(p, s) <= 0);
167 p.x = max32(s->a.x, s->b.x);
168 assert(LINE_EQ(p, s) >= 0);
170 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
173 segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2)
175 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
176 segment_init(s, x1, y1, x2, y2);
179 void segment_destroy(segment_t*s)
181 dict_clear(&s->scheduled_crossings);
185 void gfxpoly_enqueue(edge_t*list, heap_t*queue)
189 segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y);
191 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n",
192 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
193 s->dir==DIR_UP?"up":"down");
195 event_t e = event_new();
196 e.type = EVENT_START;
205 void schedule_endpoint(status_t*status, segment_t*s)
207 // schedule end point of segment
208 assert(s->b.y > status->y);
214 heap_put(status->queue, &e);
217 void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
219 /* the code that's required (and the checks you can perform) before
220 it can be said with 100% certainty that we indeed have a valid crossing
221 amazes me every time. -mk */
224 /* we probably could precompute these */
225 int32_t minx1 = min32(s1->a.x,s1->b.x);
226 int32_t miny1 = min32(s1->a.y,s1->b.y);
227 int32_t maxx1 = max32(s1->a.x,s1->b.x);
228 int32_t maxy1 = max32(s1->a.y,s1->b.y);
229 int32_t minx2 = min32(s2->a.x,s2->b.x);
230 int32_t miny2 = min32(s2->a.y,s2->b.y);
231 int32_t maxx2 = max32(s2->a.x,s2->b.x);
232 int32_t maxy2 = max32(s2->a.y,s2->b.y);
234 /* both segments are active, so this can't happen */
235 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
237 /* TODO: optimize this. remove y, precompute the two x values */
238 if(maxx1 <= minx2 || maxx2 <= minx1 ||
239 maxy1 <= miny2 || maxy2 <= miny1) {
240 /* bounding boxes don't intersect */
244 if(dict_contains(&s1->scheduled_crossings, s2)) {
245 // we already know about this one
249 double adx = s1->delta.x;
250 double ady = s1->delta.y;
251 double bdx = s2->delta.x;
252 double bdy = s2->delta.y;
253 double det = adx*bdy - ady*bdx;
256 // lines are exactly on top of each other (ignored)
258 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
262 /* lines are parallel */
266 double asign2 = LINE_EQ(s1->a, s2);
267 double bsign2 = LINE_EQ(s1->b, s2);
268 if(asign2<0 && bsign2<0) {
269 // segment1 is completely to the left of segment2
272 if(asign2>0 && bsign2>0) {
273 // segment2 is completely to the left of segment1
277 // segment1 touches segment2 in a single point (ignored)
279 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
284 // segment1 touches segment2 in a single point (ignored)
286 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
290 double asign1 = LINE_EQ(s2->a, s1);
291 double bsign1 = LINE_EQ(s2->b, s1);
292 if(asign1<0 && bsign1<0) {
293 // segment1 is completely to the left of segment2
296 if(asign1>0 && bsign1>0) {
297 // segment2 is completely to the left of segment1
301 // segment2 touches segment1 in a single point (ignored)
303 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
308 // segment2 touches segment1 in a single point (ignored)
310 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
315 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
316 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
319 p.x = (int32_t)ceil((-la*bdx +lb*adx) / det);
320 p.y = (int32_t)ceil((+lb*ady -la*bdy) / det);
322 assert(p.y >= status->y);
327 assert(!dict_contains(status->seen_crossings, &pair));
328 dict_put(status->seen_crossings, &pair, 0);
329 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
332 /* we insert into each other's intersection history because these segments might switch
333 places and we still want to look them up quickly after they did */
334 dict_put(&s1->scheduled_crossings, s2, 0);
335 dict_put(&s2->scheduled_crossings, s1, 0);
337 event_t e = event_new();
338 e.type = EVENT_CROSS;
342 heap_put(status->queue, &e);
346 void exchange_two(status_t*status, event_t*e)
348 //exchange two segments in list
349 segment_t*s1 = e->s1;
350 segment_t*s2 = e->s2;
352 if(!dict_contains(status->intersecting_segs, s1))
353 dict_put(status->intersecting_segs, s1, 0);
354 if(!dict_contains(status->intersecting_segs, s2))
355 dict_put(status->intersecting_segs, s2, 0);
357 segment_t*left = actlist_left(status->actlist, s2);
358 segment_t*right = actlist_right(status->actlist, s1);
361 actlist_swap(status->actlist, s1, s2);
362 assert(actlist_right(status->actlist, s2) == s1);
363 assert(actlist_left(status->actlist, s1) == s2);
364 left = actlist_left(status->actlist, s2);
365 right = actlist_right(status->actlist, s1);
367 schedule_crossing(status, left, s2);
369 schedule_crossing(status, s1, right);
372 void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
375 if(s->pos.x == p.x && s->pos.y == p.y) {
376 fprintf(stderr, "Error: tried to add (%d,%d) to segment [%d] twice\n", p.x, p.y, s->nr);
379 assert(s->pos.x != p.x || s->pos.y != p.y);
381 fprintf(stderr, "[%d] gets extra point (%d,%d)\n", s->nr, p.x, p.y);
384 edge_t*e = malloc(sizeof(edge_t));
387 e->next = status->output;
393 typedef struct _box {
394 point_t left1, left2, right1, right2;
396 static inline box_t box_new(int x, int y)
399 box.right1.x = box.right2.x = x;
400 box.left1.x = box.left2.x = x-1;
401 box.left1.y = box.right1.y = y-1;
402 box.left2.y = box.right2.y = y;
406 /* possible optimizations:
407 1.) keep two different active lists around, one for negative and one for
409 2.) delay starting events until after this function (tricky, because we *do*
410 need the start coordinates)
421 void add_points_to_positively_sloped_segments(status_t*status, xrow_t*xrow, int32_t y)
424 for(t=0;t<xrow->num;t++) {
425 box_t box = box_new(xrow->x[t], y);
426 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
430 seg = actlist_leftmost(status->actlist);
433 // this segment just started, ignore it
434 } else if(seg->delta.x < 0) {
435 // ignore segment w/ negative slope
437 double d1 = LINE_EQ(box.right1, seg);
438 double d2 = LINE_EQ(box.right2, seg);
441 dict_put(status->segs_with_point, seg, 0);
443 insert_point_into_segment(status, seg, box.right2);
460 void add_points_to_negatively_sloped_segments(status_t*status, xrow_t*xrow, int32_t y)
463 for(t=xrow->num-1;t>=0;t--) {
464 box_t box = box_new(xrow->x[t], y);
465 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
468 // this segment just started, ignore it
469 } else if(seg->delta.x >= 0) {
470 // ignore segment w/ positive slope
472 double d1 = LINE_EQ(box.left1, seg);
473 double d2 = LINE_EQ(box.left2, seg);
476 dict_put(status->segs_with_point, seg, 0);
478 insert_point_into_segment(status, seg, box.right2);
488 void event_apply(status_t*status, event_t*e)
492 //delete segment from list
496 dict_del(status->intersecting_segs, s);
497 dict_del(status->segs_with_point, s);
498 assert(!dict_contains(status->intersecting_segs, s));
499 assert(!dict_contains(status->segs_with_point, s));
501 insert_point_into_segment(status, s, s->b);
502 segment_t*left = actlist_left(status->actlist, s);
503 segment_t*right = actlist_right(status->actlist, s);
504 actlist_delete(status->actlist, s);
506 schedule_crossing(status, left, right);
507 segment_destroy(s);e->s1=0;
511 //insert segment into list
516 actlist_insert(status->actlist, e->p, s);
517 segment_t*left = actlist_left(status->actlist, s);
518 segment_t*right = actlist_right(status->actlist, s);
520 schedule_crossing(status, left, s);
522 schedule_crossing(status, s, right);
524 schedule_endpoint(status, e->s1);
528 // exchange two (or more) segments
529 if(actlist_right(status->actlist, e->s1) == e->s2 &&
530 actlist_left(status->actlist, e->s2) == e->s1) {
531 exchange_two(status, e);
533 /* ignore this crossing for now (there are some line segments in between).
534 it'll get rescheduled as soon as the "obstacles" are gone */
535 char del1 = dict_del(&e->s1->scheduled_crossings, e->s2);
536 char del2 = dict_del(&e->s2->scheduled_crossings, e->s1);
537 assert(del1 && del2);
542 assert(dict_contains(status->seen_crossings, &pair));
543 dict_del(status->seen_crossings, &pair);
551 void check_status(status_t*status)
553 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
554 if((s->pos.x != s->b.x ||
555 s->pos.y != s->b.y) &&
556 !dict_contains(status->segs_with_point, s)) {
557 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
559 s->delta.x<0?"-":"+",
567 edge_t* gfxpoly_process(edge_t*poly)
569 heap_t* queue = heap_new(sizeof(event_t), compare_events);
570 gfxpoly_enqueue(poly, queue);
572 memset(&status, 0, sizeof(status_t));
573 status.queue = queue;
574 status.actlist = actlist_new();
576 status.seen_crossings = dict_new2(&point_type);
580 xrow_t*xrow = xrow_new();
582 event_t*e = heap_chopmax(queue);
586 status.intersecting_segs = dict_new2(&ptr_type);
587 status.segs_with_point = dict_new2(&ptr_type);
588 fprintf(stderr, "----------------------------------- %d\n", status.y);
589 actlist_verify_and_dump(status.actlist, status.y-1);
593 xrow_add(xrow, e->p.x);
594 event_apply(&status, e);
596 e = heap_chopmax(queue);
597 } while(e && status.y == e->p.y);
600 add_points_to_positively_sloped_segments(&status, xrow, status.y);
601 add_points_to_negatively_sloped_segments(&status, xrow, status.y);
603 check_status(&status);
604 dict_destroy(status.intersecting_segs);
605 dict_destroy(status.segs_with_point);
609 dict_destroy(status.seen_crossings);
611 actlist_destroy(status.actlist);
615 return status.output;