An LGPL/GPL-licensed artwork library
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

art_svp_render_aa.c 13KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463
  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. /* The spiffy antialiased renderer for sorted vector paths. */
  20. #include "config.h"
  21. #include "art_svp_render_aa.h"
  22. #include <math.h>
  23. #include <string.h> /* for memmove */
  24. #include "art_misc.h"
  25. #include "art_rect.h"
  26. #include "art_svp.h"
  27. #include <stdio.h>
  28. typedef double artfloat;
  29. struct _ArtSVPRenderAAIter {
  30. const ArtSVP *svp;
  31. int x0, x1;
  32. int y;
  33. int seg_ix;
  34. int *active_segs;
  35. int n_active_segs;
  36. int *cursor;
  37. artfloat *seg_x;
  38. artfloat *seg_dx;
  39. ArtSVPRenderAAStep *steps;
  40. };
  41. static void
  42. art_svp_render_insert_active (int i, int *active_segs, int n_active_segs,
  43. artfloat *seg_x, artfloat *seg_dx)
  44. {
  45. int j;
  46. artfloat x;
  47. int tmp1, tmp2;
  48. /* this is a cheap hack to get ^'s sorted correctly */
  49. x = seg_x[i] + 0.001 * seg_dx[i];
  50. for (j = 0; j < n_active_segs && seg_x[active_segs[j]] < x; j++);
  51. tmp1 = i;
  52. while (j < n_active_segs)
  53. {
  54. tmp2 = active_segs[j];
  55. active_segs[j] = tmp1;
  56. tmp1 = tmp2;
  57. j++;
  58. }
  59. active_segs[j] = tmp1;
  60. }
  61. static void
  62. art_svp_render_delete_active (int *active_segs, int j, int n_active_segs)
  63. {
  64. int k;
  65. for (k = j; k < n_active_segs; k++)
  66. active_segs[k] = active_segs[k + 1];
  67. }
  68. #define EPSILON 1e-6
  69. /* Render the sorted vector path in the given rectangle, antialiased.
  70. This interface uses a callback for the actual pixel rendering. The
  71. callback is called y1 - y0 times (once for each scan line). The y
  72. coordinate is given as an argument for convenience (it could be
  73. stored in the callback's private data and incremented on each
  74. call).
  75. The rendered polygon is represented in a semi-runlength format: a
  76. start value and a sequence of "steps". Each step has an x
  77. coordinate and a value delta. The resulting value at position x is
  78. equal to the sum of the start value and all step delta values for
  79. which the step x coordinate is less than or equal to x. An
  80. efficient algorithm will traverse the steps left to right, keeping
  81. a running sum.
  82. All x coordinates in the steps are guaranteed to be x0 <= x < x1.
  83. (This guarantee is a change from the gfonted vpaar renderer, and is
  84. designed to simplify the callback).
  85. There is now a further guarantee that no two steps will have the
  86. same x value. This may allow for further speedup and simplification
  87. of renderers.
  88. The value 0x8000 represents 0% coverage by the polygon, while
  89. 0xff8000 represents 100% coverage. This format is designed so that
  90. >> 16 results in a standard 0x00..0xff value range, with nice
  91. rounding.
  92. Status of this routine:
  93. Basic correctness: OK
  94. Numerical stability: pretty good, although probably not
  95. bulletproof.
  96. Speed: Needs more aggressive culling of bounding boxes. Can
  97. probably speed up the [x0,x1) clipping of step values. Can do more
  98. of the step calculation in fixed point.
  99. Precision: No known problems, although it should be tested
  100. thoroughly, especially for symmetry.
  101. */
  102. ArtSVPRenderAAIter *
  103. art_svp_render_aa_iter (const ArtSVP *svp,
  104. int x0, int y0, int x1, int y1)
  105. {
  106. ArtSVPRenderAAIter *iter = art_new (ArtSVPRenderAAIter, 1);
  107. iter->svp = svp;
  108. iter->y = y0;
  109. iter->x0 = x0;
  110. iter->x1 = x1;
  111. iter->seg_ix = 0;
  112. iter->active_segs = art_new (int, svp->n_segs);
  113. iter->cursor = art_new (int, svp->n_segs);
  114. iter->seg_x = art_new (artfloat, svp->n_segs);
  115. iter->seg_dx = art_new (artfloat, svp->n_segs);
  116. iter->steps = art_new (ArtSVPRenderAAStep, x1 - x0);
  117. iter->n_active_segs = 0;
  118. return iter;
  119. }
  120. #define ADD_STEP(xpos, xdelta) \
  121. /* stereotype code fragment for adding a step */ \
  122. if (n_steps == 0 || steps[n_steps - 1].x < xpos) \
  123. { \
  124. sx = n_steps; \
  125. steps[sx].x = xpos; \
  126. steps[sx].delta = xdelta; \
  127. n_steps++; \
  128. } \
  129. else \
  130. { \
  131. for (sx = n_steps; sx > 0; sx--) \
  132. { \
  133. if (steps[sx - 1].x == xpos) \
  134. { \
  135. steps[sx - 1].delta += xdelta; \
  136. sx = n_steps; \
  137. break; \
  138. } \
  139. else if (steps[sx - 1].x < xpos) \
  140. { \
  141. break; \
  142. } \
  143. } \
  144. if (sx < n_steps) \
  145. { \
  146. memmove (&steps[sx + 1], &steps[sx], \
  147. (n_steps - sx) * sizeof(steps[0])); \
  148. steps[sx].x = xpos; \
  149. steps[sx].delta = xdelta; \
  150. n_steps++; \
  151. } \
  152. }
  153. void
  154. art_svp_render_aa_iter_step (ArtSVPRenderAAIter *iter, int *p_start,
  155. ArtSVPRenderAAStep **p_steps, int *p_n_steps)
  156. {
  157. const ArtSVP *svp = iter->svp;
  158. int *active_segs = iter->active_segs;
  159. int n_active_segs = iter->n_active_segs;
  160. int *cursor = iter->cursor;
  161. artfloat *seg_x = iter->seg_x;
  162. artfloat *seg_dx = iter->seg_dx;
  163. int i = iter->seg_ix;
  164. int j;
  165. int x0 = iter->x0;
  166. int x1 = iter->x1;
  167. int y = iter->y;
  168. int seg_index;
  169. int x;
  170. ArtSVPRenderAAStep *steps = iter->steps;
  171. int n_steps;
  172. artfloat y_top, y_bot;
  173. artfloat x_top, x_bot;
  174. artfloat x_min, x_max;
  175. int ix_min, ix_max;
  176. artfloat delta; /* delta should be int too? */
  177. int last, this;
  178. int xdelta;
  179. artfloat rslope, drslope;
  180. int start;
  181. const ArtSVPSeg *seg;
  182. int curs;
  183. artfloat dy;
  184. int sx;
  185. /* insert new active segments */
  186. for (; i < svp->n_segs && svp->segs[i].bbox.y0 < y + 1; i++)
  187. {
  188. if (svp->segs[i].bbox.y1 > y &&
  189. svp->segs[i].bbox.x0 < x1)
  190. {
  191. seg = &svp->segs[i];
  192. /* move cursor to topmost vector which overlaps [y,y+1) */
  193. for (curs = 0; seg->points[curs + 1].y < y; curs++);
  194. cursor[i] = curs;
  195. dy = seg->points[curs + 1].y - seg->points[curs].y;
  196. if (fabs (dy) >= EPSILON)
  197. seg_dx[i] = (seg->points[curs + 1].x - seg->points[curs].x) /
  198. dy;
  199. else
  200. seg_dx[i] = 1e12;
  201. seg_x[i] = seg->points[curs].x +
  202. (y - seg->points[curs].y) * seg_dx[i];
  203. art_svp_render_insert_active (i, active_segs, n_active_segs++,
  204. seg_x, seg_dx);
  205. }
  206. }
  207. n_steps = 0;
  208. /* render the runlengths, advancing and deleting as we go */
  209. start = 0x8000;
  210. for (j = 0; j < n_active_segs; j++)
  211. {
  212. seg_index = active_segs[j];
  213. seg = &svp->segs[seg_index];
  214. curs = cursor[seg_index];
  215. while (curs != seg->n_points - 1 &&
  216. seg->points[curs].y < y + 1)
  217. {
  218. y_top = y;
  219. if (y_top < seg->points[curs].y)
  220. y_top = seg->points[curs].y;
  221. y_bot = y + 1;
  222. if (y_bot > seg->points[curs + 1].y)
  223. y_bot = seg->points[curs + 1].y;
  224. if (y_top != y_bot) {
  225. delta = (seg->dir ? 16711680.0 : -16711680.0) *
  226. (y_bot - y_top);
  227. x_top = seg_x[seg_index] + (y_top - y) * seg_dx[seg_index];
  228. x_bot = seg_x[seg_index] + (y_bot - y) * seg_dx[seg_index];
  229. if (x_top < x_bot)
  230. {
  231. x_min = x_top;
  232. x_max = x_bot;
  233. }
  234. else
  235. {
  236. x_min = x_bot;
  237. x_max = x_top;
  238. }
  239. ix_min = floor (x_min);
  240. ix_max = floor (x_max);
  241. if (ix_min >= x1)
  242. {
  243. /* skip; it starts to the right of the render region */
  244. }
  245. else if (ix_max < x0)
  246. /* it ends to the left of the render region */
  247. start += delta;
  248. else if (ix_min == ix_max)
  249. {
  250. /* case 1, antialias a single pixel */
  251. xdelta = (ix_min + 1 - (x_min + x_max) * 0.5) * delta;
  252. ADD_STEP(ix_min, xdelta)
  253. if (ix_min + 1 < x1)
  254. {
  255. xdelta = delta - xdelta;
  256. ADD_STEP(ix_min + 1, xdelta)
  257. }
  258. }
  259. else
  260. {
  261. /* case 2, antialias a run */
  262. rslope = 1.0 / fabs (seg_dx[seg_index]);
  263. drslope = delta * rslope;
  264. last =
  265. drslope * 0.5 *
  266. (ix_min + 1 - x_min) * (ix_min + 1 - x_min);
  267. xdelta = last;
  268. if (ix_min >= x0)
  269. {
  270. ADD_STEP(ix_min, xdelta)
  271. x = ix_min + 1;
  272. }
  273. else
  274. {
  275. start += last;
  276. x = x0;
  277. }
  278. if (ix_max > x1)
  279. ix_max = x1;
  280. for (; x < ix_max; x++)
  281. {
  282. this = (seg->dir ? 16711680.0 : -16711680.0) * rslope *
  283. (x + 0.5 - x_min);
  284. xdelta = this - last;
  285. last = this;
  286. ADD_STEP(x, xdelta)
  287. }
  288. if (x < x1)
  289. {
  290. this =
  291. delta * (1 - 0.5 *
  292. (x_max - ix_max) * (x_max - ix_max) *
  293. rslope);
  294. xdelta = this - last;
  295. last = this;
  296. ADD_STEP(x, xdelta)
  297. if (x + 1 < x1)
  298. {
  299. xdelta = delta - last;
  300. ADD_STEP(x + 1, xdelta)
  301. }
  302. }
  303. }
  304. }
  305. curs++;
  306. if (curs != seg->n_points - 1 &&
  307. seg->points[curs].y < y + 1)
  308. {
  309. dy = seg->points[curs + 1].y - seg->points[curs].y;
  310. if (fabs (dy) >= EPSILON)
  311. seg_dx[seg_index] = (seg->points[curs + 1].x -
  312. seg->points[curs].x) / dy;
  313. else
  314. seg_dx[seg_index] = 1e12;
  315. seg_x[seg_index] = seg->points[curs].x +
  316. (y - seg->points[curs].y) * seg_dx[seg_index];
  317. }
  318. /* break here, instead of duplicating predicate in while? */
  319. }
  320. if (seg->points[curs].y >= y + 1)
  321. {
  322. curs--;
  323. cursor[seg_index] = curs;
  324. seg_x[seg_index] += seg_dx[seg_index];
  325. }
  326. else
  327. {
  328. art_svp_render_delete_active (active_segs, j--,
  329. --n_active_segs);
  330. }
  331. }
  332. *p_start = start;
  333. *p_steps = steps;
  334. *p_n_steps = n_steps;
  335. iter->seg_ix = i;
  336. iter->n_active_segs = n_active_segs;
  337. iter->y++;
  338. }
  339. void
  340. art_svp_render_aa_iter_done (ArtSVPRenderAAIter *iter)
  341. {
  342. art_free (iter->steps);
  343. art_free (iter->seg_dx);
  344. art_free (iter->seg_x);
  345. art_free (iter->cursor);
  346. art_free (iter->active_segs);
  347. art_free (iter);
  348. }
  349. /**
  350. * art_svp_render_aa: Render SVP antialiased.
  351. * @svp: The #ArtSVP to render.
  352. * @x0: Left coordinate of destination rectangle.
  353. * @y0: Top coordinate of destination rectangle.
  354. * @x1: Right coordinate of destination rectangle.
  355. * @y1: Bottom coordinate of destination rectangle.
  356. * @callback: The callback which actually paints the pixels.
  357. * @callback_data: Private data for @callback.
  358. *
  359. * Renders the sorted vector path in the given rectangle, antialiased.
  360. *
  361. * This interface uses a callback for the actual pixel rendering. The
  362. * callback is called @y1 - @y0 times (once for each scan line). The y
  363. * coordinate is given as an argument for convenience (it could be
  364. * stored in the callback's private data and incremented on each
  365. * call).
  366. *
  367. * The rendered polygon is represented in a semi-runlength format: a
  368. * start value and a sequence of "steps". Each step has an x
  369. * coordinate and a value delta. The resulting value at position x is
  370. * equal to the sum of the start value and all step delta values for
  371. * which the step x coordinate is less than or equal to x. An
  372. * efficient algorithm will traverse the steps left to right, keeping
  373. * a running sum.
  374. *
  375. * All x coordinates in the steps are guaranteed to be @x0 <= x < @x1.
  376. * (This guarantee is a change from the gfonted vpaar renderer from
  377. * which this routine is derived, and is designed to simplify the
  378. * callback).
  379. *
  380. * The value 0x8000 represents 0% coverage by the polygon, while
  381. * 0xff8000 represents 100% coverage. This format is designed so that
  382. * >> 16 results in a standard 0x00..0xff value range, with nice
  383. * rounding.
  384. *
  385. **/
  386. void
  387. art_svp_render_aa (const ArtSVP *svp,
  388. int x0, int y0, int x1, int y1,
  389. void (*callback) (void *callback_data,
  390. int y,
  391. int start,
  392. ArtSVPRenderAAStep *steps, int n_steps),
  393. void *callback_data)
  394. {
  395. ArtSVPRenderAAIter *iter;
  396. int y;
  397. int start;
  398. ArtSVPRenderAAStep *steps;
  399. int n_steps;
  400. iter = art_svp_render_aa_iter (svp, x0, y0, x1, y1);
  401. for (y = y0; y < y1; y++)
  402. {
  403. art_svp_render_aa_iter_step (iter, &start, &steps, &n_steps);
  404. (*callback) (callback_data, y, start, steps, n_steps);
  405. }
  406. art_svp_render_aa_iter_done (iter);
  407. }