source: trunk/third/libart_lgpl/art_svp_render_aa.c @ 18256

/* Libart_LGPL - library of basic graphic primitives
 * Copyright (C) 1998-2000 Raph Levien
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

/* The spiffy antialiased renderer for sorted vector paths. */

#include "config.h"
#include "art_svp_render_aa.h"

#include <math.h>
#include <string.h> /* for memmove */
#include "art_misc.h"

#include "art_rect.h"
#include "art_svp.h"

#include <stdio.h>

typedef double artfloat;

struct _ArtSVPRenderAAIter {
  const ArtSVP *svp;
  int x0, x1;
  int y;
  int seg_ix;

  int *active_segs;
  int n_active_segs;
  int *cursor;
  artfloat *seg_x;
  artfloat *seg_dx;

  ArtSVPRenderAAStep *steps;
};

static void
art_svp_render_insert_active (int i, int *active_segs, int n_active_segs,
                              artfloat *seg_x, artfloat *seg_dx)
{
  int j;
  artfloat x;
  int tmp1, tmp2;

  /* this is a cheap hack to get ^'s sorted correctly */
  x = seg_x[i] + 0.001 * seg_dx[i];
  for (j = 0; j < n_active_segs && seg_x[active_segs[j]] < x; j++);

  tmp1 = i;
  while (j < n_active_segs)
    {
      tmp2 = active_segs[j];
      active_segs[j] = tmp1;
      tmp1 = tmp2;
      j++;
    }
  active_segs[j] = tmp1;
}

static void
art_svp_render_delete_active (int *active_segs, int j, int n_active_segs)
{
  int k;

  for (k = j; k < n_active_segs; k++)
    active_segs[k] = active_segs[k + 1];
}

#define EPSILON 1e-6

/* Render the sorted vector path in the given rectangle, antialiased.

   This interface uses a callback for the actual pixel rendering. The
   callback is called y1 - y0 times (once for each scan line). The y
   coordinate is given as an argument for convenience (it could be
   stored in the callback's private data and incremented on each
   call).

   The rendered polygon is represented in a semi-runlength format: a
   start value and a sequence of "steps". Each step has an x
   coordinate and a value delta. The resulting value at position x is
   equal to the sum of the start value and all step delta values for
   which the step x coordinate is less than or equal to x. An
   efficient algorithm will traverse the steps left to right, keeping
   a running sum.

   All x coordinates in the steps are guaranteed to be x0 <= x < x1.
   (This guarantee is a change from the gfonted vpaar renderer, and is
   designed to simplify the callback).

   There is now a further guarantee that no two steps will have the
   same x value. This may allow for further speedup and simplification
   of renderers.

   The value 0x8000 represents 0% coverage by the polygon, while
   0xff8000 represents 100% coverage. This format is designed so that
   >> 16 results in a standard 0x00..0xff value range, with nice
   rounding.

   Status of this routine:

   Basic correctness: OK

   Numerical stability: pretty good, although probably not
   bulletproof.

   Speed: Needs more aggressive culling of bounding boxes.  Can
   probably speed up the [x0,x1) clipping of step values.  Can do more
   of the step calculation in fixed point.

   Precision: No known problems, although it should be tested
   thoroughly, especially for symmetry.

*/

ArtSVPRenderAAIter *
art_svp_render_aa_iter (const ArtSVP *svp,
                        int x0, int y0, int x1, int y1)
{
  ArtSVPRenderAAIter *iter = art_new (ArtSVPRenderAAIter, 1);

  iter->svp = svp;
  iter->y = y0;
  iter->x0 = x0;
  iter->x1 = x1;
  iter->seg_ix = 0;

  iter->active_segs = art_new (int, svp->n_segs);
  iter->cursor = art_new (int, svp->n_segs);
  iter->seg_x = art_new (artfloat, svp->n_segs);
  iter->seg_dx = art_new (artfloat, svp->n_segs);
  iter->steps = art_new (ArtSVPRenderAAStep, x1 - x0);
  iter->n_active_segs = 0;

  return iter;
}

