new function list_deep_free
[swftools.git] / lib / art / art_svp_render_aa.c
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
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
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 *
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
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, xthis;
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                     xthis = (seg->dir ? 16711680.0 : -16711680.0) * rslope *
326                       (x + 0.5 - x_min);
327                     xdelta = xthis - last;
328                     last = xthis;
329
330                     ADD_STEP(x, xdelta)
331                   }
332                 if (x < x1)
333                   {
334                     xthis =
335                       delta * (1 - 0.5 *
336                                (x_max - ix_max) * (x_max - ix_max) *
337                                rslope);
338                     xdelta = xthis - last;
339                     last = xthis;
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
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
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 }