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