[gameprogrammer] escaping worst case scenario with oct tree

Hey Guys,

Im workin on a game where the levels are defined by models that describe the
collision geometry.

Whenever the player moves, it does a ray cast (player currently is just a
single point in space as far as collision cares) against a bounding sphere
of every object in the level.

As you probably guessed, this is fairly slow :P

So, i figured i'd wrap the level in an oct tree and do the ray casts into
the tree to cull out as many of the tests as i can.

How i generate the oct tree is find the bounding box of all the models, and
then use that as the dimensions of the root node of the tree, and enforce a
3 depth oct tree to fit inside that bounding box.

My problem is that a level i'm currently working on is fairly flat which
makes it so that the tree is really short in height, which makes it so that
no objects can fit in a child node!

I was thinking about enforcing a minimum width, height, and depth to the
tree and just expanding it if it was under that, but even that hits the
problem that since it's a bounding box, a lot of geometry tends to fall
around the middle making it more likely to be stored in the root node.

basically i'm making worst case scenarios for the oct tree!

I thought of enforcing a minimum size AND offsetting the center of the tree
but that seems a little dodgy.

Anyone have any tips or has dealt w/ this before?

Thanks!

Other related posts: