updated gpdf2swf (patch from Ricardo Pedroso)
[swftools.git] / lib / art / art_vpath_dash.c
1 /* Libart_LGPL - library of basic graphic primitives
2  * Copyright (C) 1999-2000 Raph Levien
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Library General Public
6  * License as published by the Free Software Foundation; either
7  * version 2 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * Library General Public License for more details.
13  *
14  * You should have received a copy of the GNU Library General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */
19
20 /* Apply a dash style to a vector path. */
21
22 #include "config.h"
23 #include "art_vpath_dash.h"
24
25 #include <math.h>
26 #include <stdlib.h>
27
28 #include "art_misc.h"
29
30 #include "art_vpath.h"
31
32
33 /* Return the length of the largest subpath within vpath */
34 static int
35 art_vpath_dash_max_subpath (const ArtVpath *vpath)
36 {
37   int max_subpath;
38   int i;
39   int start;
40
41   max_subpath = 0;
42   start = 0;
43   for (i = 0; vpath[i].code != ART_END; i++)
44     {
45       if (vpath[i].code == ART_MOVETO || vpath[i].code == ART_MOVETO_OPEN)
46         {
47           if (i - start > max_subpath)
48             max_subpath = i - start;
49           start = i;
50         }
51     }
52   if (i - start > max_subpath)
53     max_subpath = i - start;
54
55   return max_subpath;
56 }
57
58 /**
59  * art_vpath_dash: Add dash style to vpath.
60  * @vpath: Original vpath.
61  * @dash: Dash style.
62  *
63  * Creates a new vpath that is the result of applying dash style @dash
64  * to @vpath.
65  *
66  * This implementation has two known flaws:
67  *
68  * First, it adds a spurious break at the beginning of the vpath. The
69  * only way I see to resolve this flaw is to run the state forward one
70  * dash break at the beginning, and fix up by looping back to the
71  * first dash break at the end. This is doable but of course adds some
72  * complexity.
73  *
74  * Second, it does not suppress output points that are within epsilon
75  * of each other.
76  *
77  * Return value: Newly created vpath.
78  **/
79 ArtVpath *
80 art_vpath_dash (const ArtVpath *vpath, const ArtVpathDash *dash)
81 {
82   int max_subpath;
83   double *dists;
84   ArtVpath *result;
85   int n_result, n_result_max;
86   int start, end;
87   int i;
88   double total_dist;
89
90   /* state while traversing dasharray - offset is offset of current dash
91      value, toggle is 0 for "off" and 1 for "on", and phase is the distance
92      in, >= 0, < dash->dash[offset]. */
93   int offset, toggle;
94   double phase;
95
96   /* initial values */
97   int offset_init, toggle_init;
98   double phase_init;
99
100   max_subpath = art_vpath_dash_max_subpath (vpath);
101   dists = art_new (double, max_subpath);
102
103   n_result = 0;
104   n_result_max = 16;
105   result = art_new (ArtVpath, n_result_max);
106
107   /* determine initial values of dash state */
108   toggle_init = 1;
109   offset_init = 0;
110   phase_init = dash->offset;
111   while (phase_init >= dash->dash[offset_init])
112     {
113       toggle_init = !toggle_init;
114       phase_init -= dash->dash[offset_init];
115       offset_init++;
116       if (offset_init == dash->n_dash)
117         offset_init = 0;
118     }
119
120   for (start = 0; vpath[start].code != ART_END; start = end)
121     {
122       for (end = start + 1; vpath[end].code == ART_LINETO; end++);
123       /* subpath is [start..end) */
124       total_dist = 0;
125       for (i = start; i < end - 1; i++)
126         {
127           double dx, dy;
128
129           dx = vpath[i + 1].x - vpath[i].x;
130           dy = vpath[i + 1].y - vpath[i].y;
131           dists[i - start] = sqrt (dx * dx + dy * dy);
132           total_dist += dists[i - start];
133         }
134       if (total_dist <= dash->dash[offset_init] - phase_init)
135         {
136           /* subpath fits entirely within first dash */
137           if (toggle_init)
138             {
139               for (i = start; i < end; i++)
140                 art_vpath_add_point (&result, &n_result, &n_result_max,
141                                      vpath[i].code, vpath[i].x, vpath[i].y);
142             }
143         }
144       else
145         {
146           /* subpath is composed of at least one dash - thus all
147              generated pieces are open */
148           double dist;
149
150           phase = phase_init;
151           offset = offset_init;
152           toggle = toggle_init;
153           dist = 0;
154           i = start;
155           if (toggle)
156             art_vpath_add_point (&result, &n_result, &n_result_max,
157                                  ART_MOVETO_OPEN, vpath[i].x, vpath[i].y);
158           while (i != end - 1)
159             {
160               if (dists[i - start] - dist > dash->dash[offset] - phase)
161                 {
162                   /* dash boundary is next */
163                   double a;
164                   double x, y;
165
166                   dist += dash->dash[offset] - phase;
167                   a = dist / dists[i - start];
168                   x = vpath[i].x + a * (vpath[i + 1].x - vpath[i].x);
169                   y = vpath[i].y + a * (vpath[i + 1].y - vpath[i].y);
170                   art_vpath_add_point (&result, &n_result, &n_result_max,
171                                        toggle ? ART_LINETO : ART_MOVETO_OPEN,
172                                        x, y);
173                   /* advance to next dash */
174                   toggle = !toggle;
175                   phase = 0;
176                   offset++;
177                   if (offset == dash->n_dash)
178                     offset = 0;
179                 }
180               else
181                 {
182                   /* end of line in vpath is next */
183                   phase += dists[i - start] - dist;
184                   i++;
185                   dist = 0;
186                   if (toggle)
187                     art_vpath_add_point (&result, &n_result, &n_result_max,
188                                          ART_LINETO, vpath[i].x, vpath[i].y);
189                 }
190             }
191         }
192     }
193
194   art_vpath_add_point (&result, &n_result, &n_result_max,
195                        ART_END, 0, 0);
196
197   art_free (dists);
198
199   return result;
200 }