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

Hey your tree actually has me thinkin...

think it'd be worth while to allow oct tree nodes to grow to fit the objects
they contain, and only store objects in leaves?

Normally i've just used quad and oct trees as the magic bullet, so haven't
strayed too far from that path hehe :P
On Wed, May 13, 2009 at 10:17 AM, Alan Wolfe <alan.wolfe@xxxxxxxxx> wrote:

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