Jump to content
  • Advertisement
Sign in to follow this  
d07RiV

Contact creation

This topic is 1058 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

As suggested by Dirk, I'm creating this topic to discuss some of the questions I had after reading through his presentation (http://media.steampowered.com/apps/valve/2015/DirkGregorius_Contacts.pdf).

 

I actually only have one question atm. I haven't seen any mention of caching contacts between frames. If you generate the whole manifold on each frame, how do you find the corresponding contacts from the previous frame? Especially if some contact points are the result of a clipping operation, they might change over time even when converted to local space.

Share this post


Link to post
Share on other sites
Advertisement

I have a contact for each pair of overlapping shape proxies. The contacts are persistent over frames. When I update the broadphase and detect an overlapping pair I first check if I already created a contact for that pair. Each shape has a list of associated contacts. So I simply search the shorter list. Alternatively you could have a simple hashtable. 

 

Next I create the new manifold. If the new manifold was created from the same features as the old one I match the new points with the old points using the clipping Ids. I don't use any heuristic based on distance or local contact points. 

 

In order for this to work you need relatively stable features. You need to favor one face over the other and face contacts over edge contacts. You can find an example here (b2CollidePolygons): https://github.com/erincatto/Box2D/blob/master/Box2D/Box2D/Collision/b2CollidePolygon.cpp

 

const float32 k_tol = 0.1f * b2_linearSlop;
if (separationB > k_rel * separationA + k_tol)

 

I suggest using combined relative and absolute tolerances and incorporate the edge separation as well:

http://realtimecollisiondetection.net/pubs/Tolerances/

 

You can find an example of the contact matching here:

https://github.com/erincatto/Box2D/blob/master/Box2D/Box2D/Dynamics/Contacts/b2Contact.cpp

 

There is also some example lib called Box2D Lite which is even easier to follow. It is part of one of Erin's presentations here (I think in GDC 2006):

http://box2d.org/downloads/

 

As a side note:

The pair management depends a bit on your broadphase. SAP has natural begin, persist, and end overlap events. When using a dynamic tree things are a bit different. These are really just implementation details. You just need a way to find existing contacts between pairs. Then simply match the new manifold points with the old ones.

 

We did discuss the contact ID creation at the end of this thread:

http://www.gamedev.net/topic/667499-3d-sat-problem/

 

HTH,

-Dirk

Edited by Dirk Gregorius

Share this post


Link to post
Share on other sites

Oh, and maybe for terminology. There is one contact for each pair of overlapping shape proxies. A contact can have several manifolds. In practice I have a convex contact (sphere, capsule, and hull) which has exactly one maniold and a mesh contact which has up to three. Mesh contacts are bit more involved, so maybe let's keep that for another discussion.

 

Note that some engines insert bodies/compounds into the broadphase. In that case you would need a mid-phase to dispatch down to the pair level.

Edited by Dirk Gregorius

Share this post


Link to post
Share on other sites

If you're using clipping you want to assign some unique values (perhaps based off of topology indices) to each possible clip point. Just make sure that there's a unique ID for each point created as an intersection of features from each shape.

 

I used Sutherland Hodgman clipping, and for some reason it was really difficult for me to come up with code that would create appropriate IDs. In Box2D Lite (link above in Dirk's first post) there's an example that can be extended to 3D pretty easily. I ended up drawing a lot of pictures/staring at Erin's code until the trick finally appeared to me. Hopefully others won't find it as difficult to figure out as I did.

Edited by Randy Gaul

Share this post


Link to post
Share on other sites
Ah so you just assign an ID based on what you clipped against what? I did read through Box2D Lite, I remember that FeaturePair struct which I didn't pay too much attention to.

My broadphase works similarly to what you described, checking all previous pairs to see if the boxes still intersect, and adding new pairs for boxes that moved (with a tree). I don't plan on using meshes so contact pair and manifold is the same thing for me.

Oh also you seem to have some inconsistency when choosing the contact point - for sphere vs sphere (and similar ones) you use a point halfway between the surface points, while for hull vs hull the point is always on one of the bodies. Is there any reason for that? Edited by d07RiV

Share this post


Link to post
Share on other sites

Yes, I use the feature indices (e.g. plane or edge index) to build ids. I use the half-edge data structure for my hull so this come really naturally. It is really simple and you can use anything that is consistent and creates unique ids. The link I send above discusses essentially the feature pairs for Box2D and Irlan made a nice sketch to illustrate the idea.

 

The choice has to do with the penetration correction. I found for spheres and capsules that choosing the middle of the surface points gives the most stable contact points. For the hulls you move the contact points onto the reference face for culling, so I kept them there. I think it doesn't make much difference in practice. I try to choose the contact points as coherent as possible and this is what I ended up with over the years - empirically! 

 

The art with contact points is really to find the same points again. E.g. for box vs box you could find up to 8 points. During reduction there are several combinations of four points that would be physically stable, but once you have chosen one you ideally want to find the same combination in the next frame again. You don't want the points to move around too much, because the solver would need to balance different torques every frame (hope that makes sense!) which would give it a hard time to converge considering the small number of iteration we usually use. We need to help as much as we can smile.png

Edited by Dirk Gregorius

Share this post


Link to post
Share on other sites

Thinking about it, putting the contact points always onto the surface of one shape might be a good choice for games as well. E.g. the normal points from A to B and the contact points are always on the surface of A is consistent and should help gameplay programmers.

 

The contact stuff has been solved long time ago and I didn't really think about it recently. I agree a more consistent choice might be better!

Share this post


Link to post
Share on other sites
Yeah not sure if I want to use halfedges, my goal is to use Javascript so some things are more natural here, and I don't want to create too many objects.

I'll try to see if I can do it right this time, my last attempt to rewrite my collision detection caused everything to explode sad.png

What happens if you use two points per contact, i.e. calculate velocity of body1 in pos1 and body2 in pos2? Is that completely wrong? Edited by d07RiV

Share this post


Link to post
Share on other sites
Okay I finally got my GJK to work, but what about SAT? Does it come down to testing all faces and pairwise edge cross products, or its something smarter than that (since you mention Gauss Maps)? I can't seem to find much info about it as google unfortunately thinks I'm trying to solve a boolean constraint system sad.png
 
Upd: Oh, I didn't have to look that far, its all right there *bonk*
http://www.valvesoftware.com/company/publications.html

By the way, completely unrelated, in your quickhull presentation, is it possible for the horizon to consist of more than one face? At least in 2D case, it seems easy to prove that if you pick the furthest vertex on every step, you will never 'see' other faces from the consequent vertices? Or does it have something to do with using fat planes/faces? Edited by d07RiV

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!