Wednesday, November 30, 2011

PA4 – Implicit Conversions, RVOs and Proxy Objects!


Hello once again! I am trying to keep the pace here with the posts and hopefully you are enjoying them. Today I will talk about Assignment #4 (PA4) – C++ Efficiency. This assignment was a combination of three important topics about Efficiency in C++ programming: Implicit Conversions, Return Value Optimizations and Proxy Objects. I will give you a summary of each one in the following paragraphs:

  • Implicit Conversions: the whole idea behind this trick/optimization is to prevent coders from passing wrong-typed parameters to functions. For example, imagine that you have a set function for a particular member of a class and you do not want the user to pass a value that has a different type, how can you achieve this? Aside from turning up the compiler settings (warnings), there is one trick you could use:

Class Diego {
public:
          void setX( const  float  inX );
private:
          template <typename T> void setX( const T inX );
}

When this trick is applied, anything but a float variable will give a compilation error, therefore successfully preventing wrong-typed values to be passed as parameters. Sexy or what?

  • Return Value Optimizations: I will start by saying this: temporaries kill performance big time! (quoting famous philosopher Ed Keenan). The idea behind RVO is to remove as much temporary variables as possible in order to improve performance. By removing these temporaries we are also removing unnecessary calls to constructors, destructors, copy constructors, etc. Let’s look at the following example to better understand the idea:

With temporaries (No RVO):
Vect2D Vect2D::operator + ( const Vect2D &tmp ) const {
    Vect2D sum;
    sum.x = this->x + tmp.x;
    sum.y = this->y + tmp.y;
    return ( sum );
};

Without temporaries (RVO):
Vect2D Vect2D::operator + ( const Vect2D &tmp ) const {
    return Vect2D( this->x + tmp.x, this->y + tmp.y );
};

You might think this change does not improve performance a lot, but in my assignment I had a stress test in which a bunch of math operations were performed and repeated 5 million times, and just by using RVO I improved the time to 301ms down from 939ms originally. That’s a hell of an improvement in my opinion!

  • Proxy objects: this one is another trick to remove/reduce temporaries and copies from function calls. This method involves (ab)using operator overloading to: replace operations that involve more than two operands, to compare vector length using squared distance instead of square root, etc. I will show you guys an example for your entertainment and pleasure, try running/debugging it so you really understand  what is going on (it took me a while to get it):

struct VaddV {
    const Vect2D &v1;
    const Vect2D &v2;

    VaddV( const Vect2D &t1, const Vect2D &t2 )
        : v1(t1), v2(t2) {};

    operator Vect2D() {
        return Vect2D( v1.x + v2.x, v1.y + v2.y );
    }
};

inline Vect2D::VaddV operator + ( const Vect2D &a1, const Vect2D &a2 ) {
    return Vect2D::VaddV(a1, a2);
};

Try performing an addition operation between three (3) vectors and you will see this baby up and running.

Well my fellow readers, I hope these tricks are useful for you, and if not try using them as opening lines in your next date (not recommended). See you later! Adios!

Tuesday, November 29, 2011

PA3 – Another memory system!


Hey guys! Long time no see, eeeeeh..... not!

Another assignment submitted, and if you have been following this blog for a long time (seriously?) you will know that I have “been there, done that” with this assignment. This one is Assignment #3 (PA3) – Memory System.

The whole idea behind this assignment was to build my own Memory System to replace the standard one that comes with C++, in other words, I had to create my own version of malloc() and free() functions. In order to achieve this I allocated one big block of memory (50KB + alignment padding), which we call the heap, then moved the initial block address so that it was 16-byte aligned, placed the heap header on this address and created a free block with the remaining space of the original block. The 16-byte alignment is not essential to the functionality of this project, but it will be useful later (SIMD).

