Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
1891 | serge | 1 | /* -*- Mode: c; c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t; -*- */ |
2 | /* |
||
3 | * |
||
4 | * Copyright © 2000 Keith Packard, member of The XFree86 Project, Inc. |
||
5 | * Copyright © 2000 SuSE, Inc. |
||
6 | * 2005 Lars Knoll & Zack Rusin, Trolltech |
||
7 | * Copyright © 2007 Red Hat, Inc. |
||
8 | * |
||
9 | * |
||
10 | * Permission to use, copy, modify, distribute, and sell this software and its |
||
11 | * documentation for any purpose is hereby granted without fee, provided that |
||
12 | * the above copyright notice appear in all copies and that both that |
||
13 | * copyright notice and this permission notice appear in supporting |
||
14 | * documentation, and that the name of Keith Packard not be used in |
||
15 | * advertising or publicity pertaining to distribution of the software without |
||
16 | * specific, written prior permission. Keith Packard makes no |
||
17 | * representations about the suitability of this software for any purpose. It |
||
18 | * is provided "as is" without express or implied warranty. |
||
19 | * |
||
20 | * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS |
||
21 | * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND |
||
22 | * FITNESS, IN NO EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY |
||
23 | * SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
||
24 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN |
||
25 | * AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING |
||
26 | * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS |
||
27 | * SOFTWARE. |
||
28 | */ |
||
29 | |||
30 | #ifdef HAVE_CONFIG_H |
||
31 | #include |
||
32 | #endif |
||
33 | #include |
||
34 | #include |
||
35 | #include "pixman-private.h" |
||
36 | |||
37 | static inline pixman_fixed_32_32_t |
||
38 | dot (pixman_fixed_48_16_t x1, |
||
39 | pixman_fixed_48_16_t y1, |
||
40 | pixman_fixed_48_16_t z1, |
||
41 | pixman_fixed_48_16_t x2, |
||
42 | pixman_fixed_48_16_t y2, |
||
43 | pixman_fixed_48_16_t z2) |
||
44 | { |
||
45 | /* |
||
46 | * Exact computation, assuming that the input values can |
||
47 | * be represented as pixman_fixed_16_16_t |
||
48 | */ |
||
49 | return x1 * x2 + y1 * y2 + z1 * z2; |
||
50 | } |
||
51 | |||
52 | static inline double |
||
53 | fdot (double x1, |
||
54 | double y1, |
||
55 | double z1, |
||
56 | double x2, |
||
57 | double y2, |
||
58 | double z2) |
||
59 | { |
||
60 | /* |
||
61 | * Error can be unbound in some special cases. |
||
62 | * Using clever dot product algorithms (for example compensated |
||
63 | * dot product) would improve this but make the code much less |
||
64 | * obvious |
||
65 | */ |
||
66 | return x1 * x2 + y1 * y2 + z1 * z2; |
||
67 | } |
||
68 | |||
69 | static uint32_t |
||
70 | radial_compute_color (double a, |
||
71 | double b, |
||
72 | double c, |
||
73 | double inva, |
||
74 | double dr, |
||
75 | double mindr, |
||
76 | pixman_gradient_walker_t *walker, |
||
77 | pixman_repeat_t repeat) |
||
78 | { |
||
79 | /* |
||
80 | * In this function error propagation can lead to bad results: |
||
81 | * - det can have an unbound error (if b*b-a*c is very small), |
||
82 | * potentially making it the opposite sign of what it should have been |
||
83 | * (thus clearing a pixel that would have been colored or vice-versa) |
||
84 | * or propagating the error to sqrtdet; |
||
85 | * if det has the wrong sign or b is very small, this can lead to bad |
||
86 | * results |
||
87 | * |
||
88 | * - the algorithm used to compute the solutions of the quadratic |
||
89 | * equation is not numerically stable (but saves one division compared |
||
90 | * to the numerically stable one); |
||
91 | * this can be a problem if a*c is much smaller than b*b |
||
92 | * |
||
93 | * - the above problems are worse if a is small (as inva becomes bigger) |
||
94 | */ |
||
95 | double det; |
||
96 | |||
97 | if (a == 0) |
||
98 | { |
||
99 | double t; |
||
100 | |||
101 | if (b == 0) |
||
102 | return 0; |
||
103 | |||
104 | t = pixman_fixed_1 / 2 * c / b; |
||
105 | if (repeat == PIXMAN_REPEAT_NONE) |
||
106 | { |
||
107 | if (0 <= t && t <= pixman_fixed_1) |
||
108 | return _pixman_gradient_walker_pixel (walker, t); |
||
109 | } |
||
110 | else |
||
111 | { |
||
112 | if (t * dr > mindr) |
||
113 | return _pixman_gradient_walker_pixel (walker, t); |
||
114 | } |
||
115 | |||
116 | return 0; |
||
117 | } |
||
118 | |||
119 | det = fdot (b, a, 0, b, -c, 0); |
||
120 | if (det >= 0) |
||
121 | { |
||
122 | double sqrtdet, t0, t1; |
||
123 | |||
124 | sqrtdet = sqrt (det); |
||
125 | t0 = (b + sqrtdet) * inva; |
||
126 | t1 = (b - sqrtdet) * inva; |
||
127 | |||
128 | if (repeat == PIXMAN_REPEAT_NONE) |
||
129 | { |
||
130 | if (0 <= t0 && t0 <= pixman_fixed_1) |
||
131 | return _pixman_gradient_walker_pixel (walker, t0); |
||
132 | else if (0 <= t1 && t1 <= pixman_fixed_1) |
||
133 | return _pixman_gradient_walker_pixel (walker, t1); |
||
134 | } |
||
135 | else |
||
136 | { |
||
137 | if (t0 * dr > mindr) |
||
138 | return _pixman_gradient_walker_pixel (walker, t0); |
||
139 | else if (t1 * dr > mindr) |
||
140 | return _pixman_gradient_walker_pixel (walker, t1); |
||
141 | } |
||
142 | } |
||
143 | |||
144 | return 0; |
||
145 | } |
||
146 | |||
147 | static void |
||
148 | radial_gradient_get_scanline_32 (pixman_image_t *image, |
||
149 | int x, |
||
150 | int y, |
||
151 | int width, |
||
152 | uint32_t * buffer, |
||
153 | const uint32_t *mask) |
||
154 | { |
||
155 | /* |
||
156 | * Implementation of radial gradients following the PDF specification. |
||
157 | * See section 8.7.4.5.4 Type 3 (Radial) Shadings of the PDF Reference |
||
158 | * Manual (PDF 32000-1:2008 at the time of this writing). |
||
159 | * |
||
160 | * In the radial gradient problem we are given two circles (c₁,r₁) and |
||
161 | * (c₂,r₂) that define the gradient itself. |
||
162 | * |
||
163 | * Mathematically the gradient can be defined as the family of circles |
||
164 | * |
||
165 | * ((1-t)·c₁ + t·(c₂), (1-t)·r₁ + t·r₂) |
||
166 | * |
||
167 | * excluding those circles whose radius would be < 0. When a point |
||
168 | * belongs to more than one circle, the one with a bigger t is the only |
||
169 | * one that contributes to its color. When a point does not belong |
||
170 | * to any of the circles, it is transparent black, i.e. RGBA (0, 0, 0, 0). |
||
171 | * Further limitations on the range of values for t are imposed when |
||
172 | * the gradient is not repeated, namely t must belong to [0,1]. |
||
173 | * |
||
174 | * The graphical result is the same as drawing the valid (radius > 0) |
||
175 | * circles with increasing t in [-inf, +inf] (or in [0,1] if the gradient |
||
176 | * is not repeated) using SOURCE operatior composition. |
||
177 | * |
||
178 | * It looks like a cone pointing towards the viewer if the ending circle |
||
179 | * is smaller than the starting one, a cone pointing inside the page if |
||
180 | * the starting circle is the smaller one and like a cylinder if they |
||
181 | * have the same radius. |
||
182 | * |
||
183 | * What we actually do is, given the point whose color we are interested |
||
184 | * in, compute the t values for that point, solving for t in: |
||
185 | * |
||
186 | * length((1-t)·c₁ + t·(c₂) - p) = (1-t)·r₁ + t·r₂ |
||
187 | * |
||
188 | * Let's rewrite it in a simpler way, by defining some auxiliary |
||
189 | * variables: |
||
190 | * |
||
191 | * cd = c₂ - c₁ |
||
192 | * pd = p - c₁ |
||
193 | * dr = r₂ - r₁ |
||
194 | * lenght(t·cd - pd) = r₁ + t·dr |
||
195 | * |
||
196 | * which actually means |
||
197 | * |
||
198 | * hypot(t·cdx - pdx, t·cdy - pdy) = r₁ + t·dr |
||
199 | * |
||
200 | * or |
||
201 | * |
||
202 | * ⎷((t·cdx - pdx)² + (t·cdy - pdy)²) = r₁ + t·dr. |
||
203 | * |
||
204 | * If we impose (as stated earlier) that r₁ + t·dr >= 0, it becomes: |
||
205 | * |
||
206 | * (t·cdx - pdx)² + (t·cdy - pdy)² = (r₁ + t·dr)² |
||
207 | * |
||
208 | * where we can actually expand the squares and solve for t: |
||
209 | * |
||
210 | * t²cdx² - 2t·cdx·pdx + pdx² + t²cdy² - 2t·cdy·pdy + pdy² = |
||
211 | * = r₁² + 2·r₁·t·dr + t²·dr² |
||
212 | * |
||
213 | * (cdx² + cdy² - dr²)t² - 2(cdx·pdx + cdy·pdy + r₁·dr)t + |
||
214 | * (pdx² + pdy² - r₁²) = 0 |
||
215 | * |
||
216 | * A = cdx² + cdy² - dr² |
||
217 | * B = pdx·cdx + pdy·cdy + r₁·dr |
||
218 | * C = pdx² + pdy² - r₁² |
||
219 | * At² - 2Bt + C = 0 |
||
220 | * |
||
221 | * The solutions (unless the equation degenerates because of A = 0) are: |
||
222 | * |
||
223 | * t = (B ± ⎷(B² - A·C)) / A |
||
224 | * |
||
225 | * The solution we are going to prefer is the bigger one, unless the |
||
226 | * radius associated to it is negative (or it falls outside the valid t |
||
227 | * range). |
||
228 | * |
||
229 | * Additional observations (useful for optimizations): |
||
230 | * A does not depend on p |
||
231 | * |
||
232 | * A < 0 <=> one of the two circles completely contains the other one |
||
233 | * <=> for every p, the radiuses associated with the two t solutions |
||
234 | * have opposite sign |
||
235 | */ |
||
236 | |||
237 | gradient_t *gradient = (gradient_t *)image; |
||
238 | source_image_t *source = (source_image_t *)image; |
||
239 | radial_gradient_t *radial = (radial_gradient_t *)image; |
||
240 | uint32_t *end = buffer + width; |
||
241 | pixman_gradient_walker_t walker; |
||
242 | pixman_vector_t v, unit; |
||
243 | |||
244 | /* reference point is the center of the pixel */ |
||
245 | v.vector[0] = pixman_int_to_fixed (x) + pixman_fixed_1 / 2; |
||
246 | v.vector[1] = pixman_int_to_fixed (y) + pixman_fixed_1 / 2; |
||
247 | v.vector[2] = pixman_fixed_1; |
||
248 | |||
249 | _pixman_gradient_walker_init (&walker, gradient, source->common.repeat); |
||
250 | |||
251 | if (source->common.transform) |
||
252 | { |
||
253 | if (!pixman_transform_point_3d (source->common.transform, &v)) |
||
254 | return; |
||
255 | |||
256 | unit.vector[0] = source->common.transform->matrix[0][0]; |
||
257 | unit.vector[1] = source->common.transform->matrix[1][0]; |
||
258 | unit.vector[2] = source->common.transform->matrix[2][0]; |
||
259 | } |
||
260 | else |
||
261 | { |
||
262 | unit.vector[0] = pixman_fixed_1; |
||
263 | unit.vector[1] = 0; |
||
264 | unit.vector[2] = 0; |
||
265 | } |
||
266 | |||
267 | if (unit.vector[2] == 0 && v.vector[2] == pixman_fixed_1) |
||
268 | { |
||
269 | /* |
||
270 | * Given: |
||
271 | * |
||
272 | * t = (B ± ⎷(B² - A·C)) / A |
||
273 | * |
||
274 | * where |
||
275 | * |
||
276 | * A = cdx² + cdy² - dr² |
||
277 | * B = pdx·cdx + pdy·cdy + r₁·dr |
||
278 | * C = pdx² + pdy² - r₁² |
||
279 | * det = B² - A·C |
||
280 | * |
||
281 | * Since we have an affine transformation, we know that (pdx, pdy) |
||
282 | * increase linearly with each pixel, |
||
283 | * |
||
284 | * pdx = pdx₀ + n·ux, |
||
285 | * pdy = pdy₀ + n·uy, |
||
286 | * |
||
287 | * we can then express B, C and det through multiple differentiation. |
||
288 | */ |
||
289 | pixman_fixed_32_32_t b, db, c, dc, ddc; |
||
290 | |||
291 | /* warning: this computation may overflow */ |
||
292 | v.vector[0] -= radial->c1.x; |
||
293 | v.vector[1] -= radial->c1.y; |
||
294 | |||
295 | /* |
||
296 | * B and C are computed and updated exactly. |
||
297 | * If fdot was used instead of dot, in the worst case it would |
||
298 | * lose 11 bits of precision in each of the multiplication and |
||
299 | * summing up would zero out all the bit that were preserved, |
||
300 | * thus making the result 0 instead of the correct one. |
||
301 | * This would mean a worst case of unbound relative error or |
||
302 | * about 2^10 absolute error |
||
303 | */ |
||
304 | b = dot (v.vector[0], v.vector[1], radial->c1.radius, |
||
305 | radial->delta.x, radial->delta.y, radial->delta.radius); |
||
306 | db = dot (unit.vector[0], unit.vector[1], 0, |
||
307 | radial->delta.x, radial->delta.y, 0); |
||
308 | |||
309 | c = dot (v.vector[0], v.vector[1], |
||
310 | -((pixman_fixed_48_16_t) radial->c1.radius), |
||
311 | v.vector[0], v.vector[1], radial->c1.radius); |
||
312 | dc = dot (2 * (pixman_fixed_48_16_t) v.vector[0] + unit.vector[0], |
||
313 | 2 * (pixman_fixed_48_16_t) v.vector[1] + unit.vector[1], |
||
314 | 0, |
||
315 | unit.vector[0], unit.vector[1], 0); |
||
316 | ddc = 2 * dot (unit.vector[0], unit.vector[1], 0, |
||
317 | unit.vector[0], unit.vector[1], 0); |
||
318 | |||
319 | while (buffer < end) |
||
320 | { |
||
321 | if (!mask || *mask++) |
||
322 | { |
||
323 | *buffer = radial_compute_color (radial->a, b, c, |
||
324 | radial->inva, |
||
325 | radial->delta.radius, |
||
326 | radial->mindr, |
||
327 | &walker, |
||
328 | source->common.repeat); |
||
329 | } |
||
330 | |||
331 | b += db; |
||
332 | c += dc; |
||
333 | dc += ddc; |
||
334 | ++buffer; |
||
335 | } |
||
336 | } |
||
337 | else |
||
338 | { |
||
339 | /* projective */ |
||
340 | /* Warning: |
||
341 | * error propagation guarantees are much looser than in the affine case |
||
342 | */ |
||
343 | while (buffer < end) |
||
344 | { |
||
345 | if (!mask || *mask++) |
||
346 | { |
||
347 | if (v.vector[2] != 0) |
||
348 | { |
||
349 | double pdx, pdy, invv2, b, c; |
||
350 | |||
351 | invv2 = 1. * pixman_fixed_1 / v.vector[2]; |
||
352 | |||
353 | pdx = v.vector[0] * invv2 - radial->c1.x; |
||
354 | /* / pixman_fixed_1 */ |
||
355 | |||
356 | pdy = v.vector[1] * invv2 - radial->c1.y; |
||
357 | /* / pixman_fixed_1 */ |
||
358 | |||
359 | b = fdot (pdx, pdy, radial->c1.radius, |
||
360 | radial->delta.x, radial->delta.y, |
||
361 | radial->delta.radius); |
||
362 | /* / pixman_fixed_1 / pixman_fixed_1 */ |
||
363 | |||
364 | c = fdot (pdx, pdy, -radial->c1.radius, |
||
365 | pdx, pdy, radial->c1.radius); |
||
366 | /* / pixman_fixed_1 / pixman_fixed_1 */ |
||
367 | |||
368 | *buffer = radial_compute_color (radial->a, b, c, |
||
369 | radial->inva, |
||
370 | radial->delta.radius, |
||
371 | radial->mindr, |
||
372 | &walker, |
||
373 | source->common.repeat); |
||
374 | } |
||
375 | else |
||
376 | { |
||
377 | *buffer = 0; |
||
378 | } |
||
379 | } |
||
380 | |||
381 | ++buffer; |
||
382 | |||
383 | v.vector[0] += unit.vector[0]; |
||
384 | v.vector[1] += unit.vector[1]; |
||
385 | v.vector[2] += unit.vector[2]; |
||
386 | } |
||
387 | } |
||
388 | } |
||
389 | |||
390 | static void |
||
391 | radial_gradient_property_changed (pixman_image_t *image) |
||
392 | { |
||
393 | image->common.get_scanline_32 = radial_gradient_get_scanline_32; |
||
394 | image->common.get_scanline_64 = _pixman_image_get_scanline_generic_64; |
||
395 | } |
||
396 | |||
397 | PIXMAN_EXPORT pixman_image_t * |
||
398 | pixman_image_create_radial_gradient (pixman_point_fixed_t * inner, |
||
399 | pixman_point_fixed_t * outer, |
||
400 | pixman_fixed_t inner_radius, |
||
401 | pixman_fixed_t outer_radius, |
||
402 | const pixman_gradient_stop_t *stops, |
||
403 | int n_stops) |
||
404 | { |
||
405 | pixman_image_t *image; |
||
406 | radial_gradient_t *radial; |
||
407 | |||
408 | image = _pixman_image_allocate (); |
||
409 | |||
410 | if (!image) |
||
411 | return NULL; |
||
412 | |||
413 | radial = &image->radial; |
||
414 | |||
415 | if (!_pixman_init_gradient (&radial->common, stops, n_stops)) |
||
416 | { |
||
417 | free (image); |
||
418 | return NULL; |
||
419 | } |
||
420 | |||
421 | image->type = RADIAL; |
||
422 | |||
423 | radial->c1.x = inner->x; |
||
424 | radial->c1.y = inner->y; |
||
425 | radial->c1.radius = inner_radius; |
||
426 | radial->c2.x = outer->x; |
||
427 | radial->c2.y = outer->y; |
||
428 | radial->c2.radius = outer_radius; |
||
429 | |||
430 | /* warning: this computations may overflow */ |
||
431 | radial->delta.x = radial->c2.x - radial->c1.x; |
||
432 | radial->delta.y = radial->c2.y - radial->c1.y; |
||
433 | radial->delta.radius = radial->c2.radius - radial->c1.radius; |
||
434 | |||
435 | /* computed exactly, then cast to double -> every bit of the double |
||
436 | representation is correct (53 bits) */ |
||
437 | radial->a = dot (radial->delta.x, radial->delta.y, -radial->delta.radius, |
||
438 | radial->delta.x, radial->delta.y, radial->delta.radius); |
||
439 | if (radial->a != 0) |
||
440 | radial->inva = 1. * pixman_fixed_1 / radial->a; |
||
441 | |||
442 | radial->mindr = -1. * pixman_fixed_1 * radial->c1.radius; |
||
443 | |||
444 | image->common.property_changed = radial_gradient_property_changed; |
||
445 | |||
446 | return image; |
||
447 | }>>=>=>>>=>=>=>=>=>=> |
||
448 |