Real-Time Physics Simulation Forum

Re: Collision with a quad terrain

2013-02-14T16:59:20+00:00

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.

Statistics: Posted by Dirk Gregorius — Thu Feb 14, 2013 4:59 pm

Re: Collision with a quad terrain

2013-02-14T06:22:12+00:00

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.

Statistics: Posted by c0der — Thu Feb 14, 2013 6:22 am

Re: Collision with a quad terrain

2013-01-28T00:37:29+00:00

They only maintain a small portion of the game in memory and stream in what is needed.

Statistics: Posted by Dirk Gregorius — Mon Jan 28, 2013 12:37 am

Re: Collision with a quad terrain

2013-01-26T13:28:53+00:00

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?

Statistics: Posted by c0der — Sat Jan 26, 2013 1:28 pm

Re: Collision with a quad terrain

2013-01-25T20:58:54+00:00

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.

Statistics: Posted by Dirk Gregorius — Fri Jan 25, 2013 8:58 pm

Re: Collision with a quad terrain

2013-01-25T09:46:02+00:00

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

Statistics: Posted by c0der — Fri Jan 25, 2013 9:46 am

Collision with a quad terrain

2013-01-13T03:25:06+00:00

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:

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; iiNumTriangles; ++i) {                if(!pNode->triangleList[i].m_AABB.intersects(obb))                        continue;                                // Collision with triangle's AABB occurred                break;        }         return;}

Statistics: Posted by c0der — Sun Jan 13, 2013 3:25 am