The heap header is the Memory System part that holds all the pieces together. It has pointers to the first used and free blocks, and has an internal structure that keeps updated stats about the system usage. All blocks in the system are connected by pointers (next and previous) to form doubly-linked lists for easier insertion and removal of new blocks. Now, let me talk briefly about the two functions implemented:

  • malloc(): this function first rounds up the requested size to the next multiple of 16 (to preserve the 16-byte alignment), then checks if there is enough space available in the heap, if that’s the case it proceeds to find the first free block that can hold the required amount. When the block is found, if its size is bigger than the requested one it is split into a used block and a free block, then both blocks are added to their respective lists. Finally, the stats are updated and the address of the used block is returned to the user.
  •  free(): this functions takes the address of the block to be freed as a parameter, then converts this used block into a free one and adds it to the respective list. When this is done, the function also checks if the blocks above and below the new free block are not used, and if that is the case, it coalesces them together into a bigger free block. As was the case before, the stats are updated at the end.


Beside this, PA3 also had another part related to using the Placement New operator. The big difference between this operator and the regular New is that this one takes a pointer to a previously allocated memory location as a parameter, and then uses it to create the new object there. On the other hand, the traditional new first allocates the blocks (malloc) and then creates the object there.

I was going to add some diagrams to this post, but I am kind of lazy today. Anyway, I hope this information was useful. See you later! Adios!

Monday, November 28, 2011

PA2 - Keep the hot side hot and the cold side cold


What up dudes!

Long hiatus, I know, sorry about that! But here I am again, this time I will explain Assignment #2 (PA2) – The Hot/Cold data structure.

This Hot/Cold thing refers to the process of splitting a data structure in two (2) parts to improve performance, but some conditions should be met in order for this approach to work efficiently: you need to have some kind of linked list, your data structure is bloated with members inside (size of data structure is on the large side), each data object has some kind of identifier (a key member) and a lot of searching/traversing back and forward over the linked list is done.

So, what we want to do is split the bloated data structure in two (2) parts. The first part (and small one) is called the Hot Node and it contains: the pointers (links) to the other nodes in the list, the key/ID that identifies the structure and a pointer to its Cold Node. The other part (the big one) is named the Cold Node and it carries the rest of the members from the original data structure. Therefore, if you combine each Hot Node with its corresponding Cold Node you get the original bloated data structure.


Ideally you would like to have all Hot Nodes stored close to each other in memory (data locality), that way traversing and searching the list is not that expensive (there should not be many cache misses). On the other hand, the Cold Nodes could be store anywhere in memory since they should only be fetch when the corresponding Hot Node was found.

 If you still don’t understand what all this I just talked about means, I suggest you watch the following video, it will explain it very clearly. Enjoy it!


See you soon! Adios!

Wednesday, October 5, 2011

PA1 - Warm Up completed!

What up dudes! First programming assignment has been completed. This was kind of a warm up exercise more than a challenging task, but there's always new tricks to be learned, so stay tuned. The assignment consisted of four (4) "simple" problems, and here is what they were all about:

1 - Polynomial Evaluation: You have a 5th-grade polynomial and would like to evaluate it in the fastest possible way. So, you ask yourself: what's the most expensive operation when you evaluate a polynomial? Exponentiation! Solution: instead of using expensive math operations like POW, we use Horner's Method and reduce the number of math operators to n multiplications and n additions. Therefore our evaluation ends up looking like this " ((((A5*x+A4)*x+A3)*x+A2)*x+A1)*x+A0 ".

2 - Vector Normalization: The most expensive operations in this method are the Square Root and Division by it. What can we do about them? Reduce the number of times they are used. First, we only execute the Square Root once and if the vector's components multiplication is greater than a threshold (to avoid precision problems), and second, we store in a temporal variable the result of diving 1 by the vector's magnitude and multiply each component by it, instead of dividing each one by the magnitude (reducing the number of divisions from 3 to 1).

3 - Double-Linked List Node Removal: This function removes a given node from a double-linked list, so the tricky part was covering the especial cases. As parameters for the function we received the pointer to the head of the list and the node to be removed. Probably the trickiest case is when the node to be removed is the head of the list, therefore to cover this case we passed a double-pointer to the head, that way we can modify where it actually points to. Aside from that, the rest is all about fixing the pointers of the previous and next nodes correctly, and freeing the memory of the removed node at the end (no memory leaks allowed for a code ninja).

4 - Minimum and Maximum Distance Calculation: Given an array of player positions, we want to calculate the minimum and maximum distance among them. As we mentioned before, calculating distance involves using Square Root, so the first possible optimization revolves around not using it too much, therefore we leave it for the end, we do all our comparisons using squared distances and just before returning the final values we calculate the Square Root of them. Another important improvement is to compare only once each pair of positions, so in the inner loop of the function we only iterate from i+1 to n (being i the iterator variable for the outer loop) instead of from 0 to n.

