small fix
[swftools.git] / lib / gfxpoly.c
1 /* gfxpoly.c 
2
3    Various boolean polygon functions.
4
5    Part of the swftools package.
6
7    Copyright (c) 2005 Matthias Kramm <kramm@quiss.org> 
8
9    This program is free software; you can redistribute it and/or modify
10    it under the terms of the GNU General Public License as published by
11    the Free Software Foundation; either version 2 of the License, or
12    (at your option) any later version.
13
14    This program is distributed in the hope that it will be useful,
15    but WITHOUT ANY WARRANTY; without even the implied warranty of
16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17    GNU General Public License for more details.
18
19    You should have received a copy of the GNU General Public License
20    along with this program; if not, write to the Free Software
21    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
22
23 #include "../config.h"
24 #include "gfxdevice.h"
25 #include "gfxtools.h"
26 #include "gfxpoly.h"
27 #include "art/libart.h"
28 #include <assert.h>
29 #include <memory.h>
30 #include <math.h>
31
32 static ArtVpath* gfxline_to_ArtVpath(gfxline_t*line, char fill)
33 {
34     ArtVpath *vec = NULL;
35     int pos=0,len=0;
36     gfxline_t*l2;
37     double x=0,y=0;
38
39     /* factor which determines into how many line fragments a spline is converted */
40     double subfraction = 2.4;//0.3
41
42     l2 = line;
43     while(l2) {
44         if(l2->type == gfx_moveTo) {
45             pos ++;
46         } if(l2->type == gfx_lineTo) {
47             pos ++;
48         } if(l2->type == gfx_splineTo) {
49             int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
50             if(!parts) parts = 1;
51             pos += parts + 1;
52         }
53         x = l2->x;
54         y = l2->y;
55         l2 = l2->next;
56     }
57     pos++;
58     len = pos;
59
60     vec = art_new (ArtVpath, len+1);
61
62     pos = 0;
63     l2 = line;
64     while(l2) {
65         if(l2->type == gfx_moveTo) {
66             vec[pos].code = ART_MOVETO;
67             vec[pos].x = l2->x;
68             vec[pos].y = l2->y;
69             pos++; 
70             assert(pos<=len);
71         } else if(l2->type == gfx_lineTo) {
72             vec[pos].code = ART_LINETO;
73             vec[pos].x = l2->x;
74             vec[pos].y = l2->y;
75             pos++; 
76             assert(pos<=len);
77         } else if(l2->type == gfx_splineTo) {
78             int i;
79             int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
80             double stepsize = parts?1.0/parts:0;
81             for(i=0;i<=parts;i++) {
82                 double t = (double)i*stepsize;
83                 vec[pos].code = ART_LINETO;
84                 vec[pos].x = l2->x*t*t + 2*l2->sx*t*(1-t) + x*(1-t)*(1-t);
85                 vec[pos].y = l2->y*t*t + 2*l2->sy*t*(1-t) + y*(1-t)*(1-t);
86                 pos++;
87                 assert(pos<=len);
88             }
89         }
90         x = l2->x;
91         y = l2->y;
92         l2 = l2->next;
93     }
94     vec[pos].code = ART_END;
95    
96     if(!fill) {
97         /* Fix "dotted" lines. Those are lines where singular points are created
98            by a moveto x,y lineto x,y combination. We "fix" these by shifting the
99            point in the lineto a little bit to the right 
100            These should only occur in strokes, not in fills, so do this only
101            when we know we're not filling.
102          */
103         int t;
104         for(t=0;vec[t].code!=ART_END;t++) {
105             if(t>0 && vec[t-1].code==ART_MOVETO && vec[t].code==ART_LINETO 
106                     && vec[t+1].code!=ART_LINETO
107                 && vec[t-1].x == vec[t].x
108                 && vec[t-1].y == vec[t].y) {
109                 vec[t].x += 0.01;
110             }
111             x = vec[t].x;
112             y = vec[t].y;
113         }
114     }
115
116     /* Find adjacent identical points. If an ajdacent pair of identical
117        points is found, the moveto is removed (unless both are movetos).
118        So moveto x,y lineto x,y becomes lineto x,y
119           lineto x,y lineto x,y becomes lineto x,y
120           lineto x,y moveto x,y becomes lineto x,y
121           moveto x,y moveto x,y becomes moveto x,y
122      */
123     int t;
124     while(t < pos)
125     {
126         int t = 1;
127         if ((vec[t-1].x == vec[t].x) && (vec[t-1].y == vec[t].y)) {
128             // adjacent identical points; remove one
129             int type = ART_MOVETO;
130             if(vec[t-1].code==ART_LINETO || vec[t].code==ART_LINETO)
131                 type = ART_LINETO;
132             memcpy(&vec[t], &vec[t+1], sizeof(vec[0]) * (pos - t));
133             vec[t].code = type;
134             pos--;
135         } else {
136             t++;
137         }
138     }
139
140     /* adjacency remover disabled for now, pending code inspection */
141     return vec;
142
143     // Check for further non-adjacent identical points. We don't want any
144     // points other than the first and last points to exactly match.
145     //
146     // If we do find matching points, move the second point slightly. This
147     // currently moves the duplicate 2% towards the midpoint of its neighbours
148     // (easier to calculate than 2% down the perpendicular to the line joining
149     // the neighbours) but limiting the change to 0.1 twips to avoid visual
150     // problems when the shapes are large. Note that there is no minimum
151     // change: if the neighbouring points are colinear and equally spaced,
152     // e.g. they were generated as part of a straight spline, then the
153     // duplicate point may not actually move.
154     //
155     // The scan for duplicates algorithm is quadratic in the number of points:
156     // there's probably a better method but the numbers of points is generally
157     // small so this will do for now.
158     {
159         int i = 1, j;
160         for(; i < (pos - 1); ++i)
161         {
162             for (j = 0; j < i; ++j)
163             {
164                 if ((vec[i].x == vec[j].x)
165                     && (vec[i].y == vec[j].y))
166                 {
167                     // points match; shuffle point
168                     double dx = (vec[i-1].x + vec[i+1].x - (vec[i].x * 2.0)) / 100.0;
169                     double dy = (vec[i-1].y + vec[i+1].y - (vec[i].y * 2.0)) / 100.0;
170                     double dxxyy = (dx*dx) + (dy*dy);
171                     if (dxxyy > 0.01)
172                     {
173                         // This is more than 0.1 twip's distance; scale down
174                         double dscale = sqrt(dxxyy) * 10.0;
175                         dx /= dscale;
176                         dy /= dscale;
177                     };
178                     vec[i].x += dx;
179                     vec[i].y += dy;
180                     break;
181                 }
182             }
183         }
184     }
185
186     return vec;
187 }
188
189 void show_path(ArtSVP*path)
190 {
191     int t;
192     printf("Segments: %d\n", path->n_segs);
193     for(t=0;t<path->n_segs;t++) {
194         ArtSVPSeg* seg = &path->segs[t];
195         printf("Segment %d: %d points, %s, BBox: (%f,%f,%f,%f)\n", 
196                 t, seg->n_points, seg->dir==0?"UP  ":"DOWN",
197                 seg->bbox.x0, seg->bbox.y0, seg->bbox.x1, seg->bbox.y1);
198         int p;
199         for(p=0;p<seg->n_points;p++) {
200             ArtPoint* point = &seg->points[p];
201             printf("        (%f,%f)\n", point->x, point->y);
202         }
203     }
204     printf("\n");
205 }
206
207 ArtSVP* gfxfillToSVP(gfxline_t*line, int perturb)
208 {
209     ArtVpath* vec = gfxline_to_ArtVpath(line, 1);
210     if(perturb) {
211         ArtVpath* vec2 = art_vpath_perturb(vec);
212         free(vec);
213         vec = vec2;
214     }
215     ArtSVP *svp = art_svp_from_vpath(vec);
216     free(vec);
217
218     // We need to make sure that the SVP we now have bounds an area (i.e. the
219     // source line wound anticlockwise) rather than excludes an area (i.e. the
220     // line wound clockwise). It seems that PDF (or xpdf) is less strict about
221     // this for bitmaps than it is for fill areas.
222     //
223     // To check this, we'll sum the cross products of all pairs of adjacent
224     // lines. If the result is positive, the direction is correct; if not, we
225     // need to reverse the sense of the SVP generated. The easiest way to do
226     // this is to flip the up/down flags of all the segments.
227     //
228     // This is approximate; since the gfxline_t structure can contain any
229     // combination of moveTo, lineTo and splineTo in any order, not all pairs
230     // of lines in the shape that share a point need be described next to each
231     // other in the sequence. For ease, we'll consider only pairs of lines
232     // stored as lineTos and splineTos without intervening moveTos.
233     //
234     // TODO is this a valid algorithm? My vector maths is rusty.
235     //
236     // It may be more correct to instead reverse the line before we feed it
237     // into gfxfilltoSVP. However, this seems equivalent and is easier to
238     // implement!
239     double total_cross_product = 0.0;
240     gfxline_t* cursor = line;
241     if (cursor != NULL)
242     {
243         double x_last = cursor->x;
244         double y_last = cursor->y;
245         cursor = cursor->next;
246
247         while((cursor != NULL) && (cursor->next != NULL))
248         {
249             if (((cursor->type == gfx_lineTo) || (cursor->type == gfx_splineTo))
250                 && ((cursor->next->type == gfx_lineTo) || (cursor->next->type == gfx_splineTo)))
251             {
252                 // Process these lines
253                 //
254                 // In this space (x right, y down) the cross-product is
255                 // (x1 * y0) - (x0 * y1)
256                 double x0 = cursor->x - x_last;
257                 double y0 = cursor->y - y_last;
258                 double x1 = cursor->next->x - cursor->x;
259                 double y1 = cursor->next->y - cursor->y;
260                 total_cross_product += (x1 * y0) - (x0 * y1);
261             }
262
263             x_last = cursor->x;
264             y_last = cursor->y;
265             cursor = cursor->next;
266         }
267     }
268     if (total_cross_product < 0.0)
269     {
270         int i = 0;
271         for(; i < svp->n_segs; ++i)
272         {
273             if (svp->segs[i].dir != 0)
274                 svp->segs[i].dir = 0;
275             else
276                 svp->segs[i].dir = 1;
277         }
278     }
279     return svp;
280 }
281
282 gfxline_t* gfxpoly_to_gfxline(gfxpoly_t*poly)
283 {
284     ArtSVP*svp = (ArtSVP*)poly;
285     int size = 0;
286     int t;
287     int pos = 0;
288     for(t=0;t<svp->n_segs;t++) {
289         size += svp->segs[t].n_points + 1;
290     }
291     gfxline_t* lines = (gfxline_t*)rfx_alloc(sizeof(gfxline_t)*size);
292
293     for(t=0;t<svp->n_segs;t++) {
294         ArtSVPSeg* seg = &svp->segs[t];
295         int p;
296         for(p=0;p<seg->n_points;p++) {
297             lines[pos].type = p==0?gfx_moveTo:gfx_lineTo;
298             ArtPoint* point = &seg->points[p];
299             lines[pos].x = point->x;
300             lines[pos].y = point->y;
301             lines[pos].next = &lines[pos+1];
302             pos++;
303         }
304     }
305     if(pos) {
306         lines[pos-1].next = 0;
307         return lines;
308     } else {
309         return 0;
310     }
311 }
312
313 gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line)
314 {
315     ArtSVP* svp = gfxfillToSVP(line, 1);
316     if (svp->n_segs > 500)
317     {
318         int lineParts = 0;
319         gfxline_t* lineCursor = line;
320         while(lineCursor != NULL)
321         {
322             if(lineCursor->type != gfx_moveTo) ++lineParts;
323             lineCursor = lineCursor->next;
324         }
325         fprintf(stderr, "arts_fill abandonning shape with %d segments (%d line parts)\n", svp->n_segs, lineParts);
326         art_svp_free(svp);
327         return (gfxpoly_t*)gfxpoly_strokeToPoly(0, 0, gfx_capButt, gfx_joinMiter, 0);
328     }
329     ArtSVP* svp2 = art_svp_rewind_uncrossed(art_svp_uncross(svp),ART_WIND_RULE_ODDEVEN);
330     free(svp);svp=svp2;
331     return (gfxpoly_t*)svp;
332 }
333
334 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*poly1, gfxpoly_t*poly2)
335 {
336     ArtSVP* svp1 = (ArtSVP*)poly1;
337     ArtSVP* svp2 = (ArtSVP*)poly2;
338         
339     ArtSVP* svp = art_svp_intersect(svp1, svp2);
340     return (gfxpoly_t*)svp;
341 }
342
343 gfxpoly_t* gfxpoly_union(gfxpoly_t*poly1, gfxpoly_t*poly2)
344 {
345     ArtSVP* svp1 = (ArtSVP*)poly1;
346     ArtSVP* svp2 = (ArtSVP*)poly2;
347         
348     ArtSVP* svp = art_svp_union(svp1, svp2);
349     return (gfxpoly_t*)svp;
350 }
351
352 gfxpoly_t* gfxpoly_strokeToPoly(gfxline_t*line, gfxcoord_t width, gfx_capType cap_style, gfx_joinType joint_style, double miterLimit)
353 {
354     ArtVpath* vec = gfxline_to_ArtVpath(line, 0);
355
356     ArtSVP *svp = art_svp_vpath_stroke (vec,
357                         (joint_style==gfx_joinMiter)?ART_PATH_STROKE_JOIN_MITER:
358                         ((joint_style==gfx_joinRound)?ART_PATH_STROKE_JOIN_ROUND:
359                          ((joint_style==gfx_joinBevel)?ART_PATH_STROKE_JOIN_BEVEL:ART_PATH_STROKE_JOIN_BEVEL)),
360                         (cap_style==gfx_capButt)?ART_PATH_STROKE_CAP_BUTT:
361                         ((cap_style==gfx_capRound)?ART_PATH_STROKE_CAP_ROUND:
362                          ((cap_style==gfx_capSquare)?ART_PATH_STROKE_CAP_SQUARE:ART_PATH_STROKE_CAP_SQUARE)),
363                         width, //line_width
364                         miterLimit, //miter_limit
365                         0.05 //flatness
366                         );
367     free(vec);
368     return (gfxpoly_t*)svp;
369 }
370
371 gfxline_t* gfxline_circularToEvenOdd(gfxline_t*line)
372 {
373     ArtSVP* svp = gfxfillToSVP(line, 1);
374     ArtSVP* svp2 = art_svp_rewind_uncrossed(art_svp_uncross(svp),ART_WIND_RULE_POSITIVE);
375     gfxline_t* result = gfxpoly_to_gfxline((gfxpoly_t*)svp2);
376     art_svp_free(svp);
377     art_svp_free(svp2);
378     return result;
379 }
380
381 gfxpoly_t* gfxpoly_createbox(double x1, double y1,double x2, double y2)
382 {
383     ArtVpath *vec = art_new (ArtVpath, 5+1);
384     vec[0].code = ART_MOVETO;
385     vec[0].x = x1;
386     vec[0].y = y1;
387     vec[1].code = ART_LINETO;
388     vec[1].x = x1;
389     vec[1].y = y2;
390     vec[2].code = ART_LINETO;
391     vec[2].x = x2;
392     vec[2].y = y2;
393     vec[3].code = ART_LINETO;
394     vec[3].x = x2;
395     vec[3].y = y1;
396     vec[4].code = ART_LINETO;
397     vec[4].x = x1;
398     vec[4].y = y1;
399     vec[5].code = ART_END;
400     vec[5].x = 0;
401     vec[5].y = 0;
402     ArtSVP *svp = art_svp_from_vpath(vec);
403     free(vec);
404     return (gfxpoly_t*)svp;
405 }
406
407 void gfxpoly_free(gfxpoly_t*poly)
408 {
409     ArtSVP*svp = (ArtSVP*)poly;
410     free(svp);
411 }