Just Code it!
Header

The base of all the Maths that I will use is the Vector for sure (well, the number itself… but I have no intention to start from there :P).
I assume that you are somehow familiar with the concept of vector and its basic operations (sum, vector/dot product, etc).

The vector that I need for this project is a 3D vector. Sometime it is more convenient to represent 3D vectors using 4 components (with the last one “w” set to 1) to simplify some transformation. I will start using a 3-components vector for now.

We could use directly the Vector3 class (or Vector4) in XNA for this, but I will write my own just to have more control over it and to play directly with the operations/methods that I will expose. It is just a chance to see what’s behind and we can decide to remove it in the future if we don’t need it anymore.
The nice thing about writing your own basic classes is that they will be very portable and what you will have to provide will be just the wiring with the current library (OpenGL/DirectX/XNA) Vector/Matrix classes. The rest of your code will (almost) work without any change (well… you will have to change the rendering as well).

Declaration
The basic starting point for the Vector3 class is just a set of 3 properties that stores the coordinates we are interested in.
Without wasting too much time, I will just declare the three properties as public fields in my Vector3 class.
Those are the basic declaration in C++, C# and Java:
class Vector3 {
public:
float x;
float y;
float z;
}

public class Vector3
{
public float x;
public float y;
public float z;
}

public class Vector3
{
public float x;
public float y;
public float z;
}

Easy :).

Dot Product
Aside from the 3 fields (and properties) used to represent the 3 coordinates (x, y, z), there are some more useful methods to implement.
A set of basic operations (amongst the obvious one such as assignment or equality operator) are:

  • Dot/Vector product
  • Scale
  • Magnitude (Normal/Squared)
  • Normalisation

The implementation of the dot product is straightforward.
In C#, assuming to implement it as an overloading of the multiplication operator (“operator *”), the code will be something like this:

public static float operator *(Vector3 _vectorA, Vector3 _vectorB)
{
return _vectorA.x * _vectorB.x +
_vectorA.y * _vectorB.y +
_vectorA.z * _vectorB.z;
}

Just as an example, in C++ this could be implemented in a slightly different way when declaring it as a member function:

float operator *(const Vector3 &_vector) const
{
return x*_vector.x + y*_vector.y + z*_vector.z;
}

And in Java it is more fun… I am sarcastic here. I have to implement it in another completely different way (no operator overloading):

public float GetDotProduct(Vector3 _vector)
{
return x*_vector.x + y*_vector.y + z*_vector.z;
}

It is quite interesting to notice how the overloading differs in C# and C++ and especially (missing :P) in Java.
If for some reason you like the Java version, then you can easily apply this in the other two languages as well… if you want to achieve the opposite instead (overloading in Java) then… good luck :).

I have to admit that the Dot Product is not really exciting. So let’s look at the Cross Product for a more (even if not much more) interesting example.

Cross Product
The Cross Product, differently from the previous one, is an operation between two vectors that returns another Vector. You can find the formal definition and all several properties explanation from the long series of resources on the book-shelves and websites (wiki).
A common way to write it is: v = a x b, where the “x” represent the cross product operation.
What is important to know at the moment is that when implementing the cross product you need to pay immediately attention at least to a couple of really important details:

  • You need to take into account the handedness of the coordinate system.
  • It is not a commutative operation.

(Coordinate Systems)
To see the difference due to the handedness of the coordinate system you can simply use the left-hand rule or right-hand rule that matches the handedness of your coordinate system to easily visualize how the resulting vectors differ.
The left/right-hand rules are quite easy to apply. Just use your left/right hand (or one of your friends :P), shape it like a fist and stick out the first three fingers (thumb pointing up, index pointing forward and yes, the third and preferred one, perpendicular to the other two). Now, keeping the three fingers (initially) at 90 degrees each one with the other, just rotate your left/right hand so that your thumb matches the direction of you first vector (“a”). Then rotate your hand around that axis (represented by the thumb) so that your index finger ends up on the same plane identified by the second vector (“b”) and the thumb (still fixed on “a”). If you see that you should spread the thumb and the index more than 180 degrees in order to match your index with the vector “b”, than simply flip your hand around the thumb (rotate it of 180 degrees around it) and you will see that (assuming that you can stretch your fingers as much as 180 degrees) the second vector can always be matched by your index finger now.
After all this stretching exercise you will find that the third loved middle-finger will point along the direction of the vector that results from the cross product.
Now you can relax you muscles, the left/right-hand rule will not tell you more than this… you cannot shrink or elongate your fingers to find out the length of such a vector :P… I hope.

