pixman: Changes to 'upstream-experimental'
.gitignore | 2
CODING_STYLE | 23
README | 10
configure.ac | 274 ++++++--
pixman/Makefile.am | 5
pixman/pixman-access.c | 309 +++++----
pixman/pixman-arm-neon-asm.S | 336 ++++++++--
pixman/pixman-arm-neon-asm.h | 59 +
pixman/pixman-arm-neon.c | 30
pixman/pixman-arm-simd-asm.S | 2
pixman/pixman-arm-simd.c | 16
pixman/pixman-bits-image.c | 644 ++++++++++++++-----
pixman/pixman-combine.c.template | 45 -
pixman/pixman-combine.h.template | 152 ++--
pixman/pixman-compiler.h | 39 -
pixman/pixman-conical-gradient.c | 60 +
pixman/pixman-cpu.c | 25
pixman/pixman-fast-path.c | 470 ++++----------
pixman/pixman-fast-path.h | 445 +++++++++++++
pixman/pixman-general.c | 65 -
pixman/pixman-image.c | 146 +++-
pixman/pixman-linear-gradient.c | 200 ++---
pixman/pixman-mmx.c | 110 +--
pixman/pixman-private.h | 136 ++--
pixman/pixman-radial-gradient.c | 464 +++++++------
pixman/pixman-region.c | 60 +
pixman/pixman-region16.c | 4
pixman/pixman-region32.c | 4
pixman/pixman-solid-fill.c | 9
pixman/pixman-sse2.c | 1302 ++++++++++++++++++++-------------------
pixman/pixman.c | 757 ++++++++++++----------
pixman/pixman.h | 16
test/Makefile.am | 35 -
test/affine-test.c | 261 +++++++
test/alpha-loop.c | 29
test/alphamap.c | 257 ++++++-
test/blitters-test-bisect.rb | 43 -
test/blitters-test.c | 167 ++---
test/composite-test.c | 5
test/composite.c | 260 ++++---
test/fuzzer-find-diff.pl | 68 ++
test/gradient-crash-test.c | 117 +++
test/gtk-utils.c | 2
test/lowlevel-blt-bench.c | 712 +++++++++++++++++++++
test/region-translate-test.c | 30
test/scaling-crash-test.c | 209 ++++++
test/scaling-test-bisect.rb | 38 -
test/scaling-test.c | 95 --
test/utils.c | 279 ++++++++
test/utils.h | 77 ++
50 files changed, 6104 insertions(+), 2799 deletions(-)
New commits:
commit d1051340155a099a523e71377b1d889eec8b972e
Author: Søren Sandmann Pedersen <ssp@redhat.com>
Date: Wed Oct 20 16:25:55 2010 -0400
Pre-release version bump to 0.19.6
diff --git a/configure.ac b/configure.ac
index fc08def..4bd20fd 100644
--- a/configure.ac
+++ b/configure.ac
@@ -54,7 +54,7 @@ AC_PREREQ([2.57])
m4_define([pixman_major], 0)
m4_define([pixman_minor], 19)
-m4_define([pixman_micro], 5)
+m4_define([pixman_micro], 6)
m4_define([pixman_version],[pixman_major.pixman_minor.pixman_micro])
commit a966cd04c16ad0c34b0f17e9021a4f3532575ca4
Author: Andrea Canciani <ranma42@gmail.com>
Date: Tue Oct 12 15:38:20 2010 +0200
Fix an overflow in the new radial gradient code
huge-radial in the cairo test suite pointed out an undocumented
overflow in the radial gradient code.
By casting to pixman_fixed_48_16_t before doing the operations,
the overflow can be avoided.
diff --git a/pixman/pixman-radial-gradient.c b/pixman/pixman-radial-gradient.c
index ed073ab..f0dcc96 100644
--- a/pixman/pixman-radial-gradient.c
+++ b/pixman/pixman-radial-gradient.c
@@ -290,10 +290,11 @@ radial_gradient_get_scanline_32 (pixman_image_t *image,
db = dot (unit.vector[0], unit.vector[1], 0,
radial->delta.x, radial->delta.y, 0);
- c = dot (v.vector[0], v.vector[1], -radial->c1.radius,
+ c = dot (v.vector[0], v.vector[1],
+ -((pixman_fixed_48_16_t) radial->c1.radius),
v.vector[0], v.vector[1], radial->c1.radius);
- dc = dot (2 * v.vector[0] + unit.vector[0],
- 2 * v.vector[1] + unit.vector[1],
+ dc = dot (2 * (pixman_fixed_48_16_t) v.vector[0] + unit.vector[0],
+ 2 * (pixman_fixed_48_16_t) v.vector[1] + unit.vector[1],
0,
unit.vector[0], unit.vector[1], 0);
ddc = 2 * dot (unit.vector[0], unit.vector[1], 0,
commit 70658f0a6bd451a21fbb43df7865a7dac95abe24
Author: Søren Sandmann Pedersen <ssp@redhat.com>
Date: Wed Oct 20 16:09:44 2010 -0400
Remove the class field from source_image_t
The linear gradient was the only image type that relied on the class
being stored in the image struct itself. With the previous changes, it
doesn't need that anymore, so we can delete the field.
diff --git a/pixman/pixman-image.c b/pixman/pixman-image.c
index 7a9c423..fabcd63 100644
--- a/pixman/pixman-image.c
+++ b/pixman/pixman-image.c
@@ -48,7 +48,6 @@ _pixman_init_gradient (gradient_t * gradient,
gradient->n_stops = n_stops;
gradient->stop_range = 0xffff;
- gradient->common.class = SOURCE_IMAGE_CLASS_UNKNOWN;
return TRUE;
}
diff --git a/pixman/pixman-linear-gradient.c b/pixman/pixman-linear-gradient.c
index c6ac980..b048e7b 100644
--- a/pixman/pixman-linear-gradient.c
+++ b/pixman/pixman-linear-gradient.c
@@ -44,8 +44,9 @@ linear_gradient_classify (pixman_image_t *image,
pixman_fixed_32_32_t l;
pixman_fixed_48_16_t dx, dy;
double inc;
+ source_image_class_t class;
- source->class = SOURCE_IMAGE_CLASS_UNKNOWN;
+ class = SOURCE_IMAGE_CLASS_UNKNOWN;
if (source->common.transform)
{
@@ -54,7 +55,7 @@ linear_gradient_classify (pixman_image_t *image,
source->common.transform->matrix[2][1] != 0 ||
source->common.transform->matrix[2][2] == 0)
{
- return source->class;
+ return class;
}
v.vector[0] = source->common.transform->matrix[0][1];
@@ -74,7 +75,7 @@ linear_gradient_classify (pixman_image_t *image,
l = dx * dx + dy * dy;
if (l == 0)
- return source->class;
+ return class;
/*
* compute how much the input of the gradient walked changes
@@ -86,9 +87,9 @@ linear_gradient_classify (pixman_image_t *image,
/* check that casting to integer would result in 0 */
if (-1 < inc && inc < 1)
- source->class = SOURCE_IMAGE_CLASS_HORIZONTAL;
+ class = SOURCE_IMAGE_CLASS_HORIZONTAL;
- return source->class;
+ return class;
}
static void
@@ -253,7 +254,6 @@ pixman_image_create_linear_gradient (pixman_point_fixed_t * p1,
linear->p2 = *p2;
image->type = LINEAR;
- image->source.class = SOURCE_IMAGE_CLASS_UNKNOWN;
image->common.classify = linear_gradient_classify;
image->common.property_changed = linear_gradient_property_changed;
diff --git a/pixman/pixman-private.h b/pixman/pixman-private.h
index 77f629a..c43172b 100644
--- a/pixman/pixman-private.h
+++ b/pixman/pixman-private.h
@@ -111,7 +111,6 @@ struct image_common
struct source_image
{
image_common_t common;
- source_image_class_t class;
};
struct solid_fill
diff --git a/pixman/pixman-solid-fill.c b/pixman/pixman-solid-fill.c
index 44f3362..1d911e9 100644
--- a/pixman/pixman-solid-fill.c
+++ b/pixman/pixman-solid-fill.c
@@ -66,7 +66,7 @@ solid_fill_classify (pixman_image_t *image,
int width,
int height)
{
- return (image->source.class = SOURCE_IMAGE_CLASS_HORIZONTAL);
+ return SOURCE_IMAGE_CLASS_HORIZONTAL;
}
static void
@@ -109,7 +109,6 @@ pixman_image_create_solid_fill (pixman_color_t *color)
img->solid.color_32 = color_to_uint32 (color);
img->solid.color_64 = color_to_uint64 (color);
- img->source.class = SOURCE_IMAGE_CLASS_UNKNOWN;
img->common.classify = solid_fill_classify;
img->common.property_changed = solid_fill_property_changed;
commit 741c30d9d9cf445fa2e3a2c43d37c221d49831b4
Author: Andrea Canciani <ranma42@gmail.com>
Date: Wed Oct 20 21:24:32 2010 +0200
Remove unused enum value
The new linear gradient code doesn't use SOURCE_IMAGE_CLASS_VERTICAL
anymore and it was not used anywhere else.
diff --git a/pixman/pixman-private.h b/pixman/pixman-private.h
index 71b96c1..77f629a 100644
--- a/pixman/pixman-private.h
+++ b/pixman/pixman-private.h
@@ -65,7 +65,6 @@ typedef enum
{
SOURCE_IMAGE_CLASS_UNKNOWN,
SOURCE_IMAGE_CLASS_HORIZONTAL,
- SOURCE_IMAGE_CLASS_VERTICAL,
} source_image_class_t;
typedef source_image_class_t (*classify_func_t) (pixman_image_t *image,
commit 9b72fd1b857494ea928795c89a4f827e56fe26d3
Author: Andrea Canciani <ranma42@gmail.com>
Date: Mon Oct 18 22:21:52 2010 +0200
Make classification consistent with rasterization
Use the same computations to classify the gradient and to
rasterize it.
This improves the correctness of the classification by
avoiding integer division.
diff --git a/pixman/pixman-linear-gradient.c b/pixman/pixman-linear-gradient.c
index 0865594..c6ac980 100644
--- a/pixman/pixman-linear-gradient.c
+++ b/pixman/pixman-linear-gradient.c
@@ -38,58 +38,57 @@ linear_gradient_classify (pixman_image_t *image,
int width,
int height)
{
+ source_image_t *source = (source_image_t *)image;
linear_gradient_t *linear = (linear_gradient_t *)image;
pixman_vector_t v;
pixman_fixed_32_32_t l;
- pixman_fixed_48_16_t dx, dy, a, b, off;
- pixman_fixed_48_16_t factors[4];
- int i;
+ pixman_fixed_48_16_t dx, dy;
+ double inc;
- image->source.class = SOURCE_IMAGE_CLASS_UNKNOWN;
+ source->class = SOURCE_IMAGE_CLASS_UNKNOWN;
- dx = linear->p2.x - linear->p1.x;
- dy = linear->p2.y - linear->p1.y;
-
- l = dx * dx + dy * dy;
-
- if (l)
+ if (source->common.transform)
{
- a = (dx << 32) / l;
- b = (dy << 32) / l;
+ /* projective transformation */
+ if (source->common.transform->matrix[2][0] != 0 ||
+ source->common.transform->matrix[2][1] != 0 ||
+ source->common.transform->matrix[2][2] == 0)
+ {
+ return source->class;
+ }
+
+ v.vector[0] = source->common.transform->matrix[0][1];
+ v.vector[1] = source->common.transform->matrix[1][1];
+ v.vector[2] = source->common.transform->matrix[2][2];
}
else
{
- a = b = 0;
+ v.vector[0] = 0;
+ v.vector[1] = pixman_fixed_1;
+ v.vector[2] = pixman_fixed_1;
}
- off = (-a * linear->p1.x
- -b * linear->p1.y) >> 16;
-
- for (i = 0; i < 3; i++)
- {
- v.vector[0] = pixman_int_to_fixed ((i % 2) * (width - 1) + x);
- v.vector[1] = pixman_int_to_fixed ((i / 2) * (height - 1) + y);
- v.vector[2] = pixman_fixed_1;
+ dx = linear->p2.x - linear->p1.x;
+ dy = linear->p2.y - linear->p1.y;
- if (image->common.transform)
- {
- if (!pixman_transform_point_3d (image->common.transform, &v))
- {
- image->source.class = SOURCE_IMAGE_CLASS_UNKNOWN;
+ l = dx * dx + dy * dy;
- return image->source.class;
- }
- }
+ if (l == 0)
+ return source->class;
- factors[i] = ((a * v.vector[0] + b * v.vector[1]) >> 16) + off;
- }
+ /*
+ * compute how much the input of the gradient walked changes
+ * when moving vertically through the whole image
+ */
+ inc = height * (double) pixman_fixed_1 * pixman_fixed_1 *
+ (dx * v.vector[0] + dy * v.vector[1]) /
+ (v.vector[2] * (double) l);
- if (factors[2] == factors[0])
- image->source.class = SOURCE_IMAGE_CLASS_HORIZONTAL;
- else if (factors[1] == factors[0])
- image->source.class = SOURCE_IMAGE_CLASS_VERTICAL;
+ /* check that casting to integer would result in 0 */
+ if (-1 < inc && inc < 1)
+ source->class = SOURCE_IMAGE_CLASS_HORIZONTAL;
- return image->source.class;
+ return source->class;
}
static void
commit 1d4f2d71facd5f2bbce74fbe3407ccea6cf4bea1
Author: Andrea Canciani <ranma42@gmail.com>
Date: Wed Aug 11 09:58:05 2010 +0200
Improve precision of linear gradients
Integer division (without keeping the remainder) can discard a lot
of information. Doing the division maths in floating point (and
paying attention to error propagation) allows to greatly improve
the precision of linear gradients.
diff --git a/pixman/pixman-linear-gradient.c b/pixman/pixman-linear-gradient.c
index 01588c1..0865594 100644
--- a/pixman/pixman-linear-gradient.c
+++ b/pixman/pixman-linear-gradient.c
@@ -1,3 +1,4 @@
+/* -*- Mode: c; c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t; -*- */
/*
* Copyright © 2000 SuSE, Inc.
* Copyright © 2007 Red Hat, Inc.
@@ -101,7 +102,7 @@ linear_gradient_get_scanline_32 (pixman_image_t *image,
{
pixman_vector_t v, unit;
pixman_fixed_32_32_t l;
- pixman_fixed_48_16_t dx, dy, a, b, off;
+ pixman_fixed_48_16_t dx, dy;
gradient_t *gradient = (gradient_t *)image;
source_image_t *source = (source_image_t *)image;
linear_gradient_t *linear = (linear_gradient_t *)image;
@@ -136,31 +137,31 @@ linear_gradient_get_scanline_32 (pixman_image_t *image,
l = dx * dx + dy * dy;
- if (l != 0)
+ if (l == 0 || unit.vector[2] == 0)
{
- a = (dx << 32) / l;
- b = (dy << 32) / l;
- off = (-a * linear->p1.x
- -b * linear->p1.y) >> 16;
- }
-
- if (l == 0 || (unit.vector[2] == 0 && v.vector[2] == pixman_fixed_1))
- {
- pixman_fixed_48_16_t inc, t;
-
/* affine transformation only */
- if (l == 0)
+ pixman_fixed_32_32_t t, next_inc;
+ double inc;
+
+ if (l == 0 || v.vector[2] == 0)
{
t = 0;
inc = 0;
}
else
{
- t = ((a * v.vector[0] + b * v.vector[1]) >> 16) + off;
- inc = (a * unit.vector[0] + b * unit.vector[1]) >> 16;
+ double invden, v2;
+
+ invden = pixman_fixed_1 * (double) pixman_fixed_1 /
+ (l * (double) v.vector[2]);
+ v2 = v.vector[2] * (1. / pixman_fixed_1);
+ t = ((dx * v.vector[0] + dy * v.vector[1]) -
+ (dx * linear->p1.x + dy * linear->p1.y) * v2) * invden;
+ inc = (dx * unit.vector[0] + dy * unit.vector[1]) * invden;
}
+ next_inc = 0;
- if (source->class == SOURCE_IMAGE_CLASS_VERTICAL)
+ if (((pixman_fixed_32_32_t )(inc * width)) == 0)
{
register uint32_t color;
@@ -170,81 +171,52 @@ linear_gradient_get_scanline_32 (pixman_image_t *image,
}
else
{
- if (!mask)
- {
- while (buffer < end)
- {
- *buffer++ = _pixman_gradient_walker_pixel (&walker, t);
-
- t += inc;
- }
- }
- else
+ int i;
+
+ i = 0;
+ while (buffer < end)
{
- while (buffer < end)
+ if (!mask || *mask++)
{
- if (*mask++)
- *buffer = _pixman_gradient_walker_pixel (&walker, t);
-
- buffer++;
- t += inc;
+ *buffer = _pixman_gradient_walker_pixel (&walker,
+ t + next_inc);
}
+ i++;
+ next_inc = inc * i;
+ buffer++;
}
}
}
else
{
/* projective transformation */
- pixman_fixed_48_16_t t;
+ double t;
- if (source->class == SOURCE_IMAGE_CLASS_VERTICAL)
- {
- register uint32_t color;
+ t = 0;
- if (v.vector[2] == 0)
- {
- t = 0;
- }
- else
- {
- pixman_fixed_48_16_t x, y;
-
- x = ((pixman_fixed_48_16_t) v.vector[0] << 16) / v.vector[2];
- y = ((pixman_fixed_48_16_t) v.vector[1] << 16) / v.vector[2];
- t = ((a * x + b * y) >> 16) + off;
- }
-
- color = _pixman_gradient_walker_pixel (&walker, t);
- while (buffer < end)
- *buffer++ = color;
- }
- else
+ while (buffer < end)
{
- while (buffer < end)
+ if (!mask || *mask++)
{
- if (!mask || *mask++)
+ if (v.vector[2] != 0)
{
- if (v.vector[2] == 0)
- {
- t = 0;
- }
- else
- {
- pixman_fixed_48_16_t x, y;
- x = ((pixman_fixed_48_16_t)v.vector[0] << 16) / v.vector[2];
- y = ((pixman_fixed_48_16_t)v.vector[1] << 16) / v.vector[2];
- t = ((a * x + b * y) >> 16) + off;
- }
-
- *buffer = _pixman_gradient_walker_pixel (&walker, t);
- }
+ double invden, v2;
- ++buffer;
+ invden = pixman_fixed_1 * (double) pixman_fixed_1 /
+ (l * (double) v.vector[2]);
+ v2 = v.vector[2] * (1. / pixman_fixed_1);
+ t = ((dx * v.vector[0] + dy * v.vector[1]) -
+ (dx * linear->p1.x + dy * linear->p1.y) * v2) * invden;
+ }
- v.vector[0] += unit.vector[0];
- v.vector[1] += unit.vector[1];
- v.vector[2] += unit.vector[2];
+ *buffer = _pixman_gradient_walker_pixel (&walker, t);
}
+
+ ++buffer;
+
+ v.vector[0] += unit.vector[0];
+ v.vector[1] += unit.vector[1];
+ v.vector[2] += unit.vector[2];
}
}
}
commit f6ab20ca6604739b82311fc078d6ce850f43adc0
Author: Andrea Canciani <ranma42@gmail.com>
Date: Tue Oct 12 09:52:53 2010 +0200
Add comments about errors
Explain how errors are introduced in the computation performed for
radial gradients.
diff --git a/pixman/pixman-radial-gradient.c b/pixman/pixman-radial-gradient.c
index ff7bfba..ed073ab 100644
--- a/pixman/pixman-radial-gradient.c
+++ b/pixman/pixman-radial-gradient.c
@@ -42,6 +42,10 @@ dot (pixman_fixed_48_16_t x1,
pixman_fixed_48_16_t y2,
pixman_fixed_48_16_t z2)
{
+ /*
+ * Exact computation, assuming that the input values can
+ * be represented as pixman_fixed_16_16_t
+ */
return x1 * x2 + y1 * y2 + z1 * z2;
}
@@ -53,6 +57,12 @@ fdot (double x1,
double y2,
double z2)
{
+ /*
+ * Error can be unbound in some special cases.
+ * Using clever dot product algorithms (for example compensated
+ * dot product) would improve this but make the code much less
+ * obvious
+ */
return x1 * x2 + y1 * y2 + z1 * z2;
}
@@ -66,6 +76,22 @@ radial_compute_color (double a,
pixman_gradient_walker_t *walker,
pixman_repeat_t repeat)
{
+ /*
+ * In this function error propagation can lead to bad results:
+ * - det can have an unbound error (if b*b-a*c is very small),
+ * potentially making it the opposite sign of what it should have been
+ * (thus clearing a pixel that would have been colored or vice-versa)
+ * or propagating the error to sqrtdet;
+ * if det has the wrong sign or b is very small, this can lead to bad
+ * results
+ *
+ * - the algorithm used to compute the solutions of the quadratic
+ * equation is not numerically stable (but saves one division compared
+ * to the numerically stable one);
+ * this can be a problem if a*c is much smaller than b*b
+ *
+ * - the above problems are worse if a is small (as inva becomes bigger)
+ */
double det;
if (a == 0)
@@ -246,9 +272,19 @@ radial_gradient_get_scanline_32 (pixman_image_t *image,
*/
pixman_fixed_32_32_t b, db, c, dc, ddc;
+ /* warning: this computation may overflow */
v.vector[0] -= radial->c1.x;
v.vector[1] -= radial->c1.y;
+ /*
+ * B and C are computed and updated exactly.
+ * If fdot was used instead of dot, in the worst case it would
+ * lose 11 bits of precision in each of the multiplication and
+ * summing up would zero out all the bit that were preserved,
+ * thus making the result 0 instead of the correct one.
+ * This would mean a worst case of unbound relative error or
+ * about 2^10 absolute error
+ */
b = dot (v.vector[0], v.vector[1], radial->c1.radius,
radial->delta.x, radial->delta.y, radial->delta.radius);
db = dot (unit.vector[0], unit.vector[1], 0,
@@ -284,6 +320,9 @@ radial_gradient_get_scanline_32 (pixman_image_t *image,
else
{
/* projective */
+ /* Warning:
+ * error propagation guarantees are much looser than in the affine case
+ */
while (buffer < end)
{
if (!mask || *mask++)
@@ -371,10 +410,13 @@ pixman_image_create_radial_gradient (pixman_point_fixed_t * inner,
radial->c2.y = outer->y;
radial->c2.radius = outer_radius;
+ /* warning: this computations may overflow */
radial->delta.x = radial->c2.x - radial->c1.x;
radial->delta.y = radial->c2.y - radial->c1.y;
radial->delta.radius = radial->c2.radius - radial->c1.radius;
+ /* computed exactly, then cast to double -> every bit of the double
+ representation is correct (53 bits) */
radial->a = dot (radial->delta.x, radial->delta.y, -radial->delta.radius,
radial->delta.x, radial->delta.y, radial->delta.radius);
if (radial->a != 0)
commit 1ca715ed1e6914e9bd9f050065e827d7a9e2efc9
Author: Andrea Canciani <ranma42@gmail.com>
Date: Sun Aug 15 09:07:33 2010 +0200
Draw radial gradients with PDF semantics
Change radial gradient computations and definition to reflect the
radial gradients in PDF specifications (see section 8.7.4.5.4,
Type 3 (Radial) Shadings of the PDF Reference Manual).
Instead of having a valid interpolation parameter value for every
point of the plane, define it only for points withing the area
covered by the family of circles generated by interpolating or
extrapolating the start and end circles.
Points outside this area are now transparent black (rgba 0 0 0 0).
Points within this area have the color assiciated with the maximum
value of the interpolation parameter in that point (if multiple
solutions exist within the range specified by the extend mode).
diff --git a/pixman/pixman-private.h b/pixman/pixman-private.h
index 3979f60..71b96c1 100644
--- a/pixman/pixman-private.h
+++ b/pixman/pixman-private.h
@@ -152,10 +152,11 @@ struct radial_gradient
circle_t c1;
circle_t c2;
- double cdx;
- double cdy;
- double dr;
- double A;
+
+ circle_t delta;
+ double a;
+ double inva;
+ double mindr;
};
struct conical_gradient
diff --git a/pixman/pixman-radial-gradient.c b/pixman/pixman-radial-gradient.c
index 08d5f14..ff7bfba 100644
--- a/pixman/pixman-radial-gradient.c
+++ b/pixman/pixman-radial-gradient.c
@@ -1,3 +1,4 @@
+/* -*- Mode: c; c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t; -*- */
/*
*
* Copyright © 2000 Keith Packard, member of The XFree86 Project, Inc.
@@ -33,6 +34,74 @@
#include <math.h>
#include "pixman-private.h"
+static inline 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)
+{
+ return x1 * x2 + y1 * y2 + z1 * z2;
+}
+
+static inline double
+fdot (double x1,
+ double y1,
+ double z1,
+ double x2,
+ double y2,
+ double z2)
+{
+ return x1 * x2 + y1 * y2 + z1 * z2;
+}
+
+static uint32_t
+radial_compute_color (double a,
+ double b,
+ double c,
+ double inva,
+ double dr,
+ double mindr,
+ pixman_gradient_walker_t *walker,
+ pixman_repeat_t repeat)
+{
+ double det;
+
+ if (a == 0)
+ {
+ return _pixman_gradient_walker_pixel (walker,
+ pixman_fixed_1 / 2 * c / b);
+ }
+
+ det = fdot (b, a, 0, b, -c, 0);
+ if (det >= 0)
+ {
+ double sqrtdet, t0, t1;
+
+ sqrtdet = sqrt (det);
+ t0 = (b + sqrtdet) * inva;
+ t1 = (b - sqrtdet) * inva;
+
+ if (repeat == PIXMAN_REPEAT_NONE)
+ {
+ if (0 <= t0 && t0 <= pixman_fixed_1)
+ return _pixman_gradient_walker_pixel (walker, t0);
+ else if (0 <= t1 && t1 <= pixman_fixed_1)
+ return _pixman_gradient_walker_pixel (walker, t1);
+ }
+ else
+ {
+ if (t0 * dr > mindr)
+ return _pixman_gradient_walker_pixel (walker, t0);
+ else if (t1 * dr > mindr)
+ return _pixman_gradient_walker_pixel (walker, t1);
+ }
+ }
+
+ return 0;
+}
+
static void
radial_gradient_get_scanline_32 (pixman_image_t *image,
int x,
@@ -42,118 +111,85 @@ radial_gradient_get_scanline_32 (pixman_image_t *image,
const uint32_t *mask)
{
/*
+ * Implementation of radial gradients following the PDF specification.
+ * See section 8.7.4.5.4 Type 3 (Radial) Shadings of the PDF Reference
+ * Manual (PDF 32000-1:2008 at the time of this writing).
+ *
* In the radial gradient problem we are given two circles (c₁,r₁) and
- * (c₂,r₂) that define the gradient itself. Then, for any point p, we
- * must compute the value(s) of t within [0.0, 1.0] representing the
- * circle(s) that would color the point.
- *
- * There are potentially two values of t since the point p can be
- * colored by both sides of the circle, (which happens whenever one
- * circle is not entirely contained within the other).
- *
- * If we solve for a value of t that is outside of [0.0, 1.0] then we
- * use the extend mode (NONE, REPEAT, REFLECT, or PAD) to map to a
- * value within [0.0, 1.0].
- *
- * Here is an illustration of the problem:
- *
- * p₂
- * p •
- * • ╲
- * · ╲r₂
- * p₁ · ╲
- * • θ╲
- * ╲ ╌╌•
- * ╲r₁ · c₂
- * θ╲ ·
- * ╌╌•
- * c₁
- *
- * Given (c₁,r₁), (c₂,r₂) and p, we must find an angle θ such that two
- * points p₁ and p₂ on the two circles are collinear with p. Then, the
- * desired value of t is the ratio of the length of p₁p to the length
- * of p₁p₂.
- *
- * So, we have six unknown values: (p₁x, p₁y), (p₂x, p₂y), θ and t.
- * We can also write six equations that constrain the problem:
- *
- * Point p₁ is a distance r₁ from c₁ at an angle of θ:
+ * (c₂,r₂) that define the gradient itself.
*
- * 1. p₁x = c₁x + r₁·cos θ
- * 2. p₁y = c₁y + r₁·sin θ
+ * Mathematically the gradient can be defined as the family of circles
*
- * Point p₂ is a distance r₂ from c₂ at an angle of θ:
+ * ((1-t)·c₁ + t·(c₂), (1-t)·r₁ + t·r₂)
*
- * 3. p₂x = c₂x + r2·cos θ
- * 4. p₂y = c₂y + r2·sin θ
+ * excluding those circles whose radius would be < 0. When a point
+ * belongs to more than one circle, the one with a bigger t is the only
+ * one that contributes to its color. When a point does not belong
+ * to any of the circles, it is transparent black, i.e. RGBA (0, 0, 0, 0).
+ * Further limitations on the range of values for t are imposed when
+ * the gradient is not repeated, namely t must belong to [0,1].
*
- * Point p lies at a fraction t along the line segment p₁p₂:
+ * The graphical result is the same as drawing the valid (radius > 0)
+ * circles with increasing t in [-inf, +inf] (or in [0,1] if the gradient
+ * is not repeated) using SOURCE operatior composition.
*
- * 5. px = t·p₂x + (1-t)·p₁x
- * 6. py = t·p₂y + (1-t)·p₁y
+ * It looks like a cone pointing towards the viewer if the ending circle
+ * is smaller than the starting one, a cone pointing inside the page if
+ * the starting circle is the smaller one and like a cylinder if they
+ * have the same radius.
*
- * To solve, first subtitute 1-4 into 5 and 6:
+ * What we actually do is, given the point whose color we are interested
+ * in, compute the t values for that point, solving for t in:
*
- * px = t·(c₂x + r₂·cos θ) + (1-t)·(c₁x + r₁·cos θ)
- * py = t·(c₂y + r₂·sin θ) + (1-t)·(c₁y + r₁·sin θ)
+ * length((1-t)·c₁ + t·(c₂) - p) = (1-t)·r₁ + t·r₂
+ *
+ * Let's rewrite it in a simpler way, by defining some auxiliary
+ * variables:
*
- * Then solve each for cos θ and sin θ expressed as a function of t:
+ * cd = c₂ - c₁
+ * pd = p - c₁
+ * dr = r₂ - r₁
+ * lenght(t·cd - pd) = r₁ + t·dr
*
- * cos θ = (-(c₂x - c₁x)·t + (px - c₁x)) / ((r₂-r₁)·t + r₁)
- * sin θ = (-(c₂y - c₁y)·t + (py - c₁y)) / ((r₂-r₁)·t + r₁)
+ * which actually means
*
- * To simplify this a bit, we define new variables for several of the
- * common terms as shown below:
+ * hypot(t·cdx - pdx, t·cdy - pdy) = r₁ + t·dr
*
- * p₂
- * p •
- * • ╲
- * · ┆ ╲r₂
- * p₁ · ┆ ╲
- * • pdy┆ ╲
- * ╲ ┆ •c₂
- * ╲r₁ ┆ · ┆
- * ╲ ·┆ ┆cdy
- * •╌╌╌╌┴╌╌╌╌╌╌╌┘
- * c₁ pdx cdx
+ * or
*
- * cdx = (c₂x - c₁x)
- * cdy = (c₂y - c₁y)
- * dr = r₂-r₁
- * pdx = px - c₁x
- * pdy = py - c₁y
+ * ⎷((t·cdx - pdx)² + (t·cdy - pdy)²) = r₁ + t·dr.
*
- * Note that cdx, cdy, and dr do not depend on point p at all, so can
- * be pre-computed for the entire gradient. The simplifed equations
- * are now:
+ * If we impose (as stated earlier) that r₁ + t·dr >= 0, it becomes:
*
- * cos θ = (-cdx·t + pdx) / (dr·t + r₁)
- * sin θ = (-cdy·t + pdy) / (dr·t + r₁)
+ * (t·cdx - pdx)² + (t·cdy - pdy)² = (r₁ + t·dr)²
*
- * Finally, to get a single function of t and eliminate the last
- * unknown θ, we use the identity sin²θ + cos²θ = 1. First, square
- * each equation, (we knew a quadratic was coming since it must be
- * possible to obtain two solutions in some cases):
+ * where we can actually expand the squares and solve for t:
*
- * cos²θ = (cdx²t² - 2·cdx·pdx·t + pdx²) / (dr²·t² + 2·r₁·dr·t + r₁²)
- * sin²θ = (cdy²t² - 2·cdy·pdy·t + pdy²) / (dr²·t² + 2·r₁·dr·t + r₁²)
+ * t²cdx² - 2t·cdx·pdx + pdx² + t²cdy² - 2t·cdy·pdy + pdy² =
+ * = r₁² + 2·r₁·t·dr + t²·dr²
*
- * Then add both together, set the result equal to 1, and express as a
- * standard quadratic equation in t of the form At² + Bt + C = 0
+ * (cdx² + cdy² - dr²)t² - 2(cdx·pdx + cdy·pdy + r₁·dr)t +
+ * (pdx² + pdy² - r₁²) = 0
*
- * (cdx² + cdy² - dr²)·t² - 2·(cdx·pdx + cdy·pdy + r₁·dr)·t + (pdx² + pdy² - r₁²) = 0
+ * A = cdx² + cdy² - dr²
+ * B = pdx·cdx + pdy·cdy + r₁·dr
+ * C = pdx² + pdy² - r₁²
+ * At² - 2Bt + C = 0
+ *
+ * The solutions (unless the equation degenerates because of A = 0) are:
*
- * In other words:
+ * t = (B ± ⎷(B² - A·C)) / A
*
- * A = cdx² + cdy² - dr²
- * B = -2·(pdx·cdx + pdy·cdy + r₁·dr)
- * C = pdx² + pdy² - r₁²
+ * The solution we are going to prefer is the bigger one, unless the
+ * radius associated to it is negative (or it falls outside the valid t
+ * range).
*
- * And again, notice that A does not depend on p, so can be
- * precomputed. From here we just use the quadratic formula to solve
- * for t:
+ * Additional observations (useful for optimizations):
+ * A does not depend on p
*
- * t = (-2·B ± ⎷(B² - 4·A·C)) / 2·A
+ * A < 0 <=> one of the two circles completely contains the other one
+ * <=> for every p, the radiuses associated with the two t solutions
+ * have opposite sign
*/
gradient_t *gradient = (gradient_t *)image;
@@ -161,100 +197,88 @@ radial_gradient_get_scanline_32 (pixman_image_t *image,
radial_gradient_t *radial = (radial_gradient_t *)image;
uint32_t *end = buffer + width;
pixman_gradient_walker_t walker;
- pixman_bool_t affine = TRUE;
- double cx = 1.;
- double cy = 0.;
- double cz = 0.;
- double rx = x + 0.5;
- double ry = y + 0.5;
- double rz = 1.;
+ pixman_vector_t v, unit;
+
+ /* reference point is the center of the pixel */
+ v.vector[0] = pixman_int_to_fixed (x) + pixman_fixed_1 / 2;
+ v.vector[1] = pixman_int_to_fixed (y) + pixman_fixed_1 / 2;
+ v.vector[2] = pixman_fixed_1;
_pixman_gradient_walker_init (&walker, gradient, source->common.repeat);
if (source->common.transform)
{
- pixman_vector_t v;
- /* reference point is the center of the pixel */
- v.vector[0] = pixman_int_to_fixed (x) + pixman_fixed_1 / 2;
- v.vector[1] = pixman_int_to_fixed (y) + pixman_fixed_1 / 2;
- v.vector[2] = pixman_fixed_1;
-
if (!pixman_transform_point_3d (source->common.transform, &v))
return;
-
- cx = source->common.transform->matrix[0][0] / 65536.;
- cy = source->common.transform->matrix[1][0] / 65536.;
- cz = source->common.transform->matrix[2][0] / 65536.;
- rx = v.vector[0] / 65536.;
- ry = v.vector[1] / 65536.;
- rz = v.vector[2] / 65536.;
-
- affine =
- source->common.transform->matrix[2][0] == 0 &&
- v.vector[2] == pixman_fixed_1;
+ unit.vector[0] = source->common.transform->matrix[0][0];
+ unit.vector[1] = source->common.transform->matrix[1][0];
+ unit.vector[2] = source->common.transform->matrix[2][0];
+ }
+ else
+ {
+ unit.vector[0] = pixman_fixed_1;
+ unit.vector[1] = 0;
+ unit.vector[2] = 0;
}
- if (affine)
+ if (unit.vector[2] == 0 && v.vector[2] == pixman_fixed_1)
{
- /* When computing t over a scanline, we notice that some expressions
- * are constant so we can compute them just once. Given:
+ /*
+ * Given:
*
- * t = (-2·B ± ⎷(B² - 4·A·C)) / 2·A
+ * t = (B ± ⎷(B² - A·C)) / A
Reply to: