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

Thanks Doug that sounds interesting

So would it be something like this?

#1 - find the AABB of the scene
#2 - break the scene into 2 child nodes which split the current node across
one axis.  Allow the boxes to overlap so that all objects fit in one child
or the other.
#3 - recurse for both children until some depth has been reached, or some
target object code? (ie maybe something like stop after 5 levels deep or if
there's less than 5 objects, whichever comes first)
#4 - store objects only in leave nodes.

You say the nodes can overlap, what kind of rules would you use to do that,
would it be something like this?

#1 - try splitting on the X,Y and Z axis in the middle to see the counts of
object locations which fall to the left or right.  Choose the most balanced
split based on object counts.
#2 - since objects are larger than a point in space, grow each child node to
completely encompass the objects which are located within them

Does that sound reasonable?
On Tue, May 12, 2009 at 10:42 PM, Douglas Dietrich Jr.
<simmer@xxxxxxxxxxx>wrote:

>   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: