Fio:Caching
From Fio
Contents |
Image Caching
Now Fio's renderer is implemented using DirectX(8.1). To render fast in DX images should be first loaded into back surface then blt onto the primary surface(what you see on the screen). For the video memory which hold the surfaces is limited - it isn't big enough to hold an entire level, we need an image cache to manage the back surface:
- load only images need to show up on the screen into back surface;
- and unload those ones out of screen (when the map scrolls, critter steps outof viewport, dialog sinks etc.);
- tell the renderer where to find the cached image on the back surface;
- avoid duplicated images load into back surface.
How It Works
The cache is basically a big rect(represent the back surface) and will be fraged by tokens(represent the dimension of an image) when caching in/out happens. These tokens will be arranged line by line from top to bottom of the cache. When renderer need to draw an image, it'll ask the cache to find out where the image is located then use the returned rect to blt the image from back surface onto primary surface. Let's check the details:
Token and Lines
A token is a rect representing an image's location and dimension in back surface. It is marked as busy or free.
When busy, it means an image is loaded into this token in the cache.
When it's free, it can be:
- occupied to be busy;
- merged with it's neighbour(s) which is also free into a wider token;
- fraged into 2 narrower tokens - one is busy, the other is free.
A line is a list of tokens. It's height is the max height of all its tokens(plus a tolerance value).
Cache In
When the game is first loaded, all images of the first screen in the view port need to be loaded into backsurface. Cache is virgin now. To use cache rect effectively, firstly we sort all images into a list based on image's height. And start from the left top of the cache, we create a new line to hold the new cut token(token1 : top = 0, left = 0, bottom = top + image1.height, right = image1.width) for the first image in the list, then cut a token(token2 : top = 0, left = token1.right, bottom = image2.height, right = left + image2.width) for the second image, then the third, ... when we reach the right bound of the cache, we got a line of tokens representing images postion in back surface. And we set the line's height as the max height of these tokens. Then start a new line under the first line, and tile the token from left to right, top to bottom - this approach is called tiling.
After tiling, the cache is not virgin any more. When a single image need to cache in, first we'll find a line high enough to hold that image. Then try to find a free token in that line. If a proper free token is there, we occupy it or frag it. If we can't find a wide enough token in that line, just step to next line. If a token can't stuff into any existing lines, we need to cut a new line under the last line of cache.
A typical back surface snapshot when game loaded(red crossed tokens are cached out):
For we don't erase the old image - just draw the new one over the old one in back surface when caching in, it looks a little messy - but the renderer doesn't care.
Finally if there's not enough space left in cache, bad luck for that token. see When The Cache Overflow
When an image is cached in, we'll do a dual-mapping between the token and the image(using hash table now) to allow quick find from image to token or reverse.(is a dual map needed? i'm in doubt)
