# Implementing aabb tree

## Recommended Posts

Bouteille51    122
hi, i'm new in directX and game programmation. I can load an axis aligned bouding box for each mesh and detect collisions between them. Next step is to manage an aabb tree in order to make a good CD. I've read a lot on how to do this but it's really hard to make it real. I'm using D3DX meshes of DirectX and i'd like to know how to divide the mesh by it's longer axis and sort vertex by axis related position. Must I dive in vertex buffers or index buffers (i'm not affraid, just curious) and how, must i clone my mesh before ? Don't you agree that it's really hard to find such examples on the web ? thx !

#### Share this post

##### Share on other sites
Bouteille51    122
Question 2 :) : once my vertex sorted (in a vertex buffer?), could i use again D3DXComputeBoundingBox (with the first half of my sorted vertexes first, then the second half) function in order to get my childs boxes ?

i'm sorry for this poor english...

thx again

#### Share this post

##### Share on other sites
Bouteille51    122
hello, me again for Question 3 :) (i learn new things every minute)

I know that i can read vertex buffer from a directX mesh but can i modify it ?

Also, is there a default index buffer for meshes or can i create one ?

thx, i think my questions are becoming more and more confused :)

#### Share this post

##### Share on other sites
Bouteille51    122
no one knows ? :)

#### Share this post

##### Share on other sites
vajuras    139
Well it's normally very difficult to find a good example of anything on the web. Anyway, what I do is pass in the vertex buffer to the AABB tree and from there, it does some number crunching, figuring out the best axis to use to divide the box (I used to use longest axis but this does not normally give ya the best tree). The criteria i use to figure out best axis is simple, simply test each face (group of 3 verts) by taking their face center and the ones that are less than best axis gets sorted to left else they get sorted to right node. What i mean by best axis is that I test x,y,z axis and determine which axis will produce the most balanced tree

//iAxis is index (0-2)
iAxisResult[iAxis] = abs(left-right);

The VB (vertex buffer) should only be used to compute the AABBs. You don't need to store the vertex buffer or split it up. you're just trying to compute AABBs. Each node only needs to know if it has a left/right sibling and it's bound.

I think i will write up a short tutorial on this. this all proably sounds like greek. Btw, I don't use the D3DX helper methods. it's very simple to compute an AABB. the min x,y,z is the min of your box. the max x,y,z is the max of the AABB.

#### Share this post

##### Share on other sites
vajuras    139
Here's a linky to my tutorials. Just uploaded a tut about building AABB Trees. Lemme know if things aren;t clear: Kreation's Edge

#### Share this post

##### Share on other sites
Bouteille51    122
Thanks a lot but i just have worked all night long and it's done :)

Oh yeah :)

I just got a problem : my AABB tree doesn't fit good to my mesh.

I must have mistaked :) on separating vertices... Gotta see it later since it's already not bad :)

I'm sure your code will be useful, specially for comparing with mine and see what can be optimized.

thx again, bye

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account

## Sign in

Already have an account? Sign in here.

Sign In Now

• 9
• 11
• 9
• 11
• 9