#### Archived

This topic is now archived and is closed to further replies.

# Octrees/collision detection

This topic is 5765 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I've made an octree class, and I am testing it out with a height map. I was thinking that you could check collision faster, by only checking the triangles in the frustum. Problem with this is, that what if you are walking backwards or sideways? What is generally the best way of using an octree to cut down on the number of triangles you check for collision with? EDIT: On a side note, I've read other methods for spatial subdivision. Quadtrees, octrees, bsp, AABB trees. The author that writes about these particular trees always seems to prefer his method best. I read on the flipcode site that octrees have the weakness that they draw overlapped geometry. This is not necissarily true, it you put a polygon splitter function in there, but that increases your triangle count. What would the people of gamedev recommend to someone learning, wishing to find the most elegant way of subdividing their scenes? Maybe someone with a little more experience in this area could enlighten me with a highlight of the strengths and weaknesses of each. Am I wasting my time with octrees, being that there is a method I don't yet know of or what? [edited by - xg0blin on February 7, 2003 3:02:16 PM]

##### Share on other sites
quote:

What is generally the best way of using an octree to cut down on the number of triangles you check for collision with?

The way I did it was this. You collide your object (say your colliding a Line against the Octree). For each successive level test your line against the bounding box for the each child node. Follow each child node for which the test is positive. When you reach a leaf and it''s bounding box test was positive, then test against whatever geometry you have in that leaf.

Totally forget about the frustum when it comes to collision testing against the octree.

As for preferences, I implemented an octree (for collision detection only) a few weeks ago and now I''m giving AABB trees a show. By the looks of things AABB trees will be an improvement, although I''ve been running into problems with generating the tree from the bottom up. I can do it, it just takes about 5 minutes and 160MB of RAM for a 1000 poly model!!! But that can wait for another thread....

##### Share on other sites
For the overlapped geometry problem, my octree deals with it in an elegant (or maybe not, you decide) manner. When it test the triangles to see which triangles go in each node, the triangle has to completely fit in the node. Whatever triangles are left over are kept in the parent node.

As for collision detection, I basically use the same thing as joanusdmentia. Find the smallest node that the object is completely within and test the polygons in that node.

''There''s something out there....something stupid...''
''I think I''m going to be ill. Is that a problem for you?''
''[You] overestimate my conscience by assuming that I have one.''
- Daria

DirectInput8 with the Keyboard , DirectInput8 with the Mouse , Using DirectX Audio 8

##### Share on other sites
That''s wierd that you store your triangles in any thing other than the end nodes. I put all of my vertices in end nodes only. I thought that was the way to do it? Maybe not I''m guessing?

##### Share on other sites
masonium:

You could easily get a LOT of your triangles in the parent node that way. It depends a lot on the depth as to how bad it''d get, but with a deep enough octree you''d end up with nearly EVERYTHING in the parent node!

Also, if you aren''t getting a significant number of tris in the parent, then you probably aren''t building a deep enough tree to make the most of the octree anyway. With my octree I was typically going deep enough to have around 10 tris per node, which seemed fairly optimal after a few tests. And I can guarenttee that most of those weren''t totally enclosed by the leaf''s bounding box either.

But...if what you have is good enough for your current needs I really wouldn''t bother changing it.

Joanus D''Mentia

##### Share on other sites
A slightly different approach if you want a small set of polygons to collide with rather than line intersection is to choose a bounding volume ( I use an AABB ) which is ''conservative'', ie will definitely contain all of the geometry that will potentially collide with the object.

This bounding volume is pushed down the tree to the leaves. Every leaf which intersects this volume has it''s triangles added to a list (just a vector), something like this:

V is volume
N is current node
L is list of polygons
NL is list of polygons in that leaf

L = {}

COLLECT_POLYS( N ):
IF V intersects N:
IF N is leaf:
L += NL
ELSE:
FOREACH N''s children Nc
COLLECT_POLYS( Nc )

Then L holds the potential list of polygons which can be used to do sphere or cylinder collision or whatever.

If you are using a heightmap, you could instead collect triangles using a volume/grid intersection technique which might be easier (ie just loop over the bits of the grid which are inside the volume).

1. 1
Rutin
67
2. 2
3. 3
4. 4
5. 5

• 21
• 10
• 33
• 20
• 9
• ### Forum Statistics

• Total Topics
633420
• Total Posts
3011792
• ### Who's Online (See full list)

There are no registered users currently online

×