Graphics Gems (eBook)

Front Cover 1
Graphics Gems 4
Copyright Page 5
Table of Contents 8
Preface 16
Introduction 18
Mathematical Notation 20
Pseudo-Code 22
Contributors 27
CHAPTER 1. 2D GEOMETRY 32
Useful 2D Geometry 34
Trigonometry Summary 43
Useful Trigonometry 44
Trigonometric Functions at Select Points 49
Triangles 51
Generating Random Points in Triangles 55
Fast Line–Edge Intersections on a Uniform Grid 60
Anti-Aliasing Summary 68
Area of Intersection: Circle and a Half-Plane 69
Area of Intersection: Circle and a Thick Line 71
Area of Intersection: Two Circles 74
Vertical Distance from a Point to a Line 78
A Fast 2D Point-on-Line Test 80
Fast Circle–Rectangle Intersection Checking 82
CHAPTER 2. 2D RENDERING 86
Circles of Integral Radius on Integer Lattices 88
Nice Numbers for Graph Labels 92
Efficient Generation of Sampling Jitter Using Look-up Tables 95
Scan Conversion Summary 106
Fast Anti-Aliasing Polygon Scan Conversion 107
Generic Convex Polygon Scan Conversion and Clipping 115
Concave Polygon Scan Conversion 118
Fast Scan Conversion of Arbitrary Polygons 123
Line-Drawing Summary 129
Digital Line Drawing 130
Symmetric Double Step Line Algorithm 132
Rendering Anti-Aliased Lines 136
An Algorithm for Filling in 2D Wide Line Bevel Joints 138
Rendering Fat Lines on a Raster Grid 145
Two-Dimensional Clipping: A Vector-Based Approach 152
Periodic Tilings of the Plane on a Raster Grid 160
CHAPTER 3. IMAGE PROCESSING 172
Anti-Aliasing Filters Summary 174
Convenient Anti-Aliasing Filters That Minimize "Bumpy" Sampling 175
Filters for Common Resampling Tasks 178
Smoothing Enlarged Monochrome Images 197
Median Finding on a 3 X 3 Grid 202
Ordered Dithering 207
A Fast Algorithm for General Raster Rotation 210
Useful 1-to-1 Pixel Transforms 227
Alpha Blending 241
CHAPTER 4. FRAME BUFFER TECHNIQUES 244
Frame Buffers and Color Maps 246
Reading a Write-Only Write Mask 250
A Digital "Dissolve" Effect 252
Mapping RGB Triples onto Four Bits 264
What Are the Coordinates of a Pixel? 277
Proper Treatment of Pixels as Integers 280
Normal Coding 288
Recording Animation in Binary Order for Progressive Temporal Refinement 296
1 -to-1 Pixel Transforms Optimized through Color-Map Manipulation 301
A Seed Fill Algorithm 306
Filling a Region in a Frame Buffer 309
Precalculating Addresses for Fast Fills, Circles, and Lines 316
A Simple Method for Color Quantization: Octree Quantization 318
CHAPTER 5. 3D GEOMETRY 326
Useful 3D Geometry 328
An Efficient Bounding Sphere 332
Intersection of Two Lines in Three-Space 335
Intersection of Three Planes 336
Mapping Summary 337
Digital Cartography for Computer Graphics 338
Albers Equal-Area Conic Map Projection 352
Boxes and Spheres Summary 357
Spheres-to-Voxels Conversion 358
A Simple Method for Box-Sphere Intersection Testing 366
CHAPTER 6. 3D RENDERING 372
3D Grid Hashing Function 374
Backface Culling 377
Fast Dot Products for Shading 379
Scanline Depth Gradient of a Z-Bufifered Triangle 392
Simulating Fog and Haze 395
Interpretation of Texture Map Indices 397
Multidimensional Sum Tables 407
CHAPTER 7. RAY TRACING 414
A Simple Ray Rejection Test 416
Ray–Object Intersection Summary 418
Intersection of a Ray with a Sphere 419
An Efficient Ray–Polygon Intersection 421
Fast Ray–Polygon Intersection 425
Fast Ray–Box Intersection 426
Shadow Attenuation for Ray Tracing Transparent Objects 428
CHAPTER 8. NUMERICAL AND PROGRAMMING TECHNIQUES 432
Root Finding Summary 434
Cubic and Quartic Roots 435
A Bézier Curve-Based Root-Finder 439
Using Sturm Sequences to Bracket Real Roots of Polynomial Equations 447
Distance Measures Summary 454
A High-Speed, Low Precision Square Root 455
A Fast Approximation to the Hypotenuse 458
A Fast Approximation to 3D Euclidean Distance 463
Full-Precision Constants 465
Converting between Bits and Digits 466
Storage-free Swapping 467
Generating Random Integers 469
Fast 2D–3D Rotation 471
Bit Patterns for Encoding Angles 473
Bit Interleaving for Quad- or Octrees 474
A Fast HSL-to-RGB Transform 479
CHAPTER 9. MATRIX TECHNIQUES 482
Matrix Identities 484
Rotation Matrix Methods Summary 486
Transforming Axes 487
Fast Matrix Multiplication 491
A Virtual Trackball 493
Matrix Orthogonalization 495
Rotation Tools 496
Matrix Inversion 501
Matrices and Transformations 503
Efficient Post-Concatenation of Transformation Matrices 507
CHAPTER 10. MODELING AND TRANSFORMATIONS 514
Transformation Identities 516
Fixed-Point Trigonometry with CORDIC Iterations 525
Using Quaternions for Coding 3D Transformations 529
3D Viewing and Rotation Using Orthonormal Bases 547
The Use of Coordinate Frames in Computer Graphics 553
Forms, Vectors, and Transforms 564
Properties of Surface-Normal Transformations 570
Transforming Axis-Aligned Bounding Boxes 579
Constructing Shapes Summary 582
Defining Surfaces from Sampled Data 583
Defining Surfaces from Contour Data 589
Computing Surface Normals for 3D Models 593
Calculation of Reference Frames along a Space Curve 598
CHAPTER 11. CURVES AND SURFACES 604
Planar Cubic Curves 606
Explicit Cubic Spline Interpolation Formulas 610
Fast Spline Drawing 616
Some Properties of Bézier Curves 618
Tutorial on Forward Differencing 625
Integration of Bernstein Basis Functions 635
Solving the Nearest-Point-on-Curve Problem 638
An Algorithm for Automatically Fitting Digitized Curves 643
APPENDIX I: C UTILITIES 658
Graphics Gems C Header File 660
2D and 3D Vector C Library 664
Memory Allocation in C 674
Two Useful C Macros 675
How To Build Circular Structures in C 676
How To Use C Register Variables to Point to 2D Arrays 677
APPENDIX II: C IMPLEMENTATIONS 678
Generating Random Points in Triangles 680
A Fast 2D Point-on-Line Test 685
Fast Circle–Rectangle Intersection Checking 687
Nice Numbers for Graph Labels 688
Efficient Generation of Sampling Jitter Using Look-Up Tables 691
Fast Anti-Aliasing Polygon Scan Conversion 693
Generic Convex Polygon Scan Conversion and Clipping 698
Concave Polygon Scan Conversion 712
Digital Line Drawing 716
Symmetric Double Step Line Algorithm 717
Rendering Anti-Aliased Lines 721
Two-Dimensional Clipping: A Vector-Based Approach 725
Median Finding on A 3×3 Grid 742
Ordered Dithering 744
A Digital "Dissolve" Effect 746
Mapping Rgb Triples onto Four Bits 749
Proper Treatment of Pixels as Integers 750
Recording Animation in Binary Order for Progressive Temporal Refinement 751
A Seed Fill Algorithm 752
An Efficient Bounding Sphere 754
Albers Equal-Area Conic Map Projection 757
A Simple Method for Box–Sphere Intersection Testing 761
3D Grid Hashing Function 764
An Efficient Ray –Polygon Intersection 766
Fast Ray–Box Intersection 767
Cubic and Quartic Roots 769
Using Sturm Sequences to Bracket Real Roots of Polynomial Equations 774
A High-Speed, Low Precision Square Root 787
A Fast Approximation to The Hypotenuse 789
Bit Interleaving for Quad- Or Octrees 790
A Fast Hsl-To-Rgb Transform 794
Matrix Orthogonalization 796
Efficient Post-Concatenation of Transformation Matrices 801
Fixed-Point Trigonometry with Cordic Iterations 804
Using Quaternions for Coding 3D Transformations 806
3D Viewing and Rotation Using Orthonormal Bases 809
Forms, Vectors, and Transforms 811
Transforming Axis-Aligned Bounding Boxes 816
Solving The Nearest-Point-On-Curve Problem and A Bézier Curve-Based Root-Finder 818
An Algorithm for Automatically Fitting Digitized Curves 828
References 839
Index 853