Bug 84396

Hmm, that is a convincing argument. I will have to think carefully to make sure my understanding of sample cells/locations, sample resolution and edges is correct.

Right, the other argument is that the edges are not projected onto the sample grid correctly - the effect is that we are sampling each cell at (0, 0) not (.5, .5). I wonder if using a round not truncation in the projection of the edges would fix it.

Untested, but I am thinking along the lines of:

diff --git a/src/cairo-tor-scan-converter.c b/src/cairo-tor-scan-converter.c
index 89ef20f..e271c31 100644
--- a/src/cairo-tor-scan-converter.c
+++ b/src/cairo-tor-scan-converter.c
@@ -1469,19 +1469,19 @@ glitter_scan_converter_reset(
  * shifts if possible, and something saneish if not.
  */
 #if !defined(INPUT_TO_GRID_Y) && defined(GRID_Y_BITS) && GRID_Y_BITS <= GLITTER_INPUT_BITS
-#  define INPUT_TO_GRID_Y(in, out) (out) = (in) >> (GLITTER_INPUT_BITS - GRID_Y_BITS)
+#  define INPUT_TO_GRID_Y(in, out) (out) = ((in) + ((GLITTER_INPUT_BITS - GRID_Y_BITS) >> 1) - 1) >> (GLITTER_INPUT_BITS - GRID_Y_BITS)
 #else
 #  define INPUT_TO_GRID_Y(in, out) INPUT_TO_GRID_general(in, out, GRID_Y)
 #endif
 
 #if !defined(INPUT_TO_GRID_X) && defined(GRID_X_BITS) && GRID_X_BITS <= GLITTER_INPUT_BITS
-#  define INPUT_TO_GRID_X(in, out) (out) = (in) >> (GLITTER_INPUT_BITS - GRID_X_BITS)
+#  define INPUT_TO_GRID_X(in, out) (out) = ((in) + ((GLITTER_INPUT_BITS - GRID_X_BITS) >> 1) - 1) >> (GLITTER_INPUT_BITS - GRID_X_BITS)
 #else
 #  define INPUT_TO_GRID_X(in, out) INPUT_TO_GRID_general(in, out, GRID_X)
 #endif
 
 #define INPUT_TO_GRID_general(in, out, grid_scale) do {                \
-    long long tmp__ = (long long)(grid_scale) * (in);  \
+    long long tmp__ = (long long)(grid_scale) * (in) + ((grid_scale)+1)/2-1;   \
     tmp__ >>= GLITTER_INPUT_BITS;                              \
     (out) = tmp__;                                             \
 } while (0)

Created attachment 106989 [details] [review]
move sample locations wrt edges

Pasting fail.

