Wednesday 10 February 2010

Another way to find your XNA Garbage

Like most people developing using XNA for the Xbox 360 eventually I encountered the frustrating situation where every minute or so my game froze for a few moments. With only the minimal of investigation the term Garbage Collection came to my attention.

What is garbage collection?

Garbage collection is the process used to remove unassociated items from the memory heap of the computer or console. This is necessary to make best use of the limited memory resources on the machine. What adds to the heap is outside the scope of this article but as a quick rule of thumb anything that needs a new statement infront of it will add to the heap.

The garbage collection process on a Windows PC is typically non-intrusive however the one on the Xbox 360 has a noticable impact on performance. We are therefore only talking about Xbox 360 garbage collection. It's worth noting that memory measurements on the PC are going to indicate the same areas of code using memory, so we can still debug garbage collection using the PC.

Garbage collection on the Xbox 360 happens when the heap has grown by 1M Bytes since the last garbage collection. If you can write your programme so the heap never grows that large during the game play, you will never notice garbage collection.

Memory usage is not a crime!

Before we go too far it is worth pointing out that all programmes NEED to use memory and the heap will always grow. It is usually many megabytes in size depending on the objects used in your programme. The heap is NOT garbage.

Many people also confuse memory usage with a memory leak. A memory leak is where your code continues to use more and more memory without releasing it for reuse when it is no longer needed.

Your programme will use memory and that memory usage may grow while the programme is running but that is not a memory leak. As we are talking about XNA which uses .NET which is managed code it is extremely unlikely that you could even accidentally cause a memory leak. That is one of the reasons for using a managed architecture like .NET because it deals with tidying up the memory you are using. It does that with the garbage collection process.

What is garbage then?

Garbage is made up of objects on the heap that we no longer need. More specifically items that are no longer linked to any active part of our code. Typically these are objects we create, use and discard. One common way to avoid garbage collection is to reuse objects rather than discard them. However this article is not how to get rid of the garbage but to show where the garbage is being created.

To find out about how to avoid garbage have a look at this article on the blog by Mike B. McLaughlin.

How can we tell where my code leaves stuff on the heap?

The typical way to find out what any programme is doing is to use a profiler. Two common ones for XNA are, the CLR Profiler and nProf. Both of these will provide loads of statistics to show you what your programme is doing while it is running. These should be your first port of call when you have a performance shortfall with your game.

Is there another way to measure the garbage?

There are times when for one reason or another a profiler does not give the information you need in the way you need it. As an example, and the reason I use an alternate solution, is because sometimes the CLR Profiler will not run with a particular programme. It just doesn't and no one can adequately explain why.

Rather than use an external tool to measure the memory usage we can build it in to our programme. That's the method I am demonstrating here.

The most significant part of the code simply measures the memory usage at a point in time and calculates the difference between that and the last measurement. The number recorded is the growth in memory during that update cycle.


// Call these before and after the method that we want to measure
public void Before(int pair)
{
 memBefore[pair] = System.GC.GetTotalMemory(false);
}

public void After(int pair)
{
 memAfter[pair] = System.GC.GetTotalMemory(false);
 CalcMemUsed(pair);
}

private void CalcMemUsed(int pair)
{
 long diff = memAfter[pair] - memBefore[pair];
 // Cumulative
 memUsedAllPasses[pair] += diff;
 if (diff > memUsedEachPass[pair])
 {
  memUsedEachPass[pair] = diff;
 }
 if (memUsedAllPasses[pair] < 0)
 {
  memUsedAllPasses[pair] = 0;
 }
 MeasureMemoryNow(pair);
}

private void MeasureMemoryNow(int pair)
{
 if (memAfter[pair] < memPrevious[pair])
 {
  // Set this level as the base to count from
  memLowest = memAfter[pair];
  // Clear other counters
  memUsedEachPass[pair] = 0;
  memUsedAllPasses[pair] = 0;
 }
 memPrevious[pair] = memAfter[pair];
 memGrowth = memAfter[pair] - memLowest;
}



If the total memory used has gone down there must have been a garbage collection process between the last update and this update. Therefore I set all the counters back to zero.

As mentioned above there is nothing wrong with memory usage, that is normal. All classes will use memory when they are created but what we are looking for is continuous growth.

I have created a class with the above methods in and just add that in to my code between compiler directives.


#if DEBUG
 // fixed location at the top left
 Garbage = new GarbageTools(ShorterClassName(this.GetType().ToString()), 
  new Vector2(5, 5));
#endif



How do we see what is going on?

Finally I needed a way to output the information without creating garbage! This is trickier than it sounds because any string manipulation will create garbage. Even adding a number to the end of a line of text or just changing that number will add a significant amount to the heap!

