[Pixman] [PATCH] Improve handling of tangent circles

[Andrea Canciani]

On Fri, Jan 7, 2011 at 11:54 AM, Siarhei Siamashka
<siarhei.siamashka at gmail.com> wrote:
> On Tuesday 04 January 2011 16:33:18 Andrea Canciani wrote:
>> On Tue, Jan 4, 2011 at 11:12 AM, Andrea Canciani <ranma42 at gmail.com> wrote:
>> > On Tue, Jan 4, 2011 at 10:59 AM, Siarhei Siamashka
>> >> I just wonder if it would be difficult to add a test to pixman for this
>> >> particular division by zero case? Or is it somehow triggered by cairo
>> >> tests?
>> >
>> > It is triggered by the new radial-gradient tests in cairo:
>> > http://cgit.freedesktop.org/cairo/commit/?id=ada6057b8ccab133909b127850c4
>> > 1abb3216a842
>> >
>> > The refimages have been created with a patched pixman, so the tests
>> > currently fail on cairo-image, but would pass with this change.
>> >
>> >> One of the problems with the pixman radial code is that it is slow.
>> >> And this path further slows it down a bit by adding a new branch in the
>> >> inner loop. This is perfectly fine for a reference implementation, but
>> >> if somebody decides to add some performance optimizations, then we need
>> >> to have at least some basic tests which can catch possible errors and
>> >> regressions.
>>
>> The proposed code is equivalent to:
>>
>>     if (a == 0)
>>     {
>>         double t;
>>
>>         if (b == 0)
>>             return 0;
>>
>>         t = pixman_fixed_1 / 2 * c / b;
>>         if (repeat == PIXMAN_REPEAT_NONE || t * dr > mindr)
>>             return _pixman_gradient_walker_pixel (walker, t);
>>
>>       return 0;
>>     }
>>
>> or even to
>>
>>     if (a == 0)
>>     {
>>         double t;
>>
>>         if (b == 0)
>>             return 0;
>>
>>         t = pixman_fixed_1 / 2 * c / b;
>>         if (t * dr > mindr)
>>             return _pixman_gradient_walker_pixel (walker, t);
>>
>>       return 0;
>>     }
>>
>> because the drawn part (the range [0,1]) of a REPEAT_NONE gradient
>> will always have non-negative radius and the gradient walker will always
>> return 0 for anything outside [0,1] (and we cannot have multiple solutions
>> for the same point if a==0).
>> This would remove a branch, but I'd rather do it only if the code is still
>> clear. The proposed patch looks more "obviously  correct" to me because
>> it validates the solutions just as in the a!=0 case.
>>
>> In http://cgit.freedesktop.org/~ranma42/cairo/log/?h=wip/gl3 I used this
>> property to have just one shader for the a==0 case, ignoring the extend
>> mode.
>
> Yes, it is obvious that the radial gradients can be optimized quite a lot. And
> 'gradient_walker' can be probably also converted to a branchless SIMD code for
> the cases when the number of gradient stops is small.

IIRC there has been some work on faster gradients, involving a sampling of
the color function. I believe it would be easier to implement after
Soren's patchset
for image iterators is merged.

>
> All the math for radial gradients is well commented. The real problem is not to
> introduce regressions when adding optimizations (tests should really help
> here). And also precision requirements are not quite clear, the current
> implementation uses a mix of fixed point calculations and double precision
> floating point. A clean description of precision requirements, or probably also
> another simple and clean non-optimized low precision reference radial gradients
> implementation would be nice to have (with the checks for the conditions where
> such low precision would be sufficient).

Yes, sorry about that. I tried to also provide an "exact" implementation to be
used as reference, but in fact I didn't.

Currently the code uses exact arithmetic (fixed point) to compute the
coefficients
of the quadratic equation (and to update them exactly).

radial_compute_color uses doubles when solving the equation because the
discriminant of the equation ("det" in the code) can be huge (128 bits).

I'll try to work out some tight bounds on ranges and precisions involved in the
computations, although there are some nontrivial problems in the
"fdot" computation
(which is the main reason why I didn't care about using the numerically stable
2nd degree solution algorithm).

I implemented the same algorithm in lower precision for gl shaders, but I
get some minor differences. Would this be considered acceptable?
In this case the test should probably be graphical instead of a checksum.

>
> That said, I have nothing against your patch. I was just curious about what's
> going to happen next to the pixman (and cairo) radial gradients. Is the math
> already set in stone?

I think that the "implementation math" can be changed as many times as we
like (to improve performance, numerical stability, etc), but I believe that we
should stick with the PS/PDF radial gradient definition, because it seems to be
the only one in use to handle the case where neither circle contains
the other one.

(It is not the only possible/reasonable one, but it's kind of pointless to have
multiple inconsistent definitions)

Andrea