quinta-feira, 5 de dezembro de 2013

Why would we like dot product? Part 1.

Hello there! My first series of posts will be about math; or, to be clearer, about dot product. Since I've started developing games, every once in a while I would need to solve a spatial problem. For my unhappiness, the solution usually involved math. As many other programmers in the world, I'm not really fond of calculations using angles, trigonometry, vectors, matrices and so on – however this is a knowledge that will more and more bind you down whenever you try to make something cool. Here, I will assume that you already understand the basic of vectors. Math vectors. Yes, we will dive into boring math a little bit.

So, where is a good starting point? The dot product. The dot product is composed of simple calculations using two vectors of the same dimension. Let's say that we have two vectors, A = [a0, a1, ... , an] and B = [b0, b1, ... , bn]. The dot product is defined as:

$$\begin{equation}A\cdot B = \sum^n_{i = 0} a_ib_i = a_0b_0 + a_1b_1 + ... + a_nb_n \end{equation}$$
The dot product is nothing more than the sum of the multiplications of the elements that share the same index in each vector, and thus we are happy with it. Computers are really good with sums and multiplications - good enough to do them a lot faster than even other simple calculations such as divisions. We don't want to jump into premature optimization here, but I think that this is a really useful fact to know (after all, in a few months you might be doing math on thousands of vectors that need to finish in a really short time window, or even programming your own graphics shader). But still, we don't have any clue on what or why use dot product. Before thinking on that, we need to know two small facts:

$$\begin{equation} A \cdot B = B \cdot A \end{equation}$$
The dot product has the commutative property. This is a mathematical way to say that you don't need to go through the burden of carefully ordering your vectors to reach the correct solution. Of course dot product has other interesting properties, but they I won't be listing them in this post, as we wont use them right now. What we need to know best is the following:

$$\begin{equation} A \cdot B = |A| |B| cos \theta \end{equation}$$
Given that we have the means to calculate the length of the A and B vectors - and usually we DO - and we know the angle $\theta$ between both, we can also calculate the dot product. What is interesting in this fact is that now we have two ways of calculating the dot product of two vectors. And better yet, one of the equations has a cosine!

If you look at it, assuming we know both vectors A and B, we can calculate their dot product. Since we can calculate the length of a  vectors we know the vector, this means we just have found a way to magically discover the cosine of the angle $\theta$ between them!

$$\begin{equation} cos \theta = \cfrac{A \cdot B}{|A| |B|}\end{equation}$$
Calculating this cosine is what will make the dot product so useful. The cosine. For practical programming, sometimes we won't care about the angle $\theta$ itself - for that, we could simply use a math function called atan2 that exists for your programming language of choice. One last note, though. If we normalize the vectors, their length will become 1, so the equation will be simplified:

$$\begin{equation} cos \theta =A \cdot B \end{equation}$$
By normalizing both vectors, calculating the cosine between two vectors became only sums of multiplications.

In this post, I just talked a bit about the math on dot products. There is a lot more to it, but we can really get started with what we have now. Next post, I'll write about some ways of using the dot product in game development. Some of them will use the resulting cosine while others won't. Till next time!