3 * Copyright © 2000 Keith Packard, member of The XFree86 Project, Inc.
4 * Copyright © 2000 SuSE, Inc.
5 * 2005 Lars Knoll & Zack Rusin, Trolltech
6 * Copyright © 2007 Red Hat, Inc.
9 * Permission to use, copy, modify, distribute, and sell this software and its
10 * documentation for any purpose is hereby granted without fee, provided that
11 * the above copyright notice appear in all copies and that both that
12 * copyright notice and this permission notice appear in supporting
13 * documentation, and that the name of Keith Packard not be used in
14 * advertising or publicity pertaining to distribution of the software without
15 * specific, written prior permission. Keith Packard makes no
16 * representations about the suitability of this software for any purpose. It
17 * is provided "as is" without express or implied warranty.
19 * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS
20 * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
21 * FITNESS, IN NO EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY
22 * SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
23 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
24 * AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
25 * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
34 #include "pixman-private.h"
37 radial_gradient_get_scanline_32 (pixman_image_t *image,
45 * In the radial gradient problem we are given two circles (c₁,r₁) and
46 * (c₂,r₂) that define the gradient itself. Then, for any point p, we
47 * must compute the value(s) of t within [0.0, 1.0] representing the
48 * circle(s) that would color the point.
50 * There are potentially two values of t since the point p can be
51 * colored by both sides of the circle, (which happens whenever one
52 * circle is not entirely contained within the other).
54 * If we solve for a value of t that is outside of [0.0, 1.0] then we
55 * use the extend mode (NONE, REPEAT, REFLECT, or PAD) to map to a
56 * value within [0.0, 1.0].
58 * Here is an illustration of the problem:
72 * Given (c₁,r₁), (c₂,r₂) and p, we must find an angle θ such that two
73 * points p₁ and p₂ on the two circles are collinear with p. Then, the
74 * desired value of t is the ratio of the length of p₁p to the length
77 * So, we have six unknown values: (p₁x, p₁y), (p₂x, p₂y), θ and t.
78 * We can also write six equations that constrain the problem:
80 * Point p₁ is a distance r₁ from c₁ at an angle of θ:
82 * 1. p₁x = c₁x + r₁·cos θ
83 * 2. p₁y = c₁y + r₁·sin θ
85 * Point p₂ is a distance r₂ from c₂ at an angle of θ:
87 * 3. p₂x = c₂x + r2·cos θ
88 * 4. p₂y = c₂y + r2·sin θ
90 * Point p lies at a fraction t along the line segment p₁p₂:
92 * 5. px = t·p₂x + (1-t)·p₁x
93 * 6. py = t·p₂y + (1-t)·p₁y
95 * To solve, first subtitute 1-4 into 5 and 6:
97 * px = t·(c₂x + r₂·cos θ) + (1-t)·(c₁x + r₁·cos θ)
98 * py = t·(c₂y + r₂·sin θ) + (1-t)·(c₁y + r₁·sin θ)
100 * Then solve each for cos θ and sin θ expressed as a function of t:
102 * cos θ = (-(c₂x - c₁x)·t + (px - c₁x)) / ((r₂-r₁)·t + r₁)
103 * sin θ = (-(c₂y - c₁y)·t + (py - c₁y)) / ((r₂-r₁)·t + r₁)
105 * To simplify this a bit, we define new variables for several of the
106 * common terms as shown below:
126 * Note that cdx, cdy, and dr do not depend on point p at all, so can
127 * be pre-computed for the entire gradient. The simplifed equations
130 * cos θ = (-cdx·t + pdx) / (dr·t + r₁)
131 * sin θ = (-cdy·t + pdy) / (dr·t + r₁)
133 * Finally, to get a single function of t and eliminate the last
134 * unknown θ, we use the identity sin²θ + cos²θ = 1. First, square
135 * each equation, (we knew a quadratic was coming since it must be
136 * possible to obtain two solutions in some cases):
138 * cos²θ = (cdx²t² - 2·cdx·pdx·t + pdx²) / (dr²·t² + 2·r₁·dr·t + r₁²)
139 * sin²θ = (cdy²t² - 2·cdy·pdy·t + pdy²) / (dr²·t² + 2·r₁·dr·t + r₁²)
141 * Then add both together, set the result equal to 1, and express as a
142 * standard quadratic equation in t of the form At² + Bt + C = 0
144 * (cdx² + cdy² - dr²)·t² - 2·(cdx·pdx + cdy·pdy + r₁·dr)·t + (pdx² + pdy² - r₁²) = 0
148 * A = cdx² + cdy² - dr²
149 * B = -2·(pdx·cdx + pdy·cdy + r₁·dr)
150 * C = pdx² + pdy² - r₁²
152 * And again, notice that A does not depend on p, so can be
153 * precomputed. From here we just use the quadratic formula to solve
156 * t = (-2·B ± ⎷(B² - 4·A·C)) / 2·A
159 gradient_t *gradient = (gradient_t *)image;
160 source_image_t *source = (source_image_t *)image;
161 radial_gradient_t *radial = (radial_gradient_t *)image;
162 uint32_t *end = buffer + width;
163 pixman_gradient_walker_t walker;
164 pixman_bool_t affine = TRUE;
172 _pixman_gradient_walker_init (&walker, gradient, source->common.repeat);
174 if (source->common.transform)
177 /* reference point is the center of the pixel */
178 v.vector[0] = pixman_int_to_fixed (x) + pixman_fixed_1 / 2;
179 v.vector[1] = pixman_int_to_fixed (y) + pixman_fixed_1 / 2;
180 v.vector[2] = pixman_fixed_1;
182 if (!pixman_transform_point_3d (source->common.transform, &v))
185 cx = source->common.transform->matrix[0][0] / 65536.;
186 cy = source->common.transform->matrix[1][0] / 65536.;
187 cz = source->common.transform->matrix[2][0] / 65536.;
189 rx = v.vector[0] / 65536.;
190 ry = v.vector[1] / 65536.;
191 rz = v.vector[2] / 65536.;
194 source->common.transform->matrix[2][0] == 0 &&
195 v.vector[2] == pixman_fixed_1;
200 /* When computing t over a scanline, we notice that some expressions
201 * are constant so we can compute them just once. Given:
203 * t = (-2·B ± ⎷(B² - 4·A·C)) / 2·A
207 * A = cdx² + cdy² - dr² [precomputed as radial->A]
208 * B = -2·(pdx·cdx + pdy·cdy + r₁·dr)
209 * C = pdx² + pdy² - r₁²
211 * Since we have an affine transformation, we know that (pdx, pdy)
212 * increase linearly with each pixel,
217 * we can then express B in terms of an linear increment along
220 * B = B₀ + n·cB, with
221 * B₀ = -2·(pdx₀·cdx + pdy₀·cdy + r₁·dr) and
222 * cB = -2·(cx·cdx + cy·cdy)
224 * Thus we can replace the full evaluation of B per-pixel (4 multiplies,
225 * 2 additions) with a single addition.
227 double r1 = radial->c1.radius / 65536.;
228 double r1sq = r1 * r1;
229 double pdx = rx - radial->c1.x / 65536.;
230 double pdy = ry - radial->c1.y / 65536.;
231 double A = radial->A;
232 double invA = -65536. / (2. * A);
234 double B = -2. * (pdx*radial->cdx + pdy*radial->cdy + r1*radial->dr);
235 double cB = -2. * (cx*radial->cdx + cy*radial->cdy);
236 pixman_bool_t invert = A * radial->dr < 0;
240 if (!mask || *mask++)
242 pixman_fixed_48_16_t t;
243 double det = B * B + A4 * (pdx * pdx + pdy * pdy - r1sq);
245 t = (pixman_fixed_48_16_t) (B * invA);
247 t = (pixman_fixed_48_16_t) ((B + sqrt (det)) * invA);
249 t = (pixman_fixed_48_16_t) ((B - sqrt (det)) * invA);
251 *buffer = _pixman_gradient_walker_pixel (&walker, t);
265 if (!mask || *mask++)
270 double c1x = radial->c1.x / 65536.0;
271 double c1y = radial->c1.y / 65536.0;
272 double r1 = radial->c1.radius / 65536.0;
273 pixman_fixed_48_16_t t;
289 B = -2 * (pdx * radial->cdx +
292 C = (pdx * pdx + pdy * pdy - r1 * r1);
294 det = (B * B) - (4 * radial->A * C);
298 if (radial->A * radial->dr < 0)
299 t = (pixman_fixed_48_16_t) ((-B - sqrt (det)) / (2.0 * radial->A) * 65536);
301 t = (pixman_fixed_48_16_t) ((-B + sqrt (det)) / (2.0 * radial->A) * 65536);
303 *buffer = _pixman_gradient_walker_pixel (&walker, t);
316 radial_gradient_property_changed (pixman_image_t *image)
318 image->common.get_scanline_32 = radial_gradient_get_scanline_32;
319 image->common.get_scanline_64 = _pixman_image_get_scanline_generic_64;
322 PIXMAN_EXPORT pixman_image_t *
323 pixman_image_create_radial_gradient (pixman_point_fixed_t * inner,
324 pixman_point_fixed_t * outer,
325 pixman_fixed_t inner_radius,
326 pixman_fixed_t outer_radius,
327 const pixman_gradient_stop_t *stops,
330 pixman_image_t *image;
331 radial_gradient_t *radial;
333 image = _pixman_image_allocate ();
338 radial = &image->radial;
340 if (!_pixman_init_gradient (&radial->common, stops, n_stops))
346 image->type = RADIAL;
348 radial->c1.x = inner->x;
349 radial->c1.y = inner->y;
350 radial->c1.radius = inner_radius;
351 radial->c2.x = outer->x;
352 radial->c2.y = outer->y;
353 radial->c2.radius = outer_radius;
354 radial->cdx = pixman_fixed_to_double (radial->c2.x - radial->c1.x);
355 radial->cdy = pixman_fixed_to_double (radial->c2.y - radial->c1.y);
356 radial->dr = pixman_fixed_to_double (radial->c2.radius - radial->c1.radius);
357 radial->A = (radial->cdx * radial->cdx +
358 radial->cdy * radial->cdy -
359 radial->dr * radial->dr);
361 image->common.property_changed = radial_gradient_property_changed;