Monthly Archives: September 2012

Weekly Update : Loading Large Maps

Since feature based updates take long time I am going to start some weekly posts about what I am working on.

So for this I am working on optimization techniques for large game scenes. For  testing i am using dust2 from counterstrike source and 2nd map from Half Life 2 single player. I have implemented hierarchical frustum culling, now I am looking for occlusion culling techniques.

Spatial Partitioning

Implementing Polygon level collision detection was fun and quite useful. I have implemented the system for static objects, dynamic objects, skinned characters and terrain. So even though collision detection is done it’s not ready for full game scene having 1 million polygons or more. The main reason is the performance if we use this system as it as for big levels without any High level optimizations we can’t get playable frame rates because CPU’s are still not powerful enough to do that and will never be. Because as the CPU or GPU horsepower increases people would demand larger and more realistic  looking worlds that means more polygons means more horsepower required to manage that. So we have to implement high level optimizations and we should try to rule out insignificant calculations as early as possible. Because check your character against all 1 million polygons or so every frame doesn’t make sense.

So next that’s where Spatial Partitioning comes into use. As name describes itself Spatial Partitioning algorithms divides the game level spatially into different areas or chunks depending on particular algorithm being used.  So every frame we can only test our character against objects / polygons in that particular area.

Not only collision detection same spatial partitioning algorithms can be used for speeding up rendering also. We have already divided space into smaller chunks / areas so sometimes we can get away only rendering that particular area. For example a scene consisting of 100 rooms and we are in room 50 then we just have to render that particular room and objects in it ignoring  all other rooms and objects in them. So that saves a lot of GPU power send in rendering other 99 rooms which user can’t even see (ignoring things like windows etc to make example simpler).

So this was an extreme example I gave but in many cases the amount of boost we get rendering and collision detection is comparable to example above.

Also I just gave you once example in the area of rendering deciding visibility or object but this can help in many other areas like LOD, Animation LOD and much more.

Hierarchical Partitioning

So by spatial partitioning we mean diving scene in cells (rows and columns etc) so we can just reject whole area / chunk of level at once from rendering or collision detection instead of going to each game object or polygon and checking if its visible or colliding.

Well this process can still be speeded up further much more by making the spatial partitioning hierarchical. So for example we can sometimes reject the 50% of the scene in single bounding volume check which is a major speed boost.

So here are some popular Hierarchical partitioning algorithms –

  • Quad Tree : A Quad Tree is a tree data structure in which each internal node has exactly four children. Quad Trees are most often used to partition a 2D / 3D space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. But for games shapes are mostly square or sometimes rectangle. At each parent node 2 planes are chosen which mostly divides the node into 4 equal children.
  • Oct Tree : An Oct Treeis mostly same as Quad Tree with a difference that  each internal node has 8 children. Oct Trees are used in 3D environments. At each parent node 3 planes are chosen which mostly divides the node into 8 equal children. But there are other techniques also like Loose Oct Trees in which 8 children may/mayn’t be of equal size.
  • Axis Aligned BSP Trees or KD Trees : A k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key. Even Quad Tree and Oct Tree can be thought of as k-d tree with 4 &  8 dimensions.  But in-game development k-d tree mostly means a special case of BSP or Binary Space partitioning Tree in which each internal node has only 2 children and plane used to split at any internal node is aligned to one of the Axes (X,Y or Z).
  • Polygon Aligned BSP Solid  Leaf Trees : Binary space partitioning is a generic process of recursively dividing a scene into two until the partitioning satisfies one or more requirements. At any internal node a plane aligned to one of the polygon is chosen to split other polygons at this level into back child and front child. At leaf Nodes polygons will only be present in front node and back nodes are mostly empty to represent what is called Solid Space or space where player can’t enter.  So we can easily render polygons in back to front or vice versa. Also there many occlusion culling techniques made possible by the BSP trees like Portals and PVS. All of this combined together is still the fastest way to render indoor scenes.

Another factor comes into play is whether we should clip objects / polygons or not along the boundaries of a Node. If we actually clip then polygon count will increase but 2 objects created as a result of clip along any plane will be owned by unique Nodes/ Leafs. But if we decide we don’t want to clip we either have to expand boundaries of Nodes (e.g. loose Oct Trees) or we have to include polygons in both children nodes in which case we have to implement something to avoid rendering same object more than once.

So at the time of writing this Quad Tree , Oct Tree and KD Tree were working and some foundation code for BSP is there but I most probably will be dropping it because right now I want to focus mostly on techniques that can be used in real-time and BSP takes a huge amount of pre processing time in construction of BSP Trees etc, also BSP are mostly much more useful for indoor environments or some outdoor environments with different sections that can be realized like indoor environments or areas (e.g. counterstrike or even half life2 itself).

So here are some screenshots and some statistics of what I achieved –

