Sign in to follow this  

Octree adjacency information

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

Hello,

I was thinking about structure for storing building block information, and I consider two most common approaches:

1) Array grid (x, y, z) containing block information, [b]pros[/b] - very easy and quick access to adjacent blocks, easier to work with, [b]cons[/b] - uniform block size, no easy way to store bigger and smaller units, takes large amount of storage even if most of blocks will be empty

2) Octree, [b]pros [/b]- smaller space requirement, possibility to have different size of building blocks, [b]cons - [/b]hard (?) to acquire adjacency information

I require adjacency information to check whether I can build something - like disallowing putting some block in thin air if there is no support below, so I need to check what is below. With array grid its simple, just query block thats [0, -1, 0] from current block position. With octree it becomes more complicated, not only because I don't have easy access to information at a given location (like whats at x, y, z) but also that blocks are not uniform anymore.

Is there some solution to allow quick access to neighbouring "blocks" when using octree? Lets say I'm interested in blocks of same size (so if it turns out that below block of size 4x4 there are smaller, subdivided blocks, I just consider there is either full block or no block, don't dig deeper into what those blocks are), so I guess this limits the depth I will be searching for, then I need to step up to parent node and check specific nodes around? How do I know if that node contains neighbours of my block?

I hope you get what I'm looking for, if not I will try to provide some diagram later [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

I made a diagram that shows 3 cases where I need to query elements below block that I will be building. Red border shows block I wanna build, gray blocks mean solid type block. I used quadtree because its easier to represent but consider it as a 2D slice of 3D octree - I marked UP direction with an arrow.

[img]https://dl.dropbox.com/u/1040763/quadtree.png[/img] Edited by noizex

Share this post


Link to post
Share on other sites
One other advantage of QuadTrees and OctTrees is that the search time is logarithmic rather than exponential.

Here are some ideas you could try:
-Array grid could contain the smallest allowable blocks, and larger irregular blocks are composed of lots of smallest blocks.
ie, smallest block would be 1x1. A 1x2 block would be two 1x1 blocks linked together. You'll have to create four "connectors" for each block object (left, right, top, bottom) which point to attached neighbors.

-OctTree Method: Find the adjacent blocks when you're construction the octtree and put that data into the node. Figure it out conceptually before writing the code.

Share this post


Link to post
Share on other sites
If you keep octree nodes in an array, it's possible to work out the nodes adjacent to any particular node without too much hassle, provided you have the index and depth of the node.

Let's consider a quadtree for simplicitly, but the idea extends to an octree naturally.

Start with a division of the entire space, giving us 4 initial nodes. Walking clockwise, put the top-left at index 0, top-right at index 1, bottom-right at 2 and bottom-left at 3.

Now sub-divide the top left into four nodes. In the same clockwise ordering, these will be placed at indices 4, 5, 6, 7. The subdivisions of the top-right will 8, 9, 10, 11. After those go the subdivisions for the bottom-right and finally for the bottom-left. Keep doing this as far as is required.

[s]Now, given a node at depth K, where K = 0 means the initial four nodes, take a look at bits 2K and 2K+1. These bits tell you the position of the node within it's parent. Go 2 bits lower and those tell you the position of your parent node within [i]its[/i] parent, and so on. [/s] Now given a node's index, the lower two bits tell you its position within its parent (0 => top left, 1 => top-right, ...). Also, dividing its index by 4 with integer truncation and subtracting 1 gives you the index of the parent. So you have enough here to derive adjacency information without actually storing, say, pointers in your nodes. For an octree, you'd look at the lower 3 bits and do divisions by 8, I think.

If you aren't uniformly dividing everything, you could perhaps use a hash-table to represent a sparse array, or if your tree is shallow, perhaps having an 'unused' flag in the array elements would suffice. Edited by e?dd

Share this post


Link to post
Share on other sites
You can also use a x,y,z position.

so to know which child node to go to, you take (x[curDepth],y[curDepth],z[curDepth]) (component[depth] takes the depth:th pixel of the component) which gives you a bool,bool,bool which corresponds to 1 of the child nodes.

Though edd's way of having all of it in a single integer would probably be more space efficient if that matters.

Share this post


Link to post
Share on other sites

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