Back to the Cross Product
The fact that it is not a commutative operation should now be clear. Just try to apply the same hand rule assuming that “a” and “b” are switched. Not only you will find that the direction is not the same, but you will find out that is exactly the opposite of the previous one! It is in fact true that the cross product is an anti-commutative operation!

Enough said about this… well, one thing is missing. The length of the resultant vector.
For this you can just stick to the definition I will give, or, if you are interested or curious, refer to a math book (or Wikipedia if you prefer). I will not explain where this came from because it is not relevant in this context and it would include some concepts related to matrices that I didn’t explain yet.
The direct and fast result is this:
The result of “v = a x b” is a vector with the components defined as:

  • x = ay * bz – az * by
  • y = az * bx – ax * bz
  • z = ax * by – ay * bx

Because the result is a vector we can use more fantasy when writing our code :). Those are some example of useful methods to apply this operation in the different languages.
Notice that if the two vectors are parallel the result will be 0!

Looking at the C++ example first we could decide to overload the “operator %” (if you like it) and even the “operator %=”, the compound assignment operators (well you will not like this if you didn’t like the previous of course). Here it is how it could look:

Vector3 operator %(const Vector3 &_vector) const
{
return Vector3(y * _vector.z - z * _vector.y,
z * _vector.x - x * _vector.z,
x * _vector.y - y * _vector.x);
}

void operator %=(const Vector3 &_vector)
{
*this = VectorProduct(_vector);
}

of course this is a quite lazy version of the “opertor %=”… a more optimised one should be:

void operator %=(const Vector3 &_vector)
{
float tx = y * _vector.z - z * _vector.y;
float ty = z * _vector.x - x * _vector.z;
float tz = x * _vector.y - y * _vector.x;
x = tx; y = ty; z = tz;
}

If you want, there is still an improvement to make here. If you try to write the following line:

vectorA = vectorB %= vectorC;

You will notice that the compiler is not really happy… This is because our compound “operator %=” doesn’t return anything. If you want to be able to do such a thing, then you should consider modifying the code for this operator in something like this:

Vector3& operator %=(const Vector3 &_vector)
{
float tx = y * _vector.z - z * _vector.y;
float ty = z * _vector.x - x * _vector.z;
float tz = x * _vector.y - y * _vector.x;
x = tx; y = ty; z = tz;
return *this;
}

As a last note worth considering is to define all those as inline functions in C++.

The C# version is:

public static Vector3 operator %(Vector3 _vectorA, Vector3 _vectorB)
{
return new Vector3(_vectorA.y * _vectorB.z - _vectorA.z * _vectorB.y,
_vectorA.z * _vectorB.x - _vectorA.x * _vectorB.z,
_vectorA.x * _vectorB.y - _vectorA.y * _vectorB.x);
}

And in Java:

public Vector3 GetVectorProduct(Vector3 _vector)
{
return new Vector3(y * _vector.z - z * _vector.y,
z * _vector.x - x * _vector.z,
x * _vector.y - y * _vector.x);
}

Other Operations
Enough for Vector3. All the other operation are quite straightforward to implement as well, so it is just a question of describing their functionality:

  • Add/Sum: basic operations to add and subtract to vectors.
  • Copy/Clone: return a copy of the vector object (if we are using mutable objects).
  • Compare: check if two vectors represent the “same” vector in space
  • Scale: multiplies a vector by a number.
  • Magnitude (Normal/Squared): returns the length of the vector. The squared length is useful in some cases and it is nice to have if we can avoid to waste computational time computing a square root that we don’t really need.
  • Normalisation: scales the vector in order to obtain a unit length vector.
  • More as we need them :).

Next thing will be more challenging for sure: The Matrix!

Physics Engine – Introduction

March 12th, 2011 | Posted by riccardotramma in .NET | C++ | CSharp | Java | Physics - (1 Comments)

I decided to document here my personal project: “Building a small Physics Engine” perfectly usable to build small/medium games.

