improved intersector horizontal line support

diff --git a/lib/gfxpoly/active.c b/lib/gfxpoly/active.c
index 56c7b90..51e0796 100644 (file)
--- 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 (file)
--- 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 (file)
--- 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 (file)
--- 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 v1<v2?v1:v2;}
 
 void segment_init(segment_t*s, int x1, int y1, int x2, int y2)
 {
-    assert(y1!=y2);
     if(y1<y2) {
         s->dir = 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;t<xrow->num;t++) {
-        box_t box = box_new(xrow->x[t], y);
+    for(t=0;t<status->xrow->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 (file)
--- a/lib/gfxpoly/poly.h
+++ b/lib/gfxpoly/poly.h
@@ -4,8 +4,8 @@
 #include <stdint.h>
 #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 (file)
--- 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;t<N;t++) {
+    gfxline_t* line = malloc(sizeof(gfxline_t)*num);
+    for(t=0;t<num;t++) {
         line[t].type = t?gfx_lineTo:gfx_moveTo;
-        line[t].x = (lrand48()%RANGE)-RANGE/2;
-        line[t].y = (lrand48()%RANGE)-RANGE/2;
+        line[t].x = (lrand48()%width)-width/2;
+        line[t].y = (lrand48()%height)-height/2;
         line[t].next = &line[t+1];
     }
-    line[N-1].x = line[0].x;
-    line[N-1].y = line[0].y;
-    line[N-1].next = 0;
+    line[num-1].x = line[0].x;
+    line[num-1].y = line[0].y;
+    line[num-1].next = 0;
     
     gfxpoly_t*poly = gfxpoly_fillToPoly(line);
     gfxpoly_t*poly2 = gfxpoly_process(poly);
@@ -77,25 +75,37 @@ int test2()
     gfxpoly_destroy(poly2);
 }
 
+int test2()
+{
+    test_square(200,5, 1000);
+    test_square(5,200, 1000);
+    test_square(10,10, 200);
+    test_square(500,500, 50);
+    test_square(65536,65536,256);
+}
+
 #include "../rfxswf.h"
 void test3()
 {
 #undef N
 #undef RANGE
-#define N 250
-#define RANGE 150
+#define N 20
+#define RANGE 400
 
     int i;
-    gfxline_t* line = malloc(sizeof(gfxline_t)*N);
+    gfxline_t* line = malloc(sizeof(gfxline_t)*N*2);
     for(i=0;i<N;i++) {
         line[i].type = i?gfx_lineTo:gfx_moveTo;
         line[i].x = lrand48()%RANGE - RANGE/2;
         line[i].y = lrand48()%RANGE - RANGE/2;
         line[i].next = &line[i+1];
+        line[i+N].x = lrand48()%RANGE - RANGE/2;
+        line[i+N].y = lrand48()%RANGE - RANGE/2;
+        line[i+N].next = &line[N+i+1];
     }
-    line[N-1].x = line[0].x;
-    line[N-1].y = line[0].y;
-    line[N-1].next = 0;
+    line[N*2-1].x = line[0].x;
+    line[N*2-1].y = line[0].y;
+    line[N*2-1].next = 0;
 
     gfxmatrix_t m;
     memset(&m, 0, sizeof(m));
@@ -131,17 +141,33 @@ void test3()
         RGBA rgb;
         rgb.r = rgb.g = 0x00; rgb.b = 0xff;
         rgb.a = 255;
-        int j = swf_ShapeAddSolidFillStyle(s,&rgb);
+        int fs = swf_ShapeAddSolidFillStyle(s,&rgb);
+        int ls = swf_ShapeAddLineStyle(s,20,&rgb);
         swf_SetU16(tag,t+1);
         swf_SetRect(tag,&swf.movieSize);
         swf_SetShapeHeader(tag,s);
-        swf_ShapeSetAll(tag,s,0,0,0,j,0);
+
+#ifdef FILL
+        swf_ShapeSetAll(tag,s,0,0,0,fs,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);
             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 (file)
--- a/lib/gfxpoly/xrow.c
+++ b/lib/gfxpoly/xrow.c
@@ -1,5 +1,6 @@
 #include <stdlib.h>
 #include <stdio.h>
+#include <memory.h>
 #include "../mem.h"
 #include "xrow.h"
 

diff --git a/lib/gfxpoly/xrow.h b/lib/gfxpoly/xrow.h
index 51300a3..8021085 100644 (file)
--- a/lib/gfxpoly/xrow.h
+++ b/lib/gfxpoly/xrow.h
@@ -3,6 +3,8 @@
 
 #include <stdint.h>
 
+#include "poly.h"
+
 typedef struct _xrow {
     int32_t*x;
     int num;