root/src/shape_cubic.c
/* [<][>][^][v][top][bottom][index][help] */
DEFINITIONS
This source file includes following definitions.
- halfpointCubic
- halfpointQuadratic
- errorPoints
- subdivideCubicLeft
- subdivideCubicRight
- subdivideCubic
- SWFShape_approxCubic
- SWFShape_drawScaledCubicTo
- SWFShape_drawCubic
- SWFShape_drawCubicTo
/*
Ming, an SWF output library
Copyright (C) 2002 Opaque Industries - http://www.opaque.net/
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library 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
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
#ifndef __C2MAN__
#include <math.h>
#include <string.h>
#endif
#include "ming.h"
#include "libming.h"
#include "shape_util.h"
#include "blocks/error.h"
#include "blocks/shape.h"
typedef struct
{
double x;
double y;
} point;
typedef struct
{
point a;
point b;
point c;
point d;
} cubic;
typedef struct
{
point a;
point b;
point c;
} quadratic;
static void halfpointCubic(cubic *c, double *x, double *y)
{
*x = (c->a.x + 3*c->b.x + 3*c->c.x + c->d.x) / 8;
*y = (c->a.y + 3*c->b.y + 3*c->c.y + c->d.y) / 8;
}
static void halfpointQuadratic(quadratic *q, double *x, double *y)
{
*x = (q->a.x + 2*q->b.x + q->c.x) / 4;
*y = (q->a.y + 2*q->b.y + q->c.y) / 4;
}
#define abs(f) ((f)>0?(f):-(f))
static double errorPoints(double ax, double ay, double bx, double by)
{
return abs(ax-bx) + abs(ay-by);
}
static void subdivideCubicLeft(cubic *New, cubic *old, double t)
{
SWF_assert(t>0.0 && t<1.0);
if(New != old)
memcpy(New, old, sizeof(cubic));
New->d.x = t*New->c.x + (1-t)*New->d.x;
New->d.y = t*New->c.y + (1-t)*New->d.y;
New->c.x = t*New->b.x + (1-t)*New->c.x;
New->c.y = t*New->b.y + (1-t)*New->c.y;
New->b.x = t*New->a.x + (1-t)*New->b.x;
New->b.y = t*New->a.y + (1-t)*New->b.y;
New->d.x = t*New->c.x + (1-t)*New->d.x;
New->d.y = t*New->c.y + (1-t)*New->d.y;
New->c.x = t*New->b.x + (1-t)*New->c.x;
New->c.y = t*New->b.y + (1-t)*New->c.y;
New->d.x = t*New->c.x + (1-t)*New->d.x;
New->d.y = t*New->c.y + (1-t)*New->d.y;
}
static void subdivideCubicRight(cubic *New, cubic *old, double t)
{
SWF_assert(t>0.0 && t<1.0);
if(New != old)
memcpy(New, old, sizeof(cubic));
New->a.x = t*New->a.x + (1-t)*New->b.x;
New->a.y = t*New->a.y + (1-t)*New->b.y;
New->b.x = t*New->b.x + (1-t)*New->c.x;
New->b.y = t*New->b.y + (1-t)*New->c.y;
New->c.x = t*New->c.x + (1-t)*New->d.x;
New->c.y = t*New->c.y + (1-t)*New->d.y;
New->a.x = t*New->a.x + (1-t)*New->b.x;
New->a.y = t*New->a.y + (1-t)*New->b.y;
New->b.x = t*New->b.x + (1-t)*New->c.x;
New->b.y = t*New->b.y + (1-t)*New->c.y;
New->a.x = t*New->a.x + (1-t)*New->b.x;
New->a.y = t*New->a.y + (1-t)*New->b.y;
}
static int SWFShape_approxCubic(SWFShape shape, cubic *c);
static int subdivideCubic(SWFShape shape, cubic *c)
{
cubic New;
int nCurves;
subdivideCubicLeft(&New, c, 0.5);
nCurves = SWFShape_approxCubic(shape, &New);
subdivideCubicRight(&New, c, 0.5);
nCurves += SWFShape_approxCubic(shape, &New);
return nCurves;
}
static int SWFShape_approxCubic(SWFShape shape, cubic *c)
{
quadratic q;
double cx, cy, qx, qy;
if(c->b.x == c->a.x && c->b.y == c->a.y)
{
q.a = c->a;
q.b = c->c;
q.c = c->d;
}
else if(c->d.x == c->c.x && c->d.y == c->c.y)
{
q.a = c->a;
q.b = c->b;
q.c = c->d;
}
else
if((c->a.x-c->b.x)*(c->c.x-c->b.x)+(c->a.y-c->b.y)*(c->c.y-c->b.y) >= 0 ||
(c->b.x-c->c.x)*(c->d.x-c->c.x)+(c->b.y-c->c.y)*(c->d.y-c->c.y) >= 0)
{
/* make sure that angles B and C are obtuse, so that outside
edges meet on the right side */
return subdivideCubic(shape, c);
}
else
{
double bcrossa = c->b.x*c->a.y - c->a.x*c->b.y;
double ccrossd = c->c.x*c->d.y - c->d.x*c->c.y;
double denom = (c->a.y-c->b.y)*(c->d.x-c->c.x) -
(c->a.x-c->b.x)*(c->d.y-c->c.y);
if(denom == 0)
{
/* XXX - they're collinear?? */
SWFShape_drawScaledLineTo(shape, (int)rint(c->d.x), (int)rint(c->d.y));
return 1;
}
q.a = c->a;
q.b.x = ((c->d.x-c->c.x)*bcrossa + (c->b.x-c->a.x)*ccrossd) / denom;
q.b.y = ((c->d.y-c->c.y)*bcrossa + (c->b.y-c->a.y)*ccrossd) / denom;
q.c = c->d;
}
halfpointCubic(c, &cx, &cy);
halfpointQuadratic(&q, &qx, &qy);
if(errorPoints(cx, cy, qx, qy) > Ming_cubicThreshold)
{
return subdivideCubic(shape, c);
}
else
{
/* draw quadratic w/ control point at intersection of outside edges */
SWFShape_drawScaledCurveTo(shape, (int)rint(q.b.x), (int)rint(q.b.y),
(int)rint(q.c.x), (int)rint(q.c.y));
return 1;
}
}
int SWFShape_drawScaledCubicTo(SWFShape shape, int bx, int by,
int cx, int cy, int dx, int dy)
{
int ax = SWFShape_getScaledPenX(shape);
int ay = SWFShape_getScaledPenY(shape);
/* compute coefficients */
int a1x = -ax + 3*bx - 3*cx + dx;
int a1y = -ay + 3*by - 3*cy + dy;
int a2x = ax - 2*bx + cx;
int a2y = ay - 2*by + cy;
int a3x = -ax + bx;
int a3y = -ay + by;
double a = 6*(a2x*a1y-a2y*a1x);
double b = 6*(a3x*a1y-a3y*a1x);
double c = 2*(a3x*a2y-a3y*a2x);
/* First, chop at inflection points, where a*t^2 + b*t + c = 0 */
double d = b*b - 4*a*c;
double t1 = 0.0, t2 = 1.0;
int nCurves = 0;
cubic pts = { { ax, ay }, { bx, by }, {cx, cy }, { dx, dy } };
cubic New;
if ( d > 0 )
{
/* two roots */
t1 = (-b-sqrt(d))/(2*a);
t2 = (-b+sqrt(d))/(2*a);
if ( a < 0 )
{
double tmp = t2;
t2 = t1;
t1 = tmp;
}
}
else if ( d == 0 )
{
/* singular root */
t1 = -b/(2*a);
}
/* use subdivision method to build t=0..t1, t=t1..t2, t=t2..1 curves */
if ( t1 > 0.0 && t1 < 1.0 )
{
subdivideCubicLeft(&New, &pts, t1);
nCurves += SWFShape_approxCubic(shape, &New);
/*
nCurves += SWFShape_drawCubicTo(shape,
new.b.x, new.b.y,
new.c.x, new.c.y,
new.d.x, new.d.y);
*/
subdivideCubicRight(&pts, &pts, t1);
t2 = (t2-t1)/(1-t1);
}
if ( t2 > 0.0 && t2 < 1.0 )
{
subdivideCubicLeft(&New, &pts, t2);
nCurves += SWFShape_approxCubic(shape, &New);
/*
nCurves += SWFShape_drawCubicTo(shape,
new.b.x, new.b.y,
new.c.x, new.c.y,
new.d.x, new.d.y);
*/
subdivideCubicRight(&pts, &pts, t2);
}
nCurves += SWFShape_approxCubic(shape, &pts);
return nCurves;
}
/* returns number of splines used */
int
SWFShape_drawCubic(SWFShape shape, double bx, double by,
double cx, double cy, double dx, double dy)
{
int sax = SWFShape_getScaledPenX(shape);
int say = SWFShape_getScaledPenY(shape);
int sbx = (int)rint(bx*Ming_scale) + sax;
int sby = (int)rint(by*Ming_scale) + say;
int scx = (int)rint(cx*Ming_scale) + sbx;
int scy = (int)rint(cy*Ming_scale) + sby;
int sdx = (int)rint(dx*Ming_scale) + scx;
int sdy = (int)rint(dy*Ming_scale) + scy;
return SWFShape_drawScaledCubicTo(shape, sbx, sby, scx, scy, sdx, sdy);
}
int SWFShape_drawCubicTo(SWFShape shape, double bx, double by,
double cx, double cy, double dx, double dy)
{
return SWFShape_drawScaledCubicTo(shape,
(int)rint(bx*Ming_scale),
(int)rint(by*Ming_scale),
(int)rint(cx*Ming_scale),
(int)rint(cy*Ming_scale),
(int)rint(dx*Ming_scale),
(int)rint(dy*Ming_scale));
}
/*
* Local variables:
* tab-width: 2
* c-basic-offset: 2
* End:
*/