Should I use Oriented Bounding Boxes for my collision detection tree, or should I use Bounding Spheres? In any case I''ve decided to do the following: - Build a bounding sphre for my entire object and test the two spheres of the two object before I go into tree-tree collision detection. - When I''ll find that an end-node has collided with another end-node (of the second model), I''ll do a tri-tri collision test between these two ploygones bounded by these two end-nodes for a 100% accuracy. So, should I build my tree from boxes or shperes? What are the advantages and disadvantages of each other? (Speed, tightness etc...) 10x!

I''ve read that spheres are more faster then cubes. But spheres aren''t always good to enclose everything (long spaceship, vehicles, big trees, etc.) or they make the bound way too big for an object thats small. So then a cube is used for the collision detection. Of course you can also split your larger objects into smaller objects, and then you can use spheres or cubes.
So to sum it up, use whatever works best for the shape you are using.

||--------------------------||
Black Hole Productions
http://bhp.e-chrono.net/
Resident expert on stuff
max621@barrysworld.com
||--------------------------||

sphere->sphere collision detection is VERY FAST, much faster than bounding rectangles. Basically you only have to check the distance between the 2 centers, and see if the distance is > the sum of both radii. You don''t even have to use distance, you can use distance squared and check it against the sum of each radii squared (this makes it so you don''t have to do a sqrt call to calculate distance).

struct Sphere_S{ float x,y,z; float Rad; float RadSqr;};void InitSphere(Sphere_S &s, float x, float y, float z, float rad){ s.x = x; s.y = y; s.z = z; s.Rad = rad; s.RadSqr = rad*rad;}//Returns 1 on collision, else 0char SpheresCollided(Sphere_S &s1, Sphere_S &s2){ static float dx,dy,dz,dst; //Make static, so it''s only created once! dx = s2.x-s1.x; dy = s2.y-s1.y; dz = s2.z-s1.z; dx*=dx; dy*=dy; dz*=dz; dx+=dy+dz; //Store dist sqaured into dx! if (dx<s1.RadSqr+s2.RadSqr) return 1; return 0;}

That would basically be your sphere collision detection. For a rectangle, you''d have to worry about a LOT more, and there are a lot more points to check (4 corners, + rotations to the rectangle as the object moves, etc, etc).

Personally, I would use sphers for your "simple" test, as it''s the least CPU intensive collision test.

Billy - BillyB@mrsnj.com

I have the algorithms reuired to do the shpere-sphere test and the obb-obb, but 10x anyway!

My problem is that I don''t know what to use, the Sphere-Sphere test is much faster, but less tight and the tree will require lot of spheres till I''ll get to the situation where a single shpere bounds a single triangle, unlike the obb tree.

In shpere trees, if a collision has not occured, the chances are high that a tree will report a collision untill I''ll do the tri-tri test. An unwelcome situation...

On the other hand, obb trees are much tighter and will report that a collision has not occured in the close-proximity situation much earlier then the sphere trees.

Someone told me that even with the spear time earned with the shpere-sphere collision test obb trees will still be faster. Is it true?

quote:

---

Someone told me that even with the spear time earned with the shpere-sphere collision test obb trees will still be faster. Is it true?

---

This is neither true nor false. It can only be true or false in a specific case, but never in general. A very ''spherish'' object will probably be better of with a sphere-tree. A very rectangular object will probably be better of with an OBB-tree.

I do not have any experience with either method, so I can''t tell you what my performance difference was. But I do know that dynamic (ie moving) spheres are much easier to check for collision than moving and rotating OBBs.

The extended shape over time of a moving sphere is always a capsule (cylinder with hemisphere endcaps). A moving and rotating OBB can produce very complex polyhedra.

However, when you are considering static geometry, which do not require a sweep test, than the difference in complexity is not that great.

And on the tightness: yes spheres will probably not fit as well for most game-objects. But there are fast algoritms to generate the smallest enclosing sphere possible. So that might give some performance increase in the sphere-tree vs sphere-tree tests.

But this is all theoretical. As I stated above, I have no experience with either method.