Well, I hope this was helpful. See you soon!

Adios!

Wednesday, September 21, 2011

Back in the game!

Hello! After a long hiatus I am back with some more Game Development stuff. This time I am taking a class about Game Performance Optimization with the same professor as always Ed Keenan. The basic goal for this class is to become a Code Ninja, and in order to achieve that we have to master the five (5) skills every ninja should have:
  • Scouting - Gather recon on performance issues
  • Sabotage - Disrupt old behavior
  • Espionage - Gather information through testing
  • Assassination - Eliminate performance spikes
  • Guerilla Warfare - Refactor and attack weak points
Lets see how this one goes, so far all Keenan's classes has been awesome, and he promotes this one as one of his favorites, so I am all in for this one. Let the fun begin!

Tuesday, April 26, 2011

Of engines and models... a little sample for you guys!

As I mentioned yesterday in my post, work is complete for the First Milestone. In order to do a little summary about the experience so far, I can say that the work done can be divided in two phases: creating the FBX Converter and refactoring the Engine to add the model loading capability.

The first part, which involved around 80% of the total time employed, was mostly about figuring out how to read the internals of the FBX Model. This was facilitated by using the supplied program as a starting point. With this program already displaying on screen the desired information (polygons and vertices), the following task was to reduce the code to what was actually necessary, eliminating from the code all other unnecessary functions. Finally, the code was refactored for storing the information in data structures instead of displaying it on screen, and then the File System built last quarter was integrated in order to write all the data into a single file using the archiver format.

The second part consisted of integrating the File System into the Engine in order to be able to read the file back. After this, there were some minor tweaks done here and there in the Engine for interpreting the data accordingly, but in general the code was not changed in a significant way.

I have to mention that it is an awesome feeling when you glue all the pieces together and they work flawlessly from the beginning, especially when I am talking about code that I did not spent too much time testing, but its design has proven to be well-thought and bullet-proof so far. Of course I am speaking about the File System, which was incorporated into the rest of the code quiet easily and trouble-free, saving quite a few hours of extra work.

My fellow readers, here you have a little taste of the Updated Engine I just submitted:


Well, FBX models can be converted into my own file format now, and the engine can interpret and render them on screen. Next stop is Quaternions and Animations. See you soon!

Adios!

Monday, April 25, 2011

Here is the story of how this two dudes met: the FBX Converter and Diego's 3D Model!

Hello you all! I am back from a weekend of intense work, code tuning and wrapping things together for milestone submission. That’s right! Yesterday I submitted the first milestone for my updated Graphics Engine including the first version of the FBX Converter.

Let’s get down to business. I will use this post to talk about the final details of the FBX Converter and the File Format used to store the models. Since I previously talked about the logic behind the FBX Converter, and taking into account that it has not changed, I will proceed to explain how the program can be used. The syntax for using it is the following:

                FBX_Converter.exe infile.fbx outfile.d3m [options]

There are two (2) possible options or arguments that can be passed to the program:

                -notexture
                -addtexture texture.tga

The first option simply omits any texture contained inside the FBX file, so the converter only extracts vertex and triangle data. The second option tells the converter to use an external texture instead of the one contained inside the FBX, therefore the final model file contains the texture supplied by the user.

Regarding the File Format (Diego’s 3D Model), it is composed of three big chunks of data (Vertices, Triangle Indices and Texture) accompanied by their respective type-specific headers and chunk headers.

At the beginning of the file is the File Header, which contains descriptive information for reading the rest of it like the number of Chunks and total size. Next are the Chunk Headers: these specify the size of each chunk and its respective type, this way the engine is able to interpret the data back.

Finally we have all the actual data needed for rendering the model. First we have the Vertex Array with its respective header which specifies the number vertices and the individual size of each one (this is used for the Vertex Buffer Objects calls). Next we have the Triangle Indices Array, and once again in the header we have the total number of triangles and the size of each one. At last we have the Texture with its header containing the dimensions (width and height), number of colors per pixel (depth), size of texture data array and two (2) values that are necessary for rendering the texture in OpenGL (format and components).

