Sign in to follow this  

does an octree have to be a cube?

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

From what I understand, if you divide a cube into 8 subcubes, you can as well divide a box into 8 suboxes. However, I am still unsure why people define octrees as cubes. Is there some difficulties in the implementation if I used a box instead?

Share this post


Link to post
Share on other sites
Quote:
Original post by Eelco
only then youd be calling it a kd-tree instead of an octree.

Why is that? The purpose and the concept remains the same. I subdivide a box into eight smaller boxes of the same size to partition the space. From what I can tell based on the information I found on the web, KDTree is used to do orthogonal searching, not space partitioning.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
No, a KD-Tree is basically a BSP with axis-aligned splitting planes.

I'm sure it's possible to make an octree with non-cube partitions, but I don't remember reading about anyone actually doing it. I guess no one saw the point.

Share this post


Link to post
Share on other sites
I never thought about it but I suppose if your terrain had alot of high sharp places then a box with a big height might be more efficiant and for terrain with low but wide places it might be more efficiant to use a flatter and wider box. However if you had some had both tall and pointy hills and low and round hills then cubes would probally make more sence. So (if I am right) that means that cubes are more versitile.

Share this post


Link to post
Share on other sites
Any subdivision algorithm where parent nodes have 8 children is an octree! Its like any tree where parents have 2 children is a binary tree. You could make an octree with sphere's if you wanted. The *common" implimentation uses cubes because its straightforward and it works very well - but if you want to use oblong boxes, sphere's or hexagons then go right ahead. If you can think of a way to change any algorithm that will suit you better than go ahead an do it ... just because everyone does it differently doesn't mean its best for you.

Share this post


Link to post
Share on other sites
ah so you dont want the size of every box be adaptable, but just the overall ratios?

why the hell not, as long as it suits your purposes. i dont think there is a name for it, but who cares?

Share this post


Link to post
Share on other sites
Quote:
Original post by alnite
Quote:
Original post by Eelco
only then youd be calling it a kd-tree instead of an octree.

Why is that? The purpose and the concept remains the same. I subdivide a box into eight smaller boxes of the same size to partition the space. From what I can tell based on the information I found on the web, KDTree is used to do orthogonal searching, not space partitioning.

subdividing into 8 or 2 new spaces at each step isnt really a fundamental difference. so, orthogonal searching is an application of a spatial partitioning.

Share this post


Link to post
Share on other sites
I've experimented with dividing the octree node up in some creative ways, but its hard to choose a good splitting point, since you have to satisfy 8 nodes at once. K-d trees are more suitable for this kind of fixup.

However, one thing that turned out to be useful was to build the octree and then as a post process, shrink all the nodes down to tightly encompass the triangles within. This, coupled with the fact that the octree was pretty sparse anyway (no empty nodes were stored), meant that AABB queries into the tree were much quicker. Ray tracing became more difficult mind...

Oh one last thing, my root node of the tree was never a cube, just an AABB tightly fitted around all the tris. It doesn't make any difference at all.

T

Share this post


Link to post
Share on other sites
If you use boxes instead of cubes, stuff like ray marching through the tree will get harder (no breshenham variant) but it might increase locality which could be beneficial if all you use it for is visibility determination. If locality is important though, you might want to try a bounding volume hierarchy like an AABB tree instead. Less regular but doesn't waste space on representing empty areas which can be good if you use it to store mostly static geometry for example.

Share this post


Link to post
Share on other sites

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