Thursday, August 7, 2014

[Indie Dev] And Now For Something Completely Different: Camera Math

One of the things I was hired for at Flying Helmet Games is to handle some of the more complex mathematical items. Cameras in particular. Everybody can talk about the cameras they hate in games. Mario 64 had one of the better cameras for the time, but it was still vexing. As the player, you should either not notice the camera, or if you do notice, it’s in a good way. Turns out making a good camera is part art, but there’s definitely a lot of math.


Think about a somewhat pseudo-isometric camera, like Diablo III--note that it’s not technically isometric in Diablo III, it’s just emulating an isometric projection; it’s just a plain old perspective camera locked in position at an angle above with respect to the scene. One of the weaknesses of such a camera is not being able to see ahead to understand where your enemies are. In a trigger-happy hack and slash game like Diablo III, this is fine. You’re not usually attempting to make fine-tuned tactical decisions. But in a game where you want to be able to plan ahead, seeing where enemies are situated before you run into them is key.

I apologize ahead of time for subjecting you all to my MSPaint “skills”.

The eye in the upper left is the camera, and the square is the view: what you see on your monitor. The folks on the outside are the enemies.
So you have your party, the camera is centered on them, and you as the programmer know there are enemies coming up (perhaps your players have a “sight” radius where they can detect characters beyond the camera view). The naïve approach would be to pan the camera over to the enemies to include them in the view. That’s not really too bad of an approach, except depending on how far away the enemies are, you may end up having players fall off the screen, which is terrible.

If we just move the camera over (due to a fixed angle), we end up leaving some players out of the screen!
You could do so temporarily and then pan back, but that involves loss of character control, as well as having to rely on player memory. Not to mention, what happens if they want to engage from range? No, we need to fit everyone on the screen, so instead, we need to programmatically be able to pull the camera back. We’ll also need to push the camera back in when all of that extra distance is not needed.

Note I was told by our cinematics guy that this is in no uncertain terms called "zoom". Apparently zoom involves changing the field of view, and since we need that to be static, it's not zoom. He was quite insistent, and admittedly, he knows the terminology better than I.

Rather, you want to pan to the center of them all, then pull back to ensure all actors you want are on screen.
Once we’ve centered the camera on all of the actors we want to include, how do we calculate how much we need to pull the camera back to ensure they’re all in the view? Some vector math, a little trig, and some ray-plane intersection calculations will do the trick.

So what do we know? We know where the center of the camera is pointed at (our LookAt), we know where the camera itself is situated (our Camera), and we know/can calculate where the furthest actor we need to include in the view is (PointX).


Starting with these 3 points, we can actually calculate a pair of triangles to eventually be able to get to where we want our camera. Below depicts a pretty complex diagram of where we want to be, and all the pieces in-between we need to calculate. I'll break it down.

Don't be fooled. I drew this as a right-triangle, but it's not guaranteed to be one.
So Camera, LookAt, and PointX are known quantities, as per our full diagram above. Camera' is where we want our camera such that it includes PointX. Ultimately, that's what we're trying to calculate.

