/* 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 gdouble artfloat;
struct _ArtSVPRenderAAIter {
const ArtSVP *svp;
gint x0, x1;
gint y;
gint seg_ix;
gint *active_segs;
gint n_active_segs;
gint *cursor;
artfloat *seg_x;
artfloat *seg_dx;
ArtSVPRenderAAStep *steps;
};
static void
art_svp_render_insert_active (gint i, gint *active_segs, gint n_active_segs,
artfloat *seg_x, artfloat *seg_dx)
{
gint j;
artfloat x;
gint 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 (gint *active_segs, gint j, gint n_active_segs)
{
gint 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,
gint x0, gint y0, gint x1, gint 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, gint *p_start,
ArtSVPRenderAAStep **p_steps, gint *p_n_steps)
{
const ArtSVP *svp = iter->svp;
gint *active_segs = iter->active_segs;
gint n_active_segs = iter->n_active_segs;
gint *cursor = iter->cursor;
artfloat *seg_x = iter->seg_x;
artfloat *seg_dx = iter->seg_dx;
gint i = iter->seg_ix;
gint j;
gint x0 = iter->x0;
gint x1 = iter->x1;
gint y = iter->y;
gint seg_index;
gint x;
ArtSVPRenderAAStep *steps = iter->steps;
gint n_steps;
artfloat y_top, y_bot;
artfloat x_top, x_bot;
artfloat x_min, x_max;
gint ix_min, ix_max;
artfloat delta; /* delta should be gint too? */
gint last, this;
gint xdelta;
artfloat rslope, drslope;
gint start;
const ArtSVPSeg *seg;
gint curs;
artfloat dy;
gint 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,
gint x0, gint y0, gint x1, gint y1,
void (*callback) (gpointer callback_data,
gint y,
gint start,
ArtSVPRenderAAStep *steps, gint n_steps),
gpointer callback_data)
{
ArtSVPRenderAAIter *iter;
gint y;
gint start;
ArtSVPRenderAAStep *steps;
gint 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);
}
