Whatever Crossed My Mind

Introduction To WP7 Development and Farseer Slides

2012-01-30T08:49:00.001+01:00

I've put up the slides from my presentation at Nordic Game Jam 2012. Have fun!

Windows Phone 7 Isolated Storage Helper

2012-01-12T20:20:00.001+01:00

While working with isolated storage on WP7, I faced a lot of problems such as deleting a folder containing files. The default behavior of the isolated storage is safe, this means it will not delete folders that contains files. I was also missing the convenience methods ReadAllLines() and WriteAllLines() we normally have in the .NET Framework 4.

I decided to write a small helper that supports this functionality. You can find a description of each below:

DeleteDirectoryRecursive()
WP7 isolated storage does not delete folders that contains files. This method finds all sub folders, delete files inside the sub folders and then the folder itself.

ReadAllLines()
Reads all the lines of a file and puts them into a list. This is missing from the IsolatedStorageFile API

WriteAllLines()
Writes all the lines of an enumerable collection to a file. If the file does not exist, it will create it. If the file already exists, it will overwrite the file. Just as ReadAllLines(), it is just a convenience method that is missing from the IsolatedStorageFile API.

The code can be found on my SkyDrive.

How To Make Codeplex Remember Your Password

2011-12-31T23:20:00.001+01:00

Codeplex is an open source community site created by Microsoft, and it is also where I currently host the Farseer Physics Engine project. One of the problems I’ve always have had with the site, is the missing “Remember Password” checkbox for the Team Foundation source control login. The reason they are missing the feature, is that the client is actually using the credential manager inside Windows. Here is how you make it remember your password in Windows 7:

Click Start
Click Control Panel
Click Credential Manager
Click “Add a Windows Credential”
Enter the following information:

Internet or network address: tfs.codeplex.com
User name: <Your Username Here>
Password: <Your Password Here>
Click OK and the Team Foundation client should never ask you again.

XNA and Farseer Physics Engine 3.3 Presentation at Nokia

2011-12-07T03:08:00.001+01:00

The slides and demos from the presentation at Nokia can be found here.

Thanks to everyone that showed up!

XNA 4.0 Introduction

2011-12-05T17:19:00.000+01:00

The PowerPoint slides and XNA HelloWorld application from my talk at ITU can be found here.

Thanks to Joe Kiniry for lending me a room to do the presentation.

Benchmarking Box2D Based Physics Engines

2010-12-27T17:56:00.001+01:00

With the help of Paril - the developer of Box2C - I've made a benchmark of the following engines:

jBox2D rev 261 trunk
Box2D 2.2
Box2D 2.1.2
Box2C rev 20 (wrapper for Box2D 2.1.2)
Farseer Physics Engine 3.2

I were quite surprised by the findings, so I decided to post them here.

I benchmarked the different engines using the Pyramid test from the Box2D Testbed. We used a pyramid base count of 35 that resulted in 630 stacked boxes at once. We found that higher base count resulted in too much breakup in the pyramid in the engines based on Box2D 2.2. I started the tests and waited for the solver to converge and the timer output became steady. I repeated this several times to make sure the results were consistent.

Test system

2 x Quad core Xeon 2.33 Ghz 1333 Mhz FSB
6 Gb FBDIMM RAM
Geforce 7900 GT 256 Mb RAM

Running Windows 7 64Bit with as few applications as possible.

Box2D Settings

Velocity iterations: 8
Position iterations: 3
CCD: Enabled
Sleeping: Disabled
Warmstarting: Enabled

Rest of the settings are the Box2D defaults.

Results

jBox2D rev 261 trunk (Fastmath = false to the right)

Box2D 2.2

Box2D 2.1.2

Box2C rev 20

Farseer Physics Engine 3.2

Engine:	Time	Notes
jBox2D rev 261	11/12 ms	Unstable pyramid when fastmath was set to true – I clocked it at 11 ms. Some boxes fell of the top and fell outside the screen. With fastmath = false, the simulation was a bit more stable, but also a bit more wobbly. Turing off fastmath resulted in 1 ms slower simulation (total: 12 ms)
Box2D 2.2.0	8 ms
Box2D 2.1.2	10 ms	Simulation seems more rigid than Box2D 2.2.0 and the pyramid looks perfect.
Box2C rev 20	13 ms	3 ms slower because of the overhead of being a C# wrapper.
Farseer Physics Engine 3.2	6 ms

Conclusion

Farseer Physics Engine 3.2 is by far the fastest of the engines, which might seem a little odd considering it is a direct port of Box2D 2.2.0 and written in C#. However, due to the heavy manual optimizations done to the collision system, it manages to be even more efficient than the original Box2D library. I’m not sure how different jBox2D is from Box2D 2.2 seeing as it produces different results from the rest of the engines, but 11-12 ms is a pretty good result considering it is written entirely in Java.

Optimizing Performance On The Xbox 360 - Part 2

2010-11-25T20:16:00.001+01:00

In part 1 I described the reasons why Xbox 360 is slower than an equivalent PC and some of the basic recommendations for optimizing C# code to make it run faster. In this post I will mention a few other tricks to increase performance on the Xbox 360.

Structures… again.

In the .NET world, objects are allocated on the heap and structures are allocated on the stack. Remember, only the heap is garbage collected, this means that structures are not subject to the expensive garbage collection operation. Allocation on the stack is basically free as we only need to increase a stack pointer and call a constructor. This means you can reduce garbage collection and increase speed by using structures instead of objects – however, you need to know the difference between the two. You should also follow the general recommendations for using structures:

Small data objects (data containers)
Often destroyed or created
Read-only (or mostly-read) objects

Reuse those objects

As mentioned before, objects are allocated on the heap that is garbage collected. That is why you should avoid creating a lot of objects on each update. Instead, you should reuse the objects using pools as explained in part 1. Another and simpler way is to move the object to outer scope and/or make it static. One object that you should pay close attention to is the SpriteBatch (if you are using XNA). Do not create the SpriteBatch object on each update, but keep a reference to it through out the game.

You should also pay attention to List<T>, arrays and other commonly used list types. When you create a new List<T> and add a single item to it, it will initialize an array with a size of 4. If you add more than 4 elements, it will create a new array with double the size. The results is that 2 arrays have been garbage collected. To keep that from happening, you should initialize List<T> with a capacity that is equal to what you need. To keep the List<T> form being garbage collected, you should move the list to outer scope and clear it before use instead of initializing a new instance.

Boxing

Boxing is the process of encapsulating a value type in a reference type container. This is great as it allows us to pass value types as objects to methods or store them in collections as objects. However, this is not great for performance and we have to eliminate boxing and unboxing where we can. You can use tools like Reflector or Ildasm to disassemble your application to MSIL code. Inside the MSIL code you simply look for the box and unbox keywords. You can find more info along with pictures in my post Performance Tips and Tricks Part 4.

Optimizing Performance On The Xbox 360 - Part 1

2010-11-21T19:52:00.001+01:00

After my Performance Tips and Tricks series I got a lot of requests to write a post regarding the performance on the Xbox 360 platform. I will try to focus on why Xbox 360 is slower than PC and what we can do to get around it. But first we need to underline the importance of good programming.

Algorithms and datastructure complexity

I’ve been on the topic of complexity before. I can’t underline how important it is that we keep the complexity of our algorithms low. If you are sorting a large dataset, make sure you use the correct algorithm and if you are sorting a small dataset (<10 items), there is another and faster algorithm.

Note: If you use .Net List<T>.Sort(), it automatically chooses the best algorithm depending on your dataset.

If you are using pixel perfect collision detection, perhaps you should implement a physics system that uses a polygon collision system instead. You could also implement a broad phase system to filter out collisions that you don’t need to process. Implementing a fast and efficient algorithm is 100 times better than any micro-optimization or performance trick out there. But this post is not about using efficient algorithms, it is about the case where you already have implemented the algorithms and still need to squeeze the last drops of performance out of the platform.

Why is it slow?

Xbox 360 uses a custom triple-core 64bit PowerPC 3.2 GHz CPU. It is designed by IBM with high floating point performance in mind by using multiple FPU and SIMD vector processing units in each core. It is a quite powerful platform, but an equivalent PC still outperforms it, how can that be?

I’m afraid that the hardware is not the problem here, it is the software on the Xbox 360. Let us take an example; the following piece of code runs in 12500 ticks on Xbox 360 and 10 ticks on PC.

That is a huge difference and even if we switch to integers instead of floats (to get around the FPU) we still get around 7060 ticks on Xbox 360 and 10 ticks on PC. The low performance when using floats is due to missing AltiVec support in .Net Compact Framework and some missing optimizations in the floating point code. The .Net Compact Framework was not designed to run on Xbox 360. In fact, it was designed with portability in mind and did not have any floating point code until the Xbox was released. Thankfully the .Net CF team implemented some FPU code and that improved the floating point performance a lot (by a factor of 10!).

Then there is the garbage collector. The CF has a simplified version of the garbage collector that works without generations. Instead it looks up all the objects after 1 MB has been allocated. There are also a few other differences such as code pitching where the GC frees code it has jitted before to free up memory. And last but not least there are the compiler optimizations performed by the CF JIT compiler. The optimizations carried out by the CF JIT is severely limited, especially the method inlining. The CF JIT will only inline a method based on the following criteria:

16 bytes or less of IL
No branching (if statements)
No local variables
No exception handlers
No 32-bit floating point arguments or return value
If it has more than one argument, they must be accessed in order from lowest to highest.

That means it is basically only inline property getter/setters and methods that call other methods.

The missing FPU code, the few optimizations and the simple garbage collector is all because the CF never was designed to work on anything else but embedded devices such as mobile phones. Lets take a look at what options we have…

Optimizing the code

It is very important that you start by profiling your code. You can use the XNA Remote Performance Monitor to profile memory allocations (garbage collector problems) and you can use the Stopwatch class to profile different areas of your code to see which area you should focus on. A normal PC profiler also comes in handy as the areas that tend to take up the most time on PC, almost always are the same areas on the Xbox 360.

When you have found the different areas to focus on, we can move on to actually optimizing them.

Virtual methods
One of the places to optimize are the virtual methods and properties. While virtuals are great for OOP, they are not so great for the CF JIT compiler. Virtual methods are around 40% slower than static or instance calls and just to make it all worse, they are never inlined by the compiler.

