Now the problem is this: when moving left to right we might travel a long
distance in the texture map. Imagine a very simple case where the whole
screen is filled by two rather large triangles. Imagine we texture the top
one left to right horizontally. Assume we mapped the texture in such a way
that we also travel left to right horizontally in our texture map. Now by
moving pixe- per-pixel (along the scan line) to the right, we can probably
re-use the 2 right texels as the two new left texels for the next pixel.
So essentially we only need two new texels for every pixel we visit. But
once the first scan line is finished we drop one line and we go left to
right again. What we notice is that the top 2 texels are the same texels
as we used previously to render the first pixel on the first scan line.
So, we could have re-used those texels. The problem is that we went through
to the right so far that these first texels were removed from the cache
(cache is rather small). The cache we have only contains texels from the
right side of the texture. Now the question is, how can we re-use those
texels too? After all the more re-use the higher the efficiency of the cache.
Essentially once the system is up and running optimaly, we would only need
one new texel to be able to render each new pixel.
The answer to our re-use problem is to use a Tile Based Frame Buffer. In
the example above we store everything per scan line in memory. This means
that the final image is stored left to right and top to bottom. Now that
way we lose efficiency of our cache. Now the idea is to use Tiles, or small
rectangles that go left right, top-down too. So it's a bit like storing
many small screens that combined, form the original screen. So if we read
linearly in the frame buffer, we actually read from left to right, but not
until the end of the screen line we read a limited number of pixels (the
exact number depends on the cache size but this will become clear in a minute),
so after x number of pixels we move to the next line and again we store
x pixels and this continues for y lines. So basically what we have is a
small rectangle stored in a linear way in memory. Once that first rectangle
is stored we move to the next one located to the right of the first. And
so we continue left to right, top to bottom storing the screen as a sequence
of small rectangle or tiles. So it's a bit like a puzzle with rectangular
pieces. Each puzzle piece is stored linearly in memory (this means continuous,
the color value for the most right pixel on a line and the most left pixel
on the next line are stored next to each other in memory).
Now what's the use of this different storage technique? Well there are two
advantages. One is you will suffer from fewer page breaks. I already repeatedly
explained what a page break is (remember the analogy with the notebook...
see this article.). If your frame
buffer is stored in a normal way, chances are very big that the next scan
line is stored in a different memory page. So roughly said, every time you
move to a new line you would suffer a page break. So imagine a very vertically
elongated triangle that spans from the top of the screen to the bottom.
Rendering this would cause a page break (and thus a delay and stall) for
every new line. Now when we use tiles, we have parts of multiple lines stored
linearly ( = no page breaks) in memory. So the pixels of the next line are
stored in the same memory page. Using this technique only results in a page
break at the end of every tile (rectangle). Its obvious that having a page
break once every 5 lines is more efficient than having 5 page breaks because
you have jump to a new line 5 times.
What is the link with the texture cache? Well as I said, the texture cache
has a limited size and we want to re-use the bottom texels of our first
line too. Now with this small tile based approach we can do that. After
all, we move to a new scan line not at the end of the screen but at the
end of the much smaller tile! This means that the texels are still present
in the cache and we can re-use them.