# Collision code is extremly slow

## Recommended Posts

Tera_Dragon    260
The collision detection code detects collisions between models. It first checks the AABBs of each model against each other model, and if they intersect checks each triangle in the models for intersections. There are about 30 models in the scene, each with roughly 80 triangles. There is no spatal partitioning code, but it runs smoothly (at least 75fps, can't tell properly as I don't know how to stop my graphics card from limiting the application refresh rate to my screen refresh rate), but when two models intersect the frame rate drops to 2fps or less. Here is the code:
if ( m_collision )
{
// For each object
SceneManager sceneManager;
std::map <std::string, RenderableObject*> *objects;
objects = sceneManager.GetAll();
std::map <std::string, RenderableObject*>::iterator itr;

Resources::Model *model, *model2;
model = this->m_Model;

for ( itr = objects->begin(); itr != objects->end(); itr++ )
{
if ( itr->second == this )
continue;

model2 = itr->second->m_Model;

if ( Math::IntersectAABBs(this->m_aabb, itr->second->m_aabb) )
{
Math::Triangle tri1, tri2;

int vertexIndex;

Math::Triangle *tri = new Math::Triangle[ model2->m_nTriangles ];
for ( int i = 0; i < model2->m_nTriangles; i++ )
{
vertexIndex = model2->m_pTriangles[i].m_VertexIndices[0];
tri[i].A.x = model2->m_pVertices[ vertexIndex ].m_Location[0] + itr->second->m_pos.x;
tri[i].A.y = model2->m_pVertices[ vertexIndex ].m_Location[1] + itr->second->m_pos.y;
tri[i].A.z = model2->m_pVertices[ vertexIndex ].m_Location[2] + itr->second->m_pos.z;

vertexIndex = model2->m_pTriangles[i].m_VertexIndices[1];
tri[i].B.x = model2->m_pVertices[ vertexIndex ].m_Location[0] + itr->second->m_pos.x;
tri[i].B.y = model2->m_pVertices[ vertexIndex ].m_Location[1] + itr->second->m_pos.y;
tri[i].B.z = model2->m_pVertices[ vertexIndex ].m_Location[2] + itr->second->m_pos.z;

vertexIndex = model2->m_pTriangles[i].m_VertexIndices[2];
tri[i].C.x = model2->m_pVertices[ vertexIndex ].m_Location[0] + itr->second->m_pos.x;
tri[i].C.y = model2->m_pVertices[ vertexIndex ].m_Location[1] + itr->second->m_pos.y;
tri[i].C.z = model2->m_pVertices[ vertexIndex ].m_Location[2] + itr->second->m_pos.z;
}

for ( int i = 0; i < model->m_nTriangles; i++ )
{
vertexIndex = model->m_pTriangles[i].m_VertexIndices[0];
tri1.A.x = model->m_pVertices[ vertexIndex ].m_Location[0] + this->m_pos.x;
tri1.A.y = model->m_pVertices[ vertexIndex ].m_Location[1] + this->m_pos.y;
tri1.A.z = model->m_pVertices[ vertexIndex ].m_Location[2] + this->m_pos.z;

vertexIndex = model->m_pTriangles[i].m_VertexIndices[1];
tri1.B.x = model->m_pVertices[ vertexIndex ].m_Location[0] + this->m_pos.x;
tri1.B.y = model->m_pVertices[ vertexIndex ].m_Location[1] + this->m_pos.y;
tri1.B.z = model->m_pVertices[ vertexIndex ].m_Location[2] + this->m_pos.z;

vertexIndex = model->m_pTriangles[i].m_VertexIndices[2];
tri1.C.x = model->m_pVertices[ vertexIndex ].m_Location[0] + this->m_pos.x;
tri1.C.y = model->m_pVertices[ vertexIndex ].m_Location[1] + this->m_pos.y;
tri1.C.z = model->m_pVertices[ vertexIndex ].m_Location[2] + this->m_pos.z;

for ( int j = 0; j < model2->m_nTriangles; j++ )
{
if ( tri1.TriangleIntersects( tri[j] ) )
{
return true;
}
}
}
}
}
}
return false;


Then bottle-neck is not the triangle intersection method, as I have commented this out without effect. In an attempt to speed it up I have put all of the second models triangles into a temp triangle array in the first loop, instead of calculating the values again for each loop of the first model. This helped slightly, but only to bring the frame rate up to 2fps at most. What can I do to speed this up?

##### Share on other sites
The inner loop is being executed about 6400 times (80*80). It would be my first guess, but if that's the triangle intersection method and you commented the whole thing out with minimal effect...

My next guess would be simply that you're having more than one collision. What do you do after your collision detection? If your collision reaction doesn't resolve the condition, you could be jumping right back into the same detection code at least once per frame.

##### Share on other sites
Tera_Dragon    260
I meant that I commented out call to
if ( tri1.TriangleIntersects( tri[j] ) )
{
return true;
}
without much effect. However I tested that when I was calculating the second models triangles for each of the first models triangles, and testing it again now shows that it is in fact what is slowing it down.

Quote:
 If your collision reaction doesn't resolve the condition, you could be jumping right back into the same detection code at least once per frame.

I did not think of this, I will try and implement it.

##### Share on other sites
lightbringer    1070
Also keep in mind that as you check each model for every other model, every model gets checked twice.
A checks B
B checks A
C checks A
A checks C
This is probably not the reason for the slowdown, but you'd want to think about this anyway.

Edit: I'm struggling with your code, so if this is checked above or elsewhere already, sorry.

##### Share on other sites
Tera_Dragon    260
Thanks lightbringer, I just noticed that myself. It looks as though I'll have to create a class to look after how the models make the collision detection calls.

@Metaphorically: The only way I can come up with to not check the models every frame after a collison is to let the checks be made every frame (both for AABB and models) until the models collide, then not check those two models again until the AABBs separate? Though wouldn't this mean that they could collide, and before the AABBs separate, move together again but this time the collison would not be detected and they would go right through each other.

##### Share on other sites
dawidjoubert    161
if u can code a combust OCTREE then it will simple subdivid into your models say 5 levels deep and u can do almost perfect (except projectile) collisions.

Then again if ur models are animated that means a set octree per animation (only if its triangle animation), if its bone animation u can have the octree animate along :-)

##### Share on other sites
Guest Anonymous Poster
make a bounding sphere around each triangle in your mesh and keep the center pos and radius for each. Then before performaing your expensive triang vs triangle test, perform a sphere vs sphere test. If those intersect then perform the triangle vs triangle test. This will trade memory for speed. You can also look into BSP solution for your models as well. Testing one BSP against another. IN the end if you do not need perfect mesh collision you might want to consider something like mesh vs sphere (character is sphere/ellipsoid and is tested against mesh level).

## 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