Manual Collision Resolution of btScaledBvhTriangleMeshShape?

Post Reply
K6L2
Posts: 7
Joined: Mon May 11, 2015 9:43 pm

Manual Collision Resolution of btScaledBvhTriangleMeshShape?

Post by K6L2 »

So I'm trying to use Bullet just for collision detection, so I can do my own collision resolution. I'm currently stuck on the resolution of a CapsuleShape and a static environment mesh using btScaledBvhTriangleMeshShape. I got CapsuleShape/CapsuleShape collision resolution working quite well relatively easily, however when I try to perform CapsuleShape/btScaledBvhTriangleMeshShape collision resolution, the capsule can just phase through the walls in between the seams of the triangles! I did some searching on google and in these forums and I found a few posts that describe using ContactAddedCallback to call the btAdjustInternalEdgeContacts function when btManifoldPoints are added to the manifold of the collisionObject that has the btCollisionObject::CF_CUSTOM_MATERIAL_CALLBACK flag set. In this way, I guess it tries to clear the internal edges so that you aren't getting any collision normals that don't match with the normals of the triangles (the walls of the static physical geometry)? But when I tried this, it still didn't do what I wanted. :cry:

For some insight into what my main loop looks like, I'm doing something very similar to what this guy is doing: http://hamelot.co.uk/programming/using- ... detection/

Each entity in the simulation has a function that gets called to resolve physical collisions with the static geometry:

Code: Select all

void Entity::resolvePhysicalCollision(btPersistentManifold* manifold)
{
    int smallestMpIndex = findClosestManifoldPoint(manifold);
    if(smallestMpIndex < 0)
    {
        return;
    }
    btManifoldPoint& smallestMP = manifold->getContactPoint(smallestMpIndex);
    moveBy(smallestMP.m_normalWorldOnB*fabsf(smallestMP.getDistance()));
}
And my findClosestManifoldPoint function just does this:

Code: Select all

int Entity::findClosestManifoldPoint(btPersistentManifold* manifold)
{
    bool foundValidMP = false;
    int smallestMPIndex = -1;
    btManifoldPoint& smallestMP = manifold->getContactPoint(0);
    btScalar smallestDist = INFINITY;
    if(smallestMP.getDistance() < 0.f)
    {
        foundValidMP = true;
        smallestDist = fabsf(smallestMP.getDistance());
        smallestMPIndex = 0;
    }
    for(int c = 1; c < manifold->getNumContacts(); c++)
    {
        btManifoldPoint& mp = manifold->getContactPoint(c);
        if(mp.getDistance() >= 0.f)
        {
            continue;
        }
        btScalar mpDist = fabsf(mp.getDistance());
        if(mpDist < smallestDist || !foundValidMP)
        {
            smallestDist = mpDist;
            smallestMP = mp;
            foundValidMP = true;
            smallestMPIndex = c;
        }
    }
    return smallestMPIndex;
}
Is this resolution technique not going to do what I want? Does anyone have any insight on what I might be doing wrong or if this is even possible?
K6L2
Posts: 7
Joined: Mon May 11, 2015 9:43 pm

Re: Manual Collision Resolution of btScaledBvhTriangleMeshSh

Post by K6L2 »

So after investigating the documentation a little more closely, I find the page for btAdjustInternalEdgeContacts http://bulletphysics.org/Bullet/BulletF ... _8cpp.html. It says that you have to generate the triangle normals using btGenerateInternalEdgeInfo (which I stupidly wasn't doing :oops:). So even after I presumably generated the btTriangleInfoMap using that function, it still wasn't doing what I wanted it to do; pills still collide with the static geometry and can be easily tunneled through by sliding along the wall until you find a seam. I looked at the description of the btGenerateInternalEdgeInfo function and it says:
Call btGenerateInternalEdgeInfo to create triangle info, store in the shape 'userInfo'.
, which I assumed meant that it stores the pointer in the btCollisionShape's m_userPointer (which I confirmed by doing some more google-fu). This is all fine and good, but it's not doing that! btGenerateInternalEdgeInfo is not assigning the newly generated btTriangleInfoMap to the m_userPointer of the btScaledBvhTriangleMeshShape (or even the btBvhTriangleMeshShape that it uses!). Here is the code that I use to create the shapes (with some debug code):

Code: Select all

    triMeshShape = new btBvhTriangleMeshShape(&triMesh, false);
    LOG("Room::generateCollisionData: triMeshShape->userInfo="+TOSTRING((int)triMeshShape->getUserPointer()));
    btGenerateInternalEdgeInfo(triMeshShape, &triangeInfoMap);
//    triMeshShape->setUserPointer(&triangeInfoMap);
    LOG("Room::generateCollisionData: triMeshShape->userInfo="+TOSTRING((int)triMeshShape->getUserPointer()));
    scaledTriMeshShape = new btScaledBvhTriangleMeshShape(triMeshShape, btVector3(1,1,1));
//    scaledTriMeshShape->setUserPointer(&triangeInfoMap);
My first LOG debug message here obviously prints "0" for the triMeshShape's m_userPointer. However, the second LOG message shows the same thing! I thought, "well shit, am I supposed to assign the user pointer myself?" But it turns out that even when I manually set the m_userPointer of either/both of the shapes, it still doesn't work. What is going on here?
K6L2
Posts: 7
Joined: Mon May 11, 2015 9:43 pm

