Thursday 7 March 2013

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.

4 comments:

Potato said...

Hey John! Nice blog, your posts have been very helpful in my own XNA project for a small game project. I have come across a seemingly rare problem though and am wondering if you can shed any light on it.

Right now I am using Blender to export a series of SMD animations to a XNA-compliant FBX file. Due to XNA 4's incompatibility with FBX files that contain multiple takes, I am using a couple of functions to split the animations up into timespans using a keyframe definition file. This all works just fine. However, there is this persistent T-pose flash that occurs either at the beginning or end of some of the dynamically-split takes. It doesn't occur for every take and there doesn't seem to be any pattern to which takes it occurs to. Sometimes if I adjust the definition of a take by just 1 frame (e.g. from 61-99 to 61-100) it will make the T-pose flash occur. Sometimes if I change the animations a bit and export a new FBX file the T-pose bug will now occur for a different set of takes.

I read your post titled "Multiple FBX Animations" which seemed relevant at first but after some testing it appears to be an unrelated issue. I have done extensive testing to pinpoint the problem and it doesn't seem to have anything to do with the frames being out of range. Do you have any experience with this problem or any advice for me?

John C Brown said...

I've not come across that problem and it sounds like you have checked everything I would have done.

Are you checking the FBX or the keyframe contents in code?

It sounds like a blank line, all zeros.
I would suggest outputting the in memory Keyframe array from code to a text file (or Debug output) but NUMBER each line from the array and output it even if the array entry is null or blank.

That's all I can think of.

Have you posted a thread on the XNA forums? Probably best to carry on this post there.

Potato said...

Hey, thanks for the reply. I ended up asking a video games professor for help and it turns out it was a problem with the animation player class that is provided with Microsoft's SkinningSample example project.
This line of code had to be removed: skinningDataValue.BindPose.CopyTo(boneTransforms, 0);

This code initializes the bone transforms to the bind pose (T pose). It should only be called once at initialization and not repeatedly during UpdateBoneTransforms(). Hope this helps anyone else who may encounter the same problem...

(Also, speaking of Bresenham's line algorithm, I actually used it in a previous game to calculate/render fog of war in a grid-based map system. Interesting to see that it plays a role in your calculations as well!)

John C Brown said...

Glad you found it.