src/trace/potrace/render.cpp

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