1 /* Libart_LGPL - library of basic graphic primitives
2 * Copyright (C) 1998-2000 Raph Levien
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.
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.
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.
21 #include "art_uta_vpath.h"
26 #include "art_vpath.h"
30 #define MAX(a, b) (((a) > (b)) ? (a) : (b))
34 #define MIN(a, b) (((a) < (b)) ? (a) : (b))
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.
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.
54 * Note that edge handling is fairly delicate. Please rtfs for
58 art_uta_add_line (ArtUta
*uta
, double x0
, double y0
, double x1
, double y1
,
59 int *rbuf
, int rbuf_rowstride
)
72 xmin
= floor (MIN(x0
, x1
));
76 ymin
= floor (MIN(y0
, y1
));
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
)
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
;
92 ix
= yt0
* uta
->width
+ xt0
;
95 bb
= ART_UTA_BBOX_CONS(xf0
, yf0
, xf1
, yf1
);
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
;
110 sx
= dx
> 0 ? 1 : dx
< 0 ? -1 : 0;
111 sy
= dy
> 0 ? 1 : dy
< 0 ? -1 : 0;
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
;
120 ix
= yt0
* uta
->width
+ xt0
;
121 ix1
= yt0
* uta
->width
+ xt1
;
124 bb
= uta
->utiles
[ix
];
126 bb
= ART_UTA_BBOX_CONS(xf0
, yf0
, ART_UTILE_SIZE
, yf1
);
128 bb
= ART_UTA_BBOX_CONS(MIN(ART_UTA_BBOX_X0(bb
), xf0
),
129 MIN(ART_UTA_BBOX_Y0(bb
), yf0
),
131 MAX(ART_UTA_BBOX_Y1(bb
), yf1
));
132 uta
->utiles
[ix
] = bb
;
136 bb
= uta
->utiles
[ix
];
138 bb
= ART_UTA_BBOX_CONS(0, yf0
, xf1
, yf1
);
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
;
148 /* Do a Bresenham-style traversal of the line */
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
;
173 /* we leave sy alone, because it would always be 1,
174 and we need it for the rbuf stuff. */
176 xt0
= ((int)floor (x0
) >> ART_UTILE_SHIFT
);
177 xt1
= ((int)floor (x1
) >> ART_UTILE_SHIFT
);
178 /* now [xy]0 is above [xy]1 */
180 ix
= yt0
* uta
->width
+ xt0
;
181 ix1
= yt1
* uta
->width
+ xt1
;
183 printf ("%% ix = %d,%d; ix1 = %d,%d\n", xt0
, yt0
, xt1
, yt1
);
193 /* figure out whether next crossing is horizontal or vertical */
195 printf ("%% %d,%d\n", xt0
, yt0
);
197 yn
= (yt0
+ 1) << ART_UTILE_SHIFT
;
199 /* xn is the intercept with bottom edge of this tile. The
200 following expression is careful to result in exactly
202 xn
= x1
+ dx_dy
* (yn
- y1
);
204 if (xt0
!= (int)floor (xn
) >> ART_UTILE_SHIFT
)
206 /* horizontal crossing */
211 xn
= xt0
<< ART_UTILE_SHIFT
;
212 yn
= y0
+ (xn
- x0
) / dx_dy
;
214 xf0
= (int)floor (x
) & (ART_UTILE_SIZE
- 1);
215 xf1
= ART_UTILE_SIZE
;
219 xn
= (xt0
+ 1) << ART_UTILE_SHIFT
;
220 yn
= y0
+ (xn
- x0
) / dx_dy
;
223 xmaxc
= (int)ceil (x
);
224 xf1
= xmaxc
- ((xt0
+ 1) << ART_UTILE_SHIFT
);
226 ymaxf
= (int)floor (yn
);
227 ymaxc
= (int)ceil (yn
);
228 yf1
= (ymaxf
& (ART_UTILE_SIZE
- 1)) + ymaxc
- ymaxf
;
232 /* vertical crossing */
234 xf0
= (int)floor (MIN(x
, xn
)) & (ART_UTILE_SIZE
- 1);
236 xmaxc
= (int)ceil (xmax
);
237 xf1
= xmaxc
- (xt0
<< ART_UTILE_SHIFT
);
238 yf1
= ART_UTILE_SIZE
;
241 rbuf
[yt0
* rbuf_rowstride
+ xt0
] += sy
;
245 yf0
= (int)floor (y
) & (ART_UTILE_SIZE
- 1);
246 bb
= uta
->utiles
[ix
];
248 bb
= ART_UTA_BBOX_CONS(xf0
, yf0
, xf1
, yf1
);
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
;
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
];
269 bb
= ART_UTA_BBOX_CONS(xf0
, yf0
, xf1
, yf1
);
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
;
281 * art_uta_from_vpath: Generate uta covering a vpath.
282 * @vec: The source vpath.
284 * Generates a uta covering @vec. The resulting uta is of course
285 * approximate, ie it may cover more pixels than covered by @vec.
287 * Return value: the new uta.
290 art_uta_from_vpath (const ArtVpath
*vec
)
305 art_vpath_bbox_irect (vec
, &bbox
);
307 uta
= art_uta_new_coords (bbox
.x0
, bbox
.y0
, bbox
.x1
, bbox
.y1
);
310 height
= uta
->height
;
311 utiles
= uta
->utiles
;
313 rbuf
= art_new (int, width
* height
);
314 for (i
= 0; i
< width
* height
; i
++)
319 for (i
= 0; vec
[i
].code
!= ART_END
; i
++)
328 art_uta_add_line (uta
, vec
[i
].x
, vec
[i
].y
, x
, y
, rbuf
, width
);
333 /* this shouldn't happen */
340 /* now add in the filling from rbuf */
342 for (yt
= 0; yt
< height
; yt
++)
345 for (xt
= 0; xt
< width
; xt
++)
348 /* Nonzero winding rule - others are possible, but hardly
354 bb
|= (ART_UTILE_SIZE
<< 8) | ART_UTILE_SIZE
;
360 bb
|= ART_UTILE_SIZE
;
363 if (yt
!= height
- 1)
365 bb
= utiles
[ix
+ width
];
367 bb
|= ART_UTILE_SIZE
<< 8;
368 utiles
[ix
+ width
] = bb
;
371 utiles
[ix
+ width
+ 1] &= 0xffff;