The problem
I need to calculate the N, S, E and W neighbors of a quad tree. However here is the data structure:
I need to figure this out so I can add 'LOD patches' to connect the various LODs in my terrain. Somehow during render I need to dynamically 'patch' the index buffer. As of right now I'm not leaning in this direction since this would require a lock and unlock for all patches that were 'edge' cases (literally 'edge' cases ).Code:struct TerrainPatch { bool isLeaf; int currentLOD; D3DXVECTOR3 vecWorldPos; size_t patchID; TerrainPatch *Parent; TerrainPatch *NW; TerrainPatch *NE; TerrainPatch *SW; TerrainPatch *SE; X3DUtil::AABB Bounds; BSphere bound_sphere; TerrainPatch():vecWorldPos(0.0f,0.0f,0.0f),patchID(0),Parent(0),NW(0),NE(0),SW(0),SE(0), isLeaf(false),currentLOD(0),Bounds(),bound_sphere() { } };
Current system
My system right now uses 1 vertex buffer and LOD * num_levels index buffers. The data is not held in the quadtree since the vertex buffer and the index buffer never change. To keep from dynamically locking the vertex buffer to add in the Y height values, I'm using vertex texturing in my vertex shader. The height is grabbed from a height texture, scaled, and then Y is set to this value. UV coordinates are computed in the vertex shader and passed onto the pixel shader. This means I can have a huge viewing area and yet only use 2 hardware buffers. At any one time only (patch_size * patch_size) vertices are streamed to the card. This algo is proving to be very hardware efficient. Keep in mind that patch LODs will only differ from each other by a factor of 2. So a patch LOD with 4 times less detail could only border a patch with 2 times more detail or a patch with 8 times less detai.
The option I'm leaning towards for LOD patches is to pre-compute LOD index buffers and use those at the correct time. There would be 5 more index buffers per LOD. Vertex buffer data does not change. Since the index buffer affects how the triangles are drawn if I re-arrange the index buffer I've effectively reduced or increased the LOD up to a max LOD which is the cell_size of the terrain grid. At cell_size 1 heightmap texel corresponds to 1 vertex.
The LOD index buffers just skip over several texels and vertices to create the final triangles.
Static LOD index buffers explained
Terrain patch 'edge' cases
- North - different LOD's on the north edge (ignores vertex at: row * patch_cell_width + ( col + 1 ) )
- East - different LOD's on the east edge (ignores vertex at: (row + 1) * patch_cell_width + ( col + 1 ) )
- West - different LOD's on the west edge (ignores vertex at: (row + 1) * patch_cell_width + col )
- North and East - different LOD's on both north and east edges
- West and North - different LOD's on both west and north edges
South edge cases do not matter since LOD's only differ as you move away from the camera. Essentially the south edge case of a patch with less LOD is the same as a north edge patch with more LOD.
These of course would have to be pre-computed for all LODs. So the new number of index buffers would be LODs * num_levels * 6. This may seem like a lot but the advantage is they are all static and I just choose at render time which static index buffer to use.
However for any of this to work I must know what the LOD of the patches to the N, S, E, and W are. This does not seem possible given the structure of a quad tree.
Any ideas? Sorry so long but this is not exactly a simple rendering system to explain.