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