-
Quad tree neighbors
The problem
I need to calculate the N, S, E and W neighbors of a quad tree. However here is the data structure:
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() { }
};
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 :D).
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.
-
I didn't figure I would get any responses. Guess I have to figure this one out on my own. And to think I do this stuff as a hobby. :D
-
Would love to help you out, but this is far more advance then anything what I have done before. If you wait a few years I might look into it for you...
I recommend posting the same thing over at gameDev.net.
BTW, how long have you been programming games?
Best of luck
-
Yeah, gamedev or forums.indiegamer.com would be good places to ask. I've never implemented a quad tree for the simple games I've written.
-
Have you tried seeing if any of the space filling algorithms would help you out? I just went to a talk where something very similar was discussed and space filling algorithms were used to put the data onto the disk in such a way that points near each other were kept close to each other on disk. You might be able to do something similar.
-
I've found some major issues with my index buffers. Going to try to fix that before tackling this problem. Also fixed the frustum culling by creating the planes locally and then normalizing them and saving the result in the class. Weird b/c I was setting the class member via an assignment operator but when it normalized everything went haywire.
Code:
void Compute(D3DXMATRIX matView,D3DXMATRIX matProj)
{
D3DXMATRIX matClip = matView * matProj;
//D3DXMatrixMultiply( &matClip, &matView, lpMatProj);
// Calculate the planes of the frustum
D3DXVECTOR4 col0(matClip(0,0),matClip(1,0),matClip(2,0),matClip(3,0));
D3DXVECTOR4 col1(matClip(0,1),matClip(1,1),matClip(2,1),matClip(3,1));
D3DXVECTOR4 col2(matClip(0,2),matClip(1,2),matClip(2,2),matClip(3,2));
D3DXVECTOR4 col3(matClip(0,3),matClip(1,3),matClip(2,3),matClip(3,3));
D3DXPLANE planes[6];
planes[0] = (D3DXPLANE)(col2); //near
planes[1] = (D3DXPLANE)(col3 - col2); //far
planes[2] = (D3DXPLANE)(col3 + col0); //left
planes[3] = (D3DXPLANE)(col3 - col0); //right
planes[4] = (D3DXPLANE)(col3 - col1); //top
planes[5] = (D3DXPLANE)(col3 + col1); //bottom
for (int i = 0;i < 6; ++ i)
{
D3DXPlaneNormalize(&m_Planes[i],&planes[i]);
}
}
This code works, but the following did not:
Code:
...
m_Planes[0] = (D3DXPLANE)(col2); //near
m_Planes[1] = (D3DXPLANE)(col3 - col2); //far
m_Planes[2] = (D3DXPLANE)(col3 + col0); //left
m_Planes[3] = (D3DXPLANE)(col3 - col0); //right
m_Planes[4] = (D3DXPLANE)(col3 - col1); //top
m_Planes[5] = (D3DXPLANE)(col3 + col1); //bottom
for (int i = 0;i < 6; ++ i)
{
D3DXPlaneNormalize(&m_Planes[i],&m_Planes[i]);
}
...
Why the first version works and the second does not is beyond me. They are doing the same thing.
-
Probably has to do with the implementation of D3DXPlaneNormalize not allowing the same buffer for the target and destination.
-
As for your original problem, it sounds like you're taking a bottom up approach, computing the neighbors of nodes to see if their LOD level differes. In my implementation I do it top down, never letting all divisions of a node differ by more than one LOD level. Then the "patching" can be done by adding additional edges from the lower LOD patch to the higher one.
For example, look at the following screen shot. No two neighbors will ever differ by more than one LOD level, that way you can just hook up the centre vertex to the edges of the neighboring nodes.
-
Yeah my LOD setup is the same as yours. However your LOD appears to be based on Y value screen space difference where mine is purely based on distance from camera.
I have some issues with computing the distance since it is only computing distance from camera to the center of the patch. This causes the LODs to get messed up.
Lots of work left to do to get the LOD patches in. I don't want to lock the index buffer to accomplish this. When I get it done I still should only be using a minimum of video memory for 1 vertex buffer and about 6 to 8 index buffers.
-
Implementing quad trees and octrees is on my list of things to do...right after I finish writing my ray tracer which I am currently working on......
-
Yeah, I use Roettgers algorithm which is a combination of distance and terrain roughness. That screen shot has the distance part disabled. I have a distance based screen shot on my website but it's not really close up enough to see how the differing LOD patches get connected. It works the same as in the roughness LOD though.
