X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=blobdiff_plain;f=lib%2Fgfxpoly%2Fpoly.c;h=72e72aaa1454ba5f9b4d333231e351cbda404b10;hp=8b7226999ca350fe579d8bc11691370225bd5622;hb=c41f4433d3e721073c60d55cd923a087761e45f7;hpb=163bdd5cab1758e4517e8365b3e40b5461d63640

diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c
index 8b72269..72e72aa 100644
--- a/lib/gfxpoly/poly.c
+++ b/lib/gfxpoly/poly.c
@@ -3,10 +3,12 @@
 #include <memory.h>
 #include <math.h>
 #include "../mem.h"
+#include "../types.h"
 #include "../q.h"
 #include "poly.h"
 #include "active.h"
 #include "xrow.h"
+#include "wind.h"
 
 //#define DEBUG
 //#undef assert
@@ -47,10 +49,12 @@ type_t point_type = {
 
 typedef struct _status {
     int y;
+    int num_polygons;
     actlist_t*actlist;
     heap_t*queue;
     edge_t*output;
     xrow_t*xrow;
+    windrule_t*windrule;
 #ifdef DEBUG
     dict_t*seen_crossings; //list of crossing we saw so far
     dict_t*intersecting_segs; //list of segments intersecting in this scanline
@@ -81,25 +85,61 @@ int compare_events(const void*_a,const void*_b)
         return 0;
 }
 
-gfxpoly_t* gfxpoly_new()
+gfxpoly_t* gfxpoly_new(double gridsize)
 {
-    return 0;
+    gfxpoly_t*p = (gfxpoly_t*)rfx_calloc(sizeof(gfxpoly_t));
+    p->gridsize = gridsize;
+    return p;
 }
 void gfxpoly_destroy(gfxpoly_t*poly)
 {
-    edge_t* s = poly;
+    edge_t* s = poly->edges;
     while(s) {
         edge_t*next  = s->next;
         free(s);
         s = next;
     }
+    free(poly);
+}
+char gfxpoly_check(gfxpoly_t*poly)
+{
+    edge_t* s = poly->edges;
+    dict_t*d = dict_new2(&point_type);
+    while(s) {
+        if(!dict_contains(d, &s->a)) {
+            dict_put(d, &s->a, (void*)(ptroff_t)1);
+        } else {
+            int count = (ptroff_t)dict_lookup(d, &s->a);
+            dict_del(d, &s->a);
+            count++;
+            dict_put(d, &s->a, (void*)(ptroff_t)count);
+        }
+        if(!dict_contains(d, &s->b)) {
+            dict_put(d, &s->b, (void*)(ptroff_t)1);
+        } else {
+            int count = (ptroff_t)dict_lookup(d, &s->b);
+            dict_del(d, &s->b);
+            count++;
+            dict_put(d, &s->b, (void*)(ptroff_t)count);
+        }
+        s = s->next;
+    }
+    DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
+        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);
+            return 0;
+        }
+    }
+    return 1;
 }
 
 void gfxpoly_dump(gfxpoly_t*poly)
 {
-    edge_t* s = (edge_t*)poly;
+    edge_t* s = poly->edges;
+    double g = poly->gridsize;
     while(s) {
-        fprintf(stderr, "(%d,%d) -> (%d,%d)\n", s->a.x, s->a.y, s->b.x, s->b.y);
+        fprintf(stderr, "(%f,%f) -> (%f,%f)\n", s->a.x*g, s->a.y*g, s->b.x*g, s->b.y*g);
         s = s->next;
     }
 }
