libraries/libart_lgpl-2.3.7/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 <math.h>
  23 #include <string.h> /* for memmove */
  24 #include "art_misc.h"
  25
  26 #include "art_rect.h"
  27 #include "art_svp.h"
  28
  29 #include "art_svp_render_aa.h"
  30 #include "stdio.h"
  31
  32 typedef double artfloat;
  33
  34 struct _ArtSVPRenderAAIter {
  35   const ArtSVP *svp;
  36   int x0, x1;
  37   int y;
  38   int seg_ix;
  39
  40   int *active_segs;
  41   int n_active_segs;
  42   int *cursor;
  43   artfloat *seg_x;
  44   artfloat *seg_dx;
  45
  46   ArtSVPRenderAAStep *steps;
  47 };
  48
  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;
  56
  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++);
  60
  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 }
  71
  72 static void
  73 art_svp_render_delete_active (int *active_segs, int j, int n_active_segs)
  74 {
  75   int k;
  76
  77   for (k = j; k < n_active_segs; k++)
  78     active_segs[k] = active_segs[k + 1];
  79 }
  80
  81 #define EPSILON 1e-6
  82
  83 /* Render the sorted vector path in the given rectangle, antialiased.
  84
  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).
  90
  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.
  98
  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).
 102
 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.
 106
 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.
 111
 112    Status of this routine:
 113
 114    Basic correctness: OK
 115
 116    Numerical stability: pretty good, although probably not
 117    bulletproof.
 118
 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.
 122
 123    Precision: No known problems, although it should be tested
 124    thoroughly, especially for symmetry.
 125
 126 */
 127
 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);
 133
 134   iter->svp = svp;
 135   iter->y = y0;
 136   iter->x0 = x0;
 137   iter->x1 = x1;
 138   iter->seg_ix = 0;
 139
 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;
 146
 147   return iter;
 148 }
 149
 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     }
 183
 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;
 200
 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;
 216
 217   int sx;
 218
 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     }
 241
 242   n_steps = 0;
 243
 244   /* render the runlengths, advancing and deleting as we go */
 245   start = 0x8000;
 246
 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;
 289
 290                 ADD_STEP(ix_min, xdelta)
 291
 292                 if (ix_min + 1 < x1)
 293                   {
 294                     xdelta = delta - xdelta;
 295
 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)
 311
 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;
 327
 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;
 338
 339                     ADD_STEP(x, xdelta)
 340
 341                     if (x + 1 < x1)
 342                       {
 343                         xdelta = delta - last;
 344
 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     }
 377
 378   *p_start = start;
 379   *p_steps = steps;
 380   *p_n_steps = n_steps;
 381
 382   iter->seg_ix = i;
 383   iter->n_active_segs = n_active_segs;
 384   iter->y++;
 385 }
 386
 387 void
 388 art_svp_render_aa_iter_done (ArtSVPRenderAAIter *iter)
 389 {
 390   art_free (iter->steps);
 391
 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 }
 398
 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;
 450
 451   iter = art_svp_render_aa_iter (svp, x0, y0, x1, y1);
 452
 453
 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     }
 459
 460   art_svp_render_aa_iter_done (iter);
 461 }