• entries
    743
  • comments
    1924
  • views
    579629

Interesting

Sign in to follow this  
Aardvajk

74 views

Just made quite an interesting discovery.

I was previously doing object-object tests like:


for(std::vector::iterator I=Objects.begin();I!=Objects.end();++I)
{
for(std::vector::iterator J=Objects.begin();J!=Objects.end();++J) (*I)->ObjectCollide(*(*J));
}


and testing inside ObjectCollide() to ensure the object wasn't being tested against itself.

It occurred to me as I was having a nap on the sofa that each pair was being tested twice, first A to B, then B to A again.

Since ObjectCollide() moves both objects apart by the MSD and sets up both objects new velocities, the second check is redundant.

After messing about with some very silly ideas, such as each object maintaining a vector of pointers to objects already tested that it checked against at the start of ObjectCollide(), it occurred to me that given objects with the following indicies in the vector:

0 1 2 3 4

If 0 is tested against 1, 2, 3 and 4 then 1 only needs to be tested against 2, 3 and 4, 2 only needs to be tested against 3 and 4 and 3 only needs to be tested against 4. Thus all the pairs have been tested exactly once against each other.

So:


for(std::vector::iterator I=Objects.begin();I!=Objects.end();++I)
{
for(std::vector::iterator J=I+1;J!=Objects.end();++J) (*I)->ObjectCollide(*(*J));
}


and my calls to ObjectCollide() for 80 objects drops from 6480 per frame to 3240 per frame.

Obvious really, in retrospect. Just shows what a good idea the occasional nap on the sofa can be.

Out of curiosity, I fed some numbers into Excel and this chart shows the shape of the curve of comparisions needed as the number of objects increases:



I guess there is probably a proper name for this sort of curve, but lacking any formal knowledge about this sort of stuff, I haven't got a clue. I suppose this chart represents the number of unique pairs within a set of N objects.

Anyway, the outcome is that now, on my pretty low end PC, I can now keep 60 fps with about 630 map polygons and a cool 100 polygons bouncing about. All without any kind of spatial indexing.
Sign in to follow this  


4 Comments


Recommended Comments

Quote:
Original post by jjd
It's a quadratic function. In particular, y = x(x-1)/2.


Cheers. I thought there must be a well defined formula.

By the way, I don't see your Christmas avatar yet, jjd [smile].

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now