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.
20 /* The spiffy antialiased renderer for sorted vector paths. */
23 #include <string.h> /* for memmove */
29 #include "art_svp_render_aa.h"
32 typedef double artfloat;
34 struct _ArtSVPRenderAAIter {
46 ArtSVPRenderAAStep *steps;
50 art_svp_render_insert_active (int i, int *active_segs, int n_active_segs,
51 artfloat *seg_x, artfloat *seg_dx)
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++);
62 while (j < n_active_segs)
64 tmp2 = active_segs[j];
65 active_segs[j] = tmp1;
69 active_segs[j] = tmp1;
73 art_svp_render_delete_active (int *active_segs, int j, int n_active_segs)
77 for (k = j; k < n_active_segs; k++)
78 active_segs[k] = active_segs[k + 1];
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
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
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
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
112 Status of this routine:
114 Basic correctness: OK
116 Numerical stability: pretty good, although probably not
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.
129 art_svp_render_aa_iter (const ArtSVP *svp,
130 int x0, int y0, int x1, int y1)
132 ArtSVPRenderAAIter *iter = art_new (ArtSVPRenderAAIter, 1);
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;
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) \
155 steps[sx].x = xpos; \
156 steps[sx].delta = xdelta; \
161 for (sx = n_steps; sx > 0; sx--) \
163 if (steps[sx - 1].x == xpos) \
165 steps[sx - 1].delta += xdelta; \
169 else if (steps[sx - 1].x < xpos) \
176 memmove (&steps[sx + 1], &steps[sx], \
177 (n_steps - sx) * sizeof(steps[0])); \
178 steps[sx].x = xpos; \
179 steps[sx].delta = xdelta; \
185 art_svp_render_aa_iter_step (ArtSVPRenderAAIter *iter, int *p_start,
186 ArtSVPRenderAAStep **p_steps, int *p_n_steps)
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;
202 ArtSVPRenderAAStep *steps = iter->steps;
204 artfloat y_top, y_bot;
205 artfloat x_top, x_bot;
206 artfloat x_min, x_max;
208 artfloat delta; /* delta should be int too? */
211 artfloat rslope, drslope;
213 const ArtSVPSeg *seg;
219 /* insert new active segments */
220 for (; i < svp->n_segs && svp->segs[i].bbox.y0 < y + 1; i++)
222 if (svp->segs[i].bbox.y1 > y &&
223 svp->segs[i].bbox.x0 < x1)
226 /* move cursor to topmost vector which overlaps [y,y+1) */
227 for (curs = 0; seg->points[curs + 1].y < y; 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) /
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++,
244 /* render the runlengths, advancing and deleting as we go */
247 for (j = 0; j < n_active_segs; j++)
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)
256 if (y_top < seg->points[curs].y)
257 y_top = seg->points[curs].y;
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) *
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];
276 ix_min = floor (x_min);
277 ix_max = floor (x_max);
280 /* skip; it starts to the right of the render region */
282 else if (ix_max < x0)
283 /* it ends to the left of the render region */
285 else if (ix_min == ix_max)
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)
294 xdelta = delta - xdelta;
296 ADD_STEP(ix_min + 1, xdelta)
301 /* case 2, antialias a run */
302 rslope = 1.0 / fabs (seg_dx[seg_index]);
303 drslope = delta * rslope;
306 (ix_min + 1 - x_min) * (ix_min + 1 - x_min);
310 ADD_STEP(ix_min, xdelta)
321 for (; x < ix_max; x++)
323 this = (seg->dir ? 16711680.0 : -16711680.0) * rslope *
325 xdelta = this - last;
334 (x_max - ix_max) * (x_max - ix_max) *
336 xdelta = this - last;
343 xdelta = delta - last;
345 ADD_STEP(x + 1, xdelta)
351 if (curs != seg->n_points - 1 &&
352 seg->points[curs].y < y + 1)
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;
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];
363 /* break here, instead of duplicating predicate in while? */
365 if (seg->points[curs].y >= y + 1)
368 cursor[seg_index] = curs;
369 seg_x[seg_index] += seg_dx[seg_index];
373 art_svp_render_delete_active (active_segs, j--,
380 *p_n_steps = n_steps;
383 iter->n_active_segs = n_active_segs;
388 art_svp_render_aa_iter_done (ArtSVPRenderAAIter *iter)
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);
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.
409 * Renders the sorted vector path in the given rectangle, antialiased.
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
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
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
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
437 art_svp_render_aa (const ArtSVP *svp,
438 int x0, int y0, int x1, int y1,
439 void (*callback) (void *callback_data,
442 ArtSVPRenderAAStep *steps, int n_steps),
445 ArtSVPRenderAAIter *iter;
448 ArtSVPRenderAAStep *steps;
451 iter = art_svp_render_aa_iter (svp, x0, y0, x1, y1);
454 for (y = y0; y < y1; y++)
456 art_svp_render_aa_iter_step (iter, &start, &steps, &n_steps);
457 (*callback) (callback_data, y, start, steps, n_steps);
460 art_svp_render_aa_iter_done (iter);