Jump to content
  • Advertisement
Sign in to follow this  
Kitasia

Managing a list of Contacts

This topic is 2780 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

I'm at a point where I want to recognize events that occur with contacts, and it's creating a bit of a problem.

Normally to generate contacts I'd clear the list each frame and then refill it with current contacts found, but because I'm not keeping any data, I can't keep record of any changes that occur.

It occurred to me, that I could avoid emptying the list everytime to track changes, but that would involve:
-A loop, checking to see if the contactpair exists already, everytime I generate a contact
-Looping over the final list of contacts, and removing contacts that aren't touching

I'm on the right track with this, or is there a better way?

Share this post


Link to post
Share on other sites
Advertisement

I'm at a point where I want to recognize events that occur with contacts, and it's creating a bit of a problem.

Normally to generate contacts I'd clear the list each frame and then refill it with current contacts found, but because I'm not keeping any data, I can't keep record of any changes that occur.

It occurred to me, that I could avoid emptying the list everytime to track changes, but that would involve:
-A loop, checking to see if the contactpair exists already, everytime I generate a contact
-Looping over the final list of contacts, and removing contacts that aren't touching

I'm on the right track with this, or is there a better way?


What I did was to create a separate data structure which persists to handle this - I created an overlap pair when two objects first touch and then remove it when they finally separate again. You can store a linked list of overlaps on each object using an index to ensure uniqueness:

Objects a and b

if (a.index < b.index)
{
a.AddOverlap(b);
}
else
{
b.AddOverlap(a);
}

That way you can look up the overlaps between a pair of objects really quickly. Hope that helps!

Cheers, Paul.

Share this post


Link to post
Share on other sites
I don't think I fully understand the post, but it did lead me to link into linked lists. If linked-lists can add on without allocating it would indeed be easier to embed the contact lists within the object, cutting out a great deal of looping.

Regardless of whether I understand it, thanks for the help! This was a very useful piece of info.

Share this post


Link to post
Share on other sites

I don't think I fully understand the post, but it did lead me to link into linked lists. If linked-lists can add on without allocating it would indeed be easier to embed the contact lists within the object, cutting out a great deal of looping.

Regardless of whether I understand it, thanks for the help! This was a very useful piece of info.


Heh heh - ok, let me try and simplify by example:

Suppose in one instance, your collision system returns a pair of objects A and B in that order:


ObjectsColliding(A, B);


and inside ObjectsColliding(), you add B to A's list of touching objects...

But then, on the next frame, the collision system reports objects B and A are colliding in that ordre


ObjectsColliding(B, A);


and inside you'd look at B's list of colliding objects, find A is not there yet and add it - but you've already added B to A's list above so it gets a bit messy...

If you always add the colliding object to object with the lower *index* of any two collision pairs, this problem goes away :)

Cheers, Paul.

Share this post


Link to post
Share on other sites
Okay that clears things up, but wouldn't you add A to B's list the first frame also? Otherwise B could never reference that it was touching A later on.

I was still thinking in terms of the first post but because you're looping through your own contacts to check if it already exists, instead of a list of every one that has occurred, the process is much speedier. I'd still like to keep a master list of contacts that's occurred during the frame and clear it each time, but in addition to that, I'll have objects keep record of contacts. Without a master list wouldn't you have to check every object in the contact resolver other than simply contacts?

Share this post


Link to post
Share on other sites

Okay that clears things up, but wouldn't you add A to B's list the first frame also? Otherwise B could never reference that it was touching A later on.


You wouldn't add A to B's list because then you'd be duplicating information - it is true that B can never know it was touching A; this may be a problem for you depending on your application, for us it was ok because we we were generally dealing with collision pairs anyway which meant we can always do the index check and look up the lower indexed object's touching list.



I was still thinking in terms of the first post but because you're looping through your own contacts to check if it already exists, instead of a list of every one that has occurred, the process is much speedier. I'd still like to keep a master list of contacts that's occurred during the frame and clear it each time, but in addition to that, I'll have objects keep record of contacts. Without a master list wouldn't you have to check every object in the contact resolver other than simply contacts?
[/quote]

Yes you can probably want to keep a master list of contacts which you clear every frame, we did that as well... The touching objects stuff was actually used in our broad-phase collision system as well, so it was dual purpose.

Cheers, Paul.

Share this post


Link to post
Share on other sites
Our solution was to use a dictionary; each object has a 16bit unsigned UID, combine two into a 32bit unsigned contact UID by combining two object UIDs (making sure to handle this consistantly, i.e always store the smaller UID in the high 16bits). If you have lots of objects you could do the same thing with 32bit object IDs and 64bit contact IDs.

The use of a dictionary might be a bit heavyweight. Also, we don't know/care about multiple contact points between two objects; the objects in our case were verts and edges (in 2D) so only one contact at a time was possible. For the more general case you'd need to either add some additional info to the UIDs (i.e the index of the verts/edges/faces which are participating in the collision) so that they each represent a single contact point, or use some sort of contact manifold object which represents n contact points between a pair of objects.

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!