Re: [Pixman] [PATCH 12/14] pixman-filter: Fix several issues related to normalization

[Bill Spitzak]

The attached patch changes the normalization to the version I was
suggesting. I added some print statements and discovered that the "residual
error" was always zero, after some analysis I figured out that this version
will always produce a set of values that sum to pixman_fixed_1 (unless the
filter is unrealistically wide, far larger than 2^20, to get double
precision errors to sum large enough to change this). So I removed the
new_total and residual error and left a comment in there.

I am having trouble with IMPULSE.BOX producing values that are all equal or
very close together. Do you know of a way to get gnuplot to include y==0 as
otherwise the plots are very misleading unless you read the axis values.
Also this produces "Warning: empty y range [1:1], adjusting to [0.99:1.01]"
messages, possibly these are not an actual error.


patch
Description: Binary data
___
Pixman mailing list
Pixman@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/pixman

Re: [Pixman] [PATCH 12/14] pixman-filter: Fix several issues related to normalization

[Bill Spitzak]

Excellent idea to put the error diffusion into the division. Just a bit of
cleanup and changes for some suspected bugs (that are probably invisible
but might as well get them):

On Mon, Apr 11, 2016 at 7:36 PM, Søren Sandmann Pedersen <
soren.sandm...@gmail.com> wrote:

> There are a few bugs in the current normalization code
>
> (1) The normalization is based on the sum of the *floating point*
> values generated by integral(). But in order to get the sum to be
> close to pixman_fixed_1, the sum of the rounded fixed point values
> should be used.
>
> (2) The multiplications in the normalization loops often round the
> same way, so the residual error can fairly large.
>
> (3) The residual error is added to the sample located at index
> (width - width / 2), which is not the midpoint for odd widths (and
> for width 1 is in fact outside the array).
>
> This patch fixes these issues by (1) using the sum of the fixed point
> values as the total to divide by, (2) doing error diffusion in the
> normalization loop, and (3) putting any residual error (which is now
> guaranteed to be less than pixman_fixed_e) at the first sample, which
> is the only one that didn't get any error diffused into it.
>
> Signed-off-by: Søren Sandmann 
> ---
>  pixman/pixman-filter.c | 23 +++
>  1 file changed, 15 insertions(+), 8 deletions(-)
>
> diff --git a/pixman/pixman-filter.c b/pixman/pixman-filter.c
> index 32aaa9a..4abd05f 100644
> --- a/pixman/pixman-filter.c
> +++ b/pixman/pixman-filter.c
> @@ -247,7 +247,7 @@ create_1d_filter (int  width,
>  double frac = step / 2.0 + i * step;
> pixman_fixed_t new_total;
>  int x, x1, x2;
> -   double total;
> +   double total, e;
>

I think total should be a pixman_fixed_t as that is what it is summing.


> /* Sample convolution of reconstruction and sampling
>  * filter. See rounding.txt regarding the rounding
> @@ -278,24 +278,31 @@ create_1d_filter (int  width,
>   ihigh - ilow);
> }
>
> -   total += c;
> -*p++ = (pixman_fixed_t)(c * 65536.0 + 0.5);
> +*p = (pixman_fixed_t)floor (c * 65536.0 + 0.5);
>

floor probably is a good idea to make negative filter entries work. Is
there a macro that does this conversion?

+   total += *p;
> +   p++;
>  }
>

Might want to skip the normalize if total==pixman_fixed_1, though perhaps a
test to see how often that happens would be informative.


>
> -   /* Normalize */
> +   /* Normalize, with error diffusion */
> p -= width;
> -total = 1 / total;
> +total = 65536.0 / total;
>

Remove the division so total can be a pixman_fixed_t.


>  new_total = 0;
> +   e = 0.0;
>

Change this to 0.5


> for (x = x1; x < x2; ++x)
> {
> -   pixman_fixed_t t = (*p) * total + 0.5;
> +   double v = (*p) * total + e;


Change to this so total can be a pixman_fixed_t:
   double v = (*p) * (double)(pixman_fixed_1) / total + e;

+   pixman_fixed_t t = floor (v + 0.5);
>

Change this to just floor(v). The 0.5 factor is incorporated into e. This
version is in effect adding .5 to all the samples, though that is
compensated for somewhat by floor in effect subtracting .5, but imagine
what happens if e > 0.5. This bug was in Nuke for many years btw.


> +   e = v - t;
> new_total += t;
> *p++ = t;
> }
>
> -   if (new_total != pixman_fixed_1)
> -   *(p - width / 2) += (pixman_fixed_1 - new_total);
> +   /* pixman_fixed_e's worth of error may remain; put it
> +* at the first sample, since that is the only one that
> +* hasn't had any error diffused into it.
> +*/
> +   *(p - width) += pixman_fixed_1 - new_total;
>

I'm not absolutely convinced that the first sample is best. Dumping this on
the central pixel may be better because that value is larger so the
relative change is smaller:

*(p - (width+1)/2) += pixman_fixed_1 - new_total;


>  }
>  }
>
> --
> 1.7.11.7
>
>
___
Pixman mailing list
Pixman@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/pixman