(In reply to comment #4)
> Created attachment 106989 [details] [review] [review]
> move sample locations wrt edges
> 
> Pasting fail.

I tried this patch, but it does not produce the rotated images.

The problem is that the record* tests clip the rendering in many
2x2 rectangles, in that situation the scan-converter hardly executes
full_row, mainly sub_row (in every row there is a new or end edge)
and my idea above (offsetting half of a subrow) works in that case,
but it breaks the more general fullrow case in which that offset is
not necessary/correct.

commit 5c03b20732b84370950f0c7e5648da86ef45a571
Author: Chris Wilson <chris@chris-wilson.co.uk>
Date:   Mon Sep 29 08:37:56 2014 +0100

    test/coverage: Exercise invariance under mirror symmetry
    
    Massimo noticed that the record/record-flip were not being rasterised as
    identical mirror images due to a half-subpixel offset in the tor scan
    converter. This test attempts to reproduce this error by rendering a
    rhombus around the origin of each cell (that is it generates 4 mirror
    images of a triangle in the 4 different orientations0. The expectation
    is that each pixel in the group is lit identically as the coverage is
    identical.
    
    References: https://bugs.freedesktop.org/show_bug.cgi?id=84396
    Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>

should be a good explicit test of this property. It is marked as a slow test, so needs to be run as

./cairo-test-suite -s coverage-rhombus

(Not that it is that slow and cairo-test-suite should just run tests that are named explicitly.)

Short answer, we need both. We need to take greater care inside tor to not lose precision in the intermediate projections.

Created attachment 107095 [details] [review]
proof of concept

Two other problems are that the grid cairo-tor-scan-converter uses is asymmetric
so edges are snapped to grid vertices on different coordinates on the x/y axis.

And there is a maximum precision issue that prevents increasing GRID_{X,Y}_BITS
too much. With the attached patch #defining them to 7 (not in the patch, 
at lines 118-119), coverage-rhombus passes, but tests with longer edges fail, 
probably because an overflow in certain multiplication or whatever.

Created attachment 107101 [details] [review]
Fix loss of precision from projection onto sample grid

This fixes up the subrow sampling at least. I think the fullrow sampling is probably still broken though...

(In reply to comment #8)
> Created attachment 107095 [details] [review] [review]
> proof of concept
> 
> Two other problems are that the grid cairo-tor-scan-converter uses is
> asymmetric
> so edges are snapped to grid vertices on different coordinates on the x/y
> axis.

Cool. Looks like we are working along the same lines.

Created attachment 107103 [details] [review]
Fix loss of precision from projection onto sample grid

The only issue now is that the asserts are triggering on the overflows in big-line and big-trap.

Created attachment 107104 [details] [review]
Fix loss of precision from projection onto sample grid

And don't forget to bump the precision of the walkers.

Worked through the test suite, and I am happy with the results of the last patch:

commit 03c3d4b7c159a3004071522bac2461e553fec211
Author: Chris Wilson <chris@chris-wilson.co.uk>
Date:   Tue Sep 30 08:44:43 2014 +0100

    tor: Fix loss of precision from projection onto sample grid
    
    The goal is to preserve the precision in the gradients of the edges and
    only apply the projection into the final cell location. We also include
    the half-subrow offset as spotted by Massimo.
    
    References: https://bugs.freedesktop.org/show_bug.cgi?id=84396
    Testcase: coverage-rhombus
    Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>

Now, it's time to answer the question of whether the flipped rendering is now correct...

With the last patch, comparing the output of the test a8-clear
with its 180°-rotated version, shows that all pixels computed
via sub_row are correct, while those with full_row are slighlty
wrong.

I've obtained the opposite result not altering the way e->x.quo .rem
is computed, but adjusting the rest.

The problem is that to share the same walker between full_row and 
sub_row, it would be necessary to use a grid with twice as many y
samples as the number of subrows. Cell corners for full_row and
cell centers for sub_row.

I found one outright bug in cell_list_render_edge():

commit 167561f2823767058e2be3a26131b5f820b35c35
Author: Chris Wilson <chris@chris-wilson.co.uk>
Date:   Tue Sep 30 10:22:41 2014 +0100

    tor: Review full-row walker
    
    When updating the quorem between cells, we would lose the overflow
    increment as it was only applied locally and not preserved by updating
    the quorem.
    
    Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>

Fixing the discrepancy between the fullrow and subrow processing is ongoing.

I regenerated the recordflip references,

commit 95e147bfa05a122541645f32be52cf1902c3a4b2
Author: Chris Wilson <chris@chris-wilson.co.uk>
Date:   Tue Sep 30 14:30:45 2014 +0100

    test: Explicitly flip the reference image for recordflip
    
    Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>

and I will add a new test in recordflip (and probably the other pixel exact transformed replays) for replaying the whole image.

I think the rendering errors are now just the seams between fullrow stepping (e.g. bug-seams). I added

commit 0c42d5c176b27725ac8ab293c3e941be64f51613
Author: Chris Wilson <chris@chris-wilson.co.uk>
Date:   Tue Sep 30 16:14:57 2014 +0100

    test: Add another coverage example demonstrating the seams in tor
    
    References: https://bugs.freedesktop.org/show_bug.cgi?id=84396
    Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>

./cairo-test-suite coverage-abutting

to demonstrate the problem succinctly.

Hmm, bad test. Forgot that it would require ADD to test the coverage.

(In reply to comment #17)
> I think the rendering errors are now just the seams between fullrow stepping
> (e.g. bug-seams). I added
> 

Confirming, with a note: the errors in bug-seams are not full_row,
but the upper half of row 74 is rendered by sub_row whereas the lower
part is rendered by full_row. The two are not complementary.

Skimming the new code I'm not sure whether (lines 795...) it is correct
to use edge->cell there, to me it seems that edge->cell is the x at the
y of first subrow's center and for edges nearly horizontal it could be
slightly off with respect to the x corresponding to the y at the start
of the row. (it could be compensated in the code later though)

Created attachment 107186 [details] [review]
Walk fullrow edges between precise end-points.

For the inside a pixel check, I think cell is correct (the line has to go between the cell end-points), but it does lose some precision when stepping between pixels. I was looking at that, but didn't get my math right when I spotted the bug and went to fix that.

bug-seams is indeed a different class (fullrow does the analytical coverage computation, subrow does the sample coverage) and so there does remain yet another asymmetry bug in tor somewhere.

Nope, you are right. The fullrow walker is analytical and shouldn't be messing around with sample locations.

Created attachment 107189 [details] [review]
Analytical coverage inside the pixel, not sample points

This should be closer...

Wrote a simple 256x256 rasteriser to highlight the issue with sampling along the fullrow.

commit 50b41e214533ea5fd3b64128306b6cb94d353145
Author: Chris Wilson <chris@chris-wilson.co.uk>
Date:   Wed Oct 1 22:50:10 2014 +0100

    test: Add a simple rasteriser to check fidelity of edge rendering
    
    In order to check the behaviour of the analytic rasteriser inside tor,
    let's compare it against a very simple rasteriser that uses a rectiliner
    256x256 sample grid.
    
    Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>

./cairo-test-suite simple-edges

Sadly it also says that my patch is inadequate.

Better. Realised we could do_full_row if insert new edges at the beginning of the fullrow (and have no other edge operations within the row), which fixed up the issue with switching from subsampling to analytic within bug-seams and simple-edges.

commit 950f1e7103a3b4f3405fbb3ee2844ed24b902834
Author: Chris Wilson <chris@chris-wilson.co.uk>
Date:   Thu Oct 2 07:52:05 2014 +0100

    tor: Enable analytic processing for starting rows
    
    If all the edges start at the very beginning of the whole row, we can
    merge them and include check for intersections/endings during the row.
    This allows us to enable fast analytic processing for even the very
    first row on pixel aligned vertices.
    
    Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk

Still the rasteriser is not symmetric though. :|

Created attachment 107344 [details] [review]
increase coverage area precision

There is a loss of precision in the last step of the analytical
coverage computation, that is, the uncovered area does not depend
on the number of subrows and can be computed to a greater accuracy,
improving the overall symmetrical behaviour:

the output images of record{,flip}-paint-alpha-clip-mask become
the 180°-rotated version of each other

and the output of a8-clear is within +-1 from its 180°-rotated
version.

If something like this is considered worth it, perhaps after playing
with GRID_Y or GRID_Y_BITS and EXTRA_Y, a specialized version
of GRID_AREA_TO_ALPHA could be added for the new value of GRID_XY.

Indeed. We could just use the full input precision when doing the analytic pass. We would have to apply a couple of scale factors so that the sampling and analytic generate the same total coverage.

Thanks; fix pushed:

To ssh://git.cairographics.org/git/cairo
   b4a922f..e7acf4b  master -> master

[Sorry; ignore the previous comment.  Posted on wrong bug.]

-- GitLab Migration Automatic Message --

This bug has been migrated to freedesktop.org's GitLab instance and has been closed from further activity.

You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.freedesktop.org/cairo/cairo/issues/187.