does an octree have to be a cube?
Author
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?
Author
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.
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.
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.
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.
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.
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?
why the hell not, as long as it suits your purposes. i dont think there is a name for it, but who cares?
Quote:Original post by alniteQuote: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.
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
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
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