To get around it you need to avoid virtuals where you can. If you need to use virtuals, make sure you mark your overridden methods and classes as sealed. If you use the sealed keyword, the compiler can sometimes resolve the destination of a virtual call and avoid the expensive virtual call.

Use fields instead of properties
While properties are a neat way to keep your code clean, they are not that great performance wise. Under the hood, properties are ordinary methods and while simple get/set properties gets inlined by the compiler, there are no guarantees that all of them will get inlined. The solutions is to use fields instead, but not at the costs of a poorly designed application. So use it wisely!

The ref keyword
If you are working with structs, you should try and use the ref keyword to send them by reference instead of by value. If you are working with the XNA library, the Matrix, Vector2 and Vector3 classes have math methods that uses ref and out to pass structs by reference instead of by value.

Inlining
Manually inlining code when using the Compact Framework can give you an extra performance boost. The gain is typically around 5-15% depending on your code. The tricky part of inlining is to determine what code to inline. I recommend you follow some simple rules:

Small methods
Methods that are only called from one place
Methods that does not alter the state of the object (only give input and get output methods)
Methods that does not already get inlined by the compiler

It is important to run a profiler while you inline. You might get even worse performance by inlining the wrong methods. It is important to measure it!

Pooling
In the CLR, creating an object is a really efficient operation while destroying the object is not. This is due to the fact that destroying an object will make it subject to the garbage collector. A way to get around this is to use pooling of objects. You basically create a pool (you could use a stack) and then pre-allocate a bunch of empty objects before use. When you need an object, you fetch one from the pool and when you are done with it, you put it back in the pool. This way you keep the object reference alive and it will get collected by the garbage collector.

Fixed point math
I’ve been on this subject before. If you have some heavy floating point operations that you need to run on a platform with low floating point performance, then you should implement fixed point math. A trick is to identify operations that don’t need floating point accuracy (like my code above in the explanation) and convert it to use integers instead.

Update: Part 2 is here.

Farseer Physics Engine 3.1 released

2010-11-12T19:51:00.001+01:00

I’ve just packaged and released Farseer Physics Engine 3.1. It has a lot of new features and a couple of bugs have been fixed. You can see a list of changes in the new version on the downloads page.

Tunneling explained

2010-10-27T12:56:00.001+02:00

Tunneling is an effect where two shapes can get stuck in each other or simply pass each other without impact. The effect exist because we are limited by the CPU and have to do the calculations in timesteps instead of one continuous stream.

The effect comes apparent especially at high velocities and/or with small shapes. Bullets of a gun is a perfect example because they are usually fired with high velocity and are small in size. To illustrate this, have a look at the following picture:

(The numbers illustrate the timestep/seconds)

Imagine that it runs at 1 second per update with a velocity of 34 pixels/second
Everything is fine because the bullet hits the wall as it should and the physics simulator responds with a proper collision reaction.

But when we turn up the velocity to 89 pixels/second, then this happens

The bullet went right through the wall - the physics engine never had a chance of responding to the collision because it never happened - that is what is called tunneling.

What can be done about it

There exist something called CCD or Continuous Collision Detection. It is a name that covers several different methods of preventing tunneling, one of the more used ones is Conservative Advancement. CA is a substep that is performed within a world timestep. Tt moves the shape along its path until it reaches the next timestep. This is very CPU expensive so it is best to turn it on only for shapes that needs it.

There are simpler ways of limiting tunneling, but they are not as effective in all cases:

Use a smaller timestep in the physics engine
Use raycasting
Make your shapes larger
Make your shapes slower

Value Types and Reference Types Explained

2010-09-10T23:11:00.001+02:00

There are two types of data types in the .NET framework: Value and reference types.
Lets first have a look at the value types:

Value types are allocated on the current thread’s stack.
The lifetime of the value type is only inside the scope where it is used.
When you pass a value type as a parameter in a method, the value type is copied.
A wrapper object is created if you pass a value type to a method that expects an object.

Value types are suitable for representing lightweight objects such as vectors, matrices and colors. Value types has less overhead than classes by the fact that no additional memory for the reference is needed. However, there are a few things that are worth mentioning:

Structs can’t have a default parameterless constructor. It is provided by default and it initializes all the fields to their default values.
You can’t initialize an instance field inside a struct
You can’t use inheritance in structs

Value types are important for performance since they are allocated on the stack (the stack is not garbage collected) – they are cheaper to allocate and deallocate than classes. However, if your struct is more than 16 bytes, it may be more efficient to use a class instead.

Now, let us have a look at reference types:

Stored on the managed heap.
Variables that are reference types only contain a pointer to the data.
Reference types are garbage collected when they are no longer referenced.
Are always passed by reference (the pointer to the data is passed)

For your convenience, here is a list of value and reference types:

Value types	Reference types
Enums Structs Boolean, Date and Char Decimal Byte, Short, Integer, Long Single and Double	Classes Delegates Exceptions Attributes Arrays

The ref keyword

The ref keyword is very important when it comes to both performance and the behavior of value and reference types. If you put ref in front of a parameter in a method, the argument is passed by reference regardless whether it is a value or reference type.

Example:

The output of this application is “http://google.it”. If we didn’t have the ref keyword in front of the parameter, the output would be “http://google.com”. This is because the original pointer (reference) to the data is passed to the method when using the ref keyword. Value types can also be passed to the method by reference (and no, it does not get boxed) – yielding the same behavior as the reference type.

Blank Visual Studio 2010 Team Explorer Window

2010-09-07T14:03:00.001+02:00

Recently I decided to upgrade my Visual Studio 2008 installation to Visual Studio 2010. I uninstalled all VS2008 packages and made sure to clean out folders left behind. After a long VS2010 installation I fired up Team Explorer and connected to my Codeplex.com projects; after doing so, I was met by an empty Team Explorer window.

Several reinstalls later and registry changes I tried reading up on how to repair installations and came across the command:

devenv /setup

The setup switch did the trick and I now have a fully working Team Explorer window.

Farseer Physics Engine 3.0 Has Been Released!

2010-08-23T22:35:00.001+02:00

It is out! The next generation of physics engines for the .NET platform has finally been released. It uses Box2D as the core engine, but it is so much more than just an ordinary physics engine.

You can get the 3.0 release from the Farseer Physics Engine Codeplex project.

Synchronizing Google Calendar with iPhone and Outlook

2010-08-16T23:02:00.001+02:00

I bring this little tutorial to show how to synchronize Google Calendar with both iPhone and Outlook. I use Outlook 2010 and iPhone iOS 4.0.1 for this tutorial.

Outlook 2010

Download and install Google Calendar Sync. This will enable you to syncronize between Google Calendar and Outlook.
Test out the synchronization by creating an event in Outlook calendar, right-click on the Google Calendar Sync icon in the notification area, and click “Sync”. Your event should show up in Google Calendar.

iPhone iOS 4.x

Click “Settings” and click on “Mail, Contacts and Calendars”.
Click “Add account” and pick “Microsoft Exchange” (Yes, we use Microsoft Exchange in this case. It enables Google Mail, Google Contacts and Google Calendar push-notifications support)
Enter your information:

E-Mail
Leave Domain blank
Your username; put your full email here
Your password
Description contains the name of the account. You can leave it to the default or choose one yourself.

Once you click Next, it should take 2 seconds and a Server field appears. Enter “m.google.com” and click Next again.
Select the services you want to sync. I have both mail and calendars synchronized with Google.

That is it. When you create a new event in Google Calendar, it will appear a few seconds after on your iPhone.

Shared Google calendars

A friend of mine and I share a calendar on Google Calendar. Unfurtnaly it can’t be synced with Google Calendar Sync since it only works with your default Google calendar and default Outlook calendar. However, there is a way to make your iPhone work with shared calendars:

On your iPhone, go to the address: m.google.com
Log in to Google using your Google account.
If it tells you that your device is unsupported, switch the language to English and it should disappear.
Select your device from the list.
Select the calendars you would like to sync.

Note: This did not work on my phone right away. I had to untick it and tick the shared calendar again before it worked.

Update:

Google has a sync page that gives you a tutorial for your device. The same tutorial as I wrote can be found here for iPhone. I will let this post live because it contains information not found in the Google sync tutorial (like step 3 in shared calendars).

Make Team Explorer Remember Login Credentials

2010-07-31T17:23:00.001+02:00

When working with Team Explorer in Visual Studio, you might have come across the annoying user login box that pops up each time you open a Team Foundation Server connected solution. The Team Explorer development team decided to use the built-in credential vault in Windows instead of using their own implementation. Here is how you save the credentials inside the Windows 7 credential vault.

Open the Control Panel
Click on User Accounts (Called User Accounts and Family Safety in category view)
Click Manage Your Credentials to the left (Called Manage Windows Credentials in category view)
Next to the Windows Credentials category you click the Add a Windows credential button.
Enter server address, username and password.
Click Ok

Now the Team Explorer client should remember your password.

Broad And Narrow Phase Collision Detection Systems

2010-07-03T23:23:00.001+02:00

If you don’t know about the big O notation, I recommend you read about it here first. This post gives you an idea of what broad and narrow phase algorithms are and how they are used in physics engines.

Broad Phase Collision Detection

Performance is an essential part of a physics engine. You can get away with just implementing a few algorithms that detect collisions using a O(n^2) algorithm, but when you add more and more objects to the simulator It becomes quite expensive (CPU wise). Not very good for performance.