The solution is to do everything graphically. I use the name of the class followed by a tiny line graph showing the growth of the memory used since the last garbage collection. There are three lines because I have allowed for three separate measurements within any class. I deliberately put the graphs outside the title safe area because I don't want them to get in the way of play testing the game.


private const float lineThickness = 2f;
public const float maxScale = 550f;
public const float maxMainValue = 2600000f;
private const long warnByteLevel = 100;
private const long warnEachLarge = 2000;

// This must be inside an existing SpriteBatch.Begin() End() pair
public void Draw(SpriteBatch spriteBatch, SpriteFont spriteFont, Texture2D imagePixel)
{
 if (memUsedAllPasses[0] > warnByteLevel || memUsedAllPasses[1] > warnByteLevel)
 {
  Color colour = Color.Green;
  if (memUsedEachPass[0] > warnEachLarge || memUsedEachPass[1] > warnEachLarge)
  {
   colour = Color.Red;
  }
  spriteBatch.DrawString(spriteFont, className, positionText, colour);
  // Graph
  positionGraph.X = positionText.X + spriteFont.MeasureString(className).X;
  positionGraph.Y = positionText.Y + ((spriteFont.MeasureString(className).Y) * 0.5f) - lineThickness - lineThickness;
  // Same scale as the DebugMessages
  colour = Color.Orange;
  float lineLength = (float)memUsedAllPasses[0] / maxMainValue * maxScale;
  spriteBatch.Draw(imagePixel, positionGraph, null, colour, 0, Vector2.Zero,
    new Vector2(lineLength, lineThickness), SpriteEffects.None, 0);
  positionGraph.Y += lineThickness + 1;
  colour = Color.Violet;
  lineLength = (float)memUsedAllPasses[1] / maxMainValue * maxScale;
  spriteBatch.Draw(imagePixel, positionGraph, null, colour, 0, Vector2.Zero,
    new Vector2(lineLength, lineThickness), SpriteEffects.None, 0);
  positionGraph.Y += lineThickness + 1;
  colour = Color.Purple;
  lineLength = (float)memUsedAllPasses[2] / maxMainValue * maxScale;
  spriteBatch.Draw(imagePixel, positionGraph, null, colour, 0, Vector2.Zero,
    new Vector2(lineLength, lineThickness), SpriteEffects.None, 0);
 }
}



Somewhere in your game, probably in your central controlling class, the Draw(...) call for the garbage tool needs to be added to include all the classes you have added the measurements to. I have created a base class for most of my classes which includes the various garbage bits. I can then simply add a block of code to the end of my classes which call any sub classes as part of their DrawGarbage(...) method.


#region GARBAGE
#if DEBUG
// This is the same in each class
// Override and call the base then add other classes where necessary
public override void DrawGarbage(SpriteBatch spriteBatch, SpriteFont spriteFont, Texture2D imagePixel)
{
 // Draw our own first
 base.DrawGarbage(spriteBatch, spriteFont, imagePixel);
 // Add any other classes here
 // ...
 for (int i = 0; i < controllers.Count; i++)
 {
  controllers[i].DrawGarbage(spriteBatch, spriteFont, imagePixel);
 }

}
#endif
#endregion



That's it. Once the GarbageTool has been added to a class just use the Before(0) and After(0) calls round any code you want to measure.


public override void Update(GameTime gameTime)
{
 base.Update(gameTime);
#if DEBUG
 Garbage.Before(0);
#endif

 // Do normal game stuff here and the memory usage will be measured
 // ...
 
#if DEBUG
 Garbage.After(0);
#endif
}



I use this to reduce my garbage creation to very nearly nothing and avoid garbage collections during game play.

Download Source Code

XNA Garbage helper classes (4kb) Feb. 2010

Friday 5 February 2010

XNA Triangle Intersections to Ray and Sphere

I have converted examples of Ray to Triangle and BoundingSphere to Triangle intersections available on the Internet in to a XNA C# triangle class. It also includes a few other triangle related methods.

Download Source Code

Triangle XNA class (4kb) Feb. 2010

The triangle uses an array of Vector3's for the corner points.

public Triangle()
{
 Vertex = new Vector3[3];
 Vertex[0] = Vector3.Zero;
 Vertex[1] = Vector3.Zero;
 Vertex[2] = Vector3.Zero;
}

The Intersect Ray method is from the Creators club picking with triangle accuracy sample.


