#
source:
trunk/third/libart_lgpl/art_vpath_bpath.c
@
18256

Revision 18256, 9.1 KB checked in by ghudson, 22 years ago (diff) |
---|

Line | |
---|---|

1 | /* Libart_LGPL - library of basic graphic primitives |

2 | * Copyright (C) 1998 Raph Levien |

3 | * |

4 | * This library is free software; you can redistribute it and/or |

5 | * modify it under the terms of the GNU Library General Public |

6 | * License as published by the Free Software Foundation; either |

7 | * version 2 of the License, or (at your option) any later version. |

8 | * |

9 | * This library is distributed in the hope that it will be useful, |

10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |

11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |

12 | * Library General Public License for more details. |

13 | * |

14 | * You should have received a copy of the GNU Library General Public |

15 | * License along with this library; if not, write to the |

16 | * Free Software Foundation, Inc., 59 Temple Place - Suite 330, |

17 | * Boston, MA 02111-1307, USA. |

18 | */ |

19 | |

20 | /* Basic constructors and operations for bezier paths */ |

21 | |

22 | #include "config.h" |

23 | #include "art_vpath_bpath.h" |

24 | |

25 | #include <math.h> |

26 | |

27 | #include "art_misc.h" |

28 | |

29 | #include "art_bpath.h" |

30 | #include "art_vpath.h" |

31 | |

32 | /* p must be allocated 2^level points. */ |

33 | |

34 | /* level must be >= 1 */ |

35 | ArtPoint * |

36 | art_bezier_to_vec (double x0, double y0, |

37 | double x1, double y1, |

38 | double x2, double y2, |

39 | double x3, double y3, |

40 | ArtPoint *p, |

41 | int level) |

42 | { |

43 | double x_m, y_m; |

44 | |

45 | #ifdef VERBOSE |

46 | printf ("bezier_to_vec: %g,%g %g,%g %g,%g %g,%g %d\n", |

47 | x0, y0, x1, y1, x2, y2, x3, y3, level); |

48 | #endif |

49 | if (level == 1) { |

50 | x_m = (x0 + 3 * (x1 + x2) + x3) * 0.125; |

51 | y_m = (y0 + 3 * (y1 + y2) + y3) * 0.125; |

52 | p->x = x_m; |

53 | p->y = y_m; |

54 | p++; |

55 | p->x = x3; |

56 | p->y = y3; |

57 | p++; |

58 | #ifdef VERBOSE |

59 | printf ("-> (%g, %g) -> (%g, %g)\n", x_m, y_m, x3, y3); |

60 | #endif |

61 | } else { |

62 | double xa1, ya1; |

63 | double xa2, ya2; |

64 | double xb1, yb1; |

65 | double xb2, yb2; |

66 | |

67 | xa1 = (x0 + x1) * 0.5; |

68 | ya1 = (y0 + y1) * 0.5; |

69 | xa2 = (x0 + 2 * x1 + x2) * 0.25; |

70 | ya2 = (y0 + 2 * y1 + y2) * 0.25; |

71 | xb1 = (x1 + 2 * x2 + x3) * 0.25; |

72 | yb1 = (y1 + 2 * y2 + y3) * 0.25; |

73 | xb2 = (x2 + x3) * 0.5; |

74 | yb2 = (y2 + y3) * 0.5; |

75 | x_m = (xa2 + xb1) * 0.5; |

76 | y_m = (ya2 + yb1) * 0.5; |

77 | #ifdef VERBOSE |

78 | printf ("%g,%g %g,%g %g,%g %g,%g\n", xa1, ya1, xa2, ya2, |

79 | xb1, yb1, xb2, yb2); |

80 | #endif |

81 | p = art_bezier_to_vec (x0, y0, xa1, ya1, xa2, ya2, x_m, y_m, p, level - 1); |

82 | p = art_bezier_to_vec (x_m, y_m, xb1, yb1, xb2, yb2, x3, y3, p, level - 1); |

83 | } |

84 | return p; |

85 | } |

86 | |

87 | #define RENDER_LEVEL 4 |

88 | #define RENDER_SIZE (1 << (RENDER_LEVEL)) |

89 | |

