[Yafray-devel] Antialiasing idea

[Guillermo S. Romero / Familia Romero]

Hi:

I have been reading POVRay code, and this is the algorithm I got from
it:

- It is recursive.

- It uses a grid of samples, composed of the colour RGBA and a flag to
check if already computed, which I would call slot (struct, object,
whatever way you want to look at it).

- The grid per pixel is composed of 2 to the power of one less than
max sampling level, plus one. See below for nicer formula. :]

- The grid caches results, both when moving to next column and to next
row. Next row is easy: bottom set of samples is placed as top set for
next pixel row.

  For columns, as it stores all the samples of a pixel row, it is just
referencing the proper items.

- Thus as global init, create 2^(level-1) + 1 lines, with (ImageXPix *
2^(level-1)) + 1 sample slots each.

- The per pass init is to clean up the unused data, and move the last
line so it becomes the first.

- Graphic:

  Lets suppose level 3, so a pixel would be, level by level and
supposing you have to sample all, this graph of samples:

1       1      1   2   1      1 3 2 3 1
                              3 3 3 3 3
           ->  2   2   2  ->  2 3 2 3 2
                              3 3 3 3 3
1       1      1   2   1      1 3 2 3 1

 The number of samples is, in each level:

2^(1-1) + 1    2^(2-1) + 1    2^(3-1) + 1
2 rows         3 rows         5 rows
2 columns      3 columns      5 columns
4 samples      9 samples      25 samples

  If you pack a full line of such pixels, you realize the last column
is the first of the next pixel, confirming (ImageXPic * 2^(level-1)) +
1 (all pixels reuse, except the last one, thus the final + 1).

  This is a pixel row, with six pixels columns:

  Pix 1   Pix 2   Pix 3   Pix 4   Pix 5   Pix 6   Pix 7
|       |       |       |       |       |       |       |
1 3 2 3 1 3 2 3 1 3 2 3 1 3 2 3 1 3 2 3 1 3 2 3 1 3 2 3 1 <- B
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
1 3 2 3 1 3 2 3 1 3 2 3 1 3 2 3 1 3 2 3 1 3 2 3 1 3 2 3 1 <- A

1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2
                  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9

7 pix * 2^(3-1) + 1 = 29 samples slots
2^(3-1) + 1 = 5 lines

  I hope you do not get lost with the numbers, the idea is to show how
much sample slots are needed for cache.

  When starting to calc a new pixel row, the samples of row A are put
as row B, and the rest cleared (the "used" boolean would be enough, if
you make sure you always overwrite the RGBA info). Or you request some
new containers, remembering you can not free A, but have to use as B
(so it will be freed for next scan line).

- For each square, it measures the difference among the corners, if
over a user limit, it requests the calculation of the four corners of
each square. Thanks to the storage, it only calculates five new
samples. This is the recursive part.

- It mixes the four containers (0.25 each), put it in the container it
got when called and returns.

OK, I think that is all. If anybody want to read the POV code to
verify what I got, it is around line 2106, trace_sub_pixel(), in
src/render.cpp of the 3.50c version.

Comments? Typos or logic errors? Did I missed anything? Hints about
this in nice C++? How would threads fit into it?

GSR