Black Art of 3D Game Programming: Writing Your Own High-Speed 3D Polygon Video Games in C

Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 1
Black Art of 3D Game Programming: Writing
Your Own High-Speed 3D Polygon Video
Games in C
Black Art of 3D Game Programming: Writing Your Own High-Speed 3D
Polygon Video Games in C by Andre Lamothe.
Contents
1 Introduction
2 Part 1: Incantations
3 Part 2: Alchemy
4 Part 3: Spells
Introduction
Black Art of 3D Game Programming, About the Author
Black Art of 3D Game Programming, Acknowledgments
Black Art of 3D Game Programming, Foreward
Black Art of 3D Game Programming, Preface
Black Art of 3D Game Programming, Installation
Part 1: Incantations
Black Art of 3D Game Programming, Chapter 1: The Genesis of 3D Games
Black Art of 3D Game Programming, Chapter 2: Elements of the Game
Part 2: Alchemy
Black Art of 3D Game Programming, Chapter 3: The Mysterious VGA Card
Black Art of 3D Game Programming, Chapter 4: Waking the Dead with
Animation
Black Art of 3D Game Programming, Chapter 5: Communicating with the
Outside WorldBlack Art of 3D Game Programming
Copyright 2006 Andre LaMothe 2
Black Art of 3D Game Programming, Chapter 6: Dancing with Cyberdemons
Black Art of 3D Game Programming, Chapter 7: The Magick of Thought
Black Art of 3D Game Programming, Chapter 8: The Art of Possession
Black Art of 3D Game Programming, Chapter 9: Multiplayer Game
Techniques
Black Art of 3D Game Programming, Chapter 10: 3D Fundamentals
Black Art of 3D Game Programming, Chapter 11: Building a 3D Graphics
Engine
Black Art of 3D Game Programming, Chapter 12: Solid Modeling and Shading
Black Art of 3D Game Programming, Chapter 13: Universal Transformations
Black Art of 3D Game Programming, Chapter 14: Hidden Surface and Object
Removal
Black Art of 3D Game Programming, Chapter 15: Clipping and Rendering the
Final View
Black Art of 3D Game Programming, Chapter 16: Voxel Graphics
Part 3: Spells
Black Art of 3D Game Programming, Chapter 17: Optimizing the 3D Engine
Black Art of 3D Game Programming, Chapter 18: Kill or Be Killed
Black Art of 3D Game Programming, Appendix A: Cybersorcerer and
Cyberwizard ContestsBlack Art of 3D Game Programming
Copyright 2006 Andre LaMothe 3
Black Art of 3D Game Programming, About
the Author
Andre LaMothe has worked in many areas of the computing industry, including neural networks, 3D
graphics, virtual reality, and robotics. He holds degrees in Math, Computer Science, and Electrical
Engineering. You'll find articles by Andre Published in Computer Language[1], Circuit Cellar[2], and
Game Developer[3]. Andre has also written two best-selling books previous to Black Art of 3D
Programming--Tricks of the Game Programming Gurus and Teach Yourself Game Programming in 21
Days.Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 4
Black Art of 3D Game Programming,
Acknowledgments
The acknowledgements of any piece of work, whether it be a book, a movie, or a song, is always one of
the hardest parts to write. Black Art of 3D Game Programming is the largest project I have ever
undertaken, and dealing with the sheer magnitude of it wouldn't have been possible without dozens of
other people working behind the scenes. I hope I will remember all the wonderful and talented people
that contributed, but if I've left anyone out, let me say thank you now.
First, I would like to thank Monique Parker for introducing me to Mitch Waite. The introduction was
right out of an episode of "Beverly Hills 90210." We were introduced on a car phone, which was
followed by me reading my first few paragraphs of the book to Mitch. I guess deals aren't made on golf
courses anymore, but on Highway 101 at 85 mph! Thanks to Mitch Waite for allowing me total artistic
freedom with the book and letting me have my way in most cases. I tried very hard to write a book like
you would, Mitch; I hope I have at least come close. Next, I'd like to thank Jacqueline Berry for always
keeping me up when I was down and making sure I didn't stay up more than 20 hours a day. May all
your dreams come true. And by the way, I think I saw your monkey over here again!
Black Art of 3D Game Programming took many months to complete; during this time many
souls crossed my path. Each of them had a slight effect on my mood, my views, and, of course, my
writing. First, Thanks to my training partner, Armand Delgado, for making sure that I didn't turn into a
jello mold while writing this book, and for his assistance in editing its last chapters. Next, I'd like to thank
Dion Phillips and Mark Bell for keeping me on my toes and always arguing with me (what are friends
for?). By the way, Mark, I am always right! Thanks also to Lloyd Richman for taking me jet skiing and
making me come out of my dungeon occasionally. Thank you to networking master Ash Patel for always
getting me that little item that I needed, no matter what it was. Thanks to my cousin Denis Duarte for
making sure I stayed alive and ate once in a while, and to Danny of Dry Creek Liquors for letting me hang
out and watch all those good cable channels at his store. I also would like to thank Jim Valentine, the
CEO of my new company, Andromeda FX, for his support. Thank you Steve Wozniak for making an old
dream come true--that is, sitting around and eating pizza and talking to the "Woz" about the old days of
Apple. And thanks to the producers of the Enigma CDs and the Cique Du Soleil Alergria CD for the
wonderful music. I listened solely to these CDs while writing this book, so my words and thoughts have
your music within them.
The next group of people I'd like to thank are those that had a direct or indirect input into this book in
one way or another. First, I want to thank all of the hard working editors, artists, and production staff at
Waite Group Press; you have done an incredible job, better than I could have ever expected. Thanks to
Kurt Stephan, my managing editor, for understanding that good things take time--sometimes it's worth a
slip or two (or three or four...) in a schedule to ensure that very best work. I want to thank acquisitions
editor Jill Pisoni for obtaing compilers, books, and various other items that helped make this book
happen. Thank you to Heidi Brumbaugh for her developmental edit to the book. Also, thanks to Lisa Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 5
Anderson Mann for helping put together the final marketing touches. Thank you to WGP editorial
assitants Joanne Miller and Laura Brown fore sending me all those nice letters, directing me to the right
person all the time, and for getting all the permissions for the games on the CD. Finally, thanks to 3D
modeling guru James Dowlen for creating the perfect cover for the book.
I'd like to mention some of the companies that gave me access to their products to help create the
content of this book. Tenberry Software (formerly Rational Systems) provided its killer Dos Extender.
Theresa Pulido of Creative Labs loaned me some of the company's most advanced products, such as the
AWE32 sound card and Video Blaster. By the way, Theresa I'm still, uh, using the cards. Borland and its
latest C/C++ 32-bit development system, which I must say is the coolest and most widely used DOSbased protected-mode compiler available for game programming. Finally, I want to thank Bill Dunlap, an
old college buddy and a head honcho at Borland, for getting me a copy of TASM on an hour's notice!
Next, I want to thank some other friends that took time out from their busy schedules to help me out
with the book. Thanks to musical genius Dean Hudson of Eclipse Productions for creating the music for
this book within hours, and to Rob Wallace for lending a helping hand in converting MIDI to MIDPAK
files. I want to thank Richard Benson for flying here from Los Angeles to assit me in converting all the
software from Microsoft C/C++ to Borland C/C++ to make all you Borland users happy! (And don't feel
bad that I beat you 11 times in Descent, Rich!) Also, I'd like to thank 3D Studio guru Joe Font for creating
the PLANETS.FLI animation for Kill or Be Killed.
Finally Thanks to all my family, especially my mother and father, for the support they gave me during
this adventure. And last but not least, I want to thank God in the skies above, because when I was
exhausted from lack of sleep and pushed beyound the limits of human endurance, it was He that gave
me the strength to finish this book and begin this most excelent adventure...
Andre J. La Mothe
Sometime in the late 20th Century
Silicon Vally, U.S.A.
Third Planet from the Sun, Milky Way Galaxy
Compuserve: 75441,2455Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 6
Black Art of 3D Game Programming,
Foreward
In the '50s and '60s computer were so expensive that only the largest coporations owned them...so
expensive that computers gave corporations invincibility. Computers occupied gigantic lairs requiring
dozens of Superman technicians. This kept computers shrouded in mystery from the rest of us. But
advnaces in photographic reduction have reduced the cost of computers hundreds of times during my
life. Each year, computer hcips cost less and less, and this phenomenon will continue until we reach
atomic limits. In 1969, Apple was just a glimmer in my eye. I told my father someday I'd own a
computer. he pointed out that they cost as much as a house, so I told him that I'd live in an apartment!
However, by 1975 it was feasible to build or by a tiny computer for roughtly the cost of a good electric
typewriter. The first small computers could do nothing more than blink a few lights by the were in fact
computers...mostly kits containing LEDs and switches that made little sense to most people. But to me a
computer was complete when it could be programmed with a set of logical decisions in order to play a
game. once that was possible, every conceivable application involving procedures, inputs, responses and
Decision-making was possible. Hence, if a computer could be used to write a game, then any other
application could be written.
In the early days of arcade video games (shortly before Apple), I had designed the game Breakout for
Atari. Games then were not computers; they were made purely of hardwired logic built from TTL and
CMOS chips with a single task of generating simple graphics on a TV display. When I designed the Apple,
I wanted it to be able to play games. Most computer games in 1975 were written in BASIC. The Apple II
was the first computer ever to come with a programming language in ROM, which I called GAME BASIC.
The Apple II was also the first with sound, paddles, high-resolution color graphics, and extensions to the
ROM BASIC to utilize these capabilities. Having the Apple II in hand, I set out for the ultimate test. My
test was to write Breakout as a software program instead of a collection of hard-wired logic, as I had
done for Atari. In less than an hour, I had a working version of Breakout and within the next couple
hours I was able to try a multitude of options that would be virtually impossible if the game were based
on pure hardware. At that instant I realized that game design would chagne forever--that games would
be software programs and not made of hard-wired logic designs.
Today, game programming is much more difficult than it was in the '70s and '80s. For a game to be
popular, it must strive for levels of graphics, sound, and response that are common for the day--in 1995,
this means digital sound and full 3D graphics. So how did game programming evolve from the 8-bit days
of Apple? Well, we started with a low resolution breakout game. Soon a few programmers used high-res
graphics for finer detail. They developed techniques to play sound simultaneously. Very often they were
able to accomplish what even I felt the computer was too slow to do. Each game took a single
programmer a month or more to write.
Then something happened: games became valuable and a multimillion dollar industry overnight! Soon
more effort went into them. Programmers found it useful to construct reusable "parts" that coule be Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 7
pieced together to make a game. One of the experiments in this reusable-parts technology was a game
called the Pinball Construction Set. It allowed the player to build his or her own pinball game by adding
bouncers, gadgets, and various other pinball-related components until the desired custom game was
complete. This open-ended technology was complex and took more time that usual for software
engineers to implement, but once it was complete, new pinball games could be constructed in a matter
of minutes to hours!
This was the beginning of the age of "tools." Various individuals realized that there are many aspects to
a game that the game programmer shouldn't have to worry about--such as paint and sound programs--
so many manufacturers started supplying these tools to the game programmers. Then something else
happened. Game programmers realized that for each game they were reweiting many low-level
functions for pixel plotting, sound, and so on, so graphci and sound software tool-boxes full of useful
and expertly prewritten programs emerged. The world advanced and 2D games improved. By the mid-
'80s, game creation typically involved up to a dozen key parties. But now in the '90s, 3D games are by far
the most exciting and popular, and unfortunately can be created by only a handful of individuals.
moreover, almost no serious business program can compete with a game when it comes to complexity
and speed.
Writing a good game today requires more computer knowledge than was available in all the college
courses offered when I attended school. There are literally hundreds of different topics that cover
programming alone, and hundreds more topics for writing games. It's an amazing feat that anyone has
been able to collect all this knowledge and focus it in one place at one time for others. I've never met a
programmer as impressive as Andre LaMothe. He writes book after book explaining the tricks of the
trade to everyone from young beginners on. So many youngsters find a calling for the rest of their lives
when they read on of his books. There's so much contained in Black Art of 3D Game
Programming--from 3D grpahics, systems programming, and toolboxes to examples and demos--that
it is certainly the most complete book ever on 3D game programming. To young enthusiastic
programmers, every topic is a fantastic treasure of techniques, tips, and tricks.
I feel a huge sadness when I meet someone like Andre and see how much he cares about a program
feeling right to the final user, and when I see such a wonderful book. Sadness because I am frustrated by
most programs written today (not games!) being so slow, full of bugs, not doing what's expected, giving
misleading or incorrect messages, etc. Sadness because I'm not 10 years old, with all the greatest
treasures of the world awaiting me in Black Art of 3D Game Programming, a book written with
the single goal of helping others begin a fantastic journey.
Sincerely,
Steve Wozniak
(Inventor of the Apple Computer)Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 8
Black Art of 3D Game Programming, Preface
Within these pages are the descriptions of ancient spells and incantations. If mastered, these ancient
rites foretell the techniques of creating full 3D virtual worlds existing within a parallel "electrical"
dimension. With this knowledge, you will be able to create hordes of alien creatures, living machines,
and universes where the laws of physics and gravity are yours to toy with. You will become a master
with powers beyond bound and reason. After completing this Necronomicon, you will have reached the
level of Cybersorcerer. Read on, mortal, if you dare...
For Years, video game design has been a "Black Art" passed from one master to another. Many people
affiliated with the world of software engineering and computer science think than video games are
child's play and not serious programming challenges. They are most incorrect in these assumptions. i can
attest that never in all my years of programming have I written anything as challenging as a video game.
A video game is more than a program; it is a conduit into another dimension, a dimension synthesized
by the imagination and realized by sheer will. Technically, a video game is nothing less than a work of
art. it must be incredibly efficient, it must control every aspect of the computer it is running on, and it
must be perfect. To create such a work, the Cybersocerer must be resourceful and highly creative. He
ust know every dark secret abou thte system he is using, so as to exploit it in a way that has never been
seen before.
Black Art of 3D Game Programming unlocks the mysteries of how 3D games are created. This
book will show you the details, the logic, and the "magick" of creation. It will teach the philosophy
behind game alogorithm design, and it will teach the most important thing of all: the essence of what
makes games fun to play. After reading this book, you will be able to create 3D games of your own.
However, this knowledge comes at a price and the price is this: you must use what you learn and create
the best games you possibly can. With that in mind, you are now an apprentice Cybersorcerer. Turn the
page and being your training...Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 9
Black Art of 3D Game Programming,
Installation
The software and tools for Black Art of 3D Game Programming are located on the CD-ROM
bundled with the book. To make the installation of the CD Imple, I have included a menu driven
installation program athat will query you as to the files you wish loaded. the CD contains both Microsoft
and Borland Versions of the source code along with various graphic and sound tools. Be sure to explore
the GRAPHICS and SOUND directories to discover such valuable bonuses as the NorthCAD-3D wirefram
CAD program, the NeoPaint painting program, DiamondWare's Sound ToolKit, and the BLASTER master
audio toolkit.
To load the CD onto your computer, follow these steps:
1. Place the CD into your CD-ROM drive.
2. Make the CD-ROM drive the current drive by typing E: or F: (or whatever the CD-ROM drive letter is).
3. Type in INSTALL.EXE at the DOS prompt--this will launch the installer program.
4. Once in the installation program, follow the on-line help and instructions.
VERY IMPORTANT: Please not that the installation program installs whole directories and not individual
files. If you wish to replace a file, you will have to copy it using the DOS Copy command or Windows File
Manage. Also, if you do not use the installer program and decide to copy the files instead, besuer to
change the Read Only attribute on all the files you copy.
After you have loaded the software onto your computer's hard drive, you are ready to begin the book.
You will find all the files under the main directory BLACK3D. I suggest that you load at least one version
of the source code (either Microsoft or Borland), and both the graphcis and sound programs. You might
want to hold off on loading all the bonus games since they take up quite a bit of disk space. Instead, I
suggest you try to play them directly off the CD first, or load only the games you want to check out onto
your computer one at a time. Games that will not play off the CD will need to be installed to your hard
drive. Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 10
Black Art of 3D Game Programming, Chapter 1:
The Genesis of 3D Games
We have all played video games, but do we really know what they are? Do we really understand how
they are created? Within this chapter the secrets of the technology used to create games is going to be
uncovered for all to see. We'll begin by understanding the Black Art of Cybersorcery and what it means.
Then we will discuss the history of games and their advancement through the ages. Finally, we'll cover
the details of the 3D game library that we are going to construct throughout the pages of the book.
Beware, if you read on there is no turning back...
Of Cyberspace and 3D Games
The time has arrived when the machines known as
computers can finally open up the gateway into the
parallel universe known as Cyberspace. This gateway,
depicted in Figure 1-1, was closed many eons ago by the
ancient ones. Before that time, these ancient ones
(alchemists and sorcerers) manipulated and traverse the
gateway to manifest unbelievable creatures and forces to
do their bidding. Unfortunately, after many millenniums
the ancient technology of Cybersorcery has been lost.
However, using computers as tools, once again we have
established a link to the gateway that separates our
universe from Cyberspace. Due to the primitive
nature of our machines, we can't yet teleport
objects from Cyberspace back to our world, as the
ancient ones could. We can only view them, as
shown in Figure 1-2. But this isn't too bad. Since it's
possible to control and manipulate the creatures
beyond the gateway, we can force them to
participate in games of fantasy, fiction, and
destruction. This is our goal.
An entire science based on the ancient techniques
of Cybersorcerty has been formed to create small
windows into the gateway. These small windows
are called video games. The first video games only
Figure 1- 1
Figure 1- 2Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 11
projected two-dimensional
images from the gateway onto
the screen. These twodimensional games sufficed for
many years and will probably still
be around for more to come. But
now, a far better communications
channel between us and the
gateway is possible. This new
communications channel is made
possible by the faster processing
ability and increased memory
capacity of our computers. With it
we can truly see into Cyberspace
and control the being within it to participate in full, three-dimensional video games.
Although it is impossible to draw a 3D image on a 2D surface (such as a video screen), a 3D image can be
"projected" onto a 2D surface, as shown in Figure 1-3. Cybersocerers use this technique to create the
illusion of three dimensions on a two-dimensional surface. Hence, when the term 3D is used to describe
a game, it means a projection of a 3D world. The technology of Virtual Reality (another branch of
Cybersorcery) is committed to allowing humans to project their consciousness into Cyberspace, but this
technology is still in its infancy.
Evolving from 2D to 3D
The evolution of 3D games has
taken many years. Even today they
continue to evolve and progress as
new technologies emerge.
However, there were specific
transitional stages to this evolution
that we should recall and study in
order to better understand the
problems associated with 3D
games.
Figure 1- 3
Figure 1- 4Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 12
Vector Graphics
Rendering 3D graphics was too
much for the computers of the
early eighties. Thus other
techniques had to be used,
allowing visualization of 3D
entities at a rate that was
acceptable for such a demanding
application as a video game. The
solution to this problem was
initially solved by using vector
display systems like that found in
an oscilloscope. An example is
shown in Figure 1-4. Vector
displays draw video images by
positioning an electron gun (mounted in the rear of the vector display) to different (x,y) locations on the
video screen. Then by modulating the intensity of the electron beam, straight lines can be drawn from
one point to another in very rapid succession. Figure 1-5 illustrates this process.
Since the only geometrical entities that could be drawn effectively by the vector display were lines, the
games created using this technique were all wireframe. In other words, the objects were not solid.
Video games of this type were acceptable for a while (Battle Zone and Star Wars by Atari used this
technology, but the public wanted more. Furthermore, vector graphics systems weren't available on
personal computers, so this made it difficult for PC Cybersorcerers to implement this technology. In
time, the idea of vector graphics died, and the current technology of raster displays reigned supreme.
Raster Graphics
A raster display is generated in much the same way as a vector display, except for a few aspects of the
rendering and hardware. First, the video screen itself is composed of thousands of small pixels that are
each addressable as a single (x,y) location. These pixels (picture elements) are used to generate the
image on the video screen by energizing a subset of them while leaving others off. Furthermore, each
pixel can be illuminated in a multitude of colors, unlike the vector displays that were usually in
monochrome. This is possible since each pixel is composed of three separate subelements that can
illuminate red, green, and blue, respectively.
Figure 1- 5Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 13
The Video Image of a raster display
is drawn row-by-row by the
electron gun, as shown in Figure 1-
6. When all the lines of the display
have been drawn, the gun retraces
to the top of the screen and the
process starts over. On average, the
video display of a typical computer
monitor is redrawn 60 times a
second. This is more than enough
for smooth animation and graphics
to take place. Also, raster graphic
displays look much better than
vector displays. But there is one
problem: Every 3D image on the screen has to be drawn a pixel at a time instead of a line at a time. This
was a serious bottleneck for early processors since images could have thousands of illuminated pixels in
each frame. And there are many calculations for each pixel. This problem slowed the development of 3D
games to a crawl. Cybersorcerers had to wait for the hardware to catch up with the software they
wanted to create.
Parallax Scrolling
The first 3D games weren't 3D at
all. Instead they used 3D illusions
to trick the player into thinking the
universe being projected was in
some way three-dimensional. One
of the first techniques that was
used to accomplish this trickery
was called parallax scrolling.
Parallax scrolling is a modeling of
what happens in the real world
when you're in motion and look
out to the horizon. The objects in
the distance move very slowly
while the objects nearer move
very rapidly. Figure 1-7 shows this.
The parallax effect is due to the
properties of light and relative
motion. In any case, it is easy to
simulate. It can be done by taking a few different backgrounds and moving them at different rates to
create the illusion of depth.
Figure 1- 6
Figure 1- 7Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 14
The only drawback to this technique is that all the games made with it had to be side views, and thus the
games were still locked into a 2D environment. Even though the player could see parallax in the
distance, it was only an illusion, and the player couldn't move there.
Bitmap Scaling
Next, Cybersorcerers created 3D environments that
simulated many 3D effects by means of one of the
most important cues that our brains use:
perspective. As you know, when an object moves
nearer it becomes larger, and when it moves away it
becomes smaller. An example of this is shown in
figure 1-8. This effect is created by the light rays
converging to the viewpoint of the observer.
Perspective was implemented in games by drawing
flat rectangular objects composed of pixels (usually
referred to as bitmaps) that were made larger or smaller depending on their distance from the player's
viewing position. The size of the bitmaps can be computed using the formula
Object size = K/distance
where K is a constant based on the original size of the object.
Drawing the objects on the video screen in different sizes is implemented with a technique called
bitmap scaling. Bitmap scaling is performed by multiplying the size of an object by a factor called the
scale factor. However, using bitmap scaling to synthesize a 3D world has its problems. Scaling bitmaps
isn't as easy as it seems; furthermore, all the objects in the game universe are still flat! They only look
like they have volume. Hence, the worlds constructed using this technique are still not truly threedimensional.
Wireframe Polygon Engines
At some point, Cybersorcerers looked back at what was previously done with vector graphics and
wireframe worlds and the tried to implement wireframe 3D graphics using raster hardware. This
technique was successful, and the first truly 3D games were born on the PC. These wireframe games
existed in real 3-space and were viewed by projecting the 3D images on the 2D video screen, as shown
in Figure 1-9.
Figure 1- 8Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 15
Even though they were the first
real 3D games, they looked
primitive. They needed to look
more realistic because games
using the techniques of parallax
and bitmap scaling, though not
truly 3D, actually looked better! At
last, some real brainpower was
put into the problem of rendering
3D graphics using a PC, and many
techniques were thought up that
are all good for some specific
purpose or game type. Since
Cybersocerers are only interested
in making games, we can use any
technique that we want as long as it works. Well, so much for the history lesson. Now let's learn about
the latest 3D techniques and what they offer.
Trends in Sorcery
Today, a handful of techniques are being used to create 3D games. These techniques all have their
strengths and weaknesses, but they are all interesting and solve different kinds of game problems. By
understanding all of them, or at least being acquainted with them, we will be better prepared for all of
the difficult spells we must cast to create 3D games.
Solid Polygon Rendering
The technique that we will be using to create out games
is based on polygons--more precisely, filled polygons.
Filled polygon graphics are the next step up from the
wireframe techniques described earlier. The only real
difference is that the images are solid and composed of
flat facets instead of lines, as shown in Figure 1-10.
Polygon rendering is one of the most prominent
techniques used in the flight-simulation industry and
becoming very popular among PC games as the speed of
PCs increases.
The computational expense of rendering solid polygonbased worlds is high, but since we are making games and
not modeling packages or military-quality flight
simulators, we can use tricks and shortcuts to get the
performance we need. The most common examples of polygon-based 3D games are flight simulators
Figure 1- 9
Figure 1- 10Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 16
and racing simulators. For example, the Falcon series from Specturm Holobyte uses polygon-based
graphics to render the world and the planes. It also uses bitmaps in special cases of the game, such as
explosions.
In general, polygon-based graphics are probably going to be either the most successful method of
rendering 3D games or come in a close second. Solid polygon worlds with texture mapping produce
startlingly real images, and this technology has already been used in some of the most successful video
games.
Ray Casting
Ray casting is based on ray tracing, which is a
method of rendering three-dimensional worlds by
modeling the interaction of light with the geometry
of the world. This method of rendering is one of the
most realistic to date. Ray casting, on the other
hand, is simply a subset of this technique that is
used to render special types of worlds. Ray casting
is used in Wolfenstein 3D, by id Software, to create
a realistic looking textured environment that moves
quickly, as shown in Figure 1-11.
Ray casting works by casting out a collection of
mathematical rays (one for each column on the
screen) from the player's virtual viewpoint and
recording the intersections of the objects in the
world (which are usually flat walls on a cube).
Based on these collisions, the final view is
generated by using the distance between the
player's viewpoint along with the point of the
collisions to render thin vertical strips of texture
(one for each column). This process is shown in
figure 1-12.
Voxel Graphics
Voxel graphics is a bit of a misnomer that I think the originator (Nova Logic) isn't going to bother
correcting because they don't want the whole world knowing exactly how it works! It is more of a data
structure and mathematical representation of a volume using voxels than a technique. The world voxel
itself comes from volume and pixel. Voxels are 3D entities that are cubic in nature and fill space. Each
Figure 1- 11
Figure 1- 12Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 17
voxel has eight neighbors, which are usually connected
using some kind of data structure, as shown in 1-13.
Well, that's all fine and dandy, but whatever voxel graphics
really is, isn't important to game makers. At this point, in
the context of game development, it means using a
collection of single pixels or simple lines to generate a 3D
view. These views are mostly of terrain; hence voxel
graphics are best suited for making games that are in some
kind of outside environment.
The basic technique behind voxel rendering is as follow: A
height map is generated (or input from a database) in the
form of a 2D matrix of integers. Each element in the matrix
is the height above sea level or
the "floor," as shown in Figure 1-
14. Then a rendering engine uses
this data and the perspective
transforms (we'll get to that
later) to draw the voxel data line
by line, starting from the horizon
and ending at the viewpoint of
the player. While the rendering is
being done, the voxels are either
shaded, using a light source, or
colors, using a database. it's even
possible to texture them, but the
results can be quite distorted. A
groundbreaking voxel-based
game is Commanche, by Nova Logic, which allows a helicopter pilot to fly around a mountain range and
shoot down enemies. The environment of the game was generated using voxel graphics, and the
enemies were done with bitmap scaling; so you see that sometimes techniques are mixed to create the
best overall game.
Ellipsoidal Technology
Using ellipsoids is a relatively new technology somewhere
between polygon graphics and voxel graphics. Ellipsoids are
similar to spheres except that they can be elongated in each
directions X, Y, or Z. Figure 1-15 shows an example of an
ellipsoidal man. The attractive feature of using small
ellipsoids to generate a 3D world is that ellipsoids are convex
Figure 1- 13
Figure 1- 14
Figure 1- 15Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 18
objects (have no dents), and this makes hidden surface removal easier. Also, ellipsoids are very regular
and symmetrical, and this can be used to make certain optimizations during rendering. Finally,
ellipsoidal games tend to have a natural look when couples with advanced shading techniques.
Journey into the Mind's Eye
Well, well well... Now that we have acquanted ourselves with the origins and techniques of
Cybersorcery, it's time to talk about why you are reading this book. You are reading this book to learn
how to create 3D video games. Within these pages you will find the magick and sorcery to do this, but
there is something else that you need in order to create games. Something that cant' be taught. This is
creativity. Everyone is creative; the problem is allowing yourself to be creative with all the pressures of
everyday life on your mind.
Allowing yourself to be creative is the single most important thing you need to learn about writing video
games. Cyber sorcerers are a unique group of people. They believe in the impossible and look at video
games as a form of expression. Make no doubt, a video game is apiece of art. But, unlike a painting that
is static and unlike a song that is only heard, a video game is in flux, it is art in motion. To get your
creative juices flowing, here are some suggestions:
Play lots of games and try to determine what makes them fun and addictive.
Read science fiction and fantasy novels.
Rent some science fiction movies and, especially, some Japanese animated films (lots of good
ideas in them).
Don't limit yourself to reality; remember, anything is possible in cyberspace.
When writing your games don't think that something can't be done. Just assume its possible and
then figure it out.
When trying to figure out what people like, think in terms of primal needs. Use analogies of the
needs as goals in your games.
When you work, surround yourself with interesting imagery, books, and music. They will help
you make contact with your inner creativity.
Finally, keep the lights on, because things are going to get really weird!
The Black Box
The main goal of this book is to teach you how to create 3D games on the PC. As we near this goal,
chapter by chapter, we will be creating many functions that will be used to produce the final game
library, called the Black Box. Within the Black Box will be all the sorcery needed to generate 3D worlds,
play music, obtain input, and so forth. To produce this library in an organized manner, we're going to
create a module in each chapter (if there are any programs in the respective chapter) and then add each
module to the main library as the book proceeds. Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 19
We will name each module with the prefix BLACK followed by the number of the chapter. For example,
the module for Chapter 3 will be named BLACK3.C, and if there is a header file, it will be named
BLACK3.H. By the end of the book you will have a collection of these modules that together form the
foundation of the 3D game library. Also, as the chapters proceed, you should build a library that
contains the modules up to that point. Name the library BLACKLIB.LIB and build it in the Microsoft
Library Manager or, if you are using Borland's compiler, include each module in the current project.
Then instead of individually linking all the modules from each chapter, you can simply link to the
growing library, BLACKLIB.LIB.
As far as compiler selection goes, you can use anything you like, but I suggest Microsoft or Borland
compilers. The code for this book was developed and compiled using Microsoft C/C++ 7.0, but to be fair,
there are Borland 4.5 versions of everything on the CD. However, the listing in the book are the
Microsoft versions. The following Microsoft compile line was used to create most of the objects:
CL -C -AM -G2 -Gs -Zi -W4 FILENAME.C
Here are the meanings of the compiler options:
-C : This instructs the compiler not to invoke the linker.
-AM : Use the MEDIUM memory model, which has one 64K data segment and multiple 64K code
segments.
-G2 : This allows 80286 instructions in inline assembly language and also tells the compiler to
use the 80286 instruction set when compiling programs.
-Gs : This removes stack probes. Stack probes are a run-time stack testing system that makes
sure there's enough space on the stack to allocate the variable for a function before calling the
function. This is an unnecessary waste of time since we will make sure the stack is big enough by
setting its size during the linking process.
-Zi : This directive is used to allow the Codeview debugger, or any other Codeview-compatible
debugger, to have access to the symbol table and source of the program. It inserts debugger
information into the final executable, making it a bit larger and slower.
-W4 : This turns the warning level up to maximum and will flag everything as a warning. We will
ignore most of the warnings, but it's nice to be aware of every little potential problem in
programs.
The compiler directives should all seem reasonable to you except the inclusion of debugger information
and the MEDIUM memory model. The debugger information is needed only during development, and
you should recompile everything when you are ready to generate the final version of your game(s) A
good idea is to have multiple batch files or make files that compile with and without the debugger Black Art of 3D Game Programming
Copyright 2006 Andre LaMothe 20
information inserted into the executables. This way you can quickly create a final executable once you
have found all the bugs.
We will be using the MEDIUM memory model for two reasons. First, the data segment will always be
accessible to the DS register, thus making assembly language interfacing and variable access simple.
Second, if we need more than one 64k data segment, we will use the memory allocation fuctions to
allocate the memory from the FAR heap. In general, SMALL or MEDIUM are the best memory models to
write games in when working with DOS, but for this book we will use the MEDIUM model.
After you have compiled each module and are ready to link it to your program, or one of the programs
in the book that use the game library, you will need to invoke the linker. The link line that I use for
Microsoft's Segment Executable Linker is as follows:
LINK /ST:8192 /CO SOURCE.OBJ+OBJECTS.OBJ,,,BLACKLIB..LIB,,
This informs the linker to link SOURCE.OBJ with OBJECTS.OBJ (optional) and link to the library
BLACKLIB.LIB. Also, the stack is set to 8192 BYTES (/ST:8192), and the linker is told to add in the
debugger information (/CP).
If you use the preceding compile and link lines, you should have no trouble getting everything to work.
However, just to make sure, the CD includes the compiled version of each chapter's module, along with
all C programs compiled into executable, along with a version of the game library containing each
chapter's module up to that point of the book. For example, in the directory for Chapter 5, you would
find all the source and executable for that chapter, the library module BLACK5.C, and BLACK5.OBJ.
Finally, there will be a partial version of the game library that has all the modules from chapters 1
through 5 within it.
Summary
Within the pages of this chapter we discussed the source of all games and the techniques used
throughout the years to make games more and more realisitc. Then we covered the most popular
techniques used today and selected polygon-based graphics as our chosen Cybersorcery. Finally, we
describe the Black Box game library, which we will construct as the days pass. With all that in mind, you
are now an apprentice Cybersorcerer. Turn to the next chapter and open your mind: we are about to
embark on a most excellent adventure...