#define ADD_STEP(xpos, xdelta)                          \
  /* stereotype code fragment for adding a step */      \
  if (n_steps == 0 || steps[n_steps - 1].x < xpos)      \
    {                                                   \
      sx = n_steps;                                     \
      steps[sx].x = xpos;                               \
      steps[sx].delta = xdelta;                         \
      n_steps++;                                        \
    }                                                   \
  else                                                  \
    {                                                   \
      for (sx = n_steps; sx > 0; sx--)                  \
        {                                               \
          if (steps[sx - 1].x == xpos)                  \
            {                                           \
              steps[sx - 1].delta += xdelta;            \
              sx = n_steps;                             \
              break;                                    \
            }                                           \
          else if (steps[sx - 1].x < xpos)              \
            {                                           \
              break;                                    \
            }                                           \
        }                                               \
      if (sx < n_steps)                                 \
        {                                               \
          memmove (&steps[sx + 1], &steps[sx],          \
                   (n_steps - sx) * sizeof(steps[0]));  \
          steps[sx].x = xpos;                           \
          steps[sx].delta = xdelta;                     \
          n_steps++;                                    \
        }                                               \
    }

void
art_svp_render_aa_iter_step (ArtSVPRenderAAIter *iter, int *p_start,
                             ArtSVPRenderAAStep **p_steps, int *p_n_steps)
{
  const ArtSVP *svp = iter->svp;
  int *active_segs = iter->active_segs;
  int n_active_segs = iter->n_active_segs;
  int *cursor = iter->cursor;
  artfloat *seg_x = iter->seg_x;
  artfloat *seg_dx = iter->seg_dx;
  int i = iter->seg_ix;
  int j;
  int x0 = iter->x0;
  int x1 = iter->x1;
  int y = iter->y;
  int seg_index;

  int x;
  ArtSVPRenderAAStep *steps = iter->steps;
  int n_steps;
  artfloat y_top, y_bot;
  artfloat x_top, x_bot;
  artfloat x_min, x_max;
  int ix_min, ix_max;
  artfloat delta; /* delta should be int too? */
  int last, this;
  int xdelta;
  artfloat rslope, drslope;
  int start;
  const ArtSVPSeg *seg;
  int curs;
  artfloat dy;

  int sx;
  
  /* insert new active segments */
  for (; i < svp->n_segs && svp->segs[i].bbox.y0 < y + 1; i++)
    {
      if (svp->segs[i].bbox.y1 > y &&
          svp->segs[i].bbox.x0 < x1)
        {
          seg = &svp->segs[i];
          /* move cursor to topmost vector which overlaps [y,y+1) */
          for (curs = 0; seg->points[curs + 1].y < y; curs++);
          cursor[i] = curs;
          dy = seg->points[curs + 1].y - seg->points[curs].y;
          if (fabs (dy) >= EPSILON)
            seg_dx[i] = (seg->points[curs + 1].x - seg->points[curs].x) /
              dy;
          else
            seg_dx[i] = 1e12;
          seg_x[i] = seg->points[curs].x +
            (y - seg->points[curs].y) * seg_dx[i];
          art_svp_render_insert_active (i, active_segs, n_active_segs++,
                                        seg_x, seg_dx);
        }
    }

  n_steps = 0;

  /* render the runlengths, advancing and deleting as we go */
  start = 0x8000;

  for (j = 0; j < n_active_segs; j++)
    {
      seg_index = active_segs[j];
      seg = &svp->segs[seg_index];
      curs = cursor[seg_index];
      while (curs != seg->n_points - 1 &&
             seg->points[curs].y < y + 1)
        {
          y_top = y;
          if (y_top < seg->points[curs].y)
            y_top = seg->points[curs].y;
          y_bot = y + 1;
          if (y_bot > seg->points[curs + 1].y)
            y_bot = seg->points[curs + 1].y;
          if (y_top != y_bot) {
            delta = (seg->dir ? 16711680.0 : -16711680.0) *
              (y_bot - y_top);
            x_top = seg_x[seg_index] + (y_top - y) * seg_dx[seg_index];
            x_bot = seg_x[seg_index] + (y_bot - y) * seg_dx[seg_index];
            if (x_top < x_bot)
              {
                x_min = x_top;
                x_max = x_bot;
              }
            else
              {
                x_min = x_bot;
                x_max = x_top;
              }
            ix_min = floor (x_min);
            ix_max = floor (x_max);
            if (ix_min >= x1)
              {
                /* skip; it starts to the right of the render region */
              }
            else if (ix_max < x0)
              /* it ends to the left of the render region */
              start += delta;
            else if (ix_min == ix_max)
              {
                /* case 1, antialias a single pixel */
                xdelta = (ix_min + 1 - (x_min + x_max) * 0.5) * delta;

                ADD_STEP(ix_min, xdelta)

                if (ix_min + 1 < x1)
                  {
                    xdelta = delta - xdelta;

                    ADD_STEP(ix_min + 1, xdelta)
                  }
              }
            else
              {
                /* case 2, antialias a run */
                rslope = 1.0 / fabs (seg_dx[seg_index]);
                drslope = delta * rslope;
                last =
                  drslope * 0.5 *
                  (ix_min + 1 - x_min) * (ix_min + 1 - x_min);
                xdelta = last;
                if (ix_min >= x0)
                  {
                    ADD_STEP(ix_min, xdelta)
                    
                    x = ix_min + 1;
                  }
                else
                  {
                    start += last;
                    x = x0;
                  }
                if (ix_max > x1)
                  ix_max = x1;
                for (; x < ix_max; x++)
                  {
                    this = (seg->dir ? 16711680.0 : -16711680.0) * rslope *
                      (x + 0.5 - x_min);
                    xdelta = this - last;
                    last = this;

                    ADD_STEP(x, xdelta)
                  }
                if (x < x1)
                  {
                    this =
                      delta * (1 - 0.5 *
                               (x_max - ix_max) * (x_max - ix_max) *
                               rslope);
                    xdelta = this - last;
                    last = this;

                    ADD_STEP(x, xdelta)
                    
                    if (x + 1 < x1)
                      {
                        xdelta = delta - last;

                        ADD_STEP(x + 1, xdelta)
                      }
                  }
              }
          }
          curs++;
          if (curs != seg->n_points - 1 &&
              seg->points[curs].y < y + 1)
            {
              dy = seg->points[curs + 1].y - seg->points[curs].y;
              if (fabs (dy) >= EPSILON)
                seg_dx[seg_index] = (seg->points[curs + 1].x -
                                     seg->points[curs].x) / dy;
              else
                seg_dx[seg_index] = 1e12;
              seg_x[seg_index] = seg->points[curs].x +
                (y - seg->points[curs].y) * seg_dx[seg_index];
            }
          /* break here, instead of duplicating predicate in while? */
        }
      if (seg->points[curs].y >= y + 1)
        {
          curs--;
          cursor[seg_index] = curs;
          seg_x[seg_index] += seg_dx[seg_index];
        }
      else
        {
          art_svp_render_delete_active (active_segs, j--,
                                        --n_active_segs);
        }
    }

  *p_start = start;
  *p_steps = steps;
  *p_n_steps = n_steps;

  iter->seg_ix = i;
  iter->n_active_segs = n_active_segs;
  iter->y++;
}

