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.
No comments:
Post a Comment