Generate every combination of objects (without duplicate) in a BSP Tree

Question

I am making a collision detection system using a Binary Space Partitioning Tree. I have two kinds of objects :

• Dynamic objects (characters, projectiles) whose collisions with other objects need to be checked,
• Static objects (like walls) which are not being tested for collision among each other but can only be tested against a dynamic object.

For that, I am using two data structures : a list for storing all my dynamic objects, and the BSP tree which contains every objects (dynamic or static). Therefore every dynamic object are stored in both structures.

Finally, I am performing my collision detection by looping over my list and using the tree to test each object like so :

foreach(DynamicObject dynobj in myListOfDynamicObjects)
{
    //check the collision against every close dynamic or static objects
    myBSPtree.CheckCollision(dynobj);
}

However, at this point, I didn't think about something : every collision check between two dynamic objects is made twice. For example :

                                                                \
List of dynamic objects : {dynA, dynB}            Tree :       dynA
                                                              /    \
                                                          static1  dynB

Combinations tested :

• dynA - dynA (useless case handled)
• dynA - static1
• dynA - dynB
• dynB - dynA (same as above)
• dynB - static1
• dynB - dynB

In order to skip a useless check, I thought of adding an attribute Order on each object : it would be a unique identifier given at the construction of the object and use like so :

if(dynA.Order < dynB.Order){ CheckCollision(dynA,dynB); }

That way, only one collision check is made for each combination of object.

My question is : if this technique is correct (I mean is it a good design ?), and since every object have a unique reference in C#, can I directly compare their reference like so : (?)

if(dynA.Reference < dynB.Reference){ CheckCollision(dynA,dynB); }

We can use object.ReferenceEquals to see if two references are equals but can we make an actual comparison of these references ?

Answer 1

I would take a good look at how Quake/2/3 handle this. There are a few optimizations you could consider here:

1) Use cubic sub-volumes as a 3-dimensional grid to cache what region of the BSP each solid lives in. This way, you only need to test each dynamic object against a subset of the entire tree. This is a huge performance improvement as the size of your BSP tree grows.

Here is my implementation of this, borrowed from Quake2 and heavily scrubbed for readability:

https://github.com/jdolan/quetoo/blob/master/src/server/sv_world.c

2) For avoiding duplicate collision checks, just introduce a counter on your main collision entry point, and increment it each time the function is called. When testing a given object, set its own collision counter to the current counter value. Check for that value before doing any work. This is how Quake avoids checking the same BSP nodes twice.

if (obj->collisionCounter == _collisionCounter) {
    return;
}

obj->collisionCounter = _collisionCounter;

If you want your collision code to be thread-safe, be sure you have a collision context structure for all collision parameters and state, and pass an instance of that structure into all of your collision functions. And, of course, implement the collisionCounter inside that struct. Quake calls this structure a trace_t, btw. And again, if it's at all helpful, here's mine:

https://github.com/jdolan/quetoo/blob/master/src/collision/cm_trace.c