Quadtree Mesh Management And Caching

Sometimes you can get away with half decent code when dealing with 2d terrain, but you will be punished if you try that with spherical/planet terrain.

Now that my feet are wet I've returned to the basics in order to deal with some of core issues like implementing a mesh manager to handle meshes should be visible, those that need to be built, and those are built that should be cached. I also created a customizable QuadTreeSphere class that I plan on using for the water mesh, the atmosphere and the planet surface. I now can specify the min and max node levels allowed in the quadtree, the patch size for each mesh, the max cache size for each mesh and things like whether the mesh will use normals or textures or tangents or even a heightmap.

The new system doesn't do anything but basic terrain now because I've been focusing on the mesh management and caching.

Mesh Management

I've implemented a separate manager for each QuadTreeSphere that has four std::map objects that hold pointers to the mesh objects and the key for each element in the map is the unique ID for that mesh.
1. A visible map that holds all the current visible meshes.
2. A visible build map that holds all the unbuilt meshes that are needed for immediate display.
3. A cache map that holds all the non-visible, but built meshes that we might need soon.
4. A cache build map that holds all the unbuilt meshes that we might need soon.

I also have a FIFO (first in first out) list that contains all the id's of all the meshes in the cache map. If the FIFO list ever gets larger than the max cache size then I start removing meshes from the list - and from the cache and deleting them. This list is used to delete the least recently used meshes. Of course if any mesh in the cache is moved to the visible map then it must also be removed from the FIFO list, and when that mesh is moved from the visible map to the cache map it will go on the front of the list.

Some other rules I have found that I needed to implement:
1. All meshes in the visible build map must be built immediately or you get flickering where you have not built a mesh (duh)
2. Only build one mesh from the cache build map per frame and only if no meshes in the visible build map were built because building meshes takes a lot of time (relatively).

I added a simple profiling class because I know I will need to compare build optimizations and also I needed to get a good idea for how much time each major component takes. Clicking on the chart below takes you to the larger version.

Quadtree Pre-Caching

My simple manager has a bottleneck right now and that is when the camera gets close to the surface all these new meshes are added to the visible build list and must be immediately built for immediate display. There are a couple things you can do to resolve this issue and the simplest one is to do pre-caching. My simple method is to take the closest quadrant from the closet node at the current deepest level of the tree and pre-cache the four meshes for that quadrant (which we will have to split anyways if the camera get's closer to the surface). The second simple thing to do is to pre-cache the meshes for the neighbors of the closest node at the current deepest level of the quadtree (if those neighbor nodes don't already exist).

Below is a diagram of this:


The Pink square represents the closest node to the camera at the current deepest level in the quadtree. The four orange squares are the neighbors of this node.
The purple square represents the quadrant that is closest to the camera in the pink square.

Under my simple caching scheme we know that if the camera moves closer to the surface we must split the purple quadrant - so the first thing to do is to build those meshes and save them in the cache until they're needed. If the camera moves left or right along the surface but not closer to the surface then we'll need the meshes represented by the orange squares, so build those and add them to the cache.

If the camera moves further away from the surface the larger meshes should still be in the cache because every mesh that was visible is added to the cache after it is not needed.

Pros of this scheme:
1. Simple and works without modifying the quadtree
2. This caching scheme works fine when the camera is tracking a player running on the surface, where they can change direction and speed rapidly and frequently.

Cons of this scheme:
1. If the camera moves in a diagonal fashion along the surface, the diagonal nodes will not have their meshes in the cache (green nodes)
2. This scheme is ignorant of the camera's current speed and direction, which is more useful information when dealing with fast moving objects above the surface, where the direction and speed won't change as rapidly.

I plan on implementing another cache scheme based on speed and direction where I have a second quadtree that represents where the camera will be in the next nth of a second, and based on that tree, cache all the meshes that would be visible. According to my profiling statistics, the updating of the quadtree doesn't take nearly as much time as building meshes, so it might be worth the extra time to implement this pre-cache scheme and get better cache results.

Lastly, I implemented frustum culling for my barebones quadtree system and it helps the FPS a lot! It cut down the number of triangles from about 200k to about 90k.



I plan on doing some experiments with making the mesh manager threaded to better utilize the cpu.

Atmosphere Debut

Oh atmosphere with your light scattering and all your fancy equations how you kill me. I poured over a lot of white papers and Sean O'neils atmosphere shaders, but I just couldn't get them to work right. I ended up using a simplified version of his sky shader, and came up with my own shader for the ground. The effect isn't ultra-realistic, but that isn't what I'm going for. I would like the shader to be flexible, but for now it gets the idea across that this is a fantasy-esque environment and that you are meant to play.

I added starlight to the dark side of the planet so players will still be able to accomplish things at "night". Still might need to add more moonlight though or make night time artificially short by speeding up the planet rotation or something.



I did make the planet rotate and the light rotate which is nice and now it looks like I have a glorified screensaver. Huzzah.

On the todo list for a few things to tweak next are: terrain look up table tweak and texture tweak, add some noise to the table, but try to preserve a fantasy/cartoony look, add a sun glow in the sky so I can tell where it is and make the mie scattering line up with that sun glow. I'd also like to make the water not look so deep by making it aware of the height of the terrain under it, but I might update the water mesh before I get to that -right now it is just a simple sphere primitive with no LOD and the UV is very squished at the poles.

More random pics:






I need to ask Mr. O'Neil if it is OK for me to share the modified shaders, but I imagine he'll say yes. In other news be sure to check out Ysaneya's latest dev journal post to see what a real pro can do! I just noticed he's pushing 500k tri's with more complex shaders than me and a MUCH larger planet, and I'm only doing 80k tri's with less complex shaders and a small planet and his framerates are higher *sigh*

PSVSM Shadows And Texture Updates

It's been a while since my last post so a lot has happened - mostly Christmas related stuff, but some planet work as well.

I implemented a second LOD for the textures so that when you view the planet from just outside the atmosphere the textures don't look like they repeat so much and there isn't a mipmap problem with the texture tiling so much which makes the texture really grainy. I also added back a temporary water sphere surface with some specular and normal mapping, to look like water, but it won't really look like water till it is animated, and it has uv problems at the top and bottom. Eventually I plan on coming up with a way to always have the water mesh face the camera at point where the uv isn't stretched and then do a mini-quad tree on it so that I can actually animate the vertices when you're close to the surface (but I'm getting waaayyy ahead of myself there).



After implementing that stuff I got in over my head implementing shadows.

My first success was with Ogre's PSSM shadow demo, but that had a major drawback because the shadows had a gap between where the shadow started and the base of the shadow casting triangles. Also the shadows swam a lot when you moved the camera and they were very pixelated because of the large amount of terrain that was covered.

This image shows the shadow "beards" and uses 3 512x512 shadow maps.



Later I found that this was a typical problem for basic PSSM shadows, and I read that VSM shadows didn't seem to have this problem (although they have their own drawbacks - namely light bleeding, which sounds weird to say)

I posted my latest GLSL shader code for the shadow caster and shadow receiver materials as well as the Ogre material code - and my set up code too so hopefully it can be tweaked to make it perform and look better.

These images show PSVSM using 3 1024x1024 shadow maps. I'll probably have to scale back to 512x512, unless I can come up with a way to gain back fps dramatically.





I plan on tweaking the shadow, terrain texture and water texture code next before moving on to a basic atmosphere.