minor bugfixes and speed improvements in polygon intersector
authorMatthias Kramm <kramm@matthias-kramms-macbook-pro.local>
Wed, 20 May 2009 19:50:15 +0000 (12:50 -0700)
committerMatthias Kramm <kramm@matthias-kramms-macbook-pro.local>
Wed, 20 May 2009 19:50:15 +0000 (12:50 -0700)
lib/gfxpoly/convert.c
lib/gfxpoly/poly.c
lib/gfxpoly/poly.h
lib/gfxpoly/renderpoly.c
lib/gfxpoly/renderpoly.h
lib/gfxpoly/test.c
lib/gfxpoly/wind.c

index e326333..0e458be 100644 (file)
@@ -20,6 +20,18 @@ static edge_t*edge_new(int x1, int y1, int x2, int y2)
 
 static inline void gfxpoly_add_edge(gfxpoly_t*poly, double _x1, double _y1, double _x2, double _y2)
 {
+    /* we clamp to 31 bit instead of 32 bit because we use
+       a (x1-x2) shortcut when comparing coordinates
+    */
+    if(_x1 < -0x40000000) _x1 = -0x40000000;
+    if(_x1 >  0x3fffffff) _x1 =  0x3fffffff;
+    if(_y1 < -0x40000000) _y1 = -0x40000000;
+    if(_y1 >  0x3fffffff) _y1 =  0x3fffffff;
+    if(_x2 < -0x40000000) _x2 = -0x40000000;
+    if(_x2 >  0x3fffffff) _x2 =  0x3fffffff;
+    if(_y2 < -0x40000000) _y2 = -0x40000000;
+    if(_y2 >  0x3fffffff) _y2 =  0x3fffffff;
+
     int x1 = ceil(_x1);
     int y1 = ceil(_y1);
     int x2 = ceil(_x2);
index 26218ab..7036a61 100644 (file)
@@ -4,6 +4,7 @@
 #include "../mem.h"
 #include "../types.h"
 #include "../q.h"
+#include "../MD5.h"
 #include "poly.h"
 #include "active.h"
 #include "xrow.h"
 static gfxpoly_t*current_polygon = 0;
 void gfxpoly_fail(char*expr, char*file, int line, const char*function)
 {
+    if(!current_polygon) {fprintf(stderr, "error outside polygon\n");exit(1);}
+
+    void*md5 = init_md5();
+    
+    edge_t* s = current_polygon->edges;
+    while(s) {
+       update_md5(md5, (unsigned char*)&s->a.x, sizeof(s->a.x));
+       update_md5(md5, (unsigned char*)&s->a.y, sizeof(s->a.y));
+       update_md5(md5, (unsigned char*)&s->b.x, sizeof(s->b.x));
+       update_md5(md5, (unsigned char*)&s->b.y, sizeof(s->b.y));
+       s = s->next;
+    }
+    unsigned char h[16];
+    char filename[32+4+1];
+    finish_md5(md5, h);
+    sprintf(filename, "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x.ps",
+           h[0],h[1],h[2],h[3],h[4],h[5],h[6],h[7],h[8],h[9],h[10],h[11],h[12],h[13],h[14],h[15]);
+
     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");
+    fprintf(stderr, "I'm saving a debug file \"%s\" to the current directory.\n", filename);
+
+    gfxpoly_save(current_polygon, filename);
     exit(1);
 }
 
-char point_equals(const void*o1, const void*o2)
+static char point_equals(const void*o1, const void*o2)
 {
     const point_t*p1 = o1;
     const point_t*p2 = o2;
     return p1->x == p2->x && p1->y == p2->y;
 }
-unsigned int point_hash(const void*o)
+static unsigned int point_hash(const void*o)
 {
     const point_t*p = o;
     return p->x^p->y;
 }
-void* point_dup(const void*o)
+static void* point_dup(const void*o)
 {
     const point_t*p = o;
     point_t*n = malloc(sizeof(point_t));
@@ -37,14 +57,14 @@ void* point_dup(const void*o)
     n->y = p->y;
     return n;
 }
-void point_free(void*o)
+static void point_free(void*o)
 {
     point_t*p = o;
     p->x = 0;
     p->y = 0;
     free(p);
 }
-type_t point_type = {
+static type_t point_type = {
     equals: point_equals,
     hash: point_hash,
     dup: point_dup,
@@ -52,13 +72,13 @@ type_t point_type = {
 };
 
 typedef struct _status {
-    int y;
-    int num_polygons;
+    int32_t y;
     actlist_t*actlist;
     heap_t*queue;
     edge_t*output;
     xrow_t*xrow;
     windrule_t*windrule;
+    windcontext_t*context;
     segment_t*ending_segments;
 #ifdef CHECKS
     dict_t*seen_crossings; //list of crossing we saw so far
@@ -74,16 +94,11 @@ static int compare_events_simple(const void*_a,const void*_b)
 {
     event_t* a = (event_t*)_a;
     event_t* b = (event_t*)_b;
-    if(a->p.y < b->p.y) {
-        return 1;
-    } else if(a->p.y > b->p.y) {
-        return -1;
-    } else if(a->p.x < b->p.x) {
-        return 1;
-    } else if(a->p.x > b->p.x) {
-        return -1;
-    } else
-        return 0;
+    int d = b->p.y - a->p.y;
+    if(d) return d;
+    d = b->p.x - a->p.x;
+    if(d) return d;
+    return 0;
 }
 
 static int compare_events(const void*_a,const void*_b)
@@ -92,13 +107,14 @@ static int compare_events(const void*_a,const void*_b)
     event_t* b = (event_t*)_b;
     int d = b->p.y - a->p.y;
     if(d) return d;
-    /* we need to schedule end before intersect (so that a segment about
+    /* we need to schedule end after intersect (so that a segment about
        to end has a chance to tear up a few other segs first) and start
-       events after intersect (so that start segments don't position themselves
-       between two segments about to intersect (not a problem as such, but makes
-       things slower)). Horizontal lines come last, because the only purpose
+       events after end (in order not to confuse the intersection check, which
+       assumes there's an actual y overlap between active segments)). 
+       Horizontal lines come last, because the only purpose
        they have is to create snapping coordinates for the segments (still)
-       existing in this scanline */
+       existing in this scanline.
+    */
     d = b->type - a->type;
     if(d) return d;
     d = b->p.x - a->p.x;
@@ -130,6 +146,7 @@ int gfxpoly_size(gfxpoly_t*poly)
     }
     return t;
 }
+
 char gfxpoly_check(gfxpoly_t*poly)
 {
     edge_t* s = poly->edges;
@@ -199,7 +216,7 @@ inline static event_t event_new()
     return e;
 }
 
-void event_dump(event_t*e)
+static void event_dump(event_t*e)
 {
     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);
@@ -209,6 +226,8 @@ void event_dump(event_t*e)
         fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
     } else if(e->type == EVENT_CROSS) {
         fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
+    } else if(e->type == EVENT_CORNER) {
+        fprintf(stderr, "event: segment [%d] ends, segment [%d] starts, at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
     } else {
         assert(0);
     }
@@ -217,20 +236,20 @@ void event_dump(event_t*e)
 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
 
-void segment_dump(segment_t*s)
+static void segment_dump(segment_t*s)
 {
-    fprintf(stderr, "(%d,%d)->(%d,%d) ", s->a.x, s->a.y, s->b.x, s->b.y);
+    fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
     fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k,
             (double)s->delta.x / s->delta.y);
 }
 
-void segment_init(segment_t*s, int x1, int y1, int x2, int y2, windstate_t windstate, int polygon_nr)
+static void segment_init(segment_t*s, int32_t x1, int32_t y1, int32_t x2, int32_t y2, int polygon_nr)
 {
     if(y1<y2) {
         s->dir = DIR_DOWN;
     } else if(y1>y2) {
-        int x = x1;x1=x2;x2=x;
-        int y = y1;y1=y2;y2=y;
+        int32_t x = x1;x1=x2;x2=x;
+        int32_t y = y1;y1=y2;y2=y;
         s->dir = DIR_UP;
     } else {
         /* up/down for horizontal segments is handled by "rotating"
@@ -239,8 +258,8 @@ void segment_init(segment_t*s, int x1, int y1, int x2, int y2, windstate_t winds
         s->dir = DIR_UP;
         if(x1>x2) {
             s->dir = DIR_DOWN;
-            int x = x1;x1=x2;x2=x;
-            int y = y1;y1=y2;y2=y;
+            int32_t x = x1;x1=x2;x2=x;
+            int32_t y = y1;y1=y2;y2=y;
         }
     }
     s->a.x = x1;
@@ -262,6 +281,7 @@ void segment_init(segment_t*s, int x1, int y1, int x2, int y2, windstate_t winds
     s->nr = segment_count++;
 #endif
 
+#ifdef CHECKS
     assert(LINE_EQ(s->a, s) == 0);
     assert(LINE_EQ(s->b, s) == 0);
 
@@ -277,23 +297,25 @@ void segment_init(segment_t*s, int x1, int y1, int x2, int y2, windstate_t winds
     assert(LINE_EQ(p, s) <= 0);
     p.x = max32(s->a.x, s->b.x);
     assert(LINE_EQ(p, s) >= 0);
+#endif
 
     dict_init2(&s->scheduled_crossings, &ptr_type, 0);
 }
 
-segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2, windstate_t initial, int polygon_nr)
+static segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2, int polygon_nr)
 {
     segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
-    segment_init(s, x1, y1, x2, y2, initial, polygon_nr);
+    segment_init(s, x1, y1, x2, y2, polygon_nr);
     return s;
 }
-void segment_destroy(segment_t*s)
+
+static void segment_destroy(segment_t*s)
 {
     dict_clear(&s->scheduled_crossings);
     free(s);
 }
 
-void gfxpoly_enqueue(edge_t*list, heap_t*queue, windstate_t initial, int polygon_nr)
+static void gfxpoly_enqueue(edge_t*list, heap_t*queue, int polygon_nr)
 {
     edge_t*l;
     for(l=list;l;l=l->next) {
@@ -302,7 +324,7 @@ void gfxpoly_enqueue(edge_t*list, heap_t*queue, windstate_t initial, int polygon
             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, initial, polygon_nr);
+        segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y, polygon_nr);
 #ifdef DEBUG
         if(l->tmp)
             s->nr = l->tmp;
@@ -319,7 +341,7 @@ void gfxpoly_enqueue(edge_t*list, heap_t*queue, windstate_t initial, int polygon
     }
 }
 
-void schedule_endpoint(status_t*status, segment_t*s)
+static void schedule_endpoint(status_t*status, segment_t*s)
 {
     // schedule end point of segment
     assert(s->b.y > status->y);
@@ -331,7 +353,7 @@ void schedule_endpoint(status_t*status, segment_t*s)
     heap_put(status->queue, &e);
 }
 
-void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
+static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
 {
     /* the code that's required (and the checks you can perform) before
        it can be said with 100% certainty that we indeed have a valid crossing
@@ -371,11 +393,7 @@ void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
         return; // we already know about this one
     }
 
-    double adx = s1->delta.x;
-    double ady = s1->delta.y;
-    double bdx = s2->delta.x;
-    double bdy = s2->delta.y;
-    double det = adx*bdy - ady*bdx;
+    double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
     if(!det) {
         if(s1->k == s2->k) {
             // lines are exactly on top of each other (ignored)
@@ -437,12 +455,13 @@ void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
         return;
     }
 
+    /* TODO: should we precompute these? */
     double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
     double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
 
     point_t p;
-    p.x = (int32_t)ceil((-la*bdx +lb*adx) / det);
-    p.y = (int32_t)ceil((+lb*ady -la*bdy) / det);
+    p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
+    p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
 
     assert(p.y >= status->y);
 #ifdef CHECKS
@@ -473,7 +492,7 @@ void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
     return;
 }
 
-void exchange_two(status_t*status, event_t*e)
+static void exchange_two(status_t*status, event_t*e)
 {
     //exchange two segments in list
     segment_t*s1 = e->s1;
@@ -484,15 +503,13 @@ void exchange_two(status_t*status, event_t*e)
     if(!dict_contains(status->intersecting_segs, s2))
         dict_put(status->intersecting_segs, s2, 0);
 #endif
-    segment_t*left = actlist_left(status->actlist, s2);
-    segment_t*right = actlist_right(status->actlist, s1);
-    assert(left == s1);
-    assert(right == s2);
+    assert(s2->left == s1);
+    assert(s1->right == s2);
     actlist_swap(status->actlist, s1, s2);
-    assert(actlist_right(status->actlist, s2) == s1);
-    assert(actlist_left(status->actlist, s1) == s2);
-    left = actlist_left(status->actlist, s2);
-    right = actlist_right(status->actlist, s1);
+    assert(s2->right  == s1);
+    assert(s1->left == s2);
+    segment_t*left = s2->left;
+    segment_t*right = s1->right;
     if(left)
         schedule_crossing(status, left, s2);
     if(right)
@@ -502,7 +519,7 @@ void exchange_two(status_t*status, event_t*e)
 typedef struct _box {
     point_t left1, left2, right1, right2;
 } box_t;
-static inline box_t box_new(int x, int y)
+static inline box_t box_new(int32_t x, int32_t y)
 {
     box_t box;
     box.right1.x = box.right2.x = x;
@@ -555,20 +572,15 @@ typedef struct _segrange {
     segment_t*segmax;
 } segrange_t;
 
-void segrange_adjust_endpoints(segrange_t*range, int y)
+static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
 {
 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
-#ifdef CHECK
-    /* this would mean that the segment left/right of the minimum/maximum
-       intersects the current segment exactly at the scanline, but somehow
-       wasn't found to be passing through the same snapping box */
-    assert(!min || !min->left || !XPOS_EQ(min, min->left, y));
-    assert(!max || !max->right || !XPOS_EQ(max, max->right, y));
-#endif
-
-    /* this doesn't actually ever happen anymore (see checks above) */
     segment_t*min = range->segmin;
     segment_t*max = range->segmax;
+
+    /* we need this because if two segments intersect exactly on
+       the scanline, segrange_test_segment_{min,max} can't tell which
+       one is smaller/larger */
     if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
         min = min->left;
     }
@@ -578,7 +590,7 @@ void segrange_adjust_endpoints(segrange_t*range, int y)
     range->segmin = min;
     range->segmax = max;
 }
-void segrange_test_segment_min(segrange_t*range, segment_t*seg, int y)
+static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
 {
     if(!seg) return;
     /* we need to calculate the xpos anew (and can't use start coordinate or
@@ -592,7 +604,7 @@ void segrange_test_segment_min(segrange_t*range, segment_t*seg, int y)
         range->xmin = x;
     }
 }
-void segrange_test_segment_max(segrange_t*range, segment_t*seg, int y)
+static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
 {
     if(!seg) return;
     double x = XPOS(seg, y);
@@ -699,7 +711,7 @@ static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y,
    (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)
+static void add_points_to_ending_segments(status_t*status, int32_t y)
 {
     segment_t*seg = status->ending_segments;
     while(seg) {
@@ -746,6 +758,9 @@ void add_points_to_ending_segments(status_t*status, int32_t y)
 
 static void recalculate_windings(status_t*status, segrange_t*range)
 {
+#ifdef DEBUG
+    fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
+#endif
     segrange_adjust_endpoints(range, status->y);
 
     segment_t*s = range->segmin;
@@ -785,34 +800,34 @@ static void recalculate_windings(status_t*status, segrange_t*range)
     if(end)
         end = actlist_right(status->actlist, end);
     while(s!=end) {
-#ifndef CHECK
+#ifndef CHECKS
         if(s->changed)
 #endif
         {
             segment_t* left = actlist_left(status->actlist, s);
-            windstate_t wind = left?left->wind:status->windrule->start(status->num_polygons);
-            s->wind = status->windrule->add(wind, s->fs, s->dir, s->polygon_nr);
+            windstate_t wind = left?left->wind:status->windrule->start(status->context);
+            s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
             fillstyle_t*fs_old = s->fs_out;
             s->fs_out = status->windrule->diff(&wind, &s->wind);
 
             assert(!(!s->changed && fs_old!=s->fs_out));
             s->changed = 0;
 
+#ifdef CHECKS
             s->fs_out_ok = 1;
+#endif
 #ifdef DEBUG
-            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");
+            fprintf(stderr, "[%d] %s/%d/%s/%s %s\n", s->nr, s->dir==DIR_UP?"up":"down", s->wind.wind_nr, s->wind.is_filled?"fill":"nofill", s->fs_out?"draw":"omit",
+                   fs_old!=s->fs_out?"CHANGED":"");
 #endif
         }
         s = s->right;
     }
-#ifdef DEBUG
-    fprintf(stderr, "\n");
-#endif
 }
 
 /* we need to handle horizontal lines in order to add points to segments
    we otherwise would miss during the windrule re-evaluation */
-void intersect_with_horizontal(status_t*status, segment_t*h)
+static 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);
@@ -832,7 +847,7 @@ void intersect_with_horizontal(status_t*status, segment_t*h)
 
     while(s!=right) {
         assert(s);
-        int x = XPOS_INT(s, status->y);
+        int32_t x = XPOS_INT(s, status->y);
 #ifdef DEBUG
         fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
                 s->a.x, s->a.y,
@@ -850,7 +865,7 @@ void intersect_with_horizontal(status_t*status, segment_t*h)
     }
 }
 
-void event_apply(status_t*status, event_t*e)
+static void event_apply(status_t*status, event_t*e)
 {
     switch(e->type) {
         case EVENT_HORIZONTAL: {
@@ -909,6 +924,9 @@ void event_apply(status_t*status, event_t*e)
                actlist_left(status->actlist, e->s2) == e->s1) {
                 exchange_two(status, e);
             } else {
+#ifdef DEBUG
+               fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
+#endif
                 /* ignore this crossing for now (there are some line segments in between).
                    it'll get rescheduled as soon as the "obstacles" are gone */
                 char del1 = dict_del(&e->s1->scheduled_crossings, e->s2);
@@ -927,7 +945,7 @@ void event_apply(status_t*status, event_t*e)
 }
 
 #ifdef CHECKS
-void check_status(status_t*status)
+static void check_status(status_t*status)
 {
     DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
         if((s->pos.x != s->b.x ||
@@ -943,7 +961,7 @@ void check_status(status_t*status)
 }
 #endif
 
-static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule)
+static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
 {
     /*
           |..|        |...........|                 |           |
@@ -957,14 +975,14 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule)
     fprintf(stderr, "========================================================================\n");
 #endif
     heap_t* queue = heap_new(sizeof(event_t), compare_events_simple);
-    gfxpoly_enqueue(poly->edges, queue, windrule->start(1), 0);
+    gfxpoly_enqueue(poly->edges, queue, 0);
 
     actlist_t* actlist = actlist_new();
 
     event_t*e = heap_chopmax(queue);
     while(e) {
-        int y = e->p.y;
-        int x = 0;
+        int32_t y = e->p.y;
+        int32_t x = 0;
         char fill = 0;
 #ifdef DEBUG
         fprintf(stderr, "----------------------------------- %d\n", y);
@@ -978,12 +996,26 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule)
 #ifdef DEBUG
                 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
 #endif
+               assert(x<e->p.x);
                 edge_t*l= malloc(sizeof(edge_t));
                 l->a.y = l->b.y = y;
+               /* TODO: strictly speaking we need to draw from low x to high x so that left/right fillstyles add up
+                        (because the horizontal line's fill style controls the area *below* the line)
+                */
                 l->a.x = x;
                 l->b.x = e->p.x;
                 l->next = poly->edges;
                 poly->edges = l;
+#ifdef CHECKS
+               /* the output should always be intersection free polygons, so check this horizontal
+                  line isn't hacking through any segments in the active list */
+               segment_t* start = actlist_find(actlist, l->a, l->a);
+               segment_t* s = actlist_find(actlist, l->b, l->b);
+               while(s!=start) {
+                   assert(s->a.y == y || s->b.y == y);
+                   s = s->left;
+               }
+#endif
             }
             segment_t*left = 0;
             segment_t*s = e->s1;
@@ -1001,8 +1033,8 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule)
                     heap_put(queue, &e);
                     left = actlist_left(actlist, s);
 
-                    before = left?left->wind:windrule->start(1);
-                    after = s->wind = windrule->add(before, s->fs, s->dir, s->polygon_nr);
+                    before = left?left->wind:windrule->start(context);
+                    after = s->wind = windrule->add(context, before, s->fs, s->dir, s->polygon_nr);
                     break;
                 }
                 case EVENT_END: {
@@ -1010,7 +1042,7 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule)
                     actlist_delete(actlist, s);
 
                     before = s->wind;
-                    after = left?left->wind:windrule->start(1);
+                    after = left?left->wind:windrule->start(context);
                     break;
                 }
                 default: assert(0);
@@ -1040,18 +1072,18 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule)
     heap_destroy(queue);
 }
 
-gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule)
+gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
 {
     current_polygon = poly;
     heap_t* queue = heap_new(sizeof(event_t), compare_events);
 
-    gfxpoly_enqueue(poly->edges, queue, windrule->start(1), /*polygon nr*/0);
+    gfxpoly_enqueue(poly->edges, queue, /*polygon nr*/0);
 
     status_t status;
     memset(&status, 0, sizeof(status_t));
-    status.num_polygons = 1;
     status.queue = queue;
     status.windrule = windrule;
+    status.context = context;
     status.actlist = actlist_new();
 #ifdef CHECKS
     status.seen_crossings = dict_new2(&point_type);
@@ -1109,6 +1141,6 @@ gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule)
     gfxpoly_t*p = gfxpoly_new(poly->gridsize);
     p->edges = status.output;
 
-    add_horizontals(p, &windrule_evenodd); // output is always even/odd
+    add_horizontals(p, &windrule_evenodd, context); // output is always even/odd
     return p;
 }
index dfada99..2ea3ff4 100644 (file)
@@ -5,7 +5,7 @@
 #include "../q.h"
 
 //#define DEBUG
-//#define CHECKS
+#define CHECKS
 #define SPLAY
 
 typedef enum {DIR_UP, DIR_DOWN} segment_dir_t;
