Michael Abrash’s Graphics Programming Black Book

Introduction
Foreword
Acknowledgments
Part I
	Chapter 1 – The Best Optimizer Is between Your Ears
		The Human Element of Code Optimization
		Understanding High Performance
		Rules for Building High-Performance Code
		Where We’ve Been, What We’ve Seen
	Chapter 2 – A World Apart
		The Unique Nature of Assembly Language Optimization
		Instructions: The Individual versus the Collective
		Assembly Is Fundamentally Different
		The Flexible Mind
	Chapter 3 – Assume Nothing
		Understanding and Using the Zen Timer
		The Costs of Ignorance
		The Zen Timer
		Time and the PC
		Stopping the Zen Timer
		Reporting Timing Results
		Notes on the Zen Timer
		A Sample Use of the Zen Timer
		The Long-Period Zen Timer
		Example Use of the Long-Period Zen Timer
		Using the Zen Timer from C
	Chapter 4 – In the Lair of the Cycle-Eaters
		How the PC Hardware Devours Code Performance
		Cycle-Eaters
		The Nature of Cycle-Eaters
		The 8-Bit Bus Cycle-Eater
		The Prefetch Queue Cycle-Eater
		Dynamic RAM Refresh: The Invisible Hand
		Wait States
		The Display Adapter Cycle-Eater
	Chapter 5 – Crossing the Border
		Searching Files with Restartable Blocks
		Avoiding the String Trap
		Brute-Force Techniques
		Using memchr()
		Interpreting Where the Cycles Go
		Always Look Where Execution Is Going
	Chapter 6 – Looking Past Face Value
		How Machine Instructions May Do More Than You Think
		Math via Memory Addressing
		Multiplication with LEA Using Non-Powers of Two
	Chapter 7 – Local Optimization
		Optimizing Halfway between Algorithms and Cycle Counting
		The Lessons of LOOP and JCXZ
		Local Optimization
		Unrolling Loops
	Chapter 8 – Speeding Up C with Assembly Language
		Jumping Languages When You Know It’ll Help
		Don’t Call Your Functions on Me, Baby
		Stack Frames Slow So Much
		Torn Between Two Segments
		Taking It to the Limit
	Chapter 9 – Hints My Readers Gave Me
		Optimization Odds and Ends from the Field
	Chapter 10 – Patient Coding, Faster Code
		How Working Quickly Can Bring Execution to a Crawl
		The Brute-Force Syndrome
		Recursion
	Chapter 11 – Pushing the 286 and 386
		New Registers, New Instructions, New Timings, New Complications
	Chapter 12 – Pushing the 486
		It’s Not Just a Bigger 386
		Rules to Optimize By
		Caveat Programmor
		The Story Continues
	Chapter 13 – Aiming the 486
		Pipelines and Other Hazards of the High End
		BSWAP: More Useful Than You Might Think
		Pushing and Popping Memory
		Optimal 1-Bit Shifts and Rotates
		32-Bit Addressing Modes
	Chapter 14 – Boyer-Moore String Searching
		Optimizing a Pretty Optimum Search Algorithm
		String Searching Refresher
		The Boyer-Moore Algorithm
		Boyer-Moore: The Good and the Bad
		Further Optimization of Boyer-Moore
		Know What You Know
	Chapter 15 – Linked Lists and plain Unintended Challenges
		Unfamiliar Problems with Familiar Data Structures
		Linked Lists
		Dummies and Sentinels
		Circular Lists
		Hi/Lo in 24 Bytes
	Chapter 16 – There Ain’t No Such Thing as the Fastest Code
		Lessons Learned in the Pursuit of the Ultimate Word Counter
		Counting Words in a Hurry
		Challenges and Hazards
		The Astonishment of Right-Brain Optimization
		Levels of Optimization
		Level 2: A New Perspective
	Chapter 17 – The Game of Life
		The Triumph of Algorithmic Optimization in a Cellular Automata Game
		Conway’s Game
		Where Does the Time Go?
		The Hazards and Advantages of Abstraction
		Heavy-Duty C++ Optimization
		Bringing In the Right Brain
	Chapter 18 – It’s a plain Wonderful Life
		Optimization beyond the Pale
		Breaking the Rules
		Table-Driven Magic
		Keeping Track of Change with a Change List
	Chapter 19 – Pentium: Not the Same Old Song
		Learning a Whole Different Set of Optimization Rules
		The Return of Optimization as Art
		The Pentium: An Overview
		Faster Addressing and More
		Branch Prediction
		Miscellaneous Pentium Topics
	Chapter 20 – Pentium Rules
		How Your Carbon-Based Optimizer Can Put the “Super” in Superscalar
		An Instruction in Every Pipe
		V-Pipe-Capable Instructions
		Lockstep Execution
		Superscalar Notes
	Chapter 21 – Unleashing the Pentium’s V-Pipe
		Focusing on Keeping Both Pentium Pipes Full
		Address Generation Interlocks
		Register Contention
		Who’s in First?
		Pentium Optimization in Action
	Chapter 22 – Zenning and the Flexible Mind
		Taking a Spin through What You’ve Learned
		Zenning
