+++ /dev/null
-/* 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 <math.h>
-#include <string.h> /* for memmove */
-#include "art_misc.h"
-
-#include "art_rect.h"
-#include "art_svp.h"
-
-#include "art_svp_render_aa.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);
-}
projects / rrdtool.git / blobdiff