Graphics Gems

Preface

Introduction

Mathematical Notation

Pseudo-Code

Contributors


1 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 Grid


3 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 Blending


4 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 Quantization


5 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 Tables


7 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 Objects


8 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 Curve


11 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 Arrays

C Appendix 2: C Implementations

The C Code Follows the Same Order as the Gems

References

Index