[Pixman] [PATCH 05/15] pixman-filter: Correct Simpsons integration

[Oded Gabbay]

On Thu, Dec 17, 2015 at 11:59 PM, Bill Spitzak <spitzak at gmail.com> wrote:
> Best one I think:
>
> http://www.intmath.com/integration/6-simpsons-rule.php
>
>
> On Thu, Dec 17, 2015 at 1:50 PM, Bill Spitzak <spitzak at gmail.com> wrote:
>>
>> This was based on looking up Simpson's integration on the web, from the
>> wikipedia page and another page I found.
>>
>> It cuts the samples into sets of 3, with an overlap of 1. Each set then
>> weighs 1,4,1 in the average, to simulate the weight of the control points of
>> a cubic curve. Since the overlapping samples of 1 add to 2 this results in
>> 1,4,2,4,2,...4,1 as the weights.  As there are two points per set and the
>> total weight is 1+4+1=6, you divide the full sum by 6/2 = 3.
>>
>> It appears this implementation attempted to overlap them by 2, resulting
>> in weights of 1,5,6,...6,5,1. However this is very close to a flat average
>> of all the points. Also this is a total of 6 for every point so the divisor
>> should be 6, but it was left at 3.
>>
>> Based on my reading the new version is correct. However I have not been
>> able to see any visible difference in the filtering even if I reduce the
>> number of samples to 3.
>>

Well, I don't find any major reason why to reject this, even if it
doesn't seem to make any visual difference. I prefer the code to be as
close as possible to the equations (easier to understand), unless
there is some disadvantage (low ratio of performance/quality), and I
don't see it here so patch is:

Reviewed-by: Oded Gabbay <oded.gabbay at gmail.com>

>>
>> On Thu, Dec 17, 2015 at 10:21 AM, Oded Gabbay <oded.gabbay at gmail.com>
>> wrote:
>>>
>>> On Thu, Dec 17, 2015 at 8:20 PM, Oded Gabbay <oded.gabbay at gmail.com>
>>> wrote:
>>> > On Sat, Dec 12, 2015 at 8:06 PM,  <spitzak at gmail.com> wrote:
>>> >> From: Bill Spitzak <spitzak at gmail.com>
>>> >>
>>> >> Simpsons uses cubic curve fitting, with 3 samples defining each cubic.
>>> >> This
>>> >> makes the weights of the samples be in a pattern of 1,4,2,4,2...4,1,
>>> >> and then
>>> >> dividing the result by 3.
>>> >>
>>> >> The previous code was using weights of 1,2,6,6...6,2,1 which produced
>>> >> about 2x
>>> >> the correct value, as it was still dividing by 3. The filter
>>> >> normalization
>>> >> removed this error. Also this is effectively a linear interpolation
>>> >> except for
>>> >> the ends.
>>> >> ---
>>> >>  pixman/pixman-filter.c | 11 +++++++----
>>> >>  1 file changed, 7 insertions(+), 4 deletions(-)
>>> >>
>>> >> diff --git a/pixman/pixman-filter.c b/pixman/pixman-filter.c
>>> >> index 15f9069..7c1da0d 100644
>>> >> --- a/pixman/pixman-filter.c
>>> >> +++ b/pixman/pixman-filter.c
>>> >> @@ -204,11 +204,14 @@ integral (pixman_kernel_t reconstruct, double
>>> >> x1,
>>> >>         {
>>> >>             double a1 = x1 + h * i;
>>> >>             double a2 = x2 + h * i;
>>> >> +           s += 4 * SAMPLE(a1, a2);
>>> >> +       }
>>> >>
>>> >> -           s += 2 * SAMPLE (a1, a2);
>>> >> -
>>> >> -           if (i >= 2 && i < N_SEGMENTS - 1)
>>> >> -               s += 4 * SAMPLE (a1, a2);
>>> >> +       for (i = 2; i < N_SEGMENTS; i += 2)
>>> >> +       {
>>> >> +           double a1 = x1 + h * i;
>>> >> +           double a2 = x2 + h * i;
>>> >> +           s += 2 * SAMPLE(a1, a2);
>>> >>         }
>>> >>
>>> >>         s += SAMPLE (x1 + width, x2 + width);
>>> >> --
>>> >> 1.9.1
>>> >>
>>> >> _______________________________________________
>>> >> Pixman mailing list
>>> >> Pixman at lists.freedesktop.org
>>> >> http://lists.freedesktop.org/mailman/listinfo/pixman
>>> >
>>> > You say:
>>> >
>>> > "The filter normalization removed this error. Also this is effectively
>>> > a linear interpolation except for the ends."
>>> >
>>> > So if the error was removed, why is this change needed ? I can see it
>>> > is more accurate (similar to the Simpson equation), but it also causes
>>> > the code to run over the loop twice.
>>> >
>>> > Do you have some example we can see the difference ?
>>> >
>>> >
>>> >     Oded
>>>
>>> OK, now I see that in the next patch, you reduce the samples from 128
>>> to 16, so we are now running less iterations.
>>> I still would be happy to see an example with my own eyes where this
>>> makes a difference.
>>>
>>>         Oded
>>
>>
>