[Pixman] FAST_PATH_SAMPLES_COVER_CLIP flag & fast_composite_scaled_nearest_*

[Siarhei Siamashka]

On Thursday 22 July 2010 07:26:10 Soeren Sandmann wrote:
> Siarhei Siamashka <siarhei.siamashka at gmail.com> writes:
> > Function 'pixman_transform_bounds' which is used for deciding whether to
> > set FAST_PATH_SAMPLES_COVER_CLIP flag, uses 'pixman_transform_point'
> > call. While 'fast_composite_scaled_nearest_*' functions do initial
> > addition of 'pixman_fixed_1 / 2', call to 'pixman_transform_point_3d'
> > and subtraction of 'pixman_fixed_e'.
> > 
> > Moreover, both 'pixman_transform_point' and 'pixman_transform_point_3d'
> > functions are truncating low order bits in intermediate calculations,
> > losing precision. This does not have any effect on the initial "top left
> > corner" point, but still may cause differences on the other end of the
> > bounding box (the scaler implementations use "unit_x"/"unit_y"
> > increments on each iteration, while 'pixman_transform_bounds' tries to
> > calculate the end result with 'pixman_transform_point' which is not
> > perfectly precise).
> 
> Thanks a lot for tracking down this issue and coming up with test
> cases. Both the tests look good to me, though it might be interesting
> to also have this one:
> 
>     /* can potentially access memory outside source image buffer */
>     assert (do_test (
>        10, 10, 0, 1, PIXMAN_REPEAT_PAD) == 0);
> 
> which has 1 for the scaling factor instead of 0. It has the same
> problem, but the matrix is less degenerate.

Yes, sure, this modified case can be also tested.

> The pixman coordinate system looks like this:
> 
>          +---+---+---+---+---
> 
>          | x | x | x | x | x
>          |
>          |---|---|---|---|---
>          |
>          | x | x | x | x | x
>          |
>          |---|---|---|---|---
> 
> where the x'es are pixels, which are located on half-integer
> positions, and the lines are located on integer positions.
> 
> When something is composited, we compute a box in the destination with
> integer corners. The pixman_transform_bounds() function will transform
> such a box into source space and then take the bounding box and round
> it 'outwards' to get an integer box in source space.
> 
> Normally, this box in source space will include all the samples needed
> for a NEAREST operation, but the scaling-crash-test demonstrates a
> case where this is false. What is going on is that the transformation
> has 0 in the (0, 0) position so that the source area collapses into an
> infinitely thin region along the y axis. When we try to sample under
> that transformation, the x coordinate of the location is 0, which we
> round down to -0.5, which is outside the source image. If the x
> coordinate had been 0.01, then it would have been rounded to 0.5 and
> the result would have been correct.
> 
> It is only because the transformation is so strange that this case
> fails. What pixman_transform_bounds() computes is essentially correct
> in that the result really is the bounding box of the transformed
> bounding box. However, the transform is strange enough that rounding
> issues makes us sample slightly outside this box.
> 
> Of course we shouldn't crash in this case, but I don't think it's
> particularly important to get predictable results. It's not even
> completely clear what that would mean.

If the results are used for something, it's better to have them predictable and
well defined. Off by one pixel bounding boxes may cause problems, even if they
are hard to trigger or just cause minor rendering artifacts at the image edges
instead of crashes. It makes the code a bit "shaky" and prone to causing more
complex workarounds introduced in other parts, intended to compensate or cancel
the rounding errors.

If reaching the end of the bounding box is possible via alternative methods 
like using transform or iterating over pixels from one end of the image to the 
other, then preferably these methods should provide identical results.

But this is not strictly necessary if very rare minor artifacts are tolerable
and the code is protected against problems like wrong memory accesses. Ensuring 
full predictability may be even impossible for the floating point variants of
the functions.

> The second issue is that sometimes pixman_transform_bounds() is too
> pessimistic. That's because the area we are actually interested in is
> the transformed locations of the *pixels* and not of the bounding
> box. Ie., we should take the transformed locations of
> 
>         (x1 + 0.5, y1 + 0.5) ... (x2 - 0.5, y2 - 0.5)
> 
> and compute the bounding box of those in source space.

Yes, I tried to address exactly this problem in my v2 patch variant.

> Related to this is that in this case the transformation needs to be
> done in the same way that the sampling does it, and it really needs to
> account for the filter used as well if the
> FAST_PATH_SAMPLES_COVER_CLIP is going to mean that no samples outside
> the source boundaries are needed.

Agreed. Though the usefulness of FAST_PATH_SAMPLES_COVER_CLIP flag for any 
filter other than nearest is a bit questionable. Even bilinear filter quite 
often does sampling of one extra pixel outside the source image. But anyway,
additionally taking filter into account should not harm.

> It seems to me that pixman_transform_bounds() is computing something
> meaningful, and the X server is using it in a fairly reasonable way,
> but it is wrong to use it to compute FAST_PATH_SAMPLES_COVER_CLIP
> which is a flag that is concerned with sampling and not with integer
> boxes. For that reason I don't think changing
> pixman_transform_bounds() is the right answer.

Indeed, if pixman_transform_bounds() is used for the other purposes in X 
server, changing it may cause some unnecessary regressions.

> Instead, I think both issues can be fixed by using a new function:
> 
>         compute_sample_bounds (transform, box, filter)
> 
> that would do the rounded transformation on each of the four corner
> pixels, adding the filter extents, and then compute the bounding box
> of that instead. Does that seem like a reasonable plan?

Yes, this is reasonable.

-- 
Best regards,
Siarhei Siamashka