void
art_svp_render_aa_iter_done (ArtSVPRenderAAIter *iter)
{
  art_free (iter->steps);

  art_free (iter->seg_dx);
  art_free (iter->seg_x);
  art_free (iter->cursor);
  art_free (iter->active_segs);
  art_free (iter);
}

/**
 * art_svp_render_aa: Render SVP antialiased.
 * @svp: The #ArtSVP to render.
 * @x0: Left coordinate of destination rectangle.
 * @y0: Top coordinate of destination rectangle.
 * @x1: Right coordinate of destination rectangle.
 * @y1: Bottom coordinate of destination rectangle.
 * @callback: The callback which actually paints the pixels.
 * @callback_data: Private data for @callback.
 *
 * Renders the sorted vector path in the given rectangle, antialiased.
 *
 * This interface uses a callback for the actual pixel rendering. The
 * callback is called @y1 - @y0 times (once for each scan line). The y
 * coordinate is given as an argument for convenience (it could be
 * stored in the callback's private data and incremented on each
 * call).
 *
 * The rendered polygon is represented in a semi-runlength format: a
 * start value and a sequence of "steps". Each step has an x
 * coordinate and a value delta. The resulting value at position x is
 * equal to the sum of the start value and all step delta values for
 * which the step x coordinate is less than or equal to x. An
 * efficient algorithm will traverse the steps left to right, keeping
 * a running sum.
 *
 * All x coordinates in the steps are guaranteed to be @x0 <= x < @x1.
 * (This guarantee is a change from the gfonted vpaar renderer from
 * which this routine is derived, and is designed to simplify the
 * callback).
 *
 * The value 0x8000 represents 0% coverage by the polygon, while
 * 0xff8000 represents 100% coverage. This format is designed so that
 * >> 16 results in a standard 0x00..0xff value range, with nice
 * rounding.
 * 
 **/
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)
{
  ArtSVPRenderAAIter *iter;
  int y;
  int start;
  ArtSVPRenderAAStep *steps;
  int n_steps;

  iter = art_svp_render_aa_iter (svp, x0, y0, x1, y1);


  for (y = y0; y < y1; y++)
    {
      art_svp_render_aa_iter_step (iter, &start, &steps, &n_steps);
      (*callback) (callback_data, y, start, steps, n_steps);
    }

  art_svp_render_aa_iter_done (iter);
}