Graphics Programming Black Book. ( Coriolis Group Books )

Graphics Programming Black Book. ( Coriolis Group Books )

Now pay Easier and Secure using Paypal

Read more

Michael Abrash


Albany, NY Belmont, CA Bonn Boston Clnclnnatl Detrolt Johannesburg London

Madrld Melbourne Mexlco C I N~ew York Paris Slngapore Tokyo Toronto Washlngton

e-books shop
Graphics Programming Black Book Special Edition

Because this bookw as written over many yearsi, n many different settings, an unusually
large number of people have played a part in making this book possible.
First and foremost, thanks (yet again) to Jeff Duntemann for getting this book
started, doing the dirty work, and keeping things on track and everyone’s spirits
up. Thanks to Dan Illowsky for not only contributing ideas and encouragement,
but also getting me started writing articles long ago, when I lacked the confidence
to do it on my own-and for teaching me how to handle the business end of
things. Thanks to Will Fastie for giving me my first crack at writing for a large
audience in the long-gone but still-missed PC Tech Journal, and for showing me
how much fun it could be in his even longer-vanished but genuinely terrific column
in Creative Computing (the most enjoyable single columnI have ever read in a
computer magazine; I used to haunt the mailbox around the beginning of the
month just to see what Will had to say). Thanks to Robert Keller, Erin O’Connor,
Liz Oakley, Steve Bakaern, d the rest of the cast oft housands that made PJa uniquely
fun magazine-especially Erin, who did more than anyone to teach me the proper
use of English language. (To this day, Erin will still patiently explain to me when
one should use “that” andw hen one should use “which”e ven though eight years
of instruction on this and related topics have left no discernible imprint on my
brain.) Thanks toJ on Erickson, Tami Zemel, Monica Berga,n d ther est of the DDJ
crew for excellent, professional editing, and forjusbt eing great people. Thanks to
the Coriolis gangf or their tireless hard work: JefDf untemann andK eith Weiskamp
on the editorial and publishing side, and Brad Grannis, Rob Mauhar, and Kim
Eoffwho handled art,d esign, and layout. Thanks to JiMm ischel who did a terrific
job testing code for the book and putting the code disk together. Thanks to Jack
Tseng, for teaching me a lot about graphics hardware, and even more about how
much difference hard work can make. Thanks J tooh n Cockerham, David Stafford,
Terje Mathisen,t he BitMan, Chris Hecker, Jim Mackraz, MeLlvainft te, JohnN avas,
Phil Coleman, Anton TruenfeJlosh, n Carmack,J ohn Miles,J ohn Bridges, Jim Kent,
Hal Hardenberg, Dave Miller, Steve Levy, Jack DaviDs, uane Strong, Daev Rohr, Bill
Weber, Dan Gochnauer, Patrick Milligan, Tom Wilson, the people in the ibm.pc/
fast.code topic on Bix, and all the rest of you who have been so generous with your
ideas and suggestions. I’ve done my best to acknowledge contributors by name in
this book, but if your name is omitted, my apologies, and consider yourself thanked;
this book could not have happened without you. And, of course, thanks to Shay and
Emily for their generous patience with my passion for writing and computers.
And, finally, thanks to the readers of my articles and to you, the reader of this
book. You are, after all, the ultimate reason why I write, and I hope you learn as
much and have as much fun reading this book as I did writing it!
Michael Abrash (
Bellevue, Washington, 1997


What was it like working with John Carmack on Quake? Like being strapped
onto a rocket during takeoff-in the middle of a hurricane. It seemed like
the whole world was watching, waiting to see if id Software could top Doom;
every casual e-mail tidbit or conversation with a visitor ended up posted on
the Internet within hours. And meanwhile, we were pouring everything we
had into Quake’s technology; I’d often come inin the morning to find John
still there, working on an ew idea so intriguing that he couldn’t betaor sleep
until he had tried it out. Toward the end, when I spent most of my time
speeding things up, wI ould spend the day in a trance writing optimized assembly
code, stagger out of the Town East Tower into the blazing Texas heat,
and somehowd rive home on LBJ Freeway without smacking into anyo f the
speeding pickups whizzing past me on both sides. At home, I’d fall into a
fitful sleep, then come back the next day in a daze and do it again. Everything
happeneds o fast, and unders o much pressure, that sometimIe ws onder
how any of us made it through that without completely burning out.
At the same time, of course, it was tremendously exciting. John’s ideas were
endless and brilliant, and Quake ended up establishing a new standard for
Internet and first-person 3-D game technology. Happily, id has an enlightened
attitude about sharing informationw, aasn wdi lling to let mew rite about
the Quake technology-both how it worked and how it evolved. Over the two
years I workeda t id, wI rote a number of columns about Quake in0 7: Dobb’s
Sourcebook, as well as a detailed overview for the 1997 Computer Game Developers
Conference. You can find these in the latter part of this book; they
represent a rare look into the development and inner workings of leadingedge
software development, andI hope you enjoy reading thema s much as I
enjoyed developing the technology and writing about it.

The rest of this book is pretty much everything I’ve written over the past
decade about graphics and performance programming thsatitl’ls r elevant to
programming today, and that covers a lot of ground. Most of Zen of Ch-aphics
Programming, 2nd Edition is in there (and the rest is on the CD) ; all of Zen of
Code Optimization is there too, and even my 1989 book Zen of Assembly Lan
p a g e , with its long-dated 8088 cycle counts but a lootf useful perspectives,i s
on theC D. Add to that them ost recent 20,000 words of Quake material, and
you have most of what I’ve learned over the past decade in one neat package.
I’m delighted to have all this material in printi n a single place, because over
the past ten years I’ve run into a lot of people who have found my writings
useful-and a lot morew ho would like to read them, but couldn’t find them.
It’s hard to keep programming material (especially stuff that started out as
columns) in print forv ery long, andI would like to thank The Coriolis Group,
and particularly my good friend Jeff Duntemann (without whom not only
this volume but pretty much my entire writing career wouldn’t exist), for
helping me keep this material available.

I’d also like to thank Jon Erickson, editor of 07: Dobb’s, both for encouragement
and general good cheer and fogri ving me a place to write whatever I
wanted about realtime 3-D. It still amazes me that I was able to find time to
write a column every two months during Quake’s development, and if Jon
hadn’t made isto easy and enjoyable, it coulnde ver have happened.
I’d also like to thank Chris Hecker and Jennifer Pahlka of the Computer
Game DevelopersC onference, withouwt hose encouragement, nudging, and
occasional well-deserved nagging there is no chance I would ever have written
a paper for the CGDC-a paper that ended up being the most
comprehensive overview of the Quake technology thate’vs er likely to be written,
and which appears in these pages.

I don’t have much else to say that hasn’t already been said elsewhere in
this book, in one of the introductions to the previous volumes or in one
of the astonishingly large number of chapters. As you’ll see as you read,
it’s been quite a decade for microcomputer programmers, Ia nhadv e been
extremely fortunate to not only be a paorft it, but to be able to chronicle part of it as well.
And the next decade is shaping up to be just as exciting!
Michael Abrash
Bellevue, Washington
May 1997


e-books shop

Purchase Now !
Just with Paypal

Product details
 File Size
 113,114 KB
 1262 p
 File Type
 PDF format
 1997 by The Coriolis Group, Inc 

Foreword xxxi
Introduction xxxiii
Part I
Chapter 1 The Best Optimizer Is between Your Ears
The Human Element of Code Optimization 5
Understanding High Performance 6
Rules for Building High-Performance Code 7
When Fast Isn't Fast 6
Know Where You 're Going 8
Make a Big Map 8
Make Lots of Little Maps 8
Know the Ta'tory 12
Know When It Matters 13
Always Consider the Alternatives 14
Know How to Turn On the Juice 16
Where We've Been, What We've Seen 19
' Where We're Going 19
Chapter 2 A World Apart
The Unique Nature of Assembly
Language Optimization 23
Instructions: The Individual versus
the Collective 23
Assembly Is Fundamentally Different 25
Transfwmation Inefficiencies 25
Self-Rliance 27
Knowledge 2 7
The Flexible Mind 28
Where to Begm ? 30
Chapter 3 Assume Nothing 
Understanding and Using the Zen Timer 33
The Costs of Ignorance 34
The Zen Timer 35
The Zen Timer Is a Means, Not an End 42
Starting the Zen Timer 43
Time and the PC 43
Stopping the Zen Timer 46
Reporting Timing Results 47
Notes on the Zen Timer 48
A Sample Use of the Zen Timer 49
The Long-Period Zen Timer 53
Example Use of the Long-Period Zen Timer 66
Using the Zen Timer from C 69
Stopping the Clock 54
Watch Out for Optimizing Assemblers! 71
Further Reading 72
Armed with the Zen Timq Onward and Upward 72
Chapter 4 In the Lair of the Cycle-Eaters
How the PC Hardware Devours
Code Performance 77
Cycle-Eaters 78
The Nature of Cycle-Eaters 78
The 8-Bit Bus Cycle-Eater 79
The 8088’s Ancestral Cycle-Eaters 79
The Impact of the 8-Bit Bus Cycle-Eater 82
What to Do about the 8-Bit Bus Cycle-Eater? 83
The Prefetch Queue Cycle-Eater 86
Official Execution Times Are Only Part of the Story 87
There Is No Such Beast as a True Instruction Execution Time 88
Approximating Overall Execution Times 93
What to Do about the Prefetch Queue Cycle-Eater? 93
Holding Up the 8088 94
Dynamic RAM Refresh: The Invisible Hand 95
How DRAM Refresh Works in the PC 95
The Impact of DRAM Refresh 97
What to Do About the DRAM Refresh Cycle-Eater? 98
Wait States 99
The Display Adapter Cycle-Eater 101
The Impact of the Display Adapter Cycle-Eater 104
What to Do about the Display Adapter Cycle-Eater? 107
Cycle-Eaters: A Summary 108
What Does It All Mean? 108
Chapter 5 Crossing the Border
Searching Files with Restartable Blocks 113
Avoiding the String Trap 115
Brute-Force Techniques 115
Using memchr() 116
Interpreting Where the Cycles Go 121
Always Look Where Execution Is Going 123
Searching for Text 11 4
Making a Search Restartable 11 7
Knowing When Assembly Is Pointless 122
Chapter 6 Looking Past Face Value
How Machine Instructions May Do More Than
You Think 127
Memory Addressing and Arithmetic 128
Math via Memory Addressing 130
Multiplication with LEA Using Non-Powers
The Wonders of LEA on the 386 131
ofTwo 132
Chapter 7 Local Optimization
Optimizing Halfway between Algorithms
and Cycle Counting 137
When LOOP Is a Bad Idea 138
The Lessons of LOOP and JCXZ 139
Avoiding LOOPS of Any Stripe 140
Local Optimization 140
Unrolling Loops 143
Rotating and Shzfing with Tables 145
NOTFlips Bits-Not Flags 146
Incrementing with and without Carry 147
Chapter 8 Speedin Up C with Assem1 ly Language
Jumping Languages When You Know
It’ll Help 151
Billy, Don’t Be a Compiler 152
Don’t Call Your Functions on Me, Baby 153
Stack Frames Slow So Much 153
Torn Between Two Segments 154
Taking It to the Limit 155
A GteAssembly Case Study 156
Why Speeding Up Is Hard to Do 154
Chapter 9 Hints My Readers Gave Me
Optimization Odds and Ends fiom
the Field 169
Another Look at LEA 170
The Kennedy Portfolio 171
Speeding Up Multiplication 173
Optimizing Optimized Searching 174
Shmt Sorts 180
Full 32-Bit Division 181
Sweet Spot Revisited 184
Hard-core Cycle Counting 185
Hardwired Far Jumps 186
Setting 32-Bit Registers: Time versus Space 187
Chapter 10 Patient Coding, Faster Code
How Working Quickly Can Bring Execution
to a Crawl 191
The Case f m Delayed Gratification 192
The Brute-Force Syndrome 193
Wasted Breakthroughs 196
Recursion 199
Patient Optimization 200
Chapter 1 1 Pushing the 286 and 386
New Registers, New Instructions, New Timings,
Family Matters 208
Crossing the Gulf to the 286 and the 386 208
In the Lair of the Cycle-Eaters, Part I1 209
New Complications 207
System Wait States 210
Data Alignment 213
Code Alignment 215
Alignment and the 386 21 8
Alignment and the Stuck 218
The DRAM Refresh Cycle-Eater: Still an Act of God 21 9
The Display Adapter Cycle-Eater 21 9
New Instructions and Features: The 286 221
New Instructions and Features: The 386 222
Optimization Rules: The More Things Change ... 223
Detailed Optimization 223
popf and the 286 225
Chapter 12 Pushing the 486
It’s Not Just a Bigger 386 235
Rules to Optimize By 236
Enter the 486 236
The Hazards of Indexed Addressing 23 7
Calculate Memory Pointers Ahead of Time 238
Caveat Programmor 241
Stack Addressing and Address Pipelining 241
Problems with Byte Regasters 242
More Fun with Byte Registers 244
Timing Your Own 486 Code 245
The Story Continues 246
Chapter 13 Aiming the 486
Pipelines and Other Hazards of the
High End 249
Chapter 14
Chapter 15
Chapter 16
486 Pipeline Optimization 250
BSWAP: More Useful Than You
Pushing and Popping Memory 254
Optimal 1-Bit Shifts and Rotates 255
32-Bit Addressing Modes 256
Might Think 252
Boyer-Moore String
Searching 259-
Optimizing a Pretty Optimum Search
String Searching Refresher 262
The Boyer-Moore Algorithm 263
Boyer-Moore: The Good and the Bad 266
Further Optimization of Boyer-Moore 274
Algorithm 261
Know M a t You Know 277
Linked Lists and
Unintended Challenges 279
Unfamiliar Problems with Familiar
Linked Lists 282
Dummies and Sentinels 285
Circular Lists 288
Hi/Lo in 24 Bytes 292
Data Structures 281
There Ain't No Such Thing as the
Fastest Code 295
Lessons Learned in the Pursuiotf
Counting Words in a Hurry 298
Challenges and Hazards 305
the Ultimate Word Counter 297
Which Way to G o b m Here? 302
Blinding Yourself to a Better Abtmach 306
Watch Out for Luggable Assumptions! 306
The Astonishment of Right-Brain
Optimization 307
Levels of Optimization 312
Optimization Level 1: Good Code 312
Level 2: A New Perspective 315
Level 3: Breakthrough 31 6
Enough Word Counting Already! 31 9
Chapter 1 7 The Game of Life
The Triumph of Algorithmic Optimization
Conway’s Game 324
Where Does the Time Go? 329
The Hazards and Advantages of
Heavy-Duty C t t Optimization 336
Bringing In the Right Brain 338
in a Cellular Automata Game 323
The Rules of the Game 324
Abstraction 330
&-Examining the Task 338
Acting on What We Know 340
The Challenge That Ate My Life 346
Chapter 18 It‘s a Wonderful Life
Optimization beyond the Pale 349
Breaking the Rules 350
Table-Driven Magic 351
Keeping Track of Change with a
Change List 363
A Layperson S Overview of QLIFE 366
Chapter 19 Pentium: Not the Same Old Song
Learning a Whole Different Set of
The Return of Optimization as Art 372
Optimization Rules 371
The Pentium: An Overview 373
Crossing Cache Lines 373
Cache Organization 374
Faster Addressing and More 375
Branch Prediction 37’7
Miscellaneous Pentium Topics 378
486 versus Pentium Optimization 378
Going Superscalar 379
Chapter 20 Pentium Rules
How Your Carbon-Based Optimizer Can
Put the “Super” in Superscalar 383
An Instruction in Every Pipe 384
V-Pipe-Capable Instructions 386
Lockstep Execution 390
Superscalar Notes 394
Register Starvation 395
Chapter 21 Unleashing the Pentium’s V-pipe
Focusing on Keeping Both
Pentium Pipes Full 399
Address Generation Interlocks 400
Register Contention 403
Who’s in First? 405
Pentium Optimization in Action 406
Exceptions to Register Contention 404
A Quick Note on the 386 and 486 41 1
Chapter 22 Zennin Flexib9 e a Mndin tdhe
Taking a Spin through What
Zenning 41 5
You’ve Learned 415
Chapter 23 Bones and Sinew
At the Very Heart of Standard PC
The VGA 426
An Introduction to VGA Programming 427
At the Core 427
Graphics 425
Linear Planes and True VGA Modes 430
Smooth Panning 441
Color Plane Manipulation 443
Page Flipping 444
The Hazards of VGA Clones 446
Just the Beginning 447
The Macro Assembler 447
Chapter 24 Parallel Processing with the VGA
Taking on Graphics Memory Four Bytes
VGA Programming: ALUs and Latches 451
Notes on the ALU/Latch Demo
at a Time 451
Program 458
Chapter 25 VGA Data Machinery
The Barrel Shifter, Bit Mask, and
Set/Reset Mechanisms 463
VGA Data Rotation 463
The Bit Mask 464
The VGA’s Set/Reset Circuitry 471
Setting All Planes to a Single Color 4 73
Manipulating Planes Individually 476
Notes on Set/Reset 478
A Brief Note on Word OUTS 4’79
Chapter 26 VGA Write Mode 3
The Write Mode That Grows on You 483
A Mode Born in Strangeness 483
A Note on Preserving Register Bits 496
Chapter 27 Yet Another VGA Write Mode
Write Mode 2, Chunky Bitmaps,
Write Mode 2 and Set/Reset 501
and Text-Graphics Coexistence 501
A Byte’s Progress in Write Mode 2 502
Copying ChunkJ Bitmaps to VGA Memory Using
Drawing Color-Patterned Lines Using Write Mode 2 509
Write Mode 2 504
When to Use Write Mode 2 and When
Mode 13H--320x200 with 256 Colors 515
Flipping Pages from Text to Graphics
to Use Set/Reset 515
and Back 515
Chapter 28 Reading VGA Memory
Read Modes 0 and 1, and the Color Don’t
Read Mode 0 525
Read Mode 1 531
When all Planes “Don’t Care” 534
Care Register 525
Chapter 29 Saving Screens and Other VGA Mysteries
Useful Nuggets from the VGA Zen File 541
Saving and Restoring EGA and
VGA Screens 541
16 Colors out of 64 548
Overscan 555
A Bonus Blanker 556
Modifying VGA Registers 558
Chapter 30 Video Est Omnis Divisa
The Joys and Galling Problems of Using Split
How the Split Screen Works 563
Screens on the EGA and VGA 563
The Split Screen in Action 565
VGA and EGA Split-Screen Operation Don’t Mix 572
Setting the Split-Screen-Related Registers 573
The Problem with the EGA
Split Screen and Panning 574
Notes on Setting and Reading Registers 582
Split Screens in Other Modes 584
How Safe? 585
Split Screen 573
l h e Split Screen and Horizontal Panning: An Example 5 75
Chapter 31 Higher 256-Color Resolution on the VGA
When Is 320x200 Really 320~400? 589
Why 320x200? Only IBM Knows for Sure 590
320x400 256-Color Mode 590
Display Memory Organization in 320x400 Mode 591
Reading and Writing Pixels 593
Two 256-Color Pages 600
Something to Think About 605
Chapter 32 Be It Resolved: 360x480
Taking 256-Color Modes About as Far as the
Extended 256-Color Modes: What’s
360x480 256-Color Mode 611
How 360x480 256-Color Mode Works 619
Standard VGA Can Take Them 609
Not to Like? 610
480 Scan Lines per Screen: A Little Sloweq
360 Pixels per Scan Line: No Mean Feat 620
Accessing Display Memory in 360x480 256-Color Mode 621
But No Big Deal 61 9
Chapter 33 Yogi Bear and Eurythmics Confront VGA Colors
The Basics of VGA Color Generation 625
VGA Color Basics 626
The Palette RAM 626
TheDAC 626
Color Pagmg with the Color Select Register 628
256-color Mode 629
Setting the Palette RAM 629
Setting the DAC 630
If You Can’t Call the BIOS, Who Ya
An Example of Setting the DAG 632
Gonna Call? 631
Chapter 34 Changing Colors without Writing Pixels
Special Effects through Realtime Manipulation
Color Cycling 639
The Heart of the Problem 640
of DAG Colors 639
Loading the DAC via the BIOS 641
Loading the DAC Directly 642
A Test Program for Color Cycling 643
Color Cycling Approaches that Work 649
Odds and Ends 651
The DAC Mask 651
Reading the DAC 651
Cycling Down 652
Chapter 35 Bresenham Is Fast, and Fast Is Good
Implementing and Optimizing Bresenham’s
The Task at Hand 656
Bresenham’s Line-Drawing Algorithm 657
An Implementation in C 661
Line-Drawing Algorithm 655
Strengths and Weaknesses 660
Looking at EVGALine 665
Drawing Each Line 668
Drawing Each Pixel 669
Comments on the C Implementation 670
Bresenham’s Algorithm in Assembly 671
Chapter 36 The Good, the Bad, and the Run-Sliced
Faster Bresenham Lines with Run-Length
Run-Length Slice Fundamentals 683
Run-Length Slice Implementation 685
Run-Length Slice Details 687
Slice Line Drawing 681
Chapter 37 Dead Cats and Lightning Lines
Optimizing Run-Length Slice Line Drawing
Fast Run-Length Slice Line Drawing 698
in a Major Way 697
How Fast Is Fast? 704
Further Optimizations 705
Chapter 38 The Polygon Primeval 
Drawing Polygons Efficientlya nd
Filled Polygons 710
How Do You Fit Polygons Together? 712
Filling NonOverlapping Convex Polygons 713
Oddball Cases 721
Quickly 709
Which Side Is Inside? 71 0
Chapter 39 Fast Convex Polygons
Filling Polygons in a Hurry 725
Fast Convex Polygon Filling 726
Fast Drawing 727
Fast Edge Tracing 730
The Finishing Touch: Assembly Language 732
Faster Edge Tracing 735
Maximizing REP STOS 735
Chapter 40 Of Songs, Taxes, and the Simplicity of Complex Polygons
Dealing with Irregular Polygonal Areas 741
Filling Arbitrary Polygons 742
Complex Polygon Filling: An
Active Edges 742
Implementation 750
More on Active Edges 753
Performance Considerations 753
Nonconvex Polygons '755
Details, Details 755
Chapter 41 Those Wa -Down Polygon Nomenc r ature Blues
Names Do Matter when You Conceptualize
Nomenclature in Action 760
a Data Structure 759
Chapter 42 Wu‘ed in Haste; Fried, Stewed at Leisure
Fast Antialiased Lines Using Wu’s Algorithm 775
Wu Antialiasing 776
Tracing and Intensity in One 778
Sample Wu Antialiasing 782
Notes on Wu Antialiasing 791
Chapter 43 Bit-Plane Animation
A Simple and Extremely Fast Animation
Bit-Planes: The Basics 796
Bit-Plane Animation in Action 801
Limitations of Bit-Plane Animation 81 1
Shearing and Page Flipping 813
Beating the Odds in thJea w-
Method for Limited Color 795
Stacking the Palette Regsters 799
Dropping Contest 814
Chapter 44 Split Screens Save the Page Flipped Day
640x480 Page Flipped Animation in
A Plethora of Challenges 819
A Page Flipping Animation Demonstration 820
64K.. .Almost 8 19
Write Mode 3 831
Drawing Text 832
Page Flipping 833
Knowing When to Flip 835
Enter the Split Screen 836
Chapter 45 Dog Hair and Dirty Rectangles
Different Angles on Animation 841
Plus Ca Change 842
Chapter 46 VGA Access Times
Dirty-Rectangle Animation 844
Dirty Rectangles in Action 846
Hi-Res VGA Page Flipping 851
Another Interesting Twist on Page Flipping 855
So w h y Not Use Page Flipping? 846
Who Was that Masked
Image? 859
Optimizing Dirty-Rectangle Animation 861
Dirty-Rectangle Animation, Continued 862
Masked Images 871
Internal Animation 872
Drawing Order and Visual Quality 873
Dirty-Rectangle Management 872
Chapter 47 Mode X: 256-Color VGA Magic
Introducing the VGA’s Undocumented
“Animation-Optimal” Mode 877
What Makes Mode X Special? 878
Selecting 320x240 256-Color Mode 879
Designing from a Mode X Perspective 885
Hardware Assist from an Unexpected
Quarter 889
Chapter 48 Mode X Marks the Latch
The Internals of Animation’s Best Video
Allocating Memory in Mode X 903
Copying Pixel Blocks within Display
Display Mode 897
Memory 905
Copying to Display Memory 908
Who Was that Masked Image Copier? 91 1
Chapter 49 Mode X 256-Color Animation
How to Make the VGA Really Get up
Masked Copying 915
and Dance 915
Faster Masked Copying 91 8
Notes on Masked Copying 923
Animation 924
Mode X Animation in Action 924
Works Fast, Looks Great 930
Chapter 50 Adding a Dimension
3-D Animation Using Mode X 933
References on 3-D Drawing 934
The 3-D Drawing Pipeline 935
Projection 93 7
Translation 9? 7
Rotation 9?8
A Simple 3-D Example 939
An Ongoing Journey 949
Notes on the 3-D Animation Example 948
Chapter 51 Sneakers in Space
Using Backface Removal to Eliminate
One-sided Polygons: Backface Removal 954
Incremental Transformation 964
A Note on Rounding Negative Numbers 966
Object Representation 96’7
Hidden Surfaces 953
Backface Removal in Action 957
Chapter 52 Fast 3-D Animation: Meet X-Sharp
The First Iteration of a Generalized
3-D Animation Package 971
This Chapter’s Demo Program 972
A New Animation Framework: X-Sharp 984
Three Keys to Realtime Animation
Performance 985
Drawbacks 986
Where the Time Goes 987
Chapter 53 Raw Speed and More
The Naked Truth About Speed in
Raw Speed, Part 1: Assembly Language 992
Raw Speed, Part 11: Look it Up 999
3-D Animation 991
Hidden Surfaces 1000
Rounding 1002
Having a Ball 1003
Chapter 54 3-D Shading
Putting Realistic Surfaces on Animated
Support for Older Processors 1007
Shading 1023
3-D Objects 1007
Ambient Shading 1023
Diffuse Shading 1023
Shading: Implementation Details 1027
Chapter 55 Color Modeling in 256-Color Mode
Pondering X-Sharp’s Color Model in an
A Color Model 1034
A Bonus from the BitMan 1039
RGB State of Mind 1033
Chapter 56 Pooh and the Space Station
Using Fast Texture Mapping to Place Pooh
on a Polygon 1047
Principles of Quick-and-Dirty Texture
Mapping 1048
Mapping Textures Made Easy 1049
Notes on DDA Texture Mapping 1052
Fast Texture Mapping: An
Implementation 1053
Chapter 57 10,000 Freshly Sheared Sheep on the Screen
The Critical Role of Experience in Implementing
Fast, Smooth Texture Mapping 1063
Visual Quality: A Black Hole ... Er, Art 1064
Fixed-point Arithmetic, Redux 1064
Texture Mapping: Orientation
Mapping Textures across Multiple
Independence 1065
Polygons 1068
Fast Texture Mapping 1068
Chapter 58 Heinlein's Crystal Ball, 
Spock's Brain, and the 9-Cycle Dare
Using the Whole-Brain Approach to
Texture Mapping Redux 1080
Accelerate Texture Mapping 10'79
Left-Brain Optimization 1081
A 90-Degree Shift in Perspective 1084
That's Nice-But it Sure as Heck
Ain't 9 Cycles 1086
Don 't Stop Thinking about Those Cycb 1091
Texture Mapping Notes 1092
Chapter 59 The Idea of BSP Trees 
What BSP Trees Are and How to
Walk Them 109'7
BSP Trees 1098
Visibility Determination 1099
Limitations of BSP Trees 11 00
Building a BSP Tree 1101
Inorder Walks of BSP Trees 1107
Visibility Ordm’ng 11 04
Know It Cold 1109
Measure and Learn 11 11
Surfing Amidst the Trees 11 13
Related Reading 11 14
Chapter 60 Compiling BSP Trees
Taking BSP Trees from Concept
Compiling BSP Trees 11 19
to Reality 11 17
Parametric Lines 11 19
Parametric Line Cliplbing 1121
The BSP Compiler 11 23
Optimizing the BSP Tree 11 28
BSP Optimization: an Undiscovered
Country 1 129
Chapter 61 Frames of Reference
The Fundamentals of the Math behind 3-D
Graphics 1133
3-D Math 11 34
Foundation Dejnitions 1134
The Dot Product 1135
Cross Products and the Generationo f
Using the Sign of the Dot Product 1140
Using the Dot Product for Projection 1141
Dot Products of Unit Vectors 1136
Polygon Normals 1 137
Rotation by Projection 11 43
Chapter 62 One Story, Two Rules, and a BSP Renderer
Taking a Compiled BSP Tree from Logical to
BSP-based Rendering 1148
The Rendering Pipeline 1157
Visual Reality 1147
Moving the Viewer 1157
Transformation into Viewspace 1158
Clipping 1158
Projection to Screenspace 1159
Walking the Tree, Backface Culling and Drawing 11 60
Notes on the BSP Renderer 1162
Chapter 63 Floating-Point for Real-Time 3-D
Knowing When to Hurl Conventional Math
Not Your Father’s Floating-point 1167
Pentium Floating-point Optimization 1167
Wisdom Out the Window 1165
Pipelining, Latenq, and Throughput 11 68
FXCH 1169
The Dot Product 1170
The Cross Product 1171
Transformation 11 72
Projection 11 74
Rounding Control 11 74
A Farewell to 3-D Fixed-point 1175
Chapter 64 Quake’s Visible-Surface Determination
The Challenge of Separating All Things Seen
from All Things Unseen 1179
VSD: The Toughest 3-D Challenge
The Structure of Quake Levels 1181
Culling and Visible Surface
ofAll 1180
De termination 1 18 1
Nodes Inside and Outside the Vim Frustum 11 83
Overdraw 1 184
The Beam Tree 1 185
3-D Engine du Jour 1186
Subdividing Raycast 11 87
Vntex-Free Surfaces 11 87
The DrawBufer 1 18 7
Span-Based Drawing 1 18 7
Portals 1188
Breakthrough! 1188
Simph.@, and Keep on Trying New Things 1189
Learn Now, Pay Forward 1190
References 1190
Chapter 65 3-D Clipping and Other Thoughts
Determining What’s Inside Your Field
3-D Clipping Basics 1195
Polygon Clipping 1 197
of View 1193
Intersecting a Line Segment with a Plane 11 95
Clipping to the Frustum 1200
The Lessons of Listing 65.3 1206
Advantages of Viewspace Clipping 1207
Further Reading 1208
Chapter 66 Quake’s Hidden-Surface Removal
Struggling with Z-Order Solutions to the
Creative Flux and Hidden Surfaces 12 12
Hidden Surface Problem 12 1 1
Drawing Moving Objects 1212
Performance Impact 1213
Leueling and Improving Performance 1213
Sorted Spans 1214
Edge-Sorting Keys 1220
Edges versus Spans 1215
where That l / Z Equation Comes From 1221
Quake and Z-Sorting 1221
Decisions Defered 1222
Chapter 67 Sorted Spans in Action 
Implementing Independent Span Sorting for
Quake and Sorted Spans 1226
Types of l / z Span Sorting 1228
Rendering without Overdraw 1225
Intersecting Span Sorting 1228
Abutting Span Sorting 1229
Indqbendent Span Sorting 1230
l / z Span Sorting in Action 1230
Implementation Notes 1239
Chapter 68 Quake’s Lighting Model
A Radically Different Approach to Lighting
Polygons 1245
Problems with Gouraud Shading 124 7
Perspective Correctness 1248
Decoupling Lighting from Rasten’zation 1250
Size and Speed 1251
Mipmapping To The Rescue I254
Two Final Notes on Surface Caching 1255
Chapter 69 Surface Cachin and Quake’s Triangle Modes
Letting the Graphics Card Build the Textures 1261
The Light Map as Ayha Texture 1262
Drawing Triangle Models Fast 1263
Trading Subpixel Precision for Speed 1265
An Idea that Didn’t Work 1265
An Idea that Did Work 1266
More Ideas that Might Work 1270
Chapter 70 Quake: 
A Post-Mortem and a Glimpse into the Future
Lighting 1282
Dynamic Lighting 1283
BSP Models 1284
Polygon Models and ZBuffering 1285
The Subdivision Rasterizer 1286
Sprites 1287
Particles 1287
How We Spent Our Summer Vacation:
After Shipping Quake 1287
Ven'te Quake 1287
GLQuake 1288
WinQuake 1290
Quakeworld 1291
Quake 2 1293
Afterword 1297
Index 1299


═════ ═════