#
source:
trunk/third/mozilla/other-licenses/libart_lgpl/art_svp_render_aa.c
@
22325

Revision 22325, 12.9 KB checked in by rbasch, 19 years ago (diff) |
---|

Line | |
---|---|

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

2 | * Copyright (C) 1998-2000 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 | /* The spiffy antialiased renderer for sorted vector paths. */ |

21 | |

22 | #include "config.h" |

23 | #include "art_svp_render_aa.h" |

24 | |

25 | #include <math.h> |

26 | #include <string.h> /* for memmove */ |

27 | #include "art_misc.h" |

28 | |

29 | #include "art_rect.h" |

30 | #include "art_svp.h" |

31 | |

32 | #include <stdio.h> |

33 | |

34 | typedef double artfloat; |

35 | |

36 | struct _ArtSVPRenderAAIter { |

37 | const ArtSVP *svp; |

38 | int x0, x1; |

39 | int y; |

40 | int seg_ix; |

41 | |

42 | int *active_segs; |

43 | int n_active_segs; |

44 | int *cursor; |

45 | artfloat *seg_x; |

46 | artfloat *seg_dx; |

47 | |

48 | ArtSVPRenderAAStep *steps; |

49 | }; |

50 | |

51 | static void |

52 | art_svp_render_insert_active (int i, int *active_segs, int n_active_segs, |

53 | artfloat *seg_x, artfloat *seg_dx) |

54 | { |

55 | int j; |

56 | artfloat x; |

57 | int tmp1, tmp2; |

58 | |

59 | /* this is a cheap hack to get ^'s sorted correctly */ |

60 | x = seg_x[i] + 0.001 * seg_dx[i]; |

61 | for (j = 0; j < n_active_segs && seg_x[active_segs[j]] < x; j++); |

62 | |

63 | tmp1 = i; |

64 | while (j < n_active_segs) |

65 | { |

66 | tmp2 = active_segs[j]; |

67 | active_segs[j] = tmp1; |

68 | tmp1 = tmp2; |

69 | j++; |

70 | } |

71 | active_segs[j] = tmp1; |

72 | } |

73 | |

74 | static void |

75 | art_svp_render_delete_active (int *active_segs, int j, int n_active_segs) |

76 | { |

77 | int k; |

78 | |

79 | for (k = j; k < n_active_segs; k++) |

80 | active_segs[k] = active_segs[k + 1]; |

81 | } |

82 | |

83 | #define EPSILON 1e-6 |

84 | |

85 | /* Render the sorted vector path in the given rectangle, antialiased. |

86 | |

87 | This interface uses a callback for the actual pixel rendering. The |

88 | callback is called y1 - y0 times (once for each scan line). The y |

89 | coordinate is given as an argument for convenience (it could be |

90 | stored in the callback's private data and incremented on each |

91 | call). |

92 | |

93 | The rendered polygon is represented in a semi-runlength format: a |

94 | start value and a sequence of "steps". Each step has an x |

95 | coordinate and a value delta. The resulting value at position x is |

96 | equal to the sum of the start value and all step delta values for |

97 | which the step x coordinate is less than or equal to x. An |

98 | efficient algorithm will traverse the steps left to right, keeping |

99 | a running sum. |

100 | |

101 | All x coordinates in the steps are guaranteed to be x0 <= x < x1. |

102 | (This guarantee is a change from the gfonted vpaar renderer, and is |

103 | designed to simplify the callback). |

104 | |

105 | There is now a further guarantee that no two steps will have the |

106 | same x value. This may allow for further speedup and simplification |

107 | of renderers. |

108 | |

109 | The value 0x8000 represents 0% coverage by the polygon, while |

110 | 0xff8000 represents 100% coverage. This format is designed so that |

111 | >> 16 results in a standard 0x00..0xff value range, with nice |

112 | rounding. |

113 | |

114 | Status of this routine: |

115 | |

116 | Basic correctness: OK |

117 | |

118 | Numerical stability: pretty good, although probably not |

119 | bulletproof. |

120 | |

121 | Speed: Needs more aggressive culling of bounding boxes. Can |

122 | probably speed up the [x0,x1) clipping of step values. Can do more |

123 | of the step calculation in fixed point. |

124 | |

125 | Precision: No known problems, although it should be tested |

126 | thoroughly, especially for symmetry. |

127 | |

128 | */ |

129 | |

130 | ArtSVPRenderAAIter * |

