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 /* The spiffy antialiased renderer for sorted vector paths. */
22 #include <math.h>
23 #include <string.h> /* for memmove */
24 #include "art_misc.h"
26 #include "art_rect.h"
27 #include "art_svp.h"
29 #include "art_svp_render_aa.h"
30 #include "stdio.h"
32 typedef double artfloat;
34 struct _ArtSVPRenderAAIter {
35 const ArtSVP *svp;
36 int x0, x1;
37 int y;
38 int seg_ix;
40 int *active_segs;
41 int n_active_segs;
42 int *cursor;
43 artfloat *seg_x;
44 artfloat *seg_dx;
46 ArtSVPRenderAAStep *steps;
47 };
49 static void
50 art_svp_render_insert_active (int i, int *active_segs, int n_active_segs,
51 artfloat *seg_x, artfloat *seg_dx)
52 {
53 int j;
54 artfloat x;
55 int tmp1, tmp2;
57 /* this is a cheap hack to get ^'s sorted correctly */
58 x = seg_x[i] + 0.001 * seg_dx[i];
59 for (j = 0; j < n_active_segs && seg_x[active_segs[j]] < x; j++);
61 tmp1 = i;
62 while (j < n_active_segs)
63 {
64 tmp2 = active_segs[j];
65 active_segs[j] = tmp1;
66 tmp1 = tmp2;
67 j++;
68 }
69 active_segs[j] = tmp1;
70 }
72 static void
73 art_svp_render_delete_active (int *active_segs, int j, int n_active_segs)
74 {
75 int k;
77 for (k = j; k < n_active_segs; k++)
78 active_segs[k] = active_segs[k + 1];
79 }
81 #define EPSILON 1e-6
83 /* Render the sorted vector path in the given rectangle, antialiased.
85 This interface uses a callback for the actual pixel rendering. The
86 callback is called y1 - y0 times (once for each scan line). The y
87 coordinate is given as an argument for convenience (it could be
88 stored in the callback's private data and incremented on each
89 call).
91 The rendered polygon is represented in a semi-runlength format: a
92 start value and a sequence of "steps". Each step has an x
93 coordinate and a value delta. The resulting value at position x is
94 equal to the sum of the start value and all step delta values for
95 which the step x coordinate is less than or equal to x. An
96 efficient algorithm will traverse the steps left to right, keeping
97 a running sum.
99 All x coordinates in the steps are guaranteed to be x0 <= x < x1.
100 (This guarantee is a change from the gfonted vpaar renderer, and is
101 designed to simplify the callback).
103 There is now a further guarantee that no two steps will have the
104 same x value. This may allow for further speedup and simplification
105 of renderers.
107 The value 0x8000 represents 0% coverage by the polygon, while
108 0xff8000 represents 100% coverage. This format is designed so that
109 >> 16 results in a standard 0x00..0xff value range, with nice
110 rounding.
112 Status of this routine:
114 Basic correctness: OK
116 Numerical stability: pretty good, although probably not
117 bulletproof.
119 Speed: Needs more aggressive culling of bounding boxes. Can
120 probably speed up the [x0,x1) clipping of step values. Can do more
121 of the step calculation in fixed point.
123 Precision: No known problems, although it should be tested
124 thoroughly, especially for symmetry.
126 */
128 ArtSVPRenderAAIter *
129 art_svp_render_aa_iter (const ArtSVP *svp,
130 int x0, int y0, int x1, int y1)
131 {
132 ArtSVPRenderAAIter *iter = art_new (ArtSVPRenderAAIter, 1);
134 iter->svp = svp;
135 iter->y = y0;
136 iter->x0 = x0;
137 iter->x1 = x1;
138 iter->seg_ix = 0;
140 iter->active_segs = art_new (int, svp->n_segs);
141 iter->cursor = art_new (int, svp->n_segs);
142 iter->seg_x = art_new (artfloat, svp->n_segs);
143 iter->seg_dx = art_new (artfloat, svp->n_segs);
144 iter->steps = art_new (ArtSVPRenderAAStep, x1 - x0);
145 iter->n_active_segs = 0;
147 return iter;
148 }
150 #define ADD_STEP(xpos, xdelta) \
151 /* stereotype code fragment for adding a step */ \
152 if (n_steps == 0 || steps[n_steps - 1].x < xpos) \
153 { \
154 sx = n_steps; \
155 steps[sx].x = xpos; \
156 steps[sx].delta = xdelta; \
157 n_steps++; \
158 } \
159 else \
160 { \
161 for (sx = n_steps; sx > 0; sx--) \
162 { \
163 if (steps[sx - 1].x == xpos) \
164 { \
165 steps[sx - 1].delta += xdelta; \
166 sx = n_steps; \
167 break; \
168 } \
169 else if (steps[sx - 1].x < xpos) \
170 { \
171 break; \
172 } \
173 } \
174 if (sx < n_steps) \
175 { \
176 memmove (&steps[sx + 1], &steps[sx], \
177 (n_steps - sx) * sizeof(steps[0])); \
178 steps[sx].x = xpos; \
179 steps[sx].delta = xdelta; \
180 n_steps++; \
181 } \
182 }
184 void
185 art_svp_render_aa_iter_step (ArtSVPRenderAAIter *iter, int *p_start,
186 ArtSVPRenderAAStep **p_steps, int *p_n_steps)
187 {
188 const ArtSVP *svp = iter->svp;
189 int *active_segs = iter->active_segs;
190 int n_active_segs = iter->n_active_segs;
191 int *cursor = iter->cursor;
192 artfloat *seg_x = iter->seg_x;
193 artfloat *seg_dx = iter->seg_dx;
194 int i = iter->seg_ix;
195 int j;
196 int x0 = iter->x0;
197 int x1 = iter->x1;
198 int y = iter->y;
199 int seg_index;
201 int x;
202 ArtSVPRenderAAStep *steps = iter->steps;
203 int n_steps;
204 artfloat y_top, y_bot;
205 artfloat x_top, x_bot;
206 artfloat x_min, x_max;
207 int ix_min, ix_max;
208 artfloat delta; /* delta should be int too? */
209 int last, this;
210 int xdelta;
211 artfloat rslope, drslope;
212 int start;
213 const ArtSVPSeg *seg;
214 int curs;
215 artfloat dy;
217 int sx;
219 /* insert new active segments */
220 for (; i < svp->n_segs && svp->segs[i].bbox.y0 < y + 1; i++)
221 {
222 if (svp->segs[i].bbox.y1 > y &&
223 svp->segs[i].bbox.x0 < x1)
224 {
225 seg = &svp->segs[i];
226 /* move cursor to topmost vector which overlaps [y,y+1) */
227 for (curs = 0; seg->points[curs + 1].y < y; curs++);
228 cursor[i] = curs;
229 dy = seg->points[curs + 1].y - seg->points[curs].y;
230 if (fabs (dy) >= EPSILON)
231 seg_dx[i] = (seg->points[curs + 1].x - seg->points[curs].x) /
232 dy;
233 else
234 seg_dx[i] = 1e12;
235 seg_x[i] = seg->points[curs].x +
236 (y - seg->points[curs].y) * seg_dx[i];
237 art_svp_render_insert_active (i, active_segs, n_active_segs++,
238 seg_x, seg_dx);
239 }
240 }
242 n_steps = 0;
244 /* render the runlengths, advancing and deleting as we go */
245 start = 0x8000;
247 for (j = 0; j < n_active_segs; j++)
248 {
249 seg_index = active_segs[j];
250 seg = &svp->segs[seg_index];
251 curs = cursor[seg_index];
252 while (curs != seg->n_points - 1 &&
253 seg->points[curs].y < y + 1)
254 {
255 y_top = y;
256 if (y_top < seg->points[curs].y)
257 y_top = seg->points[curs].y;
258 y_bot = y + 1;
259 if (y_bot > seg->points[curs + 1].y)
260 y_bot = seg->points[curs + 1].y;
261 if (y_top != y_bot) {
262 delta = (seg->dir ? 16711680.0 : -16711680.0) *
263 (y_bot - y_top);
264 x_top = seg_x[seg_index] + (y_top - y) * seg_dx[seg_index];
265 x_bot = seg_x[seg_index] + (y_bot - y) * seg_dx[seg_index];
266 if (x_top < x_bot)
267 {
268 x_min = x_top;
269 x_max = x_bot;
270 }
271 else
272 {
273 x_min = x_bot;
274 x_max = x_top;
275 }
276 ix_min = floor (x_min);
277 ix_max = floor (x_max);
278 if (ix_min >= x1)
279 {
280 /* skip; it starts to the right of the render region */
281 }
282 else if (ix_max < x0)
283 /* it ends to the left of the render region */
284 start += delta;
285 else if (ix_min == ix_max)
286 {
287 /* case 1, antialias a single pixel */
288 xdelta = (ix_min + 1 - (x_min + x_max) * 0.5) * delta;
290 ADD_STEP(ix_min, xdelta)
292 if (ix_min + 1 < x1)
293 {
294 xdelta = delta - xdelta;
296 ADD_STEP(ix_min + 1, xdelta)
297 }
298 }
299 else
300 {
301 /* case 2, antialias a run */
302 rslope = 1.0 / fabs (seg_dx[seg_index]);
303 drslope = delta * rslope;
304 last =
305 drslope * 0.5 *
306 (ix_min + 1 - x_min) * (ix_min + 1 - x_min);
307 xdelta = last;
308 if (ix_min >= x0)
309 {
310 ADD_STEP(ix_min, xdelta)
312 x = ix_min + 1;
313 }
314 else
315 {
316 start += last;
317 x = x0;
318 }
319 if (ix_max > x1)
320 ix_max = x1;
321 for (; x < ix_max; x++)
322 {
323 this = (seg->dir ? 16711680.0 : -16711680.0) * rslope *
324 (x + 0.5 - x_min);
325 xdelta = this - last;
326 last = this;
328 ADD_STEP(x, xdelta)
329 }
330 if (x < x1)
331 {
332 this =
333 delta * (1 - 0.5 *
334 (x_max - ix_max) * (x_max - ix_max) *
335 rslope);
336 xdelta = this - last;
337 last = this;
339 ADD_STEP(x, xdelta)
341 if (x + 1 < x1)
342 {
343 xdelta = delta - last;
345 ADD_STEP(x + 1, xdelta)
346 }
347 }
348 }
349 }
350 curs++;
351 if (curs != seg->n_points - 1 &&
352 seg->points[curs].y < y + 1)
353 {
354 dy = seg->points[curs + 1].y - seg->points[curs].y;
355 if (fabs (dy) >= EPSILON)
356 seg_dx[seg_index] = (seg->points[curs + 1].x -
357 seg->points[curs].x) / dy;
358 else
359 seg_dx[seg_index] = 1e12;
360 seg_x[seg_index] = seg->points[curs].x +
361 (y - seg->points[curs].y) * seg_dx[seg_index];
362 }
363 /* break here, instead of duplicating predicate in while? */
364 }
365 if (seg->points[curs].y >= y + 1)
366 {
367 curs--;
368 cursor[seg_index] = curs;
369 seg_x[seg_index] += seg_dx[seg_index];
370 }
371 else
372 {
373 art_svp_render_delete_active (active_segs, j--,
374 --n_active_segs);
375 }
376 }
378 *p_start = start;
379 *p_steps = steps;
380 *p_n_steps = n_steps;
382 iter->seg_ix = i;
383 iter->n_active_segs = n_active_segs;
384 iter->y++;
385 }
387 void
388 art_svp_render_aa_iter_done (ArtSVPRenderAAIter *iter)
389 {
390 art_free (iter->steps);
392 art_free (iter->seg_dx);
393 art_free (iter->seg_x);
394 art_free (iter->cursor);
395 art_free (iter->active_segs);
396 art_free (iter);
397 }
399 /**
400 * art_svp_render_aa: Render SVP antialiased.
401 * @svp: The #ArtSVP to render.
402 * @x0: Left coordinate of destination rectangle.
403 * @y0: Top coordinate of destination rectangle.
404 * @x1: Right coordinate of destination rectangle.
405 * @y1: Bottom coordinate of destination rectangle.
406 * @callback: The callback which actually paints the pixels.
407 * @callback_data: Private data for @callback.
408 *
409 * Renders the sorted vector path in the given rectangle, antialiased.
410 *
411 * This interface uses a callback for the actual pixel rendering. The
412 * callback is called @y1 - @y0 times (once for each scan line). The y
413 * coordinate is given as an argument for convenience (it could be
414 * stored in the callback's private data and incremented on each
415 * call).
416 *
417 * The rendered polygon is represented in a semi-runlength format: a
418 * start value and a sequence of "steps". Each step has an x
419 * coordinate and a value delta. The resulting value at position x is
420 * equal to the sum of the start value and all step delta values for
421 * which the step x coordinate is less than or equal to x. An
422 * efficient algorithm will traverse the steps left to right, keeping
423 * a running sum.
424 *
425 * All x coordinates in the steps are guaranteed to be @x0 <= x < @x1.
426 * (This guarantee is a change from the gfonted vpaar renderer from
427 * which this routine is derived, and is designed to simplify the
428 * callback).
429 *
430 * The value 0x8000 represents 0% coverage by the polygon, while
431 * 0xff8000 represents 100% coverage. This format is designed so that
432 * >> 16 results in a standard 0x00..0xff value range, with nice
433 * rounding.
434 *
435 **/
436 void
437 art_svp_render_aa (const ArtSVP *svp,
438 int x0, int y0, int x1, int y1,
439 void (*callback) (void *callback_data,
440 int y,
441 int start,
442 ArtSVPRenderAAStep *steps, int n_steps),
443 void *callback_data)
444 {
445 ArtSVPRenderAAIter *iter;
446 int y;
447 int start;
448 ArtSVPRenderAAStep *steps;
449 int n_steps;
451 iter = art_svp_render_aa_iter (svp, x0, y0, x1, y1);
454 for (y = y0; y < y1; y++)
455 {
456 art_svp_render_aa_iter_step (iter, &start, &steps, &n_steps);
457 (*callback) (callback_data, y, start, steps, n_steps);
458 }
460 art_svp_render_aa_iter_done (iter);
461 }