e4b36a8c6ec3bfe60fc8930e1567442dbef092c3
[swftools.git] / lib / devices / artsutils.c
1 #include <assert.h>
2 #include <math.h>
3
4 static ArtVpath* gfxline_to_ArtVpath(gfxline_t*line)
5 {
6     ArtVpath *vec = NULL;
7     int pos=0,len=0;
8     gfxline_t*l2;
9     double x=0,y=0;
10
11     /* factor which determines into how many line fragments a spline is converted */
12     double subfraction = 2.4;//0.3
13
14     l2 = line;
15     while(l2) {
16         if(l2->type == gfx_moveTo) {
17             pos ++;
18         } if(l2->type == gfx_lineTo) {
19             pos ++;
20         } if(l2->type == gfx_splineTo) {
21             int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
22             if(!parts) parts = 1;
23             pos += parts + 1;
24         }
25         x = l2->x;
26         y = l2->y;
27         l2 = l2->next;
28     }
29     pos++;
30     len = pos;
31
32     vec = art_new (ArtVpath, len+1);
33
34     pos = 0;
35     l2 = line;
36     while(l2) {
37         if(l2->type == gfx_moveTo) {
38             vec[pos].code = ART_MOVETO;
39             vec[pos].x = l2->x;
40             vec[pos].y = l2->y;
41             pos++; 
42             assert(pos<=len);
43         } else if(l2->type == gfx_lineTo) {
44             vec[pos].code = ART_LINETO;
45             vec[pos].x = l2->x;
46             vec[pos].y = l2->y;
47             pos++; 
48             assert(pos<=len);
49         } else if(l2->type == gfx_splineTo) {
50             int i;
51             int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
52             if(!parts) parts = 1;
53             for(i=0;i<=parts;i++) {
54                 double t = (double)i/(double)parts;
55                 vec[pos].code = ART_LINETO;
56                 vec[pos].x = l2->x*t*t + 2*l2->sx*t*(1-t) + x*(1-t)*(1-t);
57                 vec[pos].y = l2->y*t*t + 2*l2->sy*t*(1-t) + y*(1-t)*(1-t);
58                 pos++;
59                 assert(pos<=len);
60             }
61         }
62         x = l2->x;
63         y = l2->y;
64         l2 = l2->next;
65     }
66     vec[pos].code = ART_END;
67
68     // Spot adjacent identical points
69     {
70         int j = 1;
71         while(j < pos)
72         {
73             double dx = vec[j].x - vec[j-1].x;
74             double dy = vec[j].y - vec[j-1].y;
75             double d = dx*dx + dy*dy;
76             if ((vec[j-1].x == vec[j].x)
77                 && (vec[j-1].y == vec[j].y))
78             {
79                 // adjacent identical points; remove one
80                 memcpy(&(vec[j]), &(vec[j + 1]), sizeof(vec[j]) * (pos - j));
81                 --pos;
82             }
83             else
84             {
85                 // different
86                 ++j;
87             }
88         }
89     }
90
91     // Check for further non-adjacent identical points. We don't want any
92     // points other than the first and last points to exactly match.
93     //
94     // If we do find matching points, move the second point slightly. This
95     // currently moves the duplicate 2% towards the midpoint of its neighbours
96     // (easier to calculate than 2% down the perpendicular to the line joining
97     // the neighbours) but limiting the change to 0.1 twips to avoid visual
98     // problems when the shapes are large. Note that there is no minimum
99     // change: if the neighbouring points are colinear and equally spaced,
100     // e.g. they were generated as part of a straight spline, then the
101     // duplicate point may not actually move.
102     //
103     // The scan for duplicates algorithm is quadratic in the number of points:
104     // there's probably a better method but the numbers of points is generally
105     // small so this will do for now.
106     {
107         int i = 1, j;
108         for(; i < (pos - 1); ++i)
109         {
110             for (j = 0; j < i; ++j)
111             {
112                 if ((vec[i].x == vec[j].x)
113                     && (vec[i].y == vec[j].y))
114                 {
115                     // points match; shuffle point
116                     double dx = (vec[i-1].x + vec[i+1].x - (vec[i].x * 2.0)) / 100.0;
117                     double dy = (vec[i-1].y + vec[i+1].y - (vec[i].y * 2.0)) / 100.0;
118                     double dxxyy = (dx*dx) + (dy*dy);
119                     if (dxxyy > 0.01)
120                     {
121                         // This is more than 0.1 twip's distance; scale down
122                         double dscale = sqrt(dxxyy) * 10.0;
123                         dx /= dscale;
124                         dy /= dscale;
125                     };
126                     vec[i].x += dx;
127                     vec[i].y += dy;
128                     break;
129                 }
130             }
131         }
132     }
133
134     return vec;
135 }
136
137 static void show_path(ArtSVP*path)
138 {
139     int t;
140     printf("Segments: %d\n", path->n_segs);
141     for(t=0;t<path->n_segs;t++) {
142         ArtSVPSeg* seg = &path->segs[t];
143         printf("Segment %d: %d points, %s, BBox: (%f,%f,%f,%f)\n", 
144                 t, seg->n_points, seg->dir==0?"UP  ":"DOWN",
145                 seg->bbox.x0, seg->bbox.y0, seg->bbox.x1, seg->bbox.y1);
146         int p;
147         for(p=0;p<seg->n_points;p++) {
148             ArtPoint* point = &seg->points[p];
149             printf("        (%f,%f)\n", point->x, point->y);
150         }
151     }
152     printf("\n");
153 }
154
155 static ArtSVP* gfxfillToSVP(gfxline_t*line, int perturb)
156 {
157     ArtVpath* vec = gfxline_to_ArtVpath(line);
158     if(perturb) {
159         ArtVpath* vec2 = art_vpath_perturb(vec);
160         free(vec);
161         vec = vec2;
162     }
163     ArtSVP *svp = art_svp_from_vpath(vec);
164     free(vec);
165
166     // We need to make sure that the SVP we now have bounds an area (i.e. the
167     // source line wound anticlockwise) rather than excludes an area (i.e. the
168     // line wound clockwise). It seems that PDF (or xpdf) is less strict about
169     // this for bitmaps than it is for fill areas.
170     //
171     // To check this, we'll sum the cross products of all pairs of adjacent
172     // lines. If the result is positive, the direction is correct; if not, we
173     // need to reverse the sense of the SVP generated. The easiest way to do
174     // this is to flip the up/down flags of all the segments.
175     //
176     // This is approximate; since the gfxline_t structure can contain any
177     // combination of moveTo, lineTo and splineTo in any order, not all pairs
178     // of lines in the shape that share a point need be described next to each
179     // other in the sequence. For ease, we'll consider only pairs of lines
180     // stored as lineTos and splineTos without intervening moveTos.
181     //
182     // TODO is this a valid algorithm? My vector maths is rusty.
183     //
184     // It may be more correct to instead reverse the line before we feed it
185     // into gfxfilltoSVP. However, this seems equivalent and is easier to
186     // implement!
187     double total_cross_product = 0.0;
188     gfxline_t* cursor = line;
189     if (cursor != NULL)
190     {
191         double x_last = cursor->x;
192         double y_last = cursor->y;
193         cursor = cursor->next;
194
195         while((cursor != NULL) && (cursor->next != NULL))
196         {
197             if (((cursor->type == gfx_lineTo) || (cursor->type == gfx_splineTo))
198                 && ((cursor->next->type == gfx_lineTo) || (cursor->next->type == gfx_splineTo)))
199             {
200                 // Process these lines
201                 //
202                 // In this space (x right, y down) the cross-product is
203                 // (x1 * y0) - (x0 * y1)
204                 double x0 = cursor->x - x_last;
205                 double y0 = cursor->y - y_last;
206                 double x1 = cursor->next->x - cursor->x;
207                 double y1 = cursor->next->y - cursor->y;
208                 total_cross_product += (x1 * y0) - (x0 * y1);
209             }
210
211             x_last = cursor->x;
212             y_last = cursor->y;
213             cursor = cursor->next;
214         }
215     }
216     if (total_cross_product < 0.0)
217     {
218         int i = 0;
219         for(; i < svp->n_segs; ++i)
220         {
221             if (svp->segs[i].dir != 0)
222                 svp->segs[i].dir = 0;
223             else
224                 svp->segs[i].dir = 1;
225         }
226     }
227     return svp;
228 }
229 static ArtSVP* boxToSVP(double x1, double y1,double x2, double y2)
230 {
231     ArtVpath *vec = art_new (ArtVpath, 5+1);
232     vec[0].code = ART_MOVETO;
233     vec[0].x = x1;
234     vec[0].y = y1;
235     vec[1].code = ART_LINETO;
236     vec[1].x = x1;
237     vec[1].y = y2;
238     vec[2].code = ART_LINETO;
239     vec[2].x = x2;
240     vec[2].y = y2;
241     vec[3].code = ART_LINETO;
242     vec[3].x = x2;
243     vec[3].y = y1;
244     vec[4].code = ART_LINETO;
245     vec[4].x = x1;
246     vec[4].y = y1;
247     vec[5].code = ART_END;
248     vec[5].x = 0;
249     vec[5].y = 0;
250     ArtSVP *svp = art_svp_from_vpath(vec);
251     free(vec);
252     return svp;
253 }
254
255 static ArtSVP* gfxstrokeToSVP(gfxline_t*line, gfxcoord_t width, gfx_capType cap_style, gfx_joinType joint_style, double miterLimit)
256 {
257     ArtVpath* vec = gfxline_to_ArtVpath(line);
258     ArtSVP *svp = art_svp_vpath_stroke (vec,
259                         (joint_style==gfx_joinMiter)?ART_PATH_STROKE_JOIN_MITER:
260                         ((joint_style==gfx_joinRound)?ART_PATH_STROKE_JOIN_ROUND:
261                          ((joint_style==gfx_joinBevel)?ART_PATH_STROKE_JOIN_BEVEL:ART_PATH_STROKE_JOIN_BEVEL)),
262                         (cap_style==gfx_capButt)?ART_PATH_STROKE_CAP_BUTT:
263                         ((cap_style==gfx_capRound)?ART_PATH_STROKE_CAP_ROUND:
264                          ((cap_style==gfx_capSquare)?ART_PATH_STROKE_CAP_SQUARE:ART_PATH_STROKE_CAP_SQUARE)),
265                         width, //line_width
266                         miterLimit, //miter_limit
267                         0.05 //flatness
268                         );
269     free(vec);
270     return svp;
271 }
272
273 static gfxline_t* SVPtogfxline(ArtSVP*svp)
274 {
275     int size = 0;
276     int t;
277     int pos = 0;
278     for(t=0;t<svp->n_segs;t++) {
279         size += svp->segs[t].n_points + 1;
280     }
281     gfxline_t* lines = (gfxline_t*)rfx_alloc(sizeof(gfxline_t)*size);
282
283     for(t=0;t<svp->n_segs;t++) {
284         ArtSVPSeg* seg = &svp->segs[t];
285         int p;
286         for(p=0;p<seg->n_points;p++) {
287             lines[pos].type = p==0?gfx_moveTo:gfx_lineTo;
288             ArtPoint* point = &seg->points[p];
289             lines[pos].x = point->x;
290             lines[pos].y = point->y;
291             lines[pos].next = &lines[pos+1];
292             pos++;
293         }
294     }
295     if(pos) {
296         lines[pos-1].next = 0;
297         return lines;
298     } else {
299         return 0;
300     }
301 }
302