My intention is to bring this series of posts as far as possible. During this journey anyway, although good code and clean architecture is always important and always a basic principle for the code I am going to write, I cannot assure that I will always bring this to the extreme for this project and I will probably take some short-cuts and some lazy choice for several reasons:

  • This is a personal project
  • I want just to have fun with it
  • I don’t want to digress too much from the main argument
  • The aim is to quickly (and happily) build a Physics Engine after all
  • I don’t want to waste too much time refining something that I don’t really need (for now)

I will not explain everything in detail (there are books and books on the matter and it is not my intention to write a new one) and what I will state will not be necessarily complete and mathematically impeccable (some assumptions will be always along the way to simplify matters), but (hopefully) it will work! :)
I will assume a basic knowledge of some concepts, especially basic Maths/Physics concepts and operations. If something should not be clear just google it or ask it if you cannot find the answer you are looking for, I’ll try to answer asap.

We have to consider that there are several (sometime drastically different!) ways to obtain the same result or to simulate/model a concept. Some are better than others, sometime it is only or a question of personal preferences or can be that the results are only better in the specific context where we are using our (mathematical) model.
That said I will mostly use my personal preferences for techniques and methods, while I will use some less-efficient/precise ways when I reckon that I can save some developing time/resources and the result is still pretty acceptable. This is still a demo/personal-fun project and more fine-grained/polished/robust/efficient code can be added later on if anyone is interested. I will probably mention anyway some different techniques that I will maybe discuss more in detail even giving some examples if I will consider them worthwhile at the moment of mentioning them.

What about the source code?
Well, I will present code mainly in C# (I assume), but I do not exclude that I will show some concepts using C++ or even Java… just for fun and to have more examples :)… the important thing are the concepts after all… and the code, yes, the code!
I will give examples using DirectX, XNA or OpenGL and I will use (on my machine) Visual Studio (2005/2008/2010) or Eclipse… and yes, even the operating system will not be unique! I will use Windows or Mac (well… even Linux maybe… no ok, not for now, but it should not be difficult to implement with the existing material)!
This should give a broad view on how achieve things in different systems, using different libraries with different languages… what else? :)

So, let’s start from the basic, Math! Yes, Math is always the base :)… well, Geometry in this case.

Comment or Leave a Message

Please Comment or Leave a Message if this is what you are looking for or if you have any question/comment/suggestion/request.

RC4 is the most widely used symmetric cypher algorithm, especially given its performances.

The Key is generally between 5 and 16 bytes, equivalent to 40-128 bits.

Initialisation

To initialise the algorithm it is used a permutation of all 256 possible byte values using the Key-Scheduled algorithm.

The procedure is quite simple. Assuming that we have our key stored in an array that we can access (let’s call this array simply “key”), we have to:

  • Initialise an array with the identity permutation of the 256 values (let’s name this array simply as “buffer” for now)
  • Loop through each array element (let’s assume that “i” is the index of the array for the element currently processed) in this way:
    • Use another index “j” (initialised to 0) and add to this index the element in the i-th position (buffer[i])
    • Add to the result the content of the key buffer in the i-th mod key-length position (or “i % keylength” if you prefer). This essentially means the value in: key[i % keylength]
    • Ensure that we never end outside our buffer boundaries. Take the value of j % 256 (or j & 255 if it sounds cooler to you)
    • Swap buffer[i] with buffer[j]

The code sample shows this algorithm in action:

Encryption

Once initialised the algorithm using our key we are ready to encode the message.

This algorithm could seem a little bit more convoluted, but it is actually quite simple.
Let’s assume that the message to protect is stored in an array called “message”. The steps are those:

  • Reset i and j to 0
  • For each byte of the message that we want to encode do the following:
    • Increment i and keep it in our buffer boundaries: i = (i + 1) % 256
    • Add buffer[i] to j keeping the result in the array as well: j = (j + buffer[i]) % 256
    • Swap buffer[i] with buffer[j]
    • Add the values in buffer[i] and buffer[j], keep the result in the buffer array range: (buffer[i]+buffer[j]) % 256
    • Use it (let’s name it “encryptionByteIndex”) as an index in buffer itself: encryptionByte = buffer[encryptionByteIndex]
    • Use the value of the buffer in this position to xor the current byte of the message: encryptedMessageByte = message[currentIndex] ^ encryptionByte
    • Store this in an encryptedMessage buffer: encryptedMessage[currentIndex] = encryptedMessageByte

