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

[Oded Gabbay]

On Thu, Dec 17, 2015 at 11:59 PM, Bill Spitzak  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  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 

>>
>> On Thu, Dec 17, 2015 at 10:21 AM, Oded Gabbay 
>> wrote:
>>>
>>> On Thu, Dec 17, 2015 at 8:20 PM, Oded Gabbay 
>>> wrote:
>>> > On Sat, Dec 12, 2015 at 8:06 PM,   wrote:
>>> >> From: Bill Spitzak 
>>> >>
>>> >> 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@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
>>
>>
>
___
Pixman mailing list
Pixman@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/pixman

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

[Oded Gabbay]

On Thu, Dec 17, 2015 at 8:20 PM, Oded Gabbay  wrote:
> On Sat, Dec 12, 2015 at 8:06 PM,   wrote:
>> From: Bill Spitzak 
>>
>> 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@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
___
Pixman mailing list
Pixman@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/pixman

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

[Bill Spitzak]

Best one I think:

http://www.intmath.com/integration/6-simpsons-rule.php


On Thu, Dec 17, 2015 at 1:50 PM, Bill Spitzak  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.
>
>
> On Thu, Dec 17, 2015 at 10:21 AM, Oded Gabbay 
> wrote:
>
>> On Thu, Dec 17, 2015 at 8:20 PM, Oded Gabbay 
>> wrote:
>> > On Sat, Dec 12, 2015 at 8:06 PM,   wrote:
>> >> From: Bill Spitzak 
>> >>
>> >> 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@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
>>
>
>
___
Pixman mailing list
Pixman@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/pixman

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

[spitzak]

From: Bill Spitzak 

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@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/pixman