From 163bdd5cab1758e4517e8365b3e40b5461d63640 Mon Sep 17 00:00:00 2001 From: Matthias Kramm Date: Thu, 30 Apr 2009 03:34:08 +0200 Subject: [PATCH] improved intersector horizontal line support --- lib/gfxpoly/active.c | 9 ++- lib/gfxpoly/active.h | 2 + lib/gfxpoly/convert.c | 2 +- lib/gfxpoly/poly.c | 191 ++++++++++++++++++++++++++++++++++--------------- lib/gfxpoly/poly.h | 7 +- lib/gfxpoly/test.c | 64 ++++++++++++----- lib/gfxpoly/xrow.c | 1 + lib/gfxpoly/xrow.h | 2 + 8 files changed, 197 insertions(+), 81 deletions(-) diff --git a/lib/gfxpoly/active.c b/lib/gfxpoly/active.c index 56c7b90..51e0796 100644 --- a/lib/gfxpoly/active.c +++ b/lib/gfxpoly/active.c @@ -76,6 +76,7 @@ static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s) s->left->right = s; if(s->right) s->right->left = s; + a->size++; } void actlist_insert(actlist_t*a, point_t p, segment_t*s) @@ -95,6 +96,11 @@ void actlist_delete(actlist_t*a, segment_t*s) s->right->left = s->left; } s->left = s->right = 0; + a->size--; +} +int actlist_size(actlist_t*a) +{ + return a->size; } segment_t* actlist_leftmost(actlist_t*a) @@ -109,7 +115,8 @@ segment_t* actlist_left(actlist_t*a, segment_t*s) segment_t* actlist_right(actlist_t*a, segment_t*s) { - return s->right; + if(s) return s->right; + else return a->list; } void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2) diff --git a/lib/gfxpoly/active.h b/lib/gfxpoly/active.h index 911ed63..791e659 100644 --- a/lib/gfxpoly/active.h +++ b/lib/gfxpoly/active.h @@ -8,10 +8,12 @@ typedef struct _actlist { //SPLAY_HEAD(root, actnode_t); segment_t*list; + int size; } actlist_t; actlist_t* actlist_new(); void actlist_destroy(actlist_t*a); +int actlist_size(actlist_t*a); void actlist_verify_and_dump(actlist_t*a, int32_t y); segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2); // finds segment immediately to the left of p1 (breaking ties w/ p2) void actlist_insert(actlist_t*a, point_t p, segment_t*s); diff --git a/lib/gfxpoly/convert.c b/lib/gfxpoly/convert.c index f71a096..39d1164 100644 --- a/lib/gfxpoly/convert.c +++ b/lib/gfxpoly/convert.c @@ -21,7 +21,7 @@ static inline void gfxpoly_add_edge(edge_t**list, double _x1, double _y1, double int y1 = ceil(_y1); int x2 = ceil(_x2); int y2 = ceil(_y2); - if(y1!=y2) { + if(x1!=x2 || y1!=y2) { edge_t*s = edge_new(x1, y1, x2, y2); s->next = *list; *list = s; diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c index 48e92f9..8b72269 100644 --- a/lib/gfxpoly/poly.c +++ b/lib/gfxpoly/poly.c @@ -50,6 +50,7 @@ typedef struct _status { actlist_t*actlist; heap_t*queue; edge_t*output; + xrow_t*xrow; #ifdef DEBUG dict_t*seen_crossings; //list of crossing we saw so far dict_t*intersecting_segs; //list of segments intersecting in this scanline @@ -112,7 +113,9 @@ inline static event_t event_new() void event_dump(event_t*e) { - if(e->type == EVENT_START) { + if(e->type == EVENT_HORIZONTAL) { + 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); + } else if(e->type == EVENT_START) { fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y); } else if(e->type == EVENT_END) { fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y); @@ -128,13 +131,18 @@ static inline min32(int32_t v1, int32_t v2) {return v1dir = DIR_DOWN; - } else { + } else if(y1>y2) { int x = x1;x1=x2;x2=x; int y = y1;y1=y2;y2=y; s->dir = DIR_UP; + } else { + s->dir = DIR_HORIZONTAL; + if(x1>x2) { + int x = x1;x1=x2;x2=x; + int y = y1;y1=y2;y2=y; + } } s->a.x = x1; s->a.y = y1; @@ -146,8 +154,10 @@ void segment_init(segment_t*s, int x1, int y1, int x2, int y2) s->delta.y = y2-y1; s->pos = s->a; s->tmp = -1; -#ifdef DEBUG - static int segment_count=0; //for debugging + s->new_point.y = y1-1; +#define XDEBUG +#ifdef XDEBUG + static int segment_count=0; s->nr = segment_count++; #endif @@ -184,8 +194,13 @@ void segment_destroy(segment_t*s) void gfxpoly_enqueue(edge_t*list, heap_t*queue) { - edge_t*l = list; - while(l) { + edge_t*l; + for(l=list;l;l=l->next) { + if(l->a.x == l->b.x && + l->a.y == l->b.y) { + fprintf(stderr, "Warning: intersector input contains zero-length segments\n"); + continue; + } segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y); #ifdef DEBUG fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n", @@ -193,12 +208,11 @@ void gfxpoly_enqueue(edge_t*list, heap_t*queue) s->dir==DIR_UP?"up":"down"); #endif event_t e = event_new(); - e.type = EVENT_START; + e.type = s->dir==DIR_HORIZONTAL?EVENT_HORIZONTAL:EVENT_START; e.p = s->a; e.s1 = s; e.s2 = 0; heap_put(queue, &e); - l = l->next; } } @@ -242,6 +256,9 @@ void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2) } if(dict_contains(&s1->scheduled_crossings, s2)) { + /* FIXME: this whole segment hashing thing is really slow */ + //fprintf(stderr, "Encountered crossing between [%d] and [%d] twice\n", s1->nr, s2->nr); + // we already know about this one return; } @@ -369,8 +386,31 @@ void exchange_two(status_t*status, event_t*e) schedule_crossing(status, s1, right); } +typedef struct _box { + point_t left1, left2, right1, right2; +} box_t; +static inline box_t box_new(int x, int y) +{ + box_t box; + box.right1.x = box.right2.x = x; + box.left1.x = box.left2.x = x-1; + box.left1.y = box.right1.y = y-1; + box.left2.y = box.right2.y = y; + return box; +} + void insert_point_into_segment(status_t*status, segment_t*s, point_t p) { + edge_t*e = malloc(sizeof(edge_t)); + e->a = s->pos; + e->b = p; + assert(e->a.y != e->b.y); + e->next = status->output; + status->output = e; +} + +void mark_point_in_segment(status_t*status, segment_t*s, point_t p) +{ #ifdef DEBUG if(s->pos.x == p.x && s->pos.y == p.y) { fprintf(stderr, "Error: tried to add (%d,%d) to segment [%d] twice\n", p.x, p.y, s->nr); @@ -379,30 +419,15 @@ void insert_point_into_segment(status_t*status, segment_t*s, point_t p) assert(s->pos.x != p.x || s->pos.y != p.y); #ifdef DEBUG fprintf(stderr, "[%d] gets extra point (%d,%d)\n", s->nr, p.x, p.y); + if(!dict_contains(status->segs_with_point, s)) + dict_put(status->segs_with_point, s, 0); #endif - - edge_t*e = malloc(sizeof(edge_t)); - e->a = s->pos; - e->b = p; - e->next = status->output; - status->output = e; - - s->pos = p; + if(s->new_point.y != p.y) { + s->new_point = p; + } + s->new_pos = p; } -typedef struct _box { - point_t left1, left2, right1, right2; -} box_t; -static inline box_t box_new(int x, int y) -{ - box_t box; - box.right1.x = box.right2.x = x; - box.left1.x = box.left2.x = x-1; - box.left1.y = box.right1.y = y-1; - box.left2.y = box.right2.y = y; - return box; -} - /* possible optimizations: 1.) keep two different active lists around, one for negative and one for positive slopes @@ -411,23 +436,20 @@ static inline box_t box_new(int x, int y) */ /* SLOPE_POSITIVE: - + \ + + \+ \ + ------ I \I -I\---- I I \ --I\--- I \ I \ ------- + \ + \ */ -void add_points_to_positively_sloped_segments(status_t*status, xrow_t*xrow, int32_t y) +static void mark_points_in_positively_sloped_segments(status_t*status, int32_t y) { int t; - for(t=0;tnum;t++) { - box_t box = box_new(xrow->x[t], y); + for(t=0;txrow->num;t++) { + box_t box = box_new(status->xrow->x[t], y); segment_t*seg = actlist_find(status->actlist, box.left2, box.left2); - if(seg) - seg = seg->right; - else - seg = actlist_leftmost(status->actlist); + seg = actlist_right(status->actlist, seg); while(seg) { if(seg->a.y == y) { // this segment just started, ignore it @@ -437,15 +459,12 @@ void add_points_to_positively_sloped_segments(status_t*status, xrow_t*xrow, int3 double d1 = LINE_EQ(box.right1, seg); double d2 = LINE_EQ(box.right2, seg); if(d1>=0 || d2>=0) { -#ifdef DEBUG - dict_put(status->segs_with_point, seg, 0); -#endif - insert_point_into_segment(status, seg, box.right2); + mark_point_in_segment(status, seg, box.right2); } else { break; } } - seg = seg->right; + seg = actlist_right(status->actlist, seg); } } } @@ -457,11 +476,11 @@ void add_points_to_positively_sloped_segments(status_t*status, xrow_t*xrow, int3 | I | /I / | /+ |/ + / */ -void add_points_to_negatively_sloped_segments(status_t*status, xrow_t*xrow, int32_t y) +static void mark_points_in_negatively_sloped_segments(status_t*status, int32_t y) { int t; - for(t=xrow->num-1;t>=0;t--) { - box_t box = box_new(xrow->x[t], y); + for(t=status->xrow->num-1;t>=0;t--) { + box_t box = box_new(status->xrow->x[t], y); segment_t*seg = actlist_find(status->actlist, box.right2, box.right2); while(seg) { if(seg->a.y == y) { @@ -472,22 +491,75 @@ void add_points_to_negatively_sloped_segments(status_t*status, xrow_t*xrow, int3 double d1 = LINE_EQ(box.left1, seg); double d2 = LINE_EQ(box.left2, seg); if(d1<0 || d2<0) { -#ifdef DEBUG - dict_put(status->segs_with_point, seg, 0); -#endif - insert_point_into_segment(status, seg, box.right2); + mark_point_in_segment(status, seg, box.right2); } else { break; } } - seg = seg->left; + seg = actlist_left(status->actlist, seg); } } } +static void add_points(status_t*status) +{ + /* TODO: we could use some clever second linked list structure so that we + only need to process points which we know we marked */ + int t; + segment_t*s = actlist_leftmost(status->actlist); + while(s) { + if(s->new_point.y == status->y) { + insert_point_into_segment(status, s, s->new_point); + s->pos = s->new_pos; + } + s = actlist_right(status->actlist, s); + } +} + +void intersect_with_horizontal(status_t*status, segment_t*h) +{ + segment_t* left = actlist_find(status->actlist, h->a, h->a); + segment_t* right = actlist_find(status->actlist, h->b, h->b); + + segment_t* s = right; + + while(s!=left) { + assert(s); + /* + x1 + ((x2-x1)*(y-y1)) / dy = + (x1*(y2-y) + x2*(y-y1)) / dy + */ + point_t p; + p.y = status->y; + p.x = XPOS(s, p.y); +#ifdef DEBUG + fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr, + s->a.x, s->a.y, + s->b.x, s->b.y, + p.x, p.y + ); +#endif + assert(p.x >= h->a.x); + assert(p.x <= h->b.x); + assert(s->delta.x > 0 && p.x >= s->a.x || s->delta.x <= 0 && p.x <= s->a.x); + assert(s->delta.x > 0 && p.x <= s->b.x || s->delta.x <= 0 && p.x >= s->b.x); + xrow_add(status->xrow, p.x); + + s = actlist_left(status->actlist, s); + } + xrow_add(status->xrow, h->a.x); +} + void event_apply(status_t*status, event_t*e) { switch(e->type) { + case EVENT_HORIZONTAL: { +#ifdef DEBUG + event_dump(e); +#endif + intersect_with_horizontal(status, e->s1); + break; + } case EVENT_END: { //delete segment from list segment_t*s = e->s1; @@ -577,7 +649,7 @@ edge_t* gfxpoly_process(edge_t*poly) gfxpoly_dump(poly); #endif - xrow_t*xrow = xrow_new(); + status.xrow = xrow_new(); event_t*e = heap_chopmax(queue); while(e) { @@ -588,17 +660,20 @@ edge_t* gfxpoly_process(edge_t*poly) fprintf(stderr, "----------------------------------- %d\n", status.y); actlist_verify_and_dump(status.actlist, status.y-1); #endif - xrow_reset(xrow); + xrow_reset(status.xrow); do { - xrow_add(xrow, e->p.x); + if(e->type != EVENT_HORIZONTAL) { + xrow_add(status.xrow, e->p.x); + } event_apply(&status, e); free(e); e = heap_chopmax(queue); } while(e && status.y == e->p.y); - xrow_sort(xrow); - add_points_to_positively_sloped_segments(&status, xrow, status.y); - add_points_to_negatively_sloped_segments(&status, xrow, status.y); + xrow_sort(status.xrow); + mark_points_in_positively_sloped_segments(&status, status.y); + mark_points_in_negatively_sloped_segments(&status, status.y); + add_points(&status); #ifdef DEBUG check_status(&status); dict_destroy(status.intersecting_segs); @@ -610,7 +685,7 @@ edge_t* gfxpoly_process(edge_t*poly) #endif actlist_destroy(status.actlist); heap_destroy(queue); - xrow_destroy(xrow); + xrow_destroy(status.xrow); return status.output; } diff --git a/lib/gfxpoly/poly.h b/lib/gfxpoly/poly.h index 972d471..03f8d47 100644 --- a/lib/gfxpoly/poly.h +++ b/lib/gfxpoly/poly.h @@ -4,8 +4,8 @@ #include #include "../q.h" -typedef enum {DIR_UP, DIR_DOWN} segment_dir_t; -typedef enum {EVENT_CROSS, EVENT_END, EVENT_START} eventtype_t; +typedef enum {DIR_UP, DIR_DOWN, DIR_HORIZONTAL} segment_dir_t; +typedef enum {EVENT_CROSS, EVENT_END, EVENT_HORIZONTAL, EVENT_START} eventtype_t; typedef enum {SLOPE_POSITIVE, SLOPE_NEGATIVE} slope_t; typedef struct _point { @@ -30,11 +30,14 @@ typedef struct _segment { struct _segment*right; int tmp; point_t pos; + point_t new_point; + point_t new_pos; dict_t scheduled_crossings; } segment_t; #define LINE_EQ(p,s) ((double)(s)->delta.y*(p).x - (double)(s)->delta.x*(p).y - (s)->k) +#define XPOS(s,ypos) ((s)->a.x + ceil(((s)->delta.x * (double)((ypos) - (s)->a.y)) / (s)->delta.y)) typedef edge_t gfxpoly_t; gfxpoly_t* gfxpoly_new(); diff --git a/lib/gfxpoly/test.c b/lib/gfxpoly/test.c index e8c140c..766b1a7 100644 --- a/lib/gfxpoly/test.c +++ b/lib/gfxpoly/test.c @@ -54,21 +54,19 @@ int test1() gfxpoly_process(poly); } -int test2() +int test_square(int width, int height, int num) { -#define N 50 -#define RANGE 150 int t; - gfxline_t* line = malloc(sizeof(gfxline_t)*N); - for(t=0;ta.x*20, e->a.y*20); swf_ShapeSetLine(tag, s, e->b.x*20 - e->a.x*20, e->b.y*20 - e->a.y*20); e = e->next; } +#else + swf_ShapeSetAll(tag,s,0,0,ls,0,0); + edge_t*e = poly2; + while(e) { + swf_ShapeSetMove(tag, s, e->a.x*20, e->a.y*20); + swf_ShapeSetLine(tag, s, e->b.x*20 - e->a.x*20, e->b.y*20 - e->a.y*20); + + swf_ShapeSetCircle(tag, s, e->a.x*20, e->a.y*20, 5*20, 5*20); + swf_ShapeSetCircle(tag, s, e->b.x*20, e->b.y*20, 5*20, 5*20); + e = e->next; + } +#endif + swf_ShapeSetEnd(tag); swf_ShapeFree(s); @@ -166,5 +192,5 @@ void test3() int main() { - test3(); + test2(); } diff --git a/lib/gfxpoly/xrow.c b/lib/gfxpoly/xrow.c index 48fe7ad..29dad7a 100644 --- a/lib/gfxpoly/xrow.c +++ b/lib/gfxpoly/xrow.c @@ -1,5 +1,6 @@ #include #include +#include #include "../mem.h" #include "xrow.h" diff --git a/lib/gfxpoly/xrow.h b/lib/gfxpoly/xrow.h index 51300a3..8021085 100644 --- a/lib/gfxpoly/xrow.h +++ b/lib/gfxpoly/xrow.h @@ -3,6 +3,8 @@ #include +#include "poly.h" + typedef struct _xrow { int32_t*x; int num; -- 1.7.10.4