   geometry cache - an angorithm
  helloI should implement geometry caching in my rendering system. Unfortunately I have no idea how it could works. It can manage geometry againts video memory or usage. Maybe both. I don't see strict rules which says "this geometry must be in system memory and this in video memory". Does anybody know an caching algotithm?   
  Look at "vertex arrays" and "vertex buffers" (don't know the exact terms used for D3D). They describe ways to deal with geometry in system memory, AGP memory, and graphic cards memory. The selection between the different memory types depend on how often the geometry is changed (static vs. dynamic objects). Formerly one could specify the kind of memory directly, but it seems that the more modern way (at least used by OpenGL) is to let the gfx driver decide that.A better geometry caching system also implements some kind of estimation which geometry should be unloaded if not enough memory is available. E.g. the LRU ("least recently used") caching scheme is popular in this sense.   ;  D3D use vertex buffers. Well, D3D can manage their own resources (buffers, textures). So I can let they decide which of them must be in video memory.This is good idea. Also, LRU can be mexed with MRU ("most recently used"), right?I have one more questions. How much memory usualy are used for geometry data? I think about video memory.   ;  Err, mixing LRU and MRU? Seems me spurious. Well, when I say using LRU I mean that the least recently used block is re-used (say unlinked from the geomatry data used so far, and immediately linked to the currently pending geometry data) as soon as no more free blocks are available. Perhaps you mean something else...Quote:Original post by TheDmDWell, D3D can manage their own resources (buffers, textures). So I can let they decide which of them must be in video memory.Yes and no. You have at least hint the driver how dynamic the geometry data is. E.g. if you have a mesh that is altered by the _CPU_ due to bone animation, then it is likely that the geometry changes every frame. But frequent reading/writing of geometry data from/to video memory is sub-optimal, so you have to say "this geometry data is dynamic" with the intention that the driver don't pushes it into video memory.Quote:Original post by TheDmDHow much memory usualy are used for geometry data? I think about video memory.This is the question about the holy grail :) Using too many too small buffers will decrease the performance dramatically. Using a single huge buffer will decrease performance dramatically, too. The overall opinion here on GDnet seems to be to use 4MB blocks, and doing self (i.e. by your app/engine) a block oriented memory management on these blocks.E.g. if you have a low poly mesh for an avatar, you may have, say, 500 vertices. All 3 vertex co-ordinates are given by floats. You also push a normal with each vertex since you use smoothed meshes (another 3 floats). Moreover, you have 2 textures associated with the model (2 floats per texture co-ordinate). Then you need in total500 * [ 3*sizeof(float) + 3*sizeof(float) + 2*2*sizeof(float) ] = 20000 bytesfor the mesh.Make similar estimations with geometry you expect, and you get an idea of what you will need. Additionally, I go the way to build a statistic during running the engine. That is, after a run I know how often blocks of given sizes are requested, and how often a miss has occured. So I get a clue of how good/bad a memory layout is adapted.   ;  What is a single block? Is it a 4MB vertex buffer? This is not clear to me.Or block is a part of that 4MB buffer?I will make tests to adjust engine settings. Without caching system there is nothing to adjust ;);  It seems that the following method is usual (but notice please that other ways exists, too; there is no golden ways, I think):Allocate several 4MB (or the like) sized blocks of memory from the gfx API. Some for video memory, some for AGP memory, ... Then build an own memory management on top of these blocks. Virtually divide the blocks of a particular memory kind into sub-blocks, e.g. 128 sub-blocks of 2k, 64 sub-blocks of 4k, 32 sub-blocks of 8k, ... something like this. Then do a LRU caching on all sub-blocks of a given size and memory kind. That means that you need to have management structures in your engine. These management structures keep track of the size of the sub-block, the start address of the block, and what geometry is currently attached with the sub-block.Now, if the memory manager for the, say, video memory is asked for 3800 bytes of memory, the manager looks into its list of sub-blocks (okay, it should be a list of lists of sub-blocks to speed up searching) until it founds the list holding sub-blocks of at least 3800 bytes. That list would actually hold sub-blocks of 4k size, what is the next higher size. The list of this blocks is sorted w.r.t. the LRU scheme. That means, the first node in the list refers to the least recently used sub-block. Unlink the geometry from the sub-block, link the new geometry to it, unlink the sub-block from the head of the list and relink it to the end of the list. With this step you have guaranteed the LRU policy, since the new allocation is of course "most recent".Ah, something else: Try to deal with not more than 65536 vertices per block. So you could use small size 16 bit indices.The management system described above os more or less originating from Yann L. You may look around in GDnet forum here, since there are more threads dealing with this issue.   ;Quote:Original post by TheDmDhelloI should implement geometry caching in my rendering system. Unfortunately I have no idea how it could works. It can manage geometry againts video memory or usage. Maybe both. I don't see strict rules which says "this geometry must be in system memory and this in video memory". Does anybody know an caching algotithm?1. Maybe you could explain why and whether you really need this ? 2. What kind of game is it (indoor/outdoor) ? 3. Does the game have to run on cards with less than 64 MB of VRAM ? 64 MB is plenty for high polycounts. 4. How many polys does an average level of yours have ?5. How does your vertex format look ?Maybe a basic vertex compression could help here. There`s no reason to spend 12 bytes on a normal. 6 is enough (even 2 can be enough, but that requires few more instructions in your vertex shader to decompress), and depending on what else you need in your vertex structure, your vertex could easily occupy half of your current size just by using 2 Bytes per float instead of 4 Bytes. I have yet to see a mesh that shows artifacts with this compression - I`ve tried buildings,pillars, interiors and characters, and you can`t spot a difference even with characters that have 10k tris (and thus a quite high vertex density).If it`s an interior game, very simple solution could be to get rid of those rooms that haven`t been visited for some time (e.g. 20 seconds assuming they can`t be seen from other places).   ;  haegarr:This method which you described is good for me. Now I thnking about blocks. It must be a 4MB vertex buffer. There is no way do share video memory betwen various objects in Direct3D9. Is it right?I think index data could be cached in this same way. Currently I use 16-bit indices, so limitation is not problem ;)I'm found a few discussions, most about shading system. I will try to find something else.VladR:Ok, folowing your five points:1) Our engine needs caching because there are many meshes with very different vertex count in a single scene. For example characters have 4K polygons, terrain have 30K, particles are very veriable 2 to 12K polygons (or more). I must improve performance, now it is very poor.2) Actually it is not a game, just an engine. We want to deal both with indoor and outdoor environments.3) I suppose yes. It sholud run on cards without large amount of memory.4) As many as it possible without lossing much performance. There is not constant value. I don't know which value can be good.5) Out vertex format is variable. Is dependend to an effect applied to geometry.Using half-precision float should be good. Modern hardware have support for it, right? Smaller amount of data can bost performance. Now this optimalization is not in my hands. In future I will try to make deal with half-precision.   ;Quote:Original post by TheDmD1) Our engine needs caching because there are many meshes with very different vertex count in a single scene. For example characters have 4K polygons, terrain have 30K, particles are very veriable 2 to 12K polygons (or more). I must improve performance, now it is very poor.All of the features that you mentioned require a specific handling of their video-memory location, so they wouldn`t be a candidate for a general caching algorithm:1.1 Terrain - Since it all depends on how big your terrain is and how much video-memory are you willing to leave for the terrain, it can`t be a candidate for general caching algorithm. The most basic terran caching could be made as this: terrain consists of 9 chunks so that no matter how you rotate the camera, all visible polygons are from those 9 chunks. You are standing in the middle chunk and as you move forward, you`re updating the VBs for those new chunks that are appearing in your frustum.1.2 Particles. Again, their memory location and type (dynamic/static) depends on the nature of the effect. Are you generating plenty new particles during the effect, or reusing those that died ? I don`t think this is an area where you should apply some general geometry cache algorithm, especially if your particles have such a huge range (2k-12k).1.3 Characters - What if all types of characters are on-screen at the same time ? What use is any geometry caching in such case ? This is very application-dependent, so this should be left to an actual application (is it multiplayer/RPG game where there are dozens of various characters or just some basic 2-3 meshes ?). Quote:Original post by TheDmD3) I suppose yes. It sholud run on cards without large amount of memory.You just suppose  ? You should be damn sure about your minimal configuration, especially about gfx card or you could end up optimizing something that may not need optimization in the end thus actually slowing down the framerate because in the end it might be CPU-intensive due to geometry caching.Seems like possible over-engineering here, but if you`re paid for this...Quote:Original post by TheDmD4) As many as it possible without lossing much performance. There is not constant value. I don't know which value can be good.Loosing much performance on nVidia TNT1 8MB or nVidia GF7900 512 MB ? Again, you should sit down with your colleagues/bosses, discuss it and draw a line somewhere - anything below this won`t run whatever application is made with this and say that this is the average configuration for which we`ll be optimizing.These days it shouldn`t be a very big issue to ask for a shader-only card, thus you know that 64 MB of VRAM is guaranteed.Even Unreal 2.0 engine (that is known to be extremely over-engineered) had to draw this line somewhere. These days, no one cares for 32MB gfx cards. If your engine shall be finished next year, it`s quite possible that GF4MX&GF2TI cards won`t be able to handle the polycount/effects you are planning in your engine.But, I could be wrong, provided you`d "fake" per-pixel effects with higer mesh tesselation, thus allowing the game to run even on those cards. Or maybe you`re writing an engine that is supposed to run on notebooks (very specific market - ~3GHz CPUs, usually horribly slow gfx).Quote:Original post by TheDmD5) Out vertex format is variable. Is dependend to an effect applied to geometry.Obviously. But an example would surely help.Quote:Original post by TheDmDUsing half-precision float should be good. Modern hardware have support for it, right? Smaller amount of data can bost performance. Now this optimalization is not in my hands. In future I will try to make deal with half-precision.Unfotunately not. They have support for 64-bit not 16-bit. But decompression inside Vertex Shader takes only couple instructions, and with some assumptions, can be actually free.;Quote:Original post by TheDmDNow I thnking about blocks. It must be a 4MB vertex buffer. "Must be" is a hard formulation. I think its best to try it. If all works well you could consider to play a bit with the size, looking whether or not other sizes perform better.Quote:Original post by TheDmDThere is no way do share video memory betwen various objects in Direct3D9. Is it right?I'm not a D3D expert, but AFAIK it is possible. You allocate a vertex buffer by overhanding a count of vertices and a vertex description. So perhaps you are restricted by the vertex kind (say one block per vertex kind). A vertex array seems to be allocated even w/o a pixel description. Since you can invoke drawing with an index offset and index buffer length, you shall be able to render only parts of the vertex array/buffer, and hence you can also hold vertices of different meshes inside one array/buffer.Quote:Original post by TheDmDI think index data could be cached in this same way.Correct.   