@@ -35,13 +35,18 @@ typedef struct _windstate
 {
     char is_filled;
     int wind_nr;
-    int num_polygons;
 } windstate_t;
 
+/* TODO: maybe we should merge windcontext and windrule */
+typedef struct _windcontext
+{
+    int num_polygons;
+} windcontext_t;
+
 typedef struct _windrule
 {
-    windstate_t (*start)(int num_polygons);
-    windstate_t (*add)(windstate_t left, fillstyle_t*edge, segment_dir_t dir, int polygon_nr);
+    windstate_t (*start)(windcontext_t* num_polygons);
+    windstate_t (*add)(windcontext_t*context, windstate_t left, fillstyle_t*edge, segment_dir_t dir, int polygon_nr);
     fillstyle_t* (*diff)(windstate_t*left, windstate_t*right);
 } windrule_t;
 
@@ -52,12 +57,14 @@ typedef struct _segment {
     point_t b;
     point_t delta;
     double k; //k = a.x*b.y-a.y*b.x = delta.y*a.x - delta.x*a.y (=0 for points on the segment)
-    int minx, maxx;
+    int32_t minx, maxx;
     
     segment_dir_t dir;
     fillstyle_t*fs;
     fillstyle_t*fs_out;
+#ifdef CHECKS
     char fs_out_ok;
+#endif
     
     int polygon_nr;
     windstate_t wind;
@@ -105,7 +112,7 @@ 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);
+gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context);
 
 typedef struct _event {
     eventtype_t type;
index 9e3c593..ca0ccc2 100644 (file)
@@ -120,7 +120,7 @@ static void fill_bitwise(unsigned char*line, int x1, int x2)
     }
 }
 
-unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, windrule_t*rule)
+unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, windrule_t*rule, windcontext_t*context)
 {
     renderbuf_t _buf, *buf=&_buf;
     buf->width = (bbox->xmax - bbox->xmin);
@@ -153,7 +153,7 @@ unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, wi
         qsort(points, num, sizeof(renderpoint_t), compare_renderpoints);
         int lastx = 0;
         
-        windstate_t fill = rule->start(1);
+        windstate_t fill = rule->start(context);
         for(n=0;n<num;n++) {
             renderpoint_t*p = &points[n];
             int x = (int)(p->x - bbox->xmin);
@@ -166,7 +166,7 @@ unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, wi
             if(fill.is_filled && lastx<x) {
                 fill_bitwise(line, lastx, x);
             }
-            fill = rule->add(fill, p->fs, p->dir, p->polygon_nr);
+            fill = rule->add(context, fill, p->fs, p->dir, p->polygon_nr);
             lastx = x;
         }
         if(fill.is_filled && lastx!=buf->width) {
index 7d0afb4..1c8d183 100644 (file)
@@ -13,7 +13,7 @@ typedef struct {
     int height;
 } intbbox_t;
 
-unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, windrule_t*rule);
+unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, windrule_t*rule, windcontext_t*context);
 
 intbbox_t intbbox_new(int x1, int y1, int x2, int y2);
 intbbox_t intbbox_from_polygon(gfxpoly_t*polygon, double zoom);