Part II
	Chapter 23 – Bones and Sinew
		At the Very Heart of Standard PC Graphics
		The VGA
		An Introduction to VGA Programming
		At the Core
		The Hazards of VGA Clones
		Just the Beginning
		The Macro Assembler
	Chapter 24 – Parallel Processing with the VGA
		Taking on Graphics Memory Four Bytes at a Time
		VGA Programming: ALUs and Latches
		Notes on the ALU/Latch Demo Program
	Chapter 25 – VGA Data Machinery
		The Barrel Shifter, Bit Mask, and Set/Reset Mechanisms
		VGA Data Rotation
		The Bit Mask
		The VGA’s Set/Reset Circuitry
		Notes on Set/Reset
		A Brief Note on Word OUTs
	Chapter 26 – VGA Write Mode 3
		The Write Mode That Grows on You
		A Mode Born in Strangeness
		A Note on Preserving Register Bits
	Chapter 27 – Yet Another VGA Write Mode
		Write Mode 2, Chunky Bitmaps,and Text-Graphics Coexistence
		Write Mode 2 and Set/Reset
		When to Use Write Mode 2 and When to Use Set/Reset
		Mode 13H—320x200 with 256 Colors
		Flipping Pages from Text to Graphics and Back
	Chapter 28 – Reading VGA Memory
		Read Modes 0 and 1, and the Color Don’t Care Register
		Read Mode 0
		Read Mode 1
		When all Planes “Don’t Care”
	Chapter 29 – Saving Screens and Other VGA Mysteries
		Useful Nuggets from the VGA Zen File
		Saving and Restoring EGA and VGA Screens
		16 Colors out of 64
		Overscan
		A Bonus Blanker
		Modifying VGA Registers
	Chapter 30 – Video Est Omnis Divisa
		The Joys and Galling Problems of Using Split Screens on the EGA and VGA
		How the Split Screen Works
		Setting the Split-Screen-Related Registers
		The Problem with the EGA Split Screen
		Split Screen and Panning
		Notes on Setting and Reading Registers
		Split Screens in Other Modes
		How Safe?
	Chapter 31 – Higher 256-Color Resolution on the VGA
		When Is 320x200 Really 320x400?
		Why 320x200? Only IBM Knows for Sure
		320x400 256-Color Mode
		Two 256-Color Pages
		Something to Think About
	Chapter 32 – Be It Resolved: 360x480
		Taking 256-Color Modes About as Far as the Standard VGA Can Take Them
		Extended 256-Color Modes: What’s Not to Like?
		360x480 256-Color Mode
		How 360x480 256-Color Mode Works
	Chapter 33 – Yogi Bear and Eurythmics Confront VGA Colors
		The Basics of VGA Color Generation
		VGA Color Basics
		If You Can’t Call the BIOS, Who Ya Gonna Call?
		An Example of Setting the DAC
	Chapter 34 – Changing Colors without Writing Pixels
		Special Effects through Realtime Manipulation of DAC Colors
		Color Cycling
		The Heart of the Problem
		A Test Program for Color Cycling
		Color Cycling Approaches that Work
		Odds and Ends
	Chapter 35 – Bresenham Is Fast, and Fast Is Good
		Implementing and Optimizing Bresenham’s Line-Drawing Algorithm
		The Task at Hand
		Bresenham’s Line-Drawing Algorithm
		An Implementation in C
		Comments on the C Implementation
		Bresenham’s Algorithm in Assembly
	Chapter 36 – The Good, the Bad, and the Run-Sliced
		Faster Bresenham Lines with Run-Length Slice Line Drawing
		Run-Length Slice Fundamentals
		Run-Length Slice Implementation
		Run-Length Slice Details
	Chapter 37 – Dead Cats and Lightning Lines
		Optimizing Run-Length Slice Line Drawing in a Major Way
		Fast Run-Length Slice Line Drawing
	Chapter 38 – The Polygon Primeval
		Drawing Polygons Efficiently and Quickly
		Filled Polygons
		Filling Non-Overlapping Convex Polygons
		Oddball Cases
	Chapter 39 – Fast Convex Polygons
		Filling Polygons in a Hurry
		Fast Convex Polygon Filling
		The Finishing Touch: Assembly Language
		Faster Edge Tracing
	Chapter 40 – Of Songs, Taxes, and the Simplicity of Complex Polygons
		Dealing with Irregular Polygonal Areas
		Filling Arbitrary Polygons
		Complex Polygon Filling: An Implementation
		Nonconvex Polygons
	Chapter 41 – Those Way-Down Polygon Nomenclature Blues
		Names Do Matter when You Conceptualize a Data Structure
		Nomenclature in Action
	Chapter 42 – Wu’ed in Haste; Fried, Stewed at Leisure
		Fast Antialiased Lines Using Wu’s Algorithm
		Wu Antialiasing
		Tracing and Intensity in One
		Sample Wu Antialiasing
	Chapter 43 – Bit-Plane Animation
		A Simple and Extremely Fast Animation Method for Limited Color
		Bit-Planes: The Basics
		Bit-Plane Animation in Action
		Limitations of Bit-Plane Animation
		Shearing and Page Flipping
		Beating the Odds in the Jaw-Dropping Contest
	Chapter 44 – Split Screens Save the Page Flipped Day
		640x480 Page Flipped Animation in 64K…Almost
	Chapter 45 – Dog Hair and Dirty Rectangles
		Different Angles on Animation
		Plus ça Change
		VGA Access Times
		Dirty-Rectangle Animation
		Dirty Rectangles in Action
		Hi-Res VGA Page Flipping
		Another Interesting Twist on Page Flipping
	Chapter 46 – Who Was that Masked Image?
		Optimizing Dirty-Rectangle Animation
	Chapter 47 – Mode X: 256-Color VGA Magic
		Introducing the VGA’s Undocumented “Animation-Optimal” Mode
		What Makes Mode X Special?
		Selecting 320x240 256-Color Mode
		Designing from a Mode X Perspective
		Hardware Assist from an Unexpected Quarter
	Chapter 48 – Mode X Marks the Latch
		The Internals of Animation’s Best Video Display Mode
		Allocating Memory in Mode X
		Copying Pixel Blocks within Display Memory
		Who Was that Masked Image Copier?
	Chapter 49 – Mode X 256-Color Animation
		How to Make the VGA Really Get up and Dance
		Masked Copying
		Animation
		Mode X Animation in Action
		Works Fast, Looks Great
	Chapter 50 – Adding a Dimension
		3-D Animation Using Mode X
		References on 3-D Drawing
		The 3-D Drawing Pipeline
		A Simple 3-D Example
		An Ongoing Journey
	Chapter 51 – Sneakers in Space
		Using Backface Removal to Eliminate Hidden Surfaces
		One-sided Polygons: Backface Removal
		Incremental Transformation
		A Note on Rounding Negative Numbers
		Object Representation
	Chapter 52 – Fast 3-D Animation: Meet X-Sharp
		The First Iteration of a Generalized 3-D Animation Package
		This Chapter’s Demo Program
		A New Animation Framework: X-Sharp
		Three Keys to Realtime Animation Performance
	Chapter 53 – Raw Speed and More
		The Naked Truth About Speed in 3-D Animation
		Raw Speed, Part 1: Assembly Language
		Raw Speed, Part II: Look it Up
	Chapter 54 – 3-D Shading
		Putting Realistic Surfaces on Animated 3-D Objects
		Support for Older Processors
	Chapter 55 – Color Modeling in 256-Color Mode
		Pondering X-Sharp’s Color Model in an RGB State of Mind
	Chapter 56 – Pooh and the Space Station
		Using Fast Texture Mapping to Place Pooh on a Polygon
		Principles of Quick-and-Dirty Texture Mapping
		Fast Texture Mapping: An Implementation
	Chapter 57 – 10,000 Freshly Sheared Sheep on the Screen
		The Critical Role of Experience in Implementing Fast, Smooth Texture Mapping
	Chapter 58 – Heinlein’s Crystal Ball, Spock’s Brain, and the 9-Cycle Dare
		Using the Whole-Brain Approach to Accelerate Texture Mapping
		Texture Mapping Redux
		That’s Nice—But it Sure as Heck Ain’t 9 Cycles
		Texture Mapping Notes
	Chapter 59 – The Idea of BSP Trees
		What BSP Trees Are and How to Walk Them
		BSP Trees
		Building a BSP Tree
		Inorder Walks of BSP Trees
		Surfing Amidst the Trees
	Chapter 60 – Compiling BSP Trees
		Taking BSP Trees from Concept to Reality
		Compiling BSP Trees
		Optimizing the BSP Tree
		BSP Optimization: an Undiscovered Country
	Chapter 61 – Frames of Reference
		The Fundamentals of the Math behind 3-D Graphics
		The Dot Product
		Cross Products and the Generation of Polygon Normals
		Using the Sign of the Dot Product
		Using the Dot Product for Projection
		Rotation by Projection
	Chapter 62 – One Story, Two Rules, and a BSP Renderer
		Taking a Compiled BSP Tree from Logical to Visual Reality
		Moving the Viewer
		Transformation into Viewspace
		Clipping
		Projection to Screenspace
		Walking the Tree, Backface Culling and Drawing
	Chapter 63 – Floating-Point for Real-Time 3-D
		Knowing When to Hurl Conventional Math Wisdom Out the Window
		Not Your Father’s Floating-Point
		Pentium Floating-Point Optimization
		The Dot Product
		The Cross Product
		Transformation
		Projection
		Rounding Control
		A Farewell to 3-D Fixed-Point
	Chapter 64 – Quake’s Visible-Surface Determination
		The Challenge of Separating All Things Seen from All Things Unseen
		VSD: The Toughest 3-D Challenge of All
		The Structure of Quake Levels
		Culling and Visible Surface Determination
		Overdraw
		The Beam Tree
		3-D Engine du Jour
		Breakthrough!
		Simplify, and Keep on Trying New Things
		Learn Now, Pay Forward
		References
	Chapter 65 – 3-D Clipping and Other Thoughts
		Determining What’s Inside Your Field of View
		3-D Clipping Basics
		Polygon Clipping
		Advantages of Viewspace Clipping
		Further Reading
	Chapter 66 – Quake’s Hidden-Surface Removal
		Struggling with Z-Order Solutions to the Hidden Surface Problem
		Creative Flux and Hidden Surfaces
		Sorted Spans
		Edges versus Spans
		Edge-Sorting Keys
		Decisions Deferred
	Chapter 67 – Sorted Spans in Action
		Implementing Independent Span Sorting for Rendering without Overdraw
		Quake and Sorted Spans
		Types of 1/z Span Sorting
		1/z Span Sorting in Action
	Chapter 68 – Quake’s Lighting Model
		A Radically Different Approach to Lighting Polygons
		The Lighting Conundrum
		Gouraud Shading
		The Quest for Alternative Lighting
		Surface Caching
	Chapter 69 – Surface Caching and Quake’s Triangle Models
		Probing Hardware-Assisted Surfaces and Fast Model Animation Without Sprites
		Surface Caching with Hardware Assistance
		Drawing Triangle Models
	Chapter 70 – Quake: A Post-Mortem and a Glimpse into the Future
		Preprocessing the World
		The Potentially Visible Set (PVS)
		Passages: The Last-Minute Change that Didn’t Happen
		Drawing the World
		Rasterization
		Entities
		How We Spent Our Summer Vacation: After Shipping Quake
		Looking Forward
Afterword
About this version