X-Git-Url: https://git.octo.it/?p=rrdtool.git;a=blobdiff_plain;f=libraries%2Flibart_lgpl-2.3.7%2Fart_svp_render_aa.c;fp=libraries%2Flibart_lgpl-2.3.7%2Fart_svp_render_aa.c;h=0000000000000000000000000000000000000000;hp=35092c6389c3245f40e60d038256afd7cf13a99a;hb=5d405fd05bbfbbd94a7c6cbd876e6634025c1c25;hpb=bab0189ee9d56aca8bea909275317ab4e0be09ee diff --git a/libraries/libart_lgpl-2.3.7/art_svp_render_aa.c b/libraries/libart_lgpl-2.3.7/art_svp_render_aa.c deleted file mode 100644 index 35092c6..0000000 --- a/libraries/libart_lgpl-2.3.7/art_svp_render_aa.c +++ /dev/null @@ -1,461 +0,0 @@ -/* 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 -#include /* 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); -}