pixman/pixman-source.c

   1 /*
   2  *
   3  * Copyright © 2000 Keith Packard, member of The XFree86 Project, Inc.
   4  *             2005 Lars Knoll & Zack Rusin, Trolltech
   5  *
   6  * Permission to use, copy, modify, distribute, and sell this software and its
   7  * documentation for any purpose is hereby granted without fee, provided that
   8  * the above copyright notice appear in all copies and that both that
   9  * copyright notice and this permission notice appear in supporting
  10  * documentation, and that the name of Keith Packard not be used in
  11  * advertising or publicity pertaining to distribution of the software without
  12  * specific, written prior permission.  Keith Packard makes no
  13  * representations about the suitability of this software for any purpose.  It
  14  * is provided "as is" without express or implied warranty.
  15  *
  16  * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS
  17  * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  18  * FITNESS, IN NO EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY
  19  * SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  20  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
  21  * AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
  22  * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  23  * SOFTWARE.
  24  */
  25
  26 #ifdef HAVE_CONFIG_H
  27 #include <config.h>
  28 #endif
  29
  30 #include <stdlib.h>
  31 #include <math.h>
  32
  33 #include "pixman-private.h"
  34
  35 void
  36 pixmanFetchGradient(gradient_t *gradient, int x, int y, int width,
  37                     uint32_t *buffer, uint32_t *mask, uint32_t maskBits)
  38 {
  39     GradientWalker  walker;
  40     uint32_t       *end = buffer + width;
  41     source_image_t *pict;
  42
  43     pict = (source_image_t *)gradient;
  44
  45     _pixman_gradient_walker_init (&walker, gradient, pict->common.repeat);
  46
  47     if (pict->common.type == LINEAR) {
  48         assert (0);
  49     } else {
  50 /*
  51  * In the radial gradient problem we are given two circles (c₁,r₁) and
  52  * (c₂,r₂) that define the gradient itself. Then, for any point p, we
  53  * must compute the value(s) of t within [0.0, 1.0] representing the
  54  * circle(s) that would color the point.
  55  *
  56  * There are potentially two values of t since the point p can be
  57  * colored by both sides of the circle, (which happens whenever one
  58  * circle is not entirely contained within the other).
  59  *
  60  * If we solve for a value of t that is outside of [0.0, 1.0] then we
  61  * use the extend mode (NONE, REPEAT, REFLECT, or PAD) to map to a
  62  * value within [0.0, 1.0].
  63  *
  64  * Here is an illustration of the problem:
  65  *
  66  *              p₂
  67  *           p  •
  68  *           •   ╲
  69  *        ·       ╲r₂
  70  *  p₁ ·           ╲
  71  *  •              θ╲
  72  *   ╲             ╌╌•
  73  *    ╲r₁        ·   c₂
  74  *    θ╲    ·
  75  *    ╌╌•
  76  *      c₁
  77  *
  78  * Given (c₁,r₁), (c₂,r₂) and p, we must find an angle θ such that two
  79  * points p₁ and p₂ on the two circles are collinear with p. Then, the
  80  * desired value of t is the ratio of the length of p₁p to the length
  81  * of p₁p₂.
  82  *
  83  * So, we have six unknown values: (p₁x, p₁y), (p₂x, p₂y), θ and t.
  84  * We can also write six equations that constrain the problem:
  85  *
  86  * Point p₁ is a distance r₁ from c₁ at an angle of θ:
  87  *
  88  *      1. p₁x = c₁x + r₁·cos θ
  89  *      2. p₁y = c₁y + r₁·sin θ
  90  *
  91  * Point p₂ is a distance r₂ from c₂ at an angle of θ:
  92  *
  93  *      3. p₂x = c₂x + r2·cos θ
  94  *      4. p₂y = c₂y + r2·sin θ
  95  *
  96  * Point p lies at a fraction t along the line segment p₁p₂:
  97  *
  98  *      5. px = t·p₂x + (1-t)·p₁x
  99  *      6. py = t·p₂y + (1-t)·p₁y
 100  *
 101  * To solve, first subtitute 1-4 into 5 and 6:
 102  *
 103  * px = t·(c₂x + r₂·cos θ) + (1-t)·(c₁x + r₁·cos θ)
 104  * py = t·(c₂y + r₂·sin θ) + (1-t)·(c₁y + r₁·sin θ)
 105  *
 106  * Then solve each for cos θ and sin θ expressed as a function of t:
 107  *
 108  * cos θ = (-(c₂x - c₁x)·t + (px - c₁x)) / ((r₂-r₁)·t + r₁)
 109  * sin θ = (-(c₂y - c₁y)·t + (py - c₁y)) / ((r₂-r₁)·t + r₁)
 110  *
 111  * To simplify this a bit, we define new variables for several of the
 112  * common terms as shown below:
 113  *
 114  *              p₂
 115  *           p  •
 116  *           •   ╲
 117  *        ·  ┆    ╲r₂
 118  *  p₁ ·     ┆     ╲
 119  *  •     pdy┆      ╲
 120  *   ╲       ┆       •c₂
 121  *    ╲r₁    ┆   ·   ┆
 122  *     ╲    ·┆       ┆cdy
 123  *      •╌╌╌╌┴╌╌╌╌╌╌╌┘
 124  *    c₁  pdx   cdx
 125  *
 126  * cdx = (c₂x - c₁x)
 127  * cdy = (c₂y - c₁y)
 128  *  dr =  r₂-r₁
 129  * pdx =  px - c₁x
 130  * pdy =  py - c₁y
 131  *
 132  * Note that cdx, cdy, and dr do not depend on point p at all, so can
 133  * be pre-computed for the entire gradient. The simplifed equations
 134  * are now:
 135  *
 136  * cos θ = (-cdx·t + pdx) / (dr·t + r₁)
 137  * sin θ = (-cdy·t + pdy) / (dr·t + r₁)
 138  *
 139  * Finally, to get a single function of t and eliminate the last
 140  * unknown θ, we use the identity sin²θ + cos²θ = 1. First, square
 141  * each equation, (we knew a quadratic was coming since it must be
 142  * possible to obtain two solutions in some cases):
 143  *
 144  * cos²θ = (cdx²t² - 2·cdx·pdx·t + pdx²) / (dr²·t² + 2·r₁·dr·t + r₁²)
 145  * sin²θ = (cdy²t² - 2·cdy·pdy·t + pdy²) / (dr²·t² + 2·r₁·dr·t + r₁²)
 146  *
 147  * Then add both together, set the result equal to 1, and express as a
 148  * standard quadratic equation in t of the form At² + Bt + C = 0
 149  *
 150  * (cdx² + cdy² - dr²)·t² - 2·(cdx·pdx + cdy·pdy + r₁·dr)·t + (pdx² + pdy² - r₁²) = 0
 151  *
 152  * In other words:
 153  *
 154  * A = cdx² + cdy² - dr²
 155  * B = -2·(pdx·cdx + pdy·cdy + r₁·dr)
 156  * C = pdx² + pdy² - r₁²
 157  *
 158  * And again, notice that A does not depend on p, so can be
 159  * precomputed. From here we just use the quadratic formula to solve
 160  * for t:
 161  *
 162  * t = (-2·B ± ⎷(B² - 4·A·C)) / 2·A
 163  */
 164         if (pict->common.type == RADIAL) {
 165             /* radial or conical */
 166             pixman_bool_t affine = TRUE;
 167             double cx = 1.;
 168             double cy = 0.;
 169             double cz = 0.;
 170             double rx = x + 0.5;
 171             double ry = y + 0.5;
 172             double rz = 1.;
 173
 174             if (pict->common.transform) {
 175                 pixman_vector_t v;
 176                 /* reference point is the center of the pixel */
 177                 v.vector[0] = pixman_int_to_fixed(x) + pixman_fixed_1/2;
 178                 v.vector[1] = pixman_int_to_fixed(y) + pixman_fixed_1/2;
 179                 v.vector[2] = pixman_fixed_1;
 180                 if (!pixman_transform_point_3d (pict->common.transform, &v))
 181                     return;
 182
 183                 cx = pict->common.transform->matrix[0][0]/65536.;
 184                 cy = pict->common.transform->matrix[1][0]/65536.;
 185                 cz = pict->common.transform->matrix[2][0]/65536.;
 186                 rx = v.vector[0]/65536.;
 187                 ry = v.vector[1]/65536.;
 188                 rz = v.vector[2]/65536.;
 189                 affine = pict->common.transform->matrix[2][0] == 0 && v.vector[2] == pixman_fixed_1;
 190             }
 191
 192             radial_gradient_t *radial = (radial_gradient_t *)pict;
 193             if (affine) {
 194                 while (buffer < end) {
 195                     if (!mask || *mask++ & maskBits)
 196                     {
 197                         double pdx, pdy;
 198                         double B, C;
 199                         double det;
 200                         double c1x = radial->c1.x / 65536.0;
 201                         double c1y = radial->c1.y / 65536.0;
 202                         double r1  = radial->c1.radius / 65536.0;
 203                         pixman_fixed_48_16_t t;
 204
 205                         pdx = rx - c1x;
 206                         pdy = ry - c1y;
 207
 208                         B = -2 * (  pdx * radial->cdx
 209                                     + pdy * radial->cdy
 210                                     + r1 * radial->dr);
 211                         C = (pdx * pdx + pdy * pdy - r1 * r1);
 212
 213                         det = (B * B) - (4 * radial->A * C);
 214                         if (det < 0.0)
 215                             det = 0.0;
 216
 217                         if (radial->A < 0)
 218                             t = (pixman_fixed_48_16_t) ((- B - sqrt(det)) / (2.0 * radial->A) * 65536);
 219                         else
 220                             t = (pixman_fixed_48_16_t) ((- B + sqrt(det)) / (2.0 * radial->A) * 65536);
 221
 222                         *(buffer) = _pixman_gradient_walker_pixel (&walker, t);
 223                     }
 224                     ++buffer;
 225
 226                     rx += cx;
 227                     ry += cy;
 228                 }
 229             } else {
 230                 /* projective */
 231                 while (buffer < end) {
 232                     if (!mask || *mask++ & maskBits)
 233                     {
 234                         double pdx, pdy;
 235                         double B, C;
 236                         double det;
 237                         double c1x = radial->c1.x / 65536.0;
 238                         double c1y = radial->c1.y / 65536.0;
 239                         double r1  = radial->c1.radius / 65536.0;
 240                         pixman_fixed_48_16_t t;
 241                         double x, y;
 242
 243                         if (rz != 0) {
 244                             x = rx/rz;
 245                             y = ry/rz;
 246                         } else {
 247                             x = y = 0.;
 248                         }
 249
 250                         pdx = x - c1x;
 251                         pdy = y - c1y;
 252
 253                         B = -2 * (  pdx * radial->cdx
 254                                     + pdy * radial->cdy
 255                                     + r1 * radial->dr);
 256                         C = (pdx * pdx + pdy * pdy - r1 * r1);
 257
 258                         det = (B * B) - (4 * radial->A * C);
 259                         if (det < 0.0)
 260                             det = 0.0;
 261
 262                         if (radial->A < 0)
 263                             t = (pixman_fixed_48_16_t) ((- B - sqrt(det)) / (2.0 * radial->A) * 65536);
 264                         else
 265                             t = (pixman_fixed_48_16_t) ((- B + sqrt(det)) / (2.0 * radial->A) * 65536);
 266
 267                         *(buffer) = _pixman_gradient_walker_pixel (&walker, t);
 268                     }
 269                     ++buffer;
 270
 271                     rx += cx;
 272                     ry += cy;
 273                     rz += cz;
 274                 }
 275             }
 276         } else /* SourcePictTypeConical */ {
 277             /* radial or conical */
 278             pixman_bool_t affine = TRUE;
 279             double cx = 1.;
 280             double cy = 0.;
 281             double cz = 0.;
 282             double rx = x + 0.5;
 283             double ry = y + 0.5;
 284             double rz = 1.;
 285
 286             if (pict->common.transform) {
 287                 pixman_vector_t v;
 288                 /* reference point is the center of the pixel */
 289                 v.vector[0] = pixman_int_to_fixed(x) + pixman_fixed_1/2;
 290                 v.vector[1] = pixman_int_to_fixed(y) + pixman_fixed_1/2;
 291                 v.vector[2] = pixman_fixed_1;
 292                 if (!pixman_transform_point_3d (pict->common.transform, &v))
 293                     return;
 294
 295                 cx = pict->common.transform->matrix[0][0]/65536.;
 296                 cy = pict->common.transform->matrix[1][0]/65536.;
 297                 cz = pict->common.transform->matrix[2][0]/65536.;
 298                 rx = v.vector[0]/65536.;
 299                 ry = v.vector[1]/65536.;
 300                 rz = v.vector[2]/65536.;
 301                 affine = pict->common.transform->matrix[2][0] == 0 && v.vector[2] == pixman_fixed_1;
 302             }
 303
 304             conical_gradient_t *conical = (conical_gradient_t *)pict;
 305             double a = conical->angle/(180.*65536);
 306             if (affine) {
 307                 rx -= conical->center.x/65536.;
 308                 ry -= conical->center.y/65536.;
 309
 310                 while (buffer < end) {
 311                     double angle;
 312
 313                     if (!mask || *mask++ & maskBits)
 314                     {
 315                         pixman_fixed_48_16_t   t;
 316
 317                         angle = atan2(ry, rx) + a;
 318                         t     = (pixman_fixed_48_16_t) (angle * (65536. / (2*M_PI)));
 319
 320                         *(buffer) = _pixman_gradient_walker_pixel (&walker, t);
 321                     }
 322
 323                     ++buffer;
 324                     rx += cx;
 325                     ry += cy;
 326                 }
 327             } else {
 328                 while (buffer < end) {
 329                     double x, y;
 330                     double angle;
 331
 332                     if (!mask || *mask++ & maskBits)
 333                     {
 334                         pixman_fixed_48_16_t  t;
 335
 336                         if (rz != 0) {
 337                             x = rx/rz;
 338                             y = ry/rz;
 339                         } else {
 340                             x = y = 0.;
 341                         }
 342                         x -= conical->center.x/65536.;
 343                         y -= conical->center.y/65536.;
 344                         angle = atan2(y, x) + a;
 345                         t     = (pixman_fixed_48_16_t) (angle * (65536. / (2*M_PI)));
 346
 347                         *(buffer) = _pixman_gradient_walker_pixel (&walker, t);
 348                     }
 349
 350                     ++buffer;
 351                     rx += cx;
 352                     ry += cy;
 353                     rz += cz;
 354                 }
 355             }
 356         }
 357     }
 358 }