pixman/pixman-radial-gradient.c

   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
  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     return x1 * x2 + y1 * y2 + z1 * z2;
  46 }
  47
  48 static inline double
  49 fdot (double x1,
  50       double y1,
  51       double z1,
  52       double x2,
  53       double y2,
  54       double z2)
  55 {
  56     return x1 * x2 + y1 * y2 + z1 * z2;
  57 }
  58
  59 static uint32_t
  60 radial_compute_color (double                    a,
  61                       double                    b,
  62                       double                    c,
  63                       double                    inva,
  64                       double                    dr,
  65                       double                    mindr,
  66                       pixman_gradient_walker_t *walker,
  67                       pixman_repeat_t           repeat)
  68 {
  69     double det;
  70
  71     if (a == 0)
  72     {
  73         return _pixman_gradient_walker_pixel (walker,
  74                                               pixman_fixed_1 / 2 * c / b);
  75     }
  76
  77     det = fdot (b, a, 0, b, -c, 0);
  78     if (det >= 0)
  79     {
  80         double sqrtdet, t0, t1;
  81
  82         sqrtdet = sqrt (det);
  83         t0 = (b + sqrtdet) * inva;
  84         t1 = (b - sqrtdet) * inva;
  85
  86         if (repeat == PIXMAN_REPEAT_NONE)
  87         {
  88             if (0 <= t0 && t0 <= pixman_fixed_1)
  89                 return _pixman_gradient_walker_pixel (walker, t0);
  90             else if (0 <= t1 && t1 <= pixman_fixed_1)
  91                 return _pixman_gradient_walker_pixel (walker, t1);
  92         }
  93         else
  94         {
  95             if (t0 * dr > mindr)
  96                 return _pixman_gradient_walker_pixel (walker, t0);
  97             else if (t1 * dr > mindr)
  98                 return _pixman_gradient_walker_pixel (walker, t1);
  99         }
 100     }
 101
 102     return 0;
 103 }
 104
 105 static void
 106 radial_gradient_get_scanline_32 (pixman_image_t *image,
 107                                  int             x,
 108                                  int             y,
 109                                  int             width,
 110                                  uint32_t *      buffer,
 111                                  const uint32_t *mask)
 112 {
 113     /*
 114      * Implementation of radial gradients following the PDF specification.
 115      * See section 8.7.4.5.4 Type 3 (Radial) Shadings of the PDF Reference
 116      * Manual (PDF 32000-1:2008 at the time of this writing).
 117      *
 118      * In the radial gradient problem we are given two circles (c₁,r₁) and
 119      * (c₂,r₂) that define the gradient itself.
 120      *
 121      * Mathematically the gradient can be defined as the family of circles
 122      *
 123      *     ((1-t)·c₁ + t·(c₂), (1-t)·r₁ + t·r₂)
 124      *
 125      * excluding those circles whose radius would be < 0. When a point
 126      * belongs to more than one circle, the one with a bigger t is the only
 127      * one that contributes to its color. When a point does not belong
 128      * to any of the circles, it is transparent black, i.e. RGBA (0, 0, 0, 0).
 129      * Further limitations on the range of values for t are imposed when
 130      * the gradient is not repeated, namely t must belong to [0,1].
 131      *
 132      * The graphical result is the same as drawing the valid (radius > 0)
 133      * circles with increasing t in [-inf, +inf] (or in [0,1] if the gradient
 134      * is not repeated) using SOURCE operatior composition.
 135      *
 136      * It looks like a cone pointing towards the viewer if the ending circle
 137      * is smaller than the starting one, a cone pointing inside the page if
 138      * the starting circle is the smaller one and like a cylinder if they
 139      * have the same radius.
 140      *
 141      * What we actually do is, given the point whose color we are interested
 142      * in, compute the t values for that point, solving for t in:
 143      *
 144      *     length((1-t)·c₁ + t·(c₂) - p) = (1-t)·r₁ + t·r₂
 145      *
 146      * Let's rewrite it in a simpler way, by defining some auxiliary
 147      * variables:
 148      *
 149      *     cd = c₂ - c₁
 150      *     pd = p - c₁
 151      *     dr = r₂ - r₁
 152      *     lenght(t·cd - pd) = r₁ + t·dr
 153      *
 154      * which actually means
 155      *
 156      *     hypot(t·cdx - pdx, t·cdy - pdy) = r₁ + t·dr
 157      *
 158      * or
 159      *
 160      *     ⎷((t·cdx - pdx)² + (t·cdy - pdy)²) = r₁ + t·dr.
 161      *
 162      * If we impose (as stated earlier) that r₁ + t·dr >= 0, it becomes:
 163      *
 164      *     (t·cdx - pdx)² + (t·cdy - pdy)² = (r₁ + t·dr)²
 165      *
 166      * where we can actually expand the squares and solve for t:
 167      *
 168      *     t²cdx² - 2t·cdx·pdx + pdx² + t²cdy² - 2t·cdy·pdy + pdy² =
 169      *       = r₁² + 2·r₁·t·dr + t²·dr²
 170      *
 171      *     (cdx² + cdy² - dr²)t² - 2(cdx·pdx + cdy·pdy + r₁·dr)t +
 172      *         (pdx² + pdy² - r₁²) = 0
 173      *
 174      *     A = cdx² + cdy² - dr²
 175      *     B = pdx·cdx + pdy·cdy + r₁·dr
 176      *     C = pdx² + pdy² - r₁²
 177      *     At² - 2Bt + C = 0
 178      *
 179      * The solutions (unless the equation degenerates because of A = 0) are:
 180      *
 181      *     t = (B ± ⎷(B² - A·C)) / A
 182      *
 183      * The solution we are going to prefer is the bigger one, unless the
 184      * radius associated to it is negative (or it falls outside the valid t
 185      * range).
 186      *
 187      * Additional observations (useful for optimizations):
 188      * A does not depend on p
 189      *
 190      * A < 0 <=> one of the two circles completely contains the other one
 191      *   <=> for every p, the radiuses associated with the two t solutions
 192      *       have opposite sign
 193      */
 194
 195     gradient_t *gradient = (gradient_t *)image;
 196     source_image_t *source = (source_image_t *)image;
 197     radial_gradient_t *radial = (radial_gradient_t *)image;
 198     uint32_t *end = buffer + width;
 199     pixman_gradient_walker_t walker;
 200     pixman_vector_t v, unit;
 201
 202     /* reference point is the center of the pixel */
 203     v.vector[0] = pixman_int_to_fixed (x) + pixman_fixed_1 / 2;
 204     v.vector[1] = pixman_int_to_fixed (y) + pixman_fixed_1 / 2;
 205     v.vector[2] = pixman_fixed_1;
 206
 207     _pixman_gradient_walker_init (&walker, gradient, source->common.repeat);
 208
 209     if (source->common.transform)
 210     {
 211         if (!pixman_transform_point_3d (source->common.transform, &v))
 212             return;
 213
 214         unit.vector[0] = source->common.transform->matrix[0][0];
 215         unit.vector[1] = source->common.transform->matrix[1][0];
 216         unit.vector[2] = source->common.transform->matrix[2][0];
 217     }
 218     else
 219     {
 220         unit.vector[0] = pixman_fixed_1;
 221         unit.vector[1] = 0;
 222         unit.vector[2] = 0;
 223     }
 224
 225     if (unit.vector[2] == 0 && v.vector[2] == pixman_fixed_1)
 226     {
 227         /*
 228          * Given:
 229          *
 230          * t = (B ± ⎷(B² - A·C)) / A
 231          *
 232          * where
 233          *
 234          * A = cdx² + cdy² - dr²
 235          * B = pdx·cdx + pdy·cdy + r₁·dr
 236          * C = pdx² + pdy² - r₁²
 237          * det = B² - A·C
 238          *
 239          * Since we have an affine transformation, we know that (pdx, pdy)
 240          * increase linearly with each pixel,
 241          *
 242          * pdx = pdx₀ + n·ux,
 243          * pdy = pdy₀ + n·uy,
 244          *
 245          * we can then express B, C and det through multiple differentiation.
 246          */
 247         pixman_fixed_32_32_t b, db, c, dc, ddc;
 248
 249         v.vector[0] -= radial->c1.x;
 250         v.vector[1] -= radial->c1.y;
 251
 252         b = dot (v.vector[0], v.vector[1], radial->c1.radius,
 253                  radial->delta.x, radial->delta.y, radial->delta.radius);
 254         db = dot (unit.vector[0], unit.vector[1], 0,
 255                   radial->delta.x, radial->delta.y, 0);
 256
 257         c = dot (v.vector[0], v.vector[1], -radial->c1.radius,
 258                  v.vector[0], v.vector[1], radial->c1.radius);
 259         dc = dot (2 * v.vector[0] + unit.vector[0],
 260                   2 * v.vector[1] + unit.vector[1],
 261                   0,
 262                   unit.vector[0], unit.vector[1], 0);
 263         ddc = 2 * dot (unit.vector[0], unit.vector[1], 0,
 264                        unit.vector[0], unit.vector[1], 0);
 265
 266         while (buffer < end)
 267         {
 268             if (!mask || *mask++)
 269             {
 270                 *buffer = radial_compute_color (radial->a, b, c,
 271                                                 radial->inva,
 272                                                 radial->delta.radius,
 273                                                 radial->mindr,
 274                                                 &walker,
 275                                                 source->common.repeat);
 276             }
 277
 278             b += db;
 279             c += dc;
 280             dc += ddc;
 281             ++buffer;
 282         }
 283     }
 284     else
 285     {
 286         /* projective */
 287         while (buffer < end)
 288         {
 289             if (!mask || *mask++)
 290             {
 291                 if (v.vector[2] != 0)
 292                 {
 293                     double pdx, pdy, invv2, b, c;
 294
 295                     invv2 = 1. * pixman_fixed_1 / v.vector[2];
 296
 297                     pdx = v.vector[0] * invv2 - radial->c1.x;
 298                     /*    / pixman_fixed_1 */
 299
 300                     pdy = v.vector[1] * invv2 - radial->c1.y;
 301                     /*    / pixman_fixed_1 */
 302
 303                     b = fdot (pdx, pdy, radial->c1.radius,
 304                               radial->delta.x, radial->delta.y,
 305                               radial->delta.radius);
 306                     /*  / pixman_fixed_1 / pixman_fixed_1 */
 307
 308                     c = fdot (pdx, pdy, -radial->c1.radius,
 309                               pdx, pdy, radial->c1.radius);
 310                     /*  / pixman_fixed_1 / pixman_fixed_1 */
 311
 312                     *buffer = radial_compute_color (radial->a, b, c,
 313                                                     radial->inva,
 314                                                     radial->delta.radius,
 315                                                     radial->mindr,
 316                                                     &walker,
 317                                                     source->common.repeat);
 318                 }
 319                 else
 320                 {
 321                     *buffer = 0;
 322                 }
 323             }
 324
 325             ++buffer;
 326
 327             v.vector[0] += unit.vector[0];
 328             v.vector[1] += unit.vector[1];
 329             v.vector[2] += unit.vector[2];
 330         }
 331     }
 332 }
 333
 334 static void
 335 radial_gradient_property_changed (pixman_image_t *image)
 336 {
 337     image->common.get_scanline_32 = radial_gradient_get_scanline_32;
 338     image->common.get_scanline_64 = _pixman_image_get_scanline_generic_64;
 339 }
 340
 341 PIXMAN_EXPORT pixman_image_t *
 342 pixman_image_create_radial_gradient (pixman_point_fixed_t *        inner,
 343                                      pixman_point_fixed_t *        outer,
 344                                      pixman_fixed_t                inner_radius,
 345                                      pixman_fixed_t                outer_radius,
 346                                      const pixman_gradient_stop_t *stops,
 347                                      int                           n_stops)
 348 {
 349     pixman_image_t *image;
 350     radial_gradient_t *radial;
 351
 352     image = _pixman_image_allocate ();
 353
 354     if (!image)
 355         return NULL;
 356
 357     radial = &image->radial;
 358
 359     if (!_pixman_init_gradient (&radial->common, stops, n_stops))
 360     {
 361         free (image);
 362         return NULL;
 363     }
 364
 365     image->type = RADIAL;
 366
 367     radial->c1.x = inner->x;
 368     radial->c1.y = inner->y;
 369     radial->c1.radius = inner_radius;
 370     radial->c2.x = outer->x;
 371     radial->c2.y = outer->y;
 372     radial->c2.radius = outer_radius;
 373
 374     radial->delta.x = radial->c2.x - radial->c1.x;
 375     radial->delta.y = radial->c2.y - radial->c1.y;
 376     radial->delta.radius = radial->c2.radius - radial->c1.radius;
 377
 378     radial->a = dot (radial->delta.x, radial->delta.y, -radial->delta.radius,
 379                      radial->delta.x, radial->delta.y, radial->delta.radius);
 380     if (radial->a != 0)
 381         radial->inva = 1. * pixman_fixed_1 / radial->a;
 382
 383     radial->mindr = -1. * pixman_fixed_1 * radial->c1.radius;
 384
 385     image->common.property_changed = radial_gradient_property_changed;
 386
 387     return image;
 388 }
 389