by Paul C. Schuytema, Loyal Bassett, and William Scarboro Paul Schuytema, project leader: A spoonful of algebra makes the polygons transform. If someone had told me back in Ronnoc Connor's (yes, that was his real name) high school math class that math is one of the keys to creating a truly fun game, I would have doubled over laughing. I'd have probably cut class for the rest of the week as well. But here we are crafting Prey, a 3D game with some serious fun potential. When I load up an environment in the shell, take control of Talon Brave, and run around for a while, I marvel at the visual fidelity of the environment. After I've run around for a while, I'll pull the camera back and watch Talon move from a distance. I study his gait and the subtlety of his animation. Yet I make one hell of an assumption when I suspend disbelief and enter the world of Prey. Perhaps assumption is the wrong word--trust might be more appropriate. By participating in the Prey experience, I'm implicitly trusting the core work of our three programmers, William, Tom, and Loyal.
That Old Black MagicI'm trusting in their programming skills to make our Platonic Form of the game come into fruition. For many, programming is a black art, almost akin to necromancy. It's an amazingly alien vocabulary that programmers must master to turn their structured lines of text into code that actually does something. If the uninitiated were to look over a page of C++ code, it would appear nonsensical and alien.
To paraphrase Arthur C. Clarke: Any sufficiently advanced technology is indistinguishable from magic. The programming code our team writes is that advanced and can, at times, seem like the workings of magic. Especially to nonprogrammers. I'm not that frightened, though. I spent all of my high school years and a good chunk of my college years learning that black art myself. I feasted on C and Assembly, and when I was in my groove, I was pretty damn good. I grooved on the whole "programming is spell-casting" analogy. It made the whole thing seem so cool. For me, it was the art of optimizing--of making every bit and byte maximize its impact--that got me excited. I loved tackling a problem that should have been handled in Pascal and coding it in Assembly so that the executable was insanely small. (I had no concept of speed then, just size and algorithmic efficiency.) But I stayed away from one primary area: math. I think that it was all due to a mental meltdown I had in high school trig that I could just never overcome. Anyway, to make a long story short, coding is not magic to me. But math is. More than anything, I rely on our coders' understanding of the mathematical dark practices to coax Prey into life. When I load an environment, I'm oblivious to the heinous calculations going on under the surface to properly assemble and render the scene I see. When I watch Talon run, I notice his animation, but I forget about the insane multiplies that take place just to get him to animate from one position to the next. The math is transparent, but it's there, and it's essential. Here's a peek into the brain behind these dark practices. Warning: Dangerous math below!!
Wither What Math?Loyal Bassett, programmer: We use a bunch of different math in Prey, but most of the job is done with linear algebra on steroids: vectors, coordinate systems, and transformation matrices. We also sprinkle in a bit of quaternions, calculus, and whacked-out 4D math to handle portal transformations, and hairy stuff for our physics system. Probably the most interesting math that we have used thus far is surface area calculation for a two-manifold mesh and the area of a patch on a sphere. The sphere patch is a keen double integral in spherical space. I can hardly wait to see what the NURBS patch integral will look like!
Two of the Prey monsters, rendered in real flesh and blood: William Scarboro (left) and Loyal Bassett (right). William Scarboro, programmer: Because polygons are planar, it makes sense that most of the math required for an engine dealing with them be linear. Thus the only real trigonometry in the core math classes (vector, affine transform, coordinate system) is in the function which builds a transform for rotating about an arbitrary line. And there are Euler angles (named for the 18th-century Swiss mathematician Leonhard Euler), a compact way to describe a coordinate system as a series of rotations. Linear algebra is basically algebra involving matrices and vectors. We're not talking LU decomposition or anything, just affine transforms in 3-space (y=Ax + B, where x and y are points, A is a 3x3 matrix, and B is a vector; I use point and vector interchangeably, although transforming a vector is just y=Ax, leaving off the "grounding" term) and vectors.
The calculus for polygons is minimal, that which comes to mind being the area of a polygon or the volume of a polyhedron, and because those formulas were taken from one of the Graphics Gems and are simply utility functions, they don't figure prominently into the engine. With curved surfaces, there's more calculus. There are some surface integrals (double integrals involving the surface area of a curvilinear patch) for calculating the area of a patch for radiosity. Loyal Bassett: The character system I work on uses coordinate systems and transformation matrices as its mathematical backbone. If I need to perform any trigonometry, I convert vectors to angles with dot or cross products. Similarly, I can convert a coordinate system into Euler angles--a set of three angles for yaw, pitch, and roll. The matrices are 3D transformation matrices, which are a collection of 12 floating point numbers consisting of 4 rows and 3 columns. These matrices are mathematical operators that translate, scale, shear, and rotate points in three dimensions. For example, matrices allow us to move a character up a flight of stairs, turn around a corner, and explode it into little pellets of guts, gore, and intestines throwing the red bubbling mass upon a wall and sliding downward in the direction of the gravity vector.
A test actor model from within Skinner. This shows the wireframe with vector and CS metrics, plus textured skin. William Scarboro: A transform is a 3x3 matrix, A, plus a vector B (for our purposes, vectors are mathematical constructs having three scalars, or floating point values, which provide a linear way to get around in 3-space). Transforms are primarily used to go from one coordinate system to another. For example, you often hear of a point having x, y, and z coordinates; this is misleading. In vector land the point is xi + yj + zk + w, where i (1,0,0), j (0,1,0), and k (0,0,1) are the basis vectors in Cartesian 3-space, and w is the origin (0,0,0). But why limit yourself to i, j, and k? They don't change, for craspy's sake. So, let's pick some other vectors, say u, v, n, o. This is a coordinate system. We have a function of the form void CTform3::Build_NaturalToArbitrary(const CCS& cs); which, given an arbitrary coordinate system, builds a transform which will change the point x, y, z in natural space (i, j, k, w) to the point (a, b, c) in the arbitrary space (u, v, n, o).
Is It the Actor or the Play?Loyal Bassett: An individual character in Prey is a hierarchical model of bones and a continuous skin that covers the bones just like the skin covering our bodies. A big difference is that in Prey these bones can fly apart with a flick of the wrist and squish the body into a leafy nonthreatening mass of goo. Animating the character requires building the skeleton in the stance of an animation frame and wrapping the skin around it like molybdenum foil around an eggplant. The whole process uses a bunch of math: vectors, quaternions, coordinate systems, and so on. Not only is the word quaternion really cool-sounding, but these also facilitate coordinate system interpolations and play a central role in the animation system. Check out the February issue of Game Developer Magazine (page 34) for more details. A pic is missing here Currently, one of our actors with 50 bones requires about 3,000 multiplies and 2,000 additions for the skeleton, and 9 multiplies and 9 additions per vertex! This of course still needs to be optimized. Right now my machine executes about 725,000 matrix multiplies per second, so I am not too concerned yet. I will have to investigate this more thoroughly when I make the time.
The Engine Powers the PlayWilliam Scarboro: If you were interested in writing a generic polygon renderer, this might be your basic pipeline:
Basically, vectors, transforms, and coordinate systems are the only mathematical constructs that you need to worry about. In order to craft a truly scalable engine for today's machines, though, certain mathematical abstractions are necessary. Geometrically, biparamaterized surfaces and displacement mapping initially come to mind. For biparamaterized surfaces, the point (x, y, z) on a surface is a function of s and t, and s and t are on some interval. A plane, for example, has x=As + Bt + C, y=Ds + Et + F, and z=Gs + Ht + I--in other words, it's affine; for a sphere, using spherical coordinates, x = rsin(a)sin(b), y = rcos(a), and z = rsin(a)cos(b), where a and b are angles on the interval (0,PI) and (0,2PI), respectively; for bicubic spline surfaces, x, y, and z are cubic polynomials of s and t; a Displacement Map is just a rectangular grid of offsets, addressed by offset[s][t], for example. How you interpret these numbers to determine final geometry is up to you; they can be scalars for a vector field, a constant vector (the up vector for a landscape), the normal to the surface, whatever. Things change a bit when you consider the next generation of 3D engines. Basically, no longer will (x, y, z) be explicitly stored but generated by functions of parameters s and t. This allows, for example, Level of Detail, or rendering more polygons when something is close, and less when it's far, because players won't need all the detail when they can barely make out an object.
Let's Play Together NicelyLoyal Bassett: The programming team here is big, fun, and talented. They offer dandy suggestions covering such cool topics as designing methods, debugging approaches, programming philosophies, and sock-matching tactics. Oftentimes it all turns into a heated discussion. Some folks here consider many of these topics their religion. Recently, during a Chinese food dinner, one programmer and I argued about the correct number of spaces that should be used for a tab stop. Needless to say, I won.William Scarboro: Everybody here thinks differently, and sometimes the other programmers come up with solutions that are simpler than mine, and vice versa. Explaining problems to the others can do two things: help me understand the problem better, and create more directions of attack. A pic is missing here Paul Schuytema: Math is one of those most elusive of constructs. At times, it seems as if the whole universe follows a neat mathematical pattern. But that begs a classic chicken-and-egg question: Does the universe follow mathematical patterns because that is the way it is, or do we see mathematical patterns in the universe simply because we have invented a way to perceive and process what we experience? Oh sorry--time's up. Unfortunately, we have no more time for those philosophical questions today. We need to get back to our game, after all. Our programmers wrestle with both their code and their math, and fortunately for us, their math is usually rock solid by the time source code is penned. And if they've practiced their dark art effectively, the end result is that we can all just load up the game and play, oblivious to the arcane ruminations that rumble just below the surface...
By the way, here are some books to track down, if you're further interested in the topic: A pic is missing here
And here's one reader question answered:
Dear Confused: Until next month...cheers! |