Cross Dot Input… Wait what?

CrossProduct

Shamelessly ganked from Wikipedia's cross product article.

Another little snippet of wisdom from adventures in WP7 and XNA. Today it’s a useful little bit of trig for dealing with a particular input case… which is likely to be fairly common on a phone touchscreen, among other places.

Picture is very much related, but be not faint of heart—vectors are actually not that scary, and dot and cross products aren’t bad at all, promise. Especially not since we’re only talking about a very little bit of them for a very specific use. This lets us cut some corners for practical purposes.

The Issue At Hand

So, the problem that needs solving is basic enough. In my game, input is a touch-and-drag affair, where a central construct in the middle of the screen is rotated by the user according to their touch on the screen. Simple concept, makes a lot of sense for the game in question, etc etc.

There are a number of ways to handle this, one of the most straightforward being to take the arctangent of the cursor position(offset by the rotation origin), use that to find the angle between zero and the point, then do the same for the previous cursor location, and subtract the two to get the delta—the change in rotation. This would be a bad idea.

See, computing trig functions is fairly expensive, and we’re dealing with a game, on a phone. I’d much rather save as many cycles as I can on the limited hardware to keep the input crisp and responsive and make room for more flashy particles down the line, wouldn’t you? But we’re doing two arctangents every update this way, and that’s one more function call than is necessary (arguably two, actually, but that’s not certain). So what’s another option?

A Little Math, A Big Solution

Some handy vector math gives us a nice solution to work with. Positions are, after all, simply vectors from the origin that tell us where something is—that’s why we store points using Vector2 and Vector3 structures. There’s a very simple way to determine the angle between two vectors, as well: the dot product of a normalized vector (that is, a vector with a length of one) is equal to the cosine of the angle between them. There’s actually a lot of other useful things you can do with the dot product, actually, but not for this particular application.

So, we take the dot product of vectors A and B, which we get from the formula:

A · B = Ax * Bx+ Ay * By

Or in other words, we multiply together the Xs and the Ys and then add the results. If we had a 3-dimensional vector, we’d multiply the Zs and add them as well. We then feed the result into the arccosine function and voila! there’s the angle in radians (which needn’t be converted).

But there’s one problem—see, the cosine of an angle is the same as the cosine of its negative counterpart. So we don’t know which way the rotation is going. This is a problem, since we need to detect input rotating both ways. Enter the cross-product.

The cross product takes two vectors, and produces a vector perpendicular to them both, with a length equal to double the area of the triangle they define. If this sounds similar to a normal, that’s because it is—a normal is just a normalized cross-product. But we don’t care about that.

We do have an issue. Cross products are specifically based around 3 dimensions—we’re in 2d. But that actually simplifies the issue greatly, since it means we can throw away two-thirds of the full computation. All we care about is the Z-axis of the result. Specifically, we want to know if it’s greater than or less than zero, because that tells us which direction we’re rotating in.

As with the dot product, XNA provides functions to compute these things, but we only need very specific information, so it’s way, way easier and faster to just do it by hand. The formula we care about is this one:

Z = Ax * By – Bx * Ay

The code ends up looking like this:

TrigCodeSnippet

You Said Something About Other Tricks…

I did. There are a few other things for which you could conceivably have a use for dot and cross products. One example is if you’re only interested in whether something is to the right or left of something else… say, for 2D AI. You could use the Z-only cross product and check the sign to figure out which side it’s on rather quickly and easily, though it’s very vague.

The dot product on its own can tell you some useful general information as well. Using the direction an object is facing, and the position of another object relative to it (both normalized), You can get facing information. A dot product of 1 means that something is straight ahead. Everything from 1 to 0 is an acute angle from the front, 0 is a 90-degree angle, 0 to –1 is an obtuse angle from front, and –1 is behind. Combine that with the Z-component of a cross product, and you can tell which side it’s on as well.

There’s probably a way to eliminate the trig call entirely, as well. I suspect that given the above information, one could interpolate angle values based on where in the range the dot product lies. In theory. I’m not sure it would be strictly accurate, since trig functions don’t have linear curves. It might work; but I wouldn’t say I’m confident in it. Perhaps I will experiment with it, but I suspect one arccosine call isn’t a big enough performance hit, and I’m almost certain interpolation between the known dot-product angles wouldn’t work right. Another option is building a lookup table of known angle/cosine ratios and then interpolating between them. Probably better than using the dot product to interpolate, but I’m willing to bet it’s not that big a performance gain.

Anyway, working all this out was kind of fun, if for no other reason than learning something new and useful. Finding the angle between things is terribly, absurdly useful, so I’m sure I’ll be using this one pretty often going into future projects.

This entry was posted in Nucleus, WP7, XNA. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *