What are the best structures to use for collision detection? I currently use octrees. They work pretty well but I know you can use bsps too. So which is faster? Does it depend on the object? I guess terrain might not be good for bsp but what about a character model? And if thats the case do physics engines usually allow you to specify what type of spatial structure you want to use? I was thinking of allowing octrees, quadtrees, and bsps leaving it up to the user to select, but then during the collision detection I have to find out what object I am using, or I could leave it up to inheritance. Sorry about all the questions, this is the last for now. KC

Some character animation systems, such as the one in the NetImmerse game engine, use oriented bounding box trees for characters.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Do they generate the bounding box tree every frame or do they have it precalculated and somehow track the movement of the bbs. Hmm, I guess you could precalculate the bb tree for all frames and then lerp the box along with the verts. I will have to try that out. I am just doing simple keyframe animation right now, and lerping between frames.

NetImmerse calculates the OBB tree for a given instance of a triangle mesh---basically for one frame of an animating mesh such as skinned characters. While you can cause it to regenerate the OBB tree as the skin morphs from frame to frame, it is not necessarily efficient to recalculate the tree for the chacter skin . A better way is to rigidly attach OBB's to the bones themselves in a skinned animation system. Do collision on the OBB's of the skeleton and not the skin. This way you can precalculate the OBB's and they will move/rotate with the bones. And the skeleton OBB tree can be less deep and strange than the tree for the skin. This is how we've used the NetImmerse collision system for characters. We actually use proxy collision objects (spheres) instead of boxes, since we really don't need too much precision. (We're doing character collision just to make sure the character doesn't move through walls, and for hand-to-hand combat where we only care that one characters hand hits another characters face, ha!)

I should expand a bit. If you provide NetImmerse with alternate bounding volumes (or proxy collision objects) that you calculate yourself, then you can attach them to anything, including the skeleton's bones that have no real geometry themselves. If you want NetImmerse to actually calculate the bounding volumes (OBB's) for you, then you must give it triangles. That means your skeleton has to have geometry. In 3ds max terms, it means you have to export the mesh representation of the character studio skeleton (or max bones skeleton) in addition to the skin. You can app-cull the bones so they are not visible, and the OBB's will still be there.

Your approach, to lerp the OBB's as you lerp the vertices is basically exactly what they do.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Edited by - grhodes_at_work on February 14, 2002 12:05:59 AM

Thanks for the info. Now I have a better idea of what should be done. I guess I should try to check out some documentation of some animation packages. I am using keyframe animation so I cant put bounding boxes around the bones. But I am already using a proxy object which is a simple bb and using that for collision detection. Its just that when you shoot a character in the game I wanted to apply a decal but I guess a blood spray will have to do.

I will be looking into skeletal animation next. Would you say thats the way to go for an easier and less expensive way to do accurate collision detection?