Jump to content
  • Advertisement
Sign in to follow this  
Bozebo

A little question about octree implementation

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

Quite soon I am going to have to start using octrees to handle culling for some of my test implementations (collision detection, raytracing, rendering). I feel I understand the theory quite well but I have some questions about an actual implementation.

I have used PVS in a coridoor style engine a little bit to grasp some of the theory, but I just need to clarify a few things.

Does an octree work by having each lowest-level cell contain pointers to each entity which has a position vector residing inside it? So when an object is relocated, it's new octree position must be determined at that point in time?

Ie, I need to make a method which is called from movable entities' "move" methods that finds out which cell it is in? (entities that are derived from a "movable" entity class somewhere higher up the polymorphic entity chain/list and are stored in the entities' std::vector). That is how I made a basic PVS system which operated on a 2d basis (y axis was left out of occlusion) projecting quads drawn up wherever there was a boundry which was not a portal to another high level cell or "room" in the system. My little test worked fine and it seemed to use barely 1% of the cpu core while running with a few hundred objects moving about. But is that the way it is intended on working? Or is there a clever optimisation method to have such a technique working?

Thinking about such entities that can move between cells:
- cameras
- players & other characters
- physics objects
And other entities that would have a cell that doesn't change:
- spawn points
- triggers
- static props
- static realtime lights
To name a few.

Once an object has moved, if it is no longer within its originating cell:
The algorithm for determining the containing oct tree cell should first check adjacent cells if the object is moving relatively slow, I think - and if they provide a negative test then it can keep looking at other cells which have been left after an occlusion along the object's directional vector - I havn't yet put this into practice with an RK4 integrator. Before I move on and do a lot of testing and implementations, I just wanted to ask here incase there are some good tutorials or examples kicking about that may shed som light on any confusions that I currently have or anything that I might get caught up on at a later date.

I hope my question was clearly stated. Thanks for any help you can give.

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Bozebo

Does an octree work by having each lowest-level cell contain pointers to each entity which has a position vector residing inside it? So when an object is relocated, it's new octree position must be determined at that point in time?

That is the usual naive approach which works fairly well. Whenever an object moves it is removed, the tree is rebalanced if needed (empty nodes are removed), and object is reinserted. A logn operation per object. To move all, it's nlogn.

If many/all objects move, then it may be cheaper to simply discard old tree and build a new one. This one is nlogn as well, but doesn't need to perform rebalancing.

Quote:
seemed to use barely 1% of the cpu core while running with a few hundred objects moving about.
Completely rebuilding a tree with 10,000 objects takes under 1% on most machines today - so it doesn't really matter for such low numbers.

Quote:
The algorithm for determining the containing oct tree cell should first check adjacent cells if the object is moving relatively slow

I've found such tests to be too complex and cumbersome, too many edge cases. They might help in some cases.

Quote:
some good tutorials or examples
Almost all examples I've seen use the above approach. But they also implement it in pure OO manner which tends to be subpar.

If performance matters (it doesn't for hundreds of items), pre-allocated nodes and sequential layout helps much more - just rearranging nodes in memory allows some 10-50 tests to be performed in the time a single cache miss would take. Relevant overview (ppt).

Share this post


Link to post
Share on other sites
Ok good. So I should go ahead and work something out that follows my current understanding.

Perhaps while omitting:
Quote:
The algorithm for determining the containing oct tree cell should first check adjacent cells if the object is moving relatively slow

Is my idea to first occlude cells that do not intersect a ray along the objects direction vector a good one?

Nothing I am going to be doing for quite some time will have particularly noticable load, only a few hundred entities at most are going to be dealt with.

Maby I should start off with some terrain occlusion and then make some entities which roam about along the surface, then I can watch it in realtime and figure out how to progress beyond that complexity - maby add portals and antiportals.

Flipcode has some very understandable tutorials on the situation which I have read through, they shed quite a lot of light on the topic and the implementation concepts. (albeit from ~2000)

edit:
Much of what was in that pdf is currently beyond my understanding. But that would be expected as I am something of a novice.
Software prefetching seems like it could help, I might need to write something to test it out. The example of matrix multiplication is eye opening.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!