index 888e4d6..892798a 100644 (file)
@@ -116,13 +116,16 @@ gfxline_t* mkchessboard()
     return b;
 }
 
+static windcontext_t onepolygon = {1};
+
 int test0()
 {
     gfxline_t* b = mkchessboard();
 
     gfxmatrix_t m;
     memset(&m, 0, sizeof(gfxmatrix_t));
-    int t = 28;
+    int t;
+    for(t=0;t<360;t++) {
     m.m00 = cos(t*M_PI/180.0);
     m.m01 = sin(t*M_PI/180.0);
     m.m10 = -sin(t*M_PI/180.0);
@@ -132,10 +135,11 @@ int test0()
     gfxline_transform(b, &m);
 
     gfxpoly_t*poly = gfxpoly_from_gfxline(b, 0.05);
-    gfxpoly_t*poly2 = gfxpoly_process(poly, &windrule_evenodd);
+    gfxpoly_t*poly2 = gfxpoly_process(poly, &windrule_evenodd, &onepolygon);
     gfxpoly_destroy(poly2);
     gfxpoly_destroy(poly);
 }
+}
 
 int test1(int argn, char*argv[])
 {
@@ -165,7 +169,7 @@ int test1(int argn, char*argv[])
     gfxline_free(star);
 
     gfxpoly_dump(poly);
-    gfxpoly_t*poly2 = gfxpoly_process(poly, &windrule_evenodd);
+    gfxpoly_t*poly2 = gfxpoly_process(poly, &windrule_evenodd, &onepolygon);
     gfxpoly_destroy(poly2);
     gfxpoly_destroy(poly);
 }
