🔒 Locked

Space Partitioning: binary or octal?

Started by orbano Feb 2, 2004 at 2:25 PM 2 replies 2.5k views

Original Post

Feb 2, 2004 at 2:25 PM

Hi there! I have mainly dynamic objects in my scene (everything can move except the terrain). I want to partition the scene into a uniform volulme hierarchy. But i can not decide between binary or octal partitioning. Octal would be managable, as it results in a less deeper tree, but will become inefficient if there are too many objects crossing sector boundaries (if an object does not fit into none of the subsectors, it remains in the parent node). If i choose binary partitioning, this problem is solved, as if the object fits none of the two child nodes, it should always be drawn each time any of the children sectors are visible. But i dont know if the increase of the depth of the tree will cause too much overhead. (i think not, compared to the save of many unnecessary draws, but i think i do better ask other ppl) Thanx in advance! "Knowledge is no more expensive than ignorance, and at least as satisfying." -Barrin

SpaceDude

Feb 2, 2004 at 7:14 PM

good question, i had the same dilemma about a week ago... It depends on the type of world you have. If you have a largely 2D terrain then i would go with quadtree, if you have a terrain with a large of hills then i''d go for octree. I think the binary tree is the least efficient and should only be used in special cases where you really need it.

The problem you talked about with the octree is not really a problem at all. Because instead of just leaving the object in the parent node, you should either split it in two and store each part in the appropriate node or just add it to both nodes. This is of course assuming that you are only storing pointers to the objects and not the objects themselves (otherwise you will end up with a lot of duplicates and wasted memory).

Using binary trees is the easiest way, but i think its worth putting in the extra effort to use either a quadtree or an octree.

Zahlman

257

Zahlman

Feb 3, 2004 at 2:23 AM

Pick whichever you think will be easier to implement, and write it in a modular way so that you can change it later, if you really need to for performance reasons.

[edited by - Zahlman on February 3, 2004 3:24:14 AM]

orbano

Author

orbano

Feb 3, 2004 at 4:14 AM

thank you all. splitting is no solution for me, az the 90% of my objects are dynamic. yes making it modular is a useful thing. i spent my whole yesterday with trying to create and abstract space partitioning system, so i can have several ones, so i can even change them while running (for tests only of course). So you say "duplicating" the object is good? I think then i should set a flag for each model, if it has been already renderd in the current frame so i can avoid overdraw and in the case of collision detection, it is... yeeess. thank you. i dont know why did i think it would be a bad idea

Thank you!

"Knowledge is no more expensive than ignorance, and at least as satisfying." -Barrin

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.