There you have it! I will be back really soon, probably later tonight or tomorrow at the latest, with a video of my updated Graphics Engine.

Adios!

Monday, April 18, 2011

Let the models show you the way! This is the story of a baby engine trying to become a big boy!

What’s up you all? I am back with some updates regarding my progress. This was quite a productive and happy weekend. First of all, the Bulls won on Saturday, so let’s go Bulls! And second, I made huge advancements building the FBX Converter and modifying the Engine.

Regarding the FBX Converter, I (as the rest of the class) used a program provided by the SDK as my starting point. Basically this program goes through the internal structure of the FBX file, exploring its components and printing them out to a console window in an easy-to-understand way.

So, in order to get my first functional draft of the converter I just commented all the calls to functions that were printing stuff that I didn’t require. In the end, for this assignment all I need is Vertex information (position, color, normal and UV) and Texture data. Therefore, I ended just using a couple of functions from the original program, DisplayPolygons(KFbxMesh* pMesh) and DisplayTexture(KFbxGeometry* pGeometry), that provide me with all the stuff I require.

The first function (DisplayPolygons) goes through the list of polygons that form the whole mesh, showing all the information I need, so instead of printing it to the console, I am storing the info in a Vertex structure I created and pushing all those vertices into a STL Vector. After all the polygons are covered, I download all this data to a file using my File System from last quarter (I still cannot believe that it worked so flawlessly). I call this file format D3M, which stands for Diego’s 3D Model, sexy or what?

The second function (DisplayTexture) gives me the path to load the corresponding texture for the model. For the time being I am just uploading the texture manually in the engine and binding it to the model. The next step should be to actually store the texture data inside the D3M file, so I can load the complete model in one shot. Will see how that goes when I try it.

In regards to the Engine, well I just modified it to integrate my File System in it and be able to read/interpret the data inside the D3M file. So, as people usually say “a picture is worth a thousand words”, let the pictures speak for myself instead. Here is what I have right now:

Front View
Diagonal View from behind

You have no idea (or maybe you do?) how much joy I felt when I got the first model rendered. Right now I am so proud of my little baby engine, making its first steps to become a grown-up boy. 

So, for the time being I will say bye, but I will be back soon with more updates. Stay tuned!

Adios!

Thursday, April 14, 2011

A new adventure has begun… The wrath of Khan!

Welcome back you all! Spring break is over, and I am already two weeks into the quarter. This time I will use this blog to talk about the second Game Engine Programming class (GAM575). Same professor (Ed Keenan) and same students (well, actually only the ones the survived the first class, some were lost in combat … minute of silence … ), but new cool and interesting adventures. Let the fun start!

First assignment is up! I started working on it yesterday, so let me use this post to introduce you to how this quarter is going to be distributed. There are going to be 3 big programming assignments in total. According to Keenan they require less code than the previous quarter, but a more intelligent design and approach. Here you have a little description for each assignment:
  • Assignment #1 – FBX Converter: during this quarter we will be using standard format FBX for loading complex models into our engine. Therefore, this assignment is about building an offline format converter to read FBX files and extract all the vertex and polygon information to create a run-time file format that can be loaded directly in the engine without using any type of conversion (array of vertex, normals, UV coordinates and triangle indices).
  • Assignment #2 – Animation Engine: once again we will build an offline converter that extracts Animation data from an FBX file (Skeleton and Animation) and stores it in a run-time file format. In addition, we have to create the functionality in our engine to support animation running. Finally, we have to be able to do interpolation between animations (transitions in-between).
  • Assignment #3 – Skinning:  we have to extract Skin and Bone information from an FBX file (another offline converter) and display the animation of the rigid body. We are going to learn to ways of doing this: EA technique and Midway technique (don’t ask me what are they about, don’t know yet).

That’s about it, three (3) assignments; they look really interesting and should be great bullet points for my resume. I will be back soon with more information regarding Assignment #1. 

Adios!

P.S.: I also have another blog for the Multiplayer Game Development class I am taking. Enjoy it!

Monday, March 21, 2011

The hero’s final destination: Geometry Planetary System a.k.a. Graphics Engine!


