View Occlusion

Since the play testing a few weeks ago I have been busy but I have not got a great deal to show for it yet.

My main task is trying to improve the draw performance so I can add a bit more detail to the levels and counter some of the additions I made based on the suggestions from the play testing.

I already do the typical view frustum culling and restrict the far plane range so I am only left with the more complex things to try.  Pretty much that is some form of pre-calculation of what is in view.

From the reading I have done Binary Space Partitioning (BSP) is not appropriate to the type of exterior vistas I would like to have in the game.  Therefore I have been concentrating on Occlusion Volumes (View or Visibility Cells).  My understanding being that these are areas of the map that if you are inside that area the models and meshes in view have been pre-calculated and therefore exclude meshes that are hidden by other meshes.  Both Unity and the Unreal Engine have variations of this that can be enabled depending on if it is appropriate for the map.

My map already uses a grid for storing, triangles and other information so adding additional heights to set the boundaries of the Occlusion Volume is trivial.  The tricky task has been calculating the mesh occlusion information.

I tried to calculate the view using the GPU.  I wrote a shader that stored an index for each model and returned that in the render target.  By drawing the view in sufficient directions from various points in each Occlusion Volume I would get a fairly accurate chance of knowing what was not in view and could therefore be ignored and not drawn in game.

I wrote all the code to do the calculations using the GPU but now for the problem.  Based on my initial trials it would take 72 hours to calculate the information for the entire usable area of the map!  I decided that was too long to run every time I made a tiny change to any game level!

I was also not confident that the result from the render target was completely accurate because my tests showed that if I put a float value in, the float I got out was close but not identical when rendered!

For my next trick I am attempting to use the grid and simply ray cast between cells.  I have not finished coding this but in the process I have used the Bresenham Line Algorithm.

The algorithm was originally intended to plot a line on early printers in the '60's.  I have come across it before but as it does not include every possible cell that a line could pass through it was no good for my impact calculations.  However for view occlusion I need something that is fast and where a few false positives for grid squares in view will not be harmful to the overall result.

It's only a tiny bit of code but I decided to put my C# XNA versions on CodePlex.  The important bit is that one of the variations I've included gives the result in order from the start to the finish point.  If it is of interest you can view and download it from there.

MipMaps and Textures

I've been tidying up and improving my code.  Mainly to get my level map files in to a single file and to use the content pipeline to load the maps in to the editor rather than having two sets of loading code.

In the process I have worked out how to create a texture in the content pipeline.

As I am now loading everything in the Content Pipeline I will no longer be using the code that creates MipMaps at run time.  Rather than forget how I did this, I thought I'd add the code here to remind me.

I won't go in to detail but a MipMap is simply a half size version of the main image stored in the same file. Typically several levels of ever decreasing images are stored in the same file.  They are used so that textures displayed at a distance look less pixelated.

If the above image did not use MipMaps then the distance would look grainy.

MipMaps At Run Time

This bit of code generates MipMaps at run time:

/// Create mipmaps for a texture
/// See: http://xboxforums.create.msdn.com/forums/p/60738/377862.aspx
/// Make sure this is only called from the main thread or 
/// when drawing is not already happening.
public static void GenerateMipMaps(
  GraphicsDevice graphicsDevice, 
  SpriteBatch spriteBatch, 
  ref Texture2D inOutImage)
{
  RenderTarget2D target = 
    new RenderTarget2D(
      graphicsDevice, 
      inOutImage.Width, 
      inOutImage.Height, 
      true, 
      SurfaceFormat.Color, 
      DepthFormat.None);
  graphicsDevice.SetRenderTarget(target);
  graphicsDevice.Clear(Color.Black);
  spriteBatch.Begin();
  spriteBatch.Draw(inOutImage, Vector2.Zero, Color.White);
  spriteBatch.End();
  graphicsDevice.SetRenderTarget(null);
  inOutImage.Dispose();
  inOutImage = (Texture2D)target;
}

Textures In The Pipeline

The second bit of code creates images from a byte array in a content processor using the XNA Content Pipeline:

/// Create the texture image from the 
/// Color byte array, Red, Green, Blue, Alpha.
private Texture2DContent BuildTexture(
  byte[] bytes, 
  int sizeWide, 
  string uniqueAssetName)
{
    PixelBitmapContent<Color> bitmap = 
      new PixelBitmapContent<Color>(sizeWide, sizeWide);
    bitmap.SetPixelData(bytes);

    Texture2DContent texture = new Texture2DContent();
    texture.Name = uniqueAssetName;
    texture.Identity = new ContentIdentity();
    texture.Mipmaps.Add(bitmap);
    texture.GenerateMipmaps(true);
    return texture;
}

When I was looking I found similar samples hard to find.  I hope the bits of code may be useful to others.

MipMaps In The Pipeline

The following is how I now create the mipmaps in the content pipeline while loading an image:

///
/// Load and convert an image to the desired format.
/// Returns the image suitable to use as the texture on the Landscape.
///
private Texture2DContent BuildLayerImage(
    ContentProcessorContext context, 
    string filepath)
{
    ExternalReference layerRef = 
        new ExternalReference(filepath);
    
    // Mipmaps required to avoid speckling effects and to avoid moiray patterns.
    // Premultipled alpha required so that the texture layers fade together. 
    OpaqueDataDictionary processorParams = new OpaqueDataDictionary();
    processorParams["ColorKeyColor"] = new Color(255, 0, 255, 255);
    processorParams["ColorKeyEnabled"] = false;
    processorParams["TextureFormat"] = TextureProcessorOutputFormat.DxtCompressed;
    processorParams["GenerateMipmaps"] = true;
    processorParams["ResizeToPowerOfTwo"] = false;
    processorParams["PremultiplyAlpha"] = true;

    // Texture2DContent does not have a default processor.  
    // Use TextureContent and cast to Texture2DContent
    // A processor is required to use the parameters specified.
    return (Texture2DContent)context.BuildAndLoadAsset(
            layerRef, 
            typeof(TextureProcessor).Name, 
            processorParams, 
            null);
}

That code can be called from within the processor using something similar to:

string filepath = Path.Combine(directory, filename);
Texture2DContent LayerImage = BuildLayerImage(context, filepath);

The above was worked out from the following forum and blog posts:
http://xboxforums.create.msdn.com/forums/p/44185/263136.aspx
http://blogs.msdn.com/b/shawnhar/archive/2009/09/14/texture-filtering-mipmaps.aspx

It also helps to know what the parameters are.  You can look them up from the xml file generated by the content pipeline:
Content/obj/x86/Debug/ContentPipeline.xml

The following being extracted from that:

<Importer>TextureImporter</Importer>
<Processor>TextureProcessor</Processor>
<Parameters>
    <Data Key="ColorKeyColor" Type="Framework:Color">FFFF00FF</Data>
    <Data Key="ColorKeyEnabled" Type="bool">true</Data>
    <Data Key="TextureFormat" Type="Processors:TextureProcessorOutputFormat">DxtCompressed</Data>
    <Data Key="GenerateMipmaps" Type="bool">true</Data>
    <Data Key="ResizeToPowerOfTwo" Type="bool">false</Data>
    <Data Key="PremultiplyAlpha" Type="bool">true</Data>
</Parameters>

Already a Texture in the Pipeline

If you want to chain from one processor to another or do more than one thing to a texture you can use the ContentProcessorContext.Convert method to run another processor on the same object.  In the following example the input is an existing texture loaded elsewhere in the pipeline:

TextureContent output = 
    context.Convert<TextureContent, TextureContent>(
        input, 
        typeof(TextureProcessor).Name, 
        processorParams);

If you want to just add the mipmaps to an existing TextureContent image, as shown in the bitmap example earlier in this post, you can call the following method:

input.GenerateMipmaps( true );

The pipeline code is a bit harder to understand but is probably more useful.

===

Here's a discussion thread I found recently about mipmap coding in general:
http://xboxforums.create.msdn.com/forums/t/111550.aspx
And that came from here:
http://xboxforums.create.msdn.com/forums/p/111606/667162.aspx#667162

JCB 23 Sept 2013.

Consequences

I made what I thought was a tiny change to the code to fix a problem and now when I test on the Xbox the steady 60 frames per second (FPS) sometimes drops momentarily to 58 FPS.  This is not noticeable in game but I know it is there.

It demonstrates how close to the limit my current code is.

The change was required to fix a problem where a small model in some positions viewed from some angles would disappear from view.  It was either a bug in the frustum to sphere intersection testing code or I was just being over zealous with what I culled from the view.  Whatever the problem was, it was solved by increasing  the area used for testing what was potentially in the view.  The consequence is that more models are likely to be drawn each frame.

Those few extra models being drawn was enough in some places on my first level to tip the balance between drawing everything in 16.6 milliseconds (one frame) to not being able to draw everything in that time.

I'll tinker with the code to try to fix both problems.