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 /* The spiffy antialiased renderer for sorted vector paths. */
21
22 #include "config.h"
23 #include "art_svp_render_aa.h"
24
25 #include <math.h>
26 #include <string.h> /* for memmove */
27 #include "art_misc.h"
28
29 #include "art_rect.h"
30 #include "art_svp.h"
31
32 #include <stdio.h>
33
34 typedef double artfloat;
35
36 struct _ArtSVPRenderAAIter {
37 const ArtSVP *svp;
38 int x0, x1;
39 int y;
40 int seg_ix;
41
42 int *active_segs;
43 int n_active_segs;
44 int *cursor;
45 artfloat *seg_x;
46 artfloat *seg_dx;
47
48 ArtSVPRenderAAStep *steps;
49 };
50
51 static void
art_svp_render_insert_active(int i,int * active_segs,int n_active_segs,artfloat * seg_x,artfloat * seg_dx)52 art_svp_render_insert_active (int i, int *active_segs, int n_active_segs,
53 artfloat *seg_x, artfloat *seg_dx)
54 {
55 int j;
56 artfloat x;
57 int tmp1, tmp2;
58
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++);
62
63 tmp1 = i;
64 while (j < n_active_segs)
65 {
66 tmp2 = active_segs[j];
67 active_segs[j] = tmp1;
68 tmp1 = tmp2;
69 j++;
70 }
71 active_segs[j] = tmp1;
72 }
73
74 static void
art_svp_render_delete_active(int * active_segs,int j,int n_active_segs)75 art_svp_render_delete_active (int *active_segs, int j, int n_active_segs)
76 {
77 int k;
78
79 for (k = j; k < n_active_segs; k++)
80 active_segs[k] = active_segs[k + 1];
81 }
82
83 #define EPSILON 1e-6
84
85 /* Render the sorted vector path in the given rectangle, antialiased.
86
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
91 call).
92
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
99 a running sum.
100
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).
104
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
107 of renderers.
108
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
112 rounding.
113
114 Status of this routine:
115
116 Basic correctness: OK
117
118 Numerical stability: pretty good, although probably not
119 bulletproof.
120
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.
124
125 Precision: No known problems, although it should be tested
126 thoroughly, especially for symmetry.
127
128 */
129
130 ArtSVPRenderAAIter *
art_svp_render_aa_iter(const ArtSVP * svp,int x0,int y0,int x1,int y1)131 art_svp_render_aa_iter (const ArtSVP *svp,
132 int x0, int y0, int x1, int y1)
133 {
134 ArtSVPRenderAAIter *iter = art_new (ArtSVPRenderAAIter, 1);
135
136 iter->svp = svp;
137 iter->y = y0;
138 iter->x0 = x0;
139 iter->x1 = x1;
140 iter->seg_ix = 0;
141
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;
148
149 return iter;
150 }
151
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) \
155 { \
156 sx = n_steps; \
157 steps[sx].x = xpos; \
158 steps[sx].delta = xdelta; \
159 n_steps++; \
160 } \
161 else \
162 { \
163 for (sx = n_steps; sx > 0; sx--) \
164 { \
165 if (steps[sx - 1].x == xpos) \
166 { \
167 steps[sx - 1].delta += xdelta; \
168 sx = n_steps; \
169 break; \
170 } \
171 else if (steps[sx - 1].x < xpos) \
172 { \
173 break; \
174 } \
175 } \
176 if (sx < n_steps) \
177 { \
178 memmove (&steps[sx + 1], &steps[sx], \
179 (n_steps - sx) * sizeof(steps[0])); \
180 steps[sx].x = xpos; \
181 steps[sx].delta = xdelta; \
182 n_steps++; \
183 } \
184 }
185
186 void
art_svp_render_aa_iter_step(ArtSVPRenderAAIter * iter,int * p_start,ArtSVPRenderAAStep ** p_steps,int * p_n_steps)187 art_svp_render_aa_iter_step (ArtSVPRenderAAIter *iter, int *p_start,
188 ArtSVPRenderAAStep **p_steps, int *p_n_steps)
189 {
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;
197 int j;
198 int x0 = iter->x0;
199 int x1 = iter->x1;
200 int y = iter->y;
201 int seg_index;
202
203 int x;
204 ArtSVPRenderAAStep *steps = iter->steps;
205 int n_steps;
206 artfloat y_top, y_bot;
207 artfloat x_top, x_bot;
208 artfloat x_min, x_max;
209 int ix_min, ix_max;
210 artfloat delta; /* delta should be int too? */
211 int last, this;
212 int xdelta;
213 artfloat rslope, drslope;
214 int start;
215 const ArtSVPSeg *seg;
216 int curs;
217 artfloat dy;
218
219 int sx;
220
221 /* insert new active segments */
222 for (; i < svp->n_segs && svp->segs[i].bbox.y0 < y + 1; i++)
223 {
224 if (svp->segs[i].bbox.y1 > y &&
225 svp->segs[i].bbox.x0 < x1)
226 {
227 seg = &svp->segs[i];
228 /* move cursor to topmost vector which overlaps [y,y+1) */
229 for (curs = 0; seg->points[curs + 1].y < y; curs++);
230 cursor[i] = 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) /
234 dy;
235 else
236 seg_dx[i] = 1e12;
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++,
240 seg_x, seg_dx);
241 }
242 }
243
244 n_steps = 0;
245
246 /* render the runlengths, advancing and deleting as we go */
247 start = 0x8000;
248
249 for (j = 0; j < n_active_segs; j++)
250 {
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)
256 {
257 y_top = y;
258 if (y_top < seg->points[curs].y)
259 y_top = seg->points[curs].y;
260 y_bot = y + 1;
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) *
265 (y_bot - y_top);
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];
268 if (x_top < x_bot)
269 {
270 x_min = x_top;
271 x_max = x_bot;
272 }
273 else
274 {
275 x_min = x_bot;
276 x_max = x_top;
277 }
278 ix_min = floor (x_min);
279 ix_max = floor (x_max);
280 if (ix_min >= x1)
281 {
282 /* skip; it starts to the right of the render region */
283 }
284 else if (ix_max < x0)
285 /* it ends to the left of the render region */
286 start += delta;
287 else if (ix_min == ix_max)
288 {
289 /* case 1, antialias a single pixel */
290 xdelta = (ix_min + 1 - (x_min + x_max) * 0.5) * delta;
291
292 ADD_STEP(ix_min, xdelta)
293
294 if (ix_min + 1 < x1)
295 {
296 xdelta = delta - xdelta;
297
298 ADD_STEP(ix_min + 1, xdelta)
299 }
300 }
301 else
302 {
303 /* case 2, antialias a run */
304 rslope = 1.0 / fabs (seg_dx[seg_index]);
305 drslope = delta * rslope;
306 last =
307 drslope * 0.5 *
308 (ix_min + 1 - x_min) * (ix_min + 1 - x_min);
309 xdelta = last;
310 if (ix_min >= x0)
311 {
312 ADD_STEP(ix_min, xdelta)
313
314 x = ix_min + 1;
315 }
316 else
317 {
318 start += last;
319 x = x0;
320 }
321 if (ix_max > x1)
322 ix_max = x1;
323 for (; x < ix_max; x++)
324 {
325 this = (seg->dir ? 16711680.0 : -16711680.0) * rslope *
326 (x + 0.5 - x_min);
327 xdelta = this - last;
328 last = this;
329
330 ADD_STEP(x, xdelta)
331 }
332 if (x < x1)
333 {
334 this =
335 delta * (1 - 0.5 *
336 (x_max - ix_max) * (x_max - ix_max) *
337 rslope);
338 xdelta = this - last;
339 last = this;
340
341 ADD_STEP(x, xdelta)
342
343 if (x + 1 < x1)
344 {
345 xdelta = delta - last;
346
347 ADD_STEP(x + 1, xdelta)
348 }
349 }
350 }
351 }
352 curs++;
353 if (curs != seg->n_points - 1 &&
354 seg->points[curs].y < y + 1)
355 {
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;
360 else
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];
364 }
365 /* break here, instead of duplicating predicate in while? */
366 }
367 if (seg->points[curs].y >= y + 1)
368 {
369 curs--;
370 cursor[seg_index] = curs;
371 seg_x[seg_index] += seg_dx[seg_index];
372 }
373 else
374 {
375 art_svp_render_delete_active (active_segs, j--,
376 --n_active_segs);
377 }
378 }
379
380 *p_start = start;
381 *p_steps = steps;
382 *p_n_steps = n_steps;
383
384 iter->seg_ix = i;
385 iter->n_active_segs = n_active_segs;
386 iter->y++;
387 }
388
389 void
art_svp_render_aa_iter_done(ArtSVPRenderAAIter * iter)390 art_svp_render_aa_iter_done (ArtSVPRenderAAIter *iter)
391 {
392 art_free (iter->steps);
393
394 art_free (iter->seg_dx);
395 art_free (iter->seg_x);
396 art_free (iter->cursor);
397 art_free (iter->active_segs);
398 art_free (iter);
399 }
400
401 /**
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.
410 *
411 * Renders the sorted vector path in the given rectangle, antialiased.
412 *
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
417 * call).
418 *
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
425 * a running sum.
426 *
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
430 * callback).
431 *
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
435 * rounding.
436 *
437 **/
438 void
art_svp_render_aa(const ArtSVP * svp,int x0,int y0,int x1,int y1,void (* callback)(void * callback_data,int y,int start,ArtSVPRenderAAStep * steps,int n_steps),void * callback_data)439 art_svp_render_aa (const ArtSVP *svp,
440 int x0, int y0, int x1, int y1,
441 void (*callback) (void *callback_data,
442 int y,
443 int start,
444 ArtSVPRenderAAStep *steps, int n_steps),
445 void *callback_data)
446 {
447 ArtSVPRenderAAIter *iter;
448 int y;
449 int start;
450 ArtSVPRenderAAStep *steps;
451 int n_steps;
452
453 iter = art_svp_render_aa_iter (svp, x0, y0, x1, y1);
454
455
456 for (y = y0; y < y1; y++)
457 {
458 art_svp_render_aa_iter_step (iter, &start, &steps, &n_steps);
459 (*callback) (callback_data, y, start, steps, n_steps);
460 }
461
462 art_svp_render_aa_iter_done (iter);
463 }
464