131 | art_svp_render_aa_iter (const ArtSVP *svp, |

132 | int x0, int y0, int x1, int y1) |

133 | { |

134 | ArtSVPRenderAAIter *iter = art_new (ArtSVPRenderAAIter, 1); |

135 | |

136 | iter->svp = svp; |

137 | iter->y = y0; |

138 | iter->x0 = x0; |

139 | iter->x1 = x1; |

140 | iter->seg_ix = 0; |

141 | |

142 | iter->active_segs = art_new (int, svp->n_segs); |

143 | iter->cursor = art_new (int, svp->n_segs); |

144 | iter->seg_x = art_new (artfloat, svp->n_segs); |

145 | iter->seg_dx = art_new (artfloat, svp->n_segs); |

146 | iter->steps = art_new (ArtSVPRenderAAStep, x1 - x0); |

147 | iter->n_active_segs = 0; |

148 | |

149 | return iter; |

150 | } |

151 | |

152 | #define ADD_STEP(xpos, xdelta) \ |

153 | /* stereotype code fragment for adding a step */ \ |

154 | if (n_steps == 0 || steps[n_steps - 1].x < xpos) \ |

155 | { \ |

156 | sx = n_steps; \ |

157 | steps[sx].x = xpos; \ |

158 | steps[sx].delta = xdelta; \ |

159 | n_steps++; \ |

160 | } \ |

161 | else \ |

162 | { \ |

163 | for (sx = n_steps; sx > 0; sx--) \ |

164 | { \ |

165 | if (steps[sx - 1].x == xpos) \ |

166 | { \ |

167 | steps[sx - 1].delta += xdelta; \ |

168 | sx = n_steps; \ |

169 | break; \ |

170 | } \ |

171 | else if (steps[sx - 1].x < xpos) \ |

172 | { \ |

173 | break; \ |

174 | } \ |

175 | } \ |

176 | if (sx < n_steps) \ |

177 | { \ |

178 | memmove (&steps[sx + 1], &steps[sx], \ |

179 | (n_steps - sx) * sizeof(steps[0])); \ |

180 | steps[sx].x = xpos; \ |

181 | steps[sx].delta = xdelta; \ |

182 | n_steps++; \ |

183 | } \ |

184 | } |

185 | |

186 | void |

187 | art_svp_render_aa_iter_step (ArtSVPRenderAAIter *iter, int *p_start, |

188 | ArtSVPRenderAAStep **p_steps, int *p_n_steps) |

