render.c
Go to the documentation of this file.
```00001 /* Copyright (C) 2001-2007 Peter Selinger.
00002    This file is part of Potrace. It is free software and it is covered
00003    by the GNU General Public License. See the file COPYING for details. */
00004
00005 /* \$Id: render.c 147 2007-04-09 00:44:09Z selinger \$ */
00006
00007 #include <stdio.h>
00008 #include <stdlib.h>
00009 #include <math.h>
00010 #include <string.h>
00011
00012 #include "render.h"
00013 #include "greymap.h"
00014 #include "auxiliary.h"
00015
00016 /* ---------------------------------------------------------------------- */
00017 /* routines for anti-aliased rendering of curves */
00018
00019 /* we use the following method. Given a point (x,y) (with real-valued
00020    coordinates) in the plane, let (xi,yi) be the integer part of the
00021    coordinates, i.e., xi=floor(x), yi=floor(y). Define a path from
00022    (x,y) to infinity as follows: path(x,y) =
00023    (x,y)--(xi+1,y)--(xi+1,yi)--(+infty,yi).  Now as the point (x,y)
00024    moves smoothly across the plane, the path path(x,y) sweeps
00025    (non-smoothly) across a certain area. We proportionately blacken
00026    the area as the path moves "downward", and we whiten the area as
00027    the path moves "upward". This way, after the point has traversed a
00028    closed curve, the interior of the curve has been darkened
00029    (counterclockwise movement) or lightened (clockwise movement). (The
00030    "grey shift" is actually proportional to the winding number). By
00031    choosing the above path with mostly integer coordinates, we achieve
00032    that only pixels close to (x,y) receive grey values and are subject
00033    to round-off errors. The grey value of pixels far away from (x,y)
00034    is always in "integer" (where 0=black, 1=white).  As a special
00035    trick, we keep an accumulator rm->a1, which holds a double value to
00036    be added to the grey value to be added to the current pixel
00037    (xi,yi).  Only when changing "current" pixels, we convert this
00038    double value to an integer. This way we avoid round-off errors at
00039    the meeting points of line segments. Another speedup measure is
00040    that we sometimes use the rm->incrow_buf array to postpone
00041    incrementing or decrementing an entire row. If incrow_buf[y]=x+1!=0,
00042    then all the pixels (x,y),(x+1,y),(x+2,y),... are scheduled to be
00043    incremented/decremented (which one is the case will be clear from
00044    context). This keeps the greymap operations reasonably local. */
00045
00046 /* allocate a new rendering state */
00047 render_t *render_new(greymap_t *gm) {
00048   render_t *rm;
00049
00050   rm = (render_t *) malloc(sizeof(render_t));
00051   if (!rm) {
00052     return NULL;
00053   }
00054   memset(rm, 0, sizeof(render_t));
00055   rm->gm = gm;
00056   rm->incrow_buf = (int *) malloc(gm->h * sizeof(int));
00057   if (!rm->incrow_buf) {
00058     free(rm);
00059     return NULL;
00060   }
00061   memset(rm->incrow_buf, 0, gm->h * sizeof(int));
00062   return rm;
00063 }
00064
00065 /* free a given rendering state. Note: this does not free the
00066    underlying greymap. */
00067 void render_free(render_t *rm) {
00068   free(rm->incrow_buf);
00069   free(rm);
00070 }
00071
00072 /* close path */
00073 void render_close(render_t *rm) {
00074   if (rm->x0 != rm->x1 || rm->y0 != rm->y1) {
00075     render_lineto(rm, rm->x0, rm->y0);
00076   }
00077   GM_INC(rm->gm, rm->x0i, rm->y0i, (rm->a0+rm->a1)*255);
00078
00079   /* assert (rm->x0i != rm->x1i || rm->y0i != rm->y1i); */
00080
00081   /* the persistent state is now undefined */
00082 }
00083
00084 /* move point */
00085 void render_moveto(render_t *rm, double x, double y) {
00086   /* close the previous path */
00087   render_close(rm);
00088
00089   rm->x0 = rm->x1 = x;
00090   rm->y0 = rm->y1 = y;
00091   rm->x0i = (int)floor(rm->x0);
00092   rm->x1i = (int)floor(rm->x1);
00093   rm->y0i = (int)floor(rm->y0);
00094   rm->y1i = (int)floor(rm->y1);
00095   rm->a0 = rm->a1 = 0;
00096 }
00097
00098 /* add b to pixels (x,y) and all pixels to the right of it. However,
00099    use rm->incrow_buf as a buffer to economize on multiple calls */
00100 static void incrow(render_t *rm, int x, int y, int b) {
00101   int i, x0;
00102
00103   if (y < 0 || y >= rm->gm->h) {
00104     return;
00105   }
00106
00107   if (x < 0) {
00108     x = 0;
00109   } else if (x > rm->gm->w) {
00110     x = rm->gm->w;
00111   }
00112   if (rm->incrow_buf[y] == 0) {
00113     rm->incrow_buf[y] = x+1; /* store x+1 so that we can use 0 for "vacant" */
00114     return;
00115   }
00116   x0 = rm->incrow_buf[y]-1;
00117   rm->incrow_buf[y] = 0;
00118   if (x0 < x) {
00119     for (i=x0; i<x; i++) {
00120       GM_INC(rm->gm, i, y, -b);
00121     }
00122   } else {
00123     for (i=x; i<x0; i++) {
00124       GM_INC(rm->gm, i, y, b);
00125     }
00126   }
00127 }
00128
00129 /* render a straight line */
00130 void render_lineto(render_t *rm, double x2, double y2) {
00131   int x2i, y2i;
00132   double t0=2, s0=2;
00133   int sn, tn;
00134   double ss=2, ts=2;
00135   double r0, r1;
00136   int i, j;
00137   int rxi, ryi;
00138   int s;
00139
00140   x2i = (int)floor(x2);
00141   y2i = (int)floor(y2);
00142
00143   sn = abs(x2i - rm->x1i);
00144   tn = abs(y2i - rm->y1i);
00145
00146   if (sn) {
00147     s0 = ((x2>rm->x1 ? rm->x1i+1 : rm->x1i) - rm->x1)/(x2-rm->x1);
00148     ss = fabs(1.0/(x2-rm->x1));
00149   }
00150   if (tn) {
00151     t0 = ((y2>rm->y1 ? rm->y1i+1 : rm->y1i) - rm->y1)/(y2-rm->y1);
00152     ts = fabs(1.0/(y2-rm->y1));
00153   }
00154
00155   r0 = 0;
00156
00157   i = 0;
00158   j = 0;
00159
00160   rxi = rm->x1i;
00161   ryi = rm->y1i;
00162
00163   while (i<sn || j<tn) {
00164     if (j>=tn || (i<sn && s0+i*ss < t0+j*ts)) {
00165       r1 = s0+i*ss;
00166       i++;
00167       s = 1;
00168     } else {
00169       r1 = t0+j*ts;
00170       j++;
00171       s = 0;
00172     }
00173     /* render line from r0 to r1 segment of (rm->x1,rm->y1)..(x2,y2) */
00174
00175     /* move point to r1 */
00176     rm->a1 += (r1-r0)*(y2-rm->y1)*(rxi+1-((r0+r1)/2.0*(x2-rm->x1)+rm->x1));
00177
00178     /* move point across pixel boundary */
00179     if (s && x2>rm->x1) {
00180       GM_INC(rm->gm, rxi, ryi, rm->a1*255);
00181       rm->a1 = 0;
00182       rxi++;
00183       rm->a1 += rm->y1+r1*(y2-rm->y1)-ryi;
00184     } else if (!s && y2>rm->y1) {
00185       GM_INC(rm->gm, rxi, ryi, rm->a1*255);
00186       rm->a1 = 0;
00187       incrow(rm, rxi+1, ryi, 255);
00188       ryi++;
00189     } else if (s && x2<=rm->x1) {
00190       rm->a1 -= rm->y1+r1*(y2-rm->y1)-ryi;
00191       GM_INC(rm->gm, rxi, ryi, rm->a1*255);
00192       rm->a1 = 0;
00193       rxi--;
00194     } else if (!s && y2<=rm->y1) {
00195       GM_INC(rm->gm, rxi, ryi, rm->a1*255);
00196       rm->a1 = 0;
00197       ryi--;
00198       incrow(rm, rxi+1, ryi, -255);
00199     }
00200
00201     r0 = r1;
00202   }
00203
00204   /* move point to (x2,y2) */
00205
00206   r1 = 1;
00207   rm->a1 += (r1-r0)*(y2-rm->y1)*(rxi+1-((r0+r1)/2.0*(x2-rm->x1)+rm->x1));
00208
00209   rm->x1i = x2i;
00210   rm->y1i = y2i;
00211   rm->x1 = x2;
00212   rm->y1 = y2;
00213
00214   /* assert (rxi != rm->x1i || ryi != rm->y1i); */
00215 }
00216
00217 /* render a Bezier curve. */
00218 void render_curveto(render_t *rm, double x2, double y2, double x3, double y3, double x4, double y4) {
00219   double x1, y1, dd0, dd1, dd, delta, e2, epsilon, t;
00220
00221   x1 = rm->x1;  /* starting point */
00222   y1 = rm->y1;
00223
00224   /* we approximate the curve by small line segments. The interval
00225      size, epsilon, is determined on the fly so that the distance
00226      between the true curve and its approximation does not exceed the
00227      desired accuracy delta. */
00228
00229   delta = .1;  /* desired accuracy, in pixels */
00230
00231   /* let dd = maximal value of 2nd derivative over curve - this must
00232      occur at an endpoint. */
00233   dd0 = sq(x1-2*x2+x3) + sq(y1-2*y2+y3);
00234   dd1 = sq(x2-2*x3+x4) + sq(y2-2*y3+y4);
00235   dd = 6*sqrt(max(dd0, dd1));
00236   e2 = 8*delta <= dd ? 8*delta/dd : 1;
00237   epsilon = sqrt(e2);  /* necessary interval size */
00238
00239   for (t=epsilon; t<1; t+=epsilon) {
00240     render_lineto(rm, x1*cu(1-t)+3*x2*sq(1-t)*t+3*x3*(1-t)*sq(t)+x4*cu(t),
00241                   y1*cu(1-t)+3*y2*sq(1-t)*t+3*y3*(1-t)*sq(t)+y4*cu(t));
00242   }
00243   render_lineto(rm, x4, y4);
00244 }
```

portrait_painter
Author(s): Niklas Meinzer, Ina Baumgarten
autogenerated on Wed Dec 26 2012 16:00:43