char -> const char, warn if drawing empty characters
[swftools.git] / lib / art / art_uta_vpath.c
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
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 *
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 }