"The GRAPHICS GEMS Series" was started in 1990 by Andrew Glassner. The vision and purpose of the Series was - and still is - to provide tips, techniques, and algorithms for graphics programmers. All of the gems are written by programmers who work in the field and are motivated by a common desire to share interesting ideas and tools with their colleagues. Each volume provides a new set of innovative solutions to a variety of programming problems.

PrefaceIntroductionMathematical NotationPseudo-CodeContributors1 2D Geometry Useful 2D Geometry Trigonometry Summary Useful Trigonometry Trigonometric Functions at Select Points Triangles Generating Random Points in Triangles (649) Fast Line-Edge Intersections on a Uniform Grid (651) Anti-Aliasing Summary Area of Intersection: Circle and a Half-Plane Area of Intersection: Circle and a Thick Line Area of Intersection: Two Circles Vertical Distance from a Point to a Line A Fast 2D Point-on-Line Test (654) Fast Circle-Rectangle Intersection Checking (656)2 2D Rendering Circles of Integral Radius on Integer Lattices Nice Numbers for Graph Labels (657) Efficient Generation of Sampling Jitter Using Look-up Tables (660) Scan Conversion Summary Fast Anti-Aliasing Polygon Scan Conversion (662) Generic Convex Polygon Scan Conversion and Clipping (667) Concave Polygon Scan Conversion (681) Fast Scan Conversion of Arbitrary Polygons Line-Drawing Summary Digital Line Drawing (685) Symmetric Double Step Line Algorithm (686) Rendering Anti-Aliased Lines (690) An Algorithm for Filling in 2D Wide Line Bevel Joints Rendering Fat Lines on a Raster Grid Two-Dimensional Clipping: A Vector-Based Approach (694) Periodic Tilings of the Plane on a Raster Grid3 Image Processing Anti-Aliasing Filters Summary Convenient Anti-Aliasing Filters that Minimize "Bumpy" Sampling Filters for Common Resampling Tasks Smoothing Enlarged Monochrome Images Median Finding on a 3 X 3 Grid (711) Ordered Dithering (713) A Fast Algorithm for General Raster Rotation Useful 1-to-1 Pixel Transforms Alpha Blending4 Frame Buffer Techniques Frame Buffers and Color Maps Reading a Write-Only Write Mask A Digital "Dissolve" Effect (715) Mapping RGB Triples onto Four Bits (718) What are the Coordinates of a Pixel? Proper Treatment of Pixels as Integers (719) Normal Coding Recording Animation in Binary Order for Progressive Temporal Refinement (720) 1-to-1 Pixel Transforms Optimized Through Color-Map Manipulation A Seed Fill Algorithm (721) Filling a Region in a Frame Buffer Precalculating Addresses for Fast Fills, Circles, and Lines A Simple Method for Color Quantization: Octree Quantization5 3D Geometry Useful 3D Geometry An Efficient Bounding Sphere (723) Intersection of Two Lines in Three-Space Intersection of Three Planes Mapping Summary Digital Cartography for Computer Graphics Albers Equal-Area Conic Map Projection (726) Boxes and Spheres Summary Spheres-to-Voxels Conversion A Simple Method for Box-Sphere Intersection Testing (730)6 3D Rendering 3D Grid Hashing Function (733) Backface Culling Fast Dot Products for Shading Scanline Depth Gradient of a Z-Buffered Triangle Simulating Fog and Haze Interpretation of Texture Map Indices Multidimensional Sum Tables7 Ray Tracing A Simple Ray Rejection Test Ray-Object Intersection Summary Intersection of a Ray with a Sphere An Efficient Ray-Polygon Intersection (735) Fast Ray-Polygon Intersection Fast Ray-Box Intersection (736) Shadow Attenuation for Ray Tracing Transparent Objects8 Numerical and Programming Techniques Root Finding Summary Cubic and Quartic Roots (738) A Bézier Curve-Based Root-Finder (787) Using Sturm Sequences to Bracket Real Roots of Polynomial Equations (743) Distance Measures Summary A High-Speed, Low Precision Square Root (756) A Fast Approximation to the Hypotenuse (758) A Fast Approximation to 3D Euclidean Distance Full-Precision Constants Converting Between Bits and Digits Storage-Free Swapping Generating Random Integers Fast 2D-3D Rotation Bit Patterns for Encoding Angles Bit Interleaving for Quad- or Octrees (759) A Fast HSL-to-RGB Transform (763)9 Matrix Techniques Matrix Identities Rotation Matrix Methods Summary Transforming Axes Fast Matrix Multiplication A Virtual Trackball Matrix Orthogonalization (765) Rotation Tools Matrix Inversion (766) Matrices and Transformations Efficient Post-Concatenation of Transformation Matrices (770)10 Modeling and Transformations Transformation Identities Fixed-Point Trigonometry with CORDIC Iterations (773) Using Quaternions for Coding 3D Transformations (775) 3D Viewing and Rotation Using Orthonormal Bases (778) The Use of Coordinate Frames in Computer Graphics Forms, Vectors, and Transforms (780) Properties of Surface-Normal Transformations Transforming Axis-Aligned Bounding Boxes (785) Constructing Shapes Summary Defining Surfaces from Sampled Data Defining Surfaces from Contour Data Computing Surface Normals for 3D Models Calculation of Reference Frames Along a Space Curve11 Curves and Surfaces Planar Cubic Curves Explicit Cubic Spline Interpolation Formulas Fast Spline Drawing Some Properties of Bézier Curves Tutorial on Forward Differencing Integration of Bernstein Basis Functions Solving the Nearest-Point-on-Curve Problem (787) An Algorithm for Automatically Fitting Digitized Curves (797)C Appendix I: C Utilities Graphics Gems C Header File 2D and 3D Vector C Library Memory Allocation in C Two Useful C Macros How To Build Circular Structures in C How To Use C Register Variables to Point to 2D ArraysC Appendix 2: C Implementations The C Code Follows the Same Order as the GemsReferencesIndex