@@ -129,7 +169,7 @@ 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_init(segment_t*s, int x1, int y1, int x2, int y2)
+void segment_init(segment_t*s, int x1, int y1, int x2, int y2, windstate_t windstate, int polygon_nr)
 {
     if(y1<y2) {
         s->dir = DIR_DOWN;
@@ -138,8 +178,12 @@ void segment_init(segment_t*s, int x1, int y1, int x2, int y2)
         int y = y1;y1=y2;y2=y;
         s->dir = DIR_UP;
     } else {
-        s->dir = DIR_HORIZONTAL;
+        /* up/down for horizontal segments is handled by "rotating"
+           them 90° anticlockwise in screen coordinates (tilt your head to 
+           the right) */
+        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;
         }
@@ -153,8 +197,7 @@ void segment_init(segment_t*s, int x1, int y1, int x2, int y2)
     s->delta.x = x2-x1;
     s->delta.y = y2-y1;
     s->pos = s->a;
-    s->tmp = -1;
-    s->new_point.y = y1-1;
+    s->polygon_nr = polygon_nr;
 #define XDEBUG
 #ifdef XDEBUG
     static int segment_count=0;
@@ -180,10 +223,10 @@ void segment_init(segment_t*s, int x1, int y1, int x2, int y2)
     dict_init2(&s->scheduled_crossings, &ptr_type, 0);
 }
 
-segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2)
+segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2, windstate_t initial, int polygon_nr)
 {
     segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
-    segment_init(s, x1, y1, x2, y2);
+    segment_init(s, x1, y1, x2, y2, initial, polygon_nr);
     return s;
 }
 void segment_destroy(segment_t*s)
@@ -192,7 +235,7 @@ void segment_destroy(segment_t*s)
     free(s);
 }
 
-void gfxpoly_enqueue(edge_t*list, heap_t*queue)
+void gfxpoly_enqueue(edge_t*list, heap_t*queue, windstate_t initial, int polygon_nr)
 {
     edge_t*l;
     for(l=list;l;l=l->next) {
@@ -201,14 +244,14 @@ void gfxpoly_enqueue(edge_t*list, heap_t*queue)
             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);
+        segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y, initial, polygon_nr);
 #ifdef DEBUG
         fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n",
                 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
                 s->dir==DIR_UP?"up":"down");
 #endif
         event_t e = event_new();
-        e.type = s->dir==DIR_HORIZONTAL?EVENT_HORIZONTAL:EVENT_START;
+        e.type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
         e.p = s->a;
         e.s1 = s;
         e.s2 = 0;
@@ -399,33 +442,36 @@ static inline box_t box_new(int x, int 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)
+static void insert_point_into_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);
-    }
-#endif
     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
-    if(s->new_point.y != p.y) {
-        s->new_point = p;
+
+    assert(s->fs_out_ok);
+    if(s->fs_out) {
+#ifdef DEBUG
+        fprintf(stderr, "[%d] receives next point (%d,%d) (drawing)\n", s->nr, p.x, p.y);
+#endif
+        // omit horizontal lines
+        if(s->pos.y != p.y) {
+            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;
+        }
+    } else {
+#ifdef DEBUG
+        fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
+#endif
     }
-    s->new_pos = p;
+    s->pos = p;
 }
 
 /* possible optimizations:
@@ -443,7 +489,7 @@ void mark_point_in_segment(status_t*status, segment_t*s, point_t p)
        I  \    I \  -------
        +   \   +  \
 */
