C++ Code Optimization – Optimizing a Particle System

In the fall quarter of 2013 at DePaul University, I took the GAM491 – Optimized C++ class. In this class we learned very advanced techniques to optimize any C++ code. As a final project, we were provided with an old and slow particle system. Each student was required to individually submit an optimized version of it applying as many techniques of what we have studied as possible. The rules were:

  • Keep the number of particles at 20000 for the benchmarks.
  • Keep the particles lifetime at 11 seconds.
  • Do not modify any OpenGL calls, just the modification of the  C++ code, the algorithms and the data structures used were allowed.
  • Do not change any of the particle system behavior.

The results of the optimizations that I made were impressive. They are shown below (an improvement by a factor of about 160 times):

Before

Before - Particle System

Before – Particle System

After

After - Particle System

After – Particle System

Building The Animation System of My Game Engine

For the second milestone of the Game Engine Programming II class that I took in the spring quarter 2013 at DePaul University, I added animation capability to both my game engine and my FBX converter. It was one of the most difficult tasks that I did for this class. It took a lot of iterations to write a good easy-to-use animation system. My intention was to make the system completely data-driven, having the FBX converter extracting all the needed animation data from the FBX file (an FBX file can contain multiple models, with each model having multiple animations in a so-called animation stacks) and placing these data as a table-indexed binary chunks into a .dpu file for the model data, and into a .bdpu file for the skeleton data. The extracted skeleton data are:

  • The skeleton bones hierarchy.
  • The skeleton’s animation stacks.
  • The keyframes associated with each bone in each animation stack.

I then made the game engine capable of loading these data, and using them to draw the bones and animate them.

The Math Engine Library that I wrote for the first part of this class had to be changed to support quaternion math operations and to fully integrate them with the existing vector and matrix operations. Linear & Spherical Linear Interpolation (LERP and SLERP) operations have been added as well. These operations are crucial to any animation engine.

The Animation Engine Features

  • Completely data-driven (loads all needed data from a flexible expandable binary file).
  • Ability to draw bones based on the data read from the binary file. Bones colors can be changed by the user of the system.
  • If the FBX model has multiple animations in multiple animation stacks, they will all be available for that model’s bones and any of them can be selected to be the current active animation in the engine.
  • Ability to play back the animations forward, backward, faster, and slower.

Next thing I will be working on is “Skinning”. The above features are demoed in the below video.

Building an FBX File to My Game Engine Binary File Converter

During the second class of Game Engine Programming, which I’m currently taking this quarter, we are learning how to write offline tools to help us feed data (models and animations) into our own game engines. The choice was to create a command-line tool that converts an FBX file to the binary format expected by my own game engine ( I call it the .dpu file ). It’s a command line tool so that it can be easily used in a script to handle multiple conversion. We also chose to work with FBX files since they are widely supported by most 3D graphics creation suites. Its SDK is very well documented, and the documentations contain a lot of examples.

For the first milestone of this class, each student was required to individually write his own converter, and modify his own game engine as needed. I modified my game engine so that it’s more dynamic when loading the .dpu files. It deals now with indexed binary chunks rather than a fixed set of data in the file. It can also deal with models that are built from multiple meshes placed in a certain hierarchy. The game engine can now load these hierarchies dynamically into the scene graph and transform them correctly according to the extracted matrices from the FBX file.

Each student was required to record a demo video of his converter and Model Viewer (modified game engine), and write a design document demonstrating his own game engine binary format and why he made his own design decisions.

Here is the video:

Building And Integrating CppUnitLite in Eclipse on Linux

For this tutorial, I will be demonstrating how to build and integrate the lightweight C++ Unit Testing Framework, CppUnitLite, into your eclipse projects. I will be using Eclipse Juno on Xubuntu, but the same can be done on any other platform of your choice.

If you are familiar with CppUnit, CppUnitLite is – as the website mentions – more barebones, lighter, and more portable as it avoids using some C++ features such as exceptions, and templates.

We will build it as a static library, so that we can then link into any of our projects that we would like to write unit tests for later.

First, we need to get the source code form the CppUnitLite website. Go there and get it. Once you do, extract the zip file. You’ll find that it contains a lot of files and a couple of folders. We only need a sub-set of those, specifically the folders in the CppUnitLite sub-folder highlighted in the below screen shot.

Needed Files

Now go ahead and open up Eclipse. Select File > New > C++ Project.

New C++ Project Menu

From the C++ Project Window, name your project CppUnitLite, and make sure you selected a Static Library project type. Now click on Next >.

Static Library

For the build configuration, you can just select Debug for now. Then click Finish.

Build Configuration

You are now ready to import the source files. Right-click the project and click Import … from the menu.

Import

From the Import window, select General > File System as the import source. Then click Next >.

Import Source

From the next window, click on the Browse button, and navigate to the folder where the needed CppUnitLite sources (highlighted at the top of this post) are located. Now select only the needed files. Make sure NOT to select the two sub-folders Cpp and CppUnitTests. When you’re done, click Finish.

Import Files

Now before we build, I hope you noticed on their website that they have this important note about a bug in the CHECK_EQUAL macro, and the revised one has been provided. This macro is located in the file Test.h. Copy the correct one from the website, and paste over the wrong one in the file.

CHECK_EQUAL Bug

CHECK_EQUAL Correction

Now Build the project. This will create a sub-folder named Debug under your project. If you take a look inside it, you’ll find a file named libCppUnitLite.a. This is the static library file that you would want to link in your projects later.

Build

Library File