Hello my fellow readers! As a man of my word, here I am again. This time will be all about my Graphics Engine. I will talk about its architecture in general (components & description) and also have included a video so you can see it running in all its glory =D

Let’s start from the beginning. This engine was built in Visual Studio 2010 using C++ and OpenGL. I used the Pyramid Demo (Chapter 5) from the OpenGL SuperBible (5th edition) book as my starting point for the implementation. During the last month of the quarter, all the students worked in tandem with Prof. Keenan refactoring this code (Pyramid Demo), in order to make it more efficient and flexible, but at the same time more elegant and re-usable. In my opinion, that’s the whole idea behind a Graphics Engine, to be fast but flexible at the same time.

Basically we took the book’s code and reorganized it into different classes in order to achieve our objectives. The majority of these classes were created using the Singleton Pattern (one-instance class), and the idea behind this move was to build a collection of Managers to handle the different components of the Engine: Renderer, Camera Manager, Texture Manager, Objects Manager and Objects Library. For the porpoise of this post, I shall give you a small description of these components:
  • Renderer (Graphics Manager): handles the majority of OpenGL calls, including all the initialization, setting up, program main loop, input handling and program shutdown. This one is basically the orchestra director and the one piece that glues the whole engine together.
  • Camera Manager: takes care of camera administration, including creation and destruction of all cameras, as well as setting up a primary camera (main frustum) and alternative cameras for frustum viewing.
  • Texture Manager: this manager is in charge of loading textures to GPU’s memory, storing the appropriate texture handlers, upon request give the texture handlers and freeing all texture resources when the program is shutdown.
  • Objects Manager: holds pointers to all objects created during program execution (at least all objects that the engine will draw). This manager also handles on-the-fly texture changes for current selected object, and finally, destruction of all objects when the program is close.
  • Objects Library: this singleton class is in charge of creating models (geometry figures) in GPU’s memory using Vertex Buffer Objects and Vertex Arrays, and also storing the respective model handler (GLuint). These handlers are later assigned to objects to specify to kind figure they represent.

Now, I shall present you the demo (video) I recorded and submitted for this assignment. Hope you enjoy it!


I will probably post one more time to cover other details about the Graphics Engine before moving onto the second Game Engine Programming class (next week). So, I guess I will see you soon again! Have a nice one!

Adios!

Saturday, March 19, 2011

And right there, where nobody con see him was hiding the last mini boss... The File System!

Once again my fellow dudes, apologies for disappearing for almost three weeks, I was M.I.A. working on stuff for the three classes I am taking this quarter: A.I. for games, Graphics Development and Game Engine Programming. The quarter is over, yesterday was the last day of activities at the university, and what an effort I did to finish all the assignments on time. For this week I had: Graphics Development’s homework #4 and final exam, A.I. for Games’ take-home final exam, and Game Engine’s final essay and final project (Graphics Engine). I finished all of them on time (almost all completely, only failed to finish the A.I. final) after two days in a row without sleep (not even a small nap), so now is time to relax a little bit and tell you the story behind Game Engine’s last projects.

Since my last post I owe you guys one describing my File System implementation, so here you have it. Unfortunately, this was the last system I started from the four core systems, and since I started it two days before deadline, I did not have too much time to refine and improve my first design. But I am still quite satisfied with how the implementation ended up looking like.

The core functionality of the File System was to handle reading and writing different types of data to files on Windows. In order to do this (and due to time constrains), once again we ended up using the Win32 Library (Windows.h) as our start point for the implementation.

The system’s main functionalities were covered by creating a FileHandler class which wraps the following functions from the Win32 Library: WriteFile, ReadFile and FlushFileBuffers. All these methods use HANDLEs to manipulate files, and some of them use up to five (5) parameters as input. Therefore, the idea behind this FileHandler class was to hide some of the advance features this Win32 functions have, and create a simple interface the user can use to upload/download data to disk. The FlushFileBuffers function was used in combination with WriteFile to allow the system to write as much data as possible to memory, and then proceed to download all of it in one shot (writing to disk is a very slow operation, but one that is unavoidable sometimes, so if we must to do it, we better attempt to do it altogether in one try). Here you have a brief summary of the functions prototypes and description:

  • FileHandler(filename,mode) – Class constructor (Specifies the filename and read/write mode)
  • read(buffer,size) – reads size bytes from file into the specified buffer
  • write(buffer,size) – writes size bytes from specified buffer to file
  • flush() – flushes (writes) to file all data stored so far in the buffer

