getCollisionResultPosition SLOW! framrate drop

[fleven_2001]

Hi all, this is my first post, and I'm sorry it's on a bad note, but i have had some problems with the built in collision detection... and i know it's probably better to use a physics engine, but i only wanted basic collision detection... and it's too late in my project to start something new...

Basically, we have a class "enemy"...

each "enemy" created calls the collisionManager class that stores an octtree triangle selector for that node in a array. then when any enemy moves it uses the following function:

bool CollisionManager::CheckCollisionPosition(vector3df &position, vector3df &newDirection, vector3df elipseRadius, int collisionID, vector3df gravity)
{
triangle3df triout;
bool outFalling;

//Create Metaselector for the mesh collision
IMetaTriangleSelector* collidableMeshes = m_smgr->createMetaTriangleSelector();


//loop through all available meshes and add all meshes that are NOT the current mesh.
for (int i = 0; i < TriangleSelectors.size(); i++)
{
if (i != collisionID)
collidableMeshes->addTriangleSelector(TriangleSelectors);
}

//return the resulting position.
position = m_smgr->getSceneCollisionManager()->getCollisionResultPosition (collidableMeshes,
position,
elipseRadius, //size of elipse
newDirection, //direction of player
triout, //triangle that has the collision
outFalling,
0.0005f, //sliding factor
gravity //gravity
);

if (triout.pointA.X == 0 && triout.pointA.Y == 0 && triout.pointA.Z == 0)
return false;
else
return true;
}

the function takes the position of the enemy, the direction of the enemy, the precomputed elipse for collision detection, an int "collisionID" which is returned when the collisionManager adds the triangle selector to the list, and returns that nodes position in the list, and the gravity

the function itself works GREAT, until you add more than about 6 enemies... after which the framerate drops by about 5 frames per enemy... and when we were looking for at least 50 enemies, thats completely unplayable...

so any help would be greatly appreciated...

Thanks in advance!

[vitek]

It looks like you have a memory leak. You should probably drop collidableMeshes after you get the collision result. That probably isn't totally related to your problem, but it is an issue that should be addressed.

Think of this. If you call this function for every node and you have N nodes, this function is called N times. Every time it is called, you do collision testing against N-1 nodes. So there are basically N^2 collision tests happening. As N grows, the number of collision tests grows exponentially. That is a problem. Especially since an actual collision test is so expensive when using a triangle selector that uses mesh faces.

So you have a few options. Probably the simplest is to only do collision tests using triangle selectors against nodes that are potentially colliding with the current one. Your code would be similar, but you would need to keep a pointer to the node that owns the triangle selector so that you can see if the boxes are intersecting...

Code: Select all

// you need to be able to get a pointer to the node you are testing against
core::aabbox3df mine = node->getBoundingBox();
node->getAbsoluteTransformation().transformBoxEx(mine);

//loop through all available meshes and add all meshes that are NOT the current mesh. 
for (int i = 0; i < Nodes.size(); i++) 
{ 
  if (Nodes[i] != node) 
  {
    core::aabbox3df yours = Nodes[i]->getBoundingBox();
    Nodes[i]->getAbsoluteTransformation().transformBoxEx(yours);

    if (yours.intersectsWithBox(mine))
      collidableMeshes->addTriangleSelector(Nodes[i]->getTriangleSelector()); 
} 

// now collidableMeshes only contains triangle selectors
// for nodes that are potentially intersecting with this one.
// the collision function doesn't have to search through
// triangles that are not going to be close enough to touch.

You could also get more sophistocated and implement a proximity system. That way you don't have to do the bounding box transformation and test for every node, only the ones that are in the same sector as the one you are examining.

Travis

[hybrid]

A short note: N^2 is polynomial, not exponential.
What seems to be surprising is that the frame rate drops suddenly (maybe you use vsync? Then, higher rates are limited at 60 FPS.)

[fleven_2001]

thanks everyone for the quick replies!...

in an attempt to try and fix this issue, i removed the collidableMeshed from the function, and only used the terrains TriangleSelector (called LevelSelector) like so:

bool CollisionManager::CheckCollisionPosition(vector3df &position, vector3df &newDirection, vector3df elipseRadius, int collisionID, vector3df gravity)
{
triangle3df triout;
bool outFalling;

//return the resulting position.
position = m_smgr->getSceneCollisionManager()->getCollisionResultPosition (LevelSelector,
position,
elipseRadius, //size of elipse
newDirection, //direction of player
triout, //triangle that has the collision
outFalling,
0.0005f, //sliding factor
gravity //gravity
);

if (triout.pointA.X == 0 && triout.pointA.Y == 0 && triout.pointA.Z == 0)
return false;
else
return true;
}

thus removing the memory leak, and the looping... and yet it still drops in frame rate after about 6 enemies... (and i am not using vsync as i get 160 fps with only 1 enemy)...

i really dont know what to do...

[vitek]

A short note: N^2 is polynomial, not exponential.

You've corrected me on this before. [note: edited]

Travis

[hybrid]

It was just thought as a little note, but let's continue this off-topic some more: We are not talking about the algebraic ring of polynomials, but the so-called O-notation for the asymptotic behavior of functions (in our case run-time behavior). You can find the whole stora here:
http://en.wikipedia.org/wiki/Landau_not ... _functions
but in short there are three groups: Linear, polynomial, and exponential functions. As you said exponential functions have the argument as an exponent: f(x) = b^x, that's why x^2 is not exponential - it's just squared. Exponential functions are not efficiently computable even for small numbers, while polynomial functions are said to (but are often found to be infeasible as well for larger numbers, esp. for larger exponents). That's why the n*log(n) class is interesting. You can find many algorithms which belong to this class, and you can use algorithms of this class even for huge numbers, i.e. for large problems.
BTW: Every function can be represented by the exponential function, but this does not help when characterizing functions...

[rogerborg]

You could also get more sophistocated and implement a proximity system. That way you don't have to do the bounding box transformation and test for every node, only the ones that are in the same sector as the one you are examining.

For example, maintain an array of pointers to nodes that's ordered by (e.g.) X-coordinate. Then you only have to check against the nodes on either side of the checking node in the array, until you reach a node (in either direction) that's too far away for it to possibly collide. This will drastically cut down on the amount of checking you need to do, except under pathological conditions where all of your nodes end up with similar X co-ords.

Keeping the array sorted is a qsort() after they've all been moved, or a trivial bubblesort before doing the collision check for each node.

[kburkhart84]

You could also get more sophistocated and implement a proximity system. That way you don't have to do the bounding box transformation and test for every node, only the ones that are in the same sector as the one you are examining.

This is probably your best bet. I know you aren't using a physics API apart from Irrlicht, but I want to comment that most of them probably use such a proximity system to knock out potential collision as early quick tests. You probably should do the same before going so deep as the actual tri-tri test.