From: Matthias Kramm <kramm@quiss.org>
Date: Thu, 30 Apr 2009 09:15:12 +0000 (+0200)
Subject: polygon intersector improvements
X-Git-Tag: polyok~16
X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=commitdiff_plain;h=e5ec9f136f070b7e824e223c0b67e28efd8c70f0

polygon intersector improvements

more improvements to horizontal line handling, started with winding+rendering code
---

diff --git a/lib/gfxpoly/Makefile b/lib/gfxpoly/Makefile
index 036c5d1..8ee22ed 100644
--- a/lib/gfxpoly/Makefile
+++ b/lib/gfxpoly/Makefile
@@ -11,6 +11,8 @@ CC = gcc -g -pg
 testheap: ../libbase.a testheap.c
 	$(CC) testheap.c ../libbase.a -o testheap -lm -lz -ljpeg
 
+OBJS = active.o convert.o poly.o wind.o renderpoly.o xrow.o
+
 active.o: active.c active.h poly.h
 	$(CC) -c active.c -o active.o
 
@@ -20,12 +22,18 @@ convert.o: convert.c convert.h poly.h
 poly.o: poly.c poly.h active.h ../q.h
 	$(CC) -c poly.c -o poly.o
 
+wind.o: wind.c wind.h poly.h
+	$(CC) -c wind.c -o wind.o
+
+renderpoly.o: renderpoly.c wind.h poly.h
+	$(CC) -c renderpoly.c -o renderpoly.o
+
 xrow.o: xrow.c xrow.h ../q.h ../mem.h
 	$(CC) -c xrow.c -o xrow.o
 
 SWF = ../librfxswf.a
-test: ../libbase.a ../libgfx.a test.c poly.o convert.o active.o xrow.o poly.h convert.h
-	$(CC) test.c poly.o convert.o active.o xrow.o $(SWF) ../libbase.a ../libgfx.a -o test -lm -lz -ljpeg -lfreetype
+test: ../libbase.a ../libgfx.a test.c $(OBJS) poly.h convert.h
+	$(CC) test.c $(OBJS) $(SWF) ../libbase.a ../libgfx.a -o test -lm -lz -ljpeg -lfreetype
 
 clean: 
 	rm -f *.o test
diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c
index 8b72269..2303944 100644
--- a/lib/gfxpoly/poly.c
+++ b/lib/gfxpoly/poly.c
@@ -138,8 +138,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,7 +157,6 @@ 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;
 #define XDEBUG
 #ifdef XDEBUG
@@ -208,7 +211,7 @@ void gfxpoly_enqueue(edge_t*list, heap_t*queue)
                 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;
diff --git a/lib/gfxpoly/poly.h b/lib/gfxpoly/poly.h
index 03f8d47..6314935 100644
--- a/lib/gfxpoly/poly.h
+++ b/lib/gfxpoly/poly.h
@@ -4,7 +4,7 @@
 #include <stdint.h>
 #include "../q.h"
 
-typedef enum {DIR_UP, DIR_DOWN, DIR_HORIZONTAL} segment_dir_t;
+typedef enum {DIR_UP, DIR_DOWN} segment_dir_t;
 typedef enum {EVENT_CROSS, EVENT_END, EVENT_HORIZONTAL, EVENT_START} eventtype_t;
 typedef enum {SLOPE_POSITIVE, SLOPE_NEGATIVE} slope_t;
 
@@ -13,9 +13,14 @@ typedef struct _point {
     int32_t y;
 } point_t;
 
+typedef struct _fillstyle {
+    char is_filled;
+} fillstyle_t;
+
 typedef struct _edge {
     point_t a;
     point_t b;
+    fillstyle_t*style;
     struct _edge *next;
 } edge_t;
 
@@ -24,11 +29,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)
+    
     segment_dir_t dir;
+    fillstyle_t*style;
+
     int nr;
     struct _segment*left;
     struct _segment*right;
-    int tmp;
+    
     point_t pos;
     point_t new_point;
     point_t new_pos;
