src/trace/potrace/render.cpp

   1 /* Copyright (C) 2001-2007 Peter Selinger.
   2    This file is part of Potrace. It is free software and it is covered
   3    by the GNU General Public License. See the file COPYING for details. */
   4
   5 /* $Id$ */
   6
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <math.h>
  10 #include <string.h>
  11
  12 #include "render.h"
  13 #include "greymap.h"
  14 #include "auxiliary.h"
  15
  16 /* ---------------------------------------------------------------------- */
  17 /* routines for anti-aliased rendering of curves */
  18
  19 /* we use the following method. Given a point (x,y) (with real-valued
  20    coordinates) in the plane, let (xi,yi) be the integer part of the
  21    coordinates, i.e., xi=floor(x), yi=floor(y). Define a path from
  22    (x,y) to infinity as follows: path(x,y) =
  23    (x,y)--(xi+1,y)--(xi+1,yi)--(+infty,yi).  Now as the point (x,y)
  24    moves smoothly across the plane, the path path(x,y) sweeps
  25    (non-smoothly) across a certain area. We proportionately blacken
  26    the area as the path moves "downward", and we whiten the area as
  27    the path moves "upward". This way, after the point has traversed a
  28    closed curve, the interior of the curve has been darkened
  29    (counterclockwise movement) or lightened (clockwise movement). (The
  30    "grey shift" is actually proportional to the winding number). By
  31    choosing the above path with mostly integer coordinates, we achieve
  32    that only pixels close to (x,y) receive grey values and are subject
  33    to round-off errors. The grey value of pixels far away from (x,y)
  34    is always in "integer" (where 0=black, 1=white).  As a special
  35    trick, we keep an accumulator rm->a1, which holds a double value to
  36    be added to the grey value to be added to the current pixel
  37    (xi,yi).  Only when changing "current" pixels, we convert this
  38    double value to an integer. This way we avoid round-off errors at
  39    the meeting points of line segments. Another speedup measure is
  40    that we sometimes use the rm->incrow_buf array to postpone
  41    incrementing or decrementing an entire row. If incrow_buf[y]=x+1!=0,
  42    then all the pixels (x,y),(x+1,y),(x+2,y),... are scheduled to be
  43    incremented/decremented (which one is the case will be clear from
  44    context). This keeps the greymap operations reasonably local. */
  45
  46 /* allocate a new rendering state */
  47 render_t *render_new(greymap_t *gm) {
  48   render_t *rm;
  49
  50   rm = (render_t *) malloc(sizeof(render_t));
  51   if (!rm) {
  52     return NULL;
  53   }
  54   memset(rm, 0, sizeof(render_t));
  55   rm->gm = gm;
  56   rm->incrow_buf = (int *) malloc(gm->h * sizeof(int));
  57   if (!rm->incrow_buf) {
  58     free(rm);
  59     return NULL;
  60   }
  61   memset(rm->incrow_buf, 0, gm->h * sizeof(int));
  62   return rm;
  63 }
  64
  65 /* free a given rendering state. Note: this does not free the
  66    underlying greymap. */
  67 void render_free(render_t *rm) {
  68   free(rm->incrow_buf);
  69   free(rm);
  70 }
  71
  72 /* close path */
  73 void render_close(render_t *rm) {
  74   if (rm->x0 != rm->x1 || rm->y0 != rm->y1) {
  75     render_lineto(rm, rm->x0, rm->y0);
  76   }
  77   GM_INC(rm->gm, rm->x0i, rm->y0i, (rm->a0+rm->a1)*255);
  78
  79   /* assert (rm->x0i != rm->x1i || rm->y0i != rm->y1i); */
  80
  81   /* the persistent state is now undefined */
  82 }
  83
  84 /* move point */
  85 void render_moveto(render_t *rm, double x, double y) {
  86   /* close the previous path */
  87   render_close(rm);
  88
  89   rm->x0 = rm->x1 = x;
  90   rm->y0 = rm->y1 = y;
  91   rm->x0i = (int)floor(rm->x0);
  92   rm->x1i = (int)floor(rm->x1);
  93   rm->y0i = (int)floor(rm->y0);
  94   rm->y1i = (int)floor(rm->y1);
  95   rm->a0 = rm->a1 = 0;
  96 }
  97
  98 /* add b to pixels (x,y) and all pixels to the right of it. However,
  99    use rm->incrow_buf as a buffer to economize on multiple calls */
 100 static void incrow(render_t *rm, int x, int y, int b) {
 101   int i, x0;
 102
 103   if (y < 0 || y >= rm->gm->h) {
 104     return;
 105   }
 106
 107   if (x < 0) {
 108     x = 0;
 109   } else if (x > rm->gm->w) {
 110     x = rm->gm->w;
 111   }
 112   if (rm->incrow_buf[y] == 0) {
 113     rm->incrow_buf[y] = x+1; /* store x+1 so that we can use 0 for "vacant" */
 114     return;
 115   }
 116   x0 = rm->incrow_buf[y]-1;
 117   rm->incrow_buf[y] = 0;
 118   if (x0 < x) {
 119     for (i=x0; i<x; i++) {
 120       GM_INC(rm->gm, i, y, -b);
 121     }
 122   } else {
 123     for (i=x; i<x0; i++) {
 124       GM_INC(rm->gm, i, y, b);
 125     }
 126   }
 127 }
 128
 129 /* render a straight line */
 130 void render_lineto(render_t *rm, double x2, double y2) {
 131   int x2i, y2i;
 132   double t0=2, s0=2;
 133   int sn, tn;
 134   double ss=2, ts=2;
 135   double r0, r1;
 136   int i, j;
 137   int rxi, ryi;
 138   int s;
 139
 140   x2i = (int)floor(x2);
 141   y2i = (int)floor(y2);
 142
 143   sn = abs(x2i - rm->x1i);
 144   tn = abs(y2i - rm->y1i);
 145
 146   if (sn) {
 147     s0 = ((x2>rm->x1 ? rm->x1i+1 : rm->x1i) - rm->x1)/(x2-rm->x1);
 148     ss = fabs(1.0/(x2-rm->x1));
 149   }
 150   if (tn) {
 151     t0 = ((y2>rm->y1 ? rm->y1i+1 : rm->y1i) - rm->y1)/(y2-rm->y1);
 152     ts = fabs(1.0/(y2-rm->y1));
 153   }
 154
 155   r0 = 0;
 156
 157   i = 0;
 158   j = 0;
 159
 160   rxi = rm->x1i;
 161   ryi = rm->y1i;
 162
 163   while (i<sn || j<tn) {
 164     if (j>=tn || (i<sn && s0+i*ss < t0+j*ts)) {
 165       r1 = s0+i*ss;
 166       i++;
 167       s = 1;
 168     } else {
 169       r1 = t0+j*ts;
 170       j++;
 171       s = 0;
 172     }
 173     /* render line from r0 to r1 segment of (rm->x1,rm->y1)..(x2,y2) */
 174
 175     /* move point to r1 */
 176     rm->a1 += (r1-r0)*(y2-rm->y1)*(rxi+1-((r0+r1)/2.0*(x2-rm->x1)+rm->x1));
 177
 178     /* move point across pixel boundary */
 179     if (s && x2>rm->x1) {
 180       GM_INC(rm->gm, rxi, ryi, rm->a1*255);
 181       rm->a1 = 0;
 182       rxi++;
 183       rm->a1 += rm->y1+r1*(y2-rm->y1)-ryi;
 184     } else if (!s && y2>rm->y1) {
 185       GM_INC(rm->gm, rxi, ryi, rm->a1*255);
 186       rm->a1 = 0;
 187       incrow(rm, rxi+1, ryi, 255);
 188       ryi++;
 189     } else if (s && x2<=rm->x1) {
 190       rm->a1 -= rm->y1+r1*(y2-rm->y1)-ryi;
 191       GM_INC(rm->gm, rxi, ryi, rm->a1*255);
 192       rm->a1 = 0;
 193       rxi--;
 194     } else if (!s && y2<=rm->y1) {
 195       GM_INC(rm->gm, rxi, ryi, rm->a1*255);
 196       rm->a1 = 0;
 197       ryi--;
 198       incrow(rm, rxi+1, ryi, -255);
 199     }
 200
 201     r0 = r1;
 202   }
 203
 204   /* move point to (x2,y2) */
 205
 206   r1 = 1;
 207   rm->a1 += (r1-r0)*(y2-rm->y1)*(rxi+1-((r0+r1)/2.0*(x2-rm->x1)+rm->x1));
 208
 209   rm->x1i = x2i;
 210   rm->y1i = y2i;
 211   rm->x1 = x2;
 212   rm->y1 = y2;
 213
 214   /* assert (rxi != rm->x1i || ryi != rm->y1i); */
 215 }
 216
 217 /* render a Bezier curve. */
 218 void render_curveto(render_t *rm, double x2, double y2, double x3, double y3, double x4, double y4) {
 219   double x1, y1, dd0, dd1, dd, delta, e2, epsilon, t;
 220
 221   x1 = rm->x1;  /* starting point */
 222   y1 = rm->y1;
 223
 224   /* we approximate the curve by small line segments. The interval
 225      size, epsilon, is determined on the fly so that the distance
 226      between the true curve and its approximation does not exceed the
 227      desired accuracy delta. */
 228
 229   delta = .1;  /* desired accuracy, in pixels */
 230
 231   /* let dd = maximal value of 2nd derivative over curve - this must
 232      occur at an endpoint. */
 233   dd0 = sq(x1-2*x2+x3) + sq(y1-2*y2+y3);
 234   dd1 = sq(x2-2*x3+x4) + sq(y2-2*y3+y4);
 235   dd = 6*sqrt(max(dd0, dd1));
 236   e2 = 8*delta <= dd ? 8*delta/dd : 1;
 237   epsilon = sqrt(e2);  /* necessary interval size */
 238
 239   for (t=epsilon; t<1; t+=epsilon) {
 240     render_lineto(rm, x1*cu(1-t)+3*x2*sq(1-t)*t+3*x3*(1-t)*sq(t)+x4*cu(t),
 241                   y1*cu(1-t)+3*y2*sq(1-t)*t+3*y3*(1-t)*sq(t)+y4*cu(t));
 242   }
 243   render_lineto(rm, x4, y4);
 244 }