[gameprogrammer] Re: escaping worst case scenario with oct tree

I would use a binary Axis Aligned Bounding Box Tree.  Each node contains a 
bbox, and one or more objects OR two child nodes.  Typically no objects allowed 
in the internal nodes, just at the leafs.

The child nodes are separated via their bbox centers along one of X Y or Z 
axes.  Two child nodes can overlap, which avoids issues like you are seeing 
with your octree.

sort of like

struct node
{
   aabox box;
   size_t split_axis;

   std::vector< void* > items;
   node* pChildren[ 2 ];
};

You can make a very simple version of this in a couple of hours, and get cute 
with better split heuristics over time if need be.



--- On Tue, 5/12/09, Alan Wolfe <alan.wolfe@xxxxxxxxx> wrote:
From: Alan Wolfe <alan.wolfe@xxxxxxxxx>
Subject: [gameprogrammer] escaping worst case scenario with oct tree
To: gameprogrammer@xxxxxxxxxxxxx
Date: Tuesday, May 12, 2009, 9:50 PM

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: