source: trunk/third/mozilla/other-licenses/libart_lgpl/art_uta_vpath.c @ 22325

Revision 22325, 9.4 KB checked in by rbasch, 19 years ago (diff)
This commit was generated by cvs2svn to compensate for changes in r22324, which included commits to RCS files with non-trunk default branches.
RevLine 
[22324]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 **/
57void
58art_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 **/
289ArtUta *
290art_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          break;
335        }
336    }
337
338  /* now add in the filling from rbuf */
339  ix = 0;
340  for (yt = 0; yt < height; yt++)
341    {
342      sum = 0;
343      for (xt = 0; xt < width; xt++)
344        {
345          sum += rbuf[ix];
346          /* Nonzero winding rule - others are possible, but hardly
347             worth it. */
348          if (sum != 0)
349            {
350              bb = utiles[ix];
351              bb &= 0xffff0000;
352              bb |= (ART_UTILE_SIZE << 8) | ART_UTILE_SIZE;
353              utiles[ix] = bb;
354              if (xt != width - 1)
355                {
356                  bb = utiles[ix + 1];
357                  bb &= 0xffff00;
358                  bb |= ART_UTILE_SIZE;
359                  utiles[ix + 1] = bb;
360                }
361              if (yt != height - 1)
362                {
363                  bb = utiles[ix + width];
364                  bb &= 0xff0000ff;
365                  bb |= ART_UTILE_SIZE << 8;
366                  utiles[ix + width] = bb;
367                  if (xt != width - 1)
368                    {
369                      utiles[ix + width + 1] &= 0xffff;
370                    }
371                }
372            }
373          ix++;
374        }
375    }
376
377  art_free (rbuf);
378
379  return uta;
380}
Note: See TracBrowser for help on using the repository browser.