Collisions with Nested Compound Shapes

[karantza]

Hi - I've been working on a project where I need to identify which child object of a compound shape is involved in a collision. I'm iterating over all the collision manifolds, and this works fine, however there's a particular case where I can't find a way to get the shape involved, and that's when I have nested compound shapes. The index saved in the contact is the index into the innermost compound shape, but there's no way to access the index into the next higher compound shape.

As a more concrete example, suppose we have: CompoundX [ A, CompoundY [ B, C] ] where A, B, and C are my basic collision shapes, and X and Y are my two compound objects. A collision happens with item B. In btCompoundCompoundCollisionAlgorithm.cpp, we first process the collision with the outer compound object, X:

Code: Select all

m_resultOut->setShapeIdentifiersA(-1,childIndex0); // this equals 1, since Y is at index 1 of X
m_resultOut->setShapeIdentifiersB(-1,childIndex1);

colAlgo->processCollision(&compoundWrap0,&compoundWrap1,m_dispatchInfo,m_resultOut);

...which recurses down into checking against Y...

Code: Select all

m_resultOut->setShapeIdentifiersA(-1,childIndex0); // this equals 0 now, since B is at index 0 of Y
m_resultOut->setShapeIdentifiersB(-1,childIndex1);

colAlgo->processCollision(&compoundWrap0,&compoundWrap1,m_dispatchInfo,m_resultOut);

... and by the time I get to checking the results...

Code: Select all

btManifoldPoint& pt = contactManifold->getContactPoint(j);
pt.m_index0 == 0; // Oops.

The '1' needed to figure out which index of X to look at is entirely lost, and I can't find my collision shape.

Due to the structure of the rest of the app it would be painful to try to flatten all my structures to only use a single compound shape in all cases. I'm wondering if there's some other approach I'm missing. One thought I had was to write a patch to include the root shape inside of the contact itself, so when iterating over the manifolds I'd have direct access to A, B, or C, but there might be an easier way.

Thanks!

[karantza]

Update: adding the btCollisionObjectWrapper to the btManifoldPoint let me access the specific shape that was collided with, but I realize that's not actually enough to uniquely identify what element of your scene has been hit, since shapes can be reused.

A proper solution to this really needs to store the indices into the compound shapes in some kind of hierarchy rather than just the one field in the manifold point. I might suggest leaving the partID and index fields to refer to triangles only, and adding something new to deal with compound shapes - perhaps a linked list, so for every compound shape you come across in your traversal you can look at the next index.

Totally off the top of my head, something roughly like this:

Code: Select all

// Some simple object to store a list of indices
struct CompoundIndex { 
    int index;
    CompoundIndex* next;
};

btManifoldPoint {
...
int m_index0;
int m_index1; // no longer overloaded for compound shapes

// Add this:
CompoundIndex* m_compoundIndex; // only set if the point is in a compound shape
...
};


// Later, when processing collisions

btManifoldPoint& pt = contactManifold->getContactPoint(j);
btCollisionShape* shape = collisionObject->getCollisionShape();
CompoundIndex* ci = pt.m_compoundIndex;

// step through the compound shape heirarchy
while (ci != nullptr) {
    printf("Inside of compound shape: %p", shape);
    shape = ((btCompoundShape*)shape)->getChildShape(ci->index);
    ci = ci->next;
}
printf("Shape involved in collision: %p", shape);

// Would expect my example above to produce:
Inside of compound shape: <ptr to X>
Inside of compound shape: <ptr to Y>
Shape involved in collision: <ptr to B>

This would give you enough detail to be able to figure out exactly what object is involved in a contact no matter how many compound shapes are in the way. If this is something anyone other than me would be actually interested in, I could implement it properly and make a pull request?

[kermado]

I'm interested in this also. It's been at the back of my head and I haven't really thought about it much.
Would it not be more simple to just store a pointer to the collision shape in btManinfoldPoint? Storing indices and then traversing the compound tree just seems to add a lot of unnecessary work.

[karantza]

In my local branch I am just saving the shape, and that's probably okay, but there are some cases where you really need to know one of the intermediate collision objects. For instance, I've got a large object composed of smaller compound objects, each of which is composed of a few separate shapes that might get reused. I need to know which of the smaller compound objects has experienced a collision. If you only store the shape, then you can use the shape's userdata pointer to get to where you need, but if that shape gets reused then your pointer is going to be reused too, and you can't differentiate.

(As an example, I'm thinking of Kerbal Space Program. You assemble a rocket out of smaller parts, and each part might contain a few collision shapes. Parts are often reused within a rocket, so when you get a collision you'd like to know "something hit engine #3", not "something hit the engine bell shape that you've reused in engines #1-#5.")

If you could traverse the tree, you could get to the actual unique object you need depending on your application. I admit this is a pretty specific issue, and 90% of the problem would be addressed by just having the shape available, but I ran into it at least.

[kermado]

Ah, ok. I'm coming from ODE which has kind of an inverse relationship to Bullet, where Geoms (collision shapes) "have" a rigid body rather than the other way round. Because of this I chose to enforce that collision shapes belong to at most one collision object. Hence I wouldn't have any issues here. This doesn't impact performance, only memory consumption (which is minuscule for me anyway).

[karantza]

I finally got around to forking properly and making a commit - here's my change that adds shape access to the manifold points. I need to clean up the tabs/spaces issue before I make a real pull request (also I think this has conflicts against master - will have to check those out), but if you want to make the modification yourself you can check this out for reference.

https://github.com/karantza/bullet3/com ... 3aa123ca4b

[kermado]

Looks good. I noticed today that the m_index0 and m_index1 fields don't work as assumed when the compound contains gImpact trimesh shapes. I logged this on github: https://github.com/bulletphysics/bullet3/issues/588
I think your solution should work in this case also.