At the end of this algorithm the message will be encrypted in the buffer encryptedMessageBuffer. In order to decrypt it we can follow the same procedure using this buffer as our input buffer.

This is one code sample (in this code I will use only one buffer for the message and its encryption):

If you want to see where this could be useful have a look at my other blog entry here: Crypt in C++ and Decrypt in C# (and C++).

Comment or Leave a Message

Please Comment or Leave a Message if this is what you are looking for or if you have any question/comment/suggestion/request.


So, now you (actually Me) want to encode and crypt something in C++ and then (maybe after a network message), decrypt and decode this info in C#.

Let me explain exactly what I mean with encode/decode, crypt/decrypt.

We use the user’s two public/private key pairs to crypt/decrypt a session key that we will use to encode/decode a message. If all this make sense to you then let’s start.

First of all, let me answer one natural question: “Why all this?”

The reason of the double-step procedure to encode a message is due to two major reason:

  • crypt/decrypt (or signing and verifying) with an algorithm for public-key cryptography such as RSA (the one that I am using), uses a key pair, where one key is used to crypt some data, and the other (asymmetric) key is used to decrypt it. The things can actually work in both ways and in one case we will talk about signing and verifying.
    The protection here is very strong but the cost is resources, especially time. The algorithm is slow compared to others and for this it is not suitable for protecting a large amount of data. Another reason seems to be security itself, where many blocks encrypted with the same RSA key can help an attacker to reach his intent.
  • encode/decode instead is achieved using a symmetric key algorithm that can be very fast and if it is a stream cipher, it works great with streaming data :). I will use RC4 for this.

The Scenario

Two PC, connected through internet, where one behave as a server and the other is the client.

We assume that the server contains (well protected) its private and public keys that it will use to sign and decrypt some data that will go to or will come from the client.
For the client we assume that he knows the server’s public key and that he will use this to verify and crypt the data that he will receive from or that he will send to the server.

More about the Key Pair and Session Key

With Windows you can store/retrieve user keys (key pair) using the Crypto API. With it you can manage machine or user key in a quite simple way.
On the server we will use this API (in C++) to generate/retrieve (and then store) our machine key pair and we will tell the client our public key.

On the client will create a session key (C++) that will be used to encode a message with RC4.
Because the client knows the server public key, he will then use this to encrypt the session key.
Once this is done, the client will proceed to pack the two things together (encrypted session key plus the message) and send the packet to the server.

The Server at this point will save the message in a file, because we want to have more fun later on.

