X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=blobdiff_plain;f=lib%2Fgfxpoly%2Fpoly.c;h=26218ab39fe12d0dc5052eec41d98cd1d4c679ef;hp=bdbddf323197e587fb8cdc36f167e7c58114de46;hb=ba166d59c4c6672c8cb65c881193bb104c629bf7;hpb=ae7c92fe5721f97e786a8bbe9153eadbf292460d

diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c
index bdbddf3..26218ab 100644
--- a/lib/gfxpoly/poly.c
+++ b/lib/gfxpoly/poly.c
@@ -1,5 +1,4 @@
 #include <stdlib.h>
-#include <assert.h>
 #include <memory.h>
 #include <math.h>
 #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
@@ -68,7 +67,10 @@ typedef struct _status {
 #endif
 } status_t;
 
-int compare_events_simple(const void*_a,const void*_b)
+/* compare_events_simple differs from compare_events in that it schedules
+   events from left to right regardless of type. It's only used in horizontal
+   processing, in order to get an x-wise sorting of the current scanline */
+static int compare_events_simple(const void*_a,const void*_b)
 {
     event_t* a = (event_t*)_a;
     event_t* b = (event_t*)_b;
@@ -84,7 +86,7 @@ int compare_events_simple(const void*_a,const void*_b)
         return 0;
 }
 
-int compare_events(const void*_a,const void*_b)
+static int compare_events(const void*_a,const void*_b)
 {
     event_t* a = (event_t*)_a;
     event_t* b = (event_t*)_b;
@@ -155,9 +157,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 +175,23 @@ void gfxpoly_dump(gfxpoly_t*poly)
     }
 }
 
+gfxpoly_t* gfxpoly_save(gfxpoly_t*poly, const char*filename)
+{
+    FILE*fi = fopen(filename, "wb");
+    fprintf(fi, "%% gridsize %f\n", poly->gridsize);
+    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;
@@ -199,7 +220,7 @@ static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
 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, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k, 
+    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);
 }
 
@@ -282,9 +303,9 @@ void gfxpoly_enqueue(edge_t*list, heap_t*queue, windstate_t initial, int polygon
             continue;
         }
         segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y, initial, polygon_nr);
+#ifdef DEBUG
         if(l->tmp)
             s->nr = l->tmp;
-#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");
@@ -504,13 +525,15 @@ static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
 
     if(s->fs_out) {
 #ifdef DEBUG
-        fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr, 
+        fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
                 s->pos.x, s->pos.y, p.x, p.y);
 #endif
         // omit horizontal lines
         if(s->pos.y != p.y) {
             edge_t*e = rfx_calloc(sizeof(edge_t));
+#ifdef DEBUG
             e->tmp = s->nr;
+#endif
             e->a = s->pos;
             e->b = p;
             assert(e->a.y != e->b.y);
@@ -525,9 +548,6 @@ static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
     s->pos = p;
 }
 
-/* by restricting the recalculation of line segments to a range between the lowest
-   and the highest modified segment, we only do about a 33% overprocessing of fill
-   styles. (update: that statistic might be outdated now that xmin/xmax are double) */
 typedef struct _segrange {
     double xmin;
     segment_t*segmin;
@@ -535,16 +555,9 @@ typedef struct _segrange {
     segment_t*segmax;
 } segrange_t;
 
-static inline char xpos_eq(segment_t*s1, segment_t*s2, int y)
-{
-    if(XPOS_EQ(s1, s2, y)) {
-        return 1;
-    }
-    return 0;
-}
-
 void segrange_adjust_endpoints(segrange_t*range, int 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
@@ -553,12 +566,13 @@ void segrange_adjust_endpoints(segrange_t*range, int 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;
-    if(min) while(min->left && xpos_eq(min, min->left, y)) {
+    if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
         min = min->left;
     }
-    if(max) while(max->right && xpos_eq(max, max->right, y)) {
+    if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
         max = max->right;
     }
     range->segmin = min;
@@ -604,22 +618,26 @@ static void add_points_to_positively_sloped_segments(status_t*status, int32_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);
-        seg = actlist_right(status->actlist, seg);
 
+        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,27 +657,26 @@ 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);
         segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
-        
+
         while(seg) {
             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 +686,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,18 +752,29 @@ 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 */
     s = actlist_leftmost(status->actlist);
     while(s && s!=range->segmin) {
         assert(!s->changed);
-        s = actlist_right(status->actlist, s);
+        s = s->right;
     }
     s = actlist_rightmost(status->actlist);
     while(s && s!=range->segmax) {
         assert(!s->changed);
-        s = actlist_left(status->actlist, s);
+        s = s->left;
     }
     /* in check mode, go through the whole interval so we can test
        that all polygons where the fillstyle changed also have seg->changed=1 */
@@ -700,7 +786,7 @@ static void recalculate_windings(status_t*status, segrange_t*range)
         end = actlist_right(status->actlist, end);
     while(s!=end) {
 #ifndef CHECK
-        if(s->changed) 
+        if(s->changed)
 #endif
         {
             segment_t* left = actlist_left(status->actlist, s);
@@ -717,7 +803,7 @@ static void recalculate_windings(status_t*status, segrange_t*range)
             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
         }
-        s = actlist_right(status->actlist, s);
+        s = s->right;
     }
 #ifdef DEBUG
     fprintf(stderr, "\n");
@@ -735,8 +821,13 @@ void intersect_with_horizontal(status_t*status, segment_t*h)
     xrow_add(status->xrow, h->a.x);
     point_t o = h->a;
 
-    left = actlist_right(status->actlist, left);
-    right = actlist_right(status->actlist, right);
+    if(!right) {
+        assert(!left);
+        return;
+    }
+
+    left = actlist_right(status->actlist, left); //first seg to the right of h->a
+    right = right->right; //first seg to the right of h->b
     segment_t* s = left;
 
     while(s!=right) {
@@ -755,7 +846,7 @@ void intersect_with_horizontal(status_t*status, segment_t*h)
         assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
         xrow_add(status->xrow, x);
 
-        s = actlist_right(status->actlist, s);
+        s = s->right;
     }
 }
 
@@ -782,13 +873,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: {
@@ -797,7 +889,8 @@ void event_apply(status_t*status, event_t*e)
             event_dump(e);
 #endif
             segment_t*s = e->s1;
-            actlist_insert(status->actlist, e->p, s);
+	    assert(e->p.x == s->a.x && e->p.y == s->a.y);
+            actlist_insert(status->actlist, s->a, s->b, s);
             segment_t*left = actlist_left(status->actlist, s);
             segment_t*right = actlist_right(status->actlist, s);
             if(left)
@@ -878,7 +971,6 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule)
         actlist_dump(actlist, y-1);
 #endif
 #ifdef CHECKS
-        /* FIXME: this actually fails sometimes */
         actlist_verify(actlist, y-1);
 #endif
         do {
@@ -899,7 +991,8 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule)
             windstate_t before,after;
             switch(e->type) {
                 case EVENT_START: {
-                    actlist_insert(actlist, e->p, s);
+		    assert(e->p.x == s->a.x && e->p.y == s->a.y);
+                    actlist_insert(actlist, s->a, s->b, s);
                     event_t e;
                     e.type = EVENT_END;
                     e.p = s->b;
@@ -949,6 +1042,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 +1085,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);