Using the "BoundingFrustum" Class in multithreaded solutions

The Bounding-Frustum class can be used by many systems in many situations from lights and cameras to traversing binary space partitions and most likely this systems work on different threads(if you are not programming the next great pong), but the XNA implementation presents one problem:

it can’t be used from more than one thread at a time.

Some random person will come with something stupid to say here like “but you can lock the object“and my answer will then be “and waste valuable cycles while waiting for another thread to finish with this object and add some more overhead”, if you use this kind of scenarios in a game you will end up with code that is slower then it’s single-threaded counterpart.

To see the root of the problem you need a code reflection program, like Red Gate’s Reflector some multithreading background and some GJK background:

And the root of the problem is the Gjk object, why because it was designed to be used only from 1 thread at a time:
The first thread generates a gjk object
if (gjk == null)
{
   gjk = new Gjk();
}
The second thread sees that a gjk already exists and will call the Reset() function on the gjk invalidating the
data collected by the first thread
When the first thread looks for that data it can't find it and you get an exception.

Here is how I see a fix for the problem:

-The Gjk is an algorithmic object, this means it has no value after the end of the operation where it was involved.

-There is no reason to have more than one Gjk object per active thread because you can’t use more then one on the same thread and as stated it has no value after the operation was concluded.

Because of that a Gjk object should be static and more then that it should be thread static.

On a Pc this is easy enough just: 

[ThreadStatic] 
private static Gjk gjk;

ThreadStatic - means just that make an object that is static available just in the thread that spawned it.

static – the same object is available on all the instances of the object where it was stated.

But on the Xbox you must use a little bit of creativity:

private static Dictionary<int, Gjk> gjkObjects;

private static Gjk gjk2

{

   get

   {

      lock (typeof(BoundingFrustumThreedSafe))

      {

         if (gjkObjects == null)

         {

            gjkObjects = new Dictionary<int, Gjk>();

         }

         if (gjkObjects.ContainsKey(System.Threading.Thread.CurrentThread.ManagedThreadId))

         {

         return gjkObjects[System.Threading.Thread.CurrentThread.ManagedThreadId];

         }

         else

         {

            gjkObjects.Add(System.Threading.Thread.CurrentThread.ManagedThreadId, new Gjk());

            return gjkObjects[System.Threading.Thread.CurrentThread.ManagedThreadId];

          }

       }

   }

}

Basically the compact framework, the one on the Xbox has no knowledge about the ThreadStatic attribute so you must make one yourself.

When you will use this approach on the Xbox to bust your performance you should probably use it like this:

#if WINDOWS

if (gjk2 == null)

{

   gjk2 = new Gjk();
}

#endif

Gjk gjk = gjk2;

gjk.Reset();

So the whole lock operation can be performed only once per execution.

Another advantage on this approach is that you don’t generate as much garbage because you only generate as much Gjk objects as you need and you never dispose of them so the garbage collector never starts .

Now some words on the final implementation, Gjk and a bit of renting on my part.

Because the XNA Team in its infinite wisdom decided to make the Gjk object internal and some of the mapping functions internal I had to add them all in the class itself, this is wrong on so many levels(the function that generates the next point from an object in an algorithm should be part of that object),

But there was no other way.

The Gjk is one of the most used and abused types of algorithms in games today, it is good for any kind of convex object intersection including mesh intersections or object orientated bounding boxes, and it’s very fast the whole operation ends up in 4 to 6 steps.

I will add more articles on how to use it on convex mesh intersection detection, the idea is that this object should have been declared as a public object.

If you want a great explanation on how the Gjk works check this link http://mollyrocket.com/849 or if you don’t fancy video http://www.codezealot.org/archives/88 or do a Google search on "Gjk implementation" you will get a ton of hits.

Here is the complete source code of the modified files so you can use in your project, it's on Microsoft SkyDrive(if you have an account and you are not logged in you might not see them):
BoundingFrustum
GJK