   Terrain engine--reducing memory usage
  So I''m working on the second version of my terrain engine, after all these months since the first. Amongst other things, I''m trying to cut down on the memory usage. Currently the memory usage breakdown looks something like this:Raw data read from bitmap: ~1 MBProcessed vertex data (3D coords, diffuse color): ~16 MBIndices (unsigned int array): 24 MB (!)Quadtree: ~200KNow what concerns me most here is the size of the index array...it''s a 1025x1025 scape, which means it sports a solid 6 million   indices for over 2 million faces.Now, I thought changing to an unsigned short array, but that won''t work; there''s a good 2 million vertices. Other ideas:1) Stripify this bad boy (save massively on indices)2) Use smaller scapes3) Load quadtree sections at runtime as needed rather than all at once at init time.I''m reluctant to use #2, because I really want some big scapes  but honestly, it would be entirely possible to use multiple scape objects. #3 I don''t want to use, since the system is still in early stages and I don''t want to introduce the complexity and infrastructure required to deal with runtime caching and pre-loading. #1 seems like a good idea, but I''m not sure I want to, because it''ll realy complicate the geometry, and I''ll have to redo the quadtree somehow to deal with strips, which I''m not looking forward to. I''m also wondering if the memory is really a problem at all; the total system uses ~50MB, with a pretty huge scape. Lastly, I could use multiple scapes and precache those at runtime instead. At the same time I could use smaller scapes, making memory more efficient and maintaining a large world. I''d only have to write the infrastructure for managing entire scape objects for loading/unloading, rather than doing it at the internal scape quadtree level.I guess this isn''t so much a question as a rant, but I''m looking for some opinions as to what the best course of action might be. 
  Here''s what i doOnly Load up the patches that you need. I Load up one within a certain radious and unload the ones past that radius.When you load the patch create its quadtree vertex buffer and texture. When u step though the quad tree for culling you then add the indices you need. And dont have every texture for every patch totaly unique. If you use 4 base textures and blend them together it uses heaps less memory at runtime and storage;  Use an index buffer. Since the indexing of the vertices in a patch is the same for all patches you just need to store a single index buffer. At least this works for brute force approaches and block based LOD like GeoMipMapping. In the case of geomipmaps you would of course need one index buffer per LOD level and a set of buffers to enable connections between patches with different LOD.;quote:Original post by Promit  Processed vertex data (3D coords, diffuse color): ~16 MBcan be helped.quote:Indices (unsigned int array): 24 MB (!)definitely can be helped, youre not really indexing every single vertex, are you?quote:Quadtree: ~200Kdepends on your needs. what are you storing in each node?quote:Now what concerns me most here is the size of the index array...it''s a 1025x1025 scape, which means it sports a solid 6 millionindices for over 2 million faces.first: dont do that. as mentioned above, index one chunk with a nice size (say 33x33) and use an offset into the vertex array/buffer.second: NOW use shorts instead, some cards cant handle indices above 65k anyway.quote:1) Stripify this bad boy (save massively on indices)if you dont use lod and always draw rectangular patches its worth thinking about. else it might not be worth it.quote:2) Use smaller scapesi never get tired of mentioning that: far cry uses 1024x1024 maps and its looking huge.quote:3) Load quadtree sections at runtime as needed rather than all at once at init time.keep the nodes small and throw out all pointers. you dont need them for a complete quadtree, because storing all nodes linearly will let you traverse it by just using indices (bitshifts and inc/dec).struct SCNode { float[3] Center; float Radius; unsigned short Data;};thats the minimum, storing only center and radius for sphere culling (sounds "crude" but its fast enough and if you like you can still to box culling for the leaf=terrain chunk only) Data is actually just the index of the terrain chunk in an array (you could use a pointer, but shorts are smaller).quote:#1 seems like a good idea, but I''m not sure I want to, because it''ll realy complicate the geometry, and I''ll have to redo the quadtree somehow to deal with stripsthen something is strange, because the kind of primitive you use for rendering shouldnt affect your tree.also, you can keep your vertex buffer smaller if you feel like it. do you really need color info? you could store offsets for each chunk and in that way limit all chunks to coords of 0-32 (at the cost of a translation before drawing each chunk). so youd store 3 shorts per 33x33 chunk (youd have 1024 of them) and could reduce your vertices to a single float (you could store just three bytes and it would be much easier, but at least on my machine vbo will have horrible performance with anything but floats). your float would look like this: xxyy.zz and getting the real coords would require a vertex program and a few fraction and mul instructions (that might have the most impact on speed, so consider it last resort.. i might need that for 2048x2048 terrain, where the vertex positions alone would be 50mb).quote:Lastly, I could use multiple scapes and precache those at runtime instead. At the same time I could use smaller scapes, making memory more efficient and maintaining a large world.dont. at least not for the size youre planning. your vertex buffer should be about 12mb, 4 if you really need to make it small. indices for a single lod are 2.1kb and the tree would be about 42kb.a very early preview of the things mentioned above can be found in the framework here:http://festini.device-zero.de/downloads/index.shtmlmost things are done via console, other keys are cursor (move) page up/down (move), middle mouse button to free the cursor, your typical console key ^ (might be a ~, not sure about us layout). a will just rotate a plane and bounce that point with the annoying sound.the first tree created is a 2048 root with 32 leaf size. look for those numbers in the code and you can play around with it (still not commented or cleaned up). oh, using fragment programs etc. but no vertex "compression". im still hoping to get around that "floats only" limitation of vbo instead of using that ugly hack (btw. simple vertex arrays dont have any problems with that, display lists and maybe cva shouldnt have either). ;  > i never get tired of mentioning that: far cry uses 1024x1024 maps and its looking huge.What?! Really? Surely they''re somehow creating detail procedurally then that''s not in the map file? It''s not that blocky that 1m is the resolution, and I''d say the map width is something like 1km at least.quote:keep the nodes small and throw out all pointers [..] thats the minimum, storing only center and radius for sphere culling (sounds "crude" but its fast enough and if you like you can still to box culling for the leaf=terrain chunk only)Right on. You could save a bit more by storing Radius as a short - 64k values are enough. The cost of ''unpacking'' to float is outweighed by power-of-2 node size: indexing is significantly faster (except on P4), and your data is much(!) more cache friendly.BTW, anything smaller than 16384x16384 isn''t large  My CLOD terrain engine managed 8192x8192 on my older 256 MB, GF2 MX system. Its mem usage was 5.33 bytes / height map point (obviously, it had to cope with paging - that didn''t fit in memory). A better space-filling curve would have brought it down to 4 bytes, and crazy compression of the SCNode equivalent to an incredible 2, but I never got around to it. Maybe later Anyway, the point of that rambling: Promit, have you considered CLOD? Memory requirements are much lower, although you pay about 80 CPU clocks per output triangle (mesh updates can be done in the background, when there''s time - a few per second is enough). ;quote:Original post by Jan Wassenberg  What?! Really? Surely they''re somehow creating detail procedurally then that''s not in the map file? It''s not that blocky that 1m is the resolution, and I''d say the map width is something like 1km at least.judging from the demo its a 1024 heightmap with a scale of 2. they talk about 2km view distance on their site and it would be about the size id have guessed for the island it, so it would more or less fit and mean its actually 2"meters" between each point. in some parts you can tell, because its not too smooth from up close. i guess moving slow and low to the ground together with a lot of detail and vegetation can result in a bigger "feel" than huge heightmaps.quote:Right on. You could save a bit more by storing Radius as a short - 64k values are enough.good point. depending on the used scale rounding up to the closest integer might even be acceptable (after all spheres are just a crude approximation anyway so 122.3 or 123 wont make much difference)quote:BTW, anything smaller than 16384x16384 isn''t large  *cough* i was already breaking my head figuring out a good way to do 4096 maps. fortunately by then the far cry demo came out and i  could stop cooking up weird methods to compete with their terrains. what i had in mind would mean storing a seperate vertex buffer per lod so you can load them independently, only keep the lowest level in memory for the whole map and load higher levels in areas closer to the player. but something is telling me, that this is so obvious its a stone old method and i would just have had to open my eyes to find dozens of ressources about it.;quote:judging from the demo its a 1024 heightmap with a scale of 2. they talk about 2km view distance on their site and it would be about the size id have guessed for the island it, so it would more or less fit and mean its actually 2"meters" between each point. in some parts you can tell, because its not too smooth from up close. i guess moving slow and low to the ground together with a lot of detail and vegetation can result in a bigger "feel" than huge heightmaps.hmm, ok. It looks quite good for 2m resolution - I''m surprised. My engine was for flying - different perspective, needs to be much larger.quote:*cough* i was already breaking my head figuring out a good way to do 4096 maps. fortunately by then the far cry demo came out and i could stop cooking up weird methods to compete with their terrainshehe  There''s tons of terrain engines, and CLOD schemes. Röttger''s algorithm has a fairly low memory footprint without much work; Lindstrom-Pascucci''s "Visualization of Large Terrains Made Easy", what I implemented, is an elegant and effective method. I haven''t tried ROAM2.CLOD is universally panned for the CPU cost, but it isn''t that bad. My optimized mesh refine code (this is a top-down mesh generation algo, vs. bottom up, as in Lindstrom-Koller) is blazingly fast - I''ve seen a ROAM implementation which advertised 500 clock / tri optimized code, while this takes 80, worst case. The asm implementation is 2.5 times as fast as the compiler''s code (VC7.0 with ICC7; haven''t tried it with VC7.1 and ICC8). Also, CPUs will get faster, but more slowly and with much effort; I can see multiprocessor systems becoming popular as a cheaper way to get more speed. In this case, dedicating one processor to creating meshes would be ideal.Oh BTW, have a look at vterrain.org - lots of stuff there ;  If your video card supports vertex shaders you can divide your vertices into two parts: the first contains the 2d vertex coordinates and texture coordinates, and the second contains the vertex height (as a 1D texcoord), the normal vector, and any other unique data.  In the vertex shader you combine the 2D vertex coordinates with the height to produce a 3d coordinate.  When you're dealing with a single terrain mesh this doesn't help, but if you divide your terrain up into multiple segments, this saves alot of memory per segment, since you only need one instance of the first buffer.If you have a 1025x1025 terrain segment, for example, and assuming you need a 3D vertex coordinate, a 2D texture coordinate, and a 3D normal vector. . . the normal implementation would mean a bit more than 32 MB of memory is required.  Splitting the terrain into 16 257x257 segments and splitting the vertices means that only a little more than 17 MB is required -- quite a substantial difference!(NOTE: I've only done this in OpenGL.  I don't know how it would be done, if it is at all possible, in Direct3D.)   [edited by - Ostsol on February 5, 2004 1:09:13 PM];  Try not to include texture coords.  you can easily calculate them from your positions in the vertex shader. ;  hehe... a few more things like that and you''ll have your 4k*4k terrain up and running with less than 1mb *lol*wonder why it didnt come to my mind, that using translation offsets for each chunk would mean a lot of redundant x,z coords that you only need to store once. only thing i need to check is if it will work without cracks if one vertex ends up in two slightly different positions due to rounding errors. 