• Advertisement
Sign in to follow this  

Loose Octrees and Unifrom Grid

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

This is a re-post into the correct forum from "General game programming" forum This may be a really "basic" question, but here it goes... I'd like to use a good, "fast" dynamic object partitioning system, and they two that seem to come to mind are "loose" octrees and uniform grids. I'm having trouble finding a lot of info on either one, but here is what i've found so far: "loose" octree: where a normal octree is NxNxN sized, the "loose" octree allows the size to be 2Nx2Nx2N, or generally kN, where k is basically the size of the largest object in the scene. This is the "loosened" size, versus the "actual" size. In order to insert or update objects, you just need to find the smallest size that could fit the object in the "loose" node, and look there. This means you must pre-create the octree to a determined level, but that's a cost I'm willing to pay if this can be done quickly. However, my questions are: since the octree is "loosened" and the nodes overlap, how does one effectively determine which node objects should go into? uniform grid: This one i've had the least ability to find. I guess the concept is to pre-divide your space up and then just insert / update objects in it? Any resources or help on these topics would be greatly appreciated. thanks

Share this post


Link to post
Share on other sites
Advertisement
Uniform grids usually don't scale very well, I've seen people use them in 2d but never in 3d. A similar technique is spatial hashing, both techniques have constant time access, but spatial hashing is more flexible and scales from what i've read.

Good Luck!

-ddn

Share this post


Link to post
Share on other sites
Heya,

I've used a loose octree before, so I can comment on that bit. One of the cool things about loose octrees is that there's always only one leaf or branch that an object can be in. Basically, you just place the object in the node whose bounding box encloses the object's centre and whose size (dimension) is relevant to the radius of the object.

The loosening only applies to the fact that objects could be hanging over the edge of the nodes. This generally means that you need to use a liberal frustum culling algorithm against the tree and then test each object's bounding sphere against the frustum as well (if you need more accuracy).

Detecting collisions between objects is a little more tricky and might be better suited to another scheme, or just starting from the root for each object's test.

I definitely found it a nice and fast method for subdividing dynamic scenes tho.

Share this post


Link to post
Share on other sites
Hi LachlanL >
I'm looking for exactly that: a nice, fast way to do dynamic object culling. I realize its not very good for collision detection, but I can use a different scheme for that.

My question tho, is what do you do with the original root node's dimensions? Lets say our "space" is 300 x 300 x 300, but our largest object has radius 100. The first node should be size 300 x 300 x 300, the second level nodes will be 150 x 150 x 150, etc. one of the speeds of doing multiples of 2, is you can do inserts and removes in O(1), but since now that doesn't seem to be possible...unless I'm missing something?

Share this post


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

  • Advertisement