Saturday, July 31, 2010

Make Team Explorer Remember Login Credentials

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.

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

Now the Team Explorer client should remember your password.

Saturday, July 3, 2010

Broad And Narrow Phase Collision Detection Systems

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:

NoPair

Close and needs to be further tested for collision:

Pair

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.

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

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.

Growth

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.