90 | /** |

91 | * art_vpath_render_bez: Render a bezier segment into the vpath. |

92 | * @p_vpath: Where the pointer to the #ArtVpath structure is stored. |

93 | * @pn_points: Pointer to the number of points in *@p_vpath. |

94 | * @pn_points_max: Pointer to the number of points allocated. |

95 | * @x0: X coordinate of starting bezier point. |

96 | * @y0: Y coordinate of starting bezier point. |

97 | * @x1: X coordinate of first bezier control point. |

98 | * @y1: Y coordinate of first bezier control point. |

99 | * @x2: X coordinate of second bezier control point. |

100 | * @y2: Y coordinate of second bezier control point. |

101 | * @x3: X coordinate of ending bezier point. |

102 | * @y3: Y coordinate of ending bezier point. |

103 | * @flatness: Flatness control. |

104 | * |

105 | * Renders a bezier segment into the vector path, reallocating and |

106 | * updating *@p_vpath and *@pn_vpath_max as necessary. *@pn_vpath is |

107 | * incremented by the number of vector points added. |

108 | * |

109 | * This step includes (@x0, @y0) but not (@x3, @y3). |

110 | * |

111 | * The @flatness argument guides the amount of subdivision. The Adobe |

112 | * PostScript reference manual defines flatness as the maximum |

113 | * deviation between the any point on the vpath approximation and the |

114 | * corresponding point on the "true" curve, and we follow this |

115 | * definition here. A value of 0.25 should ensure high quality for aa |

116 | * rendering. |

117 | **/ |

118 | static void |

119 | art_vpath_render_bez (ArtVpath **p_vpath, int *pn, int *pn_max, |

120 | double x0, double y0, |

121 | double x1, double y1, |

122 | double x2, double y2, |

123 | double x3, double y3, |

124 | double flatness) |

125 | { |

126 | double x3_0, y3_0; |

127 | double z3_0_dot; |

128 | double z1_dot, z2_dot; |

129 | double z1_perp, z2_perp; |

130 | double max_perp_sq; |

131 | |

132 | double x_m, y_m; |

133 | double xa1, ya1; |

134 | double xa2, ya2; |

135 | double xb1, yb1; |

136 | double xb2, yb2; |

137 | |

138 | /* It's possible to optimize this routine a fair amount. |

139 | |

140 | First, once the _dot conditions are met, they will also be met in |

141 | all further subdivisions. So we might recurse to a different |

142 | routine that only checks the _perp conditions. |

143 | |

144 | Second, the distance _should_ decrease according to fairly |

145 | predictable rules (a factor of 4 with each subdivision). So it might |

146 | be possible to note that the distance is within a factor of 4 of |

147 | acceptable, and subdivide once. But proving this might be hard. |

148 | |

149 | Third, at the last subdivision, x_m and y_m can be computed more |

150 | expeditiously (as in the routine above). |

151 | |

152 | Finally, if we were able to subdivide by, say 2 or 3, this would |

153 | allow considerably finer-grain control, i.e. fewer points for the |

154 | same flatness tolerance. This would speed things up downstream. |

155 | |

156 | In any case, this routine is unlikely to be the bottleneck. It's |

157 | just that I have this undying quest for more speed... |

158 | |

159 | */ |

160 | |

161 | x3_0 = x3 - x0; |

162 | y3_0 = y3 - y0; |

163 | |

164 | /* z3_0_dot is dist z0-z3 squared */ |

165 | z3_0_dot = x3_0 * x3_0 + y3_0 * y3_0; |

166 | |

167 | /* todo: this test is far from satisfactory. */ |

168 | if (z3_0_dot < 0.001) |

169 | goto nosubdivide; |

170 | |

171 | /* we can avoid subdivision if: |

172 | |

173 | z1 has distance no more than flatness from the z0-z3 line |

174 | |

175 | z1 is no more z0'ward than flatness past z0-z3 |

176 | |

177 | z1 is more z0'ward than z3'ward on the line traversing z0-z3 |

178 | |

179 | and correspondingly for z2 */ |

180 | |

181 | /* perp is distance from line, multiplied by dist z0-z3 */ |

182 | max_perp_sq = flatness * flatness * z3_0_dot; |

183 | |

184 | z1_perp = (y1 - y0) * x3_0 - (x1 - x0) * y3_0; |

185 | if (z1_perp * z1_perp > max_perp_sq) |

186 | goto subdivide; |

187 | |

188 | z2_perp = (y3 - y2) * x3_0 - (x3 - x2) * y3_0; |

189 | if (z2_perp * z2_perp > max_perp_sq) |

190 | goto subdivide; |

191 | |

192 | z1_dot = (x1 - x0) * x3_0 + (y1 - y0) * y3_0; |

193 | if (z1_dot < 0 && z1_dot * z1_dot > max_perp_sq) |

194 | goto subdivide; |

195 | |

196 | z2_dot = (x3 - x2) * x3_0 + (y3 - y2) * y3_0; |

197 | if (z2_dot < 0 && z2_dot * z2_dot > max_perp_sq) |

198 | goto subdivide; |

199 | |

200 | if (z1_dot + z1_dot > z3_0_dot) |

201 | goto subdivide; |

202 | |

203 | if (z2_dot + z2_dot > z3_0_dot) |

204 | goto subdivide; |

205 | |

206 | nosubdivide: |

207 | /* don't subdivide */ |

208 | art_vpath_add_point (p_vpath, pn, pn_max, |

209 | ART_LINETO, x3, y3); |

210 | return; |

211 | |

212 | subdivide: |

213 | |

214 | xa1 = (x0 + x1) * 0.5; |

215 | ya1 = (y0 + y1) * 0.5; |

216 | xa2 = (x0 + 2 * x1 + x2) * 0.25; |

217 | ya2 = (y0 + 2 * y1 + y2) * 0.25; |

218 | xb1 = (x1 + 2 * x2 + x3) * 0.25; |

219 | yb1 = (y1 + 2 * y2 + y3) * 0.25; |

220 | xb2 = (x2 + x3) * 0.5; |

221 | yb2 = (y2 + y3) * 0.5; |

222 | x_m = (xa2 + xb1) * 0.5; |

223 | y_m = (ya2 + yb1) * 0.5; |

224 | #ifdef VERBOSE |

225 | printf ("%g,%g %g,%g %g,%g %g,%g\n", xa1, ya1, xa2, ya2, |

226 | xb1, yb1, xb2, yb2); |

227 | #endif |

228 | art_vpath_render_bez (p_vpath, pn, pn_max, |

229 | x0, y0, xa1, ya1, xa2, ya2, x_m, y_m, flatness); |

230 | art_vpath_render_bez (p_vpath, pn, pn_max, |

231 | x_m, y_m, xb1, yb1, xb2, yb2, x3, y3, flatness); |

232 | } |

