Contact graph

Question

For a physics engine I'm building, I need to quickly determine if two rigid bodies were in contact, at the previous frame. I want it to be as fast as possible, so maybe you guys could provide some ideas?

This is what I've got so far. (And it works okay, but the whole thing got me wondering how I could improve it.)

    // I thought using a struct would be a good idea with only two values?
    struct Contact 
    {
        public readonly PhyRigidBody Body1;
        public readonly PhyRigidBody Body2;

        public Contact(PhyRigidBody body1, PhyRigidBody body2)
        {
            Body1 = body1;
            Body2 = body2;
        }
    }

    class ContactComparer : IEqualityComparer<Contact>
    {
        public bool Equals(Contact x, Contact y)
        {
            // It just have to be the two same bodies, nevermind the order.
            return (x.Body1 == y.Body1 && x.Body2 == y.Body2) || (x.Body1 == y.Body2 && x.Body2 == y.Body1);
        }

        public int GetHashCode(Contact obj)
        {
            // There has got to be a better way than this?
            return RuntimeHelpers.GetHashCode(obj.Body1) + RuntimeHelpers.GetHashCode(obj.Body2);
        }
    }

    // Hold all contacts in one big HashSet.
    private HashSet<Contact> _contactGraph = new HashSet<Contact>(new ContactComparer());



    // To query for contacts I do this
    Contact contactKey = new Contact(body1, body2);
    bool prevFrameContact = _contactGraph.Remove(contactKey);
    // ... and then I re-insert it later, if there is still contact.

Answer 1

You could instead use a Dictionary<PhyRigidBody, HashSet<PhyRigidBody>> that maps a given body to a set of other bodies it was in contact with (that means you keep each "contact" twice, as each body is included in the contact-set of the other). That would avoid the Contact struct altogether, along with the somewhat-fishy Equals method. I'm not sure it's an improvement, but it's worth considering.

Answer 2

I'm confused by this:

// It just have to be the two same bodies, nevermind the order.
return (x.Body1 == y.Body1 && x.Body2 == y.Body2) || (x.Body1 == y.Body2 && x.Body2 == y.Body1);

but overall I don't get the point. How many bodies are there? Do the bodies move so their contact-ness changes often? Could you just drop them into a spatial grid? How often do you need to know what the contac-tions are?

Without knowing more about the problem it's hard to say much, though my gut feeling is that getting all wrapped up in hash codes and data structure is going to cost you big-time.