Sign in to follow this  

Quad-tree/grid, depth sorted output?

This topic is 2643 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

I'm currently traversing a quad-tree of fixed-size blocks in a grid (http://www.gamedev.net/community/forums/topic.asp?topic_id=580927) to determine the visible blocks in the grid (frustum cullings). But I'm currently traversing the quad-tree and placing all the visible blocks in an array and then sorting the array by depth.

I haven't really found anything on it so far, but intuitively it would seem like it would be possible depth-sort the visible blocks during the traversal rather than doing it afterwards... using some combination of the view-direction and relative position to the nodes (again, the quad-tree just maps into a fixed-size grid)

(PS. depth order is important as it's used for GPU-occlusion culling)


To give you an idea of my intentions (the blocks/chunks are 16x16x8).


(EDIT: Btw, I'm of course using octrees (not quadtrees), although the problem is the same).

[Edited by - Syranide on August 31, 2010 5:15:33 AM]

Share this post


Link to post
Share on other sites
It is quite simple. A quad tree without overlapping quads is a special form of a bsp tree with the x-axis/y-axis as partitioning plane.

To traverse through a bsp tree in a sorted manner, you need to determine if the viewer is infront or behind a partitioning plane. When you render all objects which are on the opposite side of the plane as the viewer first, you will render them in back-to-front order.

Try to understand how a bsp tree works, then think about the x/y axis as virtual partitioning planes. To derive a working algorithm from it is quite simple afterward.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ashaman73
It is quite simple. A quad tree without overlapping quads is a special form of a bsp tree with the x-axis/y-axis as partitioning plane.

To traverse through a bsp tree in a sorted manner, you need to determine if the viewer is infront or behind a partitioning plane. When you render all objects which are on the opposite side of the plane as the viewer first, you will render them in back-to-front order.

Try to understand how a bsp tree works, then think about the x/y axis as virtual partitioning planes. To derive a working algorithm from it is quite simple afterward.


(I actually meant octree and not quadtree, but the problem remains the same)

I'm somewhat familiar with BSP, but doesn't determining the order of the partitioning planes (3 of them, X/Y/Z right, for octree) I have to split in add a "significant" overhead (under the circumstances).

I mean, when traversing the octree, I can simply depth-sort the 8 nodes every time I split a node... but that would actually be slower than just sorting all of it at once, or did I mess up my calculation?

Or hmm, if I don't use an array to store the result of each partition/split and just do nested checks, it should be really fast right? Storing the result of each partition/split in an array would seem like it would end up being virtually as bad as simply sorting the 8 nodes.


Intuitively it just feels like there should be simpler solution to the problem, where I simply have the 8 nodes and multiply them by some computed vector, perhaps simply using "sign()" on the view-direction vector... (aka, [1,1,1] or [-1,1,1] to reorder them).

[Edited by - Syranide on August 31, 2010 5:33:05 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Syranide
I mean, when traversing the octree, I can simply depth-sort the 8 nodes every time I split a node... but that would actually be slower than just sorting all of it at once, or did I mess up my calculation?

This can be precomputed and stored in a lookup table( presort the 8 nodes depending on the "node" in which the viewer is located).

Quote:
Original post by Syranide
Or hmm, if I don't use an array to store the result of each partition/split and just do nested checks, it should be really fast right? Storing the result of each partition/split in an array would seem like it would end up being virtually as bad as simply sorting the 8 nodes.

Use a stack and push the nodes in the right order on the stack. Determine the order by precomputed look-up tables(8X):


// position of viewer
float vx,vy,vz

node* stack[MAX];
int stackPosition=0;

// push root on stack
stack[stackPosition++] = root;

while(stackPosition>0)
{
node* currentNode = stack[--stackPosition];

if(node.isLeaf())
{
// do some rendering ...
..
continue;
}

// determine
int index = 0;
index |= (vx<currentNode .x ? 0x1 : 0x0);
index |= (vy<currentNode .y ? 0x2 : 0x0);
index |= (vz<currentNode .z ? 0x4 : 0x0);

int* orderedIndiciesOfChildNodes = precomputedIndiciesOfChildNodees[index];

for(int i=0;i<8;i++)
{
int childIndex = orderedIndiciesOfChildNodes[i];
node* childNode = currentNode[childIndex];

// push child node on stack
stack[stackPosition++] = childNode ;
}
}



Share this post


Link to post
Share on other sites
Quote:
Original post by Ashaman73
Quote:
Original post by Syranide
I mean, when traversing the octree, I can simply depth-sort the 8 nodes every time I split a node... but that would actually be slower than just sorting all of it at once, or did I mess up my calculation?

This can be precomputed and stored in a lookup table( presort the 8 nodes depending on the "node" in which the viewer is located).

Quote:
Original post by Syranide
Or hmm, if I don't use an array to store the result of each partition/split and just do nested checks, it should be really fast right? Storing the result of each partition/split in an array would seem like it would end up being virtually as bad as simply sorting the 8 nodes.

Use a stack and push the nodes in the right order on the stack. Determine the order by precomputed look-up tables(8X):

*** Source Snippet Removed ***


Oh right, it's so obvious now (sad face), I kept thinking that the orientation of the camera somehow had to be involved in the ordering of the nodes... which it "obviously" isn't... the ordering is only dependent on the relative distance to the viewer.

Thanks a lot!

Share this post


Link to post
Share on other sites
No punt intended, but it's strange that z-sorting on a quad tree produces the letter "Z" on every node, starting node which the camera position is in.

In the example square terrain engine you made, this won't be a problem, but how do you deal with objects straddling multiple planes?

One way is to clip the offending objects with the plane, similar to how bsp does it with moving entities straddling a partition plane coplanar to static geometry. Or perhaps, there's a better way to go about this, such as shifting the quadtree horizontal/vertical boundaries to accommodate the offending objects.

If a loose octree is used, can pre-computed lookup tables still be done as shown in the above code example?

[Edited by - Glidias on September 19, 2010 9:37:40 AM]

Share this post


Link to post
Share on other sites

This topic is 2643 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this