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. */
5 /* $Id$ */
7 #include <stdlib.h>
8 #include <math.h>
9 #include <string.h>
11 #include "render.h"
12 #include "auxiliary.h"
14 /* ---------------------------------------------------------------------- */
15 /* routines for anti-aliased rendering of curves */
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. */
44 /* allocate a new rendering state */
45 render_t *render_new(greymap_t *gm) {
46 render_t *rm;
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 }
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 }
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);
77 /* assert (rm->x0i != rm->x1i || rm->y0i != rm->y1i); */
79 /* the persistent state is now undefined */
80 }
82 /* move point */
83 void render_moveto(render_t *rm, double x, double y) {
84 /* close the previous path */
85 render_close(rm);
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 }
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;
101 if (y < 0 || y >= rm->gm->h) {
102 return;
103 }
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 }
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;
138 x2i = (int)floor(x2);
139 y2i = (int)floor(y2);
141 sn = abs(x2i - rm->x1i);
142 tn = abs(y2i - rm->y1i);
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 }
153 r0 = 0;
155 i = 0;
156 j = 0;
158 rxi = rm->x1i;
159 ryi = rm->y1i;
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) */
173 /* move point to r1 */
174 rm->a1 += (r1-r0)*(y2-rm->y1)*(rxi+1-((r0+r1)/2.0*(x2-rm->x1)+rm->x1));
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 }
199 r0 = r1;
200 }
202 /* move point to (x2,y2) */
204 r1 = 1;
205 rm->a1 += (r1-r0)*(y2-rm->y1)*(rxi+1-((r0+r1)/2.0*(x2-rm->x1)+rm->x1));
207 rm->x1i = x2i;
208 rm->y1i = y2i;
209 rm->x1 = x2;
210 rm->y1 = y2;
212 /* assert (rxi != rm->x1i || ryi != rm->y1i); */
213 }
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;
219 x1 = rm->x1; /* starting point */
220 y1 = rm->y1;
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. */
227 delta = .1; /* desired accuracy, in pixels */
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 */
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 }