// Returns the distance from the origin of the ray to the intersection with 
// the triangle, null if no intersect and negative if behind.
public void Intersects(ref Ray ray, out float? distance)
{
 // Set the Distance to indicate no intersect
 distance = null;
 // Compute vectors along two edges of the triangle.
 Vector3 edge1, edge2;

 Vector3.Subtract(ref Vertex[2], ref Vertex[1], out edge1);
 Vector3.Subtract(ref Vertex[0], ref Vertex[1], out edge2);

 // Compute the determinant.
 Vector3 directionCrossEdge2;
 Vector3.Cross(ref ray.Direction, ref edge2, out directionCrossEdge2);

 float determinant;
 Vector3.Dot(ref edge1, ref directionCrossEdge2, out determinant);

 // If the ray is parallel to the triangle plane, there is no collision.
 if (determinant > -float.Epsilon && determinant < float.Epsilon)
 {
  return;
 }

 float inverseDeterminant = 1.0f / determinant;

 // Calculate the U parameter of the intersection point.
 Vector3 distanceVector;
 Vector3.Subtract(ref ray.Position, ref Vertex[1], out distanceVector);

 float triangleU;
 Vector3.Dot(ref distanceVector, ref directionCrossEdge2, out triangleU);
 triangleU *= inverseDeterminant;

 // Make sure it is inside the triangle.
 if (triangleU < 0 || triangleU > 1)
 {
  return;
 }

 // Calculate the V parameter of the intersection point.
 Vector3 distanceCrossEdge1;
 Vector3.Cross(ref distanceVector, ref edge1, out distanceCrossEdge1);

 float triangleV;
 Vector3.Dot(ref ray.Direction, ref distanceCrossEdge1, out triangleV);
 triangleV *= inverseDeterminant;

 // Make sure it is inside the triangle.
 if (triangleV < 0 || triangleU + triangleV > 1)
 {
  return;
 }

 // == By here the ray must be inside the triangle

 // Compute the distance along the ray to the triangle.
 float length = 0;
 Vector3.Dot(ref edge2, ref distanceCrossEdge1, out length);
 distance = length * inverseDeterminant;
}


The Triangle to sphere intersection is an expensive test compared to other intersections. I only use it to create level files. I do not use it in game.


// This is an expensive test.
// The result is true or false.
public void Intersects(ref BoundingSphere sphere, out bool result)
{
 result = false;
 // First check if any corner point is inside the sphere
 // This is necessary because the other tests can easily miss
 // small triangles that are fully inside the sphere.
 if (sphere.Contains(A) != ContainmentType.Disjoint ||
  sphere.Contains(B) != ContainmentType.Disjoint ||
  sphere.Contains(C) != ContainmentType.Disjoint)
 {
  // A point is inside the sphere
  result = true;
  return;
 }
 // Test the edges of the triangle using a ray
 // If any hit then check the distance to the hit is less than the length of the side
 // The distance from a point of a small triangle inside the sphere coule be longer
 // than the edge of the small triangle, hence the test for points inside above.
 Vector3 side = B - A;
 // Important:  The direction of the ray MUST
 // be normalised otherwise the resulting length 
 // of any intersect is wrong!
 Ray ray = new Ray(A, Vector3.Normalize(side));
 float distSq = 0;
 float? length = null;
 sphere.Intersects(ref ray, out length);
 if (length != null)
 {
  distSq = (float)length * (float)length;
  if (length > 0 && distSq < side.LengthSquared())
  {
   // Hit edge
   result = true;
   return;
  }
 }
 // Stay at A and change the direction to C
 side = C - A;
 ray.Direction = Vector3.Normalize(side);
 length = null;
 sphere.Intersects(ref ray, out length);
 if (length != null)
 {
  distSq = (float)length * (float)length;
  if (length > 0 && distSq < side.LengthSquared())
  {
   // Hit edge
   result = true;
   return;
  }
 }
 // Change to corner B and edge to C
 side = C - B;
 ray.Position = B;
 ray.Direction = Vector3.Normalize(side);
 length = null;
 sphere.Intersects(ref ray, out length);
 if (length != null)
 {
  distSq = (float)length * (float)length;
  if (length > 0 && distSq < side.LengthSquared())
  {
   // Hit edge
   result = true;
   return;
  }
 }
 // If we get this far we are not touching the edges of the triangle
 
 // Calculate the InverseNormal of the triangle from the centre of the sphere
 // Do a ray intersection from the centre of the sphere to the triangle.
 // If the triangle is too small the ray could miss a small triangle inside
 // the sphere hence why the points were tested above.
 ray.Position = sphere.Center;
 // This will always create a vector facing towards the triangle from the 
 // ray starting point.
 InverseNormal(ref ray.Position, out side);
 ray.Direction = side;
 Intersects(ref ray, out length);
 if (length != null && length > 0 && length < sphere.Radius)
 {
  // Hit the surface of the triangle
  result = true;
  return;
 }
 // Only if we get this far have we missed the triangle
 result = false;
}


A good source of intersection code mainly in C/++ and theoretical papers is available from: realtimerendering.com

To get the vertices and triangles from an XNA model:
using XNA 3.1 is available from enchantedage.com
using XNA 4.0 I have a modified version of the above here.