pixman/pixman-radial-gradient.c

   1 /*
   2  *
   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.
   7  *
   8  *
   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.
  18  *
  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
  26  * SOFTWARE.
  27  */
  28
  29 #include <config.h>
  30 #include <stdlib.h>
  31 #include <math.h>
  32 #include "pixman-private.h"
  33
  34 static void
  35 radial_gradient_get_scanline_32 (pixman_image_t *image, int x, int y, int width, uint32_t *buffer,
  36                                  const uint32_t *mask, uint32_t mask_bits)
  37 {
  38     /*
  39      * In the radial gradient problem we are given two circles (c₁,r₁) and
  40      * (c₂,r₂) that define the gradient itself. Then, for any point p, we
  41      * must compute the value(s) of t within [0.0, 1.0] representing the
  42      * circle(s) that would color the point.
  43      *
  44      * There are potentially two values of t since the point p can be
  45      * colored by both sides of the circle, (which happens whenever one
  46      * circle is not entirely contained within the other).
  47      *
  48      * If we solve for a value of t that is outside of [0.0, 1.0] then we
  49      * use the extend mode (NONE, REPEAT, REFLECT, or PAD) to map to a
  50      * value within [0.0, 1.0].
  51      *
  52      * Here is an illustration of the problem:
  53      *
  54      *              p₂
  55      *           p  •
  56      *           •   ╲
  57      *        ·       ╲r₂
  58      *  p₁ ·           ╲
  59      *  •              θ╲
  60      *   ╲             ╌╌•
  61      *    ╲r₁        ·   c₂
  62      *    θ╲    ·
  63      *    ╌╌•
  64      *      c₁
  65      *
  66      * Given (c₁,r₁), (c₂,r₂) and p, we must find an angle θ such that two
  67      * points p₁ and p₂ on the two circles are collinear with p. Then, the
  68      * desired value of t is the ratio of the length of p₁p to the length
  69      * of p₁p₂.
  70      *
  71      * So, we have six unknown values: (p₁x, p₁y), (p₂x, p₂y), θ and t.
  72      * We can also write six equations that constrain the problem:
  73      *
  74      * Point p₁ is a distance r₁ from c₁ at an angle of θ:
  75      *
  76      *  1. p₁x = c₁x + r₁·cos θ
  77      *  2. p₁y = c₁y + r₁·sin θ
  78      *
  79      * Point p₂ is a distance r₂ from c₂ at an angle of θ:
  80      *
  81      *  3. p₂x = c₂x + r2·cos θ
  82      *  4. p₂y = c₂y + r2·sin θ
  83      *
  84      * Point p lies at a fraction t along the line segment p₁p₂:
  85      *
  86      *  5. px = t·p₂x + (1-t)·p₁x
  87      *  6. py = t·p₂y + (1-t)·p₁y
  88      *
  89      * To solve, first subtitute 1-4 into 5 and 6:
  90      *
  91      * px = t·(c₂x + r₂·cos θ) + (1-t)·(c₁x + r₁·cos θ)
  92      * py = t·(c₂y + r₂·sin θ) + (1-t)·(c₁y + r₁·sin θ)
  93      *
  94      * Then solve each for cos θ and sin θ expressed as a function of t:
  95      *
  96      * cos θ = (-(c₂x - c₁x)·t + (px - c₁x)) / ((r₂-r₁)·t + r₁)
  97      * sin θ = (-(c₂y - c₁y)·t + (py - c₁y)) / ((r₂-r₁)·t + r₁)
  98      *
  99      * To simplify this a bit, we define new variables for several of the
 100      * common terms as shown below:
 101      *
 102      *              p₂
 103      *           p  •
 104      *           •   ╲
 105      *        ·  ┆    ╲r₂
 106      *  p₁ ·     ┆     ╲
 107      *  •     pdy┆      ╲
 108      *   ╲       ┆       •c₂
 109      *    ╲r₁    ┆   ·   ┆
 110      *     ╲    ·┆       ┆cdy
 111      *      •╌╌╌╌┴╌╌╌╌╌╌╌┘
 112      *    c₁  pdx   cdx
 113      *
 114      * cdx = (c₂x - c₁x)
 115      * cdy = (c₂y - c₁y)
 116      *  dr =  r₂-r₁
 117      * pdx =  px - c₁x
 118      * pdy =  py - c₁y
 119      *
 120      * Note that cdx, cdy, and dr do not depend on point p at all, so can
 121      * be pre-computed for the entire gradient. The simplifed equations
 122      * are now:
 123      *
 124      * cos θ = (-cdx·t + pdx) / (dr·t + r₁)
 125      * sin θ = (-cdy·t + pdy) / (dr·t + r₁)
 126      *
 127      * Finally, to get a single function of t and eliminate the last
 128      * unknown θ, we use the identity sin²θ + cos²θ = 1. First, square
 129      * each equation, (we knew a quadratic was coming since it must be
 130      * possible to obtain two solutions in some cases):
 131      *
 132      * cos²θ = (cdx²t² - 2·cdx·pdx·t + pdx²) / (dr²·t² + 2·r₁·dr·t + r₁²)
 133      * sin²θ = (cdy²t² - 2·cdy·pdy·t + pdy²) / (dr²·t² + 2·r₁·dr·t + r₁²)
 134      *
 135      * Then add both together, set the result equal to 1, and express as a
 136      * standard quadratic equation in t of the form At² + Bt + C = 0
 137      *
 138      * (cdx² + cdy² - dr²)·t² - 2·(cdx·pdx + cdy·pdy + r₁·dr)·t + (pdx² + pdy² - r₁²) = 0
 139      *
 140      * In other words:
 141      *
 142      * A = cdx² + cdy² - dr²
 143      * B = -2·(pdx·cdx + pdy·cdy + r₁·dr)
 144      * C = pdx² + pdy² - r₁²
 145      *
 146      * And again, notice that A does not depend on p, so can be
 147      * precomputed. From here we just use the quadratic formula to solve
 148      * for t:
 149      *
 150      * t = (-2·B ± ⎷(B² - 4·A·C)) / 2·A
 151      */
 152
 153     gradient_t *gradient = (gradient_t *)image;
 154     source_image_t *source = (source_image_t *)image;
 155     radial_gradient_t *radial = (radial_gradient_t *)image;
 156     uint32_t       *end = buffer + width;
 157     pixman_gradient_walker_t  walker;
 158     pixman_bool_t affine = TRUE;
 159     double cx = 1.;
 160     double cy = 0.;
 161     double cz = 0.;
 162     double rx = x + 0.5;
 163     double ry = y + 0.5;
 164     double rz = 1.;
 165
 166     _pixman_gradient_walker_init (&walker, gradient, source->common.repeat);
 167
 168     if (source->common.transform) {
 169         pixman_vector_t v;
 170         /* reference point is the center of the pixel */
 171         v.vector[0] = pixman_int_to_fixed(x) + pixman_fixed_1/2;
 172         v.vector[1] = pixman_int_to_fixed(y) + pixman_fixed_1/2;
 173         v.vector[2] = pixman_fixed_1;
 174         if (!pixman_transform_point_3d (source->common.transform, &v))
 175             return;
 176
 177         cx = source->common.transform->matrix[0][0]/65536.;
 178         cy = source->common.transform->matrix[1][0]/65536.;
 179         cz = source->common.transform->matrix[2][0]/65536.;
 180         rx = v.vector[0]/65536.;
 181         ry = v.vector[1]/65536.;
 182         rz = v.vector[2]/65536.;
 183         affine = source->common.transform->matrix[2][0] == 0 && v.vector[2] == pixman_fixed_1;
 184     }
 185
 186     if (affine) {
 187         while (buffer < end) {
 188             if (!mask || *mask++ & mask_bits)
 189             {
 190                 double pdx, pdy;
 191                 double B, C;
 192                 double det;
 193                 double c1x = radial->c1.x / 65536.0;
 194                 double c1y = radial->c1.y / 65536.0;
 195                 double r1  = radial->c1.radius / 65536.0;
 196                 pixman_fixed_48_16_t t;
 197
 198                 pdx = rx - c1x;
 199                 pdy = ry - c1y;
 200
 201                 B = -2 * (  pdx * radial->cdx
 202                             + pdy * radial->cdy
 203                             + r1 * radial->dr);
 204                 C = (pdx * pdx + pdy * pdy - r1 * r1);
 205
 206                 det = (B * B) - (4 * radial->A * C);
 207                 if (det < 0.0)
 208                     det = 0.0;
 209
 210                 if (radial->A < 0)
 211                     t = (pixman_fixed_48_16_t) ((- B - sqrt(det)) / (2.0 * radial->A) * 65536);
 212                 else
 213                     t = (pixman_fixed_48_16_t) ((- B + sqrt(det)) / (2.0 * radial->A) * 65536);
 214
 215                 *(buffer) = _pixman_gradient_walker_pixel (&walker, t);
 216             }
 217             ++buffer;
 218
 219             rx += cx;
 220             ry += cy;
 221         }
 222     } else {
 223         /* projective */
 224         while (buffer < end) {
 225             if (!mask || *mask++ & mask_bits)
 226             {
 227                 double pdx, pdy;
 228                 double B, C;
 229                 double det;
 230                 double c1x = radial->c1.x / 65536.0;
 231                 double c1y = radial->c1.y / 65536.0;
 232                 double r1  = radial->c1.radius / 65536.0;
 233                 pixman_fixed_48_16_t t;
 234                 double x, y;
 235
 236                 if (rz != 0) {
 237                     x = rx/rz;
 238                     y = ry/rz;
 239                 } else {
 240                     x = y = 0.;
 241                 }
 242
 243                 pdx = x - c1x;
 244                 pdy = y - c1y;
 245
 246                 B = -2 * (  pdx * radial->cdx
 247                             + pdy * radial->cdy
 248                             + r1 * radial->dr);
 249                 C = (pdx * pdx + pdy * pdy - r1 * r1);
 250
 251                 det = (B * B) - (4 * radial->A * C);
 252                 if (det < 0.0)
 253                     det = 0.0;
 254
 255                 if (radial->A < 0)
 256                     t = (pixman_fixed_48_16_t) ((- B - sqrt(det)) / (2.0 * radial->A) * 65536);
 257                 else
 258                     t = (pixman_fixed_48_16_t) ((- B + sqrt(det)) / (2.0 * radial->A) * 65536);
 259
 260                 *(buffer) = _pixman_gradient_walker_pixel (&walker, t);
 261             }
 262             ++buffer;
 263
 264             rx += cx;
 265             ry += cy;
 266             rz += cz;
 267         }
 268     }
 269
 270 }
 271
 272 static void
 273 radial_gradient_property_changed (pixman_image_t *image)
 274 {
 275     image->common.get_scanline_32 = radial_gradient_get_scanline_32;
 276     image->common.get_scanline_64 = _pixman_image_get_scanline_generic_64;
 277 }
 278
 279 PIXMAN_EXPORT pixman_image_t *
 280 pixman_image_create_radial_gradient (pixman_point_fixed_t         *inner,
 281                                      pixman_point_fixed_t         *outer,
 282                                      pixman_fixed_t                inner_radius,
 283                                      pixman_fixed_t                outer_radius,
 284                                      const pixman_gradient_stop_t *stops,
 285                                      int                           n_stops)
 286 {
 287     pixman_image_t *image;
 288     radial_gradient_t *radial;
 289
 290     return_val_if_fail (n_stops >= 2, NULL);
 291
 292     image = _pixman_image_allocate();
 293
 294     if (!image)
 295         return NULL;
 296
 297     radial = &image->radial;
 298
 299     if (!_pixman_init_gradient (&radial->common, stops, n_stops))
 300     {
 301         free (image);
 302         return NULL;
 303     }
 304
 305     image->type = RADIAL;
 306
 307     radial->c1.x = inner->x;
 308     radial->c1.y = inner->y;
 309     radial->c1.radius = inner_radius;
 310     radial->c2.x = outer->x;
 311     radial->c2.y = outer->y;
 312     radial->c2.radius = outer_radius;
 313     radial->cdx = pixman_fixed_to_double (radial->c2.x - radial->c1.x);
 314     radial->cdy = pixman_fixed_to_double (radial->c2.y - radial->c1.y);
 315     radial->dr = pixman_fixed_to_double (radial->c2.radius - radial->c1.radius);
 316     radial->A = (radial->cdx * radial->cdx
 317                  + radial->cdy * radial->cdy
 318                  - radial->dr  * radial->dr);
 319
 320     image->common.property_changed = radial_gradient_property_changed;
 321
 322     radial_gradient_property_changed (image);
 323
 324     return image;
 325 }
 326