/* [<][>][^][v][top][bottom][index][help] */
DEFINITIONS
This source file includes following definitions.
- getToken
- draw_conicTo
- draw_conicTo2
- draw_moveTo2
- draw_lineTo2
- getFloat
- draw_string
- cspline_getpoint
- qspline_getpoint
- approximate3
- draw_cubicTo
/* drawer.c
part of swftools
A generic structure for providing vector drawing.
(Helper routines, spline approximation, simple text drawers)
Copyright (C) 2003 Matthias Kramm <kramm@quiss.org>
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <ctype.h>
#include "drawer.h"
static char* getToken(const char**p)
{
const char*start;
char*result;
while(**p && strchr(" ,()\t\n\r", **p)) {
(*p)++;
}
start = *p;
/*
SVF pathdata can exclude whitespace after L and M commands.
Ref: http://www.w3.org/TR/SVG11/paths.html#PathDataGeneralInformation
This allows us to use svg files output from gnuplot.
Also checks for relative MoveTo and LineTo (m and l).
051106 Magnus Lundin, lundin@mlu.mine.nu
*/
if (strchr("LMlm", **p) && (isdigit(*(*p+1))||strchr("+-", *(*p+1)))) {
(*p)++;
}
else while(**p && !strchr(" ,()\t\n\r", **p)) {
(*p)++;
}
result = (char*)malloc((*p)-start+1);
memcpy(result,start,(*p)-start+1);
result[(*p)-start] = 0;
return result;
}
void draw_conicTo(drawer_t*draw, FPOINT* c, FPOINT* to)
{
FPOINT* pos = &draw->pos;
FPOINT c1,c2;
c1.x = (pos->x + 2 * c->x) / 3;
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->pos = *to;
}
/* convenience routine */
static void draw_conicTo2(drawer_t*draw, double x1, double y1, double x2, double y2)
{
FPOINT c1,c2;
c1.x = x1;
c1.y = y1;
c2.x = x2;
c2.y = y2;
draw_conicTo(draw, &c1, &c2);
}
/* convenience routine */
static void draw_moveTo2(drawer_t*draw, double x, double y)
{
FPOINT c;
c.x = x; c.y = y;
draw->moveTo(draw, &c);
}
/* convenience routine */
static void draw_lineTo2(drawer_t*draw, double x, double y)
{
FPOINT c;
c.x = x; c.y = y;
draw->lineTo(draw, &c);
}
static float getFloat(const char** p)
{
char* token = getToken(p);
float result = atof(token);
free(token);
return result;
}
void draw_string(drawer_t*draw, const char*string)
{
const char*p = string;
while(*p) {
char*token = getToken(&p);
if(!token)
break;
if (!*token)
{
free(token);
break;
}
if(!strncmp(token, "moveTo", 6) ||
!strncmp(token, "M", 1) //svg
) {
FPOINT to;
to.x = getFloat(&p);
to.y = getFloat(&p);
draw->moveTo(draw, &to);
}
else if(!strncmp(token, "lineTo", 6) ||
!strncmp(token, "L", 1) //svg
) {
FPOINT to;
to.x = getFloat(&p);
to.y = getFloat(&p);
draw->lineTo(draw, &to);
}
else if(!strncmp(token, "curveTo", 7) || !strncmp(token, "splineTo", 8)) {
FPOINT mid,to;
mid.x = getFloat(&p);
mid.y = getFloat(&p);
to.x = getFloat(&p);
to.y = getFloat(&p);
draw->splineTo(draw, &mid, &to);
}
else if(!strncmp(token, "conicTo", 5)) {
FPOINT mid,to;
mid.x = getFloat(&p);
mid.y = getFloat(&p);
to.x = getFloat(&p);
to.y = getFloat(&p);
draw_conicTo(draw, &mid, &to);
}
else if(!strncmp(token, "circle", 6)) {
int mx,my,r;
double r2;
mx = getFloat(&p);
my = getFloat(&p);
r = getFloat(&p);
r2 = 0.70710678118654757*r;
draw_moveTo2(draw, mx, my-r);
draw_conicTo2(draw, mx+r2, my-r2, mx+r, my);
draw_conicTo2(draw, mx+r2, my+r2, mx, my+r);
draw_conicTo2(draw, mx-r2, my+r2, mx-r, my);
draw_conicTo2(draw, mx-r2, my-r2, mx, my-r);
}
else if(!strncmp(token, "box", 3)) {
int x1,y1,x2,y2;
x1 = getFloat(&p);
y1 = getFloat(&p);
x2 = getFloat(&p);
y2 = getFloat(&p);
draw_moveTo2(draw, x1, y1);
draw_lineTo2(draw, x1, y2);
draw_lineTo2(draw, x2, y2);
draw_lineTo2(draw, x2, y1);
draw_lineTo2(draw, x1, y1);
}
else if(!strncmp(token, "cubicTo", 5) ||
!strncmp(token, "C", 1) //svg
) {
FPOINT mid1,mid2,to;
mid1.x = getFloat(&p);
mid1.y = getFloat(&p);
mid2.x = getFloat(&p);
mid2.y = getFloat(&p);
to.x = getFloat(&p);
to.y = getFloat(&p);
draw_cubicTo(draw, &mid1, &mid2, &to);
}
else if(!strncmp(token, "z", 1) //svg
) {
// ignore
}
else
fprintf(stderr, "drawer: Warning: unknown primitive '%s'\n", token);
free(token);
}
}
struct SPLINEPOINT
{
double x,y;
};
struct qspline
{
struct SPLINEPOINT start;
struct SPLINEPOINT control;
struct SPLINEPOINT end;
};
struct cspline
{
struct SPLINEPOINT start;
struct SPLINEPOINT control1;
struct SPLINEPOINT control2;
struct SPLINEPOINT end;
};
static inline struct SPLINEPOINT cspline_getpoint(const struct cspline*s, double t)
{
struct SPLINEPOINT p;
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(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);
p.y= s->end.y*t*t + 2*s->control.y*t*(1-t) + s->start.y*(1-t)*(1-t);
return p;
}
static int approximate3(const struct cspline*s, struct qspline*q, int size, double quality2)
{
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;
/* 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);
/* depending on where we are in the spline, we either try to match
the left or right tangent */
if(start<0.5)
left=1;
/* get derivative */
pos = left?start:end;
qpos = pos*pos;
test.control.x = s->end.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;
}
#define PROBES
#ifdef PROBES
/* measure the spline's accurancy, by taking a number of probes */
for(t=0;t<probes;t++) {
struct SPLINEPOINT qr1,qr2,cr1,cr2;
double pos = 0.5/(probes*2)*(t*2+1);
double dx,dy;
double dist1,dist2;
qr1 = qspline_getpoint(&test, pos);
cr1 = cspline_getpoint(s, start+pos*(end-start));
dx = qr1.x - cr1.x;
dy = qr1.y - cr1.y;
dist1 = dx*dx+dy*dy;
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;
}
}
#else // quadratic error: *much* faster!
/* convert control point representation to
d*x^3 + c*x^2 + b*x + a */
double dx,dy;
dx= s->end.x - s->control2.x*3 + s->control1.x*3 - s->start.x;
dy= s->end.y - s->control2.y*3 + s->control1.y*3 - s->start.y;
/* we need to do this for the subspline between [start,end], not [0,1]
as a transformation of t->a*t+b does nothing to highest coefficient
of the spline except multiply it with a^3, we just need to modify
d here. */
{double m = end-start;
dx*=m*m*m;
dy*=m*m*m;
}
/* use the integral over (f(x)-g(x))^2 between 0 and 1
to measure the approximation quality.
(it boils down to const*d^2)
*/
recurse = (dx*dx + dy*dy > quality2);
#endif
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)
{
struct qspline q[128];
struct cspline c;
//double quality = 80;
double maxerror = 1;//(500-(quality*5)>1?500-(quality*5):1)/20.0;
int t,num;
c.start.x = draw->pos.x;
c.start.y = draw->pos.y;
c.control1.x = control1->x;
c.control1.y = control1->y;
c.control2.x = control2->x;
c.control2.y = control2->y;
c.end.x = to->x;
c.end.y = to->y;
num = approximate3(&c, q, 128, maxerror*maxerror);
for(t=0;t<num;t++) {
FPOINT mid;
FPOINT to;
mid.x = q[t].control.x;
mid.y = q[t].control.y;
to.x = q[t].end.x;
to.y = q[t].end.y;
draw->splineTo(draw, &mid, &to);
}
}