Now we’re done with building the library, and we need to experiment with it to write some simple unit tests. For demonstration purposes, we will create a new project, import the library, and the header files of CppUnitLite there, and write some simple unit tests just to show how things work. Create a new C++ project, and make sure the project type is Executable this time. Name the project whatever you want. I named it TestCppUnitLite. Now click Finish.

Test Project

We will create a sub-folder under this project in which we will import the CppUnitLite library and header files shortly. Right-click on the project name and select New > Source Folder. Name the folder CppUnitLite.

Source Folder Menu

Now right-click on that newly created folder, and select Import. From the Import window, as shown above, select General > File System as the import source and click Next >. Click the Browse button and navigate to the folder where we built the library. Once you do that select only the library file (libCppUnitLite.a) from the list and click finish.

Import Library

Repeat exactly the same above mentioned process again to import the header files. Just browse to where they are and import them into the same folder. You’ll need to import 6 header files namely Test.h, TestHarness.h, TestResult.h, TestRegistry.h, SimpleString.h, and Failure.h. Then click Finish.

Import Headers

Now it’s time to write some simple code. Right-click on the project name, and click New > Source File. Name the file main.cpp and click Finish.

Main CPP

All you need to write is the following code. It’s kind of like a boiler-plate code to start running the tests and reporting the results.

#include "CppUnitLite/TestHarness.h"
int main()
{
     TestResult tr;
     TestRegistry::runAllTests(tr);
     return 0;
}

At this moment there isn’t any tests to run, so we need to write some very simple tests just to show how things work. We will create a new source file and we will name it tests.cpp. In this newly created file we will write some tests, some of them are intended to fail just to show how CppUnitLite reports a test failure. Notice that CppUnitLite used predefined macros to enable us to write these simple unit tests easily. Copy and paste the following code into tests.cpp.

#include "CppUnitLite/TestHarness.h"
TEST(EqualitySuccess, EqualityGroup)
{
     int a = 5;
     CHECK(a == 5);
}
TEST(EqualityFailure, EqualityGroup)
{
     int a = 6;
     CHECK(a == 5);
}
TEST(GreaterSuccess, GreaterGroup)
{
     int a = 50;
     CHECK(a > 30);
}
TEST(GreaterFailure, GreaterGroup)
{
     int a = 50;
     CHECK(a > 100);
}

For any test you write, First you’ll need to include the TestHarness.h header file, which includes all of the others for you. Next you’ll need to use the TEST macro. the TEST macro takes two arguments, the first is the test name, the second is the test group. This is useful when you want to create multiple tests that belong to a single group. As you can see above I have to test groups, each of which has two tests, one that is intended to succeed, and the other is intended to fail.

I’m using the CHECK macro for all of my tests above, but you have others too that you can use such as CHECK_EQUAL, LONGS_EQUAL, .. etc. They’re defined in the header file Test.h.

Now we need to build and run those tests to see the result. But WAIT!! If you try to build now, you’ll fail as the linker doesn’t know how to link to the library file. You must specify that yourself.

Right-click the project name and select Properties. From the Properties window, go to C/C++ Build > Settings. From the Tool Settings tab, under GCC C++ Linker > Libraries, you’ll need to do two things.

Linker

You’ll need to add  the library search path. Click on the Add… button next to Library Search Path (-L) and click on the Workspace button, and select the folder where we imported the library file. click Ok, and then Ok again.

Linker Search Path

Next you’ll need to specify the name of the library. From the same window click on the Add… button next to Libraries (-l) and type CppUnitLib. Remember our library file is name libCppUnitLite.a, but GCC C++ Linker doesn’t need the lib or .a parts of the name. So if you named your library libMonkey.a, just type Monkey when you add the library :). Click Ok and then Ok again to exit the project Properties window.

Linker Library

Now everything is ready to build and run. Build the project and run it as a C++ Application, and see the output on the console window. You’ll see that it reports the two intentional failures, what conditions that failed, in which files they are, and in which lines as well.

Console

That’s it! As you can see it’s quite easy and simple to work with CppUnitLite. Thanks everyone! Happy unit testing.

N-Queens Problem Solution With C++

The first meeting I attended at the DePaul University Computer Science Society was all about problem solving. Using one’s programming knowledge to solve some difficult problems programmatically which would be very tedious to solve otherwise, is a skill that is very important to acquire for any programming student. In the end, that’s what programming is all about solving problems, not only correctly, but also, efficiently.

One of the problems we were discussing, was the 8-Queens problem, Which, in order to solve it, you must know where to place your 8 queens on an 8 by 8 chess board, so that they won’t attack each other. This implies that you cannot place two queens on the same row, column, or diagonal.

8 Queens Problem

8 Queens Problem

Afterwards, we started discussing the solution to the more general problem, which is to place any number of queens, say N queens, on N x N chess board. My colleagues at the society, being much more experienced than I am, were able to write solutions to this problem recursively, using Python, or Haskell. I chose to write an iterative solution in C++.

My solution is quite simple. The lower part of the above picture shows a sample output when running the program like this on Linux:

./nqueens 8

Where 8 is the size of your chess board. The numbers in the output are the rows indexes where you should place your queens per each column.

The code implements the method I would follow if I would solve the problem manually by hand. I fill the queens column by column, until I reach a column in which I can’t find a valid place for the queen. At that point I backtrack, going back to the previous column, and change the position of my queen there to the next valid row in that column. If not found, I backtrack more, if found, I go forward and try to fill the rest of the columns.

Please take a look at my code, and feel free to ask any questions. May be if you have suggestions to better improve this solution, I would be also thankful. 🙂

N-Queens Problem Solution in C++ by Ahmed Fakhry

Thank you very much!