From de3641737991ed13571eb947068472cf73001032 Mon Sep 17 00:00:00 2001 From: Matthias Kramm Date: Sun, 3 May 2009 02:58:49 +0200 Subject: [PATCH] more bugfixes in new polygon intersector --- lib/gfxpoly/active.c | 1 - lib/gfxpoly/convert.c | 1 - lib/gfxpoly/poly.c | 139 +++++++++++++++++++++++++++++++++++++++++-------- lib/gfxpoly/poly.h | 16 ++++++ lib/gfxpoly/test.c | 18 +++---- lib/gfxpoly/wind.c | 1 - 6 files changed, 142 insertions(+), 34 deletions(-) diff --git a/lib/gfxpoly/active.c b/lib/gfxpoly/active.c index b0ef07c..02638f5 100644 --- a/lib/gfxpoly/active.c +++ b/lib/gfxpoly/active.c @@ -1,4 +1,3 @@ -#include #include "../q.h" #include "active.h" diff --git a/lib/gfxpoly/convert.c b/lib/gfxpoly/convert.c index f404dfc..f293d16 100644 --- a/lib/gfxpoly/convert.c +++ b/lib/gfxpoly/convert.c @@ -1,6 +1,5 @@ #include #include -#include #include #include "../gfxdevice.h" #include "../mem.h" diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c index bdbddf3..b143328 100644 --- a/lib/gfxpoly/poly.c +++ b/lib/gfxpoly/poly.c @@ -1,5 +1,4 @@ #include -#include #include #include #include "../mem.h" @@ -10,15 +9,14 @@ #include "xrow.h" #include "wind.h" -#define DEBUG -#define CHECKS - -#ifndef CHECKS -#ifdef assert -#undef assert -#endif -#define assert(x) -#endif +static gfxpoly_t*current_polygon = 0; +void gfxpoly_fail(char*expr, char*file, int line, const char*function) +{ + fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function); + fprintf(stderr, "I'm saving a debug file \"poly.ps\" to the current directory.\n"); + gfxpoly_save(current_polygon, "poly.ps"); + exit(1); +} char point_equals(const void*o1, const void*o2) { @@ -61,6 +59,7 @@ typedef struct _status { edge_t*output; xrow_t*xrow; windrule_t*windrule; + segment_t*ending_segments; #ifdef CHECKS dict_t*seen_crossings; //list of crossing we saw so far dict_t*intersecting_segs; //list of segments intersecting in this scanline @@ -155,9 +154,11 @@ char gfxpoly_check(gfxpoly_t*poly) int count = (ptroff_t)c; if(count&1) { fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count); + dict_destroy(d); return 0; } } + dict_destroy(d); return 1; } @@ -171,6 +172,22 @@ void gfxpoly_dump(gfxpoly_t*poly) } } +gfxpoly_t* gfxpoly_save(gfxpoly_t*poly, const char*filename) +{ + FILE*fi = fopen(filename, "wb"); + fprintf(fi, "%% begin\n"); + edge_t* s = poly->edges; + while(s) { + fprintf(fi, "%g setgray\n", s->b.y < s->a.y ? 0.7 : 0); + fprintf(fi, "%d %d moveto\n", s->a.x, s->a.y); + fprintf(fi, "%d %d lineto\n", s->b.x, s->b.y); + fprintf(fi, "stroke\n"); + s = s->next; + } + fprintf(fi, "showpage\n"); + fclose(fi); +} + inline static event_t event_new() { event_t e; @@ -604,22 +621,27 @@ static void add_points_to_positively_sloped_segments(status_t*status, int32_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); + seg = actlist_right(status->actlist, seg); while(seg) { if(seg->a.y == y) { // this segment started in this scanline, ignore it seg->changed = 1;last = seg;if(!first) {first=seg;} - } else if(seg->delta.x < 0) { + } else if(seg->delta.x <= 0) { // ignore segment w/ negative slope } else { + last = seg;if(!first) {first=seg;} double d1 = LINE_EQ(box.right1, seg); double d2 = LINE_EQ(box.right2, seg); - if(d1>=0 || d2>=0) { - seg->changed = 1;last = seg;if(!first) {first=seg;} + if(d1>0 || d2>=0) { + seg->changed = 1; insert_point_into_segment(status, seg, box.right2); } else { - break; + /* we unfortunately can't break here- the active list is sorted according + to the *bottom* of the scanline. hence pretty much everything that's still + coming might reach into our box */ + //break; } } seg = actlist_right(status->actlist, seg); @@ -639,7 +661,6 @@ static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range) { segment_t*first=0, *last = 0; - int firstx,lastx; int t; for(t=status->xrow->num-1;t>=0;t--) { box_t box = box_new(status->xrow->x[t], y); @@ -649,17 +670,17 @@ static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, if(seg->a.y == y) { // this segment started in this scanline, ignore it seg->changed = 1;last = seg;if(!first) {first=seg;} - if(!first) {first=seg; firstx = seg->a.x;} - } else if(seg->delta.x >= 0) { + } else if(seg->delta.x > 0) { // ignore segment w/ positive slope } else { + last = seg;if(!first) {first=seg;} double d1 = LINE_EQ(box.left1, seg); double d2 = LINE_EQ(box.left2, seg); if(d1<0 || d2<0) { - seg->changed = 1;last = seg;if(!first) {first=seg;} + seg->changed = 1; insert_point_into_segment(status, seg, box.right2); } else { - break; + //break; } } seg = actlist_left(status->actlist, seg); @@ -669,6 +690,64 @@ static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_test_segment_max(range, first, y); } +/* segments ending in the current scanline need xrow treatment like everything else. + (consider an intersection taking place just above a nearly horizontal segment + ending on the current scanline- the intersection would snap down *below* the + ending segment if we don't add the intersection point to the latter right away) + we need to treat ending segments seperately, however. we have to delete them from + the active list right away to make room for intersect operations (which might + still be in the current scanline- consider two 45° polygons and a vertical polygon + intersecting on an integer coordinate). but once they're no longer in the active list, + we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding + them to the active list just for point snapping would be overkill. + (One other option to consider, however, would be to create a new active list only + for ending segments) +*/ +void add_points_to_ending_segments(status_t*status, int32_t y) +{ + segment_t*seg = status->ending_segments; + while(seg) { + segment_t*next = seg->right;seg->right=0; + + assert(seg->b.y == status->y); + + if(status->xrow->num == 1) { + // shortcut + point_t p = {status->xrow->x[0], y}; + insert_point_into_segment(status, seg, p); + } else { + int t; + int start=0,end=status->xrow->num,dir=1; + if(seg->delta.x < 0) { + start = status->xrow->num-1; + end = dir = -1; + } + for(t=start;t!=end;t+=dir) { + box_t box = box_new(status->xrow->x[t], y); + double d0 = LINE_EQ(box.left1, seg); + double d1 = LINE_EQ(box.left2, seg); + double d2 = LINE_EQ(box.right1, seg); + double d3 = LINE_EQ(box.right2, seg); + if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 || + d0<=0 && d1<=0 && d2<=0 && d3<0)) { + insert_point_into_segment(status, seg, box.right2); + break; + } + } + +#ifdef CHECKS + /* we *need* to find a point to insert. the segment's own end point + is in that list, for Pete's sake. */ + assert(t!=end); +#endif + } + // now that this is done, too, we can also finally free this segment + segment_destroy(seg); + seg = next; + } + status->ending_segments = 0; +} + static void recalculate_windings(status_t*status, segrange_t*range) { segrange_adjust_endpoints(range, status->y); @@ -677,6 +756,17 @@ static void recalculate_windings(status_t*status, segrange_t*range) segment_t*end = range->segmax; segment_t*last = 0; +#ifdef DEBUG + s = actlist_leftmost(status->actlist); + while(s) { + fprintf(stderr, "[%d]%d%s ", s->nr, s->changed, + s == range->segmin?"S":( + s == range->segmax?"E":"")); + s = s->right; + } + fprintf(stderr, "\n"); + s = range->segmin; +#endif #ifdef CHECKS /* test sanity: check that we don't have changed segments outside of the given range */ @@ -782,13 +872,14 @@ void event_apply(status_t*status, event_t*e) assert(!dict_contains(status->intersecting_segs, s)); assert(!dict_contains(status->segs_with_point, s)); #endif - insert_point_into_segment(status, s, s->b); segment_t*left = actlist_left(status->actlist, s); segment_t*right = actlist_right(status->actlist, s); actlist_delete(status->actlist, s); if(left && right) schedule_crossing(status, left, right); - segment_destroy(s);e->s1=0; + + s->left = 0; s->right = status->ending_segments; + status->ending_segments = s; break; } case EVENT_START: { @@ -949,6 +1040,7 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule) gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule) { + current_polygon = poly; heap_t* queue = heap_new(sizeof(event_t), compare_events); gfxpoly_enqueue(poly->edges, queue, windrule->start(1), /*polygon nr*/0); @@ -991,8 +1083,13 @@ gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule) xrow_sort(status.xrow); segrange_t range; memset(&range, 0, sizeof(range)); +#ifdef DEBUG + actlist_dump(status.actlist, status.y); +#endif add_points_to_positively_sloped_segments(&status, status.y, &range); add_points_to_negatively_sloped_segments(&status, status.y, &range); + add_points_to_ending_segments(&status, status.y); + recalculate_windings(&status, &range); #ifdef CHECKS check_status(&status); diff --git a/lib/gfxpoly/poly.h b/lib/gfxpoly/poly.h index 2a76a4c..6e4c7e4 100644 --- a/lib/gfxpoly/poly.h +++ b/lib/gfxpoly/poly.h @@ -4,6 +4,9 @@ #include #include "../q.h" +//#define DEBUG +//#define CHECKS + typedef enum {DIR_UP, DIR_DOWN} segment_dir_t; typedef enum {EVENT_CROSS, EVENT_END, EVENT_CORNER, EVENT_START, EVENT_HORIZONTAL} eventtype_t; typedef enum {SLOPE_POSITIVE, SLOPE_NEGATIVE} slope_t; @@ -88,10 +91,13 @@ typedef struct _gfxpoly { edge_t*edges; } gfxpoly_t; +void gfxpoly_fail(char*expr, char*file, int line, const char*function); + gfxpoly_t* gfxpoly_new(double gridsize); char gfxpoly_check(gfxpoly_t*poly); int gfxpoly_size(gfxpoly_t*poly); void gfxpoly_dump(gfxpoly_t*poly); +gfxpoly_t* gfxpoly_save(gfxpoly_t*poly, const char*filename); gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule); typedef struct _event { @@ -101,4 +107,14 @@ typedef struct _event { segment_t*s2; } event_t; +#ifndef CHECKS +#ifdef assert +#undef assert +#endif +#define assert(x) +#else +#define assert(x) ((x)?0:gfxpoly_fail(__STRING(x), __FILE__, __LINE__, __PRETTY_FUNCTION__)) +#endif + + #endif diff --git a/lib/gfxpoly/test.c b/lib/gfxpoly/test.c index aff9208..4ab1004 100644 --- a/lib/gfxpoly/test.c +++ b/lib/gfxpoly/test.c @@ -1,6 +1,5 @@ #include #include -#include #include #include #include "../gfxtools.h" @@ -53,13 +52,13 @@ gfxline_t* mkchessboard() unsigned int r = 0; int spacing = 20; - //int num_caros = 40; - //int l = 5; - //char do_centerpiece=1; + int num_caros = 40; + int l = 5; + char do_centerpiece=1; - int num_caros = 4; - int l=1; - char do_centerpiece=0; + //int num_caros = 4; + //int l=1; + //char do_centerpiece=0; for(x=-l;x<=l;x++) for(y=-l;y<=l;y++) { @@ -251,7 +250,6 @@ void test3() m.m11 = cos(t*M_PI/180.0); m.tx = RANGE*1.41/2; m.ty = RANGE*1.41/2; - printf("%d\n", t); gfxline_t*l = gfxline_clone(line); gfxline_transform(l, &m); @@ -337,7 +335,7 @@ void test4() char* filename = allocprintf("%s/%s", dir, file->d_name); windrule_t*rule = &windrule_evenodd; - gfxpoly_t*poly = gfxpoly_from_file(filename, 0.01); + gfxpoly_t*poly = gfxpoly_from_file(filename, 1.0);//0.01); free(filename); double zoom = 1.0; @@ -487,5 +485,5 @@ void test5() int main() { - test0(); + test3(); } diff --git a/lib/gfxpoly/wind.c b/lib/gfxpoly/wind.c index fa6d724..9c2fc95 100644 --- a/lib/gfxpoly/wind.c +++ b/lib/gfxpoly/wind.c @@ -1,4 +1,3 @@ -#include #include "wind.h" fillstyle_t fillstyle_default; -- 1.7.10.4