Fio:Caching
From Fio
| Line 11: | Line 11: | ||
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: | 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. | A token is a rect representing an image's location and dimension in back surface. It is marked as busy or free. | ||
| Line 24: | Line 23: | ||
A line is a list of tokens. It's height is the max height of all its tokens(plus a tolerance value). | 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'''. | 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. | 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. | ||
| - | + | Finally if there's not enough space left in cache, bad luck for that token. see [[#anchor-cache-overflow|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.(<font color=red>is a dual map needed? i'm in doubt</font>) | |
| - | + | * '''Cache Out''' | |
| - | + | * '''Caching Operation''' | |
| + | * '''When The Cache Overflow'''<div id = "anchor-cache-overflow"></div> | ||
| - | + | * '''Mapping to Image/Frame''' | |
===Isolate Cache from Surface=== | ===Isolate Cache from Surface=== | ||
Revision as of 15:48, 28 August 2006
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.
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)
- Cache Out
- Caching Operation
- When The Cache Overflow
- Mapping to Image/Frame