We can reduce the amount of tests by implementing a broad phase into our collision system. It is responsible of eliminating tests and thus reducing the number of tests needed (We obviously don't need to test objects far away from the player). We could for example have an algorithm that tests the distance using the X and Y axis of the screen, if the objects are too far away from each other, we can eliminate them as potential collisions. There are many algorithms that can eliminate tests, a few of them are:

SAP (Sweep and Prune) - More info - O(n log(n)) algorithm

Spatial Hash - More info - O(n log(n)) algorithm

If I remember correctly they can be O(1) in best case and O(n^2) in worst case.

It is important to remember that the broad phase only keeps track of the distance between objects. If they are close enough to create a potential collision, the objects are paired. To determine if two objects are close enough to create a collision, we use something called a AABB (Axis Aligned Bounding Box). It is simply a box that does not rotate that encapsulates the whole object. It is cheaper to test box vs. box instead of a lot of polygons vs. polygon.

Too far from each other to be tested for collisions:

Close and needs to be further tested for collision:

Narrow Phase Collision Detection

Once the broad phase collider has done its job, we are left with a couple of pairs that needs further testing. A physics engine needs to know exactly how deep polygon shapes have penetrated each other and some other stuff like the normals. A narrow phase algorithm basically takes in two polygon shapes and finds out where those two polygons intersect and how deep.

We need the depth of penetration, the normal and the position of the collision to calculate a proper physics response.

Collision where the red dot is the point of collision.

There are also a few different narrow phase algorithms. Two examples of such algorithms are listed here:

SAT (Separate Axis Theorem) - More info
Distance Grid - More info

The Big O notation – Summary

2010-07-03T23:17:00.001+02:00

Big O notation was invented to describe the growth rate of a function. You basically take away all constants and small factors and only focus on the big factors. Let’s take an example; the function:

x^2 + 2x + 6

in terms of big O notation becomes:

O(x^2)

We use this notation to describe the growth rate of algorithms too. A brute force algorithm that checks each and every object against the next is called O(n^2) (quadratic growth). If you have 100 objects, you will have to do 100^2 = 10.000 checks.

Having a O(n log(n)) algorithm is obviously better as it grows slower. If you have the same 100 objects, you will only have to do 100 * log(100) = 200 checks!

To give a graphical view of the growth. X is the number of objects and Y is the number of collision checks that needs to be performed.

As you can see, when the number of items increase, the number of checks to perform increases much more rapidly in the n^2 function than the n*log(n) function.

Here is a table of the mostly used notations:

Notation	Name
O(1)	Constant
O(log n)	Logarithmic
O(n)	Linear
O(n log n)	Linearithmic
O(n^2)	Quadratic

You can find a more complete list in this Wikipedia article.

The Ramer-Douglas-Peucker Polygon Simplification Algorithm

2010-05-30T15:13:00.001+02:00

One of the important algorithms in vector graphics and robotics is the Ramer-Douglas-Peucker algorithm. It simplifies a polygon by reducing the number of points by some tolerance. It was invented independently by Urs Ramer in 1972 and by David Douglas & Thomas Peucker in 1973. In 1992 it was improved by John Hershberger & Jack Snoeyink at the cost of the algorithm only working with simple 2D planar polylines, and not in higher dimentions.

Here is how it roughly works:

0. Start with a polygon.

1. Make a polyline between the two endpoints. This is the initial approximation to the simplified polygon.

2. Calculate the distance between the edge and the remaining vertices. If the vertex tested is further away that the user defined tolerance, then the vertex is added to the simplification.

3. Repeat step 2 until you have a complete approximation of the polygon like shown in step 4 in the picture.

The idea with the algorithm is that we can give it an input like the one to the left and get an output like the one to the right:

This gives us a lot of possibilities; it can reconstruct the original representation of a polygon and it can provide us with compression of the data. A large and complicated polygon can be simplified down to the bare essentials by reducing the details of the polygon.

I’ve added this algorithm to Farseer Physics Engine 3.0.

Physics engine series

2010-02-15T22:18:00.001+01:00

A quick post to summarize the posts I’ve already made on physics engines. The series are not yet done. I will cover the broad and narrow phase algorithms when I get around to write about them.

Part 1 – The very basics of physics engines. What is the responsibility of a physics engine and how are they defined.

Part 2 – A quick overview of how a physics engine work. Collision detection, physics response and their submechanisms.

Part 3 – A look into the physics response part of a physics engine. How do we calculate velocity and how do we apply it using numerical integration.

Performance tips and tricks series

2010-01-21T17:29:00.001+01:00

In the past I posted 4 blogs posts with ways to optimize your applications using keywords, compiler tricks and approximations. Here is a quick overview of the blog posts:

Part 1 – Common sense in application development. Use constants and loop manipulation.

Part 2 – Most commonly used keywords in C#: sealed, static, struct, ref, out and unsafe

Part 3 – Information about method inlining. Notes on virtual calls, struct arguments and exception handling. Short introduction to loop unrolling.

Part 4 – Boxing and unboxing, more on exception handling and string operations

Hopefully I will get the time to write some Xbox360 specific optimizations in the near future. I’m busy with the development of Farseer Physics Engine 3.0 at the moment, so it might take some time.

My Xbox 360 nightmares

2010-01-08T01:26:00.001+01:00

Once upon a time an open source software developer wrote a physics engine for the .net platform. (Let us call him me!) Because of many requests from his users, he targeted Xbox360 as one of the supported platforms.

The many users of his free physics engine felt generous and donated a Xbox360 so that he could optimize the physics engine for that platform. Overjoyed by the offer, he accepted and could not wait to see what kind of machine the Xbox360 really was.

Nightmare number 1
After paying for a cheap Xbox360 Arcade on the Internet he waited almost a month before realizing something was wrong. After 5 emails to the retailer and several weeks later, the order was finally canceled and he went on another journey to find a cheap retailer that would provide him with a brand new Xbox360.

Nightmare number 2
After his first experience he checked out all the possible references to the new shop as he possible could. Customer comments, google ratings and even the famous E-Mark. Little did he know that the retailer just repeated his experience from the first nightmare. After several weeks, he finally got his money back again.

The dream of a Xbox360
Eager to try off a Xbox360, he went to a store with a brand new Xbox on display. He walked to the customer information desk, only to be informed that they had no Xbox360 left in the store. Feeling a taste of defeat he went outside the store to think about where to go next…

WAIT someone said from inside the store… the developer turned around to see a guy with a big greenish box with XBOX 360 written on the side. Renewed with joy and happiness he went to the checkout to get his brand new Xbox360 home. After connecting everything and make it look like the alter in a church, the Xbox360 turned on with all the glowing colors of 1080p HD.

Nightmare number 3
Like a kid at Christmas time the developer turned on his computer and tried to connect to the Xbox360. Little did he know that it required an application that could be found in the Game Markedplace, and to get the application, he had to pay 1/2 the price of the Xbox he just bought. Thinking that nothing should stand in his way of getting it to work, he paid the amount necessary and started waiting. After waiting for what seemed liked ages, the account was finally recognized in the Xbox system of magic and he could deploy games with ease.

Nightmare number 4
Getting tired of running the same physics simulation 100 times in a row and feeling curious about what else this new fancy thing could do, he decided to play some of the games that physics engine users had created. Clicking on the “free trial” link next to one of those games left him with a message saying “You have to be a gold member to play this game”… thinking that gold membership must be the Xbox world’s key to unlock all doors, he bought a gold membership and clicked the same link again. This time he got a new message saying: “This game is not available in your region”… Fury with rage he went to bed, cursing the name of Xbox while trying to sleep.

Back to the real world
Well, That was all I had to go though… only to discover that I had no way of playing the games that used the fruits of my labor. Waiting so long to get a Xbox360, only to find out I’m left with a useless mini computer with no games on it and a deep hole in my pocket. I hope that they are going to put Denmark on the “allowed region” list soon or my expensive gold membership is going to be a total waste. Thanks for nothing so far Microsoft.

Facebook style auto-complete textbox in ASP.net

2009-12-20T03:00:00.001+01:00

You might have seen the crispy AJAX enabled auto-complete list when entering friends into a textbox. I was especially intrigued by the “Compose Message – To:” textbox. You enter a part of a name and almost instantly a list of names popup. Adding a name is as simple as selecting it from the list and it gets added to the textbox.

I started to identify the different parts of this functionality:

Labels inside textbox
Auto-completion on entering text
Growable textbox size
Highlighting of results
Close button on labels
Many more…

It looked like a daunting task, so I decided to search for an already made solution instead of making one myself. I came across an Ajax Control Toolkit issue that requested this functionality and even a jQuery plugin mentioned on Stack Overflow. Seemed like a lot of people mentioned this functionality, but nothing really appealed to me until I found TextboxList on DevThought.com.

It immediately caught my attention since it had a working demo that was exactly what I wanted. The greatest thing about TextboxList is that it is simple and very extensible, so I started my journey to create a To: field like the one from Facebook.

ASP.net implementation

I’m working in ASP.net with C# and the demo provided by DevThought.com was PHP only. Since I have a past of PHP, I decided to quickly take a look at their demo and create a ASP.net clone.

The only thing I did was to convert the auto-completion to C#. Everything else has just been taken from the original demo and fitted into a simple web site project. You can download the source code here:

Download TextboxList ASP.net Demo

Pseudo orientation in Farseer Physics Engine

2009-11-23T01:43:00.001+01:00

Farseer Physics Engine does not know about its object’s orientation. It has no clue about what is up and what is down. It only needs to know where other objects are in the physics world – nothing else. Sometimes it is good to know what is left, right, top and bottom. In this blog post I will describe a way of determining the side on which an object is hit, no matter the rotation of the object.

Let’s take a simple box as an example:

We can easily determine what is left, right, top and bottom on that box. We do it all the time in the real world. In geometry though, we need to calculate it. Imagine a circle inside the box. This circle is made up of 360 degrees or 2*π in radians. We can now use this circle to find out where the box was hit (left, right, top, bottom) by determining the angle at which the other object hit.

A good reference to how radians are laid out on a circle can be found on Wikipedia.
Now we end up with something like this:

Now we need to determine the intervals of the angle values that makes up the 4 parts.

Right side: π*1.75 to π*2 and 0 to π*0.25
Bottom side: π*0.25 to π*0.75
Left side: π*0.75 to π*1.25
Top side: π*1.25 to π*1.75

But since we are using the Atan2 function that has a range from –π to π, we need a interval that is adjusted to that range:

Right side: –π to (-3*π)/4 and (3*π)/4 to π
Bottom side: (-3*π)/4 to –π
Left side: 0 to π/4 and –π/4 to 0
Top side: π/4 to (3*π)/4

Now that we know the interval of angle values to test against, we need something to test it with. Farseer Physics provide you with the normal of the collisionpoints (called contact). This is a vector pointing directly from the first geometry to the second.

It looks like we can measure the angle of the normal and then see what interval it is within right? Wrong… What if this happens:

Remember, the object is rotated, the intervals are not! If we measured the angle against the intervals now, it would say that the right side of the box is hit, when it is the top that gets hit.

The solution is to rotate either the intervals or the normal. I took the latter of the two. It can all be seen in the sample project below (Based on Farseer Physics Simple Samples for XNA):

Download sample project

(click the folder icon – XNA 3.1 needed to run it)

2D Physics Engine Tutorial – Part 3

2009-10-12T02:54:00.000+02:00

In part 2 we had a look at the collision detection part of physics engines. In this post we take a look at the collision response part and see what kind of mechanisms it involves.

Movement

Physics engines have the ability to move objects around both in linear and angular motion. It is done using linear and angular velocity (with speed and acceleration), force and integrators.

Velocity

Velocity is a vector that describes the rate of change in position; the magnitude of the vector is the speed and the direction of the vector is the direction in which the speed is applied.

Velocity definition

v is the velocity vector, Δx is the displacement and Δt is the change in time.

Force

Force exist in many ways, but generally it is the agent that cause a body to change in motion or make a mass change its velocity. Force has both magnitude and direction and thus it can be expressed as a vector.

Newton’s second law

F is the force vector, m is the mass and a is the acceleration vector.

Acceleration

Acceleration is change in velocity over time. Acceleration can be defined by isolating a from Newton’s second law:

Acceleration definition

F is the force vector, m is the mass and a is the acceleration.

Integrator

In the previous velocity definition it is stated that velocity is the displacement over time. If we know the current position, velocity and the force that will be applied on it, we can integrate it to find its position and velocity at some point in the future. The integrator performs numerical integration; that is – it takes a small step into the future and tries to find the next position and velocity an object will have – each time it takes a step, it will use the previous result as the new starting point. It works like this:

Use initial position, velocity and force
Step 1 time step into the future and integrate to find the new position and velocity
Add the position and velocity change to the previous position and velocity
Go to step 1, using the results obtained in step 3.

This way we can find the position and velocity of any object at any point in the future.

Euler’s method

Euler’s method is a simple first-order numerical integrator that we can use to integrate the position of an object. The step-by-step method mentioned above is used in Euler’s method.

Solving an example using Euler’s method of integration:

If we run this code, we will get the following results:

Time	Position	Velocity
0	0	0
1	0	10
2	10	20
3	30	30
4	60	40
5	100	50
6	150	60
7	210	70
8	280	80
9	360	90
10	450	100

The problem with this is that the result is not correct. Using the equation of motion we should get 500 meters:

But we got 450 using Euler’s method. That is because Euler is inaccurate when velocity over the time step is not constant. Using a smaller time step will get us closer to the real result, but it will always have an error.

There are a lot of alternatives to Euler’s method:

All of them are more accurate than Euler’s method, but they can also be slower (RK4 needs 4 steps at each iteration as an example) and they are more advanced.

Overview

Here is an updated overview of the physics engine structure. We just added the Integrator part of the engine.

User managed games and automatic server checks

2009-10-11T03:06:00.001+02:00

Let me ask you one thing: Why does network-enabled games utilize user controlled user management (like kick voting menus)?

The answer is really simply: User management

User management

Network-enabled games need some kind of online-police that can control the game and its users. Imagine a rouge user that joins an online game just to create havoc and chaos. I have met several examples myself in my past as both server admin, game moderator and as a player. They all have one thing in common: Make people angry and laugh at their inability to act on it. Let us have a look at the different types of bad guys:

The microphone guy

The first case is a user that connects his microphone, turns up his music (Usually obnoxious repeating music designed to drive people crazy) and press the “talk” button. This can continue the whole game and it makes people furious. Players start to blame the game and game moderators that they are not doing anything about it, but fact is that they are powerless. Once the trend has started, not even an army of server admins can respond fast enough to prevent the damage.

The message spammer guy

This one continues to spam the chat with messages of random characters. Games where the chat is displayed onscreen with the rest of the HUD are the most vulnerable ones. A devious mind can easily exploit the fact that the length of messages are only wrapped at the length of the screen. This means that he can eventually fill up the whole screen with text and make other users unable to see anything.

Example:

The foul mouth guy

The only purpose this guy has is to piss people off. He might not have bad intentions when starting the game, but as soon as someone addresses him, he sees an opportunity of playing a dangerous game of foul-mouthing. All kinds of bad words known to man are exchanged and if the game contains a profanity filter, it also becomes an exercise of finding words that are not included in the game blacklist.

The newbie hater guy

Games should be equal toward all its users in the sense that it should not prefer experienced users over new users. Once a newbie has achieved some kind of experience, he might feel better when jumping on new players and make them feel stupid. This guy makes experienced users group together and flame the new users and make them feel guilty. It can create a bad user experience and eventually loss of players.

The idle guy

This guy spawns in the game and then go for a 15 minute toilet visit. The word “player” means that the guy is playing – if he is not playing, then he is only in the way of other users. Imagine a line at the supermarket where you have been standing for 10 minutes before you realize that the guy in front of you suffers from narcolepsy and fell asleep while still standing up. (bad example, I know - You get the point)

The newbie general

This kind of guy really depends on the game. Some games contain a general or commander seat where guy in that seat controls stuff other users can’t. A good example is the Savage game where the job of the commander is giving buffs like heal, extra armor and give negative buffs to the enemy. Each game 1 player gets to know how to command and 10 players get experienced in fighting. This causes experienced commanders to become a rarity. Once a new user is in the commander seat, the game might as well announce the other team as the winners.

The evolution of games

All the cases listed above have in common that they create a bad user experience, lessen the quality of the game and fill up the forums with posts made by furious players. This is reflected in the reputation of the game and the loss of users (and again loss of money).

The solution is quite simple: User controlled user management.

Since old times when the first popular network games started popping up, we have had bad guys. The thing about being a bad guy is that there are no consequences to your actions. They might be kicked if some user decide to report them, but the problem with that is that there might be hundreds of users each day and the response time is not always great. Realizing this fact some games implemented user controlled user management though voting menus and automatic filtering and checks.

Listing the different mechanisms:

Aggressive profanity detection
- Detect profanity and keep a statistic. Kick the user when too much profanity has been detected and remember to warn first.
User kick vote
- Users can initialize a kick vote towards a single user. This is useful in cases where automatic detection fails.
Text spamming detection
- Put in a delay after 3 rapid messages and double the delay time each time this rule is violated.
Microphone spamming detection
- Record the length of time spent on the microphone.
User kick/spamming history
- If a user is constantly getting kicked from servers or has a history of rule violations, investigate the case.
Idle player detection
- When a user has not moved for 1 minute, kick him.
Game specific limitations
- Like the case of newbie commander, make sure that new players are sufficiently experienced before giving them commander status.

The bottom-line is that players and their collective attitude towards the game together with automatic “bad guy” detection is necessary to keep a game playable, we learned that though the evolution of networked games. It is more important than you might imagine and so easy to prevent.

Floating and fixed point arithmetic

2009-10-05T19:25:00.001+02:00

A user posted a question on the Farseer Physics Engine forums about fixed point math. The topic include numeral systems, implementation details and performance. A whole lot of posts have been written about it. I’m not going to provide a full introduction to fixed point math, I’m simply going to provide an abstract answer to the questions (one that apply to similar questions).

Background

Back in the good old days (before the Intel i486 CPU) all applications used fixed point arithmetic. Floating point was something new where you could get a tradeoff between space, value range and precision, but at the cost of performance.

Let us take a quick example: A fixed point number with the radix (point/dot) after the forth digit: 5186.3924, would be represented with a floating point as 51863924 with an exponent of 3:

5.1863924*10^3 = 5186.3924

Let us have a look at the up’s and down’s of floating point math.

Positive side of floating point

There are both positive and negative sides of floating point arithmetic. It is basically a tradeoff that the programmer needs to balance; choosing the lesser of two evils.

Greater range and precision

Floating point numbers have a greater range of number representations. You can’t write 0.00001234567 and 12.34567 with fixed point. The radix is fixed! You can with floating point and that is one of the main reasons we use floating point over fixed point. Let us take a look at the following example from Wikipedia:

In a decimal floating-point system with three digits, the multiplication that humans would write as

0.12 × 0.12 = 0.0144

would be expressed as

(1.2 × 10⁻¹) × (1.2 × 10⁻¹) = (1.44 × 10⁻²).

In a fixed-point system with the decimal point at the left, it would be

0.120 × 0.120 = 0.014.

A digit of the result was lost because of the inability of the digits and decimal point to 'float' relative to each other within the digit string.

Since floating point numbers are split up into 2 numbers: Significant and exponent, it makes sense that the range of floating point numbers is defined by the number of bits allocated to the significant and exponent. There are different types of floating point data types available:

Single – Single precision with 32 bits. Called single or float in C#.
- Range: ±1.5 × 10−⁴⁵ to ±3.4 × 10³⁸
- Precision: 7 digits

Double – Double precision with 64 bits. Called double in C#.
- Range ±5.0 × 10−³²⁴ to ±1.7 × 10³⁰⁸
- Precision: 15-16 digits

There are even 128 bit versions with a higher range and precision.

Negative side of floating point

Floating point numbers comes at a cost. One is space, but that is neglectable in today’s computers with the high amount of RAM and huge bandwidth. More important is accuracy and performance of the arithmetic operations associated with floating point.

Performance

As mentioned before, the i486 CPU was the first CPU to get an FPU and thus the floating point operations were no longer emulated (or run via a coprocessor). This sped up the operations by a large factor. Nearly all CPUs today have an FPU located inside of them. Graphics cards are also one big FPU – it specializes in floating point math and can process a huge amount of floating point numbers.

So what is the problem?

Well, as the forum post points out, some devices does not have a FPU and even if they do, their floating point operations can be magnitudes slower than fixed point operations. A good example is the Xbox 360 platform. It does have an FPU and it even has the AltiVec instruction set. But the software designed for the Xbox 360 (the .Net Compact Framework - NetCF for short) does not utilize those instructions. This means we have lower floating point throughput on the Xbox360.

Accuracy

Floating point numbers have a bad reputation of being inaccurate. Floating point are not able to represent numbers like π or 0.1 correctly and inaccuracies may create inconsistency in your application. Lets take an example:

If you take the sine of pi, then it should yield zero: sin(π) = 0
That is not the case with most (if not all) floating point implementations. sin(π) in C# yield the following result with double precision:

1.22460635382238^-16

Equality checks are also a cause of concern. If you check a condition like sin(π) = 0 then it will yield false even though it is mathematically true. Normally we use epsilon and check the equality up against that.

The crazy part of this is that the floating point standard is not the same on different platforms. The implementation on an Intel CPU might be different from an AMD CPU. The differences can also sometimes lie in the operation system – further fueling the inaccuracies across platforms.

The solution

There are no perfect solution. As mentioned before it is a tradeoff and sometimes floating point is the way to go. However, there are some alternatives.

Fixed point

Fixed point math is based on simple integers. You can represent the number 1.200 by the value of 1200 and a scaling factor of 100. Most fixed point libraries implement a fixed point version of integer and then use bit-shifting to scale the values.

Fixed point math has some advantages over floating point:

Same behavior on all platforms (deterministic)
Faster on platforms without FPU (and sometimes even with FPU)
Lower space usage

But as always, there is a downside too:

Complex implementations
Lower range of values
Overhead of constantly scaling values

Double precision

Double precision floating point data types are 64bit and have a higher precision than normal 32bit floating point. This is not really a solution as it simply shifts the problem to a whole other dimension. It might lower the impact of the problem, but it does not go away. Sometimes it is sufficient to switch to doubles and it is far easier to do than converting everything to fixed point math.

This solution only works on platforms with an FPU as it will run even slower than single precision floats.

2D Physics Engine Tutorial – Part 2

2009-09-25T19:06:00.001+02:00

In part 1 I explained what a physics engine does and what kind of physics engines there exists. This post will focus on the collision detection internals of physics engines.

Overview

A physics engine does two things: Collision detection and physics reaction. They work seamless together to create the illusion of things colliding and bouncing back.

Collision Detection

The collision detection part of the engine is responsible for detecting when things overlap and by how much they overlap. Most physics engines have developed a two-tier architecture where you first detect if objects are near each other using a crude representation of the object. Then it performs the collision detection on the objects itself using its real representation. It basically is setup like this:

Broad phase

The broad phase is the one responsible for detecting objects near each other. It was developed to speed up the collision detection phase by reducing the amount of collision checks needed. Imagine a simulation containing 11 balls; the engine would need to do 121 (11^2) expensive (real shape) collision checks. If a broad phase is introduced, this number of checks can be reduced to a smaller amount. Broad phase algorithms usually use AABBs to represent a crude shape of the object. It is a lot cheaper to test AABB vs. AABB than a polygon vs. polygon.

The example from before with 11 balls would in the following images only have to do 121 cheap tests and 25 (5^2) expensive checks.

With and without AABBs:

There exists a lot of algorithms to do broad phase tests:

All of them have in common that they divide the screen up into smaller parts using trees (flat or hierarchical), grid or axis-division. Have in mind that no broad phase algorithm is the “best” – it depends on the situation in which they are used.

Narrow phase

When the broad phase has detected that two objects are near each other (their crude representations intersect) the engine should create a pair (sometimes called an arbiter) that contains the two objects. The objects are then tested using the narrow phase algorithm. Unlike the broad phase, the narrow phase tests the real shapes (polygons) against each other. This is an expensive test in most cases since a polygon can be anything from 3 to n points. The narrow phase algorithm needs to find the following information:

Does a collision exist
Position
Normal
Distance

The last 3 items are vital for the collision response phase. The information is used to generate a contact; it contains the previous gathered information and can be persisted over several time steps.

Green: Normal of contact point
Red: Centroid
Black: Shortest distance to collision point

Just like the broad phase collision detection system, there are a lot of narrow phase algorithms:

Improved overview

Now that the collision detection system has been identified, the new overview looks like this:

2D Physics Engine Tutorial – Part 1

2009-09-25T15:39:00.001+02:00

In this article series the focus will be on identifying the different parts of a physics engine and then how we can implement those parts as simple as possible. There are tons of 2D and 3D engines available on the internet – this is not going to be a contestant to any of those engines, it will purely function as an educational physics engine to better grasp the concepts behind it.

What does a physics engine do

Almost all games need some way of detecting if two objects collide and respond using the proper reaction. It might be Mario standing on top of a platform or Max Payne shooting a bad guy – they both need collision detection and physics.

Wikipedia definition
A physics engine is a computer program that simulates physics models, using variables such as mass, velocity, friction, and wind resistance. It can simulate and predict effects under different conditions that would approximate what happens in real life or in a fantasy world. Its main uses are in scientific simulation and in video games.

Physics engines can be used for so much more than just fun and games:

To us it is naturally that if we toss a ball against a wall, it will hit the wall and bounce back. In the computer world all this has to be simulated.

Types of physics engines

There are two different kinds of physics engines. One of them is used for soft body (deformable) objects and the other is used for rigid body objects (hard/non-deformable)

Soft body physics

Soft body engines are used for deformable physics such as cloth, rubber, jelly or balloons. You can enlarge, rip or puncture a soft body in any way you want. There are both 3D soft body engines and 2D soft body engines. Most of them define their shapes using triangles (or particles) that can change properties (side lengths and angles) and thus deform the body that contains the triangle.

Soft body dynamics are hard to work with because of the deformations applied to a body. If a body needs to try and keep its original shape, all the deformations will have to be kept track off and slowly be resolved to gain its original shape.

Rigid body physics

Rigid body engines are used for non-deformable physics such as spacecrafts, buildings, terrain, player characters and more. They can’t be deformed in any way and only support linear (movement) and angular (rotation) motion.

Rigid body engines are a lot easier to work with compared to soft body physics. You only have to keep track of movement on the x, y and z-axis and rotation around the centroid of the object.

Play Doh (Soft) and a metal box (Rigid):

Real-time vs. High-precision

How all this is calculated depends on the type of engine used. There are generally two different types of engines:

Real-Time

Real-time engines are typically used in games and other real time applications. They are used to simulate the game environment, vehicle dynamics, player interactions and more. Real-time engines are usually more focused on performance than accuracy – when a tree falls on a vehicle, we don’t need to know where every single fiber of the tree hits the vehicle with a accuracy of 0.01 mm.

They are identified by the following characterizes:

Iterative algorithms
Low accuracy
High number of concurrent objects
Game oriented tools

High-Precision

This kind of engine is mostly used in scientific applications and animated movies. They are used to simulate weather, train collisions, explosions and space shuttle trajectory. They can’t be used for real-time applications because they are too expensive in their computations.

They are identified by the following characterizes:

Single pass algorithms
High accuracy and precision
Low number of concurrent objects
Scientific application tools

Hybrid narrow phase using convexity detection

2009-09-20T00:34:00.001+02:00

While writing Convex polygon based collision detection I came up with the idea of using a hybrid narrow phase to maximize usability and performance. It might have been thought of before and if you stumble upon this, I would like to hear your thoughts about it.

It basically consist of taking the pairs found in the broad phase and checking the convexity of the polygons before sending them down to the narrow phase. As I described in the earlier post, SAT only works on convex polygons because it uses the separating axis between two non-colliding convex polygons. This limits the users of the engine to use convex polygons only and thus resort to methods of convex decomposition to get concave polygon support.

If the polygons were checked for their convexity before being send to the narrow phase, the engine could send the pair of potentially colliding polygons to a narrow phase of its choice - depending on the composition of the pair:

Convex vs. concave – Send to concave narrow phase
Convex vs. convex – Send to convex narrow phase
Concave vs. concave – Send to concave narrow phase

The convexity check could even be done at tool-time or engine startup. Whenever the vertices of an object changes it needs to redo the convexity check.

Problems that it would solve:

Small angles

Some triangulation algorithms try to maximize the minimum angle of the triangles (like Delaunay Triangulation). But most will come up with a result that contains narrow triangle and thus it can cause tunneling problems.

Convex seems

Composing a concave polygon from several convex polygons will create a lot of seems (part where the polygons meet) and that can cause trouble for most 2D physics engines. Unrealistic collisions and hiccups can occur in the middle of a collision.

Holes

Because of the precision and accuracy of algorithms (due to iterative nature and float errors) – cases of no-intersection can happen when an intersection is expected. Imagine two narrow triangles where the narrow part are up against each other. A small gap can exist between the triangles and a ray cast in between the two triangles would go right though it. This can of course be solved by extending the edges a little.

Problems that it would create:

Memory issue

The main issue would be memory consumption. Instead of a single narrow phase algorithm you would now have a dual algorithm. Using a narrow phase collider like the Signed Distance Field can consume a lot of memory.

Expensive to change polygons

Again, if you use a narrow phase collider like the SDF you need to recalculate both the convexity check and the cached grid containing the narrow phase data for the physics object. Most games don’t change polygons on the fly, so this should not be a major issue.

Convex polygon based collision detection

2009-09-20T00:12:00.001+02:00

A lot of people have asked me: Why use a convex polygon only engine like Box2D? In this post I will provide some info on why convex polygons is the optimal polygon type to use.

What does convex mean?

Convex polygons needs to satisfy the following requirements:

All internal angles must be below 180 degrees
Every line segment between two vertices can be contained fully inside or at the edge the polygon

A non-convex polygon is called a concave polygon and it must have an internal angle measuring greater than 180 degrees. As you might have thought about yourself; concave polygons can be quite handy. Convex-only engines can’t represent a simple player polygon like Pac-Man.

Why use convex-only?

There are really only one big juicy reason: performance

Physics engines are able to take quite a few shortcuts and use cheap algorithms to determine the closest vertex, shortest distance and a lot more. An algorithm like Separating Axis Theorem and the Gilbert – Johnson – Keerthi (GJK) (pdf) algorithm both operate on convex polygons and provide fast, yet robust methods of getting collision information. Fundamentally there are two great features of convex polygons:

The existence of a separating plane between two non-colliding convex polygons
When two points on two different geometries are at a minimum, they are at a global minimum.

That might sound like gibberish for the layman. I’m not going to explain what those two characteristics involve, but suffice to say that you can cut down on the complexity of the algorithms used.

Problems with using convex-only engines

In a performance point of view there are really no problems with using convex-only algorithms. The problems that arise are mainly usability (ease of use and convenience for the users). If the user supply the engine with a concave polygon, all kinds of weird collisions will happen. A check is needed to make sure the supplied polygon is of convex nature. But that topic is reserved for another blog post.

The main approach for supporting concave polygons in a convex-only engines is described below.

Convex decomposition

This method involves the use of either triangulation algorithms or algorithms that finds a number of convex polygons from a convex polygon. The idea behind convex decomposition is to simply split a concave polygon into smaller convex polygons. This way a convex-only engine can support concave polygons. A lot of algorithms exist to do this. To name a few: Earclip, Delaunay triangulation and Seidel’s triangulation algorithm.

Here is an example of a triangulated concave polygon using a Constrained Delaunay Triangulation algorithm.

Performance tips and tricks – part 4

2009-09-03T23:40:00.001+02:00

In part 3 I explained some common manual compiler optimization tricks. This time we go back to the code itself to find places where optimizations does a difference.

Boxing and unboxing

Boxing is the process of encapsulating a value type into a reference type. Unboxing is the reverse process. They both take some time and might happen several times in your application without your knowledge. Here is some example code on boxing/unboxing:

Since int is a primitive and thus a value type, it gets boxed and stored on the heap (where reference types live, compared to stack where value types live). This makes our lifes easy, but it also comes at a performance penalty.

You can easily identify boxing and unboxing operations by their IL code names:

Boxing is called box and unboxing is called unbox in IL code. You can use Reflector to have a look at the IL code generated by your application.

Boxing is very expensive performance wise. Try to avoid encapsulating value types into reference types. Try to find other ways of doing the same, you can use generics as an example.

Exception handling

Exceptions are great for reporting problems. Many logging systems catch exceptions thrown and log them to a file. The problem is that exceptions are expensive to use and catch. In high performance applications they should not be used in performance critical parts of the code. All data should be sanitized, checked and exceptions should be thrown before the data enters the performance critical part of the code.

A few things you should think about when using exceptions:

Do not throw exceptions inside loops
Do not throw exceptions inside performance critical code
Do throw exceptions in helpers, managers and data layers and other run-once and use-multiple times code.

The last item can be a bit of a gray area since you can use helpers, managers and data layers inside performance critical code. I trust you to figure that part out yourself.

String operations

Strings can be your best friend or worst nightmare. They are easy to use and easy to manipulate. What could be wrong with using strings?

They are immutable. Memory allocations and thus garbage collections can become a problem. C# does a really great job of optimizing strings in such a way that minimum memory allocations take place. But even then there are still quite an overhead of using strings. Because they are immutable, all string operations create a new string instead of manipulating the old one. The new string take up some space (2 bytes for each character) and the whole memory copying operation also take some time. Lets take a look at some string concatenations:

Normal string

Using this code you will get the string “0123456789”. Problem with this code is that you allocate 11 strings. Yes, that is right, 11 strings:

initial allocation = 1
appending = 10
final result = 1

The allocation, the representation and writing the string to the console in C# takes up nearly 4 kb. The string operation itself takes up a couple of 100 bytes.

StringBuilder object

A better solution compared to normal strings is to this is to use the StringBuilder object. it contains a mutable (changeable) array.

The StringBuilder object allocates a lot less, but it still has an overhead. It is an object, it contains a resizable array, it has some a lot of functionality. Allocating a StringBuilder object often can actually be slower than normal strings.

Char arrays

Char arrays can be even faster. They are mutable and they contain no overhead.

It can be up to 10 times faster than a StringBuilder object (depending on how it is used) but it also has some disadvantages:

You have to know the maximum size of the string (char array is fixed size)
Can only be used in simple manipulation scenarios.

New Farseer Physics Engine based game – FreeGoo

2009-09-01T14:34:00.001+02:00

For those of you who don’t know about World Of Goo, the best advice you get today is to buy it and try it out. It is one of my favorite games, complete with a great story, nice graphics and dynamic gameplay. FreeGoo is a Farseer Physics Engine based clone of World Of Goo. Try it out.

Raycasting explained

2009-08-26T19:45:00.001+02:00

Raycasting can be an extremely useful tool in computer games. There is a lot of confusion on what raycasting really is and how it can be used. I’ll try to explain some it in simple terms and give some simple examples.

Raycasting - as the name suggests involves a ray – but what exactly is a ray?

A ray is part of a line which is finite in one direction, but infinite in the other. It can be defined by two points, the initial point, A, and one other, B.

Source: Wikipedia

In Farseer Physics Engine we define a ray as two vectors; start and end. We can for obvious reasons not have an infinite length ray, we have to have some kind of boundary where the ray stops. This means that rays essentially become lines and then we simply use those lines to test for collisions with other stuff like other lines, AABB or geometries.

Collision testing

There are 4 test cases that can be performed:

Point
Line
AABB
Geometry

The great thing about all those (except number 1) is that they can be reduced to simple line vs. line tests. An AABB is made up of 4 lines and a geometry is made of N (where N > 2) lines. With this in mind we just have to know how to test two lines against each other.

This is done simply by using a linear equation from basic algebra:

Using this equation we can create a line. m is the amount that the y-value grows or shrinks with each time x increases by 1. b is point on which the line crosses the y-axis. With this knowledge we can draw a line like this:

It has the equation: y = 2*x+1

Now that we know how to create a line, we need a second one to test against:

This line has the equation y = –1*x+1. From what we gathered earlier, b was the point where the line crosses the y-axis. Since both linear equations has a b value of 1, they must be intersecting each other there at (0, 1).

To check for intersections, we take the two equations and simply does an equality check between them and input the result (the value of x) into one of our equations:

So our intersection point is at (0,1). Exactly how this is done in code is a little more complicated. In Farseer Physics Engine we implemented line intersection like described here: Intersection Point Of Two Lines

Usage

Now we know that raycasting operates on lines, but how can this be applied to games? Here is a list of a few examples:

Collision detection
Distance calculation
Jumping
Lasers
Field of view
Lightning
Suspension
Many more…

You can use rays for collision detection and check the distance between the two objects. You can also use it for smooth jumping on to platforms and even car suspension. Another common usage is finding the field of view. The only limit is your imagination.

Ray casts are cheap, but they should not be used for everything. Some physics engines incorporate rays into their broad phase collider to speed up permanent rays. This will soon be implemented into Farseer Physics Engine too.

New game using Farseer Physics – Zombies 2.0

2009-08-22T17:34:00.001+02:00

A new game just got posted on the Farseer Physics Engine forums, this time it is a zombie survival game. You are the lone protector of a science team, but you do have the choice of 16 different base upgrades and 15 different weapons to help you out. It features real-time lightning and pure action. Check out out!

Simulators And Determinism

2009-08-22T17:21:00.001+02:00

When working with simulators, it is important to understand determinism and why we have trouble with determinism across different platform and configurations. Simulators that are iterative converge their solution over multiple iterations and can accumulate system-inherited errors and thus can become unstable over time.

Why is determinism important

Does determinism in simulation systems even matter? The short answer is yes, very important. The long answer is that simulations systems usually base their current world on the previous world. It takes one step at the time (time step) and calculate everything based on the previous step. If you shoot a projectile towards a target it, the trajectory of the projectile will travel in a certain curve. If you run the same simulation on a different platform, the projectile might end up somewhere totally different than the first simulation.

Take the following example with a projectile trajectory. They both have the same initial conditions.

Simulation on platform 1:

Simulation on platform 2:

You would expect the results to be the same on both platforms, but they are not.

What can affect determinism

There are several things that can affect the determinism of a simulation, the order of elements, the rounding of floats, the low level instructions and much more. Here is a list of some examples on what can impact determinism:

Sorting
- Stable vs. unstable sorting
Float operations
- Rounding methods
- Optimizations
Hardware instructions
- Some hardware has higher accuracy than others.

The list is by no means complete, there are hundreds of factors that can affect determinism; the list only contains those we focus on in this post.

Sorting

In Farseer Physics Engine we sort the contacts (where two shapes touch) by the amount two shapes overlap. This way we can resolve the deepest contacts first and get a more realistic simulation. We used to use Array.Sort() that is based on quick sort, but quick sort is not a stable sorting algorithm. Stable in this case just means that the order of elements are preserved if the keys that are equal are in the same order before and after sorting. If two contacts had the same amount of penetration, they might get shuffled around and the order of IDs will be out of order. We switched to an insertion sort algorithm instead and suddenly the whole simulation acted differently. Not a big problem since it would do that across all platforms, but simulations recorded from previous version of the physics simulator did not match newer versions anymore.

Floating point operations

Floats can be tricky to work with. I took the following example from this article on floating points in .net:

You would guess that the program always return true - but that is not the case. If compiled under release mode (to enable optimizations) and x86, it will return false. Even though you can represent two values exact, the result of an operation on the values might not be exact. There is a standard for floating point operations, but it allows different platforms to return different values. This means that even if two systems follow the same standard, they might return different values. You can always be sure that the same value is always returned from a float operation on the same platform.

Let us look at what happens under the hood.

The float operations are stored in a 80 bit register while the memory is only 64 bit. The value gets calculated with high precision inside the register, but gets truncated in the register. Some compilers optimize your code in such a way that the value in the register gets compared to the value in memory. Since the memory value is truncated, it is not equal to the non-truncated value. This is what happens in the C# example above. To combat this we can do some tricks to disable float optimizations (by making the float not eligible to the optimization), but the simplest thing is to check if the float is in the range of epsilon. More on this further down.

Hardware Instructions

Let us take the fused multiply-accumulate instruction as an example. This instruction can be found in IBM PowerPC or Intel Itanium processors that can compute ax±b with a single rounding instead of multiple. This increase accuracy (and performance because of the fewer rounding instructions) and thus a simulation will run with higher accuracy on the PowerPC or Intel Itanium platform compared to the PC platform.

This is just one out of many instructions. Some platforms have lower accuracy some have higher. If you develop a simulation that runs on PC, make sure to test it on other platforms if you officially support them.

What can we do about it

Now that we know some of the factors that influence the determinism of a simulation we can implement some techniques to increase the determinism.

The first thing is obvious, use stable sorting methods, it is as simple as that. Anything float related is a little more complicated. There are 3 methods of getting more accuracy:

Use doubles
Use decimal
Epsilon
Don’t use floats

Double and decimal

Using doubles simply just shift the problem. It might now be as visible as before, but it is still there. Floats have a precision of 7 digits while double have 15-16 digits. Decimal on the other hand is very accurate and modeled in such a way that no errors are involved. (They have a precision of 28-29 digits by the way). Take a look at the following example:

The code above will write false for reasons described earlier in this post. The same code using the decimal data type:

The above example will return true, just like we would expect. Performance of decimals are not as high as with floats or integers because of the added precision. But places where accuracy is paramount, it might be the only solution.

Epsilon

Epsilon is the smallest positive float value greater than zero (in .net) and can be used to check the equality between two floats, even after they have been rounded.

Using this will always make the equality check between two floats return the correct value.

Fixed point

The last thing is to simply not use floats and use integers instead. This is also called fixed point arithmetic. In fixed point math you have fixed number of digits after the radix point. It is basically an integer that you scale using some scale factor. Take the number 1.595 as an example. That is the same as 1595/1000 – so 1000 is the scale factor here. Not only can this improve accuracy, but it can also improve performance on devices without a FPU.

Conclusion

Use stable sorting methods if the order of elements are important and make sure to take great care with floats in algorithms that are sensitive to small errors. Use doubles if you simply need more precision or use fixed point math if you need exact values. Floating point values are not evil, they are a trade off between performance an accuracy, but you might need to do equality checks in places where you do float operations.

Performance tips and tricks – part 3

2009-08-20T02:18:00.001+02:00

In part 2 I gave a list of the different C# keywords that could potentially increase the performance of your code. This time we take a look at the different manual inlining techniques – it will not be like the two previous posts as this one can’t be presented in simple code snippets. The compiler is normally in charge of doing those kinds of optimizations, but sometimes it might not because of some requirements. First off, let’s get an overview of the different optimizations done by the C# compiler:

Constant folding
Constant and copy propagation
Common subexpression elimination
Code motion of loop invariants
Dead store and dead code elimination
Register allocation
Method inlining
Loop unrolling (small loops with small bodies)
More…

As you see, it is quite effective and contains the mostly used optimization techniques required by modern compilers.

Why manually optimize?

Well, the problem is that while the compiler almost always takes the right path, there are times where manual inlining is necessary. One example is when you are using an old .net version like 2.0; It will not inline methods that contain a value type parameter.

Another example is automatic properties. They will get inlined in release mode and all that, but they are considered regular methods by the compiler and thus still fall under the requirements of the compiler (see them further down).

Method inlining

The compiler has a few requirements to a method before it can be inlined:

Methods that are greater than 32 bytes of IL will not be inlined.
Virtual functions are not inlined.
Methods that have complex flow control will not be in-lined. Complex flow control is any flow control other than if/then/else; in this case, switch or while.
Methods that contain exception-handling blocks are not inlined, though methods that throw exceptions are still candidates for inlining.
If any of the method's formal arguments are structs, the method will not be inlined.

While all of them are great requirements and suffice to say that the compiler is really clever in this area (it determines inlining depending on cache size etc.) a few of those items can pose as limitations in your application. More precisely: Virtual functions, struct arguments and exception handling. I’m going to take each of them separately.

Virtual calls
The only way to get around this one is to simply not use virtual calls. If you have a way of getting rid of virtual methods, do it. Virtual calls are up to 40% slower than static or instance method calls. If you get rid of them, the compiler might also inline more methods.

Struct arguments
.Net 3.5 SP1 brought some improvements to this area and it now consider methods with struct arguments as candidates for inlining. However, if you use < .net 3.5 SP1, you will need to identify the methods yourself and inline then manually.

Exception handling
I’m not going to tell you not to do exception handling. While there are other ways of reporting errors, you might be forced to use try/catch. To get around this you need to make sure that the operation expensive methods does not contain exception handling code. Always test input once and then send it off to be calculated on.

Another thing is properties. You might have a ListCapacity property that checks if the list capacity is < 0 and throw an error if that is the case. Using that property directly in a loop can give you a performance penalty. Instead you should have a backing field (a simple variable) that contains the value and get/set from/to that instead.

Loop unrolling

As I mentioned in part 1, you should move your work outside of loops and you should not even use loops if you don’t need to. Loop unrolling is (almost) the same thing. A classic example of loop unrolling:

Before:

After:

The C# compiler only inlines small loops with small bodies. Inlining a huge loop is very inefficient since the code size would increase and thus you will get slower code execution. But intelligently unrolling a loop can greatly increase performance, so beware of what you inline and remember to profile it.

Performance tips and tricks – part 2

2009-08-19T20:33:00.001+02:00

In part 1 I presented you with some tricks on loop optimizations and constants. This time I’ll show you some simple keywords in C# that can speed up the execution of your code for the various reasons.

Sealed keyword

Marking a class as sealed makes it it unable to be used as a base class. This is primarily used to prevent other classes from deriving from it. This can unlock some run-time optimizations.

Before:

After:

Static keyword

You can use the static keyword to instantiate a copy of a class at run-time and only keep that one copy in memory. You can read more about the static keyword in the link – be careful with it, you should only use it where appropriate.

Before:

After:

Struct keyword

There are two types of allocations in C#: Stack and heap
The stack is where all the value types go: int, char, enum, structs and the like.
The heap is where all the reference types go: class, interface, string and the like.

The stack does not get garbage collected and allocations in that memory space is a lot quicker. When the data structure allow it, we should allocate our data on the stack.

Before:

After:

Ref keyword

Using ref can sometimes greatly improve performance. It copies the value type by reference instead of by value. If this sounds like gibberish to you, take a look at the following article: Parameter passing in C#

Beware that the before example does actually not change the unit data. It only changes a copy of the data. The calling class will not upgrade the unit.

Also, have in mind that this can also decrease performance. The overhead of dereferencing the value type can exceed the overhead of copying by value. Always test if you actually get more performance.

Before:

After:

Out keyword

The out keyword is almost exactly like the ref keyword. The ref keyword needs the object to be instantiated before you pass it as a parameter, the out keyword does not.

Before:

After:

Note: As you see, the responsibility of instantiating the UnitData has been shifted to the UpgradeUnit() method. Before it had to be instantiated before it was passed to the method.

Unsafe keyword

The unsafe keyword is not used very often because of its nature and a name that can scare away most developers. Not to worry, the unsafe keyword enables the use of C concepts like pointers. Pointers are not just grab and go knowledge and it can cause havoc if used incorrectly.

Remember to turn on unsafe code in the project build properties. Also remember to use the fixed keyword to pin the memory location of variables or use the stackalloc keyword to allocate memory outside of the garbage collected memory.

Before:

After:

Note how the arrow (->) is used instead of the dot (.) when accessing members.

Performance tips and tricks – part 1

2009-08-18T22:51:00.001+02:00

In this post series I will take a look at the different tips and tricks that can increase the performance of your application. You probably already know some of them and some of them are even just a bit of logical thinking. In any case, it should help you remember the different techniques. I took all these tips and tricks out of my article High Performance Game Development (The revised version – coming out soon) since they apply to almost all languages.

Move work out of loops

This one is kind of obvious, but it can be hard to identify in some cases. You simply move work from inner loops to outer loops or even out of a loop altogether. I’ve made some simple examples of this:

Before:

After:

Don’t use loops

This is much like the previous one. One important difference is that you don’t use loops at all. You will save a lot of instructions and thus you will have better performance.

Before:

After:

Use constants whenever possible

Using constants can greatly improve performance. The compiler can make better decisions about your code and make use of low level optimizations that speed up the execution of the code.

Before:

After:

Note how we can use the const keyword on the addition variable. This is only possible when the depending variables are also marked with the const keyword.

Simplify variables

Whenever you can, make sure to simplify variables to removing redundant operations. This might not always be possible and sometimes it can severely decrease the code readability. In this specific case you can maintain the readability by simply using the const keyword. The compiler will then simplify the variables for you.

Before:

After:

The famous inverse square root

2009-08-18T00:53:00.001+02:00

I’ve already mentioned before that you can approximate divisions using a division-free Newton-Raphson approximation. You can also use the Newton-Raphson method for approximating the square root and the inverse square root function.

But first, what do we actually use inverse square root and square root for? A lot really – everything that uses a normalized vector; collision responses, lightning and reflection to mention a few. It is an important part of any game and the operation has to be as fast as possible. Back in the day when computers had weaker CPUs and no specialized hardware to handle floating point operations (Today we even have specialized physics cards and specialized lightning circuits), some steps had to be taken to compute the inverse square root a million times each second as quickly as possible.

And here it is:

I could go into details on how this works, but I think it has been described sufficiently on Wikipedia's article Fast inverse square root. Suffice to say that the line with 0x5f3759df is the interesting one, and even to this day we don’t know the origin of it. Several different papers has been written to try and explain where this magic hex code came from.

I included this fast inverse square root function in the Approx.net library (C#).

Mathematical operations and micro-benchmarking

2009-08-17T00:54:00.001+02:00

You might have heard that the division operation on a modern FPU is slower than a multiplication operation. If you have not heard this before; it’s true – divisions are indeed slower. But why?

Without going into the technical details, the divide operation is an iterative algorithm and the multiplication operation is computed directly. One of the more common ways of doing divide operations on a FPU is to use a divide-free Newton-Raphson approximation to get the reciprocal of the denominator and then multiply with the numerator. More on this will come in a later post.

Let’s put it to the test.
Here we run 10.000.000 iterations where we divide 500 by 11.5

Here we multiply 500 by the multiplicative inverse (reciprocal) of 11.5

From what I described earlier our multiplication example (code example 2) should perform better than the division example. Here are the results:

Division: 00:00:00.0010787
Multiplication: 00:00:00.0010871

Something is clearly wrong. First off all, they have virtually no difference in the time it took to compute the results. Second of all, the time it took to do the operations is really small. Don’t worry, there is a perfectly good reason for this:

We used constants to represent the numbers we needed to divide and multiply. The compiler knows this and use the approximation instructions on the FPU – we also did the same operation 10.000.000 times. This leads us to the next section of this post:

Micro-benchmarking

Micro-benchmarking is where you test a single or multiple operations to see what takes the most time. In this case, all we tested was that the division and multiplication examples took the same amount of time and we simply timed the cache and not the operations themselves.

There are a bunch of examples on the internet that shows us exactly how micro-benchmarking can deceive us. In this case, the compiler simply optimizes the code and CPU cache helped us to get the results fast. To truly test the performance of the divide and multiply operators, we need to make the compiler second guess; simply remove the const keyword and rerun the code. You will see that the multiply operator is up to 10 times faster (depending on platform and compiler mode).

Conclusion

Divisions are really slower than multiplication, but the CPU uses precise approximations by either using lookup tables or iterative algorithms. It is a clever piece of hardware that always tries to speed up your the execution of your code where ever possible. When you do micro-benchmarking, make sure the compiler generates the code you actually want to test. Often the compiler even strips away your for-loop and simply run the code once. If there is no way to get around this, simply run the code once yourself and use StopWatch.ElapsedTicks as measuring tool and it will tell you of any speed differences.

New game using Farseer Physics Engine – Superspace

2009-08-14T20:23:00.001+02:00

Another game got posted on our forums. This time it is a space shooter game with cooperative, death match and racing modes. It has 36 different levels for you to play with. The game has great particle effects, nice dynamics and classic sounds.

You can view a trailer of the game on youtube: Superspace trailer

Another game using Farseer Physics Engine – Square Off

2009-08-11T20:55:00.001+02:00

A new game called Square off just got posted on the Farseer Physics Engine forums. It is created by Gnomic Studios and has entered the Dream Build Play competition.

It features great graphics, multiplayer and a huge fun-factor. Take a look at this video to see what I mean.

New game using Farseer Physics Engine - Ninjic

2009-08-11T20:48:00.001+02:00

We have about 1300 daily pageviews and 200 downloads each day over at the Farseer Physics Engine project. We also have a quite a few users posting their games for others to review and to show off how they used the engine.

A lot of the games are good, but Ninjics surpassed my expectations. The graphics is from UP Studio and the designer and a guy teamed up to create a ninja-style game.

See the video of Ninjic on youtube.

Google analytics and Blogspot

2009-08-10T18:54:00.001+02:00

I looked around for some statistics to get an idea on the amount of visitors that read my blog. I was surprised that nothing like that existed by default. Google is the owner of Blogspot and they are known for their detailed analytics of the internet and reliable site tracking, so I thought that it was a joke that Blogspot did not have a statistics module by default.

Google took the right path.

So why not include a statistics module by default? I’ll tell you why; the best sites in the world are defined by their functionality and ease of use. By not including a default statistics module and let the users choose what they like is very clever and gives your users an extremely flexible service.

I personally went with Google Analytics. There are several other services that tracks sites statistics. The choice is up to you.

The accuracy and speed of function approximations – part 3

2009-08-09T20:51:00.001+02:00

In part 2 we had a look at the accuracy of the approximated functions. In this part we will take a look at the speed of the same approximated functions.

There is no reason to use approximation unless you gain something from it. Usually the gain will be in the form of a speed improvement over the real function. Embedded devices with low memory and low frequency CPU can benefit greatly from approximation – even new computers can benefit from it. Lets test it out:

The timing depends a lot on the platform and settings. This is compiled under .Net 3.5 SP1 x64 in release mode. Timing is based on 1000000 iterations.

The results are clear – the quadratic curve equation is a lot faster than both the Taylor series and real sine function. The quadratic curve equation is also more accurate than the Taylor series.

Conclusion

If you are programming for embedded devices such as mobile phones, PDAs or barcode readers, you can gain a lot of function approximations. In this article series we tested the accuracy (true across all platforms – small but consistent variations can occur) and the speed on the PC platform. Using a quadratic curve approximation with added accuracy can give you 10 times better performance for a small sacrifice in accuracy.

You can get the code to the approximation library (written in C#) here: Approx.net

Update: I managed to improve the performance of the LowSin() function. It now runs at 3 ms on my computer.

The accuracy and speed of function approximations – part 2

2009-08-08T21:21:00.001+02:00

In part 1 we took a look at two different function approximations; Polynomials and Taylor series. We found out that Taylor series are a lot more accurate than the quadratic equation – or is it?

The quadratic equation is fine in some cases. If you want to create a swinging hammer, a wave or the movement for a platform; this approximation is fine. But we can add some extra precision to the function and get it to be even more accurate. The new function looks like this:

The first function f defines the sine approximation and the second function g adds some extra precision. The result will look like this:

We are nearly unable to distinguish the two lines from each other. And remember from part 1, it is exact in 0, π/2 and π. So using this quadratic equation is really more accurate than Taylor series – but accuracy is not everything. We will take a look at the performance in part 3.

Update: Part 3 is here

The accuracy and speed of function approximations

2009-08-08T20:53:00.001+02:00

The hard truth of function approximations is that they are not very accurate – that is why they are called approximations (duh). But just how accurate are the different approximations? Here I will take a look at the accuracy of the different sine function approximations.

First off, what exactly are we going to approximate? Let us take a look at the sine function in a graph:

The X axis goes from –π to π.

Let the approximation begin. We start out with a polynomial approximation. We simply use a quadratic equation to approximate the curve of the sine function as best as we can. I came across a post where a guy used –π, -π/2, 0, π/2,π as points of reference and derived a function from that. He came up with:

Without getting too much into the details, this quadratic equation only approximates the curve of the interval [0 ; π]. Putting this equation into a graph with the real sine function gives us this:

Blue is our sine function and red is our quadratic equation. As you can see, the quadratic function is exact in 0, π/2 and π. Now let us have a look at the good old Taylor Series approximation of sine:

Blue is our sine function and red is our Taylor series. Pretty neat huh? It is impossible to tell the difference between the two functions from the interval [0;π/2], but then it starts to deviate. Suffice to say that that we can see from our results that the Taylor series approximation is more accurate – or is it? Stay tuned for part 2.

Update: part 2 is here

That new code smell - With C# example

2009-08-08T19:59:00.002+02:00

The High Performance Game Development article is coming along fine. I wrote up some C# code that follows with the article, most of the code is examples on transcendental function approximations.

Here is a pretty example on a sine function using Taylor Series:

public static float FastSin(float x)
{
    return x - ((x * x * x) / 6) + ((x * x * x * x * x) / 120)
        - ((x * x * x * x * x * x * x) / 5040);
}

Much more to come!

Who owns the article?

2009-08-08T19:14:00.001+02:00

I've been writing an article called High Performance Game Development for quite some while now, and since it (in my opinion) contains a culmination of high quality knowledge about the complicated area of performance, I would like to make it available to the masses. I went looking for a place to post the article, but was surprised to see that most sites simply takes away your rights to the content of the article. Their disclaimer text often goes like this:

By submitting your article to xxxxxxxx, you are granting to us a permanent, non-exclusive license to use the article in any format we deem appropriate, with the assurance that you will always be given full credit for your work

I was also surprised to see that all sites want you to write the article, then upload it to them. You have no way of editing the article by yourself. You will have to contact the site owners to get your article updated. I can understand why they do this - it must be because of vandalism and inappropriate words and so on.
By why should I write an article, give it to them and essentially give them the rights to do whatever they want with the article?

No way...

That is why I decided to publish the article myself. I don't know where to host it yet, but hopefully it will get noticed and be passed around forums.

The state of TTS systems

2009-08-07T19:50:00.000+02:00

I have this semi-blind friend that I used to work together with. He uses an application called Zoomtext for reading online news, install applications and so on. The only problem is that the program is poor in quality - always lagging around the screen, crashing and is really heavy to dance with. Being geek by nature I tried to find alternatives and stumbled upon some online TTS (Text-To-Speech) system with some really good quality voices. One of them was iSpeech. It is a webservice based application where you can upload your content for free. But free does not necessarily mean easy, here is what I think about it:

1. It is online and thus you can only past it some text and then get the speech results. There are no parsing of documents on the fly so you can read while you listen. This can be solved (sort of), read on...

2. Building an application that works together with the parsing engine of Zoomtext seems to be pretty easy. Problem is that each upload of text portion will contain an advertisement for the service - You can of course get around that paying a large amount of money, but paying $99 each month (for 600 minutes of audio) for only the voice of a TTS system is not really an option.

So how come handicapped people have to live without the high quality voice proviced by iSpeech (or odiogo) in a text parser engine like the one from Zoomtext? We are way behind on the field of assistance applications in my opinion and someone needs to put those two together.

New blog

2009-08-06T19:51:00.000+02:00

I’ve been thinking about getting a blog, and now it finally happened. Stay tuned…

Whatever Crossed My Mind

Introduction To WP7 Development and Farseer Slides

Windows Phone 7 Isolated Storage Helper

How To Make Codeplex Remember Your Password

XNA and Farseer Physics Engine 3.3 Presentation at Nokia

XNA 4.0 Introduction

Benchmarking Box2D Based Physics Engines

Test system

Box2D Settings

Results

Conclusion

Optimizing Performance On The Xbox 360 - Part 2

Structures… again.

Reuse those objects

Boxing

Further reading

Optimizing Performance On The Xbox 360 - Part 1

Algorithms and datastructure complexity

Why is it slow?

Optimizing the code

Farseer Physics Engine 3.1 released

Tunneling explained

What can be done about it

Value Types and Reference Types Explained

The ref keyword

Blank Visual Studio 2010 Team Explorer Window

Farseer Physics Engine 3.0 Has Been Released!

Synchronizing Google Calendar with iPhone and Outlook

Make Team Explorer Remember Login Credentials

Broad And Narrow Phase Collision Detection Systems

Broad Phase Collision Detection

Narrow Phase Collision Detection

The Big O notation – Summary

The Ramer-Douglas-Peucker Polygon Simplification Algorithm

Physics engine series

Performance tips and tricks series

My Xbox 360 nightmares

Facebook style auto-complete textbox in ASP.net

ASP.net implementation

Pseudo orientation in Farseer Physics Engine

2D Physics Engine Tutorial – Part 3

Movement

Velocity

Force

Acceleration

Integrator

Euler’s method

Overview

User managed games and automatic server checks

User management

The microphone guy

The message spammer guy

The foul mouth guy

The idle guy

The evolution of games

Floating and fixed point arithmetic

Background

Positive side of floating point

Greater range and precision

Negative side of floating point

Performance

Accuracy

The solution

Fixed point

Double precision

2D Physics Engine Tutorial – Part 2

Overview

Collision Detection

Broad phase

Narrow phase

Improved overview

2D Physics Engine Tutorial – Part 1

What does a physics engine do

Types of physics engines

Soft body physics

Rigid body physics

Real-time vs. High-precision

Real-Time

High-Precision

Hybrid narrow phase using convexity detection