PDA

View Full Version : Collision detection?



CyBBe
06-28-2000, 09:37 PM
Is there any good tutorial or just some example of how collision detection works???

thanx...

nexusone
06-29-2000, 09:27 AM
I am not sure this is the correct way.
But since you know the position of each object, just compare the location of each oject every time you move them.

Make a varable structure something like this:

struct object_info
{
char *object_name[];
float center_x; // Center of object
float center_y;
float center_z;
float upper_x; // Boundary area
float upper_y; //
float upper_z;
float lower_x;
float lower_y;
float lower_z;
float *object_ptr; // object data
}

Just make a rutine to check each object's boundary for another object crossing into it.
Also I am sure there is other information that could be put into the structure, like direction of travel, speed, etc.
Hope this give's you some idea's.

MikeC
06-29-2000, 09:55 AM
That looks like an axis-aligned bounding box approach (AABB), which is crude but fairly simple to implement.

The other really simple technique is to use bounding spheres. Just store the radius of each object, i.e. the max distance from the object centre to a vertex. Two objects collide if the length of the vector between their centres is less than the sum of their bounding radii.

Both these approaches are very crude - they'll both report collisions in a lot of cases where they really shouldn't. Accuracy gets worse the less your object geometry resembles a box/sphere. There are more accurate (but harder, and more expensive) solutions for oriented bounding boxes (OBBs), convex polyhedra and for the worst-case, unconnected "polygon soups". For the latter, take a look at a library like SOLID.

Best bet is to start off with one of the easy algos and see how much more accuracy you really need. It's not wasted effort - with all of the advanced techniques you generally still do a fast-but-crude check first to weed out the easy cases, and save your cycles for the borderline cases.

There's more info in the comp.graphics.algorithms FAQ. There have also been a fair few collision articles on Gamasutra recently, so do a search there.

One last point - even the simple cases are only simple where objects are moving relatively slowly. With very fast-moving objects it gets a lot harder, because one object can end up zipping right through another one and out the other side in a single frame.

Hours of fun for all the family...

dans
06-29-2000, 09:58 AM
A sphere check is a quick(enough) and easy way to start on collision in OpenGL.

Pre-compute a radius for the two colliding objects. This radius is the objects size. So now your objects collision field is a near perfect sphere. More on this later.

Add both the objects radius together, this is how close they can come before a collision is detected.

psuedo
---
//
// get distance between our objects
// where obj is our objects origon
//
distance = distanceBetweenTwoPoints(obj1x,obj1y,obj1z,
obj2x,obj2y,obj2z);

//check if objects are within each others radius
if ( distance < ( obj1_radius + obj2_radius) )
{// then a bounding sphere collision has occured
// do your funky code here
};

You dont want your collision to stay at a sphere shape, unless you are checking against spherical objects. So with a more complex object you would call another more precise checking routine once the bounding sphere collision has occured. Line intersections and points crossing a plane spring to mind here. Do the bounding sphere check first though, as it will free a percentage of cpu time by eliminating distant collidable objects.

Hope to help