gvsig-raster / libjni-potrace / trunk / libjni-potrace / resources / potrace-1.8 / src / render.c @ 1780
History | View | Annotate | Download (6.88 KB)
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. */
|
4 |
|
5 |
/* $Id: render.c 147 2007-04-09 00:44:09Z selinger $ */
|
6 |
|
7 |
#include <stdio.h> |
8 |
#include <stdlib.h> |
9 |
#include <math.h> |
10 |
#include <string.h> |
11 |
|
12 |
#include "render.h" |
13 |
#include "greymap.h" |
14 |
#include "auxiliary.h" |
15 |
|
16 |
/* ---------------------------------------------------------------------- */
|
17 |
/* routines for anti-aliased rendering of curves */
|
18 |
|
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. */
|
45 |
|
46 |
/* allocate a new rendering state */
|
47 |
render_t *render_new(greymap_t *gm) { |
48 |
render_t *rm; |
49 |
|
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 |
} |
64 |
|
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 |
} |
71 |
|
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);
|
78 |
|
79 |
/* assert (rm->x0i != rm->x1i || rm->y0i != rm->y1i); */
|
80 |
|
81 |
/* the persistent state is now undefined */
|
82 |
} |
83 |
|
84 |
/* move point */
|
85 |
void render_moveto(render_t *rm, double x, double y) { |
86 |
/* close the previous path */
|
87 |
render_close(rm); |
88 |
|
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 |
} |
97 |
|
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;
|
102 |
|
103 |
if (y < 0 || y >= rm->gm->h) { |
104 |
return;
|
105 |
} |
106 |
|
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 |
} |
128 |
|
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;
|
139 |
|
140 |
x2i = (int)floor(x2);
|
141 |
y2i = (int)floor(y2);
|
142 |
|
143 |
sn = abs(x2i - rm->x1i); |
144 |
tn = abs(y2i - rm->y1i); |
145 |
|
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 |
} |
154 |
|
155 |
r0 = 0;
|
156 |
|
157 |
i = 0;
|
158 |
j = 0;
|
159 |
|
160 |
rxi = rm->x1i; |
161 |
ryi = rm->y1i; |
162 |
|
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) */
|
174 |
|
175 |
/* move point to r1 */
|
176 |
rm->a1 += (r1-r0)*(y2-rm->y1)*(rxi+1-((r0+r1)/2.0*(x2-rm->x1)+rm->x1)); |
177 |
|
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 |
} |
200 |
|
201 |
r0 = r1; |
202 |
} |
203 |
|
204 |
/* move point to (x2,y2) */
|
205 |
|
206 |
r1 = 1;
|
207 |
rm->a1 += (r1-r0)*(y2-rm->y1)*(rxi+1-((r0+r1)/2.0*(x2-rm->x1)+rm->x1)); |
208 |
|
209 |
rm->x1i = x2i; |
210 |
rm->y1i = y2i; |
211 |
rm->x1 = x2; |
212 |
rm->y1 = y2; |
213 |
|
214 |
/* assert (rxi != rm->x1i || ryi != rm->y1i); */
|
215 |
} |
216 |
|
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;
|
220 |
|
221 |
x1 = rm->x1; /* starting point */
|
222 |
y1 = rm->y1; |
223 |
|
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. */
|
228 |
|
229 |
delta = .1; /* desired accuracy, in pixels */ |
230 |
|
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 */
|
238 |
|
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 |
} |