   Creating simple contact graphs
  Hello, like most people here I'm creating a 2d rigid body simulator for some purpose (mostly to toy with :)). Currently I have rigid bodies consisting of polygons. I'm reading the following paper Non convex Rigid Bodies with Stacking (http://www.cs.ubc.ca/~rbridson/docs/rigid_bodies.pdf) trying to implement the explained algorithm. I understand most of the article, but a few things aren't clear to me.1 - Concerning the Contact Graph, I have a moderately solid idea of how to create this (Tarjan with DFS or BFS). But for my simulation I think I could simplify this. In my 2d simulation the only immovable object is the ground plane. Since the graph lets you process the contacts from the immobile objects up, shouldn't I be able to simplify this by taking the difference between two contact points, with the dot product of the ground plane normal? I.E.cp_difference = cp1 - cp2;cp_dot = cp_difference * <0, 1>If the dot product is > 0 than cp2 is under cp1, else the opposite is true. This would order the list from the bottom up. Would this be an accurate way to generate a simple contact graph for the case of a single ground plane being the only immovable object? Or am I missing the point of contact graphs completely?2 - Also, Are the contact points between objects stored on a per object basis? I.E. I have a box, and its colliding with 3 other boxes, so in that box object in question I have an array containing those 3 contact points. Or are the contact points stored in a global array containing ALL contact points?3 - My code uses the SAT for collision detection. It returns 1 point for all cases (Vertex-Vertex, Edge-Vertex, Vertex-Edge) except Edge-Edge where 2 points are returned. If I have 2 points I can collapse it into once contact point situated in the midpoint. When storing the contact pairing information, for edge edge collisions should I store these two points? I think the answer should be yes, since the moment arm would be shorter with the midpoint. I think you could account for it if you measured the true moment arm and applied it at the midpoint.Those are a few of the things currently bothering me, hopefully they're clearly explained. Any advice would be more than welcome :), as I'll certainly have more questions as I explore this.   
  hmm the afaik, SAT should return 6 cases. vertex-face, face-vertex, edge-edge, edge-face, face-edge, face-face. for multiple contacts (edge-face, face-edge, face-face), you can calculate the contact patch (or segment in case of edges) by doing clipping using edge extrusion of the clipping face. I suppose you could reduce the patch to one contact, by taking the centre of the contact patch.the vertex-vertex, edge-vertex shouldn't occur in normal condition. But there is no harm considering them. for edge-edge, I'd take the points on the the edges the closest to each other on the edges. This is usually derived by doing a edge-edge distance calculation. as for the contact graph, I couldn't say I never went that far. I'm also unclear if it would be better to keep the contacts in object space, or in world space, depending on how things work. As you move away from one intersection, that will affect all the other contact's state. but I don't know how the contact graph resolution works for sure.   ;  Well my implementation is in 2d. Therefore face collisions shouldn't occur, at least it was my knowledge that face-vertex/edge and vertex/edge-face collisions don't happen in 2d.Your right vertex-vertex and edge vertex shouldn't occur (and don't seem too, ever) but I do consider them just in case. Considering contact graphs, I did find a really good explanation on their construction from this website.http://www.trefny.net/contacts.htmlI don't think there's any difference in keeping the contact points in local or world space. My question, however, was do the objects store only their own points of contact? so to get an array of all contacts I have to iterate through all the objects? I think this one is a no, Since I believe I'm confusing Contact Pair and Contact Points.So unless I'm wrong, the contact graph is really an array containing objects, which refer to the 2 bodies that are creating the contact (along with information about the contact itself).I'm just happy I already know BFS and DFS.   ;  I have the contact graph code from the above website (http://www.trefny.net/contacts.html) mostly working, I don't seem to see any difference in the ordering with a few objects. Something in this guys code doesn't make any sense to me however. In his collision_contact struct, he hasbool bequal(const collision_contact & rhs) const;// 'bequal' returns true when '*this' and 'rhs' point//  to the same two rigid bodiesI'm unsure as to how he's comparing the two contacts here. His explaination seems to suggest he returns true ifthis.rbs0_p = o.rbs0_p AND this.rbs1_p = o.rbs1_p;But this can't possibly be the case. A couple different variations give different results, but at this point they all seem to be correct, so I'm not sure which one it isthis.rbs0_p = 0.rbs1_p OR this.rbs1_p = 0.rbs0_p;this.rbs0_p = 0.rbs1_p AND this.rbs1_p = 0.rbs0_p;this.rbs0_p = 0.rbs0_p OR this.rbs1_p = 0.rbs1_p;this last one is the one I'm currently using. Here are a couple pictures of the results so far :)