gvsig-raster / libjni-potrace / trunk / libjni-potrace / resources / potrace-1.8 / src / render.c @ 1780
History | View | Annotate | Download (6.88 KB)
1 | 1780 | nbrodin | /* 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 | } |