Terrain paging and rendering algorithms.

no input?

Never done it, might do it in the near future though:)

I wouldn't run another thread, always work a lot slower for me. The main thing i guess would be to page from disk to mem to renderer (AGP mem). Maybe running another application itself to do the loading with shared mem access to yours then if the loader blocks yours will still be running strong (might get into semaphores and crap then:S).

Each chunk should be the same size to keep the loading consistent. Do a radius check to determine what to load.

As for the loading itself not sure if it would be fastest to load the whole chunk in one go or to do it sequentially over a few frames (so load like 1MB/2MB at a time or even smaller chunks). Loading from disk will be slow and it might not be any faster doing it in chunks (app blocked more often).

For the rendering i would use CLOD, since you will most likely have each terrain piece in the same size chunk it should be easy and you could store LOD levels easily too.

If you have large terrain that you want paged in and you want it all to be viewable at any given time (i.e. it all has to be loaded to memory if the viewer is in a position to see all of it) use chunked LOD. If you have large terrain that you want paged in and you want to restrict the contents of memory to a subset of the entire terrain use geomipmapping.

I had some conversation with Thatcher Ulrich about this a long while back, but it's late so I'll elaborate tomorrow if no one answers your questions.

Hey that would be great if you had some time later on outRider, I appreciate the comments from both of you guys.

The reason I posted this was because I was working on an implementation using geomipmapping, but was really leaning towards changing the implementation to using chunked lod. The reasoning was because I wanted to have a large viewing distance and the more I read about chunked lod, it seems easily to load/unload chunks and keep what I need in memory and page it in and out.

The only problem I had is that I haven't spoken to anyone regarding chunked lod and paging. I have heard it is one of the best methods for such a thing, but haven't heard it from someone who has either discussed this at length, or implemented something similar.

Since I'll be doing this soon probably :) decided to do a few searches and one turned this up...

chunked LOD maybe with disk paging

I believe it uses paging but might be wrong since I haven't looked at the code myself, might be helpful anyway :)

You might want to look at this paper (and video demonstration). There is also alot high quality papers on other subjects there.

Great thanks for the links guys, I am definately going to read up on these today.

There are two considerations when dealing with Geomipmapping, Chunked LOD, and paging in out-of-core data.

With geomipmapping your terrain has to be memory at the full detail level, both VRAM and system memory (i.e. you create static vertex buffers and never touch them again). The different LODs are achieved through the index buffers, so you can cut down on the number of vertices processed and triangles rendered this way, but you can't cut down on memory usage without some restrictions. The only way to restrict memory usage is to not have your entire terrain in memory at once.

Imagine that your full terrain is 8*8 patches (a patch being a square grid of N*N vertices). If you only have enough memory to store 9 patches then only a portion of your terrain will be in memory, represented by a 3*3 subsection of your 32*32 terrain. When the viewpoint moves you must unload either a row or column of patches from one side and load a row/column to the other side. Observe the ascii art below, the x marks represent the area in memory. If you move right you'll have to load in the 3 patches in column 4 while unloading the 3 patches in column 1.

  0  1  2  3  4  5  6  70[ ][ ][ ][ ][ ][ ][ ][ ]1[ ][ ][ ][ ][ ][ ][ ][ ]2[ ][x][x][x][ ][ ][ ][ ]3[ ][x][x][x][ ][ ][ ][ ]4[ ][x][x][x][ ][ ][ ][ ]5[ ][ ][ ][ ][ ][ ][ ][ ]6[ ][ ][ ][ ][ ][ ][ ][ ]7[ ][ ][ ][ ][ ][ ][ ][ ]

Chunked LOD works differently in that while you load your entire terrain in memory, you load it based on the current LOD. So, in memory you have all your patches, with the closest patch being at full detail, the farthest patches being at minimum detail. You then turn around and stream all of this to VRAM. Your vertex buffers can't be static like they are with Geomipmapping. Now obviously the larger your terrain the more memory you'll use, even though your terrain isn't being stored at full detail, but with this method you can store a lot more patches than Geomipmapping in the same amount of space. Normally you'll have the closest patch stored at full detail (1), the surrounding patches at 1/2, then 1/4, etc, but you can be more or less conservative, storing at 1, 1/4, 1/16, etc, depending on how much memory you have. The point is that your entire terrain is viewable at any time if necessary. The downside is when you move you'll have to load every patch at it's new LOD from disk and then send to VRAM, not just the 3 adjacent as we did above.

