Kontakt Graph

Question

Für eine Physik-Engine, die ich baue, muss ich schnell feststellen, ob zwei starre Körper in Kontakt waren, im vorherigen Frame. Ich möchte, dass es so schnell wie möglich ist, also könntest ihr vielleicht ein paar Ideen mitbringen?

Das ist, was ich bisher habe. (Und es funktioniert gut, aber die ganze Sache bekam frage ich, wie ich es verbessern könnte.)

// 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

Sie könnten stattdessen ein Dictionary<PhyRigidBody, HashSet<PhyRigidBody>> verwenden, das einen bestimmten Körper zu einer Reihe von anderen Einrichtungen bildet sie in Kontakt war mit (Das heißt, Sie behalten jeden "Kontakt" zweimal, da jeder Körper in der Kontaktgruppe des anderen enthalten ist). Das würde die Struktur zusammen mit der etwas fischigen Equals Methode vermeiden. Ich bin mir nicht sicher, ob es eine Verbesserung ist, aber es ist eine Überlegung wert.

Answer 2

Ich bin verwirrt durch diese:

// 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); 

aber alles in allem kann ich nicht den Punkt. Wie viele Körper gibt es? Bewegen sich die Körper, so dass sich ihre Kontaktfähigkeit oft ändert? Könnten Sie sie einfach in ein räumliches Gitter fallen lassen? Wie oft müssen Sie wissen, was die Kontakte sind?

Ohne mehr über das Problem zu wissen, ist es schwer, viel zu sagen, obwohl mein Bauchgefühl ist, dass alles in Hash-Codes und Datenstruktur eingewickelt werden wird, kostet Sie große Zeit.