The Wizard of Voxels
To kick off his new column about the people and technologies behind the magic of computer games, Paul Schuytema talked to programmer Kyle Freeman about how he turned pictures of the brain into computer graphics that dazzle the mind.
by Paul C. Schuytema
After probing the darkest secrets of the human brain, after creating the hardware and software that makes a three-dimensional CAT-scan come alive, what comes next? If you're Kyle Freeman, it's time to fly a helicopter.
Freeman, an electrical engineer by trade, is NovaLogic's whiz-kid of Voxel Space technology and, as a result, was the key programmer in the creation of Comanche: Maximum Overkill. Prior to trying his hand at game design, he developed medical imaging technologies, using voxel graphics to represent the human brain roight down to the electromagnetic contents of the cerebral cortex. Why, then, leave the brain for game design? The challenge was gone. And for Freeman, who strarted programming games in college, no other genre of computer applications seemed more challenging.
Taking the knowledge he garnered from the medical technology field, he set out to make a visceral, movement-based game featuring realistic, rolling terrain. In an advanced CAT-scan, each view is pre-programmed and each frame may take up to 10 minutes to render on a micro computer. How, then, could Freeman take this technology and create a real-time voxel imaging system using only a 386? "Simple," he says. "It's all in the challenge."
PUMP UP THE VOLUME PIXEL
To understand how these two seemingly disparate fields are related, you need to know a little about voxel graphics. The term "voxel" is formed from the collision of two other words, "volume" and "pixel." In the traditional two-dimensional world of PC bit-mapped graphics, a pixel is a finite graphical unit, occupying space and containing information such as color and luminosity. A voxel is a similar unit, but it exists in a three dimensional world and has the potential to contain much more information. In a CAT-scan, for instance, a voxel may contain color information ,brain activity information, and radiation information. In a voxel taken out of Comanche, there is the density of the solid (water is less dense than rock), the color, the reflectivity, the angle towards the light source, and so on.
In traditional flight simulators, the three dimensional world is modeled in polygons, with the world-data consisting of shape and position information. In a voxel world, the information stored is not all that different, but instead of discrete polygons, a voxel world is made up of thousands upon thousands of small voxel units.
Freeman really didn't approach the Comanche project with the intention of re-defining PC graphics. He simply tackled the task using the tools with which he was familiar. In his medical imaging work, all of the rotations and manipulation of voxel images were predetermined. Freeman wanted to break that barrier to display voxel graphics in real time. Basically, he began the project from the top and worked down. Using his 386 machine, he began working with true photorealistic images, and gradually manipulated and compromised the image quality until he had reached the real time mark he was shooting for.
Listening to Freeman discuss the procfess, I couldn't help thinking that this was far too easy for him, like breathing, or perhaps the more complicated task of tying a shoe. As we talked further, I learned more about the nuts and bolts Freeman had to manipulate to make his vision become a reality.
He programs exclusively in 32-bit native mode, meaning that he uses assembly language, even bypassing the computer's floating-point unit ("it just takes too long for the information to go to and return from a math coprocessor," he told me). When he began the project, there was virtually nothing written for the 386 or 486 that used the native mode. The standard was 16-bit programming. Freeman had to write his own DOS extender and his own development environment, learning by trial and error since the documentation for programming 32-bit native mode hadn't yet been written. Writing in assembly language, Freeman was able to create graphic routines that operated from 100 to 1000 times faster than those created by the C programming language.
This low-level hacking gave Freeman the tools he needed to create his organic, voxel world. But how did he create the realistic rolling terrain and dramatic crevasses? He tried creating worlds in a 3-D modelling package, but found that even with detail levels set at the 5-6 million polygon range, he still wasn't reaching the level of perfection he crave. So, using programs of his own creation, Freeman sculpted the terrain, pushing the shapes around and molding the landscape as if it were clay.
After putting together a terrain map, he stilkl felt that it looked too soft, too artificial. The natural hacker then crafted a few program routines that would morph his voxel worlds, simulating a few million years of erosion, a few seismic disasters, and the constant pummeling by the weather. Each voxel of terrain contains information about the density of each unit, for the rocks, the soil types, the water, etc. Directing his erosion algorithms to take into account the varying density of the material is one of the ways in which he was able to create such realistic landscapes.
VOXELS TAKE FLIGHT
Oddly enough, it wasn't until the final weeks of the project that Comanche became a helicopter simulator. Before then, it was merely a real-time terrain modeling system. As Freeman worked to bring his terrain system together with the flight-model of the RA-66 Comanche, he decided to make the program expandable. Partly because of time constraints, partly because of a desire to leave the game open-ended, he left hooks and ports of access into his tightly optimized code.
With the release of the Over the Edge expansion disk, Freeman has finally taken Comanche as far as he wanted it to go. Effects such as reflection and haze were not added to the earlier missions, because the information in the terrain voxels would have to be re-written. Freeman thinks that's just fine, though. He likes the integrity of the early missions, and the fact that a pilot can land the chopper on the water doesn't phase him. Instead, he thinks of the water in the earlier missions as shallow, stagnant pools. Like any true programmer, he has turned a program limitation into a "feature."
As I was listening to Freeman discuss the sheer number of calculations involved in one frame of the on-the-fly animation, calcfulating up to a million data points and displaying nearly 100,000 surface variations per screen, I wondered just how data-intensive the terrain information is in Comanche, but the exact voxel space scheme which makes this possible is part of the company's proprietary process which makes this voxel technology possible and, with a patent pending, the company is naturally reticent to release specific information.
As each frame in Comanche is being rendered, the computer recreates the terrain from the building-block voxels in the terrain database. In Voxel Space, the terrain is not merely surface data, but the voxels exist even below the surface, filling out the entire solid. As a frame is calculated, the opaque building blocks are assembled and basic calculations are performed, such as calculating the player's viewing angle and relating that information to the angle the voxel has to the dominant light source, thereby arriving at the radiosity of a particular part of the image. When calculating reflections off the surface of lakes and rivers, the graphics engine takes into account the angle or strength of the light source, and how much of the surface image is projected over the water. Then through a creative use of colorizing algorithms, the program blends the color information of the reflected image with that of the water to achieve an appropriately muted mirror image.
BUY A VOXEL
Freeman takes pride in his programming, paying careful, almost maniacal, attention to details. He is proud of his work on Comanche, and he feels that it allows the players to explore truly realistic terrain. When asked why the graphics seem so different than the other simulators on the market, Freeman remarked, "There's a lot more craft in it."
So what future wizardry can we expect from Kyle Freeman? He sheepishly told me that that particular information was classified for the time being. He did give me a hint though, saying that it would be completely photorealistic and in real time. "On a PC?", I asked. "Sure, no problem," was the reply.
