Line data Source code
1 : /*
2 : * GPAC - Multimedia Framework C SDK
3 : *
4 : * Authors: Jean Le Feuvre
5 : * Copyright (c) Telecom ParisTech 2000-2012
6 : * All rights reserved
7 : *
8 : * This file is part of GPAC / common tools sub-project
9 : *
10 : * GPAC is free software; you can redistribute it and/or modify
11 : * it under the terms of the GNU Lesser General Public License as published by
12 : * the Free Software Foundation; either version 2, or (at your option)
13 : * any later version.
14 : *
15 : * GPAC is distributed in the hope that it will be useful,
16 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 : * GNU Lesser General Public License for more details.
19 : *
20 : * You should have received a copy of the GNU Lesser General Public
21 : * License along with this library; see the file COPYING. If not, write to
22 : * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
23 : *
24 : */
25 :
26 :
27 : #include <gpac/path2d.h>
28 :
29 : GF_EXPORT
30 29132 : GF_Path *gf_path_new()
31 : {
32 : GF_Path *gp;
33 29132 : GF_SAFEALLOC(gp, GF_Path);
34 29132 : if (!gp) return NULL;
35 29132 : gp->fineness = FIX_ONE;
36 29132 : return gp;
37 : }
38 :
39 : GF_EXPORT
40 10580 : void gf_path_reset(GF_Path *gp)
41 : {
42 : Fixed fineness;
43 : u32 flags;
44 10580 : if (!gp) return;
45 10580 : if (gp->contours) gf_free(gp->contours);
46 10580 : if (gp->tags) gf_free(gp->tags);
47 10580 : if (gp->points) gf_free(gp->points);
48 10580 : fineness = gp->fineness ? gp->fineness : FIX_ONE;
49 10580 : flags = gp->flags;
50 : memset(gp, 0, sizeof(GF_Path));
51 10580 : gp->flags = flags | GF_PATH_FLATTENED | GF_PATH_BBOX_DIRTY;
52 10580 : gp->fineness = fineness;
53 : }
54 :
55 : GF_EXPORT
56 2883 : GF_Path *gf_path_clone(GF_Path *gp)
57 : {
58 : GF_Path *dst;
59 2883 : GF_SAFEALLOC(dst, GF_Path);
60 2883 : if (!dst) return NULL;
61 2883 : dst->contours = (u32 *)gf_malloc(sizeof(u32)*gp->n_contours);
62 2883 : if (!dst->contours) {
63 0 : gf_free(dst);
64 0 : return NULL;
65 : }
66 2883 : dst->points = (GF_Point2D *) gf_malloc(sizeof(GF_Point2D)*gp->n_points);
67 2883 : if (!dst->points) {
68 0 : gf_free(dst->contours);
69 0 : gf_free(dst);
70 0 : return NULL;
71 : }
72 2883 : dst->tags = (u8 *) gf_malloc(sizeof(u8)*gp->n_points);
73 2883 : if (!dst->tags) {
74 0 : gf_free(dst->points);
75 0 : gf_free(dst->contours);
76 0 : gf_free(dst);
77 0 : return NULL;
78 : }
79 2883 : memcpy(dst->contours, gp->contours, sizeof(u32)*gp->n_contours);
80 2883 : dst->n_contours = gp->n_contours;
81 2883 : memcpy(dst->points, gp->points, sizeof(GF_Point2D)*gp->n_points);
82 2883 : memcpy(dst->tags, gp->tags, sizeof(u8)*gp->n_points);
83 2883 : dst->n_alloc_points = dst->n_points = gp->n_points;
84 2883 : dst->flags = gp->flags;
85 2883 : dst->bbox = gp->bbox;
86 2883 : dst->fineness = gp->fineness;
87 2883 : return dst;
88 : }
89 :
90 : GF_EXPORT
91 31335 : void gf_path_del(GF_Path *gp)
92 : {
93 31335 : if (!gp) return;
94 31335 : if (gp->contours) gf_free(gp->contours);
95 31335 : if (gp->tags) gf_free(gp->tags);
96 31335 : if (gp->points) gf_free(gp->points);
97 31335 : gf_free(gp);
98 : }
99 :
100 : #define GF_2D_REALLOC(_gp) \
101 : if (_gp->n_alloc_points < _gp->n_points+3) { \
102 : _gp->n_alloc_points = (_gp->n_alloc_points<5) ? 10 : (_gp->n_alloc_points*2); \
103 : _gp->points = (GF_Point2D *)gf_realloc(_gp->points, sizeof(GF_Point2D)*(_gp->n_alloc_points)); \
104 : _gp->tags = (u8 *) gf_realloc(_gp->tags, sizeof(u8)*(_gp->n_alloc_points)); \
105 : } \
106 :
107 :
108 : GF_EXPORT
109 65618 : GF_Err gf_path_add_move_to(GF_Path *gp, Fixed x, Fixed y)
110 : {
111 65618 : if (!gp) return GF_BAD_PARAM;
112 :
113 : #if 0
114 : /*skip empty paths*/
115 : if ((gp->n_contours>=2) && (gp->contours[gp->n_contours-2]+1==gp->contours[gp->n_contours-1])) {
116 : gp->points[gp->n_points].x = x;
117 : gp->points[gp->n_points].y = y;
118 : return GF_OK;
119 : }
120 : #endif
121 :
122 65618 : gp->contours = (u32 *) gf_realloc(gp->contours, sizeof(u32)*(gp->n_contours+1));
123 65618 : GF_2D_REALLOC(gp)
124 :
125 65618 : gp->points[gp->n_points].x = x;
126 65618 : gp->points[gp->n_points].y = y;
127 65618 : gp->tags[gp->n_points] = 1;
128 : /*set end point*/
129 65618 : gp->contours[gp->n_contours] = gp->n_points;
130 : /*new contour*/
131 65618 : gp->n_contours++;
132 65618 : gp->n_points++;
133 65618 : gp->flags |= GF_PATH_BBOX_DIRTY;
134 65618 : return GF_OK;
135 : }
136 :
137 : GF_EXPORT
138 31270 : GF_Err gf_path_add_move_to_vec(GF_Path *gp, GF_Point2D *pt) {
139 31270 : return gf_path_add_move_to(gp, pt->x, pt->y);
140 : }
141 :
142 : GF_EXPORT
143 1178940 : GF_Err gf_path_add_line_to(GF_Path *gp, Fixed x, Fixed y)
144 : {
145 1178940 : if (!gp || !gp->n_contours) return GF_BAD_PARAM;
146 : /*we allow line to same point as move (seen in SVG sequences) - striking will make a point*/
147 :
148 1178940 : GF_2D_REALLOC(gp)
149 1178940 : gp->points[gp->n_points].x = x;
150 1178940 : gp->points[gp->n_points].y = y;
151 1178940 : gp->tags[gp->n_points] = 1;
152 : /*set end point*/
153 1178940 : gp->contours[gp->n_contours-1] = gp->n_points;
154 1178940 : gp->n_points++;
155 1178940 : gp->flags |= GF_PATH_BBOX_DIRTY;
156 1178940 : return GF_OK;
157 : }
158 :
159 : GF_EXPORT
160 232599 : GF_Err gf_path_add_line_to_vec(GF_Path *gp, GF_Point2D *pt) {
161 232599 : return gf_path_add_line_to(gp, pt->x, pt->y);
162 : }
163 :
164 : GF_EXPORT
165 28917 : GF_Err gf_path_close(GF_Path *gp)
166 : {
167 : Fixed diff;
168 : GF_Point2D start, end;
169 28917 : if (!gp || !gp->n_contours) return GF_BAD_PARAM;
170 :
171 28915 : if (gp->n_contours<=1) start = gp->points[0];
172 11355 : else start = gp->points[gp->contours[gp->n_contours-2] + 1];
173 28915 : end = gp->points[gp->n_points-1];
174 28915 : end.x -= start.x;
175 28915 : end.y -= start.y;
176 28915 : diff = gf_mulfix(end.x, end.x) + gf_mulfix(end.y, end.y);
177 28915 : if (ABS(diff) > FIX_ONE/1000) {
178 9983 : GF_Err e = gf_path_add_line_to(gp, start.x, start.y);
179 9983 : if (e) return e;
180 : }
181 28915 : gp->tags[gp->n_points-1] = GF_PATH_CLOSE;
182 28915 : return GF_OK;
183 : }
184 :
185 : GF_EXPORT
186 10345 : GF_Err gf_path_add_cubic_to(GF_Path *gp, Fixed c1_x, Fixed c1_y, Fixed c2_x, Fixed c2_y, Fixed x, Fixed y)
187 : {
188 10345 : if (!gp || !gp->n_contours) return GF_BAD_PARAM;
189 10345 : GF_2D_REALLOC(gp)
190 10345 : gp->points[gp->n_points].x = c1_x;
191 10345 : gp->points[gp->n_points].y = c1_y;
192 10345 : gp->tags[gp->n_points] = GF_PATH_CURVE_CUBIC;
193 10345 : gp->n_points++;
194 10345 : gp->points[gp->n_points].x = c2_x;
195 10345 : gp->points[gp->n_points].y = c2_y;
196 10345 : gp->tags[gp->n_points] = GF_PATH_CURVE_CUBIC;
197 10345 : gp->n_points++;
198 10345 : gp->points[gp->n_points].x = x;
199 10345 : gp->points[gp->n_points].y = y;
200 10345 : gp->tags[gp->n_points] = GF_PATH_CURVE_ON;
201 : /*set end point*/
202 10345 : gp->contours[gp->n_contours-1] = gp->n_points;
203 10345 : gp->n_points++;
204 10345 : gp->flags |= GF_PATH_BBOX_DIRTY;
205 10345 : gp->flags &= ~GF_PATH_FLATTENED;
206 10345 : return GF_OK;
207 : }
208 :
209 : GF_EXPORT
210 54 : GF_Err gf_path_add_cubic_to_vec(GF_Path *gp, GF_Point2D *c1, GF_Point2D *c2, GF_Point2D *pt)
211 : {
212 54 : return gf_path_add_cubic_to(gp, c1->x, c1->y, c2->x, c2->y, pt->x, pt->y);
213 : }
214 :
215 :
216 : GF_EXPORT
217 87622 : GF_Err gf_path_add_quadratic_to(GF_Path *gp, Fixed c_x, Fixed c_y, Fixed x, Fixed y)
218 : {
219 87622 : if (!gp || !gp->n_contours) return GF_BAD_PARAM;
220 87622 : GF_2D_REALLOC(gp)
221 87622 : gp->points[gp->n_points].x = c_x;
222 87622 : gp->points[gp->n_points].y = c_y;
223 87622 : gp->tags[gp->n_points] = GF_PATH_CURVE_CONIC;
224 87622 : gp->n_points++;
225 87622 : gp->points[gp->n_points].x = x;
226 87622 : gp->points[gp->n_points].y = y;
227 87622 : gp->tags[gp->n_points] = GF_PATH_CURVE_ON;
228 : /*set end point*/
229 87622 : gp->contours[gp->n_contours-1] = gp->n_points;
230 87622 : gp->n_points++;
231 87622 : gp->flags |= GF_PATH_BBOX_DIRTY;
232 87622 : gp->flags &= ~GF_PATH_FLATTENED;
233 87622 : return GF_OK;
234 : }
235 : GF_EXPORT
236 3 : GF_Err gf_path_add_quadratic_to_vec(GF_Path *gp, GF_Point2D *c, GF_Point2D *pt)
237 : {
238 3 : return gf_path_add_quadratic_to(gp, c->x, c->y, pt->x, pt->y);
239 : }
240 :
241 : /*adds rectangle centered on cx, cy*/
242 : GF_EXPORT
243 1381 : GF_Err gf_path_add_rect_center(GF_Path *gp, Fixed cx, Fixed cy, Fixed w, Fixed h)
244 : {
245 1381 : GF_Err e = gf_path_add_move_to(gp, cx - w/2, cy - h/2);
246 1381 : if (e) return e;
247 1381 : e = gf_path_add_line_to(gp, cx + w/2, cy - h/2);
248 1381 : if (e) return e;
249 1381 : e = gf_path_add_line_to(gp, cx + w/2, cy + h/2);
250 1381 : if (e) return e;
251 1381 : e = gf_path_add_line_to(gp, cx - w/2, cy + h/2);
252 1381 : if (e) return e;
253 1381 : return gf_path_close(gp);
254 : }
255 :
256 : GF_EXPORT
257 167 : GF_Err gf_path_add_rect(GF_Path *gp, Fixed ox, Fixed oy, Fixed w, Fixed h)
258 : {
259 167 : GF_Err e = gf_path_add_move_to(gp, ox, oy);
260 167 : if (e) return e;
261 167 : e = gf_path_add_line_to(gp, ox + w, oy);
262 167 : if (e) return e;
263 167 : e = gf_path_add_line_to(gp, ox+w, oy-h);
264 167 : if (e) return e;
265 167 : e = gf_path_add_line_to(gp, ox, oy-h);
266 167 : if (e) return e;
267 167 : return gf_path_close(gp);
268 : }
269 :
270 : #define GF_2D_DEFAULT_RES 64
271 :
272 : GF_EXPORT
273 1845 : GF_Err gf_path_add_ellipse(GF_Path *gp, Fixed cx, Fixed cy, Fixed a_axis, Fixed b_axis)
274 : {
275 : GF_Err e;
276 : Fixed _vx, _vy, cur;
277 : u32 i;
278 1845 : a_axis /= 2;
279 1845 : b_axis /= 2;
280 1845 : e = gf_path_add_move_to(gp, cx+a_axis, cy);
281 1845 : if (e) return e;
282 116235 : for (i=1; i<GF_2D_DEFAULT_RES; i++) {
283 116235 : cur = GF_2PI*i/GF_2D_DEFAULT_RES;
284 116235 : _vx = gf_mulfix(a_axis, gf_cos(cur) );
285 116235 : _vy = gf_mulfix(b_axis, gf_sin(cur) );
286 116235 : e = gf_path_add_line_to(gp, _vx + cx, _vy + cy);
287 116235 : if (e) return e;
288 : }
289 1845 : return gf_path_close(gp);
290 : }
291 :
292 5320 : GF_Err gf_path_add_subpath(GF_Path *gp, GF_Path *src, GF_Matrix2D *mx)
293 : {
294 : u32 i;
295 5320 : if (!src) return GF_OK;
296 5320 : gp->contours = (u32*)gf_realloc(gp->contours, sizeof(u32) * (gp->n_contours + src->n_contours));
297 5320 : if (!gp->contours) return GF_OUT_OF_MEM;
298 8152 : for (i=0; i<src->n_contours; i++) {
299 8152 : gp->contours[i+gp->n_contours] = src->contours[i] + gp->n_points;
300 : }
301 5320 : gp->n_contours += src->n_contours;
302 5320 : gp->n_alloc_points += src->n_alloc_points;
303 5320 : gp->points = (GF_Point2D*)gf_realloc(gp->points, sizeof(GF_Point2D)*gp->n_alloc_points);
304 5320 : if (!gp->points) return GF_OUT_OF_MEM;
305 5320 : gp->tags = (u8*)gf_realloc(gp->tags, sizeof(u8)*gp->n_alloc_points);
306 5320 : if (!gp->tags) return GF_OUT_OF_MEM;
307 5320 : memcpy(gp->points + gp->n_points, src->points, sizeof(GF_Point2D)*src->n_points);
308 5320 : if (mx) {
309 276113 : for (i=0; i<src->n_points; i++) {
310 276113 : gf_mx2d_apply_coords(mx, &gp->points[i+gp->n_points].x, &gp->points[i+gp->n_points].y);
311 : }
312 : }
313 5320 : memcpy(gp->tags + gp->n_points, src->tags, sizeof(u8)*src->n_points);
314 5320 : gp->n_points += src->n_points;
315 5320 : gf_rect_union(&gp->bbox, &src->bbox);
316 5320 : if (!(src->flags & GF_PATH_FLATTENED)) gp->flags &= ~GF_PATH_FLATTENED;
317 5320 : if (src->flags & GF_PATH_BBOX_DIRTY) gp->flags |= GF_PATH_BBOX_DIRTY;
318 : return GF_OK;
319 : }
320 :
321 : /*generic N-bezier*/
322 1086 : static void NBezier(GF_Point2D *pts, s32 n, Double mu, GF_Point2D *pt_out)
323 : {
324 : s32 k,kn,nn,nkn;
325 : Double blend, muk, munk;
326 1086 : pt_out->x = pt_out->y = 0;
327 :
328 : muk = 1;
329 1086 : munk = pow(1-mu,(Double)n);
330 7293 : for (k=0; k<=n; k++) {
331 : nn = n;
332 : kn = k;
333 6207 : nkn = n - k;
334 6207 : blend = muk * munk;
335 6207 : muk *= mu;
336 6207 : munk /= (1-mu);
337 42030 : while (nn >= 1) {
338 29616 : blend *= nn;
339 29616 : nn--;
340 29616 : if (kn > 1) {
341 9687 : blend /= (double)kn;
342 9687 : kn--;
343 : }
344 29616 : if (nkn > 1) {
345 9687 : blend /= (double)nkn;
346 9687 : nkn--;
347 : }
348 : }
349 6207 : pt_out->x += gf_mulfix(pts[k].x, FLT2FIX(blend));
350 6207 : pt_out->y += gf_mulfix(pts[k].y, FLT2FIX(blend));
351 : }
352 1086 : }
353 :
354 34 : static void gf_add_n_bezier(GF_Path *gp, GF_Point2D *newpts, u32 nbPoints)
355 : {
356 : Double mu;
357 : u32 numPoints, i;
358 : GF_Point2D end;
359 34 : numPoints = (u32) FIX2INT(GF_2D_DEFAULT_RES * gp->fineness);
360 : mu = 0.0;
361 34 : if (numPoints) mu = 1/(Double)numPoints;
362 1120 : for (i=1; i<numPoints; i++) {
363 1086 : NBezier(newpts, nbPoints - 1, i*mu, &end);
364 1086 : gf_path_add_line_to(gp, end.x, end.y);
365 : }
366 34 : gf_path_add_line_to(gp, newpts[nbPoints-1].x, newpts[nbPoints-1].y);
367 34 : }
368 :
369 : GF_EXPORT
370 34 : GF_Err gf_path_add_bezier(GF_Path *gp, GF_Point2D *pts, u32 nbPoints)
371 : {
372 : GF_Point2D *newpts;
373 34 : if (!gp->n_points) return GF_BAD_PARAM;
374 :
375 34 : newpts = (GF_Point2D *) gf_malloc(sizeof(GF_Point2D) * (nbPoints+1));
376 34 : newpts[0] = gp->points[gp->n_points-1];
377 34 : memcpy(&newpts[1], pts, sizeof(GF_Point2D) * nbPoints);
378 :
379 34 : gf_add_n_bezier(gp, newpts, nbPoints + 1);
380 :
381 34 : gf_free(newpts);
382 34 : return GF_OK;
383 : }
384 :
385 : GF_EXPORT
386 9 : GF_Err gf_path_add_arc_to(GF_Path *gp, Fixed end_x, Fixed end_y, Fixed fa_x, Fixed fa_y, Fixed fb_x, Fixed fb_y, Bool cw)
387 : {
388 : GF_Matrix2D mat, inv;
389 : Fixed angle, start_angle, end_angle, sweep, axis_w, axis_h, tmp, cx, cy, _vx, _vy, start_x, start_y;
390 : s32 i, num_steps;
391 :
392 9 : if (!gp->n_points) return GF_BAD_PARAM;
393 :
394 9 : start_x = gp->points[gp->n_points-1].x;
395 9 : start_y = gp->points[gp->n_points-1].y;
396 :
397 9 : cx = (fb_x + fa_x)/2;
398 9 : cy = (fb_y + fa_y)/2;
399 :
400 9 : angle = gf_atan2(fb_y-fa_y, fb_x-fa_x);
401 9 : gf_mx2d_init(mat);
402 9 : gf_mx2d_add_rotation(&mat, 0, 0, angle);
403 9 : gf_mx2d_add_translation(&mat, cx, cy);
404 :
405 : gf_mx2d_copy(inv, mat);
406 9 : gf_mx2d_inverse(&inv);
407 9 : gf_mx2d_apply_coords(&inv, &start_x, &start_y);
408 9 : gf_mx2d_apply_coords(&inv, &end_x, &end_y);
409 9 : gf_mx2d_apply_coords(&inv, &fa_x, &fa_y);
410 9 : gf_mx2d_apply_coords(&inv, &fb_x, &fb_y);
411 :
412 : //start angle and end angle
413 9 : start_angle = gf_atan2(start_y, start_x);
414 9 : end_angle = gf_atan2(end_y, end_x);
415 9 : tmp = gf_mulfix((start_x - fa_x), (start_x - fa_x)) + gf_mulfix((start_y - fa_y), (start_y - fa_y));
416 9 : axis_w = gf_sqrt(tmp);
417 9 : tmp = gf_mulfix((start_x - fb_x) , (start_x - fb_x)) + gf_mulfix((start_y - fb_y), (start_y - fb_y));
418 9 : axis_w += gf_sqrt(tmp);
419 9 : axis_w /= 2;
420 9 : axis_h = gf_sqrt(gf_mulfix(axis_w, axis_w) - gf_mulfix(fa_x,fa_x));
421 9 : sweep = end_angle - start_angle;
422 :
423 9 : if (cw) {
424 2 : if (sweep>0) sweep -= 2*GF_PI;
425 : } else {
426 7 : if (sweep<0) sweep += 2*GF_PI;
427 : }
428 : num_steps = GF_2D_DEFAULT_RES/2;
429 297 : for (i=1; i<=num_steps; i++) {
430 288 : angle = start_angle + sweep*i/num_steps;
431 288 : _vx = gf_mulfix(axis_w, gf_cos(angle));
432 288 : _vy = gf_mulfix(axis_h, gf_sin(angle));
433 : /*re-invert*/
434 288 : gf_mx2d_apply_coords(&mat, &_vx, &_vy);
435 288 : gf_path_add_line_to(gp, _vx, _vy);
436 : }
437 : return GF_OK;
438 : }
439 :
440 :
441 :
442 : GF_EXPORT
443 4 : GF_Err gf_path_add_svg_arc_to(GF_Path *gp, Fixed end_x, Fixed end_y, Fixed r_x, Fixed r_y, Fixed x_axis_rotation, Bool large_arc_flag, Bool sweep_flag)
444 : {
445 : Fixed start_x, start_y;
446 : Fixed xmid,ymid;
447 : Fixed xmidp,ymidp;
448 : Fixed xmidpsq,ymidpsq;
449 : Fixed phi, cos_phi, sin_phi;
450 : Fixed c_x, c_y;
451 : Fixed cxp, cyp;
452 : Fixed scale;
453 : Fixed rxsq, rysq;
454 : Fixed start_angle, sweep_angle;
455 : Fixed radius_scale;
456 : Fixed vx, vy, normv;
457 : Fixed ux, uy, normu;
458 : Fixed sign;
459 : u32 i, num_steps;
460 :
461 4 : if (!gp->n_points) return GF_BAD_PARAM;
462 :
463 4 : if (!r_x || !r_y) {
464 1 : gf_path_add_line_to(gp, end_x, end_y);
465 1 : return GF_OK;
466 : }
467 :
468 3 : if (r_x < 0) r_x = -r_x;
469 3 : if (r_y < 0) r_y = -r_y;
470 :
471 3 : start_x = gp->points[gp->n_points-1].x;
472 3 : start_y = gp->points[gp->n_points-1].y;
473 :
474 3 : phi = gf_mulfix(x_axis_rotation/180, GF_PI);
475 3 : cos_phi = gf_cos(phi);
476 3 : sin_phi = gf_sin(phi);
477 3 : xmid = (start_x - end_x)/2;
478 3 : ymid = (start_y - end_y)/2;
479 3 : if (!xmid && !ymid) {
480 1 : gf_path_add_line_to(gp, end_x, end_y);
481 1 : return GF_OK;
482 : }
483 :
484 2 : xmidp = gf_mulfix(cos_phi, xmid) + gf_mulfix(sin_phi, ymid);
485 2 : ymidp = gf_mulfix(-sin_phi, xmid) + gf_mulfix(cos_phi, ymid);
486 2 : xmidpsq = gf_mulfix(xmidp, xmidp);
487 2 : ymidpsq = gf_mulfix(ymidp, ymidp);
488 :
489 2 : rxsq = gf_mulfix(r_x, r_x);
490 2 : rysq = gf_mulfix(r_y, r_y);
491 : assert(rxsq && rysq);
492 :
493 2 : radius_scale = gf_divfix(xmidpsq, rxsq) + gf_divfix(ymidpsq, rysq);
494 2 : if (radius_scale > FIX_ONE) {
495 0 : r_x = gf_mulfix(gf_sqrt(radius_scale), r_x);
496 0 : r_y = gf_mulfix(gf_sqrt(radius_scale), r_y);
497 0 : rxsq = gf_mulfix(r_x, r_x);
498 0 : rysq = gf_mulfix(r_y, r_y);
499 : }
500 :
501 : #if 0
502 : /* Old code with overflow problems in fixed point,
503 : sign was sometimes negative (cf tango SVG icons appointment-new.svg)*/
504 :
505 : sign = gf_mulfix(rxsq,ymidpsq) + gf_mulfix(rysq, xmidpsq);
506 : scale = FIX_ONE;
507 : /*FIXME - what if scale is 0 ??*/
508 : if (sign) scale = gf_divfix(
509 : (gf_mulfix(rxsq,rysq) - gf_mulfix(rxsq, ymidpsq) - gf_mulfix(rysq,xmidpsq)),
510 : sign
511 : );
512 : #else
513 : /* New code: the sign variable computation is split into simpler cases and
514 : the expression is divided by rxsq to reduce the range */
515 2 : if ((rxsq == 0 || ymidpsq ==0) && (rysq == 0 || xmidpsq == 0)) {
516 : scale = FIX_ONE;
517 2 : } else if (rxsq == 0 || ymidpsq ==0) {
518 1 : scale = gf_divfix(rxsq,xmidpsq) - FIX_ONE;
519 1 : } else if (rysq == 0 || xmidpsq == 0) {
520 0 : scale = gf_divfix(rysq,ymidpsq) - FIX_ONE;
521 : } else {
522 : Fixed tmp;
523 1 : tmp = gf_mulfix(gf_divfix(rysq, rxsq), xmidpsq);
524 1 : sign = ymidpsq + tmp;
525 1 : scale = gf_divfix((rysq - ymidpsq - tmp),sign);
526 : }
527 : #endif
528 : /* precision problem may lead to negative value around zero, we need to take care of it before sqrt */
529 2 : scale = gf_sqrt(ABS(scale));
530 :
531 2 : cxp = gf_mulfix(scale, gf_divfix(gf_mulfix(r_x, ymidp),r_y));
532 2 : cyp = gf_mulfix(scale, -gf_divfix(gf_mulfix(r_y, xmidp),r_x));
533 2 : cxp = (large_arc_flag == sweep_flag ? - cxp : cxp);
534 2 : cyp = (large_arc_flag == sweep_flag ? - cyp : cyp);
535 :
536 2 : c_x = gf_mulfix(cos_phi, cxp) - gf_mulfix(sin_phi, cyp) + (start_x + end_x)/2;
537 2 : c_y = gf_mulfix(sin_phi, cxp) + gf_mulfix(cos_phi, cyp) + (start_y + end_y)/2;
538 :
539 2 : vx = gf_divfix(xmidp-cxp,r_x);
540 2 : vy = gf_divfix(ymidp-cyp,r_y);
541 2 : normv = gf_sqrt(gf_mulfix(vx, vx) + gf_mulfix(vy,vy));
542 :
543 : sign = vy;
544 2 : start_angle = gf_acos(gf_divfix(vx,normv));
545 2 : start_angle = (sign > 0 ? start_angle: -start_angle);
546 :
547 : ux = vx;
548 : uy = vy;
549 :
550 2 : vx = gf_divfix(-xmidp-cxp,r_x);
551 2 : vy = gf_divfix(-ymidp-cyp,r_y);
552 2 : normu = gf_sqrt(gf_mulfix(ux, ux) + gf_mulfix(uy,uy));
553 :
554 2 : sign = gf_mulfix(ux, vy) - gf_mulfix(uy, vx);
555 2 : sweep_angle = gf_divfix( gf_mulfix(ux,vx) + gf_mulfix(uy, vy), gf_mulfix(normu, normv) );
556 : /*numerical stability safety*/
557 2 : sweep_angle = MAX(-FIX_ONE, MIN(sweep_angle, FIX_ONE));
558 2 : sweep_angle = gf_acos(sweep_angle);
559 2 : sweep_angle = (sign > 0 ? sweep_angle: -sweep_angle);
560 2 : if (sweep_flag == 0) {
561 2 : if (sweep_angle > 0) sweep_angle -= GF_2PI;
562 : } else {
563 0 : if (sweep_angle < 0) sweep_angle += GF_2PI;
564 : }
565 :
566 : num_steps = GF_2D_DEFAULT_RES/2;
567 66 : for (i=1; i<=num_steps; i++) {
568 : Fixed _vx, _vy;
569 : Fixed _vxp, _vyp;
570 64 : Fixed angle = start_angle + sweep_angle*(s32)i/(s32)num_steps;
571 64 : _vx = gf_mulfix(r_x, gf_cos(angle));
572 64 : _vy = gf_mulfix(r_y, gf_sin(angle));
573 64 : _vxp = gf_mulfix(cos_phi, _vx) - gf_mulfix(sin_phi, _vy) + c_x;
574 64 : _vyp = gf_mulfix(sin_phi, _vx) + gf_mulfix(cos_phi, _vy) + c_y;
575 64 : gf_path_add_line_to(gp, _vxp, _vyp);
576 : }
577 : return GF_OK;
578 : }
579 :
580 : GF_EXPORT
581 3 : GF_Err gf_path_add_arc(GF_Path *gp, Fixed radius, Fixed start_angle, Fixed end_angle, GF_Path2DArcCloseType close_type)
582 : {
583 : GF_Err e;
584 : Fixed _vx, _vy, step, cur;
585 : s32 i, do_run;
586 :
587 3 : step = (end_angle - start_angle) / (GF_2D_DEFAULT_RES);
588 3 : radius *= 2;
589 :
590 : /*pie*/
591 : i=0;
592 3 : if (close_type==GF_PATH2D_ARC_PIE) {
593 0 : gf_path_add_move_to(gp, 0, 0);
594 : i=1;
595 : }
596 : do_run = 1;
597 : cur=start_angle;
598 200 : while (do_run) {
599 197 : if (cur>=end_angle) {
600 : do_run = 0;
601 : cur = end_angle;
602 : }
603 197 : _vx = gf_mulfix(radius, gf_cos(cur));
604 197 : _vy = gf_mulfix(radius, gf_sin(cur));
605 197 : if (!i) {
606 3 : e = gf_path_add_move_to(gp, _vx, _vy);
607 : i = 1;
608 : } else {
609 194 : e = gf_path_add_line_to(gp, _vx, _vy);
610 : }
611 197 : if (e) return e;
612 197 : cur+=step;
613 : }
614 3 : if (close_type!=GF_PATH2D_ARC_OPEN) e = gf_path_close(gp);
615 : return e;
616 : }
617 :
618 :
619 : GF_EXPORT
620 23738 : GF_Err gf_path_get_control_bounds(GF_Path *gp, GF_Rect *rc)
621 : {
622 : GF_Point2D *pt, *end;
623 : Fixed xMin, xMax, yMin, yMax;
624 23738 : if (!gp || !rc) return GF_BAD_PARAM;
625 :
626 23738 : if (!gp->n_points) {
627 6 : rc->x = rc->y = rc->width = rc->height = 0;
628 6 : return GF_OK;
629 : }
630 23732 : pt = gp->points;
631 23732 : end = pt + gp->n_points;
632 23732 : xMin = xMax = pt->x;
633 23732 : yMin = yMax = pt->y;
634 23732 : pt++;
635 2302374 : for ( ; pt < end; pt++ ) {
636 : Fixed v;
637 2278642 : v = pt->x;
638 2278642 : if (v < xMin) xMin = v;
639 2278642 : if (v > xMax) xMax = v;
640 2278642 : v = pt->y;
641 2278642 : if (v < yMin) yMin = v;
642 2278642 : if (v > yMax) yMax = v;
643 : }
644 23732 : rc->x = xMin;
645 23732 : rc->y = yMax;
646 23732 : rc->width = xMax - xMin;
647 23732 : rc->height = yMax - yMin;
648 :
649 : #if 0
650 : /*take care of straight line path by adding a default width if height and vice-versa*/
651 : if (rc->height && !rc->width) {
652 : rc->width = 2*FIX_ONE;
653 : rc->x -= FIX_ONE;
654 : }
655 : else if (!rc->height && rc->width) {
656 : rc->height = 2*FIX_ONE;
657 : rc->y += FIX_ONE;
658 : }
659 : #endif
660 23732 : return GF_OK;
661 : }
662 :
663 : /*
664 : * conic bbox computing taken from freetype
665 : * Copyright 1996-2001, 2002, 2004 by
666 : * David Turner, Robert Wilhelm, and Werner Lemberg.
667 : * License: FTL or GPL
668 : */
669 1205 : static void gf_conic_check(Fixed y1, Fixed y2, Fixed y3, Fixed *min, Fixed *max)
670 : {
671 : /* flat arc */
672 1205 : if ((y1 <= y3) && (y2 == y1)) goto Suite;
673 :
674 1205 : if ( y1 < y3 ) {
675 : /* ascending arc */
676 687 : if ((y2 >= y1) && (y2 <= y3)) goto Suite;
677 : } else {
678 : /* descending arc */
679 518 : if ((y2 >= y3) && (y2 <= y1)) {
680 : y2 = y1;
681 : y1 = y3;
682 : y3 = y2;
683 : goto Suite;
684 : }
685 : }
686 1205 : y1 = y3 = y1 - gf_muldiv(y2 - y1, y2 - y1, y1 - 2*y2 + y3);
687 :
688 1205 : Suite:
689 1205 : if ( y1 < *min ) *min = y1;
690 1205 : if ( y3 > *max ) *max = y3;
691 1205 : }
692 :
693 :
694 : /*
695 : * cubic bbox computing taken from freetype
696 : * Copyright 1996-2001, 2002, 2004 by
697 : * David Turner, Robert Wilhelm, and Werner Lemberg.
698 : * License: FTL or GPL
699 :
700 : * Note: we're using the decomposition method, not the equation one which is not usable with Floats (only 16.16 fixed)
701 : */
702 3058 : static void gf_cubic_check(Fixed p1, Fixed p2, Fixed p3, Fixed p4, Fixed *min, Fixed *max)
703 : {
704 : Fixed stack[32*3 + 1], *arc;
705 : arc = stack;
706 3058 : arc[0] = p1;
707 3058 : arc[1] = p2;
708 3058 : arc[2] = p3;
709 3058 : arc[3] = p4;
710 :
711 : do {
712 69356 : Fixed y1 = arc[0];
713 69356 : Fixed y2 = arc[1];
714 69356 : Fixed y3 = arc[2];
715 69356 : Fixed y4 = arc[3];
716 :
717 69356 : if (ABS(y1)<FIX_EPSILON) arc[0] = y1 = 0;
718 69356 : if (ABS(y2)<FIX_EPSILON) arc[1] = y2 = 0;
719 69356 : if (ABS(y3)<FIX_EPSILON) arc[2] = y3 = 0;
720 69356 : if (ABS(y4)<FIX_EPSILON) arc[3] = y4 = 0;
721 :
722 69356 : if ( y1 == y4 ) {
723 : /* flat */
724 1691 : if ((y1 == y2) && (y1 == y3)) goto Test;
725 : }
726 67665 : else if ( y1 < y4 ) {
727 : /* ascending */
728 34307 : if ((y2 >= y1) && (y2 <= y4) && (y3 >= y1) && (y3 <= y4)) goto Test;
729 : } else {
730 : /* descending */
731 33358 : if ((y2 >= y4) && (y2 <= y1) && (y3 >= y4) && (y3 <= y1)) {
732 : y2 = y1;
733 : y1 = y4;
734 : y4 = y2;
735 : goto Test;
736 : }
737 : }
738 : /* unknown direction -- split the arc in two */
739 33149 : arc[6] = y4;
740 33149 : arc[1] = y1 = ( y1 + y2 ) / 2;
741 33149 : arc[5] = y4 = ( y4 + y3 ) / 2;
742 33149 : y2 = ( y2 + y3 ) / 2;
743 33149 : arc[2] = y1 = ( y1 + y2 ) / 2;
744 33149 : arc[4] = y4 = ( y4 + y2 ) / 2;
745 33149 : arc[3] = ( y1 + y4 ) / 2;
746 :
747 33149 : arc += 3;
748 33149 : goto Suite;
749 :
750 18834 : Test:
751 36207 : if ( y1 < *min ) *min = y1;
752 36207 : if ( y4 > *max ) *max = y4;
753 36207 : arc -= 3;
754 69356 : Suite:
755 : ;
756 : }
757 69356 : while ( arc >= stack );
758 3058 : }
759 :
760 :
761 : GF_EXPORT
762 879045 : GF_Err gf_path_get_bounds(GF_Path *gp, GF_Rect *rc)
763 : {
764 : u32 i;
765 : GF_Point2D *pt, *end;
766 : Fixed xMin, xMax, yMin, yMax, cxMin, cxMax, cyMin, cyMax;
767 879045 : if (!gp || !rc) return GF_BAD_PARAM;
768 :
769 879045 : if (!(gp->flags & GF_PATH_BBOX_DIRTY)) {
770 853327 : *rc = gp->bbox;
771 853327 : return GF_OK;
772 : }
773 : /*no curves in path*/
774 25718 : if (gp->flags & GF_PATH_FLATTENED) {
775 : GF_Err e;
776 23738 : gp->flags &= ~GF_PATH_BBOX_DIRTY;
777 23738 : e = gf_path_get_control_bounds(gp, &gp->bbox);
778 23738 : *rc = gp->bbox;
779 23738 : return e;
780 : }
781 :
782 1980 : gp->flags &= ~GF_PATH_BBOX_DIRTY;
783 :
784 1980 : if (!gp->n_points) {
785 0 : gp->bbox.x = gp->bbox.y = gp->bbox.width = gp->bbox.height = 0;
786 0 : *rc = gp->bbox;
787 0 : return GF_OK;
788 : }
789 1980 : pt = gp->points;
790 1980 : xMin = xMax = cxMin = cxMax = pt->x;
791 1980 : yMin = yMax = cyMin = cyMax = pt->y;
792 1980 : pt++;
793 165754 : for (i=1 ; i < gp->n_points; i++ ) {
794 : Fixed x, y;
795 163774 : x = pt->x;
796 163774 : y = pt->y;
797 163774 : if (x < cxMin) cxMin = x;
798 163774 : if (x > cxMax) cxMax = x;
799 163774 : if (y < cyMin) cyMin = y;
800 163774 : if (y > cyMax) cyMax = y;
801 : /*point on curve, update*/
802 163774 : if (gp->tags[i] & GF_PATH_CURVE_ON) {
803 141425 : if (x < xMin) xMin = x;
804 141425 : if (x > xMax) xMax = x;
805 141425 : if (y < yMin) yMin = y;
806 141425 : if (y > yMax) yMax = y;
807 : }
808 163774 : pt++;
809 : }
810 :
811 : /*control box is bigger than box , decompose curves*/
812 1980 : if ((cxMin < xMin) || (cxMax > xMax) || (cyMin < yMin) || (cyMax > yMax)) {
813 : GF_Point2D *ctrl1, *ctrl2;
814 : /*decompose all control points*/
815 : pt = gp->points;
816 61410 : for (i=1 ; i < gp->n_points; ) {
817 59868 : switch (gp->tags[i]) {
818 50172 : case GF_PATH_CURVE_ON:
819 : case GF_PATH_CLOSE:
820 50172 : pt = &gp->points[i];
821 50172 : i++;
822 50172 : break;
823 2585 : case GF_PATH_CURVE_CONIC:
824 : /*decompose*/
825 2585 : ctrl1 = &gp->points[i];
826 2585 : end = &gp->points[i+1];
827 2585 : if ((ctrl1->x < xMin) || (ctrl1->x > xMax))
828 611 : gf_conic_check(pt->x, ctrl1->x, end->x, &xMin, &xMax);
829 :
830 2585 : if ((ctrl1->y < yMin) || (ctrl1->y > yMax))
831 594 : gf_conic_check(pt->y, ctrl1->y, end->y, &yMin, &yMax);
832 :
833 : /*and move*/
834 : pt = end;
835 2585 : i+=2;
836 2585 : break;
837 7111 : case GF_PATH_CURVE_CUBIC:
838 : /*decompose*/
839 7111 : ctrl1 = &gp->points[i];
840 7111 : ctrl2 = &gp->points[i+1];
841 7111 : end = &gp->points[i+2];
842 7111 : if ((ctrl1->x < xMin) || (ctrl1->x > xMax) || (ctrl2->x < xMin) || (ctrl2->x > xMax))
843 1498 : gf_cubic_check(pt->x, ctrl1->x, ctrl2->x, end->x, &xMin, &xMax);
844 :
845 7111 : if ((ctrl1->y < yMin) || (ctrl1->y > yMax) || (ctrl2->y < yMin) || (ctrl2->y > yMax))
846 1560 : gf_cubic_check(pt->y, ctrl1->y, ctrl2->y, end->y, &yMin, &yMax);
847 :
848 : /*and move*/
849 : pt = end;
850 7111 : i+=3;
851 7111 : break;
852 : }
853 : }
854 : }
855 1980 : gp->bbox.x = xMin;
856 1980 : gp->bbox.y = yMax;
857 1980 : gp->bbox.width = xMax - xMin;
858 1980 : gp->bbox.height = yMax - yMin;
859 1980 : *rc = gp->bbox;
860 1980 : return GF_OK;
861 : }
862 :
863 : /*flattening algo taken from libart but passed to sqrt tests for line distance to avoid 16.16 fixed overflow*/
864 1280645 : static GF_Err gf_subdivide_cubic(GF_Path *gp, Fixed x0, Fixed y0, Fixed x1, Fixed y1, Fixed x2, Fixed y2, Fixed x3, Fixed y3, Fixed fineness)
865 : {
866 : GF_Point2D pt;
867 : Fixed x3_0, y3_0, z3_0, z1_0, z1_dot, z2_dot, z1_perp, z2_perp;
868 : Fixed max_perp;
869 : Fixed x_m, y_m, xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2;
870 : GF_Err e;
871 :
872 1280645 : pt.x = x3_0 = x3 - x0;
873 1280645 : pt.y = y3_0 = y3 - y0;
874 :
875 : /*z3_0 is dist z0-z3*/
876 1280645 : z3_0 = gf_v2d_len(&pt);
877 :
878 1280645 : pt.x = x1 - x0;
879 1280645 : pt.y = y1 - y0;
880 1280645 : z1_0 = gf_v2d_len(&pt);
881 :
882 1280645 : if ((z3_0*100 < FIX_ONE) && (z1_0*100 < FIX_ONE))
883 : goto nosubdivide;
884 :
885 : /* perp is distance from line, multiplied by dist z0-z3 */
886 1277057 : max_perp = gf_mulfix(fineness, z3_0);
887 :
888 1277057 : z1_perp = gf_mulfix((y1 - y0), x3_0) - gf_mulfix((x1 - x0), y3_0);
889 1277057 : if (ABS(z1_perp) > max_perp)
890 : goto subdivide;
891 :
892 747541 : z2_perp = gf_mulfix((y3 - y2), x3_0) - gf_mulfix((x3 - x2), y3_0);
893 747541 : if (ABS(z2_perp) > max_perp)
894 : goto subdivide;
895 :
896 739465 : z1_dot = gf_mulfix((x1 - x0), x3_0) + gf_mulfix((y1 - y0), y3_0);
897 739465 : if ((z1_dot < 0) && (ABS(z1_dot) > max_perp))
898 : goto subdivide;
899 :
900 739458 : z2_dot = gf_mulfix((x3 - x2), x3_0) + gf_mulfix((y3 - y2), y3_0);
901 739458 : if ((z2_dot < 0) && (ABS(z2_dot) > max_perp))
902 : goto subdivide;
903 :
904 739443 : if (gf_divfix(z1_dot + z1_dot, z3_0) > z3_0)
905 : goto subdivide;
906 :
907 734839 : if (gf_divfix(z2_dot + z2_dot, z3_0) > z3_0)
908 : goto subdivide;
909 :
910 731815 : nosubdivide:
911 : /* don't subdivide */
912 731815 : return gf_path_add_line_to(gp, x3, y3);
913 :
914 548830 : subdivide:
915 548830 : xa1 = (x0 + x1) / 2;
916 548830 : ya1 = (y0 + y1) / 2;
917 548830 : xa2 = (x0 + 2 * x1 + x2) / 4;
918 548830 : ya2 = (y0 + 2 * y1 + y2) / 4;
919 548830 : xb1 = (x1 + 2 * x2 + x3) / 4;
920 548830 : yb1 = (y1 + 2 * y2 + y3) / 4;
921 548830 : xb2 = (x2 + x3) / 2;
922 548830 : yb2 = (y2 + y3) / 2;
923 548830 : x_m = (xa2 + xb1) / 2;
924 548830 : y_m = (ya2 + yb1) / 2;
925 : /*safeguard for numerical stability*/
926 548830 : if ( (ABS(x_m-x0) < FIX_EPSILON) && (ABS(y_m-y0) < FIX_EPSILON))
927 0 : return gf_path_add_line_to(gp, x3, y3);
928 548830 : if ( (ABS(x3-x_m) < FIX_EPSILON) && (ABS(y3-y_m) < FIX_EPSILON))
929 0 : return gf_path_add_line_to(gp, x3, y3);
930 :
931 548830 : e = gf_subdivide_cubic(gp, x0, y0, xa1, ya1, xa2, ya2, x_m, y_m, fineness);
932 548830 : if (e) return e;
933 548830 : return gf_subdivide_cubic(gp, x_m, y_m, xb1, yb1, xb2, yb2, x3, y3, fineness);
934 : }
935 :
936 : GF_EXPORT
937 7788 : GF_Path *gf_path_get_flatten(GF_Path *gp)
938 : {
939 : GF_Path *ngp;
940 : Fixed fineness;
941 : u32 i, *countour;
942 : GF_Point2D *pt;
943 7788 : if (!gp || !gp->n_points) return NULL;
944 :
945 7788 : if (gp->flags & GF_PATH_FLATTENED) return gf_path_clone(gp);
946 :
947 : /*avoid too high precision */
948 6759 : fineness = MAX(FIX_ONE - gp->fineness, FIX_ONE / 100);
949 :
950 6759 : ngp = gf_path_new();
951 6759 : pt = &gp->points[0];
952 6759 : gf_path_add_move_to_vec(ngp, pt);
953 6759 : countour = gp->contours;
954 406409 : for (i=1; i<gp->n_points; ) {
955 392891 : switch (gp->tags[i]) {
956 209906 : case GF_PATH_CURVE_ON:
957 : case GF_PATH_CLOSE:
958 209906 : pt = &gp->points[i];
959 209906 : if (*countour == i-1) {
960 23833 : gf_path_add_move_to_vec(ngp, pt);
961 23833 : countour++;
962 : } else {
963 186073 : gf_path_add_line_to_vec(ngp, pt);
964 : }
965 209906 : if (gp->tags[i]==GF_PATH_CLOSE) gf_path_close(ngp);
966 209906 : i++;
967 209906 : break;
968 173609 : case GF_PATH_CURVE_CONIC:
969 : {
970 : GF_Point2D *ctl, *end, c1, c2;
971 173609 : ctl = &gp->points[i];
972 173609 : end = &gp->points[i+1];
973 173609 : c1.x = pt->x + 2*(ctl->x - pt->x)/3;
974 173609 : c1.y = pt->y + 2*(ctl->y - pt->y)/3;
975 173609 : c2.x = c1.x + (end->x - pt->x) / 3;
976 173609 : c2.y = c1.y + (end->y - pt->y) / 3;
977 :
978 173609 : gf_subdivide_cubic(ngp, pt->x, pt->y, c1.x, c1.y, c2.x, c2.y, end->x, end->y, fineness);
979 : pt = end;
980 173609 : if (gp->tags[i+1]==GF_PATH_CLOSE) gf_path_close(ngp);
981 173609 : i+=2;
982 : }
983 173609 : break;
984 9376 : case GF_PATH_CURVE_CUBIC:
985 9376 : gf_subdivide_cubic(ngp, pt->x, pt->y, gp->points[i].x, gp->points[i].y, gp->points[i+1].x, gp->points[i+1].y, gp->points[i+2].x, gp->points[i+2].y, fineness);
986 9376 : pt = &gp->points[i+2];
987 9376 : if (gp->tags[i+2]==GF_PATH_CLOSE) gf_path_close(ngp);
988 9376 : i+=3;
989 9376 : break;
990 : }
991 : }
992 6759 : if (gp->flags & GF_PATH_FILL_ZERO_NONZERO) ngp->flags |= GF_PATH_FILL_ZERO_NONZERO;
993 6759 : ngp->flags |= (GF_PATH_BBOX_DIRTY | GF_PATH_FLATTENED);
994 6759 : return ngp;
995 : }
996 :
997 : GF_EXPORT
998 624641 : void gf_path_flatten(GF_Path *gp)
999 : {
1000 : GF_Path *res;
1001 624641 : if (gp->flags & GF_PATH_FLATTENED) return;
1002 6756 : if (!gp->n_points) return;
1003 6756 : res = gf_path_get_flatten(gp);
1004 6756 : if (gp->contours) gf_free(gp->contours);
1005 6756 : if (gp->points) gf_free(gp->points);
1006 6756 : if (gp->tags) gf_free(gp->tags);
1007 : memcpy(gp, res, sizeof(GF_Path));
1008 6756 : gf_free(res);
1009 : }
1010 :
1011 :
1012 :
1013 : #define isLeft(P0, P1, P2) \
1014 : ( gf_mulfix((P1.x - P0.x), (P2.y - P0.y)) - gf_mulfix((P2.x - P0.x), (P1.y - P0.y)) )
1015 :
1016 :
1017 8 : static void gf_subdivide_cubic_hit_test(Fixed h_x, Fixed h_y, Fixed x0, Fixed y0, Fixed x1, Fixed y1, Fixed x2, Fixed y2, Fixed x3, Fixed y3, s32 *wn)
1018 : {
1019 : GF_Point2D s, e, pt;
1020 : Fixed x_m, y_m, xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2, y_min, y_max;
1021 :
1022 : /*if hit line doesn't intersects control box abort*/
1023 15 : y_min = MIN(y0, MIN(y1, MIN(y2, y3)));
1024 15 : y_max = MAX(y0, MAX(y1, MAX(y2, y3)));
1025 15 : if ((h_y<y_min) || (h_y>y_max) ) return;
1026 :
1027 : /*if vert diff between end points larger than 1 pixels, subdivide (we need pixel accuracy for is_over)*/
1028 9 : if (y_max - y_min > FIX_ONE) {
1029 7 : xa1 = (x0 + x1) / 2;
1030 7 : ya1 = (y0 + y1) / 2;
1031 7 : xa2 = (x0 + 2 * x1 + x2) / 4;
1032 7 : ya2 = (y0 + 2 * y1 + y2) / 4;
1033 7 : xb1 = (x1 + 2 * x2 + x3) / 4;
1034 7 : yb1 = (y1 + 2 * y2 + y3) / 4;
1035 7 : xb2 = (x2 + x3) / 2;
1036 7 : yb2 = (y2 + y3) / 2;
1037 7 : x_m = (xa2 + xb1) / 2;
1038 7 : y_m = (ya2 + yb1) / 2;
1039 :
1040 7 : gf_subdivide_cubic_hit_test(h_x, h_y, x0, y0, xa1, ya1, xa2, ya2, x_m, y_m, wn);
1041 : gf_subdivide_cubic_hit_test(h_x, h_y, x_m, y_m, xb1, yb1, xb2, yb2, x3, y3, wn);
1042 7 : return;
1043 : }
1044 :
1045 : s.x = x0;
1046 : s.y = y0;
1047 : e.x = x3;
1048 : e.y = y3;
1049 : pt.x = h_x;
1050 : pt.y= h_y;
1051 :
1052 2 : if (s.y<=pt.y) {
1053 1 : if (e.y>pt.y) {
1054 1 : if (isLeft(s, e, pt) > 0)
1055 0 : (*wn)++;
1056 : }
1057 : }
1058 1 : else if (e.y<=pt.y) {
1059 1 : if (isLeft(s, e, pt) < 0)
1060 1 : (*wn)--;
1061 : }
1062 : }
1063 :
1064 : GF_EXPORT
1065 110685 : Bool gf_path_point_over(GF_Path *gp, Fixed x, Fixed y)
1066 : {
1067 : u32 i, *contour, start_idx;
1068 : s32 wn;
1069 : GF_Point2D start, s, e, pt;
1070 : GF_Rect rc;
1071 : GF_Err err;
1072 :
1073 : /*check if not in bounds*/
1074 110685 : err = gf_path_get_bounds(gp, &rc);
1075 110685 : if (err) return GF_FALSE;
1076 110685 : if ((x<rc.x) || (y>rc.y) || (x>rc.x+rc.width) || (y<rc.y-rc.height)) return GF_FALSE;
1077 :
1078 2595 : if (!gp || (gp->n_points<2)) return GF_FALSE;
1079 :
1080 : pt.x = x;
1081 : pt.y = y;
1082 2594 : wn = 0;
1083 2594 : s = start = gp->points[0];
1084 : start_idx = 0;
1085 2594 : contour = gp->contours;
1086 72205 : for (i=1; i<gp->n_points; ) {
1087 67017 : switch (gp->tags[i]) {
1088 67016 : case GF_PATH_CURVE_ON:
1089 : case GF_PATH_CLOSE:
1090 67016 : e = gp->points[i];
1091 67016 : if (s.y<=pt.y) {
1092 34172 : if (e.y>pt.y) {
1093 2673 : if (isLeft(s, e, pt) > 0) wn++;
1094 : }
1095 : }
1096 32844 : else if (e.y<=pt.y) {
1097 2675 : if (isLeft(s, e, pt) < 0) wn--;
1098 : }
1099 : s = e;
1100 67016 : i++;
1101 67016 : break;
1102 1 : case GF_PATH_CURVE_CONIC:
1103 : {
1104 : GF_Point2D *ctl, *end, c1, c2;
1105 1 : ctl = &gp->points[i];
1106 1 : end = &gp->points[i+1];
1107 1 : c1.x = s.x + 2*(ctl->x - s.x) / 3;
1108 1 : c1.y = s.y + 2*(ctl->y - s.y) / 3;
1109 1 : c2.x = c1.x + (end->x - s.x) / 3;
1110 1 : c2.y = c1.y + (end->y - s.y) / 3;
1111 1 : gf_subdivide_cubic_hit_test(x, y, s.x, s.y, c1.x, c1.y, c2.x, c2.y, end->x, end->y, &wn);
1112 1 : s = *end;
1113 : }
1114 1 : i+=2;
1115 1 : break;
1116 0 : case GF_PATH_CURVE_CUBIC:
1117 0 : gf_subdivide_cubic_hit_test(x, y, s.x, s.y, gp->points[i].x, gp->points[i].y, gp->points[i+1].x, gp->points[i+1].y, gp->points[i+2].x, gp->points[i+2].y, &wn);
1118 0 : s = gp->points[i+2];
1119 0 : i+=3;
1120 0 : break;
1121 : }
1122 : /*end of subpath*/
1123 67017 : if (*contour==i-1) {
1124 : /*close path if needed, but don't test for lines...*/
1125 2594 : if ((i-start_idx > 2) && (pt.y<s.y)) {
1126 475 : if ((start.x != s.x) || (start.y != s.y)) {
1127 : e = start;
1128 36 : if (s.x<=pt.x) {
1129 2 : if (e.y>pt.y) {
1130 2 : if (isLeft(s, e, pt) > 0) wn++;
1131 : }
1132 : }
1133 34 : else if (e.y<=pt.y) {
1134 0 : if (isLeft(s, e, pt) < 0) wn--;
1135 : }
1136 : }
1137 : }
1138 2594 : if ( i < gp->n_points )
1139 19 : s = start = gp->points[i];
1140 2594 : i++;
1141 : }
1142 : }
1143 2594 : if (gp->flags & GF_PATH_FILL_ZERO_NONZERO) return wn ? GF_TRUE : GF_FALSE;
1144 2502 : return (wn%2) ? GF_TRUE : GF_FALSE;
1145 : }
1146 :
1147 : GF_EXPORT
1148 3 : Bool gf_path_is_empty(GF_Path *gp)
1149 : {
1150 3 : if (gp && gp->contours) return GF_FALSE;
1151 2 : return GF_TRUE;
1152 : }
1153 :
1154 : /*iteration info*/
1155 : typedef struct
1156 : {
1157 : Fixed len;
1158 : Fixed dx, dy;
1159 : Fixed start_x, start_y;
1160 : } IterInfo;
1161 :
1162 : struct _path_iterator
1163 : {
1164 : u32 num_seg;
1165 : IterInfo *seg;
1166 : Fixed length;
1167 : };
1168 :
1169 : GF_EXPORT
1170 341 : GF_PathIterator *gf_path_iterator_new(GF_Path *gp)
1171 : {
1172 : GF_Path *flat;
1173 : GF_PathIterator *it;
1174 : u32 i, j, cur;
1175 : GF_Point2D start, end;
1176 :
1177 341 : GF_SAFEALLOC(it, GF_PathIterator);
1178 341 : if (!it) return NULL;
1179 341 : flat = gf_path_get_flatten(gp);
1180 341 : if (!flat) {
1181 0 : gf_free(it);
1182 0 : return NULL;
1183 : }
1184 341 : it->seg = (IterInfo *) gf_malloc(sizeof(IterInfo) * flat->n_points);
1185 341 : it->num_seg = 0;
1186 341 : it->length = 0;
1187 : cur = 0;
1188 682 : for (i=0; i<flat->n_contours; i++) {
1189 : Fixed dx, dy;
1190 341 : u32 nb_pts = 1+flat->contours[i]-cur;
1191 341 : start = flat->points[cur];
1192 78495 : for (j=1; j<nb_pts; j++) {
1193 78154 : end = flat->points[cur+j];
1194 78154 : it->seg[it->num_seg].start_x = start.x;
1195 78154 : it->seg[it->num_seg].start_y = start.y;
1196 78154 : dx = it->seg[it->num_seg].dx = end.x - start.x;
1197 78154 : dy = it->seg[it->num_seg].dy = end.y - start.y;
1198 78154 : it->seg[it->num_seg].len = gf_sqrt(gf_mulfix(dx, dx) + gf_mulfix(dy, dy));
1199 78154 : it->length += it->seg[it->num_seg].len;
1200 : start = end;
1201 78154 : it->num_seg++;
1202 : }
1203 341 : cur += nb_pts;
1204 : }
1205 341 : gf_path_del(flat);
1206 341 : return it;
1207 : }
1208 :
1209 : GF_EXPORT
1210 341 : Fixed gf_path_iterator_get_length(GF_PathIterator *it)
1211 : {
1212 341 : return it ? it->length : 0;
1213 : }
1214 :
1215 : GF_EXPORT
1216 3558 : Bool gf_path_iterator_get_transform(GF_PathIterator *path, Fixed offset, Bool follow_tangent, GF_Matrix2D *mat, Bool smooth_edges, Fixed length_after_point)
1217 : {
1218 : GF_Matrix2D final, rot;
1219 : Bool tang = GF_FALSE;
1220 : Fixed res, angle, angleNext;
1221 : u32 i;
1222 : Fixed curLen = 0;
1223 3558 : if (!path) return GF_FALSE;
1224 :
1225 328359 : for (i=0; i<path->num_seg; i++) {
1226 331917 : if (curLen + path->seg[i].len >= offset) goto found;
1227 : curLen += path->seg[i].len;
1228 : }
1229 0 : if (!follow_tangent) return GF_FALSE;
1230 : tang = GF_TRUE;
1231 0 : i--;
1232 :
1233 7116 : found:
1234 3558 : gf_mx2d_init(final);
1235 :
1236 3558 : res = gf_divfix(offset - curLen, path->seg[i].len);
1237 3558 : if (tang) res += 1;
1238 :
1239 : /*move to current point*/
1240 3558 : gf_mx2d_add_translation(&final, path->seg[i].start_x + gf_mulfix(path->seg[i].dx, res), path->seg[i].start_y + gf_mulfix(path->seg[i].dy, res));
1241 :
1242 3558 : if (!path->seg[i].dx) {
1243 : angle = GF_PI2;
1244 : } else {
1245 3558 : angle = gf_acos( gf_divfix(path->seg[i].dx , path->seg[i].len) );
1246 : }
1247 3558 : if (path->seg[i].dy<0) angle *= -1;
1248 :
1249 3558 : if (smooth_edges) {
1250 3558 : if (offset + length_after_point > curLen + path->seg[i].len) {
1251 3188 : Fixed ratio = gf_divfix(curLen + path->seg[i].len-offset, length_after_point);
1252 3188 : if (i < path->num_seg - 1) {
1253 3188 : if (!path->seg[i+1].dx) {
1254 : angleNext = GF_PI2;
1255 : } else {
1256 3188 : angleNext = gf_acos( gf_divfix(path->seg[i+1].dx, path->seg[i+1].len) );
1257 : }
1258 3188 : if (path->seg[i+1].dy<0) angleNext *= -1;
1259 :
1260 3188 : if (angle<0 && angleNext>0) {
1261 3 : angle = gf_mulfix(FIX_ONE-ratio, angleNext) - gf_mulfix(ratio, angle);
1262 : } else {
1263 3185 : angle = gf_mulfix(ratio, angle) + gf_mulfix(FIX_ONE-ratio, angleNext);
1264 : }
1265 : }
1266 : }
1267 : }
1268 : /*handle res=0 case for rotation (point on line join)*/
1269 0 : else if (res==1) {
1270 0 : if (i < path->num_seg - 1) {
1271 0 : if (!path->seg[i+1].dx) {
1272 : angleNext = GF_PI2;
1273 : } else {
1274 0 : angleNext = gf_acos( gf_divfix(path->seg[i+1].dx, path->seg[i+1].len) );
1275 : }
1276 0 : if (path->seg[i+1].dy<0) angleNext *= -1;
1277 0 : angle = ( angle + angleNext) / 2;
1278 : }
1279 : }
1280 :
1281 3558 : gf_mx2d_init(rot);
1282 3558 : gf_mx2d_add_rotation(&rot, 0, 0, angle);
1283 3558 : gf_mx2d_add_matrix(mat, &rot);
1284 3558 : gf_mx2d_add_matrix(mat, &final);
1285 3558 : return GF_TRUE;
1286 : }
1287 :
1288 : GF_EXPORT
1289 341 : void gf_path_iterator_del(GF_PathIterator *it)
1290 : {
1291 341 : if (it->seg) gf_free(it->seg);
1292 341 : gf_free(it);
1293 341 : }
1294 :
1295 :
1296 : #define ConvexCompare(delta) \
1297 : ( (delta.x > 0) ? -1 : \
1298 : (delta.x < 0) ? 1 : \
1299 : (delta.y > 0) ? -1 : \
1300 : (delta.y < 0) ? 1 : \
1301 : 0 )
1302 :
1303 : #define ConvexGetPointDelta(delta, pprev, pcur ) \
1304 : /* Given a previous point 'pprev', read a new point into 'pcur' */ \
1305 : /* and return delta in 'delta'. */ \
1306 : pcur = pts[iread++]; \
1307 : delta.x = pcur.x - pprev.x; \
1308 : delta.y = pcur.y - pprev.y; \
1309 :
1310 : #define ConvexCross(p, q) gf_mulfix(p.x,q.y) - gf_mulfix(p.y,q.x);
1311 :
1312 : #define ConvexCheckTriple \
1313 : if ( (thisDir = ConvexCompare(dcur)) == -curDir ) { \
1314 : ++dirChanges; \
1315 : /* if ( dirChanges > 2 ) return NotConvex; */ \
1316 : } \
1317 : curDir = thisDir; \
1318 : cross = ConvexCross(dprev, dcur); \
1319 : if ( cross > 0 ) { \
1320 : if ( angleSign == -1 ) return GF_POLYGON_COMPLEX_CW; \
1321 : angleSign = 1; \
1322 : } \
1323 : else if (cross < 0) { \
1324 : if (angleSign == 1) return GF_POLYGON_COMPLEX_CCW; \
1325 : angleSign = -1; \
1326 : } \
1327 : pSecond = pThird; \
1328 : dprev.x = dcur.x; \
1329 : dprev.y = dcur.y; \
1330 :
1331 : GF_EXPORT
1332 62 : u32 gf_polygone2d_get_convexity(GF_Point2D *pts, u32 len)
1333 : {
1334 : s32 curDir, thisDir = 0, dirChanges = 0, angleSign = 0;
1335 : u32 iread;
1336 : Fixed cross;
1337 : GF_Point2D pSecond, pThird, pSaveSecond;
1338 : GF_Point2D dprev, dcur;
1339 :
1340 : /* Get different point, return if less than 3 diff points. */
1341 62 : if (len < 3 ) return GF_POLYGON_CONVEX_LINE;
1342 : iread = 1;
1343 62 : ConvexGetPointDelta(dprev, (pts[0]), pSecond);
1344 : pSaveSecond = pSecond;
1345 : /*initial direction */
1346 62 : curDir = ConvexCompare(dprev);
1347 1177 : while ( iread < len) {
1348 : /* Get different point, break if no more points */
1349 1146 : ConvexGetPointDelta(dcur, pSecond, pThird );
1350 1146 : if ( (dcur.x == 0) && (dcur.y == 0) ) continue;
1351 : /* Check current three points */
1352 1146 : ConvexCheckTriple;
1353 : }
1354 :
1355 : /* Must check for direction changes from last vertex back to first */
1356 : /* Prepare for 'ConvexCheckTriple' */
1357 : pThird = pts[0];
1358 31 : dcur.x = pThird.x - pSecond.x;
1359 31 : dcur.y = pThird.y - pSecond.y;
1360 31 : if ( ConvexCompare(dcur) ) {
1361 7 : ConvexCheckTriple;
1362 : }
1363 : /* and check for direction changes back to second vertex */
1364 31 : dcur.x = pSaveSecond.x - pSecond.x;
1365 31 : dcur.y = pSaveSecond.y - pSecond.y;
1366 : /* Don't care about 'pThird' now */
1367 31 : ConvexCheckTriple;
1368 :
1369 : /* Decide on polygon type given accumulated status */
1370 31 : if ( dirChanges > 2 ) return GF_POLYGON_COMPLEX;
1371 31 : if ( angleSign > 0 ) return GF_POLYGON_CONVEX_CCW;
1372 7 : if ( angleSign < 0 ) return GF_POLYGON_CONVEX_CW;
1373 0 : return GF_POLYGON_CONVEX_LINE;
1374 : }
|