1 = 1/1, 2 = 1/2, 8 = 1/8, etc.

  0  1  2  3  4  5  6  70[8][8][8][8][8][8][8][8]1[8][8][8][8][4][8][8][8]2[8][8][8][4][2][4][8][8]3[8][8][4][2][1][2][4][8]4[8][8][8][4][2][4][8][8]5[8][8][8][8][4][8][8][8]6[8][8][8][8][8][8][8][8]7[8][8][8][8][8][8][8][8]

[Edited by - outRider on June 16, 2004 4:39:02 PM]

I would probably use CLOD, as it will restrict memory usage to the currently visible geometric set. Far away patches will be in memory at low LOD, taking less memory than near patches.

To avoid constantly reloading patch LODs while moving, I'd use some kind of temporally coherent precaching system: if you move in a particular direction, then it's likely that incoming patches will eventually need higher LODs as they get nearer to the camera. So preloading a set of LODs might be useful here. Also, patches that just went outside the view frustum can't just be unloaded, since the user might suddendly turn around. If you use occlusion, you can unload high detail patches that were occluded for several hundered frames in a row, as they will likely be occluded further.

Exploiting temporal coherency using usage heuristics and statistics can be very useful to determine what to load and unload. Basically, don't simply load what is visible on the current frame, but try to preload what will probably be visible within the next frames. There are many parameters you can exploit: for example, if the user stands still, you can reduce framerate and have more CPU time left to precache geometry until the cache is full. That way, the probability that geometry required during the next frames is already loaded is higher. As soon as the user starts to move, reduce the streamed data from disk to the minimum required.

You'll need an efficient caching system to manage the geometry both in system RAM, as well as in VRAM. I would use a second thread for the disk to system transfer, but I would do the system RAM to VRAM/AGP management within the rendering thread itself.

You can also reduce HD access in two ways. First, when patches get farther away you don't need to load a lower LOD patch from the HD, instead retrieve the data from the patch already loaded in memory. All you have to do is copy half the vertices to the new LOD patch and discard the old one.

When patches get closer you don't need to load a higher LOD patch from the HD, instead just keep the lower level copy, which represents half the higher version and read the remaining half from the HD.

This way you completely eliminate HD access for demoted patches and cut HD access to half for promoted patches.

Note that this might be slower due to the fact that HD access is faster when it's sequential and you would be skipping long runs of vertices. Also you'd be reading from VBs which means it would be slow because reading from AGP is slower or they'd have to be put into system memory, making upload slower, but it might still be faster because your accessing the HD half the time and you're reading in half the data. Your other option is to store your patches at each LOD on disk (which is the method Ulrich uses), instead of just the highest detail patches, thereby making the loading of each patch straightforward, since it's pre-prepared, though you would need to preprocess your heightmap.

Quote:

Original post by Yann L I would probably use CLOD, as it will restrict memory usage to the currently visible geometric set. Far away patches will be in memory at low LOD, taking less memory than near patches. To avoid constantly reloading patch LODs while moving, I'd use some kind of temporally coherent precaching system: if you move in a particular direction, then it's likely that incoming patches will eventually need higher LODs as they get nearer to the camera. So preloading a set of LODs might be useful here. Also, patches that just went outside the view frustum can't just be unloaded, since the user might suddendly turn around. If you use occlusion, you can unload high detail patches that were occluded for several hundered frames in a row, as they will likely be occluded further. Exploiting temporal coherency using usage heuristics and statistics can be very useful to determine what to load and unload. Basically, don't simply load what is visible on the current frame, but try to preload what will probably be visible within the next frames. There are many parameters you can exploit: for example, if the user stands still, you can reduce framerate and have more CPU time left to precache geometry until the cache is full. That way, the probability that geometry required during the next frames is already loaded is higher. As soon as the user starts to move, reduce the streamed data from disk to the minimum required. You'll need an efficient caching system to manage the geometry both in system RAM, as well as in VRAM. I would use a second thread for the disk to system transfer, but I would do the system RAM to VRAM/AGP management within the rendering thread itself.

Hmmm very interesting with the temporal coherency, i'll have to give that system a try to :)

Another question, I believe u mentioned that you were using ABT's for your scene just wondering how you are actually storing the CLOD chunks in there. Do u insert another class with no geometric data, just an AABB that when in view is asked to populate its data to the render queue and it just sends down whatever LOD level it is determined to be. This is what I am planning on doing but maybe there is a better way.:)

My reasoning for not using another thread was that disk accesses are slow and if that thread blocks then the whole app will block (since its user not kernel space) so it wont be any slower doing it in one thread. The other thread just seems to be kinda wasted (might have missed something), probably wrong about this.