(Notice the number of triangles rendered in the 1st screenshot is only 8, which is made possible by spatial partitioning and hierarchical frustum culling)

Spatial partitioning is not the end but the beginning of algorithms or techniques that are used to manage / optimize the rendering /collision detection of large scenes. For example one next step is Hierarchical Frustum Culling and then occlusion culling etc.

For people who are interested to investigate it further here are some very good books on the subject –

RealTime Rendering

3D Game Engine Design

Realtime Collision Detection

Animation System 4 – Data Driven Workflow

Now since I have working and stable animation systems in the engine –

  • Skeletal Animation for Characters (Software Skinning & HW Indexed Skinning)
  • Non Skeletal Animation for animating objects
  • Facial Animation

Next step is to create a data driven workflow.  Right now to import a model in the engine, playing a particular animation and assigning events I have to hard everything into the C++ code itself. And in case I have to blend multiple animations that  creates another long code mess.

A proper way to do things will be to let user be able to choose things at Run Time without have to modify code. Now the ideal way to do it is to make an editor to where user can easily edit any animation related properties and save them into a file which can be loaded and used at the runtime, but my level editor itself is very long due and I don’t want to make a separate application for this purpose for now. So solution I was searching for is something based on easily editable file format. So these were my goals when trying to decide for a particular text-based file format –

  • Easy to Read and Edit in Notepad (or any other text file editor)
  • Implementing parser or read/write code for file format shouldn’t take much time because this is a temporary thing for now, later at sometime I will switch to editor for sure.

So first I thought maybe some XML based format. Even thought writing a xml parser could take some more time but there are some open source xml parsers available for the job. But XML format is not that easy to edit in Notepad.

I thought maybe make something like a file format like I had for my terrain loader just specify all properties one after other with each property in each line or maybe separated by spaces.

Something like –


But as you can see by file itself no one can tell what that file name or 10 means.A better way would be something like –

Animation Name - "walk"
Type - Loop

Making these Name / value pairs are much better than simple values in each line. So one standard format that already supports this is INI files. I still remember messing with car properties in old NFS HotPersuit  which was interesting.

So next thought came to my mind is how to parse these INI files. These INI files are old way of specifying properties for windows app. So I searched on internet if there is some standard support for it in VC++ or not. Also looked for some text-based formats others are using.  I found there’s in fact some function in VC++ to read and write separate properties of INI files. So I decided that’s the way to go. I also eventually landed on some pages about the mentioning of same thing in some GameInstitute’s Tutorials which I already had from long time back. So I also referred their way of handling animation workflow with .ini files.

So anyways here are the goals that I had for my file format . We should be able to load character and then provide various animation related parameters an should also be able to specify some common event types and data for it.

For example :- Specifying the name of walk cycle animation and its type to loop. Then be able to specify an event to play footstep sound  at specific time.

Also wanted to specify various blending parameters along with events and other stuff. Because if we think of any character in any game they mostly play multiple animations blended together e.g. shooting + walk, shoot + run, etc. This also saves a lot of time in art production because artist can only create 2 animation walk and shoot and rest will be handled in engine by blending or changing speeds for different animations etc. So 1 particular group of sequence that defines one complete behaviour in-game is termed as action here e.g. IdleWalk, RunningShoot, etc. ,   which are composed of multiple animations having different properties.

So here is a sample of how my file structure looks like this –


Name = Walk_Shooting
DefinitionCount = 3

Definition[0].SetName = Walk_Legs_Only
Definition[0].GroupName = Legs
Definition[0].Weight = 1.0
Definition[0].Speed = 1.0
Definition[0].BlendMode = MixFadeGroup
Definition[0].MixLength = 0.3
Definition[0].TimeMode = MatchGroup

Definition[1].SetName = Walk_Variation
Definition[1].GroupName = Hips
Definition[1].Weight = 1.0
Definition[1].Speed = 1.0
Definition[1].BlendMode = MixFadeGroup
Definition[1].MixLength = 0.5
Definition[1].TimeMode = MatchSpecifiedGroup
Definition[1].TimeGroup = Legs

Definition[2].SetName = Gun_Shooting_Pose
Definition[2].GroupName = Torso
Definition[2].Weight = 1.0
Definition[2].Speed = 1.0
Definition[2].BlendMode = MixFadeGroup
Definition[2].MixLength = 1.0
Definition[2].TimeMode = Begin

And here’s a screenshot  of animation system in work  –

So this text file system based on INI files is simple and easy to use for now but reading and writing INI files are very slow compared to binary files. For now couple of files won’t create that much difference but later on at some point as soon as I get some editor ready for managing animation system I would be switching to binary format so we can read and write much quickly.

References –

Game Engine Architecture (A very good reference about how animation system actually works in a game engine)

GameInstitute’s 3D Graphics Programming (for those who are interested in the action file format using INI files i mentioned above)