diff options
author | Peter Breitenlohner <peb@mppmu.mpg.de> | 2015-03-27 09:12:50 +0000 |
---|---|---|
committer | Peter Breitenlohner <peb@mppmu.mpg.de> | 2015-03-27 09:12:50 +0000 |
commit | e2182e9f9514a90e1a9deae69b6a37d8cc7dc10e (patch) | |
tree | 88dfb7229fbce506d440e5c9577ce283f670abd7 /Build/source/libs/potrace/potrace-1.12/src/render.c | |
parent | 5a249a9f3e29f0a636c640abbf4526f72813fefc (diff) |
potrace 1.12
git-svn-id: svn://tug.org/texlive/trunk@36643 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/libs/potrace/potrace-1.12/src/render.c')
-rw-r--r-- | Build/source/libs/potrace/potrace-1.12/src/render.c | 243 |
1 files changed, 243 insertions, 0 deletions
diff --git a/Build/source/libs/potrace/potrace-1.12/src/render.c b/Build/source/libs/potrace/potrace-1.12/src/render.c new file mode 100644 index 00000000000..4f44ae6a64d --- /dev/null +++ b/Build/source/libs/potrace/potrace-1.12/src/render.c @@ -0,0 +1,243 @@ +/* Copyright (C) 2001-2015 Peter Selinger. + This file is part of Potrace. It is free software and it is covered + by the GNU General Public License. See the file COPYING for details. */ + + +#include <stdio.h> +#include <stdlib.h> +#include <math.h> +#include <string.h> + +#include "render.h" +#include "greymap.h" +#include "auxiliary.h" + +/* ---------------------------------------------------------------------- */ +/* routines for anti-aliased rendering of curves */ + +/* we use the following method. Given a point (x,y) (with real-valued + coordinates) in the plane, let (xi,yi) be the integer part of the + coordinates, i.e., xi=floor(x), yi=floor(y). Define a path from + (x,y) to infinity as follows: path(x,y) = + (x,y)--(xi+1,y)--(xi+1,yi)--(+infty,yi). Now as the point (x,y) + moves smoothly across the plane, the path path(x,y) sweeps + (non-smoothly) across a certain area. We proportionately blacken + the area as the path moves "downward", and we whiten the area as + the path moves "upward". This way, after the point has traversed a + closed curve, the interior of the curve has been darkened + (counterclockwise movement) or lightened (clockwise movement). (The + "grey shift" is actually proportional to the winding number). By + choosing the above path with mostly integer coordinates, we achieve + that only pixels close to (x,y) receive grey values and are subject + to round-off errors. The grey value of pixels far away from (x,y) + is always in "integer" (where 0=black, 1=white). As a special + trick, we keep an accumulator rm->a1, which holds a double value to + be added to the grey value to be added to the current pixel + (xi,yi). Only when changing "current" pixels, we convert this + double value to an integer. This way we avoid round-off errors at + the meeting points of line segments. Another speedup measure is + that we sometimes use the rm->incrow_buf array to postpone + incrementing or decrementing an entire row. If incrow_buf[y]=x+1!=0, + then all the pixels (x,y),(x+1,y),(x+2,y),... are scheduled to be + incremented/decremented (which one is the case will be clear from + context). This keeps the greymap operations reasonably local. */ + +/* allocate a new rendering state */ +render_t *render_new(greymap_t *gm) { + render_t *rm; + + rm = (render_t *) malloc(sizeof(render_t)); + if (!rm) { + return NULL; + } + memset(rm, 0, sizeof(render_t)); + rm->gm = gm; + rm->incrow_buf = (int *) calloc(gm->h, sizeof(int)); + if (!rm->incrow_buf) { + free(rm); + return NULL; + } + memset(rm->incrow_buf, 0, gm->h * sizeof(int)); + return rm; +} + +/* free a given rendering state. Note: this does not free the + underlying greymap. */ +void render_free(render_t *rm) { + free(rm->incrow_buf); + free(rm); +} + +/* close path */ +void render_close(render_t *rm) { + if (rm->x0 != rm->x1 || rm->y0 != rm->y1) { + render_lineto(rm, rm->x0, rm->y0); + } + GM_INC(rm->gm, rm->x0i, rm->y0i, (rm->a0+rm->a1)*255); + + /* assert (rm->x0i != rm->x1i || rm->y0i != rm->y1i); */ + + /* the persistent state is now undefined */ +} + +/* move point */ +void render_moveto(render_t *rm, double x, double y) { + /* close the previous path */ + render_close(rm); + + rm->x0 = rm->x1 = x; + rm->y0 = rm->y1 = y; + rm->x0i = (int)floor(rm->x0); + rm->x1i = (int)floor(rm->x1); + rm->y0i = (int)floor(rm->y0); + rm->y1i = (int)floor(rm->y1); + rm->a0 = rm->a1 = 0; +} + +/* add b to pixels (x,y) and all pixels to the right of it. However, + use rm->incrow_buf as a buffer to economize on multiple calls */ +static void incrow(render_t *rm, int x, int y, int b) { + int i, x0; + + if (y < 0 || y >= rm->gm->h) { + return; + } + + if (x < 0) { + x = 0; + } else if (x > rm->gm->w) { + x = rm->gm->w; + } + if (rm->incrow_buf[y] == 0) { + rm->incrow_buf[y] = x+1; /* store x+1 so that we can use 0 for "vacant" */ + return; + } + x0 = rm->incrow_buf[y]-1; + rm->incrow_buf[y] = 0; + if (x0 < x) { + for (i=x0; i<x; i++) { + GM_INC(rm->gm, i, y, -b); + } + } else { + for (i=x; i<x0; i++) { + GM_INC(rm->gm, i, y, b); + } + } +} + +/* render a straight line */ +void render_lineto(render_t *rm, double x2, double y2) { + int x2i, y2i; + double t0=2, s0=2; + int sn, tn; + double ss=2, ts=2; + double r0, r1; + int i, j; + int rxi, ryi; + int s; + + x2i = (int)floor(x2); + y2i = (int)floor(y2); + + sn = abs(x2i - rm->x1i); + tn = abs(y2i - rm->y1i); + + if (sn) { + s0 = ((x2>rm->x1 ? rm->x1i+1 : rm->x1i) - rm->x1)/(x2-rm->x1); + ss = fabs(1.0/(x2-rm->x1)); + } + if (tn) { + t0 = ((y2>rm->y1 ? rm->y1i+1 : rm->y1i) - rm->y1)/(y2-rm->y1); + ts = fabs(1.0/(y2-rm->y1)); + } + + r0 = 0; + + i = 0; + j = 0; + + rxi = rm->x1i; + ryi = rm->y1i; + + while (i<sn || j<tn) { + if (j>=tn || (i<sn && s0+i*ss < t0+j*ts)) { + r1 = s0+i*ss; + i++; + s = 1; + } else { + r1 = t0+j*ts; + j++; + s = 0; + } + /* render line from r0 to r1 segment of (rm->x1,rm->y1)..(x2,y2) */ + + /* move point to r1 */ + rm->a1 += (r1-r0)*(y2-rm->y1)*(rxi+1-((r0+r1)/2.0*(x2-rm->x1)+rm->x1)); + + /* move point across pixel boundary */ + if (s && x2>rm->x1) { + GM_INC(rm->gm, rxi, ryi, rm->a1*255); + rm->a1 = 0; + rxi++; + rm->a1 += rm->y1+r1*(y2-rm->y1)-ryi; + } else if (!s && y2>rm->y1) { + GM_INC(rm->gm, rxi, ryi, rm->a1*255); + rm->a1 = 0; + incrow(rm, rxi+1, ryi, 255); + ryi++; + } else if (s && x2<=rm->x1) { + rm->a1 -= rm->y1+r1*(y2-rm->y1)-ryi; + GM_INC(rm->gm, rxi, ryi, rm->a1*255); + rm->a1 = 0; + rxi--; + } else if (!s && y2<=rm->y1) { + GM_INC(rm->gm, rxi, ryi, rm->a1*255); + rm->a1 = 0; + ryi--; + incrow(rm, rxi+1, ryi, -255); + } + + r0 = r1; + } + + /* move point to (x2,y2) */ + + r1 = 1; + rm->a1 += (r1-r0)*(y2-rm->y1)*(rxi+1-((r0+r1)/2.0*(x2-rm->x1)+rm->x1)); + + rm->x1i = x2i; + rm->y1i = y2i; + rm->x1 = x2; + rm->y1 = y2; + + /* assert (rxi != rm->x1i || ryi != rm->y1i); */ +} + +/* render a Bezier curve. */ +void render_curveto(render_t *rm, double x2, double y2, double x3, double y3, double x4, double y4) { + double x1, y1, dd0, dd1, dd, delta, e2, epsilon, t; + + x1 = rm->x1; /* starting point */ + y1 = rm->y1; + + /* we approximate the curve by small line segments. The interval + size, epsilon, is determined on the fly so that the distance + between the true curve and its approximation does not exceed the + desired accuracy delta. */ + + delta = .1; /* desired accuracy, in pixels */ + + /* let dd = maximal value of 2nd derivative over curve - this must + occur at an endpoint. */ + dd0 = sq(x1-2*x2+x3) + sq(y1-2*y2+y3); + dd1 = sq(x2-2*x3+x4) + sq(y2-2*y3+y4); + dd = 6*sqrt(max(dd0, dd1)); + e2 = 8*delta <= dd ? 8*delta/dd : 1; + epsilon = sqrt(e2); /* necessary interval size */ + + for (t=epsilon; t<1; t+=epsilon) { + render_lineto(rm, x1*cu(1-t)+3*x2*sq(1-t)*t+3*x3*(1-t)*sq(t)+x4*cu(t), + y1*cu(1-t)+3*y2*sq(1-t)*t+3*y3*(1-t)*sq(t)+y4*cu(t)); + } + render_lineto(rm, x4, y4); +} |