diff --git a/lib/gfxpoly/renderpoly.c b/lib/gfxpoly/renderpoly.c
new file mode 100644
index 0000000..de7dc0a
--- /dev/null
+++ b/lib/gfxpoly/renderpoly.c
@@ -0,0 +1,292 @@
+#include <stdlib.h>
+#include <memory.h>
+#include <math.h>
+#include "renderpoly.h"
+
+typedef struct _renderpoint
+{
+    double x;
+    segment_dir_t dir;
+    fillstyle_t*fs;
+} renderpoint_t;
+
+typedef struct _renderline
+{
+    renderpoint_t*points;
+    int size;
+    int num;
+} renderline_t;
+
+typedef struct _renderbuf
+{
+    intbbox_t bbox;
+    int width;
+    int height;
+    double zoom;
+    renderline_t*lines;
+} renderbuf_t;
+
+static inline void add_pixel(renderbuf_t*buf, double x, int y, segment_dir_t dir, fillstyle_t*fs)
+{
+    renderpoint_t p;
+    p.x = x;
+    p.dir = dir;
+    p.fs = fs;
+
+    if(x >= buf->bbox.xmax || y >= buf->bbox.ymax || y < buf->bbox.ymin) 
+        return;
+    renderline_t*l = &buf->lines[y-buf->bbox.ymin];
+
+    if(l->num == l->size) {
+	l->size += 32;
+	l->points = (renderpoint_t*)rfx_realloc(l->points, l->size * sizeof(renderpoint_t));
+    }
+    l->points[l->num] = p;
+    l->num++;
+}
+#define CUT 0.5
+#define INT(x) ((int)((x)+16)-16)
+static void add_line(renderbuf_t*buf, double x1, double y1, double x2, double y2, fillstyle_t*fs)
+{
+    x1 *= buf->zoom;
+    y1 *= buf->zoom;
+    x2 *= buf->zoom;
+    y2 *= buf->zoom;
+    double diffx, diffy;
+    double ny1, ny2, stepx;
+    segment_dir_t dir = DIR_DOWN;
+    if(y2 < y1) {
+        dir = DIR_UP;
+        double x,y;
+	x = x1;x1 = x2;x2=x;
+	y = y1;y1 = y2;y2=y;
+    }
+    diffx = x2 - x1;
+    diffy = y2 - y1;
+    ny1 = INT(y1)+CUT;
+    ny2 = INT(y2)+CUT;
+
+    if(ny1 < y1) {
+        ny1 = INT(y1) + 1.0 + CUT;
+    }
+    if(ny2 >= y2) {
+        ny2 = INT(y2) - 1.0 + CUT;
+    }
+    if(ny1 > ny2)
+        return;
+
+    stepx = diffx/diffy;
+    x1 = x1 + (ny1-y1)*stepx;
+    x2 = x2 + (ny2-y2)*stepx;
+
+    int posy=INT(ny1);
+    int endy=INT(ny2);
+    double posx=0;
+    double startx = x1;
+
+    while(posy<=endy) {
+        double xx = startx + posx;
+        add_pixel(buf, xx, posy, dir, fs);
+        posx+=stepx;
+        posy++;
+    }
+}
+
+static int compare_renderpoints(const void * _a, const void * _b)
+{
+    renderpoint_t*a = (renderpoint_t*)_a;
+    renderpoint_t*b = (renderpoint_t*)_b;
+    if(a->x < b->x) return -1;
+    if(a->x > b->x) return 1;
+    return 0;
+}
+
+static void fill_bitwise(unsigned char*line, int x1, int x2)
+{
+    int p1 = x1>>3;
+    int p2 = x2>>3;
+    int b1 = 0xff >> (x1&7);
+    int b2 = 0xff << (1+7-(x2&7));
+    if(p1==p2) {
+        line[p1] |= b1&b2;
+    } else {
+        line[p1] |= b1;
+        memset(&line[p1+1], 255, p2-(p1+1));
+        line[p2] = b2;
+    }
+}
+
+unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, windrule_t*rule)
+{
+    renderbuf_t _buf, *buf=&_buf;
+    buf->width = (bbox->xmax - bbox->xmin);
+    buf->height = (bbox->ymax - bbox->ymin);
+    buf->bbox = *bbox;
+    buf->zoom = zoom;
+    int width8 = (buf->width+7) >> 3;
+    unsigned char* image = (unsigned char*)malloc(width8*buf->height);
+    memset(image, 0, width8*buf->height);
+    
+    buf->lines = (renderline_t*)rfx_alloc(buf->height*sizeof(renderline_t));
+    int y;
+    for(y=0;y<buf->height;y++) {
+	memset(&buf->lines[y], 0, sizeof(renderline_t));
+        buf->lines[y].points = 0;
+        buf->lines[y].num = 0;
+    }
+
+    edge_t*e;
+    for(e=polygon;e;e=e->next) {
+        add_line(buf, e->a.x, e->a.y, e->b.x, e->b.y, e->style);
+    }
+
+    for(y=0;y<buf->height;y++) {
+	renderpoint_t*points = buf->lines[y].points;
+        unsigned char*line = &image[width8*y];
+	int n;
+	int num = buf->lines[y].num;
+        qsort(points, num, sizeof(renderpoint_t), compare_renderpoints);
+        int lastx = 0;
+
+        windstate_t*fill = 0;
+        for(n=0;n<num;n++) {
+            renderpoint_t*p = &points[n];
+            int x = (int)(p->x - bbox->xmin);
+            
+            if(x < lastx)
+                x = lastx;
+            if(x > buf->width) {
+                break;
+            }
+            if(fill->is_filled && x!=lastx) {
+                fill_bitwise(line, lastx, x);
+            }
+            fill = rule->add(fill, p->fs, p->dir, polygon);
+            lastx = x;
+        }
+        if(fill->is_filled && lastx!=buf->width)
+            fill_bitwise(line, lastx, buf->width);
+    }
+    
+    for(y=0;y<buf->height;y++) {
+        if(buf->lines[y].points) {
+            free(buf->lines[y].points);
+        }
+        memset(&buf->lines[y], 0, sizeof(renderline_t));
+    }
+    free(buf->lines);buf->lines=0;
+    return image;
+}
+
+#define MAX_WIDTH 8192
+#define MAX_HEIGHT 4096
+
+static inline max(double a, double b) {return a>b?a:b;}
+static inline min(double a, double b) {return a<b?a:b;}
+
+intbbox_t get_polygon_bbox(gfxpoly_t*polygon, double zoom)
+{
+    int t;
+    intbbox_t b = {0,0,0,0};
+    edge_t*e = polygon;
+
+    if(e) {
+        b.xmin = e->a.x;
+        b.ymin = e->a.y;
+        b.xmax = e->a.x;
+        b.ymax = e->a.y;
+    }
+    for(e=polygon;e;e=e->next) {
+        double x_min = min(e->a.x,e->b.x)*zoom;
+        double y_min = min(e->a.y,e->b.y)*zoom;
+        double x_max = max(e->a.x,e->b.x)*zoom;
+        double y_max = max(e->a.y,e->b.y)*zoom;
+        int x1 = floor(x_min);
+        int y1 = floor(y_min);
+        int x2 = ceil(x_max);
+        int y2 = ceil(y_max);
+        if(x1 < b.xmin) b.xmin = x1;
+        if(y1 < b.ymin) b.ymin = y1;
+        if(x2 > b.xmax) b.xmax = x2;
+        if(y2 > b.xmax) b.ymax = y2;
+    }
+    if(b.xmax > (int)(MAX_WIDTH*zoom))
+	b.xmax = (int)(MAX_WIDTH*zoom);
+    if(b.ymax > (int)(MAX_HEIGHT*zoom))
+	b.ymax = (int)(MAX_HEIGHT*zoom);
+    if(b.xmin < -(int)(MAX_WIDTH*zoom))
+	b.xmin = -(int)(MAX_WIDTH*zoom);
+    if(b.ymin < -(int)(MAX_HEIGHT*zoom))
+	b.ymin = -(int)(MAX_HEIGHT*zoom);
+    
+    if(b.xmin > b.xmax) 
+	b.xmin = b.xmax;
+    if(b.ymin > b.ymax) 
+	b.ymin = b.ymax;
+
+    b.width = b.xmax - b.xmin;
+    b.height = b.ymax - b.ymin;
+    return b;
+}
+
+#define B11100000 0xe0
+#define B01110000 0x70
+#define B00111000 0x38
+#define B00011100 0x1c
+#define B00001110 0x0e
+#define B00000111 0x07
+#define B10000000 0x80
+#define B01000000 0x40
+#define B00100000 0x20
+#define B00010000 0x10
+#define B00001000 0x08
+#define B00000100 0x04
+#define B00000010 0x02
+#define B00000001 0x01
+
+int compare_bitmaps(intbbox_t*bbox, unsigned char*data1, unsigned char*data2)
+{
+    int similar = 0;
+    int x,y;
+    int height = bbox->height;
+    int width = bbox->width;
+    int width8 = (width+7) >> 3;
+    unsigned char*l1 = &data1[width8];
+    unsigned char*l2 = &data2[width8];
+    int fail = 0;
+    for(y=1;y<height-1;y++) {
+        for(x=0;x<width8;x++) {
+            unsigned a = l1[x-width8] & l1[x] & l1[x+width8];
+            unsigned b = l2[x-width8] & l2[x] & l2[x+width8];
+
+            if((a&B11100000) && !(l2[x]&B01000000))
+                fail == 1;
+            if((a&B01110000) && !(l2[x]&B00100000))
+                fail == 1;
+            if((a&B00111000) && !(l2[x]&B00010000))
+                fail == 1;
+            if((a&B00011100) && !(l2[x]&B00001000))
+                fail == 1;
+            if((a&B00001110) && !(l2[x]&B00000100))
+                fail == 1;
+            if((a&B00000111) && !(l2[x]&B00000010))
+                fail == 1;
+
+            if((b&B11100000) && !(l1[x]&B01000000))
+                fail == 1;
+            if((b&B01110000) && !(l1[x]&B00100000))
+                fail == 1;
+            if((b&B00111000) && !(l1[x]&B00010000))
+                fail == 1;
+            if((b&B00011100) && !(l1[x]&B00001000))
+                fail == 1;
+            if((b&B00001110) && !(l1[x]&B00000100))
+                fail == 1;
+            if((b&B00000111) && !(l1[x]&B00000010))
+                fail == 1;
+        }
+        l1 += width8;
+        l2 += width8;
+    }
+    return !fail;
+}
diff --git a/lib/gfxpoly/renderpoly.h b/lib/gfxpoly/renderpoly.h
new file mode 100644
index 0000000..9172787
--- /dev/null
+++ b/lib/gfxpoly/renderpoly.h
@@ -0,0 +1,18 @@
+#ifndef __renderpoly_h__
+#define __renderpoly_h__
+
+#include "poly.h"
+#include "wind.h"
+
+typedef struct {
+    int xmin;
+    int ymin;
+    int xmax;
+    int ymax;
+    int width;
+    int height;
+} intbbox_t;
+
+unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, windrule_t*rule);
+
+#endif
diff --git a/lib/gfxpoly/wind.h b/lib/gfxpoly/wind.h
new file mode 100644
index 0000000..e057544
--- /dev/null
+++ b/lib/gfxpoly/wind.h
@@ -0,0 +1,20 @@
+#ifndef __wind_h__
+#define __wind_h__
+
+#include "poly.h"
+
+typedef struct _windstate
+{
+    char is_filled;
+} windstate_t;
+
+typedef struct _windrule
+{
+    windstate_t* (*add)(windstate_t*left, fillstyle_t*edge, segment_dir_t dir, gfxpoly_t*master);
+    fillstyle_t* (*diff)(windstate_t*left, windstate_t*right);
+} windrule_t;
+
+windrule_t* windrule_new_evenodd();
+windrule_t* windrule_new_circular();
+
+#endif