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.