Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4349 | Serge | 1 | /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */ |
2 | /* cairo - a vector graphics library with display and print output |
||
3 | * |
||
4 | * Copyright 2009 Andrea Canciani |
||
5 | * |
||
6 | * This library is free software; you can redistribute it and/or |
||
7 | * modify it either under the terms of the GNU Lesser General Public |
||
8 | * License version 2.1 as published by the Free Software Foundation |
||
9 | * (the "LGPL") or, at your option, under the terms of the Mozilla |
||
10 | * Public License Version 1.1 (the "MPL"). If you do not alter this |
||
11 | * notice, a recipient may use your version of this file under either |
||
12 | * the MPL or the LGPL. |
||
13 | * |
||
14 | * You should have received a copy of the LGPL along with this library |
||
15 | * in the file COPYING-LGPL-2.1; if not, write to the Free Software |
||
16 | * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA |
||
17 | * You should have received a copy of the MPL along with this library |
||
18 | * in the file COPYING-MPL-1.1 |
||
19 | * |
||
20 | * The contents of this file are subject to the Mozilla Public License |
||
21 | * Version 1.1 (the "License"); you may not use this file except in |
||
22 | * compliance with the License. You may obtain a copy of the License at |
||
23 | * http://www.mozilla.org/MPL/ |
||
24 | * |
||
25 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY |
||
26 | * OF ANY KIND, either express or implied. See the LGPL or the MPL for |
||
27 | * the specific language governing rights and limitations. |
||
28 | * |
||
29 | * The Original Code is the cairo graphics library. |
||
30 | * |
||
31 | * The Initial Developer of the Original Code is Andrea Canciani. |
||
32 | * |
||
33 | * Contributor(s): |
||
34 | * Andrea Canciani |
||
35 | */ |
||
36 | |||
37 | #include "cairoint.h" |
||
38 | |||
39 | #include "cairo-array-private.h" |
||
40 | #include "cairo-pattern-private.h" |
||
41 | |||
42 | /* |
||
43 | * Rasterizer for mesh patterns. |
||
44 | * |
||
45 | * This implementation is based on techniques derived from several |
||
46 | * papers (available from ACM): |
||
47 | * |
||
48 | * - Lien, Shantz and Pratt "Adaptive Forward Differencing for |
||
49 | * Rendering Curves and Surfaces" (discussion of the AFD technique, |
||
50 | * bound of 1/sqrt(2) on step length without proof) |
||
51 | * |
||
52 | * - Popescu and Rosen, "Forward rasterization" (description of |
||
53 | * forward rasterization, proof of the previous bound) |
||
54 | * |
||
55 | * - Klassen, "Integer Forward Differencing of Cubic Polynomials: |
||
56 | * Analysis and Algorithms" |
||
57 | * |
||
58 | * - Klassen, "Exact Integer Hybrid Subdivision and Forward |
||
59 | * Differencing of Cubics" (improving the bound on the minimum |
||
60 | * number of steps) |
||
61 | * |
||
62 | * - Chang, Shantz and Rocchetti, "Rendering Cubic Curves and Surfaces |
||
63 | * with Integer Adaptive Forward Differencing" (analysis of forward |
||
64 | * differencing applied to Bezier patches) |
||
65 | * |
||
66 | * Notes: |
||
67 | * - Poor performance expected in degenerate cases |
||
68 | * |
||
69 | * - Patches mostly outside the drawing area are drawn completely (and |
||
70 | * clipped), wasting time |
||
71 | * |
||
72 | * - Both previous problems are greatly reduced by splitting until a |
||
73 | * reasonably small size and clipping the new tiles: execution time |
||
74 | * is quadratic in the convex-hull diameter instead than linear to |
||
75 | * the painted area. Splitting the tiles doesn't change the painted |
||
76 | * area but (usually) reduces the bounding box area (bbox area can |
||
77 | * remain the same after splitting, but cannot grow) |
||
78 | * |
||
79 | * - The initial implementation used adaptive forward differencing, |
||
80 | * but simple forward differencing scored better in benchmarks |
||
81 | * |
||
82 | * Idea: |
||
83 | * |
||
84 | * We do a sampling over the cubic patch with step du and dv (in the |
||
85 | * two parameters) that guarantees that any point of our sampling will |
||
86 | * be at most at 1/sqrt(2) from its adjacent points. In formulae |
||
87 | * (assuming B is the patch): |
||
88 | * |
||
89 | * |B(u,v) - B(u+du,v)| < 1/sqrt(2) |
||
90 | * |B(u,v) - B(u,v+dv)| < 1/sqrt(2) |
||
91 | * |
||
92 | * This means that every pixel covered by the patch will contain at |
||
93 | * least one of the samples, thus forward rasterization can be |
||
94 | * performed. Sketch of proof (from Popescu and Rosen): |
||
95 | * |
||
96 | * Let's take the P pixel we're interested into. If we assume it to be |
||
97 | * square, its boundaries define 9 regions on the plane: |
||
98 | * |
||
99 | * 1|2|3 |
||
100 | * -+-+- |
||
101 | * 8|P|4 |
||
102 | * -+-+- |
||
103 | * 7|6|5 |
||
104 | * |
||
105 | * Let's check that the pixel P will contain at least one point |
||
106 | * assuming that it is covered by the patch. |
||
107 | * |
||
108 | * Since the pixel is covered by the patch, its center will belong to |
||
109 | * (at least) one of the quads: |
||
110 | * |
||
111 | * {(B(u,v), B(u+du,v), B(u,v+dv), B(u+du,v+dv)) for u,v in [0,1]} |
||
112 | * |
||
113 | * If P doesn't contain any of the corners of the quad: |
||
114 | * |
||
115 | * - if one of the corners is in 1,3,5 or 7, other two of them have to |
||
116 | * be in 2,4,6 or 8, thus if the last corner is not in P, the length |
||
117 | * of one of the edges will be > 1/sqrt(2) |
||
118 | * |
||
119 | * - if none of the corners is in 1,3,5 or 7, all of them are in 2,4,6 |
||
120 | * and/or 8. If they are all in different regions, they can't |
||
121 | * satisfy the distance constraint. If two of them are in the same |
||
122 | * region (let's say 2), no point is in 6 and again it is impossible |
||
123 | * to have the center of P in the quad respecting the distance |
||
124 | * constraint (both these assertions can be checked by continuity |
||
125 | * considering the length of the edges of a quad with the vertices |
||
126 | * on the edges of P) |
||
127 | * |
||
128 | * Each of the cases led to a contradiction, so P contains at least |
||
129 | * one of the corners of the quad. |
||
130 | */ |
||
131 | |||
132 | /* |
||
133 | * Make sure that errors are less than 1 in fixed point math if you |
||
134 | * change these values. |
||
135 | * |
||
136 | * The error is amplified by about steps^3/4 times. |
||
137 | * The rasterizer always uses a number of steps that is a power of 2. |
||
138 | * |
||
139 | * 256 is the maximum allowed number of steps (to have error < 1) |
||
140 | * using 8.24 for the differences. |
||
141 | */ |
||
142 | #define STEPS_MAX_V 256.0 |
||
143 | #define STEPS_MAX_U 256.0 |
||
144 | |||
145 | /* |
||
146 | * If the patch/curve is only partially visible, split it to a finer |
||
147 | * resolution to get higher chances to clip (part of) it. |
||
148 | * |
||
149 | * These values have not been computed, but simply obtained |
||
150 | * empirically (by benchmarking some patches). They should never be |
||
151 | * greater than STEPS_MAX_V (or STEPS_MAX_U), but they can be as small |
||
152 | * as 1 (depending on how much you want to spend time in splitting the |
||
153 | * patch/curve when trying to save some rasterization time). |
||
154 | */ |
||
155 | #define STEPS_CLIP_V 64.0 |
||
156 | #define STEPS_CLIP_U 64.0 |
||
157 | |||
158 | |||
159 | /* Utils */ |
||
160 | static inline double |
||
161 | sqlen (cairo_point_double_t p0, cairo_point_double_t p1) |
||
162 | { |
||
163 | cairo_point_double_t delta; |
||
164 | |||
165 | delta.x = p0.x - p1.x; |
||
166 | delta.y = p0.y - p1.y; |
||
167 | |||
168 | return delta.x * delta.x + delta.y * delta.y; |
||
169 | } |
||
170 | |||
171 | static inline int16_t |
||
172 | _color_delta_to_shifted_short (int32_t from, int32_t to, int shift) |
||
173 | { |
||
174 | int32_t delta = to - from; |
||
175 | |||
176 | /* We need to round toward zero, because otherwise adding the |
||
177 | * delta 2^shift times can overflow */ |
||
178 | if (delta >= 0) |
||
179 | return delta >> shift; |
||
180 | else |
||
181 | return -((-delta) >> shift); |
||
182 | } |
||
183 | |||
184 | /* |
||
185 | * Convert a number of steps to the equivalent shift. |
||
186 | * |
||
187 | * Input: the square of the minimum number of steps |
||
188 | * |
||
189 | * Output: the smallest integer x such that 2^x > steps |
||
190 | */ |
||
191 | static inline int |
||
192 | sqsteps2shift (double steps_sq) |
||
193 | { |
||
194 | int r; |
||
195 | frexp (MAX (1.0, steps_sq), &r); |
||
196 | return (r + 1) >> 1; |
||
197 | } |
||
198 | |||
199 | /* |
||
200 | * FD functions |
||
201 | * |
||
202 | * A Bezier curve is defined (with respect to a parameter t in |
||
203 | * [0,1]) from its nodes (x,y,z,w) like this: |
||
204 | * |
||
205 | * B(t) = x(1-t)^3 + 3yt(1-t)^2 + 3zt^2(1-t) + wt^3 |
||
206 | * |
||
207 | * To efficiently evaluate a Bezier curve, the rasterizer uses forward |
||
208 | * differences. Given x, y, z, w (the 4 nodes of the Bezier curve), it |
||
209 | * is possible to convert them to forward differences form and walk |
||
210 | * over the curve using fd_init (), fd_down () and fd_fwd (). |
||
211 | * |
||
212 | * f[0] is always the value of the Bezier curve for "current" t. |
||
213 | */ |
||
214 | |||
215 | /* |
||
216 | * Initialize the coefficient for forward differences. |
||
217 | * |
||
218 | * Input: x,y,z,w are the 4 nodes of the Bezier curve |
||
219 | * |
||
220 | * Output: f[i] is the i-th difference of the curve |
||
221 | * |
||
222 | * f[0] is the value of the curve for t==0, i.e. f[0]==x. |
||
223 | * |
||
224 | * The initial step is 1; this means that each step increases t by 1 |
||
225 | * (so fd_init () immediately followed by fd_fwd (f) n times makes |
||
226 | * f[0] be the value of the curve for t==n). |
||
227 | */ |
||
228 | static inline void |
||
229 | fd_init (double x, double y, double z, double w, double f[4]) |
||
230 | { |
||
231 | f[0] = x; |
||
232 | f[1] = w - x; |
||
233 | f[2] = 6. * (w - 2. * z + y); |
||
234 | f[3] = 6. * (w - 3. * z + 3. * y - x); |
||
235 | } |
||
236 | |||
237 | /* |
||
238 | * Halve the step of the coefficients for forward differences. |
||
239 | * |
||
240 | * Input: f[i] is the i-th difference of the curve |
||
241 | * |
||
242 | * Output: f[i] is the i-th difference of the curve with half the |
||
243 | * original step |
||
244 | * |
||
245 | * f[0] is not affected, so the current t is not changed. |
||
246 | * |
||
247 | * The other coefficients are changed so that the step is half the |
||
248 | * original step. This means that doing fd_fwd (f) n times with the |
||
249 | * input f results in the same f[0] as doing fd_fwd (f) 2n times with |
||
250 | * the output f. |
||
251 | */ |
||
252 | static inline void |
||
253 | fd_down (double f[4]) |
||
254 | { |
||
255 | f[3] *= 0.125; |
||
256 | f[2] = f[2] * 0.25 - f[3]; |
||
257 | f[1] = (f[1] - f[2]) * 0.5; |
||
258 | } |
||
259 | |||
260 | /* |
||
261 | * Perform one step of forward differences along the curve. |
||
262 | * |
||
263 | * Input: f[i] is the i-th difference of the curve |
||
264 | * |
||
265 | * Output: f[i] is the i-th difference of the curve after one step |
||
266 | */ |
||
267 | static inline void |
||
268 | fd_fwd (double f[4]) |
||
269 | { |
||
270 | f[0] += f[1]; |
||
271 | f[1] += f[2]; |
||
272 | f[2] += f[3]; |
||
273 | } |
||
274 | |||
275 | /* |
||
276 | * Transform to integer forward differences. |
||
277 | * |
||
278 | * Input: d[n] is the n-th difference (in double precision) |
||
279 | * |
||
280 | * Output: i[n] is the n-th difference (in fixed point precision) |
||
281 | * |
||
282 | * i[0] is 9.23 fixed point, other differences are 4.28 fixed point. |
||
283 | */ |
||
284 | static inline void |
||
285 | fd_fixed (double d[4], int32_t i[4]) |
||
286 | { |
||
287 | i[0] = _cairo_fixed_16_16_from_double (256 * 2 * d[0]); |
||
288 | i[1] = _cairo_fixed_16_16_from_double (256 * 16 * d[1]); |
||
289 | i[2] = _cairo_fixed_16_16_from_double (256 * 16 * d[2]); |
||
290 | i[3] = _cairo_fixed_16_16_from_double (256 * 16 * d[3]); |
||
291 | } |
||
292 | |||
293 | /* |
||
294 | * Perform one step of integer forward differences along the curve. |
||
295 | * |
||
296 | * Input: f[n] is the n-th difference |
||
297 | * |
||
298 | * Output: f[n] is the n-th difference |
||
299 | * |
||
300 | * f[0] is 9.23 fixed point, other differences are 4.28 fixed point. |
||
301 | */ |
||
302 | static inline void |
||
303 | fd_fixed_fwd (int32_t f[4]) |
||
304 | { |
||
305 | f[0] += (f[1] >> 5) + ((f[1] >> 4) & 1); |
||
306 | f[1] += f[2]; |
||
307 | f[2] += f[3]; |
||
308 | } |
||
309 | |||
310 | /* |
||
311 | * Compute the minimum number of steps that guarantee that walking |
||
312 | * over a curve will leave no holes. |
||
313 | * |
||
314 | * Input: p[0..3] the nodes of the Bezier curve |
||
315 | * |
||
316 | * Returns: the square of the number of steps |
||
317 | * |
||
318 | * Idea: |
||
319 | * |
||
320 | * We want to make sure that at every step we move by less than |
||
321 | * 1/sqrt(2). |
||
322 | * |
||
323 | * The derivative of the cubic Bezier with nodes (p0, p1, p2, p3) is |
||
324 | * the quadratic Bezier with nodes (p1-p0, p2-p1, p3-p2) scaled by 3, |
||
325 | * so (since a Bezier curve is always bounded by its convex hull), we |
||
326 | * can say that: |
||
327 | * |
||
328 | * max(|B'(t)|) <= 3 max (|p1-p0|, |p2-p1|, |p3-p2|) |
||
329 | * |
||
330 | * We can improve this by noticing that a quadratic Bezier (a,b,c) is |
||
331 | * bounded by the quad (a,lerp(a,b,t),lerp(b,c,t),c) for any t, so |
||
332 | * (substituting the previous values, using t=0.5 and simplifying): |
||
333 | * |
||
334 | * max(|B'(t)|) <= 3 max (|p1-p0|, |p2-p0|/2, |p3-p1|/2, |p3-p2|) |
||
335 | * |
||
336 | * So, to guarantee a maximum step length of 1/sqrt(2) we must do: |
||
337 | * |
||
338 | * 3 max (|p1-p0|, |p2-p0|/2, |p3-p1|/2, |p3-p2|) sqrt(2) steps |
||
339 | */ |
||
340 | static inline double |
||
341 | bezier_steps_sq (cairo_point_double_t p[4]) |
||
342 | { |
||
343 | double tmp = sqlen (p[0], p[1]); |
||
344 | tmp = MAX (tmp, sqlen (p[2], p[3])); |
||
345 | tmp = MAX (tmp, sqlen (p[0], p[2]) * .25); |
||
346 | tmp = MAX (tmp, sqlen (p[1], p[3]) * .25); |
||
347 | return 18.0 * tmp; |
||
348 | } |
||
349 | |||
350 | /* |
||
351 | * Split a 1D Bezier cubic using de Casteljau's algorithm. |
||
352 | * |
||
353 | * Input: x,y,z,w the nodes of the Bezier curve |
||
354 | * |
||
355 | * Output: x0,y0,z0,w0 and x1,y1,z1,w1 are respectively the nodes of |
||
356 | * the first half and of the second half of the curve |
||
357 | * |
||
358 | * The output control nodes have to be distinct. |
||
359 | */ |
||
360 | static inline void |
||
361 | split_bezier_1D (double x, double y, double z, double w, |
||
362 | double *x0, double *y0, double *z0, double *w0, |
||
363 | double *x1, double *y1, double *z1, double *w1) |
||
364 | { |
||
365 | double tmp; |
||
366 | |||
367 | *x0 = x; |
||
368 | *w1 = w; |
||
369 | |||
370 | tmp = 0.5 * (y + z); |
||
371 | *y0 = 0.5 * (x + y); |
||
372 | *z1 = 0.5 * (z + w); |
||
373 | |||
374 | *z0 = 0.5 * (*y0 + tmp); |
||
375 | *y1 = 0.5 * (tmp + *z1); |
||
376 | |||
377 | *w0 = *x1 = 0.5 * (*z0 + *y1); |
||
378 | } |
||
379 | |||
380 | /* |
||
381 | * Split a Bezier curve using de Casteljau's algorithm. |
||
382 | * |
||
383 | * Input: p[0..3] the nodes of the Bezier curve |
||
384 | * |
||
385 | * Output: fst_half[0..3] and snd_half[0..3] are respectively the |
||
386 | * nodes of the first and of the second half of the curve |
||
387 | * |
||
388 | * fst_half and snd_half must be different, but they can be the same as |
||
389 | * nodes. |
||
390 | */ |
||
391 | static void |
||
392 | split_bezier (cairo_point_double_t p[4], |
||
393 | cairo_point_double_t fst_half[4], |
||
394 | cairo_point_double_t snd_half[4]) |
||
395 | { |
||
396 | split_bezier_1D (p[0].x, p[1].x, p[2].x, p[3].x, |
||
397 | &fst_half[0].x, &fst_half[1].x, &fst_half[2].x, &fst_half[3].x, |
||
398 | &snd_half[0].x, &snd_half[1].x, &snd_half[2].x, &snd_half[3].x); |
||
399 | |||
400 | split_bezier_1D (p[0].y, p[1].y, p[2].y, p[3].y, |
||
401 | &fst_half[0].y, &fst_half[1].y, &fst_half[2].y, &fst_half[3].y, |
||
402 | &snd_half[0].y, &snd_half[1].y, &snd_half[2].y, &snd_half[3].y); |
||
403 | } |
||
404 | |||
405 | |||
406 | typedef enum _intersection { |
||
407 | INSIDE = -1, /* the interval is entirely contained in the reference interval */ |
||
408 | OUTSIDE = 0, /* the interval has no intersection with the reference interval */ |
||
409 | PARTIAL = 1 /* the interval intersects the reference interval (but is not fully inside it) */ |
||
410 | } intersection_t; |
||
411 | |||
412 | /* |
||
413 | * Check if an interval if inside another. |
||
414 | * |
||
415 | * Input: a,b are the extrema of the first interval |
||
416 | * c,d are the extrema of the second interval |
||
417 | * |
||
418 | * Returns: INSIDE iff [a,b) intersection [c,d) = [a,b) |
||
419 | * OUTSIDE iff [a,b) intersection [c,d) = {} |
||
420 | * PARTIAL otherwise |
||
421 | * |
||
422 | * The function assumes a < b and c < d |
||
423 | * |
||
424 | * Note: Bitwise-anding the results along each component gives the |
||
425 | * expected result for [a,b) x [A,B) intersection [c,d) x [C,D). |
||
426 | */ |
||
427 | static inline int |
||
428 | intersect_interval (double a, double b, double c, double d) |
||
429 | { |
||
430 | if (c <= a && b <= d) |
||
431 | return INSIDE; |
||
432 | else if (a >= d || b <= c) |
||
433 | return OUTSIDE; |
||
434 | else |
||
435 | return PARTIAL; |
||
436 | } |
||
437 | |||
438 | /* |
||
439 | * Set the color of a pixel. |
||
440 | * |
||
441 | * Input: data is the base pointer of the image |
||
442 | * width, height are the dimensions of the image |
||
443 | * stride is the stride in bytes between adjacent rows |
||
444 | * x, y are the coordinates of the pixel to be colored |
||
445 | * r,g,b,a are the color components of the color to be set |
||
446 | * |
||
447 | * Output: the (x,y) pixel in data has the (r,g,b,a) color |
||
448 | * |
||
449 | * The input color components are not premultiplied, but the data |
||
450 | * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc, |
||
451 | * premultiplied). |
||
452 | * |
||
453 | * If the pixel to be set is outside the image, this function does |
||
454 | * nothing. |
||
455 | */ |
||
456 | static inline void |
||
457 | draw_pixel (unsigned char *data, int width, int height, int stride, |
||
458 | int x, int y, uint16_t r, uint16_t g, uint16_t b, uint16_t a) |
||
459 | { |
||
460 | if (likely (0 <= x && 0 <= y && x < width && y < height)) { |
||
461 | uint32_t tr, tg, tb, ta; |
||
462 | |||
463 | /* Premultiply and round */ |
||
464 | ta = a; |
||
465 | tr = r * ta + 0x8000; |
||
466 | tg = g * ta + 0x8000; |
||
467 | tb = b * ta + 0x8000; |
||
468 | |||
469 | tr += tr >> 16; |
||
470 | tg += tg >> 16; |
||
471 | tb += tb >> 16; |
||
472 | |||
473 | *((uint32_t*) (data + y*stride + 4*x)) = ((ta << 16) & 0xff000000) | |
||
474 | ((tr >> 8) & 0xff0000) | ((tg >> 16) & 0xff00) | (tb >> 24); |
||
475 | } |
||
476 | } |
||
477 | |||
478 | /* |
||
479 | * Forward-rasterize a cubic curve using forward differences. |
||
480 | * |
||
481 | * Input: data is the base pointer of the image |
||
482 | * width, height are the dimensions of the image |
||
483 | * stride is the stride in bytes between adjacent rows |
||
484 | * ushift is log2(n) if n is the number of desired steps |
||
485 | * dxu[i], dyu[i] are the x,y forward differences of the curve |
||
486 | * r0,g0,b0,a0 are the color components of the start point |
||
487 | * r3,g3,b3,a3 are the color components of the end point |
||
488 | * |
||
489 | * Output: data will be changed to have the requested curve drawn in |
||
490 | * the specified colors |
||
491 | * |
||
492 | * The input color components are not premultiplied, but the data |
||
493 | * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc, |
||
494 | * premultiplied). |
||
495 | * |
||
496 | * The function draws n+1 pixels, that is from the point at step 0 to |
||
497 | * the point at step n, both included. This is the discrete equivalent |
||
498 | * to drawing the curve for values of the interpolation parameter in |
||
499 | * [0,1] (including both extremes). |
||
500 | */ |
||
501 | static inline void |
||
502 | rasterize_bezier_curve (unsigned char *data, int width, int height, int stride, |
||
503 | int ushift, double dxu[4], double dyu[4], |
||
504 | uint16_t r0, uint16_t g0, uint16_t b0, uint16_t a0, |
||
505 | uint16_t r3, uint16_t g3, uint16_t b3, uint16_t a3) |
||
506 | { |
||
507 | int32_t xu[4], yu[4]; |
||
508 | int x0, y0, u, usteps = 1 << ushift; |
||
509 | |||
510 | uint16_t r = r0, g = g0, b = b0, a = a0; |
||
511 | int16_t dr = _color_delta_to_shifted_short (r0, r3, ushift); |
||
512 | int16_t dg = _color_delta_to_shifted_short (g0, g3, ushift); |
||
513 | int16_t db = _color_delta_to_shifted_short (b0, b3, ushift); |
||
514 | int16_t da = _color_delta_to_shifted_short (a0, a3, ushift); |
||
515 | |||
516 | fd_fixed (dxu, xu); |
||
517 | fd_fixed (dyu, yu); |
||
518 | |||
519 | /* |
||
520 | * Use (dxu[0],dyu[0]) as origin for the forward differences. |
||
521 | * |
||
522 | * This makes it possible to handle much larger coordinates (the |
||
523 | * ones that can be represented as cairo_fixed_t) |
||
524 | */ |
||
525 | x0 = _cairo_fixed_from_double (dxu[0]); |
||
526 | y0 = _cairo_fixed_from_double (dyu[0]); |
||
527 | xu[0] = 0; |
||
528 | yu[0] = 0; |
||
529 | |||
530 | for (u = 0; u <= usteps; ++u) { |
||
531 | /* |
||
532 | * This rasterizer assumes that pixels are integer aligned |
||
533 | * squares, so a generic (x,y) point belongs to the pixel with |
||
534 | * top-left coordinates (floor(x), floor(y)) |
||
535 | */ |
||
536 | |||
537 | int x = _cairo_fixed_integer_floor (x0 + (xu[0] >> 15) + ((xu[0] >> 14) & 1)); |
||
538 | int y = _cairo_fixed_integer_floor (y0 + (yu[0] >> 15) + ((yu[0] >> 14) & 1)); |
||
539 | |||
540 | draw_pixel (data, width, height, stride, x, y, r, g, b, a); |
||
541 | |||
542 | fd_fixed_fwd (xu); |
||
543 | fd_fixed_fwd (yu); |
||
544 | r += dr; |
||
545 | g += dg; |
||
546 | b += db; |
||
547 | a += da; |
||
548 | } |
||
549 | } |
||
550 | |||
551 | /* |
||
552 | * Clip, split and rasterize a Bezier curve. |
||
553 | * |
||
554 | * Input: data is the base pointer of the image |
||
555 | * width, height are the dimensions of the image |
||
556 | * stride is the stride in bytes between adjacent rows |
||
557 | * p[i] is the i-th node of the Bezier curve |
||
558 | * c0[i] is the i-th color component at the start point |
||
559 | * c3[i] is the i-th color component at the end point |
||
560 | * |
||
561 | * Output: data will be changed to have the requested curve drawn in |
||
562 | * the specified colors |
||
563 | * |
||
564 | * The input color components are not premultiplied, but the data |
||
565 | * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc, |
||
566 | * premultiplied). |
||
567 | * |
||
568 | * The color components are red, green, blue and alpha, in this order. |
||
569 | * |
||
570 | * The function guarantees that it will draw the curve with a step |
||
571 | * small enough to never have a distance above 1/sqrt(2) between two |
||
572 | * consecutive points (which is needed to ensure that no hole can |
||
573 | * appear when using this function to rasterize a patch). |
||
574 | */ |
||
575 | static void |
||
576 | draw_bezier_curve (unsigned char *data, int width, int height, int stride, |
||
577 | cairo_point_double_t p[4], double c0[4], double c3[4]) |
||
578 | { |
||
579 | double top, bottom, left, right, steps_sq; |
||
580 | int i, v; |
||
581 | |||
582 | top = bottom = p[0].y; |
||
583 | for (i = 1; i < 4; ++i) { |
||
584 | top = MIN (top, p[i].y); |
||
585 | bottom = MAX (bottom, p[i].y); |
||
586 | } |
||
587 | |||
588 | /* Check visibility */ |
||
589 | v = intersect_interval (top, bottom, 0, height); |
||
590 | if (v == OUTSIDE) |
||
591 | return; |
||
592 | |||
593 | left = right = p[0].x; |
||
594 | for (i = 1; i < 4; ++i) { |
||
595 | left = MIN (left, p[i].x); |
||
596 | right = MAX (right, p[i].x); |
||
597 | } |
||
598 | |||
599 | v &= intersect_interval (left, right, 0, width); |
||
600 | if (v == OUTSIDE) |
||
601 | return; |
||
602 | |||
603 | steps_sq = bezier_steps_sq (p); |
||
604 | if (steps_sq >= (v == INSIDE ? STEPS_MAX_U * STEPS_MAX_U : STEPS_CLIP_U * STEPS_CLIP_U)) { |
||
605 | /* |
||
606 | * The number of steps is greater than the threshold. This |
||
607 | * means that either the error would become too big if we |
||
608 | * directly rasterized it or that we can probably save some |
||
609 | * time by splitting the curve and clipping part of it |
||
610 | */ |
||
611 | cairo_point_double_t first[4], second[4]; |
||
612 | double midc[4]; |
||
613 | split_bezier (p, first, second); |
||
614 | midc[0] = (c0[0] + c3[0]) * 0.5; |
||
615 | midc[1] = (c0[1] + c3[1]) * 0.5; |
||
616 | midc[2] = (c0[2] + c3[2]) * 0.5; |
||
617 | midc[3] = (c0[3] + c3[3]) * 0.5; |
||
618 | draw_bezier_curve (data, width, height, stride, first, c0, midc); |
||
619 | draw_bezier_curve (data, width, height, stride, second, midc, c3); |
||
620 | } else { |
||
621 | double xu[4], yu[4]; |
||
622 | int ushift = sqsteps2shift (steps_sq), k; |
||
623 | |||
624 | fd_init (p[0].x, p[1].x, p[2].x, p[3].x, xu); |
||
625 | fd_init (p[0].y, p[1].y, p[2].y, p[3].y, yu); |
||
626 | |||
627 | for (k = 0; k < ushift; ++k) { |
||
628 | fd_down (xu); |
||
629 | fd_down (yu); |
||
630 | } |
||
631 | |||
632 | rasterize_bezier_curve (data, width, height, stride, ushift, |
||
633 | xu, yu, |
||
634 | _cairo_color_double_to_short (c0[0]), |
||
635 | _cairo_color_double_to_short (c0[1]), |
||
636 | _cairo_color_double_to_short (c0[2]), |
||
637 | _cairo_color_double_to_short (c0[3]), |
||
638 | _cairo_color_double_to_short (c3[0]), |
||
639 | _cairo_color_double_to_short (c3[1]), |
||
640 | _cairo_color_double_to_short (c3[2]), |
||
641 | _cairo_color_double_to_short (c3[3])); |
||
642 | |||
643 | /* Draw the end point, to make sure that we didn't leave it |
||
644 | * out because of rounding */ |
||
645 | draw_pixel (data, width, height, stride, |
||
646 | _cairo_fixed_integer_floor (_cairo_fixed_from_double (p[3].x)), |
||
647 | _cairo_fixed_integer_floor (_cairo_fixed_from_double (p[3].y)), |
||
648 | _cairo_color_double_to_short (c3[0]), |
||
649 | _cairo_color_double_to_short (c3[1]), |
||
650 | _cairo_color_double_to_short (c3[2]), |
||
651 | _cairo_color_double_to_short (c3[3])); |
||
652 | } |
||
653 | } |
||
654 | |||
655 | /* |
||
656 | * Forward-rasterize a cubic Bezier patch using forward differences. |
||
657 | * |
||
658 | * Input: data is the base pointer of the image |
||
659 | * width, height are the dimensions of the image |
||
660 | * stride is the stride in bytes between adjacent rows |
||
661 | * vshift is log2(n) if n is the number of desired steps |
||
662 | * p[i][j], p[i][j] are the the nodes of the Bezier patch |
||
663 | * col[i][j] is the j-th color component of the i-th corner |
||
664 | * |
||
665 | * Output: data will be changed to have the requested patch drawn in |
||
666 | * the specified colors |
||
667 | * |
||
668 | * The nodes of the patch are as follows: |
||
669 | * |
||
670 | * u\v 0 - > 1 |
||
671 | * 0 p00 p01 p02 p03 |
||
672 | * | p10 p11 p12 p13 |
||
673 | * v p20 p21 p22 p23 |
||
674 | * 1 p30 p31 p32 p33 |
||
675 | * |
||
676 | * i.e. u varies along the first component (rows), v varies along the |
||
677 | * second one (columns). |
||
678 | * |
||
679 | * The color components are red, green, blue and alpha, in this order. |
||
680 | * c[0..3] are the colors in p00, p30, p03, p33 respectively |
||
681 | * |
||
682 | * The input color components are not premultiplied, but the data |
||
683 | * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc, |
||
684 | * premultiplied). |
||
685 | * |
||
686 | * If the patch folds over itself, the part with the highest v |
||
687 | * parameter is considered above. If both have the same v, the one |
||
688 | * with the highest u parameter is above. |
||
689 | * |
||
690 | * The function draws n+1 curves, that is from the curve at step 0 to |
||
691 | * the curve at step n, both included. This is the discrete equivalent |
||
692 | * to drawing the patch for values of the interpolation parameter in |
||
693 | * [0,1] (including both extremes). |
||
694 | */ |
||
695 | static inline void |
||
696 | rasterize_bezier_patch (unsigned char *data, int width, int height, int stride, int vshift, |
||
697 | cairo_point_double_t p[4][4], double col[4][4]) |
||
698 | { |
||
699 | double pv[4][2][4], cstart[4], cend[4], dcstart[4], dcend[4]; |
||
700 | int vsteps, v, i, k; |
||
701 | |||
702 | vsteps = 1 << vshift; |
||
703 | |||
704 | /* |
||
705 | * pv[i][0] is the function (represented using forward |
||
706 | * differences) mapping v to the x coordinate of the i-th node of |
||
707 | * the Bezier curve with parameter u. |
||
708 | * (Likewise p[i][0] gives the y coordinate). |
||
709 | * |
||
710 | * This means that (pv[0][0][0],pv[0][1][0]), |
||
711 | * (pv[1][0][0],pv[1][1][0]), (pv[2][0][0],pv[2][1][0]) and |
||
712 | * (pv[3][0][0],pv[3][1][0]) are the nodes of the Bezier curve for |
||
713 | * the "current" v value (see the FD comments for more details). |
||
714 | */ |
||
715 | for (i = 0; i < 4; ++i) { |
||
716 | fd_init (p[i][0].x, p[i][1].x, p[i][2].x, p[i][3].x, pv[i][0]); |
||
717 | fd_init (p[i][0].y, p[i][1].y, p[i][2].y, p[i][3].y, pv[i][1]); |
||
718 | for (k = 0; k < vshift; ++k) { |
||
719 | fd_down (pv[i][0]); |
||
720 | fd_down (pv[i][1]); |
||
721 | } |
||
722 | } |
||
723 | |||
724 | for (i = 0; i < 4; ++i) { |
||
725 | cstart[i] = col[0][i]; |
||
726 | cend[i] = col[1][i]; |
||
727 | dcstart[i] = (col[2][i] - col[0][i]) / vsteps; |
||
728 | dcend[i] = (col[3][i] - col[1][i]) / vsteps; |
||
729 | } |
||
730 | |||
731 | for (v = 0; v <= vsteps; ++v) { |
||
732 | cairo_point_double_t nodes[4]; |
||
733 | for (i = 0; i < 4; ++i) { |
||
734 | nodes[i].x = pv[i][0][0]; |
||
735 | nodes[i].y = pv[i][1][0]; |
||
736 | } |
||
737 | |||
738 | draw_bezier_curve (data, width, height, stride, nodes, cstart, cend); |
||
739 | |||
740 | for (i = 0; i < 4; ++i) { |
||
741 | fd_fwd (pv[i][0]); |
||
742 | fd_fwd (pv[i][1]); |
||
743 | cstart[i] += dcstart[i]; |
||
744 | cend[i] += dcend[i]; |
||
745 | } |
||
746 | } |
||
747 | } |
||
748 | |||
749 | /* |
||
750 | * Clip, split and rasterize a Bezier cubic patch. |
||
751 | * |
||
752 | * Input: data is the base pointer of the image |
||
753 | * width, height are the dimensions of the image |
||
754 | * stride is the stride in bytes between adjacent rows |
||
755 | * p[i][j], p[i][j] are the nodes of the patch |
||
756 | * col[i][j] is the j-th color component of the i-th corner |
||
757 | * |
||
758 | * Output: data will be changed to have the requested patch drawn in |
||
759 | * the specified colors |
||
760 | * |
||
761 | * The nodes of the patch are as follows: |
||
762 | * |
||
763 | * u\v 0 - > 1 |
||
764 | * 0 p00 p01 p02 p03 |
||
765 | * | p10 p11 p12 p13 |
||
766 | * v p20 p21 p22 p23 |
||
767 | * 1 p30 p31 p32 p33 |
||
768 | * |
||
769 | * i.e. u varies along the first component (rows), v varies along the |
||
770 | * second one (columns). |
||
771 | * |
||
772 | * The color components are red, green, blue and alpha, in this order. |
||
773 | * c[0..3] are the colors in p00, p30, p03, p33 respectively |
||
774 | * |
||
775 | * The input color components are not premultiplied, but the data |
||
776 | * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc, |
||
777 | * premultiplied). |
||
778 | * |
||
779 | * If the patch folds over itself, the part with the highest v |
||
780 | * parameter is considered above. If both have the same v, the one |
||
781 | * with the highest u parameter is above. |
||
782 | * |
||
783 | * The function guarantees that it will draw the patch with a step |
||
784 | * small enough to never have a distance above 1/sqrt(2) between two |
||
785 | * adjacent points (which guarantees that no hole can appear). |
||
786 | * |
||
787 | * This function can be used to rasterize a tile of PDF type 7 |
||
788 | * shadings (see http://www.adobe.com/devnet/pdf/pdf_reference.html). |
||
789 | */ |
||
790 | static void |
||
791 | draw_bezier_patch (unsigned char *data, int width, int height, int stride, |
||
792 | cairo_point_double_t p[4][4], double c[4][4]) |
||
793 | { |
||
794 | double top, bottom, left, right, steps_sq; |
||
795 | int i, j, v; |
||
796 | |||
797 | top = bottom = p[0][0].y; |
||
798 | for (i = 0; i < 4; ++i) { |
||
799 | for (j= 0; j < 4; ++j) { |
||
800 | top = MIN (top, p[i][j].y); |
||
801 | bottom = MAX (bottom, p[i][j].y); |
||
802 | } |
||
803 | } |
||
804 | |||
805 | v = intersect_interval (top, bottom, 0, height); |
||
806 | if (v == OUTSIDE) |
||
807 | return; |
||
808 | |||
809 | left = right = p[0][0].x; |
||
810 | for (i = 0; i < 4; ++i) { |
||
811 | for (j= 0; j < 4; ++j) { |
||
812 | left = MIN (left, p[i][j].x); |
||
813 | right = MAX (right, p[i][j].x); |
||
814 | } |
||
815 | } |
||
816 | |||
817 | v &= intersect_interval (left, right, 0, width); |
||
818 | if (v == OUTSIDE) |
||
819 | return; |
||
820 | |||
821 | steps_sq = 0; |
||
822 | for (i = 0; i < 4; ++i) |
||
823 | steps_sq = MAX (steps_sq, bezier_steps_sq (p[i])); |
||
824 | |||
825 | if (steps_sq >= (v == INSIDE ? STEPS_MAX_V * STEPS_MAX_V : STEPS_CLIP_V * STEPS_CLIP_V)) { |
||
826 | /* The number of steps is greater than the threshold. This |
||
827 | * means that either the error would become too big if we |
||
828 | * directly rasterized it or that we can probably save some |
||
829 | * time by splitting the curve and clipping part of it. The |
||
830 | * patch is only split in the v direction to guarantee that |
||
831 | * rasterizing each part will overwrite parts with low v with |
||
832 | * overlapping parts with higher v. */ |
||
833 | |||
834 | cairo_point_double_t first[4][4], second[4][4]; |
||
835 | double subc[4][4]; |
||
836 | |||
837 | for (i = 0; i < 4; ++i) |
||
838 | split_bezier (p[i], first[i], second[i]); |
||
839 | |||
840 | for (i = 0; i < 4; ++i) { |
||
841 | subc[0][i] = c[0][i]; |
||
842 | subc[1][i] = c[1][i]; |
||
843 | subc[2][i] = 0.5 * (c[0][i] + c[2][i]); |
||
844 | subc[3][i] = 0.5 * (c[1][i] + c[3][i]); |
||
845 | } |
||
846 | |||
847 | draw_bezier_patch (data, width, height, stride, first, subc); |
||
848 | |||
849 | for (i = 0; i < 4; ++i) { |
||
850 | subc[0][i] = subc[2][i]; |
||
851 | subc[1][i] = subc[3][i]; |
||
852 | subc[2][i] = c[2][i]; |
||
853 | subc[3][i] = c[3][i]; |
||
854 | } |
||
855 | draw_bezier_patch (data, width, height, stride, second, subc); |
||
856 | } else { |
||
857 | rasterize_bezier_patch (data, width, height, stride, sqsteps2shift (steps_sq), p, c); |
||
858 | } |
||
859 | } |
||
860 | |||
861 | /* |
||
862 | * Draw a tensor product shading pattern. |
||
863 | * |
||
864 | * Input: mesh is the mesh pattern |
||
865 | * data is the base pointer of the image |
||
866 | * width, height are the dimensions of the image |
||
867 | * stride is the stride in bytes between adjacent rows |
||
868 | * |
||
869 | * Output: data will be changed to have the pattern drawn on it |
||
870 | * |
||
871 | * data is assumed to be clear and its content is assumed to be in |
||
872 | * CAIRO_FORMAT_ARGB32 (8 bpc, premultiplied). |
||
873 | * |
||
874 | * This function can be used to rasterize a PDF type 7 shading (see |
||
875 | * http://www.adobe.com/devnet/pdf/pdf_reference.html). |
||
876 | */ |
||
877 | void |
||
878 | _cairo_mesh_pattern_rasterize (const cairo_mesh_pattern_t *mesh, |
||
879 | void *data, |
||
880 | int width, |
||
881 | int height, |
||
882 | int stride, |
||
883 | double x_offset, |
||
884 | double y_offset) |
||
885 | { |
||
886 | cairo_point_double_t nodes[4][4]; |
||
887 | double colors[4][4]; |
||
888 | cairo_matrix_t p2u; |
||
889 | unsigned int i, j, k, n; |
||
890 | cairo_status_t status; |
||
891 | const cairo_mesh_patch_t *patch; |
||
892 | const cairo_color_t *c; |
||
893 | |||
894 | assert (mesh->base.status == CAIRO_STATUS_SUCCESS); |
||
895 | assert (mesh->current_patch == NULL); |
||
896 | |||
897 | p2u = mesh->base.matrix; |
||
898 | status = cairo_matrix_invert (&p2u); |
||
899 | assert (status == CAIRO_STATUS_SUCCESS); |
||
900 | |||
901 | n = _cairo_array_num_elements (&mesh->patches); |
||
902 | patch = _cairo_array_index_const (&mesh->patches, 0); |
||
903 | for (i = 0; i < n; i++) { |
||
904 | for (j = 0; j < 4; j++) { |
||
905 | for (k = 0; k < 4; k++) { |
||
906 | nodes[j][k] = patch->points[j][k]; |
||
907 | cairo_matrix_transform_point (&p2u, &nodes[j][k].x, &nodes[j][k].y); |
||
908 | nodes[j][k].x += x_offset; |
||
909 | nodes[j][k].y += y_offset; |
||
910 | } |
||
911 | } |
||
912 | |||
913 | c = &patch->colors[0]; |
||
914 | colors[0][0] = c->red; |
||
915 | colors[0][1] = c->green; |
||
916 | colors[0][2] = c->blue; |
||
917 | colors[0][3] = c->alpha; |
||
918 | |||
919 | c = &patch->colors[3]; |
||
920 | colors[1][0] = c->red; |
||
921 | colors[1][1] = c->green; |
||
922 | colors[1][2] = c->blue; |
||
923 | colors[1][3] = c->alpha; |
||
924 | |||
925 | c = &patch->colors[1]; |
||
926 | colors[2][0] = c->red; |
||
927 | colors[2][1] = c->green; |
||
928 | colors[2][2] = c->blue; |
||
929 | colors[2][3] = c->alpha; |
||
930 | |||
931 | c = &patch->colors[2]; |
||
932 | colors[3][0] = c->red; |
||
933 | colors[3][1] = c->green; |
||
934 | colors[3][2] = c->blue; |
||
935 | colors[3][3] = c->alpha; |
||
936 | |||
937 | draw_bezier_patch (data, width, height, stride, nodes, colors); |
||
938 | patch++; |
||
939 | } |
||
940 | }>>>>>>>>>>>>>=>>>>><>>>>=>><>><>>>=>=>=>=>=>>>=>=>>>> |