@@ -188,11 +192,11 @@ int test_square(int width, int height, int num, double gridsize, char bitmaptest
     gfxline_free(line);
 
     windrule_t*rule = &windrule_circular;
-    gfxpoly_t*poly2 = gfxpoly_process(poly, rule);
+    gfxpoly_t*poly2 = gfxpoly_process(poly, rule, &onepolygon);
     if(bitmaptest) {
         intbbox_t bbox = intbbox_new(0, 0, width, height);
-        unsigned char*bitmap1 = render_polygon(poly, &bbox, 1.0, rule);
-        unsigned char*bitmap2 = render_polygon(poly2, &bbox, 1.0, &windrule_evenodd);
+        unsigned char*bitmap1 = render_polygon(poly, &bbox, 1.0, rule, &onepolygon);
+        unsigned char*bitmap2 = render_polygon(poly2, &bbox, 1.0, &windrule_evenodd, &onepolygon);
         if(!compare_bitmaps(&bbox, bitmap1, bitmap2)) {
             save_two_bitmaps(&bbox, bitmap1, bitmap2, "error.png");
             assert(!"bitmaps don't match");
@@ -226,7 +230,8 @@ void test3(int argn, char*argv[])
     //gfxline_t*line = mkrandomshape(RANGE, N);
     //windrule_t*rule = &windrule_circular;
     gfxline_t*line = mkchessboard();
-    windrule_t*rule = &windrule_evenodd;
+    //windrule_t*rule = &windrule_evenodd;
+    windrule_t*rule = &windrule_circular;
 
     gfxmatrix_t m;
     memset(&m, 0, sizeof(m));
@@ -255,7 +260,7 @@ void test3(int argn, char*argv[])
         gfxline_transform(l, &m);
         
         gfxpoly_t*poly = gfxpoly_from_gfxline(l, 0.05);
-        gfxpoly_t*poly2 = gfxpoly_process(poly, rule);
+        gfxpoly_t*poly2 = gfxpoly_process(poly, rule, &onepolygon);
 
         tag = swf_InsertTag(tag, ST_DEFINESHAPE);
         SHAPE* s;
@@ -319,6 +324,20 @@ void test3(int argn, char*argv[])
     swf_SaveSWF(&swf, "test.swf");
 }
 
+void rotate90(gfxpoly_t*poly)
+{
+    edge_t*e = poly->edges;
+    while(e) {
+       point_t a = e->a;
+       point_t b = e->b;
+       e->a.x = a.y;
+       e->a.y = a.x;
+       e->b.x = b.y;
+       e->b.y = b.x;
+       e = e->next;
+    }
+}
+
 #include <dirent.h>
 void test4(int argn, char*argv[])
 {
@@ -347,26 +366,35 @@ void test4(int argn, char*argv[])
             free(filename);
 
         double zoom = 1.0;
-        intbbox_t bbox = intbbox_from_polygon(poly, zoom);
 
         if(!gfxpoly_check(poly)) {
             printf("bad polygon\n");
             continue;
         }
 
-        gfxpoly_t*poly2 = gfxpoly_process(poly, rule);
-        unsigned char*bitmap1 = render_polygon(poly, &bbox, zoom, rule);
-        unsigned char*bitmap2 = render_polygon(poly2, &bbox, zoom, &windrule_evenodd);
-        if(!bitmap_ok(&bbox, bitmap1) || !bitmap_ok(&bbox, bitmap2)) {
-            save_two_bitmaps(&bbox, bitmap1, bitmap2, "error.png");
-            assert(!"error in bitmaps");
-        }
-        if(!compare_bitmaps(&bbox, bitmap1, bitmap2)) {
-            save_two_bitmaps(&bbox, bitmap1, bitmap2, "error.png");
-            assert(!"bitmaps don't match");
-        }
-        free(bitmap1);
-        free(bitmap2);
+        gfxpoly_t*poly2 = gfxpoly_process(poly, rule, &onepolygon);
+
+       int pass;
+       for(pass=0;pass<2;pass++) {
+           intbbox_t bbox = intbbox_from_polygon(poly, zoom);
+           unsigned char*bitmap1 = render_polygon(poly, &bbox, zoom, rule, &onepolygon);
+           unsigned char*bitmap2 = render_polygon(poly2, &bbox, zoom, &windrule_evenodd, &onepolygon);
+           if(!bitmap_ok(&bbox, bitmap1) || !bitmap_ok(&bbox, bitmap2)) {
+               save_two_bitmaps(&bbox, bitmap1, bitmap2, "error.png");
+               assert(!"error in bitmaps");
+           }
+           if(!compare_bitmaps(&bbox, bitmap1, bitmap2)) {
+               save_two_bitmaps(&bbox, bitmap1, bitmap2, "error.png");
+               assert(!"bitmaps don't match");
+           }
+           free(bitmap1);
+           free(bitmap2);
+           
+           // second pass renders the 90° rotated version
+           rotate90(poly);
+           rotate90(poly2);
+       }
+
         gfxpoly_destroy(poly);
         gfxpoly_destroy(poly2);
         if(argn==2) 
@@ -381,7 +409,12 @@ void test4(int argn, char*argv[])
 void extract_polygons_fill(gfxdevice_t*dev, gfxline_t*line, gfxcolor_t*color) 
 {
     gfxpoly_t*poly = gfxpoly_from_gfxline(line, 0.05);
-    printf("%d segments\n", gfxpoly_size(poly));
+    if(gfxpoly_size(poly)>100000) {
+       printf("%d segments (skipping)\n", gfxpoly_size(poly));
+       return;
+    } else {
+       printf("%d segments\n", gfxpoly_size(poly));
+    }
 
     if(!gfxpoly_check(poly)) {
         gfxpoly_destroy(poly);
@@ -393,13 +426,13 @@ void extract_polygons_fill(gfxdevice_t*dev, gfxline_t*line, gfxcolor_t*color)
         
     double zoom = 1.0;
     intbbox_t bbox = intbbox_from_polygon(poly, zoom);
-    unsigned char*bitmap1 = render_polygon(poly, &bbox, zoom, rule);
+    unsigned char*bitmap1 = render_polygon(poly, &bbox, zoom, rule, &onepolygon);
     if(!bitmap_ok(&bbox, bitmap1)) {
         printf("bad polygon or error in renderer\n");
         return;
     }
-    gfxpoly_t*poly2 = gfxpoly_process(poly, rule);
-    unsigned char*bitmap2 = render_polygon(poly2, &bbox, zoom, &windrule_evenodd);
+    gfxpoly_t*poly2 = gfxpoly_process(poly, rule, &onepolygon);
+    unsigned char*bitmap2 = render_polygon(poly2, &bbox, zoom, &windrule_evenodd, &onepolygon);
     if(!bitmap_ok(&bbox, bitmap2)) {
         save_two_bitmaps(&bbox, bitmap1, bitmap2, "error.png");
         assert(!"error in bitmap");
@@ -503,5 +536,5 @@ void test5(int argn, char*argv[])
 
 int main(int argn, char*argv[])
 {
-    test5(argn, argv);
+    test3(argn, argv);
 }
index 9c2fc95..c630f0f 100644 (file)
@@ -5,18 +5,15 @@ fillstyle_t fillstyle_default;
 windstate_t windstate_nonfilled = {
     is_filled: 0,
     wind_nr: 0,
-
-    /* TODO: move num_polygons into windstate_t.internal */
-    num_polygons: 1,
 };
 
 // -------------------- even/odd ----------------------
 
-windstate_t evenodd_start(int num_polygons)
+windstate_t evenodd_start(windcontext_t*context)
 {
     return windstate_nonfilled;
 }
-windstate_t evenodd_add(windstate_t left, fillstyle_t*edge, segment_dir_t dir, int master)
+windstate_t evenodd_add(windcontext_t*context, windstate_t left, fillstyle_t*edge, segment_dir_t dir, int master)
 {
     left.is_filled ^= 1;
     return left;
@@ -37,12 +34,12 @@ windrule_t windrule_evenodd = {
 
 // -------------------- circular ----------------------
 
-windstate_t circular_start(int num_polygons)
+windstate_t circular_start(windcontext_t*context)
 {
     return windstate_nonfilled;
 }
 
-windstate_t circular_add(windstate_t left, fillstyle_t*edge, segment_dir_t dir, int master)
+windstate_t circular_add(windcontext_t*context, windstate_t left, fillstyle_t*edge, segment_dir_t dir, int master)
 {
     /* which one is + and which one - doesn't actually make any difference */
     if(dir == DIR_DOWN)
@@ -70,19 +67,18 @@ windrule_t windrule_circular = {
 
 // -------------------- intersect ----------------------
 
-windstate_t intersect_start(int num_polygons)
+windstate_t intersect_start(windcontext_t*context)
 {
     windstate_t w;
-    w.num_polygons = num_polygons;
     return w;
 }
 
-windstate_t intersect_add(windstate_t left, fillstyle_t*edge, segment_dir_t dir, int master)
+windstate_t intersect_add(windcontext_t*context, windstate_t left, fillstyle_t*edge, segment_dir_t dir, int master)
 {
-    assert(master < left.num_polygons);
+    assert(master < context->num_polygons);
 
     left.wind_nr ^= 1<<master;
-    if(left.wind_nr == (1<<left.num_polygons)-1)
+    if(left.wind_nr == (1<<context->num_polygons)-1)
         left.is_filled = 1;
     return left;
 }
@@ -103,12 +99,12 @@ windrule_t windrule_intersect = {
 
 // -------------------- union ----------------------
 
-windstate_t union_start(int num_polygons)
+windstate_t union_start(windcontext_t*context)
 {
     return windstate_nonfilled;
 }
 
-windstate_t union_add(windstate_t left, fillstyle_t*edge, segment_dir_t dir, int master)
+windstate_t union_add(windcontext_t*context, windstate_t left, fillstyle_t*edge, segment_dir_t dir, int master)
 {
     assert(master<sizeof(left.wind_nr)*8); //up to 32/64 polygons max
     left.wind_nr ^= 1<<master;