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 }