Real Time Raytracing – One Possible Future of 3D Gaming

Introduction
We all love the wonderfully resplendent graphics possible on todays graphic hardware. It’s really quite amazing, the stuff we are able to squeeze out of some extremely complex arrays of silicon.

But current GPUs have a dirty little secret that I am going to share with you. Current GPUs are terrible kludges, composed of dirty trick layered haphazardly on dirty trick, resulting in an overly complex mess that requires leaf blowers to keep from melting down into slag. Raytracing could fix all that.

How Graphics Work Now
Currently, all 3D graphics cards utilize a process called “rasterization” in order to create those yummy scenes of multidimensional destruction. In rasterization, the smallest unit of processing (called a ‘primitive’) is the triangle. Triangles are used due to some interesting mathematical proprieties that I won’t bore you with here. The basic idea of a rasterization renderer is to loop through each of the primitives in the scene, determine which pixels in the image it affects, then modify those pixels accordingly.

This has some really nice advantages which is why all 3D cards have used the technique up to now. First of all, large areas of the image might not have any primitives at all and a rasterizer can simply ignore these areas and not have to do any processing. Secondly, it can drastically reduce the work needed to form an image by the fact that pixels occupied by a single primitives tend to be contiguous (ie, next to each other) in the image; using some fairly simple math here can basically copy the pixel data into huge swaths of memory without having to do any processing on it.

In terms of Big-O Notation (a standard way of expressing how fast an algorithm is), Rasterization is O(n) where ‘n’ is the number of primitives in the scene. As the number of triangles goes up in a rasterized scene, the time it takes to render it goes up linearly; a scene with just one triangle in it will take O(1) time, while a scene with two triangles in it will double the time needed to O(2), and so on.

Where Rasterization falls down, though, is in its complexity and “special effects”. In order to do most rasterization effects, one needs to know how to deal with some pretty complex linear algebra and matrix math. In addition, a lot of effort is spent on Occlusion Culling (that is, not rendering primitives which can’t be seen on the screen) since so much of the speed of the algorithm depends on not drawing things you don’t need. Special effects, such as shadows, reflections, and visual caustics (such as refraction in a water droplet or glass sphere) become ridiculously complex and expensive operations. Literally, whole books have been written on just getting dynamic shadows to work with a rasterizer.

Because all objects on the screen must be composed of triangles, a sphere is the most computationally expensive thing to make in a rasterizer; to make a “real” sphere, you would essentially have each pixel equal to a single triangle. As a result, spheres (and other curved surfaces) are approximated with dirty, filthy hacks that can result in all kinds of minor (but amusing) graphical glitches (such as the a kalediscope effect when the camera moves around a sphere, close up). And making reflections or shadows on a curved surface is a nightmare; doing either tends to reveal the illusion that what you’re seeing is not a real sphere or curve.

How Raytracing Works
Raytracing, by comparison, is much, much simpler. As an added bonus, it also more accurately approaches the way the Real World works (physicists would say that the Real World approaches the raytracing model, but physicists are all insane anyway). The practical upshot of which is that one gets things like dynamic shadows and reflections for free; they are inherent in the way the algorithm works. In addition, what are considered primitives in a raytracer is much more flexible; essentially every pixel can be a primitive BUT ALSO any type of mathematical expressed equation can be one

Fundamentally, a raytracer works like this: for every pixel on the screen, draw an imaginary ray out from it, find the nearest primitive that intersects this ray, bounce the ray off and do it again until either some maximum number of bounces or a light source is reached, then color the pixel.

Confused? Maybe an analogy will help: If you imagine the ray from the pixel being the ball from Pong, it will travel along in one direction until it hits something, then it will bounce off the object. Once it reaches the end of the line, it will apply the colors from each bounce to the pixel it represents.

That’s right, essentially a ray tracer is Pong done in three dimensions.

In Big-O Notation, a ray tracer is an O(log n) algorithm in which ‘n’ is the number of primitives (both pixels and actual scene objects). As a scene gets higher resolution and more complex, a ray tracer becomes not only competitive with rasterization, but actually better. We are hitting those numbers now.

Advantages of Raytracing
The practical upshot of playing a game of pong per pixel means that you get dynamic shadows and reflections for free; each pixel already knows the path it took to get somewhere, so it knows what is behind something else and what is reflective.

Another advantage has to do with the fact that primitives can be any mathematical construct. If you’ve done any geometry, you know that the equation for a sphere is dead simple. As a result, in a ray-tracer, a sphere is actually one the least computationally intensive things one can render. Another practical upshot is dynamically deformed terrain; since all objects in a raytraced scene are composed of mathematical functions, changing the function gives naturally deforming terrain. A rasterizer has to go through all kinds of gymnastics to update the vertices of the primitive its changing to get the same effect (this is, essentially, what current GPU Vertex Shaders do).

In addition to the above, ray tracing has another advantage in that it is in a class of problems that is known as “embarrassingly parallel”. What this means, basically, that you can linearly speed up the algorithm by simply computing pixels at the same time. So if you could have some raytracing hardware that had, say, eight special purpose mini-GPUs that all they did was run a ray trace for a single pixel, you could speed up rendering by eight times. The more of these mini-GPUs you have, the faster things render, up until you hit the total number of pixels being processed.

If the above sounds strangely familiar, then it is. It turns out, this is essentially how IBM’s Cell processors (and to a lessor extent, Intel and AMD multicore processors) operate; the difference here is that the sub-processors in current chips are more general and not special-purpose. But the technology currently exists to easily make RPUs that have these specialized sub-processors.

The (Possible) Future
Since games are getting to the point where current Rasterizer systems are beginning to fail due to both time and complexity restraints, there is currently a lot of interest in Real-time Raytracing. The fact that current CPU makers are in a slightly better position to make RPUs do to their experience with making multi-core CPUs, that both Intel and AMD now have graphics subsidararies, and the promise of much simpler graphics programming seems to make raytracers an almost sure thing in the future. Rasterizers won’t go away (they’re still really useful for some effects like particles and glyphs), but they will become less important in the future.

The main problem with bringing raytracing hardware to the masses is simple inertia. Basically, real-time computer graphics have been, for a very long time, completely ruled by Rasterization. All the tools and techniques currently used in games are geared towards it; transitioning to raytracing will mean migrating all these systems to the new development model. In addition, people are going to be (understandably) irritated if their new Whiz-Bang RPU doesn’t play their old, raster-based games as well. For this reason, I predict we’ll probably see the first RPUs being used in consoles. Here, hardware compatibility isn’t very important, and essentially all the developers have to start from scratch anyway each generation.

What remains to be seen is how long it takes.

Cool Examples!!!111oneoneWTFBBQOMG!
Here are a couple videos I’ve found of realtime raytracing that should impress.

Quake3 Raytraced. A group of bored computer scientists decided to put their new huge 20 CPU networked datacenter to good use by converting Quake 3 to use a raytracer.
Quake3 Raytraced

FPGA Prototype at 66 MHz. Here, a bunch of researchers have made a RPU prototype using a Field Programmable Gate Array (that means it’s hardware that can be rewritten by software). It’s real-time, but slow. On the plus side, a production system would be approximated twenty-three times faster than what is pictured here, so if ATI or nVidia decided to make a RPU, these demos would be quite usable.
FPGA Prototype