189 | { |

190 | const ArtSVP *svp = iter->svp; |

191 | int *active_segs = iter->active_segs; |

192 | int n_active_segs = iter->n_active_segs; |

193 | int *cursor = iter->cursor; |

194 | artfloat *seg_x = iter->seg_x; |

195 | artfloat *seg_dx = iter->seg_dx; |

196 | int i = iter->seg_ix; |

197 | int j; |

198 | int x0 = iter->x0; |

199 | int x1 = iter->x1; |

200 | int y = iter->y; |

201 | int seg_index; |

202 | |

203 | int x; |

204 | ArtSVPRenderAAStep *steps = iter->steps; |

205 | int n_steps; |

206 | artfloat y_top, y_bot; |

207 | artfloat x_top, x_bot; |

208 | artfloat x_min, x_max; |

209 | int ix_min, ix_max; |

210 | artfloat delta; /* delta should be int too? */ |

211 | int last, this; |

212 | int xdelta; |

213 | artfloat rslope, drslope; |

214 | int start; |

215 | const ArtSVPSeg *seg; |

216 | int curs; |

217 | artfloat dy; |

218 | |

219 | int sx; |

220 | |

221 | /* insert new active segments */ |

222 | for (; i < svp->n_segs && svp->segs[i].bbox.y0 < y + 1; i++) |

223 | { |

224 | if (svp->segs[i].bbox.y1 > y && |

225 | svp->segs[i].bbox.x0 < x1) |

226 | { |

227 | seg = &svp->segs[i]; |

228 | /* move cursor to topmost vector which overlaps [y,y+1) */ |

229 | for (curs = 0; seg->points[curs + 1].y < y; curs++); |

230 | cursor[i] = curs; |

231 | dy = seg->points[curs + 1].y - seg->points[curs].y; |

232 | if (fabs (dy) >= EPSILON) |

233 | seg_dx[i] = (seg->points[curs + 1].x - seg->points[curs].x) / |

234 | dy; |

235 | else |

236 | seg_dx[i] = 1e12; |

237 | seg_x[i] = seg->points[curs].x + |

238 | (y - seg->points[curs].y) * seg_dx[i]; |

239 | art_svp_render_insert_active (i, active_segs, n_active_segs++, |

240 | seg_x, seg_dx); |

241 | } |

242 | } |

243 | |

244 | n_steps = 0; |

245 | |

246 | /* render the runlengths, advancing and deleting as we go */ |

247 | start = 0x8000; |

248 | |

249 | for (j = 0; j < n_active_segs; j++) |

250 | { |

251 | seg_index = active_segs[j]; |

252 | seg = &svp->segs[seg_index]; |

253 | curs = cursor[seg_index]; |

254 | while (curs != seg->n_points - 1 && |

255 | seg->points[curs].y < y + 1) |

256 | { |

257 | y_top = y; |

258 | if (y_top < seg->points[curs].y) |

259 | y_top = seg->points[curs].y; |

260 | y_bot = y + 1; |

261 | if (y_bot > seg->points[curs + 1].y) |

262 | y_bot = seg->points[curs + 1].y; |

263 | if (y_top != y_bot) { |

264 | delta = (seg->dir ? 16711680.0 : -16711680.0) * |

265 | (y_bot - y_top); |

266 | x_top = seg_x[seg_index] + (y_top - y) * seg_dx[seg_index]; |

267 | x_bot = seg_x[seg_index] + (y_bot - y) * seg_dx[seg_index]; |

268 | if (x_top < x_bot) |

269 | { |

270 | x_min = x_top; |

271 | x_max = x_bot; |

272 | } |

273 | else |

274 | { |

275 | x_min = x_bot; |

276 | x_max = x_top; |

277 | } |

278 | ix_min = floor (x_min); |

279 | ix_max = floor (x_max); |

280 | if (ix_min >= x1) |

281 | { |

282 | /* skip; it starts to the right of the render region */ |

283 | } |

284 | else if (ix_max < x0) |

285 | /* it ends to the left of the render region */ |

286 | start += delta; |

287 | else if (ix_min == ix_max) |

288 | { |

289 | /* case 1, antialias a single pixel */ |

290 | xdelta = (ix_min + 1 - (x_min + x_max) * 0.5) * delta; |

291 | |

292 | ADD_STEP(ix_min, xdelta) |

293 | |

294 | if (ix_min + 1 < x1) |

295 | { |

296 | xdelta = delta - xdelta; |

297 | |

298 | ADD_STEP(ix_min + 1, xdelta) |

299 | } |

300 | } |

301 | else |

302 | { |

303 | /* case 2, antialias a run */ |

304 | rslope = 1.0 / fabs (seg_dx[seg_index]); |

305 | drslope = delta * rslope; |

306 | last = |

307 | drslope * 0.5 * |

308 | (ix_min + 1 - x_min) * (ix_min + 1 - x_min); |

309 | xdelta = last; |

310 | if (ix_min >= x0) |

311 | { |

312 | ADD_STEP(ix_min, xdelta) |

313 | |

314 | x = ix_min + 1; |

315 | } |

316 | else |

317 | { |

318 | start += last; |

319 | x = x0; |

320 | } |

321 | if (ix_max > x1) |

322 | ix_max = x1; |

323 | for (; x < ix_max; x++) |

324 | { |

325 | this = (seg->dir ? 16711680.0 : -16711680.0) * rslope * |

326 | (x + 0.5 - x_min); |

327 | xdelta = this - last; |

328 | last = this; |

329 | |

330 | ADD_STEP(x, xdelta) |

331 | } |

332 | if (x < x1) |

333 | { |

334 | this = |

335 | delta * (1 - 0.5 * |

336 | (x_max - ix_max) * (x_max - ix_max) * |

337 | rslope); |

338 | xdelta = this - last; |

339 | last = this; |

340 | |

341 | ADD_STEP(x, xdelta) |

342 | |

343 | if (x + 1 < x1) |

344 | { |

345 | xdelta = delta - last; |

346 | |

347 | ADD_STEP(x + 1, xdelta) |

348 | } |

349 | } |

350 | } |

351 | } |

352 | curs++; |

353 | if (curs != seg->n_points - 1 && |

354 | seg->points[curs].y < y + 1) |

355 | { |

356 | dy = seg->points[curs + 1].y - seg->points[curs].y; |

357 | if (fabs (dy) >= EPSILON) |

358 | seg_dx[seg_index] = (seg->points[curs + 1].x - |

359 | seg->points[curs].x) / dy; |

360 | else |

361 | seg_dx[seg_index] = 1e12; |

362 | seg_x[seg_index] = seg->points[curs].x + |

363 | (y - seg->points[curs].y) * seg_dx[seg_index]; |

364 | } |

365 | /* break here, instead of duplicating predicate in while? */ |

366 | } |

367 | if (seg->points[curs].y >= y + 1) |

368 | { |

369 | curs--; |

370 | cursor[seg_index] = curs; |

371 | seg_x[seg_index] += seg_dx[seg_index]; |

372 | } |

373 | else |

374 | { |

375 | art_svp_render_delete_active (active_segs, j--, |

376 | --n_active_segs); |

377 | } |

378 | } |

379 | |

380 | *p_start = start; |

381 | *p_steps = steps; |

382 | *p_n_steps = n_steps; |

383 | |

384 | iter->seg_ix = i; |

385 | iter->n_active_segs = n_active_segs; |

386 | iter->y++; |

387 | } |

