Game Math: “Dot Product” of Curves

OK. Based on some feedback, turns out the wording of this post is logically loose and not entirely correct. Here is a revised version of this post.

This post is part of my Game Math Series.

Also, this post is part 1 of a series of posts leading up to the geometric interpretation of Fourier transform and spherical harmonics.

Fourier transform and spherical harmonics are mathematical tools that can be used to represent a function as a combination of periodic functions (functions that repeat themselves, like sine waves) of different frequencies. You can approximate a complex function by just using the first couple periodic functions of lower frequencies. Fourier transform is often used in audio processing to post-process signals as combination of sine waves of different frequencies, instead of single streams of sound waves. Spherical harmonics can be used to approximate baked ambient lights in game levels.

We’ll revisit these tools in later posts, so it’s okay if you’re still not clear how they can be of use at this point. First, let’s start somewhere more basic.

Dot Product of…Curves?

That’s right. You can compute the “dot product” of two curves, just like you would with ordinary vectors.

In terms of vectors, the dot product of two unit vectors tells you how much they are in the same direction (1 being completely identical, 0 being perpendicular, and -1 being in complete opposite direction). If the two vectors are not normalized, i.e. not unit vectors, then the dot product is scaled by the magnitude (or length) of each vector. I think sometimes, though not always, it’s convenient to think the vector dot product as a measurement of how “similar” they are. For instance, given vectors \vec{a} = (1, 2, 3), \vec{b} = (1, 1, 1), and \vec{c} = (-1, 0, -2); intuitively, \vec{a} feels more “similar” to \vec{b} than \vec{c}, because all components of \vec{a} and \vec{b} are positive and the components of \vec{c} are either negative or zero. This can be verified by computing the dot products \vec{a} \cdot \vec{b} = 6 and \vec{a} \cdot \vec{c} = -7. Since \vec{a} \cdot \vec{b} is larger than \vec{a} \cdot \vec{c}, we can say that \vec{a} is indeed more similar to \vec{b} than \vec{c}.

As for dot product of curves, the idea is pretty similar. The dot product of two curves tells you how similar the two curves are. Let’s say we have curves f(t) = 1, g(t) = 0.5 + t, h(t) = -t^2. Note that when measuring similarities between curves, we need to specify an interval that we are interested in. For this example, let’s look at 0 \leq t \leq 1. Here are what the curves look like within that interval.

curves

f(t) looks more “similar” to g(t) than h(t), yes? Let’s see how we can measure that using dot product of curves.

How would you take the “dot product” of two curves? How about sampling (taking the values of) the curves evenly along the interval 0 \leq t \leq 1, multiplying sample pairs of each curve at the same t, sum up all the products of sample pairs, and then take the average by dividing the sum with the number of samples. Sounds a lot like dot product of vectors, yes? Just like adding together products of corresponding components from two vectors, except that we take the average at the end so the end result stays normalized and does not change drastically based on the number of samples we take. If we take 10 samples to compute the dot product of f(t) and g(t), then this is what we’d get:

    \[ f(t) \cdot g(t) = \frac{1}{10} \sum_{i = 1}^{10} f(\frac{i}{10}) g(\frac{i}{10}) \]

The more samples we get the more accurate this measurement will be. What if we take an infinite number of samples so we get the most accurate measurement possible?

    \[ f(t) \cdot g(t) = \lim_{n\to\infty} {\frac{1}{n} \sum_{i = 0}^{n} f(\frac{i}{n}) g(\frac{i}{n}}) \]

This basically turns into an integral:

    \[ f(t) \cdot g(t) = \int_{0}^{1} f(t) g(t) dt \]

So there we have it, one common definition of the “dot product” of two curves:
The integral of the product of two curves over the interval of interest.

Let’s see what the dot products of f(t) and g(t) is, compared to that of f(t) and h(t).

     \begin{flalign*}   f(t) \cdot g(t) = \int_{0}^{1} f(t) g(t) dt &= [\dfrac{1}{2} (t^2 + t)]_{0}^{1} = 1 \\   f(t) \cdot h(t) = \int_{0}^{1} f(t) h(t) dt &= [\dfrac{-1}{3} t^3)]_{0}^{1} = \dfrac{-1}{3} \\ \end{flalign*}

The dot products of f(t) and g(t) is indeed larger than that of f(t) and h(t), so we can say for sure that f(t) is more similar to g(t) than h(t).

Now you know how to compute the “dot product” of two curves over an interval, to determine the similarity over that interval. In the next post, we will discover how to extend what we’ve learned to “project” one curve onto another, just like we would for vectors.

About Allen Chou

Physics / Graphics / Procedural Animation / Visuals
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply