16 char point_equals(const void*o1, const void*o2)
18 const point_t*p1 = o1;
19 const point_t*p2 = o2;
20 return p1->x == p2->x && p1->y == p2->y;
22 unsigned int point_hash(const void*o)
27 void* point_dup(const void*o)
30 point_t*n = malloc(sizeof(point_t));
35 void point_free(void*o)
49 typedef struct _status {
58 dict_t*seen_crossings; //list of crossing we saw so far
59 dict_t*intersecting_segs; //list of segments intersecting in this scanline
60 dict_t*segs_with_point; //lists of segments that received a point in this scanline
64 int compare_events(const void*_a,const void*_b)
66 event_t* a = (event_t*)_a;
67 event_t* b = (event_t*)_b;
70 } else if(a->p.y > b->p.y) {
72 /* we should schedule start events after end/intersect.
73 The order of end/intersect doesn't actually matter, however,
74 so this might be doing too much */
75 } else if(a->type < b->type) {
77 } else if(a->type > b->type) {
79 } else if(a->p.x < b->p.x) {
81 } else if(a->p.x > b->p.x) {
87 gfxpoly_t* gfxpoly_new(double gridsize)
89 gfxpoly_t*p = (gfxpoly_t*)rfx_calloc(sizeof(gfxpoly_t));
90 p->gridsize = gridsize;
93 void gfxpoly_destroy(gfxpoly_t*poly)
95 edge_t* s = poly->edges;
97 edge_t*next = s->next;
104 void gfxpoly_dump(gfxpoly_t*poly)
106 edge_t* s = (edge_t*)poly;
108 fprintf(stderr, "(%d,%d) -> (%d,%d)\n", s->a.x, s->a.y, s->b.x, s->b.y);
113 inline static event_t event_new()
116 memset(&e, 0, sizeof(e));
120 void event_dump(event_t*e)
122 if(e->type == EVENT_HORIZONTAL) {
123 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);
124 } else if(e->type == EVENT_START) {
125 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
126 } else if(e->type == EVENT_END) {
127 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
128 } else if(e->type == EVENT_CROSS) {
129 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
135 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
136 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
138 void segment_init(segment_t*s, int x1, int y1, int x2, int y2, windstate_t windstate, int polygon_nr)
143 int x = x1;x1=x2;x2=x;
144 int y = y1;y1=y2;y2=y;
147 /* up/down for horizontal segments is handled by "rotating"
148 them 90° anticlockwise in screen coordinates (tilt your head to
153 int x = x1;x1=x2;x2=x;
154 int y = y1;y1=y2;y2=y;
161 s->k = (double)x1*y2-(double)x2*y1;
162 s->left = s->right = 0;
166 s->polygon_nr = polygon_nr;
169 static int segment_count=0;
170 s->nr = segment_count++;
173 assert(LINE_EQ(s->a, s) == 0);
174 assert(LINE_EQ(s->b, s) == 0);
176 /* check that all signs are in order:
184 p.x = min32(s->a.x, s->b.x);
185 assert(LINE_EQ(p, s) <= 0);
186 p.x = max32(s->a.x, s->b.x);
187 assert(LINE_EQ(p, s) >= 0);
189 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
192 segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2, windstate_t initial, int polygon_nr)
194 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
195 segment_init(s, x1, y1, x2, y2, initial, polygon_nr);
198 void segment_destroy(segment_t*s)
200 dict_clear(&s->scheduled_crossings);
204 void gfxpoly_enqueue(edge_t*list, heap_t*queue, windstate_t initial, int polygon_nr)
207 for(l=list;l;l=l->next) {
208 if(l->a.x == l->b.x &&
210 fprintf(stderr, "Warning: intersector input contains zero-length segments\n");
213 segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y, initial, polygon_nr);
215 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n",
216 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
217 s->dir==DIR_UP?"up":"down");
219 event_t e = event_new();
220 e.type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
228 void schedule_endpoint(status_t*status, segment_t*s)
230 // schedule end point of segment
231 assert(s->b.y > status->y);
237 heap_put(status->queue, &e);
240 void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
242 /* the code that's required (and the checks you can perform) before
243 it can be said with 100% certainty that we indeed have a valid crossing
244 amazes me every time. -mk */
247 /* we probably could precompute these */
248 int32_t minx1 = min32(s1->a.x,s1->b.x);
249 int32_t miny1 = min32(s1->a.y,s1->b.y);
250 int32_t maxx1 = max32(s1->a.x,s1->b.x);
251 int32_t maxy1 = max32(s1->a.y,s1->b.y);
252 int32_t minx2 = min32(s2->a.x,s2->b.x);
253 int32_t miny2 = min32(s2->a.y,s2->b.y);
254 int32_t maxx2 = max32(s2->a.x,s2->b.x);
255 int32_t maxy2 = max32(s2->a.y,s2->b.y);
257 /* both segments are active, so this can't happen */
258 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
260 /* TODO: optimize this. remove y, precompute the two x values */
261 if(maxx1 <= minx2 || maxx2 <= minx1 ||
262 maxy1 <= miny2 || maxy2 <= miny1) {
263 /* bounding boxes don't intersect */
267 if(dict_contains(&s1->scheduled_crossings, s2)) {
268 /* FIXME: this whole segment hashing thing is really slow */
269 //fprintf(stderr, "Encountered crossing between [%d] and [%d] twice\n", s1->nr, s2->nr);
271 // we already know about this one
275 double adx = s1->delta.x;
276 double ady = s1->delta.y;
277 double bdx = s2->delta.x;
278 double bdy = s2->delta.y;
279 double det = adx*bdy - ady*bdx;
282 // lines are exactly on top of each other (ignored)
284 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
288 /* lines are parallel */
292 double asign2 = LINE_EQ(s1->a, s2);
293 double bsign2 = LINE_EQ(s1->b, s2);
294 if(asign2<0 && bsign2<0) {
295 // segment1 is completely to the left of segment2
298 if(asign2>0 && bsign2>0) {
299 // segment2 is completely to the left of segment1
303 // segment1 touches segment2 in a single point (ignored)
305 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
310 // segment1 touches segment2 in a single point (ignored)
312 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
316 double asign1 = LINE_EQ(s2->a, s1);
317 double bsign1 = LINE_EQ(s2->b, s1);
318 if(asign1<0 && bsign1<0) {
319 // segment1 is completely to the left of segment2
322 if(asign1>0 && bsign1>0) {
323 // segment2 is completely to the left of segment1
327 // segment2 touches segment1 in a single point (ignored)
329 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
334 // segment2 touches segment1 in a single point (ignored)
336 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
341 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
342 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
345 p.x = (int32_t)ceil((-la*bdx +lb*adx) / det);
346 p.y = (int32_t)ceil((+lb*ady -la*bdy) / det);
348 assert(p.y >= status->y);
353 assert(!dict_contains(status->seen_crossings, &pair));
354 dict_put(status->seen_crossings, &pair, 0);
355 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
358 /* we insert into each other's intersection history because these segments might switch
359 places and we still want to look them up quickly after they did */
360 dict_put(&s1->scheduled_crossings, s2, 0);
361 dict_put(&s2->scheduled_crossings, s1, 0);
363 event_t e = event_new();
364 e.type = EVENT_CROSS;
368 heap_put(status->queue, &e);
372 void exchange_two(status_t*status, event_t*e)
374 //exchange two segments in list
375 segment_t*s1 = e->s1;
376 segment_t*s2 = e->s2;
378 if(!dict_contains(status->intersecting_segs, s1))
379 dict_put(status->intersecting_segs, s1, 0);
380 if(!dict_contains(status->intersecting_segs, s2))
381 dict_put(status->intersecting_segs, s2, 0);
383 segment_t*left = actlist_left(status->actlist, s2);
384 segment_t*right = actlist_right(status->actlist, s1);
387 actlist_swap(status->actlist, s1, s2);
388 assert(actlist_right(status->actlist, s2) == s1);
389 assert(actlist_left(status->actlist, s1) == s2);
390 left = actlist_left(status->actlist, s2);
391 right = actlist_right(status->actlist, s1);
393 schedule_crossing(status, left, s2);
395 schedule_crossing(status, s1, right);
398 typedef struct _box {
399 point_t left1, left2, right1, right2;
401 static inline box_t box_new(int x, int y)
404 box.right1.x = box.right2.x = x;
405 box.left1.x = box.left2.x = x-1;
406 box.left1.y = box.right1.y = y-1;
407 box.left2.y = box.right2.y = y;
412 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
414 assert(s->pos.x != p.x || s->pos.y != p.y);
417 if(!dict_contains(status->segs_with_point, s))
418 dict_put(status->segs_with_point, s, 0);
421 assert(s->fs_out_ok);
424 fprintf(stderr, "[%d] receives next point (%d,%d) (drawing)\n", s->nr, p.x, p.y);
426 // omit horizontal lines
427 if(s->pos.y != p.y) {
428 edge_t*e = malloc(sizeof(edge_t));
431 assert(e->a.y != e->b.y);
432 e->next = status->output;
437 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
443 /* possible optimizations:
444 1.) keep two different active lists around, one for negative and one for
446 2.) delay starting events until after this function (tricky, because we *do*
447 need the start coordinates)
458 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y)
461 for(t=0;t<status->xrow->num;t++) {
462 box_t box = box_new(status->xrow->x[t], y);
463 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
464 seg = actlist_right(status->actlist, seg);
467 // this segment just started, ignore it
468 } else if(seg->delta.x < 0) {
469 // ignore segment w/ negative slope
471 double d1 = LINE_EQ(box.right1, seg);
472 double d2 = LINE_EQ(box.right2, seg);
474 insert_point_into_segment(status, seg, box.right2);
479 seg = actlist_right(status->actlist, seg);
491 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y)
494 for(t=status->xrow->num-1;t>=0;t--) {
495 box_t box = box_new(status->xrow->x[t], y);
496 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
499 // this segment just started, ignore it
500 } else if(seg->delta.x >= 0) {
501 // ignore segment w/ positive slope
503 double d1 = LINE_EQ(box.left1, seg);
504 double d2 = LINE_EQ(box.left2, seg);
506 insert_point_into_segment(status, seg, box.right2);
511 seg = actlist_left(status->actlist, seg);
516 static void recalculate_windings(status_t*status)
518 /* TODO: we could use some clever second linked list structure so that we
519 only need to process points we know we marked */
521 segment_t*s = actlist_leftmost(status->actlist);
524 windstate_t wind = last?last->wind:status->windrule->start(status->num_polygons);
525 s->wind = status->windrule->add(wind, s->fs, s->dir, s->polygon_nr);
526 s->fs_out = status->windrule->diff(&wind, &s->wind);
529 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");
532 s = actlist_right(status->actlist, s);
535 fprintf(stderr, "\n");
540 void intersect_with_horizontal(status_t*status, segment_t*h)
542 segment_t* left = actlist_find(status->actlist, h->a, h->a);
543 segment_t* right = actlist_find(status->actlist, h->b, h->b);
545 segment_t* s = right;
550 x1 + ((x2-x1)*(y-y1)) / dy =
551 (x1*(y2-y) + x2*(y-y1)) / dy
557 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
563 assert(p.x >= h->a.x);
564 assert(p.x <= h->b.x);
565 assert(s->delta.x > 0 && p.x >= s->a.x || s->delta.x <= 0 && p.x <= s->a.x);
566 assert(s->delta.x > 0 && p.x <= s->b.x || s->delta.x <= 0 && p.x >= s->b.x);
567 xrow_add(status->xrow, p.x);
569 s = actlist_left(status->actlist, s);
571 xrow_add(status->xrow, h->a.x);
574 void event_apply(status_t*status, event_t*e)
577 case EVENT_HORIZONTAL: {
581 intersect_with_horizontal(status, e->s1);
585 //delete segment from list
589 dict_del(status->intersecting_segs, s);
590 dict_del(status->segs_with_point, s);
591 assert(!dict_contains(status->intersecting_segs, s));
592 assert(!dict_contains(status->segs_with_point, s));
594 insert_point_into_segment(status, s, s->b);
595 segment_t*left = actlist_left(status->actlist, s);
596 segment_t*right = actlist_right(status->actlist, s);
597 actlist_delete(status->actlist, s);
599 schedule_crossing(status, left, right);
600 segment_destroy(s);e->s1=0;
604 //insert segment into list
609 actlist_insert(status->actlist, e->p, s);
610 segment_t*left = actlist_left(status->actlist, s);
611 segment_t*right = actlist_right(status->actlist, s);
613 schedule_crossing(status, left, s);
615 schedule_crossing(status, s, right);
616 schedule_endpoint(status, e->s1);
620 // exchange two segments
624 if(actlist_right(status->actlist, e->s1) == e->s2 &&
625 actlist_left(status->actlist, e->s2) == e->s1) {
626 exchange_two(status, e);
628 /* ignore this crossing for now (there are some line segments in between).
629 it'll get rescheduled as soon as the "obstacles" are gone */
630 char del1 = dict_del(&e->s1->scheduled_crossings, e->s2);
631 char del2 = dict_del(&e->s2->scheduled_crossings, e->s1);
632 assert(del1 && del2);
637 assert(dict_contains(status->seen_crossings, &pair));
638 dict_del(status->seen_crossings, &pair);
646 void check_status(status_t*status)
648 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
649 if((s->pos.x != s->b.x ||
650 s->pos.y != s->b.y) &&
651 !dict_contains(status->segs_with_point, s)) {
652 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
654 s->delta.x<0?"-":"+",
662 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule)
664 heap_t* queue = heap_new(sizeof(event_t), compare_events);
666 gfxpoly_enqueue(poly->edges, queue, windrule->start(1), /*polygon nr*/0);
669 memset(&status, 0, sizeof(status_t));
670 status.num_polygons = 1;
671 status.queue = queue;
672 status.windrule = windrule;
673 status.actlist = actlist_new();
675 status.seen_crossings = dict_new2(&point_type);
678 status.xrow = xrow_new();
680 event_t*e = heap_chopmax(queue);
684 status.intersecting_segs = dict_new2(&ptr_type);
685 status.segs_with_point = dict_new2(&ptr_type);
686 fprintf(stderr, "----------------------------------- %d\n", status.y);
687 actlist_verify_and_dump(status.actlist, status.y-1);
689 xrow_reset(status.xrow);
691 if(e->type != EVENT_HORIZONTAL) {
692 xrow_add(status.xrow, e->p.x);
694 event_apply(&status, e);
696 e = heap_chopmax(queue);
697 } while(e && status.y == e->p.y);
699 xrow_sort(status.xrow);
700 add_points_to_positively_sloped_segments(&status, status.y);
701 add_points_to_negatively_sloped_segments(&status, status.y);
702 recalculate_windings(&status);
704 check_status(&status);
705 dict_destroy(status.intersecting_segs);
706 dict_destroy(status.segs_with_point);
710 dict_destroy(status.seen_crossings);
712 actlist_destroy(status.actlist);
714 xrow_destroy(status.xrow);
716 gfxpoly_t*p = gfxpoly_new(poly->gridsize);
717 p->edges = status.output;