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 #include "config.h"
21 #include "art_uta_vpath.h"
22
23 #include <math.h>
24
25 #include "art_misc.h"
26 #include "art_vpath.h"
27 #include "art_uta.h"
28
29 #ifndef MAX
30 #define MAX(a, b) (((a) > (b)) ? (a) : (b))
31 #endif /* MAX */
32
33 #ifndef MIN
34 #define MIN(a, b) (((a) < (b)) ? (a) : (b))
35 #endif /* MIN */
36
37 /**
38 * art_uta_add_line: Add a line to the uta.
39 * @uta: The uta to modify.
40 * @x0: X coordinate of line start point.
41 * @y0: Y coordinate of line start point.
42 * @x1: X coordinate of line end point.
43 * @y1: Y coordinate of line end point.
44 * @rbuf: Buffer containing first difference of winding number.
45 * @rbuf_rowstride: Rowstride of @rbuf.
46 *
47 * Add the line (@x0, @y0) - (@x1, @y1) to @uta, and also update the
48 * winding number buffer used for rendering the interior. @rbuf
49 * contains the first partial difference (in the X direction) of the
50 * winding number, measured in grid cells. Thus, each time that a line
51 * crosses a horizontal uta grid line, an entry of @rbuf is
52 * incremented if @y1 > @y0, decremented otherwise.
53 *
54 * Note that edge handling is fairly delicate. Please rtfs for
55 * details.
56 **/
57 void
art_uta_add_line(ArtUta * uta,double x0,double y0,double x1,double y1,int * rbuf,int rbuf_rowstride)58 art_uta_add_line (ArtUta *uta, double x0, double y0, double x1, double y1,
59 int *rbuf, int rbuf_rowstride)
60 {
61 int xmin, ymin;
62 double xmax, ymax;
63 int xmaxf, ymaxf;
64 int xmaxc, ymaxc;
65 int xt0, yt0;
66 int xt1, yt1;
67 int xf0, yf0;
68 int xf1, yf1;
69 int ix, ix1;
70 ArtUtaBbox bb;
71
72 xmin = floor (MIN(x0, x1));
73 xmax = MAX(x0, x1);
74 xmaxf = floor (xmax);
75 xmaxc = ceil (xmax);
76 ymin = floor (MIN(y0, y1));
77 ymax = MAX(y0, y1);
78 ymaxf = floor (ymax);
79 ymaxc = ceil (ymax);
80 xt0 = (xmin >> ART_UTILE_SHIFT) - uta->x0;
81 yt0 = (ymin >> ART_UTILE_SHIFT) - uta->y0;
82 xt1 = (xmaxf >> ART_UTILE_SHIFT) - uta->x0;
83 yt1 = (ymaxf >> ART_UTILE_SHIFT) - uta->y0;
84 if (xt0 == xt1 && yt0 == yt1)
85 {
86 /* entirely inside a microtile, this is easy! */
87 xf0 = xmin & (ART_UTILE_SIZE - 1);
88 yf0 = ymin & (ART_UTILE_SIZE - 1);
89 xf1 = (xmaxf & (ART_UTILE_SIZE - 1)) + xmaxc - xmaxf;
90 yf1 = (ymaxf & (ART_UTILE_SIZE - 1)) + ymaxc - ymaxf;
91
92 ix = yt0 * uta->width + xt0;
93 bb = uta->utiles[ix];
94 if (bb == 0)
95 bb = ART_UTA_BBOX_CONS(xf0, yf0, xf1, yf1);
96 else
97 bb = ART_UTA_BBOX_CONS(MIN(ART_UTA_BBOX_X0(bb), xf0),
98 MIN(ART_UTA_BBOX_Y0(bb), yf0),
99 MAX(ART_UTA_BBOX_X1(bb), xf1),
100 MAX(ART_UTA_BBOX_Y1(bb), yf1));
101 uta->utiles[ix] = bb;
102 }
103 else
104 {
105 double dx, dy;
106 int sx, sy;
107
108 dx = x1 - x0;
109 dy = y1 - y0;
110 sx = dx > 0 ? 1 : dx < 0 ? -1 : 0;
111 sy = dy > 0 ? 1 : dy < 0 ? -1 : 0;
112 if (ymin == ymaxf)
113 {
114 /* special case horizontal (dx/dy slope would be infinite) */
115 xf0 = xmin & (ART_UTILE_SIZE - 1);
116 yf0 = ymin & (ART_UTILE_SIZE - 1);
117 xf1 = (xmaxf & (ART_UTILE_SIZE - 1)) + xmaxc - xmaxf;
118 yf1 = (ymaxf & (ART_UTILE_SIZE - 1)) + ymaxc - ymaxf;
119
120 ix = yt0 * uta->width + xt0;
121 ix1 = yt0 * uta->width + xt1;
122 while (ix != ix1)
123 {
124 bb = uta->utiles[ix];
125 if (bb == 0)
126 bb = ART_UTA_BBOX_CONS(xf0, yf0, ART_UTILE_SIZE, yf1);
127 else
128 bb = ART_UTA_BBOX_CONS(MIN(ART_UTA_BBOX_X0(bb), xf0),
129 MIN(ART_UTA_BBOX_Y0(bb), yf0),
130 ART_UTILE_SIZE,
131 MAX(ART_UTA_BBOX_Y1(bb), yf1));
132 uta->utiles[ix] = bb;
133 xf0 = 0;
134 ix++;
135 }
136 bb = uta->utiles[ix];
137 if (bb == 0)
138 bb = ART_UTA_BBOX_CONS(0, yf0, xf1, yf1);
139 else
140 bb = ART_UTA_BBOX_CONS(0,
141 MIN(ART_UTA_BBOX_Y0(bb), yf0),
142 MAX(ART_UTA_BBOX_X1(bb), xf1),
143 MAX(ART_UTA_BBOX_Y1(bb), yf1));
144 uta->utiles[ix] = bb;
145 }
146 else
147 {
148 /* Do a Bresenham-style traversal of the line */
149 double dx_dy;
150 double x, y;
151 double xn, yn;
152
153 /* normalize coordinates to uta origin */
154 x0 -= uta->x0 << ART_UTILE_SHIFT;
155 y0 -= uta->y0 << ART_UTILE_SHIFT;
156 x1 -= uta->x0 << ART_UTILE_SHIFT;
157 y1 -= uta->y0 << ART_UTILE_SHIFT;
158 if (dy < 0)
159 {
160 double tmp;
161
162 tmp = x0;
163 x0 = x1;
164 x1 = tmp;
165
166 tmp = y0;
167 y0 = y1;
168 y1 = tmp;
169
170 dx = -dx;
171 sx = -sx;
172 dy = -dy;
173 /* we leave sy alone, because it would always be 1,
174 and we need it for the rbuf stuff. */
175 }
176 xt0 = ((int)floor (x0) >> ART_UTILE_SHIFT);
177 xt1 = ((int)floor (x1) >> ART_UTILE_SHIFT);
178 /* now [xy]0 is above [xy]1 */
179
180 ix = yt0 * uta->width + xt0;
181 ix1 = yt1 * uta->width + xt1;
182 #ifdef VERBOSE
183 printf ("%% ix = %d,%d; ix1 = %d,%d\n", xt0, yt0, xt1, yt1);
184 #endif
185
186 dx_dy = dx / dy;
187 x = x0;
188 y = y0;
189 while (ix != ix1)
190 {
191 int dix;
192
193 /* figure out whether next crossing is horizontal or vertical */
194 #ifdef VERBOSE
195 printf ("%% %d,%d\n", xt0, yt0);
196 #endif
197 yn = (yt0 + 1) << ART_UTILE_SHIFT;
198
199 /* xn is the intercept with bottom edge of this tile. The
200 following expression is careful to result in exactly
201 x1 when yn = y1. */
202 xn = x1 + dx_dy * (yn - y1);
203
204 if (xt0 != (int)floor (xn) >> ART_UTILE_SHIFT)
205 {
206 /* horizontal crossing */
207 xt0 += sx;
208 dix = sx;
209 if (dx > 0)
210 {
211 xn = xt0 << ART_UTILE_SHIFT;
212 yn = y0 + (xn - x0) / dx_dy;
213
214 xf0 = (int)floor (x) & (ART_UTILE_SIZE - 1);
215 xf1 = ART_UTILE_SIZE;
216 }
217 else
218 {
219 xn = (xt0 + 1) << ART_UTILE_SHIFT;
220 yn = y0 + (xn - x0) / dx_dy;
221
222 xf0 = 0;
223 xmaxc = (int)ceil (x);
224 xf1 = xmaxc - ((xt0 + 1) << ART_UTILE_SHIFT);
225 }
226 ymaxf = (int)floor (yn);
227 ymaxc = (int)ceil (yn);
228 yf1 = (ymaxf & (ART_UTILE_SIZE - 1)) + ymaxc - ymaxf;
229 }
230 else
231 {
232 /* vertical crossing */
233 dix = uta->width;
234 xf0 = (int)floor (MIN(x, xn)) & (ART_UTILE_SIZE - 1);
235 xmax = MAX(x, xn);
236 xmaxc = (int)ceil (xmax);
237 xf1 = xmaxc - (xt0 << ART_UTILE_SHIFT);
238 yf1 = ART_UTILE_SIZE;
239
240 if (rbuf != NULL)
241 rbuf[yt0 * rbuf_rowstride + xt0] += sy;
242
243 yt0++;
244 }
245 yf0 = (int)floor (y) & (ART_UTILE_SIZE - 1);
246 bb = uta->utiles[ix];
247 if (bb == 0)
248 bb = ART_UTA_BBOX_CONS(xf0, yf0, xf1, yf1);
249 else
250 bb = ART_UTA_BBOX_CONS(MIN(ART_UTA_BBOX_X0(bb), xf0),
251 MIN(ART_UTA_BBOX_Y0(bb), yf0),
252 MAX(ART_UTA_BBOX_X1(bb), xf1),
253 MAX(ART_UTA_BBOX_Y1(bb), yf1));
254 uta->utiles[ix] = bb;
255
256 x = xn;
257 y = yn;
258 ix += dix;
259 }
260 xmax = MAX(x, x1);
261 xmaxc = ceil (xmax);
262 ymaxc = ceil (y1);
263 xf0 = (int)floor (MIN(x1, x)) & (ART_UTILE_SIZE - 1);
264 yf0 = (int)floor (y) & (ART_UTILE_SIZE - 1);
265 xf1 = xmaxc - (xt0 << ART_UTILE_SHIFT);
266 yf1 = ymaxc - (yt0 << ART_UTILE_SHIFT);
267 bb = uta->utiles[ix];
268 if (bb == 0)
269 bb = ART_UTA_BBOX_CONS(xf0, yf0, xf1, yf1);
270 else
271 bb = ART_UTA_BBOX_CONS(MIN(ART_UTA_BBOX_X0(bb), xf0),
272 MIN(ART_UTA_BBOX_Y0(bb), yf0),
273 MAX(ART_UTA_BBOX_X1(bb), xf1),
274 MAX(ART_UTA_BBOX_Y1(bb), yf1));
275 uta->utiles[ix] = bb;
276 }
277 }
278 }
279
280 /**
281 * art_uta_from_vpath: Generate uta covering a vpath.
282 * @vec: The source vpath.
283 *
284 * Generates a uta covering @vec. The resulting uta is of course
285 * approximate, ie it may cover more pixels than covered by @vec.
286 *
287 * Return value: the new uta.
288 **/
289 ArtUta *
art_uta_from_vpath(const ArtVpath * vec)290 art_uta_from_vpath (const ArtVpath *vec)
291 {
292 ArtUta *uta;
293 ArtIRect bbox;
294 int *rbuf;
295 int i;
296 double x, y;
297 int sum;
298 int xt, yt;
299 ArtUtaBbox *utiles;
300 ArtUtaBbox bb;
301 int width;
302 int height;
303 int ix;
304
305 art_vpath_bbox_irect (vec, &bbox);
306
307 uta = art_uta_new_coords (bbox.x0, bbox.y0, bbox.x1, bbox.y1);
308
309 width = uta->width;
310 height = uta->height;
311 utiles = uta->utiles;
312
313 rbuf = art_new (int, width * height);
314 for (i = 0; i < width * height; i++)
315 rbuf[i] = 0;
316
317 x = 0;
318 y = 0;
319 for (i = 0; vec[i].code != ART_END; i++)
320 {
321 switch (vec[i].code)
322 {
323 case ART_MOVETO:
324 x = vec[i].x;
325 y = vec[i].y;
326 break;
327 case ART_LINETO:
328 art_uta_add_line (uta, vec[i].x, vec[i].y, x, y, rbuf, width);
329 x = vec[i].x;
330 y = vec[i].y;
331 break;
332 default:
333 /* this shouldn't happen */
334 art_free (rbuf);
335 art_free (uta);
336 return NULL;
337 }
338 }
339
340 /* now add in the filling from rbuf */
341 ix = 0;
342 for (yt = 0; yt < height; yt++)
343 {
344 sum = 0;
345 for (xt = 0; xt < width; xt++)
346 {
347 sum += rbuf[ix];
348 /* Nonzero winding rule - others are possible, but hardly
349 worth it. */
350 if (sum != 0)
351 {
352 bb = utiles[ix];
353 bb &= 0xffff0000;
354 bb |= (ART_UTILE_SIZE << 8) | ART_UTILE_SIZE;
355 utiles[ix] = bb;
356 if (xt != width - 1)
357 {
358 bb = utiles[ix + 1];
359 bb &= 0xffff00;
360 bb |= ART_UTILE_SIZE;
361 utiles[ix + 1] = bb;
362 }
363 if (yt != height - 1)
364 {
365 bb = utiles[ix + width];
366 bb &= 0xff0000ff;
367 bb |= ART_UTILE_SIZE << 8;
368 utiles[ix + width] = bb;
369 if (xt != width - 1)
370 {
371 utiles[ix + width + 1] &= 0xffff;
372 }
373 }
374 }
375 ix++;
376 }
377 }
378
379 art_free (rbuf);
380
381 return uta;
382 }
383