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 06/15] pixman-filter: reduced number of samples in Simpson's integration

[Oded Gabbay]

On Fri, Dec 18, 2015 at 12:17 AM, Bill Spitzak  wrote:
> Ok to squash them together. Do you want me to do that?
>
Yes. There will definitely v7 of the patchset (which most likely will
be the version getting merged into the tree), so do it in that
version.

Oded

> It actually does not increase the runtime, because the two loops are only
> adding every *other* sample. Thus the same number of samples are computed.
>

> On Thu, Dec 17, 2015 at 1:23 PM, Oded Gabbay  wrote:
>>
>> On Sat, Dec 12, 2015 at 8:06 PM,   wrote:
>> > From: Bill Spitzak 
>> >
>> > With the cubic fix this is plenty accurate enough, far in excess of the
>> > pixman
>> > fixed-point error limit. Likely even 16 samples is too many.
>> > ---
>> >  pixman/pixman-filter.c | 2 +-
>> >  1 file changed, 1 insertion(+), 1 deletion(-)
>> >
>> > diff --git a/pixman/pixman-filter.c b/pixman/pixman-filter.c
>> > index 7c1da0d..4aafa51 100644
>> > --- a/pixman/pixman-filter.c
>> > +++ b/pixman/pixman-filter.c
>> > @@ -190,7 +190,7 @@ integral (pixman_kernel_t reconstruct, double x1,
>> >  else
>> >  {
>> > /* Integration via Simpson's rule */
>> > -#define N_SEGMENTS 128
>> > +#define N_SEGMENTS 16
>> >  #define SAMPLE(a1, a2)
>> > \
>> > (filters[reconstruct].func ((a1)) * filters[sample].func ((a2) /
>> > scale))
>> >
>> > --
>> > 1.9.1
>> >
>> > ___
>> > Pixman mailing list
>> > Pixman@lists.freedesktop.org
>> > http://lists.freedesktop.org/mailman/listinfo/pixman
>>
>> I think it is better to just squash this patch into the previous one,
>> as it closely related and actually makes more sense to put them
>> together so we can see the run time hasn't increased but actually
>> decreased.
>>
>>   Oded
>
>
___
Pixman mailing list
Pixman@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/pixman

Re: [Pixman] Plan to release final development version before stable branch

[Oded Gabbay]

On Wed, Dec 16, 2015 at 4:41 AM, Bill Spitzak  wrote:
>
>
> On Tue, Dec 15, 2015 at 1:29 AM, Oded Gabbay  wrote:
>>
>> On Sat, Dec 12, 2015 at 9:10 PM, Bill Spitzak  wrote:
>> >
>> >
>> > On Sat, Dec 12, 2015 at 10:37 AM, Oded Gabbay 
>> > wrote:
>> >>
>> >> On Sat, Dec 12, 2015 at 8:34 PM, Bill Spitzak 
>> >> wrote:
>> >> > On Fri, Dec 11, 2015 at 4:15 AM, Oded Gabbay 
>> >> > wrote:
>> >> >>
>> >> >> On Thu, Dec 10, 2015 at 11:19 PM, Bill Spitzak 
>> >> >> wrote:
>> >> >> > Can you include my patches to fix the filtering? They have been
>> >> >> > posted
>> >> >> > for a
>> >> >> > long time now.
>> >> >> >
>> >> >> > The last patch makes GOOD/BEST use filtering for scaling images
>> >> >> > down.
>> >> >> > This
>> >> >> > matches the current Cairo behavior and would allow Cairo to use
>> >> >> > the
>> >> >> > pixman
>> >> >> > backend rather than doing an image fallback for any image scaling
>> >> >> > smaller
>> >> >> > than .75. It also contains a bunch of minor optimizaion and filter
>> >> >> > selection
>> >> >> > tweaks that makes the output somewhat better than current Cairo.
>> >> >> >
>> >> >> Hi Bill,
>> >> >>
>> >> >> Unfortunately, I don't see anyone reviewed your patches, and from
>> >> >> what
>> >> >> I heard, those are quite significant changes.
>> >> >>
>> >> >> It's a shame you didn't bring this up when I did the first
>> >> >> development
>> >> >> release 4 months ago. Then we had enough time to check and test it.
>> >> >> I'm quite hesitant of including such changes right before the final
>> >> >> development version, even with a review.
>> >> >
>> >> >
>> >> > I did send email on May 22, 2015, in response to your comments.
>> >>
>> >> That's strange, because I only started working on pixman during June of
>> >> 2015...
>> >
>> >
>> > You are right. That was just a general email I sent trying to get
>> > somebody
>> > to look at the patches. Searching in the history I found 3 of these.
>> >
>> >>
>> >>
>> >>
>> >> >
>> >> >> I suggest that you try to contact one of pixman's veterans (Soren,
>> >> >> Siarhei, Matt, Pekka, Ben) offline and ask them nicely to at least
>> >> >> skim over the patches and give a high-level opinion about the
>> >> >> series.
>> >> >
>> >> >
>> >> > These were discussed with Soren before. He disagreed with my previous
>> >> > version because I changed to a single filter calculation rather than
>> >> > his
>> >> > pair of filters being convoluted. This version preserves the pair of
>> >> > filters, with some fixes of bugs that caused artifacts in the
>> >> > resulting
>> >> > filters. I'm sending email directly in case they are not reading the
>> >> > pixman
>> >> > list.
>> >>
>> >> Could you send me those emails ?
>> >
>> >
>> > I forwarded the big one from him and my response. The patches I have had
>> > since then I believe address his concerns and preserve the 2-filter
>> > convolution api, they are just bug fixes and some efficiency changes.
>> >>
>> >>
>> >> >>
>> >> >>
>> >> >> Also, check if you need to rebase the patches against current pixman
>> >> >> and if so, maybe send the series again. It might stir up a
>> >> >> discussion.
>> >> >
>> >> >
>> >> > The patches applied to the newest version without any conflicts and
>> >> > my
>> >> > test
>> >> > programs still work. I have resent them to the pixman mailing list.
>> >> >>
>> >>
>> >> Great!
>> >>
>> >> >>
>> >> >> I'm willing to review them in terms of correctness and code style,
>> >> >> but
>> >> >> I'm not veteran enough in pixman to give an opinion on the
>> >> >> underlying
>> >> >> changes (which is the most important issue).
>> >> >
>> >> >
>> >> > Anything would be great.
>> >> >
>> >> > I believe these work well and have been using them for a while. This
>> >> > would
>> >> > allow the removal of redundant code in Cairo, and would allow 2-pass
>> >> > filtering to be done at some point in the future, which would really
>> >> > improve
>> >> > pixman performance.
>> >> >
>> >> ok, I'll try to take a look next week or so.
>> >>
>> >> Oded
>> >
>> >
>>
>> Hi Bill,
>>
>> I read most of the emails you sent me and I cleared time tomorrow to
>> review your patches.
>>
>> Having said that, IMHO, I believe it would be too risky to merge them
>> into the final development release. This is due to a combination of
>> two things:
>>
>> A. This release, although it is a "development release" is used by
>> current distributions (fedora 22,23, ubuntu, debian). That's because
>> there was a big gap in the release schedule earlier this year.
>>
>> B. The changes here affect users of pixman and cairo, by changing the
>> way pixman behaves. So even if your patches are perfect, and the
>> result is a better pixman, we need to give time to users (and to
>> cairo) to adapt to it. This can only be done in master branch, not in
>> stable branches.
>>
>> So, what I 

Re: [Pixman] [PATCH 01/15] demos/scale: Compute filter size using boundary of xformed ellipse, not rectangle

[Oded Gabbay]

On Thu, Dec 17, 2015 at 11:02 PM, Bill Spitzak  wrote:
> Well that was a pain to figure out again (it is tricky to get p and x and y
> cancelled out of the calculation) but does this make any sense:
>
> Calculate bounding box of radius-1 circle in xy transformed to uv:
>
> Transform x,y to u,v by this matrix calculation:
>
>   |u|   |a c| |x|
>   |v| = |b d|*|y|
>
> Horizontal component:
>
>   u = ax+cy (1)
>
> x,y describes a radius-1 circle, p is angle to the point:
>
>   p = 0..2*pi
>   x = cos(p)
>   y = sin(p)
>   x^2+y^2 = 1
>   dx/dp = -sin(p) = -y
>   dy/dp = cos(p) = x
>
> Figure out derivative of (1) relative to p:
>
>   du/dp = a(dx/dp) + c(dy/dp)
> = -ay + cx
>
> The min and max u are when du/dp is zero:
>
>   -ay + cx = 0
>   cx = ay
>   c = ay/x  (2)
>   y = cx/a  (3)
>
> Substitute (2) into (1) and simplify:
>
>   u = ax + ay^2/x
> = a(x^2+y^2)/x
> = a/x (because x^2+y^2 = 1)
>   x = a/u (4)
>
> Substitute (4) into (3) and simplify:
>
>   y = c(a/u)/a
>   y = c/u (5)
>
> Square (4) and (5) and add:
>
>   x^2+y^2 = (a^2+c^2)/u^2
>
> But x^2+y^2 is 1:
>
>   1 = (a^2+c^2)/u^2
>   u^2 = a^2+c^2
>   u = hypot(a,c)
>
> Similarily the max/min of v is at:
>
>   v = hypot(b,d)
>
>
Nice.
So please just add that as a comment inside the code above your calls
to hypot for posterity.

Oded

> On Thu, Dec 17, 2015 at 1:52 AM, Oded Gabbay  wrote:
>>
>> On Sat, Dec 12, 2015 at 8:06 PM,   wrote:
>> > From: Bill Spitzak 
>> >
>> > This is much more accurate and less blurry. In particular the filtering
>> > does
>> > not change as the image is rotated.
>> > ---
>> >  demos/scale.c | 43 ++-
>> >  1 file changed, 2 insertions(+), 41 deletions(-)
>> >
>> > diff --git a/demos/scale.c b/demos/scale.c
>> > index d00307e..71c7791 100644
>> > --- a/demos/scale.c
>> > +++ b/demos/scale.c
>> > @@ -55,50 +55,11 @@ get_widget (app_t *app, const char *name)
>> >  return widget;
>> >  }
>> >
>> > -static double
>> > -min4 (double a, double b, double c, double d)
>> > -{
>> > -double m1, m2;
>> > -
>> > -m1 = MIN (a, b);
>> > -m2 = MIN (c, d);
>> > -return MIN (m1, m2);
>> > -}
>> > -
>> > -static double
>> > -max4 (double a, double b, double c, double d)
>> > -{
>> > -double m1, m2;
>> > -
>> > -m1 = MAX (a, b);
>> > -m2 = MAX (c, d);
>> > -return MAX (m1, m2);
>> > -}
>> > -
>> >  static void
>> >  compute_extents (pixman_f_transform_t *trans, double *sx, double *sy)
>> >  {
>> > -double min_x, max_x, min_y, max_y;
>> > -pixman_f_vector_t v[4] =
>> > -{
>> > -   { { 1, 1, 1 } },
>> > -   { { -1, 1, 1 } },
>> > -   { { -1, -1, 1 } },
>> > -   { { 1, -1, 1 } },
>> > -};
>> > -
>> > -pixman_f_transform_point (trans, [0]);
>> > -pixman_f_transform_point (trans, [1]);
>> > -pixman_f_transform_point (trans, [2]);
>> > -pixman_f_transform_point (trans, [3]);
>> > -
>> > -min_x = min4 (v[0].v[0], v[1].v[0], v[2].v[0], v[3].v[0]);
>> > -max_x = max4 (v[0].v[0], v[1].v[0], v[2].v[0], v[3].v[0]);
>> > -min_y = min4 (v[0].v[1], v[1].v[1], v[2].v[1], v[3].v[1]);
>> > -max_y = max4 (v[0].v[1], v[1].v[1], v[2].v[1], v[3].v[1]);
>> > -
>> > -*sx = (max_x - min_x) / 2.0;
>> > -*sy = (max_y - min_y) / 2.0;
>> > +*sx = hypot (trans->m[0][0], trans->m[0][1]) / trans->m[2][2];
>> > +*sy = hypot (trans->m[1][0], trans->m[1][1]) / trans->m[2][2];
>> >  }
>> >
>> >  typedef struct
>> > --
>> > 1.9.1
>> >
>> > ___
>> > Pixman mailing list
>> > Pixman@lists.freedesktop.org
>> > http://lists.freedesktop.org/mailman/listinfo/pixman
>>
>> Could you please add some comment in the code about where this
>> calculation comes from (reference to some mathematical
>> equation/proof), and detail the mapping of the variables in the code
>> to the arguments of the mathematical equation ?
>>
>> Otherwise, this patch is:
>>
>> Reviewed-by: Oded Gabbay 
>
>
___
Pixman mailing list
Pixman@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/pixman