void DrawPanel(D3DXMATRIX worldmatrix, D3DXMATRIX offsetmatrix, float radius, int layer, int maxlayer, byte adjacents, ID3DXEffect* effect)
{
byte d[4];
D3DXMATRIX tempmatrix;
//Step #1
for(int i=0;i<4;i++)
{
tempmatrix = (ChunkMatrices * offsetmatrix);
//memcpy(tempmatrix.m[3], normalize(tempmatrix.m[3]),12);
float td = distance(D3DXVECTOR3(0,0,0) ,(tempmatrix * worldmatrix).m[3]);
if((td > radius) || (layer == maxlayer))
d=0;
else
d=1;
}
//Step #2
byte sadjacents[4];
sadjacents[0]=SetBits(GetBit(adjacents,0), (1-d[1])*d[0], (1-d[2])*d[0], GetBit(adjacents,3));
sadjacents[1]=SetBits(GetBit(adjacents,0), GetBit(adjacents,1), (1-d[3])*d[1], (1-d[0])*d[1]);
sadjacents[2]=SetBits((1-d[0])*d[2], (1-d[3])*d[2], GetBit(adjacents,2), GetBit(adjacents,3));
sadjacents[3]=SetBits((1-d[1])*d[3], GetBit(adjacents,1), GetBit(adjacents,2), (1-d[2])*d[3]);
//Step #3
for(int i=0;i<4;i++)
if(!d)
{
tempmatrix = (ChunkMatrices * offsetmatrix);
effect->SetMatrix( "WorldOffset", &tempmatrix );
effect->Begin( 0, 0 );
effect->BeginPass( 0 );
objects[0].meshdata->DrawSubset(sadjacents);
effect->EndPass();
effect->End();
}
else
DrawPanel(worldmatrix, (ChunkMatrices * offsetmatrix), radius / 2, layer + 1, maxlayer, sadjacents, effect);
}
Quad-Tree Adjacents (Again...Please see if you can figure this out)
Author
Well after a month of off and on work trying to figure out how to find the adjacents of a chunk in a Quad-Tree. I've been able to get it to kinda work but it's so confusing...
Here is what I did.
1. I create a array which checks 4 chunks to see if they need to be spit.
2. I create a array that contains the adjacents of each one of the 4 chunks and I pack this data into 1 byte per chunk.
3. I look at the data from step #1 and if it does not need to be spit I render the chunk. If it does need to be spit I tell it to do this function over with the values of that chunk.
Here is the source code:
Now the only problem I'm having is figuring out what values need to be in step #2 I got it to work on some of the edges but it's making my head feel like it's going to explode from the complexity.
[Edited by - EmptyVoid on June 9, 2008 3:16:35 AM]
Yesterday, I was trying to create a quad-tree for some path-finding code and I needed the adjacents, so I used this paper as a guide:
http://citeseer.ist.psu.edu/660001.html
There's even some code at the bottom.
What it'll furnish you with (you'll have to expand the two example edge-neighbor functions so you get all four) is edge neighbors of the same size or larger - if you get neighbors that have children, just recurse down and get the neighbors closest to that edge. For instance, if it returns the northern neighbor that has children, you check it's South-West and South-East child for children and keep doing that until you get to the leaf-nodes (i.e. no children), then add them to your neighborhood. It'll even give you corners.
If you hit any snags, feel free to PM me and I'll see what I can do.
http://citeseer.ist.psu.edu/660001.html
There's even some code at the bottom.
What it'll furnish you with (you'll have to expand the two example edge-neighbor functions so you get all four) is edge neighbors of the same size or larger - if you get neighbors that have children, just recurse down and get the neighbors closest to that edge. For instance, if it returns the northern neighbor that has children, you check it's South-West and South-East child for children and keep doing that until you get to the leaf-nodes (i.e. no children), then add them to your neighborhood. It'll even give you corners.
If you hit any snags, feel free to PM me and I'll see what I can do.
Author
Quote:Original post by HexiDave
Yesterday, I was trying to create a quad-tree for some path-finding code and I needed the adjacents, so I used this paper as a guide:
http://citeseer.ist.psu.edu/660001.html
There's even some code at the bottom.
What it'll furnish you with (you'll have to expand the two example edge-neighbor functions so you get all four) is edge neighbors of the same size or larger - if you get neighbors that have children, just recurse down and get the neighbors closest to that edge. For instance, if it returns the northern neighbor that has children, you check it's South-West and South-East child for children and keep doing that until you get to the leaf-nodes (i.e. no children), then add them to your neighborhood. It'll even give you corners.
If you hit any snags, feel free to PM me and I'll see what I can do.
I can't figure out where the article that your talking about is on that site? I think the site may be down at the moment...
Up in the top-right corner are the downloads for the papers:
Click for PDF
Give it a second, though - it does seem to be a bit slow today.
Click for PDF
Give it a second, though - it does seem to be a bit slow today.
Author
Quote:Original post by HexiDave
Up in the top-right corner are the downloads for the papers:
Click for PDF
Give it a second, though - it does seem to be a bit slow today.
I think it was down when I tried. Going to read it but I'm not sure if it's quite what I'm looking for.
When you construct a node in the tree, it not only needs to know its parent, but also its position relative to the parent (top left, top right, bottom left, bottom right)
Then, in the constructor build an array of neighbours.
For example, if the node is the topleft, and you want the left neighbour:
this->leftNeighbour = this->parent->leftNeighbour->topRightChild
If you are in the bottom left, and you want the right neighbour
this->rightNeighbour = this->parent->bottomRightChild
You should be able to work the rest out from there. Of course when you split a node, you would want to inform neighbours of it so they can relink etc.
Then, in the constructor build an array of neighbours.
For example, if the node is the topleft, and you want the left neighbour:
this->leftNeighbour = this->parent->leftNeighbour->topRightChild
If you are in the bottom left, and you want the right neighbour
this->rightNeighbour = this->parent->bottomRightChild
You should be able to work the rest out from there. Of course when you split a node, you would want to inform neighbours of it so they can relink etc.
Quote:Original post by Exorcist
For example, if the node is the topleft, and you want the left neighbour:
this->leftNeighbour = this->parent->leftNeighbour->topRightChild
Good suggestion, but remember that the neighbours do not always share the same parent. You might have to visit the grandparents, great-grandparents etc, in some cases (it helps to draw it on paper). It depends of course on the depth of the tree.
Author
The problem is I am passing the adjacent data for each node down to the next node correctly but after a few layers in to the quadtree it just stops working right...
[Edited by - EmptyVoid on June 11, 2008 3:57:25 AM]
[Edited by - EmptyVoid on June 11, 2008 3:57:25 AM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
