From: kramm Date: Sat, 31 Jan 2004 09:29:28 +0000 (+0000) Subject: optimized spline conversion. X-Git-Tag: release-0-5-0~97 X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=commitdiff_plain;h=facdbc2c6d5ac9b5d6551690f646355bf11ae58e optimized spline conversion. --- diff --git a/lib/drawer.c b/lib/drawer.c index f0d3d34..d371657 100644 --- a/lib/drawer.c +++ b/lib/drawer.c @@ -43,7 +43,7 @@ static char* getToken(const char**p) return result; } -void draw_conicto(drawer_t*draw, FPOINT* c, FPOINT* to) +void draw_conicTo(drawer_t*draw, FPOINT* c, FPOINT* to) { FPOINT* pos = &draw->pos; FPOINT c1,c2; @@ -51,7 +51,7 @@ void draw_conicto(drawer_t*draw, FPOINT* c, FPOINT* to) c1.y = (pos->y + 2 * c->y) / 3; c2.x = (2 * c->x + to->x) / 3; c2.y = (2 * c->y + to->y) / 3; - draw_cubicto(draw, &c1,&c2,to); + draw_cubicTo(draw, &c1,&c2,to); draw->pos = *to; } @@ -61,6 +61,8 @@ void draw_string(drawer_t*draw, const char*string) const char*p = string; while(*p) { char*token = getToken(&p); + if(!token || !*token) + break; if(!strncmp(token, "moveTo", 6)) { FPOINT to; to.x = atoi(getToken(&p)); @@ -81,6 +83,18 @@ void draw_string(drawer_t*draw, const char*string) to.y = atoi(getToken(&p)); draw->splineTo(draw, &mid, &to); } + else if(!strncmp(token, "cubicTo", 5)) { + FPOINT mid1,mid2,to; + mid1.x = atoi(getToken(&p)); + mid1.y = atoi(getToken(&p)); + mid2.x = atoi(getToken(&p)); + mid2.y = atoi(getToken(&p)); + to.x = atoi(getToken(&p)); + to.y = atoi(getToken(&p)); + draw_cubicTo(draw, &mid1, &mid2, &to); + } + else fprintf(stderr, "drawer: Warning: unknown primitive '%s'", token); + free(token); } } @@ -105,29 +119,21 @@ struct cspline struct SPLINEPOINT end; }; -/* move the control point so that the spline runs through the original - control point */ -static void fixcp(struct qspline*s) -{ - struct SPLINEPOINT mid,dir; - mid.x = (s->end.x + s->start.x)/2; - mid.y = (s->end.y + s->start.y)/2; - dir.x = s->control.x - mid.x; - dir.y = s->control.y - mid.y; - s->control.x = mid.x + 2*dir.x; - s->control.y = mid.y + 2*dir.y; -} - -static inline struct SPLINEPOINT cspline_getpoint(struct cspline*s, double t) +static inline struct SPLINEPOINT cspline_getpoint(const struct cspline*s, double t) { struct SPLINEPOINT p; - p.x= s->end.x*t*t*t + 3*s->control2.x*t*t*(1-t) - + 3*s->control1.x*t*(1-t)*(1-t) + s->start.x*(1-t)*(1-t)*(1-t); - p.y= s->end.y*t*t*t + 3*s->control2.y*t*t*(1-t) - + 3*s->control1.y*t*(1-t)*(1-t) + s->start.y*(1-t)*(1-t)*(1-t); + double tt = t*t; + double ttt = tt*t; + double mt = (1-t); + double mtmt = mt*(1-t); + double mtmtmt = mtmt*(1-t); + p.x= s->end.x*ttt + 3*s->control2.x*tt*mt + + 3*s->control1.x*t*mtmt + s->start.x*mtmtmt; + p.y= s->end.y*ttt + 3*s->control2.y*tt*mt + + 3*s->control1.y*t*mtmt + s->start.y*mtmtmt; return p; } -static struct SPLINEPOINT qspline_getpoint(struct qspline*s, double t) +static struct SPLINEPOINT qspline_getpoint(const struct qspline*s, double t) { struct SPLINEPOINT p; p.x= s->end.x*t*t + 2*s->control.x*t*(1-t) + s->start.x*(1-t)*(1-t); @@ -135,85 +141,104 @@ static struct SPLINEPOINT qspline_getpoint(struct qspline*s, double t) return p; } -static struct SPLINEPOINT cspline_getderivative(struct cspline*s, double t) +static int approximate3(const struct cspline*s, struct qspline*q, int size, double quality2) { - struct SPLINEPOINT d; - d.x = s->end.x*(3*t*t) + 3*s->control2.x*(2*t-3*t*t) + - 3*s->control1.x*(1-4*t+3*t*t) + s->start.x*(-3+6*t-3*t*t); - d.y = s->end.y*(3*t*t) + 3*s->control2.y*(2*t-3*t*t) + - 3*s->control1.y*(1-4*t+3*t*t) + s->start.y*(-3+6*t-3*t*t); - return d; -} + unsigned int gran = 0; + unsigned int istep = 0x80000000; + unsigned int istart = 0; + int num = 0; + int level = 0; + + while(istart<0x80000000) + { + unsigned int iend = istart + istep; + double start = istart/(double)0x80000000; + double end = iend/(double)0x80000000; + struct qspline test; + double pos,qpos; + char left = 0,recurse=0; + int t; + int probes = 15; -static int approximate2(struct cspline*s, struct qspline*q, double quality, double start, double end, int max, int depth) -{ - int num=0; - struct SPLINEPOINT qr1,qr2,cr1,cr2; - double dist1,dist2; - double qquality = quality*quality; - int t; - int recurse = 0; - int probes = 15; - struct qspline test; - char left = 0; - test.start = cspline_getpoint(s, start); - test.control = cspline_getpoint(s, (start+end)/2); - test.end = cspline_getpoint(s, end); - fixcp(&test); - - if(start< 0.5) { - test.control = cspline_getderivative(s, start); - test.control.x *= (end-start)/2; - test.control.y *= (end-start)/2; - test.control.x += test.start.x; - test.control.y += test.start.y; - } else { - test.control = cspline_getderivative(s, end); - test.control.x *= -(end-start)/2; - test.control.y *= -(end-start)/2; - test.control.x += test.end.x; - test.control.y += test.end.y; - } + /* create simple approximation: a qspline which run's through the + qspline point at 0.5 */ + test.start = cspline_getpoint(s, start); + test.control = cspline_getpoint(s, (start+end)/2); + test.end = cspline_getpoint(s, end); + /* fix the control point: + move it so that the new spline does runs through it */ + test.control.x = -(test.end.x + test.start.x)/2 + 2*(test.control.x); + test.control.y = -(test.end.y + test.start.y)/2 + 2*(test.control.y); - for(t=0;tend.x*(3*qpos) + 3*s->control2.x*(2*pos-3*qpos) + + 3*s->control1.x*(1-4*pos+3*qpos) + s->start.x*(-3+6*pos-3*qpos); + test.control.y = s->end.y*(3*qpos) + 3*s->control2.y*(2*pos-3*qpos) + + 3*s->control1.y*(1-4*pos+3*qpos) + s->start.y*(-3+6*pos-3*qpos); + if(left) { + test.control.x *= (end-start)/2; + test.control.y *= (end-start)/2; + test.control.x += test.start.x; + test.control.y += test.start.y; + } else { + test.control.x *= -(end-start)/2; + test.control.y *= -(end-start)/2; + test.control.x += test.end.x; + test.control.y += test.end.y; + } - dx = qr1.x - cr1.x; - dy = qr1.y - cr1.y; - dist1 = dx*dx+dy*dy; + /* measure the spline's accurancy, by taking a number of probes */ - if(dist1>qquality) { - recurse=1;break; - } - qr2 = qspline_getpoint(&test, (1-pos)); - cr2 = cspline_getpoint(s, start+(1-pos)*(end-start)); + for(t=0;tqquality) { - recurse=1;break; + if(dist1>quality2) { + recurse=1;break; + } + qr2 = qspline_getpoint(&test, (1-pos)); + cr2 = cspline_getpoint(s, start+(1-pos)*(end-start)); + + dx = qr2.x - cr2.x; + dy = qr2.y - cr2.y; + dist2 = dx*dx+dy*dy; + + if(dist2>quality2) { + recurse=1;break; + } } - } - if(recurse && (end-start)>1.0/120 && max-depth > 0) { - /* quality is too bad, split it up recursively */ - num += approximate2(s, q, quality, start, (start+end)/2, max, depth+1); - q+=num; - max-=num; - num += approximate2(s, q, quality, (start+end)/2, end, max, depth+1); - return num; - } else { - *q = test; - return 1; + if(recurse && istep>1 && size-level > num) { + istep >>= 1; + level++; + } else { + *q++ = test; + num++; + istart += istep; + while(!(istart & istep)) { + level--; + istep <<= 1; + } + } } + return num; } -void draw_cubicto(drawer_t*draw, FPOINT* control1, FPOINT* control2, FPOINT* to) +void draw_cubicTo(drawer_t*draw, FPOINT* control1, FPOINT* control2, FPOINT* to) { struct qspline q[128]; struct cspline c; @@ -225,10 +250,10 @@ void draw_cubicto(drawer_t*draw, FPOINT* control1, FPOINT* control2, FPOINT* t c.control2.y = control2->y; c.end.x = to->x; c.end.y = to->y; - double quality = 0.8; + double quality = 80; double maxerror = (500-(quality*5)>1?500-(quality*5):1)/20.0; - int num = approximate2(&c, q, maxerror, 0.0, 1.0, 128, 0); + int num = approximate3(&c, q, 128, maxerror*maxerror); int t; for(t=0;t