Sign in to follow this  
kyoukikoi

Help with the useful combination of Collision Detection algorithms

Recommended Posts

Hello everybody, after having learned all principles about collision detection i recognized, though a lot of different ways to test geometry for collision are provided, there is not single thread or tutorial about how to combine these methods for complex groups of geometry. An easy example: I have a humanoid model, containing bones and about 3000 Polygons. Furthermore i have another model, a little house, being subdivided in an octree-structure. Both do have a boundingsphere/obb. But, if a collision-test has been successful on this level, it becomes difficult. I have to test the octree against a tree of boundingspheres/obbs ( one for each bone to represent each limb of the humanoid body ). This would be one of a lot of ways to combine single methods. But the more complexe geometry-groups become, the more difficult becomes the decision to choose the correct combination of collision detection test. Does anyone have an advice how to generalize geometry to avoid a too vast variety of combinations of cd-methods? Ah btw. the CD should be implemented in a scenegraph!!! Thank you all in advance =D Marc

Share this post


Link to post
Share on other sites
You could use a delegate method

example in C++...

make a class heirachy with types for the primitives

const int SPHERE = 0;
const int BOX = 1;
ect...
const int MAX_PRIMITIVES = ...

class Primitive { int type; }
class Sphere : public Primitive
{ Sphere() { type = sphere; }
}

Define a table of function set to the intersection functions

typedef bool(*IntersectionFunction)(Primitive *A, Primitive *B)

IntersectionFunction intersectionFunctions[MAX_PRIMITIVES][MAX_PRIMITIVES]

void InitIntersectionFunctions()
{
intersectionFunctions[SPHERE][SPHERE] = IntersectSphereSphere;
intersectionFunctions[SPHERE][BOX] = IntersectSphereBox
}

then the delegate function would look like

void Intersect(Primitive *A, Primitive *B)
{
return intersectionFunctions[A->type][B->type](A, B);
}

A nice heuristic algorithm for good tree descent that doesn't involve comparing the objects together in a single function is descending into the max volume, along with other good ones.

Share this post


Link to post
Share on other sites
"Does anyone have an advice how to generalize geometry to avoid a too vast variety of combinations of cd-methods?"

Just to expand on this, in case I didn't give you exactly the anwser you wanted, if you have n basic primitives and you want to be able to test them all against eachother, you obviously need n^2 primitive test. With a few it's easy to add another, but as n increases, each new primitives requires more and more test, so you have to limit n to some reasonable number.

Obviously some have real advantages over others, Sphere/Sphere,AABB/AABB is orders of magnitude faster than some other primitive test. Your geometry is made of polygons so for visual accuracy this is probably the best test. Spot lights are made of cones and so are some other physical phenomenon, so they may be a good choice of a basic primitive.

So you have to choose for your specific application with it's specific requirements what set of primitives will best suit it's needs.

Share this post


Link to post
Share on other sites
This is a great idea i have to admit. I haven't thought of that before. =D

I stopped thinking about switch and so on but this is mad.

Well... i think the variety of combinations is possibly restrictable to 2...

( i ) boundingsphere->boundingspheretree->triangles and
( ii ) boundingsphere->octree->triangles


houses, boxes, almost any static object is describable by way ii...

humanoid, animals and anything that really has bones with i...

thank you =D

Share this post


Link to post
Share on other sites

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

Sign in to follow this