Re: Manual Collision Resolution of btScaledBvhTriangleMeshSh

Post by K6L2 »

Well since nobody responded to my questions (presumably because nobody who visits here often enough knows anything about this approach, which was a little bit sad), I was able to solve my own problem. So, for future crazy people who want to implement a similar type of thing on their own, I will now outline my approach, technique, and results.

Step 1: Don't use btScaledBvhTriangleMeshShape, use btTriangleShape instead
Or even btBvhTriangleMeshShape for that matter. I haven't tried running any dynamic scenes or anything with Bullet, as my only objective for this little project was to utilize the collision detection engine (and not the physics, etc...), so I don't actually know if this step applies to those types of scenes. But what I can say for my application is this: btBvhTriangleMeshShape is useless. Why is it useless? Well, simply because I couldn't find any way of obtaining the normal of the triangle of the surface a given entity is colliding with. I thoroughly scanned the documentation, and found no such thing. If this doesn't hold true for some reason, and there really is a way of obtaining the triangle normal (NOT the collision manifold normal, those are two very different things), then consider me an idiot and disregard this step. Although, it would have been nice for someone to tell me I could actually do this earlier in this thread, but I digress. Just use btTriangleShape, as it just so happens to give you the ability to calculate the shape's normal, which can be accessed via the collision manifold. Also, as I stated before, I couldn't get btAdjustInternalEdgeContacts/btGenerateInternalEdgeInfo working at all. I still have no idea why, and I don't even care anymore.

Step 2: Pre-processing (detecting shared edges of triangles)
As we're reading in vertices from the mesh we exported from Blender (via Ogre3D in this case), we need to identify which triangles are sharing edges with other triangles, and what those edges are. We also want to store this information in the btTriangleShape object's userPointer so that we can look it up when it comes time to resolve the collision. Moreover, we only want to mark edges as being shared that have the same (or very similar) normals. This makes it so that entities can't tunnel through walls at convex corners. I accomplished this by keeping a map of vertex index pairs to a list of indexes of btTriangleShape wrappers. The wrappers just keep the shape together with the edge info so that I can refer to this later via the shape's userPointer. So we just keep adding triangles, and check all the edges on the map to see if there already is an edge with the same two vertex indexes, and if there is, we check the normals of the two triangles. If the normals are within a certain threshold, we mark the edges in both of the shape wrappers as being disabled. Because of the fact that the points in the btTriangleShape are always stored in the same order, we can easily interpret the bools for the edge flags later simply by storing them as a bool[3] array, which will come in handy during processing.

Step 3: Collision Resolution (Ignoring the flagged edges)
So, once the triangles have all been added to the scene, we can just do standard collision detection. For the resolution of each manifold between an entity and the static geometry triangles, I do the following. First: I just find the smallest negative distance manifold point. Once I found this manifold point, I simply move the entity in the distance of the manifold's normal. So where does the edge detection come into play? We do this in an isValid(btManifoldPoint& mp) function. This function originally just returned true if the distance of the manifold point was < 0. Now, I needed to make sure that manifold points along disabled edges were thrown out. To do this, I get the triangle shape's normal, and check the angle between that and the manifold normal. If this angle is greater than some threshold, then we know that the manifold is on the edge of the triangle. So all we need to do is check the squared distances of the world-space manifold point on the triangle with all 3 vertices, and find the largest one. The point with the largest distance is the point of the triangle we don't care about, and our edge in question is made of the other two points. And because the edge flags are in order relative to the order of the triangle's points, we know which index in our bool[3] array to check! If this flag at that edge index is false, we return false. Sooooo easy! 8)

Results:
There were a few other minor tweaks I had to do to get some weird edge cases working. For example: I had this situation where if you were moving capsule into a 90-degree concave corner, you could phase through the corner. Interestingly enough, it was only doing this when both directions were being held down simultaneously. I found out this was because when one of the walls resolved the collision, on the next manifold it would call refreshContactPoints and the manifold on the other wall would no longer have valid manifold points! I solved this by simply calling manifold->setContactBreakingThreshold(1.f) on manifolds that had static geometry in them before the call to refreshContactPoints happens. I have no idea if that number is a reasonable value or not, if even if that's the best place to call it, but it seems to work fine. Another obvious result is that this solution doesn't account for tunneling. If shapes are moving fast enough, you can in fact clip through the triangle mesh static geometry. I experimented a bit and found that setting a maximum speed of 32 units-per-second was a good number for preventing tunneling through static geometry (although it can still happen rarely sometimes). For my own purposes, this is an acceptable result; I don't really care about fast-moving physical objects anyway, and there are plenty of entertaining applications that can be made with this level of error (OoT, anyone?).

Here are some videos of my implementation working on a few edge cases:
https://www.youtube.com/watch?v=lz9KpFDIxsM
https://www.youtube.com/watch?v=dJ3M1Q5mz0E

I can't wait for someone to come around to let me know how (in)efficient my solution is... :roll:
Post Reply