Last, but certainly not least, as part of the assignment I also developed an Archiver System. Essentially this class is an advance data structure that holds different types of objects inside (it has a linked list with pointers to each one) and has the functionality to download all this data to a file in an structured way (using an archiver header and table of contents), so that you can also read it back to memory when needed. The whole porpoise of the Archiver in the gaming world is to be able to store/load from disc (hard drive or optical media) files that contain complete models (maps, characters, etc.). For example, if we are talking about a character, the file would hold data regarding vertices, normals, texture coordinates and data, sounds, animations, etc.

Well my dear followers, hope all this information is useful for you or at least interesting in some way. I will be posting tomorrow the video of my Graphics Engine‘s demo followed by a post describing its architecture and implementation. Have fun tonight!

Adios!

Saturday, February 26, 2011

I shall introduce you to The Swiss Army Knife of our hero's journey… The Math Library!

What's up dudes? I am almost finished explaining the Four Core Systems, so here is the third one: The Math Library a.k.a. The Swiss Army Knife. This one has been by far the easiest one to code, just two (2) full afternoons of coding and testing, and this baby was ready to Rock n' Roll!

Even though this one has been the fastest to get completed, it doesn't make it less important than the rest. Actually, it is probably the one that is going to be use the most for the rest of the class, basically because the Graphics Engine (which is the next assignment after the core systems) relies on this library for all the dirty work.

Well, here goes the explanation. I think I mentioned this previously, the Math Library consists of a Vector class and Matrix class. The former is a four (4) float object (X, Y, Z and W) and the latter is a sixteen (16) float one (4x4 matrix). You might be asking why does the vector has four (4) components and not just three (3)? Well, as you shall see if you continue reading my blog over the next months, in the following class after this one (Game Engine Programming II) I will deal with a very famous problem called 'Gimbal Lock', and one solution to that issue is through the use of Quaternions (4-D vectors). I will expand on this topic further down the road (so continue following my story =D).

I will assume (as the professor did with us) that you readers have a basic understanding of vectors, matrices and all operations involving them (either independently or combined together). Therefore, I will present you with a list of all the functionalities that the library has:
  • Vector: dot and cross product, magnitude, normalization, angle between vectors and epsilon-based comparisons. 
  • Matrix: determinant, transpose, inverse, epsilon-based comparisons and type-based matrix definitions (identity and rotation/scaling/translation matrices).
Apart from this, the library has all the relevant Math Operators overloaded: addition(+, +=), subtraction(-, -=), multiplication (*, *=) by scalar and between types (vector*vector, matrix*matrix and vector*matrix). Both data types also have the Bracket Operators defined, e.g. you can access the vector's X component by doing "vector[X]" directly.

Finally, is important to clarify that the vector is defined as a union of four (4) floats or a _m128 object type. The same applies for the matrix, it is defined as a union of sixteen (16) floats o four (4) vectors. This is done in order to use SIMD (Single Instruction, Multiple Data) instructions from the processor, but this is a topic for another day and other class (Game Code Optimization).

Well my loyal readers, I shall abandon you for now, I will probably be back tomorrow to explain my File System implementation. So, for the time being have a nice Saturday!

Adios!

Friday, February 25, 2011

They seemed small and inoffensive, but they were bad as hell! Hence their name… Evil Minions!

What's up dudes? As promised, this time around I will talk about the rest of the implementation details for my Memory System. I already mentioned most of the internal elements of the system: the heaps types, their differences and how they are all connected together. But there are a couple details I left out on purpose in order to explain them today. So, here you have them:

The first one involves the way the user interacts with the system. The idea behind this system is to have control over memory allocations in order to improve performance and detect/correct leaks if they exist, but at the same time I want the user to feel as comfortable as possible using it. Therefore, in order to make the system feel natural to the user I overloaded the New/Delete Operators for a general general class called Object. This way, the user can still call the global new/delete operators for objects that do not inherit from this class and they will be stored in memory that is not managed by the Memory System.