Note that we know the camera is fixed in field of view and frustum, and as such we know the top-most angle on both triangles will be identical (though we don't know the actual angle A). We also know that the bottom-left angle will be the same, and via the properties of a triangle, we know that all three angles must add to 180 degrees. The result? We're just trying to figure out how much to scale our triangle to fit the triangle to PointX.

If we can calculate the sides a, b, and d, we can figure out what e should be via simple ratios:
Since we're just scaling, these ratios must be equal.
We have the exact locations of three points, so we can calculate the side-lengths b and d trivially. a, on the other hand, may be a bit more difficult. We're missing what I've labelled PointP.

The thing about triangles is that if you have some combination of angles and sides, where you know at least one side, but a total of three things, you can calculate anything else you want about the triangle. However, all we have at the moment is side b. To get side a, we need more information.

We can calculate angle C. We can do so because we have two vectors: (Camera, LookAt), and (PointX, LookAt). How do you find the angle between two vectors? If your math library doesn't offer it, just make sure your vectors are at the origin, normalized, and the take the inverse cosine of the dot product. Unity thankfully does this for you via Vector3.Angle, though you'll still want to ensure they're at the origin.

But now we're at an impasse. We have one angle, and one side, but we can't calculate any more until we figure out what I've labeled PointP. Once we have PointP, getting side a is trivial, as it's just the distance between PointP and LookAt. We cannot calculate PointP with the information we have in the above diagram, however. We need another way to do it.


Let's go back to our full camera diagram. Note that PointP is on a straight line that passes through LookAt and PointX. Also note it passes through our camera frustum! If we can figure out the intersection of that line with the correct frustum plane, we can calculate the precise location of PointP in world space.

Frustum plane calculations are a bit intense, but thankfully Unity again comes to the rescue with GeometryUtility.CalculateFrustumPlanes. It returns all of the planes for our camera frustum. All six of them (near clipping, far clipping, and the four sides). Too many planes! How do we know which one is the correct one?
Creating perspective camera diagrams in MSPaint is more time consuming than expected.
In the above diagram, we see the camera point, and two boxes: one close to "us" and one "further back" towards the camera point. These are the near and far clipping planes. By comparing their normal to the camera normal, we can remove these from the planes that we need to check, since PointP should never be anywhere near the clipping planes.

That leaves us with four planes, and a vector (PointX, LookAt). To figure out which plane we're behind, we can do a quick angle check between each plane normal and our vector using the same technique we did earlier. Whichever angle is the smallest (we don't care about the sign) is the one we're behind.

If you were to ask me to build a rigorous proof of this, I wouldn't be able to off-hand. But I'm fairly certain it works as long as LookAt is precisely in the middle of the frustum walls.
Now that we know which plane to test our intersection against, we can perform a single Ray-Plane intersection and get PointP. Once we have PointP, we can use it combined with LookAt to derive side a, and then apply our ratio calculation to get side e.

As a reminder of what we're deriving and what we have.
Subtract side b from side e, and bam, you now know the distance you need to move your camera back along the camera's normal to fit PointX in the frustum. And, as it turns out, we didn't even need to calculate angle C.

Interestingly enough, this algorithm largely works in reverse, too, if all of your actors are inside the frustum and you need to push the camera back in. One of the vectors you use in a calculation above has to be reversed once you realize you're inside the frustum instead of outside, but you can re-use 95% of the same code. But I leave that as an exercise to the reader so I'm not giving ALL of our mathematical secrets away.

Note that this technique relies on the camera being static as far as field of view and rotation in the world goes. It should be fine to have different starting rotations, but once you've got the camera running, you're stuck (if you need to use fancy zoom in cameras for animation, etc. just duplicate the camera and move the duplicate instead). It also doesn't work if your near or far clipping planes are too close to the characters, but that generally isn't a problem in a Diablo III-style camera environment.

So there you have it. All of the math required to figure out how to fit all of your actors you need to on the screen at once, just to give folks a taste of what I do on a daily/weekly basis! I'm pretty lucky that I get to talk about things at this level of detail, and hopefully we'll have more meaty design-type stuff for folks eventually, too!

#Math, #IndieDev

4 comments:

  1. Your Paint skills are better than mine, for what it's worth. Interesting stuff.

    ReplyDelete
  2. I'm loving this direction of providing guides on this stuff. I've dabbled in hobbyist game development like every hardcore gamer, but I've never managed to work on any of the larger community projects. That would be a treat.

    What kinds of games have you worked on?

    ReplyDelete
    Replies
    1. None before this one.

      Well, not entirely true. If you're talking game design, I've done a fair bit in high school/early university with my gaming group, from card games to board games to pen and paper RPGs (which interestingly enough, the homebrew system I created in high school is the ancient ancestor of the game we're making right now).

      In terms of video games? I made a racing game in University, and that's about it. Most of my experience is currently theory, not practice. So stoked at getting the practice :D

      Delete