233 | |

234 | /** |

235 | * art_bez_path_to_vec: Create vpath from bezier path. |

236 | * @bez: Bezier path. |

237 | * @flatness: Flatness control. |

238 | * |

239 | * Creates a vector path closely approximating the bezier path defined by |

240 | * @bez. The @flatness argument controls the amount of subdivision. In |

241 | * general, the resulting vpath deviates by at most @flatness pixels |

242 | * from the "ideal" path described by @bez. |

243 | * |

244 | * Return value: Newly allocated vpath. |

245 | **/ |

246 | ArtVpath * |

247 | art_bez_path_to_vec (const ArtBpath *bez, double flatness) |

248 | { |

249 | ArtVpath *vec; |

250 | int vec_n, vec_n_max; |

251 | int bez_index; |

252 | double x, y; |

253 | |

254 | vec_n = 0; |

255 | vec_n_max = RENDER_SIZE; |

256 | vec = art_new (ArtVpath, vec_n_max); |

257 | |

258 | /* Initialization is unnecessary because of the precondition that the |

259 | bezier path does not begin with LINETO or CURVETO, but is here |

260 | to make the code warning-free. */ |

261 | x = 0; |

262 | y = 0; |

263 | |

264 | bez_index = 0; |

265 | do |

266 | { |

267 | #ifdef VERBOSE |

268 | printf ("%s %g %g\n", |

269 | bez[bez_index].code == ART_CURVETO ? "curveto" : |

270 | bez[bez_index].code == ART_LINETO ? "lineto" : |

271 | bez[bez_index].code == ART_MOVETO ? "moveto" : |

272 | bez[bez_index].code == ART_MOVETO_OPEN ? "moveto-open" : |

273 | "end", bez[bez_index].x3, bez[bez_index].y3); |

274 | #endif |

275 | /* make sure space for at least one more code */ |

276 | if (vec_n >= vec_n_max) |

277 | art_expand (vec, ArtVpath, vec_n_max); |

278 | switch (bez[bez_index].code) |

279 | { |

280 | case ART_MOVETO_OPEN: |

281 | case ART_MOVETO: |

282 | case ART_LINETO: |

283 | x = bez[bez_index].x3; |

284 | y = bez[bez_index].y3; |

285 | vec[vec_n].code = bez[bez_index].code; |

286 | vec[vec_n].x = x; |

287 | vec[vec_n].y = y; |

288 | vec_n++; |

289 | break; |

290 | case ART_END: |

291 | vec[vec_n].code = bez[bez_index].code; |

292 | vec[vec_n].x = 0; |

293 | vec[vec_n].y = 0; |

294 | vec_n++; |

295 | break; |

296 | case ART_CURVETO: |

297 | #ifdef VERBOSE |

298 | printf ("%g,%g %g,%g %g,%g %g,%g\n", x, y, |

299 | bez[bez_index].x1, bez[bez_index].y1, |

300 | bez[bez_index].x2, bez[bez_index].y2, |

301 | bez[bez_index].x3, bez[bez_index].y3); |

302 | #endif |

303 | art_vpath_render_bez (&vec, &vec_n, &vec_n_max, |

304 | x, y, |

305 | bez[bez_index].x1, bez[bez_index].y1, |

306 | bez[bez_index].x2, bez[bez_index].y2, |

307 | bez[bez_index].x3, bez[bez_index].y3, |

308 | flatness); |

309 | x = bez[bez_index].x3; |

310 | y = bez[bez_index].y3; |

311 | break; |

312 | } |

313 | } |

314 | while (bez[bez_index++].code != ART_END); |

315 | return vec; |

316 | } |

317 |

**Note:**See TracBrowser for help on using the repository browser.