Jump to content
  • Advertisement
Sign in to follow this  
EmptyVoid

Quad-Tree Adjacents (Again...Please see if you can figure this out)

This topic is 3718 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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:
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);
}







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]

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!