Monday, 26 August 2013

Monday Modules And Occlusions

Bank Holiday For Some

Where some UK residents can enjoy a relaxed sunny weekend extending leisurely into an extra day thanks to the British Bank Holiday, some unfortunates must sacrifice all this in the pursuit of code.  Ladies and gentlemen, I must confess to being one of those sad creatures and reveal my meager offerings through this blog.

The Weekend

I had a mission this weekend which was to save TGC some cash and figure out if I could implement an occlusion system for Reloaded in a timely fashion. It was also an opportunity to study some middle-ware options to see if it made more sense to buy in a solution for quick integration.

After a few hours testing some third party solutions, it was apparent that I still had a substantial amount of work to do around such modules to complete the integration into the engine.  On closer investigation, segment and entity shapes, the vast amount of objects in the level and lack of fine-grain control all conspired to make the job of using a third party solution problematic.

I then spent some time researching the latest techniques on occlusion, and found that I had read most of the articles before when I explored occlusion a few months ago.  One thing that did leap out a fresh was the idea of using the GPU to help me hide occluded objects in the scene, and one article in particular was inspiring me to do an experiment in this regard.

Some of Saturday and all of Sunday was spent creating this prototype, and to make sure I got the speed I integrated directly into the DBP object engine. The essential technique is to count how many pixels are actually drawn to the screen for each object draw call. This measurement is actually free and is part of any graphics card supporting DX9 and above, and is called an Occlusion Query. Once I knew when an object no longer drew screen pixels, I could flag it as hidden and would no longer need to render it.

To make sure that hidden objects are revealed again at the right time, for any hidden object in consideration, a very quick render using depth test only is performed to check if the object is suddenly visible again, and if so, the visibility state is restored. The downside to this singular technique is that your engine is making as many draw calls as if every object was rendered. Even with the faster than light draw call, it's still not game-engine ready. The icing on the cake, and the technique I will be implementing after the AI is done, it to group the objects into a spacial hierarchy that has object sorting built-in.  The idea is that you can make a single draw call for the purpose of an occlusion test, and if it fails (i.e. no pixels drawn) then ALL the objects covered by that test are instantly dismissed from further tests. Imagine a building with four floors, and each floor has five rooms, and each room has thirty objects. When you stand in front of a wall, hiding the building, you have only one occlusion test draw call to make and if occluded, you can skip 600 occlusion tests that would otherwise have been necessary, and of course you skip drawing 600 full detailed objects into the scene thanks to the overall occlusion system.

I also have a neat idea that instead of constantly sorting the objects into front-back order as you move around the scene, that the hierarchy structure stores objects in some sort of spacial list (multidimensional array grid) and then the draw system traverses the spacial list from which ever direction you are looking at them.  Think of it as a series of connected boxes, and you start to fill water in any box on the outer edge. Eventually the water spills over to the neighboring boxes and so on until all boxes are filled. Now imagine a super fast traversal system which mimics that flow of water, ticking off each box as they are encountered and drawing the objects inside that box.  My idea is not solid yet as I need to make some prototypes, and it might turn out a simple distance based bubble sort would work just as well, but the more I think about 17,000 objects floating about the level, the more I want to keep them in a static list somewhere and only 'touch' the objects that are of immediate real-time relevance.  Sometimes a sorting algorithm can be slower than just rendering all the objects, and I want to make sure it's not the case for Reloaded.  Another benefit to front to back sorting of screen art is the massive reduction in overdraw, and when you are using intense shaders, the performance gain from this technique is substantial!

The Extra Day

I was tempted to finish off the Occlusion stuff described above, but I have set myself a mission to create an 'ace AI demo' for a meeting I am having come September. For this we need smooth character animations, clever AI bot, player weapon functionality and a good looking scene to run around in.  I only have five days, which in real terms is about three days given the nature of development to constantly throw rocks in your path.

To that end, I have finished adding the staircase traversal state to the state engine database and then cleaned up all the source code and made it a separate module for later integration.

The next step (to be done this evening) is to clean up the AI bot from the main AI prototype ready for the above state engine to replace the hacked in animation code currently there. One dilemma is that the hard fought ladder code which is pretty much a hack ought to be part of the state engine like the stair climb, but the cleanliness of the code must come secondary to making a nice looking demo for the meeting.  To that end, I plan to implement the staircase code using the proper state engine but leave the ladder hack in for the demo, and replace it afterwards. It also turns out there is a scale issue when mapping positional information from the animation to the real world, and the staircase is a much simpler animation to work with than the ladder animation. Once the problem is solved, the ladder should be integrated relatively quickly into the 'fully tested and integrated' state engine.

Mark sent me a substantial and comprehensive document on all the new weapon features introduced by the AirMod enhancement to FPSC classic. Given the power of this part of the original engine, my plan is to create a module from it as I integrate the new weapons for Reloaded.  This will be one of the module tasks for this week, as the player will need to run around and fire back at the enemies that will populate the scene.  I cannot promise the weapon system will remain untouched but if it makes sense and blends well with the improvements, it will stay in.  Naturally, some of the features of the weapon system will not feature in the set of weapons we will start with for Reloaded, but the most I would do is comment out the code, to be re-activated when new Reloaded weapons that exploit those unique characteristics emerge.

Signing Off

For now, I have to get something to eat before my head falls off, and then the work of adding the new state engine database system to the AI prototype begins in earnest.  A week might seem a long time, but with the inevitable email distractions and daily development problems, it will fly by.


  1. Hello Lee,

    I see, you have many problems with the stair climbing of your NPC. If you've got that neat physics integration, why not go for real-time collision detection on the legs and feet of the characters?

    Take a look at S.T.A.L.K.E.R. Clear Sky (and Call Of Pripyat), where GSC Gameworld did their stair climbing (and other tasks) just like this:

    Here is another example from Skyrim:

    The front Stalkers' feet are correctly aligned to what he stands on. The same works wonders when a Stalker stands on slopes. Their feet align to the angle of the ground. The legs also bend like they realistically would do.

    When climbing stairs, the Stalkers just play their normal walk animation, but the detection of some object they would run into lets them slide up, but simultaneously align the legs and feet to the object they're on right now.

    I hope, you understand what I mean and maybe this would make NPC movement not only easier for you and Mark in the end, but also make the movement smoother as there wouldn't be a need to change animations all the time.


  2. @sector49:
    That's pretty damn cool. I can definitely envision it becoming a staple in future games.

    Sounds like you will have some pretty busy days ahead of you.. I wish you the best of luck!

  3. With all the work you're putting into the new lightmapping and occlusion systems it sounds like we'll be able to fill every segment of this 500x500x20 world with entity, segment, and shader goodness. :)
    Best of luck to you in the coming days!