On the other hand, if the user decides to create classes that inherit from this general class (Object), he will get the following benefits: data locality (he can place all similar objects inside the same heap), leak detection (in debug mode, every allocation made by the user has its file and line number stored, so they can be tracked down) and also memory control & tracking (the user can track and limit the total amount of space being used at all times).

The second (and final) important design decision taken was to make the Memory System a Singleton, and by doing this, limiting the total number of memory systems a running program can have to just ONE (1), which makes since I only want one central entity managing all heaps ever created without confusing the hell out of the user.

The Singleton Pattern, as it is called in software engineering, is done in C++ by following the next two (2) steps: (1) making the class constructors privates (thus the user cannot create different copies of this class), and (2) creating an static instance of the class which will be our one and only object ever created of this class. In my particular case the Memory System class is called "MemSys", so at the beginning and end of the program the user must call the methods "MemSys::initialize()" and "MemSys::destroy()" in order to create the system, and finally destroy it before terminating the program.

So my buddies, there you have them, all the implementation details of my programming pride, my newly born child… MemSys a.k.a. Diego Jr. There is nothing left to say regarding this one, aside from admitting that it gave me a hard fight, one that I will remember for a long time, but one from which I emerged victorious! =D

I will say goodbye for now, but I shall leave you with the following quote from this video:

 

"Welcome to the world of Gentlemen, Gentlemen". Adios!

P.S.: Stay tune for details on the file system and math library.

Wednesday, February 23, 2011

And along came this dudes, the Memory System a.k.a. The Evil Heap Twins!

Hey guys, long time without hearing from me, I know, I owe every one of you a big apology. The last weeks were tough, but I came on top, victorious nonetheless. Going back and forward between the four systems, trying to finish them up first, and then doing some tuning and re-coding. As Prof. Keenan says "For every line of code you write, you will be re-writing it at least seven times" (I guess he was right about that last one). So, I will try to write a series of posts this week to summarize my design and implementation of the systems.

