segunda-feira, 10 de março de 2014

Why would we like dot product? Part 2

Hello. I've been busy sorting a few things in life, but sorry for the delay for this post. Here I will continue my babbling about dot product. In part one of this series, I talked superficially about dot product, how it can be calculated and finally that we are more interested in the fact that it returns the cosine between two vectors than anything else. We are also interested in the fact that the dot product can be calculated by means of multiplications and additions, something that the computer is very fast at.

One curious fact is that when we are not used to apply math in our projects, it can be quite a challenge to think what can be applied and how. Then there is a big surprise when we finally get to use it - we start seeing more and more ways to apply it somewhere for interesting results. In this part (and maybe the next one), I will give a few simple examples on how we can use dot product to solve problems that would otherwise be hard, confusing or simply plain annoying (arc-tangents ugh).

Finally, the codes posted here are pseudo-codes and are not likely to compile without a bit of work on them. Also, I'll use codes in C# with Unity3d, since I believe they are easy to understand (even if you don't use both) and its the combination that I'm currently using. Last thing, I'm using 3d vectors, but the techniques are the same for 2d vectors, too.

View Cone of Objects

The first time I saw code of dot product being used in the practical world was nothing more than checking if a coordinate was inside or outside of the view cone of another coordinate. Let us suppose a 3d space shooter game, where the player has this very special weapon that locks on all targets within a distance and angle from the player's aim. Yeah, pretty much like a cone. After charged, all locked enemies are blown to cosmic dust.

What we want is a pretty simple way to check if an enemy can be locked on or not. Of course you can use a render filter, check for coded color pixels and do a color picking of every valid target. This is neat and also avoid the problem of targets occluded by asteroids and debris things. But lets do the simpler situation where there are only the player and the enemies around. With simple occlusion, you can use raycasting to validate if a target can be seen or not, but that's not our objective here.

First of all, we will need a bit of information of the context to be able to check if the enemies are inside the player's view cone:

  • Vector3 playerDir: the direction of the player's aim center. We want this vector to be normalized.
  • Vector3 playerPos: the current position of the player. We need this to create a few new vectors.
  • Vector3 enemyPos: the position of the enemy being checked.
  • float viewConeAngleCosine: the cosine of the view cone opening angle.

That's all we need, really. The algorithm is pretty simple, making it fast enough for most simple cases. Since we want to check if the enemy is inside the player's view cone, we need a way to calculate the 'angle' of the player to the enemy. By 'angle' I mean the direction that the player would need to be looking so that the enemy would be dead center on his screen. This can be calculated very easily as long as our 'angle' can stay as a vector. If you're a newcomer to vectors in programming, any angle can be represented as a normalized vector, instead of messy numbers of degrees or radians. Even though rotating these vectors is not the most intuitive of the maths, they are really helpful when doing many kinds of calculations where rotation is not pushing its nose into our problem.

Vector3 playerToEnemyDir = enemyPos - playerPos;
playerToEnemyDir.Normalize(); // We want to use this vector normalized

Yes, its a simple subtraction, and then we normalize the vector. Be careful with the order of the subtraction, though. If you subtract the enemy's position from the player's position instead, you would have the direction of the enemy to the player, or the direction where the player turn away from the enemy.

Now we have two direction vectors: playerDir and playerToEnemyDir. Since both are normalized, if we calculate the dot product between them, we will get the cosine of the smallest angle possible from one to another. Even though we can't compare this directly with the view cone angle, we can compare with another cosine. So we compare with the cosine of the view cone angle. Lets suppose a few values and their results:

We filter a enemy when the viewConeAngleCosine value is:

  • 1: the enemy must be straight ahead of the player, right at the perfect center of the screen. Near impossible to mathematically be true.
  • 0: any enemy that diverges up to 90 degrees (or PI * 0.5 if you are one of those who likes radians) from the player's direction.
  • -1: any enemy that diverges up to 180 degrees (or PI) from the player's direction. You can also read this as "all enemies".
  • 0.5: any enemy that diverges up to 60 degrees (or roughly PI * 0.33) from the player's direction.

The way to compare the cosines is:

float dotValue = Vector3.Dot(playerDir, playerToEnemyDir);
if(dotValue > viewConeAngleCosine) {

That's it. That's all we need to calculate if a enemy is inside the player's cone view. The locking on enemies and exploding stuff is not exactly the aim of this post so I wont go any further.

Pierce or Deflect

Another easy use of the dot product is when you want to use information about an incoming angle. Lets suppose now a war game with tanks. A really solid armor protects a large but small-in-height metal box that holds at least one strong cannon on its head. As you probably know, tanks used to be almost a metal cube on wheels and evolved to something like a squeezed hexagonal prism. One of the reasons for this is deflection.

When a bullet hits the armor, it's angle will be an important factor whether the bullet will pierce or be deflected. That being said, a bullet coming from a straight 90 degrees from the armor is the one most likely to pierce. Something like Javelins. So, for a said bullet against a specific tank armor, we could make a diagram like this:

We will need two vectors to represent this situation. One is the vector that represents the Normal vector of the surface where the bullet will hit. The other vector represents the direction of the bullet when it hits the armor surface. The closer the angle between the two vectors is to 0 degrees, more likely is the bullet to pierce. In our diagram, if the angle is inside the "piercing area", it will pierce, or deflect otherwise.

In this calculation, we will need, then:

  • Vector3 surfaceNormal: vector that represents the normal of the surface where the bullet hits the armour. We want this to be normalized, and be sure that it points outwards the tank.
  • Vector3 inverseBulletDir: the inverse of the incoming bullet's direction (multiply the direction with -1 to obtain this). We could use the bullet direction itself, and compare how close the angle of it to the surfaceNormal is to 180 degrees. But I like it more to inverse the bullet direction and see how close the angle will be to 0 degrees.
  • Vector3 piercingCosine: the cosine of the maximum angle that allows piercing of the armor. You already know why we are using the cosine and not the angle itself, right?
The math is the same as the space example...

float dotValue = Vector3.Dot(inverseBulletDir, surfaceNormal);
if(dotValue > piercingCosine) {
} else {

That's it. Again. Really. Ok, to be honest, the deflection calculation is not so trivial, but most math packages with 3d vectors do these for you. As a final bonus, lets say you want to make a damage modifier. If the bullet hits with a near deflecting angle, but pierces, you want the damage done to the tank to be near zero. If the bullet hits perfectly straight the armor (dot product is 1), you want maximum damage. In between these two angles, you want a somewhat proportional damage. For this, you can use the two cosines (piercing and incoming bullet) to do a lerp (linear interpolation) to calculate this damage variation. This is left as a training exercise.

Nenhum comentário:

Postar um comentário