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 "art_svp_render_aa.h"
26 #include <string.h> /* for memmove */
34 typedef double artfloat;
36 struct _ArtSVPRenderAAIter {
48 ArtSVPRenderAAStep *steps;
52 art_svp_render_insert_active (int i, int *active_segs, int n_active_segs,
53 artfloat *seg_x, artfloat *seg_dx)
59 /* this is a cheap hack to get ^'s sorted correctly */
60 x = seg_x[i] + 0.001 * seg_dx[i];
61 for (j = 0; j < n_active_segs && seg_x[active_segs[j]] < x; j++);
64 while (j < n_active_segs)
66 tmp2 = active_segs[j];
67 active_segs[j] = tmp1;
71 active_segs[j] = tmp1;
75 art_svp_render_delete_active (int *active_segs, int j, int n_active_segs)
79 for (k = j; k < n_active_segs; k++)
80 active_segs[k] = active_segs[k + 1];
85 /* Render the sorted vector path in the given rectangle, antialiased.
87 This interface uses a callback for the actual pixel rendering. The
88 callback is called y1 - y0 times (once for each scan line). The y
89 coordinate is given as an argument for convenience (it could be
90 stored in the callback's private data and incremented on each
93 The rendered polygon is represented in a semi-runlength format: a
94 start value and a sequence of "steps". Each step has an x
95 coordinate and a value delta. The resulting value at position x is
96 equal to the sum of the start value and all step delta values for
97 which the step x coordinate is less than or equal to x. An
98 efficient algorithm will traverse the steps left to right, keeping
101 All x coordinates in the steps are guaranteed to be x0 <= x < x1.
102 (This guarantee is a change from the gfonted vpaar renderer, and is
103 designed to simplify the callback).
105 There is now a further guarantee that no two steps will have the
106 same x value. This may allow for further speedup and simplification
109 The value 0x8000 represents 0% coverage by the polygon, while
110 0xff8000 represents 100% coverage. This format is designed so that
111 >> 16 results in a standard 0x00..0xff value range, with nice
114 Status of this routine:
116 Basic correctness: OK
118 Numerical stability: pretty good, although probably not
121 Speed: Needs more aggressive culling of bounding boxes. Can
122 probably speed up the [x0,x1) clipping of step values. Can do more
123 of the step calculation in fixed point.
125 Precision: No known problems, although it should be tested
126 thoroughly, especially for symmetry.
131 art_svp_render_aa_iter (const ArtSVP *svp,
132 int x0, int y0, int x1, int y1)
134 ArtSVPRenderAAIter *iter = art_new (ArtSVPRenderAAIter, 1);
142 iter->active_segs = art_new (int, svp->n_segs);
143 iter->cursor = art_new (int, svp->n_segs);
144 iter->seg_x = art_new (artfloat, svp->n_segs);
145 iter->seg_dx = art_new (artfloat, svp->n_segs);
146 iter->steps = art_new (ArtSVPRenderAAStep, x1 - x0);
147 iter->n_active_segs = 0;
152 #define ADD_STEP(xpos, xdelta) \
153 /* stereotype code fragment for adding a step */ \
154 if (n_steps == 0 || steps[n_steps - 1].x < xpos) \
157 steps[sx].x = xpos; \
158 steps[sx].delta = xdelta; \
163 for (sx = n_steps; sx > 0; sx--) \
165 if (steps[sx - 1].x == xpos) \
167 steps[sx - 1].delta += xdelta; \
171 else if (steps[sx - 1].x < xpos) \
178 memmove (&steps[sx + 1], &steps[sx], \
179 (n_steps - sx) * sizeof(steps[0])); \
180 steps[sx].x = xpos; \
181 steps[sx].delta = xdelta; \
187 art_svp_render_aa_iter_step (ArtSVPRenderAAIter *iter, int *p_start,
188 ArtSVPRenderAAStep **p_steps, int *p_n_steps)
190 const ArtSVP *svp = iter->svp;
191 int *active_segs = iter->active_segs;
192 int n_active_segs = iter->n_active_segs;
193 int *cursor = iter->cursor;
194 artfloat *seg_x = iter->seg_x;
195 artfloat *seg_dx = iter->seg_dx;
196 int i = iter->seg_ix;
204 ArtSVPRenderAAStep *steps = iter->steps;
206 artfloat y_top, y_bot;
207 artfloat x_top, x_bot;
208 artfloat x_min, x_max;
210 artfloat delta; /* delta should be int too? */
213 artfloat rslope, drslope;
215 const ArtSVPSeg *seg;
221 /* insert new active segments */
222 for (; i < svp->n_segs && svp->segs[i].bbox.y0 < y + 1; i++)
224 if (svp->segs[i].bbox.y1 > y &&
225 svp->segs[i].bbox.x0 < x1)
228 /* move cursor to topmost vector which overlaps [y,y+1) */
229 for (curs = 0; seg->points[curs + 1].y < y; curs++);
231 dy = seg->points[curs + 1].y - seg->points[curs].y;
232 if (fabs (dy) >= EPSILON)
233 seg_dx[i] = (seg->points[curs + 1].x - seg->points[curs].x) /
237 seg_x[i] = seg->points[curs].x +
238 (y - seg->points[curs].y) * seg_dx[i];
239 art_svp_render_insert_active (i, active_segs, n_active_segs++,
246 /* render the runlengths, advancing and deleting as we go */
249 for (j = 0; j < n_active_segs; j++)
251 seg_index = active_segs[j];
252 seg = &svp->segs[seg_index];
253 curs = cursor[seg_index];
254 while (curs != seg->n_points - 1 &&
255 seg->points[curs].y < y + 1)
258 if (y_top < seg->points[curs].y)
259 y_top = seg->points[curs].y;
261 if (y_bot > seg->points[curs + 1].y)
262 y_bot = seg->points[curs + 1].y;
263 if (y_top != y_bot) {
264 delta = (seg->dir ? 16711680.0 : -16711680.0) *
266 x_top = seg_x[seg_index] + (y_top - y) * seg_dx[seg_index];
267 x_bot = seg_x[seg_index] + (y_bot - y) * seg_dx[seg_index];
278 ix_min = floor (x_min);
279 ix_max = floor (x_max);
282 /* skip; it starts to the right of the render region */
284 else if (ix_max < x0)
285 /* it ends to the left of the render region */
287 else if (ix_min == ix_max)
289 /* case 1, antialias a single pixel */
290 xdelta = (ix_min + 1 - (x_min + x_max) * 0.5) * delta;
292 ADD_STEP(ix_min, xdelta)
296 xdelta = delta - xdelta;
298 ADD_STEP(ix_min + 1, xdelta)
303 /* case 2, antialias a run */
304 rslope = 1.0 / fabs (seg_dx[seg_index]);
305 drslope = delta * rslope;
308 (ix_min + 1 - x_min) * (ix_min + 1 - x_min);
312 ADD_STEP(ix_min, xdelta)
323 for (; x < ix_max; x++)
325 this = (seg->dir ? 16711680.0 : -16711680.0) * rslope *
327 xdelta = this - last;
336 (x_max - ix_max) * (x_max - ix_max) *
338 xdelta = this - last;
345 xdelta = delta - last;
347 ADD_STEP(x + 1, xdelta)
353 if (curs != seg->n_points - 1 &&
354 seg->points[curs].y < y + 1)
356 dy = seg->points[curs + 1].y - seg->points[curs].y;
357 if (fabs (dy) >= EPSILON)
358 seg_dx[seg_index] = (seg->points[curs + 1].x -
359 seg->points[curs].x) / dy;
361 seg_dx[seg_index] = 1e12;
362 seg_x[seg_index] = seg->points[curs].x +
363 (y - seg->points[curs].y) * seg_dx[seg_index];
365 /* break here, instead of duplicating predicate in while? */
367 if (seg->points[curs].y >= y + 1)
370 cursor[seg_index] = curs;
371 seg_x[seg_index] += seg_dx[seg_index];
375 art_svp_render_delete_active (active_segs, j--,
382 *p_n_steps = n_steps;
385 iter->n_active_segs = n_active_segs;
390 art_svp_render_aa_iter_done (ArtSVPRenderAAIter *iter)
392 art_free (iter->steps);
394 art_free (iter->seg_dx);
395 art_free (iter->seg_x);
396 art_free (iter->cursor);
397 art_free (iter->active_segs);
402 * art_svp_render_aa: Render SVP antialiased.
403 * @svp: The #ArtSVP to render.
404 * @x0: Left coordinate of destination rectangle.
405 * @y0: Top coordinate of destination rectangle.
406 * @x1: Right coordinate of destination rectangle.
407 * @y1: Bottom coordinate of destination rectangle.
408 * @callback: The callback which actually paints the pixels.
409 * @callback_data: Private data for @callback.
411 * Renders the sorted vector path in the given rectangle, antialiased.
413 * This interface uses a callback for the actual pixel rendering. The
414 * callback is called @y1 - @y0 times (once for each scan line). The y
415 * coordinate is given as an argument for convenience (it could be
416 * stored in the callback's private data and incremented on each
419 * The rendered polygon is represented in a semi-runlength format: a
420 * start value and a sequence of "steps". Each step has an x
421 * coordinate and a value delta. The resulting value at position x is
422 * equal to the sum of the start value and all step delta values for
423 * which the step x coordinate is less than or equal to x. An
424 * efficient algorithm will traverse the steps left to right, keeping
427 * All x coordinates in the steps are guaranteed to be @x0 <= x < @x1.
428 * (This guarantee is a change from the gfonted vpaar renderer from
429 * which this routine is derived, and is designed to simplify the
432 * The value 0x8000 represents 0% coverage by the polygon, while
433 * 0xff8000 represents 100% coverage. This format is designed so that
434 * >> 16 results in a standard 0x00..0xff value range, with nice
439 art_svp_render_aa (const ArtSVP *svp,
440 int x0, int y0, int x1, int y1,
441 void (*callback) (void *callback_data,
444 ArtSVPRenderAAStep *steps, int n_steps),
447 ArtSVPRenderAAIter *iter;
450 ArtSVPRenderAAStep *steps;
453 iter = art_svp_render_aa_iter (svp, x0, y0, x1, y1);
456 for (y = y0; y < y1; y++)
458 art_svp_render_aa_iter_step (iter, &start, &steps, &n_steps);
459 (*callback) (callback_data, y, start, steps, n_steps);
462 art_svp_render_aa_iter_done (iter);