Sign in to follow this  

Spatial Coherence in terrain

This topic is 3733 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I've been reading this book on Level of Detail in Terrain, and in one specific area of the book the author mentions the following sentence: "Their approach was to optimize the layout of terrain data on disk to improve its spatial coherence." Not sure if you guys need more than what I've quoted, however I am not sure what spatial coherence means in terms of terrain, or even generically. I referenced Wikipedia's definition of Spatial Coherence, however it made absolutely no sense to me. I ended up recursively clicking links to learn definitions in each Wikipedia page I went to. Could anyone explain Spatial Coherence as it applies to 3D terrain and Level of Detail in games? Remember that I've never heard this word before so you'll probably have to use non-technical explanations. Thanks for reading. [Edited by - MrDoomMaster on October 28, 2007 11:31:11 AM]

Share this post


Link to post
Share on other sites
Need a little more to go on really, but I'll take a guess. Maybe that'll give you more to go on yourself.

I'd imagine it's talking about storing vertices that are close to each other in the terrain close to each other on disk. I guess by "improve it's spatial coherance" they mean "improve the consistency between the concept of spatial locality in model-space with the concept of spatial locality on disk". So essentially if vertices are close to each other in the world, they'd also be close together on disk.

For example; if the terrain is stored as one large file, the temptation would be to store it as any other heightmap image. Let's say the terrain is 2048x2048, but you split it into 256x256 patches. You'd probably want to be able to load a single 256x256 patch without having to load the entire 2048x2048 file. If the terrain is 2048 vertices wide in a single file and you only want a single 256x256 patch, you'd have to skip over a large number of vertices to get to the ones you want - only 256 of the 2048 in each row are actually of interest.

The main point of interest is in accessing vertices above or below each other in the heightmap. With a 2048x2048 heightmap pixel/vertex [x][y] is 2048 vertices away from [x][y+1]. With a 256x256 heightmap, it's only 256 vertices away.

Now, you could store each 256x256 patch as a seperate file instead, and this would "improve it's spatial coherance", but add overhead for the additional file open calls. Opening a file involves negotating with the OS behind the scenes and this can take a non-trivial amount of time, which is one reason many games store all their data in a single archive file.

To "improve it's spatial coherance" without the overhead introduced by multiple files, you could store all the 256x256 patches in a single file, BUT instead of ordering the vertices in the file as a single large heightmap, you could order them as they would be in 256x256 files. You'd probably duplicate vertices shared by multiple patches.

This concept also extends to your spatial hierarchy (quadtree or whatever) - terrain patches which are close in the world are also close in the hierarchy and close on disk.

It also extends to in-memory layout and access patterns when doing image filtering etc, but that's another long story [wink]

Share this post


Link to post
Share on other sites
Sign in to follow this