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 */
20 /* Apply a dash style to a vector path. */
22 #include <math.h>
23 #include <stdlib.h>
25 #include "art_misc.h"
27 #include "art_vpath.h"
28 #include "art_vpath_dash.h"
31 /* Return the length of the largest subpath within vpath */
32 static int
33 art_vpath_dash_max_subpath (const ArtVpath *vpath)
34 {
35 int max_subpath;
36 int i;
37 int start;
39 max_subpath = 0;
40 start = 0;
41 for (i = 0; vpath[i].code != ART_END; i++)
42 {
43 if (vpath[i].code == ART_MOVETO || vpath[i].code == ART_MOVETO_OPEN)
44 {
45 if (i - start > max_subpath)
46 max_subpath = i - start;
47 start = i;
48 }
49 }
50 if (i - start > max_subpath)
51 max_subpath = i - start;
53 return max_subpath;
54 }
56 /**
57 * art_vpath_dash: Add dash style to vpath.
58 * @vpath: Original vpath.
59 * @dash: Dash style.
60 *
61 * Creates a new vpath that is the result of applying dash style @dash
62 * to @vpath.
63 *
64 * This implementation has two known flaws:
65 *
66 * First, it adds a spurious break at the beginning of the vpath. The
67 * only way I see to resolve this flaw is to run the state forward one
68 * dash break at the beginning, and fix up by looping back to the
69 * first dash break at the end. This is doable but of course adds some
70 * complexity.
71 *
72 * Second, it does not suppress output points that are within epsilon
73 * of each other.
74 *
75 * Return value: Newly created vpath.
76 **/
77 ArtVpath *
78 art_vpath_dash (const ArtVpath *vpath, const ArtVpathDash *dash)
79 {
80 int max_subpath;
81 double *dists;
82 ArtVpath *result;
83 int n_result, n_result_max;
84 int start, end;
85 int i;
86 double total_dist;
88 /* state while traversing dasharray - offset is offset of current dash
89 value, toggle is 0 for "off" and 1 for "on", and phase is the distance
90 in, >= 0, < dash->dash[offset]. */
91 int offset, toggle;
92 double phase;
94 /* initial values */
95 int offset_init, toggle_init;
96 double phase_init;
98 max_subpath = art_vpath_dash_max_subpath (vpath);
99 dists = art_new (double, max_subpath);
101 n_result = 0;
102 n_result_max = 16;
103 result = art_new (ArtVpath, n_result_max);
105 /* determine initial values of dash state */
106 toggle_init = 1;
107 offset_init = 0;
108 phase_init = dash->offset;
109 while (phase_init >= dash->dash[offset_init])
110 {
111 toggle_init = !toggle_init;
112 phase_init -= dash->dash[offset_init];
113 offset_init++;
114 if (offset_init == dash->n_dash)
115 offset_init = 0;
116 }
118 for (start = 0; vpath[start].code != ART_END; start = end)
119 {
120 for (end = start + 1; vpath[end].code == ART_LINETO; end++);
121 /* subpath is [start..end) */
122 total_dist = 0;
123 for (i = start; i < end - 1; i++)
124 {
125 double dx, dy;
127 dx = vpath[i + 1].x - vpath[i].x;
128 dy = vpath[i + 1].y - vpath[i].y;
129 dists[i - start] = sqrt (dx * dx + dy * dy);
130 total_dist += dists[i - start];
131 }
132 if (total_dist <= dash->dash[offset_init] - phase_init)
133 {
134 /* subpath fits entirely within first dash */
135 if (toggle_init)
136 {
137 for (i = start; i < end; i++)
138 art_vpath_add_point (&result, &n_result, &n_result_max,
139 vpath[i].code, vpath[i].x, vpath[i].y);
140 }
141 }
142 else
143 {
144 /* subpath is composed of at least one dash - thus all
145 generated pieces are open */
146 double dist;
148 phase = phase_init;
149 offset = offset_init;
150 toggle = toggle_init;
151 dist = 0;
152 i = start;
153 if (toggle)
154 art_vpath_add_point (&result, &n_result, &n_result_max,
155 ART_MOVETO_OPEN, vpath[i].x, vpath[i].y);
156 while (i != end - 1)
157 {
158 if (dists[i - start] - dist > dash->dash[offset] - phase)
159 {
160 /* dash boundary is next */
161 double a;
162 double x, y;
164 dist += dash->dash[offset] - phase;
165 a = dist / dists[i - start];
166 x = vpath[i].x + a * (vpath[i + 1].x - vpath[i].x);
167 y = vpath[i].y + a * (vpath[i + 1].y - vpath[i].y);
168 art_vpath_add_point (&result, &n_result, &n_result_max,
169 toggle ? ART_LINETO : ART_MOVETO_OPEN,
170 x, y);
171 /* advance to next dash */
172 toggle = !toggle;
173 phase = 0;
174 offset++;
175 if (offset == dash->n_dash)
176 offset = 0;
177 }
178 else
179 {
180 /* end of line in vpath is next */
181 phase += dists[i - start] - dist;
182 i++;
183 dist = 0;
184 if (toggle)
185 art_vpath_add_point (&result, &n_result, &n_result_max,
186 ART_LINETO, vpath[i].x, vpath[i].y);
187 }
188 }
189 }
190 }
192 art_vpath_add_point (&result, &n_result, &n_result_max,
193 ART_END, 0, 0);
195 art_free (dists);
197 return result;
198 }