w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

pixman-radial-gradient.c
Go to the documentation of this file.
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 <config.h>
32 #endif
33 #include <stdlib.h>
34 #include <math.h>
35 #include "pixman-private.h"
36 
37 static inline pixman_fixed_32_32_t
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 void
71  double b,
72  double c,
73  double inva,
74  double dr,
75  double mindr,
78  int Bpp,
81 {
82  /*
83  * In this function error propagation can lead to bad results:
84  * - discr can have an unbound error (if b*b-a*c is very small),
85  * potentially making it the opposite sign of what it should have been
86  * (thus clearing a pixel that would have been colored or vice-versa)
87  * or propagating the error to sqrtdiscr;
88  * if discr has the wrong sign or b is very small, this can lead to bad
89  * results
90  *
91  * - the algorithm used to compute the solutions of the quadratic
92  * equation is not numerically stable (but saves one division compared
93  * to the numerically stable one);
94  * this can be a problem if a*c is much smaller than b*b
95  *
96  * - the above problems are worse if a is small (as inva becomes bigger)
97  */
98  double discr;
99 
100  if (a == 0)
101  {
102  double t;
103 
104  if (b == 0)
105  {
106  memset (buffer, 0, Bpp);
107  return;
108  }
109 
110  t = pixman_fixed_1 / 2 * c / b;
111  if (repeat == PIXMAN_REPEAT_NONE)
112  {
113  if (0 <= t && t <= pixman_fixed_1)
114  {
115  write_pixel (walker, t, buffer);
116  return;
117  }
118  }
119  else
120  {
121  if (t * dr >= mindr)
122  {
123  write_pixel (walker, t, buffer);
124  return;
125  }
126  }
127 
128  memset (buffer, 0, Bpp);
129  return;
130  }
131 
132  discr = fdot (b, a, 0, b, -c, 0);
133  if (discr >= 0)
134  {
135  double sqrtdiscr, t0, t1;
136 
137  sqrtdiscr = sqrt (discr);
138  t0 = (b + sqrtdiscr) * inva;
139  t1 = (b - sqrtdiscr) * inva;
140 
141  /*
142  * The root that must be used is the biggest one that belongs
143  * to the valid range ([0,1] for PIXMAN_REPEAT_NONE, any
144  * solution that results in a positive radius otherwise).
145  *
146  * If a > 0, t0 is the biggest solution, so if it is valid, it
147  * is the correct result.
148  *
149  * If a < 0, only one of the solutions can be valid, so the
150  * order in which they are tested is not important.
151  */
152  if (repeat == PIXMAN_REPEAT_NONE)
153  {
154  if (0 <= t0 && t0 <= pixman_fixed_1)
155  {
156  write_pixel (walker, t0, buffer);
157  return;
158  }
159  else if (0 <= t1 && t1 <= pixman_fixed_1)
160  {
161  write_pixel (walker, t1, buffer);
162  return;
163  }
164  }
165  else
166  {
167  if (t0 * dr >= mindr)
168  {
169  write_pixel (walker, t0, buffer);
170  return;
171  }
172  else if (t1 * dr >= mindr)
173  {
174  write_pixel (walker, t1, buffer);
175  return;
176  }
177  }
178  }
179 
180  memset (buffer, 0, Bpp);
181  return;
182 }
183 
184 static uint32_t *
186  const uint32_t *mask,
187  int Bpp,
188  pixman_gradient_walker_write_t write_pixel)
189 {
190  /*
191  * Implementation of radial gradients following the PDF specification.
192  * See section 8.7.4.5.4 Type 3 (Radial) Shadings of the PDF Reference
193  * Manual (PDF 32000-1:2008 at the time of this writing).
194  *
195  * In the radial gradient problem we are given two circles (c₁,r₁) and
196  * (c₂,r₂) that define the gradient itself.
197  *
198  * Mathematically the gradient can be defined as the family of circles
199  *
200  * ((1-t)·c₁ + t·(c₂), (1-t)·r₁ + t·r₂)
201  *
202  * excluding those circles whose radius would be < 0. When a point
203  * belongs to more than one circle, the one with a bigger t is the only
204  * one that contributes to its color. When a point does not belong
205  * to any of the circles, it is transparent black, i.e. RGBA (0, 0, 0, 0).
206  * Further limitations on the range of values for t are imposed when
207  * the gradient is not repeated, namely t must belong to [0,1].
208  *
209  * The graphical result is the same as drawing the valid (radius > 0)
210  * circles with increasing t in [-inf, +inf] (or in [0,1] if the gradient
211  * is not repeated) using SOURCE operator composition.
212  *
213  * It looks like a cone pointing towards the viewer if the ending circle
214  * is smaller than the starting one, a cone pointing inside the page if
215  * the starting circle is the smaller one and like a cylinder if they
216  * have the same radius.
217  *
218  * What we actually do is, given the point whose color we are interested
219  * in, compute the t values for that point, solving for t in:
220  *
221  * length((1-t)·c₁ + t·(c₂) - p) = (1-t)·r₁ + t·r₂
222  *
223  * Let's rewrite it in a simpler way, by defining some auxiliary
224  * variables:
225  *
226  * cd = c₂ - c₁
227  * pd = p - c₁
228  * dr = r₂ - r₁
229  * length(t·cd - pd) = r₁ + t·dr
230  *
231  * which actually means
232  *
233  * hypot(t·cdx - pdx, t·cdy - pdy) = r₁ + t·dr
234  *
235  * or
236  *
237  * ⎷((t·cdx - pdx)² + (t·cdy - pdy)²) = r₁ + t·dr.
238  *
239  * If we impose (as stated earlier) that r₁ + t·dr >= 0, it becomes:
240  *
241  * (t·cdx - pdx)² + (t·cdy - pdy)² = (r₁ + t·dr)²
242  *
243  * where we can actually expand the squares and solve for t:
244  *
245  * t²cdx² - 2t·cdx·pdx + pdx² + t²cdy² - 2t·cdy·pdy + pdy² =
246  * = r₁² + 2·r₁·t·dr + t²·dr²
247  *
248  * (cdx² + cdy² - dr²)t² - 2(cdx·pdx + cdy·pdy + r₁·dr)t +
249  * (pdx² + pdy² - r₁²) = 0
250  *
251  * A = cdx² + cdy² - dr²
252  * B = pdx·cdx + pdy·cdy + r₁·dr
253  * C = pdx² + pdy² - r₁²
254  * At² - 2Bt + C = 0
255  *
256  * The solutions (unless the equation degenerates because of A = 0) are:
257  *
258  * t = (B ± ⎷(B² - A·C)) / A
259  *
260  * The solution we are going to prefer is the bigger one, unless the
261  * radius associated to it is negative (or it falls outside the valid t
262  * range).
263  *
264  * Additional observations (useful for optimizations):
265  * A does not depend on p
266  *
267  * A < 0 <=> one of the two circles completely contains the other one
268  * <=> for every p, the radiuses associated with the two t solutions
269  * have opposite sign
270  */
271  pixman_image_t *image = iter->image;
272  int x = iter->x;
273  int y = iter->y;
274  int width = iter->width;
275  uint32_t *buffer = iter->buffer;
276 
279  uint32_t *end = buffer + width * (Bpp / 4);
282 
283  /* reference point is the center of the pixel */
284  v.vector[0] = pixman_int_to_fixed (x) + pixman_fixed_1 / 2;
285  v.vector[1] = pixman_int_to_fixed (y) + pixman_fixed_1 / 2;
286  v.vector[2] = pixman_fixed_1;
287 
288  _pixman_gradient_walker_init (&walker, gradient, image->common.repeat);
289 
290  if (image->common.transform)
291  {
292  if (!pixman_transform_point_3d (image->common.transform, &v))
293  return iter->buffer;
294 
295  unit.vector[0] = image->common.transform->matrix[0][0];
296  unit.vector[1] = image->common.transform->matrix[1][0];
297  unit.vector[2] = image->common.transform->matrix[2][0];
298  }
299  else
300  {
301  unit.vector[0] = pixman_fixed_1;
302  unit.vector[1] = 0;
303  unit.vector[2] = 0;
304  }
305 
306  if (unit.vector[2] == 0 && v.vector[2] == pixman_fixed_1)
307  {
308  /*
309  * Given:
310  *
311  * t = (B ± ⎷(B² - A·C)) / A
312  *
313  * where
314  *
315  * A = cdx² + cdy² - dr²
316  * B = pdx·cdx + pdy·cdy + r₁·dr
317  * C = pdx² + pdy² - r₁²
318  * det = B² - A·C
319  *
320  * Since we have an affine transformation, we know that (pdx, pdy)
321  * increase linearly with each pixel,
322  *
323  * pdx = pdx₀ + n·ux,
324  * pdy = pdy₀ + n·uy,
325  *
326  * we can then express B, C and det through multiple differentiation.
327  */
328  pixman_fixed_32_32_t b, db, c, dc, ddc;
329 
330  /* warning: this computation may overflow */
331  v.vector[0] -= radial->c1.x;
332  v.vector[1] -= radial->c1.y;
333 
334  /*
335  * B and C are computed and updated exactly.
336  * If fdot was used instead of dot, in the worst case it would
337  * lose 11 bits of precision in each of the multiplication and
338  * summing up would zero out all the bit that were preserved,
339  * thus making the result 0 instead of the correct one.
340  * This would mean a worst case of unbound relative error or
341  * about 2^10 absolute error
342  */
343  b = dot (v.vector[0], v.vector[1], radial->c1.radius,
344  radial->delta.x, radial->delta.y, radial->delta.radius);
345  db = dot (unit.vector[0], unit.vector[1], 0,
346  radial->delta.x, radial->delta.y, 0);
347 
348  c = dot (v.vector[0], v.vector[1],
349  -((pixman_fixed_48_16_t) radial->c1.radius),
350  v.vector[0], v.vector[1], radial->c1.radius);
351  dc = dot (2 * (pixman_fixed_48_16_t) v.vector[0] + unit.vector[0],
352  2 * (pixman_fixed_48_16_t) v.vector[1] + unit.vector[1],
353  0,
354  unit.vector[0], unit.vector[1], 0);
355  ddc = 2 * dot (unit.vector[0], unit.vector[1], 0,
356  unit.vector[0], unit.vector[1], 0);
357 
358  while (buffer < end)
359  {
360  if (!mask || *mask++)
361  {
362  radial_write_color (radial->a, b, c,
363  radial->inva,
364  radial->delta.radius,
365  radial->mindr,
366  &walker,
367  image->common.repeat,
368  Bpp,
369  write_pixel,
370  buffer);
371  }
372 
373  b += db;
374  c += dc;
375  dc += ddc;
376  buffer += (Bpp / 4);
377  }
378  }
379  else
380  {
381  /* projective */
382  /* Warning:
383  * error propagation guarantees are much looser than in the affine case
384  */
385  while (buffer < end)
386  {
387  if (!mask || *mask++)
388  {
389  if (v.vector[2] != 0)
390  {
391  double pdx, pdy, invv2, b, c;
392 
393  invv2 = 1. * pixman_fixed_1 / v.vector[2];
394 
395  pdx = v.vector[0] * invv2 - radial->c1.x;
396  /* / pixman_fixed_1 */
397 
398  pdy = v.vector[1] * invv2 - radial->c1.y;
399  /* / pixman_fixed_1 */
400 
401  b = fdot (pdx, pdy, radial->c1.radius,
402  radial->delta.x, radial->delta.y,
403  radial->delta.radius);
404  /* / pixman_fixed_1 / pixman_fixed_1 */
405 
406  c = fdot (pdx, pdy, -radial->c1.radius,
407  pdx, pdy, radial->c1.radius);
408  /* / pixman_fixed_1 / pixman_fixed_1 */
409 
410  radial_write_color (radial->a, b, c,
411  radial->inva,
412  radial->delta.radius,
413  radial->mindr,
414  &walker,
415  image->common.repeat,
416  Bpp,
417  write_pixel,
418  buffer);
419  }
420  else
421  {
422  memset (buffer, 0, Bpp);
423  }
424  }
425 
426  buffer += (Bpp / 4);
427 
428  v.vector[0] += unit.vector[0];
429  v.vector[1] += unit.vector[1];
430  v.vector[2] += unit.vector[2];
431  }
432  }
433 
434  iter->y++;
435  return iter->buffer;
436 }
437 
438 static uint32_t *
440 {
441  return radial_get_scanline (iter, mask, 4,
443 }
444 
445 static uint32_t *
447 {
448  return radial_get_scanline (iter, NULL, 16,
450 }
451 
452 void
454 {
455  if (iter->iter_flags & ITER_NARROW)
457  else
459 }
460 
463  const pixman_point_fixed_t * outer,
464  pixman_fixed_t inner_radius,
465  pixman_fixed_t outer_radius,
466  const pixman_gradient_stop_t *stops,
467  int n_stops)
468 {
470  radial_gradient_t *radial;
471 
473 
474  if (!image)
475  return NULL;
476 
477  radial = &image->radial;
478 
479  if (!_pixman_init_gradient (&radial->common, stops, n_stops))
480  {
481  free (image);
482  return NULL;
483  }
484 
485  image->type = RADIAL;
486 
487  radial->c1.x = inner->x;
488  radial->c1.y = inner->y;
489  radial->c1.radius = inner_radius;
490  radial->c2.x = outer->x;
491  radial->c2.y = outer->y;
492  radial->c2.radius = outer_radius;
493 
494  /* warning: this computations may overflow */
495  radial->delta.x = radial->c2.x - radial->c1.x;
496  radial->delta.y = radial->c2.y - radial->c1.y;
497  radial->delta.radius = radial->c2.radius - radial->c1.radius;
498 
499  /* computed exactly, then cast to double -> every bit of the double
500  representation is correct (53 bits) */
501  radial->a = dot (radial->delta.x, radial->delta.y, -radial->delta.radius,
502  radial->delta.x, radial->delta.y, radial->delta.radius);
503  if (radial->a != 0)
504  radial->inva = 1. * pixman_fixed_1 / radial->a;
505 
506  radial->mindr = -1. * pixman_fixed_1 * radial->c1.radius;
507 
508  return image;
509 }
#define width(a)
Definition: aptex-macros.h:198
#define z1
#define z2
#define b
Definition: jpegint.h:372
#define free(a)
Definition: decNumber.cpp:310
int v
Definition: dviconv.c:10
double sqrt()
#define t
Definition: afcover.h:96
#define c(n)
Definition: gpos-common.c:150
#define a(n)
Definition: gpos-common.c:148
unsigned char * image
Definition: in_pcx.cpp:323
#define NULL
Definition: ftobjs.h:61
kerning y
Definition: ttdriver.c:212
unsigned int uint32_t
Definition: stdint.h:80
int unit
Definition: tfmread.c:8
float x
Definition: cordic.py:15
#define PIXMAN_EXPORT
void _pixman_gradient_walker_init(pixman_gradient_walker_t *walker, gradient_t *gradient, pixman_repeat_t repeat)
void _pixman_gradient_walker_write_narrow(pixman_gradient_walker_t *walker, pixman_fixed_48_16_t x, uint32_t *buffer)
void _pixman_gradient_walker_write_wide(pixman_gradient_walker_t *walker, pixman_fixed_48_16_t x, uint32_t *buffer)
pixman_bool_t _pixman_init_gradient(gradient_t *gradient, const pixman_gradient_stop_t *stops, int n_stops)
Definition: pixman-image.c:79
pixman_image_t * _pixman_image_allocate(void)
Definition: pixman-image.c:182
pixman_bool_t pixman_transform_point_3d(const struct pixman_transform *transform, struct pixman_vector *vector)
#define t0
#define t1
@ RADIAL
@ ITER_NARROW
void(* pixman_gradient_walker_write_t)(pixman_gradient_walker_t *walker, pixman_fixed_48_16_t x, uint32_t *buffer)
pixman_image_t * pixman_image_create_radial_gradient(const pixman_point_fixed_t *inner, const pixman_point_fixed_t *outer, pixman_fixed_t inner_radius, pixman_fixed_t outer_radius, const pixman_gradient_stop_t *stops, int n_stops)
void _pixman_radial_gradient_iter_init(pixman_image_t *image, pixman_iter_t *iter)
static uint32_t * radial_get_scanline_wide(pixman_iter_t *iter, const uint32_t *mask)
static void radial_write_color(double a, double b, double c, double inva, double dr, double mindr, pixman_gradient_walker_t *walker, pixman_repeat_t repeat, int Bpp, pixman_gradient_walker_write_t write_pixel, uint32_t *buffer)
static double fdot(double x1, double y1, double z1, double x2, double y2, double z2)
static uint32_t * radial_get_scanline_narrow(pixman_iter_t *iter, const uint32_t *mask)
static uint32_t * radial_get_scanline(pixman_iter_t *iter, const uint32_t *mask, int Bpp, pixman_gradient_walker_write_t write_pixel)
static pixman_fixed_32_32_t dot(pixman_fixed_48_16_t x1, pixman_fixed_48_16_t y1, pixman_fixed_48_16_t z1, pixman_fixed_48_16_t x2, pixman_fixed_48_16_t y2, pixman_fixed_48_16_t z2)
int64_t pixman_fixed_32_32_t
Definition: pixman.h:118
#define pixman_int_to_fixed(i)
Definition: pixman.h:130
pixman_fixed_16_16_t pixman_fixed_t
Definition: pixman.h:123
#define pixman_fixed_1
Definition: pixman.h:126
pixman_repeat_t
Definition: pixman.h:340
@ PIXMAN_REPEAT_NONE
Definition: pixman.h:341
pixman_fixed_32_32_t pixman_fixed_48_16_t
Definition: pixman.h:119
static int repeat
Definition: pnmtops.c:230
int db
Definition: ppmqvga.c:68
int dr
Definition: ppmqvga.c:68
bstring c int memset(void *s, int c, int length)
#define x1
#define y1
#define y2
#define x2
#define mask(n)
Definition: lbitlib.c:93
Definition: utils.c:300
pixman_fixed_t radius
pixman_fixed_t x
pixman_fixed_t y
Definition: sd.h:76
float transform[6]
Definition: sd.h:78
pixman_iter_get_scanline_t get_scanline
pixman_image_t * image
iter_flags_t iter_flags
uint32_t * buffer
pixman_fixed_t x
Definition: pixman.h:160
pixman_fixed_t y
Definition: pixman.h:161
gradient_t common
Definition: dvips.h:235
Definition: fio.h:71
#define end(cp)
Definition: zic.c:71