Today is all about the Memory System, the Evil Heap Twins. Why twins you may ask? The answer goes like this: this system is a memory manager, and one way to handle this (the Windows' way at least) is trough the use of memory heaps, and in this particular case I will be using two types of heaps: Variable-size Block heaps and Fixed-size Block heaps, hence the name "twin".

Lets talk about the Variable-size type first. For this one I am completely relying on the Win32 Library (Windows.h) for the management and placement of the blocks inside the actual heap, therefore I have no control over how the free space is handled and fragmentation is being solved. I am doing it this way for time reasons, because building this kind of heap from scratch takes much more time than I probably have for this whole project. So, it's all about me finding time in the near future to upgrade this part of the system and manage the whole thing myself. I am writing it down now: it's officially part of my bucket list to port this part of the system to be 100% my creation.

Back to the heap topic. I am using the functions HeapCreate and HeapDestroy for the allocation/destruction of huge blocks of memory to use as my heaps. Everytime one of this heaps is created I place a small block inside called "Heap Header", which stores some basic information about the heap itself (stats): total size, number of blocks allocated, maximum number of blocks allocated, used space, a pointer to the first allocated block in the heap and a pointer to the next heap in the system. All heaps in the system (no matter its type) are connected together by their headers, forming a Linked List which only the Memory System have access to.

Then, as the user requests/free blocks of memory for his pleasure, I allocate/destroy blocks of memory inside the heap. In order to do this, I rely on functions HeapAlloc and HeapFree, which as their name implies just allocate and free space in a previous created heap. These blocks of memory have small headers inside, all of them connected together via pointers (forming a double linked list), and also storing the size of the block and a pointer to the heap header (used later to free the block in constant time). You can have a better idea or understanding of this heap type by looking at the following diagram:


On the right side of the diagram you can have a look at the Fixed-size block heap type (the other evil twin, the less powerful one). This one is a little easier to understand and handle, and the best part is that it is a 100% my creation, no Win32 Library involved (Sweet!). As you might guess, what we have here is a heap that contains an specified (n) number of blocks of the same size. When the heap is created (a simple call to the malloc function), we first store the header at the top of it, then we proceed to divide the rest of the space between the n blocks, all linked together by one pointer in each block header (single linked list), and having the heap header point to the first one.

Once the user requests a block from this heap, the first free block is returned by the Memory System, but behind the scenes two other things happen: the second free block in the list becomes the first (the heap header now points to this one) and the pointer inside the new used block header now points to the heap header instead of the next used block. This pointer is used to return to the heap header from the block, which is done when the user requests to free the block.

For the free operation the user only gives the system the pointer to the block itself (not the block header, which the user actually doesn't know of its existence). So, no matter what type of heap it is, the system must be able to go back from the block to the actual heap, so in order to do this as fast as possible (constant time in my case), we store a pointer to the heap header inside each block header, giving us an speed advantage in exchange for a small storage penalty. Not a bad deal in my opinion.

Well guys (if there is actually anybody reading this apart from me), there you have my memory system, a large post that summarizes a few thousands lines of code in low-level C++. This one is my pride as a programmer, and one that made me realize how little I knew about C++.

See you guys around… Adios!

P.S.: Don't you dare think this is over! I still have to talk about the evil minions of the system! Come back tomorrow for the rest of the story.

Tuesday, February 1, 2011

And they thought they would live happily ever after…


The Object System is about 95% ready, it just needs some code review here and there (there are a couple nuts that need to be tightened). I also need to setup the demos before submitting the final code in a couple of weeks, but I will get back to coding this system later.

The Object System is the first piece in a four-part Project which also includes the following three assignments: Memory System, File System and Math System. Allow me to explain the other three parts briefly.

The Memory System is a memory manager build on top the Win32 Library that allocates/frees memory based on user requests. This system creates/destroys Heaps using the Win32 Library, and allocates/frees blocks of memory from those heaps. The idea behind this system is to have control over the memory being used by the Game Engine, therefore be able to detect & fix possible memory leaks and improve performance by allocating objects in specific heaps, i.e. having different heaps for models, maps, sounds, etc., and as a result achieving data locality (much better than having your data spread all over the main memory).

The third one, the File System, is meant to manage data transfers from files to memory and vice versa. Since reaching out for data in your hard drive or optical medium is way much slower than accessing main memory (milliseconds vs. nanoseconds), you want to minimize those access as much as you can. Thus, the idea is to store the game data (models, maps, animations, etc.) in binary-format files, and have the File System manage the file loading efficiently (that’s what those loading screens are for).

The final one (for now) is the Math System, which basically translates into a Vector and Matrix Library. This system has to be able to handle all kind of operations for vectors, matrices and in-between: dot product, cross-product, matrix multiplication, determinant, transpose, inverse, etc. More than difficult, this one implies thousands lines of code and plenty of testing.

In my next posts I will go into more detail about each one of these last three systems. At least the first one is working right (at least I think so), but also made me realize that I am quite rusty in this thing called CODING. Hopefully, by the end of the quarter I will be a little bit more relaxed and skilled working with C++.

Off I go! Memory System you shall be mine!

Adios!

Friday, January 21, 2011

There was this PCSTree guy and PCSNode girl...


Well, I am back again here. I’ll use this post to explain the first assignment we got (which I actually finished a couple of days ago). The goal is to create a System to handle the Objects inside your game engine, that is, a centralized place where all game objects can be stored, organized and managed.

That’s basically the final objective of this Object System, but as Prof. Keenan says “We have to take Baby Steps in order to get there”, so for now the basic idea is to create a Tree-like Structure to store data on memory in a coherent and efficient way.

This structure consists of a bunch of nodes linked together by pointers creating a structure that resembles a tree. In the first place you have a class called PCSTree (where PCS stands for Parent-Child-Sibling) which has a pointer to an instance of the class PCSNode called Root. This root node acts as the connection between the tree and all its nodes, but when we count all the nodes in the tree this one is not taking into account. Mainly this node is generated when the tree is created and lives while the tree exists, even when it is empty.

Nodes can have as many children and siblings as possible, but each node only has a pointer to its first child and next sibling, and an additional one to its parent node. Therefore, each node ends up having a pointer to the first element of a linked list of child nodes, and also a pointer to the next element in the linked list of child nodes of its parent. In the end, this so-called Tree structure is better define as Tree of Linked Lists. Here is a diagram I drew to explain myself better.


Well, I’m off to do some code-commenting and smoothing of the rough edges (trying to optimize as much as possible). I’ll let you know how this part ends in the next post. See you around!

Adios!