In fact, to make things more interesting then we will create a .NET (C#) project that will retrieve the same key pair previously stored, reads the file, imports the session key and decodes the message. All this in pure .NET.

Does it not seem fun?

To simplify stuff I will not use any network code and I will assume that the data are passed somehow between client and server. This can be network, file, or whatever (DB, mind power,…).
The only storage that I will use will be a file (the encrypted file) to allow a simple code in C# to open it and read and decrypt its content.
To simplify the code and shrink it to the fundamental parts I will provide code snippets that are mostly implemented as simple methods (C style) and I will assume the presence of some globally scoped variable (that should really be class scoped variable in a real environment). This will hopefully simplify the understanding of the concepts without losing the focus tracking the objects relationships.

Let’s start then.

Initial Server Code (C++)

In C++ we can easily use the Crypto API to do all we can (reasonably) think about when we want to protect our data.
This is available including “wincrypt.h” in your code.
The first thing to do is acquire the context where our secret keys are stored. This can be easily done with a code such as:

After this we can retrieve our exchange keys from the container. If the keys doesn’t exist I will create a brand new pair. This code does exactly this:

Happy with the result the next thing to do is to export our public key and give this to our client… or everyone… after all is a public key!
In my sample code I will use a memory buffer. The important thing here is that we are not here to cheat and this buffer will be the only thing that we will give to the client code pretending that it is a completely separate application. The export looks like this:

If everything is fine until now we can temporarily leave our server and switch to our client code.

Client Code (C++)

Because we are still working with Crypto API, the pattern is similar and so the first thing we have to do is acquire the container context in the same way we already did for the server.
The only difference is that we will use a different container to continue simulating a separate environment:

We can then import immediately the server public key:

The initial “handshaking” is completed now! The server is configured with his Key Pair and the client has received the the public part of this pair.

The next move is in client’s hand now. It has the freedom to choose a session key that will be used to encode a secret message.
For this task I am simply generating a brand new session key, especially generated for the algorithm that I will use to encode the message:

With this key I can finally encode my message!

Cool! The message is now protected… well, almost. In order to complete the transmission of the encrypted message, back to the server, we still need to take care of a few more details.
The first one is related to the protection of the session key itself. The server needs it in order to decode the message, but for sure we cannot send it as it is otherwise all this messing around with keys would be just a waste of time (human and cpu).
As already mentioned (and I hope obvious at this point) we will send our session key encrypted with the server public key. The server, and only the server, will then be able to decrypt it.

Enough chatting, let’s go to encrypt the session key then:

In my sample scenario I will simulate the transmission of the encrypted message using a simple file where I will write all the server needs to successfully decrypt the message.

My main focus here is to write a C# server that will be able to do this.
Anyway, just to complete the circle in the C++ world, I will add few more lines that will show how read and decrypt the same message in C++ as well, although I will not follow the same path and I will just continue to use memory buffers, just to avoid to add more details that are not relevant for what I have in mind now. If there is the need I will write another side article for it.

This said, let’s go back to our server (C++).

More Server Code (C++)

Assuming the message as received together with the encrypted key the first thing to do is decrypt the key of course:

As a result we will have another key object that can be used (at last!) to decrypt the message:

Job done! (in C++).

The last (really) thing to do is to create the file that will be used by the C# server.
I will use a single file where I will store both the encrypted key and the encoded message. To keep things a little bit more interesting (and realistic) I will write few bytes at the start of the file to communicate the size of the key.
Because we already have all we need, we can simply create a new file and write this info as described:

If you want to do some cleanup (and you should), remember to release the keys and the context when we don’t need them anymore.
This can be done easily in this way (this assumes that the keys are null if not initialised):

We are ready to switch to C#!

Server Code C#

The server here has to do basically the same things that we already done in C++, but in a slightly different way. In order to retrieve the Key Pair (I am not considering the creation of it in this context) we can use an RSACryptoServiceProvider object specifically configured (with a CspParameters object) to access the same server container we used in the previous app. You can find those classes in System.Security.Cryptography.
I will configure it to use the same RSA algorithm and forcing it to retrieve existing keys without attempting to create a new pair.

This is how we can do it:

We need something to decrypt now. I will use the file that has been created in C++ reading all its content in specific objects:

Once identified the encrypted session key we need to use the RSA service provider to decrypt it.
The only awkward things here is that the .NET encryption algorithm swaps the bytes after encryption (and before decryption) and we will have to take care of this directly, because this key was encrypted by the Crypto API in C++. Another thing to consider is that the encrypted blob doesn’t simply contain the encrypted key but some extra informations about the version, the algorithm to use with that key and the algorithm used to encrypt the key itself. I will not go into any detail for this here and I will instead jump in the session blob, straight to where the encrypted key is stored and use it (we already know what kind of key we generated for this toy app).
The encryption is then as simple as doing:

If everything is correct we will not receive any exception and the original session key is in our hands.

Let’s just use then to decrypt the message… well… no unfortunately.

In .NET there is no implementation of the RC4 algorithm that we used to encode the message.
Although annoying, this is not a big issue because its implementation is not so complex and can be easily hand-crafted.

I will not cover this algorithm in this post (but I will do soon in another one. Update: the post is available here: RC4 Cypher Algorithm in C#) and I will instead assume that you have access to a class/method that takes care of the algorithm details, providing a simple method to decode a message with a specific provided key.
If this is true we can then simply complete the task in this way:

Display the decoded message and jump of joy :).

Final Notes

Wait a second… nice, but… our keys? What if I want to cleanup the keys I generate with this sample code?
Correct. It would be nice to do some housekeeping when we are done with this.
In C++ we can remove out keys from our test container very easily. Sometime it is so easy that risks to be dangerous, but we know what we are doing now :).

The same thing can be done as easily as this in C# (actually it is even easier than C++):

If you try to run the C# server code again after removing the keys you will obtain a CryptographicException “Keyset does not exist” (as expected).
This will give you the knowledge that you correctly did your house-keeping :).