summaryrefslogtreecommitdiff
path: root/Build/source/libs/potrace/potrace-1.11/src/render.c
blob: 3e8a62590616f36b3c2e2cd7c6fafb67c10757ca (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
/* Copyright (C) 2001-2013 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 *) malloc(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);
}