From 235732a3db9cfe3ac8228969ee1ad58410eab843 Mon Sep 17 00:00:00 2001 From: kramm Date: Sat, 5 Apr 2003 19:19:47 +0000 Subject: [PATCH] new algorithm --- pdf2swf/spline.cc | 269 ++++++++++++++++++++++++++++++++++++++++++++++++++--- pdf2swf/spline.h | 21 ++++- 2 files changed, 273 insertions(+), 17 deletions(-) diff --git a/pdf2swf/spline.cc b/pdf2swf/spline.cc index a0aed8d..37591be 100644 --- a/pdf2swf/spline.cc +++ b/pdf2swf/spline.cc @@ -7,17 +7,12 @@ This file is distributed under the GPL, see file COPYING for details */ -/* At the moment, we convert non-recursively into at max. 6 quadratic splines, - trying to maintain the general structure of the curve, rather than it's - exact path. - To accomplish this, we split each curve at it's X,Y extremas as well as - its deviation's X,Y extremas. - */ - +#include +#include #include #include "spline.h" -int solve(double a,double b,double c, double*dd) +static int solve(double a,double b,double c, double*dd) { double det=b*b-4*a*c; int pos = 0; @@ -43,13 +38,14 @@ struct plotxy splinepos(struct plotxy p0, struct plotxy p1, struct plotxy p2, st return p; } -double distance(struct plotxy p0, struct plotxy p1) +inline double plotxy_dist(struct plotxy a, struct plotxy b) { - double xd=p1.x-p0.x; - double yd=p1.y-p0.y; - return sqrt(xd*xd+yd*yd); + double dx = a.x - b.x; + double dy = a.y - b.y; + return sqrt(dx*dx+dy*dy); } + int wp(double p0,double p1,double p2,double p3,double*dd) { double div= (6*p0-18*p1+18*p2-6*p3); @@ -58,8 +54,7 @@ int wp(double p0,double p1,double p2,double p3,double*dd) return (dd[0]>0 && dd[0]<1); } -int approximate(struct plotxy p0, struct plotxy p1, - struct plotxy p2, struct plotxy p3, struct qspline*q) +int approximate(struct plotxy p0, struct plotxy p1, struct plotxy p2, struct plotxy p3, struct qspline*q) { double roots[12]; int pos = 0; @@ -90,7 +85,7 @@ int approximate(struct plotxy p0, struct plotxy p1, last = myxy[0]; for(t=1;t0.01 || t==pos-1) @@ -138,3 +133,247 @@ int approximate(struct plotxy p0, struct plotxy p1, return pos-1; } +/* move the control point so that the spline runs through the original + control point */ +void fixcp(qspline*s) +{ + plotxy 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; +} + +int approximate2(struct cspline*s, struct qspline*q, double quality, double start, double end); + +void check(struct cspline*s, struct qspline*q, int num) +{ + int t; + plotxy p = s->start; + for(t=0;t 0.005) { + printf("--\n"); + exit(1); + } + p = q[t].end; + } + if(plotxy_dist(p, s->end) > 0.005) { + printf("--\n"); + exit(1); + } +} + +int cspline_approximate(struct cspline*s, struct qspline*q, double quality, approximate_method method) +{ + if(method==0) { + return approximate(s->start, s->control1, s->control2, s->end, q); + } else { + return approximate2(s, q, quality, 0.0, 1.0); + } +} +inline plotxy cspline_getpoint(cspline*s, double t) +{ + plotxy 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); + return p; +} +plotxy cspline_getderivative(cspline*s, double t) +{ + plotxy 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; +} +plotxy cspline_getderivative2(cspline*s, double t) +{ + plotxy d; + d.x = s->end.x*(6*t) + 3*s->control2.x*(2-6*t) + + 3*s->control1.x*(-4+6*t) + s->start.x*(6-6*t); + d.y = s->end.y*(6*t) + 3*s->control2.y*(2-6*t) + + 3*s->control1.y*(-4+6*t) + s->start.y*(6-6*t); + return d; +} +plotxy cspline_getderivative3(cspline*s, double t) +{ + plotxy d; + d.x = 6*s->end.x - 18*s->control2.x + 18*s->control1.x - 6*s->start.x; + d.y = 6*s->end.y - 18*s->control2.y + 18*s->control1.y - 6*s->start.y; + return d; +} +void cspline_getequalspacedpoints(cspline*s, float**p, int*num, double dist) +{ + plotxy d,next; + double t = 0; + int end = 0; + int pos = 0; + float*positions = (float*)malloc(1048576); + do + { + if(t>=1.0) { + t = 1.0; + end = 1; + } + + plotxy d = cspline_getderivative(s, t); + plotxy d2 = cspline_getderivative2(s, t); + + double dl = sqrt(d.x*d.x+d.y*d.y); + double dl2 = sqrt(d2.x*d2.x+d2.y*d2.y); + + double rdl = dist/dl; + + if(rdl>1.0-t) + rdl = 1.0-t; + + plotxy p = cspline_getpoint(s, t); + while(plotxy_dist(cspline_getpoint(s, t+rdl), p) > dist) { + /* we were ask to divide the spline into dist long fragments, + but for the value we estimated even the geometric distance + is bigger than 'dist'. Approximate a better value. + */ + rdl = rdl*0.9; + } + + positions[pos] = t; + t+=rdl; + pos++; + } + while(!end); + *num = pos; + *p = positions; +} + +plotxy qspline_getpoint(qspline*s, double t) +{ + plotxy p; + p.x= s->end.x*t*t + 2*s->control.x*t*(1-t) + s->start.x*(1-t)*(1-t); + p.y= s->end.y*t*t + 2*s->control.y*t*(1-t) + s->start.y*(1-t)*(1-t); + return p; +} +plotxy qspline_getderivative(qspline*s, double t) +{ + plotxy p; + p.x= s->end.x*2*t + 2*s->control.x*(1-2*t) + s->start.x*(-2+2*t); + p.y= s->end.y*2*t + 2*s->control.y*(1-2*t) + s->start.y*(-2+2*t); + return p; +} +plotxy qspline_getderivative2(qspline*s, double t) +{ + plotxy p; + p.x= s->end.x*2 + 2*s->control.x*(-2) + s->start.x*(2); + p.y= s->end.y*2 + 2*s->control.y*(-2) + s->start.y*(2); + return p; +} +double qspline_getlength(qspline*s) +{ + double t = 0; + int end = 0; + double len; + plotxy last = qspline_getpoint(s, 0.0); + do { + if(t>=1.0) { + t = 1.0; + end = 1; + } + plotxy d2 = qspline_getderivative2(s, t); + double dl2 = sqrt(d2.x*d2.x+d2.y*d2.y); + double rdl = 1.0/dl2; + if(rdl>0.01) + rdl = 0.01; + t+=rdl; + plotxy here = qspline_getpoint(s, t); + len += plotxy_dist(last, here); + last = here; + } + while(!end); + return len; +} +void qsplines_getequalspacedpoints(qspline**s, int num, float**p, int*pnum, double acc) +{ +/* int t; + float r[128]; + for(t=0;t=1.0) { + t = 1.0; + end = 1; + } + + plotxy d = qspline_getderivative(s, t); + double dl = sqrt(d.x*d.x+d.y*d.y); + double rdl = acc/dl; + + if(rdl>acc) + rdl = acc; + + positions[pos] = t; + t+=rdl; + pos++; + } + while(!end); + *pnum = pos; + *p = positions; +} + +int approximate2(struct cspline*s, struct qspline*q, double quality, double start, double end) +{ + int num=0; + plotxy qr1,qr2,cr1,cr2; + double dist1,dist2; + int t; + int recurse = 0; + int probes = 15; + qspline test; + test.start = cspline_getpoint(s, start); + test.control = cspline_getpoint(s, (start+end)/2); + test.end = cspline_getpoint(s, end); + fixcp(&test); + for(t=0;tquality) { + recurse=1;break; + } + qr2 = qspline_getpoint(&test, (1-pos)); + cr2 = cspline_getpoint(s, start+(1-pos)*(end-start)); + dist2 = plotxy_dist(qr2, cr2); + if(dist2>quality) { + recurse=1;break; + } + } + + if(recurse && (end-start)>1.0/120) { + /* quality is too bad, split it up recursively */ + num += approximate2(s, q, quality, start, (start+end)/2); + q+=num; + num += approximate2(s, q, quality, (start+end)/2, end); + return num; + } else { + *q = test; + return 1; + } +} + diff --git a/pdf2swf/spline.h b/pdf2swf/spline.h index f9549cc..609a7bd 100644 --- a/pdf2swf/spline.h +++ b/pdf2swf/spline.h @@ -30,7 +30,24 @@ struct cspline struct plotxy end; }; -int approximate(struct plotxy p0, struct plotxy p1, - struct plotxy p2, struct plotxy p3, struct qspline*q); +typedef enum {APPROXIMATE_INFLECTION=0, APPROXIMATE_RECURSIVE_BINARY=1} approximate_method; + +int approximate(struct plotxy p0, struct plotxy p1, struct plotxy p2, struct plotxy p3, struct qspline*q); + +struct plotxy splinepos(struct plotxy p0, struct plotxy p1, struct plotxy p2, struct plotxy p3, double d); +double plotxy_dist(struct plotxy a, struct plotxy b); + +plotxy cspline_getpoint(cspline*s, double t); +plotxy cspline_getderivative(cspline*s, double t); +plotxy cspline_getderivative2(cspline*s, double t); +plotxy cspline_getderivative3(cspline*s, double t); +void cspline_getequalspacedpoints(cspline*s, float**p, int*num, double dist); +int cspline_approximate(struct cspline*s, struct qspline*q, double quality, approximate_method method); + +plotxy qspline_getpoint(qspline*s, double t); +plotxy qspline_getderivative(qspline*s, double t); +plotxy qspline_getderivative2(qspline*s, double t); +double qspline_getlength(qspline*s); +void qsplines_getequalspacedpoints(qspline**s, int num, float**p, int*pnum, double t); #endif// __spline_h__ -- 1.7.10.4