1 /*
2 Ming, an SWF output library
3 Copyright (C) 2002 Opaque Industries - http://www.opaque.net/
4
5 This library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
9
10 This library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with this library; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 */
19
20 #ifndef __C2MAN__
21 #include <math.h>
22 #include <string.h>
23 #endif
24
25 #include "ming.h"
26 #include "libming.h"
27 #include "shape_util.h"
28 #include "blocks/error.h"
29 #include "blocks/shape.h"
30
31
32 typedef struct
33 {
34 double x;
35 double y;
36 } point;
37
38 typedef struct
39 {
40 point a;
41 point b;
42 point c;
43 point d;
44 } cubic;
45
46 typedef struct
47 {
48 point a;
49 point b;
50 point c;
51 } quadratic;
52
halfpointCubic(cubic * c,double * x,double * y)53 static void halfpointCubic(cubic *c, double *x, double *y)
54 {
55 *x = (c->a.x + 3*c->b.x + 3*c->c.x + c->d.x) / 8;
56 *y = (c->a.y + 3*c->b.y + 3*c->c.y + c->d.y) / 8;
57 }
58
halfpointQuadratic(quadratic * q,double * x,double * y)59 static void halfpointQuadratic(quadratic *q, double *x, double *y)
60 {
61 *x = (q->a.x + 2*q->b.x + q->c.x) / 4;
62 *y = (q->a.y + 2*q->b.y + q->c.y) / 4;
63 }
64
65 #define abs(f) ((f)>0?(f):-(f))
66
errorPoints(double ax,double ay,double bx,double by)67 static double errorPoints(double ax, double ay, double bx, double by)
68 {
69 return abs(ax-bx) + abs(ay-by);
70 }
71
subdivideCubicLeft(cubic * New,cubic * old,double t)72 static void subdivideCubicLeft(cubic *New, cubic *old, double t)
73 {
74 SWF_assert(t>0.0 && t<1.0);
75
76 if(New != old)
77 memcpy(New, old, sizeof(cubic));
78
79 New->d.x = t*New->c.x + (1-t)*New->d.x;
80 New->d.y = t*New->c.y + (1-t)*New->d.y;
81 New->c.x = t*New->b.x + (1-t)*New->c.x;
82 New->c.y = t*New->b.y + (1-t)*New->c.y;
83 New->b.x = t*New->a.x + (1-t)*New->b.x;
84 New->b.y = t*New->a.y + (1-t)*New->b.y;
85
86 New->d.x = t*New->c.x + (1-t)*New->d.x;
87 New->d.y = t*New->c.y + (1-t)*New->d.y;
88 New->c.x = t*New->b.x + (1-t)*New->c.x;
89 New->c.y = t*New->b.y + (1-t)*New->c.y;
90
91 New->d.x = t*New->c.x + (1-t)*New->d.x;
92 New->d.y = t*New->c.y + (1-t)*New->d.y;
93 }
94
subdivideCubicRight(cubic * New,cubic * old,double t)95 static void subdivideCubicRight(cubic *New, cubic *old, double t)
96 {
97 SWF_assert(t>0.0 && t<1.0);
98
99 if(New != old)
100 memcpy(New, old, sizeof(cubic));
101
102 New->a.x = t*New->a.x + (1-t)*New->b.x;
103 New->a.y = t*New->a.y + (1-t)*New->b.y;
104 New->b.x = t*New->b.x + (1-t)*New->c.x;
105 New->b.y = t*New->b.y + (1-t)*New->c.y;
106 New->c.x = t*New->c.x + (1-t)*New->d.x;
107 New->c.y = t*New->c.y + (1-t)*New->d.y;
108
109 New->a.x = t*New->a.x + (1-t)*New->b.x;
110 New->a.y = t*New->a.y + (1-t)*New->b.y;
111 New->b.x = t*New->b.x + (1-t)*New->c.x;
112 New->b.y = t*New->b.y + (1-t)*New->c.y;
113
114 New->a.x = t*New->a.x + (1-t)*New->b.x;
115 New->a.y = t*New->a.y + (1-t)*New->b.y;
116 }
117
118 static int SWFShape_approxCubic(SWFShape shape, cubic *c);
119
subdivideCubic(SWFShape shape,cubic * c)120 static int subdivideCubic(SWFShape shape, cubic *c)
121 {
122 cubic New;
123 int nCurves;
124
125 subdivideCubicLeft(&New, c, 0.5);
126 nCurves = SWFShape_approxCubic(shape, &New);
127
128 subdivideCubicRight(&New, c, 0.5);
129 nCurves += SWFShape_approxCubic(shape, &New);
130
131 return nCurves;
132 }
133
SWFShape_approxCubic(SWFShape shape,cubic * c)134 static int SWFShape_approxCubic(SWFShape shape, cubic *c)
135 {
136 quadratic q;
137
138 double cx, cy, qx, qy;
139
140 if(c->b.x == c->a.x && c->b.y == c->a.y)
141 {
142 q.a = c->a;
143 q.b = c->c;
144 q.c = c->d;
145 }
146 else if(c->d.x == c->c.x && c->d.y == c->c.y)
147 {
148 q.a = c->a;
149 q.b = c->b;
150 q.c = c->d;
151 }
152 else
153 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 ||
154 (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)
155 {
156 /* make sure that angles B and C are obtuse, so that outside
157 edges meet on the right side */
158
159 return subdivideCubic(shape, c);
160 }
161 else
162 {
163 double bcrossa = c->b.x*c->a.y - c->a.x*c->b.y;
164 double ccrossd = c->c.x*c->d.y - c->d.x*c->c.y;
165
166 double denom = (c->a.y-c->b.y)*(c->d.x-c->c.x) -
167 (c->a.x-c->b.x)*(c->d.y-c->c.y);
168
169 if(denom == 0)
170 {
171 /* XXX - they're collinear?? */
172 SWFShape_drawScaledLineTo(shape, (int)rint(c->d.x), (int)rint(c->d.y));
173 return 1;
174 }
175
176 q.a = c->a;
177 q.b.x = ((c->d.x-c->c.x)*bcrossa + (c->b.x-c->a.x)*ccrossd) / denom;
178 q.b.y = ((c->d.y-c->c.y)*bcrossa + (c->b.y-c->a.y)*ccrossd) / denom;
179 q.c = c->d;
180 }
181
182 halfpointCubic(c, &cx, &cy);
183 halfpointQuadratic(&q, &qx, &qy);
184
185 if(errorPoints(cx, cy, qx, qy) > Ming_cubicThreshold)
186 {
187 return subdivideCubic(shape, c);
188 }
189 else
190 {
191 /* draw quadratic w/ control point at intersection of outside edges */
192
193 SWFShape_drawScaledCurveTo(shape, (int)rint(q.b.x), (int)rint(q.b.y),
194 (int)rint(q.c.x), (int)rint(q.c.y));
195 return 1;
196 }
197 }
198
199
SWFShape_drawScaledCubicTo(SWFShape shape,int bx,int by,int cx,int cy,int dx,int dy)200 int SWFShape_drawScaledCubicTo(SWFShape shape, int bx, int by,
201 int cx, int cy, int dx, int dy)
202 {
203 int ax = SWFShape_getScaledPenX(shape);
204 int ay = SWFShape_getScaledPenY(shape);
205
206 /* compute coefficients */
207 int a1x = -ax + 3*bx - 3*cx + dx;
208 int a1y = -ay + 3*by - 3*cy + dy;
209 int a2x = ax - 2*bx + cx;
210 int a2y = ay - 2*by + cy;
211 int a3x = -ax + bx;
212 int a3y = -ay + by;
213
214 double a = 6*(a2x*a1y-a2y*a1x);
215 double b = 6*(a3x*a1y-a3y*a1x);
216 double c = 2*(a3x*a2y-a3y*a2x);
217
218 /* First, chop at inflection points, where a*t^2 + b*t + c = 0 */
219
220 double d = b*b - 4*a*c;
221
222 double t1 = 0.0, t2 = 1.0;
223 int nCurves = 0;
224
225 cubic pts = { { ax, ay }, { bx, by }, {cx, cy }, { dx, dy } };
226 cubic New;
227
228 if ( d > 0 )
229 {
230 /* two roots */
231
232 t1 = (-b-sqrt(d))/(2*a);
233 t2 = (-b+sqrt(d))/(2*a);
234
235 if ( a < 0 )
236 {
237 double tmp = t2;
238 t2 = t1;
239 t1 = tmp;
240 }
241 }
242 else if ( d == 0 )
243 {
244 /* singular root */
245 t1 = -b/(2*a);
246 }
247
248 /* use subdivision method to build t=0..t1, t=t1..t2, t=t2..1 curves */
249
250 if ( t1 > 0.0 && t1 < 1.0 )
251 {
252 subdivideCubicLeft(&New, &pts, t1);
253
254 nCurves += SWFShape_approxCubic(shape, &New);
255
256 /*
257 nCurves += SWFShape_drawCubicTo(shape,
258 new.b.x, new.b.y,
259 new.c.x, new.c.y,
260 new.d.x, new.d.y);
261 */
262
263 subdivideCubicRight(&pts, &pts, t1);
264 t2 = (t2-t1)/(1-t1);
265 }
266
267 if ( t2 > 0.0 && t2 < 1.0 )
268 {
269 subdivideCubicLeft(&New, &pts, t2);
270
271 nCurves += SWFShape_approxCubic(shape, &New);
272
273 /*
274 nCurves += SWFShape_drawCubicTo(shape,
275 new.b.x, new.b.y,
276 new.c.x, new.c.y,
277 new.d.x, new.d.y);
278 */
279
280 subdivideCubicRight(&pts, &pts, t2);
281 }
282
283 nCurves += SWFShape_approxCubic(shape, &pts);
284
285 return nCurves;
286 }
287
288
289 /* returns number of splines used */
290
291 int
SWFShape_drawCubic(SWFShape shape,double bx,double by,double cx,double cy,double dx,double dy)292 SWFShape_drawCubic(SWFShape shape, double bx, double by,
293 double cx, double cy, double dx, double dy)
294 {
295 int sax = SWFShape_getScaledPenX(shape);
296 int say = SWFShape_getScaledPenY(shape);
297 int sbx = (int)rint(bx*Ming_scale) + sax;
298 int sby = (int)rint(by*Ming_scale) + say;
299 int scx = (int)rint(cx*Ming_scale) + sbx;
300 int scy = (int)rint(cy*Ming_scale) + sby;
301 int sdx = (int)rint(dx*Ming_scale) + scx;
302 int sdy = (int)rint(dy*Ming_scale) + scy;
303
304 return SWFShape_drawScaledCubicTo(shape, sbx, sby, scx, scy, sdx, sdy);
305 }
306
SWFShape_drawCubicTo(SWFShape shape,double bx,double by,double cx,double cy,double dx,double dy)307 int SWFShape_drawCubicTo(SWFShape shape, double bx, double by,
308 double cx, double cy, double dx, double dy)
309 {
310 return SWFShape_drawScaledCubicTo(shape,
311 (int)rint(bx*Ming_scale),
312 (int)rint(by*Ming_scale),
313 (int)rint(cx*Ming_scale),
314 (int)rint(cy*Ming_scale),
315 (int)rint(dx*Ming_scale),
316 (int)rint(dy*Ming_scale));
317 }
318
319
320 /*
321 * Local variables:
322 * tab-width: 2
323 * c-basic-offset: 2
324 * End:
325 */
326