While the subject of paging terrain is about, even though I've decided to abandon my own streaming terrain in favour of a small map. I have a problem with my own terrain paging.... lag basically. Loading 8 chunks in my system takes around 0.1 seconds, yet somehow this still manages to make a very noticeable effect of lag on the rendering.

Any ideas why this might be? I have created a threadsafe device. I've tried suspending the thread while rendering, setting a very low priority to spread the cost of loading over time, set it very high to get it loaded as quickly as possible. I've tried adding Sleep commands to the thread between chunks to spread processing over time, which kinda works, but makes the screen jerk rapidly several times rather than making it smoother. It's as if when the thread gets busy, the whole app jams up regardless of the fact the code is in a separate thread. I wonder if it's something to do with the fact I call a function that is outside of the thread class, and inside the same class that renders the heightmap (a bit of a bodge job to get things working).

Any suggestions for ensuring that paging is smooth? Any help would be appreciated, so if I work on it again in future, I'll have a better idea of what to improve on.

Thanks,

Steve AKA Mephs

Maybe in future,if i will have time, i will do something like that for my non-realtime renderer... i have to make simple utilite that will receive coordinates and will send commands to renderer core to load specific region of ,say,MOLA mars map,and render it.

Quote:

Original post by Mephs While the subject of paging terrain is about, even though I've decided to abandon my own streaming terrain in favour of a small map. I have a problem with my own terrain paging.... lag basically. Loading 8 chunks in my system takes around 0.1 seconds, yet somehow this still manages to make a very noticeable effect of lag on the rendering. Any ideas why this might be? I have created a threadsafe device. I've tried suspending the thread while rendering, setting a very low priority to spread the cost of loading over time, set it very high to get it loaded as quickly as possible. I've tried adding Sleep commands to the thread between chunks to spread processing over time, which kinda works, but makes the screen jerk rapidly several times rather than making it smoother. It's as if when the thread gets busy, the whole app jams up regardless of the fact the code is in a separate thread. I wonder if it's something to do with the fact I call a function that is outside of the thread class, and inside the same class that renders the heightmap (a bit of a bodge job to get things working). Any suggestions for ensuring that paging is smooth? Any help would be appreciated, so if I work on it again in future, I'll have a better idea of what to improve on. Thanks, Steve AKA Mephs

This goes back to my argument or question about why actually use multiple threads. If your application is running then it is in the running state for the OS and since it is in user space the OS doesn't see the separate threads, something more sequential with jumps to enter the different threads code.

Now when you have disk access it wont matter if one thread will be busy and unable to do anything since the application is in user space (not kernel) the whole application will be blocked by the OS and moved into the suspended state for the duration of the file load to take place. Then when the load is complete it will be moved back to the ready queue and again scheduled to run (in this blocked space if the memory space is required it will also be swapped out to disk). I believe this will cause your lag.

If you were in kernel space however then if one thread were to block another could be scheduled of the same task, unfortunately you can't create threads that exist in kernel space.

Maybe Yann could provide an explanation on how it was fast/faster for him to do it in multiple threads or someone correct me if I am way off here (my OS knowledge is a bit outdated maybe).

Quote:

Original post by nts Maybe Yann could provide an explanation on how it was fast/faster for him to do it in multiple threads or someone correct me if I am way off here (my OS knowledge is a bit outdated maybe).

Note my use of the conditional form in my last post: "I would probably use CLOD", ie. I never implemented such a system, I only gave an idea about how I would probably do it. My first reaction would be to use two threads, as it would be the most natural approach in this case. I never really did any performance critical multithreading under Windows though, so I can't comment on how the Kernel and your application will react or lock. Best is probably to try it out. I did such systems under SGIs IRIX, using multiple processors to do the streaming and rendering. But I have no idea how Windows would react. Perhaps a dual CPU system would avoid the lock, and would benefit from a feeding and a rendering thread (I'm again not sure how the Windows kernel handles two CPUs, but I guess its similar to Unix, where the threads are dispatched onto the different CPUs) ?

Quote:

Another question, I believe u mentioned that you were using ABT's for your scene just wondering how you are actually storing the CLOD chunks in there. Do u insert another class with no geometric data, just an AABB that when in view is asked to populate its data to the render queue and it just sends down whatever LOD level it is determined to be. This is what I am planning on doing but maybe there is a better way.:)

As I said, I never tried to make a streaming CLOD work with an ABT (my terrain system uses a different approach altogther, using parametric and fractal surfaces). But your idea sounds good, as it treats each patch as an independent entity before dispatching it to the render pipeline. That way, LOD levels can be determined and loaded on demand.

Read this: http://www.cc.gatech.edu/~lindstro/papers/tvcg2002/paper.pdf

Regards,

Justin.