1 /* Libart_LGPL - library of basic graphic primitives
2 * Copyright (C) 1998-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 /* Sort vector paths into sorted vector paths */
21
22 #include "config.h"
23 #include "art_svp_vpath.h"
24
25 #include <stdlib.h>
26 #include <math.h>
27
28 #include "art_misc.h"
29
30 #include "art_vpath.h"
31 #include "art_svp.h"
32
33
34 /* reverse a list of points in place */
35 static void
reverse_points(ArtPoint * points,int n_points)36 reverse_points (ArtPoint *points, int n_points)
37 {
38 int i;
39 ArtPoint tmp_p;
40
41 for (i = 0; i < (n_points >> 1); i++)
42 {
43 tmp_p = points[i];
44 points[i] = points[n_points - (i + 1)];
45 points[n_points - (i + 1)] = tmp_p;
46 }
47 }
48
49 /**
50 * art_svp_from_vpath: Convert a vpath to a sorted vector path.
51 * @vpath: #ArtVPath to convert.
52 *
53 * Converts a vector path into sorted vector path form. The svp form is
54 * more efficient for rendering and other vector operations.
55 *
56 * Basically, the implementation is to traverse the vector path,
57 * generating a new segment for each "run" of points in the vector
58 * path with monotonically increasing Y values. All the resulting
59 * values are then sorted.
60 *
61 * Note: I'm not sure that the sorting rule is correct with respect
62 * to numerical stability issues.
63 *
64 * Return value: Resulting sorted vector path.
65 **/
66 ArtSVP *
art_svp_from_vpath(ArtVpath * vpath)67 art_svp_from_vpath (ArtVpath *vpath)
68 {
69 int n_segs, n_segs_max;
70 ArtSVP *svp;
71 int dir;
72 int new_dir;
73 int i;
74 ArtPoint *points;
75 int n_points, n_points_max;
76 double x, y;
77 double x_min, x_max;
78
79 n_segs = 0;
80 n_segs_max = 16;
81 svp = (ArtSVP *)art_alloc (sizeof(ArtSVP) +
82 (n_segs_max - 1) * sizeof(ArtSVPSeg));
83
84 dir = 0;
85 n_points = 0;
86 n_points_max = 0;
87 points = NULL;
88 i = 0;
89
90 x = y = 0; /* unnecessary, given "first code must not be LINETO" invariant,
91 but it makes gcc -Wall -ansi -pedantic happier */
92 x_min = x_max = 0; /* same */
93
94 while (vpath[i].code != ART_END) {
95 if (vpath[i].code == ART_MOVETO || vpath[i].code == ART_MOVETO_OPEN)
96 {
97 if (points != NULL && n_points >= 2)
98 {
99 if (n_segs == n_segs_max)
100 {
101 n_segs_max <<= 1;
102 svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
103 (n_segs_max - 1) *
104 sizeof(ArtSVPSeg));
105 }
106 svp->segs[n_segs].n_points = n_points;
107 svp->segs[n_segs].dir = (dir > 0);
108 if (dir < 0)
109 reverse_points (points, n_points);
110 svp->segs[n_segs].points = points;
111 svp->segs[n_segs].bbox.x0 = x_min;
112 svp->segs[n_segs].bbox.x1 = x_max;
113 svp->segs[n_segs].bbox.y0 = points[0].y;
114 svp->segs[n_segs].bbox.y1 = points[n_points - 1].y;
115 n_segs++;
116 points = NULL;
117 }
118
119 if (points == NULL)
120 {
121 n_points_max = 4;
122 points = art_new (ArtPoint, n_points_max);
123 }
124
125 n_points = 1;
126 points[0].x = x = vpath[i].x;
127 points[0].y = y = vpath[i].y;
128 x_min = x;
129 x_max = x;
130 dir = 0;
131 }
132 else /* must be LINETO */
133 {
134 new_dir = (vpath[i].y > y ||
135 (vpath[i].y == y && vpath[i].x > x)) ? 1 : -1;
136 if (dir && dir != new_dir)
137 {
138 /* new segment */
139 x = points[n_points - 1].x;
140 y = points[n_points - 1].y;
141 if (n_segs == n_segs_max)
142 {
143 n_segs_max <<= 1;
144 svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
145 (n_segs_max - 1) *
146 sizeof(ArtSVPSeg));
147 }
148 svp->segs[n_segs].n_points = n_points;
149 svp->segs[n_segs].dir = (dir > 0);
150 if (dir < 0)
151 reverse_points (points, n_points);
152 svp->segs[n_segs].points = points;
153 svp->segs[n_segs].bbox.x0 = x_min;
154 svp->segs[n_segs].bbox.x1 = x_max;
155 svp->segs[n_segs].bbox.y0 = points[0].y;
156 svp->segs[n_segs].bbox.y1 = points[n_points - 1].y;
157 n_segs++;
158
159 n_points = 1;
160 n_points_max = 4;
161 points = art_new (ArtPoint, n_points_max);
162 points[0].x = x;
163 points[0].y = y;
164 x_min = x;
165 x_max = x;
166 }
167
168 if (points != NULL)
169 {
170 if (n_points == n_points_max)
171 art_expand (points, ArtPoint, n_points_max);
172 points[n_points].x = x = vpath[i].x;
173 points[n_points].y = y = vpath[i].y;
174 if (x < x_min) x_min = x;
175 else if (x > x_max) x_max = x;
176 n_points++;
177 }
178 dir = new_dir;
179 }
180 i++;
181 }
182
183 if (points != NULL)
184 {
185 if (n_points >= 2)
186 {
187 if (n_segs == n_segs_max)
188 {
189 n_segs_max <<= 1;
190 svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
191 (n_segs_max - 1) *
192 sizeof(ArtSVPSeg));
193 }
194 svp->segs[n_segs].n_points = n_points;
195 svp->segs[n_segs].dir = (dir > 0);
196 if (dir < 0)
197 reverse_points (points, n_points);
198 svp->segs[n_segs].points = points;
199 svp->segs[n_segs].bbox.x0 = x_min;
200 svp->segs[n_segs].bbox.x1 = x_max;
201 svp->segs[n_segs].bbox.y0 = points[0].y;
202 svp->segs[n_segs].bbox.y1 = points[n_points - 1].y;
203 n_segs++;
204 }
205 else
206 art_free (points);
207 }
208
209 svp->n_segs = n_segs;
210
211 qsort (&svp->segs, n_segs, sizeof (ArtSVPSeg), art_svp_seg_compare);
212
213 return svp;
214 }
215
216