Collision with a quad terrain

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
c0der
Posts: 74
Joined: Sun Jul 08, 2012 11:32 am

Collision with a quad terrain

Post by c0der »

Hi,

I have a terrain partitioned into a quadtree and the rendering is fast, but collision detection for physics is slow.

I am trying to test an OBB against the terrain as follows:

Basically, if the node is in the viewing frustum, and we are at the leaf node, I check if the OBB is above that visible node's AABB. This is a fast SAT test that doesn't affect the frame rate.

Now that there are 2192 triangles in the node that the OBB is above, it is inefficient to perform the SAT test on every one of those triangles and it is slowing the frame rate considerably for physics.

Does anyone have any suggestions on how I would go about performing the collision detection. Should I build a smaller quadtree out of those triangles and do the collision tests?

Code: Select all

void CollisionQuadtreeNode *pNode, Plane *pFrustumPlanes, const OBB &obb)
{
    // Check if node is in the view frustum
        if(pNode->aabb.cull(pFrustumPlanes)==CULLED) {
                return;
        }
        
        int nCountChilds = 0;
        
        for(int i=0; i<4; ++i) {
                if(pNode->pNodes[i]!=NULL) {
                        nCountChilds++;
                        testOBBIntersect(pNode->pNodes[i], pFrustumPlanes, obb, pContactData);
                }
        }
        
        // This is not a leaf node as it has children
        if(nCountChilds>0)
                return;
 
        // Test for overlap on the x-z plane
        OBB tmpOBB = obb;
        tmpOBB.m_vCenter.y = pNode->aabb.m_vCenter.y;
 
        // Check if OBB is above the terrain node
        if(!pNode->aabb.intersects(tmpOBB))
                return;
 
        for(int i=0; i<pNode->iNumTriangles; ++i) {
                if(!pNode->triangleList[i].m_AABB.intersects(obb))
                        continue;
                
                // Collision with triangle's AABB occurred
                break;
        }
 
        return;
}
c0der
Posts: 74
Joined: Sun Jul 08, 2012 11:32 am

Re: Collision with a quad terrain

Post by c0der »

Solved, used a grid to partition the terrain and simple AABB tests to narrow the collision down to 6 triangles and finally applied SAT to generate contacts between the terrain triangles and OBB.

Very fast for anyone who is trying to find a way to do OBB-terrain collisions with physics response
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Collision with a quad terrain

Post by Dirk Gregorius »

Nice! There was another I thing I noticed. You cannot cull collision if it not in the camera. This essentially means everything that is not visible will fall out of the world.
c0der
Posts: 74
Joined: Sun Jul 08, 2012 11:32 am

Re: Collision with a quad terrain

Post by c0der »

That's true! It is interesting how large games such as GTA handle a large amount of collisions in a huge world. Perhaps things like using really simple primitives like bounding spheres to keep objects from overlapping each other when they're out of view or too far from the camera for the detail to be seen, and taking advantage of putting objects to sleep.

This is similar to using LOD for rendering the world, as for rendering kilometres of terrain.

That's just my thoughts on the logic of it but I am not really sure if it's the best approach.

What do the experienced pros think of this?
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Collision with a quad terrain

Post by Dirk Gregorius »

They only maintain a small portion of the game in memory and stream in what is needed.
c0der
Posts: 74
Joined: Sun Jul 08, 2012 11:32 am

Re: Collision with a quad terrain

Post by c0der »

Found a problem with this approach, for anyone who may run into this problem...

Testing against 6 triangles generates more contacts than necessary, leading to jittery physics. An example is two contacts on neighbouring triangles are too close and cause double the impulse in close proximity.

I have now used a convex hull approach, building a convex hull dynamically according to the triangles of the terrain that the OBB intersects and finally running a SAT test against the hull.

This is a much better approach. I implemented the quickhull algorithm to build the convex hull. I have not made it robust yet i.e. handling if the outer point is too close to the hyperplane of a face etc. but after running some tests, it works perfectly well for a terrain, where the patches of triangles collided against are near convex anyway.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Collision with a quad terrain

Post by Dirk Gregorius »

That should not double the impulse. Say you solve the same contact point twice in a row. In the first pass you solve the contact point the relative velocity becomes zero. In the second pass the relative velocity is zero and there is no impulse. So if the impulse doubles this is a bug. I would drop a box onto a vertex where eight triangles originate. This should not make any problems. I would solve this first.

The convex hull approach is nice, but what if the triangles are concave? You might get ghost collisions. I would still use some processing. E.g. for the example above you really don't want to solve eight manifolds. Even though it is robust it is just not efficient. Instead I would cluster triangles with a similar normal (e.g. k-means). Three clusters are usually sufficient. There is an article about this in GPG 4 by Adam and Pierre from nVidia.
Post Reply