CODEWITHSUNDEEP
c++openglgraphicscollision-detectionbrute-force
sample_nickname
sample_nickname

Reputation: 301

Brute force collision detection for two objects too slow

I have a project to see if two objects (made of about 10,000 triangles each) collide using the brute force collision algorithm, rendered in OpenGL. The two objects are not moving. I will have to translate them to some positions and find e.g. 100 triangle collisions etc.

So far I have written a code that actually checks for line-plane intersection between these two models. If I got everything straight I need to check every edge of every triangle of the first model with the each plane of each triangle of the other model. This actually means 3 'for' loops that take hours to end. I suppose I must have something wrong or got the whole concept misunderstood.

     for (int i=0; i<model1_faces.num; i++) {
    for (int j=0; j<3; j++) {
        x1[j] = model1_vertices[model1_faces[i].v[j]-1].x;
        y1[j] = model1_vertices[model1_faces[i].v[j]-1].y;
        z1[j] = model1_vertices[model1_faces[i].v[j]-1].z;
    }
    A.x = x1[0]; 
    A.y = y1[0]; 
    A.z = z1[0];
    B.x = x1[1];
    B.y = y1[1];
    B.z = z1[1];
    C.x = x1[2];
    C.y = y1[2];
    C.z = z1[2];

    TriangleNormal = findNormalVector((B-A)*(C-A));
    RayDirection = B-A;

    for (int j=0; j<model2_faces.num; j++) {
        PointOnPlane = model2_vertices[model2_faces[j].v[0]-1]; // Any point of the triangle
        system("PAUSE");
        float D1 = (A-PointOnPlane)^(TriangleNormal);   // Distance from A to the plane of j triangle
        float D2 = (B-PointOnPlane)^(TriangleNormal);

        if ((D1*D2) >= 0) continue; // Line AB doesn't cross the triangle
        if (D1==D2) continue;       // Line parallel to the plane

        CollisionVect = A + (RayDirection) * (-D1/(D2-D1));
        Vector temp;
        temp = TriangleNormal*(RayDirection);
        if (temp^(CollisionVect-A) < 0) continue; 
        temp = TriangleNormal*(C-B);
        if (temp^(CollisionVect-B) < 0) continue; 
        temp = TriangleNormal*(A-C);
        if (temp^(CollisionVect-A) < 0) continue;

        // If I reach this point I had a collision //
        cout << "Had collision!!" << endl;

Also I do not know exactly where exactly should this function above be called. In my render function so that it runs continuously while rendering or just once, given the fact that I only need to check for a non-moving objects collision?

I would appreciate some explanation and if you're too busy or bored to see my code, just help me with understanding a bit more this whole concept.

Upvotes: 2

Views: 1200

Answers (2)

paddy
paddy

Reputation: 63481

As suggested already, you can use bounding volumes. To make best use of these, you can arrange your bounding volumes in an Octree, in which case the volumes are boxes.

At the outermost level, each bounding volume contains the entire object. So you can test whether the two objects might intersect by comparing their zero-level bounding volumes. Testing for intersection of two boxes where all the faces are axis-aligned is trivial.

The octree will index which faces belong to which subdivisions of the bounding volume. So some faces will of course belong to more than one volume and may be tested multiple times.

The benefit is you can prune away many of the brute-force tests that are guaranteed to fail by the fact that only a handful of your subvolumes will actually intersect. The actual intersection testing is of still brute-force, but is on a small subset of faces.

Upvotes: 1

Marc Baumbach
Marc Baumbach

Reputation: 10473

Brute force collision detection often does not scale, as you have noticed. :) The usual approach is to define a bounding volume that contains your models/shapes and simplifies the intersection calculations. Bounding volumes come in all shapes and sizes depending on your models. They can be spheres, boxes, etc.

In addition to defining bounding volumes, you'll want to detect collision in your update section of code, where you are most likely passing in some delta time. That delta time is often needed to determine how far objects need to move and if a collision occurred in that timeframe.

Upvotes: 0

Related Questions