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. */
5 /* $Id$ */
7 #include <stdio.h>
8 #include <stdlib.h>
9 #include <math.h>
10 #include <string.h>
12 #include "render.h"
13 #include "greymap.h"
14 #include "auxiliary.h"
16 /* ---------------------------------------------------------------------- */
17 /* routines for anti-aliased rendering of curves */
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. */
46 /* allocate a new rendering state */
47 render_t *render_new(greymap_t *gm) {
48 render_t *rm;
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 }
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 }
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);
79 /* assert (rm->x0i != rm->x1i || rm->y0i != rm->y1i); */
81 /* the persistent state is now undefined */
82 }
84 /* move point */
85 void render_moveto(render_t *rm, double x, double y) {
86 /* close the previous path */
87 render_close(rm);
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 }
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;
103 if (y < 0 || y >= rm->gm->h) {
104 return;
105 }
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 }
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;
140 x2i = (int)floor(x2);
141 y2i = (int)floor(y2);
143 sn = abs(x2i - rm->x1i);
144 tn = abs(y2i - rm->y1i);
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 }
155 r0 = 0;
157 i = 0;
158 j = 0;
160 rxi = rm->x1i;
161 ryi = rm->y1i;
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) */
175 /* move point to r1 */
176 rm->a1 += (r1-r0)*(y2-rm->y1)*(rxi+1-((r0+r1)/2.0*(x2-rm->x1)+rm->x1));
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 }
201 r0 = r1;
202 }
204 /* move point to (x2,y2) */
206 r1 = 1;
207 rm->a1 += (r1-r0)*(y2-rm->y1)*(rxi+1-((r0+r1)/2.0*(x2-rm->x1)+rm->x1));
209 rm->x1i = x2i;
210 rm->y1i = y2i;
211 rm->x1 = x2;
212 rm->y1 = y2;
214 /* assert (rxi != rm->x1i || ryi != rm->y1i); */
215 }
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;
221 x1 = rm->x1; /* starting point */
222 y1 = rm->y1;
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. */
229 delta = .1; /* desired accuracy, in pixels */
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 */
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 }