388 | |

389 | void |

390 | art_svp_render_aa_iter_done (ArtSVPRenderAAIter *iter) |

391 | { |

392 | art_free (iter->steps); |

393 | |

394 | art_free (iter->seg_dx); |

395 | art_free (iter->seg_x); |

396 | art_free (iter->cursor); |

397 | art_free (iter->active_segs); |

398 | art_free (iter); |

399 | } |

400 | |

401 | /** |

402 | * art_svp_render_aa: Render SVP antialiased. |

403 | * @svp: The #ArtSVP to render. |

404 | * @x0: Left coordinate of destination rectangle. |

405 | * @y0: Top coordinate of destination rectangle. |

406 | * @x1: Right coordinate of destination rectangle. |

407 | * @y1: Bottom coordinate of destination rectangle. |

408 | * @callback: The callback which actually paints the pixels. |

409 | * @callback_data: Private data for @callback. |

410 | * |

411 | * Renders the sorted vector path in the given rectangle, antialiased. |

412 | * |

413 | * This interface uses a callback for the actual pixel rendering. The |

414 | * callback is called @y1 - @y0 times (once for each scan line). The y |

415 | * coordinate is given as an argument for convenience (it could be |

416 | * stored in the callback's private data and incremented on each |

417 | * call). |

418 | * |

419 | * The rendered polygon is represented in a semi-runlength format: a |

420 | * start value and a sequence of "steps". Each step has an x |

421 | * coordinate and a value delta. The resulting value at position x is |

422 | * equal to the sum of the start value and all step delta values for |

423 | * which the step x coordinate is less than or equal to x. An |

424 | * efficient algorithm will traverse the steps left to right, keeping |

425 | * a running sum. |

426 | * |

427 | * All x coordinates in the steps are guaranteed to be @x0 <= x < @x1. |

428 | * (This guarantee is a change from the gfonted vpaar renderer from |

429 | * which this routine is derived, and is designed to simplify the |

430 | * callback). |

431 | * |

432 | * The value 0x8000 represents 0% coverage by the polygon, while |

433 | * 0xff8000 represents 100% coverage. This format is designed so that |

434 | * >> 16 results in a standard 0x00..0xff value range, with nice |

435 | * rounding. |

436 | * |

437 | **/ |

438 | void |

439 | art_svp_render_aa (const ArtSVP *svp, |

440 | int x0, int y0, int x1, int y1, |

441 | void (*callback) (void *callback_data, |

442 | int y, |

443 | int start, |

444 | ArtSVPRenderAAStep *steps, int n_steps), |

445 | void *callback_data) |

446 | { |

447 | ArtSVPRenderAAIter *iter; |

448 | int y; |

449 | int start; |

450 | ArtSVPRenderAAStep *steps; |

451 | int n_steps; |

452 | |

453 | iter = art_svp_render_aa_iter (svp, x0, y0, x1, y1); |

454 | |

455 | |

456 | for (y = y0; y < y1; y++) |

457 | { |

458 | art_svp_render_aa_iter_step (iter, &start, &steps, &n_steps); |

459 | (*callback) (callback_data, y, start, steps, n_steps); |

460 | } |

461 | |

462 | art_svp_render_aa_iter_done (iter); |

463 | } |

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