-static void mark_points_in_positively_sloped_segments(status_t*status, int32_t y)
+static void add_points_to_positively_sloped_segments(status_t*status, int32_t y)
 {
     int t;
     for(t=0;t<status->xrow->num;t++) {
@@ -459,7 +505,7 @@ static void mark_points_in_positively_sloped_segments(status_t*status, int32_t y
                 double d1 = LINE_EQ(box.right1, seg);
                 double d2 = LINE_EQ(box.right2, seg);
                 if(d1>=0 || d2>=0) {
-                    mark_point_in_segment(status, seg, box.right2);
+                    insert_point_into_segment(status, seg, box.right2);
                 } else {
                     break;
                 }
@@ -476,7 +522,7 @@ static void mark_points_in_positively_sloped_segments(status_t*status, int32_t y
    |   I    | /I   /
    |  /+    |/ +  /
 */
-static void mark_points_in_negatively_sloped_segments(status_t*status, int32_t y)
+static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y)
 {
     int t;
     for(t=status->xrow->num-1;t>=0;t--) {
@@ -491,7 +537,7 @@ static void mark_points_in_negatively_sloped_segments(status_t*status, int32_t y
                 double d1 = LINE_EQ(box.left1, seg);
                 double d2 = LINE_EQ(box.left2, seg);
                 if(d1<0 || d2<0) {
-                    mark_point_in_segment(status, seg, box.right2);
+                    insert_point_into_segment(status, seg, box.right2);
                 } else {
                     break;
                 }
@@ -501,19 +547,28 @@ static void mark_points_in_negatively_sloped_segments(status_t*status, int32_t y
     }
 }
 
-static void add_points(status_t*status)
+static void recalculate_windings(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;
+             only need to process points we know we marked */
+    
     segment_t*s = actlist_leftmost(status->actlist);
+    segment_t*last = 0;
     while(s) {
-        if(s->new_point.y == status->y) {
-            insert_point_into_segment(status, s, s->new_point);
-            s->pos = s->new_pos;
-        }
+        windstate_t wind = last?last->wind:status->windrule->start(status->num_polygons);
+        s->wind = status->windrule->add(wind, s->fs, s->dir, s->polygon_nr);
+        s->fs_out = status->windrule->diff(&wind, &s->wind);
+        s->fs_out_ok = 1;
+#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");
+#endif
+        last = s;
         s = actlist_right(status->actlist, s);
     }
+#ifdef DEBUG
+    fprintf(stderr, "\n");
+#endif
+
 }
 
 void intersect_with_horizontal(status_t*status, segment_t*h)
@@ -592,12 +647,14 @@ void event_apply(status_t*status, event_t*e)
                 schedule_crossing(status, left, s);
             if(right)
                 schedule_crossing(status, s, right);
-
             schedule_endpoint(status, e->s1);
             break;
         }
         case EVENT_CROSS: {
-            // exchange two (or more) segments
+            // exchange two segments
+#ifdef DEBUG
+            event_dump(e);
+#endif
             if(actlist_right(status->actlist, e->s1) == e->s2 &&
                actlist_left(status->actlist, e->s2) == e->s1) {
                 exchange_two(status, e);
@@ -636,17 +693,20 @@ void check_status(status_t*status)
 }
 #endif
 
-edge_t* gfxpoly_process(edge_t*poly)
+gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule)
 {
     heap_t* queue = heap_new(sizeof(event_t), compare_events);
-    gfxpoly_enqueue(poly, queue);
+    
+    gfxpoly_enqueue(poly->edges, queue, windrule->start(1), /*polygon nr*/0);
+
     status_t status;
     memset(&status, 0, sizeof(status_t));
+    status.num_polygons = 1;
     status.queue = queue;
+    status.windrule = windrule;
     status.actlist = actlist_new();
 #ifdef DEBUG
     status.seen_crossings = dict_new2(&point_type);
-    gfxpoly_dump(poly);
 #endif
     
     status.xrow = xrow_new();
@@ -671,9 +731,9 @@ edge_t* gfxpoly_process(edge_t*poly)
         } while(e && status.y == e->p.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);
+        add_points_to_positively_sloped_segments(&status, status.y);
+        add_points_to_negatively_sloped_segments(&status, status.y);
+        recalculate_windings(&status);
 #ifdef DEBUG
         check_status(&status);
         dict_destroy(status.intersecting_segs);
@@ -687,5 +747,7 @@ edge_t* gfxpoly_process(edge_t*poly)
     heap_destroy(queue);
     xrow_destroy(status.xrow);
 
-    return status.output;
+    gfxpoly_t*p = gfxpoly_new(poly->gridsize);
+    p->edges = status.output;
+    return p;
 }