#include "gfxtools.h"
#include "gfxpoly.h"
#include "mem.h"
+#ifdef INTERNAL_LIBART
#include "art/libart.h"
#include "art/art_svp_intersect.h"
#include "art/art_svp_ops.h"
+#else
+#include <libart_lgpl/libart.h>
+#include <libart_lgpl/art_svp_intersect.h>
+#include <libart_lgpl/art_svp_ops.h>
+#endif
#include "log.h"
#include <assert.h>
#include <memory.h>
//#define SHEAR
//#define DEBUG
+//----------------------------------------- svp renderer ----------------------------------------
+
+typedef struct {
+ int xmin;
+ int ymin;
+ int xmax;
+ int ymax;
+ int width;
+ int height;
+} intbbox_t;
+
+typedef struct _renderpoint
+{
+ double x;
+ signed char direction;
+} 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, signed char direction)
+{
+ renderpoint_t p;
+ p.x = x;
+ p.direction = direction;
+
+ 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, signed char direction)
+{
+ x1 *= buf->zoom;
+ y1 *= buf->zoom;
+ x2 *= buf->zoom;
+ y2 *= buf->zoom;
+ double diffx, diffy;
+ double ny1, ny2, stepx;
+ if(y2 < y1) {
+ 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, direction);
+ 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_svp(ArtSVP*svp, intbbox_t*bbox, double zoom, ArtWindRule 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;
+ }
+
+ int t;
+ for(t=0;t<svp->n_segs;t++) {
+ ArtSVPSeg* seg = &svp->segs[t];
+ int s;
+ for(s=0;s<seg->n_points-1;s++) {
+ int dir = seg->dir? 1 : -1;
+ add_line(buf, seg->points[s].x, seg->points[s].y, seg->points[s+1].x, seg->points[s+1].y, dir);
+ }
+ }
+ 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;
+ int wind = 0;
+ qsort(points, num, sizeof(renderpoint_t), compare_renderpoints);
+ int lastx = 0;
+ int 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 && x!=lastx) {
+ fill_bitwise(line, lastx, x);
+ }
+ wind += p->direction;
+ if(rule == ART_WIND_RULE_INTERSECT) {
+ fill = wind>=2;
+ } else if (rule == ART_WIND_RULE_NONZERO) {
+ fill = wind!=0;
+ } else if (rule == ART_WIND_RULE_ODDEVEN) {
+ fill = wind&1;
+ } else { // rule == ART_WIND_RULE_POSITIVE
+ fill = wind>=1;
+ }
+ lastx = x;
+ }
+ if(fill && 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
+
+intbbox_t get_svp_bbox(ArtSVP*svp, double zoom)
+{
+ int t;
+ intbbox_t b = {0,0,0,0};
+ if(svp->n_segs && svp->segs[0].n_points) {
+ b.xmin = svp->segs[0].points[0].x;
+ b.ymin = svp->segs[0].points[0].y;
+ b.xmax = svp->segs[0].points[0].x;
+ b.ymax = svp->segs[0].points[0].y;
+ }
+ for(t=0;t<svp->n_segs;t++) {
+ ArtSVPSeg* seg = &svp->segs[t];
+ int s;
+ for(s=0;s<seg->n_points;s++) {
+ double x = seg->points[s].x*zoom;
+ double y = seg->points[s].y*zoom;
+ int x1 = floor(x);
+ int x2 = ceil(x);
+ int y1 = floor(y);
+ int y2 = ceil(y);
+ 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;
+}
+
+
+//-----------------------------------------------------------------------------------------------
+
static ArtVpath* gfxline_to_ArtVpath(gfxline_t*line, char fill)
{
ArtVpath *vec = NULL;
static void shear_svp(ArtSVP*svp, double v)
{
- /* do a "shearing on the polygon. We do this to eliminate all
+ /* do a "shearing" on the polygon. We do this to eliminate all
horizontal lines (which libart can't handle properly, even though
it tries). */
}
if(!fail)
break;
- v = lrand48() / 2000000000.0;
+#ifdef HAVE_LRAND48
+ v = lrand48() / 2000000000.0;;
+#elif HAVE_RAND
+ v = rand() / 2000000000.0;
+#else
+#error "no lrand48()/rand() implementation found"
+#endif
tries++;
}
return v;
printf("\n");
}
-void check_svp(ArtSVP*svp)
+
+typedef struct svp_segment_part
+{
+ double y1;
+ double y2;
+ char active;
+} svp_segment_part_t;
+
+int compare_double(const void*_y1, const void*_y2)
+{
+ const double*y1 = _y1;
+ const double*y2 = _y2;
+ if(*y1<*y2) return -1;
+ if(*y1>*y2) return 1;
+ else return 0;
+}
+
+int compare_seg_start(const void*_s1, const void*_s2)
+{
+ svp_segment_part_t*s1 = *(svp_segment_part_t**)_s1;
+ svp_segment_part_t*s2 = *(svp_segment_part_t**)_s2;
+ if(s1->y1 < s2->y1) return -1;
+ if(s1->y1 > s2->y1) return 1;
+ else return 0;
+}
+
+int compare_seg_end(const void*_s1, const void*_s2)
+{
+ svp_segment_part_t*s1 = *(svp_segment_part_t**)_s1;
+ svp_segment_part_t*s2 = *(svp_segment_part_t**)_s2;
+ if(s1->y2 < s2->y2) return -1;
+ if(s1->y2 > s2->y2) return 1;
+ else return 0;
+}
+
+void clean_svp(ArtSVP*svp)
{
int t;
+ int oldpoints = 0;
+ int newpoints = 0;
+ int oldsegs = 0;
+ int newsegs = 0;
for(t=0;t<svp->n_segs;t++) {
ArtSVPSeg* seg = &svp->segs[t];
int p;
+ int pos=0;
+ double lasty = 0;
+ oldpoints += seg->n_points;
+ for(p=0;p<seg->n_points;p++) {
+ ArtPoint* p1 = &seg->points[p];
+ if(!p || lasty!=p1->y) {
+ seg->points[pos] = seg->points[p];
+ pos++;
+ lasty = p1->y;
+ }
+ }
+ seg->n_points = pos;
+ newpoints += seg->n_points;
+ }
+ int pos = 0;
+ oldsegs = svp->n_segs;
+ for(t=0;t<svp->n_segs;t++) {
+ if(svp->segs[t].n_points > 1) {
+ svp->segs[pos++] = svp->segs[t];
+ }
+ }
+ svp->n_segs = pos;
+ newsegs = svp->n_segs;
+ if(newsegs < oldsegs || newpoints < oldpoints) {
+ msg("<verbose> Simplified polygon from %d points to %d points, %d to %d segs",
+ oldpoints, newpoints, oldsegs, newsegs);
+ }
+}
+
+int check_svp(ArtSVP*svp)
+{
+ /* count number of y coordinates and segs */
+ int t;
+ int num_points = 0;
+ int num_segs = 0;
+ for(t=0;t<svp->n_segs;t++) {
+ if(!svp->segs[t].n_points) {
+ msg("<error> svp contains segment with zero points\n");
+ return 0;
+ }
+ num_points += svp->segs[t].n_points;
+ num_segs += svp->segs[t].n_points - 1;
+ }
+
+ /* create segs and ys */
+ double*y = malloc(sizeof(double)*num_points);
+ svp_segment_part_t*segs = malloc(sizeof(svp_segment_part_t)*num_segs);
+ svp_segment_part_t**seg_start = malloc(sizeof(svp_segment_part_t*)*num_segs);
+ svp_segment_part_t**seg_end = malloc(sizeof(svp_segment_part_t*)*num_segs);
+
+ int c1=0;
+ num_segs = 0;
+ for(t=0;t<svp->n_segs;t++) {
+ ArtSVPSeg* seg = &svp->segs[t];
+ int p;
+ for(p=0;p<seg->n_points;p++) {
+ y[c1++] = seg->points[p].y;
+ assert(c1 <= num_points);
+ }
for(p=0;p<seg->n_points-1;p++) {
ArtPoint* p1 = &seg->points[p];
ArtPoint* p2 = &seg->points[p+1];
- if(p1->y > p2->y) {
- fprintf(stderr, "bad svp, y in seg %08x is non-increasing\n");
- exit(0);
- }
+
+ if(p1->y >= p2->y) {
+ if(p1->y > p2->y) {
+ msg("<error> bad svp, y in seg is non-increasing %.16f -> %.16f\n", p1->y, p2->y);
+ }
+ } else {
+ segs[num_segs].y1 = p1->y;
+ segs[num_segs].y2 = p2->y;
+ segs[num_segs].active = 0;
+ seg_start[num_segs] = &segs[num_segs];
+ seg_end[num_segs] = &segs[num_segs];
+ num_segs++;
+ }
}
}
+
+ qsort(y, num_points, sizeof(double), compare_double);
+ qsort(seg_start, num_segs, sizeof(svp_segment_part_t*), compare_seg_start);
+ qsort(seg_end, num_segs, sizeof(svp_segment_part_t*), compare_seg_end);
+
+ double lasty = num_points?y[0]+1:0;
+ int num_active = 0;
+ int bleed = 0;
+ double bleedy1=0,bleedy2 = 0;
+ for(t=0;t<num_points;t++) {
+ if(lasty == y[t])
+ continue;
+ int s;
+ for(s=0;s<num_segs;s++) {
+ if(segs[s].y1==y[t]) {
+ /* segment is starting */
+ segs[s].active = 1;
+ num_active++;
+ } else if(segs[s].y2==y[t]) {
+ segs[s].active = 0;
+ num_active--;
+ }
+ }
+ if(num_active&1) {
+ bleed = num_active;
+ bleedy1 = y[t];
+ } else {
+ if(bleed) {
+ bleedy2 = y[t];
+ break;
+ }
+ }
+ lasty = y[t];
+ }
+ if(bleed) {
+ msg("<verbose> svp bleeds from y=%.16f to y=%.16f (%d/%d active segments)\n",
+ bleedy1, bleedy2,
+ bleed, num_segs);
+ free(y);free(segs);free(seg_start);free(seg_end);
+ return 0;
+ }
+
+ free(y);
+ free(segs);
+ free(seg_start);
+ free(seg_end);
+
+ return 1;
}
void write_svp_postscript(const char*filename, ArtSVP*svp)
{
- printf("writing %s\n", filename);
+ if(!svp)
+ return;
FILE*fi = fopen(filename, "wb");
int i, j;
double xmin=0,ymin=0,xmax=0,ymax=0;
return svp;
}
+//#ifdef SHEAR
+// double shear = find_shear_value(svp);
+// gfxline_t*line = gfxpoly_to_gfxline((gfxpoly_t*)svp);
+// gfxline_t*l = line;
+// while(l) {
+// l->y += l->x*shear;
+// l->sy += l->sx*shear;
+// l= l->next;
+// }
+// svp = (ArtSVP*)gfxpoly_fillToPoly(line);
+// printf("shearing svp by %.16f\n", shear);
+//#endif
+// ....
+//#ifdef SHEAR
+// art_svp_free(svp);
+// shear_svp(result, -shear);
+//#endif
+
+
ArtSVP* run_intersector(ArtSVP*svp, ArtWindRule rule)
{
ArtSvpWriter * swr = art_svp_writer_rewind_new(rule);
-#ifdef SHEAR
- double shear = find_shear_value(svp);
- gfxline_t*line = gfxpoly_to_gfxline((gfxpoly_t*)svp);
- gfxline_t*l = line;
- while(l) {
- l->y += l->x*shear;
- l->sy += l->sx*shear;
- l= l->next;
- }
- svp = (ArtSVP*)gfxpoly_fillToPoly(line);
- printf("shearing svp by %.16f\n", shear);
-#endif
+ double zoom = 1.0;
+ intbbox_t bbox = get_svp_bbox(svp, zoom);
art_svp_intersector(svp, swr);
ArtSVP*result = art_svp_writer_rewind_reap(swr);
- check_svp(result);
-
-#ifdef SHEAR
- art_svp_free(svp);
- shear_svp(result, -shear);
-#endif
+ clean_svp(result);
+ if(!check_svp(result)) {
+ current_svp = result;
+ art_report_error(); // might set art_error_in_intersector
+ } else {
+ msg("<verbose> Comparing polygon renderings of size %dx%d and %dx%d", bbox.width, bbox.height, bbox.width, bbox.height);
+ unsigned char*data1 = render_svp(svp, &bbox, zoom, rule);
+ unsigned char*data2 = render_svp(result, &bbox, zoom, ART_WIND_RULE_ODDEVEN);
+ if(!compare_bitmaps(&bbox, data1, data2)) {
+ msg("<verbose> Bad SVP rewinding result- polygons don't match");
+ current_svp = result;
+ art_report_error(); // might set art_error_in_intersector
+ }
+ free(data1);
+ free(data2);
+ }
+ if(art_error_in_intersector) {
+ msg("<verbose> Error in polygon processing");
+ art_svp_free(result);
+ art_error_in_intersector=0;
+ return 0;
+ }
return result;
}
-
gfxline_t* gfxpoly_to_gfxline(gfxpoly_t*poly)
{
ArtSVP*svp = (ArtSVP*)poly;
gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line)
{
/* I'm not sure whether doing perturbation here is actually
- a good idea- if that line has been run through the machine
+ a good idea- if that line has been run through the machinery
several times already, it might be safer to leave it alone,
since it should already be in a format libart can handle */
#ifdef PERTURBATE
gfxpoly_t* gfxpoly_intersect(gfxpoly_t*poly1, gfxpoly_t*poly2)
{
ArtSvpWriter *swr;
-
+
static int counter = 0;
ArtSVP* svp1 = (ArtSVP*)poly1;
ArtSVP* svp_rewinded;
svp_rewinded = run_intersector(svp, ART_WIND_RULE_POSITIVE);
+ if(!svp_rewinded) {
+ art_svp_free(svp);
+ return 0;
+ }
gfxline_t* result = gfxpoly_to_gfxline((gfxpoly_t*)svp_rewinded);
art_svp_free(svp);